Параллельное вычисление булевых функций как модель доступа к распределенным информационным ресурсам тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Назаров, Максим Николаевич

• Назаров, Максим Николаевич
• кандидат физико-математических наук
• 2002

Оглавление диссертации кандидат физико-математических наук Назаров, Максим Николаевич

Введение.

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

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

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

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

2.1. Сложность алгоритма DPrj-при ослабленном росте числа процессоров.

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

Глава 3. Параллельный доступ к криптографически защищенной базе данных.

3.1. Доступ к криптографически защищенной базе данных

3.2. Одновременный доступ к системе криптографически защищенных баз данных

Глава 4. Параллельный доступ к распределенным ресурсам при кратных обращениях к внешним носителям.

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

В связи с постоянным расширением области применения компьютерных технологий и широким распространением глобальных компьютерных сетей одним из актуальных направлений математической кибернетики являются проблемы оптимизации работы с распределенными информационными ресурсами. Кроме того, необходимо отметить, что в последнее время активно развивается новое научное направление, связанное с оптимальным хранением и поиском информации, именуемое теорией информационного поиска, одним из главных носителей которого является теория баз данных [4].

В Асиломарском отчете о направлениях исследований в области баз данных [2] прямо указывается на необходимость существенного расширения спектра исследований посредством решения задач получения, хранения и анализа огромных объемов информации.

Использование математических моделей, интерпретирующих распределенную информацию как набор булевых функций, реализованных таблицами, делает особенно актуальным разработку и исследование новых алгоритмов решения известной задачи вычисления булевой функции на нескольких независимых наборах, а также получение новых оценок сложности таких алгоритмов.

В дальнейшем под доступом к распределенным информационным ресурсам мы, как правило, будем понимать извлечение информации из распределенных баз данных, трактуя базу данных как формализованное представление информации, удобное для хранения и поиска данных в нем [4].

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

В последнее время уже создано довольно много прототипов распределенных и параллельных систем баз данных, однако в этой области остается и множество пока еще нерешенных или только частично решенных проблем [2, 48].

Выделим те из них, которые нашли свое отражение в данной диссертационной работе и рассмотрим их актуальность.

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

Другой круг актуальных проблем, имеющих отношение к применению распределенных и параллельных баз данных, связан с необходимостью выполнения огромного количества независимых запросов от различных пользователей к одной базе данных. Известно, например, что некоторые корпорации уже развертывают базы данных, рассчитанные на 50 тыс. одновременно работающих пользователей [2]. Причем сложность решения указанных проблем заключается в использовании параллельной модели, допускающей одновременный доступ к любому модулю памяти только одного процессора. Следовательно, необходимо преодолеть так называемый конфликт доступа к памяти (memory contention) [21, 36, 40, 44, 47].

Кроме того, в последнее время большое значение приобрела проблема защиты информации, хранимой в базах данных, от несанкционированного доступа. Данная проблема включает в себя множество различных направлений, из которых следует, прежде всего, выделить криптографические методы защиты [3, 6, 16, 45]. Использование распределенных и параллельных баз данных накладывает свою специфику на возможность применения криптографических методов, что требует отдельных исследований в каждом конкретном случае.

Не менее актуально сегодня довольно новое направление защиты информации, заключающееся в разработке модели и соответствующих алгоритмов, позволяющих пользователям осуществить доступ к общей базе данных, сохранив секретность самих запросов от других пользователей. Впервые такая задача была сформулирована в [26], а дальнейшее развитие получила в [20, 27, 32, 33, 25, 34]. Актуальность и практическая значимость результатов по данной тематике хорошо отражена в [24]. Отметим только, что указанное направление защиты информации напрямую связано с общей проблемой оптимального доступа к распределенным информационным ресурсам.

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

Итак, были выделены три группы актуальных проблем: минимизация количества обращений к запоминающим устройствам, организация доступа к распределенной памяти и защита информации. Причем первые две из них могут быть решены разработкой алгоритмов, обеспечивающих одно обращение к каждой части разбиения базы данных при одновременном выполнении нескольких независимых запросов. Ясно, что это направление непосредственно связано с проблематикой физической организации баз данных. При физической организации баз данных мы имеем дело не с представлением данных в прикладных программах, а с их размещением на запоминающих устройствах [4]. Согласно [13], при выборе физической организации на первом месте стоит обеспечение оптимальности поиска (в частности и оптимальность времени доступа к данным), далее идут эффективность операций добавления и удаления информации, а затем обеспечение компактности данных. Некоторые модели физической организации данных хорошо описаны в [10, 13, 8, 1].

