Transcript ppt - UCSD VLSI CAD Laboratory

Minimizing Manufacturing Cost
for Multi-Project Wafer
Multi-Project Wafer Problem and Flow
Abstract
Multi-Project Wafer and
Reticle Cost Optimization
Multi-project wafers combine several designs from different
projects onto one wafer. This approach allows the costs to be
shared among a number of customers. Fabrication of prototypes
can thus be as low as 5% to 10% of the cost of a full wafer run.
Our research considers ways to minimize production costs for
multi-project wafers. The optimization problem can be divided
into four sub-problems: chip assignment, chip placement, reticle
mapping and die sawing. (1) For the chip assignment problem,
we propose a branch-and-bound algorithm to solve the special
case with equal chip sizes. (2) For the chip placement problem,
we use a simulated annealing algorithm to optimize the reticle
area as well as dicing conflicts. (3) We optimize predicted die
yield of reticle shot mapping, taking into considerations a broad
range of parameters that have impacts on die yield. (4) We
propose ILP and NLP formulations and an iterative augment
and search algorithm to find an optimal side-to-side wafer dicing
plan.
Chip Placement Problem
Given:
n chips Ci (i=1…n),
Find: Placement of chips
To Maximize:
Number of X in M (NX)
H
1
2
V
3
4

1

M  2

3
 4
Flow
Problem Statement
Chip assignment decides the set of designs that are packed
on a reticle.
Given:
• A set of designs, with die dimensions and required
production volume for each design
• Maximum reticle area and aspect ratio
• Mask, wafer and lithography cost models
Find:
• A set of collections of designs
• For each collection, a placement of dies on a reticle
• The number of prints needed for each reticle
To satisfy the volume requirement with minimal cost
The design process can be
divided into four steps:
• Chip assignment
• Chip placement
• Shot-map & stepping
• Dicing
Shot-Map and Stepping Problem
Relationship Matrix
• Two chips are in H-Conflict if their horizontal
projections are overlapped and are not identical
• V-Conflict is similarly defined
• Relationship Matrix M is a n X n matrix, in which
• Mi,j=H if Ci ,C j are in H-Conflict
• Mi,j=V if Ci ,C j are in V-Conflict
• Mi,j=X if Ci ,C j are not in H-Conflict or V-Conflict
1
X
2
H
3
V
H
X
V
V
V
X
X
V
H
4 
X 

V 

H 
X 
Problem Statement
Placement of the reticle array on
the multi-project wafer has
significant impact on die yield.
We seek to maximize weighted
die yield, based on yield
probability.
Solution
Reticle placement is optimized
by taking into account many
parameters that impact die yield:
• Scribe lines, notches, flats
• Wafer clamping
• Weights for different designs
• Yield probabilities based on
defect distributions and radial
yield degradation
Q. Wang, X. Xu and A. B. Kahng (Advisor)
Calibrating Achievable Design
I. Mandoiu and A. Zelikovsky
Chip Assignment Problem
Multi-project wafers combine
several designs from different
projects onto one wafer, which
allow customers to share the
expensive cost of a mask set.
Our research considers ways
to minimize production costs
for multi-project wafers.
Multi-Project Wafers
Chip Placement Problem
Annual Review
September 2003
Side-to-side Dicing Problem (I)
Side-to-side Dicing Problem
Optimal Shot-Map
Given:
2
1
• A chip placement on the reticle
• A reticle placement on a wafer
4
3
Find:
rectilinear
tree
augmentation
(MRTA)
problem]
• [Minimum
A set of horizontal
and vertical
cut
lines
[Minimum
rectilinear
tree
augmentation
(MRTA)
problem
[Minimum rectilinear tree augmentation
(MRTA)
problem
Obtained:
1,3
Given
routed
tree
TTininaaManhattan
plane
and
wire
length
To Maximize:
Given
routed
tree
Manhattan
plane
and
wire
Given routed tree T in a Manhattan plane and wirelength
length
• budget
z, whichW,
is the
minimal
number
of
copies
obtained
find
edges
A

E
of
total
length
less
than
W
suc
budget
W,
find
edges
AAEEof
total
length
less
than
W
suc
budget
W,
find
edges
of
total
length
less
than
W
su
across
all
the
chips
that
the
length
ofofremaining
bridges
ininTA
isisminimum
that
the
length
remaining
bridges
TA
Here, a that
copy the
of chip
Ci is obtained
if and only
if:
length
of remaining
bridges
in TA isminimum
minimum
• The four edges of Ci are on the cut lines
• No cut lines pass through the chip Ci
Formulation
Formulation
Formulation
Nx =6
Side-to-side Dicing Problem (II)
Three Approaches
• Integer Linear Programming (ILP)
• Formulate the H-conflict and V-conflict
constraints using linear programming
• Non-linear Programming (NLP)
• Formulate the constraints as a nonlinear
program
• Iterative Augment and Search Algorithm (IASA)
• Choose cutting lines for one row or column at
a time
• Iteratively check and replace cut lines with
new ones as long as the minimal number of
copies across all chips, z, increases
Side-to-side Dicing Problem (III)
Test
Case
# chips
1
NLP-Lingo
LP-CPLEX
IASA
z
CPU(s)
z
CPU(s)
z
CPU(s)
11
18
7
18
6
18
0.1
2
10
25
1
25
8
25
0.0
3
17
7
300
6
3600
10
0.1
4
21
20
11
20
153
20
0.0
5
18
12
300
12
713
12
0.0
6
14
16
246
16
37
16
0.0
7
15
8
300
9
3600
12
0.2
8
16
12
241
12
59
12
0.0
9
14
10
300
9
3600
10
0.0
10
16
7
300
6
36
9
0.2
• Lingo and CPLEX are commercial tools for solving NLP and LP
• Runtime is limited to 300s for Lingo and 3600s for CPLEX
• z is the minimum number of obtained copies across all chips
• Performance of IASA is much better
Conclusion
•
•
•
•
•
•
We have introduced the multi-project wafer problem
The optimization is divided into four steps: chip
assignment, chip placement, reticle placement and
side-to-side dicing
We define an appropriate sub-problem for each step
We give nonlinear programming and linear
programming formulations for the side-to-side dicing
problem
We propose a new heuristic, IASA, with better
performance than commercial NLP/LP solvers
Ongoing work addresses chip placement with
multiple objectives, efficient chip assignment, and
an integrated flow for manufacturing cost reduction