VLDP Multipath Execution: Mechanism and Evaluation
Shengying Li,†† Naoya Hattori, † Yuichiro Ajima,††
Shuichi Sakai† and Hidehiko Tanaka†
This paper studies and explores cost-eﬀective execution mechanism for VLDP: a new microprocessor architecture, which performs multipath execution on a large number of execution
units with distributed registers. Special attention is payed to current development on theinterconnection network for distributed register communication. Trace-driven simulations are
performed to quantitatively evaluate the execution mechanism.

nection network and quantitatively evaluates
the execution mechanism.
The next section focuses on the execution
mechanism to exploit the parallelism both ina single EU and among multiple EUs. We
make an inquiry into to the issues of data structure, distributed registers and instruction window size. Section 3 debates the on-chip interconnection network. Moreover, related researchthat addresses speculative execution in diﬀerent
approaches is described in Section 4, and ﬁnallythe summary can be seen in Section 5.

1. Introduction
A lot of researches have been made in thearea of superscalar, which focus on exploiting
Instruction-Level Parallelism(ILP). An important point is whether there is enough parallelism to exploit. S.Jourdan [9] stated this problem that with inﬁnite issue size and instruction
window size of 256, instruction per cycle(IPC)
could reach 10. Considering usual IPC from 1
to 2 in current even state-of-the-art microprocessor, there is still large space to extend the
ILP by scaling the issue width and implementing very large instruction window.
However, the performance of processor is limited by the branch misprediction penalty. Oncea branch prediction missed, it takes many cycles
before the program recovers the right branchpath. One approach, multipath speculative execution, helps to solve this problem.
Our Very Large Data Path(VLDP) architecture is a novel microprocessor combining wide
instruction issue in large instruction window
and multipath speculative execution together toheavily exploit the instruction level parallelism.
We provide 16 on-chip execution units(EU)with register ﬁles distributed in them and makeresearch on the method for fast communication among them. Each EU performs the wideissue out-of-order superscalar policy. Multipath speculative execution on the whole multiEU implements the huge instruction window aslarge as around 200.
VLDP is constructed by control section [2],execution section [1] and memory section [3].
Former research on execution mechanism of
VLDP is presented in detail by Y.Ajima [1].
This paper further describes the current development on register communication via intercon-

2. Execution mechanism
2.1 Introduction
VLDP performs a multipath execution modelto overcome mis-speculation penalties by simultaneously processing instructions from both thetaken and not-taken out-comes of a branch. Because other paths after additional branches arelikely to be encountered before the ﬁrst branch
is resolved, speculative execution will lead more
instructions in ﬂight at the same time. Thatis, more additional functional units, registers,cache ports and so on are needed. Our VLDP
compacts maximum 32 instructions into data
structure unit , called instruction block(IB).
The large number of functional units are clustered into execution units(EU), the register ﬁles
which are usually centralized in current microprocessor are distributed into EUs and theload/store instructions are specially managed
by memory section.
2.1.1 Data structure
Execution model of VLDP is shown in ﬁgure 1. Fetch and decode are done sequentiallyat the speed of 1 IB per cycle. Then the decoded IB is allocated to one free EU according
to the arrangement of EU management unit.
The IB will not retire from the EU until all
instructions in it complete executing. Register communication among EUs and memory ac-† Graduate School of Information Science and Technology, The University of Tokyo†† Graduate School of Engineering, The University of
Tokyo

1

i0

i31
0 1

One IBIB0

D Decode 1 IB / cycle(i0~i31)

EU15

FUs FUs

FUs

2

F D E

F Fetch 1 IB / cycle

EU0 EU1

