USOO8671.

381B1

(12) United States Patent (10) Patent No.: US 8,671,381 B1

Wang et al. (45) Date of Patent: Mar. 11, 2014
(54) SYSTEM FOR OPTIMIZING NUMBER OF (56) References Cited
DES PRODUCED ON AWAFER
U.S. PATENT DOCUMENTS
(71) Applicants: Peidong Wang, Suzhou (CN); Zhijun 6,522,940 B1 2, 2003 Erck
Chen, Suzhou (CN); Zhihong Cheng, 7,033,847 B2 4/2006 Tai
Suzhou (CN): Li Ying, Suzhou (CN) 7,353,077 B2 4/2008 Lin
7,882.481 B2 2/2011 Hempel
8,239,788 B2 8, 2012 Lin
(72) Inventors: Peidong Wang, Suzhou (CN); Zhijun 8,386,981 B1* 2/2013 McGowan et al. ........... T16,122
Chen, Suzhou (CN); Zhihong Cheng, 2004.0128630 A1* 7/2004 Ward et al. ........................ T16.2
Suzhou (CN); Li Ying, Suzhou (CN) 2009/0007028 A1* 1/2009 Hempel ............................ T16.2
* cited by examiner
(73) Assignee: Fr's Semiconductor, Inc., Austin, Primary Examiner — Binh Tat
(74) Attorney, Agent, or Firm — Charles Bergere
(*) Notice: Subject to any disclaimer, the term of this (57) ABSTRACT
patent is extended or adjusted under 35 A system for optimizing the number of dies that can be
U.S.C. 154(b) by 0 days. fabricated on a wafer uses a die number optimization (DNO)
routine to determine a maximum number of dies for a target
(21) Appl. No.: 13/723,207 die area (TDA), and generate an initial result list of die shapes
that have the maximum number of dies for the TDA. Option
(22) Filed: Dec. 21, 2012 ally, a die size optimization (DSO) routine can be executed to
determine a list of die shapes having a maximum die area
corresponding to the maximum number of dies, a first list of
(51) Int. Cl. optimized die shapes having a maximum area utilization
G06F 17/50 (2006.01) (AU) for a decreased TDA, and/or a second list of optimized
(52) U.S. Cl. die shapes having a minimum AU for an increased TDA. A
USPC ........................................... 716/135: 716/134 candidate list (CL) of the various die shapes can be generated,
(58) Field of Classification Search and entries from the CL automatically selected and/or dis
USPC .................................................. 716,132 13s played to indicate proposed wafer layouts.
See application file for complete search history. 24 Claims, 11 Drawing Sheets
U.S. Patent Mar. 11, 2014 Sheet 1 of 11 US 8,671,381 B1

FIG, 1A
U.S. Patent Mar. 11, 2014 Sheet 2 of 11 US 8,671,381 B1

s
t

Eaaaaaaaaaaaaaaaaam
Eii a

NNNN N
N. NY N N
%
2Till:7427727ZZZZZZZZZ
%
NNN
\ N 2
226:::::::::::::::
::::::::::::::::::::
N y (l
NTN ::::::::::::::::::::
:::::::::::::::::::::

NG
N.
HHitti,
1
:::::::::::::::A;ZZ
U.S. Patent Mar. 11, 2014 Sheet 3 of 11 US 8,671,381 B1

Enter input variables including: minimum die width (X) and height
(Y), target aspect ratio, step size, target die area (target),
edge bandwidth (web) and scribe width (ws)
220
Execute die number optimization (DNO) Routine; Checkfirst list of die
shapes and determine which ones result in a maximum number of
dies (Nmax)
230 Maximum number of dies (Na)
Execute Die Size Optimization (DSO) Routine
500
Determine die
shapes) having Determine first Determine Second
maximum die area Optimized die optimized die
shape(s) when shape(s) when
Elsa target die area is target die area is
fixed decreased increased

List of die shape(s) First list of Second list of

having the maximum optimized die optimized die
number of dies shape(s) for a shape(s) for an
(Nma) and the decreased increased
maximum die area target die area target die
(Amax) (Atarget) Sea
240 (target)
Output candidate list
250
Select a result from the candidate list that has the maximum number of
dies (Na) and a desired aspect ratio and die shape
FIG.2
U.S. Patent US 8,671,381 B1
U.S. Patent Mar. 11, 2014 Sheet 6 of 11 US 8,671,381 B1

Opu?D
0,7

ON 097
U.S. Patent Mar. 11, 2014 Sheet 7 of 11 US 8,671,381 B1

information from 210, and the maximum number of

