Hardware Rough Set Processor Parallel Architecture in FPGA for Finding Core in Big Datasets

Maciej Kopczyński; Tomasz Grześ

doi:10.2478/jaiscr-2021-0007

Abstract

This paper presents FPGA and softcore CPU based solution for large datasets parallel core calculation using rough set methods. Architectures shown in this paper have been tested on two real datasets running presented solutions inside FPGA unit. Tested datasets had 1 000 to 10 000 000 objects. The same operations were performed in software implementation. Obtained results show the big acceleration in computation time using hardware supporting core generation in comparison to pure software implementation.

References

[1] Borowik, G.; Jankowski, J.; Kowalski K. Fast algorithm for feature extraction. Proceedings of SPIE 9662, In Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments, Proceedings of SPIE 2015, pp. 1110–1117.10.1117/12.2205909
Search in Google Scholar Back to article
[2] Choromański, M.; Grześ, T.; Hońko, P. Two FPGA Devices in the Problem of Finding Minimal Reducts. In Lecture Notes in Computer Science, Publisher: Springer, 2019, Vol. 11703, pp. 410–420.
Search in Google Scholar Back to article
[3] Czołombitko, M.; Stepaniuk, J. Generating core based on discernibility measure and MapReduce. Proceedings of the Pattern recognition and machine intelligence: 6th International conference, PReMI 2015, Warsaw, Poland, June 30–July 3, 2015, Lecture Notes in Computer Science, vol. 9124, pp. 367–376.10.1007/978-3-319-19941-2_35
Search in Google Scholar Back to article
[4] T. Geng et al., O3BNN-R: An Out-of-Order Architecture for High-Performance and Regularized BNN Inference, in IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 1, 1 Jan. 2021, doi: 10.1109/TPDS.2020.3013637, pp. 199–213.
Open DOI Search in Google Scholar Back to article
[5] Grześ T., Kopczyński M. Hardware Implementation on Field Programmable Gate Array of Two-Stage Algorithm for Rough Set Reduct Generation. In Lecture Notes in Computer Science, Publisher: Springer, 2019, Vol. 11499, pp. 495–506.
Search in Google Scholar Back to article
[6] Y. Liang, L. Lu and J. Xie, OMNI: A Framework for Integrating Hardware and Software Optimizations for Sparse CNNs in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, doi: 10.1109/TCAD.2020.3023903.
Open DOI Search in Google Scholar Back to article
[7] Z. -N. Li, C. Zhu, Y. -L. Gao, Z. -K. Wang and J. Wang, AlphaGo Policy Network: A DCNN Accelerator on FPGA in IEEE Access, doi: 10.1109/ACCESS.2020.3023739.
Open DOI Search in Google Scholar Back to article
[8] Kanasugi, A.; Yokoyama, A. A basic design for rough set processor. In Proceedings of the 15th Annual Conference of Japanese Society for Artificial Intelligence, 2001.
Search in Google Scholar Back to article
[9] Kopczyński, M.; Stepaniuk, J. Hardware Implementations of Rough Set Methods in Programmable Logic Devices. In Rough Sets and Intelligent Systems – Professor Zdzisław Pawlak in Memoriam, Intelligent Systems Reference Library 43, Heidelberg, Springer; 2013, pp. 309–321.10.1007/978-3-642-30341-8_16
Search in Google Scholar Back to article
[10] Kopczyński, M.; Grześ, T.; Stepaniuk, J. FPGA in Rough-Granular Computing: Reduct Generation. In proceedings of the 2014 IEEE/WCI/ACM International Joint Conferences on Web Intelligence Vol. 2, Warsaw, IEEE Computer Society, 2014, pp. 364–370.10.1109/WI-IAT.2014.120
Search in Google Scholar Back to article
[11] Kopczyński, M.; Grześ, T.; Stepaniuk, J. Generating core in rough set theory: Design and implementation on FPGA. In Lecture Notes in Computer Science Vol. 8537, Berlin, Springer-Verlag, 2014, pp. 209–216.
Search in Google Scholar Back to article
[12] Kopczyński, M.; Grześ, T.; Stepaniuk, J. Computation of Cores in Big Datasets: An FPGA Approach. In Lecture Notes in Computer Science Vol. 9436, Berlin, Springer-Verlag, 2015, pp. 153–163.
Search in Google Scholar Back to article
[13] Kopczyński, M.; Grześ, T.; Stepaniuk, J. Core for Large Datasets: Rough Sets on FPGA. Fundamenta Informaticae 2016, 147, pp. 241–259.10.3233/FI-2016-1407
Search in Google Scholar Back to article
[14] Lewis, T.; Perkowski, M.; Jozwiak, L. Learning in Hardware: Architecture and Implementation of an FPGA-Based Rough Set Machine. In proceedings of the Euromicro, 25th Euromicro Conference (EUROMICRO ’99), Volume 1; 1999, pp. 13–26.10.1109/EURMIC.1999.794488
Search in Google Scholar Back to article
[15] Lichman, M. UCI Machine Learning Repository [http://archive.ics.uci.edu/ml]. Irvine, CA: University of California, School of Information and Computer Science; 2013.
Search in Google Scholar Back to article
[16] Muraszkiewicz, M.; Rybiński, H. Towards a Parallel Rough Sets Computer In: Rough Sets, Fuzzy Sets and Knowledge Discovery. Springer-Verlag; 1994, pp. 434–443.10.1007/978-1-4471-3238-7_51
Search in Google Scholar Back to article
[17] Marz, N.; Warren, J.H. Big Data: Principles and best practices of scalable realtime data systems. Manning Publications Co. Greenwich; 2015.
Search in Google Scholar Back to article
[18] N. Narsale and V. Agarwal, Implementation Of LEM2 algorithm On FPGA, 2019 3rd International Conference on Electronics, Communication and Aerospace Technology (ICECA), Coimbatore, India, 2019, doi: 10.1109/ICECA.2019.8822143, pp. 1–5.
Open DOI Search in Google Scholar Back to article
[19] Nguyen, S. H.; Nguyen H. S. Some Efficient Algorithms for Rough Set Methods. In Sixth International Conference on Information Processing and Management of Uncertainty on Knowledge Based Systems IPMU’1996, volume III, Granada, Spain, July 1–5 1996, pp 1451–1456.
Search in Google Scholar Back to article
[20] Nguyen, H.S. Approximate Boolean Reasoning: Foundations and Applications in Data Mining. Transactions on Rough Sets V, Lecture Notes in Computer Science Vol. 4100, Berlin, Springer-Verlag; 2006, pp. 334–506.
Search in Google Scholar Back to article
[21] Pawlak, Z. Elementary rough set granules: Toward a rough set processor. In Rough-Neurocomputing: Techniques for Computing with Words, Cognitive Technologies, Springer-Verlag, Berlin, Germany; 2004, p. 5–14.10.1007/978-3-642-18859-6_1
Search in Google Scholar Back to article
[22] Pawlak, Z.; Skowron, A. Rudiments of rough sets. Information Sciences; 2007; 177(1), p. 3–27.10.1016/j.ins.2006.06.003
Search in Google Scholar Back to article
[23] Stepaniuk, J. Knowledge discovery by application of rough set models. In Rough Set Methods and Applications. New Developments in Knowledge Discovery, Information Systems, Physica-Verlag, Heidelberg; 2000, p. 137–233.10.1007/978-3-7908-1840-6_5
Search in Google Scholar Back to article
[24] Stepaniuk, J. Rough-Granular Computing in Knowledge Discovery and Data Mining. Springer, 2008.
Search in Google Scholar Back to article
[25] Stepaniuk, J.; Kopczyński, M.; Grześ, T. The First Step Toward Processor for Rough Set Methods. Fundamenta Informaticae 2013; 127, pp. 429–443.10.3233/FI-2013-919
Search in Google Scholar Back to article
[26] Sun, L.; Xu, J.; Li, Y. A Feature Selection Approach of Inconsistent Decision Systems in Rough Set. Journal of Computers, vol. 9, Academy Publisher; 2014, pp. 1333–1340.10.4304/jcp.9.6.1333-1340
Search in Google Scholar Back to article
[27] Tiwari, K.S.; Kothari, A.G. Design and Implementation of Rough Set Algorithms on FPGA: A Survey. IJARAI, 2014, 3, no. 9, pp. 14–23.10.14569/IJARAI.2014.030903
Search in Google Scholar Back to article
[28] Zhang, J.; Wong, J.; Pan, Y.; Li, T. A parallel matrix-based method for computing approximations in incomplete information systems. In IEEE Transactions on Knowledge Data Engineering, 2015, 27, p. 326–339.10.1109/TKDE.2014.2330821
Search in Google Scholar Back to article

Hardware Rough Set Processor Parallel Architecture in FPGA for Finding Core in Big Datasets

Abstract

Paradigm

My account