Ex Parte Brennan et al

Board of Patent Appeals and Interferences

Sep 25, 2008

11138835 (B.P.A.I. Sep. 25, 2008)

UNITED STATES PATENT AND TRADEMARK OFFICE
_____________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
_____________

Ex parte THOMAS CHARLES BRENNAN,
and
TODD ALAN GREENFIELD
_____________

Appeal 2008-3591
Application 11/138,835
Technology Center 2800
______________

Decided: September 25, 2008
_______________

Before JOHN C. MARTIN, ROBERT E. NAPPI, and
SCOTT R. BOALICK, Administrative Patent Judges.

MARTIN, Administrative Patent Judge.

DECISION ON APPEAL
STATEMENT OF THE CASE
This is an appeal under 35 U.S.C. § 134(a) from the Examiner’s
rejection of claims 1-12 under 35 U.S.C. § 103(a).
Appeal 2008-3591
Application 11/138,835

2
We have jurisdiction under 35 U.S.C. § 6(b).
We REVERSE.

A. Appellants’ invention
Appellants’ invention is an improved method for modifying existing
integrated circuit designs (Specification [0001]).
Modifying integrated circuit designs presents designers with a new
problem (id. at [0004]). During a redesign, integrated circuit designers
frequently add new circuit elements and interconnects, which may crowd the
existing design and can introduce crosstalk noise problems into the
integrated circuit design (id.).
Appellants’ invention provides a way to identify problem areas within
an integrated circuit design that are susceptible to crosstalk noise (id. at
[0006]) in order to isolate any identified problem networks from any circuit
elements or interconnects that are added during the redesign process (id. at
[0019]). The Specification explains that the terms “interconnect,” “wire,”
and “network” are used interchangeably (id. at [0019]).

Appeal 2008-3591
Application 11/138,835

3
Appellants’ Figure 3A is reproduced below.

Figure 3A is a block diagram depicting an integrated circuit in which
a preferred embodiment of the invention may be implemented (id. at
[0012]).
As illustrated, integrated circuit design 300 includes a collection of
driver circuits 302a and 302b, a collection of wires 304a, 304b, and 310, and
a collection of circuits 306, 308, 314, and 318 (id. at [0022]).
Appellants’ process begins by identifying problem networks. A
problem network includes any wire and all associated branches whose length
cumulatively equals or exceeds WLEN, which is a predetermined threshold
noisy wire length (id. at [0022]). For example, a threshold noisy wire length
(WLEN) may be set at 1 mm, in which case any network that equals or
Appeal 2008-3591
Application 11/138,835

4
exceeds 1 mm will be considered a problem network (id.). The value of
WLEN is defined by a user and varies depending on the particular integrated
circuit design (id. at [0025])).
Identification of the problem networks “may be performed by a
computer, which may calculate the length of each wire and all associated
branches utilizing a software package that enables the computer to analyze
integrated circuit designs, or by the user” (id. at [0026]). For purposes of
discussion, the Specification assumes that wires 304a and 304b in Figure 3A
have been identified as problem networks (id. at [0023]).
Next, drivers 302a and 302b, which are coupled to these problem
networks, are replaced with drivers of lesser driving capacity (id.), which
make these problem networks more susceptible to noise and crosstalk (id. at
[0026]). Replacement of the drivers is followed by retesting the entire
integrated circuit design 300 (id. at [0023]). If this testing identifies any
timing problems on any of the identified problem networks, the problem
networks are isolated in the manner discussed below.

Appeal 2008-3591
Application 11/138,835

5

Appellants’ Figure 3B is reproduced below.

Figure 3B shows how to isolate problem networks that are identified
as having timing errors in the foregoing testing (id. at [0024]).
A portion of problem network 304a is “symmetrically” isolated, i.e.,
isolated on both sides, by spaces 302 in which new wires or circuit elements
may not be routed during a redesign (id.). On the other hand, a portion of
problem network 304b is “asymmetrically” isolated, i.e., isolated on only
one side, by a space 322 in which new wires and circuit elements may not be
placed in a redesign (id.).

B. The claims
The independent claims are claims 1 and 7, of which claim 1 reads:
1. A method modifying an integrated circuit design,
comprising:
Appeal 2008-3591
Application 11/138,835

6
identifying at least one problem network within an
integrated circuit design that equals or exceeds a threshold
noisy wire length;
temporarily replacing a first driver circuit coupled to said
at least one problem network with a second driver circuit with
lesser drive capacity;
in response to said temporarily replacing said first driver,
testing said integrated circuit design to identify at least one
network that exceeds a noise threshold; and
in response to identifying said at least one network,
isolating, from future modification of said integrated circuit
design, at least one portion of said at least one network, wherein
said future modifications introduce noise problems that lead to
timing problems within said integrated circuit design.
Claims App., Br. 7.

