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

На правах рукописи

003473629

Алексеев Александр Иванович

РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ХРАНЕНИЯ И ОБРАБОТКИ ДАННЫХ БОЛЬШОЙ РАЗМЕРНОСТИ С ВЫСОКОЙ СТЕПЕНЬЮ ДОСТОВЕРНОСТИ

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Ставрополь - 2009

1 8 МОИ 2009

003473629

Работа выполнена в Северо-Кавказском государственном техническом университете на кафедре «Информационные системы и технологии»

Научный руководитель: кандидат физико-математических наук, доцент

Мезенцева Оксана Станиславовна

Официальные оппоненты1. доктор технических наук, профессор

Червяков Николай Иванович доктор технических наук, доцент Ирхин Валерий Петрович

Ведущая организация: Санкт-Петербургский государственный

электротехнический университет «ЛЭТИ», г. Санкт-Петербург

Защита состоится 1 июля 2009 года в 12 часов на заседании диссертационного совета Д 212.245.09 по присуждению ученой степени кандидата технических наук при Северо-Кавказском государственном техническом университете по адресу: 355028, г. Ставрополь, пр. Кулакова, 2, ауд. 305.

С диссертацией можно ознакомиться в библиотеке СевКавГТУ по адресу: 355028, г. Ставрополь, пр. Кулакова, 2; с авторефератом - на сайте www.ncstu.ru.

Автореферат разослан 29 мая 2009 года.

Ученый секретарь диссертационного совета кандидат физико-математических наук.

доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

Объектом диссертационного исследования являются распределенные системы хранения и обработки данных высокой разрядности.

Предметом диссертационных исследований являются математические модели хранения и обработки больших массивов данных большой размерности.

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

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

2. Разработка алгоритмов и программных реализаций модели хранения данных высокой размерности.

3. Разработка высокопроизводительных алгоритмов обработки данных в большом диапазоне с высокой степенью достоверности.

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

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

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

Научная новизна диссертационной работы заключается в следующем:

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

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

о

конечного поля, не превосходящей 2-10 , используется метод вычисления обратной матрицы, основанный на рекурсивной блочной схеме умножения матриц в формате кватернарного дерева, а для значений к> 64 применяется алгоритм Штрассена, сокращающий трудоемкость до 0(п'"1:27) против 0(п3) для традиционного метода.

3. Разработан модифицированный алгоритм «сборки» числовой последовательности высокой размерности, отличающийся от известных тем, что сборка производится в модулярном коде, позволяющем распараллелить вычислительный процесс по модулям системы остаточных классов, что повышает отказоустойчивость и быстродействие системы. Оценка производительности алгоритма показала повышение показателя ускорения в среднем на 14-32% (в зависимости от разрядности используемых типов данных) по сравнению с аналогичными показателями для традиционно используемого алгоритма.

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

5. Библиотека функций для реализации операций с данными большой размерности разработана впервые на аппаратной базе нейропроцессора ЫМ6403 и обеспечивает возможность исследования методом вычислительного эксперимента на базе векторно-матричных процессоров функций отказоустойчивости систем хранения данных большой размерности и достоверности их обработки. Анализ производительности функций обработки больших чисел (на примере функции вычисления произведения) показал повышение быстродействия в среднем на 47% для чисел до 10240 десятичных разрядов, и на 16% для чисел большей размерности.

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

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

Основные положения, выносимые на защиту:

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

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

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

4. Модифицированный параллельный алгоритм сборки числовой последовательности высокой размерности.

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

6. Параллельные алгоритмы действий с данными большой разрядности и библиотека функций их реализации на аппаратной базе нейропроцессора NM6403.

Апроба11ия работы. Основные положения диссертационной работы докладывались и обсуждались на VIII Всероссийском симпозиуме но прикладной и промышленной математике (Сочи-Адлер, 2007), Applied Mathematics, Statistics and Informatics (Trnava, 2007), международной научной конференции «Наука и технологии: актуальные проблемы 2007» (Ставрополь, 2007), международной научно-технической конференции

«Инфокоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2008), международной научной конференции «Актуальные проблемы и инновации в экономике, управлении, образовании, информационных технологиях 2009» (Ставрополь-Кисловодск, 2009).

Публикации. По содержанию и результатам диссертационной работы опубликовано 12 работ, в том числе 2 статьи в периодических научных изданиях, рекомендованных ВАК РФ, 1 статья в тематическом журнале, 6 материалов в сборниках по итогам проведения международных и всероссийских конференций, 2 работы, депонированные в ВИНИТИ, 1 свидетельство о государственной регистрации программы для ЭВМ.

Реализация и внедрение. Результаты диссертационной работы получены при выполнении НИР по теме «Разработка алгоритмических и программных решений совершенствования информационных технологий» (номер государственной регистрации 0120.0851960) в рамках программы «Участник молодежного научно-инновационного конкурса» («У.М.Н.И.К.») (государственный контракт №6019р/8509 от 16.06.2008). Полученные в диссертационной работе результаты использованы в ООО НПФ «Нейрон» (г. Ставрополь, акт о внедрении от 2 марта 2009 г.), ВГУП НИИ программных средств (г. Санкт-Петербург, акт о внедрении от 15 апреля 2009 г.), ЗАО НТЦ «Модуль» (г. Москва, акт о внедрении от 9 апреля 2009 г.).

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Показаны возможности итерационного вычисления большой величины С путем сведения соотношения:

где А, В, /(В) - большие числовые величины;

— сверхбольшая числовая величина; к форме сравнения по модулю Р>С: С(тойР) = {Агт{тойР) -[А/(3) /Д](то<1 Р) ■ В{гло6.Р))(тоАР), (2) где Р - диапазон модулярной арифметики С(тос1 Р). Обосновано, что система остаточных классов (СОК), благодаря внутреннему параллелизму, модульности, возможности арифметической коррекции ошибок, является наиболее подходящей базой для реализации высокоскоростных алгоритмов достоверной обработки данных большой размерности в распределенных компьютерных системах.

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

(1)

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

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

