On hierarchical configuration of distributed systems on mesh and hypercube

Dajin Wang, Jiannong Cao

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We study hierarchical configuration of distributed systems for achieving optimized system performance. A distributed system consists of a collection of local processes which are distributed over a network of processors, and work in a cooperative manner to fulfill various tasks. A hierarchical approach is to group and organize the distributed processes into a logical hierarchy of multiple levels, so as to coordinate the local computation/control activities to improve the overall system performance. It has been proposed as an effective way to solve various problems in distributed computing, such as distributed monitoring, resource scheduling, and network routing. The optimization problem considered in this paper is concerned with finding an optimal hierarchical partition of the processors, so that the total traffic flow over the network is minimized. The problem in its general form has been known to be NP-hard. Therefore, we just focus on distributed computing jobs which require collecting and processing information from all processors. By limiting levels of the hierarchy to two, we will establish the analytically optimal hierarchical configurations for two popular interconnection networks: mesh and hypercube. Based on analytical results, partitioning algorithms are proposed to achieve minimal communication cost (network traffic flow). We will also present and discuss heuristic algorithms for multiple-level hierarchical partitions.

Original languageEnglish
Pages (from-to)517-534
Number of pages18
JournalInternational Journal of Foundations of Computer Science
Volume15
Issue number3
DOIs
StatePublished - 1 Dec 2004

Keywords

  • Distributed processing
  • Hierarchical architecture
  • Hierarchical configuration
  • Hypercube
  • Interconnection networks
  • Mesh

Fingerprint Dive into the research topics of 'On hierarchical configuration of distributed systems on mesh and hypercube'. Together they form a unique fingerprint.

Cite this