C. The references and rejection
The Examiner relies on the following references:

Mehrotra et al. (Mehrotra) US 6,601,222 B1 July 29, 2003
Tetelbaum US 2005/0060675 A1 March 17, 2005

Claims 1-12 stand rejected under 35 U.S.C. § 103(a) for obviousness
over Mehrotra in view of Tetelbaum.

THE ISSUE
The issue is whether Appellants have shown reversible error by the
Examiner in maintaining the rejection. See In re Kahn, 441 F.3d 977, 985-
Appeal 2008-3591
Application 11/138,835

7
86 (Fed. Cir. 2006) (“On appeal to the Board, an applicant can overcome a
rejection by showing insufficient evidence of prima facie obviousness or by
rebutting the prima facie case with evidence of secondary indicia of
nonobviousness.”) (quoting In re Rouffet, 149 F.3d 1350, 1355 (Fed. Cir.
1998)).
Appellants contend that the Examiner erred in finding that Mehrotra
discloses or suggests the first step of claim 1 (“identifying at least one
problem network within an integrated circuit design that equals or exceeds a
threshold noisy wire length”) and the corresponding recitation in
independent claim 7.
ANALYSIS
A. Principles of law
“[T]he examiner bears the initial burden, on review of the prior art or
on any other ground, of presenting a prima facie case of unpatentability.” In
re Oetiker, 977 F.2d 1443, 1445 (Fed. Cir. 1992). A rejection under
35 U.S.C. § 103(a) must be based on the following factual determinations:
(1) the scope and content of the prior art; (2) the level of ordinary skill in the
art; (3) the differences between the claimed invention and the prior art; and
(4) any objective indicia of non-obviousness. DyStar Textilfarben GmbH &
Co. Deutschland KG v. C.H. Patrick Co., 464 F.3d 1356, 1360 (Fed. Cir.
2006) (citing Graham v. John Deere Co., 383 U.S. 1, 17 (1966)).

Appeal 2008-3591
Application 11/138,835

8
B. Mehrotra
Mehrotra relates in general to circuit interconnects (nets) and in
particular to a method for efficient routing of nets of a circuit (Mehrotra,
col. 1, ll. 8-10).
In Mehrotra’s “Description of Related Prior Art” (cols. 1-2), on which
the rejection is partly based, Mehrotra describes the disadvantages of the
prior-art technique of worst-case modeling, in which all wire lengths are
constrained so as not to exceed a threshold length where noise coupling may
disturb a receiver connected to the net:
Fixing the coupling problems after the detailed routing
requires at least a new routing and another extraction and noise
verification. Since the noise-analysis and subsequent
adjustments occur late in the design cycle, the noise analysis
and correction has a severe impact on the product release
schedule.
Thus, methods are required to assess potential coupling
noise problems early in the design cycle. The task is very
difficult since the data needed for noise analysis is only
available very late in the design cycle. Hence, most designers
resort to a worst case analysis. Under the worst case analysis,
each wire (net) is assumed to be coupled to wires on either side
at the minimum permissible spacing. Accordingly, the wire
length is constrained such that it does not exceed a threshold
length where the worst-case coupling may disturb any of the
receivers connected to the net. Under the analysis, the
maximum wire length is usually very pessimistic for of most
nets because of the conservative coupling assumption. Also, to
keep wire length below the maximum wire length, buffers are
inserted periodically in the net, and the driver size may be
increased (a larger driver will have a longer wire threshold
Appeal 2008-3591
Application 11/138,835

9
length). Both of the above actions result in higher power
consumption and may also have an adverse effect on chip
timing.
Traditionally, the worst-case model is utilized to make all
decisions (spacing, shielding, buffering) and leads to quite a
few post-design fails. Use of the worst-case model leads to
significant over-design, because a lot of nets which would not
have noise problems after layout are constrained through
buffering or shielding.
Mehrotra, col. 1, l. 60 to col. 2, l. 22 (emphasis added).
Mehrotra’s invention is a method for estimating and subsequently
reducing coupled noise in nets during preliminary design (i.e., global
routing) of a circuit (Mehrotra, col. 1, ll. 10-14), which occurs prior to
detailed routing (id., col. 3, ll. 29-30), i.e., the process of specifically
determining how to connect nets of a IC chip (or other circuit) to logic
components of the circuit (id., col. 5, ll. 13-15).
Global routing entails dividing the chip layout area into rectangular
“tiles” (id., col. 4, ll. 1-12). Each tile 201 (Fig. 2) is evaluated for available
wire density by counting the total number of wiring tracks available on all
the wiring layers in the tile area (id., col. 4, ll. 26-29). Typically, wiring is
routed in two orthogonal directions, and each wiring layer has a preferred
direction (id., col. 6, ll. 29-30).
Following the evaluation of available wiring density, a global routing
tool 24 (Fig. 1) subtracts from the total wiring availability all blockages due
to circuit wiring, clocks, power and ground, pre-routed nets, and nets that
have all their connections on a single tile (id., col. 4, ll. 33-37). The
Appeal 2008-3591
Application 11/138,835

