Huffman-based code compression techniques for embedded systems [Elektronische Ressource] / von Talal Bonny

Sujets

• Informatik

Informations

• Publié par: karlsruher_institut_fur_technologie
• Publié le: 01 janvier 2010
• Nombre de lectures: 27
• Langue: English
• Poids de l'ouvrage: 8 Mo

Extrait

Huffman-based Code Compression
Techniques for Embedded Systems
zur Erlangung des akademischen Grades eines
Doktors der Ingenieurwissenschaften
der Fakult¨at fu¨r Informatik
der Universit¨at Fridericiana zu Karlsruhe (TH)
genehmigte
Dissertation
von
Talal Bonny
aus Aleppo
Tag der mu¨ndlichen Pru¨fung: 18.06.2009
Erster Gutachter: Prof. Dr.-Ing. J¨org Henkel
Zweiter Gutachter: Prof. Dr.-Ing. Wael Adic Talal Bonny, 2010Talal Bonny
August-Bebel-Str.68
76187 Karlsruhe
Hiermit erkl¨are ich an Eides statt, dass ich die von mir vorgelegte Arbeit selbststa¨ndig verfasst
habe, dass ich die verwendeten Quellen, Internet-Quellen und Hilfsmittel vollsta¨ndig angegeben
habe und dass ich die Stellen der Arbeit – einschließlich Tabellen, Karten und Abbildungen –,
die anderen Werken oder dem Internet im Wortlaut oder dem Sinn nach entnommen sind, auf
jeden Fall unter Angabe der Quelle als Entlehnung kenntlich gemacht habe.
Talal Bonny
iiAcknowledgements
First and foremost, I would like gratefully and sincerely to thank my advisor Professor
J¨org Henkel for enabling and supporting the research presented in this thesis and for
offering an enjoyable work environment for his PhD students. This dissertation could not
have been written without his support and guidance.
I am also very grateful to Professor Wael Adi for accepting to be my co-examiner and
providing valuable feedback.
I thank members of our chair “Chair for Embedded Systems” at University of Karlsruhe
for their feedback and interesting discussions, especially (in alphabetical order) Moham-
mad Al Faruque, Hussam Amrouch, Lars Bauer, Thomas Ebi, Fridtjof Feldbusch, Fazal
Hameed, Nabeel Iqbal, Semeen Rehman, Muhammad Shafique and Sammer Srouji. And
allothersthatinfluencedtheresearchofthisPhDthesisandwerenotexplicitlymentioned
here.
I thank the students I supervised during their Master/Diploma thesis for their contribu-
tions to the implementation and evaluation of the code compression techniques.
I am also deeply indebted to my family for believing in me and for giving me the inspira-
tion to apply and complete a doctoral degree. Their love, guidance, and encouragement
have been a constant source of strength for me.
Andlastbutnotleast, myheartfeltthanksgoouttomybelovedbetter-half, Amani, who
has been so patient and supportive since I started the master program. She has been
my inspiration and provided encouragement when research progress was slow, and when
research felt like spiraling out of control, she brought serenity. It should be no surprise
that this dissertation would be impossible without her. I dedicate this thesis to her.
ivList of Publications
Conferences
[C.1] Talal Bonny and J¨org Henkel:
LICT: Left-uncompressed Instructions Compression Technique to Improve
the Decoding Performance of VLIW Processors.
In 46th ACM/EDA/IEEE Design Automation Conference (DAC09), ,
Pages: 903-906, San Fransisco CA, USA, July, 2009 (accepted).
[C.2] Talal Bonny and J¨org Henkel:
FBT: Filed Buffer Technique to Reduce Code Size for VLIW Processors.
In 26th IEEE/ACM International Conference on Computer-Aided Design (ICCAD’08),
Pages: 549-554, San Jose CA, USA, November, 2008.
[C.3] Talal Bonny and J¨org Henkel:
Instruction Re-encoding Facilitating Dense Embedded Code.
In IEEE/ACM Proceedings of Design Automation and Test in Europe Conference
(DATE’08),
Pages: 770-775, Munich, Germany, 2008.
[C.4] Talal Bonny and J¨org Henkel:
Instruction Splitting for Efficient Code Compression.
In ACM/EDA/IEEE Design Automation Conference (DAC07),
Pages: 646-651, San Diego CA, USA, June 2007.
[C.5] Talal Bonny and J¨org Henkel:
Efficient Code Density Through Look-up Table Compression.
In IEEE/ACM Proceedings of Design Automation and Test in Europe Conference
(DATE’07),
Pages: 809-814, Nice, France, April 2007.
vi[C.6] Talal Bonny and J¨org Henkel:
Using Lin-Kernighan Algorithm for Look-up Table Compression to
Improve Code Density
In ACM/IEEE 16th, Great Lakes Symposium on VLSI (GLSVLSI’06),
Pages: 259-265, Philadelphia, USA, April 2006.
Journals
[J.1] Talal Bonny and J¨org Henkel:
Efficient Code Compression for Embedded processors.
In IEEE Transactions on Very Large Scale Integration Systems (TVLSI),
Volume 16, Issue 12, Pages: 1696-1707, December 2008.
Book Chapter
[B.1] S. Parameswaran, J. Henkel, A. Janapsatya, T. Bonny and A. Ignjatovic:
Design and Run Time Code Compression for Embedded Systems.
In Designing Embedded Processors.
pp. 97-128, Springer 2007.
ISBN978-1-4020-5868-4 (HB).
ISBN 978-1-4020-5869-1 (e-book).Abstract
Increasing embedded systems functionality causes a steep increase in code size. For in-
stance, more than 60MB of software is installed in current state-of-the-art cars [9].
It is often challenging and cumbersome to host vast amount of software in an efficient
way within a given hardware resource budget of an embedded system. This may be done
by using code compression techniques, which compress the program code off-line (i.e. at
design time) and decompress it on-line (i.e. at run time).
Among all statistical compression algorithms, Huffman Coding is one of the best com-
pression techniques since it provably provides the shortest average codeword length [36].
When Huffman Coding is used as a compression technique, Look-up Table(s) are gener-
ated to store the original instructions. As the size of the tables becomes large, it may
negatively affect the final compression ratio (defined as the ratio of compressed code to
uncompressed code). Thus, the Look-up Tables diminish the advantages that could be
obtained by compressing the code.
This thesis presents different Huffman-based hardware supported code compression tech-
niques, which can efficiently solve this problem and improve the compression ratio. In
addition to that, this the presents a new technique to improve the performance of the
hardware decoder. The code compression techniques are targeted two processor architec-
tures, namely RISC and VLIW.
In this thesis, the Look-up Table size is reduced by using the “Look-up Table Compres-
sion Technique” for RISC processors. This is done by sorting the entries of the table to
decrease the number of bit toggles between each two successive entries.
To show the efficiency of the “Look-up Table Compression Technique”, we apply it to
twocompressionschemes,i.e.Dictionary-basedCompressionSchemeandStatisticalCom-
pression Scheme.
Using the “Look-up Table Compression Technique” reduces the table size by up to 45%
and improves the compression ratio on average by more than 25%.
The evaluations are conducted using a representative set of applications from MiBench
[20] and are built for three major embedded processor architectures, namely ARM, MIPS
viiiAbstract ix
and PowerPC.
The Look-up Table size may further be reduced if its instructions are encoded efficiently
before the “Look-up Table Compression Technique” is applied to it. For that, the second
compression technique for RISC processors is introduced, which is called “Instruction
Splitting Technique”. This technique reduces not only the Look-up Table size but also
the size of the encoded instructions generated by using Huffman Coding. It splits the
instructions into patterns of varying size before Huffman Coding is applied. Using this
techniqueimprovesthefinalcompressionratio(includingalloverhead)bymorethan20%
compared to known schemes based on Huffman Coding. Average compression ratios of
47% and 49% are achieved for ARM and MIPS processors, respectively.
Both our compression techniques “Look-up Table Compression Technique” and “Instruc-
tion Splitting Technique” are ISA (Instruction Set Architecture)-Independent, i.e. they
can be applied to any processor architecture.
When the ISA is specified, the code compression technique utilizes the information in
the opcodes and the instruction format to build the hardware decoder. In this case, the
compression ratio will be further improved. For that, ISA-Dependent code compression
technique is introduced for RISC processors, which is called “Instruction re-encoding
Technique”. In this technique, the benefits of re-encoding the unused bits in the instruc-
tion format for a specific application are investigated to improve the compression ratio.
Re-encoding those bits may reduce the size of decoding table by more than 37%. Com-
pression ratio as low as 44% is achieved (including all overhead that incurs), targeting
MIPS and ARM processors.
VLIW processors provide higher performance and better efficiency than RISC processors
in specific domains like multimedia applications. The drawback of the VLIW processors
is the bloating code size of their compiled applications in comparison to the size of the
same applications compiled for RISC processors. Therefore, reducing the size of embed-
ded applications is a key issue for VLIW processors.
For that, the last code compression technique (Deflate Algorithm [107]) in this thesis is
targeting the VLIW processors. It significantly reduces the code size compared to state-
of-the-art approaches for VLIW processors.
The Deflate Algorithm is enhanced by using a new technique called “Filled Buffer Tech-
nique”, which can be applied to any Lempel-Ziv family algorithms to improve the com-