Register allocation for embedded systems

Abstract

Compilers play an important part in the system performance improvement. A compilation process is to translate source code from a highlevel programming language to a lower level language. For embedded systems, the system resource such as the number of registers, cache size, and memory size are very limited. Therefore, an efficient compilation can particularly have great effect on the system performance of these systems. Register allocation, which is a key compilation step, aims at multiplexing a large number of target program variables onto a small number of physical registers. A register allocator tries to keep as many operands as possible in registers to maximize the execution speed of programs. For embedded systems often with limited number of registers, it is particularly important to conduct efficient register allocation for the system performance improvement. Embedded systems are usually designed for specific application and these applications vary widely. Various application of embedded systems have difference requirement in compilation. Therefore, the compilation solutions for embedded systems should be determined according to the actual need of their application. For register allocation activity in the compilation process, an identical solution can have positive or negative effect on the system performance of different embedded systems with different design purpose. As a result, register allocation also should be considered carefully in different embedded systems, depending on their applications and actual requirements. In this thesis, we study the different requirements for different embedded systems. We propose system-specific register allocation approach to meet the need of each type of embedded system. First, we study the schedule length minimization for loop programs in embedded systems. Our study is based on loop scheduling for schedule length reduction. A cooperative register allocation and loop scheduling approach is proposed that combines the phase ordering problem of register allocation and loop scheduling. Starting with an aggressive schedule, we show that a program’s schedule length can effectively reduced by considering register allocation and loop scheduling. Second, we study the application of real-time embedded systems with clustered VLIW architecture. On one hand, worst-case execution time (WCET) is an important real-time constraint for real-time systems. On the other, the phase ordering problem of register allocation, instruction scheduling, and cluster assignment should be carefully considered in systems with clustered VLIW architecture such that the effort on WCET reduction is effective. For this type of machine, we propose a WCET-aware re-scheduling register allocation technique to achieve WCET minimization. The effects of register allocation, scheduling, and cluster assignment on the quality of generated code are taken into account for WCET minimization. We show that starting with an aggressive initial scheduling and an initial cluster assignment solution for virtual registers, a program’s WCET can be effectively reduced by integrating these three activities into a single phase. Third, we study the application of real-time cyber-physical systems (CPSs). There are two challenges for CPSs. First, CPSs often include a number of sensor nodes. Update of preloaded code on remote sensor nodes powered by batteries is extremely energy-consuming. The code update issue in the energy sensitive CPS must be carefully considered. Second, CPSs are often real-time embedded systems so that WCET is an important concern in real-time system design. While existing works only consider one of these two challenges at a time, we propose a compiler level optimization, namely joinWCET and update conscious compilation technique to jointly consider WCET and code update for CPSs such that a balanced solution with minimalWCET and minimal code update can be achieved. Finally, we study the application of non-volatile memories for embedded systems. Non-volatile memories are good candidates for DRAM replacement as main memory in embedded systems and they have many desirable characteristics. However, we need to address two challenges. First, the lifetime of some of the non-volatile memories is limited by the number of erase operations. Second, read and write operations have asymmetric speed or power consumption in non-volatile memory. To process these two problems, we propose register allocation technique with re-computation to reduce the number of store instructions, which will in turn reduce write activities on non-volatile memory and extend the lifetime. To summarize, we show that for different application of different embedded systems, an effective register allocation solution can have large effect on the system performance. By specifically considering their requirements during register allocation, a significant performance improvement can be achieved.

Date of Award	3 Oct 2012
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chun Jason XUE (Supervisor)