Improving performance of simple cores by exploiting loop-level parallelism through value prediction and reconfiguration

ABSTRACT

There is a growing trend towards designing simpler CPU cores that have considerable area, complexity, and power advantages. These cores are then leveraged in large-scale multicore processors or in SoCs for hand-held devices. The most significant limitation of such simple CPU cores is their lower performance. In this paper, we propose a technique to improve the performance of simple cores with minimal increase in complexity and area. In particular, we integrate a Reconfigurable Hardware Unit (RHU) that exploits loop-level parallelism to increase the core's overall performance. The RHU is reconfigured to execute instructions with highly predictable operand values from the future iterations of loops. Our experiments show that the proposed architecture improves the performance by an average of about 51% across a wide range of applications, while incurring a area overhead of only about 5.6%.

REFERENCES

• 1: Kubilay Atasu , Laura Pozzi , Paolo Ienne, Automatic application-specific instruction-set extensions under microarchitectural constraints, Proceedings of the 40th annual Design Automation Conference, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775897]
• 2: Peter M. Athanas , Harvey F. Silverman, Processor reconfiguration through instruction-set metamorphosis, Computer, v.26 n.3, p.11-18, March 1993 [doi>10.1109/2.204677]
• 3: Anne Bracy , Prashant Prahlad , Amir Roth, Dataflow Mini-Graphs: Amplifying Superscalar Capacity and Bandwidth, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.18-29, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.15]
• 4: Anne Bracy , Amir Roth, Serialization-Aware Mini-Graphs: Performance with Fewer Resources, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.171-184, December 09-13, 2006 [doi>10.1109/MICRO.2006.45]
• 5: Philip Brisk , Adam Kaplan , Ryan Kastner , Majid Sarrafzadeh, Instruction generation and regularity extraction for reconfigurable processors, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581672]
• 6: D. Burger and T.M. Austin, The Simple Scalar Tool Set, Version 2.0, em Computer Arch. News, June 1997.
• 7: Timothy J. Callahan , John R. Hauser , John Wawrzynek, The Garp Architecture and C Compiler, Computer, v.33 n.4, p.62-69, April 2000 [doi>10.1109/2.839323]
• 8: Yuan Chou , Pazhani Pillai , Herman Schmit , John Paul Shen, PipeRench implementation of the instruction path coprocessor, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.147-158, December 2000, Monterey, California, United States [doi>10.1145/360128.360144]
• 9: Nathan Clark , Jason Blome , Michael Chu , Scott Mahlke , Stuart Biles , Krisztian Flautner, An Architecture Framework for Transparent Instruction Set Customization in Embedded Processors, Proceedings of the 32nd annual international symposium on Computer Architecture, p.272-283, June 04-08, 2005
• 10: Nathan Clark , Hongtao Zhong , Scott Mahlke, Processor Acceleration Through Automated Instruction Set Customization, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.129, December 03-05, 2003
• 11: Nathan Clark , Manjunath Kudlur , Hyunchul Park , Scott Mahlke , Krisztian Flautner, Application-Specific Processing on a General-Purpose Core via Transparent Instruction Set Customization, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.30-40, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.5]
• 12: Nathan Clark , Amir Hormati , Scott Mahlke, VEAL: Virtualized Execution Accelerator for Loops, Proceedings of the 35th International Symposium on Computer Architecture, p.389-400, June 21-25, 2008
• 13: Marc L. Corliss , E. Christopher Lewis , Amir Roth, DISE: a programmable macro engine for customizing applications, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 14: Brian Fahs , Satarupa Bose , Matthew Crum , Brian Slechta , Francesco Spadini , Tony Tung , Sanjay J. Patel , Steven S. Lumetta, Performance characterization of a hardware mechanism for dynamic optimization, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 15: David Ruimy Gonzales, Micro-RISC Architecture for the Wireless Market, IEEE Micro, v.19 n.4, p.30-37, July 1999 [doi>10.1109/40.782565]
• 16: David Goodwin , Darin Petkov, Automatic generation of application specific processors, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951730]
• 17: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 18: S. Hauck , T. W. Fry , M. M. Hosler , J. P. Kao, The Chimaera reconfigurable functional unit, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.87, April 16-18, 1997
• 19: Steven K. Hsu , Amit Agarwal , Kaushik Roy , Ram K. Krishnamurthy , Shekhar Borkar, An 8.3GHz dual supply/threshold optimized 32b integer ALU-register file loop in 90nm CMOS, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA [doi>10.1145/1077603.1077630]
• 20: Lance Hammond , Basem A. Nayfeh , Kunle Olukotun, A Single-Chip Multiprocessor, Computer, v.30 n.9, p.79-85, September 1997 [doi>10.1109/2.612253]
• 21: María Jesús Garzarán , Milos Prvulovic , José María Llabería , Víctor Viñals , Lawrence Rauchwerger , Josep Torrellas, Tradeoffs in buffering speculative memory state for thread-level speculation in multiprocessors, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.3, p.247-279, September 2005 [doi>10.1145/1089008.1089010]
• 22: I. Huang and A.M. Despain, Synthesis of application specific instruction sets IEEE TCAD, 1995
• 23: Zhining Huang , Sharad Malik , Nahri Moreano , Guido Araujo, The design of dynamically reconfigurable datapath coprocessors, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.2, p.361-384, May 2004 [doi>10.1145/993396.993403]
• 24: Christian Iseli , Eduardo Sanchez, Spyder: a SURE (SUperscalar and REconfigurable) processor, The Journal of Supercomputing, v.9 n.3, p.231-252, 1995 [doi>10.1007/BF01212870]
• 25: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 26: 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
• 27: S. Lieberman et al., Extracting Statistical Loop-Level Parallelism using Hardware-Assisted Recovery, University of Michigan CSE Technical Report, CSE-TR-528-07, 2007
• 28: Sun Microsystems, Inc. OpenSPARC T1 Micro Architecture Specification, Sun Microsystems, Inc., 2006.
• 29: Subbarao Palacharla , Norman P. Jouppi , J. E. Smith, Complexity-effective superscalar processors, Proceedings of the 24th annual international symposium on Computer architecture, p.206-218, June 01-04, 1997, Denver, Colorado, United States
• 30: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
• 31: B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192731]
• 32: 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]
• 33: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 34: Fei Sun , Srivaths Ravi , Anand Raghunathan , Niraj K. Jha, Synthesis of custom processors based on extensible platforms, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.641-648, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774667]
• 35: T. Suri et al., Scalable Multi-cores with Improved Per-core Performance using Off-the-critical Path Reconfigurable Hardware Proc. IEEE International Conference on High Performance Computing, 2008
• 36: Tameesh Suri , Aneesh Aggarwal, Improving Scalability and Per-Core Performance in Multi-Cores through Resource Sharing and Reconfiguration, Proceedings of the 2009 22nd International Conference on VLSI Design, p.145-150, January 05-09, 2009 [doi>10.1109/VLSI.Design.2009.58]
• 37: TSMC 90nm Core Library -- TCBN90GHP, Application Note -- Revision 1.2, 2006
• 38: Kai Wang , Manoj Franklin, Highly accurate data value prediction using hybrid predictors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.281-290, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 39: R. Wittig and P. Chow, Onechip: An fpga processor with reconfigurable logic, Proc. FCCM, 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Pipeline processors**

General Terms:
Design

Keywords:
data value prediction, dynamic reconfiguration, loop level parallelism