Virtual multiprocessor: an analyzable, high-performance architecture for real-time computing

ABSTRACT

The design of a real-time architecture is governed by a trade-off between analyzability necessary for real-time formalism and performance demanded by high-end embedded systems. We reconcile this trade-off with a novel Real-time Virtual Multiprocessor (RVMP). RVMP virtualizes a single in-order superscalar processor into multiple interference-free different-sized virtual processors. This provides a flexible spatial dimension. In the time dimension, the number and size of virtual processors can be rapidly reconfigured. A simple real-time scheduling approach concentrates scheduling within a small time interval, producing a simple repeating space/time schedule that orchestrates virtualization. RVMP successfully combines the analyzability (hence real-time formalism) of multiple processors with the flexibility (hence high performance) of simultaneous multithreading (SMT).Worst-case schedulability experiments show that more task-sets are provably schedulable on RVMP than on conventional rigid multiprocessors with equal aggregate resources, and the advantage only intensifies with more demanding task-sets. Run-time experiments show RVMP's statically-controlled coarser-grain space/time configurability is as effective as unsafe SMT. Moreover, RVMP provides a real-time formalism that SMT does not currently provide.

REFERENCES

• 1: Aravindh Anantaraman , Kiran Seth , Kaustubh Patil , Eric Rotenberg , Frank Mueller, Virtual simple architecture (VISA): exceeding the complexity limit in safe real-time systems, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 2: A. Anantaraman, K. Seth, E. Rotenberg, and F. Mueller. Exploiting VISA for Higher Concurrency in Safe Real-Time Systems. Tech. Report TR-2004-15, CS Dept., NC State Univ., May 2004.
• 3: Francois Bodin , Isabelle Puaut, A WCET-Oriented Static Branch Prediction Scheme for Real Time Systems, Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS'05), p.33-40, July 06-08, 2005 [doi>10.1109/ECRTS.2005.33]
• 4: D. Burger, T. M. Austin, and S. Bennett. The Simplescalar Toolset, Version 2. Tech. Report CS-TR-1997-1342, CS Dept., Univ. of Wisconsin-Madison, July 1997.
• 5: C-Lab. WCET Benchmarks. Available from http://www.c-lab.de/index.php?id=462&L=3.
• 6: Francisco J. Cazorla , Alex Ramirez , Mateo Valero , Peter M. W. Knijnenburg , Rizos Sakellariou , Enrique Fernández, QoS for High-Performance SMT Processors in Embedded Systems, IEEE Micro, v.24 n.4, p.24-31, July 2004 [doi>10.1109/MM.2004.37]
• 7: B. Chazelle. The Bottom-Left Bin-Packing Heuristic: An Efficient Implementation. IEEE Trans. on Computers, 32(8):697--707, 1983.
• 8: D. Cormie. The ARM11 Microarchitecture. White paper, Apr. 2002.
• 9: P. Crowley and J.-L. Baer. Worst-Case Execution Time Estimation of Hardware-assisted Multithreaded Processors. In Proc. of the 2nd Workshop on Network Processors, pp. 36--47, Feb. 2003.
• 10: A. G. Dean , J. P. Shen, Techniques for Software Thread Integration in Real-Time Embedded Systems, Proceedings of the IEEE Real-Time Systems Symposium, p.322, December 02-04, 1998
• 11: E. G. Coffman, Jr. , M. R. Garey , D. S. Johnson, Approximation algorithms for bin packing: a survey, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 12: John H. Edmondson , Paul Rubinfeld , Ronald Preston , Vidya Rajagopalan, Superscalar Instruction Execution in the 21164 Alpha Microprocessor, IEEE Micro, v.15 n.2, p.33-43, April 1995 [doi>10.1109/40.372349]
• 13: Ali El-Haj-Mahmoud , Eric Rotenberg, Safely exploiting multithreaded processors to tolerate memory latency in real-time systems, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023837]
• 14: Ali El-Moursy , David H. Albonesi, Front-End Policies for Improved Issue Efficiency in SMT Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.31, February 08-12, 2003
• 15: Marco Fillo , Stephen W. Keckler , William J. Dally , Nicholas P. Carter , Andrew Chang , Yevgeny Gurevich , Whay S. Lee, The M-Machine multicomputer, Proceedings of the 28th annual international symposium on Microarchitecture, p.146-156, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 16: M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown. MiBench: A Free, Commercially Representative Embedded Benchmark Suite. In Proc. of the 4th Workshop on Workload Characterization, Dec. 2001.
• 17: T. Hand. Real-Time Systems Need Predictability. Computer Design (RISC Supplement), pp. 57--59, Aug. 1989.
• 18: M. G. Harmon, T. P. Baker, and D. B. Whalley. A Retargetable Technique for Predicting Execution Time of Code Segments. In Proc. of the 13th Int'l Real-Time Systems Symp., pp. 68--77, Dec. 1992.
• 19: S. Hily , A. Seznec, Out-of-Order Execution may not be Cost-Effective on Processors Featuring Simultaneous Multithreading, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.64, January 09-12, 1999
• 20: IBM Corp. IBM PowerPC 740 / PowerPC 750 RISC Microprocessor User's Manual. Feb. 1999.
• 21: Bharath Iyer , Sadagopan Srinivasan , Bruce Jacob, Extended Split-Issue: Enabling Flexibility in the Hardware Implementation of NUAL VLIW DSPs, Proceedings of the 31st annual international symposium on Computer architecture, p.364, June 19-23, 2004, München, Germany
• 22: Rohit Jain , Christopher J. Hughes , Sarita V. Adve, Soft Real- Time Scheduling on Simultaneous Multithreaded Processors, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.134, December 03-05, 2002
• 23: Stefanos Kaxiras , Girija Narlikar , Alan D. Berenbaum , Zhigang Hu, Comparing power consumption of an SMT and a CMP DSP for mobile phone workloads, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502254]
• 24: D. B. Kirk. SMART (Strategic Memory Allocation for Real-Time) Cache Design. In Proc. of the 10th Int'l Real-Time Systems Symp., pp. 229--239, Dec. 1989.
• 25: J. Kreuzinger , A. Schulz , M. Pfeffer , T. Ungerer , U. Brinkschulte , C. Krakowski, Real-time scheduling on multithreaded processors, Proceedings of the Seventh International Conference on Real-Time Systems and Applications (RTCSA'00), p.155, December 12-14, 2000
• 26: Xianfeng Li , Abhik Roychoudhury , Tulika Mitra, Modeling Out-of-Order Processors for Software Timing Analysis, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04), p.92-103, December 05-08, 2004 [doi>10.1109/REAL.2004.33]
• 27: Y.-T. S. Li , S. Malik , A. Wolfe, Efficient microarchitecture modeling and path analysis for real-time software, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.298, December 05-07, 1995
• 28: Jörg Liebeherr , Almut Burchard , Yingfeng Oh , Sang H. Son, New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems, IEEE Transactions on Computers, v.44 n.12, p.1429-1442, December 1995 [doi>10.1109/12.477248]
• 29: S.-S. Lim , J. H. Han , J. Kim , S. L. Min, A Worst Case Timing Analysis Technique for Multiple-Issue Machines, Proceedings of the IEEE Real-Time Systems Symposium, p.334, December 02-04, 1998
• 30: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 31: Jane W. S. W. Liu, Real-Time Systems, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 32: Thomas Lundqvist , Per Stenström, An Integrated Path and Timing Analysis Method based onCycle-Level Symbolic Execution, Real-Time Systems, v.17 n.2-3, p.183-207, Nov. 1999 [doi>10.1023/A:1008138407139]
• 33: Mario Daniel Nemirovsky , Forrest Brewer , Roger C. Wood, DISC: dynamic instruction stream computer, Proceedings of the 24th annual international symposium on Microarchitecture, p.163-171, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123498]
• 34: Yingfeng Oh , Sang H. Son, Fixed-Priority Scheduling of Periodic Tasks on Multiprocessor Systems, University of Virginia, Charlottesville, VA, 1995
• 35: Emre Özer , Thomas M. Conte , Saurabh Sharma, Weld: A Multithreading Technique Towards Latency-Tolerant VLIW Processors, Proceedings of the 8th International Conference on High Performance Computing, p.192-203, December 17-20, 2001
• 36: Steven E. Raasch , Steven K. Reinhardt, The Impact of Resource Partitioning on SMT Processors, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.15, September 27-October 01, 2003
• 37: B. Smith. Architecture and Applications of the HEP Multiprocessor Computer System. In Proc. of the 4th Symp. on Real Time Signal Processing IV, pp. 241--248, 1981.
• 38: Nathan Tuck , Dean M. Tullsen, Initial Observations of the Simultaneous Multithreading Pentium 4 Processor, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.26, September 27-October 01, 2003
• 39: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 40: Ubicom, Inc. The Ubicom IP3023 Wireless Network Processor. White paper, Apr. 2003.
• 41: Sumesh Udayakumaran , Rajeev Barua, Compiler-decided dynamic memory allocation for scratch-pad based embedded systems, 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.951747]
• 42: Andrew Wolfe, Software-based cache partitioning for real-time applications, Journal of Computer and Software Engineering, v.2 n.3, p.315-327, 1994
• 43: Andrew Wolfe , John P. Shen, A variable instruction stream extension to the VLIW architecture, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.2-14, April 08-11, 1991, Santa Clara, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

General Terms:
Design, Performance

Keywords:
hard real-time, resource partitioning, schedulability analysis, simultaneous multithreading, superscalar processor, worst-case execution time