MARCO GSRC Calibrating Achievable Design: Bookshelf

Fundamental Slot (see other slots)

Generic Hypergraph Formats, rev. 1.1

Work in progress: last updated Fri Nov 05 1999

Andrew Caldwell Andrew B. Kahng Igor Markov

Contents

I. Introduction
II. Hypergraphs (1 Overview. 2 .nodes, 3 .nets, 4 .wts)
III. Extensions for master-instance hierarchy (.masters)
IV. Addressing individual pins
V. Examples
VI. 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 that typically include one line of the form

    Format name  :  filename1  filename2   ...   filenameN

Format name   must be recognized by the reader software and the following filenames must have recognizable suffixes. Filenames can be mentioned in an arbitrary order and will be processed in the order relevant for a given multi-file format. We also allow CD command in .aux files (a "command" is the word that precedes the colon) for changing the current directory and will publish relevant system-independent specifications if there is interest to them.

The following agreements are common for all component and aux files


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. (x,y)-dimensions of nodes (defined either for all nodes or for none)
  4. Single-valued attributes of nodes
  5. Nets in terms of lists of incident nodes
  6. For each net-node incidence, the directionality of the resp. pin and its (x,y)-offset from the origin(center) of the node
  7. Allowed orientations (flippings/rotations) of each node (default to 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).
The above attributes are distributed among three files with extensions: .nodes, .nets and .wts.
One may use one-line .aux files of the following format to assemble the relevant files.
       HGraphWDims : file.nodes file.nets [file.wts] 
or
       HGraph : file.nodes file.nets [file.wts] 
where the files can be mentioned in any order (in the latter case, it is assumed that pin offsets are not specified). Note that the .wts file is optional. Missing .wts file implies unit-area 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: .nodes, .nets, .wts All formats start with a line mentioning the format name and revision, e.g.,
        UCLA nets  1.0
        UCLA wts   1.0
        UCLA nodes 1.0
and are typically followed by commented lines with info about the origin of the file
        # Date:  
        # Author:  
and the like.

II.2. The .nodes format

The .nodes file specifies the name and other optional information about each node in the hypergraph. Each line specifies a single node. After the standard header, the format specifies:

NumNodes : total number of nodes
NumTerminals : number of terminal (pad etc.) nodes

Then, one line for each node with format as follows:

nodeName   [ nodeDimensions (default (0,0)]   [ : symmetry (default none)]   [ terminal (default is non-terminal)]

nodeName
is an arbitrary-length alpha-numeric string, which may include any number of characters from: {(a-z), (A-Z), (0-9), '_', '/', '\', '+' and '-'} node names are case-sensitive.
nodeDimensions
is a pair of white-space separated doubles indicating width, then height when in N orientation.
symmetry
specifies the axes about wihch the node may be flipped. Symmetry is given as any combination (in any order) of 'X', 'Y' and 'R90'. R90 means the node may be rotated 90 degrees. If no symmetry is present, the node is assumed to be not flippable.
``terminal''
is a literal that indicates that the node is a terminal
II.3. 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.

The file starts with

Standard header (as specified in section I.2)
NumNets : total number of nets
NumPins : total number of net-node connections

followed by at least total number of number of nets   netSpecifications that list all nodes incident to each individual net.

Each netSpecification consists of:

NetDegree : number of pins on the net [netName]
nodeName1 [pinDirection] [: pinOffset]
nodeName2 [pinDirection] [: pinOffset]
....
nod3NameN [pinDirection] [: pinOffset]

Net names should comply with the same restrictions as node names (above) but are optional. Unnamed nets may be assigned default names by the parser - 27-th net should be named NET27 etc (even if some nets 1-27 were named). If this collides with other named nets, the parser should add lowercase letters until it finds an available name (e.g., NET27a, NET27b,.. NET27aa etc). Note that checks for name clashes may need to be performed atfer all names nets are parsed.

If the number of nodeNames does not match the netDegree, a fatal parser error should occur with a relevant error message printed. A nodeName may appear more than once for the same net. This indicates multiple connections to a node. This functionality is intended to support block placement, but is not very essential in standard cell placement, in which case it is acceptable to ignore all but the first incidence of a node.

The optional pinDirection is given exactly as in the .netD format. (I for input, O for output, B for bidirectional)

A .nets parser should additionally check for an optional colon (:) separated by blanks as the next word. If the colon is not found, everything is ignored until the end of the line, and the pin is placed at the center of the node.

If the slash is found, two doubles are expected, separated by blanks - x and y pin offset from the origin (center) of the node. Each double can start with a percent sign, in which case it is relative to 1/2 of the respective (X or Y) dimension of the respective node (this is useful for soft macros in floorplanning).


II.4 The .wts format (weights)

The .wts format specifies the weights for each node. The format lists all weights for a given node on a single line. All nodes need not appear, however, each line must include the same number of weights. Missing nodes will have all weights set to 0. 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 may appear in any order. 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. Net names may be default net names (e.g., NET27) that generated when reading .nets files. Each weight is a double.


III. Extensions for master-instance hierarchy(.masters)

The extensions for master-instance hierarchy consist of


IV. Addressing individual pins

Individual pins can be theoretically addressed in four ways
By absolute name or number
typically inconvenient because it does give easy addressing of pins while traversing a node or a net; global numbers are risky because the internal numbering of pins may depend on the order in which nodes or nets were parsed
By name or number relative to a concrete node or master cell
convenient for addressing pins while traversing nodes, but not convenient while traversing nets. Names are better than numbers, but it may be expensive to store a hash-table at every instance node (if there is no master-instance hierarchy). This is very convenient if master-instance hierarchy is available.
By name or number relative to a net
convenient for addressing pins while traversing nets, but not convenient while traversing nodes. The remark about numbers versus names above applies; however, the availability of master-instance hierarchy brings no simplifications.
Via incidence of a node (not master cell) and a net
Multiple pins on a node that are incident to the same net cannot be addressed (only one can). The method is convenient for addressing pins during both types of traversals (nodes and nets), but may require precomputing a global hash-table for constant-time access (all combinations of pin/net must be hashed) the availability of the master-instance hierarchy does not help.
Of the four, we think that only two are of practical interest. Incidence addressing is good for its simplicity, in fact, it is available once all nodes and nets are named. Pin-on-node addressing is good for its scalability, but not yet supported in our formats.


V. Examples

SmallTestcase 1 (desrciption) (nodes/nets/wts) (netD/areM)
ISPD '98 Benchmark Suite (description) (nodes/nets/wts) (netD/areM)



VI. Executables
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 dimish 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.

Note - HGConv has not yet been updated to the new master-instance notation included in revision1.1 of this document.



Back to Bookshelf Slots

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