On hierarchical configuration of distributed systems on mesh and hypercube

Dajin Wang, Jiannong Cao

Research output: Contribution to journalArticle

4 Citations (Scopus)

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

Fingerprint

Distributed computer systems
Network routing
Heuristic algorithms
Scheduling
Monitoring
Communication
Costs

Keywords

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

Cite this

@article{abd093efb49343dab02cf14fca626016,
title = "On hierarchical configuration of distributed systems on mesh and hypercube",
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.",
keywords = "Distributed processing, Hierarchical architecture, Hierarchical configuration, Hypercube, Interconnection networks, Mesh",
author = "Dajin Wang and Jiannong Cao",
year = "2004",
month = "12",
day = "1",
doi = "10.1142/S0129054104002583",
language = "English",
volume = "15",
pages = "517--534",
journal = "International Journal of Foundations of Computer Science",
issn = "0129-0541",
publisher = "World Scientific Publishing Co. Pte Ltd",
number = "3",

}

On hierarchical configuration of distributed systems on mesh and hypercube. / Wang, Dajin; Cao, Jiannong.

In: International Journal of Foundations of Computer Science, Vol. 15, No. 3, 01.12.2004, p. 517-534.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On hierarchical configuration of distributed systems on mesh and hypercube

AU - Wang, Dajin

AU - Cao, Jiannong

PY - 2004/12/1

Y1 - 2004/12/1

N2 - 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.

AB - 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.

KW - Distributed processing

KW - Hierarchical architecture

KW - Hierarchical configuration

KW - Hypercube

KW - Interconnection networks

KW - Mesh

UR - http://www.scopus.com/inward/record.url?scp=33745175428&partnerID=8YFLogxK

U2 - 10.1142/S0129054104002583

DO - 10.1142/S0129054104002583

M3 - Article

AN - SCOPUS:33745175428

VL - 15

SP - 517

EP - 534

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

SN - 0129-0541

IS - 3

ER -