Global tracing method of the matrix large integrated circuits

Аuthors

Nazarov A. V.

e-mail: rat-rut@yandex.ru

Abstract

Goal: It is known that the quality of the final stage of matrix large-scale integrated circuits (LSI) design automation (the local routing stage) is determined by the efficiency of forming the large integrated circuits channels netlist generated in the preliminary stage of global tracing. While the problems of local tracing are covered sufficiently by publications, the problems of LSIs global tracing are insufficiently covered. The existing publications on this matter are devoted primarily to multilayered LSIs tracing. The paper proposes LSI global tracing with essentially limited pathways.

Design/Methodology/Approach. The paper presents the algorithm of the first phase of the creating conductors of a matrix LSI — the phase of global conductors tracing. This phase increases the efficiency of the successive stage of the tracing — the layout of interconnections of channels. The proposed algorithm is based on the Bellman-Kalaba method, which had been modified by introducing a system of penalties. This system of penalties allows taking into account the essntially limited resources for conductors tracing of the LSIs in the process of their synthesis.

Conclusions. According to the proposed method computer-based algorithm for LSI conductors tracing was developed. The paper presents the detailed description of the algorithm. Besides, it describes a system of penalties imposed on the new tracks, which take into account the previously created connections. This system of penalties is presented by formulas. The efficiency of the proposed algorithm is illustrated by the concrete example.

Practical implication. The algorithm implementation leads to reduction and balancing of separate channels loads. And, as consequence, tracing resources of the selected type of LSI are employed more efficiently.

Originality/Value. According to studies the suggested algorithm allows reducing the total area occupied by the LSI conductors approximately by 20–25 percent.

Keywords:

tracing, global tracing, design automation, gate array, algorithm, penalty function

References

1. Gerasimov I.V., Kuz’min S.A., Lozovoi L.N., Nikitin A.V. Osnovy tekhnologii komplementarnogo proektirovaniya naukoemkikh izdelii (Basics technology design of high-tech products), 2010, Sankt-Peterburg, Izd-vo LETI, 196 p.

2. Glushko A.A., Rodionov I.A., Makarchuk V.V. Tekhnologiya i konstruirovanie v elektronnoi apparature, 2007, no. 4, pp. 32-34.

3. Muroga S. Sistemnoe proektirovanie sverkhbol’shikh integral’nykh skhem (System design of VLSI), Moscow, Mir, 1985, 547 p.

4. Lebedev B.K., Lebedev V.B. Izvestiya Yuzhnogo federal’nogo universiteta, 2010, no. 7, pp. 32-39.

5. Voronin E.I. Razrabotka i issledovanie metodov resheniya zadachi mnogo-sloinoi global’noi trassirovki SBIS na osnove modelei adaptivnogo povedeniya prirodnykh sistem (Development and research of methods of solving the problem of global multi-layer trace VLSI based on models of adaptive behavior of natural systems), Doctor’s tchesis, Taganrog, 2012, 142 p.

6. R. Bellman. On a Routing Problem. Quarterly of Applied Mathematics, 1958, vol. 16, no. 1, pp. 87-90.

Download