Содержание к диссертации
Введение
1 Аналитический обзор. математические модели хранения и обработки больших объемов информации 13
1.1 Анализ моделей вычислений в больших диапазонах 16
1.2 Анализ моделей хранения и доступа к данным 23
1.3 Анализ моделей распределенной обработки данных 30
1.4 Обоснование целесообразности применения системы остаточных классов для вычислений в больших диапазонах и обработки больших объемов информации в распределенных системах 38
1.5 Постановка задач исследования 48
Выводы по главе 1 50
2 Разработка математических моделей распределенного хранения и обработки данных 51
2.1 Разработка принципов построения математических моделей хранения и обработки высокоразрядных данных 52
2.2 Разработка математической модели распределенного хранения данных большой размерности на основе модулярной арифметики и аппарата пороговых схем 58
2.3 Разработка математической модели распределенной обработки данных большой размерности на основе модулярной арифметики и аппарата пороговых схем 70
Выводы по главе 2 79
3 Разработка программного комплекса распределенного хранения и обработки данных высокой размерности 80
3.1 Разработка структуры программного комплекса распределенного хранения и обработки данных 82
3.2 Применение векторной обработки данных для вычислений в больших диапазонах 87
3.3 Оценка производительности и отказоустойчивости распределенных систем хранения и обработки данных, функционирующих на основе аппарата пороговых схем 103
Выводы по главе 3 115
Заключение 117
Список литературы 120
Приложение
- Обоснование целесообразности применения системы остаточных классов для вычислений в больших диапазонах и обработки больших объемов информации в распределенных системах
- Разработка математической модели распределенного хранения данных большой размерности на основе модулярной арифметики и аппарата пороговых схем
- Разработка математической модели распределенной обработки данных большой размерности на основе модулярной арифметики и аппарата пороговых схем
- Применение векторной обработки данных для вычислений в больших диапазонах
Введение к работе
Актуальность работы. Задачи факторизации, тестирования и определения простоты чисел специального вида, системы спутниковой навигации, и многие другие ресурсоемкие задачи требуют обработки больших объемов информации в широком диапазоне с высокой достоверностью и точностью вычислений. Как правило, подобные задачи сводятся к вычислительным проблемам, оперирующим целочисленными переменными, значения которых на несколько порядков превышают максимум машинного диапазона.
Для решения многих прикладных и теоретических проблем необходимо проведение вычислений уже в сверхбольших диапазонах, которые, с одной стороны, являются обобщением больших диапазонов, но в то же время принципиально отличаются от последних. Так как вычисления в них должны проводиться над потенциально бесконечными математическими объектами, их явные числовые записи невозможно или нецелесообразно хранить в памяти по причине принципиальной недостаточности вычислительных ресурсов, в результате чего в один момент времени возможны хранение и обработка лишь одного элемента представления. При таком подходе к распределенному хранению и обработке данных высокой размерности неизбежно повышается вероятность потери части представления числа. Выход из строя даже незначительного количества узлов вкупе с высокой трудоемкостью алгоритмов обработки чисел из большого и сверхбольшого диапазонов может привести к серьезным и сложно решаемым проблемам восстановления.
Параллельные вычислительные структуры являются идеальной основой для построения устойчивых к отказам вычислительных средств. Ключевую роль в процессе функционирования таких вычислительных устройств играет способность сохранения работоспособного состояния за счет снижения в допустимых пределах каких-либо показателей качества при возникновении сбоев и отказов в системе. Достоинство данного подхода к выполнению процедур обеспечения отказоустойчивости реализуется в полной мере при перераспределении исходных данных между сохранившимися вычислительными ресурсами при деградации системы. Однако, существующие методы обеспечения достоверности передачи и обработки данных высокой размерности не лишены недостатков, среди которых
4 можно отметить излишнюю избыточность, повышенные требования к среде передачи, низкую эффективность средств локализации и устранения сбоев, особенно в случае пакетирования ошибок.
В то же время, на фоне развития сетевых технологий и увеличения объемов обрабатываемых данных, все большее значение приобретает разработка технологий высоконадежного хранения данных и удаленного высокоскоростного доступа к ним, средств и методов управления нагрузкой серверов и каналов связи. Размеры многих локальных сетей достигают значений, при которых подобные сети по техническим и топологическим характеристикам мало отличаются от глобальных. Проблемы хранения информации и обеспечения доступа к ней в глобальных и локальных сетях и вычислительных системах приобретают одинаковый характер и требуют единого подхода к их решению.
В связи с вышеизложенным, проводимое в работе комплексное исследование научной и технической задачи повышения достоверности и быстродействия систем распределенного хранения и обработки данных высокой разрядности с применением технологии математического моделирования и вычислительного эксперимента, является важным и актуальным.
Целью диссертационного исследования является повышение отказоустойчивости вычислительных структур хранения и обработки данных большой размерности.
Объектом диссертационного исследования являются распределенные системы хранения и обработки данных высокой разрядности.
Предметом диссертационных исследований являются математические модели хранения и обработки больших массивов данных большой размерности.
Научная задача исследований заключается в разработке математических моделей хранения и параллельных вычислительных структур для обработки больших массивов данных с высокой степенью достоверности. В решении поставленной общей научной задачи можно выделить следующие частные задачи:
1. Разработка математических моделей распределенного хранения и обработки данных высокой размерности на основе пороговых схем и модулярной арифметики.
Разработка алгоритмов и программных реализаций модели хранения данных высокой размерности.
Разработка высокопроизводительных алгоритмов обработки данных в большом диапазоне с высокой степенью достоверности.
Комплексное исследование задачи повышения отказоустойчивости вычислительных структур распределенного хранения и обработки данных высокой разрядности с применением технологии математического моделирования и вычислительного эксперимента.
Методы исследования. Для решения поставленных в диссертационной работе задач использованы методы математического моделирования, теории чисел, абстрактной и линейной алгебры, теории параллельных вычислений, криптографии, комбинаторики, теории кодирования, теории функций случайных аргументов.
Достоверность и обоснованность полученных в диссертационной работе результатов и формулируемых на их основе выводов обеспечивается строгостью выполненных математических выкладок, базирующихся на аппарате теории чисел, абстрактной и линейной алгебры, криптографии. Справедливость выводов по эффективности разработанных математических моделей и вычислительных структур подтверждена результатами компьютерного моделирования, а также результатами тестирования программных реализаций разработанных алгоритмов.
Научная новизна диссертационной работы заключается в следующем:
1. Разработаны математические модели хранения и обработки данных
большой разрядности, отличающиеся от известных тем, что для их построения
впервые используются совместно математический аппарат пороговых схем и
модулярной арифметики, позволяющие распределить информацию о хранимых
больших числах по узлам распределенной вычислительной системы, обеспечить
сборку данных с высокой степенью достоверности за счет введения регулируемой
избыточности.
2. Разработан модифицированный алгоритм «разборки» числовой
последовательности высокой размерности, отличающийся от известных тем, что
для повышения скорости вычислений при малых значениях к и характеристике
конечного поля, не превосходящей 2-10 , используется метод вычисления обратной матрицы, основанный на рекурсивной блочной схеме умножения матриц
в формате кватернарного дерева, а для значений к > 64 применяется алгоритм Штрассена, сокращающий трудоемкость до 0(п 82) против 0(п) для традиционного метода.
3. Разработан модифицированный алгоритм «сборки» числовой
последовательности высокой размерности, отличающийся от известных тем, что
сборка производится в модулярном коде, позволяющем распараллелить
вычислительный процесс по модулям системы остаточных классов, что повышает
отказоустойчивость и быстродействие системы. Оценка производительности
алгоритма показала повышение показателя ускорения в среднем на 14-32% (в
зависимости от разрядности используемых типов данных) по сравнению с
аналогичными показателями для традиционно используемого алгоритма.
4. Разработан программный комплекс распределенного хранения и
обработки данных, базирующийся на пороговых схемах и модулярных кодах,
обеспечивающий, как следствие, высокую степень достоверности и
отказоустойчивости, в частности, введение дополнительной единицы
избыточности повышает вероятность безотказной работы системы за расчетный
период в среднем на 20%.
5. Библиотека функций для реализации операций с данными большой
размерности разработана впервые на аппаратной базе нейропроцессора NM6403 и
обеспечивает возможность исследования методом вычислительного эксперимента
на базе векторно-матричных процессоров функций отказоустойчивости систем
хранения данных большой размерности и достоверности их обработки. Анализ
производительности функций обработки больших чисел (на примере функции
вычисления произведения) показал повышение быстродействия в среднем на 47%
для чисел до 10240 десятичных разрядов, и на 16% для чисел большей
размерности.
Теоретическая значимость исследования состоит в разработке математических моделей хранения и обработки данных большой разрядности с высокой степенью достоверности.
Практическая значимость исследования. Реализация разработанных моделей в распределенных вычислительных системах существенным образом повышает достоверность хранения и обработки данных высокой размерности, поэтому полученные результаты могут быть использованы при решении задач
7 факторизации, тестирования и определения простоты чисел специального вида, разработки систем спутниковой навигации, других ресурсоемких задач, требующих обработки больших объемов информации в широком диапазоне с высокой достоверностью и скоростью вычислений. Основные положения, выносимые на защиту:
Математическая модель распределенного хранения данных большой разрядности с высокой степенью достоверности, базирующаяся на аппарате пороговых схем и модулярной арифметики.
Модифицированный параллельный алгоритм разборки числовой последовательности высокой размерности.
Математическая модель распределенной обработки данных большой разрядности с высокой степенью достоверности, базирующаяся на аппарате пороговых схем и модулярной арифметики.
Модифицированный параллельный алгоритм сборки числовой последовательности высокой размерности.
Программный комплекс распределенного хранения и обработки данных в большом диапазоне.
Параллельные алгоритмы действий с данными большой разрядности и библиотека функций их реализации на аппаратной базе нейропроцессора NM6403.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на VIII Всероссийском симпозиуме по прикладной и промышленной математике (Сочи-Адлер, 2007), Applied Mathematics, Statistics and Informatics (Trnava, 2007), международной научной конференции «Наука и технологии: актуальные проблемы 2007» (Ставрополь, 2007), международной научно-технической конференции «Инфокоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2008), международной научной конференции «Актуальные проблемы и инновации в экономике, управлении, образовании, информационных технологиях 2009» (Ставрополь-Кисловодск, 2009).
Публикации. По содержанию и результатам диссертационной работы опубликовано 12 работ, в том числе 2 статьи в периодических научных изданиях, рекомендованных ВАК РФ, 1 статья в тематическом журнале, 6 материалов в сборниках по итогам проведения международных и всероссийских конференций, 2
8 работы, депонированные в ВИНИТИ, 1 свидетельство о государственной регистрации программы для ЭВМ.
Реализация и внедрение. Результаты диссертационной работы получены при выполнении НИР по теме «Разработка алгоритмических и программных решений совершенствования информационных технологий» (номер государственной регистрации 0120.0851960) в рамках программы «Участник молодежного научно-инновационного конкурса» («У.М.Н.И.К.») (государственный контракт №6019р/8509 от 16.06.2008). Полученные в диссертационной работе результаты использованы в ООО НПФ «Нейрон» (г. Ставрополь, акт о внедрении от 2 марта 2009 г.), ВГУП НИИ программных средств (г. Санкт-Петербург, акт о внедрении от 15 апреля 2009 г.), ЗАО НТЦ «Модуль» (г. Москва, акт о внедрении от 9 апреля 2009 г.).
Структура и объем диссертации. Работа состоит из введения, трех разделов, списка используемых источников, содержащего 200 наименований, заключения и приложений. Основная часть работы содержит 119 листов машинописного текста.
Обоснование целесообразности применения системы остаточных классов для вычислений в больших диапазонах и обработки больших объемов информации в распределенных системах
Сегодня размеры многих локальных сетей достигают таких значений, что подобные сети по техническим и топологическим характеристикам мало отличаются от глобальных. Таким образом, проблемы хранения информации и обеспечения доступа к ней в глобальных и локальных сетях приобрели одинаковый характер и требуют единого подхода к их решению. В то же время существующие технологии построения распределенных сетей хранения данных предлагают различные по своей сути подходы. Наиболее перспективными технологиями построения хранилищ данных сегодня признаны сетевые устройства хранения SAN (Storage Area Network) [157], устройства прямого подключения к серверам DAS (Direct Attached Storage) и устройства, подключаемые через интернет NAS (Network Attached Storage). В локальных сетях преимущественно используется архитектура SAN, в глобальных-NAS [182, 197]. Система DAS подключена напрямую к серверу, поэтому ее также называют SAS (Server Attached Software). Другие серверы могут получить доступ только через сервер владельца. Внешний RAID-массив подключается к одному или нескольким серверам через SCSI или FC (Fibre Channel), причем каждый из таких портов доступен лишь одному серверу [181]. Основное преимущество SAS перед другими вариантами — низкая стоимость и высокое быстродействие (при расчете - одна система хранения данных для одного сервера). При относительно низкой стоимости оборудования SAS системы хороши для хранения потоковых мультимедиа данных благодаря высокой скорость обмена с дисками, а также возможности построения емких систем. Традиционное хранение данных, предполагающее прямое подключение к серверу, имеет ряд существенных недостатков [160, 187]. Так как в SAS для передачи данных используются локальная сеть, то при подключении нескольких серверов с системами хранения нагрузка на локальную сеть сильно возрастает.
Поэтому пользователи длительное время не смогут получить информацию. Решения SAS, также, не позволяют нескольким серверам совместно использовать файлы данных. Кроме того, они ограничены небольшим расстоянием подключения сервера к системам хранилищ данных. И все же, на сегодняшний день многие заказчики предпочитают решения SAS, так как одним из основных преимуществ этого решения является невысокая стоимость. В системе SAS защита информации ограничена возможностями ОС: это разграничение прав доступа к объектам и специализированное ПО (антивирусные системы, криптографические инструменты). Все это накладывает существенные ограничения на производительность и надежность [161,168]. Представляя собой дальнейшее развитие модели DAS, SAN предлагает доступ к файлам на уровне блочного устройства. Если для DAS характерны ограниченная масштабируемость, сложность управления и повышенная опасность возникновения узких мест на серверах и в локальных сетях, то классическая SAN обеспечивает резервные пути между клиентами и устройством хранения, а также удаленное зеркалирование на случай сбоев и резервное копирование, не снижающее производительность работы серверов приложений и базовой сети [81]. Кроме того, в SAN системах можно консолидировать хранилища, упростив таким образом управление ими. Централизованное управление объединенным пулом хранилищ зачастую более эффективно, чем отдельными напрямую подключенными подсистемами хранения [111, 112]. По мере необходимости можно легко выделять место в объединенном пуле, что упрощает администрирование и позволяет оптимизировать хранение данных.
Основное преимущество такой модели хранения — максимальная производительность и эффективность использования ресурсов путем их объединения и централизованного управления данными и ресурсами хранения [94]. Стандартом де-факто для SAN стала технология Fibre Channel, обеспечивающая достижение производительности порядка 200 Мбайт/сек и позволяющая строить распределенные хранилища данных масштаба предприятия [150]. Благодаря использованию Fibre Channel в решениях SAN удалось добиться максимальной защиты информации. Набор встроенных в сеть SAN инструментов включает аутентификацию хостов путем процедур Fabric Login и Process Login, управление доступом хостов к целям с помощью разбиения на зоны и списков доступа, и что не менее важно — технологию VSAN. Последняя делит сеть SAN на множество виртуальных коммутирующих структур.
Разработка математической модели распределенного хранения данных большой размерности на основе модулярной арифметики и аппарата пороговых схем
На сегодняшнем уровне технического развития эффективное объединение более 20-30 процессоров на основе общей памяти затруднительно. Каждый процессор должен иметь физический доступ к каждому из блоков оперативной памяти. Например, при использовании раздельных 32-разрядной адресной шины и 64-разрядной шины данных требуется минимум 96-разрядная высокоскоростная линия доступа к памяти от каждого процессора, что само по себе уже представляет технологическую проблему. Необходимость обеспечения обмена со скоростью 500 Мбайт/с и выше ограничивает физическое расстояние от каждого процессора до каждого блока памяти. Как правило, системы с общей памятью действительно выглядят достаточно компактно, размещаясь в одном корпусе. Этот фактор ограничивает общее число процессоров числом блоков, которые можно разместить в пределах, заданных максимальным расстоянием от блока памяти до процессора. Но есть и более существенные ограничения. В принципе, общая память предполагает возможность всех процессоров одновременно прочесть или записать разные данные из одного и того же блока памяти. Для этого каждый блок памяти должен обладать числом точек входа, равных числу процессоров, что технически сегодня нереализуемо.
Ряд современных систем построен по кластерному принципу: процессоры и оперативная память разбиваются на несколько групп кластеров [14, 145-148]. Внутри кластера процессоры имеют быстрый доступ к оперативной памяти. Доступ процессоров одного кластера к оперативной памяти, расположенной в другом кластере, также возможен, но время доступа при этом значительно возрастает [22, 27].
Конфликты, неизбежно возникающие при записи разными процессорами одних и тех же данных, носят фундаментальный характер и снижают производительность системы за счет потерь на синхронизацию, независимо от конкретной аппаратной реализации системы [123-125, 196]. Сказанное выше приводит к тому, что сконструированная система, как правило, не предусматривает возможности существенного наращивания числа процессорных узлов и приводит к крайне высокой, относительно систем с раздельной памятью, стоимости.
Масштабируемые системы массового параллелизма с раздельной памятью конструируют на основе объединения каналами передачи данных процессорных узлов, обладающих своей локальной оперативной памятью, недоступной другим процессорам [62, 63]. Обмен данными между процессорами при таком подходе возможен лишь с помощью сообщений, передаваемых по каналам связи. Такая схема обладает рядом преимуществ по сравнению с системами, построенными на основе общей памяти [43, 55]. Основными преимуществами систем с распределенной памятью являются: сравнительно низкая стоимость - наилучший показатель отношения цена/производительность; масштабируемость - возможность построения систем требуемой производительности, и наращивания их мощности за счет установки дополнительных процессоров.
Системы с раздельной памятью, по-видимому, всегда будут лидировать по показателю пиковой производительности, поскольку любые новые однопроцессорные (или многопроцессорные на основе общей памяти) системы могут быть легко объединены сетью и использованы в качестве многопроцессорных комплексов с раздельной памятью. Но, к сожалению, эффективное использование систем с распределенной памятью требует значительных усилий со стороны разработчиков прикладного обеспечения и возможно далеко не для всех типов задач. Для широкого круга хорошо зарекомендовавших себя последовательных алгоритмов до сих пор не удается построить эффективные параллельные аналоги [89-93].
С распространением локальных сетей получили свое развитие кластеры рабочих станций. Как правило, они представляют собой объединение небольшого числа ЭВМ. Являясь сравнительно дешевым решением, эти системы часто проигрывают в эффективности обработки прикладных задач специализированным системам по следующим основным причинам [84, 88]: ряд распространенных локальных сетей (Ethernet, Token Ring) не поддерживают одновременную передачу данных между различными парами компьютеров в пределах одного сегмента сети. Это означает, что данные между компьютерами С и D могут быть переданы только после передачи данных между компьютерами А и В, что уменьшает и без того не очень высокую скорость передачи данных в таких сетях [18, 29]; практически всегда на рабочих станциях, составляющих кластер, продолжают выполняться последовательные задания пользователей. В результате менее загруженные процессоры вынуждены ожидать более загруженные, что приводит к общему снижению производительности кластера при решении параллельной задачи до уровня, определяемого самой загруженной машиной. Эффективное решение этой задачи в условиях динамически изменяющейся, причем вне всякой зависимости от собственно параллельной программы, загруженности процессоров, представляется на сегодня весьма проблематичным; наличие в сети файловых серверов приводит к нерегулярно изменяющемуся объему данных, передаваемых через локальную сеть, что может значительно увеличивать время обмена сообщениями между процессорами увеличивая интервалы простоя последних.
Рассмотренные модели распределенной обработки данных позволяют обрабатывать большие массивы данных с достаточно высокой скоростью за счет параллельного выполнения. Однако, используемые средства? обеспечения отказоустойчивости обладают рядом существенных недостатков, делающих исследованные модели мало или вовсе непригодными для распределенной обработки данных из больших диапазонов.. Среди таких недостатков можно выделить значительные аппаратные и; программные затраты, необходимые для обеспечения отказоустойчивости, сложность реализации процедур поиска и локализации ошибок в процессе вычислений, необходимость перезапуска после; восстановления работоспособной структурной конструкции вычислительной системы, что - неприемлемо при1 выполнении задачи в масштабе реального1 времени [5, 6].
Разработка математической модели распределенной обработки данных большой размерности на основе модулярной арифметики и аппарата пороговых схем
1. Исследованы методы повышения быстродействия и достоверности систем распределенного хранения данных, основанных на аппарате пороговых схем (на примере схемы разделения секрета Шамира). Описаны основные понятия используемого математического аппарата — схемы разделения секрета и непозиционные коды, в частности, коды системы остаточных классов. Сформулированы ключевые преимущества и недостатки схем разделения секрета как моделей распределенного хранения данных.
2. Проведен анализ факторов, влияющих на производительность распределенных систем обработки данных. Показано, что при обработке больших объемов данных высокой размерности велика вероятность частичной потери передаваемой информации. Обосновано введение регулируемой избыточности системы хранения, позволяющей осуществлять эффективное восстановление данных в случае выхода из строя одного и более узлов.
3. Разработаны математические модели распределенного хранения и обработки данных большой размерности, базирующиеся на аппарате пороговых схем и обеспечивающие высокую степень достоверности. 4. Для построения математических моделей используется аппарат модулярной арифметики, что позволяет добиться существенного повышения коэффициента ускорения и отказоустойчивости предложенных алгоритмов, открывает перспективы их использования в системах реального времени.
5. Разработаны пути повышения быстродействия, точности и достоверности вычислений. Для повышения скорости вычислений при малых значениях к и характеристике конечного поля, не превосходящей 2-10 , используется метод вычисления обратной матрицы, основанный на рекурсивной блочной схеме умножения матриц в формате кватернарного дерева, для значений к 64 применяется алгоритм Штрассена, сокращающий трудоемкость до 0(п827) против 0(п) для традиционного метода.
Одним из основных организационных принципов, ведущих к повышению быстродействия, является идея одновременного выполнения нескольких команд, приводящая к концепции векторной обработки данных. Для увеличения количества выполняемых за один цикл операций необходимо на одной платформе разместить несколько функциональных модулей обработки и обеспечить надежное параллельное исполнение машинных инструкций, что дает возможность включить в работу все модули одновременно. Надежность в таком контексте означает, что результаты вычислений будут правильными. Исследование факторов, оказывающих влияние на корректность параллельной обработки, показывает, что повышение степени параллелизма выполнения операций в рамках традиционного подхода неизбежно приводит к уменьшению достоверности вычислений. В то же время, при использовании остаточных кодов, обладающих высокими корректирующими свойствами, арифметичностью и возможностью обнаружения и исправления пакетов ошибок, параллельные вычислительные структуры становятся идеальной основой для построения устойчивых к отказам вычислительных средств. Ключевую роль в процессе функционирования таких вычислительных устройств играет способность сохранения работоспособного состояния за счет снижения в допустимых пределах каких-либо показателей качества при возникновении сбоев и отказов в системе. Достоинство данного подхода к выполнению процедур обеспечения отказоустойчивости реализуется в полной мере при перераспределении исходных данных между сохранившимися вычислительными ресурсами при деградации системы.
Проведенное комплексное исследование факторов, влияющих на производительность систем, функционирующих на основе аппарата пороговых схем, выявило основные узкие места рассматриваемого алгоритма. Были предложены методы повышения достоверности и производительности системы за счет применения параллельных методов вычислений, обосновано использование модулярной арифметики, разработаны алгоритмы, реализующие предложенные математические модели.
Применение векторной обработки данных для вычислений в больших диапазонах
1. Исследованы факторы, влияющие на производительность векторной обработки данных большой размерности, проведено компьютерное моделирование разработанных алгоритмов повышения производительности и достоверности систем хранения и обработки данных высокой размерности на аппаратной базе векторных процессоров. 2. Произведены обоснование и выбор основных технологий, используемых для программной реализации разработанной математической модели распределенного хранения и обработки данных большой размерности. Создан прототип разрабатываемого программного комплекса. Осуществлено непосредственное кодирование разработанных алгоритмов с учетом результатов, полученных на этапе анализа прототипа. 3. Разработан программный комплекс распределенного хранения и обработки данных, базирующийся на пороговых схемах и модулярных кодах, обеспечивающий высокую степень достоверности и отказоустойчивости. 4. Разработана библиотека функций для реализации действий с данными большой размерности на аппаратной базе нейропроцессора NN46403. 5. Проведенный анализ отказоустойчивости, опирающийся на метод расчета надежности параллельных структур на основе аппарата функций случайных аргументов с использованием О распределения, показал, что введение дополнительной единицы избыточности повышает вероятность безотказной работы системы за расчетный период в среднем на 20%. Таким образом, дополнительная избыточность хранимой информации оправдывается повышенной безотказностью системы и представляется целесообразной. На основе анализа производительности наиболее трудоемкой части общего алгоритма (вычисление Л Я,) для вычислительной системы из 32 узлов были получены следующие значения показателя ускорения: 19,63 для 16-разрядных операндов, 9,91 для 32115 разрядных операндов, что превосходит аналогичные показатели для традиционно используемых алгоритмов в среднем на 32% и 14% соответственно. Анализ производительности функций обработки больших чисел (на примере функции вычисления произведения) показал повышение быстродействия в среднем на 47% для чисел до 10240 десятичных разрядов, и на 16% для чисел большей размерности. Основные результаты, полученные в диссертационной работе, можно сформулировать следующим образом: 1.
Показано, что успешное развитие сетевой инфраструктуры, средств и методов сетевого взаимодействия, повышения производительности вычислительных систем в целом непосредственно связано с разработкой математических моделей достоверного распределенного хранения и обработки данных большой размерности, высокоскоростных алгоритмов доступа к ним. 2. Исследованы методы повышения быстродействия и достоверности систем распределенного хранения данных, основанных на аппарате пороговых схем. Сформулированы ключевые преимущества и недостатки пороговых схем как моделей распределенного хранения данных. 3. Проведен анализ факторов, влияющих на производительность распределенных систем обработки данных. Показано, что при обработке больших объемов данных высокой размерности велика вероятность частичной потери передаваемой информации. Обосновано введение регулируемой избыточности системы хранения, позволяющей осуществлять эффективное восстановление данных в случае выхода из строя одного и более узлов. 4. Разработаны пути повышения быстродействия и достоверности вычислений. Для повышения скорости вычислений при малых значениях к и о характеристике конечного поля, не превосходящей 2-10 , используется метод вычисления обратной матрицы, основанный на рекурсивной блочной схеме умножения матриц в формате кватернарного дерева, а для значений к 64 применяется алгоритм Штрассена, сокращающий трудоемкость до 0(п1ё27) о против 0(п ) для традиционного метода. 5. Обосновано, что система остаточных классов, благодаря внутреннему параллелизму, модульности, возможности арифметической коррекции ошибок, является наиболее подходящей основой для реализации высокоскоростных алгоритмов достоверной обработки данных большой размерности в распределенных компьютерных системах. 6.
Разработаны математические модели распределенного хранения и обработки данных большой размерности, базирующиеся на аппарате пороговых схем и обеспечивающие высокую степень достоверности. Для построения математических моделей используется аппарат модулярной арифметики, что позволяет добиться существенного повышения коэффициента ускорения и отказоустойчивости предложенных алгоритмов, открывает перспективы их использования в системах реального времени. 7. Предложены алгоритмы сборки и разборки числовой последовательности высокой размерности. На основе анализа производительности наиболее трудоемкой части алгоритма сборки для вычислительной системы из 32 узлов были получены следующие значения показателя ускорения: 19,63 для 16-разрядных операндов, 9,91 для 32-разрядных операндов, что превосходит аналогичные показатели для традиционно используемых алгоритмов в среднем на 32% и 14% соответственно. 8. Разработан программный комплекс распределенного хранения и обработки данных, базирующийся на пороговых схемах и модулярных кодах, обеспечивающий высокую степень достоверности и отказоустойчивости. 9. По результатам общего расчета отказоустойчивости сделан вывод, что введение дополнительной единицы избыточности повышает вероятность безотказной работы системы за расчетный период в среднем на 20%. 10. Исследованы факторы, влияющие на производительность векторной обработки данных большой и большой размерности. Проведено компьютерное моделирование разработанных алгоритмов повышения производительности и достоверности систем хранения и обработки данных высокой размерности на аппаратной базе векторных процессоров. 11. Разработана библиотека функций для реализации действий с данными большой и большой размерности на аппаратной базе нейропроцессора ЫМ6403. Анализ производительности функций обработки больших чисел (на примере функции вычисления произведения) показал повышение быстродействия в среднем на 47% для чисел до 10240 десятичных разрядов, и на 16% для чисел большей размерности.
