Compiler Supports and Optimizations for PAC
VLIW DSP Processors ?
Yung-Chia Lin
Yi-Ping You

Chung-Lin Tang
Chung-Ju Wu
Ya-Chiao Moo
Sheng-Yuan Chen

Ming-Yu Hung
Jenq-Kuen Lee

Department of Computer Science
National Tsing-Hua University
Hsinchu 300, Taiwan

Abstract. The Parallel Architecture Core (PAC) is a new VLIW DSP
architecture, featuring a two cluster design, and partitioned, distributed
register files with restricted access ports. Such an irregular processor
poses many challenges in the construction of its compiler. This paper
presents our work in providing the compilation support for PAC, basedon the Open Research Compiler (ORC). We describe the design of the
PAC processor and code generation methods used in coping with its
features. Evaluation results of the compiler/architecture are then given,demonstrating the effectiveness of our presented methods.

1

Introduction

Current embedded applications and mobile systems are moving towards the conflicting requirements of high-performance and low-power consumption. This has
influenced embedded processor design to evolve into a style of large computation resources combined with restricted and/or specialized datapaths and register storage. These architectures rely on the compiler to do much work, staticallyorchestrating the generated code to work around the restrictions of the hardware.
In this paper we describe our work in supporting such an embedded DSP
processor. The Parallel Architecture Core (PAC) [3–5] is a new VLIW DSP processor designed by the SoC Technology Center, Industrial Technology ResearchInstitute, Taiwan. It is architecturally designed to meet high-performance andlow power requirements of embedded multimedia in portable devices.
The remainder of this paper is organized as follows. Section 2 describes the
PAC architecture and its related compilation issues. The development of the PAC
compiler based on ORC [1] and its code generation are presented in Section 3. Experimental benchmark results of the compiler/architecture in its current state are
given in Section 4. Our current experiments show that our scheduling/allocation
methods for PAC’s datapath and register file design are quite effective. Other?

The work was supported in part by NSC under grant no. 93-2220-E-007-019 and93-2220-E-007-020, by Ministry of Economic Affairs under grant no. 93-EC-17-A-03S1-0002 and 94-EC-17-A-01-S1-034, and by MOE research excellent project under
grant no. 94-2752-E-007-004-PAE in Taiwan

transformations such as peephole optimizations, and the higher-level loop-nest
optimizer (LNO), are also put into comparison. Section 5 concludes this paper.

2

The Parallel Architecture Core

The Parallel Architecture Core (PAC) is a fixed-point, 5-way issue VLIW DSP
architecture. PAC contains two Arithmetic Logic Units (ALU), two Load/Store
Units (LSU), and a single Scalar Unit. The ALU and LSU units are organized
into two clusters, each containing a pair of both functional unit (FU) types. The
Scalar Unit executes branch operations, and is also capable of most common
load/store and arithmetic operations. The architecture is illustrated in Fig. 1.
Memory Interface

cluster 1cluster 2

Private Registers (A)Private Registers (A)Load / Store Unit

Load / Store Unit

Public Registers (D)Public Registers (D)Public Registers (D)Public Registers (D)Arithmetic Unit

Arithmetic Unit

Private Registers(AC)

Private Registers(AC)

Program Sequence
Control Unit

Scalar Unit

Private Registers (R)Fig. 1. The PAC DSP Architecture

The registers of PAC are highly partitioned and distributed. The rationale ofthis design is to avoid complete connections to all functional units, thus lowering
register file port counts. This is to avoid the large area, slow access speed, andhigh power consumption of a fully connected unified register file, although at
the expense of an irregular architecture.
Examining PAC’s registers, the A and AC register files are private registers,
directly attached to and only accessible by each LSU and ALU respectively.
The R-register file is private to the Scalar Unit. There are four D-register files,
partitioned among the two clusters. Each of the D-register files have only 3 readports and 2 write ports (3R/2W). Among them, 1R/1W are dedicated to the
Scalar Unit, leaving only 2R/1W for the cluster FUs to use. The remaining set
of 2R/1W ports are not enough to connect to both cluster FUs simultaneously.
Instead, they are switched between the LSU/ALU: during each cycle, the accessports of each of the two D-register files (in a single cluster) may be connected to
the LSU or ALU, but not both. This means that access of the two D-register
files are mutually-exclusive for each FU, and each LSU/ALU can access only oneof them during each cycle. The designers of PAC called this a ‘ping-pong register
file’ design, presumably due to the back-and-forth style of register file access.

