Improved Algorithms for Mapping Pipelined and Parallel Computations

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.