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

Journal of Inforamtion Science and Engineering, Vol.16, No.1, pp.117-126 (January 2000)

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

Full Text (¥þ¤åÀÉ) Retrieve PDF document (200001_07.pdf : 3,563,874 bytes)

Received March 19, 1998; revised March 4, 1999; accepted April 1, 1999.
Communicated by Jang-Ping Sheu
*This research was supported by the National Science Council of R.O.C. under contract NSC87-2213-E011-001.