автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы и алгоритмы повышения эффективности вычислительной системы с параллельной архитектурой на основе модулярных структур данных

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

Чернобровкин Виталий Викторович

МЕТОДЫ И АЛГОРИТМЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ С ПАРАЛЛЕЛЬНОЙ АРХИТЕКТУРОЙ НА ОСНОВЕ МОДУЛЯРНЫХ СТРУКТУР ДАННЫХ

Специальность 05.13.01 - «Системный анализ, управление и обработка информации»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

„„„„ 2 5 МАР 2015

005561255

Сургут-2015

005561255

Работа выполнена в государственном бюджетном образовательном учреждении высшего профессионального образования «Сургутский государственный университет Ханты-Мансийского автономного округа - Югры».

Научный руководитель:

Официальные оппоненты:

Инютин Сергей Арнольдович доктор технических наук, профессор кафедры проектирования вычислительных комплексов, ФГБОУ ВПО «МАТИ-Россий-ский государственный технологический университет им. К.Э. Циолковского (МАТИ)» Шапцев Валерий Алексеевич доктор технических наук, профессор кафедры информационных систем, Институт математики и компьютерных наук, ФГБОУ ВПО Тюменского государственного университета

Цибульский Владимир Романович, доктор технических наук, профессор, г.н.с. Института проблем освоения севера Сибирского отделения Российской академии наук

ФГБОУ ВПО «Югорский государственный университет»

Защита диссертации состоится «17» апреля 2015 г. В Ю00 часов на заседании диссертационного совета по защите докторских и кандидатских диссертаций Д.800.005.06 при ФГБОУ ВПО Сургутском государственном университете ХМАО - Югры по адресу: 682400, Тюменская область, г. Сургут, ул. Ленина, 1.

С диссертацией можно ознакомиться в научной библиотеке ФГБОУ ВПО Сургутского государственного университета по адресу: 682400, г. Сургут, ул. Ленина, 1. Автореферат разослан «15» марта 2015 г.

Ученый секретарь

диссертационного совета к.т.н. профессорB.C. Микшина

Ведущая организация:

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

Актуальность работы. В современных социально-экономических и эргономических системах интенсивно возрастают потоки различного рода информации. И эффективное управление ими требует адекватных средств ее обработки. Базовой стратегией в разработке эффективных методов и алгоритмов управления сложными системами и обработки многоразрядных носителей - данных и чисел - является параллелизм. Это привело к созданию вычислительных систем, основанных на параллельной архитектуре, и к новой организации управления вычислениями. Появилась тенденция перехода к параллельной машинной архитектуре на основе ОРи-процессоров, а также - к непозиционным системам счисления. В частности, перспективной является модулярная система счисления (МСС), представляющая собой набор простых или взаимно-простых чисел р\,р2, ■■■,Рп, называемых основаниями этой системы. Вычис-

п

лительный диапазон такой системы Р=|определяет область

1

чисел, над которыми можно выполнять операции модулярной арифметики. Если к целому многоразрядному числу А применить деление с остатком на заранее выбранные основания модулярной системы, то получаться остатки (вычеты) — а\,а2,..., а„, которые являются малоразрядными числами. Стоит заметить, что каждый остаток получается независимо друг от друга, а значит параллельно; причем каждый из них в отдельности несет информацию о числе А.

Благодаря своему естественному внутреннему параллелизму и перечисленным выше качествам, модулярная система счисления выдвигается как приоритетная основа для вычислительных операций с многоразрядными числами. Адаптация МСС к вычислительной системе с параллельной архитектурой на основе ОРи-процес-соров приводит к возрастанию ее производительности.

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

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

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

Научная задача исследования.

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

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

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

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

Методы исследования основываются на системном анализе параллельных машинных архитектур и модулярной системы счисления, использовании методов теории сравнений, математическом и компьютерном моделировании машинных операций, систематизации методов и алгоритмов параллельной обработки информации, исследования операций. Также применяются результаты исследований российских и зарубежных ученых (В.М. Амербаев, И .Я. Акуш-ский, Д.И. Юдицкий, В.П. Гергель, В.В. Топорков, С.А. Инютин, Н.И. Червяков, М.В. Лобес, И.Н. Лавриненко, Donald Knuth, Richard Е. Blahut).

Научная новизна полученных в диссертации результатов состоит в следующем.

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

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

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

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