1. Построение СР(А'). Существует два основных метода построения конечных полей. Выбор того или иного варианта основывается на требуемом числе элементов поля. Для поля, содержащего р элементов, где р - простое, кольцо вычетов 2п (и = /;) является полем, и элементы 2р есть 0,1,...,р — 1. Для более реального в рассматриваемой ситуации случая вР(д), ц = р", где р -простое: К =Рр[л:]/{/(л")) является полем тогда и только тогда, когда /(х) есть многочлен, неприводимый над полем Ер, = рт ,т = .

2. Представление исходных данных в виде элементов Ы). Рассматривая ¿-мерное пространство векторов Ь над ОР(Щ, исходная последовательность данных может быть представлена в виде последовательности векторов из Ь: (1 = (/,,/2,...,/т)•

3. Построение набора векторов Е. Необходимо построить набор векторов Е из Ь, состоящий из п векторов так, что любые к из Е есть базис в I:

__п

1 <У</5л |Ы

(определитель Вандермонда).

4. Формирование матрицы АкЛ и нахождение обратной ей Л~1;

VвJ е £: (/,,^) - (4)

где е, - вектора построенного набора Е,

1, - элементы исходной последовательности данных. По условию формирования Е построенная матрица имеет обратную А''.

1 1 ... 1

Р\ Рг - Р.

и-1 п-1

Р\ Рг - Рп

5. Сборка последовательности. Выражение для сборки исходной последовательности имеет вид:

Д = (5)

где /, = /Г'.У(,

- столбец А, содержащий /-ыс компоненты всех мастей.

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

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

„ v1

л"' -Лсок ~

(б)

Н к2 — Ькк )

где с. - модулярные представления элементов векторов е1 е Е, соответствующих скалярным произведениям Е1 — (2^,е ).

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

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

Построение

Построение К-мерного просрЖ'ОТМ векторов

__ЕиядС^ЛЦ_

РоЛлемие исходной послвдоватепи'ости на гьОитныв части ..

ПоС1рое>1ио киОДа векгороо Е

Ър.ревВ(Ы),р*0-. {р'.р'.....р')

1 р, ... рГ1

1 р2 ... РГ1

|1 р„ ■•• рг

Формирование «•охримы А (к к к)

Разбиение ко б лежи

[А С\ В о

П -л-м а о ^

[о / ; 1>0 (О-ВА 'су1)

('. "Но 3

Разбиение на блоки

Л\ Аз1 Г^И

^ = Аа . х ^,

РЭ = Р1ХЛ2- А*^ 3 = =

X1

Перевод коэЭДнуивнтов матрицы о коды сиетймь! ктё'С'ных илассой

Л - (-((<У> + «м)Р + <•„., )Р + - + а, )р + о, в е Д цю<! р1 = а1 той р; (а^р + = Д то(1

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

Для значений к > 1286 повышение производительности может быть достигнуто применением алгоритма Штрассена для нахождения обратной матрицы. Трудоемкость алгоритма умножения Штрассена, на котором базируется одноименный метод отыскания обратной матрицы, составляет 0(п1о*г7) против О (г?) для традиционного метода. Используя модификации метода Штрассена для параллельных вычислений (алгоритм Штрассена-Ныотона), можно добиться существенного снижения порога значении А*, при котором становится целесообразным применение этого алгоритма (до к>64).

В зависимости от размерности матрицы, обращение производится одним из двух способов:

1. Для к <64: четыре квадратных блока, полученные в процессе разбиения исходной матрицы подвергаются повторному разбиению до тех пор, пока порядок блока не достигнет единицы. Результирующая структура является кватернарным деревом.

А =

А С

В О

-А~'С^

ОУ А-'

О

(7)

О /

,0 (О-ва-'СГ'Д-Я 1]{ 0

2. Для к >64: используется параллельная модификация алгоритма Штрассена для обращения матриц:

Р2 = А1ХХР,, рг = АП, РА = АПХР„ Р5 = Р<-А12, Р6 = Р;\

£-|2 = Х > £-21 = Х ¿2 > ^11 = ~ ^Ъ Х £-21 ' £-22 = '

(8)

ч Аг -1 "Си с 12

А А22_ с ."-21 ^22 _

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

к

А = акрк +акАрк'1 + ...+ +а0р", или А = ^а.р', V/: 0 < а, < /> -1, (9)

в виде

А = (...((акр +• ак_,)р + ак_2)р + ... + а,)р + аа ~ А, то Ар, - а] тос] р], (Ю) где (акр + аы)р = Ак то(1р..

Операция сборки базового метода (5) состоит из к2 операций умножения и сложения в поле Галуа, что в свою очередь представляет собой А-2 операций обычного сложения и обычного умножения и иг операции вычисления остатка от деления. Учитывая, что число тактов на выполнение операции вычисления остатка от деления для современных 8180-процессоров превышает число тактов на выполнение операции умножения в среднем в четыре раза, обосновано, что значительное увеличение общей трудоемкости алгоритма связано именно с этим участком вычислений. Использование математического аппарата системы остаточных классов позволяет существенно повысить быстродействие рассматриваемого участка.

Построенная математическая модель обработки числовой последовательности высокой разрядности имеет вид:

-1

Чь*1 ькг ■■■

А = и '«• А = и I,' ° = Ф*. © АII '--К ® Р1)'

(П)

(12)

А = рм

¿к, - ах 11'

+ ам >

ГЬ

где - столбец Л, содержащий ¡'-ые компоненты всех частей, О, = («,,...,«„), 02 — (Д ,...,/?„) - собранные операнды, р,,-.,р„ - система оснований СОК, © - модульная операция,

8 =

(Пй-Ам) м

Пй

(13)

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

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

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

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

Л = р,/,+а„ (14)

где /, показывает, сколько раз р1 укладывается в числе А, и выражении:

4 = /V

*К| - 4чГ<

Пл

(15)

Па

где 8, ~

(П л-д+.) -

Па

(р{х) - функция Эйлера.

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

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

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

Показано, что разработанные алгоритмы могут быть реализованы на любой аппаратной платформе, поддерживающей параллелизм операций, однако, наиболее эффективное отображение алгоритмических решений на аппаратную базу может быть получено при использовании разработки НТЦ «Модуль» - процессора Л1879ВМ1 (ЫМ6403), являющегося одной из наиболее высокопроизводительных моделей, реализующих 81МО-архитсктуру. Процессор NN16403 работает с машинными командами 32-х и 64-х разрядного формата и в этом смысле представляет собой суперскалярный микропроцессор со статической УЫ\У-архитектурой. Одной из важнейших особенностей процессора NN46403 является возможность работы с операндами произвольной длины в диапазоне 1-64 бит. Эта характеристика процессора особенно важна при рассмотрении ее в свете специфики используемого математического аппарата: оба уровня обеспечения параллелизма разработанного комплекса -вычисления в остаточных классах и механизм пороговых схем - позволяют динамически управлять нагрузкой узлов.

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

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

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

локализации и исправления ошибок. Аппаратно-логическая схема разработанной библиотеки приведена на рисунке 5. Код функций ориентирован па процессор N№16403, однако, благодаря совместимости коммуникационных портов процессоров ЫМ6403 и серии ТМ8320С4х, библиотека допускает расширение средствами других вычислительных устройств.

с:

1 |

1 V ■Л |

1 « 1

| с = 0 I

а)

б)

Рисунок 3 - Алгоритмы вычисления суммы (а) и произведения чисел (б) из большого диапазона

Определение разряда

Определение весов ортогональны* базисов 01,

Опред«ленно ортогональных базисов В(

>

р.™, в<

А",.....а,)

Рисунок 4 - Схема функции локализации и устранения ошибок

Рисунок 5 - Аппарагно-логическая схема библиотеки базовых арифметических функций для проведения вычислений в большом диапазоне

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

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

На основе анализа производительности наиболее трудоемкой части общего алгоритма (вычисление ) для вычислительной системы из 32 узлов были получены следующие значения показателя ускорения: 19,63 для 16-разрядных операндов, 9,91 для 32-разрядных операндов, что превосходит аналогичные показатели для традиционно используемых алгоритмов в среднем на 32% и 14% соответственно. Анализ производительности функций обработки больших чисел (на примере функции вычисления произведения) показал повышение быстродействия в среднем на 47% для чисел до 10240 десятичных разрядов, и на 16% для чисел большей размерности.

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

ЗАКЛЮЧЕНИЕ

Основные результаты, полученные в диссертационной работе, можно сформулировать следующим образом:

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

2. Исследованы методы повышения быстродействия и достоверности систем распределенного хранения данных, основанных на аппарате пороговых

схем. Сформулированы ключевые преимущества и недостатки пороговых схем как моделей распределенного хранения данных.

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

4. Разработаны пути повышения быстродействия и достоверности вычислений. Для повышения скорости вычислений при малых значениях к и характеристике конечного поля, не превосходящей 2108, используется метод вычисления обратной матрицы, основанный на рекурсивной блочной схеме умножения матриц в формате кватернарного дерева, а для значений к > 64 применяется алгоритм Штрассена, сокращающий трудоемкость до 0(п'"127) против О(п) для традиционного метода.

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

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

7. Предложены алгоритмы сборки и разборки числовой последовательности высокой размерности. На основе анализа производительности наиболее трудоемкой части алгоритма сборки для вычислительной системы из 32 узлов были получены следующие значения показателя ускорения: 19,63 для 16-разрядных операндов, 9,91 для 32-разрядных операндов, что превосходит аналогичные показатели для

традиционно используемых алгоритмов в среднем на 32% и 14% соответственно.

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

9. По результатам общего расчета отказоустойчивости сделай вывод, что введение дополнительной единицы избыточности повышает вероятность безотказной работы системы за расчетный период в среднем на 20%.

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

1 ¡.Разработана библиотека функций для реализации действий с данными большой и большой размерности па аппаратной базе нейропроцессора ИМ6403. Анализ производительности функций обработки больших чисел (на примере функции вычисления произведения) показал повышение быстродействия в среднем на 47% для чисел до 10240 десятичных разрядов, и на 16% для чисел большей размерности.

СПИСОК ОСНОВНЫХ РАБОТ ПО ТЕМЕ ДИССЕРАЦИИ

Статьи в периодических научных изданиях, рекомендованных ВАК РФ:

1. Алексеев, А. И. О реализации пороговых схем на базе системы остаточных классов [Текст] / А. И. Алексеев, О. С. Мезенцева // Обозрение прикладной и промышленной математики, том 15, выпуск 2-2008.

2. Мезенцева, О. С. Применение аппарата пороговых схем и модулярной арифметики для повышения производительности распределенных вычислительных систем [Текст] / О. С. Мезенцева, А. И. Алексеев // Научно-технические ведомости СПбГПУ №5 - 2008.

Статья в тематическом сборнике:

1. Мезенцева, О. С. О возможностях реализации модулярной арифметики на процессоре Л1879ВМ1 (№Л6403) [Текст] / О. С. Мезенцева, А, И. Алексеев //

Вестник Северо-Кавказского государственного технического университета №2 (11)2007.

Статьи в сборниках по итогам проведения международных научных конференций:

1. Mezentseva, О. Regarding the (N, k)-threshold schemes realization based on modular arithmetic algorithms [Текст] / О. Mezentseva, A. Alekscev // Journal of the Applied Mathematics, Statistics and Informatics (JAMSI), 3 (2007), No. 1.

2. Алексеев, А. И. Методы повышения быстродействия систем, функционирующих на основе пороговых схем [Текст] / А. И. Алексеев // Материалы международной научно-технической конференции «Инфокоммуникациоиные технологии в науке, производстве и образовании». Ставрополь, 2008.

3. Мезенцева, О. С. Применение системы остаточных классов для вычислений в сверхбольших диапазонах и обработки больших объемов информации в распределенных системах [Текст] / О. С. Мезенцева, А. И. Алексеев // Материалы III международной научной студенческой конференции «Научный потенциал студенчества в XXI веке». Ставрополь, 2009.

4. Алексеев, А. И. Оценка отказоустойчивости распределенных систем хранения и обработки данных, функционирующих на основе аппарата пороговых схем [Текст] / А. И. Алексеев, О. С. Мезенцева II Материалы международной научной конференции «Актуальные проблемы и инновации в экономике, управлении, образовании, информационных технологиях 2009», Ставрополь, 2009.

5. Алексеев, А. И. Применение векторной обработки данных для вычислений в сверхбольших диапазонах [Текст] / А. И. Алексеев, О. С. Мезенцева // Материалы международной научной конференции «Актуальные проблемы и инновации в экономике, управлении, образовании, информационных технологиях 2009», Ставрополь, 2009.

6. Мезенцева, О. С. О возможностях реализации модулярной арифметики на процессоре JI1879BM1 (NM6403) [Текст] / О. С. Мезенцева, А. И. Алексеев // Материалы международной научной конференции «Наука и технологии: актуальные проблемы 2007». Ставрополь 2007.

Работы, депонированные в ВИНИТИ:

1, Разработка математических моделей распределенного хранения и обработки данных [Текст] / Алексеев А. И.; Северо-Кавказский государственный технический университет. - Ставрополь, 2009. - 25 с. -Библиогр.: 8 назв. - Рус. Деп. в ВИНИТИ 250309, №160-В2009.

2. Вычисления в сверхбольших диапазонах и обработка больших объемов информации в распределенных системах [Текст] / Алексеев А. И.; Северо-Кавказский государственный технический университет. - Ставрополь, 2009. - 26 с. - Библиогр.: 10 назв. - Рус. Деп. в ВИНИТИ 250309, №161-В2009.

Свидетельство о государственной регистрации программы для ЭВМ:

1. Мезенцева О. С., Алексеев А. И. «Система распределенного хранения и обработки данных, базирующаяся на пороговых схемах и модулярных кодах», свидетельство о государственной регистрации программы для ЭВМ №2009610891 от 9 февраля 2009 г.

Печатается в авторской редакции

Подписано в печать 27.05.2009 Формат60x84 1/16 Усл. печ. л,- 1,5 Уч.-изд. л.- 1,0 Бумага офсетная. Печать офсетная. Заказ №254 Тираж 100 экз. ГОУ ВПО «Северо-Кавказский государственный технический университет» 355028, г. Ставрополь, пр. Кулакова, 2

Издательство Северо-Кавказского государственного технического университета Отпечатано в типографии СевКавГТУ

ВВЕДЕНИЕ.

1 АНАЛИТИЧЕСКИЙ ОБЗОР. МАТЕМАТИЧЕСКИЕ МОДЕЛИ

ХРАНЕНИЯ И ОБРАБОТКИ БОЛЬШИХ ОБЪЕМОВ

ИНФОРМАЦИИ.

1.1 Анализ моделей вычислений в больших диапазонах.

1.2 Анализ моделей хранения и доступа к данным.

1.3 Анализ моделей распределенной обработки данных.

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

1.5 Постановка задач исследования.

Выводы по главе 1.

2 РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

РАСПРЕДЕЛЕННОГО ХРАНЕНИЯ И ОБРАБОТКИ ДАННЫХ

2.1 Разработка принципов построения математических моделей 52 хранения и обработки высокоразрядных данных.

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

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

Выводы по главе 2.

3 РАЗРАБОТКА ПРОГРАММНОГО КОМПЛЕКСА

РАСПРЕДЕЛЕННОГО ХРАНЕНИЯ И ОБРАБОТКИ ДАННЫХ

ВЫСОКОЙ РАЗМЕРНОСТИ.

3.1 Разработка структуры программного комплекса распределенного хранения и обработки данных.

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

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

Выводы по главе 3.

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

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

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

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

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

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

Объектом диссертационного исследования являются распределенные системы хранения и обработки данных высокой разрядности.

Предметом диссертационных исследований являются математические модели хранения и обработки больших массивов данных большой размерности.

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

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

2. Разработка алгоритмов и программных реализаций модели хранения данных высокой размерности.

3. Разработка высокопроизводительных алгоритмов обработки данных в большом диапазоне с высокой степенью достоверности.

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

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

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

Научная новизна диссертационной работы заключается в следующем:

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

2. Разработан модифицированный алгоритм «разборки» числовой последовательности высокой размерности, отличающийся от известных тем, что для повышения скорости вычислений при малых значениях к и характеристике конечного поля, не превосходящей 2-108, используется метод вычисления обратной матрицы, основанный на рекурсивной блочной схеме умножения матриц в формате кватернарного дерева, а для значений к> 64 применяется алгоритм Штрассена, сокращающий трудоемкость до O(nlog2?) против 0(п3) для традиционного метода.

3. Разработан модифицированный алгоритм «сборки» числовой последовательности высокой размерности, отличающийся от известных тем, что сборка производится в модулярном коде, позволяющем распараллелить вычислительный процесс по модулям системы остаточных классов, что повышает отказоустойчивость и быстродействие системы. Оценка производительности алгоритма показала повышение показателя ускорения в среднем на 14-32% (в зависимости от разрядности используемых типов данных) по сравнению с аналогичными показателями для традиционно используемого алгоритма.

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

5. Библиотека функций для реализации операций с данными большой размерности разработана впервые на аппаратной базе нейропроцессора NM6403 и обеспечивает возможность исследования методом вычислительного эксперимента на базе векторно-матричных процессоров функций отказоустойчивости систем хранения данных большой размерности и достоверности их обработки. Анализ производительности функций обработки больших чисел (на примере функции вычисления произведения) показал повышение быстродействия в среднем на 47% для чисел до 10240 десятичных разрядов, и на 16% для чисел большей размерности.

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

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

Основные положения, выносимые на защиту:

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

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

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

4. Модифицированный параллельный алгоритм сборки числовой последовательности высокой размерности.

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

6. Параллельные алгоритмы действий с данными большой разрядности и библиотека функций их реализации на аппаратной базе нейропроцессора NM6403.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на VIII Всероссийском симпозиуме по прикладной и промышленной математике (Сочи-Адлер, 2007), Applied Mathematics, Statistics and Informatics (Trnava, 2007), международной научной конференции «Наука и технологии: актуальные проблемы 2007» (Ставрополь, 2007), международной научно-технической конференции «Инфокоммуникационные технологии в науке, производстве и образовании» (Ставрополь, 2008), международной научной конференции «Актуальные проблемы и инновации в экономике, управлении, образовании, информационных технологиях 2009» (Ставрополь-Кисловодск, 2009).

Публикации. По содержанию и результатам диссертационной работы опубликовано 12 работ, в том числе 2 статьи в периодических научных изданиях, рекомендованных ВАК РФ, 1 статья в тематическом журнале, 6 материалов в сборниках по итогам проведения международных и всероссийских конференций, 2 работы, депонированные в ВИНИТИ, 1 свидетельство о государственной регистрации программы для ЭВМ.

Реализация и внедрение. Результаты диссертационной работы получены при выполнении НИР по теме «Разработка алгоритмических и программных решений совершенствования информационных технологий» (номер государственной регистрации 0120.0851960) в рамках программы

Участник молодежного научно-инновационного конкурса» («У.М.Н.И.К.») (государственный контракт №6019р/8509 от 16.06.2008). Полученные в диссертационной работе результаты использованы в ООО НПФ «Нейрон» (г. Ставрополь, акт о внедрении от 2 марта 2009 г.), ВГУП НИИ программных средств (г. Санкт-Петербург, акт о внедрении от 15 апреля 2009 г.), ЗАО НТЦ «Модуль» (г. Москва, акт о внедрении от 9 апреля 2009 г.).

Структура и объем диссертаг\ии. Работа состоит из введения, трех разделов, списка используемых источников, содержащего 200 наименований, заключения и приложений. Основная часть работы содержит 119 листов машинописного текста. В первой главе на основе анализа российской и зарубежной литературы исследованы перспективные технологии построения хранилищ данных и модели распределенной обработки данных высокой размерности. Проведенный анализ позволил сделать вывод об отсутствии единого подхода к проектированию систем распределенного хранения и обработки данных. Большинство традиционных решений ориентировано на конкретный и зачастую довольно узкий спектр задач и характеризуется низкой масштабируемостью и рядом других существенных ограничений. Лишенные многих из этих недостатков системы с масштабируемой избыточностью также не имеют широкого распространения по причине сложности эксплуатации и недостаточной надежности. Показано, что успешное развитие сетевой инфраструктуры, средств и методов сетевого взаимодействия, повышения производительности вычислительных систем в целом непосредственно связано с разработкой математических моделей и алгоритмов достоверного распределенного хранения и обработки данных, высокоскоростных методов доступа к ним. Обосновано, что система остаточных классов, благодаря внутреннему параллелизму, модульности, возможности арифметической коррекции ошибок, является наиболее подходящей основой для реализации высокоскоростных алгоритмов достоверной обработки данных большой размерности в распределенных компьютерных системах.

Во второй главе предложены математические модели распределенного хранения и обработки данных большой размерности, базирующиеся на аппарате пороговых схем и обладающие высокой степенью достоверности и отказоустойчивости. Для построения моделей системы используется аппарат модулярной арифметики, что позволяет добиться существенного повышения коэффициента ускорения и отказоустойчивости предложенных алгоритмов, открывает перспективы использования разработанных моделей в системах реального времени. Исследованы методы повышения быстродействия и достоверности систем распределенного хранения данных, основанных на аппарате пороговых схем (на примере схемы разделения секрета Шамира). Описаны основные понятия используемого математического аппарата — схемы разделения секрета и непозиционные коды, в частности, коды системы остаточных классов. Сформулированы ключевые преимущества и недостатки схем разделения секрета как моделей распределенного хранения данных. Проведен анализ факторов, влияющих на производительность распределенных систем обработки данных. Показано, что при обработке больших объемов данных высокой размерности велика вероятность частичной потери передаваемой информации. Обосновано введение регулируемой избыточности системы хранения, позволяющей осуществлять эффективное восстановление данных в случае выхода из строя одного и более узлов. Разработаны пути повышения быстродействия, точности и достоверности вычислений. Для повышения скорости вычислений при малых о значениях к и характеристике конечного поля, не превосходящей 2-10 , используется метод вычисления обратной матрицы, основанный на рекурсивной блочной схеме умножения матриц в формате кватернарного дерева, для значений к> 64 применяется алгоритм Штрассена, сокращающий трудоемкость до 0(п1°82) против 0(п3) для традиционного метода.

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

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

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

АНАЛИТИЧЕСКИЙ ОБЗОР. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ХРАНЕНИЯ И ОБРАБОТКИ БОЛЬШИХ ОБЪЕМОВ ИНФОРМАЦИИ

В последние годы, на фоне бурного развития сетевых технологий с одной стороны, и резкого увеличения объемов обрабатываемых данных с другой, все большее значение приобретает разработка технологий высоконадежного хранения данных и удаленного высокоскоростного доступа к ним, средств и методов управления нагрузкой серверов и каналов связи. По данным исследования IDC, совокупный объем существующей цифровой информации к концу 2007 года составил 281 экзабайт (281 млрд. гигабайт), а к 2011 году этот показатель должен достигнуть значения 1800 экзабайт, причем более 95% цифровой среды на настоящий момент состоит из неструктурированных данных. По прогнозам экспертов Cisco к 2012 году среднемесячный объем глобального IP-трафика достигнет уровня 44 экзабайт. Приводимые в документе Cisco VNI данные свидетельствуют о том, что в период с 2007 по 2012 год объем IP-трафика будет ежегодно увеличиваться на 46 процентов, то есть практически удваиваться каждые два года. В результате спрос на полосу пропускания в мировых IP-сетях составит примерно 522 экзабайт, или более половины зетабайта [156, 167].

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

Tejas и Jayhawk в 2004 году стала переломным моментом в истории развития

13 микропроцессоров и ознаменовала конец идеи повышения тактовой частоты, как основного средства повышения производительности, с этого времени главным организационным принципом увеличения быстродействия компьютерных систем становится распараллеливание выполнения программ — технология распределенных вычислений [165].

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

Характерной особенностью таких задач является невозможность их решения в настоящее время только аналитическими или алгебраическими методами, и по этой причине находят широкое использование вычислительные методы поиска полного или частичного решения [171, 172]. Современная точка зрения на некоторые из этих проблем такова, что найти их удовлетворительные решения возможно только вычислительными методами. Решение перечисленных задач имеет большое теоретическое значение. На данный момент даже частные решения, полученные вычислительными методами, находят широкое практическое применение.

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

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

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

Основные результаты, полученные в диссертационной работе, можно сформулировать следующим образом:

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

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

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

4. Разработаны пути повышения быстродействия и достоверности вычислений. Для повышения скорости вычислений при малых значениях к и о характеристике конечного поля, не превосходящей 2-10 , используется метод вычисления обратной матрицы, основанный на рекурсивной блочной схеме умножения матриц в формате кватернарного дерева, а для значений к > 64 применяется алгоритм Штрассена, сокращающий трудоемкость до 0(nlog27) о против 0(п ) для традиционного метода.

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

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

7. Предложены алгоритмы сборки и разборки числовой последовательности высокой размерности. На основе анализа производительности наиболее трудоемкой части алгоритма сборки для вычислительной системы из 32 узлов были получены следующие значения показателя ускорения: 19,63 для 16-разрядных операндов, 9,91 для 32-разрядных операндов, что превосходит аналогичные показатели для традиционно используемых алгоритмов в среднем на 32% и 14% соответственно.

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

9. По результатам общего расчета отказоустойчивости сделан вывод, что введение дополнительной единицы избыточности повышает вероятность безотказной работы системы за расчетный период в среднем на 20%.

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

11. Разработана библиотека функций для реализации действий с данными большой и большой размерности на аппаратной базе нейропроцессора NM6403. Анализ производительности функций обработки больших чисел (на примере функции вычисления произведения) показал повышение быстродействия в среднем на 47% для чисел до 10240 десятичных разрядов, и на 16% для чисел большей размерности.

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

ЗАКЛЮЧЕНИЕ

1. Аляутдинов, Д. А., Параллельный СИ (PARALLEL С) Текст. / Д. А. Аляутдинов, А. Н. Далевич. М. : МАИ. 1991. - 112 с.

2. Антонов, А. С. Параллельное программирование с использованием технологии MPI Текст. / А. С. Антонов. М. : Изд-во Московского университета. 2004.

3. Антонов, А. С. Введение в параллельные вычисления Текст. / А. С. Антонов. М. : Изд-во Физического факультета МГУ. 2002.

4. Ахо, А. Структуры данных и алгоритмы Текст. / А. Ахо, Дж. Хопкрофт, Дж. Ульман. Издательский дом «Вильяме». 2000. — 384 с.

5. Бабаян, Б. А. Многопроцессорные ЭВМ и методы их проектирования Текст. / Б. А. Бабаян, А. В. Бочаров, В. С. Волин и др. М. : Высшая школа. 1990.

6. Бабенко, JI. К. Архитектура и математическое обеспечение многопроцессорных суперЭВМ Текст. / JT. К. Бабенко, П. П. Кравченко, О. Б. Макаревич, А. Г. Чефранов. Таганрог : Таганрогский радиотехнический институт. 1992.

7. Барский, А. Б. Параллельные информационные технологии Текст. / А. Б. Барский. Издательство «Бином. Лаборатория знаний». 2007.

8. Барский, А. Б. Параллельные процессы в вычислительных системах: планирование и организация Текст. / А. Б. Барский. М. : Радио и связь. 1990.

9. Барский, А. Б. Параллельные технологии решения оптимизационных задач Текст. / А. Б. Барский // Информационные технологии № 2. М. 2001.

10. Барский, А. Б. Вычислительная система, управляемая потоком данных Текст. / А. Б. Барский, В. В. Шилов // Информационные технологии № 8. -М. 2000.

11. Барский, А. Б. Потоковая вычислительная система: программирование и оценка эффективности Текст. / А. Б. Барский, В. В. Шилов // Информационные технологии № 7. — М. 2003.

12. Барский, А. Б. Применение SPMD-технологии при построении сетевых баз данных с циркулирующей информацией Текст. / А. Б. Барский // Информационные технологии № 7. М. 2003.

13. Барский, А. Б. Оптимизация ветвления при решении задачи сортировки на процессоре EPIC-архитектуры Текст. / А. Б. Барский, В. В. Шилов // Информационные технологии № 1. — М. 2005.

14. Богачев, К. Ю. Основы параллельного программирования Текст. / К. Ю. Богачев. Издательство «Бином. Лаборатория знаний». 2003. - 342 с.

15. Богданов, А. В. Архитектуры и топологии многопроцессорных вычислительных систем Текст. / А. В. Богданов, В. В. Корхов, В. В. Мареев, Е. Н. Станкова. Издательство «Бином. Лаборатория знаний». 2004.

16. Бочаров, Н. В. Технологии и техника параллельного программирования Текст. / Н. В. Бочаров // Программирование № 1. — М. 2003.-С. 5-23.

17. Брой, М. Информатика. Теоретическая информатика, алгоритмы и структуры данных, логическое программирование, объектная ориентация Текст. / М. Брой. М. : Диалог-МИФИ. 1998. - 224 с.

18. Буза, М. К. Введение в архитектуру компьютеров Текст. / М. К. Буза. Мн.: БГУ. 2000. - 253 с.

19. Букатов, А. А. Программирование многопроцессорных вычислительных систем Текст. / А. А. Букатов, В. Н. Дацюк, А. И. Жегуло. -Ростов-на-Дону : Издательство ООО «ЦВВР». 2003.

20. Булос, Дж. Вычислимость и логика Текст. / Дж. Булос. М. : Мир. 1994.-396 с.

21. Бурцев, В. С. Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ Текст. / В. С. Бурцев. М. : ИВВС РАН. 1997. -152 с.

22. Бурцев, В. С. Принципы построения многопроцессорных вычислительных комплексов «Эльбрус» Текст. / В. С. Бурцев. — М.: ИТМ и ВТ АН СССР. 1977.

23. Бурцев, В. С. Тенденции развития суперЭВМ. Оптические принципы обработки информации в архитектуре суперЭВМ Текст. / В. С. Бурцев. М. : ВЦКП АН СССР. 1992.

24. Бэбб, Р. Программирование на параллельных вычислительных системах Текст. / Р. Бэбб. М. : Мир. 1991. - 376 с.

25. Варпаховский, Ф. JI. Элементы теории алгоритмов Текст. / Ф. JI. Варпаховский. М. : Просвещение. 1970.

26. Варшавский, В. И. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах Текст. / В. И. Варшавский. — М. : Наука. Гл. ред. физ.-мат. лит. 1986. 400 с.

27. Василенко, О. Н. Теоретико-числовые алгоритмы в криптографии Текст. / О. Н. Василенко. М.: МЦНМО. 2003. - 328 с.

28. Верещагин, Н. К. Математическая логика и теория алгоритмов Текст. / Н. К. Верещагин, А. Шень. -М. : МЦНМО. 1999. 176 с.

29. Вержбицкий, В. М. Численные методы Текст. / В. М. Вержбицкий. М. : Высш. школа. 2000 г. — 268 с.

30. Вирт, Н. Алгоритмы и структуры данных Текст. / Н. Вирт. —"М. : Мир. 1989.

31. Воеводин, В. В. Параллельные вычисления Текст. / В. В. Воеводин, Вл. В. Воеводин. СПб.: БХВ-Петербург. 2002. - 608 с.

32. Воеводин, В. В. Архитектура ЭВМ и численные методы Текст. / Сб. науч. трудов под ред. В. В. Воеводина. М.: ОВМ АН СССР. 1983. -142 с.

33. Воеводин, В. В. Математические проблемы параллельных вычислений Текст. / В. В. Воеводин // Научный сервис в сети Интернет: технологии распределенных вычислений / Сб. тр. всероссийской конф. Изд-во Московского ун-та. 2005. - С. 3-8.

34. Воеводин, В. В. Математические основы параллельных вычислений Текст. / В. В. Воеводин. -М. : Изд-во МГУ. 1991.

35. Воеводин, В. В. Математические модели и методы в параллельных процессах Текст. / В. В. Воеводин. М.: Наука. 1986.

36. Воеводин, В. В. Параллельные структуры алгоритмов и программ Текст. / В. В. Воеводин. М. : ОВМ АН СССР. 1987.

37. Волконский, В. Ю. Предикатное представление как основа оптимизации программы для архитектур с явно выраженной параллельностью Текст. / В. Ю. Волконский, С. К. Окунев. М. : Информационные технологии № 4. 2003.

38. Вялый, М. Н. Сложность вычислительных задач Текст. / М. Н: Вялый // Математическое просвещение, вып. 4. М. : МЦНМО. 2000. с.81-114.

39. Гергель, В. П. Теория и практика параллельных вычислений Текст. / В. П. Гергель. Издательство «Бином. Лаборатория знаний». 2007.

40. Головашкин, Д. Л. Методы параллельных вычислений Текст. / Д. Л. Головашкин. Ч. 1. — Самара : Самар. гос. аэрокосм, ун-т. 2002.

41. Головашкин, Д. Л; Методы параллельных вычислений Текст. / Д. Л. Головашкин, С. П. Головашкина. Ч. 2. Самара: Самар. гос. аэрокосм, ун-т. 2003.

42. Головкин, Б. А. Параллельные вычислительные системы Текст. / Б. А. Головкин. М. : Наука. 1980.

43. Головкин, Б. А. Расчёт характеристик и> планирование параллельных вычислительных процессов Текст. / Б. А. Головкин. — М. : Радио и связь. 1983.

44. Гудман, С. Введение в разработку и анализ алгоритмов Текст. / С. Гудман, С. Хидетниеми. М. : Мир. 1981. - 368 с.

45. Гэри, М. Вычислительные машины и труднорешаемые задачи Текст. / М. Гэри. М. : Мир. 1982. - 416 с.

46. Деменев, А. Г. Параллельные вычислительные системы: основы программирования и компьютерного моделирования Текст. / А. Г. Деменев. -Пермь :ПГПУ. 2001.

47. Демидович, Б. П. Основы вычислительной математики Текст.1 / Б. П. Демидович, И. А. Марон. — М. : Наука: 1966. — 664 с.

48. Денис, Дж. Схемы потоков данных Текст. / Дж. Денис // В кн. Теория программирования. 4 2. Новосибирск : ВЦ СО АН СССР. 1972 г. С. 7-43.

49. Дорошенко, А. Е. Математические модели и методы организаций высокопроизводительных вычислений Текст. / А. Е. Дорошенко. Киев : Наукова думка. 2000.

50. Джесхоуп, X. JI. Параллельные ЭВМ: архитектура, программирование и алгоритмы Текст. / X. JI. Джесхоуп. М. : Радио и связь. 1986.

51. Ершов, А. П. Алгоритмы, математическое обеспечение и проектирование архитектур, многопроцессорных вычислительных систем Текст. / Под ред. А. П. Ершова. — М : Наука. 1982.

52. Зайченко, Ю. П. Исследование операций Текст. / Ю. П. Зайченко. -Киев: Вища школа. 1979.

53. Запечников, С. В. Обеспечение безопасности восстановительного резервирования информации в системах распределенного хранения данных Текст. / С. В. Запечников. М. : Издательство МИФИ. 2004.

54. Ивенс, Д. Системы параллельной обработки Текст. / Под ред. Д. Ивенс. -М. : Мир. 1985.

55. Игнатущенко, В. В. Организация структур управляющих многопроцессорных вычислительных систем Текст. / В. В. Игнатущенко. -М. : Энергоатомиздат. 1984.

56. Инютин, С. А. Вычислительные задачи большой алгоритмической сложности и модулярная арифметика Текст. / С. А. Инютин. Вестник Тюменского госуниверситета № 3. Тюмень. 2002.

57. Калиткин, Н. Н. Численные методы Текст. / Н. Н. Калиткин. М.: Наука. 1978.-512 с.

58. Карп, Р. М. Сводимость комбинаторных проблем Текст. / Р. М. Карп. М. : Мир. 1975.

59. Катленд, Н. Вычислимость. Введение в теорию рекурсивных функций Текст. / Н. Катленд. М. : Мир. 1983. - 256 с.

60. Клини, С. К. Математическая логика Текст. / С. К. Клини. Новосибирск : ВЦ СО АН СССР. 1982.

61. Кнут, Д. Искусство программирования, том 1. Основные алгоритмы Текст. / Д. Кнут. — М. : Вильяме. 2006. — 720 с.

62. Кнут, Д. Искусство программирования, том 2. Получисленные методы Текст. / Д. Кнут. М. : Вильяме. 2007. - 720 с.

63. Коваленко, В. Эволюция и проблемы Grid Текст. / В. Коваленко, Д. Корягин // Открытые системы № 1. 2003. С. 27-33.

64. Ковалик, Я. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы суперЭВМ Текст. / Под ред. Я. Ковалика. — М. : Радио и связь. 1988. 432 с.

65. Комолкин, А. В. Программирование для высокопроизводительных ЭВМ Текст. / А. В. Комолкин, С. А. Немнюгин. — СПб. : Издательство СпбГУ. 1998.

66. Коновалов, Н. Параллельные программы для вычислительных кластеров и сетей Текст. / Н. Коновалов, В. Крюков // Открытые системы №3.2002.-С. 12-18.

67. Коновалов, А. Н. Введение в вычислительные методы линейной алгебры Текст. / А. Н. Коновалов. Новосибирск : ВО «Наука». Сибирская издательская фирма. 1993.

68. Кормен, Т. Алгоритмы: построение и анализ Текст. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. -М. : Вильяме. 2006. 1296 с.

69. Корнеев, В. В. Параллельные вычислительные системы Текст. / В. В. Корнеев. М. : Нолидж. 1999. - 320 с.

70. Корнеев, В. Д. Параллельное программирование Текст. / В. Д. Корнеев. — Издательство «Регулярная и хаотическая динамика». 2003. -303 с.

71. Котов, В. Е. Сети Петри Текст. / В. Е. Котов. М. : Наука. Главная редакция физико-математической литературы. 1984. - 160 с.

72. Котов, В. Е. Теория схем программ Текст. / В. Е. Котов, В. К. Сабельфельд. М. : Наука. 1991.

73. Кравченко, П. П. Методы управления ресурсами вычислительных систем Текст. / П. П. Кравченко, А. Г. Чефранов. — Таганрог : Таганрогский радиотехнический институт. 1991.

74. Крылов, В. И. Вычислительные методы Текст. / В. И. Крылов, В. В. Бобков, П. И. Монастырный. М.: Наука. 1977. - 400 с.

75. Кузнецов О. П. Дискретная математика для инженера Текст. / О. П. Кузнецов. М. : Энергоатомиздат. 1988. - 480 с.

76. Лавров, С. С. Программирование. Математические основы, средства, теория. Текст. / С. С. Лавров. СПб;: БХВ-Петербург. 2001. — 320 с.

77. Ларионов, А. М. Вычислительные комплексы, системы и сети Текст. / А. М. Ларионов, С. А. Майоров, Г. И. Новиков. М. : Энергоатом издат. 1987.

78. Лацис, А. Как построить и использовать суперкомпьютер Текст. / А. Лацис. М. : Бестселлер. 2003. - 240 с.

79. Легалов, А. И. Модель параллельных вычислений? функционального языка- Текст.- / А. И. Легалов // Структуры и математическое обеспечение специализированных средств / Известия ГЭТУ, сборник научных трудов. — СПб. : 1996; С. 56-63.

80. Легалов, А. И. Функциональный язык для создания архитектурно-независимых параллельных программ Текст. / А. И: Легалов. -Вычислительные технологии № 1 (10). 2005. С. 71-89.

81. Легалов; А. И; На пути к переносимым параллельным программам. Текст. / А. Ш Легалов. Открытые системы № 5 (май). 2003. - С. 36-42.

82. Липаев, В. В. Распределение ресурсов в вычислительной системе Текст. / В. В. Липаев. -М. : Статистика. 1979.

83. Малашонок, Г. И. Параллельные алгоритмы компьютерной алгебры Текст. / Г. И. Малашонок, А. И. Аветисян, Ю. Д. Валеев, М. С. Зуев // Труды Института Системного Программирования РАН. 2004.

84. Матюшков, Л. П. Основы машинной математики. Текст. / Л. П. Матюшков, А. А. Лихтарович. М. : Наука. 1988. - 240 с.

85. Мезенцева, О. С. О возможностях реализации модулярной арифметики на процессоре Л1879ВМ1 (NM6403) Текст. / О. С. Мезенцева, А. И. Алексеев // Вестник Северо-Кавказского государственного технического университета № 2 (11). Ставрополь : СевКавГТУ. 2007.

86. Мезенцева, О. С. О реализации пороговых схем на базе системы остаточных классов Текст. II О. С. Мезенцева, А. И. Алексеев // Обозрение прикладной и промышленной математики, Т. 15, вып. 2. М. 2008.

87. Мезенцева, О. С. Применение аппарата пороговых схем и модулярной арифметики для повышения производительности распределенных вычислительных систем Текст. / О. С. Мезенцева, А. И. Алексеев // Научно-технические ведомости СПбГПУ № 5. СПб. : СПбГПУ. 2008.

88. Митчелл, Д. А. Внутри транспьютера Текст. / Д. А. Митчелл. — М.: Мейкер. 1992.-206 с.

89. Мулярчик, С. Г. Численные методы Текст. / С. Г. Мулярчик. -Мн.: БГУ. 2001.-127 с.

90. ЮЗ.Немнюгин, С. А. Параллельное программирование для многопроцессорных вычислительных систем Текст. / С. А. Немнюгин, О. Л. Стесик. СПб. : БХВ-Петербург. 2002.

91. НТЦ «Модуль». Архитектура процессора цифровой обработки сигналов Л1879ВМ1 (NM6403) Электронный ресурс. / НТЦ «Модуль». 2006. http://www.module.ru/files/nm6403arch-r.pdf.

92. Ю5.0лифер, В. Г. Компьютерные сети. Принципы, технологии, протоколы Текст. / В. Г. Олифер, Н. А. Олифер. СПб. : Питер. 2003. -864 с.

93. Оре, О. Теория графов Текст. / О. Ope. М. : Наука. 1980. - 336 с.107.0ртега, Дж. Введение в параллельные и векторные методы решения линейных систем Текст. / Дж. Ортега. — М. : Мир, 1991.

94. Павловский, Ю. Н. Проблема декомпозиции в математическом>моделировании Текст. / Ю. Н. Павловский. М. : Фазис. 1998. - 272 с.

95. Пападимитриу, X. Комбинаторная оптимизация. Алгоритмы и сложность Текст. / X. Пападимитриу, К. Стайнглиц. М. : Мир. 1985. -512 с.

96. Пескова, С. А. Центральные и периферийные устройства электронных вычислительных средств Текст. / С. А. Пескова, А. И. Гуров, А. В. Кузин. Под ред. О. П. Глудкина. М. : Радио и связь. 1999.

97. Ш.Поспелов, Д. А. Введение в теорию вычислительных систем Текст. / Д. А. Поспелов. М.: Сов. Радио. 1972.

98. Поспелов, Д. А. Ситуационное управление. Теория и практика Текст. Д. А. Поспелов. -М. : Наука. 1986.

99. Разборов, А. А. О сложности вычислений Текст. / А. А. Разборов // Математическое просвещение, вып. 3. -М.: МЦНМО. 1999. С. 127-141.

100. Самарский, А. А. Введение в численные методы Текст. / А. А. Самарский. М. : Наука. 1987. - 286 с.

101. Седжвик, Р. Фундаментальные алгоритмы на С. Анализ, структуры данных, сортировка, поиск Текст. / Р. Седжвик. СПб. : ДиаСофтЮП. 2003. - 672 с.

102. Соловьев, В. Д. Абстрактная теория вычислимости: программистский подход Текст. / В. Д. Соловьев. Казань : КГУ. 1993. - 124 с.

103. Старченко, А. В. Параллельные вычисления на многопроцессорных вычислительных система Текст. / А. В: Старченко, А. О. Есаулов. Томск : ТГУ. 2002.

104. Стрельников, В. П. Расчет надежности параллельных структур на основе аппарата функций случайных аргументов с использованием DN-распределения Текст. / В. П. Стрельников // Сетевой электронный научный журнал «Системотехника» № 6. 2008.

105. Сэвидж, Дж. Сложность вычислений Текст. / Дж. Сэвидж. — М.: Факториал. 1998. 368 с.

106. Таланов, В. А. Математическая логика и модели вычислений Текст. / В. А. Таланов. Н. Новгород : Изд-во ННГУ. 1994. - 116 с.

107. Таненбаум, Э. Архитектура компьютера Текст. / Э. Таненбаум. -СПб. : Питер. 2002.

108. Танненбаум, Э. Распределенные системы. Принципы и парадигмы Текст. / Э. Танненбаум, М. Ван Стеен. СПб. : Питер. 2003. - 877 с.

109. Тербер, К. Дж. Архитектура высокопроизводительных вычислительных систем Текст. / К. Дж. Тербер. М.: Наука. 1985.

110. Тормасов, А. Г. Модель распределенного хранения данных с регулируемой избыточностью Текст. / А. Г. Тормасов, М. А. Хасин, Ю. И. Пахомов // Электронный журнал «Исследовано в России». 2001.

111. Успенский, В. А. Теория алгоритмов: основные открытия и приложения Текст. / В. А. Успенский, A. JL Семенов. — М. : Наука. 1987. 288 с.

112. Фернбах, С. СуперЭВМ: Аппаратная и программная организация Текст. / Под. ред. С. Фернбаха. М. : Радио и связь. 1989.

113. Фейт, С. TCP/IP: Архитектура, протоколы, реализация (включая ГР версии 6 и IP Security) Текст. / С. Фейт. М.: Издательство «Лори». 2003. — 424 с.

114. Фомин, А. Д. Управление ключами в Ad-hoc сетях Текст. / А. Д. Фомин, А. В. Фомина // Материалы школы-семинара «Новые информационные технологии 2004». 2004.

115. Харп, Г. Транспьютеры. Архитектура и программное обеспечение. Текст. / Под ред. Г. Харпа. М. : Радио и связь. 1993. - 304 с.

116. Хейгеман, Л. Прикладные итерационные методы Текст. / Л. Хейгеман. М.: Мир. 1986. - 448 с.

117. Херрманн, Р. Распределенные вычисления в одноранговых сетях и высокопроизводительные вычислительные системы на базе архитектуры Intel Текст. / Р. Херрманн // журнал «Technology@Intel», август 2003.

118. Хоар, Ч. Взаимодействующие последовательные процессы Текст. / Ч. Хоар. М. : Мир, 1989. - 264 с.

119. Червяков, Н. И. Принципы построения модулярных сумматоров и умножителей Текст. / / Н. И. Червяков, И. В. Дьяченко // Модулярная арифметика / Материалы международной научной конференции. 2005.

120. Червяков, Н. И. Модулярные параллельные вычислительные структуры нейропроцессорных систем Текст. / Н. И. Червяков, П. А. Сахнюк, А. В. Шапошников. М. : Физматлит. 2003.

121. Червяков, Н. И. Нейрокомпьютеры в остаточных классах Текст. / Н. И. Червяков, А. Н. Макоха, П. А. Сахнюк. М. : Радиотехника. 2003.

122. Червяков, Н. И. Нейрокомпьютеры в системах обработки сигналов Текст. / Н. И. Червяков. — М. : Радиотехника, 2003.

123. Червяков, Н. И. Нейроматематика. Книга 6 Текст. / Н. И. Червяков Н. И. — М. : Радиотехника. 2002.

124. Червяков, Н. И. Элементы компьютерной математики и нейроматематики Текст. / Н. И. Червяков, И. А. Калмыков, В. А. Галкина, Ю. О. Щелкунова, А. А. Шилов. — М. : Физматлит. 2003.

125. Чинин, Г. Д. Векторизация программ: теория, методы, реализация Текст. / Под ред. Г. Д. Чинина. М. : Мир. 1991.

126. Шабунин, Л. В. Комбинаторные исчисления Текст. / Л. В. Шабунин. Чебоксары : ЧТУ. 1984. - 87 с.

127. Шенен, П. Математика и САПР. Текст. / П. Шенен. М. : Мир.1988.

128. Шнайер, Б. Прикладная криптография Текст. / Б. Шнайдер — М. : Триумф. 2002.

129. Шпаковский, Г. И. Организация параллельных ЭВМ и суперскалярных процессоров Текст. / Г. И. Шпаковский. -Мн.: Белгосуниверситет. 1996. 284 с.

130. Шпаковский, Г. И. Программирование для многопроцессорных систем в стандарте MPI Текст. / Г. И. Шпаковский, Н. В. Серикова. Мн. : БГУ. 2002. - 323 с.

131. Эндрюс, Г. Основы многопоточного, параллельного и распределенного программирования. Текст. / Г. Эндрюс. Издательство «Вильяме». 2003. - 512 с.

132. Якобовский, М. В. Распределенные системы и сети Текст. / М. В. Якобовский. М. : МГТУ «Станкин». 2000.

133. Ященко, В. В. Введение в криптографию Текст. / В. В. Ященко. -СПб.: Питер. 2001.

134. Buonadonna, P. Queue pair IP: a hybrid architecture for system area networks Текст. / P. Buonadonna, D. Culler // Proceedings of the 29th annual international symposium on Computer architecture, Anchorage, Alaska. 2002.

135. Buyya, R. High Performance Cluster Computing Текст. / Ed. By Rajkumar Buyya (Monash Univ., Australia). Prentice Hall. 1999.

136. Callaghan, B. NFS over RDMA Текст. / В. Callaghan // 1st USENIX FAST Conference, Monterey, CA. 2002.

137. Cebral, J. R. ZFEM: Collaborative visualisation for parallel multidisciplinary applications Текст. / J. R. Cebral // Parallel CFD 97: Recent development and advances using parallel computes, Manchester. 1997.

138. Cisco. Cisco Visual Networking Index. Forecast and Methodology Текст. / Cisco. 2008.

139. Clark, T. Designing Storage Area Networks Текст. / Т. Clark. Addison-Wesley Longman. 1999.

140. D'Alberto, P. Adaptive Strassen's matrix multiplication Текст. / P. D'Alberto, A. Nicolau // International Conference on Supercomputing, Proceedings of the 21st annual international conference on Supercomputing. Seattle, Washington. 2007. pp. 284-292.

141. Dijkstra, E. W. Cooperating Sequential Processes in Programming Languages Текст. / ed. F. Genuys, Academic Press, New York. 1968.

142. Duato, J. Interconnection Networks (Computer Architecture and Design) Текст. / J. Duato, S. Yalamanchili, N. Lionel. Morgan Kaufmann. 2002.

143. Eager, D. L. AMVA techniques for high service time variability Текст. / D. L. Eager, D. J. Sorin, M. K. Vernon // ACM SIGMETRICS Performance Evaluation Review, v. 28 n. 1. 2000. p. 217-228.

144. Fiduccia, С. M. A Linear-Time Heuristic for Improving Network Partitions Текст. / С. M. Fiduccia. 19th Design Automatic Conference. 1982. — p. 175-181.

145. Fiedler, M. property of eigenvectors of nonnegative symmetric matrices and its application to graph theory Текст. / M. Fiedler. Praha, Czechoslovak Mathematical Journal, 25(100). 1975. pp. 619-633.

146. Fiedler, M. Eigenvectors of acyclic matrices Текст. / M. Fiedler. — Praha, Czechoslovak Mathematical Journal, 25(100). 1975. pp. 607-618.

147. Flynn, L. Intel Halts Development of 2 New Microprocessors Текст. / L. J. Flynn. New York Times. 2004.

148. Flynn, M. J. Some Computer Organizations and their Effectiveness Текст. / M. J. Flynn // IEEE Trans Comput., vol. C21. 1972. pp. 948-960.

149. Gantz, J. The Diverse and Exploding Digital Universe: An Updated Forecast of Worldwide Information Growth Through 2011 Текст. / J. Gantz, C. Chute, A. Manfrediz, S. Minton, D. Reinsel, W. Schlichting, A. Toncheva. -ICD March 2008.

150. Gropp W. Using MPI Текст. / W. Gropp. Prentice Hall. 2000.

151. Haletky, E. L. VMware ESX Server in the Enterprise: Planning and Securing Virtualization Servers Текст. / E. L. Haletky. Prentice Hall. 2008.

152. Hendrickson, B. An Improved Spectral Partitioning Algorithm for Mapping Parallel Computations Текст. / В. Hendrickson // SIAM J. Comput. Phys. Vol. 16, N 2. 1995. p. 452-469.

153. Hendrickson, В. Multi-Level Algorithm for Partitioning Graphs Текст. / В. Hendrickson // Tech. Rep. SAND93-1301, Sandia National Laboratories, Albuquerce. 1993.

154. Hennessy, J. L. Computer Architecture: A Quantitative Approach Текст. / J. L. Hennessy, D. A. Patterson. Morgan Kaufmann. 2002.

155. Hoare C. Communicating sequential processes Текст. / С. Hoare // In B. Shaw, editor, Digital Systems Design. Proceedings of the Joint IBM University of Newcastle upon Tyne Seminar, 6-9 September. 1978. — pp. 145-156.

156. Hockney, R. The communication challenge for MPP: Intel Paragon and Meiko CS-2 Текст. / R. Hockney // Parallel Computing, 20(3). 1994. pp. 389-398.

157. Intel 64 and IA-32 Architectures Optimization Manual. Текст. / Intel. 2001.

158. Jin, H. Adaptive Sector Grouping to Reduce False Sharing in Distributed RAID Текст. / H. Jin, K. Hwang // Cluster Computing, v. 4 n. 2. 2001.-pp. 133-143.

159. Katz, R. H. High-Performance Network and Channel Based Storage Текст. / R. H. Katz // Proceedings of the IEEE, vol. 80, no. 8. 1992. -pp. 1238-1261.

160. Katz, R. H. Network-attached storage systems Текст. / R. H. Katz // Scalable High Performance Computing Conference, Proceedings. 1992. -pp. 68-75.

161. Kothari, S. C. Generalized Linear Threshold Scheme Текст. / S. C. Kothari // Advances in Cryptology: Proceedings of CRYPTO 84, Springer-Verlag. 1985.

162. Ma, G. Performance Evaluation of Storage Systems Based on Network-Attached Disks Текст. / G. Ma, A. Khaleel, A. Narasimha // IEEE Transactions on Parallel and Distributed Systems, v. 11 n. 9. 2000. pp. 956-968.

163. Menasce, D. A. A Method for Design and Performance Modeling of Client/Server Systems Текст. / D. A. Menasce, H. Gomaa // IEEE Transactions on Software Engineering, v. 26 n. 11. 2000. pp. 1066-1085.

164. Menasce, D. A. Simple analytic modeling of software contention Текст. / D. A. Menasce // ACM SIGMETRICS Performance Evaluation Review, v. 29, n. 4. 2002.

165. Mezentseva, O. S. Regarding the (N, k)-threshold schemes realization based on modular arithmetic algorithms Текст. / О. S. Mezentseva, A. I. Alekseyev // Journal of the Applied Mathematics, Statistics and Informatics (JAMSI), 3 (2007), No. 1. 2007.

166. Microsoft development library Электронный ресурс. / Microsoft.

167. Microsoft developer network. 2007.

168. Pacheco, P. Parallel Programming With MPI Текст. / P. Pacheco. -Prentice Hall. 2002.

169. Parlett, В. On Estimating the Largest Eigenvalue with the Lanczos Algorithm Текст. / В. Parlett // Mathematics of computation. Vol. 38, Number 157. 1995.-pp. 153-165.

170. Pentakalos, О. I. An approximate performance model of a Unitree mass storage system Текст. / О. I. Pentakalos, D. A. Menasce, M. Halem, Y. Yesha // Proceedings of the 14th IEEE Symposium on Mass Storage Systems. 1995. — p. 210.

171. Reinders, J. VTune Performance Analyzer Essentials. Measurement and Tuning Techniques for Software Developers Текст. / J. Reinders. Intel Press. 2005.-455 p.

172. Rice, H. G. Classes of recursively enumerable sets of positive numbers and their decision problems Текст. H. G. Rice / Trans. Amer. Math. Soc. 74(2). 1953. pp.358—366.

173. Simon, H. D. Partitioning Of Unstructured Problems For Parallel Processing Текст. / H. D. Simon. Computing Systems in Engineering. 1991.

174. Tanenbaum, A. S. Modern Operating Systems Текст. /А. S. Tanenbaum. Prentice Hall. 2007.

175. Thornburgh, R. H. Storage Area Networks: Designing and Implementing a Mass Storage System Текст. / R. H. Thornburgh, B. J. Schoenborn. Prentice Hall PTR. 2000.

176. Turing, A. M. On computable numbers, with an application to the Entscheidungsproblem Текст. / A. M. Turing // Proc. London Math. Soc., ser.2, 42. №3-4. pp. 230-265.

177. Watson, R. W. The parallel I/O architecture of the high-performance storage system (HPSS) Текст. / R. W. Watson, R. A. Coyne // Proceedings of the 14th IEEE Symposium on Mass Storage Systems. 1995. p. 27.

178. Wood C. Client/server data serving for high-performance computing Текст. / С. Wood // Proceedings of the 14th IEEE Symposium on Mass Storage Systems. 1995.-p. 107.