A fast neural-network algorithm for VLSI cell placement
A fast neural-network algorithm for VLSI cell placement
复制标题
用于 VLSI 单元放置的快速神经网络算法
DOI：
10.1016/s0893-6080(98)00089-6
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Ismail Haritaoglu
中科院分区：
文献类型：
--
作者：
C. Aykanat;T. Bultan;Ismail Haritaoglu
单元布局是当前标准单元、门阵列、现场可编程门阵列等VLSI电路设计的重要阶段。虽然模拟退火法(SA)等非确定性算法成功地解决了这一问题，但众所周知，它们的速度很慢。在本文中，提出了一种神经网络算法，它能在相当短的时间内产生与SA一样好的解。该算法基于平均场退火法，已成功地应用于各种组合优化问题。推导了单元布局问题的MFA公式，该公式可以很容易地应用于所有VLSI设计风格。为了证明该算法在实际中的适用性，给出了该算法的详细设计公式，并给出了几种基准电路的版图。通过与采用SA技术的商用自动布局布线软件Xilinx Automatic Place and Routing(APR)的比较，对该算法的性能进行了评估。使用ACM/SIGDA设计自动化基准电路进行性能评估。实验结果表明，提出的MFA算法具有与APR相似的结果。然而，MFA的平均速度几乎是APR的20倍。
Cell placement is an important phase of current VLSI circuit design styles such as standard cell, gate array, and Field Programmable Gate Array (FPGA). Although nondeterministic algorithms such as Simulated Annealing (SA) were successful in solving this problem, they are known to be slow. In this paper, a neural network algorithm is proposed that produces solutions as good as SA in substantially less time. This algorithm is based on Mean Field Annealing (MFA) technique, which was successfully applied to various combinatorial optimization problems. A MFA formulation for the cell placement problem is derived which can easily be applied to all VLSI design styles. To demonstrate that the proposed algorithm is applicable in practice, a detailed formulation for the FPGA design style is derived, and the layouts of several benchmark circuits are generated. The performance of the proposed cell placement algorithm is evaluated in comparison with commercial automated circuit design software Xilinx Automatic Place and Route (APR) which uses SA technique. Performance evaluation is conducted using ACM/SIGDA Design Automation benchmark circuits. Experimental results indicate that the proposed MFA algorithm produces comparable results with APR. However, MFA is almost 20 times faster than APR on the average.