Chapter 6: Placement

6.1 Introduction

The Placer agent server undertakes the placement of circuit cells in a defined area. In chapter 4, the server interface and communication aspects were discussed. This chapter focusses on how the server does the placement itself.

After reading the design information from its client in EDIF format [55], the server performs the placement of components basically in three steps:

It forms columns of related transistors. These columns can be formed by MOS transistors that are connected by their gates, MOS transistors that have their source and drain interconnected (pass pair) or bipolar transistors that share connections.
It forms groups joining columns that share drain or source connections. As these connections are implemented using diffusion layers, the line of transistors, formed by joining the MOSFET columns, can be laid out in the same diffusion strip [48].
It performs the layout of each cell by placing the groups using genetic algorithm techniques and calling Router agent servers to route them.

The best placement successfully routed becomes the final circuit. This circuit is then sent back to the client application, again, as an EDIF description.

6.2 The EDIF description

The server receives, from its client, an EDIF description of the circuit to place and route and the area available for this design. The design is formed by a list of EDIF cells containing physical mask layout views and one cell, the main cell, containing a symbolic view reporting how the other cells are connected. An EDIF cell with just a physical view looks like:

(cell NMOS
  (userData cellFunction NMOS) 
  (view maskLayout Physical 
   (interface 
   (declare inout port (list source drain)) 
   (portImplementation drain (figureGroup NDIFF ...) ...) 
   ...) 
   (contents (figureGroup POLY ...) ...)))

The userData field defines the type of the cell. The cell type is defined for use in the Agents system, it is not a type defined in EDIF, thus an userData command is used. The mask layout view is divided into two parts, the interface and the view's contents. In the interface command, the cell's input and output terminals are declared and their implementation described. In the contents command, the whole cell is described including the terminals. This data structure is maintained after the EDIF commands are interpreted by the Placer server.

The main cell, the one containing the netlist information, looks like:

(cell mainCell 
  (userData cellFunction main) 
  (view symbolic Symbolical 
   (contents 
    (instance PMOS Physical fet1)
   (instance stdNode Physical node0)
    (instance VSS Physical VSS)
   (mustJoin (qualify node0 node)
    (qualify fet7 source) (qualify bip2 emiter)
     (qualify VDD pad)
   ) 
    (mustJoin (qualify node1 node) 
     (qualify VSS pad)
     (qualify fet1 drain) (qualify fet4 drain)
     (qualify bip1 colector) 
    )
   ...
  )))

Again, an userData command defines the type of the cell and there can be only one main cell per design. Only the content field of the symbolic view is used. It holds two commands: the instance command, which declares a cell as part of the layout and gives it a name, and the mustJoin command, which declares what cells are connected and the terminals used in the connection.

Apart from the main cell there are five kinds of cells:

* Pad cells - They describe the ports used by the design. Ports are the terminals used by the design as input/output ports. They come already placed.

* MOSFET cells - They describe CMOS field effect transistors. These transistors will be placed as an array of components.

* Bipolar cells - They describe bipolar transistors (PNP or NPN).

* General cells - They describe any kind of cell.

* ElectricNode cells - They describe all the wiring for a given node. They usually would come empty and the Router agent server would place all the necessary wires to route the particular node in them. However they can come prerouted.

Pad cells come already placed because their placement is more closely related to the global strategy of the leaf cell placement by a silicon compiler (or other type of client), than to the internal arrangements of the cell design. Having used an object oriented approach, the placer should not take part in activities outside its boundaries, such as the global silicon compiler's strategies for leaf cell placement and routing.

Bipolar cells were added having in mind to support BICMOS (Bipolar plus CMOS transistors) digital designs. General cells are used to include any kind of cells. They can be used to include small analogue cells, resistors, capacitors, unusually big or shaped transistors. They give greater flexibility to the placement, but, because of their possibly unusual shape, they can reduce the quality of the final placement. They should be used with care.

