seaofgatesengine.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: SeaOfGatesEngine.java
 * Routing tool: Sea of Gates routing
 * Written by: Steven M. Rubin
 *
 * Copyright (c) 2007 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.routing;

import com.sun.electric.database.geometry.DBMath;
import com.sun.electric.database.geometry.EPoint;
import com.sun.electric.database.geometry.ERectangle;
import com.sun.electric.database.geometry.GenMath;
import com.sun.electric.database.geometry.Orientation;
import com.sun.electric.database.geometry.Poly;
import com.sun.electric.database.geometry.PolyBase;
import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.hierarchy.Export;
import com.sun.electric.database.hierarchy.HierarchyEnumerator;
import com.sun.electric.database.hierarchy.Nodable;
import com.sun.electric.database.network.Netlist;
import com.sun.electric.database.network.Network;
import com.sun.electric.database.prototype.NodeProto;
import com.sun.electric.database.text.TextUtils;
import com.sun.electric.database.topology.ArcInst;
import com.sun.electric.database.topology.Connection;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.database.topology.RTBounds;
import com.sun.electric.database.topology.RTNode;
import com.sun.electric.database.variable.EditWindow_;
import com.sun.electric.database.variable.VarContext;
import com.sun.electric.technology.ArcProto;
import com.sun.electric.technology.DRCTemplate;
import com.sun.electric.technology.Layer;
import com.sun.electric.technology.PrimitiveNode;
import com.sun.electric.technology.SizeOffset;
import com.sun.electric.technology.Technology;
import com.sun.electric.technology.technologies.Generic;
import com.sun.electric.tool.Job;
import com.sun.electric.tool.drc.DRC;
import com.sun.electric.tool.user.ErrorLogger;

import java.awt.geom.AffineTransform;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import java.util.concurrent.Semaphore;

/**
 * Class to do sea-of-gates routing.
 * This router replaces unrouted arcs with real geometry.  It has these features:
 * > The router only works in layout, and only routes metal wires.
 * > The router uses vias to move up and down the metal layers.
 *   > Understands multiple vias and multiple via orientations.
 * > The router is not tracked: it runs on the Electric grid
 *   > Favors wires on full-grid units
 *   > Tries to cover multiple grid units in a single jump
 * > Routes power and ground first, then goes by length (shortest nets first)
 * > Prefers to run odd metal layers on horizontal, even layers on vertical
 * > Routes in both directions (from A to B and from B to A) and chooses the one that completes first
 *   > Serial method alternates advancing each wavefront, stopping when one completes
 *   > Parallel option runs both wavefronts at once and aborts the slower one
 * > Users can request that some layers not be used, can request that some layers be favored
 * > Routes are made as wide as the widest arc already connected to any point
 *   > User preference can limit width
 * > Cost penalty also includes space left in the track on either side of a segment
 *
 * Things to do:
 *     At the end of routing, try again with those that failed
 *     Detect "river routes" and route specially
 *     Ability to route to any previous part of route when daisy-chaining?
 *     Lower cost if running over existing layout (on the same net)
 *     Ability to connect to anything on the destination net
 *     Rip-up
 *     Global routing(?)
 *     Sweeping cost parameters (with parallel processors) to find best, dynamically
 *     Forcing each processor to use a different grid track
 *     Characterizing routing task (which parallelism to use)
 */
public class SeaOfGatesEngine
{
	/** True to display each step in the search. */								private static final boolean DEBUGSTEPS = false;
	/** True to display the first routing failure. */							private static final boolean DEBUGFAILURE = false;
	/** True to debug "infinite" loops. */										private static final boolean DEBUGLOOPS = false;
	/** true to use full, gridless routing */									private static final boolean FULLGRAIN = true;

	/** Percent of min cell size that route must stay inside. */				private static final double PERCENTLIMIT = 7;
	/** Number of steps per unit when searching. */								private static final double GRANULARITY = 1;
	/** Size of steps when searching. */										private static final double GRAINSIZE = (1/GRANULARITY);
	/** Cost of routing in wrong direction (alternating horizontal/vertical) */	private static final int COSTALTERNATINGMETAL = 100;
	/** Cost of changing layers. */												private static final int COSTLAYERCHANGE = 8;
	/** Cost of routing away from the target. */								private static final int COSTWRONGDIRECTION = 15;
	/** Cost of running on non-favored layer. */								private static final int COSTUNFAVORED = 10;
	/** Cost of making a turn. */												private static final int COSTTURNING = 1;
	/** Cost of having coordinates that are off-grid. */						private static final int COSTOFFGRID = 15;

	private SearchVertex svAborted = new SearchVertex(0, 0, 0, 0, null, 0, null);
	private SearchVertex svExhausted = new SearchVertex(0, 0, 0, 0, null, 0, null);
	private SearchVertex svLimited = new SearchVertex(0, 0, 0, 0, null, 0, null);

