«Зоопарк» нейронных сетей

Назаров Максим Николаевич

Краткая биография

Выпускник факультета МПиТК МИЭТ (2008 г.), аспирантуры МИЭТ (2011 г.). С 2011 года работает в МИЭТе.

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

Научная деятельность

Научная специальность/направление: 05.13.18 Математическое моделирование, численные методы и комплексы программ.

Научная деятельность, области научных интересов: математическое моделирование в химии и биологии, общая алгебра и её приложение, дискретная математика, нейронные сети.

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

  1. М. Н. Назаров, “Обобщение усредненных моделей с введением трёхмерного пространства”, Вестн. Сам. гос. техн. ун-та . Сер. Физ.-мат. Науки, 4(25) (2011), 110-117.
  2. М. Н. Назаров, “О построении корректной математической модели химической кинетики”, Вестн. Удмуртск. ун-та . Матем. Мех. Компьют. Науки, 2012, № 3, 65–73.
  3. М. Н. Назаров, «Об альтернативе уравнениям в частных производных при моделировании систем типа реакция–диффузия», Вестн. Удмуртск. ун-та . Матем. Мех. Компьют. Науки, 2013, № 2, 35–47.
  4. М. Н. Назаров, “Искусственная нейронная сеть с модуляцией коэффициентов синапсов”, Вестн. Сам. гос. техн. ун-та . Сер. Физ.-мат. Науки, 2(31) (2013), 58–71.
  5. М. Н. Назаров, “О поиске универсальных параметров для моделей морфогенеза”, Владикавк. матем. журн., 15:3 (2013), 41–49

Работу современных компьютеров отчасти можно назвать интеллектуальной. Машины рисуют картины и сочиняют романы, откликаются на «О’кей, Google» и успешно различают людей. «Умными» их делают специальные алгоритмы (есть и аппаратные реализации) - нейронные сети. «ИНверсия» разбирается, в чём их особенности и к чему может привести развитие искусственного интеллекта.

Познавать новое

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

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

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

Нейронные сети - это приближённая модель. Даже элементарная единица такой структуры - искусственный нейрон - пока не может выполнять все функции человеческого.

«Зоопарк» нейронных сетей

Полноценного искусственного интеллекта в ближайшее время мы не увидим. Существующие алгоритмы имитируют значительно меньшие системы. Для сравнения: в рядовых программах редко используется более ста тысяч нейронов, «прорывной» нейрочип IBM (SyNAPSE) содержит миллион, а головной мозг - 86 миллиардов! Для работы таких моделей не хватит производительности даже самых мощных компьютеров.

Учёные пошли в обход: вместо того, чтобы имитировать работу всего мозга, они создали множество различных нейронных сетей, ориентированных на разные задачи.

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

Зачем имитировать человека

Интерфейсы, имитирующие живое общение, вызывают у нас симпатию. Нейронные сети эксплуатируют этот когнитивный обман: уже существуют боты, способные поддерживать диалог. Правда, их пока нельзя назвать идеальными собеседниками. Однако иногда даже такие возможности позволяют создать успешный продукт. Этим пользуются создатели голосовых сервисов Siri, Cortrana, Google Now и им подобных.

Страшилки недалёкого будущего: чат, в котором можно использовать готовые ответы. Картинка кликабельна.

Спрос на человекоподобные системы находится даже в не самых очевидных областях. Компания DeepMind (на данный момент часть Google), среди прочих работ с нейронными сетями, учила их играть в консольные игры. «Таким образом можно заставить машину реалистичнее отзываться на действия игрока. В логике не будет строгих скриптов и правил: компьютер сам решит, как ему лучше действовать. Это повышает удовольствие от игры», - объясняет Александр Фёдоров (ВМ-21), который участвовал в хакатоне с решением такой же задачи в составе команды 5vision.

Сверхразум

Появление человекоподобных интерфейсов - приятный побочный продукт. Машина, при всех своих недостатках, обладает и некоторыми достоинствами перед человеком, и эти достоинства надо использовать. «Важным развитием нейронных сетей является решение тех задач, в которых человек может ошибаться, что порой приводит к ужасающим последствиям», - считает доцент кафедры ВТ А.В. Туркин . Человек устаёт и становится невнимательным, поддаётся эмоциям - всё это ведёт к потерям: финансовым, или, что более страшно, людским. Одна из перспективных разработок, которая с большой вероятностью заменит человека в обозримом будущем, - беспилотные автомобили.

