route.java

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

/* -*- tab-width: 4 -*-
 *
 * Electric(tm) VLSI Design System
 *
 * File: Route.java
 * Silicon compiler tool (QUISC): routing
 * Written by Andrew R. Kostiuk, Queen's University.
 * Translated to Java by Steven M. Rubin, Sun Microsystems.
 *
 * Copyright (c) 2005 Sun Microsystems and Static Free Software
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
package com.sun.electric.tool.sc;

import com.sun.electric.database.geometry.GenMath;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.prototype.PortProto;

import java.util.Iterator;
import java.util.List;

/**
 * The routing part of the Silicon Compiler tool.
 */
public class Route
{
	/** not verbose default */			private static final boolean DEBUG = false;

	/** seen in processing */			private static final int ROUTESEEN		= 0x00000001;
	/** unusable in current track */	private static final int ROUTEUNUSABLE	= 0x00000002;
	/** temporary not use */			private static final int ROUTETEMPNUSE	= 0x00000004;

	/** fuzzy window for pass th. */	private static final double DEFAULT_FUZZY_WINDOW_LIMIT	= 6400;

	/** global feed through number */	private int		feedNumber;

	/**
	 * Class for communicating routing information between router and netlist reader.
	 */
	public static class SCRoute
	{
		/** list of channels */				RouteChannel	channels;
		/** exported ports */				RouteExport		exports;
		/** route rows */					RouteRow		rows;
	};

	private static class RouteRow
	{
		/** number, 0 = bottom */			int				number;
		/** list of extracted nodes */		RouteNode		nodes;
		/** reference actual row */			Place.RowList	row;
		/** last in row list */				RouteRow		last;
		/** next in row list */				RouteRow		next;
	};

	private static class RouteNode
	{
		/** extracted node */				GetNetlist.ExtNode extNode;
		/** reference row */				RouteRow		row;
		/** first port in row */			RoutePort		firstPort;
		/** last port in row */				RoutePort		lastPort;
		/** same nodes in above rows */		RouteNode		sameNext;
		/** same nodes in below rows */		RouteNode		sameLast;
		/** nodes in same row */			RouteNode		next;
	};

	/**
	 * Class for communicating routing information between router and maker.
	 */
	public static class RoutePort
	{
		/** reference place */				Place.NBPlace	place;
		/** particular port */				GetNetlist.SCNiPort port;
		/** reference node */				RouteNode		node;
		/** flags for processing */			int				flags;
		/** previous port in list */		RoutePort		last;
		/** next port in list */			RoutePort		next;
	};

	/**
	 * Class for communicating channel information between router and maker.
	 */
	public static class RouteChannel
	{
		/** number, 0 is bottom */			int				number;
		/** list of nodes */				RouteChNode		nodes;
		/** list of tracks */				RouteTrack		tracks;
		/** last in channel list */			RouteChannel	last;
		/** next in channel list */			RouteChannel	next;
	};

	/**
	 * Class for communicating routing information between router and maker.
	 */
	public static class RouteChNode
	{
		/** extracted node */				GetNetlist.ExtNode extNode;
		/** optional net number */			int				number;
		/** first port in row */			RouteChPort		firstPort;
		/** last port in row */				RouteChPort		lastPort;
		/** reference channel */			RouteChannel	channel;
		/** flags for processing */			int				flags;
		/** same nodes in above rows */		RouteChNode		sameNext;
		/** same nodes in below rows */		RouteChNode		sameLast;
		/** nodes in same row */			RouteChNode		next;
	};

	/**
	 * Class for communicating routing information between router and maker.
	 */
	public static class RouteChPort
	{
		/** reference port */				RoutePort		port;
		/** reference channel node */		RouteChNode		node;
		/** x position */					double			xPos;
		/** flags for processing */			int				flags;
		/** previous port in list */		RouteChPort		last;
		/** next port in list */			RouteChPort		next;
	};

	private static class RouteVCG
	{
		/** channel node */					RouteChNode		chNode;
		/** flags for processing */			int				flags;
		/** edges of graph */				RouteVCGEdge	edges;
	};

	private static class RouteVCGEdge
	{
		/** to which node */				RouteVCG		node;
		/** next in list */					RouteVCGEdge	next;
	};

	private static class RouteZRG
	{
		/** number of zone */				int				number;
		/** list of channel nodes */		RouteZRGMem		chNodes;
		/** last zone */					RouteZRG		last;
		/** next zone */					RouteZRG		next;
	};

	private static class RouteZRGMem
	{
		/** channel node */					RouteChNode		chNode;
		/** next in zone */					RouteZRGMem		next;
	};

