router.java

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

package com.sun.electric.tool.generator.flag.router;

import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.network.Netlist;
import com.sun.electric.database.network.Network;
import com.sun.electric.database.network.Netlist.ShortResistors;
import com.sun.electric.database.prototype.PortProto;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.database.topology.PortInst;
import com.sun.electric.technology.ArcProto;
import com.sun.electric.tool.generator.flag.FlagConfig;
import com.sun.electric.tool.generator.flag.FlagDesign;
import com.sun.electric.tool.generator.flag.LayoutNetlist;
import com.sun.electric.tool.generator.flag.Utils;
import com.sun.electric.tool.generator.flag.scan.Scan;
import com.sun.electric.tool.generator.layout.AbutRouter;
import com.sun.electric.tool.generator.layout.LayoutLib;
import com.sun.electric.tool.generator.layout.TechType;

public class Router {
	private class PortInfo {
		public final PortInst portInst;
		public final double x, y, maxY, minY;
		public final Channel m2Chan;
		public Segment m2Seg;
		public PortInfo(PortInst pi, LayerChannels m2Chans) {
			portInst = pi;
			x = pi.getCenter().getX();
			y = pi.getCenter().getY();
			maxY = y + config.pinHeight;
			minY = y - config.pinHeight;
			m2Chan = m2Chans.findChanOverVertInterval(x, minY, maxY);
			if (m2Chan==null) {
				prln("no m2 channel for PortInst: "+pi.toString());
				prln(m2Chans.toString());
			}
		}
		public void getM2OnlySeg(double xL, double xR) {
			if (connectsToM2(portInst)) {
				m2Seg = m2Chan.allocateBiggestFromTrack(xL-config.trackPitch, 
						                                x, xR+config.trackPitch, y);
				if (m2Seg==null) {
					prln("failed to get segment for m2-only PortInst: center="+y+
						 "["+(xL-config.trackPitch)+", "+(xR+config.trackPitch)+"]");				
					prln(m2Chan.toString());
				}
			}
		}
	}
    public static final double DEF_SIZE = LayoutLib.DEF_SIZE;

	private final FlagConfig config;
	private final Scan scan;

	private TechType tech() {return config.techTypeEnum.getTechType();}
	
	private void prln(String s) {Utils.prln(s);}
	private void pr(String s) {Utils.pr(s);}
	private void error(boolean cond, String msg) {Utils.error(cond, msg);}
	private void saveTaskDescription(String s) {Utils.saveTaskDescription(s);}
	private void clearTaskDescription() {Utils.clearTaskDescription();}

	
	private void sortLeftToRight(List<PortInfo> pis) {
		Collections.sort(pis, new Comparator<PortInfo>() {
			public int compare(PortInfo p1, PortInfo p2) {
				double diff = p1.portInst.getCenter().getX() -
				              p2.portInst.getCenter().getX();
				return (int) Math.signum(diff);
			}
		});
	}
	private void sortBotToTop(List<PortInfo> pis) {
		Collections.sort(pis, new Comparator<PortInfo>() {
			public int compare(PortInfo p1, PortInfo p2) {
				double diff = p1.portInst.getCenter().getY() -
				              p2.portInst.getCenter().getY();
				return (int) Math.signum(diff);
			}
		});
	}

	private void blockInvisibleM3(Blockage1D m3block, double xLeft) {
		double pitch = config.m3PwrGndPitch;
		for (int i=0; i<36; i++) {
			double x = xLeft + pitch/2 + pitch*i;
			m3block.block(x-config.m3PwrGndWid/2, x+config.m3PwrGndWid/2);
		}
	}
	
	private void blockInvisibleM2(LayerChannels m2Chnls, Rectangle2D bounds) {
		double xCenter = bounds.getCenterX();
		double[] yBlocks = new double[] {-44, 228, 476, 716};
		for (double y : yBlocks) {
			Channel m2ch = m2Chnls.findChanOverVertInterval(xCenter, y, y);
			Segment s =  m2ch.allocate(m2ch.getMinTrackEnd()+6, m2ch.getMaxTrackEnd()-6, y, y);
			
			// debug
			prln("Blocking m2: "+s.toString());
		}
	}
	
