Optimization on instruction reorganization

ABSTRACT

A pipelined processor increases its performance by partitioning an instruction into several separate operation steps. Several instructions can be executed in the pipeline in different pipe stages at the same time. Since the overlapped execution of instructions, the result of an instruction may be attempted to be used before it is available. One way to solve this problem is to schedule instructions at compiler time, thus the codes generated will be free from interlocks. The scheduling algorithm presented by [Hen 83, Gro 83] had significantly reduced the pipeline interlocks. With some modifications to distinguish the conflict condition, the algorithm will do better works at the same cost.

REFERENCES

• Aho 77: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• Allan 86: Vivki H. Allen , Robert A. Mueller, Phase coupling for horizontal microcode generation, ACM SIGMICRO Newsletter, v.18 n.4, p.24-29, Dec. 1987 [doi>10.1145/16360.1096734]
• Gib 86: Philip B. Gibbons , Steven S. Muchnick, Efficient instruction scheduling for a pipelined architecture, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.11-16, June 25-27, 1986, Palo Alto, California, United States
• Gro 83: Thomas Karl Richard Gross, Code optimization of pipeline constraints, 1983
• Hen 83: John L. Hennessy , Thomas Gross, Postpass Code Optimization of Pipeline Constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.422-448, July 1983 [doi>10.1145/2166.357217]
• Kuc 78: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• Lil 88: David J. Lilja, Reducing the Branch Penalty in Pipelined Processors, Computer, v.21 n.7, p.47-55, July 1988 [doi>10.1109/2.68]
• MARS 89: G-S Jang, et al., "MARS-Multiprocessor Architecture Reconciling Symbolic with Numerical Processing," Int'l Symp. VLSI Technology, Systems, and Applications., May 1989, pp. 365-370.
• Tho 64: J. E. Thornton, Parallel Operation in the Control Data 6600, Proc. Fall Joint Camp. Conf., Part 2, Vol. 26, 1964, pp. 33-40.
• Tom 67: R. M. Tomasulo, "An Efficient Algorithm for Exploiting Multiple Arithmetic Units," IBM Journal of Res. and Devt., Vol. 11, No. 1, Jan. 1967, pp. 25-33.
• Tow 76: Ross Albert Towle, Control and data dependence for program transformations., 1976