A SOFTWARE APPROACH FOR LOWER POWER CONSUMPTION Bui Ngoc Hai Faculty of Information Technology University of Engineering and Technology Vietnam National University, Hanoi Supervised by Assoc. Nguyen Ngoc Binh A thesis submitted in fulfillment of the requirements for the degree of Master of Science in Computer Science April 2014 TIEU LUAN MOI download : skknchat@gmail.com ORIGINALITY STATEMENT ‘I hereby declare that this submission is my own work and to the best of my knowledge it contains no materials previously published or written by another person, or substantial proportions of material which have been accepted for the award of any other degree or diploma at University of Engineering and Technology (UET) or any other educational institution, except where due acknowledgement is made in the thesis. Any contribution made to the research by others, with whom I have worked at UET or elsewhere, is explicitly acknowledged in the thesis. I also declare that the intellectual content of this thesis is the product of my own work, except to the extent that assistance from others in the project's design and conception or in style, presentation and linguistic expression is acknowledged.’ Hanoi, April 25th , 2014 Signed.
TIEU LUAN MOI download : skknchat@gmail.com ABSTRACT Optimizing the power consumption is an important topic in embedded system engineering, especially for embedded systems that use battery power source. Power optimization can be achieved by software techniques and instruction scheduling is an effective software approach for reducing power cost of processor(s). In this thesis, we propose our idea of using a genetic algorithm for low power instruction scheduling. Our algorithm is applied to each basic block of assembly code to generate lower power program.
In the experiment section, we use two open source simulation tools that are SimpleScalar Tool Set and SimplePower, the algorithm is applied to assembly programs of SimpleScalar Instruction Set, these programs are compiled and then have their power consumptions measured by SimplePower. The experimental results showed the effectiveness of our proposed method. This scheduling method will be combined with the idea of reducing memory access for low power design in our further work. TIEU LUAN MOI download : skknchat@gmail.com ACKNOWLEDGEMENTS First and foremost, I would like to express my deepest gratitude to my supervisor, Assoc.
Nguyen Ngoc Binh for giving me the opportunity to work with him and for his patient guidance and continuous support throughout the years. I would like to give my honest appreciation to my colleagues at the Laboratory of Embedded Systems for their great support. I also would like to thank all my friends who gave me moral support during this work. Finally, this thesis would not have been possible without the moral support and love of my parents and my brother.
Thank you! TIEU LUAN MOI download : skknchat@gmail.com Table of Contents Chapter 1.1 Software power optimization .2 Power optimization by instruction scheduling .1 Software power estimation .2 Energy code driven generation for low power .3 Reducing memory access .4 Software power optimization using symbolic algebra .5 List scheduling for low power .6 Instruction scheduling to reduce switching activity .7 Low power instruction scheduling as traveling salesman problem .8 Force-directed scheduling for low power.9 Instruction scheduling to reduce the off-chip power .10 Energy-oriented and performance-oriented combination scheduling .11 Criticality-directed and Uncriticality-directed instruction scheduling for low power .12 Low power instruction scheduling using Particle Swarm Optimization algorithm. Instruction Scheduling for Low Power.2 Partitioning Basic Blocks of assembly code .2 Data Flow Graph construction .4 Generating Power Dissipation Table. 14 TIEU LUAN MOI download : skknchat@gmail.Genetic Algorithm for low power Instruction scheduling .3 Representation of chromosome .4 Cross Over operator.7 Genetic Algorithm for low power scheduling .1 SimpleScalar tool set .3 Experimental benchmarks set .5 Analysis and evaluation. Conclusion and Future Work.
Some important source code. Source code of benchmark programs. Power Dissipation Table. An example of scheduling a basic block.
56 TIEU LUAN MOI download : skknchat@gmail.com List of Figures Figure 2.1 List scheduling for low power .1 Flow of low power instruction scheduling .2 An example of a Basic Block and its Data Flow Graph .3 Examples of Basic Blocks .4 Algorithm to construct a DFG .5 PDT generation example .1 Topological sorting with random priorities assignment .3 Cross over operator .4 Cross over operator example .6 Genetic algorithm for low power scheduling .2 SimpleScalar simulator software architecture .3 SimplePower result example. 31 TIEU LUAN MOI download : skknchat@gmail.com List of Tables Table 3.1 Instruction set architecture .1 Experimental benchmark set .2 Experimental results of GA scheduling .3 Experimental results of list scheduling .4 Results comparison of two algorithms. 35 TIEU LUAN MOI download : skknchat@gmail.com List of Abbreviations BB Basic Block DC Direct Current DFG Data Flow Graph GA Genetic Algorithm ISA Instruction Set Architecture PDT Power Dissipation Table PISA Portable Instruction Set Architecture PSO Particle Swarm Optimization RAW Read after Write RTL Register Transfer Level TSP Travelling Salesman Problem WAR Write after Read WAW Write after Write TIEU LUAN MOI download : skknchat@gmail.com List of Notations ∑ Sum Energy Power of a program Power Base Cost of instruction i Overhead cost between two instruction i and j n Number of instruction in a basic block Number of times i get executed Number of times the pair (i,j) get executed Energy cost of other effects of the program P(t) Population at the loop t xti Solution i at the loop t vi Vertex i TIEU LUAN MOI download : skknchat@gmail.com 1 Chapter 1 Introduction In embedded system engineering, optimization is an important problem. Embedded systems always have limited resources such as the size of memory, the speed of the processor, power supply, etc.
Optimization will make the system work more efficiently with allowed resources. Optimizing the power consumption is an important issue, especially for embedded systems using battery power source. Since embedded devices are portable and use DC powered cells, optimized power consumption can help prolong the life time of such systems. Today, embedded devices are becoming more popular in daily life as well as in science and technology.
Many people have become attracted by popular embedded devices such as smart phones, tablet computers, MP3 players. Ubiquitous devices will need a longer battery life. Since the ability to reduce power consumption of an embedded device is more important, this optimization problem has become a major challenge for the designers and the manufacturers. They must continually improve product quality to meet the needs of users, and low power consumption really is a necessary requirement.1 Software power optimization Software controls most activity of hardware in the systems, therefore, it can have a significant effect on the power dissipation of a system.
Power can be optimized by software techniques. There have been many software techniques on optimizing the power consumption of the processor. Some techniques are instruction scheduling [1-10], reducing memory access, energy cost driven code generation, and instruction packing [2-3,11]. Since the order of instructions controls internal switching in the processor; it can affect the power of processor during execution.
Therefore choosing a suitable order of instructions can reduce power consumption of the system. In terms of energy consumption, memory accesses are more expensive than register accesses, so optimal register allocation that reduces the TIEU LUAN MOI download : skknchat@gmail.com 2 memory operands, can also reduce power. If we can obtain a table of power costs of individual instructions, a reduction in total power cost can be obtained by using a code generator which selects proper low power instructions. Another method is optimizing program source code for low power.
An example of this method is proposed in [12], where the authors optimize the C code by approximating complex expressions by simple polynomial expressions and converting floating point data to fixed point data, so that the energy dissipation of the program execution is reduced. Some other techniques are voltage software controlling and frequency scaling for dynamic power optimization [13].2 Power optimization by instruction scheduling One of the main features that affect the power consumption of the systems is how the assembly instructions are scheduled or combined together, the power consumed during the execution of an instruction will depend on the previous instruction. For a given C program as well as other high level languages code, there can be more than one sequence of instructions (assembly code) for a given processor. Therefore, a suitable order of instructions in a program can result in the lower power consumption.
Instruction Scheduling for Low Power is an effective software approach for power optimization; this work is reordering the assembly instructions of a program so that power consumption is reduced, of course keeping the semantics of the program. There are many scheduling techniques that have been proposed, most of which aim to reduce overhead cost between pairs of instructions [2-5,7-9,11]. Moreover, some techniques have other objectives for power reduction such as reducing switching activity [6,22] and using critical path [14].3 Our work In this thesis, we introduce our method for optimizing power consumption by instruction scheduling. Scheduling is an NP-hard problem; the main difficulty being that the search space of the possible instruction orders is very large.
When finding a good schedule, our usual stumbling block is resolving the constraints of the data flow graph, i. when we create a new order of instructions, we are not sure whether it satisfies the data flow graph or not. Hence, our approach uses a genetic algorithm with a chromosome encoding that solves the data dependency problems TIEU LUAN MOI download : skknchat@gmail. This method was introduced in [15], where the authors proposed this method to solve the traveling salesman problem (TSP).
We apply their method to the scheduling problem in order to reduce energy consumption. This algorithm has the advantage of avoiding the local optimum. For finding solutions in the large search space, we use a heuristic table, called Power Dissipation Table (PDT), which is generated by power simulations. A PDT for an instruction set with n instructions is a (n × n) matrix, where each entry PDT(i,j) is the power cost consumed in the execution of instruction i followed by instruction j.
Each entry is used as overhead cost between i and j, and this table is used for evaluating the solution. The original assembly programs are divided into basic blocks, and then a Data Flow Graph (DFG) is constructed for each basic block. This is a directed graph that presents the data dependencies of instructions in a basic block. Our algorithm is applied for each basic block of an assembly program; it takes as input a data flow graph of a given basic block and the power dissipation table and its output is the low power instruction sequence.
For experiments, we use two open source simulation tools: SimpleScalar Tool Set [16-18] and SimplePower [19]. A sub set of SimpleScalar Instruction Set is considered and SimplePower is used to simulate the power consumption. The algorithm is applied to assembly programs of SimpleScalar ISA. Then these programs are compiled and their power consumptions are measured by SimplePower for visual observation.4 Thesis organization The remainder of this thesis is organized as follows.
Chapter 2 introduces some related works about software power optimization and instruction scheduling for low power. Chapter 3 describes the steps of our low power instruction scheduling problem in detail. Chapter 4 presents the proposed approach based on a genetic algorithm for this problem. Chapter 5 reports the simulation tools, the benchmarks for experiment, experimental results and analysis.
Chapter 6 presents our conclusions and introduces the future work. TIEU LUAN MOI download : skknchat@gmail.com 4 Chapter 2 Related Work This chapter summarizes related research about software power optimization 2.1 Software power estimation The first step for power consumption is power estimation. The ability to estimate software power consumption can help to verify that a design meets its power constraints and verify the correctness of power optimization methods.