Skip navigation

Multilevel mesh partitioning for heterogeneous communication networks

Multilevel mesh partitioning for heterogeneous communication networks

Walshaw, Christopher ORCID: 0000-0003-0253-7779 and Cross, Mark (2001) Multilevel mesh partitioning for heterogeneous communication networks. Future Generation Computer Systems, 17 (5). pp. 601-623. ISSN 0167-739X (doi:10.1016/S0167-739X(00)00107-2)

Full text not available from this repository.

Abstract

Multilevel algorithms are a successful class of optimisation techniques which address the mesh partitioning problem for distributing unstructured meshes onto parallel computers. They usually combine a graph contraction algorithm together with a local optimisation method which refines the partition at each graph level. To date these algorithms have been used almost exclusively to minimise the cut edge weight in the graph with the aim of minimising the parallel communication overhead, but recently there has been a perceived need to take into account the communications network of the parallel machine. For example the increasing use of SMP clusters (systems of multiprocessor compute nodes with very fast intra-node communications but relatively slow inter-node networks) suggest the use of hierarchical network models. Indeed this requirement is exacerbated in the early experiments with meta-computers (multiple supercomputers combined together, in extreme cases over inter-continental networks). In this paper therefore, we modify a multilevel algorithm in order to minimise a cost function based on a model of the communications network. Several network models and variants of the algorithm are tested and we establish that it is possible to successfully guide the optimisation to reflect the chosen architecture.

Item Type: Article
Additional Information: CMS Ref. No: 01/17.
Uncontrolled Keywords: graph partitioning, mesh partitioning, multilevel optimisation, mapping, meta-computing, SMP clusters
Subjects: Q Science > QA Mathematics > QA76 Computer software
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Centre for Numerical Modelling & Process Analysis
School of Computing & Mathematical Sciences > Centre for Numerical Modelling & Process Analysis > Computational Science & Engineering Group
School of Computing & Mathematical Sciences > Computer & Computational Science Research Group
School of Computing & Mathematical Sciences > Department of Computer Science
School of Computing & Mathematical Sciences > Department of Mathematical Sciences
Related URLs:
Last Modified: 14 Oct 2016 09:00
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/519

Actions (login required)

View Item View Item