Towards Memory-Load Balanced Fast Fourier Transformations in Fine-grain Execution Models

Abstract—The codelet model is a fine-grain dataflow-inspired program execution model that balances the parallelism and overhead of the runtime system. It plays an important role in terms of performance, scalability, and energy efficiency in exascale studies such as the DARPA UHPC project and the DOE X-Stack project. As an important application, the Fast Fourier Transform (FFT) has been deeply studied in fine-grain models, including the codelet model. However, the existing work focuses on how fine-grain models achieve more balanced workload comparing to traditional coarse-grain models. In this paper, we make an important observation that the flexibility of execution order of tasks in fine-grain models improves utilization of memory bandwidth as well. We use the codelet model and the FFT application as a case study to show that a proper execution order of tasks (or codelets) can significantly reduce memory contention and thus improve performance. We propose an algorithm that provides a heuristic guidance of the execution order of the codelets to reduce memory contention. We implemented our algorithm on the IBM Cyclops-64 archi-tecture. Experimental results show that our algorithm improves up to 46 % performance compared to a state-of-the-art coarse-grain implementation of the FFT application on Cyclops-64. Keywords—FFT; fine grain; execution model; memory band-width. I