Практическая значимость. Разработанные модели, методы и алгоритмы параллельной обработки многоразрядной информации на основе МСС позволяют строить высокопроизводительные и отказоустойчивые вычислительные системы нового класса, которые способны выполнять в реальном масштабе времени большие объемы математических расчетов. Адаптация таких моделей на ОРи-процес-соры технологии С1ЛЭА приводит их к сверхбольшой производительности. Разработанные методы и алгоритмы повышения производительности вычислительных операций над многоразрядными числами могут быть использованы для целей развития теоретико-числовых методов и алгоритмов, а соответственно и для развития различных областей, в которых они применяются: криптография, криптоанализ; проектирование баз данных, интеллектуальных и экспертных систем; в системах обработки сигналов радиолокации.

Положения, выносимые на защиту.

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

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

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

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

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

Апробация работы. Основные результаты диссертационного исследования докладывалисьна X и XI окружных конференциях молодых ученых в г. Сургут, декабрь 2010 г., ноябрь 2011 г. Региональной научно-практической конференции «Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов», проведенной 28 февраля 2012 г. на базе Алтайского государственного университета г. Барнаул. Международной конференции «40-е Гагаринские чтения» на базе Московского Авиационного Технического Института им. Циолковского (МАТИ), апрель 2014 г. Научно-практической конференции «Математические методы в нефтегазовом деле» посвященной П.Л. Чебышеву состоявшейся в СурГУ, май 2014 г., г. Сургут.

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

Структура и объем диссертации. Работа состоит из введения, четырех глав, заключения, четьгрех приложений, списка сокращений и обозначений, а также списка литературы содержащего 96 наименования 31 из которых зарубежные и 5 приложений. Основная часть работы содержит 108 страниц машинописного текста иллюстрированного 23 рисунками и содержащего 14 таблиц. Общий объем диссертационной работы 138 страниц.

Основное содержание работы

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

В первой главе проводится всесторонний анализ структуры и производительности параллельных вычислительных систем на основе синтеза численных алгоритмов и GPU-процессоров, который определил, что такой показатель эффективности системы как R -

ускорение обработки информации зависящий от двух параметров: р, -загруженности, я, - пиковой производительности каждого вычислительного ядра системы имеет физический предел в рамках вычислительного машинного диапазона. В ходе исследования обнаружено, что реальная производительность системы ниже пиковой производительности. Все ядра не могут одновременно достигнуть пиковой производительности, так как напрямую зависят от вычислительных параллельных алгоритмов, которые как выяснилось, имеют «последовательные» участки. Иначе говоря, для сохранения необходимого ускорения системы при ее максимальной загрузке необходимо наращивать количество вычислительных ядер. Но при тенденции уменьшения аппаратных затрат, такой вариант не будет иметь успеха у разработчиков вычислительных систем (ВС). Анализ вычислительных структур на основе МСС показал преимущества перед позиционными системами счисления и определил обоснование целесообразности ее применения для многоразрядной обработки информации. Арифметика, построенная на таких структурах, имеет многократную точность, которая отражает: высокий уровень параллелизма, надежность и способность к самокоррекции. Выделен ряд областей, в которых преимущества модулярной системы счисления могут быть использованы максимально эффективно. Это в первую очередь обработка многоразрядных чисел, сигналов (свертка, дискретное преобразование Фурье), разного рода физических и биолого-химических процессов. Обоснована необходимость разработки методов и алгоритмов выполнения вычислительных операций на базе модулярных структур данных и адаптации их под СРи-процес-сорные вычислительные системы.

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

А,В<Р (1)

где А, В- целые многоразрядные числа,

Р = (рь р1у..., р„,) - вычислительный диапазон модулярной системы.

На основе теории чисел формулу (1) можно задать тождествами:

А *-* ах = агтос1 ри а2 = а2 то<1 р2,..., ап = аптос1 рп

в 01той рг, Ъ2 = Р2тос1 р2,..., Ьп = Рптой рп (2)

итоге получится: А <-> {аг,а2,... ,ап); В ■«./?«)■

Результатом, например, аддитивных операций будет: Л ± В(тос1 Р) «-» = X <-> О^, ...,хп) (3)

