Computing Sorted Subsets for Data Processing in Communicating Software/Hardware Control Systems

  • Valery Sklyarov University of Aveiro
  • Iouliia Skliarova University of Aveiro
  • Artjom Rjabov Tallinn University of Technology
  • Alexander Sudnitson Tallinn University of Technology

Abstract

Computing and filtering sorted subsets are frequently required in statistical data manipulation and control applications. The main objective is to extract subsets from large data sets in accordance with some criteria, for example, with the maximum and/or the minimum values in the entire set or within the predefined constraints. The paper suggests a new computation method enabling the indicated above problem to be solved in all programmable systems-on-chip from the Xilinx Zynq family that combine a dual-core Cortex-A9 processing unit and programmable logic linked by high-performance interfaces. The method involves highly parallel sorting networks and run-time filtering. The computations are done in communicating software, running in the processing unit, and hardware, implemented in the programmable logic. Practical applications of the proposed technique are also shown. The results of implementation and experiments clearly demonstrate significant speed-up of the developed software/hardware system comparing to alternative software implementations.

References

[1] Sklyarov, V.; Skliarova, I. (2013); Digital Hamming Weight and Distance Analyzers for Binary Vectors and Matrices, Int. Journal of Innovative Computing, Information and Control, 9(12): 4825-4849.

[2] Zmaranda, D.; Silaghi, H.; Gabor, G.; Vancea, C. (2012); Issues on applying knowledgebased techniques in real-time control systems, International Journal of Computers Communications & Control, 8(1): 166-175.
http://dx.doi.org/10.15837/ijccc.2013.1.181

[3] Field, L.; Barnie, T.; Blundy, J.; Brooker, R. A.; Keir, D.; Lewi, E.; Saunders, K. (2012); Integrated field, satellite and petrological observations of the November 2010 eruption of Erta Ale, Bulletin of Volcanology, 74(10): 2251-2271.

[4] Zhang, W.; Thurow, K.; Stoll, R. (2014); A knowledge-based telemonitoring platform for application in remote healthcare, International Journal of Computers Communications & Control, 9(5): 644-654.
http://dx.doi.org/10.15837/ijccc.2014.5.661

[5] Farmahini-Farahani, A.; Duwe, H. J.; Schulte, M. J.; Compton, K. (2013); Modular design of high-throughput, low-latency sorting units, Computers, IEEE Transactions on, 62(7): 1389-1402.

[6] Baker, Z. K.; Prasanna, V. K. (2006); An architecture for efficient hardware data mining using reconfigurable computing systems. In Field-Programmable Custom Computing Machines, Proc. 14th Annual IEEE Symp. on Field-Programmable Custom Computing Machines - FCCM, Napa, USA, 67-75.
http://dx.doi.org/10.1109/fccm.2006.22

[7] Xilinx, Inc.; Zynq-7000 All Programmable SoC Technical Reference Manual, available at http://www.xilinx.com/support/documentation/user_guides/ug585-Zynq-7000-TRM.pdf.

[8] Sklyarov, V.; Skliarova, I.; Rjabov, A.; Sudnitson, A. (2015); Zynq-based System for Extracting Sorted Subsets from Large Data Sets, Journal of Microelectronics, Electronic Components and Materials, 45(2): 142-152.

[9] Sklyarov, V.; Skliarova, I.; Silva, J.; Rjabov, A.; Sudnitson, A.; Cardoso, C. (2014); Hardware/ software co-design for programmable systems-on-chip, TUT Press.

[10] Mueller, R.; Teubner, J.; Alonso, G.; (2012); Sorting networks on FPGAs, The VLDB Journal—The International Journal on Very Large Data Bases, 21(1), 1-23.

[11] Sklyarov, V.; Skliarova, I. (2014); High-performance implementation of regular and easily scalable sorting networks on an FPGA, Microprocessors and Microsystems, 38(5): 470-484.
http://dx.doi.org/10.1016/j.micpro.2014.03.003

[12] Baddar, S. W. A. H.; Batcher, K. E. (2012); Designing sorting networks: A new paradigm, Springer Science & Business Media.

[13] Knuth, D. E. (2011); The art of computer programming: sorting and searching (Vol. 3), Addison-Wesley.

[14] Kipfer, P.; & Westermann, R. (2005); Improved GPU sorting, GPU gems 2: programming techniques for high-performance graphics and general-purpose computation, edited by M. Pharr, 733-746, available at http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html.

[15] Silva, J.; Sklyarov, V.; Skliarova, I. (2015). Comparison of On-chip Communications in Zynq-7000 All Programmable Systems-on-Chip, Embedded Systems Letters, IEEE, 7(1): 31- 34.
http://dx.doi.org/10.1109/LES.2015.2399656

[16] Sklyarov, V.; Skliarova, I.; Barkalov, A.; Titarenko, L. (2014); Synthesis and Optimization of FPGA-based Systems, Springer.

[17] Sun, S. (2011); Analysis and acceleration of data mining algorithms on high performance reconfigurable computing platforms, Ph.D. thesis, Iowa State University, available at: http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1421&context=etd.

[18] Wu, X.; Kumar, V.; Quinlan, J. R. et al. (2008); Top 10 algorithms in data mining, Knowledge and Information Systems, 14(1): 1-37.
http://dx.doi.org/10.1007/s10115-007-0114-2

[19] Firdhous, M. (2012); Automating legal research through data mining, Journal of Advanced Computer Science and Applications, 1(6): 1-8.

[20] Avnet, Inc. (2014); ZedBoard (ZynqTM Evaluation and Development) Hardware User's Guide, Version 2.2, available at: http://www.zedboard.org/sites/default/files/documentations/ZedBoard_HW_UG_v2_2.pdf.

[21] Xilinx, Inc.; OS and Libraries Document Collection UG647, available at: http://www.xilinx.com/support/documentation/sw_manuals/xilinx2014_2/oslib_rm.pdf.

[22] Xilinx, Inc.; ZC706, All Programmable SoC Evaluation Kit, UG961, Available at: http://www.xilinx.com/support/documentation/boards_and_kits/zc706/2014_3/ug961- zc706-GSG.pdf.
Published
2015-11-16
How to Cite
SKLYAROV, Valery et al. Computing Sorted Subsets for Data Processing in Communicating Software/Hardware Control Systems. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 11, n. 1, p. 126-141, nov. 2015. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/1442>. Date accessed: 30 sep. 2020. doi: https://doi.org/10.15837/ijccc.2016.1.1442.

Keywords

computing sorted subsets, communicating hardware/software systems, filtering, sorting networks, control applications