color=black>

Exploring Potential Benefits of 3D FPGA Integration 1
Exploring Potential Benefits of 3D FPGA Integration




ABSTRACT
A new timing-driven partitioning-based placement tool for 3D
FPGA integration is presented. The circuit is first divided into
layers with limited number of inter-layer vias, and then placement is
performed on individual layers, while minimizing the delay of
critical paths. We use our tool, which will be available on the web
for the research community, as a platform for exploring potential
benefits in terms of delay and wire-length that 3D technologies have
to offer for FPGA fabrics. We show that 3D integration results in
wire-length reduction for FPGA designs. However, unlike the ASIC
case, wire-length reduction does not automatically translate to much
smaller circuit delays, unless multi-segment lengths are employed
between layers. Our empirical analysis shows that wire-length can
be reduced by up to 50% (20% on average) using 5 layers. Delay
reductions are estimated to be up to 30% (15% on average) using
the same number of layers.
1. INTRODUCTION
Smaller feature size and increasing transistor counts allow
implementation of more complex and larger designs. However, a
number of new design problems emerge and old problems become
more difficult to solve. For example, global wires dominate the
delay and power budgets of circuits, and signal integrity, IR-drops,
process variations, and high temperature gradients pose new
difficult design problems. Furthermore, shrinking time-to-market
windows and ever-increasing mask costs have reduced profit
margins alarmingly.
In response to mounting problems of the integrated circuit
technology, various research groups have shown renewed interest in
3D IC integration, and a number of successful projects have shown
the viability of the technology [15]-[21]. 3D integration can
significantly reduce wire-lengths (and hence circuit delay), and
boost yield
1
. Furthermore, there has been an inclination towards
employing IP-based design and structured gate arrays (e.g., FPGA
blocks) to partially solve complex signal integrity and noise issues.
3D integration can particularly be useful for FPGA fabrics. It can
address problems pertaining to routing congestion, limited I/O
connections, low resource utilization and long wire delays.
On the standard cell arena, Das et al. recently proposed a
placement and global routing tool as well as a 3D layout editor [13].
The placement algorithm is based on recursive min-cut partitioning
of the circuit represented as a hypergraph and follows the same idea
as in the Capo placer [23]. Interlayer via minimization is sought by
min-cut partitioning for layer assignment. Wire-length minimization
is done by considering aspect ratio during the partitioning. The user
can select either hMetis [25] or PaToH [26] as the partitioning
algorithm. Their global routing algorithm is a concurrent approach
based on the idea in [24]. It was shown that 28% (51%) wire-length

1
True only in technologies that fabricate different layers separately, weed
out the faulty layers from the layer wafers, and only integrate the working
ones. However, wafer stacking technologies have been shown to be more
practical and successful compared to techniques that grow different
layers on top of each other in a single process.
improvement could be obtained with two (five) layers, compared
to [31] (the improvement is only 7% (17%) when inter-layer via
minimization is the main objective). Wire-length reduction of up
to 74% was reported in [33]. Deng and Maly showed using a
placement algorithm based on Capo that the total wire-length can
be reduced by 16% compared to flat placement, when two-layer
integration is used [27]. It is important to note that current
technologies allow for CMP substrate thinning down to about 5-
10
µm, hence allowing for multiple thin active device layers and
interconnect levels be stacked on top of each other, resulting in
short inter-layer vias with small aspect ratios [15].
Even though the idea of 3D integrated circuits is not new, recent
technological advances have made it a viable alternative.
However, there is a lack of efficient 3D CAD tools that can exploit
the potential gains that 3D integration has to offer. Furthermore, a
number of important issues such as heat dissipation, thermal
stress
2
, and physical design considerations remain to be
addressed for some 3D architectures.
There has been some previous work proposing 3D FPGA
architectures. Borrowing ideas from multi-chip module (MCM)
techniques, Alexander et al. proposed to build a 3D FPGA by
stacking together a number of 2D FPGA bare dies [1]. Electrical
contacts between different dies would be made using solder bumps
or vias passing through the die. The number of solder bumps that
can fit on a die determines the width and separation of vertical
channels between FPGA layers. Depreitere et al. proposed using
optical interconnects to construct a multi-layer FPGA [2]. An
straightforward extension of a 2D architecture [6] is found in the
Rothko 3D architecture, which has routing-and-logic blocks
(RLBs) placed in more than one layer [5]. Fine-grained interlayer
connections were added outside each RLB, providing connections
between cells above and below, using a specially designed
technique [8], [9]. An improved version of Rothko architecture
which advocates placing the routing in one layer and logic on
another for more efficient layer utilization appears in [7]. It was
shown that the percentage of routed connections increases with an
increase in the flexibility of switch boxes. Also, computational
density is higher compared to a 2D architecture. Universal switch
blocks for 3D FPGA design were analyzed in [34]. It is important
to point out that all of these works assume that the inter-layer
connectivity is provided by vertical wire segments that connect
each layer to its adjacent layers only.
There has also been previous work on CAD tools for 3D FPGA
integration. Alexander et al. proposed 3D placement and routing
algorithms [3] for their architecture in [1]. Their placement
algorithm is partitioning-based followed by a simulated annealing
based refinement for total interconnect length minimization.
Savings of up to 23% and 14% in total interconnect length at the
placement level and routing level respectively were reported. An
improved version of the placement algorithm appears as Spiffy,
which performs placement and global routing simultaneously [3].

2
There is already previous work addressing thermal issues in physical
design for 3D integration [32]. 2
In the experimental methodology presented in [7], placement was
performed with VPR [10] and routing was performed with a custom
routing tool [12].
In this paper we present a fast placement tool for 3D FPGAs
called TPR (Three dimensional Place and Route). Unlike previous
works on 3D FPGA architecture and CAD tools, we investigate the
effect of 3D integration on delay, in addition to wire-length. We
show that wire-length alone cannot be relied on as a metric for 3D
integration benefits.
Our placement algorithm is partitioning-based, and hence
scalable in the face of explosive growth of design sizes. A circuit is
first partitioned for min-cut minimization into a number of
partitions equal to the number of layers for the 3D integration.
Then, timing-driven partitioning-based placement is performed on
every layer starting with the top layer and continuing downwards.
Allowable bounding box for nets on a particular layer is decided by
the layers above it, to minimize the 3D bounding-boxes of the most
critical nets. Constraints for any given layer are set by the
placement on layers above. The routing algorithm is currently being
imported and adapted for the 3D architecture from the leading
academic placement and routing tool for 2D architectures, VPR
[10]. The main contribution of our work is as follows.
We analyze the potential benefits, which can be obtained by 3D
integration for FPGAs. More specifically, we place circuits onto
3D FPGA architectures and study the variation in circuit delay
and total wire-length compared to their 2D counterparts, under
different 3D arch