seaofgatesengine.java

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

			System.out.println("NOTE: " + numFailedRoutes + " nets were not routed");
	}

	/**
	 * Method to do the routing in a single thread.
	 * @param allRoutes the routes that need to be done.
	 * @param routeBatches the routing batches (by network)
	 * @param job the job that invoked this routing.
	 */
	private void doRouting(List<NeededRoute> allRoutes, RouteBatches [] routeBatches, Job job)
	{
		int totalRoutes = allRoutes.size();
		for(int r=0; r<totalRoutes; r++)
		{
			if (job != null && job.checkAbort())
			{
				System.out.println("Sea-of-gates routing aborted");
				break;
			}
	
			// get information on the segment to be routed
			NeededRoute nr = allRoutes.get(r);
			Job.getUserInterface().setProgressValue(r*100/totalRoutes);
			String routeName = nr.routeName;
			if (routeBatches[nr.batchNumber].segsInBatch > 1)
				routeName += " (" + nr.routeInBatch + " of " + routeBatches[nr.batchNumber].segsInBatch + ")";
			Job.getUserInterface().setProgressNote("Network " + routeName);
			System.out.println("Routing network " + routeName + "...");
	
			// route the segment
			findPath(nr);
	
			// if the routing was good, place the results
			if (nr.winningWF != null && nr.winningWF.vertices != null)
				createRoute(nr);
		}
	}

	private void doRoutingParallel(int numberOfThreads, List<NeededRoute> allRoutes, RouteBatches [] routeBatches)
	{
		// create threads and other threading data structures
		RouteInThread[] threads = new RouteInThread[numberOfThreads];
		for(int i=0; i<numberOfThreads; i++) threads[i] = new RouteInThread("Route #" + (i+1));
		NeededRoute [] routesToDo = new NeededRoute[numberOfThreads];
		int [] routeIndices = new int[numberOfThreads];
		Semaphore outSem = new Semaphore(0);

		// create list of routes and blocked areas
		List<NeededRoute> myList = new ArrayList<NeededRoute>();
		for(NeededRoute nr : allRoutes) myList.add(nr);
		List<Rectangle2D> blocked = new ArrayList<Rectangle2D>();

		// now run the threads
		int totalRoutes = allRoutes.size();
		int routesDone = 0;
		while (myList.size() > 0)
		{
			int threadAssign = 0;
			blocked.clear();
			for(int i=0; i<myList.size(); i++)
			{
				NeededRoute nr = myList.get(i);
				boolean isBlocked = false;
				for(Rectangle2D block : blocked)
				{
					if (block.intersects(nr.routeBounds)) { isBlocked = true;   break; }
				}
				if (isBlocked) continue;

				// this route can be done: start it
				blocked.add(nr.routeBounds);
				routesToDo[threadAssign] = nr;
				routeIndices[threadAssign] = i;
				threads[threadAssign].startRoute(nr, outSem);
				threadAssign++;
				if (threadAssign >= numberOfThreads) break;
			}

			String routes = "";
			for(int i=0; i<threadAssign; i++)
			{
				String routeName = routesToDo[i].routeName;
				if (routeBatches[routesToDo[i].batchNumber].segsInBatch > 1)
					routeName += "(" + routesToDo[i].routeInBatch + "/" + routeBatches[routesToDo[i].batchNumber].segsInBatch + ")";
				if (routes.length() > 0) routes += ", ";
				routes += routeName;
			}
			System.out.println("Parallel routing " + routes + "...");
			Job.getUserInterface().setProgressNote(routes);

			// now wait for routing threads to finish
			outSem.acquireUninterruptibly(threadAssign);

			// all done, now handle the results
			for(int i=0; i<threadAssign; i++)
			{
				if (routesToDo[i].winningWF != null && routesToDo[i].winningWF.vertices != null)
					createRoute(routesToDo[i]);
			}
			for(int i=threadAssign-1; i>=0; i--)
				myList.remove(routeIndices[i]);
			routesDone += threadAssign;
			Job.getUserInterface().setProgressValue(routesDone*100/totalRoutes);
		}

		// terminate the threads
		for(int i=0; i<numberOfThreads; i++) threads[i].startRoute(null, null);
	}

	private class RouteInThread extends Thread
	{
		private Semaphore inSem = new Semaphore(0);
		private NeededRoute nr;
		private Semaphore whenDone;

		public RouteInThread(String name)
		{
			super(name);
			start();
		}

		public void startRoute(NeededRoute nr, Semaphore whenDone)
		{
			this.nr = nr;
			this.whenDone = whenDone;
			inSem.release();
		}

		public void run()
		{
			for (;;)
			{
				inSem.acquireUninterruptibly();
				if (nr == null) return;
				findPath(nr);
				whenDone.release();
			}
		}
	}

	/**
	 * Method to initialize technology information, including design rules.
	 * @return true on error.
	 */
	private boolean initializeDesignRules(Cell c)
	{
		// find the metal layers, arcs, and contacts
		cell = c;
		tech = cell.getTechnology();
		numMetalLayers = tech.getNumMetals();
		metalLayers = new Layer[numMetalLayers];
		metalArcs = new ArcProto[numMetalLayers];
		favorArcs = new boolean[numMetalLayers];
		preventArcs = new boolean[numMetalLayers];
		viaLayers = new Layer[numMetalLayers-1];
		metalVias = new MetalVias[numMetalLayers-1];
		for(int i=0; i<numMetalLayers-1; i++) metalVias[i] = new MetalVias();
		for(Iterator<Layer> it = tech.getLayers(); it.hasNext(); )
		{
			Layer lay = it.next();
			if (!lay.getFunction().isMetal()) continue;
			if (lay.isPseudoLayer()) continue;
			int layerIndex = lay.getFunction().getLevel()-1;
			if (layerIndex < numMetalLayers) metalLayers[layerIndex] = lay;
		}
		boolean hasFavorites = false;
		for(Iterator<ArcProto> it = tech.getArcs(); it.hasNext(); )
		{
			ArcProto ap = it.next();
			for(int i=0; i<numMetalLayers; i++)
			{
				if (ap.getLayer(0) == metalLayers[i])
				{
					metalArcs[i] = ap;
					favorArcs[i] = Routing.isSeaOfGatesFavor(ap);
					if (favorArcs[i]) hasFavorites = true;
					preventArcs[i] = Routing.isSeaOfGatesPrevent(ap);
					break;
				}
			}
		}
		if (!hasFavorites)
			for(int i=0; i<numMetalLayers; i++) favorArcs[i] = true;
		for(Iterator<PrimitiveNode> it = tech.getNodes(); it.hasNext(); )
		{
			PrimitiveNode np = it.next();
			if (np.isNotUsed()) continue;
			if (np.getFunction() != PrimitiveNode.Function.CONTACT) continue;
			ArcProto [] conns = np.getPort(0).getConnections();
			for(int i=0; i<numMetalLayers-1; i++)
			{
				if ((conns[0] == metalArcs[i] && conns[1] == metalArcs[i+1]) ||
					(conns[1] == metalArcs[i] && conns[0] == metalArcs[i+1]))
				{
					metalVias[i].addVia(np, 0);

					// see if the node is asymmetric and should exist in rotated states
					boolean square = true, offCenter = false;
					NodeInst dummyNi = NodeInst.makeDummyInstance(np);
					Poly [] conPolys = tech.getShapeOfNode(dummyNi);
					for(int p=0; p<conPolys.length; p++)
					{
						Poly conPoly = conPolys[p];
						Layer conLayer = conPoly.getLayer();
						Layer.Function lFun = conLayer.getFunction();
						if (lFun.isMetal())
						{
							Rectangle2D conRect = conPoly.getBounds2D();
							if (conRect.getWidth() != conRect.getHeight()) square = false;
							if (conRect.getCenterX() != 0 || conRect.getCenterY() != 0) offCenter = true;
						} else if (lFun.isContact())
						{
							viaLayers[i] = conLayer;
						}
					}
					if (offCenter)
					{
						// off center: test in all 4 rotations
						metalVias[i].addVia(np, 90);
						metalVias[i].addVia(np, 180);
						metalVias[i].addVia(np, 270);
					} else if (!square)
					{
						// centered but not square: test in 90-degree rotation
						metalVias[i].addVia(np, 90);
					}
					break;
				}
			}
		}
		for(int i=0; i<numMetalLayers; i++)
		{
			if (metalLayers[i] == null)
			{
				System.out.println("ERROR: Cannot find layer for Metal " + (i+1));
				return true;
			}
			if (metalArcs[i] == null)
			{
				System.out.println("ERROR: Cannot find arc for Metal " + (i+1));
				return true;
			}
			if (i < numMetalLayers-1)
			{
				if (metalVias[i].getVias().size() == 0)
				{
					System.out.println("ERROR: Cannot find contact node between Metal " + (i+1) + " and Metal " + (i+2));
					return true;
				}
				if (viaLayers[i] == null)
				{
					System.out.println("ERROR: Cannot find contact layer between Metal " + (i+1) + " and Metal " + (i+2));
					return true;
				}
			}
		}

		// compute design rule spacings
		worstMetalSurround = new double[numMetalLayers];
		for(int i=0; i<numMetalLayers; i++)
			worstMetalSurround[i] = DRC.getMaxSurround(metalLayers[i], Double.MAX_VALUE);
		viaSurround = new double[numMetalLayers-1];
		for(int i=0; i<numMetalLayers-1; i++)
		{
			Layer lay = viaLayers[i];

			double spacing = 2;
			double arcWidth = metalArcs[i].getDefaultLambdaBaseWidth();
			DRCTemplate ruleSpacing = DRC.getSpacingRule(lay, null, lay, null, false, -1, arcWidth, 50);
			if (ruleSpacing != null) spacing = ruleSpacing.getValue(0);

			// determine cut size
			double width = 0;
			DRCTemplate ruleWidth = DRC.getMinValue(lay, DRCTemplate.DRCRuleType.NODSIZ);
			if (ruleWidth != null) width = ruleWidth.getValue(0);

			// extend to the size of the largest cut
			List<MetalVia> nps = metalVias[i].getVias();
			for(MetalVia mv : nps)
			{
				NodeInst dummyNi = NodeInst.makeDummyInstance(mv.via);
				Poly [] conPolys = tech.getShapeOfNode(dummyNi);
				for(int p=0; p<conPolys.length; p++)
				{
					Poly conPoly = conPolys[p];
					if (conPoly.getLayer().getFunction().isContact())
					{
						Rectangle2D bounds = conPoly.getBounds2D();
						width = Math.max(width, bounds.getWidth());
						width = Math.max(width, bounds.getHeight());
					}
				}
			}

			viaSurround[i] = spacing + width;
		}
		return false;
	}

	private double getMinWidth(List<PortInst> orderedPorts)
	{
		double minWidth = 0;
		for(PortInst pi : orderedPorts)
		{
			double widestAtPort = getWidestMetalArcOnPort(pi);
			if (widestAtPort > minWidth) minWidth = widestAtPort;
		}
		if (minWidth > Routing.getSeaOfGatesMaxWidth()) minWidth = Routing.getSeaOfGatesMaxWidth();
		return minWidth;
	}

	/**
	 * Get the widest metal arc already connected to a given PortInst.
	 * Looks recursively down the hierarchy.
	 * @param pi the PortInst to connect.
	 * @return the widest metal arc connect to that port (zero if none)
	 */
	private double getWidestMetalArcOnPort(PortInst pi)
	{
		// first check the top level
		double width = 0;
		for (Iterator<Connection> it = pi.getConnections(); it.hasNext(); )
		{
			Connection c = it.next();
			ArcInst ai = c.getArc();
			if (!ai.getProto().getFunction().isMetal()) continue;
			double newWidth = ai.getLambdaBaseWidth();
			if (newWidth > width) width = newWidth;
		}

		// now recurse down the hierarchy
		NodeInst ni = pi.getNodeInst();
		if (ni.isCellInstance())
		{
			Export export = (Export)pi.getPortProto();
			PortInst exportedInst = export.getOriginalPort();
			double width2 = getWidestMetalArcOnPort(exportedInst);
			if (width2 > width) width = width2;
		}
		return width;
	}

	private boolean inValidPort(PortInst pi)
	{
		ArcProto [] conns = pi.getPortProto().getBasePort().getConnections();
		boolean valid = false;
		for(int j=0; j<conns.length; j++)
		{
			ArcProto ap = conns[j];
			if (ap.getTechnology() != tech) continue;
			if (!ap.getFunction().isMetal()) continue;
			if (preventArcs[conns[j].getFunction().getLevel()-1]) continue;
			valid = true;
			break;
		}
		if (!valid)
		{
			System.out.println("Cannot connect to port " + pi.getPortProto().getName() +
				" on node " + pi.getNodeInst().describe(false) +
				" because all connecting layers have been prevented by Routing Preferences");
			return true;
		}
		return false;
	}