seaofgatesengine.java

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

	 * @param to the tail PortInst of the new ArcInst.
	 * @param netID the network ID of geometry in this ArcInst.
	 * @return the ArcInst that was created (null on error).
	 */
	private ArcInst makeArcInst(ArcProto type, double wid, PortInst from, PortInst to, int netID)
	{
		ArcInst ai = ArcInst.makeInstanceBase(type, wid, from, to);
		if (ai != null)
		{
			PolyBase [] polys = tech.getShapeOfArc(ai);
			for(int i=0; i<polys.length; i++)
				addLayer(polys[i], GenMath.MATID, netID, false);

			// accumulate the total length of wires placed
			PolyBase fromPoly = from.getPoly();
			PolyBase toPoly = to.getPoly();
			double length = fromPoly.getCenter().distance(toPoly.getCenter());
			totalWireLength += length;
		}
		return ai;
	}

	/**
	 * Method to find a path between two ports.
	 * @param nr the NeededRoute object with all necessary information.
	 * If successful, the NeededRoute's "vertices" field is filled with the route data.
	 */
	private void findPath(NeededRoute nr)
	{
		// special case when route is null length
		Wavefront d1 = nr.dir1;
		if (DBMath.areEquals(d1.toX, d1.fromX) && DBMath.areEquals(d1.toY, d1.fromY) && d1.toZ == d1.fromZ)
		{
			nr.winningWF = d1;
			nr.winningWF.vertices = new ArrayList<SearchVertex>();
			SearchVertex sv = new SearchVertex(d1.toX, d1.toY, d1.toZ, 0, null, 0, nr.winningWF);
			nr.winningWF.vertices.add(sv);
			nr.cleanSearchMemory();
			return;
		}

		if (parallelDij)
		{
			// create threads and start them running
			Semaphore outSem = new Semaphore(0);
			new DijkstraInThread("Route a->b", nr.dir1, nr.dir2, outSem);
			new DijkstraInThread("Route b->a", nr.dir2, nr.dir1, outSem);

			// wait for threads to complete and get results
			outSem.acquireUninterruptibly(2);
		} else
		{
			// run both wavefronts in parallel (interleaving steps)
			doTwoWayDijkstra(nr);
		}

		// analyze the winning wavefront
		Wavefront wf = nr.winningWF;
		double verLength = Double.MAX_VALUE;
		if (wf != null) verLength = getVertexLength(wf.vertices);
		if (verLength == Double.MAX_VALUE)
		{
			// failed to route
			String errorMsg;
			if (wf == null) wf = nr.dir1;
			if (wf.vertices == null)
			{
				errorMsg = "Search too complex (exceeds complexity limit of " +
					Routing.getSeaOfGatesComplexityLimit() + " steps)";
			} else
			{
				errorMsg = "Failed to route from port " + wf.from.getPortProto().getName() +
					" of node " + wf.from.getNodeInst().describe(false) + " to port " + wf.to.getPortProto().getName() +
					" of node " + wf.to.getNodeInst().describe(false);
			}
			System.out.println("ERROR: " + errorMsg);
			List<EPoint> lineList = new ArrayList<EPoint>();
			lineList.add(new EPoint(wf.toX, wf.toY));
			lineList.add(new EPoint(wf.fromX, wf.fromY));
			errorLogger.logError(errorMsg, null, null, lineList, null, null, cell, 0);

			if (DEBUGFAILURE && firstFailure)
			{
				firstFailure = false;
				EditWindow_ wnd = Job.getUserInterface().getCurrentEditWindow_();
				wnd.clearHighlighting();
				showSearchVertices(nr.dir1.searchVertexPlanes, false);
				wnd.finishedHighlighting();
			}
		}
		nr.cleanSearchMemory();
	}

	private void doTwoWayDijkstra(NeededRoute nr)
	{
		SearchVertex result = null;
		int numSearchVertices = 0;
		while (result == null)
		{
			// stop if the search is too complex
			numSearchVertices++;
			if (numSearchVertices > Routing.getSeaOfGatesComplexityLimit()) return;

			SearchVertex resultA = advanceWavefront(nr.dir1);
			SearchVertex resultB = advanceWavefront(nr.dir2);
			if (resultA != null || resultB != null)
			{
				result = resultA;
				nr.winningWF = nr.dir1;
				if (result == null || result == svExhausted)
				{
					result = resultB;
					nr.winningWF = nr.dir2;
				}
			}
		}
		if (result == svAborted || result == svExhausted)
		{
			nr.winningWF = null;
			return;
		}

//		dumpPlane(0);
//		dumpPlane(1);
//		dumpPlane(2);
		List<SearchVertex> realVertices = getOptimizedList(result);
		nr.winningWF.vertices = realVertices;
	}

	private class DijkstraInThread extends Thread
	{
		private Wavefront wf;
		private Wavefront otherWf;
		private Semaphore whenDone;

		public DijkstraInThread(String name, Wavefront wf, Wavefront otherWf, Semaphore whenDone)
		{
			super(name);
			this.wf = wf;
			this.otherWf = otherWf;
			this.whenDone = whenDone;
			start();
		}

		public void run()
		{
			SearchVertex result = null;
			int numSearchVertices = 0;
			while (result == null)
			{					
				// stop if the search is too complex
				numSearchVertices++;
				if (numSearchVertices > Routing.getSeaOfGatesComplexityLimit())
				{
					result = svLimited;
				} else
				{
					if (wf.abort) result = svAborted; else
					{
						result = advanceWavefront(wf);
					}
				}
			}
			if (result != svAborted && result != svExhausted && result != svLimited)
			{
				if (DEBUGLOOPS)
					System.out.println("    Wavefront " + wf.name + " first completion");
				wf.vertices = getOptimizedList(result);
				wf.nr.winningWF = wf;
				otherWf.abort = true;
			} else
			{
				if (DEBUGLOOPS)
				{
	                String status = "completed";
	                if (result == svAborted) status = "aborted"; else
	                	if (result == svExhausted) status = "exhausted"; else
	                		if (result == svLimited) status = "limited";
					System.out.println("    Wavefront " + wf.name + " " + status);
				}
			}
			whenDone.release();
		}
	}

	private SearchVertex advanceWavefront(Wavefront wf)
	{
		// get the lowest cost point
		if (wf.active.size() == 0) return svExhausted;
		SearchVertex svCurrent = wf.active.first();
		wf.active.remove(svCurrent);
		double curX = svCurrent.getX();
		double curY = svCurrent.getY();
		int curZ = svCurrent.getZ();

		if (wf.debug) System.out.print("AT ("+TextUtils.formatDouble(curX)+","+TextUtils.formatDouble(curY)+",M"
			+(curZ+1)+")C="+svCurrent.cost+" WENT");

		// look at all directions from this point
		for(int i=0; i<6; i++)
		{
			// compute a neighboring point
			double dx = 0, dy = 0;
			int dz = 0;
			switch (i)
			{
				case 0:
					dx = -GRAINSIZE;
					if (FULLGRAIN)
					{
						double intermediate = upToGrainAlways(curX+dx);
						if (intermediate != curX+dx) dx = intermediate - curX;
					}
					break;
				case 1:
					dx =  GRAINSIZE;
					if (FULLGRAIN)
					{
						double intermediate = downToGrainAlways(curX+dx);
						if (intermediate != curX+dx) dx = intermediate - curX;
					}
					break;
				case 2:
					dy = -GRAINSIZE;
					if (FULLGRAIN)
					{
						double intermediate = upToGrainAlways(curY+dy);
						if (intermediate != curY+dy) dy = intermediate - curY;
					}
					break;
				case 3:
					dy =  GRAINSIZE;
					if (FULLGRAIN)
					{
						double intermediate = downToGrainAlways(curY+dy);
						if (intermediate != curY+dy) dy = intermediate - curY;
					}
					break;
				case 4: dz = -1;   break;
				case 5: dz =  1;   break;
			}

			// extend the distance if heading toward the goal
			boolean stuck = false;
			if (dz == 0)
			{
				boolean goFarther = false;
				if (dx != 0)
				{
					if ((wf.toX-curX) * dx > 0) goFarther = true;
				} else
				{
					if ((wf.toY-curY) * dy > 0) goFarther = true;
				}
				if (goFarther)
				{
					double jumpSize = getJumpSize(curX, curY, curZ, dx, dy, wf);
					if (dx > 0)
					{
						if (jumpSize <= 0) stuck = true;
						dx = jumpSize;
					}
					if (dx < 0)
					{
						if (jumpSize >= 0) stuck = true;
						dx = jumpSize;
					}
					if (dy > 0)
					{
						if (jumpSize <= 0) stuck = true;
						dy = jumpSize;
					}
					if (dy < 0)
					{
						if (jumpSize >= 0) stuck = true;
						dy = jumpSize;
					}
				}
			}
			double nX = curX + dx;
			double nY = curY + dy;
			int nZ = curZ + dz;

			if (wf.debug)
			{
				switch (i)
				{
					case 0: System.out.print("  X-"+TextUtils.formatDouble(Math.abs(dx)));   break;
					case 1: System.out.print("  X+"+TextUtils.formatDouble(dx));   break;
					case 2: System.out.print("  Y-"+TextUtils.formatDouble(Math.abs(dy)));   break;
					case 3: System.out.print("  Y+"+TextUtils.formatDouble(dy));   break;
					case 4: System.out.print("  -Z");   break;
					case 5: System.out.print("  +Z");   break;
				}
			}
			if (stuck)
			{
				if (wf.debug) System.out.print(":CannotMove");
				continue;
			}

			if (nX < wf.nr.minimumSearchBoundX)
			{
				nX = wf.nr.minimumSearchBoundX;
				dx = nX - curX;
				if (dx == 0) { if (wf.debug) System.out.print(":OutOfBounds");   continue; }
			}
			if (nX > wf.nr.maximumSearchBoundX)
			{
				nX = wf.nr.maximumSearchBoundX;
				dx = nX - curX;
				if (dx == 0) { if (wf.debug) System.out.print(":OutOfBounds");   continue; }
			}
			if (nY < wf.nr.minimumSearchBoundY)
			{
				nY = wf.nr.minimumSearchBoundY;
				dy = nY - curY;
				if (dy == 0) { if (wf.debug) System.out.print(":OutOfBounds");   continue; }
			}
			if (nY > wf.nr.maximumSearchBoundY)
			{
				nY = wf.nr.maximumSearchBoundY;
				dy = nY - curY;
				if (dy == 0) { if (wf.debug) System.out.print(":OutOfBounds");   continue; }
			}
			if (nZ < 0 || nZ >= numMetalLayers) { if (wf.debug) System.out.print(":OutOfBounds");   continue; }
			if (preventArcs[nZ])  { if (wf.debug) System.out.print(":IllegalArc");   continue; }

			// see if the adjacent point has already been visited
			if (wf.getVertex(nX, nY, nZ)) { if (wf.debug) System.out.print(":AlreadyVisited");   continue; }
			// see if the space is available
			int whichContact = 0;
			Point2D [] cuts = null;
			if (dz == 0)
			{
				// running on one layer: check surround
				double width = Math.max(metalArcs[nZ].getDefaultLambdaBaseWidth(), wf.nr.minWidth);
				double metalSpacing = width / 2;
				boolean allClear = false;
				for(;;)
				{
					SearchVertex prevPath = svCurrent;
					double checkX = (curX+nX)/2, checkY = (curY+nY)/2;
					double halfWid = metalSpacing + Math.abs(dx)/2;
					double halfHei = metalSpacing + Math.abs(dy)/2;
					while (prevPath != null && prevPath.last != null)
					{
						if (prevPath.zv != nZ || prevPath.last.zv != nZ) break;
						if (prevPath.xv == prevPath.last.xv && dx == 0)
						{
							checkY = (prevPath.last.yv + nY) / 2;
							halfHei = metalSpacing + Math.abs(prevPath.last.yv - nY)/2;
							prevPath = prevPath.last;
						} else if (prevPath.yv == prevPath.last.yv && dy == 0)
						{
							checkX = (prevPath.last.xv + nX) / 2;
							halfWid = metalSpacing + Math.abs(prevPath.last.xv - nX)/2;
							prevPath = prevPath.last;
						} else break;
					}
					SOGBound sb = getMetalBlockageAndNotch(