基于蒙特卡洛方法的触发器聚类布局算法

An algorithm for register cluster placement based on the Monte Carlo method

针对触发器聚类的布局问题,提出了一种基于蒙特卡洛方法的触发器聚类布局算法。该方法的核心思想为设计合理的评分函数,并通过蒙特卡洛方法模拟触发器聚类在版图上的随机游走过程,获取样本,再通过评分函数评价样本质量,逐步地在可行域中搜索最优解。实验结果表明,相较于现有的方法,该方法在总线长与时序性能两方面,分别得到平均约9%与17%的改善与提升。此外,该方法具有较强的健壮性,适用于复杂度较高或者版图利用率较高的设计,并能够快速收敛,以较小的时间代价完成优化。

This study focused on the placement of register clusters, and proposed a novel placement algorithm based on the Monte Carlo method. The main idea of the algorithm is to simulate the random walking process of register clusers, use a reasonable scoring function to evaluate the quality of the samples gained by the Monte Carlo method, and eventually search for the optimal solution in the feasible region. Experiments prove that, compared to the exist ing approach, this algorithm can achieve about 9% and 17% improvement in the total wire length and the timing performance respectively. This algorithm is robust, and fits for the designs with the high complexity or high utiliza- tion ratio of layout. In addition it converges fast, and achieves the optimization at a low cost of time.