'Libraries
`
`ARIZONA STATE UNIVERSITY
`
`DECLARATION OF SHERRIE SCHMIDT
`
`I, Sherrie Schmidt, declare as follows:
`
`1.
`
`I am the University Librarian at the Arizona State University Libraries.
`
`I have personal
`
`knowledge of the facts listed below.
`
`2. The Arizona State University Libraries are open to the public. Any member of the public
`
`may enter any of the Arizona State University Libraries, including Science, and view the
`
`periodicals in the library's collection.
`
`3. The title, IEEE/ACM International Conference on Computer-Aided Design: digest of
`
`technical papers November S-9, 1995, San Jose, California was cataloged at the ASU
`
`Libraries on 2/16/96; it would have been shelved in Science by 2/19/96; it would have been
`
`discoverable by browsing the shelf at that time; it would have been discoverable in the
`
`online catalog between 2/23/96 and 3/2/96.
`
`4. Attached are scanned images of the publication's front and back cover, the title page, the
`
`verso of the title page, and the article "Timing Analysis with Known False Sub Graphs"
`
`pp. 736-739.
`
`I declare under penalty of perjury that the foregoing is true and correct.
`
`Dated: 30 May 2014
`
`PO Box 871006, Tempe, AZ 85287-1006
`{480) 965-3417 Fax: {480) 965-9169
`
`Exhibit 1005 - Page 1 of 10
`
`

`
`
`
`‘a‘nfi\fi»f1{iF\ifi1\1\i\fl\Q‘\[nmjifliflwflmf
`
`Q1564
`
`_
`
`
`
`Exhibit 1005 - Page 2 of 10
`
`

`
`
`
`U -- 3§;.'|'..Eo3Ei ~ 'J’?}1E>:- ~
`
`Exhibit 1005 - Page 3 of 10
`
`Exhibit 1005 - Page 3 of 10
`
`

`
`1995
`IEEE/ACM International Conference
`on Computer-Aided Design
`
`November 5:....9, 1995
`
`San Jose, California
`
`Digest of _.Technical Papers
`
`~
`rtSlGi
`. ~Z?5
`\Gtl1~
`ev\t?AIGU
`
`IEEE Computer Society Press
`Los Alamitos, California
`
`Washington
`
`•
`
`Brussels
`
`•
`
`Tokyo
`
`Exhibit 1005 - Page 4 of 10
`
`

