ATopTech, Inc.v.Synopsys, Inc.

Patent Trial and Appeal Board

Jan 21, 2015

09301143 (P.T.A.B. Jan. 21, 2015)

Trials@uspto.gov Paper 7
571-272-7822 Entered: January 21, 2015

UNITED STATES PATENT AND TRADEMARK OFFICE
____________

BEFORE THE PATENT TRIAL AND APPEAL BOARD
____________

ATOPTECH, INC.,
Petitioner,

v.

SYNOPSYS, INC.
Patent Owner.

Case IPR2014-01153
Patent 6,507,941 B1

Before TRENTON A. WARD, PETER P. CHEN, and FRANCES L.
IPPOLITO, Administrative Patent Judges.

CHEN, Administrative Patent Judge.

DECISION
Denying Institution of Inter Partes Review
37 C.F.R. § 42.108

IPR2014-01153
Patent 6,507,941 B1

2

I. INTRODUCTION

ATopTech, Inc. (“Petitioner”) filed a Petition requesting an inter
partes review of claims 1–14, 16–20, 26–37, and 39–45 of U.S. Patent No.
6,507,941 (Ex. 1001, “the ’941 patent”). Paper 1 (“Pet.”). Synopsys, Inc.
(“Patent Owner”) filed a Preliminary Response. Paper 6 (“Prelim. Resp.”).
We have statutory authority under 35 U.S.C. § 314, which provides that an
inter partes review may not be instituted “unless . . . there is a reasonable
likelihood that the petitioner would prevail with respect to at least 1 of the
claims challenged in the petition.”
Upon consideration of the Petition, we are not persuaded Petitioner
has demonstrated a reasonable likelihood that it would prevail in showing
the unpatentability of any of the challenged claims of the ’941 patent.
Accordingly, we do not institute an inter partes review of these claims.
A. Related Proceedings
On June 26, 2013, Patent Owner filed a Complaint against Petitioner
in the U.S. District Court for the Northern District of California, alleging
infringement of the ’941 patent. Synopsys, Inc. v ATopTech, Inc., Case No.
3:13-cv-02965-MMC (N.D. Cal.). Pet. 1. In addition, Petitioner has filed
Petitions challenging the patentability of certain claims of Patent Owner’s
U.S. Patent Nos. 6,237,127 (IPR2014-01145), 6,567,967 (IPR2014-01150
and IPR2014-01159), and 6,405,348 (IPR2014-01160).

IPR2014-01153
Patent 6,507,941 B1

3

B. The ’941 Patent
The subject matter of the challenged claims of the ’941 patent relates
generally to a router for designing integrated circuits (ICs), and in particular,
a subgrid detailed router. Ex. 1001, Abstract. Routing is the term used to
describe placing wires into locations on an IC. Id. at 1:10–12. Grid based
routing systems use global routing and detailed routing to place wires into
locations on an IC. Id. at 1:10–36. In a conventional grid based detailed
routing system, different layers in an IC are represented in the detailed
routing grid. Id. at 1:39–41. Figure 2 of the ’941 patent is reproduced
below.

IPR2014-01153
Patent 6,507,941 B1

4

Figure 2 depicts one layer of a routing grid, subdivided into grid pattern 10
having separate grids 12. Id. at 1:46–48. For simpler designs, the ’941
patent states that the size of the grid – the separation between grid points –
could be made relatively large. Id. at 3:57–59. More complex designs
required reduction in grid size and a significant increase in the number of
grid points and in the time needed to traverse a path. Id. at 3:65–4:2; see
also Pet. 6. Figure 5 of the ’941 patent is reproduced below.

In Figure 5, grid 10 of Figure 2, which had a single grid square 12 per unit
area, is quadrupled in horizontal and vertical dimensions for a more complex
design, resulting in a 16X increase in the number of grid points, and an
increase in routing time. Id. at 4:2–9. For efficient routing in complex IC
IPR2014-01153
Patent 6,507,941 B1

5

