We present an algorithm for computing minimal-area fanout networks satisfying a delay constraint. We focus on one type of fanout network structure, the fanout chain. We show that, when using libraries designed for high-speed custom CMOS chips, the fanout chain typically produces minimal-area fanout networks for a given delay constraint. We then present fast, near-optimal algorithms to compute these fanout structures.

We present a technology mapper for full-custom ECL gates. These gates are characterized by high fanins and a regular structure. Full-custom gates differ from ECL library gates in that a full range of structures is available as a single form, rather than a large number of individual gates that sparsely cover the possible design space. This paper presents a complete Boolean matching algorithm and gives a proof of its correctness. We show that it can efficiently map logic into the general ECL gate form. We also show two variants of the algorithm, and show that they given poorer results with no savings in runtime. The mapper described in the paper is a necessary component of a CAD system for designing ECL microprocessors. Manual design of full-custom ECL gates would not be acceptable for control logic since it is a tedious, error prone, and lengthy activity. Nor would a gate-array style mapper and library with a limited number of gates be acceptable, because this makes less effective use of the inherent speed of the technology.

Retiming is an optimization technique for sequential circuits which consists in modifying the position of latches relative to blocks of combinational logic in order to minimize the maximum propagation delay between latches or to meet a given delay requirement while minimizing the number of latches. If the initial state of the circuit is meaningful, one must compute an equivalent initial state for the retimed circuit after retiming. The authors present a simple linear time algorithm to compute a correct initial state for a retimed circuit that can be used whenever the initial state of the original circuit satisfies a simple condition. If this condition is not originally satisfied, it is shown how it can be automatically enforced by a logic synthesis tool with no need for user intervention.>

An algorithm for computing local don't cares (in terms of immediate fanin variables) at each intermediate node of a Boolean network is presented. These don't cares can be directly used for the simplification of each node by a two-level minimizer. The simplification is relatively fast and the optimized circuits are 100% testable in most cases. The method is more powerful than previous ones developed for node simplification because it computes almost the full local don't care set at each node using image computation techniques. External don't cares are used effectively and there is no restriction on how these are represented because BDDs (binary decision diagrams) are used to translate them into local don't cares. This algorithm has been implemented in the sequential interactive logic synthesis system (SIS), and experimental results are presented that show the effectiveness of the proposed algorithm on benchmark circuits with and without external don't cares.>

The authors propose a novel technology-independent algorithm to minimize circuit delay. The algorithm works in two steps. The first step performs a partial collapse of the circuit based on a delay-driven clustering. The second step factorizes and simplifies the circuit without increasing the number of levels of logic. The computational cost of the algorithm is dominated by the simplification step. To estimate circuit delay, a state-of-the-art technology mapper is used, incorporating fanout optimization and tree covering for delay minimization. On average over a representative set of benchmarks, a delay reduction of 18% is obtained for an area increase of 11%.>

Abstract In performance analysis of computer systems, trace‐driven simulation techniques have the important advantage of credibility and accuracy. Unfortunately, traces are usually difficult to obtain, and little work has been done to provide efficient tools to help in the process of reducing and manipulating them. This paper presents TRAMP, a tool for the data reduction and data analysis phases of trace‐driven simulation studies. TRAMP has three main advantages: it accepts a variety of common trace formats; it provides a programmable user interface in which many actions can be directly specified; and it is easy to extend. TRAMP is particularly helpful for reducing and analysing complex trace data, such as traces of file system or database activity. This paper presents the design principles and implementation techniques of TRAMP and provides a few concrete examples of the use of this tool.

The authors address the problem of computing sequential don't cares that arise in the context of multi-level sequential networks and their use in sequential logic synthesis. The key to their approach is the use of binary decision diagram (BDD)-based implicit state space enumeration techniques and multi-level combinational simplification procedures. Using the algorithms described, exact sequential don't care sets for circuits with over 10/sup 68/ states have been successfully computed.>

The authors propose a novel method based on transition relations that only requires the ability to compute the BDD (binary decision diagram) for f/sub i/ and outperforms O. Coudert's (1990) algorithm for most examples. The method offers a simple notational framework to express the basic operations used in BDD-based state enumeration algorithms in a unified way and a set of techniques that can speed up range computation dramatically, including a variable ordering heuristic and a method based on transition relations.>