Беспилотный автомобиль от google. Фото: wikipedia

Важно и то, как люди и машины накапливают опыт. Человек делает это непрерывно в течение длительного времени (всей жизни). Компьютер получает не такую связную, но зато разнообразную и обширную базу знаний благодаря интернету. Эта разница лишает нейронную сеть возможности улавливать некоторые тонкости человеческого восприятия, но даёт ей узнать то, на что не все люди обращают внимание. Именно поэтому искусственные системы распознавания лиц работают в некоторых ситуациях (когда речь идёт о фронтальных снимках) лучше человека. В частности, в отличие от компьютера, мы с трудом идентифицируем людей других рас. Для описания этого явления в науке ввели специальный термин - cross-race effect.

Неоспоримое преимущество машины - способность в кратчайший срок обработать большой (для человека) объём данных. Подобный «козырь в рукаве» позволил существовать FindFace - программе, позволяющей по фотографии найти пользователя социальной сети ВКонтакте. Нейронные сети в совокупности с вычислительными возможностями компьютера дают потрясающие результаты!

Лишают работы!

Хотя построить «мозг» мы пока не можем, существующие системы уже удивляют. В средствах массовой информации пишут не столько о применениях в науке и бизнесе: на пике славы (как и среди людей) ИИ, создающие песни, стихи и рисующие картины в стиле Ван Гога. В интернете даже агитируют за то, чтобы сделать аналитическую машину президентом США (watson2016.com)! Значит ли это, что человечество рискует остаться без работы? Вовсе нет.

Нейронная сеть пытается рисовать как Ван Гог. Работа со страницы Александра Фёдорова.

М.Н. Назаров, старший преподаватель кафедры ВМ-1 : «Дело в том, что сейчас нейронная сеть умеет только подражать стилю. Генерировать что-то похожее на стихи, что-то похожее на литературное произведение. Однако так будет казаться только на первый взгляд, а при тщательном разборе смысла в итоговом произведении будет мало. Пока наши возможности далеки от создания полноценного ИИ, и в ближайшие десятилетия вся действительно интеллектуальная работа останется за человеком».

А.В. Туркин: «Машина может подражать, но не может создавать. Поэтому человеку, с его умением находить нестандартные решения, всегда найдётся, чем заняться в будущем.

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

Эксперты, консультировавшие при работе над материалом:


Максим Николаевич Назаров , старший преподаватель кафедры ВМ-1. Занимается построением нейронных сетей. Автор научной публикации «Искусственная нейронная сеть с модуляцией коэффициентов синапсов».


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

Александр Фёдоров (ВМ-21, направление «Цифровая обработка сигналов и изображений») - представитель команды 5vision, занимающейся машинным обучением и анализом данных. При поддержке крупных IT-компаний 5vision организуют семинары по глубинному обучению (Deep Learning).

Алексей Смагин

  • Специальность ВАК РФ01.01.09
  • Количество страниц 105

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

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

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

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

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

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

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

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

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

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

Рекомендованный список диссертаций

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

  • Компьютерно-ориентированные схемы минимизации временной сложности цифровой обработки сигналов при динамическом изменении отсчетов 2010 год, кандидат технических наук Забеглов, Валерий Валерьевич

  • Моделирование адаптивных систем управления манипуляционных роботов на параллельных вычислительных структурах 2000 год, кандидат технических наук Иншаков, Дмитрий Юрьевич

  • Высокопроизводительные сопроцессоры для параллельной обработки данных в формате с плавающей точкой в системах цифровой обработки сигналов 2013 год, кандидат технических наук Пантелеев, Алексей Юрьевич

  • Исследование и организация эффективных вычислений в параллельных системах баз данных на основе сетей ЭВМ 2001 год, кандидат технических наук Маликов, Андрей Валерьевич

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В последнее время распространение получила математическая модель, представляющая базу данных в виде таблицы для булевой функции /: {0,1}" {0,1} (см., например, ). Запрос пользователя интерпретируется как входной набор х е {0,1}". Результатом запроса является значение f. Получены соответствующие оценки сложности. Однако, при вычислении булевой функции на нескольких независимых наборах возникает проблема, формулируемая следующим образом. Верно ли, что сложность такого вычисления булевой функции эквивалентна суммарной сложности независимого вычисления указанной функции на каждом входе, то есть, что индивидуальные вычисления не пересекаются? Впервые такая задача была рассмотрена в на основе схем из функциональных элементов, причем был получен отрицательный ответ на предыдущий вопрос. Общая постановка описанной проблемы, получила название Direct Sum Problem и успешно исследовалась в литературе. В случае сложности связи (communication complexity) был также получен отрицательный ответ на Direct Sum Problem . Зато в случае сложности монотонных схем (monotone circuit size complexity) и в случае сложности булевых деревьев решений (boolean decision trees) ответ был положителен.

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

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

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

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

