Document Type
Report
Date
1990
Keywords
Parallel computing
Language
English
Disciplines
Computer Sciences
Description/Abstract
In parallel computing, it is important to map a parallel program onto a parallel computer such that the total execution time of a parallel program is minimized. In general, a parallel program and a parallel computer can be represented by a task graph (TG) and a processor graph (PG), respectively. For a TG, nodes represent tasks of a parallel program and edges denote the data communication needed between tasks. The weights associated with nodes and edges represent the computational load and communication cost, respectively. For a PG, nodes and edges denote processors and communication channels, respectively. By using the graph model, the mapping problem becomes a task allocation problem. In the task allocation problem, we try to distribute the computational load of a parallel program to the processors of a parallel computer as evenly as possible (the load balance criterion (LBC) and minimize the communication cost of processors (the minimum communication cost criterion (MCCC)). The optimal assignment of tasks to processors in order to minimize the total execution time is known to be NP-complete [GaJo79]. This means that the optimal solution is intractable. Therefore, satisfactory suboptimal solutions are generally sought. In this paper, we will discuss how to map finite element graphs (FEGs) onto hypercubes. Our schemes are general and are applicable to a wide variety of PGs. The finite element method (FEM) is a widely used method for the structural modeling of physical system [LaPi83]. Due to the properties of compute-intensiveness and compute-locality, it is very attractive to implement this method on parallel computers [BeBo87] [Bokh81] [Jord78] [SaEr87]. The number of nodes in a FEG is usually greater than the number of processors in a parallel computer. It is important to partition a FEG into M modules such that the computational load of modules are equal and the communication cost among modules are minimized, where M is the number of processors of a parallel computer.
Recommended Citation
Chung, Yeh-Ching and Ranka, Sanjay, "Mapping Finite Element Graphs on Hypercubes" (1990). Electrical Engineering and Computer Science - Technical Reports. 95.
https://surface.syr.edu/eecs_techreports/95
Source
local
Additional Information
School of Computer and Information Science, Syracuse Uniersity, SU-CIS-90-19