2.1.2 Distributed register files• Objective
To support the multipath speculative execution, VLDP executes multiple IBs on EUs
in parallel. Further, every EU performs a
multi-issue superscalar execution and provides enough functional units to exploit the
ILP of program. However, as described by
S. Palacharla [10], large instruction issue
size will cause comparably complexity andexpensive register rename logic for sharedregister ﬁles. In order to avoid the highcost on it, VLDP distributes register ﬁlesinto separate EUs and manages registers byregister synchronous maps in IB.
• Organization
VLDP provides 64 logical registers with 64bit, shared by both integer and ﬂoating
point arithmetic processing. Physical registers are distributed in 16 EUs. In every
EU, there are 8 register banks with 32 register entries, that is, 256 physical registers
in each EU and overall 4096 physical registers.
• Register communication
Instead of register rename logic, result of
instruction in IB is written into ﬁxed register entry of allocated register bank for the
IB directly on the EU. So, VLDP only needto communicate for register reading, whenan IB need values from other EUs. Although the distributed registers avoid thelarge cost of register rename logic for concentrated register ﬁle, it brings additional
cost of register communication.
2.1.3 Instruction window
Instruction window size refers to all the instructions simultaneously held in the execution
pipeline. Beneﬁt from low cost of register accessto distributed register ﬁles, VLDP introduces
as large as 16 EUs to process maximum up to
512 instructions in parallel in order to support
the multipath speculative execution. Because
new IB can not enter an EU until old IB retires
from it, the real instruction window size in execution is less than the maximum value, whichis examined in simulation.
2.2 Evaluation
2.2.1 Simulation environment• Simulator
We developed cycle-level multi-EU superscalar simulator on the data structure of IB.
This simulator achieves the most aggressive instruction issue policy inside of an EU:
out-of-order issue using reservation stationand forwarding mechanism. Further it per-

time
15

E

IB1
(i32~i63)

E

E
F D E
E

E
E
F

IB15

Interconnection network(a) Data path(b) Execution pipeline

Fig. 1 Execution model of VLDP: (a) Data path; (b)Execution pipeline

Instruction processing from head inst

Inst 0

BB0

7

15

BB1

BP(Break Point) 0

23

BB2
BP 1

31

BB3
BP 2

BP3

Instruction Block(IB)Fig. 2 Instruction block(IB) of VLDP, containing
maximum 32 instructions in 4 basic blocks continuously at the same control ﬂow. Branch instruction can only be in Break Point.

cesses are implemented via an interconnection
network. Since multiple EUs execute IBs simultaneously, execution is performed in parallel.
To take advantage of instruction parallelism
and improve the throughput of instructions
per cycle, VLDP processes the instruction
block(IB) as the basic unit for execution. The
IB is constructed with instructions up to 4 continuous basic blocks on the same control ﬂow
statically produced by compiler, and contains
opcode, operands, and data synchronous information for each instruction.
As shown in ﬁgure 2, an IB has ﬁxed 32 instruction slots, which is divided into 4 Basic
Block(BB) ﬁelds with 8 instruction slots in each
BB. If it happens that there are more than 8
instructions in one basic block in original program, they are scattered into multiple BBs.
The branch instruction can only appear at theend of the BB ﬁeld, which is called Break Point.
Each IB is always processed from the head instruction. Depending on the result of branch,
the real control ﬂow may divert from the pathof the IB at a certain Break Point. Instructions
after the break point then will be cancelled dynamically during execution. By fetching IBs in
multipath [4] and processing multi-IB in parallel, VLDP executes instructions from multiple
paths simultaneously.

2

Table 1 Benchmark summary, including the number of IBs and instructions
executed on the seven SpecInt 95 benchmarks, in the unit of million(M).
go m88ksim
compress
li
ijpeg
perl
vortex
IB
9.1M
9.6M
9.1M
18.3M
8.4M
12.7M
11.2M
Inst 165.0M
151.5M
174.0M 255.5M 211.0M 206.3M 210.3M
Table 2 Instruction window size of VLDP, referring to the instruction
number simultaneously active in the execution pipeline.
go m88ksim compressli
ijpeg
perl vortex
198.4
201.6
192.0 139.2 304.0 188.8
148.8

forms the multipath execution across EUs:
IBs in poly data paths can speculatively execute on multiple EUs simultaneously. In
order to focus on investigation of the performance purely on execution mechanism,
we assume:– ideal instruction-fetch mechanism: one
IB per cycle;– perfect cache;– perfect branch predictor;– wide issue size of 32 in an EU;– 1 cycle for non-memory instruction execution and 2 cycles for memory instruction execution.
• Benchmarks
In this paper, we evaluate our scheme using
seven applications in the SPECint95 benchmark summarized in Table 1.
2.2.2 Result and discussion

IPC

Relative performance of 1 EU and 16 EUs

gom88k comp

li

ijpeg

perl

vort

1 EU average instruction window size of 12
16 EU average instruction window size of 200

Fig. 4 Performance impact of instruction window size,
showing instruction window size of around 200
speeds up 1.8-3.0 to that of around 12