Дальнейшее развитие методы из получили в работах . Все данные работы посвящены проблеме организации распределения набора данных по модулям памяти в так называемых машинах с распределенной памятью (DMM - Distributed Memory Mashine) или параллельных модульных компьютерах (Module Parallel Computer) . Главным ограничением указанной задачи является допуск одновременного доступа к любому модулю памяти только одного процессора, то есть отсутствие конфликтов доступа к памяти. Легко видеть, что данное ограничение очень похоже на главное ограничение алгоритма из , откуда и следуют сходные методы решения указанных задач. Ранее проблема организации распределения данных по модулям памяти, как правило, решалась путем моделирования PRAM алгоритмов на DMM модели , что обеспечивало эффективность решения только в предположении об относительно небольшом объеме распределяемых данных. Методы же обеспечивают эффективное решение в случае большого количества распределяемых данных, причем без конфликтов доступа к памяти при выполнении запросов. Отметим, что в и была затронута проблема уменьшения числа процессоров в используемых алгоритмах, но только для конкретного типа задач.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Похожие диссертационные работы по специальности «Дискретная математика и математическая кибернетика», 01.01.09 шифр ВАК

  • Методы и алгоритмы автоматизированного проектирования параллельных вычислительных процессов с учетом загрузки регистровой памяти суперскалярных процессоров 2002 год, кандидат технических наук Михеева, Людмила Борисовна

  • Теория и методы реализации массивных вычислений в итеративно-битовых СБИС-структурах 1998 год, доктор технических наук Князьков, Владимир Сергеевич

  • Методы обращения дискретных функций с применением двоичных решающих диаграмм 2010 год, кандидат физико-математических наук Игнатьев, Алексей Сергеевич

  • Математическое моделирование и синтез вычислительных и управляющих логических устройств 2004 год, доктор технических наук Чебурахин, Игорь Федорович

  • Оптимизация межресурсного обмена при сборке данных в распределённых GRID-вычислениях на основе сетевых и суперкомпьютерных технологий 2012 год, кандидат технических наук Амиршахи Бита

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Назаров, Максим Николаевич, 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.

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.

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

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

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

Образование:

В 1994 г. с отличием окончил Волгоградский государственный университет по специальности «Прикладная математика».

В 2003 г. защитил кандидатскую диссертацию «Параллельное вычисление булевых функций как модель доступа к распределенным информационным ресурсам» в Саратовском государственном университете имени Н.Г. Чернышевского, с присвоением ученой степени кандидата физико-математических наук.

В 2005 г. присвоено звание «доцент».

Курсы переподготовки и повышения квалификации:

2004 г. — курсы повышения квалификации в Пилотном центре УФК Минфина России по Волгоградской области по программе «Администратор безопасности информации ЛВС».

2008 г. — обучение по программе «Экспертиза качества профессионального образования» со специализацией «эксперт по тестированию» Рособрнадзора.

2009 г. — повышение квалификации по программе «Основы инновационной деятельности ВУЗа» в Московской академии государственного и муниципального управления.

2012 г. — повышение квалификации по программе «Вопросы создания электронного правительства и перевода государственных услуг субъектов Российской Федерации» в РАНХиГС.

Читает курс лекций:

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

Сфера научных интересов:

Дискретная математика; математическая кибернетика; сложность алгоритмов; базы данных; хранение и поиск информации; распределенные вычисления; криптография; PIR-протоколы; алгоритмы сжатия данных; обеспечение информационной безопасности экономических систем; экспертиза качества образования.

Опыт работы:

1995-1999 гг. - Качинское высшее военное авиационное училище летчиков, старший преподаватель кафедры математики.

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

2008-2012 гг. проректор по учебной работе Волгоградской академии государственной службы.

2012-2013 гг. - Волгоградский филиал РАНХиГС, заместитель директора Волгоградского филиала РАНХиГС.

2013 г. - н.в. - проректор РАНХиГС.

Работает в Академии: с 1999 г.

Общий стаж работы: с 1995 г.