`
`IEEE Computer Society Press
`10662 Los Vaqueros Circle
`P.O. Box 3014
`Los Alamitos, CA 90720-1264
`
`..
`, .. ('
`
`I
`
`Copy.right © 1.995 by The lnstitl,lte q(;EJt;,etrical and Electronics Engineers, Inc .
`,.
`·.~ :.·
`.
`.
`.-
`,, An rights reserved. . ' y
`... ··.
`. . ,
`Copyright and Reprint Permissions: Abstracting is permitted with credit to the source. Libraries may
`photocopy beyond the limits of US copyright law, for private use of patrons, those articles in this volume
`that carry a code at the bottom of the first page, provided that the per-copy fee indicated in the code is paid
`through the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923.
`
`•
`
`•
`
`•
`
`•
`
`...
`
`Other copying, reprint, or republication requests should be addressed to: IEEE Copyrights Manager, IEEE
`Service Center, 445 Hoe_s Lane, P.O. Box 1331, Piscataway, NJ 08855-1331.
`
`The papers in this book comprise the proceedings of the meeting mentioned on the cover and title page. They
`reflect the authors' opinions and, in the interests of timely dissemination, are published as presented and
`without change. Their inclusion in this publication does not necessarily constitute endorsement by the
`editors, the IEEE Computer Society Press, or the Institute of Electrical and Electronics Engineers, Inc .
`
`...
`
`..
`
`IJjEE Gomp~ter Sq~!ety-Pres~-Ot:d~f'Number PR07213
`· ·IEEE oiderPhnicataJ.o·g·N'umber 95ca35859 ·
`Library of Congress Number 86-646631
`ISBN 0-8186-7213-7
`Microfiche ISBN 0-8186-7214-5
`IEEE Order Plan ISBN 0-8186-7215-3
`ISSN 1063-6757
`
`Additional copies may be ordered from:
`
`IEEE Computer Society Press
`Customer Service Center
`10662 Los Vaqueros Circle
`P.O. Box 3014
`Los Alamitos, CA 90720-1264
`Tel: +1-714-821-8380
`Fax: +1-714-821-4641
`Email: cs.books@computer.org
`
`IEEE Service Center
`445 Hoes Lane
`P.O. Box 1331
`Piscataway, NJ 08855-1331
`Tel: +1-908-981-1393·
`Fax: +1-908-981-9667
`misc.custserv @computer.org
`
`IEEE Computer Society
`13, A venue de I' Aquilon
`B-1200 Brussels
`BELGIUM
`Tel: +32-2-770-2198
`•' Fax: +32-2-770-8505
`euro.ofc @computr.org
`
`IEEE Computer Society
`Ooshima Building
`2-19-1 Minami-Aoyama
`Minato-ku, Tokyo 107 .
`JAPAN
`Tel: +81-3-3408-3118
`Fax: +81-3-3408-3553
`tokyo.ofc@computer.org
`
`Editorial production by Penny Storms
`Cover by MP Associates
`. :
`Printed in the United States of America by KNI, Inc.
`
`•
`
`The Institute of Electrical and Electronics Engineers, Inc,.
`
`Exhibit 1005 - Page 5 of 10
`
`

`
`Timing Analysis with known False Sub Graphs
`Krishna P. Belkhale *
`Alexander J. Suess
`AMBIT, Suimyvale, CA 94086
`IBM, East Fishkill, New York 12533
`belkhale@ ambit. com
`aj suess @vnet.ibm.com
`
`Abstract - In this paper we formulate the problem of
`timing analysis with known false sub graphs. This problem
`is important when we want the timing analysis system to
`take into account false path information that is supplied
`either by the user or by another program, and supply ac(cid:173)
`curate timing information to optimization programs such
`as placement and wiring. We present an efficient algorithm
`for the problem.
`
`Introduction
`
`Static timing analysis algorithm, as described in [1], is
`currently a widely used mechanism for efficiently verifying
`the timing behavior of circuits.. The algorithm computes
`th_e arrival time of signals in a forward pass ~ough ·the
`timing graph. The second step involves propagating the
`required times computed at the latChes in a backward pass
`through the graph. At the end of two passes each vertex in
`the timing graph has a computed arrival time AT and re(cid:173)
`quired arrival time RAT. The quantity slack SLK is then
`computed as RAT- AT. This gives a good local measure
`of the magnitude of the timing violll,tion.
`
`The problem with the ·static timing analysis procedure
`described above is that it does not take' logic into account.
`Thus some of the paths that are considered by the algo(cid:173)
`rithm may. not be logically realizable. These paths are of(cid:173)
`ten referred to as false paths. Such paths must be detected
`and eliminated from consideration from the timing analy(cid:173)
`sis. This problem has been studied extensively by many
`researchers, and various interesting algorithms for false
`path ·detection and elimination have been discovered
`[2,3,4,5,6,7].
`
`In this paper, we formulate and analyze a new problem of
`timing analysis given a set of false sub graphs .. TP,e notion
`of false sub graphs is more general than the notion of false
`paths as we· can simultaneously remove the consideration
`of multiple paths.
`
`This problem is useful for a variety of reasons. In many
`cases, users do have an idea that certain paths ·reported by
`the timing system are really false. This formulation allows
`the users to convey this information to the timing system
`resulting in a more meaningful analysis. As will be shown
`in Section 2, the ability to remove entire sub graphs from
`consideration from timing is a powerful feature.
`
`* The work was done while the author was at IBM
`
`A second reason for looking into this. problem is that
`though techniques described in [2,3,4,5,6,7] solve the
`problem of determining the true delay of the circuit, they
`do not determine slacks at all points in the design. These
`slacks are a useful input to physical optimization programs,
`such as placement and wiring. Our problem formulation
`and solution, with the false sub graphs as input, allows us
`to still maintain .the notion of slacks in the design. The
`false sub graphs may either be provided by the user or de(cid:173)
`termined automatically. An interesting problem arises in
`this context. The determination that a given path js false
`depends on both logic and temporal factors. Thus, a false
`path may not stay false through a physical optimization
`process. For a common definition of a false path, the loose
`criterion defined in [4], one could prove that removing the
`false paths from consideration during a series of physical
`optimization steps (note the false paths were determined at
`the start of optimization) will only result in an analysis that
`does not underestimate the delays in the circuit. Thus, the
`result of the analysis is still useful and the actual false paths
`need not be .re-determined during the optimization process.
`
`The outline of the paper is as follows. In Section 2, we
`formulate the problem of timing analysis with known false
`sub graphs.
`In Section. 3, we describe an algorithm for
`solving the problem. in Section 4, we describe some im(cid:173)
`plementation results.
`In Section 5, we give the conclu(cid:173)
`sions.
`
`2 · Problem specification
`
`In this section, we formulate the problem of timing
`analysis with known false sub graphs. For our discussion,
`we assume that the timing model of a circuit is a graph.
`The graph is assumed to be acyclic. The edges of the
`graph are associated with the delays.
`
`Let Fz, ... , Fk be k false sub graphs, which are sub graphs
`of G. We define the sets B;, E;, 1 :::::; i:::::; k, which are re(cid:173)
`ferred to as the begin set and end set respectively, as fol-
`lows.
`'
`
`Definition 1 The begin set B;
`is the set of vertices x in
`each sub graph F; such that there are edges in the sub
`graph that start from X but there are none that end in X.
`Similarly, the end set E; is the set of vertices x in each sub
`graph F; such that there are edges in the sub graph that
`end in x but none that start from x.
`
`1063-6757/95 $04.00 © 1995 IEEE
`
`736
`
`Exhibit 1005 - Page 6 of 10
`
`

`
`The problem considered in this paper can be defined as
`follows. An example is illustrated in Figure 1 .
`
`Definition 2 The problem of timing the graph G with false
`sub graphs FJ> ... ,F"' consists of computing the timing
`quantities AT, RAT and SLKfor all the vertices in G, while
`disregarding some paths from the analysis. The paths to
`be disregarded are the set of all paths in G, which have a
`sub path in some F~> that starts at a vertex in B; and ends
`in a vertex in E;.
`
`In the definition above, if the false sub graphs are speci- .
`fied by the user, then there is a necessity for making the
`user specification easier. One mechanism involves specify(cid:173)
`ing F; as a set of ordered pair of vertices. An ordered pair
`(vh vm) implies the inclusion of all the edges and vertices in
`G, that lie on a path from v1 to vm, into F;. The sub. graph
`F; can be specified as a collection of .such ordered pairs.
`Note that this specification in some cases may be the same
`as specifying all the edges in F1, resulting in no compres(cid:173)
`sion in specification. For example in Figure 1, F1 cannot
`be specified as { (vt. v1)} as this will result in the inclusion
`of the diagonal edges. Instead, it needs· to be specified as a
`set of seven ordered pairs corresponding to the seven edges
`of the graph. However, in many cases this will allow com(cid:173)
`pact user specification of false sub graphs. For example,
`consider the standard false path situation as shown in Fig(cid:173)
`ure 2. Assuming the control path delays are small; all
`paths leading from the h pin of the first multiplexer MUX1
`to the I1 pin of the second multiplexer MUX2 are false. This
`is because the control signal setting that allows the propa(cid:173)
`gation at the first pin will block the propagation at the sec(cid:173)
`ond pin. This situation can be specified ~y using a single
`ordered pair. T he false sub graph is r~prdented by' the .set
`{(MUX .f/11 MUX'lf/1)) .
`.
`'
`.
`. •
`.' ·,
`
`3 Algorithm for the problero ·
`
`I
`. •"
`The overall app roach of t.he algorithm is the sam~ ~ de-
`scribed in [ 1), except that the timing 1?f9rmatlon. , com(cid:173)
`puted at a node is now more complex . . The algorithm
`computes multiple arrival and required times ~t ~ node.
`The different arrival and required tim es at a nop~ are dis(cid:173)
`tinguished based' on a set attribute .. The set atl:(ib~te. i~ il
`subset of the set { l, ... ,k}, where k is the number of input
`In other words, the set attribu.~e is an
`fa lse sub graphs.
`element of the power set of { l , ... ,k} . For example, will} k
`= 2, t.he possi ble values for the set attribute are {}, { 1 } ,
`{2}, and {1 , 2}. The set attribute value gives the' set of
`false sub graphs the signal has come through.
`
`At a node in the graph, some of the elements of the power
`set are associated with timing information. The actual
`elements that have associated timing information at a node
`
`is determined by the algorithm, which is described below.
`We will use the notation AT(v, s), RAT(v, s), SLK(v, s) to
`for the
`denote the respective timing quantities at node v
`element s of the power set.
`
`We first describe the arrival time propagation phase of the
`algorithm. The required time propagation is essentially the
`inverse of the arrival time propagation. Once these are
`calculated at a node v, the slack is obtained by first com(cid:173)
`puting SLK(v,s) = RAT(v,s) - AT(v,s) for all s, where s is
`an element of the power set with a valid time at the node.
`The slack at the node is then computed as the minimum of
`the quantities SLK(v,s) for all elements s of the power set at
`thenode.
`·
`·
`
`The arrival time propagation phase is a breadth first ap(cid:173)
`proach starting at the primary inputs. The arrival time at
`the primary inputs are based on user assertions. These
`times are taken to be associated with the null set 0. A
`node vis processed for arrival time computation only if all
`the edgeS incident to v come from vertices whose arrivai
`time information has already been computed. Since the
`timing graph G is acyclic, this algorithm will result in the
`computation of arrival times at all nodes in the graph. The
`arrival time procesSing at node v i's described below, fol(cid:173)
`lowing some definitions.
`
`Definition 3 For every node v in G, we define the set
`BG(v) to be the set of all false sub graphs for which the
`vertex v is a element in the begin set. In other words,
`BG(v) = {ilv E B,}. Similarly, we define EG(v) to be the
`set of all false sub graphs for which the vertex v is in the
`end set. In other words, EG(v) = {ilv E E.}.
`
`Definition 4 For every edge e in G, we define the set
`IN (e) to be the set of all indices of false sub graphs that
`contain e.
`' '
`
`Algorithm 1
`
`___ ... _______________ . __ .:__ _____ _
`
`arrival _process ( ·v ) ·{ ·
`for each edge e ~ (u, v) {
`for each element s · ( in power set )
`with valid time at ·u do {
`s' +- (s v BG (u)) n IN (e)
`if ( s' n EG (v) = 0 {
`AT(v, s'). ~ max(AT(u,s) +delay( c), ATlv,s'JJ ..
`
`'•
`
`}
`
`I·
`
`.
`
`. , ,
`
`_____ .. ______ ,..,. __ ,.. _____________ _
`
`' I
`
`: .. .
`l latl
`
`' • , . l.!'
`
`It
`
`737
`
`lg
`n,
`h.
`
`hs
`:e(cid:173)
`o.!-
`
`in
`,·ub
`t x.
`fUb
`hat
`
`Exhibit 1005 - Page 7 of 10
`
`

`
`T
`
`An element set indicates the set otfals.e sub graphs the
`arriving signal has propag~ted through. The algorithm
`above takes each arrival time at the source of an edge and
`derives the sink arrival time and the sink element set. The
`sink element set is obtained by taking the source element
`set and performing a union with BG (source), followed by
`intersection with IN (edge). The union operation signifies
`the new false sub graphs that begin at the source point.
`The intersection operation signifies that the sink element
`set cannot contain indices of false sub graphs that do not
`contain the edge e. If the sink element set contains an in(cid:173)
`dex of a false sub graph that ends at vertex v, then the
`propagated arrival time is ignored. This condition is
`checked by determining if s' and EG (sink) have a valid
`intersection. If they do not, then the arrival time at the sink
`is updated to the maximum
`of the computed arrival time and the previously computed
`result (which is taken as - oo if there is none before). The
`required arrival time computation proceeds in a reverse
`manner to the arrival time propagation. The complete
`algorithm result for the example in Figure I' is shown in
`Figure 3.
`
`The performance of the algorithm depends heavily on the
`number of, elements of the power set that are associated
`with valid times at a node. In the most general case, the
`number of elements at a node v is bounded above by 2!,
`where f is the number of false sub graphs that contain v.
`This bound will be reached only when there are varied
`patterns of intersections between the false sub graphs. If all
`the false graphs are really just false paths, we can prove the
`following theorem.
`
`Theorem 1 If all the false sub graphs are just false paths,
`then the number of elements with valid times at a node v is
`at most f, where f. is the number of false paths that go
`through v.
`
`Proof: Let s be an element with a valid time at node v.
`Among all the false path indices in sets, let i be the index
`of a false path whose sub path sub;, till node v is the long(cid:173)
`est. It can be seen that the sub paths of the other false paths
`in set s till node v are also sub paths of sub;. Also, if a false
`path, with index x, has a sub path starting from its start
`vertex till node v which is a sub path of sub;, then the index
`x must be an element of set s. Based on the above observa(cid:173)
`tions the set s is totally determined by the index of the false
`path with the maximum sub path. Since there are only f
`choices for this index, there can be only f different set ele(cid:173)
`ments at the node.
`
`It should be noted that the above theorem does not imply
`that it is advantageous to deal only with false .paths. This is
`because the number of false paths that are needed to re-
`
`place a false sub graph may be exponential in terms of the
`size of the false sub graph.
`
`4 Implementation Results
`
`The algorithm for timing analysis with known false sub
`graphs has been implemented as part of a timing analysis
`program. The performance results of the algorithm are pre(cid:173)
`sented for a two dimensional array of blocks as shown in
`Figure 4. Each of the blocks in the circuit has two inputs
`and two outputs. The timing graph for a block connects
`each of the inputs to the outputs by direct edges. The re(cid:173)
`sults presented in this section are for a mesh of size 100,
`with number of edges in the timing graph equal to 60,200.
`
`Total False
`Edges Paths
`
`False
`Per Path
`
`Avg.Edge
`
`Time
`
`0
`30,000
`60,000
`90,000
`120,000
`150,000
`180,000
`210,000
`240,000
`?70.000
`
`0
`159
`314
`463
`609
`760
`919
`1063
`1218
`11'i7
`
`0.0
`188.7
`191.1
`194.4
`197.0
`197.4
`195.9
`197.6
`197.0
`lQQ 0
`
`12.6
`20.1
`29.8
`39.3
`51.4
`60.9
`74.2
`86.4
`107.5
`121 .R
`
`Table 1: Performance for false paths on 100 by 100 mesh
`
`·In Table 1, we give the execution time for timing analysis
`for varying number of false paths. The times are in sec(cid:173)
`onds on a IBM RS/6000 processor. The false paths were
`randomly generated by walking backwards randomly from
`outputs of the mesh to the inputs of the mesh. The first
`column gives the total number of false path edges that were
`asserted. This is just the count of the total number of edges
`in each fals~ path. The second column gives the number of
`false paths. The third column gives the average number o~
`edges in a false path, which can be derived from the first,,
`two columns. The fourth column gives the execution time"
`of the timing analysis algorithm. The table shows the per(cid:173)
`formance of the algorithm from 0 false path edges to
`270,000 false path edges (which is more than 4 times the
`original timing graph size). The table shows that the per(cid:173)
`formance is fairly linear in the range.
`
`738
`
`Exhibit 1005 - Page 8 of 10
`
`

`
`Avg. Edges
`False
`Total False
`Edges Paths Sub Graphs Per Sub Graph
`
`Time
`
`0
`30,000
`60,000
`90,000
`120,000
`150,000
`180,000
`210,000
`240,000
`270,000
`
`0
`29
`54
`80
`107
`133
`153
`169
`194
`217
`
`0.0
`1034.5
`1lll.l
`1125.0
`1121.5
`1127.8
`1176.5
`1242.6
`1237.1
`1244.2
`
`12.6
`19.3
`29.6
`43.2
`52.6
`65.3
`73.2
`87.0
`103.6
`120.0
`
`Table 2: Performance for false sub graphs on 100 by 100
`mesh
`
`In Table 2, we give the execution time for timing analysis
`for varying number of false sub graphs. The false sub
`graphs were randomly generated by walking backwards
`randomly from outputs of the mesh to the inputs of the
`mesh. Instead of going backwards on only one edge to a
`point, a secondary edge was also traced back on certain
`points.- These points were chosen randorilly based on an
`input probability. The first column gives the total number
`of false path edge:; that were asserted. This is the total of
`the number of edges in the individual false sub graphs. The
`second column gives the number of false sub graphs. The
`third column gives the average number of edges in a false
`sub graph, that can be derived from the first two columns.
`The fourth column gives the execution time of the timirig
`analysis algorithm. The table shows the performance of
`the algorithm for the identical range of false path edges as
`in Table 1. The overall performance matches the perform(cid:173)
`ance shown in Table 1. It should be noted that although
`the two tables contain similar results for matching numbers
`of false edges, the sub graph results are more impressive
`because they suppress many more false paths. This is be(cid:173)
`cause a sub graph is, in general, equivalent to many indi(cid:173)
`vidual paths, but a sub graph specification uses far fewer
`edges.
`'
`
`5 Conclusions
`
`We formulated the problem- of timing analysis with
`known false sub graphs and presented an algorithm for
`solving the problem. Furthermore, we described some
`performance results of the implementation, which . showed
`the effectiveness of the problem formulation and solution.
`
`References
`
`[1]
`
`[2]
`
`[3]
`
`[4]
`
`[5]
`
`[6]
`
`[7]
`
`R. B. Hitchcock, "Timing Verification
`and Timing Analysis Program", Proc. of the
`19th ACMIJEEE DAC 1982, pp. 594-604.
`
`D. H. C. Du, S. H. C. Yen, and S. Ghanta, "On the
`General False Path Problem in Timing Analysis",
`Proc. of the 26th Design Automation Conference
`1989, pp. 555-560.
`
`P. McGeer and R. K. Brayton, "Efficient
`algorithms for computing the longest viable path
`in a combinational network", Proc. of the 26th
`Design Automation Conference 1989, pp. 561-
`567.
`
`H. C. Chen, D. H. C. Du, "Path Sensitization in
`Critical Path Problem",
`IEEE Trans. on CAD
`Feb. 1993,pp. 196-207.
`
`S. T. Huang;T. M. Parng, and J. M. Shyu,
`"A Polynomial-Time Heuristic Approach to
`· Approximate a Solution to the False Path
`Problem", Proc. of the 30th Design Automation
`Conference 1993, pp. 118-122.
`
`H. Chang, and J. A. Abraham, "VIPER: An
`Efficient Vigorously Sensitizable Path Extractor",
`Proc. of the 30th Design Automation Conference
`1993, pp. 112-117.
`
`P. McGeer and R. K. Brayton, "Integrating
`Functional and Temporal Domains in Logic
`Design", Norwell, MA: Kluwer Academic, 1991.
`
`Acknowledgements:
`
`The aut~ors acknowledge valuable discussions with
`Mr. Jiteridra Apte, Mr. Rajesh Gupta .and Mr. Deepak
`Sherlekar on the applicability of the problem in physical
`design.
`
`739
`
`Exhibit 1005 - Page 9 of 10
`
`

`
`v -'...---___.., v3
`(delay for all edges=l)
`vl
`v3
`v6
`
`Comb Logic
`
`Fig. 1. Timing graph and false sub graphs.
`
`Fig. 2. A standard false path test case.
`
`Comb Logic
`
`Comb Logic
`
`V1
`
`V2
`
`V3
`
`V4
`
`V5
`
`V6
`
`V7
`
`V8
`
`V9
`
`(0,{})
`
`(1,{ 1,2})
`
`(1, { 1,2})
`
`(2,{ 1})
`
`(2,{})
`
`(3,{1,2})
`
`(3,{ 1,2})
`
`(N,{1})
`
`(1,{})
`(2,{ 1,2})
`
`(3,{})
`(4,{ 1,2})
`
`(2,{2})
`
`(2,{})
`
`(2,{})
`
`(3,{})
`
`(N,{2})
`
`(4,{})
`
`(4,{})
`
`(5,{})
`
`Fig. 3: Arrival Time and Required Time propagation (N =No RAT)
`
`Outp,uts
`
`Outputs
`
`Inputs
`Fig. 4. Two dimensional Mesh.
`
`740
`
`Exhibit 1005 - Page 10 of 10