EU can not accept new instructions until
the IB on it retired or cancelled, the sizeof instruction window is still as large asaround 200 in the simulations. Figure 4
veriﬁes the performance(IPC) impact of the
instruction window size. Compared to IPC
on single EU with instruction window sizearound 12, VLDP speeds up from 1.8 to 3.0
on the benchmarks.

Av e rage instructions pe r IB

30.0
25.0
20.0
15.0
10.0
5.0
0.0

4.00
IPC

rt

eg

rl

store

5.00

av

load

vo

logic

pe

li

i jp

eg

k

m

88

co

m

int_add

p

6.00

go

num ber of instructions

6.0
5.0
4.0
3.0
2.0
1.0
0.0

branch

3.00
2.00
1.00

Fig. 3 Instructions per IB for benchmarks, showing
the number of non-nop instruction per IB.

Simulator Configuration of Functional Unit:
Simple Integer Unit__Integer Multiply Unit__FPU

0.00
1_1_2

go
ijpeg

• Instruction block(IB)Upon the deﬁnition of IB in VLDP, we
examine its organization on benchmarks,
summarized in ﬁgure 3. As it indicates, average non-nop instructions per IB is around
19, which is heavily limited by the return
instruction.
• Instruction window size
Table 2 shows the investigation result on
instruction window size. The upper boundof 512 for VLDP appears when 16 IBs with
32 instructions enter EUs. Although the

2_1_2

m88ksim
perl

3_1_2

4_1_2

compress
vortexinfiniteliaverageFig. 5 Functional unit conﬁguration• Functional unit conﬁguration
On the basis of data structure, IB, we investigated the performance of IPC for alternative ﬁxed numbers of functional units
in EUs, and compared with that for inﬁnite number of functional units. To support ﬂoating point applications, we assume3

two ﬂoating point units in our simulators.
Figure 5 indicates that conﬁguration of 3
simple integer units, 1 integer multiply unit
and 2 ﬂoating point units in an EU is a comparably eﬀective conﬁguration for VLDP.

EUs.
Figure 6-8 illustrate the frequency, traﬃcand EU relationship for distributed register communication. Focusing on one EU,
HS(d) and HS(s) gives the information at
the cycle when the EU is the destination or
the source for hot-spot contention respectively; R(d) and R(s) shows information
when the EU receives or sends as destination or source respectively in regular communication; EU traf includes all the communication information for an EU.
The traﬃc for regular communication on an
EU is around 1.5 registers per cycle withfrequency of 4% among the simulation cycles. At the same time, it is clear thatthe traﬃc for a hot EU is not high, about
2.5 from 2 other EUs with frequency of 1%
among the whole simulation time. Part of
the reason is the instruction parallelism limited by the data dependence among the IBs
in the same data path. Another reason isthat 100% branch prediction accuracy in
our current simulator lessens the communication among EUs. We will examine theimpact of the hot-spot contention on performance in the latter section.
In addition, simulation result veriﬁes that
there is no obvious diﬀerence in EUs for register communication.

3. Interconnection network

Frequency per EU

3.1 Introduction
In VLDP, via the interconnection network
on-chip, separate EU may communicate either
through the shared memory, or through registers. Since the data transfered among EUs neednot to leave the chip, communication is fast.
The on-chip cache and shared memory allow
quantities of simultaneous accesses [3]. VLDP
also implements register communication amongEUs, allowing an EU to read register values inother EUs. This section focus on the registercommunication among EUs.
Because results for instructions in an IB are
written into local registers directly on the EU,
VLDP only need transfer register value for read.
To perform fast communication, we perform theregister communication on the register-readymechanism driven by sending-side EU. Oncevalues in the registers are valid and interconnection network is free, they are transfered tothe destination EUs. When data arrives from aremote register write, any operation waiting on
the register is allowed to issue.
Register request information for an IB is produced by decode unit and broadcasted to all
related EUs that hold the needed physical register. When the IB is allocated into an EU,
through interconnection network, the requested
register values are sent from other EUs, if ready.
It is the time that may be a communication
burst for an EU attempts to be accessed by multiple other EUs simultaneously. Here, such an
EU is called a hot EU and the phenomenon iscalled hot-spot contention. Register communication at any other time is called regular communication.
3.2 Evaluation• Simulation environment
This study is made according to the assumptions outlined in section 2.2.1. Further, when allocating a new IB into freeEU, the priority of EUs decrease as the EU
number increases from 0 to 15. That is, EU
0 features the highest priority while EU 15
has the lowest one.
• Analysis of Register Communication
Before conversion to the investigation oninterconnection network, we ﬁrst examine
the register communication traﬃc among

