1990 · 274 citations · 0 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureParallel AlgorithmsParallel ComputingMultiprocessor SystemsParallel Algorithm DesignParallel ArchitecturesParallel ComputationParallel Computer ArchitectureShared-memory ParallelismParallel Computing InterconnectsShared MemoryShared-memory AlgorithmsShared-memory ArchitectureVlsi Implementation
Parallel computation is rapidly becoming a dominant theme across computer science, with expectations that nearly all future developments in architecture, systems, applications, and algorithm design will occur within a parallel context, prompting theoretical work on parallel algorithms and architectures and the exploration of diverse abstract models constrained by communication limits. The authors focus on VLSI models, which examine the technological limits of current chips by packing gates and wires into a small number of planar layers. This chapter discusses parallel algorithms for shared‑memory machines.
Publisher Summary This chapter discusses parallel algorithms for shared-memory machines. Parallel computation is rapidly becoming a dominant theme in all areas of computer science and its applications. It is estimated that, within a decade, virtually all developments in computer architecture, systems programming, computer applications and the design of algorithms will be taking place within the context of parallel computation. In preparation for this revolution, theoretical computer scientists have begun to develop a body of theory centered on parallel algorithms and parallel architectures. As there is no consensus yet on the appropriate logical organization of a massively parallel computer, and as the speed of parallel algorithms is constrained as much by limits on interprocessor communication as it is by purely computational issues, it is not surprising that a variety of abstract models of parallel computation have been pursued. Closest to the hardware level are the VLSI models, which focus on the technological limits of today's chips, in which gates and wires are packed into a small number of planar layers.