[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

PaGrid: A Mesh Partitioner for Computational Grids

  • Published:
Journal of Grid Computing Aims and scope Submit manuscript

Abstract

Computational Grids are emerging as a new infrastructure for high performance computing. Since the resources in a Grid can be heterogeneous and distributed, mesh-based applications require a mesh partitioner that considers both processor and network heterogeneity. We have developed a heterogeneous mesh partitioner, called PaGrid. PaGrid uses a multilevel graph partitioning approach, augmented by execution time load balancing in the final uncoarsening phase. We show that minimization of total communication cost (e.g., as used by JOSTLE) can lead to significant load being placed on processors connected by slow links, which results in higher application execution times. Therefore, PaGrid balances the estimated execution time of the application across processors. PaGrid performance is compared with two existing mesh partitioners, METIS 4.0 and JOSTLE 3.0, for mapping several application meshes to two models of heterogeneous computational Grids. PaGrid is found to produce significantly better partitions than JOSTLE and slightly better partitions than METIS in most cases, in terms of estimated application execution time averaged over a large number of runs with different random number seeds.

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
£29.99 /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 (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. Chen and V. E. Taylor, ‘Mesh Partitioning for Efficient Use of Distributed Systems’, IEEE Trans. Parallel and Distributed Systems, Vol. 13, No. 1, pp. 67–79, 2002.

    Article  Google Scholar 

  2. D.T. Connolly, ‘An Improved Annealing Scheme for the QAP’. European Journal of Operational Research, Vol. 46, pp. 93–100, 1990.

    Article  MATH  MathSciNet  Google Scholar 

  3. I. Foster and C. Kesselman, ‘The Globus Toolkit’, in I. Foster and C. Kesselman (eds.), The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann, pp. 259–278, 1999.

  4. A.S. Grimshaw and W.A. Wulf, ‘The Legion Vision of a Worldwide Virtual Computer’, Communications of the ACM, Vol. 40, No. 1, pp. 39–45, 1997.

    Article  Google Scholar 

  5. W. Gropp, E. Lusk and A. Skjellum, Using MPI, 2nd Edition: Portable Parallel Programming with the Message-Passing Interface, MIT, Cambridge, Massachusetts.

    Google Scholar 

  6. Y.F. Hu, R.J. Blake and D. R. Emerson, ‘An Optimal Migration Algorithm for Dynamic Load Balancing’, Concurrency: Practice and Experience, Vol. 10, pp. 467–483, 1998.

    Article  MATH  Google Scholar 

  7. S. Huang, ‘PaGrid: A Mesh Partitioner for Computational Grids’, Master's thesis, Faculty of Computer Science, University of New Brunswick, Fredericton, NB, Canada, 2003.

  8. S. Huang, E. Aubanel and V. Bhavsar, ‘Mesh Partitioners for Computational Grids: a Comparison’, in V. Kumar, M. Gavrilova, C. Tan, and P. L'Ecuyer (eds.), Computational Science and Its Applications, Vol. 2269 of Lecture Notes in Computer Science, Springer Inc., Berlin Heidelberg New York, pp. 60–68, 2003.

  9. N. Karonis, B. Toonen and I. Foster, ‘MPICH-G2: A Grid-Enabled Implementation of the Message Passing Interface’, Journal of Parallel and Distributed Computing, Vol. 63, No. 5, pp. 551–563, 2003.

    Article  MATH  Google Scholar 

  10. G. Karypis and V. Kumar, ‘A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs’, SIAM Journal on Scientific Computing, Vol. 20, No. 1, pp. 359–392, 1998a.

    Article  MathSciNet  Google Scholar 

  11. G. Karypis and V. Kumar, ‘Multilevel K-Way Partitioning Scheme for Irregular Graphs’, Journal of Parallel and Distributed Computing, Vol. 48 No. 1, pp. 96–129, 1998b.

    Article  MathSciNet  Google Scholar 

  12. G. Karypis and V. Kumar, ‘METIS Graph Archive’, ftp://ftp.cs.umn.edu/dept/users/kumar/Graphs/ 2003.

  13. D. Knuth, ‘Programs to Read’, http://www-csfaculty. stanford.edu/ knuth/programs.html, 2005.

  14. S. Kumar, S. Das, and R. Biswas, ‘Graph Partitioning for Parallel Applications in Heterogeneous Grid Environments’, in International Parallel and Distributed Processing Symposium, Florida, 2002.

  15. F. Pellegrini and J. Roman: 1996, ‘SCOTCH: A Software Package for Static Mapping by Dual Recursive Bipartitioning of Process and Architecture Graphs’ in HPCN’96. pp. 493–198.

  16. K. Schloegel, G. Karypis and V. Kumar, ‘Graph Partitioning for High-Performance Scientific Simulations’ in e. a. Dongarra, J. (ed.), Sourcebook of Parallel Computing Morgan Kaufmann, pp. 491–541, 2003.

  17. V.E. Taylor, E.J. Schwabe, B.K. Holmer and M.R. Hribar, ‘Balancing Load versus Decreasing Communication: Parameterizing the Tradeoff’, Journal of Parallel and Distributed Computing, Vol. 61, pp. 567–580, 2001.

    Article  MATH  Google Scholar 

  18. C. Walshaw, ‘University of Greenwich Graph Partitioning Archive’, http://www.gre.ac.uk/ c.walshaw/partition/. 2003.

  19. C. Walshaw and M. Cross, ‘Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm’, SIAM J. Sci. Comput. Vol. 22, No. 1, pp. 63–80, 2000.

    Article  MATH  MathSciNet  Google Scholar 

  20. C. Walshaw and M. Cross, ‘Multilevel Mesh Partitioning for Heterogeneous Communication Networks’, Future Generation Comput. Syst. Vol. 17, No. 5, p. 24, 2001.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Computer Science, University of New Brunswick, Fredericton, NB, E3B 5A3, Canada

    Sili Huang, Eric Aubanel & Virendrakumar C. Bhavsar

Authors
  1. Sili Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eric Aubanel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Virendrakumar C. Bhavsar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Eric Aubanel.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Huang, S., Aubanel, E. & Bhavsar, V.C. PaGrid: A Mesh Partitioner for Computational Grids. J Grid Computing 4, 71–88 (2006). https://doi.org/10.1007/s10723-005-9018-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10723-005-9018-0

Key words

Search

Navigation