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
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.