Browse Prior Art Database

Fanin Ordering in Multi-slot Timing Analysis

IP.com Disclosure Number: IPCOM000110420D
Original Publication Date: 1992-Nov-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 4 page(s) / 161K

IBM

Related People

van Ginneken, LPP: AUTHOR

Abstract

This article describes a method for fanin ordering of commutative functions in combinational logic. The objective is to maximize the worst slack in a multi-slot timing analysis environment. Its main contribution is the notion that the problem can be formulated as a bipartite matching problem, in which the minimum weight of any element is maximized. The fanin ordering problem

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 49% of the total text.

Fanin Ordering in Multi-slot Timing Analysis

commutative functions in combinational logic.  The objective is to
maximize the worst slack in a multi-slot timing analysis environment.
Its main contribution is the notion that the problem can be
formulated as a bipartite matching problem, in which the minimum
weight of any element is maximized.
The fanin ordering problem

In combinational logic circuits, logic functions often have
commutative inputs which are functionally identical, but which have
different delays.  The signals on the nets that are connected to the
commutative inputs often have different arrival times.  The nets can
be assigned to the inputs in such a way that the output is ready as
early as possible.

When a single arrival time of the signals and a single delay
for each pin is used, a simple sorting method [1] can be used to
assign the signals to the pins optimally: The signal with latest
arrival time will be assigned to the input with the smallest delay,
and the signal with the earliest arrival time is assigned to the pin
with the largest delay.  The problem can be solved in such a simple
way because the timing model is very simple.  In practice, more
complicated delay models are used, in which case this simple
algorithm will not always give the optimal answer.

Algorithmic complications can come from the use of multiple
timing slots, for instance, distinct slots (times and delays) for
falling and rising signals.  Another example is to have different
slots for best-case and worst-case delays.

The sorting method relies on comparing arrival times of the
signals and required times on the inputs.  This does not work if the
timing model has multiple timing slots.  The basic problem is that
the slack at a pin is not simply the difference between the worst
arrival time and the worst required time, but instead, the worst of
the slacks of several slots.

In addition, the delay may depend on the connection between a
particular signal and a particular pin.  The delay may be a complex
formula, depending on the slew or capacitance at the input.

There are n signals and n inputs, so there are n2 possible
connections.  We assume that the delay can be calculated
independently for each connection.  That is, the delay from one
connection to the output is not influenced by any of the other
connections.  The delay models of (2,3) satisfy this condition.

The problem that we want to solve is:

(Image Omitted)

3.  |M| = n
4.  min {Sij | (i,j) e M} is maximal
Conditions 1 and 2 say that the signals must be assigned one-to-one
to the inputs.  Condition 3 says that all inputs must be connected.
Condition 4 says that the worst slackmust be maximal.
The fanin matching method

From the description of the problem we note immediately the
simila...