10
remaining tracks are the tracks available for the global wiring of the chip
200 (i.e., placement/routing of nets) (id., col. 4, ll. 37-39). Global routing
tool 24 then undertakes the task of connecting all the chip wires over the
global tile map such that the number of wires crossing a tile in a given
direction are fewer than the number of available tracks in the tile in that
direction, with no attempt being made to resolve the actual track that any
given wire is going to occupy (id., col. 4, ll. 40-45).
In addition to allocating global paths for each net, Mehrotra’s
invention provides enhanced features to the global routing tool by which the
results of a noise analysis typically available after detailed routing are made
available before actually completing a detailed routing (id., col. 4, ll. 52-56).
Figure 3A is a flow chart illustrating the steps of the process of
completing an estimated noise analysis in accordance with one embodiment
of Mehrotra’s invention (id., col. 5, ll. 27-29). In the preferred embodiment,
the parameters utilized in the noise analysis include aggressor capacitance,
drive strength of aggressor, transmission times, and switching windows (id.,
col. 2, ll. 49-52).
Figure 3B illustrates the process of evaluating worse case and average
case models for each parameter utilized in the noise analysis (id., col. 5, ll.
37-39). The process begins at block 351, and the aggressor capacitance (i.e.,
the capacitance of each aggressor net) for each net is assigned at block 353,
which entails computing the average coupling strength and the worst case
coupling strength of adjacent (parallel) nets (id., col. 5, ll. 40-45). Each wire
Appeal 2008-3591
Application 11/138,835

11
segment has two adjacent aggressors, one on either side (id., col. 5, ll. 45-
46). The average strength of the coupling is evaluated probabilistically and
the worst case strength of the coupling is evaluated assuming that
neighboring wires are located at a minimum pitch on either side (id., col. 5,
ll. 46-51).
Following the computation of aggressor capacitance, all the nets
crossing a tile are examined to determine the fastest transition time and the
average transition time at that tile at block 357 (id., col. 5, ll. 64-67). The
calculation of the transition time entails first determining the worst-case and
average value of drive strength for each aggressor (id., col. 5, l. 67 to col. 6,
l. 2). A similar analysis is completed for signal switching windows at block
359 (id., col. 6, ll. 12-13).
Utilizing the assigned values for aggressor capacitance, transition
times, and switching windows, worst-case and an average-case models for
noise analysis are derived for each net (id., col. 6, ll. 17-20).
As shown in Figure 3A, these models are used in performing three
different types of noise analysis for each net (id., col. 6, ll. 21-56). If a net
fails the third noise analysis, which is performed only if the net has also
failed the first and second analyses (id., col. 6, ll. 34-35, 49-50), “an
assumption is made and a routing code recorded that the net needs to be
shielded from the neighboring nets at block 327” (id., col. 6, ll. 58-60). Two
shielding mechanisms are described: “(1) increasing spacing between the net
and the neighboring nets and (2) placing the net next to a non-switching line,
Appeal 2008-3591
Application 11/138,835

12
e.g., a power supply wire” (id., col. 6, l. 66 to col. 7, l. 2). In the preferred
embodiment, mechanism (2) is preferred over mechanism (1) (id., col. 7,
ll. 10-13).
If mechanism (2) is not feasible (id., col. 7, ll. 25-30), a determination
is made at block 411 (Fig. 4) of whether additional spacing exists in all the
tiles 21 that include the problem net (id., col. 7, ll. 36-38). If additional
spacing is not available in all of the tiles 21 that are traversed by the problem
net, global routing tool 24 is invoked at blocks 415 and 417 to find a next
(i.e., alternative) embedding for the problem net (id., col. 7, ll. 41-44). If a
next embedding is found with no significant wire length penalty, the next
embedding is assigned to the problem net (id., col. 46-47). If a next
embedding is not found, the problem net is considered to have a real noise
failure and is tagged as a candidate for repeater insertion in order to shorten
the coupled length at block 419 (id., col. 7, ll. 48-51).
In the Final Action, the Examiner read the first step of claim 1 on
Mehrotra’s discussion of the related prior art (i.e., on column 2, lines 5-8)
and on Mehrotra’s illustrative embodiment (at columns 3 and 7; Fig. 4),
finding that
Mehrotra teaches, in Col 3 lines 22-23, identifying at least one
problem network within an integrated circuit design (i.e.
“identifying nets which could potentially have a problem due to
coupling noise”). Further, Mehrotra teaches exceeding a
threshold noisy wire length in Col 2 lines 5-8 (i.e., “wire length
is constrained such that it does not exceed a threshold length
where the worst case coupling may disturb any of the receivers
Appeal 2008-3591
Application 11/138,835

13

connected to the net”). Even furthermore, the above-mentioned
limitation is disclosed/implemented by block 419 in Fig 4 of
Mehrotra, i.e., Col 7 lines 49-52: “The problem net ..... shorten
the coupled length at block 419”.
Final Action 6-7.1
Appellants responded by arguing that the wire lengths described at
column 2, lines 6-8 of Mehrotra are constrained so as not to exceed the
threshold wire length and that Mehrotra’s identification of problem networks
is based only on a threshold noise level:
When taken as a whole, Mehrotra discloses a method for
pre-design estimation of coupling noise and avoidance of
coupling noise failures in interconnects. (Abstract). Wire
length is constrained so that none of the wires in the design
exceed a threshold length. (Summary [sic, “Description of the
Related Art”], col. 2, lines 6-8). The cited text merely discloses
that a wire length is constrained so that the wire length does not
exceed a threshold length. This constraint indicates that the
threshold length is an absolute maximum wire length that
cannot be exceeded. In col. 2, lines 35-45 [“Summary of the
Invention”], Mehrotra merely discloses a determination made
as to whether coupling noise of any one of the nets is above a
threshold level utilizing worst case and average-case models. If
the coupling noise of any one of the nets is above a threshold
level, the system disclosed in Mehrotra teaches changing wire
spacing configurations of the nets.
Br. 5.2

