Wyniki wyszukiwania - BazTech

1

Accuracy influence of the hardware implementation of the Hopfield network on the solution quality for the travelling salesman problem

Nagórny Z.

Journal of Applied Computer Science

|

2012

|

Vol. 20, nr 1

51-67

EN

The objective of this work was to study the accuracy influence of the hardware implementation of the Hopfield network on the solution quality for the travelling salesman problem. In this work the 8-bit accuracy influence of the hardware implementation of weights, activation functions, and external input signals on the quality of achieved solutions for 100 randomly generated instances of the 10-city TSP was studied and comparable results in comparison with the simulation in which the network was simulated using double precision floating point numbers were obtained. The results show that the hardware implementation of the Hopfield network with the 8-bit accuracy allows to obtain satisfactory solutions for the TSP. It should be also noted that the network described in this work utilizes the novel method of auto-tuning of Hopfield network parameters and thanks to this method, in contrast to other works, none of the network parameters is tuned for a given solved TSP on the basis of preliminary simulations. The Hopfield network presented in this work is destined for the hardware implementation. The application of the hardware implementation of the network could significantly decrease the time required to obtain the combinatorial problem solution in comparison with methods using von Neumann architecture computers.

2

Projektowanie topografii systemów VLSI. Cz. 4. Symulowane wyżarzanie, sieci neuronowe

Nagórny Z., Kos A.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 4

697-727

PL

Niniejsza praca jest czwartą, ostatnią częścią przeglądu metod rozmieszczania modułów, stosowanych podczas projektowania topografii układów VLSI. Modułem jest fragment systemu wyodrębniony ze względu na pełnioną funkcję. Praca jest poświęcona algorytmowi symulowanego wyżarzania oraz sieciom neuronowych. Przedstawiono dokładny opis algorytmu symulowanego wyżarzania oraz sposób zastosowania algorytmu do rozmieszczania modułów. Programy wykorzystujące algorytm symulowanego wyżarzania zostały szczegółowo opisane. W tym celu scharakteryzowano następujące programy rozmieszczania: TimberWolf, MGP, MPG-MS, VPR. Następnie, opisano sposób zastosowania sieci samoorganizującej się oraz sieci Hopfielda w optymalizacji topografii układów VLSI. Przedstawiono rezultaty rozmieszczania modułów otrzymane z użyciem sieci Hopfielda. Następnie, scharakteryzowano inne metody stosowane podczas rozmieszczania modułów: algorytmy genetyczne, strategie ewolucyjne, schemat rozmieszczanie-planowanie topografii-rozmieszczanie, programy dla układów 3D VLSI oraz sprzętowe metody rozwiązania problemu rozmieszczania modułów. Porównano metody rozmieszczania modułów przedstawione w przeglądzie.

EN

The design process of the VLSI circuits requires the use of computer aided design tools. This paper is the fourth part of the survey of the cell placement techniques for digital VLSI circuits. In this part of the survey, the simulated annealing algorithm and neural networks are presented. An application of the simulated annealing algorithm to the cell placement problem is described. Nowadays the tools used for the cell placement, which utilize the presented algorithms are characterized: TimberWolfSC, TimberWolfMC, MGP, MPG-MS, VPR. Then, applications of neural networks to the cell placement problem are described. A self-organizing network and Hopfield network for the cell placement problem are presented. Some circuit layouts generated by using the Hopfield network are presented. Applications of a genetic algorithm, evolutionary strategy, three-stage placement-floorplanning-placement flow and special purpose hardware for the cell placement are described. Tools used for the 3D VLSI cell placement are characterized. Some conclusions concerning described techniques and tools are presented.

3

Projektowanie topografii systemów VLSI. Cz. 3. Metody analityczne

Nagórny Z., Kos A.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 4

669-695

PL

Niniejsza praca jest trzecią częścią przeglądu metod rozmieszczania modułów, stosowanych podczas projektowania topografii układów VLSI. W pracy szczegółowo został opisany algorytm zamiany parami oraz metody analityczne. Przedstawiono liczne modyfikacje algorytmu zamiany parami, łącznie z algorytmami wykorzystującymi metody relaksacyjne. Modyfikacje algorytmu zamiany parami oraz metody relaksacyjne są stosowane w programach rozmieszczania opartych na metodach analitycznych. Następnie, opisano podstawy zastosowania programowania kwadratowego i liniowego w rozmieszczaniu modułów. Ze względu na dużą liczbę rozwiązań stosowanych w metodach analitycznych, poszczególne rozwiązania szczegółowo przedstawiono na przykładzie wybranych programów rozmieszczania. W tym celu scharakteryzowano następujące programy rozmieszczania: GORDIAN / DOMINO, KraftWerk, FastPlace, mPL, PROUD, ATLAS, FAR, mFAR, BloBB, APlace. Przedstawiono również sposób zastosowania metody relaksacyjnej w układach o topografii swobodnej oraz możliwość optymalizacji topografii układu ze względu na aspekt termiczny.

EN

