Display Full Text | Download Full Text
6.74 MB PDF file

Degree

Doctor of Philosophy, Case Western Reserve University, Computer Engineering, 1990.

Abstract

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.

Subject Headings

Computer Science

Keywords

Fine grain mapping strategies pipelined computer systems

Advisor

Christos A. Papachristou

Pages

214p.

Document number: case1054583150
Permalink: http://rave.ohiolink.edu/etdc/view?acc_num=case1054583150

This ETD has been downloaded 189 times (through March 2013)