Важно знать, что в формуле (3) должно всегда соблюдаться условие X < Р. То есть, будущий результат любых вычислительных операций в модулярной арифметике не должен превышать Р. Иначе может произойти выход за пределы вычислительного диапазона и результат может оказаться не верным. Универсальность представления многоразрядных чисел состоит в том, что все остатки являются малоразрядными числами и получаются не зависимо друг от друга, а значит параллельно. Отметим, что в кольце вычетов такие арифметические операции как аддитивные так и мультипликативные имеют те же свойства, что и в алгебраическом кольце.

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

Вычислительные операции: +, -, *,Л

Вход А1,В1 -► Преобразователь многоразрядных чисел из ПСС в МСС И1Р1 В ычислительный канал по модулю рх Вычислительны» канал по модулю р2 Мрг Преобразователь многоразрядных чисел из МСС в ПСС Выход

-► И1р2 \в\Рг

ь

Вычислительный канал по модулю рп

-—►

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

Необходимо отметить, что арифметические операции, проводимые в модулярной арифметике (МА) необходимо разделить на модульные (легкие) и немодульные (проблемные). К модульным операциям относятся выше перечисленные аддитивные и мультипликативные операции, которые не требуют вычисления позиционных характеристик (ПХ) чисел.

Для немодульных операций которые представляют собой:

1) вычисление значений вычетов числа, представленных в позиционном формате, по модулям р^ (0 < £ < р - 1) принятой модулярной системы счисления;

2) определение знака числа, представленного модулярным кодом;

3) определение признака выхода результатов вычислительных операций за Р - диапазон;

4) округление результата вычислений;

5) масштабирование;

6) перевод числа из модулярного формата в позиционный.

Вычисление ПХ крайне необходимо, так как все эти операции

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

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

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

Выберем основания модулярной системы Р = (рх ■ р2 ■... ■ Рп)> с помощью которой представим п - разрядное число А (сг1,а2. -.а„). Пусть Р = (рг ■ р2 ■...■ рп)также являются основаниями полиадической системы. Тогда число А будет представлено в виде:

А = *пР1Р2»-Рп-1+*П-1Р1Р2-"Рп-2+"-+*зР1Р2+*2Р1+*1. (4)

где 0 < хк < П?^1 Рг» 0 < I < п - цифры полиадической системы счисления, где вычислительные диапазоны чисел, представимых в модулярной и полиадической системах счисления совпадают.

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

Цифры модулярной системы счисления могут быть получены из соотношений:

Обе части уравнения (4) возьмем по модулю рг: хг = \А |р1= ах Перепишем уравнение (4) в виде:

А-х! = ХпР-^2 ... рп_! + Х„-1Р1Р2 - Рп-2+- • • +Х3Р1Р2 + Х2Р1, (5)

Обе части уравнения (5) возьмем по модулю р2: И — х1|р2= |х2р1|Р2 Умножим обе части данного уравнения на |рГ11р2:

\\VI\M ~ Х^\Р2= 1*2\Р2, т.к. х2 < р2

Поскольку|Л - хх |Р2 = |\А\Р2 - \хг 1Р2 \а2 — хг\Рг, то

формула для вычисления х2 будет выглядеть следующим образом: дг2 = \а2-х1\Р2 • \Р1%2

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

Константные значения инверсных величин р1( р2,..., рп заранее рассчитываются и хранятся в кэш-памяти (Ь1) ¿Ри-процессора.

хг = А- i41p1, где Аг = ,

р 1-

х2 = А- А2р2, где А2 = ,

Ц> 2-1

хп = А- Апрп, где Ап =

Р1 А

х1 = \А\р = ах х2 = \а2 ~ Хг\-рг • |рГ11Р2

*п = \\\ап-х1\Рп-\р11\Рп-х2\ • \р2х\

Рп

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

Вход числа А в ПСС

Табличные сумматоры

Результат Выход числа А в МСС

Система оснований

Полиадиче-_

ский код

Формирование произведений полиадического кода и оснований МСС

Блок О

-------1---------------------

Кэш ¿1

Р1

в

«1

±_х

V 2

а2

ми и

Рз

а3

миц

Р*

миь,

ЕЗ ПП □□

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

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

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

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

числа Ферма - Т^з на простоту. Для ее решения необходимо построение МСС, настроенной на вычислительную проблему, в которой необходимо оценить количество оснований рабочего диапазона модулярной системы:

р2з — р223 + ^ ~ 28388608 яг (230)279620

Как было выявлено, при более точной оценке для выбранной модулярной системы требуется 275110 оснований из диапазона [2Л ..., 231]. В связи, с чем был разработан метод параллельного поиска простых оснований модулярной системы суть которого состоит в том, что:

1) в некотором заданном диапазоне [2", ..., 2"+ '] определяется нижняя и верхняя граница.

2) находятся числа, у которых младший разряд - /0 = 1, 3, 7, 9;

