The current stage of development of information technology is characterized by the expansion of the applications, much of which is associated with the accumulation of large data sets and parallel data searching in real-time. Such applications include automated systems for multi-level control of technological processes and complex objects, where at the lower levels of such systems is the accumulation of large data sets and their processing in real time. The main source in these systems are different sensors and devices that generate telemetric data. That is why it is very crucial to preprocess this data in real-time for finding further issues. One of the optimal ways for implementing it, is to use hardware approach like programmable logic device (PLD) with FPGA type. For resolving this issue in the article were analyzed the recent research and publications and has shown that the disadvantage of existing methods and algorithms for finding the maximum and minimum numbers in one-dimensional and two-dimensional arrays is that they are not focused on hardware implementation by using PLD with FPGA type. It is shown that the development of high-speed hardware for finding maximum and minimum numbers in one-dimensional and two-dimensional arrays should be carried out with an integrated approach, which includes methods, algorithms, structures and modern LPD and should be based on the following principles: homogeneity and regularity of structure; localization and simplification of connections between elements; modularity of construction; pipeline and spatial parallelism of data processing; consistency of the intensity of the discharge of bit sections with the intensity of their processing in the device. The basic operations for the implementation of algorithms for vertical-parallel search of maximum and minimum numbers in one-dimensional and two-dimensional arrays are highlighted and it is shown that they are based on the same type of basic operations with local and regular connections. In the article was developed the method of vertical-parallel searching of maximum and minimum numbers in arrays, which due to parallel processing of the first bit of an array of numbers and parallel formation of control words provides reduction of search time, which is mainly determined by bit numbers. Improved vertical-parallel method of simultaneous search of maximum and minimum numbers in two-dimensional arrays, which due to the simultaneous processing of p one-dimensional arrays and the use of the displacement method reduces the search time by p times compared to the existing method. It is shown that the time of vertical-parallel search of maximum and minimum numbers in one-dimensional and two-dimensional arrays is determined by the bit size of numbers, not their numbers. It is determined that the use of a common bus for formatting of the i-th bit of the maximum (minimum) number and the parallel formation of control words provides an increasing in the processing frequency of bit slices of one-dimensional array. It is determined that the amount of FPGA hardware resources that required for implementation a device for vertical-parallel searching of maximum and minimum numbers in a one-dimensional array mainly depends on the size of the array of numbers, and search time on their bit size.
[1] Aho, A., Ullman, J., & Hopcroft, J. (2001). Data Structures and Algorithms. Pearson India, 384 p.
[2] Altera Corporation. MAX FPGA Evaluation Kit. Guide. Retrieved from: http://itcj.sethost.net/pdf/epivt_2_1_36.pdf.
[3] Ashenden, P. J. (2010). The designers guide to VHDL. Third Edition. Morgan Kaufmann, 936 p.
[4] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill, 296 p.
[5] Date, C. J. (2003). An introduction to database systems (8th Edition). Pearson, 328 p.
[6] Grushvitsky, R. I., Mursaev, A. Kh., & Ugryumov, E. P. (2002). Designing systems based on programmable logic chips. St. Petersburg: BHV-Petersburg, 219, 148, 287–288pp. [In Russian].
[7] Hrytsiuk, Yu. I., & Buchkovska, A. Yu. (2018). Visualization of the results of expert evaluation of software quality using polar diagrams. Scientific Bulletin of UNFU, 27(10), 137–145. https://doi.org/10.15421/40271025
[8] Hrytsiuk, Yu. I., & Dalyavskyy, V. S. (2018). Using Petal Diagram for Visualizing the Results of Expert Evaluation of Software Quality. Scientific Bulletin of UNFU, 28(9), 97–106. https://doi.org/10.15421/411832
[9] Hrytsiuk, Yu. I., & Nemova, E. A. (2018). Management Features Process of Developing Software Requirements. Scientific Bulletin of UNFU, 28(8), 161–169. https://doi.org/10.15421/40280832
[10] Jiang, Q., Guo, Y., Yang, Z., & Zhou, X. (2020). A parallel whale optimization algorithm and its implementation on FPGA. IEEE Xplore: IEEE Congress on Evolutionary Computation (CEC). https://doi.org/10.1109/CEC48606.2020.9185737
[11] Kleinberg, J., & Tardos, E. (2006). Algorithm Design. Pearson, 800 p.
[12] Knuth, E. D. (1998). Art of computer programming, The: Volume 3: Sorting and Searching (Second edition). Addison-Wesley Professional, 832 p.
[13] Komolov, D. A., Myalk, R. A., Zobenko, A. A., & Filippov, A. S. (2002). Computer-aided design systems from Altera MAX+plus II and Quartus II. Moscow: RadioSoft. [In Russian].
[14] Kopczyński, M., & Grześ, T. (2021). Hardware rough set processor parallel architecture in FPGA for finding core in big datasets. University of Social Sciences. Information Technology Institute: Journal of Artificial Intelligence and Soft Computing Research Vol. 11, No. 2. 99–110 pp. https://doi.org/10.2478/jaiscr-2021-0007
[15] Krenevich, A. P. (2021). Algorithms and data structures. Kyiv: PPC "University of Kyiv", 200 p. [In Ukrainian].
[16] Levitin, A. V. (2006). Algorithms: introduction to development and analysis. Moscow: Williams, 215–218pp. [In Russian].
[17] Mizutani, K., Yamaguchi, H., Urino, Y., & Koibuchi, M. (2022). Accelerating parallel data processing using optically tightly coupled FPGAs. Journal of Optical Communications and Networking Vol. 14, Issue 2, A166–A179 pp. https://doi.org/10.1364/JOCN.448626
[18] Ott, D. E., & Wilderotter, T. J. (2010). A designers guide to VHDL synthesis. Springer Publisher, 336 p.
[19] Palagin, A., & Opanasenko, V. (2006). Reconfigurable computing systems. Kyiv: Prosvita. 280 p. [In Ukrainian].
[20] Rashkevich, Y. M, Tsmots, I. G, & Zerbino, D. D. (2000). Device for determining the maximum number from a group of numbers. Ukrainian patent for invention № 29700. Bull. № 6–11. [In Ukrainian].
[21] Tsmots, I. G, & Skoroshoda, O. V. (2013). Device for determining the maximum number from a group of numbers. Patent of Ukraine for utility model № 103106, 10.09.2013, Bull. № 17. [In Ukrainian].
[22] Tsmots, I. G., Skoroshoda, O. V., Medikovsky, M. O., & Antoniv, V. Ya. (2015). Device for determining the maximum number from a group of numbers. Patent of Ukraine for the invention № 110187, 25. Bull. № 22. [In Ukrainian].
[23] Walus, K., Dysart, T. J., Jullien, G. A., & Budiman, R. A. QCADesigner. Retrieved from: http://www.mina.ubc.ca/qcadesigner.
[24] Zotov, V. (2010). Features of the architecture of a new generation of FPGAs with architecture from Xilinx. Finestreet Publishing: Components and technologies № 12, 17–24 pp. [In Russian].