Balancing Fine- and Medium-Grained Parallelism in Scheduling Loops for the XIMD Architecture
Chris J. Newburn, Andrew S. Huang, John Paul Shen · 1993
This paper presents an approach to scheduling loops that leverages the distinctive architectural features of the XIMD, particularly the variable number of instruction streams and low synchronization cost. The classical VLIW and MIMD architectures have a fixed number of instruction streams, each with a fixed width. A compiler for the XIMD architecture can exploit fine-grained parallelism within each instruction stream and medium-grained parallelism between instruction streams. Its task is to schedule code using the instruction stream widths best suited for the available program parallelism in each loop nest. The combination of instruction stream widths is selected to make the best utilization of the machine resources, and hence to minimize the execution time for the whole schedule. A new loop scheduling technique is presented for the XIMD called iteration mapping. It applies and extends doacross to use more than one processing unit per instruction stream, and to exploit both fine- and m...