	/**
	 * Class for communicating routing information between router and maker.
	 */
	public static class RouteTrack
	{
		/** number of track, 0 = top */		int				number;
		/** track member */					RouteTrackMem	nodes;
		/** last track in list */			RouteTrack		last;
		/** next track in list */			RouteTrack		next;
	};

	/**
	 * Class for communicating routing information between router and maker.
	 */
	public static class RouteTrackMem
	{
		/** channel node */					RouteChNode		node;
		/** next in same track */			RouteTrackMem	next;
	};

	/**
	 * Class for communicating routing information between router and maker.
	 */
	public static class RouteExport
	{
		/** export port */					GetNetlist.SCPort	xPort;
		/** channel port */					RouteChPort		chPort;
		/** next export port */				RouteExport		next;
	};

	/**
	 * Method to do routing.  Here is the description:
	 *
	 * Preliminary Channel Assignment:
	 *    o  Squeeze cells together
	 *    o  Below unless required above
	 *    o  Includes stitches and lateral feeds
	 * Feed Through Decision:
	 *    o  Preferred window for path
	 *    o  Include Fuzzy Window
	 * Make Exports:
	 *    o  Path to closest outside edge
	 * Track Routing:
	 *    o  Create Vertical Constraint Graph
	 *    o  Create Zone Representation for channel
	 *    o  Decrease height of VCG and maximize channel use
	 */
	public String routeCells(GetNetlist gnl)
	{
		// check if working in a cell
		if (gnl.curSCCell == null) return "No cell selected";

		// check if placement structure exists
		if (gnl.curSCCell.placement == null)
			return "No PLACEMENT structure for cell '" + gnl.curSCCell.name + "'";

		// create route structure
		SCRoute route = new SCRoute();
		gnl.curSCCell.route = route;
		route.channels = null;
		route.exports = null;
		route.rows = null;

		// first squeeze cell together
		squeezeCells(gnl.curSCCell.placement.theRows);

		// create list of rows and their usage of extracted nodes
		RouteRow rowList = createRowList(gnl.curSCCell.placement.theRows, gnl.curSCCell);
		route.rows = rowList;

		// create Route Channel List
		RouteChannel channelList = createChannelList(gnl.curSCCell.placement.numRows + 1);
		route.channels = channelList;

		// Do primary channel assignment
		channelAssign(rowList, channelList, gnl.curSCCell);

		// decide upon any pass through cells required
		createPassThroughs(channelList, gnl.curSCCell.placement.theRows);

		// decide upon export positions
		route.exports = decideExports(gnl.curSCCell);

		// route tracks in each channel
		tracksInChannels(channelList, gnl.curSCCell);

		return null;
	}

	/**
	 * Method to try to squeeze adjacent cells in a row as close together.
	 * Checks where their active areas start and uses the minimum active distance.
	 * @param rows pointer to start of row list.
	 */
	private void squeezeCells(List<Place.RowList> theRows)
	{
		for(Place.RowList row : theRows)
		{
			for (Place.NBPlace place = row.start; place != null; place = place.next)
			{
				if (place.next == null) continue;

				// determine allowable overlap
				GetNetlist.SCCellNums cell1Nums = GetNetlist.getLeafCellNums((Cell)place.cell.np);
				GetNetlist.SCCellNums cell2Nums = GetNetlist.getLeafCellNums((Cell)place.next.cell.np);
				double overlap = 0;
				if ((row.rowNum % 2) != 0)
				{
					// odd row, cell are transposed
					overlap = cell2Nums.rightActive + cell1Nums.leftActive
						- SilComp.getMinActiveDistance();
				} else
				{
					// even row
					overlap = cell1Nums.rightActive + cell2Nums.leftActive
						- SilComp.getMinActiveDistance();
				}

				// move rest of row
				for (Place.NBPlace place2 = place.next; place2 != null; place2 = place2.next)
					place2.xPos -= overlap;
			}
		}
	}