В последнее время распространение получила математическая модель, представляющая базу данных в виде таблицы для булевой функции /: {0,1}" {0,1} (см., например, [26, 23]). Запрос пользователя интерпретируется как входной набор х е {0,1}". Результатом запроса является значение f[x). Следовательно, одновременное выполнение нескольких запросов трактуется как задача параллельного вычисления булевой функции на нескольких независимых наборах. Задача вычисления булевой функции на одном произвольном наборе исследована довольно давно [12, 19, 14, 50]. Получены соответствующие оценки сложности. Однако, при вычислении булевой функции на нескольких независимых наборах возникает проблема, формулируемая следующим образом. Верно ли, что сложность такого вычисления булевой функции эквивалентна суммарной сложности независимого вычисления указанной функции на каждом входе, то есть, что индивидуальные вычисления не пересекаются? Впервые такая задача была рассмотрена в [17, 42, 30] на основе схем из функциональных элементов, причем был получен отрицательный ответ на предыдущий вопрос. Общая постановка описанной проблемы, получила название Direct Sum Problem и успешно исследовалась в литературе. В случае сложности связи (communication complexity) был также получен отрицательный ответ на Direct Sum Problem [29, 35]. Зато в случае сложности монотонных схем (monotone circuit size complexity) [49] и в случае сложности булевых деревьев решений (boolean decision trees) [41] ответ был положителен.

Однако, новый подход к решению проблемы вычисления булевой функции на нескольких независимых наборах и ее интерпретация как алгоритма параллельного доступа к базе данных был реализован в [23]. В трактовке базы данных как булевой функции авторами [23] была s рассмотрена специальная модель, представляющая собой вычислительную сеть, каждый элемент которой называется булевым процессором или просто процессором и является булевой схемой из функциональных элементов со сложностью равной некоторой константе. Данная сеть может выполнять запросы к внешней памяти (то есть базе данных), затрачивая определенное время, обозначенное extime. Причем главным ограничением рассмотренной модели является допуск единственного обращения каждого процессора к внешней памяти при выполнении одного запроса по нескольким адресам. Это ограничение связано с тем, что на практике скорость обращения и считывания информации с любого внешнего носителя существенно ниже скорости работы процессора (проблема, отмеченная в [2]). Поэтому общее время доступа к базе данных будет минимально при одном обращении к внешнему носителю информации, даже если это ограничение потребует дополнительных вычислений.

Очевидно, что при хранении базы данных одним блоком (без распределения информации), извлечение нескольких не связанных между собой бит за одно обращение невозможно. Более того, простое разбиение данных на части не обеспечит выполнение главного ограничения, так как может потребоваться извлечь несколько независимых бит из одной части разбиения. Следовательно, необходимо введение специальной дополнительной информации. В [23] был построен алгоритм, названный DPrf> который максимально распараллелен, удовлетворяет главному ограничению и имеет оптимальное (относительно extime) время работы и оптимальное увеличение размера базы данных при ее распределении по различным носителям. Для разработанного алгоритма получены оценки его сложности: время параллельных вычислений, количество булевых процессоров и размер базы данных.

Заметим однако, что из [23] непосредственно следуют еще несколько не решенных, но актуальных и практически значимых задач. Прежде всего следует рассмотреть возможность применения алгоритма для доступа к базе данных, представляющей собой не одну, а несколько булевых функций в табличном виде. То есть, в этом случае каждому входному набору (запросу пользователя) соответствует не один бит информации, а несколько. Фактически, это задача параллельного вычисления системы булевых функций на нескольких независимых наборах переменных. Далее отметим, что алгоритм, полученный в [23], требует очень большого количества параллельных процессоров. Поэтому весьма важна задача минимизации количества процессоров указанного алгоритма при сохранении всех его ограничений. Заметим, что в [23] был рассмотрен один из возможных способов уменьшения числа процессоров, требующий увеличения размера базы данных в несколько раз. Ясно, что такой путь не всегда возможен из-за чрезмерного увеличения базы данных.

