PROCESSOR-TIME TRADEOFFS UNDER BOUNDED-SPEED MESSAGE PROPAGATION .1. UPPER-BOUNDS

Citation
G. Bilardi et Fp. Preparata, PROCESSOR-TIME TRADEOFFS UNDER BOUNDED-SPEED MESSAGE PROPAGATION .1. UPPER-BOUNDS, theory of computing systems, 30(6), 1997, pp. 523-546
Citations number
8
Categorie Soggetti
System Science",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
Volume
30
Issue
6
Year of publication
1997
Pages
523 - 546
Database
ISI
SICI code
Abstract
Upper bounds are derived for the processor-time tradeoffs of machines such as linear arrays and two-dimensional meshes, which are compatible with the physical limitation expressed by bounded-speed propagation o f messages (due to the finiteness of the speed of light). It is shown that parallelism and locality combined may yield speedups superlinear in the number of processors. The speedups are inherent, due to the opt imality of the obtained tradeoffs as established in a companion paper. Simulations of multiprocessor machines are developed by analogous mac hines with fewer processors. A crucial role is played by the hierarchi cal nature of the memory system. A divide-and-conquer technique for hi erarchical memories is developed, based on the graph-theoretic notion of a topological separator. For multiprocessors, this technique also r equires a careful balance of memory access and interprocessor communic ation costs, which leads to nonintuitive orchestrations of the simulat ion process.