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:https://doi.org/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:	Publisher Organisation
Last Modified:	14 Oct 2016 09:00
URI:	http://gala.gre.ac.uk/id/eprint/519

Actions (login required)

View Item