Procedure based program compression.
Cost and power consumption are two of the most important design factors for many embedded systems, particularly consumer devices. Products such as personal digital assistants, pagers with integrated data services and smart phones have fixed performance requirements but unlimited appetites for reduced cost and increased battery life. Program compression is one technique that can be used to attack both of these problems. Compressed programs require less memory, thus reducing the cost of both direct materials and manufacturing. Furthermore, by relying on compressed memory, the total number of memory references is reduced. This reduction saves power by lowering the traffic on high-capacitance buses. This paper discusses a new approach to implementing transparent program compression that requires little or no hardware support. Procedures are compressed individually, and a directory structure is used to bind them together at run-time. Decompressed procedures are explicitly cached in ordinary RAM as complete units, thus resolving references within each procedure. This approach has been evaluated on a set of 25 embedded multimedia and communications applications, and results in an average memory reduction of 40% with a run-time performance overhead of 10%.
Introduction
We will present a technique for saving power and
reducing cost in embedded systems. We are concerned
primarily with data-rich consumer devices used for
computation and communications, e.g. the so-called
information appliance. Currently this product category
includes devices such as simple Personal Digital
Assistants, pagers and cell phones. In the future, there
is an emerging industry vision of ubiquitous multimedia
devices and the Java appliance. These products have
extremely tight constraints on component cost. It is not
at all uncommon for memory to be one of the most
expensive components in these products, thus providing
the need to reduce the size of stored programs. A
second important design goal is low power
consumption. Each of these products is battery
powered, and reduced power consumption can be
directly translated into extended battery life. Battery
life is often the most important factor for this product
class: once a pager or cellular phone is functionally
verified, battery life is one of the few effective
techniques for product differentiation. For a large
number of embedded systems, the power used to access
memory on the processor bus is the dominant factor in
the system power consumption.
Unlike desktop computing, performance often is not
a primary factor for these devices. While information
appliances are not the classic forms of mission-critical
computing, they tend to have important real-time
aspects. For example, a certain amount of processor
performance is necessary to decode a paging message;
there is little benefit in providing more.
Faced with these factors, we have decided to
investigate the benefits storing programs in a
compressed form. The compressed programs may
reside in any type of memory, often depending on
whether the system supports software field upgrades.
The basic approach is to store the program image in a
compressed form, and dynamically decompress it on
demand. An effective compression scheme would
reduce the amount of system memory required for
various applications, thus saving cost, board space and
some static power consumption. An additional benefit
involves significantly reduced power consumption due
to dynamic memory references. While we believe that
an effective compression scheme will reduce power
consumption, we cannot currently provide any direct
evidence of the relationship.
1.1 Previous Approaches
The relevant previous work can be divided into four
groups: whole program transformation, cache-based
dictionary schemes and highly encoded
instruction set architectures.
The most direct technique for compressing
programs involves explicit compression and
decompression of the complete program. A portion of
RAM is dedicated for a decompressed buffer, and
programs are expanded from their compressed form into
this RAM prior to execution. This approach has been
applied to file systems [1] for saving disk space.
Virtual memory and explicit file caches are usually
effective at reducing the impact of the decompression
algorithms on latency. Unfortunately, this approach is
not well suited to embedded systems. Some
information appliances have only a single application,
for example a data-rich pager with a vertical-market
application such as the Motorola SportsTrax news
device. Whole program decompression for such
systems would result in RAM size exceeding ROM size,
which increases both cost and power consumption.
Wolfe, Chanin and Kozuch presented a scheme for
block based decompression in response to dynamic
demands [2, 3]. Their goal was to improve code
density of general-purpose processor architectures.
They considered a number of compression algorithms,
and concluded that a Huffman code [4], which reduced
code size to 74% of the original, was most effective.
Programs are decompressed as they are brought into the
instruction cache, and thus the compression is
transparent to the executing application. One problem
that Wolfe et al. identified involves translating memory
addresses between the program space (i.e.
decompressed) and the compressed program in the
backing store. For example, if the program does a PC
relative jump, which hits in the cache, the ordinary
cache hardware will resolve the reference. However, in
the case of a cache miss the refill hardware must
determine where in the compressed space the target is
stored. This problem requires a set of jump tables to
patch references from the program space to the
compressed space. A link time tool can be used to
automatically generate the necessary jump tables.
Liao, Devadas and Keutzer developed a dictionary
approach to reduce code size for DSP processors [5].
A correlation is done across all basic blocks in a
program after compilation but before linking. The
purpose of this correlation is to identify common
instruction sequences that exceed some minimal length.
These sequences are written into a dictionary, and each
of the original occurrences is replaced with a mini-
subroutine call (sic), i.e. a procedure call with no
arguments. The application code is a skeleton of
procedure calls and bits of uncommon code sequences.
This approach can be implemented with no hardware
support, and results were presented which indicated that
it might achieve code size reductions of approximately
12%. With a minor modification of the hardware an
additional 4% code size reduction can also be achieved.
While this approach will result in an extremely high rate
of procedure calls, there is no discussion of the impact
of these calls on performance. This issue could be
particularly significant in the face of the tight code
scheduling constraints of their target machine, the Texas
Instruments TMS320C25 DSP.
Ernst et al investigated the use of byte-coded
machine language [6] for compression. This approach
hearkens back to the original goal of tightly encoded
ISA formats for CISC processors, and much of their
work is focused on minimizing the impact on
performance.
2. The Procedure Cache
While Wolfe et al. have developed an effective
technique for transparent code compression, their
approach has two specific features which may prove
disadvantageous. First, since the compression process
is transparent to the supervisor code as well as the
application, the entire decompression and translation
process must be implemented in hardware. While
dedicated decompression hardware has the benefit of
low overhead, there is no option to use the approach on
stock hardware. We are interested in schemes that can
leverage existing hardware, with the option (but not
necessity) of hardware accelerators. Secondly, the
mapping problem between compressed space and
program space complicates the hardware as well as the
linking process.
Pcache
Application Directory
ROM
Compression utilities
Compression Tables
Processor Core
ROM
Hardware Accelerator