	/**
	 * Method to create list of which extracted nodes each member of the rows of
	 * a placement need connection to.
	 * @param rows pointer to start of placement rows.
	 * @param cell pointer to parent cell.
	 * @return created list.
	 */
	private RouteRow createRowList(List<Place.RowList> theRows, GetNetlist.SCCell cell)
	{
		// clear all reference pointers in extracted node list
		for (GetNetlist.ExtNode eNode = cell.exNodes; eNode != null; eNode = eNode.next)
			eNode.ptr = null;

		// create a route row list for each placement row
		RouteRow firstRRow = null, lastRRow = null;
		RouteNode sameNode = null;
		for(Place.RowList row : theRows)
		{
			RouteRow newRRow = new RouteRow();
			newRRow.number = row.rowNum;
			newRRow.nodes = null;
			newRRow.row = row;
			newRRow.last = lastRRow;
			newRRow.next = null;
			if (lastRRow != null)
			{
				lastRRow.next = newRRow;
				lastRRow = newRRow;
			} else
			{
				firstRRow = lastRRow = newRRow;
			}

			// create an entry of every extracted node in each row
			RouteNode lastNode = null;
			for (GetNetlist.ExtNode enode = cell.exNodes; enode != null; enode = enode.next)
			{
				RouteNode newNode = new RouteNode();
				newNode.extNode = enode;
				newNode.row = newRRow;
				newNode.firstPort = null;
				newNode.lastPort = null;
				newNode.sameNext = null;
				newNode.sameLast = sameNode;
				newNode.next = null;
				if (lastNode != null)
				{
					lastNode.next = newNode;
				} else
				{
					newRRow.nodes = newNode;
				}
				lastNode = newNode;
				if (sameNode != null)
				{
					sameNode.sameNext = newNode;
					sameNode = sameNode.next;
				} else
				{
					enode.ptr = newNode;
				}
			}
			sameNode = newRRow.nodes;

			// set reference to all ports on row
			for (Place.NBPlace place = row.start; place != null; place = place.next)
			{
				for (GetNetlist.SCNiPort port = place.cell.ports; port != null; port = port.next)
				{
					RouteNode newNode = (RouteNode)port.extNode.ptr;
					if (newNode != null)
					{
						for (int i = 0; i < row.rowNum; i++)
							newNode = newNode.sameNext;
						RoutePort newPort = new RoutePort();
						newPort.place = place;
						newPort.port = port;
						newPort.node = newNode;
						newPort.next = null;
						newPort.last = newNode.lastPort;
						if (newNode.lastPort != null)
						{
							newNode.lastPort.next = newPort;
						} else
						{
							newNode.firstPort = newPort;
						}
						newNode.lastPort = newPort;
					}
				}
			}
		}

		return firstRRow;
	}

	/**
	 * Method to create the basic channel list.
	 * The number of channels is one more than the number of rows.
	 * @param number number of channels to create.
	 * @return result list.
	 */
	private RouteChannel createChannelList(int number)
	{
		// create channel list
		RouteChannel firstChan = null, lastChan = null;
		for (int i = 0; i < number; i++)
		{
			RouteChannel newChan = new RouteChannel();
			newChan.number = i;
			newChan.nodes = null;
			newChan.tracks = null;
			newChan.next = null;
			newChan.last = lastChan;
			if (lastChan != null)
			{
				lastChan.next = newChan;
			} else
			{
				firstChan = newChan;
			}
			lastChan = newChan;
		}

		return firstChan;
	}

	/**
	 * Method to do primary channel assignment for all ports.
	 * The basis algorithm is:
	 *
	 *		if no ports higher
	 *			use below channel
	 *		else
	 *			if ports lower
	 *				use channel with closest to other ports
	 *			else
	 *				use above channel
	 * @param rows list of rows of ports.
	 * @param channels list of channels.
	 * @param cell pointer to parent cell.
	 */
	private void channelAssign(RouteRow rows, RouteChannel channels, GetNetlist.SCCell cell)
	{
		// clear flags
		for (RouteRow row = rows; row != null; row = row.next)
		{
			for (RouteNode node = row.nodes; node != null; node = node.next)
			{
				for (RoutePort port = node.firstPort; port != null; port = port.next)
					port.flags &= ~ROUTESEEN;
			}
		}

		for (RouteRow row = rows; row != null; row = row.next)
		{
			for (RouteNode node = row.nodes; node != null; node = node.next)
			{
				if (node.firstPort == null)
					continue;

				// check for ports above
				boolean portsAbove = false;
				for (RouteNode node2 = node.sameNext; node2 != null; node2 = node2.sameNext)
				{
					if (node2.firstPort != null)
					{
						portsAbove = true;
						break;
					}
				}

				// if none found above, any ports in this list only going up
				if (!portsAbove && node.firstPort != node.lastPort)
				{
					for (RoutePort port = node.firstPort; port != null; port = port.next)
					{
						int direct = GetNetlist.getLeafPortDirection((PortProto)port.port.port);
						if ((direct & GetNetlist.PORTDIRUP) != 0 && (direct & GetNetlist.PORTDIRDOWN) == 0)
						{
							portsAbove = true;
							break;
						}
					}
				}

				// check for ports below
				boolean portsBelow = false;