Realizacja algorytmu sekwencyjnego wyznaczania macierzy rozróżnialności zbiorów przybliżonych w układzie FPGA

• Autorzy: Kopczyński M. , Grześ T. , Stepaniuk J.

Warianty tytułu

EN

Realization of a sequential algorithm related to rough sets methodology in FPGA

• Języki publikacji: PL

Abstrakty

PL

W niniejszym artykule przedstawiono implementację sprzętową algorytmu stosowanego w obliczeniach związanych ze zbiorami przybliżonymi służącego do wyznaczania macierzy rozróżnialności. Istniejące dotychczas rozwiązania implementowały algorytm w językach programowania wysokiego poziomu. W wyniku prac badawczych stworzono i opisano w języku VHDL układ kombinacyjny realizujący równoważne obliczenia. Przeprowadzono badania porównawcze pod względem czasu potrzebnego do zakończenia obliczeń. Uzyskane wyniki pokazują ogromne przyspieszenie układu sprzętowego w porównaniu do implementacji programowej.

EN

In this paper the authors present an example of sequential software algorithm implementation as a hardware unit using VHDL in FPGA programmable logic structure. The converted algorithm is one of the principal operations in the rough sets theory – discernibility matrix calculation. Rough sets methods are used in data analysis, knowledge discovery and datasets attributes downsizing. At present there are no complete hardware implementations of rough sets methods. The existing solutions are only software implementations which need huge amount of time for processing big datasets. The authors created hardware implementation of such an algorithm as a pure combinational unit described in the VHDL language. Software implementation was also created to compare processing times between two solutions. The obtained results show that the usage of a hardware processing unit gives huge acceleration in terms of the time needed to finish creating a discernibility matrix. The FPGA structure utilization focused on LEs (Logical Elements) and pins usage was also examined. The first section of the paper is an introduction to rough sets and FPGA structures. In the second section there are presented the example of entry dataset and the calculated discernibility matrix. This section also includes description of the algorithm for creating a discernibility matrix as well as the proposed hardware solution. The third section presents the experimental results for the processing time and FPGA structure utilization. The last section focuses on conclusions and plans for future research.

Słowa kluczowe

PL

zbiory przybliżone; układy programowalne; FPGA

EN

rough sets; programmable logic structures; FPGA

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2014
• Tom: R. 60, nr 5
• Strony: 321--324
• Opis fizyczny: Bibliogr. 11 poz., tab., wykr.

Twórcy

autor

Kopczyński M.

• Wydział Informatyki, Politechnika Białostocka, ul. Wiejska 45a, 15-351 Białystok

autor

Grześ T.

• Wydział Informatyki, Politechnika Białostocka, ul. Wiejska 45a, 15-351 Białystok

autor

Stepaniuk J.

• Wydział Informatyki, Politechnika Białostocka, ul. Wiejska 45a, 15-351 Białystok

Bibliografia

• [1] Athanas P., Pnevmatikatos D., Sklavos N. (Eds.): Embedded Systems Design with FPGAs, Springer, 2013.
• [2] Grześ T., Kopczyński M., Stepaniuk J.: FPGA in rough set based core and reduct computation, Lecture Notes in Computer Science Vol.8171: Lecture Notes in Articial Intelligence, Rough sets and knowledge technology: 8th International Conference: RSKT2013, eds. Pawan Lingras, Marcin Wolski, Chris Cornelis, Sushmita Mitra, Piotr Wasilewski, Berlin, Springer-Verlag, s. 263-270, 2013.
• [3] Kanasugi A., Yokoyama A.: A basic design for rough set processor, In The 15th Annual Conference of Japanese Society for Articial Intelligence, 2001.
• [4] Kopczyński M., Stepaniuk J.: Rough set methods and hardware implementations, Zeszyty Naukowe Politechniki Białostockiej. Informatyka Zeszyt 8, s. 5-18, 2011.
• [5] Kopczyński M., Stepaniuk J.: Hardware Implementations of Rough Set Methods in Programmable Logic Devices, Rough Sets and Intelligent Systems – Professor Zdzisław Pawlak in Memoriam, eds. Andrzej Skowron, Zbigniew Suraj, Intelligent Systems Reference Library 43, Heidelberg, Springer, s. 309-321, 2013.
• [6] Lewis T., Perkowski M., Jozwiak L.: Learning in Hardware: Architecture and Implementation of an FPGA-Based Rough Set Machine, euromicro, vol. 1, 25th Euromicro Conference (EUROMICRO '99)- Volume 1, s. 1326, 1999.
• [7] Pawlak Z.: Elementary rough set granules: Toward a rough set processor. In: S. K. Pal, L. Polkowski, and A. Skowron, editors, Rough- Neurocomputing: Techniques for Computing with Words, Cognitive Technologies. Springer-Verlag, Berlin, Germany, pp. 5-14, 2004.
• [8] Pawlak Z., Skowron A.: Rudiments of rough sets. Information Sciences, 177(1), s. 3-27, 2007.
• [9] Stepaniuk J.: Knowledge discovery by application of rough set models. In: L. Polkowski, S. Tsumoto, T.Y. Lin (Eds.), Rough Set Methods and Applications. New Developments in Knowledge Discovery in Information Systems, Physica-Verlag, Heidelberg, 137- 233, 2000.
• [10] Stepaniuk J.: Rough-Granular Computing in Knowledge Discovery and Data Mining, Springer, 2008.
• [11] Stepaniuk J., Kopczyński M., Grześ T.: The First Step Toward Processor for Rough Set Methods, Fundamenta Informaticae Vol. 127, s. 429-443, 2013.