lesizer.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: LESizer.java
 * Written by: Jonathan Gainsley, Sun Microsystems.
 *
 * 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.
 *
 * Created on November 11, 2003, 4:42 PM
 */

package com.sun.electric.tool.logicaleffort;

import com.sun.electric.database.text.TextUtils;
import com.sun.electric.database.topology.NodeInst;
import com.sun.electric.tool.Job;
import com.sun.electric.tool.user.ErrorLogger;

import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * LESizer sizes an LENetlist. The LENetlist is generated by LENetlister from
 * the Electric database, or perhaps read in from a Spice file(?)
 *
 * NOTE: the only 'Electric' objects used are in LENetlister,
 * any objects referenced in this file are from the logicaleffort
 * package, although their names may imply otherwise.  Their names
 * are as such because their names match PNP's naming scheme.
 *
 * @author  gainsley
 */
public class LESizer {
    
    /** which algorithm to use */                   private Alg optimizationAlg;
    /** Where to direct output */                   private PrintStream out;
    /** What job we are part of */                  private Job job;
    /** Netlist */                                  private LENetlister1 netlist;
    /** error logger */                             private ErrorLogger errorLogger;

    /** Alg is a typesafe enum class that describes the algorithm to be used */
    public static enum Alg {
        
        /** Sizes all gates for user specified equal gate delay */
        EQUALGATEDELAYS("Equal Gate Delays"),
        /** Sizes for optimal path delay */
        PATHDELAY("Path Delay");
        
        private final String name;
        private Alg(String name) { this.name = name; }
        public String toString() { return name; }
    }
        
    /** Creates a new instance of LESizer */
    protected LESizer(Alg alg, LENetlister1 netlist, Job job, ErrorLogger errorLogger) {
        optimizationAlg = alg;
        this.netlist = netlist;
        this.job = job;
        this.errorLogger = errorLogger;

        out = new PrintStream(System.out);
    }


    // ============================ Sizing For Equal Gate Delays ==========================

