ACM SIGPLAN Notices · 2009 · 54 citations · 18 references
ComputingComputer ScienceHigh-performance ComputingAlgorithmsComputer ArchitectureParallel ComputingAlgorithm AnalysisData ParallelismParallel Algorithm DesignParallel ArchitecturesParallel Computer ArchitectureParallel Computing SystemsAutomatic ParallelizationCompiler DesignGranularityGranularity ControlHigh PerformanceParallelization
It is often impossible to obtain a one-size-fits-all solution for high performance algorithms when considering different choices for data distributions, parallelism, transformations, and blocking. The best solution to these choices is often tightly coupled to different architectures, problem sizes, data, and available system resources. In some cases, completely different algorithms may provide the best performance. Current compiler and programming language techniques are able to change some of these parameters, but today there is no simple way for the programmer to express or the compiler to choose different algorithms to handle different parts of the data. Existing solutions normally can handle only coarse-grained, library level selections or hand coded cutoffs between base cases and recursive cases. We present PetaBricks, a new implicitly parallel language and compiler where having multiple implementations of multiple algorithms to solve a problem is the natural way of programming. We make algorithmic choice a first class construct of the language. Choices are provided in a way that also allows our compiler to tune at a finer granularity. The PetaBricks compiler autotunes programs by making both fine-grained as well as algorithmic choices. Choices also include different automatic parallelization techniques, data distributions, algorithmic parameters, transformations, and blocking. Additionally, we introduce novel techniques to autotune algorithms for different convergence criteria. When choosing between various direct and iterative methods, the PetaBricks compiler is able to tune a program in such a way that delivers near-optimal efficiency for any desired level of accuracy. The compiler has the flexibility of utilizing different convergence criteria for the various components within a single algorithm, providing the user with accuracy choice alongside algorithmic choice.
18
The Design and Implementation of FFTW3
Matteo Frigo, Steven G. Johnson · Proceedings of the IEEE · 2005 · 5.2K citations
FFTW: an adaptive software architecture for the FFT
Matteo Frigo, Steven G. Johnson · 2002 · 1.8K citations
SPIRAL: Code Generation for DSP Transforms
Markus Püschel, José M. F. Moura, Jeremy Johnson et al. · Proceedings of the IEEE · 2005 · 829 citations