> gRoot Entry F@rVʆvӆCompObjnWordDocumentObjectPool'tVʆ'tVʆ
d
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcfehijklmno~SummaryInformation(
n MirMuhammad Ahmad Imam@F@솼@솼@J&Microsoft Word 6.095>
FMicrosoft Word 6.0 Document
MSWordDocWord.Document.69q_Oh+'0@d
<` designs. Figure 1(a) shows the C:\WORD6\TEMPLATE\NORMAL.DOTNDEVELOPMENTS IN ANALYTICAL TECHNIQUES FOR BUILDING-BLOCK LAYOUT OPTIMIZATIONMustahsaܥe- e0][vbvvvv(v1"$$$*N"&Tzdf"2T"t
A REVIEW OF ANALYTICAL TECHNIQUES FOR BUILDING-BLOCK LAYOUT OPTIMIZATION
Mustahsan Mir and M. Hasan Imam
Faculty of Engineering, Umm Al-Qura University
Makkah, Saudi Arabia
ABSTRACT: Analytical techniques for building-block layout optimization have evolved over the past three decades. Earlier analytical techniques completely ignored the dimensions of the blocks during the optimization process and were therefore able to obtain only a topological layout (relative placement). The next generation techniques did consider the dimensions of the blocks in their formulations but only after modifying their shapes. As a result, the generated layouts were not completely free from overlaps. Current techniques, which are the primary focus of this paper, optimize the layout considering the actual sizes and shapes of the blocks and the optimal layouts generated are free from any overlaps. The primary objective of this paper is to review the developments in analytical techniques for building-block layout design, with particular emphasis on the current generation techniques. It is expected that explanation of the salient features of the latest techniques would help dispel the notion that analytical techniques are too complex to solve large-sized layout problems without resorting to a divide and conquer strategy. Some suggestions for future research are also included.
1. INTRODUCTION
In building-block layout (BBL) design, functional blocks of fixed but arbitrary dimensions are to be placed on a two-dimensional plane such that a particular objective function is minimized subject to a specified set of constraints. The blocks could represent general cells (macro-cells) or ICs, and the typical objectives are minimization of total wire-length or chip area or a combination of both. In addition to the constraint on non-overlapping of blocks, other constraints such as the maximum allowable net delay may also be imposed.
Contrary to many other optimization problems, no general solution is available for this important but complex problem of building-block layout optimization. Numerous heuristic as well as some analytical techniques have been suggested to obtain sub-optimum solutions [1-19]. However, many of the heuristics and most of the earlier genera of some representative analytical techniques which can be applied to building-block layout design. Even though the paper is not intended to be a survey paper, sufficient information about recent analytical techniques for building-block layout design has been provide to give the reader an overall view of these techniques.
2. TYPES OF ANALYTICAL TECHNIQUES
Over the past three decades, there has been a gradual development of analytical techniques for layout optimization. For the purpose of classification, these techniques will be divided into three types depending upon the way the blocks are represented in the mathematical formulations and the strategies adopted for optimization.
2.1. Type-I Techniques
These techniques are characterized by their point-module formulation in which the blocks are represented simply by points. In other words, the dimensions of the blocks are completely ignored during the optimization process. The optimal positions of these point modules are generally determined by using methods based on some physical analogy such as resistive network analogy or by application of Hooks law [5-7]. In [8], analytical methods based on the univariate search and the steepest descent method are used to obtain the optimal placement. The main advantages of techniques belonging to this category are as follows:
Minimal computational cost.
Ease of programming.
Their drawbacks, which outweigh the above advantages, can be summarized as follows:
The presence of some fixed points is essential, otherwise all the points will overlap each other and a trivial solution will be obtained.
Only relative positions of the blocks are optimized.
Significant overlaps may occur when the actual blocks are placed at the optimal positions obtained by the point modules.
Analytical techniques in this category are presently used to obtain an initial placement for many heuristic techniques which require an initial design [9,10]. It may, however, be noted that an initial placement which completely ignores the dimensions of the blocks can be useful for gate-array design and may be utilized for standard-cell placement optimization, but is not very helpful in optimizing building-block layout designs. Figure 1(a) shows the placement at the completion of the optimization process for a simple problem of 6 blocks with 4 pads at fixed positions. When the actual blocks are placed with their centroids positioned at the corresponding points, the resulting layout has considerable overlaps as shown in Figure 1(b).
(a) (b)
Figure 1: Overlapping of blocks in type-I techniques
2.2. Type-II Techniques
These techniques represent significant improvement over type-I techniques. Instead of ignoring the dimensions of the blocks, their shapes are modified in accordance with the optimization strategy. In [11], the blocks are considered to have modified rectangular shapes and a modified Newtons method is used to minimize the objective function based on the total weighted wire length. In [12,13] the blocks are considered to be represented by circles of appropriate radii and techniques based on the quasi-Newton methods (variable metric algorithms) are utilized for optimization. In [14], the Lagrangian differential gradient method is used to solve the layout optimization problem by considering the blocks to be of circular shapes .
The representation of blocks by modified shapes has the drawback that in the converged solutions the actual blocks overlap each other. This problem becomes more severe when many of the blocks have aspect ratios quite different from unity. Figure 2(a) shows an overlap-free optimal placement obtained by representing the blocks with circles. When the actual blocks are replaced with their centroids coinciding with the centers of the corresponding circles, the resulting layout has overlaps as shown in Figure 2(b).
(a) (b)
Figure 2: Overlapping of blocks in a type-II technique
2.3. Type-III Techniques
The analytical techniques which belong to this category incorporate the actual dimensions of the blocks in their mathematical formulations. The optimization process is therefore carried out with the actual blocks and the optimal layouts obtained are free from overlaps. A discussion of some representative techniques in this category is presented in the following.
In [15], mixed integer linear program formulation is used considering the actual dimensions of the blocks. The technique is applicable to both floorplanning and building-block layout design. It has been suggested that, for this approach to be realistic, the number of modules (blocks) must be kept very small (around 10) [1]. For larger size problems a divide and conquer strategy called successive augmentation [15] has been utilized. Using this strategy the blocks are first grouped in a number of subsets. For each subset, a linear program is formulated and a partial solution is obtained. This obviously decreases the probability of getting a final solution near to the global optimum. Furthermore, this approach not only requires a partitioning of the problem into sub-problems, the order in which each sub-problem is solved has an impact on the quality of the final solution.
The analytical technique presented in [16] formulates the general problem of floorplanning as a constrained non-linear optimization problem. The mathematical formulation incorporates the dimensions of rigid (hard) blocks as well as the bounds on the aspect ratios of flexible (soft) blocks. Since in the initial formulation, the number of constraint equations for overlaps was proportional to the square of the number of blocks, a penalty function formulation was used to eliminate these constraint equations. Large-sized problems could therefore be solved without resorting to any divide and conquer strategy. In this technique, optimization is carried out using the method of feasible directions. Starting from a random initial placement in which the blocks are placed far from each other, all the blocks attempt to move simultaneously towards their optimal positions. This has the advantage of not requiring ordering of the blocks but, as described in the following section, it can significantly affect the optimality of the converged solution.
Analytical techniques presented in [17] and [18] also incorporate the actual dimensions of the blocks in their non-linear mathematical formulations. However, instead of resorting to classical methods for optimization such as the steepest descent, modified Newton and quasi-Newton methods, univariate [17] and bivariate [18] search strategies are used for finding the optimal positions of the blocks. A discussion of both these search strategies and their comparison with multivariable optimization procedure of [16] will be presented in the following section. Here, it must be pointed out that the use of such search strategies requires the ordering of blocks. The random initial placement and the ordering of blocks required in these techniques can bias the optimal solutions. However, both these techniques are capable of solving large-sized problems on a personal computer.
Analytic annealing has been suggested in [19] to minimize the impact of both the initial placement and the ordering of blocks for the bivariate technique of [18]. The impact of initial placement is minimized by using controlled convergence and the sensitivity to the ordering is reduced by introducing a dynamic ordering of blocks. The resultant technique is powerful enough to obtain good quality solutions for large-sized problems in a reasonable computer time.
3. SOLUTION STRATEGIES
The building-block placement optimization is a non-linear constrained optimization problem which can be stated in the general form as follows:
Minimize F(X)
subject to gr ( 0 r =1,2,3,........m (1)
where, F is the objective function, X is the set of design variables, and gr are m number of constraints. For the present discussion it is assumed that the above formulation incorporates the geometrical characteristics of the blocks and only feasible designs are generated at every stage of the optimization process. In other words, only type-III techniques are considered.
The objective function F is basically a non-linear function for the problem under discussion. Approximating it with a linear function will allow linear programming formulation, as has been done in [15], but this will be at the expense of the quality of optimal solution. Obviously, it is preferable to solve the above problem as a constrained non-linear optimization problem. For this purpose a number of well-known optimization methods [20] may be considered. It is important to note, however, that application of these methods to building-block layout optimization is not straightforward because the search domain is not only enclosed by the constraint boundaries but it is also segmented by the overlap constraints [17], as shown in Figure 3. With a penalty function formulation the edges of these segments represent points of discontinuity at which derivatives cannot be calculated analytically. To overcome this problem, reference [16] has utilized the finite difference to calculate the derivatives. Depending upon the signs of forward and backward differences, the points of discontinuity were identified. However, it was not possible to jump over the constraint segments to find the minimum. Another problem with the multivariable approach considered in [16] is that when a move is made, all the blocks move simultaneously but independently of each other. This causes unpredictable overlaps for a given step size, which must be reduced until there are no overlaps.
Figure 3: Overlap constraint segments in 1-D search domain
The above limitations were overcome by the search algorithm presented in [17]. Based on the univariate search, a single block is moved at a time either along the x- or y-axes. This allows the moving block to jump over the constraint segments and obtain its optimal position with respect to the current placement of all other blocks. Further improvements in the search procedure were made in [18] which introduced the bivariate formulation for building-block layout optimization. Once again, a single block was moved at a time, but its direction of movement was along the line of steepest descent, which corresponds to the direction of maximum rate of reduction of the objective function. This resulted in significant improvement in the quality of optimal solutions.
4. COMPARISON
Having classified various analytical techniques into three main types depending upon their mathematical formulation of the problem, a qualitative as well as a quantitative comparison is now presented. On the basis of these comparisons, some general conclusions are drawn about recent analytical techniques for building-block layout optimization.
4.1 Qualitative Comparison
A comparison of the main features of the three types of analytical techniques is presented in Table I. It is obvious from this table that type-III techniques are better than the other two types for automated layout optimization of building blocks.
Table I: Comparison of the three types of analytical techniques
No.FeatureTechnique
Type-I Type-II Type-III1Modeling of geometrical characteristics of blocks in mathematical formulation.Ignored Modified Exact 2Fixed points required for a non-trivial solution.Yes No No3Overlapping of blocks in optimal layout designs.Extensive Noticeable None4Computational cost.Minimal High Average5Quality of optimal solution.Poor Fair Best
4.2 Quantitative Comparison
Since type-III techniques are better than the other two types, a quantitative comparison of various techniques in this category is presented in the following for a test problem taken from [17]. The purpose of presenting this comparison is to demonstrate that, even for the same category of classification, the solution quality is significantly dependent upon the solution strategy adopted in a particular technique. Four different solution strategies are considered. The computer program POP [16] is based on a multivariable approach and uses one of the well-known software packages for non-linear optimization. The computer programs TOPOPT [17] and BITOPT [18], on the other hand, are based on the univariate and bivariate nonlinear programming, respectively. The AA [19] program utilizes the concept of analytic annealing during the optimization process which is based on a bivariate formulation of the problem.
The results for the test problem are summarized in Table II. The objective function to be minimized is the weighted sum of squared Euclidean distances between the centroids of the blocks. It is clear from the results presented in this Table that the solution strategy significantly affects the performance of a technique in Type-III category. Among the four different techniques considered for comparison, the analytic annealing technique has the best performance.
Table II: Comparison of results for the test problem
Computer ProgramBest value of Objective FunctionMean value of Objective FunctionStandard DeviationPOP [16]897.141158.92240.11TOPOPT [17]801.971081.17168.34BITOPT [18]792.43857.5546.49AA [19]706.15738.3319.96
5. FURTHER DEVELOPMENTS
The type-III analytical techniques incorporate the geometrical characteristics of the blocks in their mathematical formulations which need not be linearized for optimization. Also, the search strategy based on bivariate formulation with analytic annealing is quite powerful in circumventing many of the search-related problems when the actual dimensions of the blocks are considered during the optimization process. However, further improvements are needed in the mathematical formulation of the current analytical techniques to incorporate constraints other than the geometrical constraints. For instance, due to the importance of interconnect delays in VLSI design [21], path delay constraints need to be included in the mathematical formulation of these techniques without unduly increasing the computational time. One possibility is to use a penalty function approach similar to that used for the overlapping of blocks. However, for analytical techniques in which the blocks are initially scattered far from each other, imposition of such constraints using a penalty function is not straight forward and requires further research work. Also, for analytical techniques in which a single block is moved at a time, further research is needed for determining an improved ordering criterion. Finally, it appears that the quality of solutions can be improved by developing hybrid techniques which integrate the desirable features of both analytical and heuristic techniques for building-block layout designs.
6. CONCLUSIONS
A review of many representative analytical techniques developed over the past three decades for building-block layout design has been presented. Limitations of earlier analytical techniques and salient features of some recently developed analytical techniques are described. A comparison of various solution strategies adopted for solving the layout optimization problem is given. It is shown that the latest analytical techniques, which incorporate the actual dimensions of blocks in their mathematical formulations, are capable of solving large-sized problems without requiring any linearization and without resorting to any divide and conquer strategy. Furthermore, the impact of initial placement and the ordering of blocks on the optimized layouts can be minimized by the use of analytic annealing.
Although the current analytical techniques are quite powerful for solving large-sized problems on a personal computer, further developments are needed so that their mathematical formulations take into account all other constraints imposed by most heuristic techniques for building-block layout design. In this regard, some guidelines are suggested for future work in this area.
REFERENCES
[1] S. M. Sait and H. Youssef, VLSI Physical Design Automation: Theory and Practice, McGraw-Hill Book Company, Europe (also co-published by IEEE Press), 1995.
[2] E.S. Kuh and T. Ohtsuki, Recent Advances in VLSI Layout, Proceedings of IEEE, Vol. 78, No. 2, pp. 237-263, 1990.
[3] T.C. Hu and E.S. Kuh (Eds.), VLSI Circuit Layout: Theory and Design, IEEE Press, New York, 1985.
[4] M. Hannan and J.M. Kurtzberg, Placement Techniques in Design Automation of Digital Systems: Theory and Techniques, Ed. M.A. Breur, Prentice-Hall, New York, 1972.
[5] N.R. Quinn and M.A. Breur, A Force Directed Component Placement Procedure for Printed Circuit Boards, IEEE Trans. Circuits & Syst., Vol. 26, No. 6, pp. 377-388, 1979.
[6] K. Ueda, H. Kitazawa and I.Harada, CHAMP: Chip Floorplan for Hierarchical VLSI Layout Design, IEEE Trans. On CAD, Vol. 4, No. 1, pp. 12-22, 1985.
[7] C.K. Cheng and E.S. Kuh, Module Placement Based on Resistive Network Optimization, IEEE Trans. On CAD, Vol. 3, pp. 218-225, 1984.
[8] Z. Drezner and G.O. Wesolowsky, Layout of Facilities with some Fixed Points, J. Comput. Ops. Res., Vol. 12, No. 6, pp. 603-610, 1985.
[9]H. Youssef, S. M. Sait and K. J. Al-Farra, Timing Influenced Force Directed Floorplanning, Proceedings of the EURO-DAC 95, pp. 156-161, 1995.
[10] N. Yonezawa, N. Nishiguchi and A. Etani, A VLSI Floorplanner Based on Balloon Expansion, Proceedings of the European Design Automation Conference, pp. 257-261, 1990.
[11] L. Sha and R.W. Dutton, An Analytical Algorithm for Placement of Arbitrarily Sized Rectangular Blocks, Proc. 22nd Design Automation Conf., pp. 602-608, 1985.
[12] A. Alon and U. Ascher, Model and Solution Strategy for Placement of Rectangular Blocks in the Euclidean Plane, IEEE Trans. On CAD, Vol. 7, No. 3, pp. 378-386, 1988.
[13] C.S. Ying and J.S. Wong, An Analytical Approach to Floorplanning for Hierarchical Building Block Layout, IEEE Trans. On CAD, Vol. 8, No. 4, pp. 403-412, 1989.
[14] Z. Drezner, A New Method for the Layout Problem, J. Opns Res., Vol. 28, pp. 1375-1384, 1980.
[15] S. Sutanthavibul, E. Shragowitz and J.B. Rosen, An Analytical Approach to Floorplanning Design and Optimization, IEEE Trans. CAD, Vol. 10, No. 6, pp. 761-769, 1991.
[16] M. Mir and M. H. Imam, Optimal Placement for Hierarchical VLSI Layout Design, J. Microproc. & Microprog., Vol. 25, pp. 177-182, 1989.
[17] M. H. Imam and M. Mir, Nonlinear Programming Approach to Automated Topology Optimization, Comput.-Aided Des., Vol. 21, No. 2, pp. 107-115, 1989.
[18] M. Mir and M. H. Imam, Topology Optimization of Arbitrary-Size Blocks using a Bivariate Formulation, Comput.-Aided Des., Vol. 24, No. 10, pp. 556-564, 1992.
[19] M. Mir and M. H. Imam, Analytic Annealing for Macrocell Placement Optimization, Computers & Elect. Engng, Vol. 22, No. 2, pp.169-177, 1996.
[20] D.G. Leunberger, Introduction to Linear and Non-linear Programming, Addison-Wesley, Reading, Mass., 1973.
[21] S.M. Sait, H. Youssef, K. Nassar, M.S.T. Benten, Timing Driven Genetic Algorithm for Standard-cell Placement, Proceedings of the IEEE 14th Annual Int. Phoenix Conference on Computers and Communications, pp. 403-409, 1995.
.A inN
:/c"4:;8 n[6au69a--9n-%+ +%+% % %+%++ %$$%$%%$%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%R=%=K%B=%=9%0=%=(%$=%=0%9=%=B%K=%=R%V=%=V%=$%(=% 0>%>9%9C%C>%>S%V>%>"V%+S>%>2L%6C>%>+*%"&>%>&%*>%> L%>69%20>%
'
%
%
%
%
%
%
%
%
%
'%
+
%
+%
%
%
%
%D%DD%D%%%%%%
%
%
%
%
%
$
%$
$
%$
%
%
%
%
%
%
%
%
%
%$%$$D%$DD%D%#%%%%D%%D#D%#D#%7*V0V%0V0D%0D7*D%7*D7*V%7*2%22+%2+7*+%7*+7*%+'%''
%'
+
%+
+%+%+P%+Pu&P%u&Pu&%%u&%+%%.p3%p3p3 %p3 . %. .%617%1717D%17D6D%6D6%66%617%1717%176%88 88%88#%## %# #%#88%8888 %%#%##%#%%%%' N":.c7;:8<> 22X6--K6-%7y7%7%y% 4%4c%c%%j%jU3
%U3
Cl
%Cl
5
%5
+
%+
%%%#U%#U%%%+%+5%5C>%C>Uw%Uwj%j%%H%Hv%v % 6 %6 b %b % 7% 7 U% U+
n%+
na
%a
%
%
%
H%H%%%3%3l%l%n%n
U%
UC
7%C
7v
%v
%
%
%
!v%!vEH%EHe%e%%w%w>%>%%%U%U%
%
%
l
%l
3
%3
%%e%eEc%Ec!4%!4
%
%
%
v
%v
C
s%C
s
V%
V<%<'%'l%l3%3
%
%
%
H
%H
%
%
%
a
'%a
'+
<%+
< V% V s% s % b %b 6 %6 %%&
%&
X[
%X[
4
%4
%
%=%=z%z%%8%8y%y%%;%;{%{%%6%6r%r%4%4X%XM%M}%}%
%
=%=s"%s"C%Cb%b {% {]%]%%%\%\%%%^%^%%{%{Ub%UbC%C"%"%0%0`%`}%}M%M%%'%'Dr%Dr^6%^6t%t%{%{;%;%%y%y8%8%%tz%tz^=%^=D%D'
%'
%
[
%[
&
%&
%`%`0%0u%uQ%Q0%0U%U%%%^%^%%%\%\%%%]%] % %0%0sQ%sQ=u%=u
%
%v~%v~FW%FW4%4%%s%s9%9
%
%
%
I
%I
%
%%V%V%%%n%n8%84%4
W%
W
~%
~v
%v
L
%L
%
%%
6%
6 k% k % % % L% Lv %v l %l f %f d >%d >f |%f |l %l v %v 1% 1 k% k % % %
F%
F%
y%%
yL
%L
v
%v
%
&%
&I%I8i%8in%n%%%V%V%%
%
I
%I
%
%
%
9%9s%s%i%iI%IF&%F&v%v%%y%yF%F7%7T%Tm%mk%k1%1%%|%|>%>%%%L%L%m%mT%T7k%7k6%6%%%y$$%$$%$%3%%38%P%8%Pl%i%l%i%%%%%%%%&&%&6'%6'p'%p''%''%'(i%(iL(P%L(Pn(<%)4)%4)Z)t%Z)t})E%})E)%))%))%))v%)v)>%)>)4%)6)u%)u)%))%)),%)6)%))%)*~%*~ *P%*W*%**
%*
*
%*
)p
%)p
)8
%)8
)
%)
)%))%))%)(%((%((|%(|L(_%L(_(E%(E'0%'0'%''%&
&%&N&%N&&%&%%%%0%%0l%E%l%E8%_%8%_%r%e$P$%P$*$;%*$;$i%$i#%##%##
%#
#8
%#8
#p
%#p
#z
%i#Wk#%k#q#%q#{#%{##>%#>#v%#v#%##%##%e$y$%G&&/%&/%T%%T%{%%{%%%W%%W%/%%/%%6%%6%;%$$%$$Q%$Q}$%}$s$%s$m$%m$k$F%k$Fm$%m$r$%$$%$$%$$#%$#%X%%X/%%/%W%%W%%%%%%G&~&%~&&%&&%&,'%,'i'%i''%''%''%((%()%)T)%T))%))%))%)3*^%3*^[*B%*+%+:+X%:+X[+#%[+#x+%x++%++y%+y+=%+=+"%+F+%++%++%++Q%+Q+%++%+x+%x+u+%+7
,M%
,MF,h%F,h,%,,%,,%,6-%6-t-%t--%--%..%..%.&/%&/b/%b//h%/h/M%/M0-%0-?0%?0]0%
1O$15%$15I1%I1k1%k11%11_%1_1$%1$1%11%11%21u%1u16%161%11%11~%1~1C%1C1 %1 1
%
1
0
%0
0%00%0s0%s0?0\%?0\0:%0:/%//%//%.o.%o./.%/.-%--%-t-%t-6-%6-,%,,%+/+:%+:+\%+\p+%p+@+%@++%+*
%*
*2
%*2
*e
%*e
*y
% *$*$%$*$=*_%=*_Y*%Y*x*%x**%**5%*5*e%*e+%+(+%**{%*{f*T%f*T3*/%3*/)%))%))%((%(a(%a("(%"('%''%'i'%i','%,''%**%**%=*=*m %=*m B#m %B#m B#%B#=*%q)
2
%2
2}%2}q)}%q)}q)
%i-Ii- %i- " %" "I%"Ii-I%W5 % y% y 0% 0W50%W50W5y%W5yW5%7y70%700%0y'SI=:0cA&;;8e%NN "#4<#4%9--%9-% - !% !
8!%-& %&&%*'*'(%'i'%(c(o%'/}%..;%b.b.*%--b%--%-{-%,,%B,B,%+B+5%i+i+%*i*\%**%"*"*%)O+%+T-%T->/%>/F1l%010%0)
%"*
"*
%*x *R%**%;+2%22%52q52%11%\1\1\%0E0
%0\
0%/k/%/L/N/O/Q/R/S/`/g/i/j///////66I:W:;;=$=&=`=b=U?X?t?EzEEFKLPPPQQRlRRDS`SSSwTTTUVcbUbcUbUbcuDcJhchcuDguDP]]UccUUcOUUU'V_VVWWW7XIXXXIYXYYYmZZ[$[[[[#\0]defghij
cuVcc3d~
DEg<Xnp#Pp#Pp#Pp# p#p#p# p#p#p#p# p# p# p# p#
p# p# p# p# p# p# p# p# p# "
<4.#
x<4.mn7hxxnMG0 1 J !!*%+%D)p# p# p# p# p# p# p#p# p# p# p# p# p# p# p#
p# p# p# p# p# p#
p# p# p# <<"
x4.#
xx4.xD)E),,...,/-/?//)1*16666?7@7H7H:I:W:;;;<<<===%=a=b=p#
p# p# p# p# p# p# p# p#Pp#Pp# p# p# p# p# p#}p# p# p# p# p# p# p# p# p# p# p# p# p# PpP+P++l("IJIIIIIIIIIJx"Root Entry F@rVʆ>dӆuCompObjnWordDocumentvObjectPool'tVʆ'tVʆ
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcrtwxyz{|}SummaryInformation(
n MirMuhammad Ahmad Imam@F@憼@lu솼@G&Microsoft Word 6.094>
FMicrosoft Word 6.0 Document
MSWordDocWord.Document.69q_Oh+'0@d
<` designs. Figure 1(a) shows the C:\WORD6\TEMPLATE\NORMAL.DOTNDEVELOPMENTS IN ANALYTICAL TECHNIQUES FOR BUILDING-BLOCK LAYOUT OPTIMIZATIONMustahsaܥe- e0][p\pppp(p1*HT\df2Tt
A REVIEW OF ANALYTICAL TECHNIQUES FOR BUILDING-BLOCK LAYOUT OPTIMIZATION
Mustahsan Mir and M. Hasan Imam
Faculty of Engineering, Umm Al-Qura University
Makkah, Saudi Arabia
ABSTRACT: Analytical techniques for building-block layout optimization have evolved over the past three decades. Earlier analytical techniques completely ignored the dimensions of the blocks during the optimization process and were therefore able to obtain only a topological layout (relative placement). The next generation techniques did consider the dimensions of the blocks in their formulations but only after modifying their shapes. As a result, the generated layouts were not completely free from overlaps. Current techniques, which are the primary focus of this paper, optimize the layout considering the actual sizes and shapes of the blocks and the optimal layouts generated are free from any overlaps. The primary objective of this paper is to review the developments in analytical techniques for building-block layout design, with particular emphasis on the current generation techniques. It is expected that explanation of the salient features of the latest techniques would help dispel the notion that analytical techniques are too complex to solve large-sized layout problems without resorting to a divide and conquer strategy. Some suggestions for future research are also included.
1. INTRODUCTION
In building-block layout (BBL) design, functional blocks of fixed but arbitrary dimensions are to be placed on a two-dimensional plane such that a particular objective function is minimized subject to a specified set of constraints. The blocks could represent general cells (macro-cells) or ICs, and the typical objectives are minimization of total wire-length or chip area or a combination of both. In addition to the constraint on non-overlapping of blocks, other constraints such as the maximum allowable net delay may also be imposed.
Contrary to many other optimization problems, no general solution is available for this important but complex problem of building-block layout optimization. Numerous heuristic as well as some analytical techniques have been suggested to obtain sub-optimum solutions [1-19]. However, many of the heuristics and most of the earlier generation analytical techniques are primarily developed for a special class of this problem involving blocks (cells) of the same size to be placed on a 2-D grid. Even this simplified problem is known to be np-hard. The building-block layout optimization on a continuous 2-D plane is a more difficult problem because the sites are not predetermined and the blocks must search for their optimal positions in the entire plane avoiding overlaps with each other.
Recent analytical techniques appear to be quite promising for solving large-sized building-block layout problems on a PC. However, unlike heuristic techniques, the analytical techniques have not yet been well established for practical building-block layout design. In fact, there is hardly any published work which evaluates various analytical techniques, giving a detailed account of methodologies adopted by these techniques and comparing their advantages and limitations. It is the objective of this paper to compare mathematical formulations and solution strategiesb=d===== >U>V>X>>>>>>>???T?U?W?X?t? C
CDDE$EEEfE p + + p + + p + + p + + p + + p# p# p#
p# p# p# p# p# xl("JIIIIIIIJl("JIIIIJfEyEzEEEEEEEEEEEEEEEEEEEEEEEFKKL-O.OPPPTQQ0RRSTT p# p# p# p# p# p# p# p# p# p# p# p#p#p#p#p#p#p#l
,9!(T2UUtVWWmXX}YZZH[[K\0]efhijp#p#p#p#p#p#p#p#p#p#p#p#p#p#p#
p# p# p# p# p# p#Pp# p# <K$@$Normala bc8@8 Heading 1hx
U[]ck(@( Heading 2U]c&@& Heading 3U]"A@"Default Paragraph Fontost-processing is therefore needed at the completion of the optimization process to remove these overlaps.
.A
for ten trial runs starting with different initial layouts its It not only attained the minimum value of the objective function, its mean value of the objective function for ten trial runs has a value smaller than the best values obtained by the other three programs.tComputer program AA based on this techniquedesign[j!!!!!! 2F-7CP[z5wd~DE<Xnef~K\" ,
,,,,,..44447`:a:::::::K;;;;;; <O<Q<f<<<<<@@CCCCD,D5Dm m >m m 2r UVbpJJJJIII
IIIJJI>m m J>m m 2r EUVbp>m m >m m 2r UVbpJJJJII
IIIJJ>m m >m m 2r UVbpJJJJII
IIIJJ>m m >m m 2r UVbpJJJJIII
IIIJJ>m m >m m 2r cddef}~,-,,-*-447:::::::::;;;;N<O<<<<<@AAAAAAABBBBBBBBCCCC+D,DKDLDnDoDDDDDYOZO[O[[cddefbg/ 0 >//h6I:====$= %=`= a=
b= == U>V> >> >? T?U?FCC>DD1DaD
DEyEzEEEEEEEEEiPP/]1Times New RomanSymbol&Arial"hdfdf_MDEVELOPMENTS IN ANALYTICAL TECHNIQUES FOR BUILDING-BLOCK LAYOUT OPTIMIZATION
Mustahsan MirMuhammad Ahmad Imamx