Keywords: distributed memory, domain mapping, decomposition heuristics, partitioning, matrices decomposition, parallel iterative solvers, parallel processing, coarse-grain parallelisation
Start Date: 1 February 95 / Duration: 30 months
[ participants / contact]
Parallelisation on distributed memory architectures often employs data parallelism by breaking the data structures into pieces and then assigning those pieces to different processors. These tasks constitute the domain mapping problem. The objective in the domain mapping is to find a mapping which minimises the communication overhead while maintaining almost the same workload for each processor. The domain mapping problem is known to be NP-hard for unstructured domains. Hence, heuristics giving suboptimal solutions are used to solve the problem. Domain mapping is a preprocessing introduced for the sake of efficient parallelisation. Hence, there is a trade-off between the mapping quality and the execution time. The objective of DOMAP is to investigate, propose and develop new fast heuristics for domain mapping. The relative performances of the proposed and existing heuristics and the models used will be experimentally evaluated on a Parsytec's parallel system using various domain mapping benchmarks.
Two hypergraph models were proposed which avoid all deficiencies of the graph model used for decomposing sparse matrices. The proposed models enable the representation and hence the decomposition of unsymmetric square and rectangular matrices as well as symmetric matrices and introduce a much more accurate representation of the communication requirement for the decomposition of unstructured domains in general. The proposed models are also successfully exploited and reformulated to transform large linear programming programs into block angular forms for coarse-grain parallelisation. The proposed models reduce the decomposition problem to the hypergraph partitioning problem. A multilevel hypergraph partitioning tool (PaToH) has been developed for experimenting both the validity of the proposed hypergraph models and the performance of the multilevel approach on hypergraph partitioning. Initial experimental results on large sparse matrices, selected from Harwell-Boeing collection and NETLIB suite, confirm both the validity of the proposed hypergraph models and the appropriateness of the multilevel approach to hypergraph partitioning.
A list of more than seven publications may be requested by the coordinator. The initial version of PaToH with the relevant documentation will be publicly available in 1997.
Computer Engineering Department
06533 Ankara, T
Parsytec Computer GmbH, D
Bilkent University, T
Prof. Cevdet Aykanat
Tel: +90 312 266 4133
Fax: +90 312 266 4126
DOMAP - ITDC-204, May 1997
please address enquiries to the ESPRIT Information Desk
html version of synopsis by Nick Cook