Open access

Mean Field Annealing Based Techniques for Resolving VLSI Automatic Design Problems

Written By

G.R. Karimi and A. AziziVerki

Submitted: 27 November 2011 Published: 17 October 2012

DOI: 10.5772/52092

From the Edited Volume

Simulated Annealing - Single and Multiple Objective Problems

Edited by Marcos de Sales Guerra Tsuzuki

Chapter metrics overview

1,844 Chapter Downloads

View Full Metrics

1. Introduction

The neuro-computing approaches based on Hopfield model were successfully applied to various combinatorial optimization problems such as the traveling salesman problem [1-3], scheduling problem [4], mapping problem [5], knapsack problem [6,7], communication routing problem [8], graph partitioning problem [2,9,10], graph layout problem [11], circuit partitioning problem [12,13].

MFA, as a neuro-computing technique, is applied for solving combinatorial optimization problems [1,2,4-8,10,13], cell placement problem [14].

MFA combines the annealing notion of SA approach with the collective computation property of Hopfield neural networks to obtain optimal solution for np-hard problems.

We begin our study with the review of basic concepts of MFA techniques and describe the applied use of this technique to solve the problems in high speed Integrated Circuits (IC) design and in addition we applied a modified MFA algorithm to solve VLSI relocation problem [15].

1.1. Annealing

Annealing is a mechanical process in which material is slowly cooled allowing the molecules to arrange themselves in such a way that the material is less strained thereby making it more stable.

If materials such as glass or metal are cooled too quickly its constituent molecules will be under high stress lending it to failure (breaking) if further thermal or physical shocks are encountered. Slowing the cooling of the material allows each molecule to move into a place it feels most comfortable, i.e., less stress.

Figure 1.

Molecules movement at the cooling process

As the material is kept at a high temperature the molecules are able to move around quite freely thus reducing stress on a large scale, indeed if the material is made too hot it will move into the liquid state allowing free movement of the molecules. As the material is cooled the molecules are not able to move around as freely but still move limited distances reducing stress in regional areas. The result is a material with significantly less internal stress and resistant to failure due to external shock.

The statistic mechanic is a domain in physics that describes the process of slow cooling of HamiltonianIsing for particles or spins with high degree of freedom until they accede on their equilibrium states. The particles that are cooling, on solid state, provide a framework to characteristics improvisation of intricate and large systems. Now this idea is stated inside optimization algorithms to resolve various cases of problems.

1.2. Hopfield Neural Network (HNN)

The Hopfield Network is a fully connected network of simple processing units, Vi, with numerically weighted symmetric connections, Tij, between units Vi and Vj. processing units have states (either discrete in {0, 1}, or continuous in [0, 1] depending on whether the discrete or the continuous version of the network is being considered). Each processing unit performs simple and identical computations which generally involve summing weighted inputs to unit, applying an internal transfer function, and changing state if necessary. The power of the Hopfield model lies in the connections between unitsand the weights of these connections [16]. An Energy function was defined by Hopfield on the states of the network (values of all units). The energy function, E, in its simplest form is:

E= -12i=1Nj=1NTijVjVi+ i=1NViIiE1

WhereVi denotes the current state (value) of the ith neuron and Ii denotes its bias. Hopfield utilized the fact that the E(Vi)is a Liapunov function (bounded from below) to show that, from any starting state, the network would always converge to some energy function minimum upon applying a sequence of asynchronous local state updates (that locally reduce energy).

To solve any particular problem, first a decision must be made on how to set the network parameters T and I, so that minimization of the problem objective function and enforces satisfaction of the problem constraints; this process is termed ‘mapping’ the problem onto the network. Hopfield gives the motion equation of the ith neuron:

dUidt= UiϢ- E(Vi)Vi,
Ui= EH(Vi)ViE2

WhereE is energy function in term of Vi andEH is Hopfield termof energy function. Totally Eq. 2.is motion (updating) equation of state of neurons andits output isUi.Usually a simple nondecreasing monatomic output function in term of Ui like g(Ui)is applied torelate Uito the states. Typically this function is a step function or a hyperbolic tangent function.Ϣ is a constant number as the weighting factor ofUi.Thereforea Hopfield Neural Network minimizes a cost function that is encoded with its weights by implementation of gradient descent.For more details see [16]

Advertisement

2. MFA technique