designs, the ’941 patent implements a detailed subgrid router, with subgrids
within grids, where the subgrids have finer and greater resolution than in
conventional grids. Id. at 4:29–56, 6:44–50. See Pet. 6. Figure 7 of the
’941 patent is reproduced below.

Figure 7 depicts grid-based router 20 in bounded area 10, with grids 12. Id.
at 6:27–29. Within each grid 12 is a plurality of sixteen subgrids 22, in
positions 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, and A, B, C, D, E, and F. Id. at 6:44–
50, 9:55–58. The ’941 patent states that wires are placed more precisely in
locations on a subgrid level. Id. at 7:17–22.

IPR2014-01153
Patent 6,507,941 B1

6

C. Illustrative Claims
Claims 1–14, 16–20, 26–37, and 39–45 are the subject of the petition.
Claims 1, 16, 26, and 40 are independent. Independent claims 1 and 40 are
reproduced as follows.
1. A method of automatically extending a wire location
representation from one grid to another grid comprising:

comparing a first plurality of sub grid indicia associated
with certain subgrids of the one grid with a second
plurality of subgrid indicia associated with certain
subgrids of the another grid to determine whether the
wire representation can be extended from the one grid
to the another grid,

wherein each of the subgrid indicia indicates one of
availability and nonavailability of a corresponding wire
portion representation and the first plurality of sub grid indicia and the
second plurality of sub grid indicia are adjacent to each other.

Independent claim 40 is reproduced below (emphasis added).
40. A method of automatically extending a wire location
representation from one region to an adjacent region of an
integrated circuit chip representation comprising:

determining that a wire representation can be extended
from the one region to the adjacent region, the step of
determining using:

a first availability representation of a first edge of the
one region that is adjacent to the adjacent region and
which provides a finer level of detail than that
provided for by a first global representation of the
IPR2014-01153
Patent 6,507,941 B1

7

one region, and a second availability representation of
a second edge of the another region that is adjacent to
the one reaction [sic] and which provides another finer level
of detail than that provided for by a second global representation
of the adjacent region, and wherein

the step of determining performs a logical operation that
compares the first availability representation with the
second availability representation to determine that the
wire representation can be extended from the one
region to the adjacent region.

D. Prior Art Relied Upon
Petitioner relies upon three prior art references.
Reference Title Date Ex. No.
Nakajima US 4,855,929 Aug. 8,
1989
Ex. 1005
JP ’446 Patent Application JP H3-278446, with
certified English translation
Dec. 10,
1991
Ex. 1006
Schiele W.L. Schiele et al., “A Gridless Router
for Industrial Design Rules,” 27th
ACM/IEEE Design Automation
Conference, pp. 626-631 (1990)

1990 Ex. 1007

IPR2014-01153
Patent 6,507,941 B1

8

E. The Asserted Grounds
Petitioner contends the challenged claims are unpatentable based on
five grounds.
Reference(s) Basis Claims Challenged
Nakajima and JP’446 § 103 1–12, 16
Nakajima and JP’446 § 103 17–20
Nakajima and JP’446 § 103 26–35, 39
Nakajima and JP’446 § 103 40–45
Nakajima, JP ’446, and Schiele § 103 13, 14, 36, 37

II. ANALYSIS
A. Claim Construction
In an inter partes review, claim terms in an unexpired patent are
interpreted according to their broadest reasonable construction in light of the
specification of the patent in which they appear. See 37 C.F.R. § 42.100(b);
Office Patent Trial Practice Guide, 77 Fed. Reg. 48,756, 48,766 (Aug. 14,
2012). Claim terms generally are given their ordinary and customary
meaning, as would be understood by one of ordinary skill in the art in the
context of the entire disclosure. See In re Translogic Tech., Inc., 504 F.3d
1249, 1257 (Fed. Cir. 2007).
Petitioner proposes a construction for a single term, “subgrids,”
asserting that “the broadest reasonable interpretation in view of the patent is
IPR2014-01153
Patent 6,507,941 B1