The design process of the VLSI circuits requires the use of computer aided design tools. This paper is the third part of the survey of the cell placement techniques for digital VLSI circuits. In this part of the survey, the pairwise interchange algorithm and some analytical methods are presented. The force-directed placement algorithm and some modifications of the pairwise interchange algorithm, which are used in analytical algorithms are described. Then, the nonlinear programming, quadratic programming and linear programming techniques are presented. An application of these techniques to the cell placement problem is described. Nowadays the tools used for the cell placement, which utilize the presented algorithms are characterized: GORDIAN, DOMINO, KraftWerk, FastPlace, mPL, PROUD, ATLAS, FAR, mFAR, BloBB, APlace. A force-directed placer for a building block design style is described. The principles of the multilevel optimization for the cell placement problem are presented. Applications of the flow network and branch and bound algorithm to the cell placement are characterized. Some conclusions concerning described techniques and tools are presented.

4

Projektowanie topografii systemów VLSI. Cz. 2, Algorytm min-cut

Nagórny Z., Kos A.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 3

469-488

PL

Niniejsza praca jest drugą częścią przeglądu metod rozmieszczania modułów, stosowanych podczas projektowania topografii układów VLSI. W pracy szczegółowo został opisany algorytm min-cut. Przedstawiono algorytm Kernighana i Lina, który jest stosowany w algorytmie min-cut. Opisano algorytm podziału Fiduccia i Mattheysesa. Przedstawiono modyfikacje algorytmu min-cut. Podany został sposób zastosowania algorytmu min-cut dla topografii swobodnej. Omówiono wielopoziomowy algorytm podziału hMETIS. Scharakteryzowano obecnie stosowane programy, które wykorzystują algorytm min-cut: Capo, Dragon, Feng Shui, QUAD.

EN

The design process of the VLSI circuits requires the use of computer aided design tools. This paper is the second part of the survey of the cell placement techniques for digital VLSI circuits. In this part of the survey, the min-cut algorithm is presented. The Kernighan-Lin algorithm and its modifications, which are the base of the min-cut algorithm are described. Then, the Fiduccia-Mattheyses algorithm is described. The computation time of the Fiduccia-Mattheyses algorithm increases only slightly more than linearly with the number of logic cells in the circuit. It is a very important improvement. Some modifications of the min-cut algorithm are presented. The terminal propagation and the quadrisection algorithm are described. The application of the min-cut algorithm for the building block design style is presented. The principles of the multilevel circuit partitioning algorithm are described. Two multilevel circuit partitioning algorithms are characterized: hMETIS and hMETIS-Kway. Nowadays the tools used for the cell placement, which utilize the presented algorithms are characterized Capo, Dragon, Feng Shui, QUAD. Some conclusions concerning described techniques and tools are presented.

5

Projektowanie topografii systemów VLSI. Cz. 1, Style i etapy projektowania, rozmieszczanie modułów

Nagórny Z., Kos A.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 3

451-468

PL

Projektowanie układów VLSI wymaga stosowania systemów projektowania wspomaganych komputerowo. Niniejsza praca jest pierwszą częścią przeglądu metod rozmieszczania modułów, stosowanych podczas projektowania topografii układów VLSI. Opisano różne style topografii oraz przykłady układów dla poszczególnych stylów. Następnie, przedstawiono etapy projektowania topografii: podział, planowanie układu, rozmieszczenie, trasowanie połączeń oraz weryfikacja. Planowanie układu zostało szczegółowo omówione, ze względu na podobieństwa łączące ten etap z rozmieszczaniem. Przedstawiono problem rozmieszczania modułów. Omówiono sposoby estymacji długości połączeń. Opisano metody minimalizacji opóźnień w układzie. Przedstawiono stosowane metody rozmieszczania modułów.

EN

The design process of the VLSI circuits requires the use of computer aided design tools. This paper the first part of the survey of the cell placement techniques for digital VLSI circuits. Design styles used in VLSI circuits are described. Layouts of Standard Cell, Gate Array, Sea-of-Gates and Field Programmable Gate Array are presented. Then the physical design flow, which includes partitioning, becouse this stage is similar to the placement problem. The cell placement problem and placement techniques are describes. VLSI cell placement phase of the physical design process. Cell placement, which is a ver difficult optimization problem, has proved to be a np. - compete. The goail of the VLSI cell placement is to arrange all the cells on a placement carrier while minimizing an objective or cost function. The most commonly used objectives of the placement are to minimize the total estimated wire length and the interconnect congestion, and to meet the timing requirements for critical nets. Commonly used wire length estimates for the cell placement are presented. The timing driven placement methods are described. The algorithms used for the cell placement are presented.

6

Optymalizacja z wykorzystaniem zmodyfikowanej sieci Hopfielda

Nagórny Z., Kos A.

Kwartalnik Elektroniki i Telekomunikacji

|

2005

|

Vol. 51, z. 2

255--275

PL

