place.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: Place.java
 * Silicon compiler tool (QUISC): placement
 * Written by Andrew R. Kostiuk, Queen's University.
 * Translated to Java by Steven M. Rubin, Sun Microsystems.
 *
 * Copyright (c) 2005 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.sc;

import com.sun.electric.database.hierarchy.Cell;

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;

/**
 * The placement part of the Silicon Compiler tool.
 */
public class Place
{
	/** for debugging output */				private static final boolean DEBUG = false;
	/** TRUE = sort cluster tree */			private static final boolean SORTFLAG = true;
	/** TRUE = do net balance */			private static final boolean BALANCEFLAG = false;
	/** limit of movement */				private static final int     BALANCELIMIT = 2;
	/** scaling factor */					private static final int     VERTICALCOST = 2;

	/***** general placement information *****/
	static class SCPlace
	{
		/** number of instances */					int				numInst;
		/** total size of instances */				int				sizeInst;
		/** average size of inst */					int				avgSize;
		/** average height of inst */				int				avgHeight;
		/** number of rows */						int				numRows;
		/** target size of each row */				int				sizeRows;
		/** rows of placed cells */					List<RowList>   theRows;
		/** start of cell list */					NBPlace			plist;
		/** end of cell list */						NBPlace			endList;
	};

	private static final int BITS_PLACED	= 0x01;
	static final int BITS_EXTRACT			= 0x02;

	private static class Cluster
	{
		/** instance of cluster */					GetNetlist.SCNiTree node;
		/** number of cluster */					int				number;
		/** total size of members */				double			size;
	};

	private static class ClusterTree
	{
		/** cluster, null if intermediate node*/	Cluster			cluster;
		/** working bits */							int				bits;
		/** parent node */							ClusterTree		parent;
		/** pointer to nodes on same level */		ClusterTree		next;
		/** pointer to one group */					ClusterTree		lPtr;
		/** pointer to second group */				ClusterTree		rPtr;
	};

	private static class ClConnect
	{
		/** pointers to names of nodes */			ClusterTree  [] node;
		/** number of connections */				int				count;

		private ClConnect(ClusterTree ct0, ClusterTree ct1, int c)
		{
			node = new ClusterTree[2];
			node[0] = ct0;
			node[1] = ct1;
			count = c;
		}
	};

	static class RowList
	{
		/** start of row cells */					NBPlace		start;
		/** end of row cells */						NBPlace		end;
		/** row number (0 = bottom) */				int			rowNum;
		/** current row size */						int			rowSize;
	};

	static class NBPlace
	{
		/** pointer to cell */						GetNetlist.SCNiTree cell;
		/** x position (0 at left) */				double		xPos;
		/** pointer to last in list */				NBPlace		last;
		/** pointer to right in list */				NBPlace		next;
	};

	private static class Channel
	{
		/** number of channel */					int			number;
		/** list of trunks */						NBTrunk		trunks;
	};

	private static class NBTrunk
	{
		/** pointer to extracted node */			GetNetlist.ExtNode ext_node;
		/** minimum trunk going left */				double		minX;
		/** maximum trunk going right */			double		maxX;
		/** same in next channel */					NBTrunk		same;
		/** pointer to next trunk */				NBTrunk		next;
	};

	/************************* File variables *************************/

	/** global root of cluster tree */		private ClusterTree   gClusterTree;
	/** cost of current cluster tree */		private int           currentCost;