The server places components' cells over a design containing the pad cells and any preplaced cells. The server can accept partially placed or wired layouts for completion. Figure 6.1 shows a possible input design and the three types of cells to be placed: CMOS transistors, bipolar transistors and general cells (It is considered that all ElectricNode cells are empty).

6.3 Column formation

The placement strategy is first to form columns of related transistors. Related transistors are: MOS transistors that are connected by their gates, MOS transistors that have their source and drain interconnected (pass pair) or bipolar transistors that share connections. Then to form groups joining columns of MOSFETs that share drain or source connections. And finally to perform the layout of each cell by placing the groups using genetic algorithm techniques and calling Router agent servers to route them.

There are three kinds of agent objects for placement: the Cont agent object controls all the operations; the Abutted agent object first builds columns of related transistors and subsequently tries to unite with other Abutted agents to form groups, and the Eval agent object uses the genetic algorithm (GA) to find a good placement for the groups.

The Cont agent coordinates all the actions. It receives the new circuit, after it has been interpreted from EDIF as a list. It separates the NMOS, PMOS and bipolar transistors and general cells in different lists and creates the first Abutted agent.

An Abutted agent has two behaviours. When it is created it performs its first behaviour: it goes to the lists of available cells, in the Cont agent, and grabs the first cell it can obtain in the following order: NMOS, PMOS, bipolar or general cells. Then it tries to create the biggest possible column following the rules:

To make a gate-connected MOSFET column: if it obtained a PMOS transistor, it tries to obtain other PMOS that have their gate connected to the first one. When there are no more PMOS transistors, it tries the NMOS. If it begins with a NMOS transistor, it tries only the NMOS transistors, the PMOS list is already empty.
To make a pass pair MOSFET column: if the Abutted agent obtained a single transistor and could not make a column of gate connected transistors out of it, it tries to obtain other ones that form a pass pair with the first one. A pass pair are two transistors that have their source and drain interconnected.
To make a column of bipolar transistors: if all MOSFETs have already been processed, the Abutted agent obtains a bipolar transistor and tries to find another that has interconnections with the first to form a column.
To get a general cell: if all the transistors have been used, the Abutted agent obtains a cell. They do not try to join cells together, since there can be only one per agent.

These rules are followed in sequence, when an Abutted agent is created it first tries to grab MOSFETs, then transistors and, at the end, cells. When an agent forms its column of MOSFETs, or of bipolar transistors or gets a cell, it stops and tries to reproduce. If there are more cells to be obtained in the Cont agent, a new Abutted agent is created and it tries to obtain its own set of cells. Abutted agents behave like a culture of bacteria, they keep reproducing until there is no more food.

Figure 6.2 shows the moment when a new Abutted agent is created. There are no more MOSFETs available (PMOS and NMOS lists are empty). The agent is then attempting to grab a bipolar transistor from the bipolar list. At least one more agent will be created to grab the only element of the general list.

6.4 Group formation

When the column creation process finishes, the Cont agent switches the Abutted agents to their second behaviour. The Abutted agents will now try to pair up with other agents joining their cells. To pair up, two agents have to share a number of source/drain interconnections. The idea is to join columns of MOSFETs, by either the source or the drain sides. In this way these MOSFETs can be laid out in parallel strips of diffusion, they can be abutted. Only Abutted agents holding MOSFETs' columns can pair up, but not all of them have to pair up. At the end there can be agents holding just one cell.

The group formation process is performed in cycles controlled by the Cont agent. In this process only Abutted agents holding columns of MOSFETs are considered. In each cycle, the Cont agent goes through the list of Abutted agents, exposes each agent to the others and asks the other agents how well they connect to this agent. Each agent then creates a report showing its situation relating to the exposed agent. This report states if a match is possible, how good this match is and details how it should be implemented. At the end of a cycle, the two agents that have the best connections between each other are joined. These cycles continue until no agents can be joined or the quality of the possible connections is too poor.