9

‘lowest level of a hierarchy within a hierarchical detailed router, in which
each subgrid can have only a single wire/net passing there-through.’” Pet. 9
(emphasis in original). The claims and specification do not specifically
define subgrid. Patent Owner states, “[b]ecause Nakajima fails to disclose
or render obvious ‘subgrids’ even when the Petitioner’s claim construction is
applied, the Patent Owner adopts the Petitioner’s constructions for the
limited purpose of” the Preliminary Response, Prelim. Resp. 7 n.1. Patent
Owner also notes that claim 1:
recites a hierarchical grid structure where “subgrids” are “of the one
grid” or “of the other grid.” In other words, a “subgrid” is a “sub” part
of a larger “grid” that it resides in.

Prelim. Resp. 6. Patent Owner further argues that the Petition “proposes an
unsupported construction for ‘subgrids,’” because “the defining
characteristic of a subgrid is not how many wires can pass through a single
grid point; it is that the subgrid has a lower level of granularity than the main
(or higher level) grid.” Id. at 7–8.
We agree with Patent Owner. The ’941 patent specification has no
disclosure of the number of wires passing through grid points. In contrast,
the specification states, “[w]ithin each grid there are a plurality of sub-
grids.” Ex. 1001, 6:44–50. Petitioner acknowledges that “in every
embodiment, the grids of a detailed router are subdivided so that each
contain a plurality of subgrids.” Pet. 9. The ’941 patent specification
further describes subgrids as having finer, or greater, or increased resolution
than the grid in which they are contained. Ex. 1001, Abstract, 4:54–5:10,
IPR2014-01153
Patent 6,507,941 B1

10

6:44–50, 7:59–8:3, 9:55–56, Figures 7, 10. For purposes of this Decision,
we are persuaded that the broadest reasonable interpretation of “subgrids” is
“a plurality of finer resolution grids within another grid.”

B. Claims 1–14, 16–20, 26–37, and 39 – Asserted Obviousness over
Nakajima and JP ’446

Petitioner contends claims 1–14, 16–20, 26–37, and 39 are
unpatentable under 35 U.S.C. § 103(a) as obvious over Nakajima and
JP ’446. Pet. 29–45. Claims 1, 17, and 26 are independent. Claims 2–16
depend from claim 1, claims 18–20 depend from claim 17, and claims 27–37
and 39 depend from claim 26. As in claim 1 reproduced above, claims 17
and 26 recite subgrids or a subgrid.
Nakajima (Exhibit 1005)

Nakajima is titled, “Routing Method for use in Wiring Design,” and
describes a method of routing that: (i) identifies in a wiring section where no
wiring path is yet determined, the direction of a line segment prohibited by
obstacles, (ii) determines a wiring path, and (iii) generates obstacles
prohibiting only line segments parallel to the identified line segment, on the
wiring path. Ex. 1005, Abstract, 1:39–51. The method is performed using
grid points in a grid map. Id. at 2:19–68.

IPR2014-01153
Patent 6,507,941 B1

11

Figure 1 of Nakajima is reproduced below.

Figure 1 is a flowchart of the routing method disclosed in Nakajima,
including processing modules 101–112 that perform steps in the routing
IPR2014-01153
Patent 6,507,941 B1

12

process between a starting point and terminal point on grid map 117.
Ex. 1005, 2:19–3:6.1 Figure 4 of Nakajima is reproduced below.

Figure 4 shows grid point 401, and grid points NC(i) 402–407
adjacent to grid point 401. Id. at 5:64–66, 6:3–5. The letter i indicates the
direction with respect to grid point 401, and when i is 1, 2, 3, 4, 5, and 6, the
direction is to the right, upward, left, downward, forward, and backward,
respectively. Id. at 6:5–8.

JP ’446 (Ex. 1006)

