Інформаційні технології паралельного сортування та пошуку даних

Abstract

Дисертаційна робота присвячена вирішенню актуального наукового завдання – розробленню нових та удосконаленню існуючих методів, моделей і засобів інформаційних технологій паралельного сортування і пошуку даних у реальному часі з високою ефективністю використання обладнання. Обґрунтовано актуальність теми дисертаційної роботи, сформульовано мету та основні завдання досліджень, визначено наукову новизну роботи і практичне значення отриманих результатів, показано зв'язок роботи із науковими темами. Подано відомості про апробацію результатів роботи, особистий внесок автора та його публікації. Для забезпечення операцій сортування та пошуку даних у реальному часі розроблено інформаційну технологію паралельного сортування даних, яка завдяки використанню розроблених і вдосконалених методів, функціональних моделей паралельно-потокового сортування даних та врахуванню інтенсивності надходження даних, розмірів масивів даних і засобів реалізації забезпечує сортування даних у реальному часі з високою ефективністю використання обладнання. Розроблено метод паралельно-вертикального пошуку максимальних і мінімальних чисел у масивах, який внаслідок паралельного опрацювання і-го розрядного зрізу масиву чисел і паралельного формування слів управління зменшує час пошуку, що визначається в основному розрядністю чисел. Також було удосконалено метод паралельного сортування злиттям, який завдяки використанню базової операції об'єднання двох масивів з одночасним формуванням елементів Диссертация посвящена решению актуальной научной задачи: разработке новых и совершенствованию существующих методов, моделей и программноаппаратных средств информационных технологий параллельной сортировки и поиска данных в реальном времени с высокой эффективностью использования оборудования. Обоснована актуальность темы диссертационной работы, сформулированы цель и основные задачи исследований, определены научная новизна работы и практическая значимость полученных результатов, показана связьработы с научными темами. Даются сведения об апробации результатов работы, личном вкладе автора и его публикациях. Для обеспечения операционной сортировки и поиска данных в реальном времени разработана информационная технология параллельной сортировки данных, которая за счет использования разработанных и усовершенствованных методов, ункциональных моделей параллельно-потоковой сортировки данных и учету интенсивности поступления данных, размеров массивов данных и средств реализации обеспечивает выполнение сортировки данных в реальном времени с высокой эффективностью использования оборудования. Разработан метод параллельно-вертикального поиска максимальных и минимальных чисел в массивах, который за счет параллельной обработки i-го разрядного среза массива чисел и параллельного формирования слов управления уменьшает время поиска, которое определяется в основном разрядностью чисел. Усовершенствован метод параллельной сортировки слиянием, который за счет использования базовой операции объединения двух массивов с одновременным формированием элементов растущего и убывающего массивов обеспечивает уменьшение времени сортировки. Усовершенствован метод параллельно-вертикальной сортировки данных, который благодаря подсчету единиц в i-м входном разрядном срезе и параллельному формированию і-го разрядного среза отсортированного массива чисел уменьшает время сортировки.In the dissertation work the important scientific task is solved – development new and improvement the existing methods, models and software and hardware of information technologies for parallel sorting and data searching in real-time with high efficiency of equipment. The current stage of development of information technology for sorting and searching data is characterized by the expansion of their applications, much of which is associated with the accumulation of large data sets and parallel-stream sorting and 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. When processing data arrays often must use sorting and data searching operations, which can take up to 40% of the total time working with databases. Effective processing of data flows requires the creation of information technologies for parallel sorting and data searching in real-time based on new and improved methods, models and equipment. Methods and models of information technologies for sorting and data searching in realtime should be focused on parallel-data flow and adaptation to the intensity of data. Effective sorting and data searching in real-time requires the development, improvement and orientation of methods to a modern element base (graphics processors and programmable logic devices). To ensure data sorting in real-time information technology for parallel data sorting was developed, that by using the created and improved methods, functional models of parallel-stream data sorting and taking into account the intensity of data, the size of data arrays and equipment for implementation provides real-time data sorting with high efficiency of equipment. Also, the information technology of parallel data was developed, which provides real-time data searching with high efficiency of equipment by using the developed method of parallel-vertical searching of maximum and minimum numbers, functional models and taking into account data intensity and choice of implementation equipment. In the thesis was developed the method of parallel-vertical 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. The method of parallel merge sorting was improved, which due to the use of the basic operation of combining two arrays with simultaneous formation of elements of ascending and descending arrays provides a reduction of data sorting time in about two times. Also, the method of parallel-vertical data sorting was improved, which due to the calculation of units in the i-th input bit slice and parallel formation of the i-th bit slice of the sorted array of numbers provides reduction of sorting time in 17%. Developed software for sorting data arrays based on a graphics processor. Whereby using the improved method of parallel merge sorting, provides a time reduction of 31%. The development of software for parallel sorting and data searching is based on using the integrated approach, which includes: research, improvement, and development of methods and algorithms for parallel sorting and data searching; flow graphs of parallel algorithms; GPU architecture and CUDA software model. Also, the hardware for parallel-vertical search of maximum(minimum) values on FPGA EP3C16F484 family Cyclone III company Altera was developed. The hardware works with a clock equal to the time of operation of the trigger and three logical elements of type "AND".