A parametric algorithm for semigroup computation on mesh with buses

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 2^1/9 n ^11/18×2^(−1/9) n ^7/18 MRB; when$O(\sqrt {\log _2 n} )$, it takesO(log₂ 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.

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 2^1/9 n ^11/18×2^−1/9 n ^7/18 MRB erforderlich; für$c = O(\sqrt {\log _2 n} )$ istO(log₂ 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.