Feature selection and policy optimization for distributed instruction placement using reinforcement learning

ABSTRACT

Communication overheads are one of the fundamental challenges in a multiprocessor system. As the number of processors on a chip increases, communication overheads and the distribution of computation and data become increasingly important performance factors. Explicit Dataflow Graph Execution (EDGE) processors, in which instructions communicate with one another directly on a distributed substrate, give the compiler control over communication overheads at a fine granularity. Prior work shows that compilers can effectively reduce fine-grained communication overheads in EDGE architectures using a spatial instruction placement algorithm with a heuristic-based cost function. While this algorithm is effective, the cost function must be painstakingly tuned. Heuristics tuned to perform well across a variety of applications leave users with little ability to tune performance-critical applications, yet we find that the best placement heuristics vary significantly with the application.

First, we suggest a systematic feature selection method that reduces the feature set size based on the extent to which features affect performance. To automatically discover placement heuristics, we then use these features as input to a reinforcement learning technique, called Neuro-Evolution of Augmenting Topologies (NEAT), that uses a genetic algorithm to evolve neural networks. We show that NEAT outperforms simulated annealing, the most commonly used optimization technique for instruction placement. We use NEAT to learn general heuristics that are as effective as hand-tuned heuristics, but we find that improving over highly hand-tuned general heuristics is difficult. We then suggest a hierarchical approach to machine learning that classifies segments of code with similar characteristics and learns heuristics for these classes. This approach performs closer to the specialized heuristics. Together, these results suggest that learning compiler heuristics may benefit from both improved feature selection and classification.

REFERENCES

