Один із варіантів методу m-паралельного блочного пошуку записів і його ефективність

Abstract

Запропоновано один із варіантів методу m-паралельного блочного пошуку записів у файлах баз даних, орієнтований на використання в багатопроцесорних ЕОМ. Досліджено його ефективність для відомих законів розподілу ймовірностей звертання до записів (рівномірного, "бінарного", Зіпфа й узагальненого, частковим випадком якого є розподіл, який наближено задовольняє правило "80-20"). За критерій ефективності прийнято математичне сподівання кількості паралельних порівнянь, необхідних для пошуку запису у файлі. Побудовано оптимальні схеми методу, тобто схеми, за яких математичне сподівання досягає мінімуму. Зі збільшенням кількості процесорів у k разів ефективність запропонованого варіанта методу зростає в k разів, порівняно з ефективністю звичайного блочного методу, для всіх розглянутих законів розподілу ймовірностей звертання до записів, окрім "бінарного".

A version of m-parallel block record browsing method in a database file is proposed. The method is designed for application in multiprocessors of computers. The effectiveness of the method for different probability distribution of record request frequency (discrete uniform, binomial, Zipf and generalized, the partial case of which is the probability distribution approximately satisfying the rule "80-20") is investigated. The mathematical expectation of the parallel comparisons number needed for the search of a record in a file is taken as a criterion of effectiveness. The optimal schemes of the method i. e. the scheme in which the mathematical expectation attains its minimum are proposed. When the number of processors increases in k times the effectiveness of the proposed method increases in k times as compared with the effectiveness of the conventional block method for all examined probability distributions of record request frequency except for binomial one.

Предлагается вариант метода m-параллельного блочного поиска записей в файлах баз данных, ориентированный на использование в многопроцессорных ЭВМ. Исследуется эффективность этого метода для известных законов распределения вероятностей обращения к записям (равномерного, "бинарного", Зипфа и обобщенного, частным случаем которого является распределение, приближенно удовлетворяющее правило "80-20"). В качестве критерия эффективности принимается математическое ожидание количества параллельных сравнений, необходимых для поиска записи в файле. Построены оптимальные схемы метода, при которых математическое ожидание достигает минимума. С увеличением количества процессоров в k раз эффективность предложенного варианта метода возрастает в k раз по сравнению с эффективностью обычного блочного метода для всех рассмотренных законов распределения вероятностей обращения к записям за исключением "бинарного".