(Continued on next page.)
1 The Examiner does not rely on Tetelbaum for the first step of
claim 1 or the corresponding limitation in independent claim 7.
2 Appellants also asserted that “[n]othing disclosed in Mehrotra
Appeal 2008-3591
Application 11/138,835

14
The Examiner responded by stating that “[c]ol 2 lines 5-15 of
Mehrotra suggests that one way to determine whether a net in Mehrotra is
above a threshold level for noise-induced failure is to determine whether a
net exceeds a threshold length (i.e. exceed a threshold length, see Mehrotra,
Col 2 lines 5-10)” (Answer 10-11) and that “[t]herefore, Mehrotra does in
fact result in an identification of a network based on wire length” (id. at 11).
In view of these statements, we understand the Examiner’s position to be
that at least one of Mehrotra’s three noise analyses, which are used to
determine whether the coupling noise of a net under analysis exceeds the
“noise failure threshold” (Mehrotra, col. 6, l. 28) and thus is a problem net,
inherently is (or obviously could have been) carried out by comparing the
length of the net to a threshold length corresponding to a threshold noise
level. The Examiner’s reasoning does not persuade us that a comparison of
wire lengths is inherent in any of Mehrotra’s noise analyses or would have
been an obvious modification thereof. The Examiner’s reasoning is
unconvincing because it fails to address the fact that Mehrotra’s noise
analyses preferably employ the parameters of aggressor capacitance, drive
strength of aggressor, transmission times, and switching windows (id., col.
2, ll. 49-52) and the fact that Mehrotra faults the prior-art technique of

(Continued on next page.)
teaches performing any function after constraining the wire length in the
integrated circuit design below a threshold length” (Br. 5), to which the
Examiner correctly responded (Answer 7-8) that the assertion fails to take
into account Mehrotra’s disclosure in column 2, lines 40-50 of the response
Appeal 2008-3591
Application 11/138,835

15

constraining wire lengths to a threshold wire length as having a number of
disadvantages (id., col. 2, ll. 8-22), such as the need for buffers and larger
drivers to keep the wire lengths below the maximum length (id., col. 2, ll.
11-14).
The Examiner’s alternative reliance on block 419 (Fig. 4) and
column 7, lines 49-52 is also misplaced. The sentence that appears in those
lines reads in full as follows: “If, however, a next embedding is not found,
the problem net is considered to have a real noise failure and is tagged as a
candidate for repeater insertion to shorten the coupled length at block 419.”
Assuming for the sake of argument that the decision to insert a repeater
involves comparing the problem net to some reference length, such a
comparison is not used for the purpose of identifying a problem link, as
required by the claim language; the problem link is identified prior to
determining whether a repeater should be inserted therein.
For the foregoing reasons, we agree with Appellants that the Examiner
has failed to demonstrate that Mehrotra discloses or suggests the first step of
claim 1 (“identifying at least one problem network within an integrated
circuit design that equals or exceeds a threshold noisy wire length”) and the
corresponding limitation in independent claim 7.

DECISION

mechanisms triggered when a net fails to satisfy the noise-failure threshold.
Appeal 2008-3591
Application 11/138,835

16
The rejection of claims 1-12 under 35 U.S.C. § 103(a) for obviousness
over Mehrotra in view of Tetelbaum is reversed.

REVERSED

rvb

IBM CORPORATION
3605 Highway 52 North
Dept. 917
Rochester, MN 55901-7829