Кроме того, желательно рассмотреть проблему защиты информации при учете особенностей указанного распределения информационных ресурсов и задачу параллельного доступа к данным при допуске нескольких обращений к внешним носителям информации.

Дальнейшее развитие методы из [23] получили в работах [21, 22, 28]. Все данные работы посвящены проблеме организации распределения набора данных по модулям памяти в так называемых машинах с распределенной памятью (DMM — Distributed Memory Mashine) или параллельных модульных компьютерах (Module Parallel Computer) [36, 38, 40, 44, 47]. Главным ограничением указанной задачи является допуск одновременного доступа к любому модулю памяти только одного процессора, то есть отсутствие конфликтов доступа к памяти. Легко видеть, что данное ограничение очень похоже на главное ограничение алгоритма из [23], откуда и следуют сходные методы решения указанных задач. Ранее проблема организации распределения данных по модулям памяти, как правило, решалась путем моделирования PRAM алгоритмов на DMM модели [37, 36, 40, 44, 47], что обеспечивало эффективность решения только в предположении об относительно небольшом объеме распределяемых данных. Методы же [21, 22, 28] обеспечивают эффективное решение в случае большого количества распределяемых данных, причем без конфликтов доступа к памяти при выполнении запросов. Отметим, что в [22] и [28] была затронута проблема уменьшения числа процессоров в используемых алгоритмах, но только для конкретного типа задач.

Кроме того, в [22] указывается, что разработанные методы могут быть напрямую использованы для построения PIR-протоколов (Private Information Retrieval) защиты информации [26, 27, 31]. Данные протоколы должны обеспечить секретность запросов одного пользователя базы данных от всех других пользователей этой же базы. Заметим однако, что проблема организации криптографической защиты базы данных при использовании методов [23] для параллельного доступа к информации ранее не рассматривалась. Поэтому решение указанной задачи особенно актуально, техм более что криптографические методы могут найти широкое применение и при построении PIR-протоколов. Например, некоторые криптографические методы уже использовались для шифрования запросов, но не самой информации в [39]. Возможно применение криптографических методов защиты информации и в симметричных PIR-протоколах [31, 39], которые должны обеспечить не только секретность запросов каждого пользователя, но и не позволят узнать пользователю ничего, кроме запрошенной записи при выполнении одного запроса.

Целью данной диссертационной работы является исследование и разработка алгоритмов параллельного вычисления булевых функций на нескольких независимых наборах, используемых как модель доступа к распределенным информационным ресурсам и обеспечивающих оптимальное время получения информации при полиномиально ограниченном количестве процессоров.

Достижение поставленной цели включает решение следующих задач:

1. Исследовать случай параллельного вычисления системы булевых функций на нескольких независимых входных наборах переменных. Соответственно, необходимо рассмотреть математическую модель, в которой распределенная информация представлена таблицами для нескольких булевых функций и каждому входному набору (запросу пользователя) соответствует некоторая двоичная строка, а не один бит информации. На основе указанной модели необходимо построить алгоритм доступа к распределенным ресурсам по нескольким независимым адресам и оценить его сложность. При этом алгоритм должен быть максимально распараллелен и обеспечивать однократное обращение к внешним носителям информации при выполнении одного набора запросов (это обеспечивает оптимальность времени доступа к информации).

2. Определить минимальное число процессоров, необходимое для оптимального параллельного вычисления булевой функции на нескольких независимых наборах переменных при допуске одного единственного обращения к таблицам для каждой входной последовательности наборов. Разработать соответствующий алгоритм, обеспечивающий минимальное количество процессоров, и оценить сложность всех алгоритмов при ограниченном количестве процессоров.

3. Для использованных математических моделей разработать и оценить сложность алгоритмов параллельного извлечения информации из криптографически защищенной распределенной базы данных по нескольким независимым адресам за одно обращение к внешним носителям информации. Алгоритмы должны быть максимально распараллелены и иметь оптимальное время доступа при полиномиально ограниченном количестве процессоров и оптимальном размере базы данных.

4. Оценить сложность алгоритмов параллельного доступа к распределенным информационным ресурсам по нескольким независимым адресам при допуске заранее определенного количества обращений к внешним носителям информации.

