A framework for adaptive algorithm selection in STAPL

ABSTRACT

Writing portable programs that perform well on multiple platforms or for varying input sizes and types can be very difficult because performance is often sensitive to the system architecture, the run-time environment, and input data characteristics. This is even more challenging on parallel and distributed systems due to the wide variety of system architectures. One way to address this problem is to adaptively select the best parallel algorithm for the current input data and system from a set of functionally equivalent algorithmic options. Toward this goal, we have developed a general framework for adaptive algorithm selection for use in the Standard Template Adaptive Parallel Library (STAPL). Our framework uses machine learning techniques to analyze data collected by STAPL installation benchmarks and to determine tests that will select among algorithmic options at run-time. We apply a prototype implementation of our framework to two important parallel operations, sorting and matrix multiplication, on multiple platforms and show that the framework determines run-time tests that correctly select the best performing algorithm from among several competing algorithmic options in 86-100% of the cases studied, depending on the operation and the system.

REFERENCES

• 1: P. An, A. Jula, S. Rus, S. Saunders, T. Smith, G. Tanase, N. Thomas, N. Amato, and L. Rauchwerger. STAPL: A standard template adaptive parallel C++ library. In Proc. of the Intern. Workshop on Advanced Compiler Technology for High Performance and Embedded Processors (IWACT), Bucharest, Romania, July 2001.
• 2: P. An, A. Jula, S. Rus, S. Saunders, T. Smith, G. Tanase, N. Thomas, N. Amato, and L. Rauchwerger. STAPL: An adaptive, generic parallel programming library for C++. In Workshop on Languages and Compilers for Parallel Computing (LCPC), Cumberland Falls, KY, August 2001.
• 3: Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau , David E. Culler , Joseph M. Hellerstein , David A. Patterson, High-performance sorting on networks of workstations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.243-254, May 11-15, 1997, Tucson, Arizona, United States
• 4: Guy E. Blelloch , Charles E. Leiserson , Bruce M. Maggs , C. Greg Plaxton , Stephen J. Smith , Marco Zagha, A comparison of sorting algorithms for the connection machine CM-2, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.3-16, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113380]
• 5: Guy E. Blelloch , Jonathan C. Hardwick , Siddhartha Chatterjee , Jay Sipelstein , Marco Zagha, Implementation of a portable nested data-parallel language, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.102-111, May 19-22, 1993, San Diego, California, United States
• 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: W.H. Burge. Sorting, trees, and measures of order. Information and Control, 1(3):181--197, 1958.
• 8: Geeta Chaudhry , Thomas H. Cormen , Leonard F. Wisniewski, Columnsort lives! an efficient out-of-core sorting program, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.169-178, July 2001, Crete Island, Greece [doi>10.1145/378580.378627]
• 9: Jaeyoung Choi , Jack J. Dongarra , L. Susan Ostrouchov , Antoine P. Petitet , David W. Walker , R. Clint Whaley, Design and implementation of the ScaLAPACK LU, QR, and Cholesky factorization routines, Scientific Programming, v.5 n.3, p.173-184, Fall 1996
• 10: Jaeyoung Choi, Jack J. Dongarra, and David W. Walker. PUMMA: Parallel Universal Matrix Multiplication Algorithms on distributed memory concurrent computers. Concurrency: Practice and Experience, 6(7):543--570, 1994.
• 11: Curtis R. Cook , Do Jin Kim, Best sorting algorithm for nearly sorted lists, Communications of the ACM, v.23 n.11, p.620-624, Nov. 1980 [doi>10.1145/359024.359026]
• 12: Edsger W. Dijkstra. Smoothsort, an alternative for sorting in situ. Science of Computer Programming, 1(3):223--233, 1982.
• 13: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 14: Amr Elmasry , Michael L. Fredman, Adaptive Sorting and the Information Theoretic Lower Bound, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.654-662, February 27-March 01, 2003
• 15: Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992 [doi>10.1145/146370.146381]
• 16: G. C. Fox and S. W. Otto. Matrix algorithms on a hypercube I: matrix multiplication.
• 17: R. A. Van De Geijn and J. Watts. SUMMA: scalable universal matrix multiplication algorithm. Concurrency: Practice and Experience, 9(4):255--274, 1997.
• 18: 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]
• 19: Hyuk-Jae Lee , James P. Robertson , José A. B. Fortes, Generalized Cannon's algorithm for parallel matrix multiplication, Proceedings of the 11th international conference on Supercomputing, p.44-51, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263591]
• 20: Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
• 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: David B. Loveman, High Performance Fortran, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.1, p.25-42, February 1993 [doi>10.1109/88.219857]
• 23: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 24: David R. Musser , Gilmer J. Derge , Atul Saini, STL tutorial and reference guide, second edition: C++ programming with the standard template library, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 25: Marek Olszewski and Michael Voss. Proc. of the international conference on parallel and distributed processing techniques and applications, pdpta '04, june 21-24, 2004, las vegas, nevada, usa, volume 1. In Hamid R. Arabnia, editor, PDPTA. CSREA Press, 2004.
• 26: Ola Petersson , Alistair Moffat, A Framework for Adaptive Sorting, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.422-433, July 08-10, 1992
• 27: Of Signal Processing. SPIRAL: A generator for platform-adapted libraries.
• 28: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 29: Lawrence Rauchwerger , Francisco Arzu , Koji Ouchi, Standard Templates Adaptive Parallel Library (STAPL), Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.402-409, May 28-30, 1998
• 30: J. R. Rice. The algorithm selection problem. Advances in Computers, 15:65--118, 1976.
• 31: D. Rumelhart, G. Hinton, and R. Williams. Learning internal representations by error propagation. IEEE Transactions on Parallel and Distributed Systems: Explorations in the Microstructure of Cognition, 1, 1986.
• 32: Steven Saunders , Lawrence Rauchwerger, ARMI: an adaptive, platform independent communication library, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 33: Steven Saunders, Nathan Thomas, Nancy Amato, and Lawrence Rauchwerger. Adaptive parallel sorting in the STAPL library. Technical Report TR01-005, Parasol Laboratory, Texas A&M University, November 2001.
• 34: Jeremy G. Siek , Andrew Lumsdaine, The Matrix Template Library: A Generic Programming Approach to High Performance Numerical Linear Algebra, Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments, p.59-70, December 08-11, 1998
• 35: 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]
• 36: R. Clint Whaley, Antoine Petitet, and J. Dongarra. Automated empirical optimizations of software and the ATLAS project. Parallel Computing, 27(1-2):3--35, January 2001.
• 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Algorithms, Experimentation, Languages, Performance

Keywords:
adaptive algorithms, machine learning, matrix multiplication, parallel algorithms, sorting