Sprzętowa implementacja zachłannego algorytmu kolorowania grafu

• Autorzy: Wyrwoł B.

Warianty tytułu

EN

Hardware implementation of the graph greedy coloring algorithm

• Języki publikacji: PL

Abstrakty

PL

Kolorowanie grafów znajduje zastosowanie wszędzie tam, gdzie konieczny jest podział zbioru na rozłączne podzbiory wg określonego kryterium jakie spełniają lub nie elementy zbioru. Większość algorytmów kolorowania realizowana jest zwykle na drodze programowej. W sytuacji, kiedy dużą rolę odgrywają uwarunkowania czasowe, konieczna jest realizacja sprzętowa z wykorzystaniem dedykowanego układu. W artykule przedstawiony został zachłanny algorytm kolorowania wierzchołków grafu oraz jego sprzętowa implementacja w układzie programowalnym FPGA. Dodatkowo omówiona została metoda reprezentacji danych opisujących strukturę grafu i przykład wykorzystania sprzętowego modułu kolorowania grafu, wspomagającego proces dekompozycji lingwistycznej, w systemie wnioskowania przybliżonego.

EN

Graph coloring algorithms are used wherever it is necessary to divide set on disjoint subsets according to specified criteria or not they meet the elements of the set. Most of the coloring algorithms are usually implemented as a computer or microcontroller program. To reduce computing time of the coloring result it is necessary to implement hardware using a dedicated chip. The paper presents graph greedy vertex algorithm and its hardware implementation in an FPGA chip. It describes also a graph data structure and finally implementation of the graph coloring module in the fuzzy hierarchical inference system. It is used in linguistic decomposition process of the knowledge base in the stage of the partitioning the rule base.

Słowa kluczowe

PL

graf nieskierowany; wierzchołek grafu; kolorowanie wierzchołków grafu; macierz sąsiedztwa; algorytm zachłanny; system wnioskowania przybliżonego; reguła rozmyta; dekompozycja lingwistyczna; FPGA

EN

undirected graph; graph vertex; graph vertex coloring; adjacency matrix; greedy algorithm; fuzzy inference system; fuzzy rule; linguistic decomposition; FPGA

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2010
• Tom: Vol. 51, nr 9
• Strony: 21--23
• Opis fizyczny: Bibliogr. 9 poz., il., wykr.

Twórcy

autor

Wyrwoł B.

• Politechnika Śląska, Wydział Automatyki, Elektroniki i Informatyki, Gliwice

Bibliografia

• [1] Driankov D., Hellendoorn H., Reinfrank M.: Wprowadzenie do sterowania rozmytego. WNT, Warszawa, 1996.
• [2] Gupta M. M., Kiszka J. B., Trojan G. M.: Multivariable Structure of Fuzzy Contral Systems. IEEE Transactions on Systems, Man, and Cybernetics, vol. 16, no. 5, 1986.
• [3] Praca zbiorowa pod red. Kubale M.: Optymalizacja dyskretna. Modele i metody kolorowania grafów. WNT, Warszawa, 2002.
• [4] Ross K. A., Wright Ch. R. B.: Matematyka dyskretna. PWN, Warszawa, 1996.
• [5] Rutkowska D., Piliński M., Rutkowski L.: Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. PWN, Warszawa-Łódź, 1997.
• [6] Wyrwoł B.: Linguistic decomposition technique based on partitioning the knowledge base of the fuzzy inference system. BULLETIN OF THE POLISH ACADEMY OF SCIENCES, TECHNICAL SCIENCES, Vol. 56, No. 1, pp. 71-76, 2008.
• [7] Yager R. R., Filev D. R.: Podstawy modelowania i sterowania rozmytego. WNT, Warszawa, 1995.
• [8] Spartan-3 FPGA Family. Technical Documentation, DS099, Xilinx, 2009.
• [9] Verilog Reference Guide. Xilinx, 1991-1999.