Проведено аналіз останніх досліджень та публікацій, який показав, що недоліком наявних методів та алгоритмів пошуку максимального і мінімального чисел в одновимірному та двовимірному масивах є те, що вони не орієнтовані на апаратну реалізацію з використанням програмованих логічних інтегральних схем (ПЛІС) типу FPGA. Показано, що розроблення високошвидкісних апаратних засобів для пошуку максимальних і мінімальних чисел у одновимірному та двовимірному масивах доцільно здійснювати при інтегрованому підході, який охоплює методи, алгоритми, структури та сучасні ПЛІС і ґрунтується на використанні таких принципів: однорідності та регулярності структури; локалізації та спрощення зв'язків між елементами; модульності побудови; конвеєризації та просторового паралелізму опрацювання даних; узгодженості інтенсивності надходження розрядних зрізів із інтенсивністю їх опрацювання у пристрої. Виділено базові операції для реалізації алгоритмів вертикально-паралельного пошуку максимальних і мінімальних чисел у одновимірних і двовимірних масивах і показано, що вони ґрунтуються на однотипних базових операціях з локальними та регулярними зв'язками. Розроблено вертикально-паралельний метод одночасного пошуку максимальних і мінімальних чисел у одновимірних масивах, який за рахунок паралельного опрацювання і-го розрядного зрізу масиву чисел і паралельного формування слів управління забезпечує зменшення часу пошук, який в основному визначається розрядністю чисел. Вдосконалено вертикально-паралельний метод одночасного пошуку максимальних і мінімальних чисел у двовимірних масивах, який за рахунок одночасного опрацювання р одновимірних масивів і використання методу витіснення забезпечує зменшення тривалості пошуку у р разів порівняно з наявним методом. Показано, що час вертикально-паралельного пошуку максимальних і мінімальних чисел у одновимірному та двовимірному масивах визначається розрядністю чисел, а не їх кількістю. Визначено, що використання спільної шини для формування і-го розряду максимального (мінімального) числа та паралельне формування слів управління забезпечує підвищення частоти опрацювання розрядних зрів одновимірного масиву. Визначено, що кількість апаратних ресурсів FPGA необхідних для реалізації пристрою вертикально-паралельного пошуку максимального і мінімального чисел у одновимірному масиві в основному залежить від розміру масиву чисел, а тривалість пошуку від їх розрядності.
[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].