Unstructured Domain Mapping for Distributed Memory Architectures


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]

Objectivies and Approach

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.

Progress and Results

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.

Information Dissemination Activities and/or Exploitation

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.


Bilkent University
Computer Engineering Department
06533 Ankara, T

EU Partners

Parsytec Computer GmbH, D

Non-EU Partners

Bilkent University, T


Prof. Cevdet Aykanat
Tel: +90 312 266 4133
Fax: +90 312 266 4126
E-mail: aykanat@cs.bilkent.edu.tr

INCO synopses home page INCO cooperation index INCO keyword index
INCO acronym index INCO number index INCO Projects index
synopses home page all keywords index all acronyms index all numbers index

DOMAP - ITDC-204, May 1997

please address enquiries to the ESPRIT Information Desk

html version of synopsis by Nick Cook