DocumentCode :
1548965
Title :
Instruction scheduling for instruction level parallel processors
Author :
Faraboschi, Paolo ; Fisher, Joseph A. ; Young, Cliff
Author_Institution :
Hewlett-Packard Labs., Cambridge, MA, USA
Volume :
89
Issue :
11
fYear :
2001
fDate :
11/1/2001 12:00:00 AM
Firstpage :
1638
Lastpage :
1659
Abstract :
Nearly all personal computer and workstation processors, and virtually all high-performance embedded processor cores, now embody instruction level parallel (ILP) processing in the form of superscalar or very long instruction word (VLIW) architectures. ILP processors put much more of a burden on compilers; without "heroic" compiling techniques, most such processors fall far short of their performance goals. Those techniques are largely found in the high-level optimization phase and in the code generation phase; they are also collectively called instruction scheduling. This paper reviews the state of the art in code generation for ILP parallel processors. Modern ILP code generation methods move code across basic block boundaries. These methods grew out of techniques for generating horizontal microcode, so we introduce the problem by describing its history. Most modem approaches can be categorized by the shape of the scheduling "region." Some of these regions are loops, and for those techniques known broadly as "Software Pipelining" are used. Software Pipelining techniques are only considered here when there are issues relevant to the region-based techniques presented. The selection of a type of region to use in this process is one of the most controversial questions in code generation; the paper surveys the best known alternatives. The paper then considers two questions: First, given a type of region, how does one pick specific regions of that type in the intermediate code. In conjunction with region selection, we consider region enlargement techniques such as unrolling and branch target expansion. The second question, how does one construct a schedule once regions have been selected, occupies the next section of the paper. Finally, schedule construction using recent, innovative resource modeling based on finite-state automata is then reexamined. The paper includes an extensive bibliography
Keywords :
instruction sets; parallel architectures; pipeline processing; processor scheduling; program compilers; VLIW architecture; code generation; compiler; finite-state automata; instruction level parallel processor; instruction scheduling; region scheduling; resource modeling; software pipelining; superscalar architecture; Automata; Computer architecture; History; Microcomputers; Modems; Pipeline processing; Processor scheduling; Shape; VLIW; Workstations;
fLanguage :
English
Journal_Title :
Proceedings of the IEEE
Publisher :
ieee
ISSN :
0018-9219
Type :
jour
DOI :
10.1109/5.964443
Filename :
964443
Link To Document :
بازگشت