Figure 6.3 shows the report and joining stages in more detail. During this particular report stage, agent Abutted #5 was exposed and agent Abutted #8 created a report about their match. They have two possible connections through nodes 1 and 2. The joining report has two parts: a list, containing the line's connection order, and the sides of the connection. The list contains pairs of connecting lines. In the example from figure 6.3, the report states that, in a connection between the two agents, two lines will be joined: line 0 of Abutted #8 will connect to line 1 of Abutted #5 and line 1 of Abutted #8 will connect to line 0 of Abutted #5. Also it states that the drain side of Abutted #8 should join the drain side of Abutted #5. Source side means the right side, and drain side means the left side.

In this particular case, the report was the best one and the two Abutted agents are joined. As the report states that the two agents should be joined by their left side, and because any two groups of MOSFETs only can be joined left to right, the group of MOSFETs belonging to Abutted #5 will be mirrored in relation to the Y axis. After this transformation, Abutted #5 connection side becomes right and the connection is possible. To connect each line properly the program uses the connection description list from the report.

After the grouping of cells has finished, the Cont agent contains a list of Abutted agents holding groups of cells. It then takes these cells from the agents and puts them in a list. The Abutted agents are then destroyed. The next step is to place the groups of cells in the empty design (Top of figure 6.1).

6.5 The genetic algorithm placement

Up to now, only topological relationships between the cells of the design have been exploited to create the groups of cells held by the Cont agent, no grid or position coordinates have been determined for them. This groups will be now placed and this placement optimized using the genetic algorithm (GA) encapsulated in the Eval agent object.

The inputs for the Eval agent are an empty design and a list holding the groups of cells to be placed. The empty design is the same received by the server and shown in figure 6.1. The list of groups comes from the Cont agent and it holds three kinds of groups of cells: arrays of MOSFETs, a list of bipolar transistors and individual general cells (fig. 6.4). The Eval agent has to position them in the empty design in the best possible way.

Before describing the actual algorithm implementation, some steps should be defined because they are closely related to the system being optimized. There are four main points to be defined: encoding, genetic operations, evaluation and classification.

6.5.1 Encoding

Each individual solution in the population is represented by a set of numbers and this representation should be as robust as possible. Figure 6.5 shows an individual and the chromosome that represents it.

The chromosome is not represented by a string, as would be expected, but by a list. This is done to avoid Hamming cliffs and to enhance robustness. As the top of figure 6.5 shows, the elements of this list represent each group being laid out in the cell, with the groups laid out in the same order as they appear in the list. For each group there is another list describing how that particular group will be laid out. This list has the following elements:

Group number is the position (integer) of the group in the group list, the list that holds the description of all groups.
Flip flag is a flag (symbol) that indicates if the group is to be flipped or not, to be flipped means to be mirrored in the Y axis.
Line list is a list with the order that the lines in the group should be laid out. Lines in a group can be freely swapped and will be laid out in the order they appear in the list.
Dx represents the distance (integer) between this group and the last group laid out.
Dy represents the distance (integer) between the group and the Y axis.
Gap represents the distance (integer) added to either the minimum separation between PMOS and NMOS transistors in the case of a group holding an array of them or to the minimum separation between two bipolar transistors in the case of a group holding a list of bipolar transistors.

With the information provided by the chromosome, the individual, shown in figure 6.5, is laid out on the design, in this case, containing only the pads (Vss, Vee, Input and Output). Figure 6.6 shows the actual circuit placement.

6.5.2 Genetic operations

The way the genetic operations are carried out is dependent upon the chosen encoding for the genes. The chosen encoding, in this case, was a list and this affects the way cross-over and mutation are performed.

As figure 6.7 shows, when two individuals mate, their genetic material mix, in this case the list containing placement information for each group. A parent is chosen randomly to be the main parent, the order of the groups in its chromosome will determine the order in the offspring chromosome. In figure 6.7, parent 1 was chosen as the main parent, the order of groups in the offspring reassembles its own, but the actual group's placement information came randomly from both parents. Indeed, in this particular example, only group 3 came from parent 1.

