Ideograph/Ideogram: framework/hardware for eager evaluation

ABSTRACT

Ideograph integrates data and control dependencies into a unified representation and is used to precisely characterize the concepts of branch prediction and eager evaluation. The Ideogram computer is designed to execute Ideographs. Unlike dataflow computers, The Ideogram computer accepts a 3-address code language called igf. Through igf, Ideographs are constructed and executed by the Ideogram computer at run-time. In this paper, the descriptions of both Ideograph and Ideogram computer are introduced, and the preliminary benchmark results are included.

REFERENCES

• 1: Tilak Agerwala and Arvind. Data flow systems. IEEE Computer, 15(2):10-13, 1982.
• 2: Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
• 3: Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
• 4: D. E. Culler , Arvind, Resource requirements of dataflow programs, Proceedings of the 15th Annual International Symposium on Computer architecture, p.141-150, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 5: Yoichi Muraoka David Kuck and Shyh-Ching Chen. On the number of operations simultaneously executable in fortran-like programs and their resulting speedup. IEEE Transactions on Computers, 21(12):1293-1310, December 1972.
• 6: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 7: J. A. Fisher. The vliw machine: A multiprocessor for compiling scientific code. IEEE Computer, pages 45-53, July 1984.
• 8: V. G. Grafe , G. S. Davidson , J. E. Hoch , V. P. Holmes, The Epsilon dataflow processor, Proceedings of the 16th annual international symposium on Computer architecture, p.36-45, April 1989, Jerusalem, Israel
• 9: Zhiyuan Li , Pen-Chung Yew, Some results on exact data dependence analysis, Selected papers of the second workshop on Languages and compilers for parallel computing, p.374-401, May 1990, Urbana, Illinois, United States
• 10: D.A. Padua, D.J. Kuck, and D.H. Lawrie. Highspeed multiprocessors and compilation techniques. IEEE Transactions on Computers, 29(9), September 1980.
• 11: Constantine Demetrios Polychronopoulos, On program restructuring, scheduling, and communication for parallel processor systems, 1986
• 12: E. M. Riseman and C. C. Foster. The inhibition of potential parallelism by conditional jumps. IEEE Transactions on Computers, pages 1405- 1411, December 1972.
• 13: J. E. Thorton. Parallel operation in the control data 6600. In AFIPS Proceedings of the Fall Joint Computer Conference, pages 33-40, 1964.
• 14: R. M. Tomasulo. An efficient algorithm for exploiting multiple arithmetic units. IBM Journal, pages 25-33, January 1967.
• 15: Augustus K. Uht, Desirable code transformations for a concurrent machine, Selected papers of the second workshop on Languages and compilers for parallel computing, p.511-530, May 1990, Urbana, Illinois, United States
• 16: Augustus K. Uht , Constantine D. Polychronopoulos , John F. Kolen, On the combination of hardware and software concurrency extraction methods, Proceedings of the 20th annual workshop on Microprogramming, p.133-141, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255331]
• 17: Augustus Kinzel Uht, Hardware extraction of low-level concurrency from sequential instruction streams (parallelism, implementation, architecture, dependencies, semantics), 1985
• 18: Harrick M. Vin, Francine Berman, and James Mattson. Controlled eager evaluation in a dynamic-arc tagged-token dataflow model. Technical Report TR-CS90-168, University of California, San Diego, La Jolla, Ca. 92093, January 1990.
• 19: S. ShouHan Wang and Augustus K. Uht. Ideograph and minimal procedural dependencies. Technical Report TR-CS88-140, University of California, San Diego, La Jolla, Ca., December 1988.
• 20: S. ShouHan Wang and Augustus K. Uht. Program optimization with ideograph. In International Conference on Parallel Processing, August 1989.
• 21: S. ShouHan Wang and Augustus K. Uht. Ideograph: An imperative program graph for eager evaluation. Technical Report TR-CS90-172, University of California, San Diego, La Jolla, Ca., September 1990.
• 22: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982