Aiding the design of an operation having timing interactions by operating a computer system

• US 4,965,758 A
• Filed: 03/01/1988
• Issued: 10/23/1990
• Est. Priority Date: 03/01/1988
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Sherman, Steven K.
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): Melnick, S. A.
• Application Number:
  US07/162,624
• Time in Patent Office: 966 Days
• Field of Search: 364/579, 364/580, 364/488, 364/578, 324/73 PC, 324/73 AT, 324/73 R, 371/25, 371/23
• US Class Current: 716/113
• CPC Class Codes: G06F 30/3312 Timing analysis

Abstract

An aid for design analysis of timing requirements of a computer operation by operating a computer system and identifying an optimized reduced set of requirements which is self consistent and which is minimally reduced from the original.

Claims

1. A method to aid in the design of an operation having timing interactions, by operating a computer system including a processor, a memory, a means for entering data and a display, the method comprising the steps of:

(a) generating with said processor a dependence list data structure from a set D of dependence information entered into the memory, the dependence information describing timing relationships between first and second events of each dependence of the operation and describing each dependence as a primary dependence or secondary dependence;

(b) generating an event list data structure in the memory from the dependence list data structure, said events identified in one or more of said primary class dependences being primary events and said events identified in no primary class dependence being secondary events, said set D including related dependences which are isomorphic with a single graph G having edges connecting vertexes, the vertexes of G corresponding to events named in the events list data structure and the edges of G corresponding to the dependences in the dependence list data structure;

(c) searching the dependence list and locating a first primary dependence to serve as a root dependence for a tree;

(d) forming a primary event nucleus by selecting and attaching additional primary dependences to said tree;

(e) adding secondary dependences in layers around the primary event nucleus of said tree;

(f) assigning a time attribute to events in said tree, said time attributes being consistent with the timing relationships specified in the set D of dependence information;

(g) repeating steps (d), (e) and (f) to develop a time consistent graph T having all the vertexes of graph G and with edges corresponding to dependences in a set I of included dependences, I being a subset of G, a dependence being in I if its interval corresponds to the difference in time attributes of its two vertexes, the set I of included dependences and the time attributes being subject to the conditions that;

(1) the number of primary class dependences from the set D included in I be maximized;

(2) all primary vertexes be connected by a set C of core linkage dependences, set C being a subset of I, the number of secondary dependences in the core linkage set C being minimized;

(3) each secondary vertex S_i be connected to a primary vertex by a set P_i of peripheral-linkage secondary dependences, set P_i being a subset of I, the number of secondary dependences in each peripheral-linkage set P_i being minimized;

(4) subject to the above conditions in (1), (2) and (3), the number of secondary class dependences in I be maximized;

(h) providing design information from the time consistent graph T on the display means; and

(i) applying the design information to aid in the design of said operation.

2. A method as claimed in claim 1, wherein said providing step includes reporting those dependences in set D which are not in set I.

3. A method as claimed in claim 2, wherein said generating step includes entering data characterizing dependence intervals as maximum or minimum, and wherein said providing step includes reporting whether those dependences in set D which are not in set I are violated.

4. A method as claimed in claim 1, wherein said generating step includes entering signal sequence data about said operation, and wherein said providing step includes reporting a timing pattern based on the graph T.

5. A method as claimed in claim 1, wherein said generating step includes entering signal sequence data about said operation, and wherein said providing step includes reporting events sequenced differently in graph T than in the entered signal sequence data.

6. A method as claimed in claim 1, wherein said generating step includes entering data defining a query as to time interval between two events and wherein said providing step includes reporting such time interval as indicated by the graph T.

7. A method as claimed in claim 1, wherein said generating step includes entering data defining a timing pattern, and wherein said providing step includes reporting discrepancies between said timing pattern and a timing pattern implied by the graph T.