After an offspring is generated, swap and mutation operations can be applied. At the top level, mutation can be used to swap the position of some groups in the offspring. Inside each group description, cross-over and mutation can happen. The FLIP flag can be changed by mutation and the group's lines can be swapped. The distances Dx, Dy and gap can be swapped among the groups or just changed.

Cross-over and mutation operations can generate illegal individuals. Illegal meaning placements that violate design rules. When evaluated they will be classified as "born dead" individuals and will not be added to the population list. It is not possible, at the mating stage, to detect all "born dead" configurations, however the ones that produce out of boundaries placement of cells can be detected and corrected.

To correct them, the program calculates the length of all cells and subtracts it from the length of the available area for placement. This gives the available free space between cells. This space is then divided by the number of cells plus one, which gives the average separation in between the cells and from them to the border of the placement area. The routine then calculates the space left between the last placed cell in the offspring and the border of the available area. If this value is negative it means that the cells are overflowing the available area. If this value is too big, it means that all cells are crowded in one end of the available space (fig. 6.8).

Figure 6.8 shows what the program does to correct the placement. The routine randomly chooses one of the group of cells, then, using the average separation calculated before as a base value, it randomly takes a percentage of the base value and subtracts or adds (depending if the cell is overflowing or crowded) this value to the group's Dx (at maximum adding or subtracting 50% of Dx). It repeats this operation until the space left between the last cell and the available area is neither negative nor too big.

The same operations are repeated for the Dy and Gap distances, the only differences being that these operations have to be undertaken for each group of cells and the distance to be adjusted is the distance from the top of the cell and the top of the available placement area. In this case Dy and Gap are altered until the cell fits in the space.

6.5.3 Evaluation

The new individuals created should be evaluated to find how good their placement is. This step is more closely related to the system being optimized than to the algorithm itself. The best way of doing the evaluation would be by actually routing each placement using the Router agent server. Unfortunately the routing process is slow and would take too long to evaluate all candidates. In place of full routing a method is used to estimate the cost of wiring the circuit. The objective of this method is to evaluate how much a particular placement contributes for the total length of wire and to the amount of crossing among the wires of the circuits. Figure 6.9 shows the wire connection as straight lines in a "rat's nest" fashion, from that projection one can see how much this particular placement will influence the routing process.

To get a similar effect, the evaluation routine uses the same wiring algorithms, that the router uses, but it allows crossing over and short circuits to take place and it does not test for design rule violations. All connections are carried out with the smallest wire possible, changes of layer, however, are undertaken whenever necessary.

As the evaluation pseudo routing takes place, the cost of the wires is being computed. The routine that calculates the cost of each wire is the same that is used by the router. The number of crossings of each new wire with all the old ones, already laid out, is accumulated. At the end, the evaluation routine has the total cost of the pseudo routing and the total number of crossings. Each placement will be judged by these two values.

6.5.4 Classification

After evaluation, each placement or "individual" has two values: the total wire cost and the number of crossings. The whole population of individuals is kept in a list, which is ordered by fitness, the fittest individuals coming first in the list. Every new individual has to be appended to this list in the appropriate position. There is another list holding the evaluation values of each individual in the same order as in the population list. The classification routine goes through this list, calculating a fitness value from each individual evaluation value, and comparing it with the new individual fitness. The routine can give different weights to each evaluation value when calculating the fitness, which can make some characteristics more important than others. After an individual's position has been found, the routine appends it and its evaluation values in the same position to respective lists.

As discussed in chapter 5, the offspring produced by genetic manipulation (the next population to be evaluated) could either replace the whole population (generational approach) or just its less fitted members (steady-state approach). The steady-state approach was implemented here, because the processing time to evaluate each individual is high, which leads to the use of a relatively small population. The program could not afford to kill all individuals from one generation to the next. New individuals are then continuously appended to the population list. When the population reaches a predetermined maximum number, half of it is killed.

