Содержание к диссертации
Введение
Глава 1 Анализ производительности многоядерной машинной архитектуры и вычислительных алгоритмов многоразрядной обработки информации 16
1.1 Обзорный анализ архитектуры современных многоядерных процессоров 16
1.2 Характеристики машинной архитектуры и параллельных вычислительных процессов 21
1.3 Обоснование применения модулярной арифметики в системах с параллельной машинной архитектурой 28
1.4 Постановка целей и задач исследования 33
Выводы 37
Глава 2 Теория распараллеливания многоразрядных вычислений на основе модулярной арифметики 38
2.1 Распараллеливание многоразрядных вычислений на основе модулярных структур данных 38
2.2 Адаптация модулярной арифметики под вычислительные проблемы 45
2.3 Методы вычисления позиционных характеристик в модулярной арифметике 51
2.4 Методика преобразования числовых кодов в позиционные и непозиционные форматы Выводы 68
Глава 3 Разработка алгоритмов немодульных операций 61
3.1 Метод распараллеливания поиска простых оснований 61
3.2 Алгоритмы деления в модулярной арифметике 70
3.3 Алгоритм вычета модулярной величины по большому модулю 75
3.4 Масштабирование целых положительных чисел 77
Выводы 85
Глава 4 Адаптация модулярных вычислительных моделей на параллельную машинную архитектуру 84
4.1 Программно - аппаратная модель многоразрядной обработки информации на базе модулярных вычислений и параллельной архитектуры 84
4.2 Особенности адаптации вычислительных алгоритмов под параллельную архитектуру GPU - процессоров
4.3 Адаптация модулярных вычислений на GPU-процессоры с помощью CUDA-технологии 102
4.4 Экспериментальные оценки производительности вычислительной системы INSERModCom 109
Выводы 112
Заключение 113
Список литературы
- Обоснование применения модулярной арифметики в системах с параллельной машинной архитектурой
- Адаптация модулярной арифметики под вычислительные проблемы
- Алгоритм вычета модулярной величины по большому модулю
- Особенности адаптации вычислительных алгоритмов под параллельную архитектуру GPU - процессоров
Обоснование применения модулярной арифметики в системах с параллельной машинной архитектурой
Таким образом, операции сложения и умножения над числами, представленными в модулярной системе счисления, сводятся к соответствующим операциям над цифрами этого представления, причем это относится и к любым комбинациям этих операций.
Одним из важных достоинств модулярной системы является малая разрядность остатков, что обеспечивает возможность реализации табличного выполнения модульных операций, если их результат не выходит за пределы диапазона представления чисел в процессоре. Это свойство ставит ее вне конкуренции по производительности при обработке многоразрядных чисел перед любыми ПСС [16,54].
Следующее важное качество высокая точность, надежность и способность к самокоррекции. Причём в МСС можно построить непозиционные коды, обнаруживающие и исправляющие ошибки, которые являются полностью арифметическими, то есть в этих кодах информативная и контрольная части равноправны относительно любой операции [2, 22, 24]. Эта особенность предоставляет возможность варьировать корректирующей способностью кода за счёт изменения точности вычислений. Кроме того, так как в этой системе информация представляется параллельно по различным основаниям, то появление ошибки по одному из них не влияет на точность информации в других параллельных каналах [42]. Это одно из важнейших преимуществ МСС перед всеми ПСС: ни одна из них не позволяет находить и, тем более, исправлять ошибки в процессе выполнения арифметических операций. Наоборот, в арифметическом устройстве они, раз возникнув, бесконтрольно размножаются. В ЭВМ, работающих в обычных ПСС, контроль и исправление ошибок обеспечиваются только в системах хранения и передачи информации. Арифметико-логические устройства - один из основных источников сбоев и ошибок в позиционных ЭВМ, остаются бесконтрольными [54]. Проведенный анализ показал, что алгоритмы цифровой обработки информации и модулярной арифметики обладают естественным параллелизмом и могут быть реализованы на современной вычислительной базе, представленной в виде многоядерной архитектуры GPU - процессоров, имеющими все необходимые сопоставимые характеристики.
Так как модулярная алгоритмика направлена на область многоразряд-ных,многократных целочисленных вычислений, то под вычислительной базой в данном исследовании понимается совокупность вычислительных и алгоритмических средств. Теоретические основы, модулярной вычислительной базы содержат: - представление числовой величины; -математическое соотношение, связывающее данное представление с иными представлениями числовых данных; -алгоритмы выполнения операций. Модулярный вычислительный алгоритм ориентирован на выполнение в модулярной вычислительной базе, и он будет эффективным, если при этом достигаются наименьшие оценки временной и алгоритмической сложности.
Под эффективностью вычислительного алгоритма понимаются меньшие затраты операционного оборудования и памяти на его выполнение на параллельной архитектуре.
Для анализа и сравнения модулярных вычислительных алгоритмов между собой необходима универсальная система оценки их вычислительной сложности. К системе оценок предъявляются следующие требования: 1. Удобство и прозрачность формирования оценок сложности. 2. Учет особенностей модулярного варианта выполнения алгоритма. 3. Удобство использования при сравнительном анализе на выбранном уровне глубины детализации машинных и вычислительных алгоритмов. В доказательствах корректности алгоритмов обозначим этапы: 1. Доказательство частичной корректности, заключающееся в том, что-если алгоритм завершен, то он дает правильный результат. 2. Доказательство выхода, подтверждающее, что всякое выполнениеал-горитма для данных из области его определения завершится за конечное время.
Для модулярного варианта будем использовать оценки для максимального распараллеливания на необходимое число модулярных оснований.
Цель диссертационного исследования состоит: 1. Повышение быстродействия и надежности многоядерных процессоров цифровой обработки информации. Основными путями повышения производительности ЭВМ являются внедрение новых, более эффективных способов организации и проведения вычислений. Одним из важнейших современных направлений теории и практики применения цифровой обработки информации, получивших в последнее время, особенно интенсивное развитие, является создание и внедрение принципиально новых по производительности и надежности вычислительных структур параллельно-конвейерного типа [20, 39]. Несмотря на разнообразие вычислительных алгоритмов многоразрядной обработки информации, их реализация фактически сводится к выполнению некоторого набора алгоритмических преобразований. Ключевую роль в современных системах цифровой обработки играют процедуры ортогональных преобразований, алгоритмы которых характеризуются внутренним параллелизмом. Применение многоядерных процессоров позволяет использовать особенности алгоритмов МА для повышения скорости и надежности обработки информации.
Разработка теоретических основ и методов моделирования вычислительного процесса с распараллеливанием на уровне машинных операций, ориентированного на вычисления в больших и сверхбольших компьютерных диапазонах на основе модулярной арифметики и параллельной машинной архитектуры.
Разработка конструктивной системы количественных оценок алгоритмической и временной сложности модельных машинных операций и проблемных вычислительных алгоритмов на модулярной базе, позволяющей сравнивать модулярный, позиционный и полиадический подходы к решению вычислительной проблемы и выявлять классы эффективных модулярных вычислений.
Адаптация модулярной арифметики под вычислительные проблемы
При адаптации модулярной арифметики и подстройки ее к проблемным вычислительным алгоритмам необходимо учесть следующее: - настройка вычислительного диапазона и выбор величины (будущего результата); - выбор подмножества модульных вычислительных операций на модулярной основе; - выбор подмножество немодульных вычислительных операций на модулярной основе.
Одной из важных операцией среди множества вычислительных проблем в больших диапазонах является операция вычисления остатка по заданному, большому модулю от входной числовой величины. Она должна быть базисной в разрабатываемой машинной арифметике и предъявляет требования к выбору алгоритмов "модульных" и "немодульных" операций МА. Такая операция должна обеспечивать максимальную простоту вычисления вычета по модулю от заданного большого числа.
Настройка проблемных алгоритмов на вычислительную основу есть его отображение в вычетную форму на базе модулярной арифметики [19,21,27]. Одновременная настройка машинной арифметики на те же проблемы позволяет оптимизировать по быстродействию и затратам операционных ресурсов упомянутых вычислительных алгоритмов. Центральной задачей является выбор диапазона модулярной системы для выбранной вычислительной проблемы. Выявлено, что для некоторых алгоритмов вычисления арифметических операций в больших и сверхбольших диапазонах уменьшается время и сложность их выполнения, если например, вычислительный диапазон модулярной системы Р = Р\ р2 Рп хотя бы не много отличается от значения выбранной величины, характерной для вычислительной проблемы. Однако для вычислительных алгоритмов проблемы будут существовать всегда. Например, определение максимума значения числовой величины - будущего результата. Решение такой проблемы находится в выборе соответствующего модулярного диапазона, т.к. для корректности модулярного алгоритма будущий результат должен быть Р — 1.
Оптимальным выбором является когда модулярный диапазон равен выбранной величине но для этого необходимо каноническое разложение самой числовой величины, которая как правило неизвестна. Такой выбор интересен для получения минимальных оценок быстродействия и сложности алгоритмов.
Вычислительный интерес представляет собой приближение большой величины X к максимуму типового машинного диапазона, который является произведением некоторого количества простых чисел из фиксированного множества простых чисел равному некоторому большому числу у верхней границы этого диапазона. Допустим, что получено упорядоченное множество таких простых чисел: р± ... pn,S = {рг,... ,рп].
Алгоритмы приближения модулярного диапазона к базовым величинам проблемных алгоритмов рассмотрены в [21]. На их основе разработаем алгоритм с меньшей сложностью.
Учтем, что X, Р - большие величины, а числа р1 ...шрп из типового машинного диапазона. Заметим, что модулярная система замкнута относительно процедуры выбора своего диапазона.
В основе алгоритмов выполнения немодульных операций лежат методы вычисления позиционных характеристик (ПХ) разработанные [21,26,50,67]. Сложность алгоритмов вычисления ПХ непосредственно влияет на скорость выполнения немодульных операций в модулярной арифметике.
Известно, что сравнение обрабатываемых чисел по величине можно выполнить путем вычитания одного числа из другого, а так же определения знака разности чисел. Но так как разряды числа, представленные в МСС, не информируют о знаке числа, то необходимо вычислить позиционные характеристики, которые смогут его определить. Существующие методы определения позиционных характеристик называются:
Все эти методы важно необходимы в протекании процессов вычислений многоразрядной обработки информации. Разработаем алгоритмы распознавания положительных и отрицательных характеристик обрабатываемых чисел, а также сравнения чисел по величинам, представленных в МСС.
Определение знака числа в модулярном формате связано непосредственно с определением абсолютной величины самого числа. Конкретное представление знака числа не устраняет необходимость для определения относительных величин, так как на знак числа могут влиять арифметические операции (например, вычитание чисел одного знака) [7]. Одним из способов определения знака числа, является интервальное разбиение исходного диапазона чисел представленных модулярным кодом. Пусть диапазон МСС представлен как Р = ПЇ Pi, тогда все числа из интерва р р ла, [0,- — 1) определим как положительные, а из диапазона [-,Р — 1) - отрицательные. Тогда знак числа определяется сравнением представления чис р п ла с представлением величины - при условии, что рг = 2. Метод определения знака числа на базе ОПСС и МСС Приведем простой пример: Определить знак числа с помощью метода перевода в полиадическую систему счисления для модулей рх = 3, р2 = 5, р3 — 7, р4 — 2 для которой рабочий диапазон есть Р = 3-5-7-2 = 210.
Пусть число Л = 17 тогда его модулярное представление будет (2, 2, 3, 1), число = 150 (0,0,3,0).
В случае явного представления знака сравнение чисел осуществляется путем сравнения коэффициентов полиадической системы счисления. Для этого, во-первых, необходимо получить цифры полиадического кода для каждого числа; во-вторых, сравнить цифры полученных представлений, переходя от старших разрядов к младшим. Если А В, то первая отличная от нуля разность цифр будет положительной, и наоборот.
При неявном представлении знака, сравнение осуществляется путем вычитания сравниваемых чисел и определением знака разности сравниваемых чисел. Для этого, во-первых, необходимо получить цифры полиадического кода для каждого числа; во-вторых, определить наиболее значимую не нулевую цифру каждого числа. Функцию сравнения в этом случае целесообразно реализовать таблично.
Алгоритм вычета модулярной величины по большому модулю
Выбор оптимального алгоритма выполнения базисной операции вычислительной проблемы - один из способов настройки модулярной арифметики на проблемную область[21,27,72,92,99]. Рассмотрим метод вычисления вычета по некоторому модулю, близкому к величине вычислительного модулярного диапазона. Эта операция, как правило, является базовой в модулярных вычислительных алгоритмах, она дает наибольший вклад в алгоритмическую сложность, поэтому ее алгоритм должен быть оптимален на выбранной вычислительной базе. В общем случае, пусть В (mod Р) F Р, (F, Р) = 1, А = В (mod Р), необходимо вычислить \А mod P\F(mod Р).
Рассмотрим задачу определения вычета от модулярной величины A(mod Р) по модулю F, обладающему следующими свойствами: (F,P) = 1, Р F, min\P — F, в частности при соотношениях F Р 2F. Такая немодульная операция необходима, например на каждом шаге алгоритма теста на простоту по критериям теста Пепина и Лукаса-Лемера. На множестве - шагов алгоритмов этих критериев возникает следующая подзадача в Z:Bi F Р, В і = А Р, \Bt \F = Ві+1
Для позиционного варианта временная сложность операции вычисления вычета по большому модулю от модулярной величины квадратичная относительно количества компонент модулярной величины.
В связи с тем, что модулярная арифметика целочисленная, то при вычислениях промежуточные значения операндов могут переполнять динамический диапазон. Подобная проблема может возникнуть и в традиционных-компьютерах, если они оперируют с целыми числами. Во избежание переполнения надо промасштабировать (уменьшить) значения операндов. Про-масштабированные величины затем используются в следующих итерациях. Это означает, что операция масштабирования должна применяться к дан-нымс использованием заранее заданной константы, которая округляется до ближайшего целого. Все эти операции связаны с операцией деления.
Деление в любой целочисленной системе счисления определяется фор мулой а = b + \а\ъ где а представляет собой делимое, b - делитель целая часть отношения ак b (частное), а \а\ь- остаток (наименьший целый положительный остаток). Целью алгоритма масштабирования является на хождение - для значений Ъ из ограниченной области. Заметим, что Рп значения. Если Ъ совпадает с одним из pt или является произведением первых степеней некоторых модулей Pi, то \а\ъ можно найти. Тогда по теореме, используемой в форме деления с нулевым остатком, для всех і, для которых НОД величин pi и Ъ равен 1, можно получить
Как видно для масштабирования числа большим коэффициентом масштаба используется последовательное деление на простые числа и расширение базы оснований модулярной системы. Отрицательные числа в МСС можно записать как Р — а. Если известно, что число отрицательное, то легко можно его определить из Р — а, затем проводится масштабирование на Ь, получаем — и затем представляем результаты как Р + - . Если же знак неизвестен, то возникает определенная сложность. При масштабировании отрицательного числа как будто бы число положительное, результатом будет — + - вместо необходимого Р + - . , определяется знак а. Ес р Поэтому перед масштабированием необходимо определить знак а, этого процесса можно избежать, если принять во внимание следующее обстоятельство: деление на Ъ отображает все числа в интервале 0, /2 — lj в интервал О,Р/2Ь - 1 и все числа в интервале [р/2, Р - lj в интервал YІ2Ь,р 1ъ После чего нужно выполнить вначале деление числа на Ь, а затем, принимая во внимание интервал, в котором находится , то к нему прибавляется по модулю Р для р ли а отрицательное число получения правильного ответа Р + Определение интервала, в котором находится - требует такого же количества времени, что и для определения знака числа. Однако, как было рассмотрено в предыдущем примере, процесс масштабирования требует операции расширения базы модулей СОК на основе цифр ОПСС, поэтому можно определить местонахождение числа - путем использования цифр ОПСС. Рассмотрим метод одновременного масштабирования и распознавания знака. Пример 3.4.2 Одновременное масштабирование и определение знака. Для модулей рх = 13, р2 = 9, р3 — 11 Р4 — 7, и р5 = 2 масштабируем число а = —979 - (9,2,0,1,1) на число Ъ = 11 7 с округлением до ближайшего целого числа.
Введение модулярных вычислительных структур в обязательном порядке должно сопровождаться проектированием схем декомпозиции данных по узлам и ядрам вычислительных устройств. Поэтому была произведена разработка и анализ схемы распределения модулярных структур данных между узлами и вычислительными ядрами в пределах GPU- процессора.
Особенности адаптации вычислительных алгоритмов под параллельную архитектуру GPU - процессоров
Причем каждой отдельной нити соответствует один элемент вычислительных данных. Этот фактор говорит о том, что под такие условия можно легко адаптировать модулярную систему счисления, обладающую естественным параллелизмом на уровне данных. В свою очередь распараллеливание инструкций во многом зависит от среды программирования и необходимых алгоритмов.
Приведем простой пример: 1) А= [array 1]; 2) B=[array2]; 3) С=А+В. Первые две инструкции вполне можно выполнить параллельно, только третья от них зависит. А значит — всю программу можно выполнить за два шага, а не за три. Учтем, что максимальное ускорение, которое можно получить от распараллеливания программы на Р-процессоров(ядер), дается законом Амдала [93,95,100,101]: где Р - число процессоров, а - последовательный фрагмент алгоритма.
Закон Амдала показывает, что прирост эффективности вычислений зависит от алгоритма задачи и ограничен сверху для любой задачи с а ф 0. Однако не для всякой задачи имеет смысл наращивание числа процессоров в вычислительной архитектуре. Более того, если учесть время, необходимое для передачи данных между узлами вычислительной системы, то зависимость времени вычислений от числа узлов будет иметь максимум. Это накладывает ограничение на масштабируемость вычислительной системы, то есть означает, что с определенного момента добавление новых узлов в систему будет увеличивать время расчёта задачи.
На первом шаге необходимо решить проблему "последовательного участка" (п.З) параллельного алгоритма. Возможные варианты решения - это уменьшение такого участка либо преобразование его большую часть в параллельный код. Второй шаг подразумевает разработку наименее затратного варианта обращения к памяти. На третьем шаге необходимо разработать и применять вычислительные алгоритмы, построенные на модулярных структурах данных [7,21, 66,75, 78].
Перейдем непосредственно к параллельным алгоритмам, которые основаны на модулярной системе счисления или как упоминалось выше системе остаточных классов [5].
На рисунке 4.3.5 показана схема распределенной обработки информации. На вход поступают многоразрядные числа, которые распределяются по блокам (поточное программирование).
Серверная часть является «ядром» пакета и реализует выполнение всех заложенных в нееалгоритмические решения по обработке модулярно-позиционных структур данных. Сервер приложения состоитиз трех частей: - блок инициализации параметров, - блок приведения данных к параллельным модулярным структурам, - вычислительный блок. 1. Блок инициализации параметров позволяет настроить программный пакет для работы на конкретнойвычислительной системе, а также на решение кон кретной задачи посредством задания доступных параметров вычислений. К таким параметрам относятся: - число необходимых для использования вычислительных узлов; - число вычислительных ядер в каждом узле; - необходимость использования межпроцессорных коммуникаций; - разрядность вычислительных устройств; - число параллельных процессов и нитей для решения задачи; - требуемая точность вычислений (задается посредством указания разрядности мантисс операндов); - схема распределения модулярных структур данных.
В блоке инициализации параметров заложены правила выбора оптимальной для конкретной задачи и вычислительной системы схемы распределения модулярных структур. 2. Блок приведения данных к параллельным модулярным структурам осуще ствляет взаимодействие с хранилищем, загружая исходные позиционные данные. Далее загруженные данные преобразуются к модулярному формату и становятся доступными для вычислительного блока. В основе функциони рования блока приведения данных к модулярным структурам заложены пол по ностью параллельные масштабируемые алгоритмы, которые разрабатывались сучетом особенностей типов данных [7]. 3. Вычислительный блок реализует выполнение параллельных численных расчетов в модулярном формате. В вычислительном блоке определяется полезный для конечного пользователя функционал пакета INSERModCom. К функциям, реализуемым вычислительным блоком, относятся:
В вычислительном блоке на программном уровне реализуются схемы распределения модулярных структур данных, алгоритмы межпроцессорных обменов, а также базовые параллельные алгоритмы выполнения высокоточных арифметических операций разработанных в главе 3. Основная концепция, заложенная в вычислительном блоке это максимально возможное объединение алгоритмического параллелизма задачи и арифметического параллелизма модулярных структур, благодаря использованию технологии параллельной обработки CUDA. Основные идеи, увеличивающие «вычислительную плотность» процессора:
На основе анализа разработанной модели адаптации модулярной арифметики на параллельную архитектуру GPU-процессора были выбраны приоритетные методы распределения вычислительных потоков. С помощью CUDA - технологии все потоки распределялись по заданным вычислительным ядрам. Преимущество выбранных методов состоит в том, что преобразование обрабатываемых данных в модулярный формат, а в конечном итоге
