SAMC: a code compression algorithm for embedded processors

Author

Lekatsas, Haris ; Wolf, Wayne

Author_Institution

Dept. of Electr. Eng., Princeton Univ., NJ, USA

Volume

18

Issue

12

fYear

1999

fDate

12/1/1999 12:00:00 AM

Firstpage

1689

Lastpage

1701

Abstract

In this paper, we present a method for reducing the memory requirements of an embedded system by using code compression. We compress the instruction segment of the executable running on the embedded system, and we show how to design a run-time decompression unit to decompress code on the fly before execution. Our algorithm uses arithmetic coding in combination with a Markov model, which is adapted to the instruction set and the application. We provide experimental results on two architectures, Analog Devices´ Share and ARM´s ARM and Thumb instruction sets, and show that programs can often be reduced by more than 50%. Furthermore, we suggest a table-based design that allows multibit decoding to speed up decompression

Keywords

Markov processes; arithmetic codes; data compression; decoding; embedded systems; instruction sets; microprocessor chips; ARM; Markov model; SAMC; Share; Thumb; arithmetic coding; code compression algorithm; embedded processors; instruction segment; instruction set; memory requirements; multibit decoding; run-time decompression unit; table-based design; Arithmetic; Compression algorithms; Decoding; Embedded system; Image coding; Instruction sets; Pipelines; Power system modeling; Runtime; Thumb;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.811316

Filename

811316