Algorithms for Modern Vector Processor Architectures

Modern computers are incredibly fast; in a single second they can perform several billion ‘simple operations’, such as additions, subtractions and multiplications. To utilize computers to the fullest, researchers have long been studying algorithms, which are efficient solutions to computational problems. Most new computers now ship with powerful vector processors which allow multiple operations to be executed in parallel, making computers even better at processing data. This has opened a new avenue of algorithms research allowing for interesting new results, which is what this project will explore.

The most common type of vector processors is called single instruction, multiple data (SIMD). As the name implies, a single instruction is applied to multiple data simultaneously. The figure shows the addition of two SIMD vectors of eight elements each on the left, and an addition of two numbers on normal hardware on the right. On a computer with good SIMD hardware, these two operations take approximately the same amount of time. The question is, how much of this increased processing power can we actually harness?

SIMD has been used to solve certain types of problems to great effect, such as various multi-media operations that process large amounts of data and relies heavily on arithmetic operations. What we are interested in knowing is to what extent SIMD can be useful to solve more general problems such as for instance maintaining a dictionary and allowing you to look up certain words efficiently. Many solutions in use in the industry are based on previously developed algorithms that did not rely on the existence of vector hardware.  Hence, they might not immediately work well with the new operations SIMD enables. As such, improving existing algorithms by using SIMD is not only an interesting challenge; there is also the potential to have a real and significant impact on real world computing. Modern computers are marvels of engineering; it would be a shame to not utilize the full power they offer.