place.java

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

			newNode.cluster = null;
			newNode.bits = 0;
			newNode.parent = null;
			newNode.lPtr = nodes;
			newNode.lPtr.parent = newNode;
			nodes.bits |= BITS_PLACED;
			newNode.rPtr = nodes.next;
			newNode.rPtr.parent = newNode;
			nodes.next.bits |= BITS_PLACED;
			newNode.next = newStart;
			newStart = newNode;
		}

		// add any remaining tree nodes as singular nodes
		for (ClusterTree tPtr = nodes; tPtr != null; tPtr = tPtr.next)
		{
			if ((tPtr.bits & BITS_PLACED) == 0)
			{
				// create new cluster tree node
				ClusterTree newNode = new ClusterTree();
				newNode.cluster = null;
				newNode.bits = 0;
				newNode.parent = null;
				newNode.lPtr = tPtr;
				newNode.lPtr.parent = newNode;
				tPtr.bits |= BITS_PLACED;
				newNode.rPtr = null;
				newNode.next = newStart;
				newStart = newNode;
			}
		}
		return newStart;
	}

	private static class Temp
	{
		ClusterTree	node;		/* cluster tree node */
		int			count;		/* number of times seen */
		ClConnect	ref;		/* first reference */
	}

	/**
	 * Method to find the best cluster connection.
	 * The best has both members unplaced, has the same weight as the one top on the list,
	 * and appears the smallest number of times.
	 * @param connect start of sorted list.
	 * @return pointer to best pair.
	 */
	private ClConnect bestPair(List<ClConnect> connectList, int index)
	{
		List<Temp> sList = new ArrayList<Temp>();
		ClConnect connect = connectList.get(index);
		for(int oIndex=index; oIndex<connectList.size(); oIndex++)
		{
			ClConnect nConnect = connectList.get(oIndex);
			if (nConnect.count < connect.count) break;
			if ((nConnect.node[0].bits & BITS_PLACED) != 0 ||
				(nConnect.node[1].bits & BITS_PLACED) != 0) continue;

			// check if nodes previously counted
			for(int i=0; i<2; i++)
			{
				Temp nList = null;
				for(Temp nl : sList)
				{
					if (nl.node == nConnect.node[i])
					{
						nList = nl;
						break;
					}
				}
				if (nList != null)
				{
					nList.count++;
				} else
				{
					nList = new Temp();
					nList.node = nConnect.node[i];
					nList.count = 1;
					nList.ref = nConnect;
					sList.add(nList);
				}
			}
		}

		// find the minimum count
		Temp best = null;
		for(Temp nList : sList)
		{
			if (best == null || nList.count <= best.count) best = nList;
		}
		return best.ref;
	}

	/**
	 * Method to sort the cluster tree into a list by sorting groups.
	 * Sorting attempts to optimize the placement of groups by
	 * minimizing length of connections between groups and locating groups
	 * close to any specified ports.
	 * @param cTree pointer to root of cluster tree.
	 * @param cell pointer to parent cell.
	 */
	private void sortClusterTree(ClusterTree cTree, GetNetlist.SCCell cell)
	{
		NBTrunk trunks = null;

		// create a list of trunks from the extracted nodes
		for (GetNetlist.ExtNode enode = cell.exNodes; enode != null; enode = enode.next)
		{
			NBTrunk newTrunk = new NBTrunk();
			newTrunk.ext_node = enode;
			newTrunk.minX = 0;
			newTrunk.maxX = 0;
			newTrunk.next = trunks;
			trunks = newTrunk;
			enode.ptr = newTrunk;		// back reference pointer
		}

		currentCost = costClusterTree(gClusterTree, trunks, cell);
		if (DEBUG)
			System.out.println("***** Cost of placement before cluster sorting = " + currentCost);

		// call top-down swapper
		sortSwapperTopDown(cTree, trunks, cell);

		// call bottom-up swapper
		sortSwapperBottomUp(cTree, trunks, cell);
		if (DEBUG)
			System.out.println("***** Cost of placement after cluster sorting = " + currentCost);
	}

	/**
	 * Method to do preorder transversal of cluster tree, swapping groups to try
	 * and sort tree into a more efficient placement.
	 * @param cTree root of cluster tree.
	 * @param trunks list of trunks for costing.
	 * @param cell pointer to parent cell.
	 */
	private void sortSwapperTopDown(ClusterTree cTree, NBTrunk trunks, GetNetlist.SCCell cell)
	{
		if (cTree == null) return;

		// process tree node if there are two subtrees
		if (cTree.lPtr != null && cTree.rPtr != null)
		{
			// swap groups
			switchSubtrees(cTree);

			// check new cost
			int cost2 = costClusterTree(gClusterTree, trunks, cell);

			// swap back if old cost is less than new
			if (currentCost < cost2)
			{
				switchSubtrees(cTree);
			} else
			{
				currentCost = cost2;
			}
		}

		sortSwapperTopDown(cTree.lPtr, trunks, cell);

		sortSwapperTopDown(cTree.rPtr, trunks, cell);
	}

	/**
	 * Method to do a postorder transversal of cluster tree, swapping groups to try
	 * and sort tree into a more efficient placement.
	 * @param cTree root of cluster tree.
	 * @param trunks list of trunks for costing.
	 * @param cell pointer to parent cell.
	 */
	private void sortSwapperBottomUp(ClusterTree cTree, NBTrunk trunks, GetNetlist.SCCell cell)
	{
		if (cTree == null) return;

		sortSwapperBottomUp(cTree.lPtr, trunks, cell);

		sortSwapperBottomUp(cTree.rPtr, trunks, cell);

		// process tree node if there are two subtrees
		if (cTree.lPtr != null && cTree.rPtr != null)
		{
			// swap groups
			switchSubtrees(cTree);

			// check new cost
			int cost2 = costClusterTree(gClusterTree, trunks, cell);

			// swap back if old cost is less than new
			if (currentCost < cost2)
			{
				switchSubtrees(cTree);
			} else
			{
				currentCost = cost2;
			}
		}
	}

	/**
	 * Method to switch the subtrees recursively to perform a mirror image operation along "main" axis.
	 * @param node pointer to top tree node.
	 */
	private void switchSubtrees(ClusterTree node)
	{
		if (node == null) return;

		ClusterTree temp = node.lPtr;
		node.lPtr = node.rPtr;
		node.rPtr = temp;
		switchSubtrees(node.lPtr);
		switchSubtrees(node.rPtr);
	}

	/**
	 * Method to return the "cost" of the indicated cluster tree sort.
	 * Cost is a function of the length of connections between clusters and placement to ports.
	 * @param cTree pointer to cluster tree node.
	 * @param trunks pointer to trunks to use to cost.
	 * @param cell pointer to parent cell.
	 * @return cost.
	 */
	private int costClusterTree(ClusterTree cTree, NBTrunk trunks, GetNetlist.SCCell cell)
	{
		// clear trunks to record lengths
		for (NBTrunk nTrunk = trunks; nTrunk != null; nTrunk = nTrunk.next)
		{
			nTrunk.minX = -1;
			nTrunk.maxX = -1;
		}

		// set trunks lengths
		costClusterTree2(cTree, trunks, 0);

		// calculate cost
		int cost = 0;
		for (NBTrunk nTrunk = trunks; nTrunk != null; nTrunk = nTrunk.next)
		{
			if (nTrunk.minX < 0) continue;
			cost += nTrunk.maxX - nTrunk.minX;
		}

		for (GetNetlist.SCPort pport = cell.ports; pport != null; pport = pport.next)
		{
			if ((pport.bits & GetNetlist.PORTDIRMASK) == 0) continue;
			NBTrunk nTrunk = (NBTrunk)pport.node.ports.extNode.ptr;
			if (nTrunk == null) continue;
			if ((pport.bits & GetNetlist.PORTDIRUP) != 0)
			{
				// add distance to top row
				int row = (int)(nTrunk.maxX / cell.placement.sizeRows);
				if ((row + 1) < cell.placement.numRows)
				{
					cost += (cell.placement.numRows - row - 1) *
						cell.placement.avgHeight * VERTICALCOST;
				}
			}
			if ((pport.bits & GetNetlist.PORTDIRDOWN) != 0)
			{
				// add distance to bottom row
				int row = (int)(nTrunk.minX / cell.placement.sizeRows);
				if (row != 0)
				{
					cost += row * cell.placement.avgHeight * VERTICALCOST;
				}
			}
		}

		return cost;
	}

	/**
	 * Method to set the limits of the trunks by doing an inorder transversal of the cluster tree.
	 * @param cTree pointer to cluster tree node.
	 * @param trunks pointer to trunks to use to cost.
	 * @param pos current position.
	 */
	private double costClusterTree2(ClusterTree cTree, NBTrunk trunks, double pos)
	{
		if (cTree == null) return pos;

		// do all nodes left
		pos = costClusterTree2(cTree.lPtr, trunks, pos);

		// process node
		if (cTree.cluster != null)
		{
			for (GetNetlist.SCNiPort port = cTree.cluster.node.ports; port != null; port = port.next)
			{
				NBTrunk nTrunk = (NBTrunk)port.extNode.ptr;
				if (nTrunk == null) continue;
				if (nTrunk.minX < 0)
					nTrunk.minX = pos + port.xPos;
				nTrunk.maxX = pos + port.xPos;
			}
			pos += cTree.cluster.size;
		}

		// do all nodes right
		return costClusterTree2(cTree.rPtr, trunks, pos);
	}

	/**
	 * Module to create the placement list by simply taking the clusters from the
	 * sorted cluster list and placing members in a snake pattern.
	 * Do an inorder transversal to create placelist.
	 * @param cTree pointer to start of cluster tree.
	 * @param cell pointer to parent cell.
	 */
	private void createPlaceList(ClusterTree cTree, GetNetlist.SCCell cell)
	{
		if (cTree == null) return;

		createPlaceList(cTree.lPtr, cell);

		// add clusters to placement list
		if (cTree.cluster != null)
		{
			addClusterToRow(cTree.cluster, cell.placement.theRows, cell.placement);
		}

		createPlaceList(cTree.rPtr, cell);
	}

	/**
	 * Method to add the members of the passed cluster to the indicated row.
	 * Add new rows as necessary and also maintain a global placement
	 * bidirectional list.
	 * @param culster pointer to cluster to add.
	 * @param row pointer to the current row.
	 * @param place pointer to placement information.
	 */
	private void addClusterToRow(Cluster cluster, List<RowList> theRows, SCPlace place)
	{
		if (cluster.node.type != GetNetlist.LEAFCELL) return;
		NBPlace newPlace = new NBPlace();
		newPlace.cell = cluster.node;
		newPlace.xPos = 0;
		cluster.node.tp = newPlace;
		newPlace.next = null;
		newPlace.last = place.endList;
		if (place.endList == null)
		{
			place.plist = place.endList = newPlace;
		} else
		{
			place.endList.next = newPlace;
			place.endList = newPlace;
		}

		// get the last entry in the list
		RowList row = theRows.get(theRows.size() - 1);
		double oldCondition = place.sizeRows - row.rowSize;
		double newCondition = place.sizeRows - (row.rowSize + cluster.node.size);
		if ((row.rowNum + 1) < place.numRows &&
			Math.abs(oldCondition) < Math.abs(newCondition))
		{
			RowList row2 = new RowList();
			row2.start = null;
			row2.end = null;
			row2.rowNum = row.rowNum + 1;
			row2.rowSize = 0;
			theRows.add(row2);
			row = row2;
		}

		// add to row
		if ((row.rowNum % 2) != 0)
		{
			// odd row
			if (row.end == null)
				row.end = newPlace;
			row.start = newPlace;
		} else
		{
			// even row
			if (row.start == null)
				row.start = newPlace;
			row.end = newPlace;
		}
		row.rowSize += cluster.node.size;
	}

	/**
	 * Method to do a net balancing on the placelist.
	 * @param row pointer to start of row list.
	 * @param cell pointer to parent cell.
	 */
	private void netBalance(GetNetlist.SCCell cell)
	{
		// create channel list
		List<Channel> channels = new ArrayList<Channel>();
		int i = 0;
		NBTrunk sameTrunk = null;
		do
		{
			Channel newChan = new Channel();
			newChan.number = i;
			NBTrunk trunks = null, oldTrunk = null;

			// create trunk list for each channel
			for (GetNetlist.ExtNode nList = cell.exNodes; nList != null; nList = nList.next)
			{
				NBTrunk nTrunk = new NBTrunk();
				nTrunk.ext_node = nList;
				nTrunk.minX = 0;
				nTrunk.maxX = 0;
				nTrunk.same = null;
				if (sameTrunk == null)
				{
					nList.ptr = nTrunk;
				} else
				{
					sameTrunk.same = nTrunk;
					sameTrunk = sameTrunk.next;
				}
				nTrunk.next = null;
				if (oldTrunk == null)
				{
					trunks = oldTrunk = nTrunk;
				} else
				{
					oldTrunk.next = nTrunk;
					oldTrunk = nTrunk;
				}
			}
			newChan.trunks = trunks;
			channels.add(newChan);
			sameTrunk = trunks;
			i++;
		} while ((i + 1) < cell.placement.numRows);

		// report current placement evaluation
		if (DEBUG)
			System.out.println("Evaluation before Net-Balancing  = " +
				nBCost(cell.placement.theRows, channels, cell));

		// do the net balance for each cell
		nBAllCells(cell, channels);

		// number placement
		nBRebalanceRows(cell.placement.theRows, cell.placement);
		numberPlacement(cell.placement.theRows);

		// report new evaluation
		if (DEBUG)
			System.out.println("Evaluation after Net-Balancing   = %d" +
				nBCost(cell.placement.theRows, channels, cell));
	}

	/**
	 * Method to do a net balance for each cell on at a time.  Use the SCNiTree to
	 * insure that each cell is processed.
	 * @param cell pointer to parent cell.
	 * @param channels pointer to start of channel list.
	 */
	private void nBAllCells(GetNetlist.SCCell cell, List<Channel> channels)
	{
		// process cell
		for (GetNetlist.SCNiTree iList : cell.niList)
		{
			if (iList.type == GetNetlist.LEAFCELL)
				nBDoCell((NBPlace)iList.tp, channels, cell);
		}
	}

	/**
	 * Method to do a net balance for the indicated instance.
	 * @param place pointer to place of instance.
	 * @param channels pointer to channel list of trunks.
	 * @param cell parent complex cell.
	 */
	private void nBDoCell(NBPlace place, List<Channel> channels, GetNetlist.SCCell cell)
	{
		if (place == null) return;

		// find cost at present location and set as current minimum
		List<RowList> theRows = cell.placement.theRows;
		int minCost = nBCost(theRows, channels, cell);
		int pos = 0;

		// temporarily remove from list
		NBPlace oldLast = place.last;
		NBPlace oldNext = place.next;
		nBRemove(place, theRows);

		// check locations backwards for nb_limit
		int nPos = -1;
		for (NBPlace nPlace = oldLast; nPos >= -BALANCELIMIT; nPlace = nPlace.last)
		{
			if (nPlace != null)
			{
				// temporarily insert in list
				nBInsertBefore(place, nPlace, theRows);

				// check new cost
				int cost = nBCost(theRows, channels, cell);
				if (cost < minCost)