	/**
	 * Method to place the nodes in the current cell in optimal position for routing
	 * based upon number of connections between cells.
	 *
	 * Cluster Tree Creation:
	 *    o  Maxi-cut Algorithm
	 *    o  Minimum use for best pair choice for equal weight
	 * Cluster Tree Sorting:
	 *    o  Top-down cluster tree sort
	 *    o  Bottom-up cluster tree sort
	 * Net Balancing:
	 *    o  Independent routing channels
	 *    o  Cross refencing of trunks to improve speed
	 *    o  Effective calculation of rows in costing
	 */
	public String placeCells(GetNetlist gnl)
	{
		// check to see if currently working in a cell
		if (gnl.curSCCell == null) return "No cell selected";

		// create placement structure
		SCPlace place = new SCPlace();
		gnl.curSCCell.placement = place;
		place.numInst = 0;
		place.sizeInst = 0;
		place.avgSize = 0;
		place.avgHeight = 0;
		place.numRows = SilComp.getNumberOfRows();
		place.sizeRows = 0;
		place.theRows = new ArrayList<RowList>();
		place.plist = null;
		place.endList = null;

		// create clusters of cells
		List<Cluster> clusters = createClusters(gnl.curSCCell);
		int numCl = clusters.size();
		if (numCl == 0)
		{
			System.out.println("ERROR - No cells found to place.  Aborting.");
			return null;
		}

		// if there are fewer cells than rows, decrease the number of rows
		if (numCl < place.numRows) place.numRows = numCl;

		// create a cluster tree node for each cluster
		ClusterTree nStart = null;
		for (Cluster clus : clusters)
		{
			ClusterTree node = new ClusterTree();
			node.cluster = clus;
			node.parent = null;
			node.next = nStart;
			nStart = node;
			node.lPtr = null;
			node.rPtr = null;
		}

		// recursively create cluster tree
		gClusterTree = createCTreeRecurse(nStart, gnl.curSCCell);
		cTreeAddParents(gClusterTree, null);

		if (DEBUG)
		{
			System.out.println("************ Initial placement of Clusters");
			printClusterTree(gClusterTree, 0);
		}
		place.sizeRows = place.sizeInst / place.numRows;

		// place clusters in list by sorting groups
		if (SORTFLAG)
		{
			sortClusterTree(gClusterTree, gnl.curSCCell);
			if (DEBUG)
			{
				System.out.println("************ Placement of Clusters after Sorting");
				printClusterTree(gClusterTree, 0);
			}
		}

		// create first row structure
		RowList row = new RowList();
		row.start = null;
		row.end = null;
		row.rowNum = 0;
		row.rowSize = 0;
		gnl.curSCCell.placement.theRows.add(row);

		// create cell placement list from sorted cluster list
		createPlaceList(gClusterTree, gnl.curSCCell);

		// number placement
		numberPlacement(gnl.curSCCell.placement.theRows);
		if (DEBUG)
		{
			System.out.println("************ Placement before Net Balancing");
			showPlacement(gnl.curSCCell.placement.theRows);
		}

		// do net balance algorithm
		if (BALANCEFLAG)
		{
			netBalance(gnl.curSCCell);
			if (DEBUG)
			{
				System.out.println("************ Placement after Net Balancing");
				showPlacement(gnl.curSCCell.placement.theRows);
			}
		}

		// print process time for placement
		reorderRows(gnl.curSCCell.placement.theRows);

		return null;
	}

	/**
	 * Method to add the parent pointer to the cluster tree by doing a preorder transversal.
	 * @param node pointer to current node in transversal.
	 * @param parent pointer to parent node.
	 */
	private void cTreeAddParents(ClusterTree node, ClusterTree parent)
	{
		if (node == null) return;
		node.parent = parent;
		cTreeAddParents(node.lPtr, node);
		cTreeAddParents(node.rPtr, node);
	}

	/**
	 * Method to create "clusters" of cells of size one.
	 * @param cell pointer to complex cell.
	 * @return list of clusters.
	 */
	private List<Cluster> createClusters(GetNetlist.SCCell cell)
	{
		// find total 'size' and number of all the cells
		int size = 0;
		int num = 0;
		int height = 0;
		for (GetNetlist.SCNiTree iList : cell.niList)
		{
			if (iList.type == GetNetlist.LEAFCELL)
			{
				num++;
				size += iList.size;
				height += SilComp.leafCellYSize((Cell)iList.np);
			}
		}

		List<Cluster> clusters = new ArrayList<Cluster>();
		if (num == 0)
		{
			System.out.println("WARNING - No leaf cells found for placement");
			return clusters;
		}
		int avgSize = size / num;
		int avgHeight = height / num;
		if (DEBUG)
		{
			System.out.println("************ Cell Statistics");
			System.out.println("    Number of cells         = " + num);
			System.out.println("    Total length            = " + size);
			System.out.println("    Average size of cells   = " + avgSize);
			System.out.println("    Average height of cells = " + avgHeight);
		}
		cell.placement.numInst = num;
		cell.placement.sizeInst = size;
		cell.placement.avgSize = avgSize;
		cell.placement.avgHeight = avgHeight;

		// create cluster list
		int i = 0;
		boolean warn = false;
		for (GetNetlist.SCNiTree node : cell.niList)
		{
			if (node.type != GetNetlist.LEAFCELL)
			{
				if (node.type == GetNetlist.COMPLEXCELL) warn = true;
				continue;
			}
			Cluster cluster = new Cluster();
			cluster.node = node;
			cluster.size = node.size;
			cluster.number = i++;
			clusters.add(cluster);
		}
		if (warn)
		{
			System.out.println("WARNING - At least one complex cell found during Create_Clusters");
			System.out.println("        - Probable cause:  Forgot to do 'PULL' command");
		}

		return clusters;
	}

