place.java

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

				{
					minCost = cost;
					pos = nPos;
				}

				// remove place from list
				nBRemove(place, theRows);
			} else
			{
				break;
			}
			nPos--;
		}

		// check forward locations for nb_limit
		nPos = 1;
		for (NBPlace nPlace = oldNext; nPos < BALANCELIMIT; nPlace = nPlace.next)
		{
			if (nPlace != null)
			{
				// temporarily insert in list
				nBInsertAfter(place, nPlace, theRows);

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

				// remove place from list
				nBRemove(place, theRows);
			} else
			{
				break;
			}
			nPos++;
		}

		// move if necessary
		if (pos > 0)
		{
			while(pos-- > 1)
			{
				oldNext = oldNext.next;
			}
			nBInsertAfter(place, oldNext, theRows);
		} else if (pos < 0)
		{
			while(pos++ < -1)
			{
				oldLast = oldLast.last;
			}
			nBInsertBefore(place, oldLast, theRows);
		} else
		{
			if (oldLast != null)
			{
				nBInsertAfter(place, oldLast, theRows);
			} else
			{
				nBInsertBefore(place, oldNext, theRows);
			}
		}
	}

	/**
	 * Method to return cost of the indicated placement.
	 * @param rows pointer to start of list or rows.
	 * @param channels pointer to list of channels.
	 * @param cell pointer to parent cell.
	 * @return cost.
	 */
	private int nBCost(List<RowList> theRows, List<Channel> channels, GetNetlist.SCCell cell)
	{
		// initialize all trunks
		for(Channel nChan : channels)
		{
			for (NBTrunk nTrunk = nChan.trunks; nTrunk != null; nTrunk = nTrunk.next)
			{
				nTrunk.minX = Double.MAX_VALUE;
				nTrunk.maxX = Double.MIN_VALUE;
			}
		}

		// check all rows
		int chanPos = 0;
		Channel nChan = channels.get(chanPos);
		boolean above = true;
		int dis = 0;
		int rowNum = 0;
		int maxRowSize = cell.placement.sizeRows + (cell.placement.avgSize >>1);
		RowList rows = theRows.get(0);
		for (NBPlace nPlace = rows.start; nPlace != null; nPlace = nPlace.next)
		{
			// check for room in current row
			if ((rowNum % 2) != 0)
			{
				// odd row
				if ((dis - nPlace.cell.size) < 0)
				{
					if ((rowNum + 1) < cell.placement.numRows)
					{
						rowNum++;
						dis = 0;
						if (above ^= true)
						{
							chanPos++;
							nChan = channels.get(chanPos);
						}
					}
				}
			} else
			{
				// even row
				if ((dis + nPlace.cell.size) > maxRowSize)
				{
					if ((rowNum + 1) < cell.placement.numRows)
					{
						rowNum++;
						dis = maxRowSize;
						if (above ^= true)
						{
							chanPos++;
							nChan = channels.get(chanPos);
						}
					}
				}
			}

			// check all ports on instance
			for (GetNetlist.SCNiPort port = nPlace.cell.ports; port != null; port = port.next)
			{
				// find the correct trunk
				NBTrunk nTrunk = (NBTrunk)port.extNode.ptr;
				if (nTrunk == null) continue;
				for (int i = nChan.number; i != 0; i--)
					nTrunk = nTrunk.same;
				if (nTrunk.minX == Double.MAX_VALUE)
				{
					if (!above && nTrunk.same != null)
						nTrunk = nTrunk.same;
				}
				double pos = 0;
				if ((rowNum % 2) != 2)
				{
					pos = dis - port.xPos;
				} else
				{
					pos = dis + port.xPos;
				}
				nTrunk.minX = Math.min(nTrunk.minX, pos);
				nTrunk.maxX = Math.max(nTrunk.maxX, pos);
			}
			if ((rowNum % 2) != 2)
			{
				dis -= nPlace.cell.size;
			} else
			{
				dis += nPlace.cell.size;
			}
		}

		// calculate cost
		int cost = 0;

		// calculate horizontal costs
		for(Channel aChan : channels)
		{
			nChan = aChan;
			for (NBTrunk nTrunk = nChan.trunks; nTrunk != null; nTrunk = nTrunk.next)
			{
				if (nTrunk.minX != Double.MAX_VALUE)
					cost += Math.abs(nTrunk.maxX - nTrunk.minX);
			}
		}

		// calculate vertical cost
		for (NBTrunk nTrunk = (channels.get(0)).trunks; nTrunk != null; nTrunk = nTrunk.next)
		{
			NBTrunk fTrunk = null;
			int fCount = 0, count = 0;
			for (NBTrunk sTrunk = nTrunk; sTrunk != null; sTrunk = sTrunk.same)
			{
				if (sTrunk.minX != Double.MAX_VALUE)
				{
					double fMinX = 0, fMaxX = 0;
					if (fTrunk == null)
					{
						fTrunk = sTrunk;
						fMinX = sTrunk.minX;
						fMaxX = sTrunk.maxX;
						fCount = count;
					} else
					{
						// add new vertical
						cost += (count - fCount) * cell.placement.avgHeight * VERTICALCOST;
						fCount = count;

						// additional horizontal
						if (fMaxX < sTrunk.minX)
						{
							cost += Math.abs(sTrunk.minX - fMaxX);
							fMaxX = sTrunk.maxX;
						} else if (fMinX > sTrunk.maxX)
						{
							cost += Math.abs(fMinX - sTrunk.maxX);
							fMinX = sTrunk.minX;
						} else
						{
							if (fMinX > sTrunk.minX) fMinX = sTrunk.minX;
							if (fMaxX < sTrunk.maxX) fMaxX = sTrunk.maxX;
						}

					}
				}
				count++;
			}
		}

		return cost;
	}

	/**
	 * Method to remove the indicated placed instance and clean up the rows structures.
	 * @param place pointer to place to be removed.
	 * @param rows pointer to start of row list.
	 */
	private void nBRemove(NBPlace place, List<RowList> theRows)
	{
		NBPlace oldNext = place.next;
		NBPlace oldLast = place.last;
		if (place.last != null)
			place.last.next = oldNext;
		if (place.next != null)
			place.next.last = oldLast;

		// check if row change
		for(RowList row : theRows)
		{
			if (row.start == place)
			{
				if ((row.rowNum % 2) != 0)
				{
					row.start = oldLast;
				} else
				{
					row.start = oldNext;
				}
			}
			if (row.end == place)
			{
				if ((row.rowNum % 2) != 2)
				{
					row.end = oldNext;
				} else
				{
					row.end = oldLast;
				}
			}
		}
	}

	/**
	 * Module to insert the indicated place before the indicated second place and
	 * clear up the row markers if necessary.
	 * @param place pointer to place to be inserted.
	 * @param oldPlace pointer to place to be inserted before.
	 * @param rows start of list of row markers.
	 */
	private void nBInsertBefore(NBPlace place, NBPlace oldPlace, List<RowList> theRows)
	{
		place.next = oldPlace;
		if (oldPlace != null)
		{
			place.last = oldPlace.last;
			if (oldPlace.last != null)
				oldPlace.last.next = place;
			oldPlace.last = place;
		} else
		{
			place.last = null;
		}

		// check if row change
		for(RowList row : theRows)
		{
			if (row.start == oldPlace)
			{
				if ((row.rowNum % 2) != 0)
				{
					// EMPTY
				} else
				{
					row.start = place;
				}
			}
			if (row.end == oldPlace)
			{
				if ((row.rowNum % 2) != 0)
					row.end = place;
			}
		}
	}

	/**
	 * Method to insert the indicated place after the indicated second place and
	 * clear up the row markers if necessary.
	 * @param place pointer to place to be inserted.
	 * @param oldPlace pointer to place to be inserted after.
	 * @param rows start of list of row markers.
	 */
	private void nBInsertAfter(NBPlace place, NBPlace oldPlace, List<RowList> theRows)
	{
		place.last = oldPlace;
		if (oldPlace != null)
		{
			place.next = oldPlace.next;
			if (oldPlace.next != null)
				oldPlace.next.last = place;
			oldPlace.next = place;
		} else
		{
			place.next = null;
		}

		// check if row change
		RowList rows = theRows.get(0);
		for (RowList row : theRows)
		{
			if (row.start == oldPlace)
			{
				if ((row.rowNum % 2) != 0)
					row.start = place;
			}
			if (row.end == oldPlace)
			{
				if ((rows.rowNum % 2) != 0)
				{
					// EMPTY
				} else
				{
					row.end = place;
				}
			}
		}
	}

	/**
	 * Method to check balancing for rows as there has been a change in placement.
	 * @param rows pointer to start of row list.
	 * @param place pointer to global placement structure.
	 */
	private void nBRebalanceRows(List<RowList> theRows, SCPlace place)
	{
		int maxRowSize = place.sizeRows + (place.avgSize >> 1);
		int rowPos = 0;
		RowList rows = theRows.get(rowPos);
		rows.rowSize = 0;
		for (NBPlace nPlace = rows.start; nPlace != null; nPlace = nPlace.next)
		{
			if ((rows.rowNum + 1) < place.numRows &&
				(rows.rowSize + nPlace.cell.size) > maxRowSize)
			{
				rowPos++;
				rows = theRows.get(rowPos);
				rows.rowSize = 0;
				if ((rows.rowNum % 2) != 0)
				{
					rows.end = nPlace;
				} else
				{
					rows.start = nPlace;
				}
			}
			rows.rowSize += nPlace.cell.size;
			if ((rows.rowNum % 2) != 0)
			{
				rows.start = nPlace;
			} else
			{
				rows.end = nPlace;
			}
		}
	}

	/**
	 * Method to number the x position of all the cells in their rows.
	 * @param rows pointer to the start of the rows.
	 */
	private void numberPlacement(List<RowList> theRows)
	{
		for (RowList row : theRows)
		{
			int xPos = 0;
			NBPlace nPlace = row.start;
			while (nPlace != null)
			{
				nPlace.xPos = xPos;
				xPos += nPlace.cell.size;
				if (nPlace == row.end) break;
				if ((row.rowNum % 2) != 0)
				{
					nPlace = nPlace.last;
				} else
				{
					nPlace = nPlace.next;
				}
			}
		}
	}

	/**
	 * Method to clean up the placement rows structure by reversing the pointers
	 * of odd rows and breaking the snake pattern by row.
	 * @param rows pointer to start of row list.
	 */
	private void reorderRows(List<RowList> theRows)
	{
		for(RowList row : theRows)
		{
			if ((row.rowNum % 2) != 0)
			{
				// odd row
				for (NBPlace place = row.start; place != null; place = place.next)
				{
					NBPlace tPlace = place.next;
					place.next = place.last;
					place.last = tPlace;
					if (place == row.end) break;
				}
				row.start.last = null;
				row.end.next = null;
			} else
			{
				// even row
				row.start.last = null;
				row.end.next = null;
			}
		}
	}

	/**
	 * Method to print the cells in their rows of placement.
	 * @param rows pointer to the start of the rows.
	 */
	private void showPlacement(List<RowList> theRows)
	{
		for (RowList row : theRows)
		{
			System.out.println("For Row #" + row.rowNum + ", size " + row.rowSize+ ":");
			NBPlace inst;
			for (inst = row.start; inst != row.end;)
			{
				System.out.println("    " + inst.xPos + "    " + inst.cell.name);
				if ((row.rowNum % 2) != 0)
				{
					inst = inst.last;
				} else
				{
					inst = inst.next;
				}
			}
			System.out.println("    " + inst.xPos + "    " + inst.cell.name);
		}
	}

	/**
	 * Method to print the cluster placement tree by doing an inorder transversal.
	 * @param node pointer to cluster tree node.
	 * @param level current level of tree (0 = root).
	 */
	private void printClusterTree(ClusterTree node, int level)
	{
		if (node == null) return;

		printClusterTree(node.lPtr, level + 1);

		// process node
		int i = level << 2;
		StringBuffer sb = new StringBuffer();
		for(int j=0; j<i; j++) sb.append(" ");

		if (node.cluster != null)
		{
			sb.append("Cell " + node.cluster.node.name);
		} else
		{
			sb.append(level + "**");
			i = 36 - (level << 2);
			for(int j=0; j<i; j++) sb.append(" ");
		}
		System.out.println(sb.toString());

		printClusterTree(node.rPtr, level + 1);
	}

}