Для решения поставленных задач в работе были использованы методы дискретной математики и математической кибернетики, параллельных вычислений и распараллеливания алгоритмов, теории математического моделирования, аппарата баз данных и криптографии.

Как результат проведенного исследования и решения поставленных задач на защиту выносятся:

1. Параллельный алгоритм вычисления системы булевых функций на нескольких независимых наборах, учитывающий все введенные ограничения модели, и оценки его сложности.

2. Оценки сложности алгоритма DPrf ПРИ ослабленном росте числа процессоров.

3. Алгоритм параллельного вычисления булевой функции на нескольких независимых наборах, обеспечивающий минимальное число процессоров при соблюдении главного ограничения модели, и оценки его сложности.

4. Метод распределения информации в криптографически защищенной базе данных, обеспечивающий оптимальное время доступа, соответствующие алгоритмы доступа и оценки их сложности.

5. Оценки сложности алгоритмов параллельного доступа к распределенным информационным ресурсам по нескольким независимым адресам при допуске нескольких обращений к внешним носителям информации.

В целом работа носит теоретический характер, и ее результаты могут быть использованы для получения дальнейших оценок сложности параллельных алгоритмов вычисления булевых функций на нескольких независимых наборах, сложности параллельного доступа к распределенным информационным ресурсам, построении моделей в теории информационного поиска, разработке схем устранения конфликта доступа к разделяемой памяти, а также для разработки PIR-протоколов защиты информации. В то же время, все предложенные алгоритмы могут найти и широкое практическое применение при проектировании распределенных и параллельных баз данных, а также при создании системного программного обеспечения для современных многопроцессорных вычислительных комплексов.

Отметим, что один из современных классов аппаратных архитектур многопроцессорных вычислительных систем [9, 43], получивший название МРР (Massively Parallel Processing), содержит системы, строящиеся из однотипных вычислительных узлов, включающих один или несколько центральных процессоров, локальную память, коммуникационный процессор или сетевой адаптер и жесткий диск [18]. Причем, общее число процессоров в таких системах может достигать несколько тысяч. Легко видеть, что методы хранения инфорхмации и алгоритмы доступа к данным, исследованные в этой диссертационной работе, могут быть успешно реализованы на практике именно для систем с подобной архитектурой. Кроме того, как уже было отмечено выше, одним из перспективных направлений в развитии многопроцессорных вычислительных систем являются параллельные машины баз данных [5]. Согласно же классификации Стоунбрейкера [46], аппаратные архитектуры таких систем могут быть разделены на три основных класса: системы с распределяемой памятью и дисками, системы с разделяемыми дисками и системы без совместного использования ресурсов. При этом в последних системах каждый процессор имеет собственную память, свой диск и процессоры соединяются в систему при помощи некоторой соединительной сети. Заметим, что математические модели, использованные в данной работе, описывают подобные системы и могут найти свое применение на практике.

В системах с распределяемой памятью и дисками все процессоры при помощи общей шины соединяются с распределяемой памятью и дисками. Поэтому, при большом количестве процессоров в таких системах начинают возникать конфликты доступа к памяти, которые позволяют разрешить методы, рассмотренные в данной работе.

На сегодняшний момент среди отечественных разработок многопроцессорных вычислительных систем одной из перспективных является вычислительный комплекс МВС-100/1000 [18, 7, 51, II]. Данный комплекс можно рассматривать как систему класса ММР, а до классификации Стоунбрейкера [46], как систему без совместного использования ресурсов, если к каждому процессорному модулю подключается отдельный диск [18]. Следовательно, теоретические методы и алгоритмы, исследованные в работе, можно попытаться реализовать на практике в указанном комплексе, тем более что "предстоят дальнейшие разноплановые работы по техническому и математическому освоению созданных систем" [11].

Данная диссертационная работа состоит из четырех глав и заключения.

В первой главе вводятся основные определения и анализируются некоторые известные результаты [23], необходимые для дальнейшего изложения материала. В частности, описывается математическая модель базы данных и рассматривается задача вычисления булевой функции на нескольких независимых наборах переменных. Строятся все вспомогательные процедуры и основной алгоритм DPrj[23].