0.08
0.07
0.06
0.05
0.04
0.03
0.02
0.01
0.00
go

HS(s) freq
R(d) freq

m88k comp

li

jpeg

HS(d)
freq
Benchmarks
EU traf

perl

vort

aveg

R (s) freq
EU request

Fig. 6 Register communication frequency among EUs.
Cycles for an EU to perform regular communication are 4 times as many as those for hot-spot
contention.

• Requirement of register communication fordata network
In this section, we examine VLDP requirement to interconnection network on register communication. Figure 9 shows theheavy performance impact of communication latency with inﬁnite bandwidth. IPC
increases 30% when latency decreases from
4 cycles to 1 cycle. Figure 10 summarized the impact of communication band-

4

4.00

R(s) traf

4

1eu traf

jp
e

li

go
m
88
k
co
m
p

rt
vo

R(d) traf

av
eg

g

HS(s)traf

pe
rl

ijp
e

li

k

co

HS(d) traf

m
p

0.00
go

1.00

0.00

3

rt
av
eg

2.00

1.00

pe
rl

2.00

3.00

vo

3.00

g

IPC

4.00

m
88

number of registe for 1 EU

5.00
5.00

2

1

Fig. 9 Application IPC as a function of communication latency with inﬁnite wide bandwidth.

Fig. 7 Register communication traﬃc among EUs. A
hot EU receives average 2.5 registers per cycle,
which is larger than that of 1.5 per cycle for aregular EU.

6.00
5.00

0.00

HS(d) s_eurtvo

Crossbar

av
eg

rt
vo

g

Crossbar_3_Rportcomplete_commu

av
eg

g

R(d) s_eu

pe
rl

li

ijp
e

k

m
p
co

m
88

go

1 bus

pe
rl

go

EU numbers

0.50

li

0.00

1.00

jp
e

1.00

1.50

k

2.00

m
p

3.00
2.00

co

2.50

m
88

IPC

4.00
3.00

Fig. 10 Application IPC as a function of communication bandwidth with latency zero.

R(s) d_eu

IPC

Fig. 8 Communication relationship among EUs.
HS(d)s eu shows that a hot EU as communication destination receives from average 2 EUs;
R(d) s eu or R(s) d eu indicates that an EU inregular communication receives from or send toaround 1 EU.

width with ideal latency zero on performance IPC. Here, Crossbar means the point
to point crossbar. To examine the inﬂuenceof the hot-spot contention, in the Crossbar 3 Rport, we added 2 receive ports especially for the hot EU. No obvious performance improvement can be seen while thebandwidth increases. Also, hot-spot contention has low impact on performance. So,
we focus on small latency interconnection
network in future research.
• Analysis of 3 typical data networks
Considering the latency and hardware costof diﬀerent kind of the data network, we examine the following typical data networks.
– Simple Bus
Its advantage is low cost. However, latency for communication on bus is usually 3 cycles. Furthermore, bandwidthis limited to 1 messages per cycle.
– Multistage Interconnection Network
Cost of multistage interconnection network is more than bus but less than

4.5
4.0
3.5
3.0
2.5
2.0
1.5
1.0
0.5
0.0
go

m88k compBus with latency 3

li

ijpeg

perl

vort

aveg

Crossbar with latency 1

Fig. 11 Performance comparison with bus and crossbar. Comparing to crossbar with latency of 1,
bus with latency of 3 decreases IPC of 26%.