1 Nakajima is cited in the ’941 patent, which was allowed over Nakajima and
other references, as the Examiner found “the prior art of record does not
specifically disclose or teach subgrids which depict a plurality of finer
resolution grids within each one and another grid.” Ex. 1002, at 123–25.
IPR2014-01153
Patent 6,507,941 B1

13

JP ’446 is titled, “Automated Wiring Method for Semiconductor
Device,” and discloses a routing process “where a semiconductor chip is
divided into a plurality of unit wiring regions, and after each wiring pathway
between the wiring pathway regions is determined by a general wiring
process, the wiring pathway within each unit wiring region is determined by
a detailed wiring process.” Pet. 10; Ex. 1006, 13–14. The routing process
can be performed using grid points in a general wiring grid. Id. at 17.
Analysis
Petitioner explains how the subject matter of independent claim 1 is
disclosed by Nakajima and JP ’446. Pet. 29–41. Petitioner contends
Nakajima and JP ’446 teach the recited comparison, of a first plurality of
subgrid indicia associated with subgrids of one grid, with a second plurality
of subgrid indicia associated with subgrids of another grid, in order to
determine whether the wire representation can be extended from the one grid
to the another grid. Pet. 30–33, 40–41. Petitioner further contends that
Nakajima and JP ’446 teach the recited limitation wherein each of the
subgrid indicia indicates one of availability and nonavailability of a
corresponding wire representation, and that the first and second pluralities of
subgrid indicia are adjacent to each other. Pet. 33–34, 40–41.
In particular, Petitioner argues that Nakajima’s grid points are the
recited subgrids of claim 1. Pet. 11 fn.1, 29. Patent Owner contends that
Nakajima’s grid points do not disclose the claimed subgrids. Prelim. Resp.
5–8. We agree with Patent Owner. Grid points are not recited in claim 1 or
IPR2014-01153
Patent 6,507,941 B1

14

any other claims of the ’941 patent. As set forth in the ’941 patent’s
background of prior art, grid points were an aspect of prior art, grid based
routers; namely, grid based detailed routers described “the square of a net to
be routed” as “the square centered on the grid point.” Ex. 1001, 2:28–31.
Nakajima, in summarizing prior art routing methods, described “grid points
of the wiring path positions discovered upon completion of the wiring of
each segment,” Ex. 1005, 1:19–20. In JP ’446, the disclosed wiring method
describes wiring segments composed of grid points. Ex. 1006, at 17.
In addition, the textbook titled “An Introduction to VLSI Physical
Design,” relied upon by Petitioner, describes grid points as “vertices”
located in the “center of the tiles” in a grid. Ex. 1008, at 11–12, Fig. 1.5. A
vertex is a point where two or more lines meet, or that comprises the
intersection of two or more lines. Merriam-Webster Online Dictionary,
www.merriam-webster.com/dictionary/vertex. Thus, a grid point is not a
grid, but rather, a point, located in a grid. In contrast, the subgrid required
by claim 1 of the ’941 patent is not a point but rather, as construed above, is
itself a grid, in particular one of “a plurality of finer resolution grids within
another grid.”
Because Nakajima’s grid points are not the recited subgrids of claim
1, we are not persuaded that the Petition demonstrates a reasonable
likelihood that Petitioner would prevail in establishing unpatentability of
claim 1 or claims 2-14 and 16 dependent from claim 1. As in claim 1,
independent claims 17 and 26 also require a subgrid. Claim 17’s preamble
IPR2014-01153
Patent 6,507,941 B1

15

recites a method of determining whether a wire representation can be routed
from a first grid to an adjacent second grid, where each of the first and
second grids contain at least four subgrids and the availability indicia for the
subgrids are represented as a digital representation. Ex. 1001, 15:10–33.
Claim 26’s preamble recites a method of making a subgrid wire
representation that spans a plurality of grids. Id. at 16:30–32. As with
claim 1, we are not persuaded that the Petition demonstrates a reasonable
likelihood that Petitioner would prevail in establishing unpatentability of
independent claims 17 and 26, or dependent claims 18-20, 27-37, and 39
dependent from these independent claims.

