On optimal hierarchical configuration of distributed systems on mesh and hypercube

Dajin Wang, Jiannong Cao

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

Abstract

This paper studies hierarchical configuration of distributed systems for achieving optimized system performance. A distributed system consists of a collection of local processes which are distributed over the network of processors and cooperate to perform some functions. An 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 cost is minimal. The problem in its general form has been known to be NP-hard. Therefore, we just focus on distributed computing jobs which require collecting information from all processors. One example of such job is distributed monitoring. By limiting the levels of the hierarchy to 2, we study optimal hierarchical configurations for two popular interconnection networks: mesh and hypercube. Based on analytical results, partitioning algorithms are proposed which achieve optimal communication cost attributed to information collection. We also discuss heuristic schemes for multiple-level hierarchical partitions. Although this paper is presented in terms of distributed monitoring, the approaches can also be applied to other hierarchical control problems in distributed computing.

Original languageEnglish
Title of host publicationProceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)0769519261, 9780769519265
DOIs
StatePublished - 1 Jan 2003
EventInternational Parallel and Distributed Processing Symposium, IPDPS 2003 - Nice, France
Duration: 22 Apr 200326 Apr 2003

Publication series

NameProceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003

Other

OtherInternational Parallel and Distributed Processing Symposium, IPDPS 2003
CountryFrance
CityNice
Period22/04/0326/04/03

Fingerprint

Distributed computer systems
Hypercube
Distributed Systems
Mesh
Distributed Computing
Configuration
Monitoring
Network routing
System Performance
Partition
Costs
Local Computation
Hierarchical Control
Resource Scheduling
Scheduling
Communication Cost
Interconnection Networks
Communication
Partitioning
Control Problem

Cite this

Wang, D., & Cao, J. (2003). On optimal hierarchical configuration of distributed systems on mesh and hypercube. In Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003 [1213311] (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPS.2003.1213311
Wang, Dajin ; Cao, Jiannong. / On optimal hierarchical configuration of distributed systems on mesh and hypercube. Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003. Institute of Electrical and Electronics Engineers Inc., 2003. (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003).
@inproceedings{6ee9ac79f23845fa8ecc949d9ee39b98,
title = "On optimal hierarchical configuration of distributed systems on mesh and hypercube",
abstract = "This paper studies hierarchical configuration of distributed systems for achieving optimized system performance. A distributed system consists of a collection of local processes which are distributed over the network of processors and cooperate to perform some functions. An 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 cost is minimal. The problem in its general form has been known to be NP-hard. Therefore, we just focus on distributed computing jobs which require collecting information from all processors. One example of such job is distributed monitoring. By limiting the levels of the hierarchy to 2, we study optimal hierarchical configurations for two popular interconnection networks: mesh and hypercube. Based on analytical results, partitioning algorithms are proposed which achieve optimal communication cost attributed to information collection. We also discuss heuristic schemes for multiple-level hierarchical partitions. Although this paper is presented in terms of distributed monitoring, the approaches can also be applied to other hierarchical control problems in distributed computing.",
author = "Dajin Wang and Jiannong Cao",
year = "2003",
month = "1",
day = "1",
doi = "10.1109/IPDPS.2003.1213311",
language = "English",
series = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003",

}

Wang, D & Cao, J 2003, On optimal hierarchical configuration of distributed systems on mesh and hypercube. in Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003., 1213311, Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003, Institute of Electrical and Electronics Engineers Inc., International Parallel and Distributed Processing Symposium, IPDPS 2003, Nice, France, 22/04/03. https://doi.org/10.1109/IPDPS.2003.1213311

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

Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003. Institute of Electrical and Electronics Engineers Inc., 2003. 1213311 (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

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

AU - Wang, Dajin

AU - Cao, Jiannong

PY - 2003/1/1

Y1 - 2003/1/1

N2 - This paper studies hierarchical configuration of distributed systems for achieving optimized system performance. A distributed system consists of a collection of local processes which are distributed over the network of processors and cooperate to perform some functions. An 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 cost is minimal. The problem in its general form has been known to be NP-hard. Therefore, we just focus on distributed computing jobs which require collecting information from all processors. One example of such job is distributed monitoring. By limiting the levels of the hierarchy to 2, we study optimal hierarchical configurations for two popular interconnection networks: mesh and hypercube. Based on analytical results, partitioning algorithms are proposed which achieve optimal communication cost attributed to information collection. We also discuss heuristic schemes for multiple-level hierarchical partitions. Although this paper is presented in terms of distributed monitoring, the approaches can also be applied to other hierarchical control problems in distributed computing.

AB - This paper studies hierarchical configuration of distributed systems for achieving optimized system performance. A distributed system consists of a collection of local processes which are distributed over the network of processors and cooperate to perform some functions. An 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 cost is minimal. The problem in its general form has been known to be NP-hard. Therefore, we just focus on distributed computing jobs which require collecting information from all processors. One example of such job is distributed monitoring. By limiting the levels of the hierarchy to 2, we study optimal hierarchical configurations for two popular interconnection networks: mesh and hypercube. Based on analytical results, partitioning algorithms are proposed which achieve optimal communication cost attributed to information collection. We also discuss heuristic schemes for multiple-level hierarchical partitions. Although this paper is presented in terms of distributed monitoring, the approaches can also be applied to other hierarchical control problems in distributed computing.

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

U2 - 10.1109/IPDPS.2003.1213311

DO - 10.1109/IPDPS.2003.1213311

M3 - Conference contribution

T3 - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003

BT - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Wang D, Cao J. On optimal hierarchical configuration of distributed systems on mesh and hypercube. In Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003. Institute of Electrical and Electronics Engineers Inc. 2003. 1213311. (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003). https://doi.org/10.1109/IPDPS.2003.1213311