首页   按字顺浏览 期刊浏览 卷期浏览 Fine grain mapping strategy for multiprocessor systems
Fine grain mapping strategy for multiprocessor systems

 

作者: J.J.Shieh,   C.A.Papachristou,  

 

期刊: IEE Proceedings E (Computers and Digital Techniques)  (IET Available online 1991)
卷期: Volume 138, issue 3  

页码: 109-120

 

年代: 1991

 

DOI:10.1049/ip-e.1991.0015

 

出版商: IEE

 

数据来源: IET

 

摘要:

A fine grain mapping strategy for multiprocessor systems especially suitable for RISC and VLIW type MIMD computers is described. The objective of the strategy is to minimise the total execution time of the application algorithms that are to be executed on the target systems. An application algorithm which has been coded as a straight line program is compiled to generate intermediate codes. 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 arcs between nodes represent the data dependence between operations. The mapping strategy, called SR-mapper, is a generalised list scheduler. When SR-mapper does the mapping procedure, the data dependence between nodes, the pipeline effect of each processing element within the system, and the communication cost between processing elements are considered. 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 synchronisation between processing elements. SR-mapper has 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. Results show that on the average the speedup obtained by SR-mapper is 4.480 times as large as the one obtained by the mapper which does not employ the pipeline effect assuming the weight of operations are 4 for addition and subtraction and 6 for multiplication and division. During the mapping phase, if the slot reservation technique is adopted, the gain of speedup is 21%, on the average, more than the one obtained by the mapper which does not apply the slot reservation technique. If all nodes have an equal weight of 1, the average efficiency of the systems with the number of processing elements ranging from 2 to 32 and communication costs ranging from 0 to 20 is 0.481. These results are encouraging.

 

点击下载:  PDF (1510KB)



返 回