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

摘要

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.%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.