route.java

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

				}
				addPortToChannel(port, port.node.extNode, channels, port.node.row.number + offset);
			} else
			{
				// add to channel above
				addPortToChannel(port, port.node.extNode, channels, port.node.row.number + 1);
			}
		}
	}

	/**
	 * Method to create pass throughs required to join electrically equivalent nodes
	 * in different channels.
	 * @param channels pointer to current channels.
	 * @param rows pointer to placed rows.
	 */
	private void createPassThroughs(RouteChannel channels, List<Place.RowList> theRows)
	{
		feedNumber = 0;

		// clear the flag on all channel nodes
		for (RouteChannel chan = channels; chan != null; chan = chan.next)
		{
			for (RouteChNode chNode = chan.nodes; chNode != null; chNode = chNode.next)
				chNode.flags &= ~ROUTESEEN;
		}

		// find all nodes which exist in more than one channel
		for (RouteChannel chan = channels; chan != null; chan = chan.next)
		{
			for (RouteChNode chNode = chan.nodes; chNode != null; chNode = chNode.next)
			{
				if ((chNode.flags & ROUTESEEN) != 0) continue;
				chNode.flags |= ROUTESEEN;
				RouteChNode oldChNode = chNode;
				for (RouteChNode chNode2 = chNode.sameNext; chNode2 != null; chNode2 = chNode2.sameNext)
				{
					chNode2.flags |= ROUTESEEN;
					betweenChNodes(oldChNode, chNode2, channels, theRows);
					oldChNode = chNode2;
				}
			}
		}
	}

	/**
	 * Method to route between two channel nodes.
	 * Consider both the use of pass throughs and the use of nodes of the same extracted node in a row.
	 * Note that there may be more than one row between the two channels.
	 * @param node1 first node (below).
	 * @param node2 second node (above).
	 * @param channels list of channels.
	 * @param rows list of placed rows.
	 */
	private void betweenChNodes(RouteChNode node1, RouteChNode node2, RouteChannel channels, List<Place.RowList> theRows)
	{
		GetNetlist.ExtNode extNode = node1.extNode;

		// determine limits of second channel
		double minX2 = minPortPos(node2);
		double maxX2 = maxPortPos(node2);

		// do for all intervening channels
		for (RouteChannel chan = node1.channel; chan != node2.channel; chan = chan.next,
			node1 = node1.sameNext)
		{
			// determine limits of first channel node
			double minX1 = minPortPos(node1);
			double maxX1 = maxPortPos(node1);

			// determine preferred region of pass through
			double pMinX, pMaxX;
			if (maxX1 <= minX2)
			{
				// no overlap with first node to left
				pMinX = maxX1;
				pMaxX = minX2;
			} else if (maxX2 <= minX1)
			{
				// no overlap with first node to right
				pMinX = maxX2;
				pMaxX = minX1;
			} else
			{
				// have some overlap
				pMinX = Math.max(minX1, minX2);
				pMaxX = Math.min(minX1, minX2);
			}

			// set window fuzzy limits
			pMinX -= DEFAULT_FUZZY_WINDOW_LIMIT;
			pMaxX += DEFAULT_FUZZY_WINDOW_LIMIT;

			// determine which row we are in
			Place.RowList row = null;
			for(Place.RowList r : theRows)
			{
				row = r;
				if (row.rowNum == chan.number) break;
			}

			// check for any possible ports which can be used
			RouteNode rNode;
			for (rNode = (RouteNode)extNode.ptr; rNode != null; rNode = rNode.sameNext)
			{
				if (rNode.row.number == row.rowNum) break;
			}
			if (rNode != null)
			{
				// port of correct type exists somewhere in this row
				RoutePort rPort;
				for (rPort = rNode.firstPort; rPort != null; rPort = rPort.next)
				{
					double pos = portPosition(rPort);
					int direct = GetNetlist.getLeafPortDirection((PortProto)rPort.port.port);
					if ((direct & GetNetlist.PORTDIRUP) == 0 && (direct & GetNetlist.PORTDIRDOWN) != 0) continue;
					if (pos >= pMinX && pos <= pMaxX) break;
				}
				if (rPort != null)
				{
					// found suitable port, ensure it exists in both channels
					RouteChPort chPort = null;
					for (RouteChNode node = chan.nodes; node != null; node = node.next)
					{
						if (node.extNode == node1.extNode)
						{
							for (chPort = node.firstPort; chPort != null; chPort = chPort.next)
							{
								if (chPort.port == rPort) break;
							}
						}
					}
					if (chPort == null)
					{
						// add port to this channel
						addPortToChannel(rPort, extNode, channels, chan.number);
					}
					chPort = null;
					for (RouteChNode node = chan.next.nodes; node != null; node = node.next)
					{
						if (node.extNode == node1.extNode)
						{
							for (chPort = node.firstPort; chPort != null; chPort = chPort.next)
							{
								if (chPort.port == rPort) break;
							}
						}
					}
					if (chPort == null)
					{
						// add port to next channel
						addPortToChannel(rPort, extNode, channels, chan.next.number);
					}
					continue;
				}
			}

			// if no port found, find best position for feed through
			double bestPos = Double.MAX_VALUE;
			Place.NBPlace bestPlace = null;
			for (Place.NBPlace place = row.start; place != null; place = place.next)
			{
				// not allowed to feed at stitch
				if (place.cell.type == GetNetlist.STITCH ||
					(place.last != null && place.last.cell.type == GetNetlist.STITCH))
						continue;

				// not allowed to feed at lateral feed
				if (place.cell.type == GetNetlist.LATERALFEED ||
					(place.last != null && place.last.cell.type == GetNetlist.LATERALFEED))
						continue;
				if (place.xPos >= pMinX && place.xPos <= pMaxX)
				{
					bestPlace = place;
					break;
				}
				double pos;
				if (place.xPos < pMinX)
				{
					pos = Math.abs(pMinX - place.xPos);
				} else
				{
					pos = Math.abs(pMaxX - place.xPos);
				}
				if (pos < bestPos)
				{
					bestPos = pos;
					bestPlace = place;
				}
			}

			// insert feed through at the indicated place
			insertFeedThrough(bestPlace, row, channels, chan.number, node1);
		}
	}

	/**
	 * Method to return the position of the port which is farthest left (minimum).
	 * @param node pointer to channel node.
	 * @return leftmost port position.
	 */
	private double minPortPos(RouteChNode node)
	{
		double minX = Double.MAX_VALUE;
		for (RouteChPort chPort = node.firstPort; chPort != null; chPort = chPort.next)
		{
			// determine position
			double pos = portPosition(chPort.port);

			// check versus minimum
			if (pos < minX) minX = pos;
		}

		return minX;
	}

	/**
	 * Method to return the position of the port which is farthest right (maximum).
	 * @param node pointer to channel node.
	 * @return rightmost port position.
	 */
	private double maxPortPos(RouteChNode node)
	{
		double maxX = Double.MIN_VALUE;
		for (RouteChPort chPort = node.firstPort; chPort != null; chPort = chPort.next)
		{
			// determine position
			double pos = portPosition(chPort.port);

			// check versus maximum
			if (pos > maxX) maxX = pos;
		}

		return maxX;
	}

	/**
	 * Method to return the x position of the indicated port.
	 * @param port pointer to port in question.
	 * @return x position.
	 */
	private double portPosition(RoutePort port)
	{
		double pos = port.place.xPos;
		if ((port.node.row.number % 2) != 0)
		{
			pos += port.place.cell.size - port.port.xPos;
		} else
		{
			pos += port.port.xPos;
		}

		return pos;
	}

	/**
	 * Method to insert a feed through in front of the indicated place.
	 * @param place place where to insert in front of.
	 * @param row row of place.
	 * @param channels channel list.
	 * @param chanNum number of particular channel below.
	 * @param node channel node within the channel.
	 */
	private void insertFeedThrough(Place.NBPlace place, Place.RowList row,
		RouteChannel channels, int chanNum, RouteChNode node)
	{
		// create a special instance
		GetNetlist.SCNiTree inst = new GetNetlist.SCNiTree("Feed_Through", GetNetlist.FEEDCELL);
		inst.size = SilComp.getFeedThruSize();

		// create instance port
		GetNetlist.SCNiPort port = new GetNetlist.SCNiPort();
		port.port = new Integer(feedNumber++);
		port.extNode = node.extNode;
		port.bits = 0;
		port.xPos = SilComp.getFeedThruSize() / 2;
		port.next = null;
		inst.ports = port;

		// create the appropriate place
		Place.NBPlace nPlace = new Place.NBPlace();
		nPlace.cell = inst;
		nPlace.last = place.last;
		nPlace.next = place;
		if (nPlace.last != null)
			nPlace.last.next = nPlace;
		place.last = nPlace;
		if (place == row.start)
			row.start = nPlace;

		resolveNewXPos(nPlace, row);

		// create a route port entry for this new port
		RouteNode rNode;
		for (rNode = (RouteNode)node.extNode.ptr; rNode != null; rNode = rNode.sameNext)
		{
			if (rNode.row.number == row.rowNum) break;
		}
		RoutePort rPort = new RoutePort();
		rPort.place = nPlace;
		rPort.port = port;
		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 channels
		addPortToChannel(rPort, node.extNode, channels, chanNum);
		addPortToChannel(rPort, node.extNode, channels, chanNum + 1);
	}

	/**
	 * Method to resolve the position of the new place and update the row.
	 * @param place new place.
	 * @param row pointer to existing row.
	 */
	private void resolveNewXPos(Place.NBPlace place, Place.RowList row)
	{
		double xPos;
		if (place.last != null)
		{
			if (place.last.cell.type == GetNetlist.LEAFCELL)
			{
				GetNetlist.SCCellNums cnums = GetNetlist.getLeafCellNums((Cell)place.last.cell.np);
				xPos = place.last.xPos + place.last.cell.size;
				double overlap = 0;
				if ((row.rowNum % 2) != 0)
				{
					// odd row, cells are transposed
					overlap = cnums.leftActive - SilComp.getMinActiveDistance();
				} else
				{
					// even row
					overlap = cnums.rightActive - SilComp.getMinActiveDistance();
				}
				if (overlap < 0 && place.cell.type != GetNetlist.LATERALFEED)
					overlap = 0;
				xPos -= overlap;
				place.xPos = xPos;
				xPos += place.cell.size;
			} else
			{
				xPos = place.last.xPos + place.last.cell.size;
				place.xPos = xPos;
				xPos += place.cell.size;
			}
		} else
		{
			place.xPos = 0;
			xPos = place.cell.size;
		}

		if (place.next != null)
		{
			double oldXPos = place.next.xPos;
			double nXPos = 0;
			if (place.next.cell.type == GetNetlist.LEAFCELL)
			{
				GetNetlist.SCCellNums cnums = GetNetlist.getLeafCellNums((Cell)place.next.cell.np);
				double overlap = 0;
				if ((row.rowNum % 2) != 0)
				{
					// odd row, cells are transposed
					overlap = cnums.rightActive - SilComp.getMinActiveDistance();
				} else
				{
					// even row
					overlap = cnums.leftActive - SilComp.getMinActiveDistance();
				}
				if (overlap < 0 && place.cell.type != GetNetlist.LATERALFEED)
					overlap = 0;
				nXPos = xPos - overlap;
			} else
			{
				nXPos = xPos;
			}

			// update rest of the row
			for (place = place.next; place != null; place = place.next)
				place.xPos += nXPos - oldXPos;
			row.rowSize += nXPos - oldXPos;
		}
	}

	/**
	 * Method to decide upon the exports positions.
	 * If port is available on either the top or bottom channel, no action is required.
	 * If however the port is not available, add special place to the beginning or
	 * end of a row to allow routing to left or right edge of cell (whichever is shorter).
	 * @param cell pointer to cell.
	 * @return created data.
	 */
	private RouteExport decideExports(GetNetlist.SCCell cell)
	{
		RouteExport lExport = null;

		// check all exports
		for (GetNetlist.SCPort port = cell.ports; port != null; port = port.next)
		{
			// get extracted node
			GetNetlist.ExtNode eNode = port.node.ports.extNode;

			RouteChNode chNode = null;
			for (RouteChannel chan = cell.route.channels; chan != null; chan = chan.next)
			{
				for (chNode = chan.nodes; chNode != null; chNode = chNode.next)
				{
					if (chNode.extNode == eNode) break;
				}
				if (chNode != null) break;
			}

			// find limits of channel node
			boolean bottom = false, top = false, left = false, right = false;
			double bestDist = Double.MAX_VALUE;
			RouteChPort bestChPort = null;
			for (RouteChNode chNode2 = chNode; chNode2 != null; chNode2 = chNode2.sameNext)
			{
				RouteChPort chPort;
				for (chPort = chNode2.firstPort; chPort != null; chPort = chPort.next)
				{
					// check for bottom channel
					if (chPort.node.channel.number == 0)
					{
						bottom = true;
						bestChPort = chPort;
						break;
					}

					// check for top channel
					if (chPort.node.channel.number == cell.placement.numRows)
					{
						top = true;
						bestChPort = chPort;
						break;
					}

					// check distance to left boundary
					double dist = portPosition(chPort.port);
					if (dist < bestDist)
					{
						bestDist = dist;
						left = true;
						right = false;
						bestChPort = chPort;
					}

					// check distance to right boundary
					double maxX = chPort.port.node.row.row.end.xPos +
					chPort.port.node.row.row.end.cell.size;
					dist = maxX - portPosition(chPort.port);
					if (dist < bestDist)
					{
						bestDist = dist;
						right = true;
						left = false;
						bestChPort = chPort;
					}
				}
				if (chPort != null) break;
			}
			if (top)
			{
				// EMPTY
			} else if (bottom)
			{