Далее в этой же главе исследуется случай параллельного вычисления системы булевых функций на нескольких независимых входных наборах переменных. Строится алгоритм параллельного вычисления системы булевых функций как модель доступа к двоичным строкам распределенной базы данных, расположенным по нескольким независимым адресам и оценивается его сложность при условии максимальной распараллеленности всех процедур и обеспечении однократного обращения к внешним носителям информации для выполнения одного набора запросов.

Во второй главе определяется минимальное количество процессоров, необходимое алгоритму DPrj- [23] для обеспечения одного единственного обращения к внешним носителям информации при отказе от условия максимальной распараллеленности алгоритма. Оценивается сложность данного алгоритма при таком ограниченном количестве процессоров. Доказывается, что при некоторой модификации исходного алгоритма DPrf [23] количество процессоров можно минимизировать. Построен указанный модифицированный алгоритм вычисления булевой функции на нескольких независимых наборах и оценена его сложность при ограниченном количестве процессоров.

В третьей главе исследована проблема криптографической защиты распределенной базы данных при использовании описанных в главе 1 алгоритмов для доступа к информации. Разработан метод распределения данных при их хранении, обеспечивающий оптимальное время доступа. Рассмотрены обе математические модели из главы 1 и построены два алгоритма параллельного извлечения информации из криптографически защищенной базы данных по нескольким независимым адресам за одно обращение к внешним носителям. Оба алгоритма максимально распараллелены, имеют полиномиально ограниченное количество процессоров и оптимальный размер базы данных. Оценена сложность каждого из полученных алгоритмов.

В четвертой главе рассмотрен параллельный доступ к базе данных при допуске нескольких обращений к внешним носителям информации. Таким образом, в данной главе отменяется главное ограничение всех предыдущих глав. Определена взаимосвязь допустимого количества обращений к внешним носителям и минимального числа процессоров, необходимых алгоритмам, разработанным в главах 1, 2. Произведена оценка сложности алгоритмов параллельного доступа к базе данных по нескольким независимым адресам при допуске заранее определенного количества обращений к внешним носителям.

В заключении отражены основные результаты диссертационной работы и их соотношение с общей целью и конкретными задачами проведенного исследования. Указана теоретическая значимость и практическая ценность полученных результатов.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Назаров, Максим Николаевич

ЗАКЛЮЧЕНИЕ

Как было указано во введении, цель данной диссертационной работы заключается в исследовании и разработке алгоритмов параллельного вычисления булевых функций на нескольких независимых наборах, используемых как модель доступа к распределенным информационным ресурсам и обеспечивающих оптимальное время получения информации при полиномиально ограниченном количестве процессоров. При этом использована математическая модель, интерпретирующая распределенную информацию как набор булевых функций, реализованных таблицами, а каждый набор значений переменных как адрес, по которому хранится информация. Причем главным ограничением исследованной модели является допуск единственного обращения каждого процессора к внешней памяти при выполнении одного набора запросов по нескольким независимым адресам. Это ограничение связано с тем, что на практике скорость обращения и считывания информации с любого внешнего носителя существенно ниже скорости работы процессора. Поэтому общее время доступа к базе данных будет минимально при одном обращении к внешнему носителю информации, даже если это ограничение потребует дополнительных вычислений.

В соответствии с поставленной целью и учетом указанных ограничений в работе были решены следующие задачи:

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

2. Рассмотрена проблема минимизации числа процессоров при параллельном вычислении булевой функции на нескольких независимых наборах переменных, допускающем одно единственное обращение к таблицам для каждой входной последовательности наборов. Определено минимальное число процессоров, необходимое алгоритму DPгу [23] для обеспечения одного единственного обращения к внешним носителям информации при отказе от условия его максимальной распараллеленности. Оценена сложность данного алгоритма при ослабленном росте числа процессоров. Доказано, что при некоторой модификации исходного алгоритма DPrj- количество процессоров можно минимизировать. Построен указанный модифицированный алгоритм доступа, и оценена его сложность при минимальном числе процессоров.

3. Предложен метод распределения информации в криптографически защищенной базе данных, обеспечивающий оптимальное время доступа. Построены алгоритмы параллельного извлечения информации из криптографически защищенной распределенной базы данных по нескольким независимым адресам за одно обращение к внешним носителям информации. Алгоритмы максимально распараллелены и обеспечивают оптимальное время доступа при полиномиально ограниченном количестве процессоров и оптимальном размере базы данных.