As it mentioned before, MFA merges collective computation and annealing properties of Hopfield neural Networks and SA, respectively, to obtain a general algorithm for solving combinatorial optimization problems. MFA can be used for solving a combinatorial optimization problem by choosing a representation schemeinwhichthefinalstatesofthe discrete variables (spins or neurons)canbedecodedasasolutiontotheproblem. In fact the space of problem is mapped to the space of MFA variables (spins) and there will be a one-to-one relation between two spaces. This is called encoding. Then, an energy function is formulated in term of spins with a structure that is based on essence of problem whose global minimum value corresponds to an optimumsolutionoftheproblem. MFAisexpectedtocomputetheoptimumsolutiontothetargetproblem,starting from a randomly chosen initial state, by minimizing this energy function. Steps of applying MFA technique to a problem can be summarized as follows:

  1. Choose a representation plan which encodes the configuration space of the target optimization problem using spins. In order to get a good performance, number of possible configurations in the problem domain and the spin domain must be equal. That means there must be a one-to-onemapping between the configurationsofspinsandtheproblem.

  2. Formulatethecostfunctionoftheproblemintermsofspins toderivetheenergyfunction of the system.Globalminimumoftheenergy functionshouldcorrespondtotheglobalminimumofthecost function.

  3. Derive the mean field theory equations using formulated energy function. Derive equations are used for updatingaverages (expected values) ofspins.

  4. cooling schedule

  5. Set suitableparameters of theenergy functionand the cooling schedule to obtain efficient algorithm.

These main steps are same for various types of optimization problems and are explained at the following sections.

2.1. Encoding

The MFA algorithm is derived by analogy to Ising and Potts models which are used to estimate the state of asystem of particles, called spins, in thermal equilibrium. In Ising model, spins can be in one of the two statesrepresented by0 and 1, whereas in Potts model they can be in one of the K states andthe configuration of the problem determines which one has to be used.

For K-state Potts model with nS spins, the states of spins are represented using nS K-dimensional vectors.

Si= [Si1,…,Sik, …, SiK] for 1≤ i ≤ nS(3)

Just one of the components of Si is 1 and the others are 0. That means ith spin must be at one of the K- states.

k=1KSik=1 for 1inSE3

For encoding of VLSI circuit design problem, for example, each spin vector corresponds to a cell in the circuit or a module in the placement. Hence, number of spin vectors is equal to the number of cells or modules; nC. Dimension K of the spin vectors is equal to the number of empty part of overall circuit space or empty spaces of the placement. That means we can divide the circuit space (chip area or die surface)to K parts and fill every part just by one and only one of the circuit elements [12, 13]. Therefore when a spin is assigned in kth state that means its corresponding cell or module (circuit element) is placed on kth space or part of circuit or placement.

2.2. Energy function formulation

In the MFA algorithm, the aim is to find the spinvaluesminimizingtheenergyfunctionofthesystem.Inorder to achieve this goal, the average (expected) valueVi = <Si> of each spin vector Si is computed and iteratively updateduntilthesystemstabilizesatsomefixed point.

Vi = < Si>for1inCandVi =[vi1, …, vik, … viK] So:

[vi1, …,vik, … viK]= [< Si1>, …. <Sik>, …, <SiK>] for1inC

vik is probability of finding spini at state k and can take any real value between 0 and 1. When the system is stabilized, vik values are expected to converge to 0 or 1.As the system is a Potts glass we have the following constraint:

k=1Kvik=1 for 1inCE4

This constraint guarantees that each Potts spin Si is in one of the K states at a time, and each cell is assigned to only one position for encoded configuration of the problem.In order to construct an energy function it is helpful to associate the following meaning to the valuesvik, for example:

vik=Pspin i is in position k for 1inC , 1kK(P{} is probability function)

vikis the probability of finding spin i at state k.Ifvik =1, then spin i is in state k and thecorrespondingconfiguration isVi = Si.

Locating spin i at stat k relevant to type of target problem has some costs and actually energy function calculates these costs.Example given, for circuit partitioning problem, utilizing the interconnection cost and the wire-length costfor VLSI placement problem are common cost functions and are used toformulating energy function of these target problems [12-14].

