Compiler optimization on instruction scheduling for low power

ABSTRACT

In this paper, we investigate the compiler transformation techniques to the problem of scheduling VLIW instructions aimed to reduce the power consumption on the instruction bus. It can be categorized into two types: horizontal and vertical scheduling. For the horizontal case, we propose a bipartite-matching scheme. We prove that our greedy algorithm always gives the optimal switching activities of the instruction bus. In the vertical case, we prove that the problem is NP-hard, and propose a heuristic algorithm. Experimental results show average 13% improvements with 4-way issue architecture and average 20% improvement with 8-way issue architecture for power consumptions of instruction bus as compared with conventional list scheduling for an extensive set of benchmarks.

REFERENCES

• 1: Chi-Ying Tsui , Massoud Pedram , Alvin M. Despain, Technology decomposition and mapping targeting low power dissipation, Proceedings of the 30th international conference on Design automation, p.68-73, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164577]
• 2: Mazhar Alidina , José Monteiro , Srinivas Devadas , Abhijit Ghosh , Marios Papaefthymiou, Precomputation-based sequential logic optimization for low power, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.74-81, November 06-10, 1994, San Jose, California, United States
• 3: Inki Hong , Darko Kirovski , Gang Qu , Miodrag Potkonjak , Mani B. Srivastava, Power optimization of variable voltage core-based systems, Proceedings of the 35th annual conference on Design automation, p.176-181, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277088]
• 4: Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.29-35, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217502]
• 5: Mike Tien-Chien Lee , Masahiro Fujita , Vivek Tiwari , Sharad Malik, Power analysis and minimization techniques for embedded DSP software, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.1, p.123-135, March 1997 [doi>10.1109/92.555992]
• 6: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 7: Ching-ren Lee, "Compiler Optimization on Advacned Processors for Low Power", Master Thesis, Dept. of Computer Sciense, National Tsing Hua Univ, Taiwan, 1999.
• 8: Stanford Compiler Group, The SUIF Library, Stanford Compiler Group, Stanford, March 1995.
• 9: Michael D. Smith, The SUIF Machine Library, Division of of Engineering and Applied Science, Harvard University, March 1998.
• 10: Al Aburto, collections of common benchmarks of FAQ ofcomp.benchmarks USENET newsgroup, ftp site: ftp.nosc.mil/pub/aburto.