任意元胞布局问题的一种统计新算法(英文)

A NOVEL STATISTICAL ALGORITHM FOR PLACEMENT OF ARBITRARILY SIZED RECTANGULAR BLOCKS

介绍了一种任意矩形模块布局问题的统计算法,它能同时满足布局的拓扑和几何特性要求.它利用一组约束方程较为准确地描述模块的几何约束,然后定义了罚函数来描述模块的逻辑特性,最后利用统计算法求解所建立的连续方程寻求最好的解,整个算法思想已编程在68000微机上实现,实例的运行结果表明了算法的有效性.

A new analytical algorithm of the placement of arbitrarily sized rec-tangular blocks is presented,which can incorporate both the topological andgeometical characteristics of the placement simultaneously.In the analytical model pro-posed in this paper,a function is defined which reflects the objective function,a set ofconstraints is imposed which represent the requirements of the geometrical characteris-tics.For rectangular block B_i three variables x_i,y_i,α_i are used to describe B'_i s posi-tion and orintation.The objective function is a continuous function with variables x_i,y_i,α_i(i=1, 2,…,n),the constraints can be defined either as inequalities or asequalities of continuoes functions with variables x_i, y_i,α_i(i=1,2,…,n)bymathematical tricks.Thus the placement problem can be viewed as an optimizationproblem by the penalty function method.But the obtaining problem without con-straints has many local optimal solutions,ordinary optimization can't find theoptimal solution.In order to find the general optimal solution,the iterative statisticalmethod is used.This method reduces greatly the computation complexity in contrastto the ordinary statistical method.