Halide Talk

This is what I was trying to get at - using column vectors gives good cache locality and lets you use SIMD for "multiply all of these by this scalar" for each column, and then for "sum all of these" for the resulting rows. I'd imagine it could also let you optimize multiplications into things like bit-shifts with minimal overhead as well, though I have no idea if that's done in practice. Maybe only tangentially related, but I feel like this talk on Halide[0] is really illustrative of the general concepts. As others have mentioned, for some operations it can also save you from loading whole columns that aren't relevant for your transformation. The compression point in the sibling comment is definitely also relevant, especially for serialization. A whole lot of reasons to use column vectors. Using "column-major" here might've been terminology abuse; sorry for the confusion. [0] ▶ this video

▶ this video Here is a relevant video from the creator. It has some fun illustrations to help with what its going on. /edit - letters

please look at link and especially ▶ this video they seem to open new ground in the area you are prusuing edit: if you know any other groups/ppl who practice a similar approach send them my way anyhow, it seems like the hand written assembly vs compiled code goes in to a new skirmish the age where the whole spectrum from generalcpu > asic becomes available to programmers all around bottle necks of parallelism, locality and redundancy seems to be the guiding lights hand written we'll be probably lead by the magnificent link compiler generated by halide and the like and once we got the ball rolling and more public knowledge is available probably the locked down techniques of the major supercomputers will start to emerge ( i just assume pps from the supercomputers area have been dealing with this stuff for the last couple of decades ) can i spit some more, dear hacker news? focus, you gotta focus, forget about the compiler generating good code, it's all about the ability for us humans to explore the domain even in halide, they mention the point that you still need to sit down and code different approaches, but their tool makes it a breeze compared to exploring those different approaches using hand written assembly

A really nice video with animations of various scheduling approaches for these types of linear algebra algorithms: ▶ this video

You can see it a little bit in the blur example on the front page: the blur algorithm is described in two lines and the optimizations are described separately in the "schedule" below. In this case the schedule specifies that intermediate results should be computed in tiles of a certain size, and the whole thing is both vectorized and parallelized. The best way to understand it is probably to watch the video, which is relatively long but explains things clearly: ▶ this video

Halide! That's the one I was thinking of: ▶ this video I'd love to find out if this could be a more generally-applicable technique, but it's fascinating regardless.

Halide is an interesting direction for generating optimized code. By isolating algorithm from schedule, it is better able to optimize for vectorization, locality, pipelining, threading, tiling, and recomputation vs. storage. It then uses LLVM to do all the ordinary optimization. Example code: // The algorithm - no storage or order blur_x(x, y) = (input(x-1, y) + input(x, y) + input(x+1, y))/3; blur_y(x, y) = (blur_x(x, y-1) + blur_x(x, y) + blur_x(x, y+1))/3; // The schedule - defines order, locality; implies storage blur_y.tile(x, y, xi, yi, 256, 32) .vectorize(xi, 8).parallel(y); blur_x.compute_at(blur_y, x).vectorize(x, 8); Halide can auto-optimize to create schedules for specific architectures, which can match or exceed performance of C code written by experts. It's intended for image processing, and has an unnatural affinity for rectangles, but it's an interesting direction for optimization. Darkroom does similar optimization for FPGAs Website: link Video: ▶ this video Paper: link