A Model-driven Framework for High-level Adaptation of Algorithms to Computing Architectures

To avoid the high cost of algorithm optimization at the later algorithm development phase, early and rapid exploration of the algorithm behavior on compute architectures is becoming more necessary due to highly complex architectures and algorithms. To achieve desirable performance, the conventional method is to repetitively experiment with many different algorithmic structures (shapes) of the algorithm implemented in a programming language for a specific architecture until the best shape is found. This approach is challenging, error-prone, and very time-consuming because it requires coding several versions of the computation in a programming language, which requires the use of very detailed constructs, using detailed architecture simulators, which are slow but provide flexibility, and using sophisticated performance analysis tools, which requires the algorithm implementation be written in a programming language. Even worse, to explore different architectures for a given algorithm, different algorithm implementations are required for each architecture. Additionally, the shape space is usually very large, which prohibitively slows down the exploration process. To address the challenge, we have built the HAAF framework, which provides a realistic yet simple performance model to explore the behavior of algorithms on single- and multi-core processors. We only model key components to yield acceptable results for predicting the behavior of the algorithm on the architecture for different shapes more efficiently than conventional methods. By finding the best shape, the user can begin from a good starting point to implement the algorithm in a programming language. In this work, we develop Simplified C and ADL, a language to more easily describe algorithm shapes, and use it to describe four benchmarks representing differing types of computation kernels. We seek the simplest architectural simulator model and find that just modeling memory accesses and approximating the non-memory delays between those accesses is sufficient to show the performance trends between algorithm shapes for each of the benchmark kernels. By validating our simulator platform against a fully cycle-accurate simulator, we have shown that HAAF can be used to automatically explore a space of algorithm shapes and find the shapes that will result in the best performance.Ph.D