seaofgatesengine.java

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

	/**
	 * Method to add extra blockage information that corresponds to ends of unrouted arcs.
	 * @param arcsToRoute the list of arcs to route.
	 * @param tech the technology to use.
	 */
	private void addBlockagesAtPorts(List<ArcInst> arcsToRoute)
	{
		Netlist netList = cell.getUserNetlist();
//		Netlist netList = cell.acquireUserNetlist();
//		if (netList == null) return;

		for(ArcInst ai : arcsToRoute)
		{
			int netID = -1;
			Integer netIDI = netIDs.get(ai);
			if (netIDI != null)
			{
				netID = -(netIDI.intValue()-1);
				if (netID > 0) System.out.println("INTERNAL ERROR! net="+netID+" but should be negative");
			}
			Network net = netList.getNetwork(ai, 0);
			HashSet<ArcInst> arcsToDelete = new HashSet<ArcInst>();
			HashSet<NodeInst> nodesToDelete = new HashSet<NodeInst>();
			List<Connection> netEnds = Routing.findNetEnds(net, arcsToDelete, nodesToDelete, netList, true);
			List<PortInst> orderedPorts = makeOrderedPorts(net, netEnds);
			if (orderedPorts == null) continue;

			// determine the minimum width of arcs on this net
			double minWidth = getMinWidth(orderedPorts);

			for(PortInst pi : orderedPorts)
			{
				PolyBase poly = pi.getPoly();
				Rectangle2D polyBounds = poly.getBounds2D();
				ArcProto[] poss = pi.getPortProto().getBasePort().getConnections();
				int lowMetal = -1, highMetal = -1;
				for(int i=0; i<poss.length; i++)
				{
					if (poss[i].getTechnology() != tech) continue;
					if (!poss[i].getFunction().isMetal()) continue;
					int level = poss[i].getFunction().getLevel();
					if (lowMetal < 0) lowMetal = highMetal = level; else
					{
						lowMetal = Math.min(lowMetal, level);
						highMetal = Math.max(highMetal, level);
					}
				}
				if (lowMetal < 0) continue;

				// reserve space on layers above and below
				for(int via = lowMetal-2; via < highMetal; via++)
				{
					if (via < 0 || via >= numMetalLayers-1) continue;
					MetalVia mv = metalVias[via].getVias().get(0);
					PrimitiveNode np = mv.via;
					SizeOffset so = np.getProtoSizeOffset();
					double xOffset = so.getLowXOffset() + so.getHighXOffset();
					double yOffset = so.getLowYOffset() + so.getHighYOffset();
					double wid = Math.max(np.getDefWidth()-xOffset, minWidth) + xOffset;
					double hei = Math.max(np.getDefHeight()-yOffset, minWidth) + yOffset;
					NodeInst dummy = NodeInst.makeDummyInstance(np, EPoint.ORIGIN, wid, hei, Orientation.IDENT);
					PolyBase [] polys = tech.getShapeOfNode(dummy);
					for(int i=0; i<polys.length; i++)
					{
						PolyBase viaPoly = polys[i];
						Layer layer = viaPoly.getLayer();
						if (!layer.getFunction().isMetal()) continue;
						Rectangle2D viaBounds = viaPoly.getBounds2D();
						Rectangle2D bounds = new Rectangle2D.Double(viaBounds.getMinX() + polyBounds.getCenterX(),
							viaBounds.getMinY() + polyBounds.getCenterY(), viaBounds.getWidth(), viaBounds.getHeight());
						addRectangle(bounds, layer, netID);
					}
				}
			}
		}
	}

	/**
	 * Method to order a set of connections for optimal routing.
	 * @param net the Network being ordered.
	 * @param netEnds a list of Connections that must be routed.
	 * @return a list of PortInsts to connect which are ordered such that they
	 * form the proper sequence of routes to make.  Returns null on error.
	 */
	private List<PortInst> makeOrderedPorts(Network net, List<Connection> netEnds)
	{
		List<PortInst> portEndList = new ArrayList<PortInst>();
		for(int i=0; i<netEnds.size(); i++)
		{
			PortInst pi = netEnds.get(i).getPortInst();
			if (!pi.getNodeInst().isCellInstance() &&
				((PrimitiveNode)pi.getNodeInst().getProto()).getTechnology() == Generic.tech())
					continue;
			if (portEndList.contains(pi)) continue;
			portEndList.add(pi);
		}
		int count = portEndList.size();
		if (count == 0) return null;
		if (count == 1)
		{
			System.out.println("Error: Network " + net.describe(false) + " has only one end");
			return null;
		}
		PortInst [] portEnds = new PortInst[count];
		int k=0;
		for(PortInst pi : portEndList) portEnds[k++] = pi;

		// find the closest two points
		int closest1 = 0, closest2 = 0;
		double closestDist = Double.MAX_VALUE;
		for(int i=0; i<count; i++)
		{
			PolyBase poly1 = portEnds[i].getPoly();
			for(int j=i+1; j<count; j++)
			{
				PolyBase poly2 = portEnds[j].getPoly();
				double dist = poly1.getCenter().distance(poly2.getCenter());
				if (dist < closestDist)
				{
					closestDist = dist;
					closest1 = i;
					closest2 = j;
				}
			}
		}
		List<PortInst> orderedPorts = new ArrayList<PortInst>();
		orderedPorts.add(portEnds[closest1]);
		orderedPorts.add(portEnds[closest2]);
		portEnds[closest1] = null;
		portEnds[closest2] = null;
		for(;;)
		{
			// find closest port to ends of current string
			boolean foundsome = false;
			double closestDist1 = Double.MAX_VALUE, closestDist2 = Double.MAX_VALUE;
			for(int i=0; i<count; i++)
			{
				if (portEnds[i] == null) continue;
				PolyBase poly = portEnds[i].getPoly();
				PolyBase poly1 = orderedPorts.get(0).getPoly();
				double dist1 = poly.getCenter().distance(poly1.getCenter());
				if (dist1 < closestDist1)
				{
					closestDist1 = dist1;
					closest1 = i;
					foundsome = true;
				}
				PolyBase poly2 = orderedPorts.get(orderedPorts.size()-1).getPoly();
				double dist2 = poly.getCenter().distance(poly2.getCenter());
				if (dist2 < closestDist2)
				{
					closestDist2 = dist2;
					closest2 = i;
					foundsome = true;
				}
			}
			if (!foundsome) break;
			if (closestDist1 < closestDist2)
			{
				orderedPorts.add(0, portEnds[closest1]);
				portEnds[closest1] = null;
			} else
			{
				orderedPorts.add(portEnds[closest2]);
				portEnds[closest2] = null;
			}
		}
		return orderedPorts;
	}

	/**
	 * Method to create the geometry for a route.
	 * Places nodes and arcs to make the route, and also updates the R-Tree data structure.
	 * @param nr the route information.
	 */
	private void createRoute(NeededRoute nr)
	{
		Wavefront wf = nr.winningWF;
		PortInst lastPort = wf.to;
		PolyBase toPoly = wf.to.getPoly();
		if (toPoly.getCenterX() != wf.toX || toPoly.getCenterY() != wf.toY)
		{
			// end of route is off-grid: adjust it
			if (wf.vertices.size() >= 2)
			{
				SearchVertex v1 = wf.vertices.get(0);
				SearchVertex v2 = wf.vertices.get(1);
				ArcProto type = metalArcs[wf.toZ];
				double width = Math.max(type.getDefaultLambdaBaseWidth(), nr.minWidth);
				PrimitiveNode np = metalArcs[wf.toZ].findPinProto();
				if (v1.getX() == v2.getX())
				{
					// first line is vertical: run a horizontal bit
					NodeInst ni = makeNodeInst(np, new EPoint(v1.getX(), toPoly.getCenterY()),
						np.getDefWidth(), np.getDefHeight(), Orientation.IDENT, cell, nr.netID);
					makeArcInst(type, width, ni.getOnlyPortInst(), wf.to, nr.netID);
					lastPort = ni.getOnlyPortInst();
				} else if (v1.getY() == v2.getY())
				{
					// first line is horizontal: run a vertical bit
					NodeInst ni = makeNodeInst(np, new EPoint(toPoly.getCenterX(), v1.getY()),
						np.getDefWidth(), np.getDefHeight(), Orientation.IDENT, cell, nr.netID);
					makeArcInst(type, width, ni.getOnlyPortInst(), wf.to, nr.netID);
					lastPort = ni.getOnlyPortInst();
				}
			}
		}
		for(int i=0; i<wf.vertices.size(); i++)
		{
			SearchVertex sv = wf.vertices.get(i);
			boolean madeContacts = false;
			while (i < wf.vertices.size()-1)
			{
				SearchVertex svNext = wf.vertices.get(i+1);
				if (sv.getX() != svNext.getX() || sv.getY() != svNext.getY() || sv.getZ() == svNext.getZ()) break;
				List<MetalVia> nps = metalVias[Math.min(sv.getZ(), svNext.getZ())].getVias();
				int whichContact = sv.getContactNo();
				MetalVia mv = nps.get(whichContact);
				PrimitiveNode np = mv.via;
				Orientation orient = Orientation.fromJava(mv.orientation*10, false, false);
				SizeOffset so = np.getProtoSizeOffset();
				double xOffset = so.getLowXOffset() + so.getHighXOffset();
				double yOffset = so.getLowYOffset() + so.getHighYOffset();
				double wid = Math.max(np.getDefWidth()-xOffset, nr.minWidth) + xOffset;
				double hei = Math.max(np.getDefHeight()-yOffset, nr.minWidth) + yOffset;
				NodeInst ni = makeNodeInst(np, new EPoint(sv.getX(), sv.getY()), wid, hei, orient, cell, nr.netID);
				ArcProto type = metalArcs[sv.getZ()];
				double width = Math.max(type.getDefaultLambdaBaseWidth(), nr.minWidth);
				makeArcInst(type, width, lastPort, ni.getOnlyPortInst(), nr.netID);
				lastPort = ni.getOnlyPortInst();
				madeContacts = true;
				sv = svNext;
				i++;
			}
			if (madeContacts && i != wf.vertices.size()-1) continue;

			PrimitiveNode np = metalArcs[sv.getZ()].findPinProto();
			PortInst pi = null;
			if (i == wf.vertices.size()-1)
			{
				pi = wf.from;
				PolyBase fromPoly = wf.from.getPoly();
				if (fromPoly.getCenterX() != sv.getX() || fromPoly.getCenterY() != sv.getY())
				{
					// end of route is off-grid: adjust it
					if (wf.vertices.size() >= 2)
					{
						SearchVertex v1 = wf.vertices.get(wf.vertices.size()-2);
						SearchVertex v2 = wf.vertices.get(wf.vertices.size()-1);
						ArcProto type = metalArcs[wf.fromZ];
						double width = Math.max(type.getDefaultLambdaBaseWidth(), nr.minWidth);
						if (v1.getX() == v2.getX())
						{
							// last line is vertical: run a horizontal bit
							PrimitiveNode pNp = metalArcs[wf.fromZ].findPinProto();
							NodeInst ni = makeNodeInst(pNp, new EPoint(v1.getX(), fromPoly.getCenterY()),
								np.getDefWidth(), np.getDefHeight(), Orientation.IDENT, cell, nr.netID);
							makeArcInst(type, width, ni.getOnlyPortInst(), wf.from, nr.netID);
							pi = ni.getOnlyPortInst();
						} else if (v1.getY() == v2.getY())
						{
							// last line is horizontal: run a vertical bit
							PrimitiveNode pNp = metalArcs[wf.fromZ].findPinProto();
							NodeInst ni = makeNodeInst(pNp, new EPoint(fromPoly.getCenterX(), v1.getY()),
								np.getDefWidth(), np.getDefHeight(), Orientation.IDENT, cell, nr.netID);
							makeArcInst(type, width, ni.getOnlyPortInst(), wf.from, nr.netID);
							pi = ni.getOnlyPortInst();
						}
					}
				}
			} else
			{
				NodeInst ni = makeNodeInst(np, new EPoint(sv.getX(), sv.getY()),
					np.getDefWidth(), np.getDefHeight(), Orientation.IDENT, cell, nr.netID);
				pi = ni.getOnlyPortInst();
			}
			if (lastPort != null)
			{
				ArcProto type = metalArcs[sv.getZ()];
				double width = Math.max(type.getDefaultLambdaBaseWidth(), nr.minWidth);
				makeArcInst(type, width, lastPort, pi, nr.netID);
			}
			lastPort = pi;
		}

		// now see how far out of the bounding rectangle the route went
		Rectangle2D routeBounds = new Rectangle2D.Double(Math.min(wf.fromX,wf.toX), Math.min(wf.fromY,wf.toY),
			Math.abs(wf.fromX-wf.toX), Math.abs(wf.fromY-wf.toY));
		double lowX = routeBounds.getMinX(), highX = routeBounds.getMaxX();
		double lowY = routeBounds.getMinY(), highY = routeBounds.getMaxY();
		for(int i=0; i<wf.vertices.size(); i++)
		{
			SearchVertex sv = wf.vertices.get(i);
			if (i == 0)
			{
				lowX = highX = sv.getX();
				lowY = highY = sv.getY();
			} else
			{
				if (sv.getX() < lowX) lowX = sv.getX();
				if (sv.getX() > highX) highX = sv.getX();
				if (sv.getY() < lowY) lowY = sv.getY();
				if (sv.getY() > highY) highY = sv.getY();
			}
		}
	}

	/**
	 * Method to sum up the distance that a route takes.
	 * @param vertices the list of SearchVertices in the route.
	 * @return the length of the route.
	 */
	private double getVertexLength(List<SearchVertex> vertices)
	{
		if (vertices == null) return Double.MAX_VALUE;
		if (vertices.size() == 0) return Double.MAX_VALUE;
		double sum = 0;
		SearchVertex last = null;
		for(SearchVertex sv : vertices)
		{
			if (last != null)
				sum += Math.abs(sv.getX() - last.getX()) +
					Math.abs(sv.getY() - last.getY()) +
					Math.abs(sv.getZ() - last.getZ())*10;
			last = sv;
		}
		return sum;
	}

	/**
	 * Method to create a NodeInst and update the R-Trees.
	 * @param np the prototype of the new NodeInst.
	 * @param loc the location of the new NodeInst.
	 * @param wid the width of the new NodeInst.
	 * @param hei the height of the new NodeInst.
	 * @param orient the orientation of the new NodeInst.
	 * @param cell the Cell in which to place the new NodeInst.
	 * @param netID the network ID of geometry in this NodeInst.
	 * @return the NodeInst that was created (null on error).
	 */
	private NodeInst makeNodeInst(NodeProto np, EPoint loc, double wid, double hei, Orientation orient, Cell cell, int netID)
	{
		NodeInst ni = NodeInst.makeInstance(np, loc, wid, hei, cell, orient, null, 0);
		if (ni != null)
		{
			AffineTransform trans = ni.rotateOut();
			Poly [] nodeInstPolyList = tech.getShapeOfNode(ni, true, false, null);
			for(int i=0; i<nodeInstPolyList.length; i++)
			{
				PolyBase poly = nodeInstPolyList[i];
				if (poly.getPort() == null) continue;
				poly.transform(trans);
				addLayer(poly, GenMath.MATID, netID, false);
			}
		}
		return ni;
	}

	/**
	 * Method to create an ArcInst and update the R-Trees.
	 * @param type the prototype of the new ArcInst.
	 * @param wid the width of the new ArcInst.
	 * @param from the head PortInst of the new ArcInst.