MARCO GSRC Calibrating Achievable Design: Bookshelf
Generic Hypergraph Formats, rev. 1.1
: last updated Fri Nov 05 1999
Contents
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 - allow easy mixing of attributes
- allow for reasonable defaults for missing attributes
- reduce total storage requirements (through reuse) if many combinations of the same attributes are of interest
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
- blank characters are spaces and tabs.
- multiple blank characters are equivalent to one
- a colon (:) must always be preceded and followed by a space
- the pound sign (#) denotes commented out lines and is only guaranteed to be processed correctly if all characters earlier on the line are blank characters
- when the tokens expected to be found on the line are successfully parsed, all characters until the end of the line must be ignored (this allows for easy extensions); a one-time warning must be issued by the parser if any non-blank characters were ignored: "Non-blank characters are ignored until the end of line XXX and, possibly, later".
- if the line-end character is encountered before all tokens are parsed, a fatal error message "Unexpected line end on line XXX" must be generated.
- all units with dimensions, such as locations, offsets, sizes, weights etc, can be specified as doubles. It is possible to use integers, but we felt that restricting to integers may be too risky as, e.g., Cadence Design Systems, Inc. LEFDEF specifies doubles. We believe that resolving 3.000000 vs 2.99999 (that may arise if a particular program expects an integer) is not difficult via rounding to integers and checking with a reasonably small round-off tolerance. This should be done by the programs that save doubles (i.e., test if a number to be saved is epsilon-close to an integer, and if it is, round it up before saving). Physical design tools that use floats internally (less memory needed than when using doubles) should read doubles and check for overflows during conversion to floats.
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):
- The number of nodes and nets
- Names of all nodes
- (x,y)-dimensions of nodes (defined either for all nodes or for none)
- Single-valued attributes of nodes
- Nets in terms of lists of incident nodes
- For each net-node incidence, the directionality of the resp. pin and its (x,y)-offset from the origin(center) of the node
- 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 - An additional file with extension .masters that uses the .nodes format but is parsed before the .nodes file. The names from the .master file are interpreted as names of master cells that can be instantiated in the .nodes file.
- Extended syntax for the .nodes files.
Instead of nodeName [ nodeDimensions (default 0 0] [ : symmetry (default none)] [ terminal (default is non-terminal)]
we also allow (i.e., either syntax is allowed)
nodeName isA masterName
with literal "isA". This means that pin geometries for nodeName are exactly as in masterName
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
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