	/** Cell in which routing occurs. */										private Cell cell;
	/** Cell size. */															private Rectangle2D cellBounds;
	/** Technology to use for routing. */										private Technology tech;
	/** R-Trees for metal blockage in the cell. */								private Map<Layer,RTNode> metalTrees;
	/** R-Trees for via blockage in the cell. */								private Map<Layer,RTNode> viaTrees;
	/** Maps Arcs to network IDs in the R-Tree. */								private Map<ArcInst,Integer> netIDs;
	/** number of metal layers in the technology. */							private int numMetalLayers;
	/** metal layers in the technology. */										private Layer [] metalLayers;
	/** via layers in the technology. */										private Layer [] viaLayers;
	/** arcs to use for each metal layer. */									private ArcProto [] metalArcs;
	/** favoritism for each metal layer. */										private boolean [] favorArcs;
	/** avoidance for each metal layer. */										private boolean [] preventArcs;
	/** vias to use to go up from each metal layer. */							private MetalVias [] metalVias;
	/** worst spacing rule for a given metal layer. */							private double [] worstMetalSurround;
	/** minimum spacing between the centers of two vias. */						private double [] viaSurround;
	/** the total length of wires routed */										private double totalWireLength;
	/** true if this is the first failure of a route (for debugging) */			private boolean firstFailure;
	/** true to run to/from and from/to routing in parallel */					private boolean parallelDij;
	/** for logging errors */													private ErrorLogger errorLogger;

	/**
	 * Class to hold a "batch" of routes, all on the same network.
	 */
	private static class RouteBatches
	{
		Set<ArcInst> unroutedArcs;
		Set<NodeInst> unroutedNodes;
		List<PortInst> orderedPorts;
		int segsInBatch;
		int numRouted, numUnrouted;
	}

	private class Wavefront
	{
		/** The route that this is part of. */								private NeededRoute nr;
		/** Wavefront name (for debugging). */								private String name;
		/** List of active search vertices while running wavefront. */		private TreeSet<SearchVertex> active;
		/** Resulting list of vertices found for this wavefront. */			private List<SearchVertex> vertices;
		/** Set true to abort this wavefront's search. */					private boolean abort;
		/** The starting and ending ports of the wavefront. */				private PortInst from, to;
		/** The starting X/Y coordinates of the wavefront. */				private double fromX, fromY;
		/** The starting metal layer of the wavefront. */					private int fromZ;
		/** The ending X/Y coordinates of the wavefront. */					private double toX, toY;
		/** The ending metal layer of the wavefront. */						private int toZ;
		/** debugging state */												private final boolean debug;
		/** Search vertices found while propagating the wavefront. */		private Map<Integer,Set<Integer>> [] searchVertexPlanes;
		/** Gridless search vertices found while propagating wavefront. */	private Map<Double,Set<Double>> [] searchVertexPlanesDBL;
		/** minimum spacing between this metal and itself. */				private Map<Double,Map<Double,Double>>[] layerSurround;

		Wavefront(NeededRoute nr, PortInst from, double fromX, double fromY, int fromZ,
			PortInst to, double toX, double toY, int toZ, String name, boolean debug)
		{
			this.nr = nr;
			this.from = from;  this.fromX = fromX;  this.fromY = fromY;  this.fromZ = fromZ;
			this.to = to;      this.toX = toX;      this.toY = toY;      this.toZ = toZ;
			this.name = name;
			this.debug = debug;
			active = new TreeSet<SearchVertex>();
			vertices = null;
			abort = false;
			searchVertexPlanes = new Map[numMetalLayers];
			searchVertexPlanesDBL = new Map[numMetalLayers];
			layerSurround = new Map[numMetalLayers];
			for(int i=0; i<numMetalLayers; i++)
				layerSurround[i] = new HashMap<Double,Map<Double,Double>>();

			if (debug) System.out.println("----------- SEARCHING FROM ("+TextUtils.formatDouble(fromX)+","+
				TextUtils.formatDouble(fromY)+",M"+(fromZ+1)+") TO ("+TextUtils.formatDouble(toX)+","+
				TextUtils.formatDouble(toY)+",M"+(toZ+1)+") -----------");

			SearchVertex svStart = new SearchVertex(fromX, fromY, fromZ, 0, null, 0, this);
			svStart.cost = 0;
			setVertex(fromX, fromY, fromZ);
			active.add(svStart);
		}

		/**
		 * Method to get the SearchVertex at a given coordinate.
		 * @param x the X coordinate desired.
		 * @param y the Y coordinate desired.
		 * @param z the Z coordinate (metal layer) desired.
		 * @return the SearchVertex at that point (null if none).
		 */
		public boolean getVertex(double x, double y, int z)
		{
			if (FULLGRAIN)
			{
				Map<Double,Set<Double>> plane = searchVertexPlanesDBL[z];
				if (plane == null) return false;
				Set<Double> row = plane.get(new Double(y));
				if (row == null) return false;
				boolean found = row.contains(new Double(x));
				return found;
			}

			Map<Integer,Set<Integer>> plane = searchVertexPlanes[z];
			if (plane == null) return false;
			Set<Integer> row = plane.get(new Integer((int)(y*GRANULARITY)));
			if (row == null) return false;
			boolean found = row.contains(new Integer((int)(x*GRANULARITY)));
			return found;
		}

