Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


case1059406414.pdf (3.7 MB)

ETD Abstract Container

Abstract Header

A large-grain mapping approach for multiprocessor systems through data flow model*

Kim, Hwa-Soo
http://rave.ohiolink.edu/etdc/view?acc_num=case1059406414

Abstract Details

1991, Doctor of Philosophy, Case Western Reserve University, Computer Engineering.
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 best 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
Christos Papachristou (Advisor)
187 p.
Computer Science
Large-grain mapping; Multiprocessor systems

Recommended Citations

Citations

  • Kim, H.-S. (1991). A large-grain mapping approach for multiprocessor systems through data flow model* [Doctoral dissertation, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1059406414

    APA Style (7th edition)

  • Kim, Hwa-Soo. A large-grain mapping approach for multiprocessor systems through data flow model*. 1991. Case Western Reserve University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1059406414.

    MLA Style (8th edition)

  • Kim, Hwa-Soo. "A large-grain mapping approach for multiprocessor systems through data flow model*." Doctoral dissertation, Case Western Reserve University, 1991. http://rave.ohiolink.edu/etdc/view?acc_num=case1059406414

    Chicago Manual of Style (17th edition)

case1059406414
387
© 1991, all rights reserved.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.