The interconnection cost is represented by Ec that for the circuit is total length of internal connectionsbetween circuit components or the cost of the connections among the circuit partitions. It is clear that if all of the circuit elements are located in one place and overlaps together, the interconnection cost (total wire length) becomes 0 and it is not acceptable. This is what we mean illogical minimization of interconnection cost energy function. So another term of the energy function must be applied for penalizing illogical minimization of first cost function. This term is represented by Ep. For example, this term is imbalanced partitioning for circuit partitioning problem and overlap between modules for VLSI placement problem [13, 14].The total energy function, Et,is sum of both terms:

Et= Ec+ Ϗ × EpE5

Where α parameter is introduced to maintain a balance between the two opposite terms of total energy function.

2.3. Derivation of the mean field theory equations

Mean field theory equations, needed to minimize the total energy function Et, can be derived as follow:

ϳik=-E(V)vikE6

The quantityϳikrepresents the kth element of the mean field vector effecting on spin i.Using themean field values, average spin values, vik, can be updated.

vik=eϳik/Tn=1Keϳin/Tfor1 i nC, 1 k K

Where T is the temperature parameter which is used the relax the system iteratively and is managed with a cooling schedule program.

2.4. Energy difference and cooling schedule

Ateachiteration of algorithm, the mean field vector effecting on a randomly selected spin is computed. Then, spin average vector is updated. This process is repeated for a random sequence of spins until the system is stabilized for the current temperature. The system is observed after each spin vector update in order to detect the convergence to an equilibrium state for a given temperature.

If the total energy does not decrease in most of the successive spin vector updates, this means that the system is stabilized for that temperature. Then, Tis decreased according to the cooling schedule by a decreasing factor and theiterative process restarted again with new temperature. To reduce the complexity of energy difference computation an efficient scheme could be used.

βEik= ϳik βvik so βE=k=1Kϳik βvikwhere βvik=viknew-vik (old)

Depending to complexity of problem, the cooling program could be in one stage or more stages in order to reach faster and better result. In some problems like circuit partitioning problem the applied cooling schedule is simply in one stage (tfis decreasing factor):

Tnew= Told× tf for 0<tf<1E7

Actually cooling schedule controls amount of acceptable cost increasing moves and the efficiency of the algorithm.Clearly for very large temperatures almost any change will be accepted while as the temperature is reduced the chance that a positive cost change will also be accepted is reduced.

2.5. Total MFA algorithm

The total format of MFA for various kind of problem is represented as:

1. Get the initial temperature T0, and set T = T0

2. Initialize the spin averages V=[v11,…, vik,…,vnCK ]

3. While temperature T is in the cooling range DO:

3.1. While E is decreasing DO:

3.1.1. Select the ith spin randomly.

3.1.2. Compute mean field vector corresponding to the ith spin:ϳik=-E(V)vik

3.1.3. Compute the summation: n=1Keϳin/T

3.1.4. Compute new spin average vector: vik(new)=eϳik/T/l=1Keϳil/T

3.1.5. Compute new spin average vector: βE=k=1Kϳik (viknew-vik)

3.1.6. Update the spin average vector: viknew=vik

3.2. Decrease the temperature:T= T× tf

Inside the algorithm some notes must be considered. Selection of initial temperatures is crucial for obtaining good quality solutions. Typically spin averages initialize with an equalvalues plus a smalldisturbing part that is randomly valued but this is not aneternal rule. Addingthis disturbing part causes the spins exit their stable states and their movement starts.Selecting balance factors in energy function has important role for efficiency of the algorithm.

Advertisement

3. VLSI Relocation problem using MFA technique

In modern VLSI physical design, Engineering Change Order (ECO) optimization methods are used to mitigate model placement problems such as hot spots and thermal dissipation that are identified at a given layout at post-routing analysis that is an evaluation stage after placement stage. The relocation problem is defined as adding an additional module to a model placement in order to solve problems at a manner that similarity of the resultant placement to the model placement is kept.

Our presented MFA-based technique is modified form which was applied for cell placement problem in [14] by adding some considerations relating to particular characteristics of the local relocation problem.

3.1. Cell placement problem

Placement is the process of determining the locations of circuit devices on a die surface. ItisanimportantstageintheVLSIdesignflowbecauseitaffectsroutability, performance, heat distribution, and to a less extent, power consumption of a design.

Traditionally, it is applied after the logic synthesis stage and before the routing stage. Since the advent of deep submicron process technology around mid-1990, interconnect delay, which is largely determined by placement, has become the dominating component of circuit delay. As a result, placementinformation is essential even in early design stages to achieve better circuit performance.

