Approximate algorithms for partitioning problems | International Journal of Parallel Programming Skip to main content
Springer Nature Link
Log in

Approximate algorithms for partitioning problems

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

Abstract

We consider the problem of optimally assigning the modules of a parallel/pipelined program over the processors of a multiple processor system under certain restrictions on the interconnection structure of the program as well as the multiple computer system. We show that for a variety of such problems, it is possible to find if a partition of the modular program exists in which the load on any processor is whithin a certain bound. This method when combined with a binary search over a fixed range, provides an optimal solution to the partitioning problem.

The specific problems we consider are partitioning of (1) a chain structured parallel program over a chain-like computer system, (2) multiple chain-like programs over a host-satellite system, and (3) a tree structured parallel program over a host-satellite system.

For a problem withN modules andM processors, the complexity of our algorithm is no worse thanO(Mlog(N)log(W T/∈)), whereW T is the cost of assigning all modules to one processors, and ∈ the desired accuracy. This algorithm provides an improvement over the recently developed best known algorithm that runs inO(MNlog(N)) time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Bokhari, Partitioning Problems in Parallel, Pipelined and Distributed Computing,IEEE Tran. Comput., Vol. 37, No. 1 (January 1988).

  2. M. A. Iqbal, J. H. Saltz, and S. H. Bokhari, Performance Tradeoffs in Static and Dynamic Load Balancing Strategies,Proc. of the Int'l. Conf. on Parallel Processing, pp. 1040–1047 (August 1986).

  3. D. M. Nicol and D. R. O'Hallaron, Improved Algorithms for Mapping Pipelined and Parallel Computations,IEEE Trans. on Computers (to appear). An earlier version is available as ICASE Report No. 88-2, NASA Contractor Report 181655 (April 1988).

  4. M. A. Iqbal, Efficient Algorithms for Partitioning Problems,Proc. of the Int'l. Conf. on Parallel Processing (August 1990).

  5. Hyeong-Ah Choi and B. Narahari, Algorithms for Mapping and Partitioning Chain Structured Parallel Computations,Proc. of the Int'l. Conf. on Parallel Processing (August 1991).

  6. M. A. Iqbal, Approximate Algorithms for Partitioning and Assignment Problems, ICASE Report No. 86-40, NASA Contractor Report 178130 (June 1986).

  7. E. Horowitz and S. Sahni,Fundamentals of Computer Algorithms, Computer Science Press, Inc. (1978).

  8. Michal Cenkle, Partitioning Algorithm Graphs for Pipelined Computation, The MITRE Corporation Report, Bedford, Massachusetts (September 1991).

  9. Ajay Mohindra and Sudhakar Yalamanchili, Dominant Representations: A Paradigm for Mapping Parallel Computations, Georgia Institute of Technology, Atlanta, Georgia (September 1991).

    Google Scholar 

  10. M. Annaratone, E. Arnould, T. Gross, H. Kung, M. Lam, O. Menzilcioglu, and J. Webb, The Warp Computer: Architecture, Implementation, and Performance,IEEE Trans. on Computers, Vol. C-36, No. 12 (December 1987).

  11. H. S. Stone, Multiprocessor Scheduling with the Aid of Network Flow Algorithms,IEEE Trans. Software Engineering,SE-4(1):85–93 (January 1977).

    Google Scholar 

  12. H. S. Stone, Critical Load Factors in Distributed Computer Systems,IEEE Trans. Software Engineering,SE-4(3):254–258 (May 1987).

    Google Scholar 

  13. M. A. Iqbal, Mapping and Assignment Problems in Multiple Computer Systems, PhD Dissertation, Department of Electrical Engineering, University of Engineering and Technology, Lahore, Pakistan (January 1991).

    Google Scholar 

  14. B. Kernighan, Optimal Sequential Partitions of Graphs,JACM,18(1):34–40 (January 1971).

    Google Scholar 

  15. M. Berger and S. Bokhari, A Partitioning Strategy for Non-Uniform Problems Across Multiprocessors,IEEE Trans. Comput., Vol. C-36, No. 5 (May 1987).

Download references

Author information

Author notes

  1. Mohammad Ashraf Iqbal

    Present address: Department of EE-Systems, University of Southern California, 90007, Los Angeles, California

Authors and Affiliations

  1. Department of Electrical Engineering, University of Engineering and Technology, Lahore, Pakistan

    Mohammad Ashraf Iqbal

Authors
  1. Mohammad Ashraf Iqbal
    View author publications

    You can also search for this author inPubMed Google Scholar

Additional information

This Research was supported by a grant from the Division of Research Extension and Advisory Services, University of Engineering and Technology Lahore, Pakistan. Further support was provided by NASA Contracts NAS1-17070 and NAS1-18107 while the author was resident at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, Virginia, USA.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Iqbal, M.A. Approximate algorithms for partitioning problems. Int J Parallel Prog 20, 341–361 (1991). https://doi.org/10.1007/BF01407812

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01407812

Key Words