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

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.