4. Сформулировано новое ограничение модели, заключающееся в допуске нескольких обращений к внешним носителям для каждого процессора при выполнении одного набора запросов. Оценена сложность алгоритмов параллельного доступа к распределенным информационным ресурсам в новых условиях. Определена взаимосвязь допустимого количества обращений к внешним носителям и минимального числа процессоров, необходимых указанным алгоритмам.

Именно решение всех перечисленных задач включает в себя достижение поставленной цели исследования. Действительно, рассмотренные нами четыре группы решенных задач можно представить как четыре этапа достижения цели работы. На начальном этапе рассмотрена задача построения алгоритмов параллельного вычисления булевых функций на нескольких независимых наборах, используемых как модель оптимального доступа к распределенным информационным ресурсам. Именно здесь описывается булева модель распределенных ресурсов, определяется главное ограничение задачи и методы распределения информации. Второй этап определяет решение задачи минимизации числа процессоров при отказе от условия максимальной распараллеленности алгоритмов и увеличении оценок времени, но с сохранением общей эффективности алгоритмов. Данный этап позволяет улучшить оценки сложности используемых алгоритмов. На третьем этапе исследована специфика криптографической защиты распределенных баз данных при использовании методов оптимального доступа первого этапа. Здесь определяются новые методы распределения информации, обеспечивающие возможность ее криптографической защиты. И, наконец, на четвертом этапе определяется возможность оптимизации алгоритмов доступа при частичном отказе от главного ограничения первого этапа. Результаты данного этапа позволяют более гибко подходить к практическому использованию построенных алгоритмов. Все эти этапы вместе составляют итоговые результаты данного диссертационного исследования.

Отметим, что в целом работа носит теоретический характер, и ее результаты могут быть использованы для получения оценок сложности параллельных алгоритмов вычисления булевых функций на нескольких независимых наборах, сложности параллельного доступа к базам данных, построении моделей в теории информационного поиска, разработке схем устранения конфликта доступа к разделяемой памяти, а также для разработки протоколов защиты информации.

Продолжение теоретических исследований по теме данной диссертационной работы предполагает рассмотрение возможности применения полученных алгоритмов и оценок их сложности при организации распределения набора данных по модулям памяти в машинах с распределенной памятью (DMM — Distributed Memory Mashine) или параллельных модульных компьютерах (Module Parallel Computer) [36, 40, 44, 47]. Кроме того, необходимы теоретические исследования по применению полученных алгоритмов при потсроении PIR-протоколов (Private Information Retrieval) защиты информации [26, 27, 31].

Другое возможное наравление продолжения теоретических исследований по тематике данной диссертационной работы заключается в построении новых методов распределения данных по носителям и разработке соответствующих алгоритмов доступа.

В то же время, все предложенные алгоритмы могут найти и широкое практическое применение при проектировании распределенных и параллельных баз данных, а также при создании системного программного обеспечения для современных многопроцессорных вычислительных комплексов.

На сегодняшний момент среди отечественных разработок многопроцессорных вычислительных систем одной из перспективных является вычислительный комплекс МВС-100/1000 [18, 7, 51, 11]. Данный комплекс можно рассматривать как систему, строящуюся из однотипных вычислительных узлов, включающих один или несколько центральных процессоров, локальную память, коммуникационный процессор или сетевой адаптер и жесткий диск [18], причем все вычислительные узлы соединяются в систему при помощи некоторой соединительной сети. Легко видеть, что методы хранения информации и алгоритмы доступа к данным, исследованные в этой диссертационной работе, могут быть успешно реализованы на практике именно для систем с подобной архитектурой. Следовательно, в дальнейшем возможны практические исследования возможности применения алгоритмов данной диссертационной работы при работе с описанным вычислительным комплексом.

Таким образом, использование математических моделей, интерпретирующих распределенную базу данных как набор булевых функций, реализованных таблицами, позволяет построить новые алгоритмы параллельного доступа, которые могут найти не только теоретическое, но и практическое применение.

Для подведения окончательных итогов можно сделать вывод о том, что цель данного диссертационного исследования достигнута, все рассмотренные задачи актуальны и имеют теоретическое и практическое значение.