These port access restrictions makes operand access in the PAC architecture
resource dependent. This makes instruction scheduling and register assignment
inherently inseparable. For example, the short code sequence:
mov TN1, 1
mov TN2, 2
Two move operations that assign a constant to a virtual register: they can only
be scheduled in parallel if TN1 and TN2 are assigned registers from different
D-register files; if both are assigned to the same D-register file, they can only bescheduled and issued sequentially. We see parallelism restricted by the ping-pongregister in this example.
Adding another operation, the example becomes more complicated. The third
add instruction accesses TN1 and TN2, thus they must be simultaneously accessible by the add operation to be valid.
mov TN1, 1
mov TN2, 2
add TN3, TN1, TN2
As mentioned above, an operation cannot access both D-register files in thesame cycle. As shown in Fig. 2, a copy operation must be inserted to transfer
TN1 or TN2 to another register file, to generate valid code. This example used
an additional copy with no gain in performance
M-UnitTN1, TN2 both assigned to
one D register bank
mov TN1, 1
mov TN2, 2
add TN3, TN1, TN2
TN1, TN2 assigned todifferent D register banks

I-Unitmov D1, 1

2 cycles to execute the first2 instructions, and 1 cycle toexecute the last instruction

mov D2, 2
add D3, D1, D2

M-UnitI-Unitmov D1, 1

mov D8, 2

mov A1, D8

1 cycle to execute the first2 instructions, but 1
additional instruction
before the last instruction

add D3, D1, A1

Fig. 2. An illustration of interference caused by ping-pong register files

Figure 3 shows example of how cross cluster communication works: thecurrent version of PAC requires explicit cross-cluster copy operations to transfer
data between clusters. Cross cluster data transfer is a high latency operation
requiring many cycles to complete, and can hinder performance if not used withrespect to the overall schedule.

3

Compiling for the PAC Architecture

The design of PAC as an instruction set has made it a hard fit into contemporary
compiler target machine models, affecting our development of its compiler. The

Vector Dot Product

B-UnitX = ( A, B )Y = (7,8)
Z = 6 + X •Y
mov TN1, 6
mov TN2, .A
lw TN3, [TN2]
mov TN4, 7
mul TN5, TN3, TN4
add TN6, TN1, TN5
mov TN7, .B
lw TN8, [TN7]
mov TN9, 8
mul TN10, TN8, TN9
add TN11, TN6, TN10
mov TN12, .Z
sw TN11, [TN12]

M-Unitmov A0, .A
lw D0, [A0]copy D3, D18

mov A1, .Z
add D4, D2, D3
sw D4, [A1]

I-Unitmov AC0, 6
mov AC1, 7
mul D1, D0, AC1
add D2, AC0, D1

M-Unitmov A8, .B
lw D17, [A8]I-Unitmov AC8, 8
mul D18, D17, AC8

Exploiting Parallelism in Two Clusters as Usual
Utilizing Ping-pong Registers (1 more instruction, but
may turn-off 1 I-Unit)
mov R0, 6
copy D1, R0
copy D8, D17

mov A0, .A
lw D0, [A0]
mov A1, .Z
add A2, D1, D2
add D10, A2, D9
sw D10, [A1]

mov AC0, 7
mov AC1, 8
mul D2, D0, AC0
mul D9, D8, AC1

mov A8, .B
lw D17, [A8]Fig. 3. An example of scheduling operations across clusters

