Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The problem of choosing fast implementations for a class of recursive algorithms such as the fast Fourier transforms can be formulated as an optimization problem over the language generated by a suitably defined grammar. We propose a novel algorithm that solves this problem by reducing it to maximizing an objective function over the sinks of a directed acyclic graph. This algorithm valuates nodes using Monte-Carlo and grows a subgraph in the most promising directions by considering local maximum k-armed bandits. When used inside an adaptive linear transform library, it cuts down the search time by an order of magnitude compared to the existing algorithm. In some cases, the performance of the implementations found is also increased by up to 10% which is of considerable practical importance since it consequently improves the performance of all applications using the library.

REFERENCES

• 1: Peter Auer , Nicolò Cesa-Bianchi , Paul Fischer, Finite-time Analysis of the Multiarmed Bandit Problem, Machine Learning, v.47 n.2-3, p.235-256, May-June 2002 [doi>10.1023/A:1013689704352]
• 2: Chaslot, G., De Jong, S., Saito, J.-T., & Uiterwijk, J. W. H. M. (2006). Monte-Carlo tree search in production management problems. Proc. 18th BeNeLux Conf. on Artificial Intel. (BNAIC) (pp. 91--98).
• 3: Cicirello, V., & Smith, S. (2005). The max k-armed bandit: A new model for exploration applied to search heuristic selection. Proc. 20th National Conf. on Artificial Intelligence (AAAI) (pp. 1355--1361).
• 4: Coulom, R. (2006). Efficient selectivity and backup operators in Monte-Carlo tree search. Proc. 5th Int. Conf. on Computers and Games (CG), 72--83.
• 5: Frigo, M., & Johnson, S. (2005). The design and implementation of FFTW3. Proc. IEEE, 93, 216--231.
• 6: Sylvain Gelly , David Silver, Combining online and offline knowledge in UCT, Proceedings of the 24th international conference on Machine learning, p.273-280, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273531]
• 7: Intel (2008). Integrated performance primitives.
• 8: J. Johnson , M. Puschel, In search of the optimal Walsh-Hadamard transform, Proceedings of the Acoustics, Speech, and Signal Processing, 2000. on IEEE International Conference, p.3347-3350, June 05-09, 2000 [doi>10.1109/ICASSP.2000.860117]
• 9: Kocsis, L., & Szepesvi, C. (2006). Bandit based Monte-Carlo planning. Euro. Conf. on Mach. Learn. (ECML), LNCS 4212 (pp. 282--293). Springer.
• 10: Lai, T., & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6, 4--22.
• 11: Püschel, M., Moura, J. M. F., Johnson, J., Padua, D., Veloso, M., et al. (2005). SPIRAL: Code generation for DSP transforms. Proc. of the IEEE, 93, 232--275.
• 12: Bryan Singer , Manuela Veloso, Learning to construct fast signal processing implementations, The Journal of Machine Learning Research, 3, 3/1/2003
• 13: Streeter, M. J., & Smith, S. F. (2006). A simple distribution-free approach to the max k-armed bandit problem. Principles and Practice of Constraint Programming (CP) (pp. 560--574).
• 14: Yevgen Voronenko, Library generation for linear transforms, Carnegie Mellon University, Pittsburgh, PA, 2008
• 15: Yevgen Voronenko , Frédéric de Mesmay , Markus Püschel, Computer Generation of General Size Linear Transform Libraries, Proceedings of the 2009 International Symposium on Code Generation and Optimization, p.102-113, March 22-25, 2009 [doi>10.1109/CGO.2009.33]
• 16: Vuduc, R., Demmel, J. W., & Yelick, K. A. (2005). Oski: A library of automatically tuned sparse matrix kernels. Journal of Physics: Conf. Series, 16, 521--530.
• 17: Wang, Y., & Gelly, S. (2007). Modifications of UCT and sequence-like simulations for Monte-Carlo Go. IEEE Symp. on Computational Intelligence and Games (CIG) (pp. 175--182).
• 18: R. Clint Whaley , Antoine Petitet, Minimizing development and maintenance costs in supporting persistently optimized BLAS, Software—Practice & Experience, v.35 n.2, p.101-121, February 2005 [doi>10.1002/spe.v35:2]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory