AN OPTIMAL INSTRUCTION SCHEDULER FOR SUPERSCALAR PROCESSOR

被引:32
作者
CHOU, HC
CHUNG, CP
机构
[1] Institute of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu
关键词
PIPELINE PROCESSORS; SEQUENCING AND SCHEDULING; OPTIMIZATION; PRUNE AND SEARCH; AND NP-COMPLETENESS;
D O I
10.1109/71.372778
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Performance in superscalar processing strongly depends on the compiler's ability to generate codes that can be executed by hardware in an optimal or near optimal order, Generating optimal code is an NP-complete problem. However, there is a need for highly optimized code, such as in superscalar or real-time systems, In this paper, an instruction scheduling scheme for optimizing a program trace is proposed. Optimized code can be arrived at without much redundant work, if some important features in code are well explored and utilized in scheduling. To formalize the task, two abstract models, one for a superscalar processor and the other for a program trace, are given, These two models reflect most of the characteristics of the scheduling problem. The interrelations between instructions and partial schedules are thoroughly studied, and dominance and equivalence relations on them are defined, These relations are then used to reduce the solution space and eventually help to produce optimal schedules. The results of experiments that show the promise of the proposed scheme are also presented.
引用
收藏
页码:303 / 313
页数:11
相关论文
共 21 条
[1]  
BRUNO J, 1980, IEEE T COMPUT, V29, P308, DOI 10.1109/TC.1980.1675569
[2]  
CHOU HC, 1992, THESIS NAT CHIAO TUN
[3]  
EDWARD MR, 1977, COMBINATIORIAL ALGOR
[4]  
ELLIS JR, 1986, BULLDOG COMPILER VLI
[5]  
FISHER JA, 1981, IEEE T COMPUT, V30, P478, DOI 10.1109/TC.1981.1675827
[6]  
FISHER JA, 1984, IEEE T COMPUTERS JUL, P45
[7]  
Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[8]  
HENNESSY JL, 1983, ACM T PROGR LANG SYS, V5, P442
[9]  
JOHNSON M, 1990, SUPERSCALAR MICROPRO
[10]  
LAWER E, 1987, IBM RJ5738 RES REP