MARCO GSRC Calibrating Achievable Design: Bookshelf

Fundamental Slot (see other slots)

Netlist/Generic Hypergraph Slot, rev. 1.2

Work in progress: last updated Sun Nov 21 1999

Andrew Caldwell Andrew B. Kahng Igor Markov

Contents

0. Older version (including old format descriptions)
I. Introduction
II. Hypergraphs (1 Overview. 2 .masters, 3 .masterpins, 4 .mastertime, 5 .nodes, 6 .nets, 7 .wts)
III. Examples
IV. Executables

I. Introduction

The proposed formats are designed to be simple and easily human readable, as well as conveniently parsable. Whether you are interested in pin geometries or not, you can use the proposed formats without extra overhead. We are motivated by the desires to Therefore, we distribute placement information over several component files. To assemble multiple component files into problem instances, we use .aux files.

All Netlist/Hypergraph format follow the general bookshelf format guidelines.

II. Hypergraphs with pins

II.1. Overview of the multi-file format

We consider the following attributes of directed circuit hypergraphs (many of them optional):

  1. The number of nodes and nets
  2. Names of all nodes
  3. Node type
  4. (x,y)-dimensions of nodes
  5. Single-valued attributes of nodes
  6. Nets in terms of lists of incident nodes and optionally pins
  7. For each net-node incidence, the directionality of the resp. pin and its (x,y)-offset from the center of the node
  8. Current Orientation and node Symmetries (determines allowed flippings/rotations) of each node (default is N).
Orientations :
the default orientation is "vertically and face up" - N (North). Rotate by 90deg clockwise to get E, S and W, flip to get FN, FE, FS and FW. (think of a dial).
Symmetries:
X and Y - allows flips around axis, ROT90 - allows any of rotations by 0, 90, 180 or 270 degrees
Usage
A given set of symmetries, e.g., X ROT90, is typically applied to a given orientation, e.g., N, to produce a set of allowed orientations (all orientations will be allowed in this case). If a node has X symmetry and a N orientation, then it can legally have either N or FS orientation, for example.
The above attributes are distributed among four files with extensions: .masters, .nodes, .nets and .wts. Currently defined .aux file tags are: Note that the files can be mentioned in any order. The .wts file is always optional. Missing .wts file implies unit-weight for all nodes. The order in which files are parsed is independent of the order in which they are mentioned in the .aux file and is as follows: .masters, .nodes, .nets, .wts All formats start with an XML element, a < header>. The header currently contains an entry for the author name, and creation date.

II.2. The .masters format

The .masters format defines information about master nodes. It can be viewed as a libary of node types in the hypergraph. Each vertex in the .nodes file is an instance of a master node (an identical copy). For example, a typical standard cell netlist will define a small number of master node in the .masters file, with many instances of each in the .nodes file. A block placement instance, where each block is unique, will have a N master nodes and N instances in the .nets file -- each master will have only one instance.

If you do not need to know pin directions/offsets, node dimensions and other information (e.g. for weighted hypergraph partitioning), you do not need to parse the .masters file (the .nodes file contains the names of all instances, and the .nets provides connectivity information).

proposed .masters DTD
sample masters XML file (best viewed with MS Internet Explorer5.0 -- Netscape4.7 does not support XML)

The following give semantic constraints (not enforced by XML) and some aspects of [semantic] interpretation.

master
name are required and must be unique
delay is (a rough measure of) the cell delay
unateness is only meaningful for buffers and inverters
In attribute names, "AR" stands for "aspect ratio"
pin/areaPin
pin names are required and must be unique within a given master
res is driver resistance
cap is load capacitance
x and y components for relOffset are specified in percents of the node width or height. Percentages should be >eq; 0 and <eq; 100.
x and y components for absOffset are actual offsets from the node center (geometric). Typically offsets are between (+/-master width/2, +/-master height/2).
relRange/absRange specify a min and max relative or absolute offset. max's should be >eq; min's.

II.3. The .masterpins format 


