Concentrations, load balancing, multicasting and partial permutation routing on hypercube parallel computers

Gene Eu Jan, Frank Yeong Sung Lin, Ming Bo Lin, Deron Liang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)693-712
Number of pages20
JournalJournal of Information Science and Engineering
Volume18
Issue number5
StatePublished - Sep 2002

Keywords

  • Concentration
  • Hypercubes
  • Interconnection networks
  • Load balancing
  • Multicasting
  • Partial permutation routing
  • Permutation networks
  • Superconcentration

Fingerprint

Dive into the research topics of 'Concentrations, load balancing, multicasting and partial permutation routing on hypercube parallel computers'. Together they form a unique fingerprint.

Cite this