	private void findChannels(LayerChannels m2Chnls, LayerChannels m3Chnls, 
			                  List<NodeInst> stages) {
		Rectangle2D colBounds = Utils.findBounds(stages.get(0).getParent());
		Blockage1D m2block = new Blockage1D();
		Blockage1D m3block = new Blockage1D();
		for (NodeInst ni : stages) {
			for (Iterator piIt=ni.getPortInsts(); piIt.hasNext();) {
				PortInst pi = (PortInst) piIt.next();
				double x = pi.getCenter().getX();
				double y = pi.getCenter().getY();
				if (Utils.isPwrGnd(pi) || scan.isScan(pi)) {
					if (connectsToM2(pi)) {
						// horizontal m2 channel
						m2block.block(y-config.m2PwrGndWid/2, y+config.m2PwrGndWid/2);
					} else if (connectsToM3(pi)) {
						// vertical m3 channel
						m3block.block(x-config.m3PwrGndWid/2, x+config.m3PwrGndWid/2);
					} else {
						error(true, "unexpected metal for port: "+pi.toString());
					}
				}
			}
		}
		blockInvisibleM3(m3block, colBounds.getMinX());
		
		Interval prv = null;
		for (Interval i : m2block.getBlockages()) {
	//		 debug
	//		prln("Interval: "+i.toString());
			if (prv!=null) {
				m2Chnls.add(new Channel(true, colBounds.getMinX(),
						                colBounds.getMaxX(),
					                    prv.getMax(), i.getMin(), "metal-2"));
			}
			prv = i;
		}

		blockInvisibleM2(m2Chnls, colBounds);
		
		prv = null;
		for (Interval i : m3block.getBlockages()) {
			double prvMax = prv==null ? colBounds.getMinX() : prv.getMax();
			m3Chnls.add(new Channel(false, colBounds.getMinY(),    
					                colBounds.getMaxY(),
				                    prvMax, i.getMin(), "metal-3"));
			prv = i;
		}
		// add channel between last blockage and cell boundary
		Interval last = prv;
		m3Chnls.add(new Channel(false, colBounds.getMinY(),    
                colBounds.getMaxY(),
                last.getMax(), colBounds.getMaxX(), "metal-3"));
		
		// print status
		prln("Found: "+m2Chnls.numChannels()+" metal-2 channels");
		prln("Found: "+m3Chnls.numChannels()+" metal-3 channels");
	}
	private void routeTwoOrThreePinNet(ToConnect toConn, LayerChannels m2Chan,
            LayerChannels m3Chan) {
		if (toConn.numPortInsts()==2) routeTwoPinNet(toConn, m2Chan, m3Chan);
		if (toConn.numPortInsts()==3) routeThreePinNet(toConn, m2Chan, m3Chan);
	}
	// Single vertical m3 connects to all PortInsts in m2
	private void routeThreePinNet(ToConnect toConn, LayerChannels m2Chan,
	                              LayerChannels m3Chan) {
		saveTaskDescription("Connecting three pins: "+toConn);

		List<PortInst> pis = toConn.getPortInsts();

		List<PortInfo> infos = new ArrayList<PortInfo>();
		for (PortInst pi : pis) {
			PortInfo inf = new PortInfo(pi, m2Chan);
			if (inf.m2Chan==null) return;
			infos.add(inf);
		}
		
		sortLeftToRight(infos);
		PortInfo infoL = infos.get(0);
		PortInfo infoLR = infos.get(1);
		PortInfo infoR = infos.get(2);

		sortBotToTop(infos);
		PortInfo infoB = infos.get(0);
		PortInfo infoT = infos.get(2);

		/** For m2-only pins, allocate m2 segment that can connect any
		 *  two PortInsts */
		for (PortInfo inf : infos) inf.getM2OnlySeg(infoL.x, infoR.x);
		
		// share m2 segments if we can connect PortInsts using m2
		for (int i=0; i<infos.size(); i++) {
			PortInfo inf1 = infos.get(i);
			for (int j=i+1; j<infos.size(); j++) {
				PortInfo inf2 = infos.get(j);
				if (inf1.m2Chan==inf2.m2Chan && !(inf1.m2Seg!=null && inf2.m2Seg!=null)) {
					// connect using m2 
					if (inf1.m2Seg==null && inf2.m2Seg!=null) {
						inf2.m2Seg = inf1.m2Seg;
					} else if (inf1.m2Seg!=null && inf2.m2Seg==null) {
						inf2.m2Seg = inf1.m2Seg; 
					} else {
						// both are null
						// allocate m2 segment that can connect any two PortInsts
						inf1.m2Seg = inf2.m2Seg = 
							inf1.m2Chan.allocate(infoL.x, infoR.x, inf1.y, inf2.y);
						if (inf1.m2Seg==null) return;
					}
				}
			}
		}
		
		// In principle we should test to see if all three pins can be connected 
		// in m2 only. Leave this for later.
		
		// need m3 channel to connect top and bottom m2 channels
		Channel c3 = m3Chan.findVertBridge(infoB.m2Chan, infoT.m2Chan,
				                           infoL.x, infoR.x);
		if (c3==null) {prln("no m3 channel"); return;}

		Segment m3Seg = c3.allocate(infoB.m2Chan.getMinTrackCenter(), 
				                    infoT.m2Chan.getMaxTrackCenter(), 
				                    infoL.x, infoR.x);
		if (m3Seg==null) return;

		// allocate m2 segments for PortInsts that don't share m2 and 
		// that aren't m2 only.
		for (PortInfo inf : infos) {
			if (inf.m2Seg==null) {
				inf.m2Seg = inf.m2Chan.allocate(infoL.x, infoR.x, infoB.y, infoT.y);
				if (inf.m2Seg==null)  return;
			}
		}

		routeUseM3(infoL.portInst, infoLR.portInst, infoL.m2Seg, infoLR.m2Seg, 
				   m3Seg);
		routeUseM3(infoLR.portInst, infoR.portInst, infoLR.m2Seg, infoR.m2Seg,
				   m3Seg);
		clearTaskDescription();
	}
	
	
	private void routeTwoPinNet(ToConnect toConn, LayerChannels m2Chan,
	                            LayerChannels m3Chan) {
		List<PortInst> pis = toConn.getPortInsts();
		
		saveTaskDescription("Connecting two pins: "+toConn);

		List<PortInfo> infos = new ArrayList<PortInfo>();
		for (PortInst pi : pis) {
			PortInfo inf = new PortInfo(pi, m2Chan);
			if (inf.m2Chan==null) return;
			infos.add(inf);
		}
		
		sortLeftToRight(infos);
		PortInfo infoL = infos.get(0);
		PortInfo infoR = infos.get(1);
		
		/** For m2 only pins, allocate m2 segment that can connect any
		 *  two PortInsts */
		for (PortInfo inf : infos) inf.getM2OnlySeg(infoL.x, infoR.x);

		Segment s3 = null;
		
		if (infoL.m2Chan==infoR.m2Chan && !(infoL.m2Seg!=null && infoR.m2Seg!=null)) {
			// connect using m2 only
			if (infoL.m2Seg==null && infoR.m2Seg!=null) {
				infoR.m2Seg = infoL.m2Seg;
			} else if (infoL.m2Seg!=null && infoR.m2Seg==null) {
				infoR.m2Seg = infoL.m2Seg; 
			} else if (infoL.m2Seg==null && infoR.m2Seg==null){
				infoL.m2Seg = infoR.m2Seg = 
					infoL.m2Chan.allocate(infoL.x, infoR.x, infoL.y, infoR.y);
				if (infoL.m2Seg==null) return;
			}
		} else {
			// need to use m3
			// need m3 channel to connect two m2 channels
			Channel c3 = m3Chan.findVertBridge(infoL.m2Chan, infoR.m2Chan, 
					                           infoL.x, infoR.x);
			if (c3==null) {prln("no m3 channel"); return;}
			
			// allocate segments for PortInsts that don't share m2 and that aren't 
			// m2 only.
			for (PortInfo inf : infos) {
				if (inf.m2Seg==null) {
					double minX = Math.min(c3.getMinTrackCenter(), infoL.x);
					double maxX = Math.max(c3.getMaxTrackCenter(), infoR.x);
					inf.m2Seg = inf.m2Chan.allocate(minX, maxX, infoL.y, infoR.y);
					
					if (inf.m2Seg==null) return;

//					// debug
//					if (inf.m2Seg.getTrackCenter()==1102 && Math.abs(inf.m2Seg.min-3585)<100) {
//						prln("Allocating segment: "+inf.m2Seg);
//						prln(m2Chan.toString());
//					}
					
				}
			}
				
			// use more than necessary because using adjacent tracks causes via 
			// spacing violations
			double minY = Math.min(infoL.m2Seg.getTrackCenter(), 
					               infoR.m2Seg.getTrackCenter());
			double maxY = Math.max(infoL.m2Seg.getTrackCenter(), 
					               infoR.m2Seg.getTrackCenter());
			s3 = c3.allocate(minY, maxY, infoL.x, infoR.x);
			
			// hack, return the unused portion of both m2Segs that we don't need
			// I need to do this because of two metal-2-only pins in the same 
			// m3 routing channel.
			infoL.m2Seg.trim(infoL.x-config.trackPitch, s3.getTrackCenter()+config.trackPitch);
			infoR.m2Seg.trim(s3.getTrackCenter()-config.trackPitch, infoR.x+config.trackPitch);
		}

		// do the actual routing right now. In a two level
		// scheme we would actually postpone this
		routeUseM3(infoL.portInst, infoR.portInst, infoL.m2Seg, infoR.m2Seg, s3);
		clearTaskDescription();
	}
	
	private void routeUseM3(PortInst pL, PortInst pR, Segment m2L, Segment m2R, Segment m3) {
		if (m2L==null)  {prln("no m2 track for left PortInst");}
		if (m2R==null)  {prln("no m2 track for right PortInst");}
		if (m3==null)   {prln("no m3 track");}
		if (m2L==null || m2R==null || m3==null) return;
		
		//prln("  Route m3: "+m3.toString());
		
		PortInst m2PortA = null;
		
		Cell parent = pL.getNodeInst().getParent();
		if (connectsToM1(pL)) {
			// left port connects to m1
			NodeInst m1m2a = 
				LayoutLib.newNodeInst(tech().m1m2(), 
					              	  pL.getCenter().getX(),
					                  m2L.getTrackCenter(),