Code Generation for Custom Architectures using Constraint Programming

Sammanfattning: The computation power we expect from the various smart devices we use keeps increasing. Not only do we want faster devices but also less power hungry and energy efficient devices, both for the environment and our personal convenience (remember that "mobile phone" attached to a power plug at all times?).One way of addressing this demand is to build custom processor architectures that focus on a specific application domain and meet specific demands such as limited power budget, bandwidth requirements, and chip area. As a wise woman once said, "there is no such thing as a free lunch" and in contrast to general purpose processor architectures, these architectures tend to end up notoriously hard to program. This is because of the customization of the hardware to a level that it becomes hard and inefficient to use tools and languages available for general purpose processors. So much so, that they quite often become solely programmable in the machine language specific to the architecture. This means many expert-hours spent in manual translation of relatively simple programs into machine code, rendering the architecture hardly usable by anyone else than the architect.This thesis is the result of our effort to increase the programmability of such custom architectures through automatic code generation, without losing performance compared to code written manually by the architect.Automatic code generation for general purpose architectures is a well studied research area and there exist many straightforward techniques. However, modeling code generation for custom architectures is complicated by the restrictions and constraints of the architectures, and performance requirements that need to be met for the targeted applications.Constraint programming is a programming paradigm that fits problems defined naturally by constraints and relations between entities. Here, a problem is formulated as a series of constraints over placeholder variables (much like the empty squares in sudoku) and solved by a constraint solving engine. The solving engine eliminates the infeasible values for each placeholder variable step-by-step, until a solution with each variable assigned to a value is found. As the capabilities and restrictions on the architectures, and the requirements on the applications we target can easily be translated into constraints, we choose constraint programming as our tool for modeling code generation for custom architectures. Throughout the thesis we demonstrate the effectiveness of our method by comparing to theoretical or practical bounds and code written manually by the architect. The frameworks we present make the architectures easier to program by letting the programmer write in a higher level language than the specific architecture's machine language. Our experiments show that the machine code generated by our frameworks are competitive with the state of the art.