Algorithm engineering and experimentation

Symmetric multiprocessors (SMPs) are dominant in the high-end server market and are key for large-scale multiprocessor systems. However, designing efficient parallel algorithms for this platform presents challenges due to the rapid increase in microprocessor speed, which has made main memory access the main performance bottleneck. Consequently, merely increasing the number of processors does not guarantee improved performance, as memory bus limitations typically restrict SMPs to 16 processors. This situation has two implications for algorithm designers: first, parallel algorithms must compete effectively with their sequential counterparts using as few as one processor; second, to scale well with the number of processors, algorithms must minimize both the number and type of main memory accesses. This paper introduces a computational model for developing efficient algorithms for symmetric multiprocessors. Using this model, we derive efficient solutions for two distinct problem types: linked list prefix computations and generalized sorting. Both problems are memory-intensive but differ in their access patterns. Generalized sorting algorithms often require numerous memory accesses to contiguous locations, while prefix computation algorithms need fewer accesses, typically to non-contiguous memory locations.