dies (Na) from step 355 of FIG.3
510
Compute a third maximum die width (Xmas") and a
third maximum die height (Ya") when die area is
decreased to a lower limit die area (A)
520
Based on Xmax, Xmin Ymax", Ymin generate a
ESGraps"
525
Compute a number (NI) of dies for a Current die shape
in a third list of die shapes
530
Compute Area Utilization (AU)
Select next
die shape in the AU and the die number increased
third list as
Current die
shape 540
Store Current die area associated with the current
die shape as a second result
550 All
shapes in third list evaluated
560 S
Record first list of optimized die shapes having
maximum.AU for a decreased target die area (Aage)
570
End

FIG, 5
U.S. Patent Mar. 11, 2014 Sheet 8 of 11 US 8,671,381 B1

information from 210, and the maximum number

of dies (Na) from step 355 of FIG. 3, and second
list je shapes from step 420 of FIG. 4
625
Compute a number (Nu) of dies for a current
die shape in a second list of die shapes
630
Compute Area Utilization (AU)
Select next 635 Has
dieSecond
shapelistin the AU decreased
as Current
die shape 640
Store Current die area associated with the
Current die shape as a third result
650 AI
shapes in Second list evaluated
660 YES
Record second list of optimized die shapes having
minimum AU for an increased target die area (target)
670

FIG. 6
U.S. Patent Mar. 11, 2014 Sheet 9 of 11 US 8,671,381 B1

FIG. 8
U.S. Patent Mar. 11, 2014 Sheet 10 of 11 US 8,671,381 B1

086

96

ø»/Ø
U.S. Patent US 8,671,381 B1
 US 8,671,381 B1
1. 2
SYSTEM FOR OPTIMIZING NUMBER OF DETAILED DESCRIPTION
DES PRODUCED ON AWAFER
The following detailed description is merely exemplary in
BACKGROUND OF THE INVENTION nature and is not intended to limit the invention or the appli
cation and uses of the invention. Furthermore, there is no
The present invention is directed to fabricating integrated intention to be bound by any theory presented in the preced
circuits on a semiconductor wafer and, more particularly, to ing background or the following detailed description.
methods and systems for optimizing the number of dies that FIG. 1A is an exemplary top view of a wafer 100 that
can be produced on a particular wafer. includes a plurality of dies including a die 140. As used
In Semiconductor design and manufacturing, it is desirable 10 herein, the term "wafer' refers to a thin slice of electronic
to optimize the number of dies that can fit in a wafer of a grade semiconductor material. Such as a silicon crystal, used
particular size or diameter. The number of dies in a wafer is in the fabrication of “dies' such as integrated circuits and
often referred to in the art as dies per wafer (DPW). For any other microelectronic devices. As is well-known in the art, a
wafer serves as the substrate that dies are fabricated in and on
particular wafer diameter d, mm and target die size S. 15 using fabrication processing steps such as doping or ion
mm, the number of dies that can be sliced out of the wafer implantation, etching, deposition of various materials, and
can be estimated by the following expression: photolithographic patterning. In FIG. 1A each of the dies is
represented by a tiny rectangle within a potential fabrication
d 1 area 130 where dies can be fabricated. The rectangle 140
DPW dri vie) represents one particular die. FIG. 1B is an exemplary top
view of the die 140 of FIG.1A. As used herein, the term “die”
refers to a small block of semiconducting material, on which
Electronic Design Automation (EDA) software refers to a a given functional circuit is fabricated. Typically, multiple
category of Software tools used for designing electronic sys dies are produced in and/or on the wafer 100. When the wafer
tems such as integrated circuits. It would be desirable if EDA 25 100 is cut (or “diced') into many pieces, each of these pieces
software could optimize the number of dies that can be pro is called a die. The terms “die”, “microchip”, “chip' and
duced or fabricated in a particular wafer. “integrated circuit” are used interchangeably herein.
As illustrated in FIG. 1A, the wafer 100 has a total wafer
BRIEF DESCRIPTION OF THE DRAWINGS area (A); however, a portion of the total wafer area (A) is
30 not used for fabrication of dies, and the term wafer area (A)
The present invention will hereinafter be described in con is used herein to distinguish between to total wafer area and
junction with the following drawing figures, wherein like the potential fabrication area 130 where potential good dies
numerals denote like elements, and can be fabricated (e.g., where commercially acceptable or
FIG. 1A is a top plan view of a wafer that includes a viable dies can be fabricated). In other words, as used herein,
plurality of dies including an exemplary die; 35 the term "wafer area (A)” refers to the portion of the wafer
FIG.1B is a top plan view of the exemplary die of FIG. 1A. 100 on which dies can potentially be fabricated (e.g., total
FIG. 2 is a flow chart that illustrates a computer-imple wafer area (A) excluding the edge band 110 and notch 120
mented method for optimizing the number of dies that can be of the wafer 100). The edge band 110 of the wafer 100 refers
fabricated on a wafer in accordance with an embodiment of to a band along the outer edge of the wafer 100 where dies
the present invention; 40 cannot be fabricated; the edge band 110 typically has a sub
FIG. 3 is a flow chart that illustrates a die number optimi stantially constant edge band width (W) except for in the
zation (DNO) routine of the computer-implemented method region that is commonly referred to as the notch 120.
of FIG. 2 in accordance with an embodiment of the present As is well-known in the art, the dies that make up the wafer
invention; 100 are eventually separated (or “diced'), for example, by
FIGS. 4A and 4B depict a flow chart that illustrates a die 45 scribing and breaking, by mechanical sawing (normally with
area maximization routine of a die size optimization (DSO) a machine called a dicing saw) or by laser cutting. Following
routine of the computer-implemented method of FIG. 2 in the dicing process the individual silicon chips are packaged
accordance with an embodiment of the present invention; (e.g., encapsulated into chip carriers).
FIG.5 is a flow chart that illustrates a second routine of the As illustrated in FIG. 1B, the die 140 has a height (y)
DSO routine of the computer-implemented method of FIG.2 50 dimension and a width (x) dimension. As used herein with
in accordance with an embodiment of the present invention; reference to a die, the term “height” refers to a dimension (y)
FIG. 6 is a flow chart that illustrates a third routine of the of the die that is measured in a plane that is parallel to an upper
DSO routine of the computer-implemented method of FIG.2 surface of the die, and the term "width” refers to another
in accordance an embodiment of the present invention; dimension (X) of the die that is also measured in a plane that
FIG. 7 is a top plan view of a wafer when a conventional die 55 is parallel to an upper surface of the die, but that is usually
number optimization routine is performed; substantially perpendicular to the dimension (y) of the die. In
FIG. 8 is a top plan view of the wafer of FIG. 7 when a other words, the die’s height (y) and width (x) dimensions are
method for optimizing the number of dies is performed in measured along a surface of the die. Its noted that in FIG. 1B,
accordance with an embodiment of the present invention; the dies height (y) and width (x) dimensions are interchange
FIG. 9 is a table illustrating a comparison between a num 60 able, and can be swapped without changing their meaning.
ber of dies per wafer for the conventional die number optimi The term “depth' or “thickness' refers to a dimension of the
zation routine and a number of dies per wafer when the die die (not illustrated, but into the page on FIG. 1B) that is
number optimization method in accordance with an embodi measured in a plane that is Substantially perpendicular to the
ment of the present invention is performed; and height (y) and width (x) dimensions of the die.
FIG. 10 is a schematic block diagram of a computer system 65 As used herein, the term “shape' when used with reference
for executing the die optimization methods and EDA tools in to a die refers to a specific combination of a particular width
accordance with an embodiment of the present invention. (X) dimension and a particular height (y) dimension. Its noted
 US 8,671,381 B1
3 4
that in generala die may have any shape generated by Straight includes iteratively checking each die shape in a first list ofdie
lines, but that they are typically either Substantially rectangu shapes to determine which ones of the die shapes have the
lar-shaped or Substantially square-shaped. maximum number of dies (N) for the target die area
As used herein, the term “aspect ratio (x/y) when used (A). The die shapes have the maximum number of dies
with reference to a die refers to a number that is equal to the (N) for the target die area (A)
targe are added to an initial
ratio of the dies width (x) to the die’s height (y). result list.
As used herein, the term “area' when used with reference At 230, as will be described in greater detail below with
to a die refers to a product (xy) of the dies height (y) and the reference to FIGS. 4-6, a die size optimization (DSO) routine
die's width (x). When used with reference to a die, the terms 230 is executed to determine: (a) a list of die shapes having a
“size' and “area are used interchangeably. As used herein 10 maximum die area (A) corresponding to the maximum
number of dies (N), (b) a first list of optimized die shapes,
the term “target die area (A) can refer to a user or cus
tomer defined die area. which have a maximum area utilization (AU), for a decreased
As such, a particular die shape will have a particular area target die area (A), and (c) a second list of optimized die
and a particular aspect ratio. However, a particular die area or shapes, which have a minimum area utilization (AU), for an
increased target die area (A).
a die particular aspect ratio can correspond to many different 15
At 240, entries from the initial result list that was generated
die shapes. at 220, and optionally entries in each of the three lists (that
Unfortunately, current EDA software has no automated were generated at 230) are compiled and output as entries in
tool that can concurrently and reliably evaluate the number of a candidate list, for example, on a computer display or other
dies that can be fabricated on a particular wafer for a given medium so that they can be evaluated by a user. Thus, in one
optimized die shape for each one of a number of different die embodiment, the candidate list includes a plurality of entries
sizes. Instead, designers have to evaluate how different die from (1) the initial result list of die shapes that have the
sizes (areas) impact the number of dies that can be fabricated maximum number of dies (N) for the target die area
on a particular wafer by randomly evaluating the number of (A) (that was generated during the DNO routine at 220),
dies per wafer that will result for different die sizes (having a (2) the list of die shapes having the maximum die area (A)
fixed die shape). In doing so, the designers must compute the 25 corresponding to the maximum number of dies (N) (that
number of dies per wafer over and over again. This task is a was generated during the DSO routine at 230/400), (3) the
very time consuming, inefficient, error prone, and labor-in first list of optimized die shapes (that was generated during
tensive, and does not automatically optimize the number of the DSO routine at 230/500), and (4) the second list of opti
dies per wafer. Consequently, time delays and other ineffi mized die shapes (that was generated during the DSO routine
ciencies are introduced into the overall manufacturing pro 30 at 230/600). In one exemplary implementation, each entry in
cess. To save time and money, it would be desirable to provide the candidate list can include, for example, die width (x), die
an EDA software tool that can be used to make such an height (y), die area (x:y), die aspect ratio (x/y), and die num
evaluation in an automated manner. For example, it would be ber (or “number of dies’). An example of such a candidate list
desirable to provide EDA software that includes a DPW opti will be described below with reference to FIG. 9. The candi
mization component or tool that designers can use during 35 date list allows for a variety of different die shapes to be
planning and layout for estimating DPW for a number of evaluated to determine which one will yield a desired number
different die sizes, and that can be used to optimize the num of dies per wafer (e.g., the maximum number of dies (N)
ber of dies on a wafer by optimizing die size to determine a on the wafer).
maximum number of dies per wafer. In some scenarios, the candidate list will have multiple
In accordance with some of the disclosed embodiments, 40 entries that all have the same maximum number of dies
computer-implemented methods and systems are provided (N) on the wafer. When there is more than one entry
for die area and die shape co-optimization that can be used to having the same maximum number of dies (N) on the
optimize a number of dies that can be fabricated on a particu wafer, at 250, one of the entries from the candidate list can be
lar wafer. In accordance with some of the disclosed embodi selected automatically by a computer or by a user. In some
ments, computer-implemented methods and systems are also 45 embodiments, the selected entry can be, for example, the
provided that can also be used to further optimize die size and entry that has the maximum number of dies (N) on the
number of dies together so that utilization of wafer area (A) wafer, and a desired aspect ratio and/or desired die shape, etc.
can be optimized. In addition, in Some embodiments, text can be included on the
FIG. 2 is a flowchart that illustrates a computer-imple display that indicates a proposed wafer layout corresponding
mented method 200 for optimizing a number of dies that can 50 to one of the entries from the candidate list. In one implemen
be fabricated on a wafer in accordance with some of the tation, the proposed wafer layout can include a suggested die
disclosed embodiments. area (x,y), a suggested die height (X), a Suggested die width
Method 200 begins at 210, when input variables are input. (y), a Suggested die aspect ratio (X/y.), and the maximum
As used herein, the term “input variables' can be used to refer number of dies (N). In addition, in some implementations,
to user-defined die and wafer dimensions. In one embodi 55 an image that includes a wafer having the proposed wafer
ment, the input variables can include the die dimensions, layout can also be displayed.
which can include a minimum die width (x), a minimum FIG. 3 is a flowchart that illustrates a die number optimi
die height (yi), a target aspect ratio, Step size, and a target zation (DNO) routine 220 of the computer-implemented
die area (A), for example, and a wafer area (A), an edge method 200 of FIG. 2 in accordance with some of the dis
band width (w), and a scribe width (w) of the scribe lines 60 closed embodiments. As noted above, the DNO routine 220
between the dies. The step size is used for creation of each involves iteratively checking each die shape in the first list of
shape list. The step size is used to specify the minimal offset die shapes to determine which ones of the die shapes have the
between the width (x) and height (y) values in a shape list. maximum number of dies (N) for the target die area
At 220, a die number optimization (DNO) routine 220 is (A). One exemplary embodiment of the DNO routine
executed to determine a maximum number of dies (N) for 65 will now be described with reference to FIG. 3.
the target die area (A). As will be described in greater The DNO routine 220 begins at 310, a first maximum die
detail below with reference to FIG. 3, the DNO routine 220 width (x) and a first maximum die height (y) can be
 US 8,671,381 B1
5 6
computed. In one embodiment, the first maximum die width The DNO routine 220 is complete at 360, and the method
(x,) is computed by dividing the target die area (A) by 200 then proceeds to execute the DSO routine 230. As will be
the minimum die width (x), and the first maximum die explained below with reference to FIGS. 4-6, the DSO routine
height (y) is computed by dividing the target die area 230 may include three processes or routines that can be
(A) by the minimum die height (yi). executed in parallel in one embodiment.
Based on the minimum die width (x), the minimum die FIG. 4 is a flowchart that illustrates a routine 400 of the die
height (yi), the maximum die width (x) and the maxi size optimization (DSO) routine 230 of the computer-imple
mum die height (y), at 320, a first list of die shapes that mented method 200 of FIG. 2 in accordance with some of the
have the target die area (A) can be generated. For disclosed embodiments. As will be explained in greater detail
example, in one embodiment, the first list of die shapes is 10 below, the routine 400 determines, while holding the maxi
generated by creating a set of values within the range mum number of dies (N) determined during the DNO
{X, . . . X, that are bound by the minimum die width routine 220 at a fixed number, a list of die shapes having a
maximum die area (A) corresponding to the maximum
(X) and the maximum die width (X) creating another set number of dies (N).
of values with another range {y, ...y, that are boundby 15 Preliminarily, it is noted that the routine 400 receives at
the minimum die height (yi) and the maximum die height least some of the input variables that were input at 210 of FIG.
(y), and then computing different combinations of widths 2 (e.g., the minimum die width (x) and minimum die
and heights within these ranges or die shapes that have the height (yi), Step size (e.g., the minimal offset between the
target die area (A). The number of die shapes in the first width (x) and height (y) values), target die area (A)), and
list can vary depending on the implementation, and any the maximum number of dies (N) specified in final result
degree of granularity for the width/height combinations that list generated at step 355 of the DNO routine 220.
is desired can be utilized. The routine 400 begins at 410, where a second maximum
Prior to 325, a “next die shape in the first list of die shapes die width (x) and a second maximum die height (y) are
is selected as the current die shape (to be evaluated). During computed based on an upper limit die area (A), the mini
the first iteration of the DNO routine 220 the current die shape 25 mum die width (x) and the minimum die height (y). In
is the first die shape in the first list. At 325, a number (Ni) of one embodiment, the upper limit die area (A) can be com
dies for that current die shape (that is presently selected from puted based on the target die area (A) by increasing the
the first list of die shapes) is computed. The computation at target die area (A) by a first scaling factor (e.g., a number
325 can also be referred to as a potential die per wafer greater than one) to an upper limit or "maximum. For
(PDPW) computation routine. 30 example, in one implementation the target die area (A)
At 335, it is determined whether the computed number (Ni) can be multiplied by a first scaling factor of 1.5 to increase the
of dies for the current die shape is greater than or equal to a target die area (A) by 50%. In one embodiment, the
current maximum die number (N) stored in a result list. second maximum die width (x) is computed by dividing
When the computed number (Ni) of dies for the current die the upper limit die area (A) by the minimum die width (x)
shape is determined (at 335) to be equal to the current maxi 35 and the second maximum die height (y) is computed by
mum die number (N) stored in the result list, then at 340, dividing the upper limit die area (A) by the minimum die
the current die shape, the computed number (Ni) of dies for height (ymin).
the current die shape, and a current aspect ratio of the current Based on the minimum die width (X), the minimum die
die shape can be added to a result list. The DNO routine 220 height (yi), the second maximum die width (x) and the
then proceeds to 350, where it is determined whether all die 40 second maximum die height (y), at 420, a second list of
shapes in the first list of die shapes been evaluated. die shapes that have the upper limit die area (A) is generated.
By contrast, when the computed number (Ni) of dies for the For example, in one embodiment, the second list of die shapes
current die shape is determined (at 335) to be greater than the is generated by creating a set of values within the range
current maximum die number (N) stored in the result list, {X, . . . X, that are bound by the minimum die width
then at 345, the result list is cleared of all entries (or reset), and 45 (X) and the second maximum die width (X), creating
the current die shape, the computed number (Ni) of dies for another set of values with another range {y, ...y,' that
the current die shape, and the current aspect ratio of the are bound by the minimum die height (y) and the second
current die shape are added to the result list. The DNO routine maximum die height (y), and then computing different
220 then proceeds to 350, where it is determined whether all combinations of widths and heights within these ranges or die
die shapes in the first list of die shapes have been evaluated. 50 shapes that have the upper limit die area (A). The number of
When the computed number (Ni) of dies for the current die die shapes in the second list can vary depending on the imple
shape is determined (at 335) to be less than the current maxi mentation, and any degree of granularity for the width/height
mum die number (N) stored in the result list, then the DNO combinations that is desired can be utilized.
routine 220 proceeds to 350, where it is determined whether As will now be explained with reference to 425 through
all die shapes in the first list of die shapes have been evaluated. 55 460, the second list of die shapes can then be iteratively
When it is determined, at 350, that all die shapes in the first evaluated to which one(s) have a maximum die area (A)
list of die shapes have not yet been evaluated, the next die that corresponds to the maximum number of dies (N) that
shape in the first list is selected as the current die shape, and was computed during the DNO routine 220.
the DNO routine returns to 325 for another iteration. This Prior to 425, a “next die shape in the second list of die
iterative processing continues until it is determined that all die 60 shapes is selected as the current die shape (to be evaluated),
shapes in the first list of die shapes have been evaluated (at and at 425, a number (Nul) of dies for that current die shape is
350) at which point the DNO routine 220 proceeds to 355. computed. During the first iteration of the DNO routine 220
At 355, the result list is recorded as a final result list. The the current die shape is the first die shape in the second list.
final result list can include one or more entries, wherein each The computation at 425 can also be referred to as a potential
entry comprises: a particular die shape for that entry, the 65 die per wafer (PDPW) computation routine.
maximum number of dies (N), and a particular aspect ratio At 430, it is determined whether the computed second
for that entry. number (Nul) of dies for the current die shape is equal to the
 US 8,671,381 B1
7 8
maximum number of dies (N) (i.e., that was computed (X), the minimum die height (yi), the third maximum die
during the DNO routine 220). When the computed second width (x") and the third maximum die height (y"). For
number (Nul) of dies for the current die shape is determined (at example, in one embodiment, the third list of die shapes is
430) not to be equal to the maximum number of dies (N), generated by creating a set of values within the range
the routine 400 proceeds to 450, where it is determined {x . . . X" that are bound by the minimum die width
whether all die shapes in the second list of die shapes have (X) and the third maximum die width (x"), creating
been evaluated. When it is determined at 450 that all die another set of values with another range {y, ...y,' that
shapes in the second list of die shapes have not yet been are bound by the minimum die height (y) and the third
evaluated, the next die shape in the second list of die shapes is maximum die height (y"), and then computing different
selected as the current die shape, and the routine 400 returns 10
combinations of widths and heights within these ranges or die
to 425 to begin another iteration. shapes that have the lower limit die area (A). The number of
When the computed second number (Nul) of dies for the die shapes in the third list can vary depending on the imple
current die shape is determined (at 430) to be equal to the mentation, and any degree of granularity for the width/height
maximum number of dies (N) (i.e., that was computed combinations that is desired can be utilized.
during the DNO routine 220), then the routine 400 proceeds 15
As will now be described below with reference to 525-560,
to 435, where it is determined whether current die area has the third list of die shapes that have the lower limit die area
increased in comparison to the target die area (A) when (A) can then be evaluated to determine which ones have the
using the current die shape. maximum area utilization (AU) in view of the lower limit die
When the current die area is determined (at 435) not to have area (A).
increased in comparison to the target die area (A) when Prior to 525, a “next die shape in the third list of die shapes
using the current die shape, then the routine 400 proceeds to is selected as the current die shape (to be evaluated), and at
450, where it is determined whether all die shapes in the 525, a number (N1) of dies is computed for the current die
second list of die shapes have been evaluated. shape.
When the current die area is determined (at 435) to have At 530, a first area utilization value is computed for the
increased in comparison to the target die area (A) when 25
current die shape, and then at 535, it is determined whether
using the current die shape, then the routine 400 proceeds to both the first area utilization value and the computed number
440, where a first result is stored in a list of die shapes having (N1) of dies for the current die shape have increased from
a maximum die area (A) corresponding to the maximum previously stored values. In one exemplary embodiment, the
number of dies (N). The first result is the current die area area utilization value can be computed per equation (1) as
associated with the current die shape. The routine 400 then 30
follows:
proceeds to 450, where it is determined whether die shapes in
the second list of die shapes have been evaluated.
When it is eventually determined at 450 that all die shapes ADieNumber current die number-maximum die number (1)
in the second list of die shapes have been evaluated, the ADie Area current die area - target die area
routine 400 proceeds to 460, where the list of die shapes 35
having the maximum die area (A) is recorded. Each die
shape in the list of die shapes having the maximum die area When it is determined, at 535, that the first area utilization
(A) also have the maximum number of dies (N) that value and the computed number (N1) of dies for the current
was computed during the DNO routine 220. die shape have not increased from previously stored values, at
FIG.5 is a flowchart that illustrates a second routine 500 of 40 550, it is determined whether all die shapes in the third list of
the die size optimization (DSO) routine 230 of the computer die shapes have been evaluated.
implemented method 200 of FIG. 2 in accordance with some When it is determined, at 535, that both the first area
of the disclosed embodiments. utilization value and the computed number (N1) of dies for the
Preliminarily, it is noted that the second routine 500 current die shape have increased from previously stored val
receives at least some of the input variables that were input at 45 ues, then at 540, the current die area associated with the
210 of FIG. 2 (e.g., the minimum die width (x) and mini current die shape is stored as a second result. Then at 550, it
mum die height (yi), step size, target die area (A)), and is determined whether all die shapes in the third list of die
the maximum number of dies (N) specified in final result shapes have been evaluated.
list generated at step 355 of the DNO routine 220. When it is determined at 550 that all die shapes in the third
At 510, the target die area (A) is decreased and a third 50 list of die shapes have not yet been evaluated, the next die
maximum die width (X") and a third maximum die height shape in the third list is selected as the current die shape and
(y") are computed. For example, in one embodiment, the another iteration begins at 525. This iterative processing at
target die area (A) can be multiplied by a second scaling 525 through 540 is repeated per FIG. 5 until all die shapes in
factor (e.g., a number less than one) to compute a decreased the third list of die shapes have been evaluated.
target die area (A) that will be referred to below as a 55 When it is determined at 550 that all die shapes in the third
lower limit die area (A). For example, in one implementa list of die shapes have been evaluated, at 560, the second
tion, where the designer decides that the target die area results that are presently stored are recorded as the first list of
(A) should be decreased by 50%, the second scaling optimized die shapes. This first list of optimized die shapes
factor would be 0.5, which is the lower limit or minimum die are the ones of the third list of die shapes (from 520) that have
area to be evaluated. Once the lower limit die area (A) has 60 been determined to have the maximum area utilization (AU).
been computed, the third maximum die width (x") can FIG. 6 is a flowchart that illustrates a third routine 600 of
then be computed by dividing the lower limit die area (A) by the die size optimization (DSO) routine 230 of the computer
the minimum die width (x), and the third maximum die implemented method 200 of FIG. 2 in accordance with some
height (y") can then be computed by dividing the lower of the disclosed embodiments.
limit die area (A) by the minimum die height (y). 65 Preliminarily, it is noted that the third routine 600 receives
At 520, a third list of die shapes that have the lower limit die at least some of the input variables that were input at 210 of
area (A) is generated based on the minimum die width FIG. 2 (e.g., the minimum die width (x) and minimum die
 US 8,671,381 B1
9 10
height (yi), step size, target die area (A)), the maxi routine 230 is performed (row 974), simulation results after
mum number of dies (N) specified in final result list gen the third routine 600 of the DSO routine 230 (FIG. 6) is
erated at step 355 of the DNO routine 220, and the second list performed (row 976).
of die shapes that was generated at step 420 of FIG. 4. When the DNO routine 220 (FIG. 3) is performed (row
Prior to 625, a “next die shape in the second list of die 5 970), the width (x) dimension of the dies decreases and the
shapes is selected as the current die shape (to be evaluated), height (y) dimension of the dies increases slightly in com
and at 625, a number (Nu') of dies for a current die shape in the parison to the values when the conventional die number opti
second list of die shapes is computed. mization routine (row 960) is applied, whereas the target die
At 630, a second area utilization value for the current die 10 area (A) remains fixed (i.e., does not change). As illus
shape is computed using equation (1) above. trated in table 900, the conventional die number optimization
At 635, it is determined whether the second area utilization routine (row 960) results in having an aspect ratio of 1.1033,
value for the current die shape has decreased from previously and 3342 die being fit into a particular wafer having a par
stored values. ticular fabrication area. By contrast, after the DNO routine
When it is determined, at 635, that the second area utiliza 15 220 is performed (row 970), 3362 die are fit into the same
tion value for the current die shape has decreased from pre wafer with each of the die having as aspect ratio of 1.1146. As
viously stored value, at 650, it is determined whether all die such, the simulation results show that implementing the DNO
shapes in the second list of die shapes have been evaluated. routine alone increases the number of dies that can be fabri
When it is determined, at 635, that the second area utiliza cated on the wafer by 0.598% in comparison to the conven
tion value for the current die shape has decreased from pre tional die number optimization routine (row 960).
viously stored values, at 640, the current die area associated When the routine 400 of the DSO routine 230 (FIG. 4) is
with the current die shape is stored as a third result, and it is performed (row 972), the width (x) dimension of the dies
determined at 650, whether all die shapes in the second list of decreases and the height (y) dimension of the dies increases
die shapes have been evaluated. slightly in comparison to the values when the conventional
When it is determined (at 650) that all die shapes in the 25 die number optimization routine (row 960) is applied, and the
second list of die shapes have not yet been evaluated, the next die area also increases. As illustrated in table 900, after the
die shape in the second list of die shapes is selected as the routine 400 of the DSO routine 230 is performed (row 972),
current die shape, and the routine 600 returns to 625 to begin 3362 die are fit into the same wafer with each of the diehaving
anotheriteration. This iterative processing at 625 through 640 30
as aspect ratio of 1.1150. As such, the simulation results show
is repeated per FIG. 6 until all die shapes in the second list of that implementing the DNO routine along with the routine
die shapes have been evaluated. 400 of the DSO routine 230 increases the number of dies that
When it is determined (at 650) that all die shapes in the can be fabricated on the wafer by 0.598% incomparison to the
second list of die shapes have been evaluated, the third results conventional die number optimization routine (row 960). In
that are presently stored can be recorded at 660, as the second 35 this particular example, implementing the routine 400 of the
list of optimized die shapes. The second list of optimized die DSO routine 230 results in a negligible increase in die area
shapes are the ones of the second list of die shapes (from 420 (0.017%) and aspect ratio, but no increase indie number, with
of FIG. 4) that have been determined to have the minimum respect to the results produced when only the DNO routine is
area utilization (AU). performed.
FIG. 7 is an exemplary top view of a wafer 700-A when a 40 When the second routine 500 (FIG. 5) of the DSO routine
conventional die number optimization routine is performed. 230 is performed (row 974), the width (x) dimension of the
The wafer 700-A includes 3342 dies. dies decreases and the height (y) dimension of the dies
FIG. 8 is an exemplary top view of the same wafer 700-B of increases slightly in comparison to the values when the con
FIG. 7 when the method 200 for optimizing a number of dies ventional die number optimization routine (row 960) is
is performed in accordance with some of the disclosed 45 applied, while the die area actually decreases. As illustrated in
embodiments. The wafer 700-B now includes 3368 dies, or table 900, after the second routine 500 of the DSO routine 230
26 additional dies in the same wafer 700-A. is performed (row 974), 3368 die are fit into the same wafer
FIG. 9 is an exemplary table 900 illustrating a comparison with each of the die having a larger aspect ratio of 1.1174. As
between a number of dies per wafer for the conventional die Such, the simulation results show that implementing the sec
number optimization routine (FIG. 7) and a number of dies 50 ond routine 500 of the DSO routine 230 (in conjunction with
per wafer when the method 200 for optimizing a number of the DNO routine and the routine 400 of the DSO routine 230)
dies is performed in accordance with some of the disclosed the number of dies that can be fabricated on the wafer can be
embodiments. increased by 0.788% in comparison to the conventional die
Column 905 of table 900 shows various optimization rou number optimization routine (row 960).
tines that can be performed to optimize the number of dies on 55 When the third routine 600 (FIG. 6) of the DSO routine 230
a particular wafer, and row 955 of table 900 shows variables is performed (row 976), the width (x) dimension of the dies
that can be computed when each of the different optimization decreases and the height (y) dimension of the dies increases
routines are performed. Specifically, the variables in row 955 slightly in comparison to the values when the conventional
include die width (x) dimensions in column 910, die height die number optimization routine (row 960) is applied, while
(y) dimensions in column 920, die area (x y) in column 930, 60 the die area increases. As illustrated in table 900, after the
die number in column 940, and die aspect ratio (x/y) in third routine 600 of the DSO routine 230 is performed (row
column 950. The table 900 includes simulation results for a 976), 3360 die are fit into the same wafer with each of the die
conventional die number optimization routine (row 960), having a larger aspect ratio of 1.1158. As such, the simulation
simulation results after the DNO routine 220 is performed results show that implementing the third routine 600 of the
(row 970), simulation results after the routine 400 (FIG. 4) of 65 DSO routine 230 (in conjunction with the DNO routine, the
the DSO routine 230 is performed (row 972), simulation routine 400 of the DSO routine 230 and the second routine
results after the second routine 500 (FIG. 5) of the DSO 500 of the DSO routine 230), the number of dies that can be
 US 8,671,381 B1
11 12
fabricated on the wafer can be increased by 0.539% in com The processor 1002 may include a single microprocessor
parison to the conventional die number optimization routine or a plurality of microprocessors configured as a multi-pro
(row 960). cessor System.
AS Such, the various embodiments can allow for an The main memory 1004 stores, in part, instructions and
increase in the number of dies that can be fabricated on a 5 data to be executed by the processor 1002. The main memory
particular wafer. 1004 preferably includes banks of dynamic random access
It is noted that the information included in rows 970,972, memory (DRAM) as well as high-speed cache memory.
974,976 of the table 900 is one example of the candidate list For the purpose of simplicity, the components of the com
that could be outputat block 240 of FIG. 2; however, its noted 10
puter system 1000 are connected via interconnect bus 1006.
that there could be multiple entries in any of the rows 970, However, the computer system 1000 may be connected
972,974,976 in otherexamples where multiple entries result. through one or more data transport means. For example, the
Although the embodiments and implementations are processor 1002 and main memory 1004 may be connected via
described above are illustrated in terms of functional and/or a local microprocessor bus and mass storage device 1008,
logical block components (or modules) and various process 15 peripheral device(s) 1010, portable storage medium drive(s)
ing steps, it should be appreciated that Such block compo 1014, and graphic subsystem 1016 may be connected via one
nents (or modules) may be realized by any number of hard or more input/output (I/O) buses.
ware, Software, and/or firmware components configured to Mass storage device 1008, which may be implemented
perform the specified functions. As used herein the term with a magnetic disk drive, an optical disk drive, a Solid State
“component' or “module' can generally refer to a device, a 20 device, or an attachment to network storage, is non-volatile
circuit, an electrical component, and/or a software based storage device for storing data, databases, and instructions, to
component for performing a task. As such, those of skill in the be used by the processor 1002. In a software embodiment,
art will appreciate that the various illustrative logical blocks, mass storage device 1008 may store the software to load it
modules, circuits, and algorithm steps described in connec into main memory 1004.
tion with the embodiments disclosed herein may be imple- 25 Portable storage medium drive 1014 operates in conjunc
mented as electronic hardware, computer Software, or com tion with a portable non-volatile storage medium Such as a
binations of both. floppy disk, a compact disk read only memory (CD-ROM), or
For example, the various illustrative logical blocks, mod a digital versatile disk read only memory (DVD-ROM), to
ules, and circuits described in connection with the embodi input and output data and code to and from the computer
ments disclosed herein may be implemented or performed 30 system 1000. In one embodiment, the software is stored on
with a general purpose processor, a digital signal processor Such a portable medium, and is input to computer system
(DSP), an application specific integrated circuit (ASIC), a 1000 via portable storage medium drive 1014.
field programmable gate array (FPGA) or other program Peripheral device(s) 1010 may include any type of com
mable logic device, discrete gate or transistor logic, discrete puter Support device Such as an input/output (I/O) interface, to
hardware components, or any combination thereof designed 35 add additional functionality to computer system 1000. For
to perform the functions described herein. A general-purpose example, peripheral device(s) 1010 may include a network
processor may be a microprocessor, but in the alternative, the interface card to interface computer system 1000 to a net
processor may be any conventional processor, controller, work.
microcontroller, or state machine. A processor may also be Input control device(s) 1012 provide a portion of the user
implemented as a combination of computing devices, e.g., a 40 interface for the computer system 1000 user. Input control
combination of a DSP and a microprocessor, a plurality of device(s) 1012 may include an alphanumeric keypad for
microprocessors, one or more microprocessors in conjunc inputting alphanumeric and other key information; and a
tion with a DSP core, or any other such configuration. cursor control device Such as a mouse, a track pad or stylus; or
The steps of a method or algorithm described in connection cursor direction keys.
with the embodiments disclosed herein may be embodied 45 In order to display textual and graphical information, com
directly in hardware, in a software module executed by a puter system 1000 contains graphic subsystem 1014 and out
processor, or in a combination of the two. A Software module put display(s) 1018. Output display 1018 may include a cath
may reside in RAM memory, flash memory, ROM memory, ode ray tube (CRT) display, liquid crystal display (LCD),
EPROM memory, EEPROM memory, registers, hard disk, a plasma, or light emitting diode (LED) display, etc.
removable disk, a CD-ROM, or any other form of storage 50 Graphic subsystem 1016 receives textual and graphical
medium known in the art. An exemplary storage medium is information and processes the information for output to dis
coupled to the processor Such the processor can read infor play 1018.
mation from, and write information to, the storage medium. In a software implementation, the EDA software includes a
In the alternative, the storage medium may be integral to the plurality of computer executable instructions, to be imple
processor. The processor and the storage medium may reside 55 mented on a computer system. Prior to loading in the com
in an ASIC. puter system, the EDA software may reside as encoded infor
One example a computing environment in which the dis mation on a computer-readable tangible medium Such as a
closed embodiments may be implemented will now be magnetic floppy disk, a magnetic tape, CD-ROM, DVD
described below with reference to FIG. 10. ROM, flash memory, or any other suitable computer readable
FIG. 10 illustrates a block diagram of a computer system 60 medium.
1000 for executing electronic design automation programs in In a hardware implementation, Such a system may be
accordance with various ones of the disclosed embodiments. implemented in any suitable computer based platform known
The computer system 1000 includes a processor 1002, a main in the art. For example, the system may comprise Suitable
memory 1004, an interconnect bus 1006, a mass storage storage media and one or more dedicated processors or share
device 1008, peripheral device(s) 1010, input control 65 one or more processors executing/controlling other functions,
device(s) 1012, portable storage drive(s) 1014, a graphics wherein the employed processor(s) is programmably config
subsystem 1016, and a display 1018. ured with processor instructions for performing the functions
 US 8,671,381 B1
13 14
described herein. Suitable circuits may also be developed to In some embodiments, the computer-implemented method
execute certain aspects of these functions. can also include executing a die size optimization (DSO)
In one embodiment, a computer-implemented method is routine to determine (1) a list of die shapes having a maxi
provided for optimizing a number of dies that can be fabri mum die area (A) corresponding to the maximum number
cated on a wafer. In accordance with the computer-imple 5 of dies (N), (2) a first list of optimized die shapes, which
mented method, input variables can be received that include: have a maximum area utilization (AU), for a decreased target
a minimum die width (x), a minimum die height (yi), a die area (A), and (3) a second list of optimized die
target aspect ratio, a target die area (A), a wafer area shapes, which have a minimum area utilization (AU), for an
(A), an edge band width (W), and a scribe width (W). In increased target die area (A).
Some embodiments of the computer-implemented method, a In some implementations, the DSO routine comprises a
first maximum die width (x) and a first maximum die first DSO routine, a second DSO routine and a third DSO
height (y) can be computed, and the first list of die shapes routine.
that have the target die area (A) can be generated based During the first DSO routine, the maximum die area (A)
on the minimum die width (x), the minimum die height 15 corresponding to the maximum number of dies (N) is
(y), the maximum die width (x) and the maximum die determined while holding the maximum number of dies
height (y). (N) determined during the DNO routine at a fixed number.
As part of the computer-implemented method, a die num During the first DSO routine, the target die area (A) can
ber optimization (DNO) routine can be executed to determine be multiplied by a first scaling factor to compute an upper
a maximum number of dies (N) for the target die area limit die area (A) based on the target die area (A), and
(A). During the DNO routine each die shape in a first list then, based on the upper limit die area (A), the minimum die
of die shapes can be iteratively checked to determine which width (x,) and the minimum die height (yi), a second
ones of the die shapes have the maximum number of dies maximum die width (x) and a second maximum die height
(N) for the target die area (A), and an initial result list (y) can be computed. Based on the minimum die width
of die shapes that have the maximum number of dies (N) 25 (X), the minimum die height (yi), the second maximum
for the target die area (A) can be generated. die width (x) and the second maximum die height (y"),
For example, in one implementation of the DNO routine of a second list of die shapes can be generated that have an upper
the computer-implemented method, each die shape in the first limit die area (A). The first DSO routine can then include
list of die shapes can be iteratively checked to determine steps (f) through (). At step (f) a next die shape from the
which ones of the die shapes have the maximum number of 30 second list of die shapes can be selected as a current die shape,
dies (N) for the target die area (A) by (a) selecting a and a second number (Nul) of dies for that current die shape
next die shape from the first list of die shapes as a current die can be computed. At step (g) it can then be determined
shape, and computing a first number (Ni) of dies for the whether the computed second number (Nul) of dies for the
current die shape from the first list of die shapes, and then at current die shape is equal to the maximum number of dies
step (b) determining whether the computed number (Ni) of 35 (N) that was computed during the DNO routine.
dies for the current die shape is greater than or equal to a When the computed second number (Nul) of dies for the
current maximum die number (N) stored in a result list. current die shape is determined to be not equal to the maxi
When the computed first number (Ni) of dies for the current mum number of dies (N) that was computed during the
die shape is equal to the current maximum die number (N) DNO routine, at step () it can be determined whether all die
stored in the result list, then at step (c) adding the computed 40 shapes in the second list of die shapes have been evaluated.
first number (Ni) of dies for the current die shape, the current When the computed second number (Nu) of dies for the
die shape and a current aspect ratio of the current die shape to current die shape is determined to be equal to the maximum
the result list, and then (e) determining whether all die shapes number of dies (N) that was computed during the DNO
in the first list of die shapes have been evaluated. When the routine, then at step (h) it can be determined whether current
computed first number (Ni) of dies for the current die shape is 45 die area has increased in comparison to the target die area
greater than the current maximum die number (N) stored (A) when using the current die shape. When the current
in the result list, then at step (d) the result list is cleared and the die area is determined not to have increased in comparison to
computed first number (Ni) of dies for the current die shape, the target die area (A) (when using the current die shape),
the current die shape and the current aspect ratio of the current then at step () it can be determined whether all die shapes in
die shape are added to the result list, and then at step (e) it can 50 the second list of die shapes have been evaluated. When the
be determined whether all die shapes in the first list of die current die area is determined to have increased in compari
shapes have been evaluated. son to the target die area (A) (when using the current die
When the computed first number (Ni) of dies for the current shape), then at Step (i) the current die shape can be stored as
die shape is not greater than the current maximum die number a first result in the list of die shapes having the maximum die
(N) stored in the result list, then at step (e) it can be 55 area (A) and corresponding to the maximum number of
determined whether all die shapes in the first list of die shapes dies (N). Then at step () it can be determined whether all
have been evaluated, and when it is determined that all die die shapes in the second list of die shapes have been evalu
shapes in the first list of die shapes have not yet been evaluated ated.
at Step (e), steps (a) through (e) can be iteratively repeated. By Whenever it is determined at step () that all die shapes in
contrast, when it is determined that all die shapes in the first 60 the second list of die shapes have not yet been evaluated, steps
list of die shapes have been evaluated at step (e), the result list (f) through () are iteratively repeated for a next die shape
can be recorded as a final result list. The final result list from the second list of die shapes (that can be selected as a
comprises a plurality of entries, wherein each entry com “new” current die shape). When it is determined at step () that
prises: a particular die shape for that entry, the maximum all die shapes in the second list of die shapes have been
number of dies (N), and a particular aspect ratio for that 65 evaluated, the list of die shapes having the maximum die area
entry. The aspect ratio of each entry in the final result list is (A) that corresponds to the maximum number of dies
different. (N) computed during the DNO routine can be recorded.
 US 8,671,381 B1
15 16
During the second DSO routine the target die area (A.) current die area associated with the current die shape can be
can be decreased to generate a decreased target die area stored as a third result. Then, at step (t), it can be determined
(A), and the first list of optimizeddie shapes, which have whether all die shapes in the second list of die shapes have
the maximum area utilization (AU), for the decreased target been evaluated. When it is determined at step (t) that all die
die area (A) can then be determined. shapes in the second list of die shapes have been evaluated,
For example, in one embodiment, the target die area the third results that are presently stored can be recorded as
(A) can be multiplied by a second scaling factor to com the second list of optimized die shapes, which have the mini
pute lower limit die area (A) based on the target die area mum area utilization (AU), for the increased target die area
(A), and then a third maximum die width (x,") and a (Arage).
third maximum die height (y") can be computed based on 10 In some embodiments, a candidate list can be output. The
the lower limit die area (A), the minimum die width (x) candidate list can include one or more entries that can include,
and the minimum die height (y). A third list of die shapes for example, die shapes from the initial result list that have the
that have the lower limit die area (A) can then be generated maximum number of dies (N) for the target die area
based on the minimum die width (x), the minimum die (A), die shapes from the list of die shapes having the
height (yi), the third maximum die width (X") and the 15 maximum die area (A) corresponding to the maximum
third maximum die height (y"). number of dies (N), the optimized die shapes from the first
The first list of optimized die shapes, which have the maxi list of optimized die shapes, and the optimized die shapes
mum area utilization (AU), for the decreased target die area from the second list of optimized die shapes. One of the
(A) can then be determined by performing steps (k) entries from the candidate list that will result in the maximum
through (o) as follows. At step (k), a next die shape from the number of dies (N) on the wafer can be selected automati
third list of die shapes can be selected as a current die shape, cally as part of the computer implemented method, or by a
and a third number (N1) of dies for the current die shape (in the user who inspects the candidate list.
third list of die shapes) can be computed. At step (1) a first area In some embodiments, information that is generated as part
utilization value for the current die shape can be computed, of the computer-implemented method can be displayed, for
and then at step (m) it can be determined whether the first area 25 example, on a graphical user interface. This information can
utilization value or the computed third number (N1) of dies for include text that indicates a proposed wafer layout corre
the current die shape has increased from previously stored sponding to one of the entries from the candidate list, and/or
values (if any have been stored). When it is determined, at step an image that includes a wafer having the proposed wafer
(m), that neither the first area utilization value nor the com layout. Text that indicates the proposed wafer layout can
puted third number (N1) of dies for the current die shape has 30 include, for example, a Suggested die area (x,y), a Suggested
increased from previously stored values, it can be determined die height (X), a suggested die width (y), a Suggested die
at step (o) whether all die shapes in the third list of die shapes aspect ratio (x,y), and the maximum number of dies (N).
have been evaluated. By contrast, when it is determined, at The computer-implemented methods that are described
step (m), that either the first area utilization value or the above for optimizing the number of dies that can be fabricated
computed third number (N1) of dies for the current die shape 35 on a wafer can be implemented in a computer program prod
has increased from previously stored values, then at step (n) uct for use with a computer. The computer program product
the current die area associated with the current die shape can comprises a non-transitory computer-readable storage
be stored as a second result. It can then be determined at Step medium comprising computer-executable instructions stored
(o) whether all die shapes in the third list of die shapes have thereon for optimizing the number of dies that can be fabri
been evaluated. When it is determined at step (o) that all die 40 cated on the wafer. In Such implementations, the computer
shapes in the third list of die shapes have not yet been evalu executable instructions can perform any combination of the
ated, steps (k) through (n) can be iteratively repeated. By various steps described herein.
contrast, when it is determined at step (o) that all die shapes in The computer-implemented methods and computer pro
the third list of die shapes have been evaluated, the second gram products that are described above can be implemented
results that are presently stored as can be stored as the first list 45 as part of a system for performing electronic design automa
of optimized die shapes. The die shapes in the first list of tion tasks including optimizing the number of dies that can be
optimizeddie shapes have the maximum area utilization (AU) fabricated on a wafer. In this case, the system comprises a
for the decreased target die area (A). computer processor, a storage memory coupled to the com
During the third DSO routine steps (p) through (t) can be puter processor, an input apparatus for inputting input vari
iteratively performed. At step (p) a next die shape from the 50 ables and a computer program that includes Software modules
second list of die shapes can be selected as a current die shape, including software modules that are designed to perform the
and a fourth number (Nu') of dies for the current die shape computer-executable instructions that are described above.
(from the second list of die shapes) can be computed. At step For instance, the computer program can includes, in one
(q) a second area utilization value for the current die shape is implementation, a first module configured to compute a first
computed, and at step (r) it can be determined whether the 55 maximum die width (X) and a first maximum die height
second area utilization value for the current die shape has (y, to generate a first list of die shapes that have the target
decreased from a previously stored value (if any is/are die area (A), based on the minimum die width (x), the fia
stored). When it is determined, at step (r), that the second area minimum die height (yi), the maximum die width (x)
utilization value for the current die shape has not decreased and the maximum die height (y), to determine a maximum
from the previously stored value, then at step (t) it can be 60 number of dies (N) for the target die area (A) by
determined whether all die shapes in the second list of die iteratively checking each die shape in a first list of die shapes
shapes have been evaluated. When it is determined at step (r) to determine which ones of the die shapes have the maximum
that all die shapes in the second list of die shapes have not yet number of dies (N) for the target die area (A), and to
been evaluated steps (p) through (t), can be iteratively generate an initial result list of die shapes that have the maxi
repeated. By contrast, when it is determined, at step (r), that 65 mum number of dies (N) for the target die area (A):
the second area utilization value for the current die shape has and a second module configured to determine (1) a list of die
decreased from the previously stored value, then at step(s) the shapes having a maximum die area (A) corresponding to
 US 8,671,381 B1
17 18
the maximum number of dies (N), (2) a first list of opti generating an initial result list of die shapes that have the
mized die shapes, which have a maximum area utilization maximum number of dies (N) for the target die
(AU), for a decreased target die area (A), and (3) a second aca (Atarge):
list of optimized die shapes, which have a minimum area executing a die size optimization (DSO) routine to deter
utilization (AU), for an increased target die area (A). The mine (1) a list of die shapes having a maximum die area
computer program can optionally include a third module (A) corresponding to the maximum number of dies
configured to generate a candidate list (as described above). (N), (2) a first list of optimized die shapes that have a
Further, in some implementations, the system can include a maximum area utilization (AU) for a decreased target
display for displaying one or more of a proposed wafer die area (A), and (3) a second list of optimized die
layout corresponding to one of the entries from the candidate 10
shapes that have a minimum area utilization (AU) for an
list, the proposed wafer layout comprising: a Suggested die
area (x,y), a suggested die height (X), a Suggested die width increased target die area (A):
(ys), a Suggested die aspect ratio (X/y.), and the maximum outputting a candidate list comprising a plurality of entries
number of dies (N); and an image that includes a wafer including die shapes from the initial result list that have
having the proposed wafer layout 15 the maximum number of dies (N) for the target die
In this document, relational terms such as first and second, area (A), die shapes from the list of die shapes
and the like may be used solely to distinguish one entity or having the maximum die area (A) corresponding to
action from another entity or action without necessarily the maximum number of dies (N), the optimized die
requiring or implying any actual Such relationship or order shapes from the first list of optimized die shapes, and the
between Such entities or actions. Numerical ordinals such as optimized die shapes from the second list of optimized
“first.” “second,” “third,' etc. simply denote different singles die shapes; and
of a plurality and do not imply any order or sequence unless selecting one of the entries from the candidate list that will
specifically defined by the claim language. The sequence of result in the maximum number of dies (N) on the f

the text in any of the claims does not imply that process steps wafer.
must be performed in a temporal or logical order according to 25 2. The computer-implemented method of claim 1, further
Such sequence unless it is specifically defined by the language comprising:
of the claim. The process steps may be interchanged in any computing a first maximum die width (X, ) and a first
order without departing from the scope of the disclosed maximum die height (y), and
embodiments as long as such an interchange does not contra generating the first list of die shapes that have the target die
dict the claim language and is not logically nonsensical. 30 area (A), based on the minimum die width (x,a),
Furthermore, depending on the context, words such as the minimum die height (yi), the maximum die width
“connect” or “coupled to used in describing a relationship (X) and the maximum die height (y).
between different elements do not imply that a direct physical 3. The computer-implemented method of claim 2, wherein
connection must be made between these elements. For the step of iteratively checking each die shape in the first list
example, two elements may be connected to each other physi 35 of die shapes to determine which ones of the die shapes have
cally, electronically, logically, or in any other manner, the maximum number of dies (N) for the target die area
through one or more additional elements. (A), comprises:
While at least one exemplary embodiment has been pre (a) selecting a next die shape from the first list of die shapes
sented in the foregoing detailed description of the invention, as a current die shape, and computing a first number (Ni)
it should be appreciated that a vast number of variations exist. 40 of dies for the current die shape from the first list of die
It should also be appreciated that the exemplary embodiment shapes; and
or exemplary embodiments are only examples, and are not (b) determining whether the computed number (Ni) of dies
intended to limit the scope, applicability, or configuration of for the current die shape is greater than or equal to a
the invention in any way. Rather, the foregoing detailed current maximum die number (N) stored in a result
description will provide those skilled in the art with a conve 45 list, and
nient road map for implementing an exemplary embodiment the method further comprising:
of the invention. It being understood that various changes when the computed first number (Ni) of dies for the current
may be made in the function and arrangement of elements die shape is equal to the current maximum die number
described in an exemplary embodiment without departing (N) stored in the result list, then (c) adding the com
from the scope of the invention as set forth in the appended 50 puted first number (Ni) of dies for the current die shape,
claims. the current die shape and a current aspect ratio of the
The invention claimed is: current die shape to the result list, and then (e) determin
1. A computer-implemented method for optimizing a num ing whether all die shapes in the first list of die shapes
ber of dies that can be fabricated on a wafer, the computer have been evaluated;
implemented method comprising: 55 when the computed first number (Ni) of dies for the current
receiving input variables comprising: a minimum die width die shape is greater than the current maximum die num
(X), a minimum die height (yi), a target aspect ratio, ber (N) stored in the result list, then (d) clearing the
a target die area (A), a wafer area (A), an edge band result list and adding the computed first number (Ni) of
width (W), and a scribe width (W); dies for the current die shape, the current die shape and
executing a die number optimization (DNO) routine to 60 the current aspect ratio of the current die shape to the
determine a maximum number of dies (N) for the result list, and then (e) determining whether all die
target die area (A), wherein the DNO routine com shapes in the first list of die shapes have been evaluated;
prises: when the computed first number (Ni) of dies for the current
iteratively checking each die shape in a first list of die die shape is not greater than the current maximum die
shapes to determine which ones of the die shapes have 65 number (N) stored in the result list, then (e) deter
a maximum number of dies (N) for the target die mining whether all die shapes in the first list of die
area (A,e), and shapes have been evaluated;
 US 8,671,381 B1
19 20
if all die shapes in the first list of die shapes have not yet number of dies (N); and then () determining whether
been evaluated at Step (e), iteratively repeating steps (a) all die shapes in the second list of die shapes have been
through (e); evaluated;
after all die shapes in the first list of die shapes have been when it is determined at step () that all die shapes in the
evaluated at step (e), recording the result list as a final 5 second list of die shapes have not yet been evaluated,
result list, wherein the final result list comprises a plu iteratively repeating steps (f) through ();
rality of entries, each entry comprising: a particular die when it is determined at step () that all die shapes in the
shape for that entry, the maximum number of dies second list of die shapes have been evaluated, recording
(N), and a particular aspect ratio for that entry, the list of die shapes having the maximum die area
wherein the aspect ratio of each entry in the final result 10 (A) that that corresponds to the maximum number of
list is different. dies (N) computed during the DNO routine.
4. The computer-implemented method of claim 1, wherein 7. The computer-implemented method of claim 4, wherein
the DSO routine comprises a first DSO routine, the first DSO the DSO routine comprises a second DSO routine, the second
routine comprising: DSO routine comprising:
determining, while holding the maximum number of dies 15 decreasing the target die area (A) to generate a
(N) determined during the DNO routine at a fixed decreased target die area (A), and
number, the maximum die area (A) corresponding to then determining the first list of optimized die shapes,
the maximum number of dies (N). which have the maximum area utilization (AU), for the
5. The computer-implemented method of claim 4, wherein decreased target die area (A).
the step of determining, while holding the maximum number 8. The computer-implemented method of claim 7, wherein
of dies (N) determined during the DNO routine at the fixed decreasing the target die area (A) to generate the
number, the maximum die area (A) corresponding to the decreased target die area (A), comprises:
maximum number of dies (N), comprises: multiplying the target die area (A) by a second scaling
multiplying the target die area (A) by a first scaling factor to compute lower limit die area (A) based on the
factor to compute an upper limit die area (A) based on 25 target die area (A), and then computing, based on
the target die area (A), and then computing, based the lower limit die area (A), the minimum die width
on the upper limit die area (A), the minimum die width (X) and the minimum die height (yi), a third maxi
(X) and the minimum die height (yi), a second mum die width (X") and a third maximum die height
maximum die width (x) and a second maximum die (yna"); and
height (yi); and 30 generating a third list of die shapes that have the lower limit
generating a second list of die shapes that have an upper die area (A), based on the minimum die width (x),
limit die area (A), based on the minimum die width the minimum die height (y), the third maximum die
(X), the minimum die height (yi), the second maxi width (x") and the third maximum die height (y").
mum die width (x) and the second maximum die 9. The computer-implemented method of claim8, wherein
height (y). 35 the step of then determining the first list of optimized die
6. The computer-implemented method of claim 5, further shapes, which have the maximum area utilization (AU), for
comprising: the decreased target die area (A), comprises:
(f) selecting a next die shape from the second list of die (k) selecting a next die shape from the third list of die
shapes as a current die shape, and computing a second shapes as a current die shape, and computing a third
number (Nu) of dies for the current die shape from the 40 number (N1) of dies for the current die shape in the third
second list of die shapes; list of die shapes;
(g) determining whether the computed second number (1) computing a first area utilization value for the current
(Nul) of dies for the current die shape is equal to the die shape;
maximum number of dies (N) computed by the DNO (m) determining whether the first area utilization value or
routine; 45 the computed third number (N1) of dies for the current
when the computed second number (Nu) of dies for the die shape has increased from previously stored values;
current die shape is determined to be not equal to the when it is determined, at step (m), that neither the first area
maximum number of dies (N) that was computed utilization value nor the computed third number (N1) of
during the DNO routine, () determining whether all die dies for the current die shape has increased from previ
shapes in the second list of die shapes have been evalu 50 ously stored values, (o) determining whether all die
ated; shapes in the third list of die shapes have been evaluated;
when the computed second number (Nu) of dies for the when it is determined, at step (m), that either the first area
current die shape is determined to be equal to the maxi utilization value or the computed third number (N1) of
mum number of dies (N) that was computed during dies for the current die shape has increased from previ
the DNO routine, then (h) determining whether current 55 ously stored values, (n) storing the current die area asso
die area has increased in comparison to the target die ciated with the current die shape as a second result; and
area (A) when using the current die shape; then (o) determining whether all die shapes in the third
when the current die area is determined not to have list of die shapes have been evaluated;
increased in comparison to the target die area (A) when it is determined at step (o) that all die shapes in the
when using the current die shape, then () determining 60 third list of die shapes have not yet been evaluated,
whether all die shapes in the second list of die shapes iteratively repeating steps (k) through (n);
have been evaluated; when it is determined at step (o) that all die shapes in the
when the current die area is determined to have increased in third list of die shapes have been evaluated, recording
comparisonto the target die area (A) when using the the second results that are presently stored as the first list
current die shape, then (i) storing the current die shape as 65 of optimized die shapes, which have the maximum area
a first result in the list of die shapes having the maximum utilization (AU), for the decreased target die area
die area (A) and corresponding to the maximum (Aife get)
 US 8,671,381 B1
21 22
10. The computer-implemented method of claim 4, a second module configured to determine (1) a list ofdie
wherein the DSO routine comprises a third DSO routine, the shapes having a maximum die area (A) corre
third DSO routine comprising: sponding to the maximum number of dies (N), (2)
(p) selecting a next die shape from the second list of die a first list of optimized die shapes, which have a maxi
shapes as a current die shape, and computing a fourth 5 mum area utilization (AU), for a decreased target die
number (Nu') of dies for the current die shape from the area (A), and (3) a second list of optimized die
second list of die shapes; shapes, which have a minimum area utilization (AU),
(q) computing a second area utilization value for the cur for an increased target die area (A); and
rent die shape; a third module that generates a candidate list comprising
(r) determining whether the second area utilization value 10 a plurality of entries, wherein the plurality of entries
for the current die shape has decreased from a previously comprise: die shapes from the initial result list that
stored value; have the maximum number of dies (N) for the
when it is determined, at step (r), that the second area target die area (A), die shapes from the list of die
shapes having the maximum die area (A) corre
utilization value for the current die shape has not 15 sponding to the maximum number of dies (N), the
decreased from the previously stored value, (t) deter optimized die shapes from the first list of optimized
mining whether all die shapes in the second list of die die shapes, and the optimized die shapes from the
shapes have been evaluated; second list of optimized die shapes.
when it is determined, at step (r), that the second area 13. The system of claim 12, wherein iteratively checking
utilization value for the current die shape has decreased each die shape in the first list of die shapes to determine which
from the previously stored value, (s) storing the current ones of the die shapes have the maximum number of dies
die area associated with the current die shape as a third (N) for the target die area (A), comprises:
result; and then (t) determining whetherall die shapes in (a) selecting a next die shape from the first list of die shapes
the second list of die shapes have been evaluated; as a current die shape, and computing a first number (Ni)
when it is determined at step (r) that all die shapes in the 25 of dies for the current die shape from the first list of die
second list of die shapes have not yet been evaluated, shapes;
iteratively repeating steps (p) through (t): (b) determining whether the computed number (Ni) of dies
when it is determined at step (t) that all die shapes in the for the current die shape is greater than or equal to a
second list of die shapes have been evaluated, recording current maximum die number (N) stored in a result
the third results that are presently stored as the second 30 list;
list of optimized die shapes, which have the minimum when the computed first number (Ni) of dies for the current
area utilization (AU), for the increased target die area die shape is equal to the current maximum die number
(Arage). (N) stored in the result list, then (c) adding the com
11. The computer-implemented method of claim 1, further puted first number (Ni) of dies for the current die shape,
comprising: 35 the current die shape and a current aspect ratio of the
displaying a proposed wafer layout corresponding to one current die shape to the result list, and then (e) determin
of the entries from the candidate list, wherein the pro ing whether all die shapes in the first list of die shapes
posed wafer layout comprises a Suggested die area have been evaluated;
(x,y), a Suggested die height (X), a Suggested die width when the computed first number (Ni) of dies for the current
(y), a Suggested die aspect ratio (X/y), and the maxi 40 die shape is greater than the current maximum die num
mum number of dies (N). ber (N) stored in the result list, then (d) clearing the
12. A system for performing electronic design automation result list and adding the computed first number (Ni) of
tasks including optimizing a number of dies that can be fab dies for the current die shape, the current die shape and
ricated on a wafer, the system comprising: the current aspect ratio of the current die shape to the
a processor; 45 result list, and then (e) determining whether all die
a memory coupled to the processor, shapes in the first list of die shapes have been evaluated;
an input apparatus for inputting input variables, the input when the computed first number (Ni) of dies for the current
variables including a minimum die width (X), a mini die shape is not greater than the current maximum die
mum die height (yi), a target aspect ratio, a step size, a number (N) stored in the result list, then (e) deter
target die area (A), a wafer area (A), an edge band 50 mining whether all die shapes in the first list of die
width (W), and a scribe width (W); and shapes have been evaluated;
a computer program having a plurality of software mod when it is determined that all die shapes in the first list of
ules, including: die shapes have not yet been evaluated at Step (e), itera
a first module configured to compute a first maximum tively repeating steps (a) through (e);
die width (x) and a first maximum die height 55 when it is determined that all die shapes in the first list of
(y), to generate a first list of die shapes that have die shapes have been evaluated at step (e), recording the
the target die area (A.), based on the minimum die result list as a final result list, wherein the final result list
width (x), the minimum die height (y,z), the comprises a plurality of entries, wherein each entry com
maximum die width (x) and the maximum die prises: a particular die shape for that entry, the maximum
height (y), to determine a maximum number of 60 number of dies (N), and a particular aspect ratio for
dies (N) for the target die area (A) by itera that entry, wherein the aspect ratio of each entry in the
tively checking each die shape in a first list of die final result list is different.
shapes to determine which ones of the die shapes have 14. The system of claim 12, wherein the second module is
the maximum number of dies (N) for the target die configured to determine the list of die shapes having the
area (A), and to generate an initial result list of 65 maximum die area (A) corresponding to the maximum
die shapes that have the maximum number of dies number of dies (N) while holding the maximum number of
(N) for the target die area (Aife get) dies (N) at a fixed number by:
 US 8,671,381 B1
23 24
multiplying the target die area (A) by a first scaling (k) selecting a next die shape from the third list of die
factor to compute an upper limit die area (A) based on shapes as a current die shape, and computing a third
the target die area (A), and then computing, based number (N1) of dies for the current die shape in the third
on the upper limit die area (A), the minimum die width list of die shapes;
(X) and the minimum die height (yi), a second 5 (1) computing a first area utilization value for the current
maximum die width (x) and a second maximum die die shape;
height (yi); (m) determining whether the first area utilization value or
generating a second list of die shapes that have the upper the computed third number (N1) of dies for the current
limit die area (A), based on the minimum die width die shape has increased from previously stored values;
(X), the minimum die height (y,z), the second maxi 10 when it is determined, at step (m), that neither the first area
mum die width (x) and the second maximum die utilization value nor the computed third number (N1) of
height (yi); dies for the current die shape has increased from previ
(f) selecting a next die shape from the second list of die ously stored values, (o) determining whether all die
shapes as a current die shape, and computing a second shapes in the third list of die shapes have been evaluated;
15 when it is determined, at step (m), that either the first area
number (Nu) of dies for the current die shape from the utilization value or the computed third number (N1) of
second list of die shapes; dies for the current die shape has increased from previ
(g) determining whether the computed second number ously stored values, (n) storing the current die area asso
(Nul) of dies for the current die shape is equal to the ciated with the current die shape as a second result; and
maximum number of dies (N): then (o) determining whether all die shapes in the third
when the computed second number (Nu) of dies for the list of die shapes have been evaluated;
current die shape is determined to be not equal to the when it is determined at step (o) that all die shapes in the
maximum number of dies (N), () determining third list of die shapes have not yet been evaluated,
whether all die shapes in the second list of die shapes iteratively repeating steps (k) through (n);
been evaluated; 25 when it is determined at step (o) that all die shapes in the
when the computed second number (Nu) of dies for the third list of die shapes have been evaluated, recording
current die shape is determined to be equal to the maxi the second results that are presently stored as the first list
mum number of dies (N), then (h) determining of optimized die shapes, which have the maximum area
whether current die area has increased in comparison to utilization (AU), for the decreased target die area
the target die area (A) when using the current die 30 (Arage).
shape; 16. The system of claim 12, wherein the second module is
when the current die area is determined not to have configured to determine (the second list of optimized die
increased in comparison to the target die area (A) shapes, which have the minimum area utilization (AU), for
when using the current die shape, then () determining the increased target die area (A) by:
whether all die shapes in the second list of die shapes 35 (p) selecting a next die shape from the second list of die
been evaluated; shapes as a current die shape, and computing a fourth
when the current die area is determined to have increased in number (Nu') of dies for the current die shape from the
comparisonto the target die area (A) when using the second list of die shapes;
current die shape, then (i) storing the current die shape as (q) computing a second area utilization value for the cur
a first result in the list of die shapes having the maximum 40 rent die shape;
die area (A) and corresponding to the maximum (r) determining whether the second area utilization value
number of dies (N); and then () determining whether for the current die shape has decreased from a previously
all die shapes in the second list of die shapes have been stored value;
evaluated; when it is determined, at step (r), that the second area
when it is determined at step () that all die shapes in the 45 utilization value for the current die shape has not
second list of die shapes have not yet been evaluated, decreased from the previously stored value, (t) deter
iteratively repeating steps (f) through (); mining whether all die shapes in the second list of die
when it is determined at step () that all die shapes in the shapes have been evaluated;
second list of die shapes have been evaluated, recording when it is determined, at step (r), that the second area
the list of die shapes having the maximum die area 50 utilization value for the current die shape has decreased
(Anax) that that corresponds to the maximum number of from the previously stored value, (s) storing the current
dies (N). die area associated with the current die shape as a third
15. The system of claim 12, wherein the second module is result; and then (t) determining whetherall die shapes in
configured to determine the first list of optimized die shapes, the second list of die shapes have been evaluated:
which have the maximum area utilization (AU), for the 55 when it is determined at step (r) that all die shapes in the
decreased target die area (A) by: second list of die shapes have not yet been evaluated,
multiplying the target die area (Atarge) by a second scaling iteratively repeating steps (p) through (t):
factor to compute lower limit die area (A) based on the when it is determined at step (t) that all die shapes in the
target die area (Atarge), and then computing, based on second list of die shapes have been evaluated, recording
the lower limit die area (A), the minimum die width 60 the third results that are presently stored as the second
(X) and the minimum die height (yi), a third maxi list of optimized die shapes, which have the minimum
mum die width (X") and a third maximum die height area utilization (AU), for the increased target die area
(y,a"): (Arage).
generating a third list of die shapes that have the lower limit 17. The system of claim 12, further comprising:
die area (A), based on the minimum die width (x), 65 a display for displaying at least one of:
the minimum die height (yi), the third maximum die a proposed wafer layout corresponding to one of the
width (X") and the third maximum die height (y"); entries from the candidate list, the proposed wafer
 US 8,671,381 B1
25 26
layout comprising: a Suggested die area (x,y), a Sug when the computed first number (Ni) of dies for the current
gested die height (X), a suggested die width (y), a die shape is equal to the current maximum die number
Suggested die aspect ratio (X/y), and the maximum (N) stored in the result list, then (c) adding the com
number of dies (N); and puted first number (Ni) of dies for the current die shape,
an image that includes a wafer having the proposed the current die shape and a current aspect ratio of the
wafer layout. current die shape to the result list, and then (e) determin
18. A computer program product for use with a computer, ing whether all die shapes in the first list of die shapes
the computer program product comprising a non-transitory have been evaluated;
computer-readable storage medium comprising computer when the computed first number (Ni) of dies for the current
executable instructions stored thereon for optimizing a num 10
die shape is greater than the current maximum die num
ber of dies that can be fabricated on a wafer, the computer ber (N) stored in the result list, then (d) clearing the
executable instructions performing steps comprising: result list and adding the computed first number (Ni) of
receiving input variables comprising: a minimum die width
(X), a minimum die height (yi), a target aspect ratio, dies for the current die shape, the current die shape and
a step size, a target die area (A), a wafer area (A), 15 the current aspect ratio of the current die shape to the
an edge band width (w), and a scribe width (w); and result list, and then (e) determining whether all die
executing a die number optimization (DNO) routine to shapes in the first list of die shapes have been evaluated;
compute a first maximum die width (x) and a first when the computed first number (Ni) of dies for the current
maximum die height (y), to generate a first list of die die shape is not greater than the current maximum die
shapes that have the target die area (A.), based on the number (N) stored in the result list, then (e) deter
minimum die width (x), the minimum die height mining whether all die shapes in the first list of die
(y), the maximum die width (X, ) and the maximum shapes have been evaluated;
die height (y), and to determine a maximum number when it is determined that all die shapes in the first list of
of dies (N) for the target die area (A), wherein die shapes have not yet been evaluated at Step (e), itera
the DNO routine comprises: iteratively checking each 25 tively repeating steps (a) through (e);
die shape in a first list of die shapes to determine which when it is determined that all die shapes in the first list of
ones of the die shapes have the maximum number of dies die shapes have been evaluated at step (e), recording the
(N) for the target die area (A); and result list as a final result list, wherein the final result list
executing a die size optimization (DSO) routine to deter comprises a plurality of entries, wherein each entry com
mine (1) a list of die shapes having a maximum die area 30
prises: a particular die shape for that entry, the maximum
(A) corresponding to the maximum number of dies number of dies (N), and a particular aspect ratio for
(N), (2) a first list of optimized die shapes, which that entry, wherein the aspect ratio of each entry in the
have a maximum area utilization (AU), for a decreased final result list is different.
target die area (A), and (3) a second list of optimized 20. A computer program product according to claim 18,
die shapes, which have a minimum area utilization (AU), 35
wherein the computer-executable instructions perform steps
for an increased target die area (A), comprising further comprising:
wherein the DSO routine comprises a first DSO routine
comprising: (f) selecting a next die shape from the second list of die
determining, while holding the maximum number of dies shapes as a current die shape, and computing a second
(N) determined during the DNO routine at a fixed 40 number (Nu) of dies for the current die shape from the
number, the maximum die area (A) corresponding to second list of die shapes;
the maximum number of dies (N), by: (g) determining whether the computed second number
multiplying the target die area (A) by a first scaling (Nul) of dies for the current die shape is equal to the
factor to compute an upper limit die area (A) based maximum number of dies (N) that was computed
on the target die area (A), and then computing, 45 during the DNO routine;
based on the upper limit die area (A), the minimum when the computed second number (Nul) of dies for the
die width (x) and the minimum die height (yi), a current die shape is determined to be not equal to the
second maximum die width (x) and a second maximum number of dies (N) that was computed
maximum die height (yi); and during the DNO routine, (j) determining whether all die
generating a second list of die shapes that have the upper 50 shapes in the second list of die shapes have been evalu
limit die area (A), based on the minimum die width ated;
(X), the minimum die height (yi), the second when the computed second number (Nul) of dies for the
maximum die width (x) and the second maximum current die shape is determined to be equal to the maxi
die height (y). mum number of dies (N) that was computed during
19. A computer program product according to claim 18, 55 the DNO routine, then (h) determining whether current
wherein the step of iteratively checking each die shape in the die area has increased in comparison to the target die
first list of die shapes to determine which ones of the die area (A) when using the current die shape;
shapes have the maximum number of dies (N) for the when the current die area is determined not to have
target die area (A), comprises: increased in comparison to the target die area (A)
(a) selecting a next die shape from the first list of die shapes 60 when using the current die shape, then () determining
as a current die shape, and computing a first number (Ni) whether all die shapes in the second list of die shapes
of dies for the current die shape from the first list of die have been evaluated;
shapes; when the current die area is determined to have increased in
(b) determining whether the computed number (Ni) of dies comparisonto the target die area (A) when using the
for the current die shape is greater than or equal to a 65 current die shape, then (i) storing the current die shape as
current maximum die number (N) stored in a result a first result in the list of die shapes having the maximum
list; die area (A) and corresponding to the maximum
 US 8,671,381 B1
27 28
number of dies (N); and then () determining whether when it is determined, at step (m), that either the first area
all die shapes in the second list of die shapes have been utilization value or the computed third number (N1) of
evaluated; dies for the current die shape has increased from previ
when it is determined at step () that all die shapes in the ously stored values, (n) storing the current die area asso
second list of die shapes have not yet been evaluated, 5 ciated with the current die shape as a second result; and
iteratively repeating steps (f) through (); then (o) determining whether all die shapes in the third
when it is determined at step () that all die shapes in the list of die shapes have been evaluated;
second list of die shapes have been evaluated, recording when it is determined at step (o) that all die shapes in the
the list of die shapes having the maximum die area third list of die shapes have not yet been evaluated,
(A) that that corresponds to the maximum number of 10 iteratively repeating steps (k) through (n);
dies (N) computed during the DNO routine. when it is determined at step (o) that all die shapes in the
21. A computer program product according to claim 18,
wherein the DSO routine comprises a second DSO routine, third list of die shapes have been evaluated, recording
the second DSO routine comprising: the second results that are presently stored as the first list
decreasing the target die area (A) to generate a 15 of optimized die shapes, which have the maximum area
decreased target die area (A), and utilization (AU), for the decreased target die area
then determining the first list of optimized die shapes, (Atarge).
which have the maximum area utilization (AU), for the 24. A computer program product according to claim 21,
decreased target die area (A). wherein the DSO routine comprises a third DSO routine, the
22. A computer program product according to claim 21, 20 third DSO routine comprising:
wherein decreasing the target die area (A) to generate the (p) selecting a next die shape from the second list of die
decreased target die area (A), comprises: shapes as a current die shape, and computing a fourth
multiplying the target die area (A) by a second scaling number (Nu') of dies for the current die shape from the
factor to compute lower limit die area (A) based on the second list of die shapes;
target die area (A), and then computing, based on 25 (q) computing a second area utilization value for the cur
the lower limit die area (A), the minimum die width rent die shape;
(X) and the minimum die height (yi), a third maxi (r) determining whether the second area utilization value
mum die width (X") and a third maximum die height for the current die shape has decreased from a previously
(yna"); and stored value;
generating a third list of die shapes that have the lower limit 30 when it is determined, at step (r), that the second area
die area (A), based on the minimum die width (x), utilization value for the current die shape has not
the minimum die height (y), the third maximum die decreased from the previously stored value, (t) deter
width (x") and the third maximum die height (y"). mining whether all die shapes in the second list of die
23. A computer program product according to claim 22,
wherein the step of then determining the first list of optimized 35 shapes have been evaluated;
die shapes, which have the maximum area utilization (AU), when it is determined, at step (r), that the second area
for the decreased target die area (A), comprises: utilization value for the current die shape has decreased
(k) selecting a next die shape from the third list of die from the previously stored value, (s) storing the current
shapes as a current die shape, and computing a third die area associated with the current die shape as a third
number (N1) of dies for the current die shape in the third 40 result; and then (t) determining whetherall die shapes in
list of die shapes; the second list of die shapes have been evaluated:
(1) computing a first area utilization value for the current when it is determined at step (r) that all die shapes in the
die shape; second list of die shapes have not yet been evaluated,
(m) determining whether the first area utilization value or iteratively repeating steps (p) through (t):
the computed third number (N1) of dies for the current 45 when it is determined at step (t) that all die shapes in the
second list of die shapes have been evaluated, recording
die shape has increased from previously stored values;
when it is determined, at step (m), that neither the first area the third results that are presently stored as the second
utilization value nor the computed third number (N1) of list of optimized die shapes, which have the minimum
dies for the current die shape has increased from previ area utilization (AU), for the increased target die area
ously stored values, (o) determining whether all die 50 (Aife get)
shapes in the third list of die shapes have been evaluated;