	/**
	 * Optimize using loop algorithm;
	 * @param maxDeltaX maximum tolerance allowed in X
	 * @param N maximum number of loops
	 * @param verbose print out size information for each optimization loop
	 * @return true if succeeded, false otherwise
     *
	 * Optimization will stop when the difference in sizes (X) is 
	 * less than maxDeltaX, or when N iterations have occurred.
	 */
	protected boolean optimizeLoops(float maxDeltaX, int N, boolean verbose,
        float alpha, float keeperRatio)
	{
		// iterate through all the instances, updating sizes

		float currentLoopDeltaX = maxDeltaX + 1;	// force at least one iteration
        float lastLoopDeltaX = currentLoopDeltaX;
        int divergingIters = 0;                     // count number if iterations sizing is diverging
        long startTime;
		int loopcount = 0;

		while ((currentLoopDeltaX > maxDeltaX) && (loopcount < N)) {

            // check for aborted state of job
            if (((LETool.AnalyzeCell)job).checkAbort(null)) return false;

			currentLoopDeltaX = 0;
            startTime = System.currentTimeMillis();
            System.out.print("  Iteration "+loopcount);
            if (verbose) System.out.println(":");
            
			// iterate through each instance
			Iterator<Instance> instancesIter = netlist.getAllInstances().values().iterator();

			while (instancesIter.hasNext()) {
				Instance instance = instancesIter.next();
				String instanceName = instance.getName();
				
				// make sure it is a sizeable gate
				if (instance.isLeGate()) {
					
					// get output pin (do not iterate over all output pins, does not make sense)
					ArrayList<Pin> outputPins = instance.getOutputPins();
                    if (outputPins.size() != 1) {
                        // error
                        continue;
                    }
                    Pin outputPin = outputPins.get(0);                    
                    Net net = outputPin.getNet();
                    
                    // now find all pins connected to this net
                    ArrayList<Pin> netpins = net.getAllPins();

                    // find all drivers in same group, of same type (LEGATe or LEKEEPER)
                    List<Instance> drivers = new ArrayList<Instance>();
                    List<Instance> arrayedDrivers = new ArrayList<Instance>();
                    for (Pin pin : netpins) {
                        // only interested in drivers
                        if (pin.getDir() != Pin.Dir.OUTPUT) continue;
                        Instance inst = pin.getInstance();
                        if (inst.getType() == instance.getType()) {
                            if (inst.getParallelGroup() == instance.getParallelGroup()) {
                                // add the instance. Note this adds the current instance at some point as well
                                drivers.add(inst);
                                // error check
                                if (inst.getParallelGroup() > 0 && loopcount == 0 && inst.getLeSU() != instance.getLeSU()) {
                                    String msg = "\nError: LEGATE \""+inst.getName()+"\" drives in parallel with \""+instance.getName()+
                                            "\" but has a different step-up";
                                    System.out.println(msg);
                                    NodeInst ni = inst.getNodable().getNodeInst();
                                    if (ni != null) {
                                        errorLogger.logError(msg, ni, ni.getParent(), inst.getContext(), 0);
                                    }
                                }
                            }
                        }
                        if ((inst.getNodable().getNodeInst() == instance.getNodable().getNodeInst()) &&
                            (inst.getContext() == instance.getContext())) {
                            // this must be an arrayed driver: not this also adds current instance at some point as well
                            arrayedDrivers.add(inst);
                        }
                    }

                    // this will be the new size.
                    float newX = 0;

                    // if this is an LEKEEPER, we need to find smallest gate (or group)
                    // that also drives this net, it is assumed that will have to overpower this keeper
                    if (instance.getType() == Instance.Type.LEKEEPER) {
                        Map<String,List<Instance>> drivingGroups = new HashMap<String,List<Instance>>();

                        float smallestX = 0;

                        // iterate over all drivers on net
                        for (Pin pin : netpins) {
                            // only interested in drivers
                            if (pin.getDir() != Pin.Dir.OUTPUT) continue;
                            Instance inst = pin.getInstance();
//                            if ((inst.getType() == Instance.Type.LEGATE) ||
//                                (inst.getType() == Instance.Type.STATICGATE)) {
                            if ((inst.getType() == Instance.Type.LEGATE)) {
                                // organize by groups
                                int i = inst.getParallelGroup();
                                Integer integer = new Integer(i);
                                if (i <= 0) {
                                    // this gate drives independently, check size
                                    if (smallestX == 0) smallestX = inst.getLeX();
                                    if (inst.getLeX() < smallestX) smallestX = inst.getLeX();
                                }
                                // add to group to sum up drive strength later
                                List<Instance> groupList = drivingGroups.get(integer.toString());
                                if (groupList == null) {
                                    groupList = new ArrayList<Instance>();
                                    drivingGroups.put(integer.toString(), groupList);
                                }
                                groupList.add(inst);
                            }
                        }

                        // find smallest total size of groups
                        Set<String> keys = drivingGroups.keySet();
                        for (String str : keys) {
                            List<Instance> groupList = drivingGroups.get(str);
                            if (groupList == null) continue;            // skip empty groups
                            // get size
                            float sizeX = 0;
                            for (Instance inst : groupList) {
                                sizeX += inst.getLeX();
                            }
                            // check size of group
                            if (smallestX == 0) smallestX = sizeX;
                            if (sizeX < smallestX) smallestX = sizeX;
                        }

                        // if no drivers found, issue warning
                        if (!keys.iterator().hasNext() && loopcount == 0) {
                            String msg = "\nError: LEKEEPER \""+instance.getName()+"\" does not fight against any drivers";
                            System.out.println(msg);
                            NodeInst ni = instance.getNodable().getNodeInst();
                            if (ni != null) {
                                errorLogger.logError(msg, ni, ni.getParent(), instance.getContext(), 0);
                            }
                        }

                        // For now, split effort equally amongst all drivers
                        if (instance.getParallelGroup() <= 0) {
                            newX = smallestX * netlist.getKeeperRatio() / arrayedDrivers.size();
                        }
                        else {
                            newX = smallestX * netlist.getKeeperRatio() / drivers.size();
                        }
                    }

                    // If this is an LEGATE, simply sum all capacitances on the Net
                    if (instance.getType() == Instance.Type.LEGATE) {

                        // compute total le*X (totalcap)
                        float totalcap = 0;
                        Iterator<Pin> netpinsIter = netpins.iterator();
                        int numLoads = 0;
                        while (netpinsIter.hasNext()) {
                            Pin netpin = netpinsIter.next();
                            Instance netpinInstance = netpin.getInstance();
                            float load = netpinInstance.getLeX() * netpin.getLE() * (float)netpinInstance.getMfactor();
                            if (netpin.getDir() == Pin.Dir.OUTPUT) load *= alpha;
                            totalcap += load;
                            // check to see if gate is only driving itself
                            if (netpinInstance != instance)
                                numLoads++;
                        }

                        // create error if no loads only on first iteration
                        if (numLoads == 0 && loopcount == 0) {
                            String msg = "\nError: LEGATE \""+instance.getName()+"\" has no loads: will be ignored";
                            System.out.println(msg);
                            NodeInst ni = instance.getNodable().getNodeInst();