Title :
An enhanced Co-scheduling method using reduced MS-state diagrams
Author :
Govindarajan, R. ; Rao, N. S S Narasimha ; Altman, E.R. ; Gao, Guang R.
Author_Institution :
Supercomput. Educ. & Res. Centre, Indian Inst. of Sci., Bangalore, India
fDate :
30 Mar-3 Apr 1998
Abstract :
Instruction scheduling methods based on the construction of state diagrams (or automata) have been used for architectures involving deeply pipelined function units. However, the size of the state diagram is prohibitively large, resulting in high execution time and space requirement. We present a simple method for reducing the size of the state diagram by recognizing unique paths of a state diagram. Our experiments show that the number of paths in the reduced state diagram is significantly lower-by 1 to 3 orders of magnitude-compared to the number of paths in the original state diagram. Using the reduced MS-state diagrams, we develop an efficient software pipelining method. The proposed software pipelining algorithm produced efficient schedules and performed better than R.A. Huff´s (1993) Slack Scheduling method, and the original Co-scheduling method, in terms of both the initiation interval (II) and the time taken to construct the schedule
Keywords :
automata theory; instruction sets; parallel programming; pipeline processing; processor scheduling; Slack Scheduling method; automata; deeply pipelined function units; enhanced Co-scheduling method; initiation interval; instruction scheduling methods; oftware pipelining algorithm; reduced MS-state diagrams; reduced state diagram; software pipelining method; unique paths; Automation; Computer science; Delay; Hazards; Pipeline processing; Processor scheduling; Scheduling algorithm; Software algorithms; Software maintenance; Supercomputers;
Conference_Titel :
Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International ... and Symposium on Parallel and Distributed Processing 1998
Conference_Location :
Orlando, FL
Print_ISBN :
0-8186-8404-6
DOI :
10.1109/IPPS.1998.669906