A parallel algorithm for mapping a special class of task graphs onto linear array multiprocessors

Sibabrata Ray, Hong Jiang, Jitender S. Deogun

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In parallel and distributed computing, mapping a task graph to a specific multiprocessor topology is an important problem. In this paper we investigate a special case of this problem for linear task graph and linear array multiprocessors. A polynomial time sequential algorithm and a parallel algorithm are developed and analyzed. It has been shown that the sequential algorithm developed has a time complexity at least as aood as the existing n log rz algorithm while the parallel algorithm presents the very first attempt at parallelizing the sequential solution. Further, we have proved that the partitioning problem is NP-complete for tree task graphs. Applications of the algorithm are briefly discussed.

Original languageEnglish (US)
Title of host publication1994 ACM Symposium on Applied Computing, SAC 1994
PublisherAssociation for Computing Machinery
Pages473-477
Number of pages5
ISBN (Electronic)0897916476
DOIs
StatePublished - Apr 6 1994
Event1994 ACM Symposium on Applied Computing, SAC 1994 - Phoenix, United States
Duration: Mar 6 1994Mar 8 1994

Publication series

NameProceedings of the ACM Symposium on Applied Computing
VolumePart F129433

Other

Other1994 ACM Symposium on Applied Computing, SAC 1994
CountryUnited States
CityPhoenix
Period3/6/943/8/94

Keywords

  • Computational complexity
  • Load balancing
  • Multiprocessors
  • Parallel algorithms
  • Task graph partitioning

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'A parallel algorithm for mapping a special class of task graphs onto linear array multiprocessors'. Together they form a unique fingerprint.

  • Cite this

    Ray, S., Jiang, H., & Deogun, J. S. (1994). A parallel algorithm for mapping a special class of task graphs onto linear array multiprocessors. In 1994 ACM Symposium on Applied Computing, SAC 1994 (pp. 473-477). (Proceedings of the ACM Symposium on Applied Computing; Vol. Part F129433). Association for Computing Machinery. https://doi.org/10.1145/326619.326815