3) параллельно создаются четыре файла для чисел каждого из окончаний (^ь Р3, Я,), т.е. файлы с нечетными числами;

4) в каждом из подмножества каждого файла происходит «отсев» ненужных чисел;

5) в каждом из файлов параллельно происходит поиск простых чисел;

6) формируются файлы с простыми числами - Ри Р3, Ръ Рд. Соответственно простые числа, у которых г'0 = 1 перемещаются в />, и т.д.;

7) Формируется файл со всеми простыми числами - Р, из диапазона [2", ..., 2" + ] в который входят все простые числа из файлов РиРъРъР*

Рис. 3. Схема распараллеливания поиска

Рис. 4. Время параллельного поиска простых чисел

Таблица 1

Распределение простых чисел с каждым из окончаний _^_в диапазоне [230,..., 23']___

{после дователь ного поиска в сек. t парал лельного поиска в сек. Р1 РЗ Р7 Р9 ¿общ

48,129 48,129 12008 12039 12097 11985 48129

47,882 47,882 12004 11919 12051 11908 47882

47,889 47,889 11885 11883 12022 12099 47889

47,470 47,470 11887 11891 11811 11881 47470

47,148 47,148 11795 11773 11799 11781 47148

47,250 47,250 11827 11817 11784 11822 47250

47,067 47,067 11757 11837 11717 11756 47067

46,798 46,798 11565 11668 11801 11764 46798

46,874 46,874 11730 11665 11661 11818 46874

46,696 46,696 11703 11762 11586 11645 46696

46,669 46,669 11667 11640 11616 11746 46669

Очевидно, что при распараллеливание поиска время уменьшается, примерно, в четыре раза и составляет, приблизительно около 12 сек.

Результаты поиска простых оснований показаны на рисунке 5.

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

Алгоритм Деления на основания МСС

1. Вычисляем модулярную величину

i4° - aiimod Р)

(..., а,- - а£ + (kj - ki) • pj(mod pj), ...,0(mod pt),...).

2. Вычисляем следующую модулярную величину А1 = СА0 - a.i—kiPi)/pi(mod P/Pi) «

«-» (..., (ау - аг + (fcj- - ki) • Pj) • \p\-f(mod pj), ...,z(mod pf),...), где г - неопределенное значение модулярного представления.

3. Выполняем присвоение Л° = Л'.

4. Выполняем п. 1, 2, 3 для всех pt-.

Результат - модулярная величина [Л/(р; ■... • pi+x)(mod Р/ (.Pi---Pi+x))]-

про<!*н млел - ЩШ'

■| 1073741924 21474336*8 1

| 5 . 1 | . «внес

¡Зсего чисел в диапазоне: N«1073741523 ¿¿Всего чисел, заке<*»аю»«ихея на У. Р1«107374132 <10% от И)

Чисел, делящихся на 3: 35791394 (33,33% ОТ 1=1) Ч*ееп, делжаихсяна 7: 10226113 (9,52% от Р1) •Чисел, лепящихся не 11: 5577879 (Б, 19% от Р1) Чясел, деллцяхс* на 13: 4290676 {4% от Я!) Чисел, делящихся на 17:3023 714 (2,32% от Р1) Чкел, делящихся на 19: 2550494 {2,33% от Р $ депод.хся не 23: 1996038 <1,36% от Р1} Чисел, делящихся иа 29: 1514239 {1,41% от Я1) 4>*сел, делящихся на 31: 136768? {1,27% от Р1} Чисел, дег-яшикся не 37: 110895С (1,03% от Р1) Чкел, делящихся на 41: 973702 {0,91% от Р1) Чисел, делящихся на 47: 825692 (0,77% от Р1)

Получение простых чисел

Левая гммииа Новая Заканчиваются нг

«373741824 2147-*33648 1

1073880671

1 1073330721

| 1073331111

