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

Abstract

У дисертаційній роботі розроблено метод m-паралельного послідовного перегляду та два варіанти методу m-паралельного блочного пошуку інформації у файлах баз даних. Виведено явні вирази математичного сподівання кількості паралельних порівнянь, необхідних для пошуку запису за рівномірного закону розподілу ймовірностей звертання до записів та таких нерівномірних законів як: “бінарний”, Зіпфа та узагальнений, частковим випадком якого є розподіл, що наближено задовольняє правило “80 – 20”. Для двох варіантів методу m-паралельного блочного пошуку знайдено оптимальну кількість блоків, за яких математичне сподівання кількості паралельних порівнянь досягає мінімуму. Розроблено оптимальні схеми доступу до інформації послідовних файлів для різних законів розподілу ймовірностей звертання до записів за допомогою поділу файла на оптимальну кількість блоків та вибору різних стратегій доступу до пам’яті. За критерій ефективності взято математичне сподівання загального часу, необхідного для пошуку запису. Розроблено систему паралельного опрацювання даних, яка надає можливість створення, накопичення, модифікації та оброблення інформації, а для пошуку запису використовує розроблені оптимальні схеми доступу до інформації, враховуючи закон розподілу ймовірностей звертання до записів файла. В диссертационной работе разработаны метод m-параллельного последовательного просмотра и два варианты метода m-параллельного блочного поиска. Найдены явные выражения математического ожидания количества параллельных сравнений, необходимых для поиска записи в файле для равномерного закона распределения вероятностей обращения к записям и таких неравномерных законов распределения как: “бинарный”, Зипфа и обобщенный, частным случаем которого является распределение, приближенно удовлетворяющее правило “80-20”. Разработаны оптимальные схемы доступа к информации последовательных файлов для разных законов распределения вероятностей обращения к записям файла путем разбиения файла на оптимальное количество блоков и выбора различных стратегий доступа к памяти. В качестве критерия эффективности использовано математическое ожидание общего времени, необходимого для поиска записей в файле. Разработана система параллельной обработки данных, которая предоставляет возможность создания, накопления, модификации и обработки информации, а для поиска записи использует разработанные оптимальные схемы доступа к информации, учитывая закон распределения вероятностей обращения к записям файла. This thesis addresses the realization of parallel modification of sequential field searching method and block field searching method. The m-parallel method of sequential field searching and two variants of m-parallel block field searching method are offered. These methods are oriented to be used in multiprocessing system for information searching in files of database. The effectiveness of these methods is analyzed for different probability distribution laws of field access as a discrete uniform, binomial, Zipf, and generalized the partial occasion of witch is the probability distribution approximately satisfying the rule “80 – 20”. The mathematical expectation of number of parallel comparisons necessary for field searching in files was taken as a criterion of the effectiveness. The explicit expression of mathematical expectation of number of parallel comparisons is found for each considered probability distribution law. In case of two variants of m-parallel block field searching method it was found the optimal number of blocks in which the mathematical expectation of parallel comparisons reached its minimum, for each considered distribution law of field access. Indicators of performance of parallel algorithm such as „speedup‟ and „parallel efficiency‟ were calculated for each proposed method in case of different probability distribution laws. It was obtained that the effectiveness of the m-parallel method of sequential field searching increased proportionally to the number of processors and all processors are fully used during the execution of the method. The analysis of the obtained indicators of „speedup‟ for the first variant of m-parallel block field searching showed us that increasing the number of processors leaded only to a slight increase of efficiency. And the „parallel efficiency‟ showed us a small processors usage during the execution of the method. The effectiveness of the second variant of m-parallel block field searching increases almost proportionally increasing the number of processors. During the execution of this method the processors used more than 90% CPU. The optimal strategies of field searching in sequenced files stored in external memory of multiprocessing system are made. The optimal strategies indicate how to split the file on the optimal number of blocks considering different probability distribution laws. This makes it possible for each considered distribution law to use its optimal access to sequential files stored in external memory of multiprocessor system. In this case the mathematical expectation of total time needed for field searching in files was taken as a criterion of effectiveness. The analysis of obtained optimal strategies in case of using m-parallel method of sequential field searching showed that increasing the number of processors increased the effectiveness only to a specific number of processors for each considered probability distribution law except binomial law. It was investigated three variants of using the method of m-parallel block field searching in case of different probability distribution laws, such as: using the method of m-parallel block field searching with loading of full block in RAM, with loading of m records in RAM and with a minimum loading of records in RAM. The effectiveness of three variants of using the method of m-parallel block field searching was compared and analyzed for different probability distribution laws and different number of processors. The system of parallel data processing is developed. It provides the creation, storage, modification and processing of information. This system of parallel data processing uses developed optimal strategies of field searching considering different probability distribution laws. The theoretical calculated results were fully confirmed by obtained statistical data from developed software.