SmartApps: middle-ware for adaptive applications on reconfigurable platforms

ABSTRACT

One general avenue to obtain optimized performance on large and complex systems is to approach optimization from a global perspective of the complete system in a customized manner for each application, i.e., application-centric optimization. Lately, there have been encouraging developments in reconfigurable operating systems and hardware that will enable customized optimization. For example, machines built with PIM's and FPGA's can be quickly reconfigured to better fit a certain application and operating systems, such as IBM's K42, can have their services customized to fit the needs and characteristics of an application. While progress in operating system and hardware and hardware has made re-configuration possible, we still need strategies and techniques to exploit them for improved application performance.In this paper, we describe the approach we are using in our smart application (SMARTAPPS) project. In the SMARTAPP executable, the compiler embeds most run-time system services and a feedback loop to monitor performance and trigger run-time adaptations. At run-time, after incorporating the code's input and determining the system's state, the SMARTAPP performs an instance specific optimization. During execution, the application continually monitors its performance and the available resources to determine if restructuring should occur. The framework includes mechanisms for performing the actual restructuring at various levels including: algorithmic adaptation, tuning reconfigurable OS services (scheduling policy, page size, etc.), and system configuration (e.g., number of processors). This paper concentrates on the techniques for providing customized system services for communication, thread scheduling, memory management, and performance monitoring and modeling.

REFERENCES

