route.java

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

				// EMPTY
			} else if (right)
			{
				// create special place for export at end of row
				bestChPort = createSpecial(port.node, bestChPort, false, cell);
			} else if (left)
			{
				// create special place for export at start of row
				bestChPort = createSpecial(port.node, bestChPort, true, cell);
			}

			// add port to export list
			RouteExport nExport = new RouteExport();
			nExport.xPort = port;
			nExport.chPort = bestChPort;
			nExport.next = lExport;
			lExport = nExport;
		}

		return lExport;
	}

	/**
	 * Method to create a special place on either the start or end of the row where
	 * the passed channel port real port resides.
	 * @param inst instance for place to point to.
	 * @param chPort channel port in question.
	 * @param w true at start, false at end.
	 * @param cell parent cell.
	 * @return newly created channel port.
	 */
	private RouteChPort createSpecial(GetNetlist.SCNiTree inst, RouteChPort chPort, boolean where, GetNetlist.SCCell cell)
	{
		inst.size = SilComp.getFeedThruSize();
		inst.ports.xPos = SilComp.getFeedThruSize() / 2;

		// find row
		Place.RowList row = chPort.port.node.row.row;

		// create appropriate place
		Place.NBPlace nPlace = new Place.NBPlace();
		nPlace.cell = inst;
		if (where)
		{
			if (row.start != null)
			{
				double xpos = row.start.xPos - SilComp.getFeedThruSize();
				nPlace.xPos = xpos;
				row.start.last = nPlace;
			} else
			{
				nPlace.xPos = 0;
			}
			nPlace.last = null;
			nPlace.next = row.start;
			row.start = nPlace;
		} else
		{
			if (row.end != null)
			{
				nPlace.xPos = row.end.xPos + row.end.cell.size;
				row.end.next = nPlace;
			} else
			{
				nPlace.xPos = 0;
			}
			nPlace.next = null;
			nPlace.last = row.end;
			row.end = nPlace;
		}

		// create a route port entry for this new port
		RouteNode rNode;
		for (rNode = (RouteNode)chPort.node.extNode.ptr; rNode != null; rNode = rNode.sameNext)
		{
			if (rNode.row.number == row.rowNum) break;
		}
		RoutePort rPort = new RoutePort();
		rPort.place = nPlace;
		rPort.port = inst.ports;
		rPort.node = rNode;
		rPort.flags = 0;
		rPort.next = null;
		rPort.last = rNode.lastPort;
		if (rNode.lastPort != null)
		{
			rNode.lastPort.next = rPort;
		} else
		{
			rNode.firstPort = rPort;
		}
		rNode.lastPort = rPort;

		// add to channel
		addPortToChannel(rPort, chPort.port.node.extNode,
			cell.route.channels, chPort.node.channel.number);

		return chPort.node.lastPort;
	}

	/**
	 * Method to route the tracks in each channel by using an improved channel router.
	 * @param channels list of all channels.
	 * @param cell pointer to parent cell.
	 */
	private void tracksInChannels(RouteChannel channels, GetNetlist.SCCell cell)
	{
		// do for each channel individually
		for (RouteChannel chan = channels; chan != null; chan = chan.next)
		{
			if (DEBUG)
				System.out.println("**** Routing tracks for Channel " + chan.number+ " ****");

			// create Vertical Constraint Graph (VCG)
			RouteVCG vGraph = createVCG(chan, cell);

			// create Zone Representation Graph (ZRG)
			RouteZRG zrGraph = createZRG(chan);

			// do track assignment
			RouteTrack tracks = trackAssignment(vGraph, zrGraph, chan.nodes);

			chan.tracks = tracks;
		}
	}

	/**
	 * Method to create the Vertical Constrain Graph (VCG) for the indicated channel.
	 * @param channel pointer to channel.
	 * @param cell pointer to parent cell.
	 * @return where to write created VCG.
	 */
	private RouteVCG createVCG(RouteChannel channel, GetNetlist.SCCell cell)
	{
		// first number channel nodes to represent nets
		int netNumber = 0;
		for (RouteChNode chNode = channel.nodes; chNode != null; chNode = chNode.next)
		{
			chNode.number = netNumber++;

			// calculate actual port position
			for (RouteChPort chPort = chNode.firstPort; chPort != null; chPort = chPort.next)
				chPort.xPos = portPosition(chPort.port);

			// sort all channel ports on node from leftmost to rightmost
			for (RouteChPort chPort = chNode.firstPort; chPort != null; chPort = chPort.next)
			{
				// bubble port left if necessay
				for (RouteChPort port2 = chPort.last; port2 != null; port2 = chPort.last)
				{
					if (port2.xPos <= chPort.xPos) break;

					// move chport left
					chPort.last = port2.last;
					port2.last = chPort;
					if (chPort.last != null)
						chPort.last.next = chPort;
					port2.next = chPort.next;
					chPort.next = port2;
					if (port2.next != null)
						port2.next.last = port2;
					if (port2 == chNode.firstPort)
						chNode.firstPort = chPort;
					if (chPort == chNode.lastPort)
						chNode.lastPort = port2;
				}
			}
		}

		// create the VCG root node
		RouteVCG vcgRoot = new RouteVCG();
		vcgRoot.chNode = null;
		vcgRoot.edges = null;

		// create a VCG node for each channel node (or net)
		for (RouteChNode chNode = channel.nodes; chNode != null; chNode = chNode.next)
		{
			RouteVCG vcgNode = new RouteVCG();
			vcgNode.chNode = chNode;
			vcgNode.edges = null;
			RouteVCGEdge vcgEdge = new RouteVCGEdge();
			vcgEdge.node = vcgNode;
			vcgEdge.next = vcgRoot.edges;
			vcgRoot.edges = vcgEdge;
		}

		vcgCreateDependents(vcgRoot, channel);

		// add any ports in this channel tied to power
		createPowerTies(channel, vcgRoot, cell);

		// add any ports in this channel tied to ground
		createGroundTies(channel, vcgRoot, cell);

		// remove all dependent nodes from root of constraint graph*/
		// clear seen flag
		for (RouteVCGEdge vcgEdge = vcgRoot.edges; vcgEdge != null; vcgEdge = vcgEdge.next)
			vcgEdge.node.flags &= ~ROUTESEEN;

		// mark all VCG nodes that are called by others
		for (RouteVCGEdge vcgEdge = vcgRoot.edges; vcgEdge != null; vcgEdge = vcgEdge.next)
		{
			for (RouteVCGEdge edge1 = vcgEdge.node.edges; edge1 != null; edge1 = edge1.next)
				edge1.node.flags |= ROUTESEEN;
		}

		// remove all edges from root which are marked
		RouteVCGEdge edge1 = vcgRoot.edges;
		for (RouteVCGEdge vcgEdge = vcgRoot.edges; vcgEdge != null; vcgEdge = vcgEdge.next)
		{
			if ((vcgEdge.node.flags & ROUTESEEN) != 0)
			{
				if (vcgEdge == vcgRoot.edges)
				{
					vcgRoot.edges = vcgEdge.next;
					edge1 = vcgEdge.next;
				} else
				{
					edge1.next = vcgEdge.next;
				}
			} else
			{
				edge1 = vcgEdge;
			}
		}

		// print out Vertical Constraint Graph if verbose flag set
		if (DEBUG)
		{
			System.out.println("************ VERTICAL CONSTRAINT GRAPH");
			for (edge1 = vcgRoot.edges; edge1 != null; edge1 = edge1.next)
			{
				System.out.println("Net " + edge1.node.chNode.number + ":");
				printVCG(edge1.node.edges, 1);
			}
		}

		return vcgRoot;
	}

	/**
	 * Method to resolve any cyclic dependencies in the Vertical Constraint Graph.
	 * @param vcgRoot pointer to root of VCG.
	 * @param channel pointer to particular channel.
	 */
	private void vcgCreateDependents(RouteVCG vcgRoot, RouteChannel channel)
	{
		boolean check = true;
		while (check)
		{
			check = false;
			vcgSetDependents(vcgRoot);
			GenMath.MutableInteger found = new GenMath.MutableInteger(0);
			GenMath.MutableDouble diff = new GenMath.MutableDouble(0);
			Place.NBPlace place = vcgCyclicCheck(vcgRoot, diff, found);
			if (found.intValue() != 0)
			{
				check = true;

				// move place and update row
				for (Place.NBPlace place2 = place; place2 != null; place2 = place2.next)
					place2.xPos += diff.doubleValue();

				// update channel port positions
				for (RouteChNode chNode = channel.nodes; chNode != null; chNode = chNode.next)
				{
					// calculate actual port position
					for (RouteChPort chPort = chNode.firstPort; chPort != null; chPort = chPort.next)
						chPort.xPos = portPosition(chPort.port);

					// reorder port positions from left to right
					for (RouteChPort chPort = chNode.firstPort; chPort != null; chPort = chPort.next)
					{
						for (RouteChPort port2 = chPort.last; port2 != null; port2 = chPort.last)
						{
							if (port2.xPos <= chPort.xPos) break;

							// move chPort left
							chPort.last = port2.last;
							port2.last = chPort;
							if (chPort.last != null)
								chPort.last.next = chPort;
							port2.next = chPort.next;
							chPort.next = port2;
							if (port2.next != null)
								port2.next.last = port2;
							if (port2 == chNode.firstPort)
								chNode.firstPort = chPort;
							if (chPort == chNode.lastPort)
								chNode.lastPort = port2;
						}
					}
				}
			}
		}
	}

	/**
	 * Method to create a directed edge if one channel node must be routed before another.
	 * @param vcgRoot root of Vertical Constraint Graph.
	 */
	private void vcgSetDependents(RouteVCG vcgRoot)
	{
		// clear all dependencies
		for (RouteVCGEdge edge1 = vcgRoot.edges; edge1 != null; edge1 = edge1.next)
			edge1.node.edges = null;

		// set all dependencies
		for (RouteVCGEdge edge1 = vcgRoot.edges; edge1 != null; edge1 = edge1.next)
		{
			for (RouteVCGEdge edge2 = edge1.next; edge2 != null; edge2 = edge2.next)
			{
				// Given two channel nodes, create a directed edge if
				// one must be routed before the other
				boolean depend1 = false, depend2 = false;
				for (RouteChPort port1 = edge1.node.chNode.firstPort; port1 != null; port1 = port1.next)
				{
					for (RouteChPort port2 = edge2.node.chNode.firstPort; port2 != null; port2 = port2.next)
					{
						if (Math.abs(port1.xPos - port2.xPos) < SilComp.getMinPortDistance())
						{
							// determine which one goes first
							if (port1.port.node.row.number > port2.port.node.row.number)
							{
								depend1 = true;
							} else
							{
								depend2 = true;
							}
						}
					}
				}
				if (depend1)
				{
					RouteVCGEdge vcgEdge = new RouteVCGEdge();
					vcgEdge.node = edge2.node;
					vcgEdge.next = edge1.node.edges;
					edge1.node.edges = vcgEdge;
				}
				if (depend2)
				{
					RouteVCGEdge vcgEdge = new RouteVCGEdge();
					vcgEdge.node = edge1.node;
					vcgEdge.next = edge2.node.edges;
					edge2.node.edges = vcgEdge;
				}
			}
		}
	}

	/**
	 * Method to return TRUE if cyclic dependency is found in Vertical Constraint Graph.
	 * Also set place and offset needed to resolve this conflict.
	 * Note that only the top row may be moved around as the bottom row
	 * may have already been used by another channel.
	 * @param vcgRoot root of Vertical Constraint Graph.
	 * @param diff offset required is stored here.
	 * @return pointer to place.
	 */
	private Place.NBPlace vcgCyclicCheck(RouteVCG vcgRoot, GenMath.MutableDouble diff, GenMath.MutableInteger found)
	{
		// check each VCG node
		Place.NBPlace place = null;
		for (RouteVCGEdge edge = vcgRoot.edges; edge != null; edge = edge.next)
		{
			// clear all flags
			for (RouteVCGEdge edge3 = vcgRoot.edges; edge3 != null; edge3 = edge3.next)
			{
				edge3.node.flags &= ~(ROUTESEEN | ROUTETEMPNUSE);
			}

			// mark this node
			edge.node.flags |= ROUTESEEN;

			// check single cycle
			for (RouteVCGEdge edge2 = edge.node.edges; edge2 != null; edge2 = edge2.next)
			{
				RouteVCG lastNode = edge.node;
				GenMath.MutableInteger subFound = new GenMath.MutableInteger(0);
				lastNode = vcgSingleCycle(edge2.node, lastNode, subFound);
				if (subFound.intValue() != 0)
				{
					// find place of conflict
					for (RouteChPort port1 = edge.node.chNode.firstPort; port1 != null; port1 = port1.next)
					{
						for (RouteChPort port2 = lastNode.chNode.firstPort; port2 != null; port2 = port2.next)
						{
							if (Math.abs(port1.xPos - port2.xPos) < SilComp.getMinPortDistance())
							{
								// determine which one goes first
								if (port1.port.node.row.number > port2.port.node.row.number)
								{
									place = port1.port.place;
									if (port1.xPos < port2.xPos)
									{
										diff.setValue((port2.xPos - port1.xPos) + SilComp.getMinPortDistance());
									} else
									{
										diff.setValue(SilComp.getMinPortDistance() - (port1.xPos - port2.xPos));
									}
								} else if (port2.port.node.row.number > port1.port.node.row.number)
								{
									place = port2.port.place;
									if (port2.xPos < port1.xPos)
									{
										diff.setValue((port1.xPos - port2.xPos) + SilComp.getMinPortDistance());
									} else
									{
										diff.setValue(SilComp.getMinPortDistance() - (port2.xPos - port1.xPos));
									}
								} else
								{
									System.out.println("SEVERE ERROR - Cyclic conflict to same row, check leaf cells.");
									System.out.println("At " + port1.port.place.cell.name + " " + ((PortProto)port1.port.port.port).getName() +
										" to " + port2.port.place.cell.name + " " + ((PortProto)port2.port.port.port).getName());
									return null;
								}
								found.setValue(1);
								return place;
							}
						}
					}
					System.out.println("SEVERE WARNING - Cyclic conflict discovered but cannot find place to resolve.");
				}
			}
		}
		found.setValue(0);
		return place;
	}

	/**
	 * Method to decide whether Breadth First Search encounters the marked node.
	 * @param node node to start search.
	 * @param lastNode last node searched.
	 * @param found MutableInteger to hold result: nonzero if marked node found.
	 * @return the last node searched.
	 */
	private RouteVCG vcgSingleCycle(RouteVCG node, RouteVCG lastNode, GenMath.MutableInteger found)
	{
		if (node == null)
		{
			found.setValue(0);
			return lastNode;
		}
		if ((node.flags & ROUTESEEN) != 0)
		{
			// marked node found
			found.setValue(1);
			return lastNode;
		}
		if ((node.flags & ROUTETEMPNUSE) != 0)
		{
			// been here before
			found.setValue(0);
			return lastNode;
		}

		// check others
		node.flags |= ROUTETEMPNUSE;
		RouteVCG saveNode = lastNode;
		for (RouteVCGEdge edge = node.edges; edge != null; edge = edge.next)
		{
			lastNode = node;
			lastNode = vcgSingleCycle(edge.node, lastNode, found);
			if (found.intValue() != 0) return lastNode;
		}
		lastNode = saveNode;
		found.setValue(0);
		return lastNode;
	}

	/**
	 * Method to create the Zone Representation Graph (ZRG) for the indicated channel.
	 * @param channel pointer to channel.