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

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

Warianty tytułu

EN

Wire length estimation in VLSI circuits

• Konferencja: Krajowa Konferencja Elektroniki (4 ; 12-15.06.2005 ; Darłówko Wschodnie, Polska)
• Języki publikacji: PL

Abstrakty

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.

Słowa kluczowe

PL

VLSI; rozmieszczanie modułów; estymacja długości połączeń; half-perimeter; graf pełny; minimalne drzewo rozpinające; algorytm Prima; algorytm Lee; minimalne drzewo Steinera

EN

VLSI; cell placement; routing; wire length estimation; half-perimeter; complete graph; minimum spanning tree; Prim algorithm; Lee algorithm; minimum Steiner tree

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2005
• Tom: Vol. 46, nr 11
• Strony: 47--49
• Opis fizyczny: Bibliogr. 14 poz., wykr.

Twórcy

autor

Kos A.

• Akademia Górniczo-Hutnicza, Katedra Elektroniki, Kraków

autor

Nagórny Z.

• Wyższa Szkoła Humanistyczno-Przyrodnicza, Sandomierz

Bibliografia

• [1] M. J. S. Smith: Application-Specific Integrated Circuits. Addison Wesley Longman, 1997.
• [2] M. M. Vai: VLSI Design. CRC Press, 2001.
• [3] K. Shahookar, P. Mazumder: VLSI Cell Placement Techniques. ACM Computing Surveys, vol. 23, pp. 143-220, 1991.
• [4] M. A. Breuer (Ed.): Automatyczne projektowanie maszyn cyfrowych. PWN, Warszawa, 1976.
• [5] V. Betz, J. Rose: VPR: A New Packing, Placement and Pouting Tool for FPGA Research. Proc. 7th International Workshop on Field Programmable Logic and Applications, 1997, pp. 213-222, http://www.eecg.toronto.edu/ ~vaughn/papers/fpl97.pdf.
• [6] M. Gajęcki, A. Kos: A Problem of Optimization of Topography of VLSI Circuit. Proc. XIXth National Conference on Circuit Theory and Electronic Networks, Kraków-Krynica 1996, pp. 11/307-312.
• [7] D. S. Rao, J. D. Provence: An integrated approach to routing and via minimization. Inform. Processing Lett., vol. 39, pp. 257-263, 1991.
• [8] J. Ganley, P. Madden, G. Robins, I. Mandoiu: Rectilinear Steiner Minimum Tree Slot. http://vlsicad.ucsd.edu/GSRC/bookshelf/ Slots/RSMT/.
• [9] P. Winter: Steiner Problem in Networks: A Survey. Networks, vol. 17, pp. 129-167, 1991.
• [10] A. Kos, Z. Nagórny: Minimalizacja długości połączeń w układach elektronicznych z wykorzystaniem sieci Hopfielda. Kwartalnik Elektroniki i Telekomunikacji, 2005, t. 51, z. 1, ss. 55-72.
• [11] Z. Nagórny, A. Kos: Optymalizacja z wykorzystaniem zmodyfikowanej sieci Hopfielda. Jak wyżej, z. 2, ss. 255-275.
• [12] International Conference Mixed Design MIXDES2005, Kraków (Poland), June 2005, vol. 1, pp. 33-38.
• [13] C. Ebeling, L. McMurchie, S.A. Hauck, S. Burns: Placement and Routing Tools for the Triptych FPGA. IEEE Trans, on VLSI Systems, vol. 3, pp. 473-482, 1995.
• [14] A. Drozdek, D.L. Simon: Struktury danych w języku C. WNT, Warszawa 1996.