The circuit is presented with a hyper-graphΩ(C, N), that consists of a set C representing the cells circuit, a cell weight function of the circuit, a hyper-edge set N representing the nets of the ϧcell:CNand a net weight function ϧnet:NNwhere Nrepresents the set of natural numbers. Space of circuit is a rectangular grid of clusters with P rows and Qcolumns where the cells will be placed.

Figure 2.

Cell location on spin space configuration

As presented before in the K-state Potts model of S spins, the states of spins re represented using S K-dimensional vectors. To apply MFA technique for cell placement problem the circuit layout space is mapped to a grid space with P rows and Q columns. If the number of cells be CL, the number of spins that encode the configuration of problem is CL (P × Q)-dimensional Potts spins so there would be a total of |CL|×P×Q two-state variables.To decreasing the number of spins that encode the configuration of problem, they are separated to two types: row and column spins. Therefore there would be P row spins and Q column spins and totally |CL|× (P+Q) spins[14].For example for a circuit space with 2 rows and 3 columns if the row spin vector of ith cell is vipr=0,1 and its column spin vector is viqc=0,0,1 that means this cell is located at second row and third column of configuration space as Fig. 2.

3.1.1. Energy function formulation

Energy function in the MFA algorithm corresponds to formulation of the cost function of the cell placement problem in terms of spins. Since the MFA algorithm iterates on the expected values of the spins, the expected value of the energy function is formulated. The gradient of the expected value of the energy function is used in the MFA algorithm to compute the new values to update spin vectors in order to minimize the energy function.The applied cost energy for this problem is routing cost energy that is calculated approximately. It is not feasible to calculate the exact routing length for two reasons. Firstly, a feasible placement is not available during the execution of some algorithms; secondly, the computation of the exact routing cost necessitates the execution of the global and the detailed routing phases which are as hard astheplacementphase. Commonly used approximationsare the semi-perimeter method or Half Perimeter Wire Length (HPWL)method.

Using the expected values of spins, the probability of existence of one or more cells of nthnet in pth row and qth column is calculated andapplying HPWL method routing length costis obtained. Different weights for row and column routing length costs could be considered.

If the routing cost is used as the only factor in the cost function, the optimum solution is mapping all cells of the circuit to one location in the layout. This placement willreduce the routing cost to zero but obviously it is not feasible. Hence, a term in the energy function is needed which willpenalize the placements that put more than one cell to the same location. This term is called the overlap cost. This term is calculated by multiplyingthe probabilities of being ith and jth cells in same location.The total energy functionEt, is:

Et= Evrc+ Ehrc+ ϐ × EoE8

whereEvrc, Ehrcand Eo are vertical routing cost, horizontal routing cost and overlap cost respectively.The parameter ϐis balance factor between routing and overlap cost functions.

3.1.2. Half Perimeter Wire Length (HPWL) method

A very simple and widely used cost function parameter is the interconnect wire length of a placement solution; this can be easily approximated using the bounding box method. This wire length estimation method draws a bounding box around all ports in a given net,half the perimeter of this box is taken as the net’s interconnect length approximation. The half perimeter wire length (HPWL) estimation for minimally routed two and three port nets gives an exact value.

3.2. Local relocation using MFA technique

Our method executes local relocation on a model placement where an additional module is added to it for modification with minimum number of displacement.The model placement is a given placement of the circuit that needs modification.MFA based method resolves the problem in less time and hardware in compare to SA-based method. In addition, the runtime of solution is mostly independent of size and complexity of input model placement. Our proposed MFA algorithm is optimized by adding the ability of rotation of modules inside an energy function called permissible distances preservation energythat will be defined at section 3.2.6. This in turn allows more options in moving the engaged modules. Finally, a three-phase cooling process governs convergence of problem variables called neurons or spins.

The relocation problem is formulated as follows:

Input: A model placement including a set of modules and a netlist or hypergraph representation of circuit, the additional module with its coordinates and the incident nets.

Output: Local relocated placement

Objective: Fast relocation with minimum number of displacements and more similarity

Constraint: No overlap between modules and preservation of permissible distances

There are four classified approaches to the problem of inserting an extra module into a model placement.

  1. The additional elements are inserted into unoccupied “whitespace” areas as much as possible.

  2. Before additional logic elements are inserted, an effort is made to predict the amount of whitespace area required; this whitespace is distributed over the chip. If the prediction is accurate (or conservative), the added elements can be placed within the available space.

  3. The third approach is to simply insert or resize the required logic elements, and begin the optimization process from scratch.

  4. The fourth approach is to insert additional logic elements without considering overlaps.

