DocumentCode :
2533065
Title :
Efficient instruction scheduling using finite state automata
Author :
Bala, Vasanth ; Rubin, Norman
Author_Institution :
Hewlett Packard Labs., USA
fYear :
1995
fDate :
29 Nov-1 Dec 1995
Firstpage :
46
Lastpage :
56
Abstract :
Modern compilers employ sophisticated instruction scheduling techniques to shorten the number of cycles taken to execute the instruction stream. In addition to correctness, the instruction scheduler must also ensure that hardware resources are not oversubscribed in any cycle. For a contemporary processor implementation with multiple pipelines and complex resource usage restrictions, this is not an easy task. The complexity involved in reasoning about such resource hazards is one of the primary factors that constrain the instruction scheduler from performing many aggressive transformations. For example, the ability to do code motion or instruction replacement in the middle of an already scheduled block would be a very powerful transformation if it could be performed efficiently. We extend a technique for detecting pipeline resource hazards based on finite state automata, to support the efficient implementation of such transformations that are essential for aggressive instruction scheduling beyond basic blocks. Although similar code transformations can be supported by other schemes such as reservation tables, our scheme is superior in terms of space and time. A global instruction scheduler that used these techniques was implemented in the KSR compiler
Keywords :
finite automata; hazards and race conditions; pipeline processing; program compilers; scheduling; KSR compiler; code motion; compilers; finite state automata; instruction replacement; instruction scheduler; instruction scheduling; multiple pipelines; pipeline resource hazards; resource hazards; Automata; Creep; Hardware; Hazards; Law; Legal factors; Phase detection; Pipelines; Processor scheduling; Vents;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Microarchitecture, 1995., Proceedings of the 28th Annual International Symposium on
Conference_Location :
Ann Arbor, MI
ISSN :
1072-4451
Print_ISBN :
0-8186-7349-4
Type :
conf
DOI :
10.1109/MICRO.1995.476812
Filename :
476812
Link To Document :
بازگشت