AbstractEmbedding one parallel architecture into another is very important in the area of parallel processing because parallel architectures can vary widely. Given a pyramid architecture of (4N-1)/3 nodes and height N, this paper presents a mapping method to embed the pyramid architecture into a ((4k+1+2)/3) x 2N-1-k x 2N-1-k mesh for 0 <= k <= N-1. Our method has dilation max {4k, 2N-2-k }and expansion 1+(2/(4k+1). When k=(N-2)/3, the pyramid can be embedded into a (4(N+1)/3+2)/3 x 2(2N-1)/3 x 2(2N-1)/3 mesh with dilation 2(2N-4)/3 and expansion 1+2/(4(N+1)/3). This result has an optimal expansion when N is sufficiently large and is superior to the previous mapping methods \cite{Ip93} in terms of the dilation and expansion.
Categories and Subject Descriptors: C.1.2 [Processor Architectures]: Multiple Data Stream Architectures (Multiprocessors); C.2.1 [Computer-Communication Networks]: Network Architecture and Design; F.1.2 [Computation by Abstract Devices]: Modes of Computation; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: dilation, embedding, expansion, parallel architecture, pyramid, 3-dimensional mesh