Minimalizacja długości połączeń w układach elektronicznych z wykorzystaniem sieci Hopfielda

• Autorzy: Kos A. , Nagórny Z.

Warianty tytułu

EN

Minimization of the total length of interconnections in electronic circuits by using hopfield net

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono oryginalną metodę rozmieszczania elementów w układzie elektronicznym VLSI z wykorzystaniem sieci neuronowej typu Hopfielda. Celem rozmieszczenia elementów jest zapewnienie minimalnej sumarycznej długości połączeń w układzie. Określono postać funkcji energii, która jest minimalizowana przez sieć. W klasycznym rozwiązaniu wartości wag połączeń między neuronami w sieci są obliczane przed symulacją i nie ulegają zmianie. W niniejszej pracy zbadano wpływ zmian wartości wag podczas symulacji pracy sieci, na otrzymywane rozwiązania. Zauważono, że zmiana wartości wag umożliwia uzyskanie lepszych rozwiązań. Przedstawiono przykłady i wnioski płynące z zastosowania tej metody.

EN

The paper presents a novel method for solving two-dimensional assignment problems in electronic circuits. The method makes use of the Hopfield neural network. The aim of component placement is the minimization of the total length of interconnections in electronic circuits. The method makes use of the Hopfield net with continuous function of neurons according to Eq. (4). An energy function of the neural net is described by Eq. (9). This function consists of three components: the total length of interconnections between components in an electronic circuit and two terms, which make that all components are placed in separate cells of a substrate. Comparing Eq. (9) and Eq. (5), which is a general form of neural net energy function, we get Eqs. (10) and (11) for weight and external input signal values. We force the weight matrix to have zeros on the diagonal according to Eq. (14). The model Hopfield net in electronic components is shown in Figure 3. The Hopfield net is implemented in software in this work, a simulating program makes use of Eq. (21) to calculate the output of each neuron in the net. In conventional method weight values of the net are calculated before simulation and are constant. Our method is a novel method, because the weights are changed during simulation according to the algorithm shown in Figure 4. During the simulation the values of weights are changed in a linear way in accordance with Eq. (22). The speed of weight values changing is defined by a random value. Finally, a number of iterations to achieve a stable state of the net are done. A number of triaIs are performed for each assignment problem and the best results are chosen. Simulations were done for four examples of electronic circuits. The method with weight values changing during simulation gives better results than the conventional one. Results are performed in Table 3. Some conclusions coming from using this method are presented.

Słowa kluczowe

PL

projektowanie topografii układów VLSI; rozmieszczanie elementów; optymalizacja; równoległe przetwarzanie; sieć neuronowa; sieć Hopfielda; funkcja energii

EN

VLSI; assignment problem; cell placement; optimization; paralleI processing; neural network; Hopfield net; energy function

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2005
• Tom: Vol. 51, z. 1
• Strony: 55--72
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Kos A.

• Akademia Górniczo-Hutnicza w Krakowie, Katedra Elektroniki, al. Mickiewicza 30, 30-059 Kraków

autor

Nagórny Z.

• Studium Generalne Sandomiriense, Wyższa Szkoła Humanistyczno-Przyrodnicza w Sandomierzu, ul. Krakowska 26, 27-600 Sandomierz

Bibliografia