crossbar. By 2x2 crossbar, there are atleast 4-cycle latency for register communication among 16 EUs. Further,message contention will cause high latency.
– Crossbar
16x16 Crossbar is the most expensive
data network among the 3 data networks, but with lowest latency. So wechoose the crossbar as our baseline performance for evaluation of interconnection network in VLDP.
Figure 11 demonstrates the performance
diﬀerence among bus and crossbar. Here,5the simulator did not implement pipeline
for bus communication. With larger latency, performance of bus is 26% less thanthat of crossbar.
3.3 Future work
Upon the examination above, we consider
to use multi-bus interconnection network withlinks shown in ﬁgure 12. The bus and link network combines the simple low cost bus and thelow latency link together. As described in thesection 3.2, the IB allocation mechanism in our
simulator puts the nearest IBs in the same path
into the close near two EUs. Since the registercommunication happens frequently between thenearest two IBs in the same path, communication among the close two EUs is expected tobe high. So we add low latency links among
the near EUs like illustrated in ﬁgure 12. Detailed research on it will be held in future andwe intend to ﬁnd a cost-eﬀective interconnection network for VLDP.

IB
EU0

IB
EU1

IB
EU2

IB
EU15

Interconnection Network

Fig. 12 Interconnection network with link amongEUs.

4. Related research
Numerous researches have made on multipath speculative execution to reduce the misprediction cost in diﬀerent approaches. Selective eager execution [5] executed both paths
after branches in an extension of an aggressive superscalar, out-of-order architecture. Ypipe [6] duplicated the early pipeline stages toeliminate the penalty of branch misprediction.
TME [7] attempts to combines simultaneous
multithreading(SMT [8]) with multipath execution.
5. Summary
This paper introduced the execution mechanism of Very Large Data Path(VLDP) architecture. We investigated the basic data structure of IB, the large instruction window sizeand functional unit conﬁguration for VLDP.
Furthermore, we present current development
in on-chip interconnection network and ana-lyzed requirement for distributed register communication. Upon the simulations on several
SpecInt95 benchmarks, quantitative evaluationon performance of IPC shows that comparing
to a single EU, the large instruction windowof 16 EUs in VLDP speeds up to 1.8 to 3.0.
Performance impacts on interconnection network of several basic data network models arealso examined. Considering the heavy inﬂuenceof latency and the hardware cost, we intend
to extend our research on multi-bus with links
among EUs in the future.
Acknowledgments
This work is supported in part by scientiﬁc
research founding in Ministry of Education,
Japan, (foundation research(B) NO.11480066)
and Semiconductor Academic Research Center(STARC).
References[1] 安島 雄一郎, 辻 秀典, 坂井 修一, 田中 英彦, 大規
模データパス アーキテクチャの実行機構, 情報処
理学会研究報告 2000-ARC-139, pp.55-60, 2000
[2] 辻 秀典, 安島 雄一郎, 坂井 修一, 田中 英彦, 大
規模データパス アーキテクチャの提案, 情報処理学会研究報告 2000-ARC-139, pp.49-54, 2000
[3] 入江 英嗣, 安島 雄一郎, 辻 秀典, 坂井 修一, 田
中 英彦, 大規模データパス アーキテクチャに適したロードストアユニット構成, 情報処理学会研究報告 2000-ARC-139, pp.43-48, 2000
[4] 塚本 泰通, 辻 秀典, 安島 雄一郎, 坂井 修一, 田
中 英彦, 大規模データパス アーキテクチャにおける命令ブロックの構成の検討, 情報処理学会研究報告 2000-ARC-139, pp.61-66, 2000
[5] A. Klauser, A. Parthankar, D. Grunward, Selective Eager Execution on the PolyPath Architecture, 25th Intl. Symposium on Computer
Architecture(ISCA), pages 122-131, 1998
[6] M. J. Knieser, C. A. Papachristou, Y-Pipe:
A Conditional Branching Scheme Without
Pipeline Delays, 25th Intl. Conf. on Microarchitecture, pages 125-128, 1992
[7] S. Wallace, B. Calder, and D. Tullsen,
Threaded Multiple Path Execution, 25th Intl.
Symposium on Computer Architecture, 1998
[8] D. M. Tullsen, S. J. Eggers and H. M. Levy,
Simultaneous Multithreading: Maximizing OnChip Parallelism, Proc. 22nd Annual International Symposium on Computer Architecture,pages 392-403, 1995
[9] S. Jourdan, P. Sainrat, D. Litaize, Exploring
Conﬁguration of Functional Units in an Outof-Order Superscalar Processor, Proc. 22nd
Annual Intl. Symposium on Computer Architecture, pages 206-218, 1997[10] S. Palacharla, N. P. Jouppi, J. E. Smith,Complexity-Eﬀective Superscalar Processors
Proc. 22nd Annual International Symposiumon Computer Architecture, pages 117-125, 1995