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

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

作　　者：王昊[1,2,3] 刘臻[1,2,3] 王剑[1,2,4] 章隆兵[1,2,4] 

机构地区：[1]计算机体系结构国家重点实验室(中国科学院计算技术研究所),北京100190 [2]中国科学院计算技术研究所,北京100190 [3]中国科学院大学,北京100049 [4]龙芯中科技术有限公司,北京100095

出　　处：《高技术通讯》2017年第1期1-8,共8页Chinese High Technology Letters

基　　金：国家"核高基"科技重大专项课题(2014ZX01020201;2014ZX01030101);国家自然科学基金(61432016);863计划(2013AA014301)资助项目

摘　　要：针对触发器聚类的布局问题,提出了一种基于蒙特卡洛方法的触发器聚类布局算法。该方法的核心思想为设计合理的评分函数,并通过蒙特卡洛方法模拟触发器聚类在版图上的随机游走过程,获取样本,再通过评分函数评价样本质量,逐步地在可行域中搜索最优解。实验结果表明,相较于现有的方法,该方法在总线长与时序性能两方面,分别得到平均约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.

关 键 词：触发器聚类 布局 蒙特卡洛方法 层次化设计方法 

分 类 号：TN40[电子电信—微电子学与固体电子学] TP301.6[自动化与计算机技术—计算机系统结构]