The fitness of an individual, and thus its position in the population list, determines its probability of reproduction and death. As figure 6.10 shows, as the position of an individual in the population list increases, its probability of reproduction decreases and its probability of death increases. Both probabilities depend solely on the individual's position in the list, not on its actual fitness value. The two probabilities vary following the normal distribution. To generate the random numbers in such a distribution, the output of a function that generates random numbers between 0 and 1 with equal probability (r) is used as an argument for the erf function:

To find an individual for reproduction or death:

Indreproduction= round((1-Rnumber)*Total), Inddeath= round(Rnumber*Total).

The normal distribution was chosen because it is the distribution used by nature. Whenever individuals are chosen to reproduce or die one of these two probabilities is always used. It means that an unfit individual can reproduce and a fit one can die, but these events have a very small probability of taking place.

6.5.5 The algorithm implementation

Once the four steps, encoding, genetic operations, evaluation and classification, are defined the actual algorithm implementation is basically that described in Chapter 5.

As stated earlier, the inputs for the Eval agent are an empty design and a list holding the groups of cells to be placed. When this agent is created it generates four individuals by placing then randomly. These individuals are then evaluated and classified and become the population.

The Cont agent can use the Eval agent's method run to run a certain number of generations. This cycle (fig. 6.11) is very similar to the one described in figure 5.2. The main difference is the classification stage. This new cycle takes into account the position of an individual in the population list which determines its probability of reproducing or dying, not its actual fitness value. This is similar to nature: fitness only gives a better chance of survival, it does not guarantee it. The stages depicted in figure 6.11 are:

Selection - Two individuals are chosen to mate from the population. The probability of an individual being chosen is greater for the ones in the beginning of the population list (section 6.5.4).
Genetic Operations - The genetic material is mixed using cross-over and mutation. If clones are generated (individuals identical to one of the parents) the process is repeated.
Evaluation - The resulting genetic description is translated into a placement and then evaluated. Placements that are illegal are considered "born dead" and are not included in the population.
Classification - The result of the evaluation is classified in relation to the results of the other members of the population, according to the fitness criteria.
Population - The offspring enters the population list in its proper position.

The cycle is repeated until a certain number of generations has been tried. This number of generations is variable, it is determined by the Cont agent when it calls the Eval agent method run.

6.6 The placement routing cycle

The Cont agent refines the placement of a circuit by doing placement/routing cycles. First, the Cont agent runs a number of generations in the Eval agent to produce a placement for the design and then it sends it to a Router agent server. This cycle is repeated until a Router server produces a fully routed design.

All the communication and resource management of the Router servers is undertaken by the RouterComm object (fig. 6.12). When it receives a design to route the object tries to find a free Router server. If there is none it requests a new one from the Broker agent server. When a Router server is available, the RouterComm object sends the placed design to it. In each cycle, the RouterComm checks if any Router server has already finished its wiring. If one has and the routing was successful, the completed design is returned to the client and the Placer server stops. If the routing failed, this Router server is marked free and can be used for wiring another design.

If the RouterComm object doesn't have any free Router servers available and the Broker server refuses to give it a new one, the program stops until a Router becomes available.

The Placer server finishes, when a design is successfully routed, an error condition occurs or if it has been trying to route for a number of generations unsuccessfully. Figure 6.13 shows a placed/wired design ready to be returned to a client application by the server. If successful the server returns the placed/wired circuit:

(edif shiftreg.cir (design shiftreg ...))

If it fails it returns the statement:

(list sorry)

In both cases the server stops and waits for further commands from the client application.

6.1 - Introduction
6.2 - The EDIF description
6.3 - Column formation
6.4 - Group formation
6.5 - The genetic algorithm placement
6.5.1 - Encoding
6.5.2 - Genetic operations
6.5.3 - Evaluation
6.5.4 - Classification
6.5.5 - The algorithm implementation
6.6 - The placement routing cycle

 Next             Contents        Talk to me