Document Type





Parallel computing




Computer Sciences


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.

Additional Information

School of Computer and Information Science, Syracuse Uniersity, SU-CIS-90-19





To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.