| 1073881181

I 1073381331

1 1073831-^1

| 1073381511

1 1073881541

Й 1073331631

I 1073331741

\ 1073381771

1 1073882011

| 1073832021

10Г5332031

I 1073382111

? 1073382141

! Стоп» | __________________________„„ ПОИСХ

Рис. 5. Результаты поиска простых оснований МСС

Таблица 2

Временная сложность немодульной операции деления модулярной величины на п - оснований

Вариант Адцит. операции Мульт. операции

ПВ 2п 2п

1MB 2п 2п

Алгоритм основан на соотношении [A/(Pi ■ ... • Pi+x) (jnodP/(pi ■ ...-рг+*))] = [[...[A/Pi]/...]/pi+x],

которое последовательно вычисляется для всех р,.

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

1. По А-2.4.4 выполняем проверки: \А\Р > F(modP), К > F(jnodP). По их результатам:

Uni | _(\A\P-F,ecmi\A\P>F ||Л|р|,г~1 \А\Р, если|Л|Р < F

_ 1 lF I K,ecmiK<F

2. \A\f = \\A\p\f + \K\f ■ (P - FXmodP).

3. Выполняем проверки:

Если < P, ho|1|f > F, то^"^ = |Л|К - F,ecnn\Ä\F < F, то переход к п. 5. Если \Ä|F > P, то переход к п.4.

4._Вычисляем Р - разложение: \Ä\F = \\Ä\F\P + К" ■ P(modP). Переход к п. 1, 2, 3 алгоритма.

5. Конец алгоритма, получили модулярную величину:

= ||Л|р|я- + |/f|F ■ \P\F(modP).

Таблица 3

Временная сложность операции вычисления вычета по большому модулю от модулярной величины

Вариант Адцит. операции Мульт. операции

ПВ 5п2 6п2

1MB 5п 6п

Масштабирование целых неотрицательных чисел

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

Пример 1 Масштабирование целого неотрицательного числа четырьмя модулями МС. Пусть рг = 2, р2 = З,р3 = 5,р4 = 7 - основания МС. Определим вычеты значения целого числа а = 89, у которого модулярный код (1, 2, 4, 5). Масштабируем коэффициентом 15. Обозначим результат <-> 2.

Решение

2 ч 7

МОДУЛИ

вычеты (1.2,4,5)

, , 0 (0,2,2,2) вычитаем а 3 = 2 > '

(1,0,2,3) 2Д5<7

а - |а|3

|i| (1,-2,5)

умножаем на - _—

|3|PÍ (1,-4,1) 2,5,7

(0,-4,4)

а - |а|3

вычитаем |а|5 = 4

(1,-0,4) 2,3,7

а-|а|

умножаем наН (1, —, —,3)

15|р, -

(1.-.-5)

Для расширения базы внесем 0 в пропущенные колонки для метода Гарнера и обозначим как |а|3, и |а|5 - для предложенного метода.

Метод Гарнера

Метод с большим коэффициентом

(1,0,0,5)

1. вычитаем 1

(0,2,4,4)

_ |1| (-,2,3,4)

2. умножаем на |-|

3. вычитаем2

(-,2,2,2) (-.2,0,0)

4. Тогда|^ |г|3 + 2| = 0 и |^|г|5 + 2| = 0

Следовательно, ¡г\3 = 2и]г\5 = О

Отсюда масштабируемое число —

это(1,2,0,5) <-» 5

Разобьем матрицу констант измененной последовательности модулей на две

модули

1. умножаем

2, 7,3 2, 7,5

1,3,1 0,4,2 0,0,2

1,3,2 0,4,1 0,0,1

1-13 1 5- 0 20 10

Мз • 0, 0, 2 • Из ; 1,2,14 + 2 -Из

Отсюда

1-13 2

5' 0 20 5

М5 ■ 0, 0, 9-[*15 1, 2,10 + 3-М5

1*15=0 |1|

14 + 2 ■ |х|з=0 10 + 3

1*1з= -7 тос) 3= 2 той 3 Ы-= -ю1-| =20

1315

= (1,2,0,5) <-> 5 тос1 5 = 0 тосг 5

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

Четвертая глава указывает на зависимость вычислительных параллельных алгоритмов от двух парадигм распараллеливания. Первая - это параллельная машинная архитектура. Вторая - структуры данных на базе МСС. В связи с чем уделяется внимание на синтез таких передовых технологий как ОР1Г-процессоры и модулярная система счисления.

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