Список литературы диссертационного исследования кандидат физико-математических наук Назаров, Максим Николаевич, 2002 год

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Бернштейн Ф. и др. Программа исследований в области баз данных на следующее десятилетие. Асиломарский отчет о направлениях исследований в области баз данных// Открытые системы. 1999. - № 1. -С. 61-68.

3. Брикелл Э.Ф., Одлижко Э.М. Криптоанализ: обзор новейших результатов// Труды института инженеров по электротехнике и радиоэлектронике. 1988. - Т. 76. - № 5. - С. 75-93.

4. Гасанов Э.Э., Кудрявцев В.Б. Теория хранения и поиска информации. М.:ФИЗМАТЛИТ, 2002.

5. Девитт Д., Грэй Д. Параллельные системы баз данных: будущее высокоэффективных систем баз данных // СУБД. 1995. - № 2. -С. 8-31.

6. Диффи У. Первые десять лет криптографии с открытым ключом// Труды института инженеров по электротехнике и радиоэлектронике. 1988. - Т. 76. - № 5. - С. 54-74.

7. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. М.: Мир, 1976.

8. Кузьминский М., Волков Д. Современные суперкомпьютеры: состояние и перспективы // Открытые системы. 1995. - № 6. -С. 33-40.

9. Кульба В.В., Ковалевский С.С., Косяченко С.А., Сиротюк В.О. Теоретические основы проектирования оптимальных структур распределенных баз данных. М.: "Синтег", 1999.

10. Левин В.К. Отечественные суперкомпьютеры семейства МВС. http://parallel.ru/mvs/levin.html.

11. Лупанов О.Б. Об одном подходе к синтезу управляющих систем принципе локального кодирования // Проблемы кибернетики. -М: Наука, 1965.-Вып. 14.-С. 31-110.

12. Мартин Дж. Организация баз данных в вычислительных системах. М.: Мир, 1980.

13. Нигматулин Р.Г. Сложность булевых функций. М.: Наука,1991.

14. Оззу М., Валдуриз П. Распределенные и параллельные системы баз данных // СУБД. 1996. - № 4. - С. 4-26.

15. Саломаа А. Криптография с открытым ключом. М.: Мир, 1996.-318 с.

16. Улиг Д. О синтезе самокорректирующихся схем из функциональных элементов с небольшим числом зависимых элементов// Математические заметки. 1974. - № 15. - С. 558-562.

17. Цымблер М.Л. Создание системного программного обеспечения для систем с массивно-параллельной архитектурой// Диссертация на соискание ученой степени кандидата физико-математических наук. Челябинский государственый университет, 2000.

18. Шоломов JI.А. О реализации недоопределенных булевых функций схемами из функциональных элементов // Проблемы кибернетики. -М.: Наука, 1969. Вып. 21. - С. 215-226.

19. Ambainis A. Upper Bound on the Communication Complexity of Private Information Retrieval// Proc. of 24th 1С ALP. Lecture Notes in Computer Science. - 1997. - Vol. 1256. - P. 401-407.

20. Andreev A.E., Clementi A.E.F., Penna P., Rolim J.D.P. Parallel Read Operations Without Memory Contention // Technical Report TR00-053 of the ECCC.-2000.

21. Andreev A.E., Clementi A.E.F., Rolim J.D.P. On the Parallel Computations of Boolean Functions on Unrelated Inputs // IV IEEE Israel Symposium on Theory of Computing and Systems (ISTCS'96). IEEE. -1996.-P. 155-161.

22. Asonov D. Private Information Retrieval an Overview And Current Trends// Proc. of ECDPvA Workshop, Informatik 2001. Vienna, 2001.

23. Beimel A., Ishai Y. Information-Theoretic Private Information Retrieval: A unified construction // Technical Report TR01-015 of the ECCC.-2001.

24. Chor В., Gilboa N. Computationally Private Information Retrieval // Proc. of 29th ACM STOC. 1997. - P. 304-313.

25. Chor В., Goldreich O., Kushilevitz E., Sudan M. Private Information Retrieval // Proc. of 36th IEEE FOCS. 1995. - P. 41-50.