		/**
		 * Method to mark a given coordinate.
		 * @param x the X coordinate desired.
		 * @param y the Y coordinate desired.
		 * @param z the Z coordinate (metal layer) desired.
		 */
		public void setVertex(double x, double y, int z)
		{
			if (FULLGRAIN)
			{
				Map<Double,Set<Double>> plane = searchVertexPlanesDBL[z];
				if (plane == null)
				{
					plane = new HashMap<Double,Set<Double>>();
					searchVertexPlanesDBL[z] = plane;
				}
				Double iY = new Double(y);
				Set<Double> row = plane.get(iY);
				if (row == null)
				{
					row = new HashSet<Double>();
					plane.put(iY, row);
				}
				row.add(new Double(x));
				return;
			}

			Map<Integer,Set<Integer>> plane = searchVertexPlanes[z];
			if (plane == null)
			{
				plane = new HashMap<Integer,Set<Integer>>();
				searchVertexPlanes[z] = plane;
			}
			Integer iY = new Integer((int)(y*GRANULARITY));
			Set<Integer> row = plane.get(iY);
			if (row == null)
			{
				row = new HashSet<Integer>();
				plane.put(iY, row);
			}
			row.add(new Integer((int)(x*GRANULARITY)));
		}

		/**
		 * Method to determine the design rule spacing between two pieces of a given layer.
		 * @param layer the layer index.
		 * @param width the width of one of the pieces (-1 to use default).
		 * @param length the length of one of the pieces (-1 to use default).
		 * @return the design rule spacing (0 if none).
		 */
		public double getSpacingRule(int layer, double width, double length)
		{
			// use default width if none specified
			if (width < 0) width = metalArcs[layer].getDefaultLambdaBaseWidth();
			if (length < 0) length = 50;

			// convert these to the next largest integers
			Double wid = new Double(upToGrain(width));
			Double len = new Double(upToGrain(length));

			// see if the rule is cached6
			Map<Double,Double> widMap = layerSurround[layer].get(wid);
			if (widMap == null)
			{
				widMap = new HashMap<Double,Double>();
				layerSurround[layer].put(wid, widMap);
			}
			Double value = widMap.get(len);
			if (value == null)
			{
				// rule not cached: compute it
				Layer lay = metalLayers[layer];
				DRCTemplate rule = DRC.getSpacingRule(lay, null, lay, null, false, -1, width, length);
				double v = 0;
				if (rule != null) v = rule.getValue(0);
				value = new Double(v);
				widMap.put(len, value);
			}
			return value.doubleValue();
		}
	}

	/**
	 * Class to hold a route that must be run.
	 */
	private class NeededRoute
	{
		String routeName;
		int netID;
		double minWidth;
		int batchNumber;
		int routeInBatch;
		Rectangle2D routeBounds;
		double minimumSearchBoundX;
		double maximumSearchBoundX;
		double minimumSearchBoundY;
		double maximumSearchBoundY;
		Rectangle2D jumpBound;
		Wavefront dir1, dir2;
		Wavefront winningWF;

		NeededRoute(String routeName, PortInst from, double fromX, double fromY, int fromZ,
			PortInst to, double toX, double toY, int toZ,
			int netID, double minWidth, int batchNumber, int routeInBatch)
		{
			this.routeName = routeName;
			this.netID = netID;
			this.minWidth = minWidth;
			this.batchNumber = batchNumber;
			this.routeInBatch = routeInBatch;

			cellBounds = cell.getBounds();
			minimumSearchBoundX = downToGrain(cellBounds.getMinX());
			maximumSearchBoundX = upToGrain(cellBounds.getMaxX());
			minimumSearchBoundY = downToGrain(cellBounds.getMinY());
			maximumSearchBoundY = upToGrain(cellBounds.getMaxY());
			if (PERCENTLIMIT > 0)
			{
				double maxStrayFromRouteBounds = Math.min(cellBounds.getWidth(), cellBounds.getHeight()) * PERCENTLIMIT / 100;
				routeBounds = new Rectangle2D.Double(
					Math.min(fromX, toX)-maxStrayFromRouteBounds, Math.min(fromY, toY)-maxStrayFromRouteBounds,
					Math.abs(fromX-toX)+maxStrayFromRouteBounds*2, Math.abs(fromY-toY)+maxStrayFromRouteBounds*2);
				minimumSearchBoundX = routeBounds.getMinX();
				maximumSearchBoundX = routeBounds.getMaxX();
				minimumSearchBoundY = routeBounds.getMinY();
				maximumSearchBoundY = routeBounds.getMaxY();
			}
			jumpBound = new Rectangle2D.Double(Math.min(fromX, toX), Math.min(fromY, toY),
				Math.abs(fromX-toX), Math.abs(fromY-toY));

			// make two wavefronts going in both directions
			dir1 = new Wavefront(this, from, fromX, fromY, fromZ, to, toX, toY, toZ, "a->b", DEBUGSTEPS);
			dir2 = new Wavefront(this, to, toX, toY, toZ, from, fromX, fromY, fromZ, "b->a", false);