Рис. 6. Выбор распараллеливания вычислений

Схема организации вычислений

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

Рис. 7. Абстрактная вычислительная схема адаптации модулярных вычислений на ОРи-процессор

Основные идеи, увеличивающие «вычислительную плотность» процессора:

• использовать большее количество простых ядер;

• упаковывать в ядро больше ALU;

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

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

Рис. 8. Зависимость загрузки вычислительных нитей ядра от числа MPI-процессов

Анализируя график, показанный на рисунке 8 можно сделать вывод, что полная загрузка одной нити (thread) вычислениями, проходящими в ПСС достигает при количестве 64 загруженных процессов. В то время как в модулярной системе полная загрузка нити одного ядра начинается с количества более, чем 512 процессов. Эффект превосходит более чем в 8 раз.

В заключении подведены итоги и обобщены результаты исследования. Также показаны универсальная, конструктивная систе-

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

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

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

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

В работе получены следующие основные результаты:

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

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

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

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

Публикации в научных журналах из перечня ВАК

1. Чернобровкин В.В. Распараллеливание представлений многоразрядных чисел на модулярных структурах данных // Фундаментальные исследования. - 2013. - № 11. - С. 904-910.

2. Чернобровкин В.В. Распараллеливание вычислительных операций на основе модулярных структур данных // Современные проблемы науки и образования, Издательство: Издательский Дом «Академия Естествознания» (Пенза)188№ 1817-6321.-2014. - № 1. -С. 249.

3. Инютин С.А., Чернобровкин В.В. Адаптация модулярных вычислений на вРи-процессоры с помощью С1ГОА-технологии // НТЖ «Вестник кибернетики». - 2014. - № 2(14). - С. 35-41.

В других изданиях

1. Чернобровкин В.В. Поиск усовершенствованных алгоритмов вычисления сверхбольших чисел //Наука и инновации XXI века : мат-лы XI Окр. конф. молодых ученых. Сургут : ИЦ СурГУ, 2011. — Т. 1.-С. 27-28.

2. Чернобровкин В.В. Новый метод поиска простых оснований модулярной системы счисления // Сборник статей региональной научно-практической конференции «Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов». - Барнаул : Изд-во АлтГУ, 2012. - С. 16.

3. Чернобровкин В.В., Метод распараллеливания поиска простых чисел по их младшим разрядам в ограниченном диапазоне // Вестник СурГУ. - 2013. - № 2. -Ч. 2. - С. 8-11.

4. Чернобровкин В.В. О проблеме оценки эффективности в задачах моделирования // Сборник научных трудов по материалам международной научной конференции «40-е Гагаринские чтения», МАТИ им. Циолковского, г. Москва, 2014 г. -М., 2014. - С. 341-342.

5. Чернобровкин В.В. Повышение эффективности многоразрядных вычислений основанных на теории сравнений и параллельного программирования по технологии С1ГОА// Международная конференция «Математика и информационные технологии в нефтегазовом комплексе», посвящ. дню рожд. академика П.Л. Чебышёва. -Сургут: Изд-во СурГУ, 2014. - С. 252-255.

Чернобровкин Виталий Викторович

МЕТОДЫ И АЛГОРИТМЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ С ПАРАЛЛЕЛЬНОЙ АРХИТЕКТУРОЙ НА ОСНОВЕ МОДУЛЯРНЫХ СТРУКТУР ДАННЫХ

Специальность 05.13.01 «Системный анализ, управление и обработка информации»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 12.03.2015 г. Формат 60x84/16. Усл. печ. л. 1,3. Уч.-изд. л. 1,1. Тираж 120. Заказ № 15.

Оригинал-макет подготовлен в редакционно-издательском отделе издательского центра СурГУ. Тел. (3462) 76-30-65, 76-30-66.

Отпечатано в полиграфическом отделе издательского центра СурГУ. г. Сургут, ул. Энергетиков, 8. Тел. (3462) 76-30-67.

ГБОУ ВПО «Сургутский государственный университет ХМАО - Югры» 628400, Россия, Ханты-Мансийский автономный округ, г. Сургут, пр. Ленина, 1. Тел. (3462) 76-29-00, факс (3462) 76-29-29.