Browse Prior Art Database

Method for Minimizing Critical Timing of a Digital System

IP.com Disclosure Number: IPCOM000039608D
Original Publication Date: 1987-Jul-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 3 page(s) / 17K

Publishing Venue

IBM

Related People

Brayton, RK: AUTHOR [+2]

Abstract

A technique is described whereby the critical delay timings of logic circuits, as used in digital computer systems, are minimized by synthesizing the logic in a hierarchical manner. Since input signals arrive at different times and the outputs are required at different times, logic blocks (macros) are re-synthesized along the systems critical timing paths. This method, when used in conjunction with other techniques, decreases the overall delay of the logic flow. Since each logic block of a digital system contains a number of inputs and outputs, the system can be viewed as a direct graph where each node is a logic block. A branch is drawn from node i toward node j if one of the outputs of node i is a primary input for node j. It is then assumed that the graph is acyclic.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 39% of the total text.

Page 1 of 3

Method for Minimizing Critical Timing of a Digital System

A technique is described whereby the critical delay timings of logic circuits, as used in digital computer systems, are minimized by synthesizing the logic in a hierarchical manner. Since input signals arrive at different times and the outputs are required at different times, logic blocks (macros) are re-synthesized along the systems critical timing paths. This method, when used in conjunction with other techniques, decreases the overall delay of the logic flow.

Since each logic block of a digital system contains a number of inputs and outputs, the system can be viewed as a direct graph where each node is a logic block. A branch is drawn from node i toward node j if one of the outputs of node i is a primary input for node j. It is then assumed that the graph is acyclic. In synthesizing each logic sub-block, each input signal arrival time is assumed to arrive at a given time. The outputs are also assumed to be required at a required time. This would be the situation if the logic macro received its inputs from latches and its output drove other latches. However, in digital systems, inputs arrive at different times and the outputs are required at different times. The technique described herein synthesizes the logic in a hierarchical manner, taking into account system timing considerations for minimizing the critical path lengths. Each logic macro is also represented by another graph defining a Boolean network. Each node of that network has a logic function associated with it. This is represented by a gate implementing that function or simply that logic in a disjunctive form. Assuming that each gate or logic function has an associated delay equation outlining the delay from its input signals to its output, the system timing can be computed by tracing the delays through each gate in a block of logic, and in a hierarchical manner through each logic block. The systems critical path is computed by starting at the primary inputs for the system, and assigning them appropriate arrival times. Since the logic macros are interconnected by an acyclic directed graph, the logic macro delays can be processed as an ordered set. Inside each logic macro, each signal delay is computed as follows: delay (i) = gate delay (i) + maximum (delay (j)) j in

FEEDS (i) FEEDS (i) is a set of nodes which feed into node i. By tracing forward through the logic macros, the delay of each signal or wire of the system can be computed. The system slacks on each signal can be computed by a similar computation by tracing backward through the graph and computed as follows: Initialize all slacks to be a large number. Let the outputs of the digital system be denoted by OUT. slack (i) = desired arrival_time (i) - delay (i) for i in OUT and for each node j, compute for all k in FEEDS(j) slack (k) = minimum< slack (k) , slack (j)+max (delay (l))-delay (k) > l in

1

Page 2 of 3

FEEDS(j) The system slacks are computed by pro...