ISSN:
1436-5057
Keywords:
68Q20
;
90C39
;
65F
;
Semigroup computation
;
broadcasting
;
mesh-connected computers with segmented buses
;
reconfigurable buses
;
parametric parallel algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Wir stellen einen Algorithmus für die Halbgruppenberechnung auf Gittern mit rekonfigurierbaren Bussen (MRB) vor. Mitn Operanden kann unser Algorithmus in $$O(2^{(2c^2 + 3c)/(4c + 1)} n^{1/(8c + 2)} )$$ Zeit ausgeführt werden, wennn Prozessoren in einem $$2^{(c^2 - c)/(8c + 2)} n^{1/(5c + 1)/(8c + 2)} \times 2^{(c - c^2 )/(8c + 2)} n^{(3e + 1)/(8c + 2)} $$ MRB-Gitter zur Verfügung stehen. Dabei gilt $$0 \leqslant c \leqslant O(\sqrt {\log _2 n} )$$ . Fürc=0 bedeutet dies $$O(\sqrt n )$$ Zeit für den $$\sqrt n \times \sqrt n $$ MRB und stimmt mit dem Wert für Gitter ohne Busse überein; fürc=1 ist nurO(n 1/10) Zeit für einenn 3/5×n 2/5 MRB erforderlich, was mit einem früheren Ergebnis für Berechnung auf Gittern mit mehreren segmentierten Bussen übereinstimmt; fürc=2 istO(n 1/18) Zeit für einen 21/9 n 11/18×2−1/9 n 7/18 MRB erforderlich; für $$c = O(\sqrt {\log _2 n} )$$ istO(log2 n) Zeit erforderlich, was auch mit dem früheren Ergebnis über MRB übereinstimmt. Unsere Resultate können also als vereinheitlichte Darstellung der bekanntesten Ergebnisse bei verschiedenen Modellen des Parallel-Computing angesehen werden.
Notes:
Abstract In this paper, we present a new parametric parallel algorithm for semigroup computation on mesh with reconfigurable buses (MRB). Givenn operands, our parallel algorithm can be performed in $$O(2^{(2c^2 + 3c)/(4c + 1)} n^{1/(8c + 2)} )$$ , time on a $$2^{(c^2 - c)/(8c + 2)} n^{(5c + 1)/(8c + 2)} \times 2^{(c - c^2 )/(8c + 2)} n^{(3c + 1)/(8c + 2)} $$ MRB ofn processors, where $$0 \leqslant c \leqslant O(\sqrt {\log _2 n} )$$ . Specifically, whenc=0, it takes $$O(\sqrt n )$$ time on the $$\sqrt n \times \sqrt n $$ MRB and is equal to the result on the mesh-connected computers; whenc=1, it takesO(n 1/10) time on then 3/5×n 2/5 MRB and is equal to the previous result on the mesh-connected computers with segmented multiple buses; whenc=2, it takesO(n 1/18) time on the 21/9 n 11/18×2(−1/9) n 7/18 MRB; when $$O(\sqrt {\log _2 n} )$$ , it takesO(log2 n) time and is equal to the previous result on the MRB. Consequently, our results can be viewed as a unification of some best known results on different parallel computational models.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02247408
Permalink
