Tartan: evaluating spatial computation for whole program execution

ABSTRACT

Spatial Computing (SC) has been shown to be an energy-efficient model for implementing program kernels. In this paper we explore the feasibility of using SC for more than small kernels. To this end, we evaluate the performance and energy efficiency of entire applications on Tartan, a general-purpose architecture which integrates a reconfigurable fabric (RF) with a superscalar core. Our compiler automatically partitions and compiles an application into an instruction stream for the core and a configuration for the RF. We use a detailed simulator to capture both timing and energy numbers for all parts of the system.Our results indicate that a hierarchical RF architecture, designed around a scalable interconnect, is instrumental in harnessing the benefits of spatial computation. The interconnect uses static configuration and routing at the lower levels and a packet-switched, dynamically-routed network at the top level. Tartan is most energyefficient when almost all of the application is mapped to the RF, indicating the need for the RF to support most general-purpose programming constructs. Our initial investigation reveals that such a system can provide, on average, an order of magnitude improvement in energy-delay compared to an aggressive superscalar core on single-threaded workloads.

REFERENCES

• 1: Micah Beck , Richard Johnson , Keshav Pingali, From control flow to dataflow, Journal of Parallel and Distributed Computing, v.12 n.2, p.118-129, June 1991 [doi>10.1016/0743-7315(91)90016-3]
• 2: Tobias Bjerregaard , Jens Sparso, A Scheduling Discipline for Latency and Bandwidth Guarantees in Asynchronous Network-on-Chip, Proceedings of the 11th IEEE International Symposium on Asynchronous Circuits and Systems, p.34-43, March 14-16, 2005 [doi>10.1109/ASYNC.2005.7]
• 3: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 4: M. Budiu, P.V. Artigas, et al. Dataflow: A complement to superscalar. In IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 177--186, March 20-22 2005.
• 5: 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
• 6: M. Budiu and S.C. Goldstein. Pegasus: An efficient intermediate representation. Technical Report CMU-CS-02-107, Carnegie Mellon University, May 2002.
• 7: Mihai Budiu , Mahim Mishra , Ashwin R. Bharambe , Seth Copen Goldstein, Peer-to-Peer Hardware-Software Interfaces for Reconfigurable Fabrics, Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.57, September 22-24, 2002
• 8: 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
• 9: Timothy J. Callahan , John Wawrzynek, Adapting software pipelining for reconfigurable computing, Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, p.57-64, November 17-19, 2000, San Jose, California, United States [doi>10.1145/354880.354889]
• 10: Lori Carter , Beth Simon , Brad Calder , Larry Carter , Jeanne Ferrante, Path analysis and renaming for predicted instruction scheduling, International Journal of Parallel Programming, v.28 n.6, p.563-588, Dec. 2000 [doi>10.1023/A:1007512717742]
• 11: Tiberiu Chelcea , Steven M. Nowick, Robust interfaces for mixed-timing systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.8, p.857-873, August 2004 [doi>10.1109/TVLSI.2004.831476]
• 12: 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]
• 13: Maya B. Gokhale , Janice M. Stone , Edson Gomersall, Co-Synthesis to a Hybrid RISC/FPGA Architecture, Journal of VLSI Signal Processing Systems, v.24 n.2-3, p.165-180, Mar. 2000 [doi>10.1023/A:1008141305507]
• 14: S. C. Goldstein, The impact of the nanoscale on computing systems, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.655-661, November 06-10, 2005, San Jose, CA
• 15: Seth Copen Goldstein , Herman Schmit , Matthew Moe , Mihai Budiu , Srihari Cadambi , R. Reed Taylor , Ronald Laufer, PipeRench: a co/processor for streaming multimedia acceleration, Proceedings of the 26th annual international symposium on Computer architecture, p.28-39, May 01-04, 1999, Atlanta, Georgia, United States
• 16: Scott Hauck , Steven Burns , Gaetano Borriello , Carl Ebeling, An FPGA for Implementing Asynchronous Circuits, IEEE Design & Test, v.11 n.3, p.60-69, July 1994 [doi>10.1109/MDT.1994.303848]
• 17: J.R. Heath, P.J. Kuekes, et al. A defect-tolerant computer architecture: Opportunities for nanotechnology. Science, 280, 1998.
• 18: N. Huot , H. Dubreuil , L. Fesquet , M. Renaudin, FPGA Architecture for Multi-Style Asynchronous Logic, Proceedings of the conference on Design, Automation and Test in Europe, p.32-33, March 07-11, 2005 [doi>10.1109/DATE.2005.159]
• 19: Intel Corp. Intel Pentium M Datasheet, January 2006.
• 20: James Kao , Siva Narendra , Anantha Chandrakasan, Subthreshold leakage modeling and reduction techniques, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.141-148, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774593]
• 21: Ian Kuon , Jonathan Rose, Measuring the gap between FPGAs and ASICs, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117205]
• 22: E. Larson, S. Chatterjee, et al. MASE: A novel architecture or detailed microarchitectural modeling. In IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), November 4-6 2001.
• 23: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 24: Scott A. Mahlke , David C. Lin , William Y. Chen , Richard E. Hank , Roger A. Bringmann, Effective compiler support for predicated execution using the hyperblock, Proceedings of the 25th annual international symposium on Microarchitecture, p.45-54, December 01-04, 1992, Portland, Oregon, United States
• 25: 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
• 26: B.J. Nelson. Remote procedure call. Technical Report CSL-81-9, Xerox Palo Alto Research Center, 1981.
• 27: Rob Payne, Self-Timed FPGA Systems, Proceedings of the 5th International Workshop on Field-Programmable Logic and Applications, p.21-35, September 01, 1995
• 28: Rahul Razdan , Michael D. Smith, A high-performance microarchitecture with hardware-programmable functional units, Proceedings of the 27th annual international symposium on Microarchitecture, p.172-180, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192749]
• 29: Scott Rixner , William J. Dally , Ujval J. Kapasi , Brucek Khailany , Abelardo López-Lagunas , Peter R. Mattson , John D. Owens, A bandwidth-efficient architecture for media processing, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.3-13, November 1998, Dallas, Texas, United States
• 30: Karthikeyan Sankaralingam , Ramadass Nagarajan , Haiming Liu , Changkyu Kim , Jaehyuk Huh , Doug Burger , Stephen W. Keckler , Charles R. Moore, Exploiting ILP, TLP, and DLP with the polymorphous TRIPS architecture, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 31: H. Schmit, D. Whelihan, et al. Piperench: A virtualized programmable datapath in 0.18 micron technology. In IEEE Custom Integrated Circuits Conference, pages 63--66, 2002.
• 32: High-Level Power Modeling of CPLDs and FPGAs, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.46, September 23-26, 2001
• 33: Li Shang , Alireza S. Kaviani , Kusuma Bathala, Dynamic power consumption in Virtex™-II FPGA family, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503072]
• 34: Standard Performance Evaluation Corp. SPEC INT 95 Benchmark Suite, 1995.
• 35: Standard Performance Evaluation Corp. SPEC INT 2000 Benchmark Suite, 2000.
• 36: I. E. Sutherland, Micropipelines, Communications of the ACM, v.32 n.6, p.720-738, June 1989 [doi>10.1145/63526.63532]
• 37: 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
• 38: Michael Bedford Taylor , Walter Lee , Jason Miller , David Wentzlaff , Ian Bratt , Ben Greenwald , Henry Hoffmann , Paul Johnson , Jason Kim , James Psota , Arvind Saraf , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, Evaluation of the Raw Microprocessor: An Exposed-Wire-Delay Architecture for ILP and Streams, Proceedings of the 31st annual international symposium on Computer architecture, p.2, June 19-23, 2004, München, Germany
• 39: John Teifel , Rajit Manohar, An Asynchronous Dataflow FPGA Architecture, IEEE Transactions on Computers, v.53 n.11, p.1376-1392, November 2004 [doi>10.1109/TC.2004.88]
• 40: William Tsu , Kip Macy , Atul Joshi , Randy Huang , Norman Walker , Tony Tung , Omid Rowhani , Varghese George , John Wawrzynek , André DeHon, HSRA: high-speed, hierarchical synchronous reconfigurable array, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.125-134, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296442]
• 41: Girish Venkataramani , Tiberiu Chelcea , Seth Copen Goldstein , Tobias Bjerregaard, SOMA: a tool for synthesizing and optimizing memory accesses in ASICs, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084894]
• 42: G. Venkataramani, M. Budiu, et al. C to asynchronous dataflow circuits: An end-to-end toolflow. In International Workshop on Logic Synthesis, June 2004.
• 43: G. Venkataramani, T. Chelcea, et al. HLS support for unconstrained memory accesses. In International Workshop on Logic Syntheis, June 2005.
• 44: M. Wazlowski, L. Agarwal, et al. PRISM-II compiler and architecture. In IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), pages 9--16, Apr 1993.
• 45: C. Wong, A. Martin, et al. An architecture for asynchronous FPGAs. In Proceedings of Field Programmable Technology (FPT), pages 170--177, 2003.
• 46: Zhi Alex Ye , Andreas Moshovos , Scott Hauck , Prithviraj Banerjee, CHIMAERA: a high-performance architecture with a tightly-coupled reconfigurable functional unit, Proceedings of the 27th annual international symposium on Computer architecture, p.225-235, June 2000, Vancouver, British Columbia, Canada

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis; Simulation
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Heterogeneous (hybrid) systems

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

General Terms:
Design, Performance

Keywords:
asynchronous circuits, dataflow machine, defect tolerance, low power, reconfigurable hardware, spatial computation