• 1: F. Agakov , E. Bonilla , J. Cavazos , B. Franke , G. Fursin , M. F. P. O'Boyle , J. Thomson , M. Toussaint , C. K. I. Williams, Using Machine Learning to Focus Iterative Optimization, Proceedings of the International Symposium on Code Generation and Optimization, p.295-305, March 26-29, 2006 [doi>10.1109/CGO.2006.37]
• 2: John Cavazos , Christophe Dubach , Felix Agakov , Edwin Bonilla , Michael F. P. O'Boyle , Grigori Fursin , Olivier Temam, Automatic performance model construction for the fast software exploration of new hardware designs, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176765]
• 3: John Cavazos , J. Eliot B. Moss, Inducing heuristics to decide whether to schedule, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 4: J. Cavazos and E. Moss. Hybrid optimization: Which optimization to use? In International Conference on Compiler Construction, pages 124--138, Vienna, Austria, 2006.
• 5: John Cavazos , Michael F. P. O'Boyle, Automatic Tuning of Inlining Heuristics, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.14, November 12-18, 2005 [doi>10.1109/SC.2005.14]
• 6: Katherine E. Coons , Xia Chen , Doug Burger , Kathryn S. McKinley , Sundeep K. Kushwaha, A spatial path scheduling algorithm for EDGE architectures, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 7: Katherine E. Coons , Xia Chen , Doug Burger , Kathryn S. McKinley , Sundeep K. Kushwaha, A spatial path scheduling algorithm for EDGE architectures, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 8: D. Dasgupta and D. McGregor. Designing application-specific neural networks using the structured genetic algorithm. In International Conference on Combinations of Genetic Algorithms and Neural Networks, pages 87--96, 1992.
• 9: Inderjit S. Dhillon , Yuqiang Guan , Brian Kulis, Weighted Graph Cuts without Eigenvectors A Multilevel Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.11, p.1944-1957, November 2007 [doi>10.1109/TPAMI.2007.1115]
• 10: Christophe Dubach , John Cavazos , Björn Franke , Grigori Fursin , Michael F.P. O'Boyle , Olivier Temam, Fast compiler optimisation evaluation using code-feature based performance prediction, Proceedings of the 4th international conference on Computing frontiers, May 07-09, 2007, Ischia, Italy [doi>10.1145/1242531.1242553]
• 11: Toru Kisuki , Peter M. W. Knijnenburg , Michael F. P. O'Boyle , François Bodin , Harry A. G. Wijshoff, A Feasibility Study in Iterative Compilation, Proceedings of the Second International Symposium on High Performance Computing, p.121-132, May 26-28, 1999
• 12: T. Kisuki, P. Knijnenburg, M. O'Boyle, and H. Wijshoff. Iterative compilation in program optimization. In Compilers for Parallel Computers 2000, pages 35--44, Aussois, France, 2000.
• 13: H. Leather, E. Yom-Tov, M. Namolaru, and A. Freund. Automatic feature generation for setting compilers heuristics. In 2nd Workshop on Statistical and Machine Learning Approaches to Architectures and Compilation (to appear), 2008.
• 14: Bertrand A. Maher , Aaron Smith , Doug Burger , Kathryn S. McKinley, Merging Head and Tail Duplication for Convergent Hyperblock Formation, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.65-76, December 09-13, 2006 [doi>10.1109/MICRO.2006.34]
• 15: 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
• 16: Martha Mercaldi , Steven Swanson , Andrew Petersen , Andrew Putnam , Andrew Schwerin , Mark Oskin , Susan J. Eggers, Instruction scheduling for a tiled dataflow architecture, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 17: Martha Mercaldi , Steven Swanson , Andrew Petersen , Andrew Putnam , Andrew Schwerin , Mark Oskin , Susan J. Eggers, Modeling instruction placement on a spatial architecture, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148137]
• 18: Antoine Monsifrot , François Bodin , Rene Quiniou, A Machine Learning Approach to Automatic Production of Compiler Heuristics, Proceedings of the 10th International Conference on Artificial Intelligence: Methodology, Systems, and Applications, p.41-50, September 04-06, 2002
• 19: Eliot Moss , Paul Utgoff , John Cavazos , Carla Brodley , David Scheeff , Doina Precup , Darko Stefanović, Learning to schedule straight-line code, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.929-935, July 1998, Denver, Colorado, United States
• 20: P. G. Paulin , J. P. Knight, Force-directed scheduling in automatic data path synthesis, Proceedings of the 24th ACM/IEEE conference on Design automation, p.195-202, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37918]
• 21: Karthikeyan Sankaralingam , Ramadass Nagarajan , Robert McDonald , Rajagopalan Desikan , Saurabh Drolia , M. S. Govindan , Paul Gratz , Divya Gulati , Heather Hanson , Changkyu Kim , Haiming Liu , Nitya Ranganathan , Simha Sethumadhavan , Sadia Sharif , Premkishore Shivakumar , Stephen W. Keckler , Doug Burger, Distributed Microarchitectural Protocols in the TRIPS Prototype Processor, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.480-491, December 09-13, 2006 [doi>10.1109/MICRO.2006.19]
• 22: Aaron Smith , Jon Gibson , Bertrand Maher , Nick Nethercote , Bill Yoder , Doug Burger , Kathryn S. McKinle , Jim Burrill, Compiling for EDGE Architectures, Proceedings of the International Symposium on Code Generation and Optimization, p.185-195, March 26-29, 2006 [doi>10.1109/CGO.2006.10]
• 23: Kenneth O. Stanley , Risto Miikkulainen, Evolving neural networks through augmenting topologies, Evolutionary Computation, v.10 n.2, p.99-127, Summer 2002 [doi>10.1162/106365602320169811]
• 24: Mark Stephenson , Saman Amarasinghe, Predicting Unroll Factors Using Supervised Classification, Proceedings of the international symposium on Code generation and optimization, p.123-134, March 20-23, 2005 [doi>10.1109/CGO.2005.29]
• 25: Mark Stephenson , Saman Amarasinghe , Martin Martin , Una-May O'Reilly, Meta optimization: improving compiler heuristics with machine learning, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 26: Matthew E. Taylor , Shimon Whiteson , Peter Stone, Comparing evolutionary and temporal difference methods in a reinforcement learning domain, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144202]
• 27: R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society. Series B (Methodological), 58(1):267--288, 1996.
• 28: Todd Waterman , Keith D. Cooper, Adaptive compilation and inlining, Rice University, Houston, TX, 2006
• 29: Shimon Whiteson , Peter Stone , Kenneth O. Stanley , Risto Miikkulainen , Nate Kohl, Automatic feature selection in neuroevolution, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068210]
• 30: Ian Witten, Data Mining, Elsevier Science Inc., New York, NY, 2005
• 31: X. Yao. Evolving artificial neural networks. Proceedings of the IEEE, 87(9):1423--1447, 1999.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.2 Automatic Programming

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Design, Performance

Keywords:
compiler heuristics, genetic algorithms, instruction scheduling, machine learning, neural networks