JISE

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

Journal of Information Science and Engineering, Vol. 18 No. 5, pp. 693-712

Concentrations, Load Balancing, Multicasting and Partial Permutation Routing on Hypercube Parallel Computers

Gene Eu Jan, Frank Yeong-Sung Lin^*, Ming-Bo Lin^**
and Deron Liang
Department of Computer Science
National Taiwan Ocean University
Keelung, 202 Taiwan
E-mail: {B0199, drliang}@mail.ntou.edu.tw
^*Department of Information Management
National Taiwan University
Taipei, 106 Taiwan
^**Department of Electronic Engineering
National Taiwan University of Science and Technology
Taipei, 106 Taiwan
E-mail: mblin@et.ntust.edu.tw

Some basic algorithms on hypercube interconnection networks are addressed and then applied to concentration, superconcentration, multicasting, partial permutation routing, and load balancing problems in this paper. The results show that both concentration and superconcentration problems can be solved in O(n) time and the multicasting and partial permutation routing problems in O(n2) time with O(1) buffers for each node, where n is the dimension of hypercube interconnection networks. The load balancing problem based on superconcentration can be solved in O(Mn) time, where M is the maximum number of tasks in each node.

Keywords: concentration, hypercubes, interconnection networks, load balancing, multicasting, partial permutation routing, permutation networks, superconcentration

Retrieve PDF document (JISE_200205_03.pdf)