Object code compression using different schemes for different instruction types
Patent 6691305 Issued on February 10, 2004. Estimated Expiration Date: April 21, 2020. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
A code compression method for system-level power optimization that lessens the requirements imposed on main memory size. The method reduces the power consumption of a complete system comprising a CPU, instruction cache, data cache, main memory, data buses and address bus. The method includes extracting compressible instruction and data portions from executable code, creating a mathematical model of the extracted code portions, class the individual instructions in the extracted portions based upon their operation codes and compressing the instructions. The compressed instructions are further compressed when extracted from memory by using bus compaction. The method is also embodied in a computer system with a processor and a memory adapted to perform the steps of the method to compress the extracted instruction portions. Additionally, the method is embodied on a computer program product bearing software instructions adapted to perform the steps of the method to compress the extracted instruction portions. The invention also has an apparatus utilizing a post-cache architecture that has a decompression engine that decompresses instructions that have been compressed using the method of the invention. The apparatus extracts the compressed instructions from memory or the instruction/data cache using a bus compression technique to save power as the compressed instructions/data traverses the bus.
Other References
Texas Instruments Inc., TI's 0.07-Micron CMOS Technology Ushers in Era of Gigahertz DSP and Analog Performance, pp. 1-4, 1999
T.M. Kemp, R.K. Montoye, J.D. Harper, J.D. Palmer and D.J. Auerbach, A Decompression Core for PowerPC, IBM J. Res. Develop. vol. 42, No. 6, pp. 807-811, Nov. 1988
T. Okuma, H. Tomiyama, A. Inoue, E. Fajar and H. Yasuura, Instruction Encoding Techniques for Area Minimization of Instruction ROM, IEEE, pp. 125-130, 1998
Luca Benini, Alberto Macii, Encrico Macii and Massimo Poncino, Selective Instruction Compression for Memory Energy Reduction in Embedded Systems, ACM, pp. 206-211, 1999
Bharat P. Dave, Ganesh Lakshminarayna, Niraj K. Jha, COSYN: Hardware-Software Co-Synthesis of Embedded Systems, ACM, pp. 703-708, 1997
Inki Hong, Darko Kirovski, Gang Qu, Miodrag Potkonjak and Mani B. Srivastava, Power of Optimization of Variable Voltage Core-Based Systems, ACM, pp. 176-181, 1998
Tohru Ishihara and Hiroto Yasuura, Voltage Scheduling Problem for Dynamically Variable Voltage Processors, ACM, pp. 197-202, 1998
Cheng-Ta Hsieh, Massoud Pedram, Gaurav Mehta and Fred Rastgar, Profile-Driven Program Synthesis for Evaluation of System Power Dissipation, ACM, pp. 576-581, 1997
Vivek Tiwari, Sharad Malik, Andrew Wolfe and Mike Tien-Chien Lee, Instruction Level Power Analysis and Optimization of Software, Journal of VLSI Signal Processing, pp. 1-18, 1996
Vivek Tiwari, Sharad Malik and Andrew Wolfe, Power Analysis of Embedded Software: A First Step Towards Software Power Minimization, IEEE Transactions on VLSI Systems, Dec. 1994
Mike Tien-Chen Lee, Vivek Tiwari, Sharad Malik and Masahiro Fujita, Power Analysis and Minimization Techniques for Embedded DSP Systems, Dec. 1996
Qinru Qiu, Qing Wu and Massoud Pedram, Stochastic Modeling of a Power-Managed System: Construction and Optimization, ACM, pp. 194-199, 1999
Luca Benini, Allesandro Bogliolo, Giuseppe A. Paleologo and Giovanni De Micheli, Policy Optimization for Dynamic Power Management, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, No. 6, pp. 813-833, Jun. 1999
William Fornaciari, Donatella Sciuto and Cristina Silvano, Power Estimation for Architectural Exploration of HW/SW Communication on System-Level Buses, ACM, pp. 152-156, 1999
Mircea R. Stan and Wayne P. Burleson, Bus-Invert Coding for Low-Power I/O, IEEE Transaction on Very Large Scale Integration (VLSI) Systems, vol. 3, No. 1, pp. 49-58, Mar. 1995
Tony Givargis and Frank Vahid, Interface Exploration for Reduced Power in Core-Based Systems, IEEE, pp. 117-122, 1998
Jue-Hsien Chern, Jean Huang, Lawrence Arledge, Ping-Chung Li, and Ping Yang, Multilevel Metal Capacitance Models for CAD Design Synthesis Systems, IEEE Electron Device Letters, vol. 13, No. 1, pp. 32-34, Jan. 1992
Yanbing Li and Jorg Henkel, A Framework for Estimating and Minimizing Energy Dissipation of Embedded HW/SW Systems, ACM, pp. 188-193, 1998
Paul G. Howard and Jeffrey Scott Vitter, Practical Implementations of Arithmetic Coding, Brown University, pp. 1-30, 1991 (a similar version appears in Image and Text Compression, pp 85-112, 1992)
G.V. Cormack and R.N.S. Horspool, Data Compression Using Dynamic Markov Modelling, The Computer Journal, vol. 30, No. 6, pp. 541-550, 1987
Jacob Ziv and Abraham Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, vol. IT-23, No. 3, pp. 337-343, May 1977
Ian H. Witten, Radford M. Neal and John G. Cleary, Arithmetic Coding for Data Compression, Communications of the ACM, vol. 30, No. 6, pp. 520-540, Jun. 1987
Nagisa Ishiura and Masayuki Yamaguchi, Instruction Code Compression for Application Specific VLIW Processors Based on Automatic Field Partitioning, pp. 105-109. (Research Paper)
Darko Kirovski, Johnson Kin and William H. Mangione-Smith, Procedure Based Program Compression, The Departments of Computer Science and Engineering, The University of California at Los Angeles
Kevin D. Kissell, MIPS16: High-Density MIPS for the Embedded Market, (A version of this paper appears in the proceedings of the RTS97 conference)
Michael Kozuch and Andrew Wolfe, Compression of Embedded System Programs, (Appeared in ICCD 1994)
Guido Araujo, Paulo Centoducatte, Mario Cortes and Ricardo Pannain, Code Compression Based on Operand Factorization (Research Paper)
Martin Benes, Andrew Wolfe and Steven M. Nowick, A High-Speed Asynchronous Decompression Circuit for Embedded Processors (Research Paper)
Martin Benes, Steven M. Nowick and Andrew Wolfe, A Fast Synchronous Huffman Decoder for Compressed-Code Embedded Processors (Research Paper)
Luca Benini, Alberto Macii, Enrico Macii and Massimo Poncino, Selective Instruction Compression for Memory Energy Reduction in Embedded Systems, ACM, pp. 206-211, 1999
Peter L. Bird and Trevor N. Mudge, An Instruction Stream Compression Technique, EECS Department, University of Michigan, (Technical Report) pp. 1-21, Nov. 27, 1996
John Bunda, Donald Fussell, Roy Jenevein and W.C. Athas, 16-Bit v. 32-Bit Instructions for Pipelined Microprocessors, Department of Computer Sciences, The University of Texas at Austin, (Technical Report) pp. 1-28, Oct. 23, 1992
Paulo Centoducatte, Guido Araujo and Ricardo Pannain, Compressed Code Execution on DSP Architectures (Research Paper)
I-Cheng K. Chen, Peter L. Bird and Trevor Mudge, The Impact of Instruction Compression of I-cache Performance, University of Michigan, Technical Report CSE-TR-330-97, University of Michigan, pp. 1-7
Lars Raeder Clausen, Ulrik Pagh Schultz, Charles Consel and Gilles Muller, Java Bytecode Compression for Embedded Systems, Institut De Recherche En Informatique Et Systemes Aleatoires (IRISA), Publication No. 1213, pp. 1-22, Dec. 1998
Thomas M. Conte, Sanjeev Banerjia, Sergei Y. Larin, Kishore N. Menezes and Sumedh W. Sathaye, Instruction Fetch Mechanisms for VLIW Architectures with Compressed Encodings, IEEE, pp. 201-211, 1996
Keith D. Cooper and Nathaniel McIntosh, Enhanced Code Compression for Embedded RISC Processors, (Research Paper)
Jens Ernst, William Evans, Christopher W. Fraser, Steven Lucco and Todd A. Proebsting, Code Compression, (Research Paper)
Christopher W. Fraser and Todd A. Proebsting, Custom Instruction Sets for Code Compression, pp. 1-9, Oct. 19, 1995
Jan Hoogerbrugge, Lex Augusteijn, Jeroen Trum and Rik Van de Wiel, A Code Compression System Based on Pipelined Interpreters, Software Practice and Experience, pp. 1005-1023, 1999
David A. Huffman, A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the I.R.E., pp. 1098-1101, Sep. 1952
Charles Lefurgy, Eva Piccininni and Trevor Mudge, Evaluation of a High Performance Code Compression Method, IEEE, 1999
Charles Lefurgy, Eva Piccininni and Trevor Mudge, Reducing Code Size with Run Time Decompression, EECS Department, University of Michigan, (Research Paper)
Charles Lefurgy, Peter Bird, I-Cheng Chen and Trevor Mudge, Improving Code Density Using Compression Techniques, IEEE, 1999
Charles Lefurgy and Trevor Mudge, Code Compression for DSP, EECS Department, University of Michigan, CSE-TR-380-98, pp. 1-5
Charles Lefurgy and Trevor Mudge, Fast Software-managed Code Decompression, EECS Department, University of Michigan, presented at CASES '99, pp. 1-5, Oct. 1-3, 1999.
Haris Lekatsas and Wayne Wolf, Code Compression for Embedded Systems, Department of Electrical Engineering, Princeton University, (Research Paper).
Haris Lekatsas and Wayne Wolf, SAMC: A Code Compression Algorithm for Embedded Processors, Department of Electrical Engineering, Princeton University, pp. 1-17, Nov. 1, 1999.
Haris Lekatsas and Wayne Wolf, Random Access Decompression Using Binary Arithmetic Coding, Department of Electrical Engineering Princeton University, (Research Paper).
Stan Y. Liao, Sprinivas Devadas and Kurt Keutzer, Code Density Optimization for Embedded DSP Processors Using Data Compression Techniques, (Research Paper).
Stan Liao, Sprinivas Devadas and Kurt Keutzer, A Text-Compression-Based Method for Code Size Minimization in Embedded Systems, pp. 1-38, 1998
Advanced RISC Machines (ARM), An Introduction to Thumb™, pp. 9-26, Mar. 1995
Maarten Wegdam, Compact Code Generation through Custom Instruction Sets, Nat. Lab. Unclassified Report 822/98, pp. 1-60, Sep. 1998
Andrew Wolfe and Alex Chanin, Executing Compressed Programs on An Embedded RISC Architecture, (Appears in Proceedings of 25th Annual International Symposium on Microarchitectures), pp. 1-19, Dec. 1992
Yukihiro Yoshida, Boa-Yu Song, Hiroyuki Okuhata, Takao Onoye and Isao Shirakawa, An Object Code Compression Approach to Embedded Processors, ACM, pp. 265-268, 1997
April 21, 2020. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
