Generalized parallel divide and conquer on 3D mesh and torus

Abstract

In this paper, we handle the problem of (1)mapping divide-and-conquer idea to 3D mesh and torus interconnection networks. Binary tree is not an efficient computation structure, thus, we select the computation structure as binomial tree. We propose an algorithm for divide and conquer on 3D meshes/torus. After that we give dilation of this algorithm for any 3D mesh whose size is power of 2 and the congestion of this embedding is 1, since each binomial tree consists of two edge-disjoint binomial tree B(n - 1)s. The communication times of proposed algorithm for store-and-forward routing mechanisms are evaluated with respect to some specific values of message ratio alpha, The results of wormhole routing mechanism are better than the results of store-and-forward routing mechanism due to the nommit dilation of embedding. The efficiency of the proposed algorithm is also investigated in this paper. If sequential algorithm has the complexity or number of computation as the quadratic form of size of data, then the proposed algorithm is cost-optimal depending on the routing mechanism being wormhole. In the store-and-forward routing mechanism, the number of computation in the sequential algorithm does not make the proposed algorithm be cost-optimal or not. The communication time is dominant and computation time is less effective than communication time. (c) 2004 Elsevier B.V.. All rights reserved.