Talk: TPL -- A Language for FFT Algorithms (Jeremy Johnson)

Start!

Abstract

  1. Title
  2. Mathematics and the Implementation of the FFT
  3. Related & Previous Work (incomplete)
  4. FFT as a Matrix Factorization
  5. Matrix Factorizations and Algorithms
  6. Rewrite Rules
  7. FFT Variants
  8. TPL
  9. TPL Grammar
  10. TPL Grammar (cont)
  11. An Example of TPL Program
  12. Meta-TPL
  13. TPL Compiler
  14. An Example of the Output
  15. Simple Algorithm of Generating Straight-line Code
  16. Performance of Straight-line Code
  17. Formula Generator
  18. Symbolic Rule Set
  19. Example Rules
  20. Symbolic Formula Generation
  21. FFT Decomposition Trees
  22. Comparison of Left, Right, and Balanced Decompositions
  23. Distribution of Times (N = 128)
  24. Distribution of Trees (N = 128)
  25. Reducing the Search
  26. Partitioning Search Space
  27. Dynamic Programming
  28. Dynamic Programming (N = 128)
  29. Optimal Performance
  30. Desired System Properties
  31. Benefits from Computer Algebra
back to session index