C. Claims 40–45: Asserted Obviousness Over Nakajima and JP ’446

Petitioner contends claims 40–45 are unpatentable under 35 U.S.C.
§ 103(a) as obvious over Nakajima and JP ’446. Pet. 13–29.
Claim 40 does not recite a subgrid or subgrids. Claim 40 instead
recites a method of extending a wire location from one region of an IC
representation to another adjacent region, including determining that the
wire representation can be extended. Ex. 1001, 18:1–6. Claim 40 further
recites, however, that the determination uses a “first availability
representation” of a first edge of the one region, “which provides a finer
level of detail than that provided for by a first global representation of the
one region.” Id. at 18:7–11. Additionally, claim 40 requires that the
“second availability representation” provide “another finer level of detail
IPR2014-01153
Patent 6,507,941 B1

16

than that provided for by a second global representation of the adjacent
region.” Id. at 18:11–15.
Petitioner explains how the limitations of claim 40 are disclosed by
Nakajima and JP ’446. Pet. 13–20. For the recited “finer level of detail”
required by the first availability representation and the second availability
representation, however, Petitioner’s conclusions are unsupported by
evidence. Petitioner concludes that Nakajima Figure 12 presents “the finest
level of detail” and that one of ordinary skill in the art would have
understood or inferred that in view of JP ’446, this “finest level of detail” is
the recited “finer level of detail” than that provided for by first and second
global representations of regions of an IC representation. Pet. 18–19. The
Petition cites to the accompanying declaration of Soheil Ghiasi, Ph.D., but
the declaration simply repeats verbatim the arguments made in the Petition,
without additional evidence or reasoning as to why one of ordinary skill
would have inferred or understood that Nakajima Figure 12 (which
“illustrate[s] the states of a grid map,” Ex. 1005, 2:4) discloses claim 40’s
recited “finer level of detail than that provided for by” the first and second
global representations of regions of an IC representation. This testimony is
conclusory in nature and entitled to little, if any, weight. See 37 C.F.R. §
42.65 (“Expert testimony that does not disclose the underlying facts or data
on which the opinion is based is entitled to little or no weight.”); see also
Rohm and Haas Co. v. Brotech Corp., 127 F.3d 1089, 1092 (Fed. Cir. 1997)
(nothing requires a fact finder to credit the inadequately explained testimony
IPR2014-01153
Patent 6,507,941 B1

17

of an expert). Furthermore, we are not persuaded that Petitioner sufficiently
establishes for purposes of this decision that Nakajima and JP ’446 teach or
suggest the “finer level of detail” limitations of claim 40.
Claims 41–45 depend directly or indirectly from claim 40. Claims 41
and 42 also recite subgrids, which as construed herein are not disclosed or
taught or suggested by Nakajima or JP ’446. See section II. B above.
Accordingly, we are not persuaded that Petitioner has demonstrated a
reasonable likelihood that it would prevail in establishing that independent
claim 40 and dependent claims 41–45 are unpatentable over Nakajima and
JP ’446.
III. CONCLUSION
For the foregoing reasons, we are not persuaded the information
presented in the Petition establishes a reasonable likelihood that Petitioner
would prevail in establishing unpatentability of claims 1–14, 16–20, 26–37,
and 39–45 of the ’941 patent as obvious over Nakajima and JP ’446.
IV. ORDER
Accordingly, it is
ORDERED that the Petition is denied and no trial is instituted.

IPR2014-01153
Patent 6,507,941 B1

18

PETITIONER:

Jeffrey A. Miller
Krista M. Carter
Katie J.L. Scott
DICKSTEIN SHAPIRO LLP
millerj@dicksteinshapiro.com
carterk@dicksteinshapiro.com
scottk@dicksteinshapiro.com

PATENT OWNER:

David Cochran
Joseph Sauer
David W. Wu
JONES DAY
dcochran@jonesday.com
jmsauer@jonesday.com
dwwu@jonesday.com