seaofgatesengine.java

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

		}

		public void cleanSearchMemory()
		{
			dir1.searchVertexPlanes = null;
			dir1.searchVertexPlanesDBL = null;
			dir1.active = null;
			if (dir1.vertices != null)
			{
				for(SearchVertex sv : dir1.vertices)
					sv.clearCuts();
			}

			dir2.searchVertexPlanes = null;
			dir2.searchVertexPlanesDBL = null;
			dir2.active = null;
			if (dir2.vertices != null)
			{
				for(SearchVertex sv : dir2.vertices)
					sv.clearCuts();
			}
		}
	}

	/************************************** ROUTING **************************************/

	/**
	 * This is the public interface for Sea-of-Gates Routing when done in batch mode.
	 * @param cell the cell to be Sea-of-Gates-routed.
	 * @param arcsToRoute a List of ArcInsts on networks to be routed.
	 */
	public void routeIt(Job job, Cell cell, List<ArcInst> arcsToRoute)
	{
		// initialize information about the technology
		if (initializeDesignRules(cell)) return;

		// user-interface initialization
		long startTime = System.currentTimeMillis();
		Job.getUserInterface().startProgressDialog("Routing " + arcsToRoute.size() + " nets", null);
		Job.getUserInterface().setProgressNote("Building blockage information...");

		// create an error logger
		errorLogger = ErrorLogger.newInstance("Routing (Sea of gates)");

		// get all blockage information into R-Trees
		metalTrees = new HashMap<Layer, RTNode>();
		viaTrees = new HashMap<Layer, RTNode>();
		netIDs = new HashMap<ArcInst,Integer>();
		BlockageVisitor visitor = new BlockageVisitor(arcsToRoute);
		HierarchyEnumerator.enumerateCell(cell, VarContext.globalContext, visitor);
		addBlockagesAtPorts(arcsToRoute);
//for(Iterator<Layer> it = metalTrees.keySet().iterator(); it.hasNext(); )
//{
//	Layer layer = it.next();
//	RTNode root = metalTrees.get(layer);
//	System.out.println("RTree for "+layer.getName()+":");
//	root.printRTree(2);
//}

		// make a list of all routes that are needed
		List<NeededRoute> allRoutes = new ArrayList<NeededRoute>();
		int numBatches = arcsToRoute.size();
		RouteBatches [] routeBatches = new RouteBatches[numBatches];
		for(int b=0; b<numBatches; b++)
		{
			// get list of PortInsts that comprise this net
			ArcInst ai = arcsToRoute.get(b);
			Netlist netList = cell.getUserNetlist();
//			Netlist netList = cell.acquireUserNetlist();
//			if (netList == null)
//			{
//				System.out.println("Sorry, a deadlock aborted routing (network information unavailable).  Please try again");
//				break;
//			}
			Network net = netList.getNetwork(ai, 0);
			if (net == null)
			{
				System.out.println("Arc " + ai.describe(false) + " has no network!");
				continue;
			}
			Set<ArcInst> arcsToDelete = new HashSet<ArcInst>();
			Set<NodeInst> nodesToDelete = new HashSet<NodeInst>();
			List<Connection> netEnds = Routing.findNetEnds(net, arcsToDelete, nodesToDelete, netList, true);
			List<PortInst> orderedPorts = makeOrderedPorts(net, netEnds);
			if (orderedPorts == null)
			{
				System.out.println("No valid connection points found on the network.");
				continue;
			}
			routeBatches[b] = new RouteBatches();
			routeBatches[b].unroutedArcs = arcsToDelete;
			routeBatches[b].unroutedNodes = nodesToDelete;
			routeBatches[b].orderedPorts = orderedPorts;
			routeBatches[b].segsInBatch = 0;

			// determine the minimum width of arcs on this net
			double minWidth = getMinWidth(orderedPorts);
			int netID = -1;
			Integer netIDI = netIDs.get(ai);
			if (netIDI != null) netID = netIDI.intValue() - 1;

			// find a path between the ends of the network
			int batchNumber = 1;
			for(int i=0; i<orderedPorts.size()-1; i++)
			{
				PortInst fromPi = orderedPorts.get(i);
				PortInst toPi = orderedPorts.get(i+1);
				if (inValidPort(fromPi) || inValidPort(toPi)) continue;

				// get information about one end of the path
				ArcProto fromArc = null;
				ArcProto[] fromArcs = fromPi.getPortProto().getBasePort().getConnections();
				for(int j=0; j<fromArcs.length; j++)
					if (fromArcs[j].getFunction().isMetal()) { fromArc = fromArcs[j];   break; }
				if (fromArc == null)
				{
					String errorMsg = "Cannot connect port " + fromPi.getPortProto().getName() +
						" of node " + fromPi.getNodeInst().describe(false) + " because it has no metal connection";
					System.out.println("ERROR: " + errorMsg);
					List<PolyBase> polyList = new ArrayList<PolyBase>();
					polyList.add(fromPi.getPoly());
					errorLogger.logError(errorMsg, null, null, null, null, polyList, cell, 0);
					continue;
				}

				// get information about the other end of the path
				ArcProto toArc = null;
				ArcProto[] toArcs = toPi.getPortProto().getBasePort().getConnections();
				for(int j=0; j<toArcs.length; j++)
					if (toArcs[j].getFunction().isMetal()) { toArc = toArcs[j];   break; }
				if (toArc == null)
				{
					String errorMsg = "Cannot connect port " + toPi.getPortProto().getName() +
						" of node " + toPi.getNodeInst().describe(false) + " because it has no metal connection";
					System.out.println("ERROR: " + errorMsg);
					List<PolyBase> polyList = new ArrayList<PolyBase>();
					polyList.add(toPi.getPoly());
					errorLogger.logError(errorMsg, null, null, null, null, polyList, cell, 0);
					continue;
				}

				if (fromArc.getTechnology() != tech || toArc.getTechnology() != tech)
				{
					String errorMsg = "Route from port " + fromPi.getPortProto().getName() + " of node " + fromPi.getNodeInst().describe(false) +
						" on arc " + fromArc.describe() + " cannot connect to port " + toPi.getPortProto().getName() + " of node " +
						toPi.getNodeInst().describe(false) + " on arc " + toArc.describe() + " because they have different technologies";
					System.out.println("ERROR: " + errorMsg);
					List<PolyBase> polyList = new ArrayList<PolyBase>();
					PolyBase fromPoly = fromPi.getPoly();
					PolyBase toPoly = toPi.getPoly();
					polyList.add(fromPoly);
					polyList.add(toPoly);
					List<EPoint> lineList = new ArrayList<EPoint>();
					lineList.add(new EPoint(toPoly.getCenterX(), toPoly.getCenterY()));
					lineList.add(new EPoint(fromPoly.getCenterX(), fromPoly.getCenterY()));
					errorLogger.logError(errorMsg, null, null, lineList, null, polyList, cell, 0);
					continue;
				}

				// determine the coordinates of the route
				EPoint fromLoc = fromPi.getPoly().getCenter();
				EPoint toLoc = toPi.getPoly().getCenter();
				double fromX = fromLoc.getX(), fromY = fromLoc.getY();
				double toX = toLoc.getX(), toY = toLoc.getY();
				if (toLoc.getX() < fromLoc.getX())
				{
					toX = upToGrain(toLoc.getX());
					fromX = downToGrain(fromLoc.getX());
				} else if (toLoc.getX() > fromLoc.getX())
				{
					toX = downToGrain(toLoc.getX());
					fromX = upToGrain(fromLoc.getX());
				} else
				{
					toX = fromX = upToGrain(fromLoc.getX());
				}
				if (toLoc.getY() < fromLoc.getY())
				{
					toY = upToGrain(toLoc.getY());
					fromY = downToGrain(fromLoc.getY());
				} else if (toLoc.getY() > fromLoc.getY())
				{
					toY = downToGrain(toLoc.getY());
					fromY = upToGrain(fromLoc.getY());
				} else
				{
					toY = fromY = upToGrain(fromLoc.getY());
				}
				int fromZ = fromArc.getFunction().getLevel()-1;
				int toZ = toArc.getFunction().getLevel()-1;

				// see if access is blocked
				double metalSpacing = Math.max(metalArcs[fromZ].getDefaultLambdaBaseWidth(), minWidth) / 2;

				// determine "from" surround
				Layer lay = metalLayers[fromZ];
				DRCTemplate rule = DRC.getSpacingRule(lay, null, lay, null, false, -1, metalArcs[fromZ].getDefaultLambdaBaseWidth(), -1);
				double surround = 0;
				if (rule != null) surround = rule.getValue(0);
				SOGBound block = getMetalBlockage(netID, fromZ, metalSpacing, metalSpacing, surround, fromX, fromY);
				if (block != null)
				{
					// see if gridding caused the blockage
					fromX = fromLoc.getX();
					fromY = fromLoc.getY();
					block = getMetalBlockage(netID, fromZ, metalSpacing, metalSpacing, surround, fromX, fromY);
					if (block != null)
					{
						String errorMsg = "Cannot Route to port " + fromPi.getPortProto().getName() +
							" of node " + fromPi.getNodeInst().describe(false) + " at (" + TextUtils.formatDouble(fromX) + "," +
							TextUtils.formatDouble(fromY) + ") because it is blocked on layer " + metalLayers[fromZ].getName() +
							" [needs " + TextUtils.formatDouble(metalSpacing+surround) + " all around, blockage is " +
							TextUtils.formatDouble(block.bound.getMinX()) + "<=X<=" + TextUtils.formatDouble(block.bound.getMaxX()) + " and " +
							TextUtils.formatDouble(block.bound.getMinY()) + "<=Y<=" + TextUtils.formatDouble(block.bound.getMaxY()) + "]";
						System.out.println(errorMsg);
						List<PolyBase> polyList = new ArrayList<PolyBase>();
						polyList.add(new PolyBase(fromX, fromY, (metalSpacing+surround)*2, (metalSpacing+surround)*2));
						polyList.add(new PolyBase(block.bound));
						List<EPoint> lineList = new ArrayList<EPoint>();
						lineList.add(new EPoint(block.bound.getMinX(), block.bound.getMinY()));
						lineList.add(new EPoint(block.bound.getMaxX(), block.bound.getMaxY()));
						lineList.add(new EPoint(block.bound.getMinX(), block.bound.getMaxY()));
						lineList.add(new EPoint(block.bound.getMaxX(), block.bound.getMinY()));
						errorLogger.logError(errorMsg, null, null, lineList, null, polyList, cell, 0);
						continue;
					}
				}
				metalSpacing = Math.max(metalArcs[toZ].getDefaultLambdaBaseWidth(), minWidth) / 2;

				// determine "to" surround
				lay = metalLayers[toZ];
				rule = DRC.getSpacingRule(lay, null, lay, null, false, -1, metalArcs[toZ].getDefaultLambdaBaseWidth(), -1);
				surround = 0;
				block = getMetalBlockage(netID, toZ, metalSpacing, metalSpacing, surround, toX, toY);
				if (block != null)
				{
					// see if gridding caused the blockage
					toX = toLoc.getX();
					toY = toLoc.getY();
					block = getMetalBlockage(netID, toZ, metalSpacing, metalSpacing, surround, toX, toY);
					if (block != null)
					{
						String errorMsg = "Cannot route to port " + toPi.getPortProto().getName() +
							" of node " + toPi.getNodeInst().describe(false) + " at (" + TextUtils.formatDouble(toX) + "," +
							TextUtils.formatDouble(toY) + ") because it is blocked on layer " + metalLayers[toZ].getName() +
							" [needs " + TextUtils.formatDouble(metalSpacing+surround) + " all around, blockage is " +
							TextUtils.formatDouble(block.bound.getMinX()) + "<=X<=" + TextUtils.formatDouble(block.bound.getMaxX()) + " and " +
							TextUtils.formatDouble(block.bound.getMinY()) + "<=Y<=" + TextUtils.formatDouble(block.bound.getMaxY()) + "]";
						System.out.println("ERROR: " + errorMsg);
						List<PolyBase> polyList = new ArrayList<PolyBase>();
						polyList.add(new PolyBase(toX, toY, (metalSpacing+surround)*2, (metalSpacing+surround)*2));
						polyList.add(new PolyBase(block.bound));
						List<EPoint> lineList = new ArrayList<EPoint>();
						lineList.add(new EPoint(block.bound.getMinX(), block.bound.getMinY()));
						lineList.add(new EPoint(block.bound.getMaxX(), block.bound.getMaxY()));
						lineList.add(new EPoint(block.bound.getMinX(), block.bound.getMaxY()));
						lineList.add(new EPoint(block.bound.getMaxX(), block.bound.getMinY()));
						errorLogger.logError(errorMsg, null, null, lineList, null, polyList, cell, 0);
						continue;
					}
				}
				NeededRoute nr = new NeededRoute(net.getName(), fromPi, fromX, fromY, fromZ, toPi, toX, toY, toZ,
					netID, minWidth, b, batchNumber++);
				routeBatches[b].segsInBatch++;
				allRoutes.add(nr);
			}
		}

		// now do the actual routing
		boolean parallel = Routing.isSeaOfGatesUseParallelRoutes();
		parallelDij = Routing.isSeaOfGatesUseParallelFromToRoutes();

		firstFailure = true;
		totalWireLength = 0;
		int numberOfProcessors = Runtime.getRuntime().availableProcessors();
		if (numberOfProcessors <= 1) parallelDij = false;
		int numberOfThreads = numberOfProcessors;
		if (parallelDij) numberOfThreads /= 2;
		if (!parallel) numberOfThreads = 1;
		if (numberOfThreads == 1) parallel = false;

		// show what is being done
		System.out.println("Sea-of-gates router finding " + allRoutes.size() + " paths on " + numBatches + " networks");
		if (parallel || parallelDij)
		{
			String message = "NOTE: System has " + numberOfProcessors + " processors so";
			if (parallel) message += " routing " + numberOfThreads + " paths in parallel";
			if (parallelDij)
			{
				if (parallel) message += " and";
				message += " routing both directions of each path in parallel";
			}
			System.out.println(message);
		}
		if (numberOfThreads > 1)
		{
			doRoutingParallel(numberOfThreads, allRoutes, routeBatches);
		} else
		{
			doRouting(allRoutes, routeBatches, job);
		}

		// finally analyze the results and remove unrouted arcs
		int numRoutedSegments = 0;
		int totalRoutes = allRoutes.size();
		for(int a=0; a<totalRoutes; a++)
		{
			NeededRoute nr = allRoutes.get(a);
			if (nr.winningWF != null && nr.winningWF.vertices != null)
			{
				routeBatches[nr.batchNumber].numRouted++;
				numRoutedSegments++;
			} else
				routeBatches[nr.batchNumber].numUnrouted++;
		}
		int numFailedRoutes = 0;
		for(int b=0; b<numBatches; b++)
		{
			if (routeBatches[b] == null) continue;
			if (routeBatches[b].numUnrouted == 0)
			{
				// routed: remove the unrouted arcs
				for(ArcInst aiKill : routeBatches[b].unroutedArcs)
					if (aiKill.isLinked()) aiKill.kill();
				cell.killNodes(routeBatches[b].unroutedNodes);
			} else
			{
				numFailedRoutes++;

				// remove arcs that are routed
				List<PortInst> orderedPorts = routeBatches[b].orderedPorts;
				for(ArcInst aiKill : routeBatches[b].unroutedArcs)
				{
					int headPort = -1, tailPort = -1;
					for(int i=0; i<orderedPorts.size(); i++)
					{
						PortInst pi = orderedPorts.get(i);
						if (aiKill.getHeadPortInst() == pi) headPort = i; else
							if (aiKill.getTailPortInst() == pi) tailPort = i;
					}
					if (headPort >= 0 && tailPort >= 0)
					{
						boolean allRouted = true;
						if (headPort > tailPort) { int swap = headPort;   headPort = tailPort;   tailPort = swap; }
						for(NeededRoute nr : allRoutes)
						{
							if (nr.batchNumber != b) continue;
							if (nr.routeInBatch-1 < headPort || nr.routeInBatch-1 >= tailPort) continue;
							if (nr.winningWF == null || nr.winningWF.vertices == null) allRouted = false;
						}
						if (allRouted && aiKill.isLinked()) aiKill.kill();
					}
				}
			}
		}

		// clean up at end
		errorLogger.termLogging(true);
		long stopTime = System.currentTimeMillis();
		Job.getUserInterface().stopProgressDialog();
		System.out.println("Routed " + numRoutedSegments + " out of " + totalRoutes +
			" segments; total length of routed wires is " + TextUtils.formatDouble(totalWireLength) +
			"; took " + TextUtils.getElapsedTime(stopTime-startTime));
		if (numFailedRoutes > 0)