SIMD:
"Single Instruction, Multiple Data"; i.e. when a single instruction executes an
operation on a group of data items in parallel. What it specifically means
depends very much on the capabilities of a specific machine.
to vectorize:
To (re-)arrange a program such that data format, data storage, data flow, as
well as computational operations and control flow can be done with (a
particular set of) SIMD semantics.
vectorization overhead:
The loss of efficiency incurred as a side effect of (re-)arrangement of data
format, data storage, data flow, as well as computational operations and
control flow for (a particular set of) SIMD semantics.
vectorizable:
When an abstract algorithm can be vectorized in an obvious or straight
forward way, it is said to be vectorizable.
practically vectorizable:
When the "optimal" SIMD implementation of a vectorizable algorithm actually
performs substantially better than the "optimal" scalar implementation, then
the algorithm is said to be practically vectorizable. This depends heavily on
the vectorization overhead of a particular machine.
SIMOMD:
"Single Instruction, Multiple Operations, Multiple Data"; i.e. a machine
where a single instruction executes a particular pattern of operations on a
group of data items in parallel. Surprisingly, this model is not fundamentally
more powerful than plain SIMD. But the availability of such instructions can
significantly enlarge the set of practically vectorizable algorithms.
The above definitions of terms and concepts may have their flaws, but hopefully they serve to illustrate that vectorization is not (yet) a well defined concept. Instead, its meaning varies widely depending on the specific machines that we have at our disposal. The definition of "practically vectorizable" may seem pedantic and redundant, but I find it important to notice that only a small subset of algorithms is of practical interest for vectorization. On the one hand that means SIMD computing might be confined to a small niche. But on the other hand it means that this niche has a lot of room to potentially grow into.
I believe in scientific exploration, therefor I propose to pursue a grander vision of vectorization. As of this writing in 2009, the end of the road for further advancements in semiconductor fabrication technology is in sight. Soon all the low hanging fruit will have been picked, so our only choice is to look for other trees to harvest. One such tree could be a vectorization like the following:
to vectorize:
To look for SIMD primitives that extend the possibilities for data formats,
data storage, data flow, as well as computational operations and control flow
in practically viable ways. Hopefully this would grow the set of practically
vectorizable algorithms significantly enough to make a notable difference
almost no matter what applications you care for.
This is what vectorizer.org exists for:
to make a broader collection of algorithms practically vectorizable by making the concept of vectorization more general.