26. Clementi A.E.F., Bongiovanni G., Penna P. A Note on Parallel Read Operations on Large Public Databases // Intern. Workshop on Approximation and Randomized Algorithms in Communication Networks (ARACNE'00). Carleton Scientific Press, 2000. - P. 123-133.

27. Feder Т., Kushilevitz E., Naor M. Ammortized Communication Complexity//Proc. of 32nd IEEE FOCS. 1991. - P. 239-248.

28. Galbiati G., Fisher M.J. On the Complexity of 2-Output Boolean Networks // Theoretical Computer Science 1981. - 16. - P. 177-185.

29. Gertner Y., Goldwasser S., Malkin T. A Random Server Model for Private Information Retrieval // Technical Report MIT-LCS-TR-715. 1998.

30. Ishai Y., Kushilevitz E. Improved Upper Bounds or Information-Theoretic Private Information Retrieval // Proc. of 31-st STOC. 1999. -P. 79-88.

31. Itoh T. Efficient Private Information Retrieval// IEICE Transactions. 1999. - Vol. E82. - No. 1. - P. 11 -20.

32. Itoh T. On Lower Bounds for the Communication Complexity of Private Information Retrieval II IEICE Transactions. 2001. - Vol. E84. -No. 1.-P. 157-165.

33. Karchmer M., Raz R., Wigderson A. On Proving Super-Logarithmic Depth Lower Bounds via the Direct Sum in Communication Complexity // Proc. of 6th IEEE Struct, in Complexity Theory. 1991. -P. 299-304.

34. Karlin A., Upfal E. Parallel Hashing an Efficient Implementation of Shared Memory // Proc. ACM STOC. - 1986. - P. 160-168.

35. Karp R.M., Luby M., Meyer auf der Heide F. Efficient PRAM Simulation on a Distributed Memory Machine // Algoritmica. 1996. - 16. -P. 517-542.

36. Kruskal С.P., Rudolph L., Snir M. A Complexity Theory of Efficient Parallel Algorithms 11 Theoretical Computer Science 1990. - 71. -P. 95-132.

37. Kushilevitz E., Ostrovsky R. Replication is NOT Needed: Single-Database Computationally Private Information Retrieval // Proc. of 38th FOCS.- 1997.-P. 364-373.

38. Mehlhorn K., Vishkin U. Randomized and Deterministic Simulation of PRAM by Parallel Machines with Restricted Granularity of Parallel Memories // ACTA Informatica. 1984. - 21. - P. 339-374.

39. Nisan N., Rudich S., Saks M. Products and Help Bits in Decision Trees // Proc. of 35th IEEE FOCS. 1994. - P. 318-329.

40. Paul W.J. Realizing Boolean Functions on Disjoint Set of Variables // Theoretical Computer Science 1976. - 2. - P. 383-396.

41. Pfister G. Sizing Up Parallel Architectures // Database Programming & Design Online. 1998. - Vol. 11. - No. 5.

42. Pietracaprina A., Preparata F.P. A Practical Constructive Scheme for Deterministic Shared-Memory Access // Proc. of ACM SPAA. 1993. -P. 100-109.

43. Rivest R.L., Shamir A., Adleman L. A Method For Obtaining Digital Signatures And Public Key Cryptosystems// Commun. ACM. 1978. -Vol. 21.-No. 2.-P. 120-126.

44. Stonebraker M. The Case for Shared Nothing // Database Engineering Bulletin. 1986. - Vol. 9. - No. 1. - P. 4-9.

45. Upfal E. Efficient Schemes for Parallel Communication // J. of the ACM. 1984.- 31(3).-P. 507-517.

46. Valduriez P. Parallel Database Systems: Open Problems and New Issues // Distributed and Parallel Databases. 1993. - Vol. 1. - No. 2. -P. 137-165.105

47. Wegener I. Switching Functions Whose Monotone Complexity in Nearly Quadratic // Theoretical Computer Science 1979. - No. 9. -P. 83-97.

48. Wegener I. The Complexity of Boolean Functions. Stuttgart, 1987.-469 p.

49. Zabrodin A.V., Levin V.K., Korneev V.V. The Massively Parallel Computer System MBC-100 // Proc. of the Int. Conf. on Parallel Computing Technologies (PaCT'95). Lecture Notes in Computer Science. 1995. - Vol. 964.-P. 342-356.