Proc. International Workshop on Synthesis And System Integration of MIxed Technologies (SASIMI '97)
Osaka, Japan, August 1997

Instruction Code Compression
for Application Specific VLIW Processors
Based on Automatic Field Partitioning
Nagisa Ishiura†

Masayuki Yamaguchi†,††ishiura@ise.eng.osaka-u.ac.jp

masa@edag.ptdg.sharp.co.jp† Dept. Information Systems Engineering†† Precision Technology Development Center

Osaka University
Suita, Osaka, 565 Japan

Sharp Corporation
Tenri, Nara, 632 Japan

This paper presents a method of reducing the instruction memory size of application specific VLIW processors. Given an object code of a processor, we try tocompress it by recoding each instruction word with asmaller number of bits. The problem of finding a goodcoding which achieves large reduction and yet curbs
the size and the delay of the decoder is reduced tothe problem of finding a good field partitioning. By
establishing a relation between a field partition andthe cost of the program and decoders, we formulate
an optimum field partitioning problem in which a fieldpartition minimizing the cost of the program and thedecoder is sought. We have developed an approximation algorithm to solve this problem. In a preliminary experiment on three sets of practical VLIW processors and application programs, the total objective
cost, which is defined as the sum of the total bits ofthe coded program and the size of the ROMs to implement the decoder, is reduced into 46%∼60% of theoriginal ones.

I. Introduction
A VLIW architecture is becoming increasingly popular in embedded processor design, for the simultaneous
activation of multiple hardware resources enables fast execution of softwares in audio and video applications. A
drawback of this architecture is that the memory space
to store the instruction code becomes larger. The long
instruction word, whose every bit may not be utilized inevery execution step, leads to large instruction memory
size. Since the size of the memory is directly related tothe hardware cost and the power consumption, the reduction of the instruction memory size will be beneficial tothe overall cost-performance of the system.
One resource we can exploit for this purpose is the factthat processors are application specific. By making certain modifications to the instruction set or on the instruction formats taking the characteristics of the given program into account, we may be able to reduce necessary

bits to store the program.
Unlike the methods of redesigning both the instruction set and the datapath architecture, or the methodsof synthesizing an instruction set and a datapath architecture from a given set of benchmark programs [Hua93],
we start from where a datapath architecture and an application program to be executed on it are given. We
assume a hardware designer has “done a good job” in designing datapath architecture taking the characteristics ofthe program and various constraints on the hardware into
consideration, using support tools such as an architectureevaluator [Yam97]. Thus what we try to do here is tocompact the program without touching the datapath.
One method of doing this is to store the program in acompressed form (Figure 1). When the processor fetches
the next instruction, it is supplied by way of a decoderthat expands the compressed code. So far, a cache-based
method [Koz94] and a code-by-code method [Yos97] havebeen proposed. The former encodes the program by theunit of a cache block. It achieves high compression ratiowith the use of variable length coding, but the delay andthe cost of the decode engine will be significantly large.
Moreover, it does not fit in the architectural scheme if theprocessor does not employ an instruction cache. The latter encodes each instruction word by fixed length coding.
If the program consists of M different code words, theneach word can be encoded with ⌈log M ⌉ bits. The problem
again is the the size of the decoder. Even in the code-bycode approach, the decoder size, measured in ROM bits
to implement the decoder, is 2⌈log M⌉ ×(instruction wordsize) bit large and could offset the gain obtained by thecode compression.
In this paper, we propose an improved code-by-code
method which can reduce the program size while curbing
the decoder size. The idea is to introduce field partitioning. As is usually done in designing vertical microinstruction sets from horizontal microinstruction sets, the original instruction word is partitioned into several fields sothat the decoder for each field stays within a reasonable
size. In order to obtain a good field partition automati-

105

processor

processor

instruction

instruction
decoderaddress

addresscally, we formulate a field partitioning problem and give
an approximate solution to this problem.
This method is applicable to all kinds of processors with
fixed instruction word length, but we think it is especiallyeffective for VLIW processor. In a preliminary experimenton three sets of industrial VLIW processors and application programs, the total objective cost, which is definedas the sum of the total bits of the coded program and thesize of the ROMs to implement the decoder, is reduced
into 46%∼60% of the original ones.
In the following sections, we first formulate the optimum field partitioning problem and then show an approximation algorithm. After presenting the experimental results, we discuss pros and cons of our approach.

instruction
memory1 2 3 4 5 6 7 8 9 10001 0001 001
001 0001 010
001 0001 100
001 0001 100
001 0001 100
001 0001 100
001 0010 001
001 0010 010
001 0010 010
001 0010 010
001 0100 010
001 0100 100
001 1000 001
001 1000 001
010 0001 001
010 0001 010
010 0001 100
010 0001 100
010 0001 100
010 0010 001
010 0010 010
010 0100 010
010 0100 100
010 1000 001
101 0001 001
101 0010 001
101 1000 001
110 0001 001
110 0010 001
110 1000 001

instruction
memory(coded)Figure 1: Configuration of a processor and an instruction
memoryII. Optimum Field Partitioning Problem

Figure 2: Sample program.

A. Formulation
Let a given application specific program consist of N
instructions, each of which is w bit long. Let B ={b1 , b2 , · · · , bw } be the set of bit positions in an instruction word. Then a field partition F = {f1 , f2 , · · · , fn } is apartition of B where fi ⊆ B, f1 ∪· · ·∪fn = B, fi 6= φ, andfi ∩ fj = φ for i 6= j. We call each fi a field. Let M (fi )be the number of different bit patterns appearing in field
fi of the program. For example, if a program consistsof only ADD and SUB instructions, then the number ofdifferent bit patterns that appears in the field specifying
the operation is two. Let m(fi ) be the number of bits toencode the M (fi ) patterns of field fi . Since we assume
the minimum number of bits, we havem(fi ) = ⌈log M (fi )⌉.
The size of the (coded) program for partition F , denotedby P (F ), is expressed asX
P (F ) =N · m(fi ).
fi ∈FThe decoder size D(F ) for partition F isX
D(F ) =d(fi )
fi ∈F

where d(fi ) is the decoder size for field fi . There are various ways of defining a decoder cost, but here we define it

as the size of the ROM, in terms of bits, which implements
the decoder. Thus d(fi ) is defined as|fi | · 2m(fi ) (m(fi ) ≥ 2)d(fi ) =.
0(m(fi ) ≤ 1)
The reason why d(fi ) is 0 for m(fi ) ≤ 1 is that decoder isimplemented with only wires or inverters. Our objective
cost T (F ) is the sum of the program size and the decodersize.
T (F ) = P (F ) + D(F ).
Finally, an optimum field partitioning problem is a problem to find a field partition F that minimizes T (F ) for agiven program.
B. Examples of Field Partitioning
Let us illustrate how field partitioning works using asimple example in Figure 2. The instructions are sorted
for easier understanding. It consists of 30 instructions andeach instruction word is 10 bit long. The original program
size is 10 × 30 = 300 bits.
In the 30 instructions, we have only 22 different instructions, for some instructions are repeatedly used. Then wecan code the 22 patterns using ⌈log 22⌉ = 5 bits. By
this coding, the program size becomes 5 × 30 = 150 bits,
the half of the original one. However, we must count the106cost of the decoder. If it is implemented by an ROM,the necessary bits are 25 × 10 = 320. The total cost of
150 + 320 = 470 bits is even larger than the original program.
Now we see a few ways of field partitioning. The first
three bits (bits 1–3) may correspond to a field that chases
ALU operations. In this example, we see only four different patterns on this three bit field. Then we can recodethem using two bits. Similar y bits 4–7 that presents only
four different one-hot-code patterns can be coded withtwo bits. This kind of patterns may be generated in arbitrating bus access or selecting operands. Since the final
bits 8–10 shows only three distinctive patterns and codedwith two bits, the coded instruction word will consist of
2 + 2 + 2 = 6 bits (see Figure 3 (a)). The decoder sizesare22 × 3, 22 × 4, and 22 × 3
which accumulate to 40 bits. Total hardware cost withthis field partitioning is 6 × 30 + 40 = 220 bits.
Depending on programs, it is sometimes effective to
make the field larger. By grouping bits 4–10 into a single
field, we find only eight patterns out of possible twelve
patterns. This corresponds to the case where the patterns of operand references are somehow limited. If we
code this with three bits, as shown in Figure 3 (b), theinstruction word becomes 5 bit long. Since the decoder
size is 22 ×3+23 ×7 = 68, the total cost is 5×30+68 = 218
bits and slightly better than the previous one.
We need not restrict ourselves to the knowledge of a
relation between the bits and the hardware control. We
could detach the bit 1 from bits 2–3 and join it with bit
8–10. The resulting field partition (Figure 3 (c)) also
produces an instruction format of 5 bit long. The decoder
cost of 0 × 2 + 22 × 4 + 22 × 4 = 32 bits and the total cost
becomes 150 + 32 = 182 bits. In this way, we can makegood use of a correlation between a specific operation andits operand reference patterns.

f1
123
001
010
101
110

f2
4567
0001
0010
0100
1000

f3
8 9 10
001
010
100

00
00
01
01
10
10
11
11
12
34
f1′
f2′
(a) Field partitioning (1).

f1
123
001
010
101
110

00
01
10
11
12
f1′

f2
4 5 6 7 8 9 100001001
00010100001100
0010001
001001001000100100100
1000001

56
f3′

000
001
010
011
100
101
110
111
345
f2′

(b) Field partitioning (2).
f1
23
01
10

0
1
1
f1′

f2
4567
0001
0010
0100
1000

f3
1 8 9 10
0001
0010
0100
1001

00
01
10
11
23
f2′
(c) Field partitioning (3).

107

00
01
10
11
45
f3′

Figure 3: Examples of field partitioning.

III. Approximation Algorithm
We have developed an approximation algorithm to solve
the field partitioning problem, for it would take enormous
computation time to find exact solutions.
Our algorithm tries to search an optimal partition by
merging fields starting from the primitive partitioning
F = {{b1 }, {b2 }, · · · , {bw }} where each field consists ofa single bit. Merges of the largest cost gains are applied
repeatedly until we have no more cost improvement.
This scheme is, unfortunately, easily trapped by local
optima. Merges which would produce good field partition in the future are often rejected because the cost gainat hand is zero. To counter this problem, we introduce
auxiliary costs T ′ (F ) and T ′′ (F ) which can express thequality of the merges more precisely.
Let us consider the example of Figure 4 (a). If we merge
1, 2, and 3, the number of the different patterns on this

00
01
10

123
000
001
111
101

(a)

12
00
00
01
01
10
10
11
11

34
00
00
00
01
10
10
10
11

5
0
1
0
1
0
1
0
1

(b)

Figure 4: Fraction of a program.

field will be four. The field can be recoded with two bits
and we can save one bit. However, in order to merge thethree bits by our algorithm, we should first merge either
two bits of them. The merge of any two bits of the three
results in three different patterns, which requires two bits.
Since the merge does not reduce the necessary bits for the
instruction word, the merge of any two bits is rejected andwe have no way to merge the three bits.
This type of rejection of merges is due to the fact thatthe cost is not improved until the number of different
patterns decreases below 2’s power. The merge whichlargely reduce the number of different patterns should beselected even if the cost gain on the spot is zero, for it
may lead to significant reduction of the cost in the future.
For this purpose, we use exact value of log M (fi ), insteadof ⌈log M (fi )⌉, to represent the necessary bits to encode
the field. In the example above, the necessary bits torecode the new field obtained by merging bits 1 and 2 isevaluated to be log 3 = 1.58, instead of ⌈log 3⌉ = 2, whichmakes the gain positive. The approximate cost function
T ′ (F ) is created in this way, which is formally defined asfollows:F ← {{b1 }, {b2 }, · · · , {bw }};repeat {find (fi , fj ) ∈ F × F that maximize G(F, fi , fj );if (G(F, fi , fj ) > 0) merge fi and fj ;else {
find (fi , fj ) ∈ F × F that maximize G′ (F, fi , fj );if (G′ (F, fi , fj ) > 0) merge fi and fj ;else {
find (fi , fj ) ∈ F × F that maximize G′′ (F, fi , fj );if (G′′ (F, fi , fj ) > 0) then merge fi and fj ;}}} until (no more merge occurs)

Figure 5: Approximation algorithm for field partitioning.
m′′ (fi )=H(fi ),′′d′′ (fi ) =|fi | · 2m (fi ) ,X
P ′′ (F ) =N · m′′ (fi ),fi ∈FD′′ (F )=Xd′′ (fi ),

fi ∈F
′′

T (F ) =P ′′ (F ) + D′′ (F ).
m′ (fi )=log M (fi ),m′ (fi )′d (fi ) =|fi | · 2,
X
P ′ (F ) =N · m′ (fi ),fi ∈FD′ (F )=Xd′ (fi ),fi ∈F′

T (F ) =P ′ (F ) + D′ (F ).
Unlike in the exact cost T (F ), the decoder cost d′ (fi ) is
not defined as zero even for m′ (fi ) ≤ 1. This is due to thesame reason why we do not round up the value of m′ (fi ).
The other cost function T ′′ (F ) attempts to evaluate
the quality of the merges even more precisely than T ′ (F ).
Consider an example in Figure 4 (b). Both the merge ofbits 1, 2 and the merge of bits 3, 4 result in four different patterns and thus present the same cost gains in theprevious cost functions. However, the distribution of patterns is less uniform in the field (3,4) than (1,2). Since
the merges resulting in biased distribution can lead to the
reduction of different patterns in future merges, it should
be given a higher priority. (Compare the merge (1,2,5)and (3,4,5)). The bias is well-known to be numerated as
entropy. It fits into our scheme very well, because theentropy of an information source works as a lower boundof the number of bits to encode the symbol of the source.
Let H(fi ) be the entropy of the set of patterns appearing
in field fi . Then the cost T ′′ (F ) is defined as follows:

Our approximation algorithm is constructed using
the three cost functions as listed in Figure 5. Here,
G(F, f1 , f2 ) is the gain of the cost T obtained by merging f1 and f2 in field partition F . Let F(f1 ,f2 ) denotethe new field partition obtained by merging f1 and f2 infield partition F , then G(F, f1 , f2 ) = T (F ) − T (F(f1 ,f2 ) ).
G′ (F, f1 , f2 ) and G′′ (F, f1 , f2 ) represent the gains of costs
T ′ and T ′′ , respectively, which are defined in the sameway. Starting from an initial partitioning where each field
consists of a single bit, merges of two fields are tried until
there are no candidates. If there exist field pairs that improves T (F ), then a merge of the largest gain is adopted.
If no field pairs improve T (F ), then a merge that shows
the largest gain of T ′ (F ) is adopted. Furthermore, if wehave no field pairs that improve T ′ (F ), then a merge ofthe largest gain in T ′′ (F ) is adopted. Finally, when eventhe improvement of T ′′ (F ) is impossible, the algorithm
finishes.
In order to find a pair of fields (fi , fj ) that maximize
G(F, fi , fj ), G′ (F, fi , fj ), and G′′ (F, fi , fj ), we must compute the gains for all the possible pairs at the beginning.
Since it takes O(N ) to compute the gains for a pair, thecomputation time for all the pairs is O(N w2 ). Every timea pair is merged, we must have the gains for the pairs associated with the new fields created by the merge. This costs
O(N w) time for each creation of a new field, which accumulates to O(N w2 ) throughout the computation. Thus
the total computation time of this approximation algorithm is O(N w2 ).

108

Table 1: Experimental results.

P1

P2

P3

code
length
(bit)
vliw
80
min
11
auto
26
vliw
52
min
11
auto
26
vliw
52
min
11
auto
20

program decoder
P
D
(bit)
(bit)
227,360
031,262 163,840
73,892 31,233
183,404
038,877 122,880
74,067 36,360
249,392
052,756 122,880
95,920 24,072

total
T
%
(bit)
227,360 100.00
195,102 85.81
105,124 46.24
183,404 100.00
161,877 88.15
110,427 60.21
249,392 100.00
175,636 70.43
119,992 48.11

IV. Experimental Result
We implemented an experimental version of a code compression program based on the method described so far.
We applied it to three industrial programs P1, P2, andP3 for embedded VLIW processors. P1 and P2 are programs for audio encoding/decoding and P3 for video encoding/decoding. The size of the programs are 2,842,
3,527, and 4,796 instructions, respectively.
Table 1 shows the evaluation of the code length, program size P , decoder size D, and sum of the program anddecoder T for three field partitioning. “Vliw” is the initial(one-bit per one-field) partitioning which corresponds tothe original VLIW code. “Min” is the partitioning where
all bits are grouped into a single field. This corresponds
to the encoding method [Yos97] without field partitioning.
“Auto” is the field partition obtained by our algorithm.
It turned out that our algorithm sometimes tend to doexcessive merge of fields which makes decoder cost significantly large. In order to avoid this, we rejected themerge which makes the ratio of D(F ) to P (F ) greaterthan a constant r. (The value of r is set to 0.7 in thisexperiment.)
Although “min” reduces the program size the most, thedecoder costs are so large that the total costs remain 70%∼ 85% of the original ones. Our method, on the other
hand, reduces the cost to 46% ∼ 60%.
The program is currently implemented in perl andthe computation time for P1, P2, P3 on UltraSPARC(200MHz) is 235 sec., 180 sec., and 169 sec., respectively.

V. Conclusion
We presented a method of reducing size of object codesof application specific VLIW processors.
The most simple way of applying this method to embedded system design is to store coded program in the
instruction memory and to expand them by a decoder attached to a processor core. We may be able to reduce thechip area for programs, the power consumption, and also
the bandwidth between the instruction memory and theprocessor.

If the decoding delay is critical, we may have to change
control pipeline scheme or redesign (resynthesize) the decoder of the processor. We may be able to reduce theoverall decode delay by merging our decoder to the original decoder of the processor.
Another application we have in mind is to use this technique to design assistance or automatic synthesis of instruction sets. Our program gives us information on bit
correlation which may be utilized in design of instruction
format. If we can use compilers from high-level language
to horizontal instruction codes, we may directly apply thecode compression to the horizontal code, skipping the instruction set design.
One demerit of our scheme in practical system design isthat we can not start the implementation of the decoder
and a part of control unit until we finish the software.
Software design with compiler is a requisite to our scheme.
Finally, it is also obvious that our approximation algorithm leaves much to be improved. It should be reconsidered so that it can find better solutions in shorter amountof time.
Acknowledgement
Authors express their appreciation to Prof. Isao Shirakawa and Mr. Takao Onoye of Osaka University, Dr.
Takashi Kambe and Dr. Tetsuya Fujimoto of Sharp Corporation for their helpful advice and discussion.
References[Hua93] I.-J. Huang, B. Holmer, and A. Despain: “ASIA:
Automatic Synthesis of Instruction-Set Architectures,” in Proc. SASIMI ’93, pp. 15–22 (Oct. 1993).
[Koz94] M. Kozuch and A. Wolfe: “Compression of Embedded System Programs,” in Proc. IEEE Int. Conf.
Computer Design (ICCD ’94), pp. 270–277 (Oct.
1994).
[Yam97] M. Yamaguchi, A. Yamada, T. Nakaoka, T.
Kambe and N. Ishiura, “Architecture Evaluation
Based on the Datapath Structure and Parallel Constraint,” IEICE Trans. Fundamentals of Electronics,
Communications and Computer Sciences, vol. E97A, no. 10 (Oct. 1997).
[Yos97] Y. Yoshida B. Y. Song, H. Okuhata, T. Onoye,and I. Shirakawa: “Low-Power Consumption Architecture for Embedded Processor,” in Proc. 2nd International Conference on ASIC, pp. 77–80 (Oct. 1996).

109