porting of the main ORC infrastructure involved filling in many target machine
information fields, and writing code expansion procedures for WHIRL-to-CG
translation. Much of the machine level transformations, however, required rollingout our own methods. This section will describe some of our work in generatingcode for PAC.
3.1

Allocation of Operand Storage

The clustered design and ping-pong register files in PAC, implies the conceptof scheduling has to be extended from functional units, to resources guarding
access of operand storage. The access port restriction of the ping-pong registers
is an example.
Our current method, is a scheduling pass that simultaneously optimizes the
instruction sequencing and resource assignment by simulated annealing (SA).
The design originates from Leupers’ work [9] and our initial implementation [6],using a combined instruction scheduling/register file assignment algorithm toiteratively obtain better results.
Leupers’ algorithm operates by first generating a random bi-partitioning of
the operations; a list scheduler (LS) then schedules the partitioned instructions,inserting/managing cross cluster communications along the way. The LS thenreturns the obtained schedule length as the ‘energy’ value used in a simulated
annealing optimization process, representing an evaluation of the current partitioning state. This process is repeatedly invoked, and in each iteration, depending on whether improvement is gained or not, the random change may beretained or discarded. Iteration continues until the energy/evaluation falls undersome threshold, where we are confident that the obtained optimization state isof sufficient quality.
To adapt this SA method for PAC we need a change in the formulation of
optimized state: instead of a partitioning of operations, we optimize a register
file assignment of the virtual registers. Figure 4 shows the high-level simulated
annealing control. It iteratively runs the scheduler, which does fine-grain sequencing of operations, and returns an evaluation of the current optimization
state. Currently, the evaluation consists of just the length of the schedule, as inCombined Instruction Scheduling and Register File Assignment
by Simulated Annealing
Input: n operations to be scheduled
Output: Schedule of the n instructions and a register file assignment (RFA) map:
V R: set of all virtual registers, RF : set of register files
RF A map = {(v1 , f1 ), (v2 , f2 ), ...} vi ∈ V R, fi ∈ RF
1. Choose a schematic register file placement(e.g. 1 cluster, 2 clusters, ...).
2. Make initial register file assignments: randomly assign each
virtual register to any of the wanted register files, and record in RF A map.
3. Given RF A map, run PAC Scheduler,and set sched len to the computed total schedule length in cycles.
4. Set initial values for:threshold: threshold value for the simulated annealing process.
energy: initial energy, larger than threshold.
p test: a probability test value p test (0 < p test < 1).
5. Repeat the following steps while energy > threshold:
5a. Make change in RF A map:
randomly choose a virtual register, and assign it to a different register file.
optionally change the schematic register file placement.
5b. With the new RFA assignment change, run PAC Scheduler again,
and set new sched len to the new count of total schedule length.
5c. Adjust energy, sched len, and RF A map by the following rules:
If new sched len < sched len thendecrease energy, set sched len to new sched len,and keep the new RFA changes made in step 5a.
If new sched len ≥ sched len, get random number 0 ≤ R ≤ 1:
If R > p test thendecrease energy, set sched len to new sched len,and keep the changes made in step 5a.
If R ≤ p test thenincrease energy and revert changes made in step 5a.
6. Optionally choose another schematic register file placement,
and repeat steps 2–5 to select the better results.
7. Retain the final schedule and RF A map as the output results.
Fig. 4. The high-level simulated annealing algorithm

The PAC Scheduler Algorithm
Input: ReadyList of operations to be scheduled
RF A map, in the form of a function RegisterF ile : V R → RF
Output: Schedule of the n instructions, and the schedule length
While ReadyList is not empty:
Select operation Op from ReadyList
Find earliest cycle Cycle we can schedule Op
While Op is not scheduled:
Examine available resources in Cycle, and:For each register operand oi of Op:
If no resources available to access RegisterF ile(oi):Enumerate possible copy sequences to transfer oi to an accessible register fileFor each copy sequence cpseq
If cpseq is schedulable in prior cycles:
F easible(cpseq) = true
If for each register operand oi of Op we have resources to access RegisterF ile(oi),or we have some c such that F easible(c):Schedule Op into Cycle, advance ReadyList
Break from inner loop
else
Increment Cycle
Return length of scheduleFig. 5. The scheduler/evaluation algorithm