• 1: The CHARM++ Programming Language Manual. http://charm.cs.uiuc.edu, 2000.
• 2: P. An, et al. STAPL: A standard template adaptive parallel C++ library. In Proc. of the Int. Workshop on Advanced Compiler Technology for High Performance and Embedded Processors, Bucharest, Romania, Jul. 2001.
• 3: J. Appavoo , M. Auslander , M. Butrico , D. M. da Silva , O. Krieger , M. F. Mergen , M. Ostrowski , B. Rosenburg , R. W. Wisniewski , J. Xenidis, Experience with K42, an open-source, Linux-compatible, scalable operating-system kernel, IBM Systems Journal, v.44 n.2, p.427-440, January 2005
• 4: Peter H. Beckman , Dennis Gannon, Tulip: A Portable Run-Time System for Object-Parallel Systems, Proceedings of the 10th International Parallel Processing Symposium, p.532-536, April 15-19, 1996
• 5: Guy E. Blelloch, NESL: A Nested Data-Parallel Language (Version 2.6), Carnegie Mellon University, Pittsburgh, PA, 1993
• 6: Eric A. Brewer, High-level optimization via automated statistical modeling, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.80-91, July 19-21, 1995, Santa Barbara, California, United States
• 7: Calin Cascaval , Evelyn Duesterwald , Peter F. Sweeney , Robert W. Wisniewski, Multiple Page Size Modeling and Optimization, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.339-349, September 17-21, 2005 [doi>10.1109/PACT.2005.32]
• 8: Chialin Chang , Alan Sussman , Joel Saltz, Object-oriented runtime support for complex distributed data structures, University of Maryland at College Park, College Park, MD, 1995
• 9: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 10: Francis H. Dang , Lawrence Rauchwerger, Speculative Parallelization of Partially Parallel Loops, Selected Papers from the 5th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.285-299, May 25-27, 2000
• 11: Ewa Deelman , Aditya Dube , Adolfy Hoisie , Yong Luo , Richard L. Oliver , David Sundaram-Stukel , Harvey Wasserman , Vikram S. Adve , Rajive Bagrodia , James C. Browne , Elias Houstis , Olaf Lubeck , John Rice , Patricia J. Teller , Mary K. Vernon, Poems: end-to-end performance design of large parallel adaptive computational systems, Proceedings of the 1st international workshop on Software and performance, p.18-30, October 12-16, 1998, Santa Fe, New Mexico, United States [doi>10.1145/287318.292468]
• 12: Ian Foster , Carl Kesselman , Steven Tuecke, The Nexus approach to integrating multithreading and communication, Journal of Parallel and Distributed Computing, v.37 n.1, p.70-82, Aug. 25, 1996 [doi>10.1006/jpdc.1996.0108 ]
• 13: Matteo Frigo , Charles E. Leiserson , Keith H. Randall, The implementation of the Cilk-5 multithreaded language, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.212-223, June 17-19, 1998, Montreal, Quebec, Canada
• 14: Madhusudhan Govindaraju , Aleksander Slominski , Venkatesh Choppella , Randall Bramley , Dennis Gannon, Requirements for and evaluation of RMI protocols for scientific computing, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.61-es, November 04-10, 2000, Dallas, Texas, United States
• 15: Elizabeth L. Johnson , Dennis Gannon, Support for parallel generic programming, 1998
• 16: Elizabeth Johnson , Dennis Gannon, HPC++: experiments with the parallel standard template library, Proceedings of the 11th international conference on Supercomputing, p.124-131, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263614]
• 17: A. Jula and L. Rauchwerger. Defero memory allocator: A semantic driven memory allocator. Tech. Rep. TR-JR-05, Parasol Lab, Dept. of Computer Science, Texas A&M Univ., Nov. 2005.
• 18: Laxmikant V. Kale , Sanjeev Krishnan, CHARM++: a portable concurrent object oriented system based on C++, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.91-108, September 26-October 01, 1993, Washington, D.C., United States
• 19: L. Kale and S. Krishnan. Charm++: Parallel programming with message-driven objects. In Gregory Wilson and Paul Lu, editors, Parallel Programming using C++, pp. 175--213. Cambridge, MA: MIT Press, 1996.
• 20: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 21: Xiaoming Li , María Jesús Garzarán , David Padua, A Dynamically Tuned Sorting Library, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.111, March 20-24, 2004, Palo Alto, California
• 22: M. Olszewski and M. Voss. Proc. of the International Conference on Parallel and Distributed Processing Techniques and Applications, June 21--24, 2004. In Hamid R. Arabnia, editor, PDPTA. CSREA Press, 2004.
• 23: M. Puschl et al. SPIRAL: Code Generation for DSP Transforms. Proceedings of the IEEE special issue on Program Generation, Optimization, and Adaptation, 93(2):232--275, 2005.
• 24: Lawrence Rauchwerger , Nancy M. Amato , David A. Padua, A scalable method for run-time loop parallelization, International Journal of Parallel Programming, v.23 n.6, p.537-576, Dec. 1995 [doi>10.1007/BF02577866]
• 25: Lawrence Rauchwerger , David A. Padua, The LRPD Test: Speculative Run-Time Parallelization of Loops with Privatization and Reduction Parallelization, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.160-180, February 1999 [doi>10.1109/71.752782 ]
• 26: Lawrence Rauchwerger , David A. Padua, Parallelizing while loops for multiprocessor systems, Proceedings of the 9th International Symposium on Parallel Processing, p.347-356, April 25-28, 1995
• 27: J. Reynders. Pooma: A framework for scientific simulation on parallel architectures, 1996. In Wilson, G., Lu, P. (Eds.): Parallel Programming using C++. M.I.T. Press, pp. 553--594, 1996.
• 28: J. R. Rice. The algorithm selection problem. Advances in Computers, 15:65--118, 1976.
• 29: Silvius Rus , Lawrence Rauchwerger , Jay Hoeflinger, Hybrid analysis: static & dynamic memory reference analysis, International Journal of Parallel Programming, v.31 n.4, p.251-283, August 2003 [doi>10.1023/A:1024597010150]
• 30: T. Sheffler. A portable MPI-based parallel vector template library. Tech. Rep. RIACS-TR-95.04, Research Inst. for Advanced Computer Science, March 1995.
• 31: Nathan Thomas , Gabriel Tanase , Olga Tkachyshyn , Jack Perdue , Nancy M. Amato , Lawrence Rauchwerger, A framework for adaptive algorithm selection in STAPL, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065981]
• 32: D. Vallejo, C. V. Jones, and N. M. Amato. An adaptive framework for 'single shot' motion planning. In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 1722--1727, 2000.
• 33: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
• 34: Richard Vuduc , James W. Demmel , Jeff A. Bilmes, Statistical Models for Empirical Search-Based Performance Tuning, International Journal of High Performance Computing Applications, v.18 n.1, p.65-94, February 2004 [doi>10.1177/1094342004041293]
• 35: R. Whaley, A. Petitet, and J. Dongarra. Automated empirical optimizations of software and the ATLAS project. Parallel Computing, 27(1-2):3--35, Jan. 2001.
• 36: Gregory V. Wilson , Paul Lu , Bjane Stroustrup, Parallel Programming Using C++, MIT Press, Cambridge, MA, 1996
• 37: Hao Yu , Lawrence Rauchwerger, Adaptive reduction parallelization techniques, Proceedings of the 14th international conference on Supercomputing, p.66-77, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335238]
• 38: Hao Yu , Dongmin Zhang , Lawrence Rauchwerger, An Adaptive Algorithm Selection Framework, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.278-289, September 29-October 03, 2004 [doi>10.1109/PACT.2004.6]
• 39: M. Morales, L. Tapia, R. Pearce, S. Rodriguez, and N. M. Amato. A machine learning approach for feature-sensitive motion planning. In Proc. Int. Workshop on Algorithmic Foundations of Robotics (WAFR), Utrecht/Zeist, The Netherlands, July 2004.
• 40: M. A. Morales et. al. C-space subdivision and integration in feature-sensitive motion planning. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), April 2005.
• 41: R. Wisniewski, et. al. Performance and Environment Monitoring for Whole-System Characterization and Optimization in Proc. Conf. on Power/Performance interaction with Architecture, Circuits and Compilers 2004.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies
      D.4.8 Performance
          Subjects: Monitors; Modeling and prediction

General Terms:
Design, Performance