"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 (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.
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.
When an abstract algorithm can be vectorized in an obvious or straight forward way, it is said to be 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.
"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 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.