Leupers’ algorithm. We are currently looking at incorporating other statistics(e.g. register pressure, number of inserted copies) as part of the evaluation. The
assignment of register files will improve progressively throughout the SA iterations, with respect to the evaluation function. A final register allocator is thenrun to allocate and assign hardware registers, which is guided by the result register file assignments (RF A map). Fig. 5 illustrates the details of the scheduler
algorithm.
3.2

Peephole Optimizations for PAC

The Extended Block Optimizer (EBO) is a collection of peephole optimization
passes performed at the scope of extended basic blocks on the low-level machine
instruction IR in ORC. Our work on EBO not only refines existing optimizations, but also intend to utilize PAC’s DSP-specific features. Table 1 shows acomparison of EBO in the original ORC for Itanium, and our PAC port of ORC.
Table 1. Comparison of EBO collections
EBO optimization

ORC for
IA64

PAC DSP
compiler

×
×
×
×
×
×
×
-

×
×
×
×
×
×
×
×

Forward Propagation
Common Subexpression Elimination (CSE)
Constant Folding
Dead Code Elimination (DCE)
Resolve Conditional Branch
Condition Redundant
Merge Memory Offset
Compound Operation Conversion
Subword Calculation
Dual Operation

Some of the optimizations, specifically constant folding and DCE, are lessaffected by the restrictions of PAC. But others, when applied after register allocation, such as forward propagation and CSE which modify the operationreferenced operands (TNs) may produce invalid code due to register access restrictions.
Original code sequence
1: TN186(d1) <- copy_m TN185(a1)2: TN187(d9) <- copy_m TN186(d1)3: TN188(d8) <- addi_i TN187(d9) 0x4
After propagation
TN188(d8) <- addi_i TN185(a1) 0x4 ;An example above illustrates a typical copy propagation: The value from TN185(a1)is transferred to TN187(d9) in lines 1 and 2, so TN185(a1) should be able topropagate to the reference of TN187(d9) in line 3, leaving lines 1 and 2 as redundant code that can be eliminated. However, it is invalid under PAC’s architectural restrictions; the operation code addi i is an I-unit (ALU) instruction whose
operand must be in the AC- or D-register files. a1 is not accessible by addi i under
any conditions, and thus not valid code. In order to prevent such errors, we should
utilize the register file assignment map, mentioned in the last section, to guard
against invalid code transformations. We are also working on optimizations thatmakes use of PAC’s more sophisticated operations: multiply-accumulate, doubleword load/store, vector operations, post-increment/decrement addressing, etc.

4Experimental Results

Our experiments were done with the DSPstone benchmark suite [10]. Since the
PAC DSP compiler is still in progress, we have only evaluated some stable optimization combinations to obtain an early assessment of the effectiveness of ourwork. All benchmark programs are compiled with three types of option sets: thetraditional register allocation (TRA), TRA with LNO and EBO (LNO+EBO),
and register allocation with simulated annealing scheduling (SARA). TRA refers
to a modification of the original ORC register allocator that assumes full general purpose registers, with a post-process pass that forces copy operations togenerate valid code. It is treated as the base reference in our comparison.
3
2.5

Traditional
RA

Speedup

2
1.5
1
0.5

Traditional
RA + EBO +
LNO
SA RA

bi
qu
ad
bi _onq u e_ f iad se r_N ct
_s ionectio
nsreco al_ lms
m upplex dat
_u e
pd
at
e
m
n_
at
rix
co
1
m
pl ma
ex tri
_u x2
pd
at
e
fir s
2
di
co
m
m
pl ma
ex t 1xn_ _m 3re ultal_ ipu ly
do pdat _ t espr
co odu
nv ct
ol
ut
io
n

