结群算法中多目标形状的产生方法

A Method of Clustering With Multiple Target Shapes

本文提出了在结群算法中引入多目标形状的算法(Clustering With Multiple Target Shapes—CWMTS)以及它对解决积木块布局(BBL,Bunding Block Layout)问题所作的贡献,指出如何选取多目标形状和减轻算法的复杂度的重要性。文章最后采用美国提供的BBL测试模型,工业界选的实例以及我们自己所用的例子对CWMTS进行了实测并和U.C.Berkeley的BEAR系统进行了比较。结果表明,CWMTS不仅减少了布局面积和连线总长,同时还缩短了处理时间。

In this paper, we present a new method of clustering with multiple target shapes-CWMTS, which is used in floorplanning and placement for building block layout ( BBL ) . The necessity of the multiple target shapes is explained.The simplification of the algorithm complexity is discussed. Several examples. from industrials and our example are tested in the System. The area of placement, the total lengths of wires and the running time are reduced significantly in comparison with the BEAR system whith is developed by U.C. Berkeley.