A large-grain mapping approach for multiprocessor systems through data flow model
Hwa-Soo Kim · OhioLink ETD Center (Ohio Library and Information Network) · 1992
This dissertation presents a large-grain level mapping method of numerical-oriented applications onto multiprocessor systems. The method is based on the large-grain data flow representation of the input application and it assumes a general interconnection topology of the multiprocessor system. We use the large-grain data flow model because such representation exhibits inherited parallelism in many important applications, e.g., CFD models based on partial differential equations can be represented in large grain data flow format, very effectively. We consider a generalized interconnection topology of the multiprocessor architecture, including such architectural issues as interprocessor communication cost, with the aim to identify the best matching between the application and the multiprocessor structure. The overall objective is to minimize the total execution time of the input algorithm running on the target system. The mapping strategy consists of the following steps: (1) Large grain data flow graph generation from the input application using compilation techniques. (2) Data flow graph partitioning into basic computation blocks. (3) Physical mapping onto the target multiprocessor using a priority allocation scheme for the computation blocks. The proposed method is applicable to the parallel solution of complex Computational Fluid Dynamics (CFD), particularly CFD problems using a large number of partial differential equations (PDEs). Our approach achieves automatic parallelization of the PDEs involved by detecting their complex data dependencies, segmenting the PDEs into PDE blocks, and providing a cost-effective scheduling of the PDE blocks onto the target multiprocessor architecture. The several numerical-oriented application algorithms, such as differential equations, rotating shaft problems, 2-D Navier Stokes equations, etc., have been used as the testing inputs. The experimental results are analyzed with respect to time-steps required, number of data transfer, speedup, efficiency, and load-balance. These results are very encouraging. ftn*This work is partially supported by NASA Lewis Research Center under grant number: NAG3-1103.