Improved Algorithms for Mapping Pipelined and Parallel Computations

David M. Nicol, David R. O 'Hallaron

Research output: Contribution to journalArticlepeer-review


This paper extends recent work on the problem of mapping pipelined or parallel computations onto linear array, shared memory, and host—satellite systems. We show how these problems can be solved even more efficiently when computation module execution times are bounded from below, intermodule communication times are bounded from above, and the processors satisfy certain homogeneity constraints. Our improvements have significantly lower time and space complexities than those of the more general algorithms: In one case, we replace an O(nm3) time algorithm for mapping m modules onto n processors with an O(nm log m) time algorithm, and reduce the space requirements from O(nm2) to O(m). We then reduce run-time complexity further with parallel mapping algorithms based on these improvements, that run on the architectures for which they create mappings.

Original languageEnglish (US)
Pages (from-to)295-306
Number of pages12
JournalIEEE Transactions on Computers
Issue number3
StatePublished - Mar 1991
Externally publishedYes


  • Mapping problem
  • parallel algorithms
  • parallel processing
  • performance optimization
  • pipelined computations

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Improved Algorithms for Mapping Pipelined and Parallel Computations'. Together they form a unique fingerprint.

Cite this