Our approach matched the fourth approach above. The MFA relocation algorithm removes overlaps by moving or rotating modules. Note that all of the movements and rotations must observe some permissible distances that will be explained in the following sections. Feasibility of problem depends on topology of placement and similarity. It is clear that selecting a big part of model placement as the relocation range may cause a feasible solution but causes more unsimilarity.

3.2.1. Local relocation algorithm

The proposed relocation algorithm consists of two stages:

  1. Construction of MFA vectors and calculation of permissible distances from a proper relocation range around additional module.

  2. Local Relocation with MFA

At first stage, given the model placement and an additional module with its coordinates, the small area around the additional module is scanned to find proper range that has enough free space as the local relocation range, then necessary information that will be used at the second stage are extracted.At second stage, MFA algorithm starts to move or rotate some modules (movable modules) considering critical distances criteria using information of first stage.All of theseconcepts like movable modules, permissible distances andcritical distancesare defined at the following sections.

3.2.2. Calculation of permissible distances and construction of MFA vectors

The first stage oflocal relocation algorithm has to extract information of hypergraph representation of selected part of model placement as inputs of second stage, such as P, Q and sets C and N and MFA input vectors.The selected part of model placement is called the local relocation rangeand must has enough free space or dead space for inserting an extra module.

Selecting size and position of relocation rang depends on size of additional module and desirable similarity between model placement and relocated placement. It is clear that selecting bigger part of a model placement as a relocation range may cause more unsimilarity. So, this algorithm seeks around additional module in different directions considering relocation range limitation to find desirable range.

After relocation range determination, its underlying modules are classified into two groups:

First group includes modules that are completely inside the relocation range and are movable modules. Second group consists of modules that just overlap with relocation range and must have fixed position during relocation because they form a frame around movable modulesand are fixed modules.

Actually if we assume the model placement as a puzzle, this frame is just a piece of it. It's clear that after local relocation, this piece must fit on its location again so any movement or rotation from inside modules must preserve vertical and horizontal distances between outer ones. Fig. 3.a shows the relocation range and its underlying modules on the model placement. Fig. 3.b shows local relocated placement of Fig. 3.a.

Dashed square is the relocation range and black module is the additional module. Modules marked as "o" are outer modules and those marked as "i" are inner modules. In our method we have used MFA with discrete variable for relocation, so the problem's configuration must encode to discrete space. As a result, the width and height of relocationrange are divided into equal spans that form some columns and rows respectively. The rows and columns that are occupied with modules are marked. The outer modules are then separated into four sets: up boundary modules, down boundary modules, left boundary modules and right boundary modules.

Figure 3.

a) Relocation range and itsunderlying modules.b) Local relocated placement using MFA

3.2.3. Calculating permissible distances

For each row or column, two modules are determined as its boundary module. Permissible distance of every row or column is obtained with calculating distance between left boundary module and right boundary module of that row or distance between up boundary module and down boundary module of that column respectively. Fig. 4.a shows coordinates of a module. Left-down corner and right-top corners of a module are considerable here. Right-top corner coordinate of module "i" is obtained.

xwi= xi+ wi , yhi= yi+ hiE9

For each row or column, two modules are determined as its boundary modules. Fig. 4.b represents boundary modules of the relocation range shown in Fig. 3.

In Fig. 4.b row and column permissible distances are computed using Eq. 15 considering coordinates of the boundary modules of that row or column. Subscribe "o" Refers to outer modules, Rpdiand Cpdirepresent ith row's jth column's permissible distances.

Rpdi= xoi- xwoi , Cpdi= yoj- yhojE10

Figure 4.

a) Coordinates of a moduleb) Boundary modules

In main algorithm sum of widths or heights of modules that are located in the same row or column are calculated and results are not permitted to exceed permissible distance of that row or column. For decreasing number of variables and calculations, outer modules that must have fixed position are laid aside and just inner modules that are movable enter MFA algorithm. In addition extra module as an overlap maker module enters the algorithm but it stays on its location during algorithm. Some of outer modules that advance inside the inner modules area could enter MFA algorithm to prevent some undesirable locating.

