Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Packing Algorithm for Massively Distributed Simulation Engine

IP.com Disclosure Number: IPCOM000107965D
Original Publication Date: 1992-Apr-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 6 page(s) / 256K

Publishing Venue

IBM

Related People

Beece, DK: AUTHOR [+2]

Abstract

A technique is described whereby a packing algorithm for the massively distributed simulation engine (MDSE) leads to a reduction in logic gate counts and a reduction in the length of the longest path. Statistics of two design models are described.

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

Packing Algorithm for Massively Distributed Simulation Engine

       A technique is described whereby a packing algorithm for
the massively distributed simulation engine (MDSE) leads to a
reduction in logic gate counts and a reduction in the length of the
longest path.  Statistics of two design models are described.

      The concept outlines optimization goals and the relevance with
the parallelism of the hardware simulator. Described are the clean-up
and packing phases as well as the various local transforms employed.
Compared are the various statistics and results of optimization using
MDSEOPT and COALESCE.

      The MDSE (1), special-purpose hardware simulator, and its
precursor EVE (2) utilize EVETRAN (3) to convert a register level
description, BDL/CS, into a gate level description, called NODES,
which is then compiled, linked and loaded into EVE.  EVETRAN consists
of two stages.  In the first stage, BDL/CS is translated by XLATE
into a set of logic gates, called TEMP.  In the second stage,
COALESCE is optimized into NODES.  The concept described herein is to
generate an improved optimizer, henceforth referred to as MDSEOPT,
which better exploits the design requirements of MDSE.

      The structure of MDSEOPT is basically the same as that of
COALESCE, which includes an initial clean-up phase and then a packing
phase.  The initial clean-up phase removes constant inputs,
duplicates gates, one input gates, irrelevant dangling gates, and
other redundancies in the TEMP file.  The major difference between
MDSEOPT and COALESCE lies in the packing phase, which is the
combination of several gates into one gate with a new function
provided that the total fanin of the resultant gate is four or less.
The resultant function, after packing in COALESCE, is restricted to
certain prescribed ones, whereas the resultant functions in MDSEOPT
can be any of 216 four-input one- output logic gates.  Furthermore,
the packing phase is split into three stages and a level reducing
algorithm is implemented.  These added features in MDSEOPT account
for most of its improvement over COALESCE.

      The most obvious goal of a logic optimizer is to reduce the
number of logic gates needed to perform a specified function.  Fewer
gates in a circuit usually lead to faster simulation.  However, since
the target simulator consists of a large number of parallel
processors, each with a fixed depth, the number of levels in the
circuit could become an important parameter.  For example, if the
number of levels approaches or exceeds the depth of a logic
processor, the partitioning and scheduling problem becomes difficult.
As a result, the parallelism of the hardware simulator cannot be
fully exploited, leading to degradation of performance.  A third
parameter which measures the performance of the optimizer is the
percentage of gate utilization, such as:

                            (Image Omitted)

where FANIN(n) is th...