Problem projektowania topografii systemów wielkiej skali integracji

Abstract

The aim of this work is to solve the problem of wire length optimization in VLSI systems. In current VLSI systems, delays caused by circuit interconnections have a great impact on the functional properties of circuits. In this work, the method which utilizes the Hopfield network is chosen, for the possibility of hardware realization of this method. Hardware realization of the cell placement could significantly decrease computation time. In this work, a survey of cell placement techniques is presented. The modified Hopfield network cost function for the problem of minimization of the total wire length and auto-feedback of neurons in the Hopfield network are originally used. These modifications enabled a significant improvement on the quality of results obtained. The Hopfield network is originally used for the minimization of the total wire length in a circuit with fixed position pads. In this work, the Hopfield network for the minimization of the total wire length in a circuit with nets containing multiple terminals and also a method for the correction of the wire length estimation in the net are originally used. The Hopfield network was originally used as processing units in parallel placement, which enabled very efficient minimization of the wire length in VLSI circuits. The excellent results of using the Hopfield network for other optimization problems, for example of the travelling salesman problem are presented. The possibilities of the Hopfield network application for VLSI systems topography design are described.

Celem pracy jest rozwiązanie problemu optymalizacji długości połączeń w systemach VLSI. W obecnych systemach VLSI, opóźnienia wnoszone przez połączenia wywierają decydujący wpływ na właściwości funkcjonalne układu. W pracy wybrano metodę wykorzystującą sieć neuronową Hopfielda, ze względu na możliwość sprzętowej realizacji metody. Sprzętowa realizacja rozmieszczania komórek logicznych umożliwiłaby znaczne skrócenie czasu obliczeń. W pracy dokonano przeglądu metod rozmieszczania komórek logicznych. Oryginalnie zmodyfikowano funkcję kosztu sieci Hopfielda dla problemu minimalizacji długości połączeń i wprowadzono autosprzężenia neuronów w sieci Hopfielda. Powyższe modyfikacje umożliwiły znaczną poprawę jakości otrzymywanych rozwiązań. Oryginalnie zastosowano sieć Hopfielda do minimalizacji długości połączeń w układach z ustalonym położeniem końcówek całego układu (padów). W pracy oryginalnie wykorzystano sieć Hopfielda do minimalizacji długości połączeń w układach z węzłami posiadającymi wiele końcówek i opracowano metodę korekcji estymacji długości połączeń w tych układach. Oryginalnie zastosowano sieć Hopfielda jako jednostkę przetwarzającą w systemie równoległego przetwarzania, który umożliwił bardzo skuteczną minimalizację długości połączeń w układach VLSI. Przedstawiono bardzo dobre rezultaty zastosowania zmodyfikowanej sieci Hopfielda w innych problemach optymalizacyjnych, na przykładzie problemu komiwojażera. Opisano możliwości zastosowania sieci Hopfielda podczas projektowania topografii systemów VLSI.