Multiple Byte Processing with Full-Word Instructions

My algorithms for parallelizing loops, described in papers starting with [9], were rather inefficient. They could be sped up with parallel execution on an array processor like the Illiac-IV. But I realized one could do even better than the 64-times speedup provided by the Illiac’s 64 processors. Each datum being manipulated was just a few bits, so I had the idea of packing several of the data into a single word and manipulating them simultaneously. Not only could this speed computation on the Illiac, but it allowed one to do array processing on an ordinary uniprocessor. This paper describes general techniques for doing such parallel computation on packed data. It’s a neat hack, and it’s more useful now than it was then for two reasons. The obvious reason is that word size is larger now, with many computers having 64-bit words. The less obvious reason is that conditional operations are implemented with masking rather than branching. Instead of branching around the operation when the condition is not met, masks are constructed so the operation is performed only on those data items for which the condition is true. Branching is more costly on modern multi-issue computers than it was on the computers of the 70s.