placer.java

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

/* -*- tab-width: 4 -*-
 *
 * Electric(tm) VLSI Design System
 *
 * File: Placer.java
 *
 * Copyright (c) 2003 Sun Microsystems and Static Free Software
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
package com.sun.electric.tool.generator.layout;

import java.util.ArrayList;

import com.sun.electric.database.hierarchy.Cell;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.tool.generator.layout.gates.WellTie;

class Placer {
	private static final boolean VERBOSE = false;
	
	public static final int P = 0;        // PMOS only gate
	public static final int N = 1;        // NMOS only gate
	public static final int PN = 2;       // PMOS and NMOS gate
	
	private StdCellParams stdCell;
	private Cell part;
	private double rowHeight;
	
	private ArrayList<Inst> buildInsts = new ArrayList<Inst>();
	private ArrayList<Net> buildNets = new ArrayList<Net>();
	
	private static void error(boolean pred, String msg) {
		LayoutLib.error(pred, msg);
	}
	
	// ---------------------- private classes --------------------------
	interface PermutationAction {
		// return true if you want to stop checking other permutations
		boolean usePermutation(int[] permutation);
		boolean prunePermutation(int[] permutation, boolean[] placed,
								 int depth);
	}
	
	private static class PermChecker implements PermutationAction {
		int[] bestPermutation = null;
		double bestCost = Double.MAX_VALUE;
		ArrayList<Inst> insts;
		ArrayList<Net> nets;
		double leftX;
		ArrayList<Inst> permInsts = new ArrayList<Inst>();
		long nbChecked, maxPerms;
		
		private void abutLeftRight(int[] permutation) {
			for (int i=0; i<permutation.length; i++) {
				permInsts.set(i, insts.get(permutation[i]));
			}
			Placer.abutLeftRight(leftX, permInsts);
		}
		
		// returns true to abort checking
		public boolean usePermutation(int[] permutation) {
			error(permutation.length!=insts.size(), "wrong permutation size");
			abutLeftRight(permutation);
			double cost = getCostX(nets);
			if (cost<bestCost) {
				bestCost = cost;
				bestPermutation = permutation.clone();
				//System.out.println("Cost= "+cost);
			}
			nbChecked++;
			if (nbChecked>=maxPerms) {
				if (VERBOSE) {
					System.out.println("Abort after checking "+maxPerms+" permutations");
				}
				return true;
			}
			return false;
		}
		// Return the X coordinate of the right boundary of the rightmost
		// placed cell.  Any ports to the left of this are placed. Any
		// ports to the right of this are unplaced.  Return -1 if we
		// shouldn't prune.
		private double abutLeftRight(int[] permutation, boolean[] placed,
									 int depth) {
			double pX=leftX, nX=leftX;
			for (int i=0; i<=depth; i++) {
				Inst inst = insts.get(permutation[i]);
				if (inst.isN()) {
					// NMOS only gate
					inst.moveTo(nX, 0);
					nX += inst.getWidth();
				} else if (inst.isP()) {
					// PMOS only gate
					inst.moveTo(pX, 0);
					pX += inst.getWidth();
				} else {
					// full height NMOS and PMOS gate
					double x = Math.max(nX, pX);
					inst.moveTo(x, 0);
					pX = nX = x+inst.getWidth();
				}
			}
			if (pX!=nX) {
				// Abut failed because I don't know how to find a set of
				// positions representing a tight lower bound on the cost of
				// the unplaced instances.  We will simply choose not to prune
				// in this case.
				return -1;
			}
			
			// Stack all unplaced cells on top of each other. Cost can't
			// possibly be less than this.
			for (int i=0; i<placed.length; i++) {
				if (!placed[i]) {
					Inst inst = insts.get(i);
					inst.moveTo(nX, 0);
				}
			}
			return nX;
		}
		public boolean prunePermutation(int[] permutation, boolean[] placed,
										int depth) {
			// If we've placed all but one, there's nothing to prune.
			// If we've placed all but two, we only save checking 4 permutations.
			// Only consider pruning if there are three or more unplaced cells.
			int nbUnplaced = placed.length - (depth+1);
			if (nbUnplaced<=2) return false;
			
			double maxX = abutLeftRight(permutation, placed, depth);
			if (maxX==-1) return false;
			
			double cost = getPlacedCostX(nets, maxX);
			boolean prune = cost>=bestCost;
			/*
			  if (prune) {
			  if (nbUnplaced>=5) 
			  System.out.println("Pruning at placed/total: "+(depth+1)+"/"+placed.length);
			  }
			*/
			return prune;
		}
