基于最短长链接优先选择的VLSI阵列重构算法

Reconstruction algorithm for VLSI array with the priority selection of theshortest long interconnect

为了提高超大规模集成逻辑阵列的重构效率,提出一种基于最短长链接优先选择原则的改进算法。该算法从阵列2端分别构建逻辑列,直到2条逻辑列相交,则停止构建逻辑列。在2条相交逻辑列作为边界的局部区域内,以从上到下的方式寻找每行长链接最短的处理器单元,所选取的处理单元用于构建局部最优的逻辑列。基于上述操作,利用分治思想,将新获得的逻辑列作为新的局部区域的边界,依次迭代获得新的局部最优逻辑列。最后,将所得到的局部最优逻辑列连接起来,即可获得最终的目标阵列。通过与现有的重构算法的比较分析,验证了算法的高效性。仿真结果表明,在保证逻辑阵列规模不变的条件下,相较于现有的重构算法,该算法能够有效减少阵列重构过程中处理器的访问数,并能在一定程度上降低重构的运行时间,提高逻辑阵列的重构效率。

In order to improve the reconstruction efficiency of the very large-scale integrated logic array,an improved algorithm based on the principle of first selecting the shortest and long interconnect is proposed.This improved algorithm constructs logical columns from both ends of the array until the two logical columns intersect,then stops constructing logical columns.In the local area with two intersecting logical columns as the boundary,the processor unit with the shortest link length of each row is searched from top to bottom,and the selected processing unit is used to construct the locally optimal logical column.Based on the above operations,using the idea of divide and conquer,the newly obtained logical column is used as the boundary of the new local area,and the new local optimal logical column is obtained in turn.Finally,connect the obtained local optimal logical columns to obtain the final target array.Through comparison and analysis with existing reconstruction algorithms,the efficiency of the proposed algorithm is verified.The final simulation results show that under the condition that the scale of the logic array remains unchanged,compared with the existing reconstruction algorithm,this improved algorithm can effectively reduce the number of processor accesses during the array reconstruction process,and to a certain extent,the running time of the reconstruction is reduced,and the reconstruction efficiency of the logic array is improved.