Figure

1: Embedded system architecture for pcache
system
In place of dedicated hardware that transparently
code blocks, we propose using demand
driven decompression triggered by procedure
invocations. Procedures are decompressed as atomic
units, and are stored into a dedicated region of RAM
that is explicitly managed by the runtime system (Figure
1). This approach efficiently solves the problem of
address mapping for all references that are contained
within one procedure (e.g. loops and conditional code),
and experience shows that these are the most common
forms of branching. The remaining inter-procedure and
global references must be resolved through the use of a
directory service. We call this software cache the
Procedure Cache (pcache).
The pcache should be able to store any procedure
that is small enough to fit within it. As a result of this
goal the pcache algorithms must manage variable size
objects which may not be aligned on a boundary that is
convenient for addressing, unlike conventional
hardware caches which manage fixed size lines and
blocks. The issue of maximum procedure size is
problematic, and while a number of solutions present
themselves we have not decided yet upon a
recommended path.
2.1 Runtime Binding
Procedure calls are bound together at runtime by
consulting a directory service. A linking tool translates
each call into a request through a unique identifier. The
directory service looks up the location of the call target
and activates the target with the proper linkage needed
for the return operation. A table stored with each
program is used to translate procedure identifiers into
addresses in the compressed memory. As was the case
with the scheme from Wolfe et al., this table must be
generated when the program is linked.
The process used for runtime binding can be broken
down into the following stages:
1. Source invokes directory service with unique
identifier of the target procedure
2. If the target is in the pcache go to step 9
3. Find the target address in compressed
memory by consulting the directory service
4. If enough contiguous free space exists in the
pcache for the target go to step 8
5. If enough fragmented free space exists in the
pcache for the target go to step 7
6. Mark procedures for eviction until enough
space is available
7. Coalesce fragmented space into contiguous
block
8. Decompress target procedure into assigned
pcache location
9. Patch the state to allow the target to return to
the caller
10. Invoke the target procedure
The traditional execution environment binds one
procedure to another through a call instruction, which
typically executes one memory reference and updates
the program counter. Two call instructions are used in
the process above, one at step 1 and one at step 10. Let
l represent the time required to lookup the target
procedure identifier in the directory service data
structure in step 2. Let m represent the time required
for management, which should be relatively stable at
steady state, and let d t
required to
decompress procedure t . The pcache hit rate is
represented by h , and is significant in the calculation
of the expected case performance.
The worst-case execution time involves compacting
the free space and identifying procedures to replace,
followed by the time required to decompress the target
procedure. The worst case call time is
. In the expected case, i.e. that
of a cache hit, the call time is
. In this case it is
clearly important to increase the hit rate. However, in
the limiting case where the hit rate is high, the directory
scheme still imposes a cost of c l
on every procedure
invocation.
A better approach is to cache the address of the
target procedure at the call site, and then avoid the
directory service overhead for subsequent calls to the
target. A similar approach has been used in high
performance object-oriented runtimes systems to
speculatively bind method invocations to typed methods
[7]. The runtime directory binds call sites to targets
once and then patches the call site. Subsequent
invocations jump straight to the target, and then test the
runtime type information to determine if the processor
ended up at the right location. If the test succeeds the
execution continues and if it fails the directory service
is consulted. This approach works if the cached target
address is guaranteed to be the start of a valid code
sequence, which is difficult to guarantee when code
blocks move within the address space after they are
loaded. Such an approach would not work for the
pcache because cache replacement and compaction
make alignment restrictions prohibitively expensive.
Procedures need not be aligned on any standard
boundary, and thus the risk exists that a jump would end
up in the middle of a procedure or in free space.
An alternate approach, which we are advocating, is
to test the validity of the cached target address at the
call site. This scheme involves more test operations in
the pcache than does testing at the destination, since
each procedure has a single entry point but may call
multiple targets. In order to test at the call site, each
procedure must have a prologue that contains the
procedure identifier. Conceptually, the call site loads
the word that precedes the cached target address,
compares it to the target it wishes to invoke, and jumps
to the cached address on a match. This sequence
changes the best case invocation sequence from two
jumps and the directory service lookup to one load, a
test and a conditional jump. For a pcache with a large
number of procedures, and thus an expensive directory
service lookup, the cached target should result in a
performance improvement over the pure directory
scheme.
There is the possibility that some procedure will
have an identifier that corresponds to a legal code
sequence, introducing the danger of a false positive test.
This problem is avoided by introducing a tag byte that
identifies the word as a procedure identifier. The
specific tag byte to use depends on the processor
architecture, as it must correspond to an illegal opcode
and be placed at the proper word alignment.
Unfortunately, this approach is not foolproof for
processors with variable length instructions, such as the
Intel x86 and the 68k. In these cases it is not possible
to guarantee that the target identifier will not match
some code sequence or embedded data, though the
likelihood of this event can be reduced.
Tagging procedure identifiers also makes it easy to
implement a reference scheme in order to approximate
LRU data for pcache management. The runtime system
will periodically clear each of the tag bytes, thus forcing
the cached targets to fail and invoking the directory
service. For machines with 32-bit words the use of tag
bytes does reduce the procedure identifier space to 24
bits, but we feel that this range will prove more than
sufficient for the needs of embedded systems.
2.2 Procedure Returns
Return instructions are a bit complicated because the
traditional code sequence cannot explicitly name the
destination of the return operation. The pcache runtime
system solves this problem by storing three pieces of
data: the source procedure identifier, the predicted
address of the start of then return procedure (that is the
address that the caller had at the time it invoked the
active procedure), and the offset of the call site from the
start of the source procedure. The regular return
procedure is then replaced by a test of the predicted
prologue for the source, and a jump to that address plus
displacement in the event of success. A failure causes
the directory service to lookup (and possibly reload) the
destination of the return operation and then do a jump to
the address plus displacement.
2.3 Replacement Algorithms
The task of allocating space in the pcache for a new
procedure involves a two step process. First, the pcache
is searched for a free block that is large enough to
satisfy the new demand. We have experimented with
both best fit and first-fit for this stage, and have found
that both approaches produce similar results. All of the
results presented below will be with respect to first-fit,
because of the simplified implementation.
If there is enough free space available, but not in
any single block, then the runtime system must invoke
the pcache compactor. The pcache is compacted by
moving all of the live procedures to the start of the
pcache and all of the free fragments to the end of the
pcache.
In the event that the runtime system does not find
must invoke a replacement
algorithm to identify procedures that should be evicted
from the pcache. We have experimented with two
algorithms for replacement: least recently used (LRU)
and Neighbor. With LRU the runtime system scans an
LRU list and marks each procedure in sequence for
eviction, until enough space has been freed. Once this
is accomplished, the compactor is invoked to coalesce
the free space into a single block large enough for the
new procedure. While LRU is easy to implement and
conceptually simple, it will tend to cause a significant
amount of memory traffic in the pcache to coalesce the
fragmented free space. For example, consider the case
where together the two LRU procedures have enough
space to satisfy a new request but happen to reside in
the first and third quadrant of the pcache. The
subsequent compacting stage will need to move
approximately half of the pcache data in order to
combine the space freed up by evicting these two
procedures. It may be the case that the third LRU
procedure could be combined with one of the first two
and resides in an adjoining region of memory. In this
case, the compacting procedure is trivial, since no
intervening procedures need to be moved in the pcache.
While the primary benefit of such an optimization is
reducing the data movement in the pcache, a secondary
benefit is avoiding subsequent tag misses on the moved
procedures, and the resulting lookup events at the
directory service.
We have experimented with two schemes to reduce
the amount of data movement within the pcache in
response to pcache misses. The first scheme is called
Neighbor, and involves looking for sets of adjacent
procedures that are good candidates for eviction. Each
set of procedures is evaluated on the basis of the sum of
squares of the LRU values, where the least recently
used procedure has an LRU value of 1 and all other
increase sequentially. This approach is biased toward
avoiding those procedures that were used recently,
though it does not explicitly exclude them from
consideration. Neighbor scans the pcache for adjacent
blocks of memory that are large enough for the new
request, and considers both free and occupied space.
The algorithm then selects the set of blocks that have
the lowest sum of squares for the LRU values. A more
general form of Neighbor involves evaluating a function
F(S) for each set of neighbors, where F() is some
arbitrary function. The advantage of using a sum of
squares is that it is easy to evaluate at runtime and it
provides a strong bias against selecting the most
recently used procedures.
A modification of this approach is to use a limiting
term to cap the value for each set of adjacent blocks,
and exclude from consideration a set that exceeds this
limit. The goal of this approach is to make it
impossible to remove the most frequently used
procedures, even in those cases where one of these
procedures would otherwise be selected, e.g. when it
neighbors a large procedure which is the least
frequently used.
3. Experiments
3.1 Approach
Trace driven simulation is used to evaluate the
effectiveness of caching whole procedures. The pcache
simulator must know when each procedure is activated,
either through a directed call, the result of a return
operation or an asynchronous transfer (e.g. exception or
UNIX longjmp). The traces are collected with a special
augmented version of Lsim from the IMPACT
compilation system [8]. This tool allows us to
dynamically generate a large set of activation events,
with support for sophisticated trace sampling.
3.2 Applications
There currently exists a significant void with regards
to effective benchmarks for embedded systems. While
a number of industrial and academic efforts have been
proposed, to date there has been little progress towards
a suite of representative programs and workloads. One
part of the problem is that the field of embedded
systems covers an extremely wide range of computing
systems. It is difficult to imagine a benchmark suite
that would reveal useful information to the designers of
machines and cellular phones, because of the
drastically different uses for these products. While
there is some hope for emerging unification in the area
of information appliances, because of the more cohesive
focus to the devices, there currently are no options to
choose from. This unfortunate state of affairs is best
reflected by the continued use of the Dhrystones
benchmark, and the derivative metric Dhrystones per
milli-Watt.
For the purposes of this paper we have adopted a
number of programs from the MediaBench benchmark
suite [9]. Six additional programs have been selected,
five from the SPEC95 benchmark set along with the
Backwater basic interpreter.