• 1. A. Gołda, A. Kos: Experimental verification of energy losses in CMOS gates. Proc, of the 9th International Conference Mixed Design MIXDES 2002, Wroclaw (Poland), June 2002, pp. 375-380.
• 2. A. Gołda, A. Kos: Width of MOSFET channel influence on energy losses and propagation time delay in CMOS circuits. Proc, of the 16th European Conference on Circuits Theory and Design, Kraków (Poland), September 2003, pp. 1-34-37.
• 3. D. S. Rao, J. D. Provence: An integrated approach to routing and via minimization. Information Processing Letters 1991, vol. 39, no. 5, pp. 257-263.
• 4. A . Kos: Modelowanie hybrydowych układów mocy i optymalizacja ich konstrukcji ze względu na rozkład temperatury. Kraków, Wydawnictwa AGH, 1994.
• 5. В. Krishnamurthy: An improved min-cut algorithm for partitioning VLSI networks. IEEE Transactions on Computers 1984, vol. 33, no. 5, pp. 438-446.
• 6. S. Bose, A. R. Saha: Implementation of a heuristic method for standard cell placement. International Journal of Electronics 1993, vol. 74, no. 2, pp. 281-298.
• 7. D. S. Rao, L. M. Patnaik: Circuit layout through an analogy with neural networks. Computer-Aided Design 1992, vol. 24, no. 5, pp. 251-257.
• 8. M. Gajęcki, A. Kos: A problem of optimization of topography of VLSI circuit. Proc, of the XIXth National Conference on Circuit Theory and Electronic Networks, Kraków-Krynica (Poland), October 1996, pp. 11/307-312.
• 9. J.- T. Yan: Fuzzy-clustering-based algorithm for circuit partitioning in standard cell placement. Electronics Letters 1995, vol. 31, no. 3, pp. 151-152.
• 10. P. Bratek, A. Kos: Complex optimisation of topology of VLSI circuits with self-organising neural nets. Proc, of the Mixed Design of Integrated Circuits and Systems, Łódź (Poland), June 1996, pp. 78-83.
• 11. H. Mączka, P. Dziurdzia, А. Kоs: Neural algorithm for minimisation of total length of connections in VLSI circuits. Proc, of the XIXth National Conference on Circuit Theory and Electronic Networks, Kraków-Krynica (Poland), October 1996, pp. II/319-324.
• 12. K. B. Sriram, L. M. Patnaik: Neural network approach for the two-dimensional assignment problem. Electronics Letters 1990, vol. 26, no. 12, pp. 809-810.
• 13. S. P. Eberhardt, T. Daud, D. A. Kerns, T. X. Brown, A. P. Thakoor: Competitive neural architecture for hardware solution to the assignment problem. Neural Networks 1991, vol. 4, pp. 431-442.
• 14. A. Hemani, A. Postula: Cell placement by self-organisation. Neural Networks 1990, vol. 3, pp. 377-383.
• 15. J. Hertz, A. Krogh, R. G. Palmer: Wstęp do teorii obliczeń neuronowych. Warszawa, WNT, 1995.16. L.-Y. Wang, K.-N. Chen, Y.-T. Lai, B.-D. Liu: Neural network on two-dimensional 1C layout compaction. Electronics Letters 1992, vol. 28, no. 14, pp. 1297-1298
• 17. J. J. Hopfield, D. W. Tank: "Neural” computation of decisions in optimization problems. Biological Cybernetics 1985, vol. 52, pp. 141-152.
• 18. R. Tadeusiewicz: Sieci neuronowe. Warszawa, Akademicka Oficyna Wydawnicza, 1993.
• 19. J. Mańdziuk: Sieci neuronowe typu Hopftelda. Teoria i przykłady zastosowań. Warszawa, Akademicka Oficyna Wydawnicza EXIT, 2000.
• 20. J. Żurada, M. Barski, W. Jędruch: Sztuczne sieci neuronowe. Warszawa, Wydawnictwo Naukowe PWN, 1996.
• 21. J. Żurada, M. J. Кang: Computational circuits using neural optimization concept. International Journal of Electronics 1989, vol. 67, no. 3, pp. 311-320.
• 22. J. A. Freeman, D. M. Skapura: Neural networks: algorithms, applications, and programming techniques. Addison-Wesley Publishing Company, 1991.
• 23. T. Khanna: Foundations of neural networks. Addison-Wesley Publishing Company, 1990.
• 24. S. Osowski: Sieci neuronowe w ujęciu algorytmicznym. Warszawa, WNT, 1996.
• 25. R. Tadeusiewicz: Elementarne wprowadzenie do techniki sieci neuronowych z przykładowymi programami. Warszawa, Akademicka Oficyna Wydawnicza PLJ, 1999.