route.java

The ElectricTM VLSI Design System is an open-source Electronic Design Automation (EDA) system that c

	 * @return the created ZRG.
	 */
	private RouteZRG createZRG(RouteChannel channel)
	{
		RouteZRG firstZone = null, lastZone = null;
		int zNumber = 0;

		// create first zone
		RouteZRG zone = new RouteZRG();
		zone.number = zNumber++;
		zone.chNodes = null;
		zone.next = null;
		zone.last = null;
		firstZone = lastZone = zone;

		// clear flag on all channel nodes
		int numChNodes = 0;
		for (RouteChNode chNode = channel.nodes; chNode != null; chNode = chNode.next)
		{
			chNode.flags &= ~ROUTESEEN;
			numChNodes++;
		}

		// allocate enough space for channel node temporary list
		RouteChNode [] chNodeList = new RouteChNode[numChNodes+1];

		for(;;)
		{
			RouteChNode leftChNode = findLeftmostChNode(channel.nodes);
			if (leftChNode == null) break;
			createZRGTempList(channel.nodes, leftChNode.firstPort.xPos, chNodeList);
			if (zrgListCompatible(chNodeList, zone))
			{
				zrgAddChNodes(chNodeList, zone);
			} else
			{
				zone = new RouteZRG();
				zone.number = zNumber++;
				zone.chNodes = null;
				zone.next = null;
				zone.last = lastZone;
				lastZone.next = zone;
				lastZone = zone;
				zrgAddChNodes(chNodeList, zone);
			}
			leftChNode.flags |= ROUTESEEN;
		}

		// print out zone representation if verbose flag set
		if (DEBUG)
		{
			System.out.println("************ ZONE REPRESENTATION GRAPH");
			for (zone = firstZone; zone != null; zone = zone.next)
			{
				System.out.println("Zone " + zone.number + ":");
				for (RouteZRGMem mem = zone.chNodes; mem != null; mem = mem.next)
					System.out.println("    Node " + mem.chNode.number);
			}
		}
		return firstZone;
	}

	/**
	 * Method to return a pointer to the unmarked channel node of the indicated
	 * channel which has the left-most first port.
	 * If no channel nodes suitable found, return null.
	 * @param nodes pointer to a list of channel nodes.
	 * @return pointer to leftmost node, null if none unmarked found.
	 */
	private RouteChNode findLeftmostChNode(RouteChNode nodes)
	{
		RouteChNode leftChNode = null;
		double leftXPos = Double.MAX_VALUE;

		for (RouteChNode node = nodes; node != null; node = node.next)
		{
			if ((node.flags & ROUTESEEN) != 0) continue;
			if (node.firstPort.xPos < leftXPos)
			{
				leftXPos = node.firstPort.xPos;
				leftChNode = node;
			}
		}

		return leftChNode;
	}

	/**
	 * Method to fill in the temporary list of all channel nodes which encompass the indicated x position.
	 * @param nodes list of channel nodes.
	 * @param xPos X position of interest.
	 * @param list array of pointer to fill in, terminate with a null.
	 */
	private void createZRGTempList(RouteChNode nodes, double xPos, RouteChNode [] list)
	{
		int i = 0;
		for (RouteChNode node = nodes; node != null; node = node.next)
		{
			if (xPos > node.firstPort.xPos - SilComp.getMinPortDistance()
				&& xPos < node.lastPort.xPos + SilComp.getMinPortDistance())
					list[i++] = node;
		}
		list[i] = null;
	}

	/**
	 * Method to return a TRUE if the indicated list of channel nodes is compatible
	 * with the indicated zone, else return FALSE.
	 * @param list array of pointers to channel nodes.
	 * @param zone pointer to current zone.
	 * @return true if compatible.
	 */
	private boolean zrgListCompatible(RouteChNode [] list, RouteZRG zone)
	{
		if (zone.chNodes != null)
		{
			// check each member of current zone being in the list
			for (RouteZRGMem mem = zone.chNodes; mem != null; mem = mem.next)
			{
				int i;
				for (i = 0; list[i] != null; i++)
				{
					if (mem.chNode == list[i]) break;
				}
				if (list[i] == null) return false;
			}
			return true;
		}

		// no current channel nodes, so compatible
		return true;
	}

	/**
	 * Method to add the channel nodes in the list to the indicated zone if they
	 * are not already in the zone.
	 * @param list list of channel nodes.
	 * @param zone pointer to current zone.
	 */
	private void zrgAddChNodes(RouteChNode [] list, RouteZRG zone)
	{
		for (int i = 0; list[i] != null; i++)
		{
			RouteZRGMem mem;
			for (mem = zone.chNodes; mem != null; mem = mem.next)
			{
				if (mem.chNode == list[i]) break;
			}
			if (mem == null)
			{
				mem = new RouteZRGMem();
				mem.chNode = list[i];
				mem.next = zone.chNodes;
				zone.chNodes = mem;
			}
		}
	}

	/**
	 * Method to use the Vertical Constraint Graph and the Zone Representation
	 * Graph, assign channel nodes to tracks.
	 * @param vcg pointer to Vertical Constraint Graph.
	 * @param zrg pointer to Zone Representation Graph.
	 * @param nodes pointer to list of channel nodes.
	 * @return created tracks.
	 */
	private RouteTrack trackAssignment(RouteVCG vcg, RouteZRG zrg, RouteChNode nodes)
	{
		RouteTrack firstTrack = null, lastTrack = null;
		int trackNumber = 0;

		// create first track
		RouteTrack track = new RouteTrack();
		track.number = trackNumber++;
		track.nodes = null;
		track.last = null;
		track.next = null;
		firstTrack = lastTrack = track;

		// clear flags on all channel nodes
		int numberNodes = 0;
		for (RouteChNode node = nodes; node != null; node = node.next)
		{
			node.flags = 0;
			numberNodes++;
		}
		RouteChNode [] nList = new RouteChNode[numberNodes+1];

		// get channel node on longest path of VCG
		for(;;)
		{
			RouteChNode node = longestVCG(vcg);
			if (node == null) break;

			// clear flags of all nodes
			for (RouteChNode node2 = nodes; node2 != null; node2 = node2.next)
				node2.flags = 0;

			// add node to track
			addNodeToTrack(node, track);

			// mark all other nodes in the same zones as not usable
			markZones(node, zrg, ROUTEUNUSABLE);

			// find set of remaining nodes which can be added to track
			findBestNodes(vcg, zrg, nList, numberNodes + 1);

			// add to track
			for (int i = 0; nList[i] != null; i++)
			{
				addNodeToTrack(nList[i], track);
			}

			// delete track entries from VCG
			deleteFromVCG(track, vcg);

			// create next track
			track = new RouteTrack();
			track.number = trackNumber++;
			track.nodes = null;
			track.last = lastTrack;
			lastTrack.next = track;
			lastTrack = track;
		}

		// delete last track if empty
		if (track.nodes == null)
		{
			if (track.last != null)
			{
				track.last.next = null;
			} else
			{
				firstTrack = null;
			}
		}

		// print out track assignment if verbose flag set
		if (DEBUG)
		{
			System.out.println("************ TRACK ASSIGNMENT");
			for (track = firstTrack; track != null; track = track.next)
			{
				System.out.println("For Track #" + track.number + ":");
				for (RouteTrackMem mem = track.nodes; mem != null; mem = mem.next)
					System.out.println("    " + mem.node.number + "     " + mem.node.firstPort.xPos + "  " + mem.node.lastPort.xPos);
			}
		}

		return firstTrack;
	}

	/**
	 * Method to mark all channel nodes in the same zones as the indicated zone as indicated.
	 * @param node channel node in question.
	 * @param zrg zone representation graph.
	 * @param bits bits to OR in to nodes flag field.
	 */
	private void markZones(RouteChNode node, RouteZRG zrg, int bits)
	{
		// mark unusable nodes
		for (RouteZRG zone = zrg; zone != null; zone = zone.next)
		{
			RouteZRGMem zMem;
			for (zMem = zone.chNodes; zMem != null; zMem = zMem.next)
			{
				if (zMem.chNode == node) break;
			}
			if (zMem != null)
			{
				for (zMem = zone.chNodes; zMem != null; zMem = zMem.next)
					zMem.chNode.flags |= bits;
			}
		}
	}

	/**
	 * Method to return a pointer to the channel node which is not dependent on
	 * any other nodes (i.e. top of Vertical Constraint Graph) and on
	 * the longest path of the VCG.  If a tie, return the first one.
	 * If none found, return null.  Remove and update VCG.
	 * @param vcg pointer to Vertical Constraint Graph.
	 * @return channel node, null if node.
	 */
	private RouteChNode longestVCG(RouteVCG vcg)
	{
		RouteChNode node = null;
		double longestPath = 0;

		// check for all entries at the top level
		for (RouteVCGEdge edge = vcg.edges; edge != null; edge = edge.next)
		{
			double path = pathLength(edge.node);
			if (path > longestPath)
			{
				longestPath = path;
				node = edge.node.chNode;
			}
		}

		return node;
	}

	/**
	 * Method to return the length of the longest path starting at the indicated
	 * Vertical Constraint Graph Node.
	 * @param vcgNode vertical Constraint Graph node.
	 * @return longest path length.
	 */
	private double pathLength(RouteVCG vcgNode)
	{
		if (vcgNode.edges == null) return 1;

		// check path for all edges
		double longest = 0;
		for (RouteVCGEdge edge = vcgNode.edges; edge != null; edge = edge.next)
		{
			double path = pathLength(edge.node);
			if (path > longest) longest = path;
		}

		return longest + 1;
	}

	/**
	 * Method to add the indicated channel node to the track and mark as seen.
	 * Note add the node in left to right order.
	 * @param node pointer to channel node to add.
	 * @param track pointer to track to add to.
	 */
	private void addNodeToTrack(RouteChNode node, RouteTrack track)
	{
		RouteTrackMem mem = new RouteTrackMem();
		mem.node = node;
		mem.next = null;
		if (track.nodes == null)
		{
			track.nodes = mem;
		} else
		{
			RouteTrackMem oldMem = track.nodes;
			RouteTrackMem mem2;
			for (mem2 = track.nodes; mem2 != null; mem2 = mem2.next)
			{
				if (mem.node.firstPort.xPos > mem2.node.firstPort.xPos)
				{
					oldMem = mem2;
				} else
				{
					break;
				}
			}
			mem.next = mem2;
			if (mem2 == track.nodes)
			{
				track.nodes = mem;
			} else
			{
				oldMem.next = mem;
			}
		}

		node.flags |= ROUTESEEN;
	}

	/**
	 * Method to find the set of remaining nodes with no ancestors in the Vertical
	 * Constraint Graph which are available and are of maximum combined length.
	 * @param vcg vertical Constraint Graph.
	 * @param zrg zone Representation Graph.
	 * @param nList array to write list of selected nodes.
	 * @param num maximum size of nList.
	 */
	private void findBestNodes(RouteVCG vcg, RouteZRG zrg, RouteChNode [] nList, int num)
	{
		int i = 0;
		nList[i] = null;

		// try all combinations
		for(;;)
		{
			// find longest, usable edge
			RouteVCGEdge edge2 = null;
			double maxLength = 0;
			for (RouteVCGEdge edge = vcg.edges; edge != null; edge = edge.next)
			{
				if ((edge.node.chNode.flags & (ROUTESEEN | ROUTEUNUSABLE)) != 0) continue;
				double length = edge.node.chNode.lastPort.xPos - edge.node.chNode.firstPort.xPos;
				if (length >= maxLength)
				{
					maxLength = length;
					edge2 = edge;
				}
			}
			if (edge2 == null) break;

			// add to list
			nList[i++] = edge2.node.chNode;
			nList[i] = null;
			markZones(edge2.node.chNode, zrg, ROUTEUNUSABLE);
		}
	}

	/**
	 * Method to delete all channel nodes in the track from the top level of the
	 * Vertical Constraint Graph and update VCG.
	 * @param track pointer to track.
	 * @param vcg pointer to Vertical Constraint Graph.
	 */
	private void deleteFromVCG(RouteTrack track, RouteVCG vcg)
	{
		// for all track entries in VCG
		for (RouteTrackMem mem = track.nodes; mem != null; mem = mem.next)
		{
			RouteVCGEdge edge2 = vcg.edges;
			for (RouteVCGEdge edge = vcg.edges; edge != null; edge = edge.next)
			{
				if (edge.node.chNode != mem.node)
				{
					edge2 = edge;
					continue;
				}

				// remove from top level VCG
				if (edge == vcg.edges) vcg.edges = edge.next;
					else edge2.next = edge.next;

				// check if its edges have nodes which should be added to VCG
				for (edge2 = edge.node.edges; edge2 != null; edge2 = edge2.next)
					edge2.node.flags &= ~ROUTESEEN;

				// mark any child edges
				for (edge2 = edge.node.edges; edge2 != null; edge2 = edge2.next)
					markVCG(edge2.node.edges);

				markVCG(vcg.edges);
				RouteVCGEdge edge3 = null;
				for (edge2 = edge.node.edges; edge2 != null; edge2 = edge3)
				{
					edge3 = edge2.next;
					if ((edge2.node.flags & ROUTESEEN) == 0)
					{
						// add to top level
						edge2.next = vcg.edges;
						vcg.edges = edge2;
					}
				}
				break;
			}
		}
	}

	/**
	 * Method to recursively mark all nodes of Vertical Constraint Graph called by other nodes.
	 * @param edges list of edges.
	 */
	private void markVCG(RouteVCGEdge edges)
	{
		if (edges == null) return;

		for ( ; edges != null; edges = edges.next)
		{
			edges.node.flags |= ROUTESEEN;
			markVCG(edges.node.edges);
		}
	}

	/**
	 * Method to add data to insure that input ports of the row below tied to power
	 * are handled correctly.