JISE


  [1] [2] [3] [4] [5] [6] [7] [8]


Journal of Information Science and Engineering, Vol. 16 No. 1, pp. 117-126


A Parallel Approach for Embedding Large Pyramids Into Smaller Hypercubes With Load Balancing


Yu-Wei Chen and Kuo-Liang Chung+
Department of Information Science 
Tamsui Oxford University College 
Tamsui, Taipei County, Taiwan 251, R.O.C. 
E-mail: ywchen@jupiter.touc.edu.tw 
+Department of Infomation Management and Institute of Information Engineering 
National Taiwan University of Science and Technology 
Taipei, Taiwan 106, R.O.C. 
E-mail: klchung@cs.ntust.edu.tw


    With dilation 2, congestion 2, expansion 3/2, and load 1, this short paper first presents a parallel method for embedding a pyramid with height n, Pn for n ?2, into a (2n - 1) - dimensional hypercube, H2n - 1, in O(n) time. With dilation 2, congestion 2n - t + 3 (or 2n-t+1 + 2), and load when 0 ?k = 2t (or k = 2t - 1) ? 2n - 2, our proposed parallel method is further extended to map Pn into Hk with load balancing in O(k) time.


Keywords: congestion, dilation, parallel algorithm, hypercube, load balancing, nCUBE 2S, pyramid

  Retrieve PDF document (JISE_200001_07.pdf)