	/**
	 * Method to recursively create the cluster tree from the bottom up by pairing
	 * strongly connected tree nodes together.  When only one tree node
	 * exists, this is the root and can be written to the indicated address.
	 * @param nodes pointer to start of tree nodes.
	 * @param cell pointer to parent cell.
	 * @return tree root.
	 */
	private ClusterTree createCTreeRecurse(ClusterTree nodes, GetNetlist.SCCell cell)
	{
		// if no node, end
		if (nodes == null) return null;

		// if one node, write to root and end
		if (nodes.next == null) return nodes;

		// create list of connections between nodes
		List<ClConnect> connectList = cTreeNumConnects(nodes, cell);

		// pair by number of connects
		ClusterTree nStart = cTreePair(nodes, connectList);

		// recurse up a level
		return createCTreeRecurse(nStart, cell);
	}

	/**
	 * Method to create a list of the number of connections from all groups to all other groups.
	 * @param nodes List of current nodes.
	 * @param cell Pointer to parent cell.
	 */
	private List<ClConnect> cTreeNumConnects(ClusterTree nodes, GetNetlist.SCCell cell)
	{
		List<ClConnect> connections = new ArrayList<ClConnect>();
		int nodeNum = 0;

		// go through list of nodes
		for ( ; nodes != null; nodes = nodes.next)
		{
			// check all other node
			for (ClusterTree nextnode = nodes.next; nextnode != null; nextnode = nextnode.next)
			{
				nodeNum += 2;

				// mark all extracted nodes used by first node
				setExtNodesByCTree(nodes, nodeNum);

				// count number of common extracted nodes
				int common = countExtNodes(nextnode, nodeNum);

				if (common != 0)
				{
					ClConnect newCon = new ClConnect(nodes, nextnode, common);
					connections.add(newCon);
				}
			}
		}

		// sort number of connects from largest to smallest
        Collections.sort(connections, new ConnectsByCount());

        return connections;
	}

    private static class ConnectsByCount implements Comparator<ClConnect>
    {
        public int compare(ClConnect c1, ClConnect c2)
        {
            return c2.count - c1.count;
        }
    }

	/**
	 * Method to mark all extracted nodes references by any member of all the
	 * clusters in the indicated cluster tree.
	 * @param node pointer to cluster tree node.
	 * @param marker value to set flags field to.
	 */
	private void setExtNodesByCTree(ClusterTree node, int marker)
	{
		if (node == null) return;

		setExtNodesByCTree(node.lPtr, marker);

		// process node if cluster
		if (node.cluster != null)
		{
			// check every port of member
			for (GetNetlist.SCNiPort port = node.cluster.node.ports; port != null; port = port.next)
				port.extNode.flags = marker;
		}

		setExtNodesByCTree(node.rPtr, marker);
	}

	/**
	 * Method to return the number of extracted nodes which have flag bit set only
	 * and is accessed by subtree.
	 * @param node start of cluster tree node.
	 * @param marker value to look for.
	 */
	private int countExtNodes(ClusterTree node, int marker)
	{
		if (node == null) return 0;

		int count = countExtNodes(node.lPtr, marker);

		// process node if cluster
		if (node.cluster != null)
		{
			// check every port of member
			for (GetNetlist.SCNiPort port = node.cluster.node.ports; port != null; port = port.next)
			{
				if (port.extNode.flags == marker) count++;
			}
		}

		count += countExtNodes(node.rPtr, marker);
		return count;
	}

	/**
	 * Method to pair up the given nodes by using the information in the connection list.
	 * @param nodes pointer to start of list of nodes.
	 * @param nConnects pointer to start of list of connections.
	 * @return new list.
	 */
	private ClusterTree cTreePair(ClusterTree nodes, List<ClConnect> connectList)
	{
		// clear the placed flag in all tree nodes
		for (ClusterTree tPtr = nodes; tPtr != null; tPtr = tPtr.next)
			tPtr.bits &= ~BITS_PLACED;

		// go through connection list
		ClusterTree newStart = null;
		if (connectList.size() > 0)
		{
			for (int i=0; i<connectList.size(); )
			{
				ClConnect connect = connectList.get(i);
	
				// if either placed, continue
				if ((connect.node[0].bits & BITS_PLACED) != 0 ||
					(connect.node[1].bits & BITS_PLACED) != 0)
				{
					i++;
					continue;
				}
	
				// get best choice
				ClConnect bConnect = bestPair(connectList, i);
	
				// create new cluster tree node
				ClusterTree newNode = new ClusterTree();
				newNode.cluster = null;
				newNode.bits = 0;
				newNode.parent = null;
				newNode.lPtr = bConnect.node[0];
				newNode.lPtr.parent = newNode;
				bConnect.node[0].bits |= BITS_PLACED;
				newNode.rPtr = bConnect.node[1];
				newNode.rPtr.parent = newNode;
				bConnect.node[1].bits |= BITS_PLACED;
				newNode.next = newStart;
				newStart = newNode;
	
				// remove from list
				connectList.remove(bConnect);
			}
		} else
		{
			// create new cluster tree node
			ClusterTree newNode = new ClusterTree();