Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


case1054583150.pdf (6.74 MB)

ETD Abstract Container

Abstract Header

Fine grain mapping strategies for pipelined computer systems

Shieh, Jong-Jiann
http://rave.ohiolink.edu/etdc/view?acc_num=case1054583150

Abstract Details

1990, Doctor of Philosophy, Case Western Reserve University, Computer Engineering.
This dissertation proposes fine grain mapping strategies for pipelined computer systems, especially suitable for RISC and VLIW architectures. One strategy is to reorder the instruction streams for single processor systems and the other is to schedule these streams for multiprocessor systems. The objective is to minimize the total execution time of input application programs running on the target systems. The application algorithm which has been coded as a straight line program is compiled to generate intermediate code. This code is then represented by a data dependence graph. A node in the graph corresponds to the operation of one intermediate code statement, and an arc between two nodes represents the data dependence between operations. The strategies are to reorder the instruction streams, nodes in the graph, for single processor systems and to schedule these streams for multiprocessor systems. They are generalized list schedulers. The data dependence, the pipeline effect, and the communication cost (in case of multiprocessor system) are all considered within these strategies. The reordering algorithm for single processor systems reorders the instruction sequence in such a way that each instruction will be issued as early as possible. The scheduler for multiprocessor systems, cal led SR-mapper, uses Slot Reservation technique to insert send nodes for the immediate successor nodes when a node has been scheduled to maintain the data dependence between nodes and to achieve the synchronization between processing elements. Both the reorderer and SR-mapper have been implemented and several scientific application algorithms, such as matrix multiplication, L-U decomposition, weighted median filter, convolution kernel, etc., have been used as the testing inputs. Data show that the reordering technique can be embedded within a compiler to improve the performance of a general purpose computer without making any hardware changes, and the slot reservation mapping strategy is a promising way to schedule the fine grain instruction streams for multiprocessor systems. These results are very encouraging.
Christos Papachristou (Advisor)
214 p.
Computer Science
Fine grain mapping strategies pipelined computer systems

Recommended Citations

Citations

  • Shieh, J.-J. (1990). Fine grain mapping strategies for pipelined computer systems [Doctoral dissertation, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1054583150

    APA Style (7th edition)

  • Shieh, Jong-Jiann. Fine grain mapping strategies for pipelined computer systems. 1990. Case Western Reserve University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1054583150.

    MLA Style (8th edition)

  • Shieh, Jong-Jiann. "Fine grain mapping strategies for pipelined computer systems." Doctoral dissertation, Case Western Reserve University, 1990. http://rave.ohiolink.edu/etdc/view?acc_num=case1054583150

    Chicago Manual of Style (17th edition)

case1054583150
490
© 1990, all rights reserved.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.