W pracy przedstawiono oryginalną metodę rozwiązywania problemów optymalizacyjnych z wykorzystaniem zmodyfikowanej sieci neuronowej typu Hopfielda. W klasycznym rozwiązaniu wartości wag połączeń między neuronami w sieci Hopfielda są obliczane przed symulacją i nie ulegają zmianie. W niniejszej pracy zbadano wpływ modyfikacji wartości sygnałów wejściowych neuronów lub wag podczas symulacji sieci, na otrzymywane rozwiązania. Zauważono, że modyfikacja sygnałów wejściowych lub wag umożliwia uzyskanie lepszych rozwiązań. W pracy przedstawiono rezultaty otrzymane zmodyfikowaną siecią dla problemu komiwojażera. Dla problemów o wymiarze równym 10, sieć dla 100% prób generowała optymalne rozwiązanie. Dla większych problemów rozwiązania są lepsze od otrzymanych klasyczną siecią. Przedstawiono wnioski płynące z zastosowania opisanej metody.

EN

The paper presents a novel method for solving optimization problems by using a modified Hopfield network. In a conventional Hopfield network weight values of the net are calculated before simulation and are constant. Our method is a novel method, because the values of input signals or weights are modified during simulation. The method makes use of the Hopfield net with continuous function of neurons according to Eq. (2). The model Hopfield net in electronic components is shown in Figure 1. An energy function of the neural net is described by Eq. (3). Comparing Eq. (3) and Eq. (4), which is a general form of an optimization problem cost function, we get weight and external input signal values. The Hopfield net is implemented in software in this work. A simulating program makes use of Eq. (11) to calculate the input of each neuron in the net. During the simulation the input signals are modified in accordance with Eq. (12). The duration of input signals modifying is defined by a random value nnar. Finally, a number of iterations to achieve a stable state of the net are done. A number of trials are performed for each optimization problem and the best results are chosen. Figure 2 shows the algorithm of the method. In this work, simulations were done for six examples of the travelling salesman problem. A cost function of the travelling salesman problem is described by Eq. (17). This function consists of four components: the total length of the salesman's tour, two terms, which ensure that the salesman's tour is valid and the term, which forces neurons to have the output signal equal zero or one. The method with input signal values modifying during simulation gives better results than the conventional one. Results are performed in Table 1 and 2. For ten-city problems the modified Hopfield net finds the optimal solution with 100% success rate. Some conclusions coming from using this method are presented.

7

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

Kos A., Nagórny Z.

Kwartalnik Elektroniki i Telekomunikacji

|

2005

|

Vol. 51, z. 1

55--72

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.

8

Estymacja długości połączeń w układach VLSI

Kos A., Nagórny Z.

Elektronika : konstrukcje, technologie, zastosowania

|

2005

|

Vol. 46, nr 11

47-49

PL

Znane są różne sposoby estymacji długości połączeń w układach VLSI. Nie zawsze istnieje zgodność między wartością estymowanej długości połączeń a rzeczywistą długością połączeń po ich wyznaczeniu. Przedstawiono sposób wyznaczenia współczynników korygujących wartość estymowanej długości połączeń, w zależności od liczby końcówek w danym węźle układu elektronicznego. Określono wartości współczynników dla dwóch sposobów estymacji długości połączeń: half-perimeter oraz grafu pełnego. Wartości współczynników wyznaczono na podstawie porównania estymowanej długości połączeń bez współczynników z długością wyznaczoną na podstawie zmodyfikowanego algorytmu Prima, który jest stosowany do prowadzenia połączeń w układach VLSI. Przedstawiono rezultaty rozmieszczania modułów, uzyskane z zastosowaniem otrzymanych współczynników.

EN

The design process of the VLSI circuits requires the use of computer aided design tools. The physical design phases are described: floorplanning, placement and routing. The cell placement is a very important phase of the physical design process. The most commonly used objective of the placement is to minimize the total wire length. Placement algorithms use a wire length estimate to minimize the total wire length, because each intermediate configurations routing takes too much time. The most commonly used methods to estimate the total wire length are halfperimeter and complete graph measures. There is not a good correlation between these estimations and the actual total wire length after routing. In this paper a method to adjust the halfperimeter and complete graph measures using correction factors is presented. The correction factor of the net wire length estimate is a function of the number of net terminals. The actual net wire length is calculated by using a modified Prim algorithm and the Lee algorithm.

9

Optyczne testowanie topografii układów elektronicznych z wykorzystaniem morfologii matematycznej

Nagórny Z.

Elektrotechnika i Elektronika

|

2003

|

T. 22, z. 1

9--16

PL

W pracy przedstawiono optyczną metodę testowania topografii układów elektronicznych. Metoda ta wykorzystuje morfologię matematyczną. Zaproponowano algorytm testowania połączeń, który sprawdza wymaganą minimalną szerokość ścieżek. Przedstawiono przykłady i wnioski płynące z zastosowania tej metody.

EN

The paper presents a visual method of testing the topography of electronic circuits. The method makes use of mathematical morphology techniques. The algorithm for the testing connection, which inspects minimum conductor traces width requirement is proposed. Some examples and conclusions coming from using this method are presented.