3.2.4. Construction of MFA initial average spin vectors based on the position of movable modules (mapping)

In addition extra module as an overlap maker module enters the algorithm too but it stays on its location during algorithm. Some of outer modules that advance inside the inner modules area could enter MFA algorithm to prevent some undesirable locating. We divided inner modules area to P rows and Q columns. Minimum value between all of the heights and widths of the modules is obtained. Then the width and height of relocation range are divided to this obtained value and rounded to integer values that are number of columns and rows; Q and P. We define position of a module with two vectors at MFA space, one for representing its vertical position and another one for its horizontal position. These vectors have P and Q elements respectively and for module "m" these vectors are shown with vmr andvmc that finally form overall matrices as vrandvc. Every element of above mentioned vectors called spin (neuron) and sum of values of these elements is equal to 1. Left-down corner coordinate of a module determines its position, that means if this point locates in range of ith row and jth column, ith element ofvmrand jth element of vmc is set to 1 and others to 0 as:

(16)

So construct precision vertical and horizontal vectors we used a pseudo-trigonometric method. Module position is determined using its left-down corner distance with left-down corner of relocation range with coordinate as(xrr,yrr).Fig. 5 shows the relocation range of Fig. 3 and its incident inner modules that are darker one. We used a special value to normalize these distances. This value is Euclidean distance between left-down corner of relocation range and a point with coordinate of inner modules maximum "x" and maximum "y" as:

Sd= maxmaxxin-xrr2+maxmaxyin-yrr2E11

Figure 5.

Relocation range and its inner modules for construction of MFA initial average spin vectors

Then for calculating row vector of a module, its vertical distance with left-down corner of relocation range is obtained and then normalized as Eq. 18. Same calculation is done for column vector.

vdi=yi- yrrSd , hdj=xj- xrrSdE12

Eq. 19 represents normalized total horizontal and vertical ranges. Horizontal range is divided into P parts and vertical range into Q parts. The algorithm then determines position of modules based on their vdiand hdjvalues in comparison to P and Q obtained spans.

Horizontal range=minminxin- xrrSd ,maxmaxxin- xrrSdE13
Vertical range=(minminyin- yrrSd ,maxmaxyin- yrrSd )E14

For module "m", being in the ith vertical span causes the ith element of vmr to become 1 and being in the jth horizontal span causes the jth element of vmc to be equal to 1. In MFA space that means probability of finding module "m" at row "i" and column "j" is 1. vrandvc are initial average spin vectors as two inputs of MFA algorithm. Fig. 6 shows the flowchart of first stage of MFA local relocation algorithm.

Figure 6.

The flowchart of first stage of Local relocation

3.2.5. MFA relocation algorithm

At every epoch of MFA Algorithm one of the movable modules is selected randomly for mean field vector calculation from a random select list that includes movable modules with unconverged average spin vectors, and then selected module's average spin vector are updated using this vector. At the end of every epoch spin of every average vector that is greater than “0.9” is set to 1 and others are set to 0 and this vector is deleted from random select list because it has converged.

3.2.6. Energy functions

MFA Algorithm moves modules to minimize a total energy function. Our MFA relocation algorithm's total energy function is summation of three energy functions. First of all is routing cost function or wire length energy that is sum of vertical and horizontal routing costs and the algorithm minimizes it. Second one is the overlap cost and avoids algorithm to locate more than one module in same location. In MFA probability of being a module in row “i” and column “j” in the same location is computed for all of the modules. The energy term is formulated corresponding to the overlap cost as Eq. 7 in cell-placement problem [14]. In Eq. 20, ϧiandϧj are constant values as the weights of modules "i" and "j" and are given from a module weight function that is used to encode the areas of modules. These values are some of input values of the algorithm andϧi for module "i" is related to its area. vipris the probability of finding module "i" in one of the Qlocations at row "p", and vjqc is the probability of finding module "i" in one of the P locations at column "q", respectively.

Last energy function that supervises preserving permissible distances is permissible distances preservation energy orEpd. When a selected module moves to a location, the summation of widths and heights of the modules that are in the same column or row are calculated and are compared to permissible distance of that row and column. If these values exceed the permissible distances first the selected module is rotated and the summation and comparison is done again. Ifthe problem still exists the value ofEpdand total energy increases respectively. In Eq. 21, Et, EwandEo are total energy function, routing cost or wire length energy function and overlap energy function, respectively. α and β are balance factors betweenEw, EoandEpd.α and β are constant during simulation and are used to increase or decrease importance of every energy functions in total energy function related to others.