0

Fig. 6. Comparison of speedups under various optimization options

Fig. 6 shows and compares the speedup of the benchmarks with option sets
LNO+EBO and SARA, using TRA as the baseline. As shown in Fig. 6, theperformance gains vary widely across different benchmarks with average speedupof 1.78 for LNO+EBO and 1.58 for SARA.
Although the LNO+EBO+SARA combination is not yet stable enough for
full testing, the current results show that our methods of scheduling/allocation,code optimizations, and integration of the LNO phase could yield substantial
improvement in the generated code. Also, the simulated annealing process gives
a potentially exhaustive exploration on how the register usage affects PAC, investigating architectural parameters. Currently, there is a restriction that data
dependencies across different functional units takes 3 cycles, due to lack of bypass
paths between FUs. This causes significant restrictions in utilizing all functional
units, causing some of the benchmarks, such as biquad one section, less affectedby our optimizations. We should note that these test results have all been used as
feedback for the DSP design team, and we expect an enhanced next generation
PAC to improve on these deficiencies.

5

Conclusion

We have presented our compiler development for PAC, a new VLIW DSP processor which features a clustered design and complex, partitioned register files.
We have described methods of code generation for PAC and demonstrated their
viability through several preliminary experiments which were done with the PAC
DSP prototype. We also note that many deficiencies of the first generation PAC
architecture were revealed by our evaluation and we are currently referring to theexperiences and reforming the development of compilers for the next generationof PAC DSP architecture, which will further extend our current work.

References
1. Roy Ju, Sun Chan, and Chengyong Wu: Open Research Compiler for the Itanium
Family. Tutorial at the 34th Annual Int’l Symposium on Microarchitecture, Dec.
2001
2. Tay-Jyi Lin, Chen-Chia Lee, Chih-Wei Liu, and Chein-Wei Jen: A Novel Register
Organization for VLIW Digital Signal Processors. Proceedings of 2005 IEEE
International Symposium on VLSI Design, Automation, and Test, pages 335–
338, 2005
3. David Chang and Max Baron: Taiwan’s Roadmap to Leadership in Design. Microprocessor Report, In-Stat/MDR, Dec. 2004.
http://www.mdronline.com/mpr/archive/mpr 2004.html
4. Tay-Jyi Lin, Chin-Chi Chang. Chen-Chia Lee, and Chein-Wei Jen: An Efficient
VLIW DSP Architecture for Baseband Processing. Proceedings of the 21th International Conference on Computer Design, 2003
5. Tay-Jyi Lin, Chie-Min Chao, Chia-Hsien Liu, Pi-Chen Hsiao, Shin-Kai Chen,
Li-Chun Lin, Chih-Wei Liu, Chein-Wei Jen: Computer architecture: A unified
processor architecture for RISC & VLIW DSP. Proceedings of the 15th ACM
Great Lakes symposium on VLSI, April 2005
6. Cheng-Wei Chen, Chung-Lin Tang, Yung-Chia Lin, and Jenq-Kuen Lee:
ORC2DSP: Compiler Infrastructure Supports for VLIW DSP Processors. Proceedings of 2005 IEEE International Symposium on VLSI Design, Automation,
and Test, pages 224-227, 2005
7. OMAP5910 Dual Core Processor - Technical Reference Manual, Texas Instruments, Jan, 2003.
8. S. Rixner, W. J. Dally, B. Khailany, P. Mattson, U. J. Kapasi, and J. D. Owens:
Register organization for media processing. International Symposium on High
Performance Computer Architecture (HPCA), pp.375-386, 2000
9. R. Leupers: Instruction scheduling for clustered VLIW DSPs. In Proc. Int’l Conference on Parallel Architecture and Compilation Techniques, pages 291–300,
Oct. 2000
10. V. Zivojnovic, J. Martinez, C. Schläger and H. Meyr: DSPstone: A DSP-Oriented
Benchmarking Methodology. Proc. of ICSPAT, Dallas, 1994