 |
 |
|
|
Networks provide a suitable representation for connectivity. Most commonly, nodes of a network are electronic components and arcs are connecting wires. Some systems reverse this to represent wires as nodes and components as arcs [Karplus]. Without significant loss of generality, the discussion here will adopt the former assumption to show how networks can represent connectivity.
In network representations, there are two types of objects: nodes and arcs. Each arc object connects exactly two nodes and so it has attributes that identify these two objects. However, it is not as easy to list every arc that connects to a node because there is no limit to the number of connections that a node can have. In addition to this need for unlimited arc pointers, there may be other attribute information associated with these node-arc connections. For this reason, a connection object is used to link nodes and arcs, called a port. A port is the site of an arc connection on a node. By having explicit port objects in a linked list, it is possible to represent an unlimited number of connecting arcs on a node and to store any information about the connection.
 |
| FIGURE 3.11 Node, arc, and port objects form a network. |
| The most basic connectivity representation has node, arc, and port objects (see Fig. 3.11). The node and arc objects in this figure are named and so have "name" attributes, which identify them. These objects also have "link" attributes, which collect them into two lists that form the circuit. An external list head for these lists is all that is needed to identify the entire collection. To link arcs with nodes, each arc object has a "from" and "to" attribute that points to node objects. Also, each node object has a "first port" attribute that heads a list of port objects. If there are no arcs connected to a node (as in node E of the figure), then this field is null because there are no ports. For every arc that does connect, there is a port object that contains a pointer to that arc. The port object also has a "next port" attribute that points to the next port object in the linked list on the node. When there are no more arc connections, and therefore no more ports, the "next port" attribute contains a null value to terminate the list. Figure 3.12 shows the circuit in a more natural way. |
|
| When representing a VLSI circuit both geometrically and as a network, there is a question about how the geometry of components and wires will relate. Since the wire attaches onto the component, its geometry will overlap that of the component. Also, when two wires meet, their geometry must be correct at the intersection point. Three popular approaches are for wires to be rounded, for them to extend beyond the endpoint by one-half of their width, and for them to terminate cleanly at their endpoint (see Fig. 3.13). With no extension, some additional geometry must appear at wire intersections to make a correct connection. If this additional material is round, the wires can meet at all angles. With an extension of one-half of the width, wires will meet correctly when at orthogonal orientations. However, extended wires that meet at nonorthogonal angles will have to extend somewhere between zero and one-half of the wire width [Mead and Conway]. Yet another problem in the one-half-width extension scheme is that the two wires may have differing widths. In this case, wire extension should be by one-half of the width of the narrowest wire. |
|
The representation of connected networks is somewhat complex. Part of this complexity is a response to the need for arbitrary circuit-size capacity and part is a result of cooperation with other representational needs.
|
Previous |  |
Table of Contents | Next | |
Static Free Software |  |
