Методи та засоби вертикально-паралельного пошуку в масивах максимальних і мінімальних чисел

Abstract

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

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 twodimensional 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 verticalparallel 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.