Параллельное вычисление булевых функций как модель доступа к распределенным информационным ресурсам

• Автор: Назаров, Максим Николаевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Волгоград
• Количество страниц: 105 с. : ил

ОГЛАВЛЕНИЕ
Введение

Глава 1. Основные определения и исходные алгоритмы

1.1. Булева модель параллельного доступа к распределенным ресурсам

1.2. Параллельный алгоритм вычисления системы булевых функций и его сложность

Глава 2. Минимизация числа процессоров для параллельного вычисления булевых функций

2.1. Сложность алгоритма ВРпри ослабленном росте числа

процессоров

2.2. Модификация алгоритма для минимизации числа процессоров

Глава 3. Параллельный доступ к криптографически защищенной базе данных
3.1. Доступ к криптографически защищенной базе данных
3.2. Одновременный доступ к системе криптографически защищенных баз данных
Глава 4. Параллельный доступ к распределенным ресурсам при
кратных обращениях к внешним носителям
Заключение
Библиографический список
ВВЕДЕНИЕ
В связи с постоянным расширением области применения компьютерных технологий и широким распространением глобальных компьютерных сетей одним из актуальных направлений математической кибернетики являются проблемы оптимизации работы с распределенными информационными ресурсами. Кроме того, необходимо отметить, что в последнее время активно развивается новое научное направление, связанное с оптимальным хранением и поиском информации, именуемое теорией информационного поиска, одним из главных носителей которого является теория баз данных [4].
В Асиломарском отчете о направлениях исследований в области баз данных [2] прямо указывается на необходимость существенного расширения спектра исследований посредством решения задач получения, хранения и анализа огромных объемов информации.
Использование математических моделей, интерпретирующих распределенную информацию как набор булевых функций, реализованных таблицами, делает особенно актуальным разработку и исследование новых алгоритмов решения известной задачи вычисления булевой функции на нескольких независимых наборах, а также получение новых оценок сложности таких алгоритмов.
В дальнейшем под доступом к распределенным информационным ресурсам мы, как правило, будем понимать извлечение информации из распределенных баз данных, трактуя базу данных как формализованное представление информации, удобное для хранения и поиска данных в нем [4].
Несмотря на существенное увеличение быстродействия компьютеров, рост объемов обрабатываемой информации требует разработки новых подходов к управлению базами данных. Как было

отмечено в [2], в ближайшем будущем некоторые организации будут обладать базами данных, объем которых измеряется петабайтами или экзабайтами. Ясно, что решить проблему эффективной обработки таких объемов информации могут только распределенные и параллельные системы баз данных [15], которые становятся доминирующими инструментами для создания соответствующих приложений. Традиционные компьютеры все более вытесняются успешными параллельными системами баз данных, строящихся на обычных процессорах, памяти и дисках [5]. Причем необходимо отметить, что их архитектура базируется на идее аппаратного обеспечения без совместного использования ресурсов, то есть в таких системах кортежи каждого отношения в базе данных разделяются между дисковыми запоминающими устройствами, напрямую подсоединенными к каждому процессору [5].
В последнее время уже создано довольно много прототипов распределенных и параллельных систем баз данных, однако в этой области остается и множество пока еще нерешенных или только частично решенных проблем [2, 48].
Выделим те из них, которые нашли свое отражение в данной диссертационной работе и рассмотрим их актуальность.
Заметим, во-первых, что на современном этапе развития компьютерной техники производительность процессоров растет значительно быстрее пропускной способности запоминающих устройств. Следовательно, многопроцессорные системы доступа к распределенным информационным ресурсам могут вскоре столкнуться с проблемами ограниченной пропускной способности при вводе-выводе [5]. Об актуальности этой же проблемы говорится в уже упомянутом Асиломарском отчете [2]: “К тому же, хотя емкость дисковой памяти возрастает очень быстро, время доступа уменьшается относительно

Кратко подведем итоги главы 1. Были введены основные определения и описаны вспомогательные процедуры, необходимые для построения алгоритмов доступа. Следуя работе [23], мы рассмотрели задачу вычисления булевых функций на нескольких независимых наборах переменных как математическая модель параллельного доступа к распределенной базе данных по нескольким независимым адресам. Главным ограничением рассмотренной модели является допуск только одного обращения к внешним носителям информации при выполнении одного набора запросов.
Во втором параграфе задача была обобщена на случай параллельного вычисления системы булевых функций. В соответствии с такой модификацией модели построен алгоритм параллельного доступа к двоичным строкам распределенной базы данных, расположенным по нескольким независимым адресам. Исследованы два варианта обращения каждого процессора к внешним носителям. В первом случае при одном обращении каждого процессора считывается только один бит информации, а во втором - сразу 5 бит. Доказано, что при условии максимальной распараллеленности алгоритма оба варианта имеют одинаковую сложность.
Получены все оценки сложности построенного алгоритма, сравнение которых с оценками сложности алгоритма параллельного вычисления одной булевой функции на нескольких независимых наборах [23], позволяет сделать следующий вывод.
При выполнении всех ограничений модели вычисление системы из 5 булевых функций на нескольких независимых наборах сопоставимо с параллельным выполнением л алгоритмов вычисления одной булевой функции.