Reducing control overhead in dataflow architectures

ABSTRACT

In recent years, computer architects have proposed tiled architectures in response to several emerging problems in processor design, such as design complexity, wire delay, and fabrication reliability. One of these architectures, WaveScalar, uses a dynamic, tagged-token dataflow execution model to simplify the design of the processor tiles and their interconnection network and to achieve good parallel performance. However, using a dataflow execution model reawakens old problems, including the instruction overhead required for control flow. Previous work compiling the functional language Id to the Monsoon Dataflow System found this overhead to be 2–3× that of programs written in C and targeted to a MIPS R3000.In this paper, we present and analyze three compiler optimizations that significantly reduce control overhead with minimal additional hardware. We begin by describing how to translate imperative code into dataflow assembly and analyze the resulting control overhead. We report a similar 2–4× instruction overhead, which suggests that the execution model, rather than a specific source language or target architecture, is responsible. Then, we present the compiler optimizations, each of which is designed to eliminate a particular type of control overhead, and analyze the extent to which they were able to do so. Finally, we evaluate the effect using all optimizations together has on program performance. Together, the optimizations reduce control overhead by 80% on average, increasing application performance between 21–37%.

REFERENCES

• 1: Michael Bedford Taylor , Jason Kim , Jason Miller , David Wentzlaff , Fae Ghodrat , Ben Greenwald , Henry Hoffman , Paul Johnson , Jae-Wook Lee , Walter Lee , Albert Ma , Arvind Saraf , Mark Seneski , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs, IEEE Micro, v.22 n.2, p.25-35, March 2002 [doi>10.1109/MM.2002.997877]
• 2: Ken Mai , Tim Paaske , Nuwan Jayasena , Ron Ho , William J. Dally , Mark Horowitz, Smart Memories: a modular reconfigurable architecture, Proceedings of the 27th annual international symposium on Computer architecture, p.161-171, June 2000, Vancouver, British Columbia, Canada
• 3: Ramadass Nagarajan , Karthikeyan Sankaralingam , Doug Burger , Stephen W. Keckler, A design space evaluation of grid processor architectures, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 4: Steven Swanson , Ken Michelson , Andrew Schwerin , Mark Oskin, WaveScalar, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.291, December 03-05, 2003
• 5: Steven Swanson , Andrew Putnam , Martha Mercaldi , Ken Michelson , Andrew Petersen , Andrew Schwerin , Mark Oskin , Susan J. Eggers, Area-Performance Trade-offs in Tiled Dataflow Architectures, Proceedings of the 33rd annual international symposium on Computer Architecture, p.314-326, June 17-21, 2006
• 6: T. Shimada , K. Hiraki , K. Nishida , S. Sekiguchi, Evaluation of a prototype data flow processor of the SIGMA-1 for scientific computations, Proceedings of the 13th annual international symposium on Computer architecture, p.226-234, June 02-05, 1986, Tokyo, Japan
• 7: J. R Gurd , C. C Kirkham , I. Watson, The Manchester prototype dataflow computer, Communications of the ACM, v.28 n.1, p.34-52, Jan. 1985 [doi>10.1145/2465.2468]
• 8: Gregory M. Papadopoulos , Kenneth R. Traub, Multithreading: a revisionist view of dataflow architectures, Proceedings of the 18th annual international symposium on Computer architecture, p.342-351, May 27-30, 1991, Toronto, Ontario, Canada
• 9: S. Sakai , y. Yamaguchi , K. Hiraki , Y. Kodama , T. Yuba, An architecture of a dataflow single chip processor, Proceedings of the 16th annual international symposium on Computer architecture, p.46-53, April 1989, Jerusalem, Israel
• 10: Gregory M. Papadopoulos , David E. Culler, Monsoon: an explicit token-store architecture, Proceedings of the 17th annual international symposium on Computer Architecture, p.82-91, May 28-31, 1990, Seattle, Washington, United States
• 11: David E. Culler , Anurag Sah , Klaus E. Schauser , Thorsten von Eicken , John Wawrzynek, Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.164-175, April 08-11, 1991, Santa Clara, California, United States
• 12: K. Arvind , Rishiyur S. Nikhil, Executing a Program on the MIT Tagged-Token Dataflow Architecture, IEEE Transactions on Computers, v.39 n.3, p.300-318, March 1990 [doi>10.1109/12.48862]
• 13: "The WaveScalar architecture," In submission to ACM Transactions on Computer Systems (TOCS), 2006.
• 14: Arvind, "Dataflow: Passing the token," in Keynote at the International Symposium on Computer Architecture (ISCA), 2005.
• 15: David E. Culler , Klaus E. Schauser , Thorsten von Eicken, Two Fundamental Limits on Dataflow Multiprocessing, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.153-164, January 20-22, 1993
• 16: James Hicks , Derek Chiou , Boon Seong Ang , Arvind, Performance studies of Id on the Monsoon dataflow system, Journal of Parallel and Distributed Computing, v.18 n.3, p.273-300, July 1993 [doi>10.1006/jpdc.1993.1065]
• 17: David A. Patterson , John Hennessy, Computer Organization and Design, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 18: Jack B. Dennis , David P. Misunas, A preliminary architecture for a basic data-flow processor, Proceedings of the 2nd annual symposium on Computer architecture, p.126-132, January 20-22, 1975
• 19: A. L. Davis, The architecture and system method of DDM1: A recursively structured Data Driven Machine, Proceedings of the 5th annual symposium on Computer architecture, p.210-215, April 03-05, 1978 [doi>10.1145/800094.803050]
• 20: 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
• 21: Aaron Smith , Jon Gibson , Bertrand Maher , Nick Nethercote , Bill Yoder , Doug Burger , Kathryn S. McKinle , Jim Burrill, Compiling for EDGE Architectures, Proceedings of the International Symposium on Code Generation and Optimization, p.185-195, March 26-29, 2006 [doi>10.1109/CGO.2006.10]
• 22: Ramadass Nagarajan , Sundeep K. Kushwaha , Doug Burger , Kathryn S. McKinley , Calvin Lin , Stephen W. Keckler, Static Placement, Dynamic Issue (SPDI) Scheduling for EDGE Architectures, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.74-84, September 29-October 03, 2004 [doi>10.1109/PACT.2004.26]
• 23: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 24: Martha Mercaldi , Steven Swanson , Andrew Petersen , Andrew Putnam , Andrew Schwerin , Mark Oskin , Susan J. Eggers, Instruction scheduling for a tiled dataflow architecture, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 25: 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]
• 26: R. Nikhil, "The parallel programming language id and its compilation for parallel machines," in the Workshop on Mazzive Paralleism: Hardware, Programming and Applications, Acamedic Press, 1990.
• 27: K. R. Traub, A COMPILER FOR THE MIT TAGGED-TOKEN DATAFLOW ARCHITECTURE, Massachusetts Institute of Technology, Cambridge, MA, 1986
• 28: Mihai Budiu , Girish Venkataramani , Tiberiu Chelcea , Seth Copen Goldstein, Spatial computation, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 29: Mihai Budiu , Seth C. Goldstein, Optimizing memory accesses for spatial computation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 30: D. E. Culler, S. C. Goldstein, K. E. Schauser, and T. von Eicken, "Empirical study of a dataflow language on the CM-5," in the 2nd Workshop on Dataflow Computing, pp. 187--210, 1992.
• 31: 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
• 32: M. Budiu, P. V. Artigas, and S. C. Goldstein, "Dataflow: A complement to superscalar," in the IEEE International Symposium on Performance Analysis of Systems and Software, pp. 177--186, 2005.
• 33: Rishiyur S. Nikhil, A Multithreaded Implementation of Id using P-RISC Graphs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.390-405, August 12-14, 1993
• 34: S. Lennart Johnsson, The connection machine systems CM-5, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.365-366, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.157377]
• 35: David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser , Thorsten von Eicken, TAM—a compiler controlled threaded abstract machine, Journal of Parallel and Distributed Computing, v.18 n.3, p.347-370, July 1993 [doi>10.1006/jpdc.1993.1070]
• 36: Mihai Budiu , Seth Copen Goldstein, Compiling Application-Specific Hardware, Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications, p.853-863, September 02-04, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Performance

Keywords:
Wavescalar, compiler, dataflow, tiled architecture