//		private double getBestCost() {return bestCost;}
		private ArrayList<Inst> getBestPermutation() {
			ArrayList<Inst> best = new ArrayList<Inst>();
			for (int i=0; i<bestPermutation.length; i++)
				best.add(insts.get(bestPermutation[i]));
			return best;
		}
		PermChecker(ArrayList<Inst> insts, ArrayList<Net> nets, double leftX,
					int maxPerms) {
			this.insts=insts;  this.nets=nets;  this.leftX=leftX;
			this.maxPerms=maxPerms; nbChecked=0;
			
			for (int i=0; i<insts.size(); i++)  permInsts.add(null);
		}
	}
	
	// ------------------------ Private methods ------------------------
	private static void updateElectric(ArrayList<Inst> insts, double rowHeight) {
		for (int i=0; i<insts.size(); i++) {
			insts.get(i).updateElectric(rowHeight);
		}
	}
	
	private static void abutLeftRight(double leftX, ArrayList<Inst> insts) {
		double pX=leftX, nX=leftX;
		for (int i=0; i<insts.size(); i++) {
			Inst inst = insts.get(i);
			if (inst.isN()) {
				// NMOS only gate
				inst.moveTo(nX, 0);
				nX += inst.getWidth();
			} else if (inst.isP()) {
				// PMOS only gate
				inst.moveTo(pX, 0);
				pX += inst.getWidth();
			} else {
				// full height NMOS and PMOS gate
				double x = Math.max(nX, pX);
				inst.moveTo(x, 0);
				pX = nX = x+inst.getWidth();
			}
		}
	}
	
	private static double getCostX(ArrayList<Net> nets) {
		double cost = 0;
		for (int i=0; i<nets.size(); i++) {
			cost += nets.get(i).getCostX();
		}
		return cost;
	}
//	private static double getCost2row(ArrayList<Net> nets) {
//		double cost = 0;
//		for (int i=0; i<nets.size(); i++) {
//			cost += nets.get(i).getCost2row();
//		}
//		return cost;
//	}
	
	// Any ports to the right of maxX are unplaced. Compute the cost as
	// if they are all at maxX.
	private static double getPlacedCostX(ArrayList<Net> nets, double maxX) {
		double cost = 0;
		for (int i=0; i<nets.size(); i++) {
			cost += nets.get(i).getPlacedCostX(maxX);
		}
		return cost;
	}
	
	// returns true to stop checking
	private static boolean forEachPermutation1(int depth, boolean[] mask,
											   int[] permutation,
											   PermutationAction action) {
		int sz = mask.length;
		if (depth>sz-1) {
			// do something with permutation
			return action.usePermutation(permutation);
		}
		for (int i=0; i<sz; i++) {
			if (mask[i]==false) {
				permutation[depth] = i;
				mask[i] = true;
				if (!action.prunePermutation(permutation, mask, depth)) {
					if (forEachPermutation1(depth+1, mask, permutation,
											action)) {
						return true;
					}
				}
				mask[i] = false;
			}
		}
		return false;
	}
	
	// find all permuatations of nb objects
	private static void forEachPermutation(int nb, PermutationAction action) {
		error(nb==0, "permutations of nothing?");
		int[] permutation = new int[nb];
		boolean[] mask = new boolean[nb];
		for (int i=0; i<nb; i++)  mask[i]=false;
		forEachPermutation1(0, mask, permutation, action);
	}
	
	private static long factorial(int i) {
		if (i==0) return 0;
		if (i==1) return 1;
		return i * factorial(i-1);
	}
	
	// try every permutation: exponential
	private static ArrayList<Inst> exhaustive(ArrayList<Inst> insts, ArrayList<Net> nets,
										double leftX, int maxPerms) {
		PermChecker checker = new PermChecker(insts, nets, leftX, maxPerms);
		int nbGates = insts.size();
		if (nbGates==0) return new ArrayList<Inst>();
		if (VERBOSE) {
			System.out.print("Number of gates: "+nbGates);
			System.out.println(", Number of permutations: "+
							   factorial(nbGates));
		}
		forEachPermutation(nbGates, checker);
		return checker.getBestPermutation();
	}
	
	// The distance between ties should be no more than maxDist.  The
	// distance from the edge to the closest tie should be maxDist/2.
	private static ArrayList<Inst> insertWellTies(ArrayList<Inst> insts,
											StdCellParams stdCell, Cell part) {
		// In order to patch right most well gaps, add a full height dummy
		// instance at the end.  Remove it after we're done.
		insts = (ArrayList) insts.clone(); // don't modify input list
		Inst dummy = new Inst(PN, 0, null);
		insts.add(dummy);