Can parallel algorithms enhance serial implementation?
Uzi Vishkin · Communications of the ACM · 1996
Performance improvement is a fundamental concern in computer science and engineering.Observing the history of the field, one would expect that any improvement in the ability of computer systems would be quickly met by applications utilizing it.Over the last few decades, much effort has been invested in seeking gains in performance by using parallel computers.However, the state of the art is that the programming models for many available parallel computers do not make them very easy to program.In contrast, this article presents a software-centric approach, in which ease of programming is a first priority for both uniprocessors and multiprocessors.Here, I outline two concrete reasons and one general reason why parallel programs could give a (modest) gain in performance over serial code on uniprocessors, especially with the current trends in uniprocessor architecture. Hiding latency to memory through prefetching.In a parallel program with p-fold parallelism it is possible to prefetch data p steps ahead of when it needed, since there are p tasks to execute while waiting for the result.If the available bandwidth permits these p prefetches, then this will make all references appear as if they are in fast cache memory, rather than in slower main memory.The response rate of main memory then becomes limited by total bandwidth to that memory, but it is no longer strictly limited by latency to main memory.Increased bandwidth can be bought, and the price is dropping.Decreasing latency is much more difficult, and large improvements appear to be problematic. Instruction-level parallelism.A parallel program should provide a much higher degree of instruction level parallelism (ILP) than a serial program.The extensive use of ILP is one of the most important advances made in commodity processors over the past decade.However, current designs are approaching, if not hitting, the limit in terms of how much inherent parallelism appears in standard serial programs.To show the increasing role that ILP plays in computer architecture, we need only to note that nearly 20% of [2] is devoted to that issue.See references therein to quite a few processors using ILP that were announced in 1994--95 by many major computer vendors. State changes. Consider an instantaneous description