Hardware implementation of a general multi-way jump mechanism

ABSTRACT

A VLIW architecture capable of testing multiple conditions in one cycle must support effective multiway (conditional) jumps. In this paper, a hardware-implemented, fast, and space-efficient multi-way jump mechanism is developed that speeds up the execution of multiple conditional jumps and reduces wasted storage. A cluster of multiple conditional jumps packed in an instruction can form an arbitrary rooted DAG (Directed Acyclic Graph), where each node corresponds to a condition. Our scheme provides a hardware device called an M-unit, which can combinationally produce the next target address using an encoded description of the DAG and the actual test bits. A technique to reduce the number of different configurations is introduced, along with a memory packing scheme that minimizes wasted memory.

REFERENCES

• 1: F. Gasperoni. Compilation techniques for VLIW architectures. Research Report RC 14915, IBM Research Division, T.J. Watson Research Center, Sep 1989.
• 2: D. R. Ditzel , H. R. McLellan, Branch folding in the CRISP microprocessor: reducing branch delay to zero, Proceedings of the 14th annual international symposium on Computer architecture, p.2-8, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30351]
• 3: Joseph A. Fisher, 2n-way jump microinstruction hardware and an effective instruction binding method, Proceedings of the 13th annual workshop on Microprogramming, p.64-75, November 30-December 03, 1980, Springs, Colorado, United States
• 4: John R. Ellis, Bulldog: a compiler for vliw architectures (parallel computing, reduced-instruction-set, trace scheduling, scientific), 1985
• 5: Joseph A. Fisher, Very Long Instruction Word architectures and the ELI-512, Proceedings of the 10th annual international symposium on Computer architecture, p.140-150, June 13-17, 1983, Stockholm, Sweden
• 6: J. Fisher. The VLIW machine: a multiprocessor for compiling scientific code. IEEE Computer, pages 45- 53, July 1984.
• 7: A. Aiken , A. Nicolau, A Development Environment for Horizontal Microcode, IEEE Transactions on Software Engineering, v.14 n.5, p.584-594, May 1988 [doi>10.1109/32.6136]
• 8: Alexandru Nicolau, Percolation Scheduling: A Parallel Compilation Technique, Cornell University, Ithaca, NY, 1985
• 9: K. Karplus , A. Nicolau, Efficient hardware for multiway jumps and pre-fetches, Proceedings of the 18th annual workshop on Microprogramming, p.11-18, December 03-06, 1985, Pacific Grove, California, United States
• 10: S. Moon, S. Carson, and A. Agrawala. Hardware implementation of a general multi-way jump. Technical Report CSC 733, Univ. of Maryland, Aug 1990.
• 11: Robert P. Colwell , Robert P. Nix , John J. O'Donnell , David B. Papworth , Paul K. Rodman, A VLIW architecture for a trace Scheduling Compiler, IEEE Transactions on Computers, v.37 n.8, p.967-979, August 1988 [doi>10.1109/12.2247]
• 12: K. Ebcioglu. Some design ideas for a VLIW architecture for sequential natured software. Proceedings of IFIP WG 10.3 Working Conference on Parallel Processing(Pisa, Italy), pages 3-17, April 1988.
• 13: S. McFarling , J. Hennesey, Reducing the cost of branches, Proceedings of the 13th annual international symposium on Computer architecture, p.396-403, June 02-05, 1986, Tokyo, Japan
• 14: K. Karplus and A. Nicolau. Getting high performance with slow memory. In Proceedings of Compcon'86, pages 248-252, 1986.