placer.java

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

		
		// build smallest well ties containing 1 well contact.
		Cell pTie = WellTie.makePart(false, true, 0, stdCell);
		Cell nTie = WellTie.makePart(true, false, 0, stdCell);
		
		// default width of WellTie containing 1 contact
		final double tieWid = pTie.getBounds().getWidth();
		
		// maximum distance from right edge of well tie to closest contact
		final double tieEdgeToContDist = WellTie.edgeToContDist();
		
		double pX=0, nX=0;
		double maxDist = stdCell.getWellTiePitch();
		double pSp=maxDist/2, nSp=maxDist/2;
		for (int i=0; i<insts.size(); i++) {
			Inst inst = insts.get(i);
			double instWid = inst.getWidth();
			if (instWid > maxDist) {
				System.out.println("The gate: "+
								  inst.getNodeInst().getProto().getName()+
								   " is larger than the well tap spacing!!!");
			}
			
			boolean nAbuts = nX>=pX;
			double testDist = inst==dummy ? maxDist/2 : maxDist;
			if (inst.isN() || (inst.isPN() && nAbuts)) {
				// NMOS abuts NMOS
				if ((nSp + instWid > testDist) && nSp!=0) {
					// insert NMOS well tie
					NodeInst ni = LayoutLib.newNodeInst(nTie,0,0,0,0,0,part);
					insts.add(i, new Inst(N, tieWid, ni));
					nX += tieWid;
					nSp = 0;
				} else if (inst.isPN()) {
					// abut full height gate
					double gap = nX-pX;
					if (gap>0) {
						// There's a PMOS well gap. Patch it.
						Cell patch = WellTie.makePart(false, true,gap,stdCell);
						NodeInst ni =
							LayoutLib.newNodeInst(patch,0,0,0,0,0,part);
						insts.add(i, new Inst(P, gap, ni));
						i++;
						pSp = gap>=tieWid ? tieEdgeToContDist : pSp + gap;
					}
					pX = nX = nX + instWid;
					nSp += instWid;
					pSp += instWid;
				} else {
					// abut half height NMOS
					nX += instWid;
					nSp += instWid;
				}
			} else if (inst.isP() || (inst.isPN() && !nAbuts)) {
				// PMOS abuts PMOS
				if ((pSp + instWid > testDist) && pSp!=0) {
					// insert PMOS well tie
					NodeInst ni = LayoutLib.newNodeInst(pTie,0,0,0,0,0,part);
					insts.add(i, new Inst(P, tieWid, ni));
					pX += tieWid;
					pSp = 0;
				} else if (inst.isPN()) {
					// abut full height gate
					double gap = pX-nX;
					if (gap>0) {
						// There's a NMOS well gap. Patch it.
						Cell patch = WellTie.makePart(true, false,gap,stdCell);
						NodeInst ni =
							LayoutLib.newNodeInst(patch,0,0,0,0,0,part);
 						insts.add(i, new Inst(N, gap, ni));
						i++;
						nSp = gap>=tieWid ? tieEdgeToContDist : nSp + gap;
					}
					pX = nX = pX + instWid;
					pSp += instWid;
					nSp += instWid;
				} else {
					// abut half height PMOS
					pX += instWid;
					pSp += instWid;
				}
			}
		}
		insts.remove(dummy);
		return insts;
	}
	
	private static ArrayList<Inst> threeRegionPlace(ArrayList<Inst> insts, ArrayList<Net> nets,
											  int maxPerms) {
		ArrayList<Inst> nInsts=new ArrayList<Inst>(),  pInsts=new ArrayList<Inst>(),
			pnInsts=new ArrayList<Inst>();
		for (int i=0; i<insts.size(); i++) {
			Inst inst = insts.get(i);
			if (inst.isN()) {
				nInsts.add(inst);
			} else if (inst.isP()) {
				pInsts.add(inst);
			} else {
				pnInsts.add(inst);
			}
		}
		ArrayList<Inst> allInsts = new ArrayList<Inst>(pnInsts);
		allInsts.addAll(nInsts);
		allInsts.addAll(pInsts);
		abutLeftRight(0, allInsts);
		
		Inst lastFull = pnInsts.get(pnInsts.size()-1);
		double rightFullX = lastFull.getX() + lastFull.getWidth();
		
		ArrayList<Inst> ans = new ArrayList<Inst>(exhaustive(pnInsts, nets, 0, maxPerms));
		ans.addAll(exhaustive(nInsts, nets, rightFullX, maxPerms));
		ans.addAll(exhaustive(pInsts, nets, rightFullX, maxPerms));
		
		return ans;
	}
	
	// ------------------------ Public classes -----------------------------
	public static class Inst {
		double x;        // position of Cell reference
		int row;
		double w;
		boolean mirrorX, mirrorY;
		int type;           // P, N, or PN
		NodeInst nodeInst;  // allows us to position the part instance
		
		ArrayList<Port> ports = new ArrayList<Port>();
		
		Inst(int type, double width, NodeInst nodeInst) {
			error(type!=P && type!=N && type!=PN, "Placer.Inst: bad type: "+type);
			this.type=type; w=width;
			this.nodeInst = nodeInst;
		}
		
		int nbPorts() {return ports.size();}
		Port getPort(int i) {return ports.get(i);}
		public Port addPort(double ofstX, double ofstY) {
			Port p = new Port(this, ofstX, ofstY);
			ports.add(p);
			return p;
		}
		
		void moveTo(double x, int row) {this.x=x; this.row=row;}
		double getX() {return x;}
		double getMaxX() {return x+w;}
		int getRow() {return row;}
		
		void setMirrorX(boolean mirror) {mirrorX=mirror;}
		boolean getMirrorX() {return mirrorX;}
		void setMirrorY(boolean mirror) {mirrorY=mirror;}
		boolean getMirrorY() {return mirrorY;}
		boolean isN() {return type==N;}
		boolean isP() {return type==P;}
		boolean isPN() {return type==PN;}
		double getWidth() {return w;}
		NodeInst getNodeInst() {return nodeInst;}
		
		// Move NodeInsts in Electric.
		void updateElectric(double rowHeight) {
			LayoutLib.modNodeInst(nodeInst, x, row*rowHeight,0,0,false,false,0);
		}
	}
	
	public static class Port {
		Inst inst;
		double ofstX, ofstY;
		Port(Inst inst, double ofstX, double ofstY) {
			this.inst=inst; this.ofstX=ofstX; this.ofstY=ofstY;
		}
		double getX() {
			double offset = inst.getMirrorX() ? (inst.getWidth()-ofstX) : ofstX;
			return inst.getX() + offset;
		}
		int getRow() {return inst.getRow();}
		Inst getInst() {return inst;}
	}
	
	public static class Net {
		ArrayList<Port> ports = new ArrayList<Port>();
		
		int nbPorts() {return ports.size();}
		Port getPort(int i) {return ports.get(i);}
		public void addPort(Port port) {ports.add(port);}
		
		double getCostX() {
			// handle special case because otherwise we return -infinity
			if (nbPorts()==0)  return 0;
			
			double minX = Double.MAX_VALUE;
			double maxX = Double.MIN_VALUE;
			for (int i=0; i<ports.size(); i++) {
				double x = getPort(i).getX();
				minX = Math.min(minX, x);
				maxX = Math.max(maxX, x);
			}
			return maxX-minX;
		}
		
		// Any port to the right of unplacedX is unplaced. Compute the
		// cost as if all those ports are at unplacedX.
		double getPlacedCostX(double unplacedX) {
			double minX = Double.MAX_VALUE;
			double maxX = Double.MIN_VALUE;
			for (int i=0; i<ports.size(); i++) {
				double x = getPort(i).getX();
				minX = Math.min(minX, x);
				maxX = Math.max(maxX, x);
			}
			maxX = Math.min(maxX, unplacedX);
			minX = Math.min(minX, unplacedX);
			return maxX-minX;
		}
		
		double getCost2row() {
			final int nbRows = 2;
			double[] minX = new double[nbRows],
				maxX = new double[nbRows];
//			double[] costX = new double[nbRows];
			for (int i=0; i<nbRows; i++) {
				minX[i] = Double.MAX_VALUE;  maxX[i] = Double.MIN_VALUE;
			}
			for (int i=0; i<ports.size(); i++) {
				Port port = getPort(i);
				double x = port.getX();
				int r = port.getRow();
				minX[r] = Math.min(minX[r], x);
				maxX[r] = Math.max(maxX[r], x);
			}
			double cost = 0;
			for (int i=0; i<nbRows; i++) {
				if (minX[i]!=Double.MAX_VALUE)  cost += maxX[i] - minX[i];
			}
			return cost;
		}
	}
	
	// -------------------------- public methods------------------------------
	public Placer(StdCellParams stdCell, Cell part) {
		this.stdCell=stdCell;  this.part=part;
		rowHeight = stdCell.getNmosWellHeight() + stdCell.getPmosWellHeight();
	}
	
	public Inst addInst(int type, double w, NodeInst nodeInst) {
		Inst inst = new Inst(type, w, nodeInst);
		buildInsts.add(inst);
		return inst;
	}
	
	public Net addNet() {
		Net net = new Net();
		buildNets.add(net);
		return net;
	}
	
	public ArrayList<NodeInst> place1row() {
		int maxPerms = stdCell.getNbPlacerPerms();
		ArrayList<Inst> insts = threeRegionPlace(buildInsts, buildNets, maxPerms);
		abutLeftRight(0, insts);
		double threeRegCost = getCostX(buildNets);
		
		if (stdCell.getExhaustivePlace()) {
			insts = exhaustive(insts, buildNets, 0, stdCell.getNbPlacerPerms());
			abutLeftRight(0, insts);
			double exhCost = getCostX(buildNets);
			double improve = Math.rint(1000 * (threeRegCost-exhCost)/threeRegCost)/10;
			if (VERBOSE) {
				System.out.println("exhaustive search improvement: "+improve+"%");
			}
		}
		
		insts = insertWellTies(insts, stdCell, part);
		abutLeftRight(0, insts);
		updateElectric(insts, rowHeight);
		
		Inst rightInst = insts.get(insts.size()-1);
		stdCell.addEssentialBounds(0, rightInst.getMaxX(), part);
		
		ArrayList<NodeInst> nodeInsts = new ArrayList<NodeInst>();
		for (int i=0; i<insts.size(); i++) {
			nodeInsts.add(insts.get(i).getNodeInst());
		}
		return nodeInsts;
	}
	
	public ArrayList place2row() {
		return new ArrayList();
	}
}