BEGIN MASTERPIN
MASTERCELLNAME 
PIN  
PORT   
PORT   
PORT   

 a PORT is on a layer, and is a polygon specified by a list of vertex
 locations (offsets from the cell center); the locations
 are specified as doubles SEparated by spaces.   the list of vertex
 locations does not start/end with the same vertex, i.e., it is not
 a closed list.

 STRONGCONNECTED means that the ports are connected by metal wire inside
 the cell, so the router may connect to more than one port and assume
 that this is electrically reasonable.
 WEAKCONNECTED means that the ports are connected by poly wire inside
 the cell, so the router cannot connect to more than one port without
 incurring too much resistance/delay.
 MUSTCONNECT is a flag for the detailed router, saying that the ports
 must be connected by routing (typically in hierarchical design).
II.4. The .mastertime format

BEGIN TIMINGMODELS CellMasterName

FROMPIN pinId
TOPIN pinId
DIRECTION {RISE | FALL}
DELAY {CELL | TRANSITION}
UNATENESS {INVERT | NONINVERT}
TABLEDIMENSIONS N1 N2
TABLEAXIS1 f1, f2, ..., fN1
TABLEAXIS2 f1, f2, ..., fN2
INTERPOLATION {LINEAR | SPLINE}
TABLEENTRIES
(( min11 typ11 max11 ) (min12 typ12 max12) ... (min1fN2 typ1fN2 max1fN2))
(( min21 typ21 max21 ) (min22 typ22 max22) ... (min2fN2 typ2fN2 max2fN2))
...
(( minfN11 typfN11 maxfN11 ) (minfN12 typfN12 maxfN12) ... (minfN1fN2 typfN1fN2 maxfN1fN2))

END TIMINGMODELS
 II.5. The .nodes format

The .nodes file specifies the name of nodes/cells/blocks in the netlist/hypergraph. Each is an instance (a copy) of a MASTER defined in the .masters file.

If you do not care about any of the information contained in the .masters format (i.e. for balanced hypergraph partitioning), you may ignore everything but the instanceName. The .nodes file then simply supplies the list of node names in the instance.

proposed .nodes DTD
sample nodes XML file

II.6. The .nets format

The .nets format specifies the connections in the hypergraph. The format is similar to the .net and .netD formats, as it specifes nets by listing their incident nodes and optionally the pin on the node.

proposed .nets DTD
sample nets XML file

II.7 The .wts format (weights)

The .wts format specifies weights for nodes and nets. The format lists all weights for a given node/net on a single line. All nodes/nets need not appear. However, all nodes that are listed must have the same number of weights, as must all nets. (nodes and nets do not need to have the same number of weights...just all nodes, and seperately, all nets). Missing nodes will have all weights set to 0. Missing nets will have a weight of 1. This is to accommodate the most common partitioning and placement use models. The parser will determine the number of weights by counting the number of values given for the first node (taken from the first line). Nodes/nets may appear in any order, and may be mixed.

The format of each line is:

nodeName   weight1   [weight2]   [weight3]

or

netName   weight1   [weight2]   [weight3]

where nodeName and netName use characters allowed for nodenames in .nodes files.

II. Examples

NOTE!! These examples are out of date! We are converting to XML (probably). These examples are in the older format. They will be updated very shortly.

IV. Executables

NOTE!! These are out of date! We are converting to XML. All executables below were built to read/write the older nodes/nets format. They will be updated very shortly.

HGConv1.0 (Sun Solaris 2.7) (Intel-Linux) (Win95/98/NT)
HGConv1.0 both reads and writes the older netD/areM hypergraph format as well as the new nodes/nets/wts format. This allows it to be used as a converter between the two, or simply to check compliance with the standard. If HGConv can parse your file, it meets the standard. If not, then after checking your file thoroughly send us email (it's of course possible that there's a bug in HGConv..the odds of this will diminish as more people use it).

HGConv1.0 produces a number of useful statistics about the Hypergraph, including counts of edges, nodes, terminals and non-terminals, as well as a profile of node weights and widths and edge degrees.

Finally, HGConv1.0 provides the -setDims HEIGHT command, which sets all non-terminal node heights to HEIGHT, and each node's width such that node's area equals the node's first weight.

notation included in revision1.1 of this document.

Back to Bookshelf Slots

caldwell@cs.ucla.edu,abk@ucsd.edu,imarkov@cs.ucla.edu