Figure 7.

The energy function minimization: Et, Ew,Eoand Epd

E15
Et= Ew+ Ϗ×Eo+ ϐ×EpdE16

Fig. 7 shows energy function and its parameters, wire length cost, overlap energy and permissible distances preservation energy. At the final epoch, where all of the spins converge, overlap and permissible distances preservation energies become 0 and wire length cost is minimized, therefore total energy is minimized too.

3.2.7. Cooling Schedule

For local relocation problem the cooling process is realized in three phases, slow cooling followed by fast cooling and then very fast cooling(or quenching).Eq. 22 shows the cooling schedule algorithm.Tr0,Tc0 ,Tr and Tc are horizontal and vertical initial temperatures and horizontal and vertical current temperatures of system, respectively.

Figure 8.

The total energy function minimization for three values oftf: 10, 100, 1000 and 5000

if 0.8×Tr0Tr& 0.8×Tc0Tc:
Tr=0.95×Tr ; Tc=0.95×Tc E17
elseif 0.35×Tr0Tr0.8×Tr0& 0.35×Tc0Tc0.8×Tc0E18
:
Tr=0.8×Tr ; Tc=0.8×Tc E19
elseif 0.35×Tr0Tr& 0.35×Tc0Tc:
Tr=0.65×Tr ; Tc=0.65×Tc E20
endE21

Due to having vertical and horizontal spins two initial temperatures are calculated at the first of algorithm according to vertical and horizontal sizes of problem and a constant factor is called initial temperature factor or tflike Eq. 23.

Tr0tf×P , Tc0tf×QE22

Fig. 8 represents total energy minimization during algorithm iterations for three different values of tfas 10, 100 and 1000.It is clear that changing this factor causes changing number of iterations and also minimum value of total energy function.

On the other hand, setting this factor to insufficient values (specially too high values) may cause unconvergence or unacceptable results, so the range of this factor is limited and according to our experiments is less than 5000.

The cooling process continues until either 90% of the spins are converged or temperature reduces below 1% of initial temperature. So when current temperature is below the 35% of initial temperature, a very fast phase of cooling process moderates the unconverged spins very fast.

At the end of this process, the variable with maximum value in each unconverged spin is set to 1 and all other variables are set to 0.

Fig. 9 shows the flowchart of second stage of MFA local relocation algorithm.

Figure 9.

The flowchart of second stage of MFA local relocation algorithm

3.2.8. Experimental results

We implemented the proposed algorithm on a 2.4GHz Intel Pentium IV with 512MB memory using MATLAB 7.2.0.232 (R2006a) in WINDOWS operating system. We applied the proposed algorithm to the relocation of n300a, n200a, and n100a, which are distributed in GSRC benchmarks in [17].

For every benchmark five different problems were resolved using our proposed algorithm and maximum and average runtime of 10 runs of them are presented in Table 1. Results show that our MFA based algorithm is faster than SA-based proposed method in SA-based relocation method in [18] because the number of displacements is limited to the number of movable modules of problem and the problem is local relocation. Actually relocation range reflects on number of displacements and also similarity of resultantplacement with model placement.

Results show runtimes of our proposed algorithm almost do not depend on the size of benchmark circuit in compare to the method represented in SA-based proposed method, actually size of local relocation range and numbers of movable modules of each problem are the main parameters here. Also feasibility of local relocation solution, to guarantee the similarity of resultant placement with model placement depends on the existence of enough dead space near additional module so that the relocation rage becomes limited and small.

SAMFA Local Relocation
Min. runtime (Sec.)Max. runtime(Sec.)Average runtime (Sec.)Min. runtime (Sec.)Benchmark
1.02.522.372.0n100
9.03.723.623.2n200
60.83.963.923.7n300

Table 1.

MFA Local Relocation results for GSRC benchmarks

Advertisement

4. Conclusion

Briefly, Our proposed method as a local solution method has less displacement and by taking advantages of MFA algorithm in comparison to SA algorithm and localizing problem (that reduces number of engaged modules) and therefore by having less variables, is faster. Also having less number of movable modules causes more similarity if the solution is feasible.