Figure

2 and Figure 3 show the cumulative
distribution functions (CDF) of procedure sizes for
bwbasic and go, which represent the typical distribution
and worst case (widest spread) respectively. Data is
presented for both the static program image in memory,
as well as the dynamic distribution seen during
execution. This data suggests that a modest size pcache
will often succeed in capturing the working set. In
general the dynamic data exhibits a slightly slower
growth than the static data and show sharper breaks;
both phenomena are a result of the skewed distribution
of call frequency among the procedures.0.10.30.50.70.9Static
Dynamic

Figure

2: Procedure size distribution for bwbasic
3.3 Pcache Miss Rates

Table

1 shows the raw miss rates for LRU
replacement, while Table 2 presents the same data for
when Neighbor is used for replacement. Miss rates are
calculated by counting each reference generated by the
program, regardless of whether the procedure is actually
cacheable (i.e. smaller than the simulated pcache size).
The significance of low cache miss rates is much more
difficult to evaluate than for a traditional hardware
cache with fixed size objects. For example, there is a
significant difference between missing on the average
static procedure for go, which is under 1k, and missing
on the most frequent procedure which is over 12k.
Nevertheless, the simulator marks both as a single miss
event.0.10.30.50.70.9Static
Dynamic

Figure

3: Procedure size distribution for go
Several application, in particular the raw audio
encoder and decoder, achieve extremely low miss rates.
The general trends are for both LRU and Neighbor to
have very similar hit rates, with two notable exceptions.
Both djpeg and mpeg2enc show high miss rates with 1k
pcaches with both LRU and Neighbor. The rates stay
relatively high for 2k for Neighbor, while the drop for
LRU. In both cases there is a specific procedure which
is frequently called and which is captured by the LRU
dynamics, though not for Neighbor.
The procedure size CDF of go (Figure suggests
that the dynamic reference stream has a much larger
footprint than bwbasic (Figure 2), and thus it is not
surprising that bwbasic shows reduced miss rates for
comparable pcache sizes. On the other hand, a
relatively small pcache size (e.g. 16k or 32k) can still be
very effective.
The miss rate data displays an interesting result:
Neighbor generally achieves a lower miss rate than
LRU. While it is certainly possible for pathological or
pedagogical cases to exhibit behavior like this, in
general LRU is expected to achieve the highest hit rates.
This behavior is a consequence of the caching of
variable size objects.
Consider the case of a hardware cache with a fixed
block size. If a certain amount of space must be made
available and the entire cache is allocated, a specific
number of blocks must be evicted from the cache. For
such a cache LRU has proven to be effective at
providing the best guess for which blocks should be
evicted. With the software pcache used here the
number of procedures evicted from the pcache depends
upon the specific procedures selected. We explain this
result by considering three different types of pcaches:
small, medium and large. For a small pcache Neighbor
will tend to approach LRU performance because of the
smaller spread in LRU values between the least and the
most recently used procedures. For a large pcache
evictions will be rare so performance will approach the
compulsory miss regardless of the replacement
algorithm. For the medium case some number of
references will be satisfied by the available free space,
and for these the replacement algorithm is
inconsequential. Assume that the CDF of procedure
size is not correlated to LRU value 1 , and a new
procedure activation causes the runtime to invoke the
replacement algorithm. For half of these cases the size
of the newly activated procedure will be equal to or less
than the size of the LRU procedure, and thus both LRU
and Neighbor will select the LRU procedure. For the
remaining cases, the LRU algorithm will traverse the
list of least frequently used procedures and mark each
for eviction until the amount of space freed up is at least
equal to the new request. Neighbor, however, looks for
contiguous blocks that are good candidates according to
a specific cost function. By relying on the SQU(LRU)
cost function, Neighbor is biased against combining
multiple procedures into the best set.

Figure

4 illustrates this phenomenon. Assume that
three "units" of space must be freed up. The LRU
algorithm will choose the first three procedures on the
LRU list (procedures 23, 17 and 87) for eviction and
1 While this may not hold in all cases, we believe
that the assumption is valid in general.
then invoke the compactor to coalesce the space. On
the other hand, because Neighbor is using the square of
the LRU counts, it will select procedure 12 for
eviction 2 . We have found that, in general, for those
cases where LRU and Neighbor select different sets of
procedures for replacement Neighbor tends to select
fewer procedures. Continuing the example in Figure 4,
while it may be a good idea to evict either procedure 17,
or 87 before procedure 12, it seems intuitive that it
would not be best to evict all three rather than 12.
Proc 12: LRU: 4: Cost:
Proc
Proc 23: LRU: 3: Cost: 9
Proc 35: LRU: 12: Cost: 144
Proc 87: LRU: 2: Cost: 4 Selected by
LRU
Selected by
Neighbor

Figure

4: Example: LRU chooses "optimal" set
while Neighbor evicts fewer procedures
The pcache miss rate for gcc is a direct result of the
dynamic program size CDF. The most frequently used
procedure in gcc is over 12k bytes and corresponds to
8% of the procedure activations, while the second most
common procedure is 52 bytes and corresponds to 2%
of the procedure activations. Although procedures that
exceed the pcache size are excluded they still contribute
to the count of procedure activations: thus the gcc
simulations have low hit rates for pcaches below 64k
bytes. An interesting phenomenon may occur when one
of these large and common procedures is finally
admitted to the pcache. The impact of introducing the
large procedure into the pcache causes LRU to evict a
huge number of procedures, while as was just discussed
Neighbor tends to evict fewer. The resulting impact on
pcache miss rate for LRU can be dramatic, as seen for
gsmencode between 8k and 16k.
3.4 Compacting Events

Table

3 and Table 4 show the rate of compaction
events per procedure activation, rather than raw event
counts, in order to make the presentation consistent
across the test programs. This data illustrates the
effectiveness of the Neighbor algorithm. While both
Neighbor and LRU achieve roughly comparable results
for pcache hit rates, Neighbor is much more effective at
reducing the number of compacting events. For this
data, the Neighbor algorithm generally produces a much
2 Note that the position of procedure 35 (with a high
LRU) in the cache blocks Neighbor from merging
procedures 17 and 35 along with the free space adjacent
to 35.
flatter response as a function of pcache size. This
performance is a consequence of Neighbor compacting
the pcache only when there is already enough free space
and no procedure eviction is required. The amount of
expected free space in a pcache is not monotonic with
pcache size, but rather is a complicated function of the
size of dynamic references. This fact is illustrated for
pcache size of 8k for go, illustrating that the rate of
compacting events can actually increase in response to
an increase in pcache size. Again, gcc shows a sharp
response soon after the admission of the 12k procedure.
126.gcc
cjpeg
djpeg
gsmdecode
mipmap
pgpdecode
rasta
rawdaudio
unepic

Figure

5: Performance impact of pcache operations,
relative to the base case
4. Performance
The pcache structure will reduce performance due to
three types of events: cache management including
LRU management and directory service, memory
movement due to compaction events within the pcache,
and decompression of data transferred from memory.
The impact of these factors was evaluated, and the
resulting performance is shown in Figure 5. Because of
the large volume of memory traffic into and within the
pcache, the management component has comparatively
little impact on performance. Each byte of memory
moved within the pcache due to compaction was
charged half of a clock cycle, assuming that two 32-bit
memory operations are required and loop unrolling can
be used to hide loop management overhead. The
compression technique used is based on an algorithm
that requires an average of 22 cycles on a SPARC to
compress each byte of SPARC binaries and achieves a
60% compression ratio [10]. However, a number of
algorithms could be selected to balance the demands of
performance against compression. In particular, an
application of Huffman coding (in hardware) will be
briefly discussed later.
The average slowdown for all of the applications is
166% with a 64k-byte pcache. However, when go and
gcc are excluded from the pcache, the average
slowdown is only 11%. These numbers climb to 600%
and 36% for 32k-byte caches. Clearly, it is important to
exclude ill-behaved applications from the pcache, but
this problem is easy to manage with an embedded
system where the software is generally more highly
tuned to the execution environment.
5. Discussion
While there is a benefit to considering schemes that
require no additional hardware, the pcache architecture
can still take advantage of hardware acceleration if
available. A number of researchers have designed
hardware for instruction decompression. A particularly
good example is [11], which provides 480Mb/s
Huffman decompression on a Mips instruction stream.
This device requires 1 cm 2 in 0.8-micron process
technology. When used with hardware decompression,
the pcache is still effective at increasing compression
rates, by increasing significantly increasing the block
size. Furthermore, the dictionary size is reduced, since
instead of having an entry for every possible jump
target there is only an entry for each subroutine.
It is impossible to say how the pcache will interact
with traditional hardware caches without discussing the
specific hardware configuration. If the pcache memory
is nearby on high-speed SRAM the cache should ignore
it, as transparent caching in hardware will provide no
direct latency benefit while consuming valuable
resources. On the other hand, if the pcache memory is
relatively slow it should be cached by the hardware as
well. Almost all sophisticated embedded processors
include memory control hardware for functions such as
chip-select, wait-state insertion and bus sizing. This
hardware should be augmented to allow blocks of
memory to become non-cacheable, which is a common
feature in high-performance processors.
6. Conclusions
We have presented a new approach to applying
compression to stored program images. This technique
can easily reduce the program storage by approximately
40%, which can correspond to a significant cost
reduction for embedded products targeted to the
consumer market. By compressing complete
procedures, rather than smaller sub-blocks, we are able
to avoid the cost of dedicated hardware. The resulting
performance impact has been measured to be
approximately 10% for a wide range of sophisticated
embedded applications.
Trace driven simulation has been used to evaluate
the opportunity of using compression and the associated
tradeoff points. The results suggest that a small
software controlled cache, perhaps 16k bytes of
standard SRAM, can be effective at caching the
working set and reducing dynamic memory traffic. The
additional effect of compressing traffic on the system
bus further decreases main memory traffic, and thus
helps to attack the problem of power consumption.



--R

"Combining the Concepts of Compression and Caching for a Two-Level Filesystem,"
"Executing Compressed Programs on an Embedded RISC Architecture,"
"Compression of Embedded System Programs,"
"A Method for the Construction of Minimum Redundancy Codes,"
"Code Density Optimization for Embedded DSP Processors Using Data Compression Techniques,"
"Code Compression,"
"Efficient Implementation of the Smalltalk-80 System,"
"IMPACT: An Architectural Framework for Multiple-Instruction- Issue Processors,"
A Tool for Evaluating Multimedia and Communications Systems,"
"An Extremely Fast Ziv-Lempel Data Compression Algorithm,"
"A High-Speed Asynchronous Decompression Circuit for Embedded Processors,"
--TR
Combining the concepts of compression and caching for a two-level filesystem
IMPACT
Executing compressed programs on an embedded RISC architecture
Code compression
Compression of Embedded System Programs
Code density optimization for embedded DSP processors using data compression techniques
A High-Speed Asynchronous Decompression Circuit for Embedded Processors
Efficient implementation of the smalltalk-80 system

--CTR
Israel Waldman , Shlomit S. Pinter, Profile-driven compression scheme for embedded systems, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy
Saumya Debray , William S. Evans, Cold code decompression at runtime, Communications of the ACM, v.46 n.8, August
Youtao Zhang , Jun Yang , Rajiv Gupta, Frequent value locality and value-centric data cache design, ACM SIGPLAN Notices, v.35 n.11, p.150-159, Nov. 2000
Youtao Zhang , Jun Yang , Rajiv Gupta, Frequent value locality and value-centric data cache design, ACM SIGOPS Operating Systems Review, v.34 n.5, p.150-159, Dec. 2000
Stacey Shogan , Bruce R. Childers, Compact Binaries with Code Compression in a Software Dynamic Translator, Proceedings of the conference on Design, automation and test in Europe, p.21052, February 16-20, 2004
G. Hallnor , Steven K. Reinhardt, A compressed memory hierarchy using an indirect index cache, Proceedings of the 3rd workshop on Memory performance issues: in conjunction with the 31st international symposium on computer architecture, p.9-15, June 20-20, 2004, Munich, Germany
Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, ACM SIGPLAN Notices, v.34 n.5, p.139-149, May 1999
Jun Yang , Youtao Zhang , Rajiv Gupta, Frequent value compression in data caches, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.258-265, December 2000, Monterey, California, United States
Marc L. Corliss , E. Christopher Lewis , Amir Roth, A DISE implementation of dynamic code decompression, ACM SIGPLAN Notices, v.38 n.7, July
Charles Lefurgy , Eva Piccininni , Trevor Mudge, Evaluation of a high performance code compression method, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.93-102, November 16-18, 1999, Haifa, Israel
Bita Gorjiara , Daniel Gajski, FPGA-friendly code compression for horizontal microcoded custom IPs, Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays, February 18-20, 2007, Monterey, California, USA
O. Ozturk , H. Saputra , M. Kandemir , I. Kolcu, Access Pattern-Based Code Compression for Memory-Constrained Embedded Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.882-887, March 07-11, 2005
Susan Cotterell , Frank Vahid, Synthesis of customized loop caches for core-based embedded systems, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.655-662, November 10-14, 2002, San Jose, California
Susan Cotterell , Frank Vahid, Tuning of loop cache architectures to programs in embedded system design, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan
Oliver Rthing , Jens Knoop , Bernhard Steffen, Sparse code motion, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.170-183, January 19-21, 2000, Boston, MA, USA
Marc L. Corliss , E. Christopher Lewis , Amir Roth, The implementation and evaluation of dynamic code decompression using DISE, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.1, p.38-72, February 2005
Guilin Chen , Mahmut Kandemir, Optimizing Address Code Generation for Array-Intensive DSP Applications, Proceedings of the international symposium on Code generation and optimization, p.141-152, March 20-23, 2005
Milenko Drini , Darko Kirovski , Hoi Vo, Code optimization for code compression, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Sifting out the mud: low level C++ code reuse, ACM SIGPLAN Notices, v.37 n.11, November 2002
Milenko Drini , Darko Kirovski , Hoi Vo, PPMexe: Program compression, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.1, p.3-es, January 2007
Bjorn De Sutter , Ludo Van Put , Dominique Chanet , Bruno De Bus , Koen De Bosschere, Link-time compaction and optimization of ARM executables, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.1, February 2007
rpd Beszdes , Rudolf Ferenc , Tibor Gyimthy , Andr Dolenc , Konsta Karsisto, Survey of code-size reduction methods, ACM Computing Surveys (CSUR), v.35 n.3, p.223-267, September
Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Link-time binary rewriting techniques for program compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.882-945, September 2005
pagers;run-time performance overhead;procedural reference resolution;multimedia applications;procedure-based program compression;compressed memory;cached procedures;battery life;power consumption;high-capacitance bus traffic;consumer devices;embedded systems;RAM;memory references;performance requirements;source coding;transparent program compression;smart telephones;design factors;directory structure;memory reduction;integrated data services;communications applications;personal digital assistants