Selection of modules for relocation is based on the range that includes enough free space around the extra module so the runtimes of our proposed algorithm almost do not depend on the size of benchmark circuit in compare to the SA-based method, actually size of local relocation range and numbers of movable modules of each problem are the main parameters. Applying ability of rotation of modules inside a fixed distance controller energy function as permissible distances preservation energy and three phases cooling process are main properties of our employed MFA algorithm. Results show our method is almost independent of size and complexity of model placement.

Although the use of SA provides for escaping from the local minima, it results in an excessive computation time requirement that has hindered experimentation with the Boltzmann machine. In order to overcome this major limitation of the Boltzmann machine, a mean field approximation may be used. In mean field network, the binary state stochastic neurons of the Boltzmann machine are replaced by deterministic analogue neurons. A simple formulation of the Traveling Salesman Problems energy function is described which, in combination with a normalized Hopfield-Tank neural network, eliminates the difficulty in finding valid tours[1]. This technique, as the one of the bases of MFA algorithm, is applicable to many other optimization problems involving n-way decisions (such as VLSI layout and resource allocation) and is easily implemented in a VLSI neural network. The solution quality is shown to be dependent on the formation of elements of the problem configuration which are influenced by the constraint penalties and the temperature as what is borrowed from SA technique.The applied algorithm for local relocation problem is modified form of which is applied for cell placement problem. The cooling schedule has three stages that the final stage is very fast cooling with decreasing factor 0.65 that may be what you mean quenching.Otherwise other two stages with decreasing factors 0.95 and 0.8 are not so fast and have annealing essence.For more information about this topic, one can refer to [1].

References

  1. 1. VandenBout. D. E.MillerT. K.1989Improving the performance of the Hopfield-Tank neural network through normalization and annealing, Biological Cybernetics, 622129139
  2. 2. PetersonC.SoderbergB.1989A new method for mapping optimization problems on to neural networks, International Journal of Neural Systems, 1322
  3. 3. TakahashiY.1997Mathematical improvement of the Hopfield modelfor TSP, feasible solutions by synapse dynamical systems.Neurocomputing, 151543
  4. 4. [4]Gislen. L.PetersonC. .SoderbergB.(19921992Complex scheduling with Potts neural networks," Neural Computation, 4805831
  5. 5. BultanT. .AykanatC.1992A new mapping heuristic based on mean field annealing, Journal of Parallel and Distributed Computing, 16292305
  6. 6. OhlssonM.PetersonC. .SoderbergB.1993Neural networks for optimization problems with inequality constraints- the knapsack problem, Neural Computation, 5331339
  7. 7. OhlssonM.PiH.(19971997A study of the mean field approach to knapsack problems, Neural Networks, 10263271
  8. 8. HokkinenJ.LagerholmM.PetersonC. .SoderbergB.(19981998A Potts neuron approach to communication routing, Neural Computation, 1015871599
  9. 9. HeraultL. .NiezJ.1989Neural networks and graph k-partitioning, Complex Systems, 3531575
  10. 10. VandenBout. D. E.MillerT. K.1990Graph partitioning using annealing neural networks, IEEE Transaction on Neural Networks, 1192203
  11. 11. CimikowskiR. .ShopeP.(19961996A neural-network algorithm for a graph layout problem, IEEE Transactions on Neural Networks, 7341345
  12. 12. YihJ. S. .MazumderP.1990A neural network design for circuit partitioning,IEEE Transactions on Computer-Aided Design, 912651271
  13. 13. BultanT. .AykanatC.1995Circuit partitioning using mean field annealing, Neurocomputing, 8171194
  14. 14. AykanatC.BultanT. .HaritaogluI.1998A fast neural-network algorithm for VLSI cell Placement, Neural Networks, 1116711684
  15. 15. KarimiG. R.AziziVerki. A. .MirzakuchakiS.2010Optimized Local Relocation for VLSI Circuit Modification Using MeanField Annealing, ETRI Journal, 326
  16. 16. HopfieldJ. J.TankD. W.1985Neural” Computation of Decisions in Optimization Problems, Biologica Cybernetics, 52141152
  17. 17. http://vlsicad.eecs.umich.edu/BK/CompaSS
  18. 18. YanagibashiK.TakashimaY.NakamuraY. .December2007A Relocation Method for Circuit Modifications, IEICE TRANS, FUNDAMENTALS, E90-A12

Written By

G.R. Karimi and A. AziziVerki

Submitted: 27 November 2011 Published: 17 October 2012