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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 511. 334. 12
РАСПАРАЛЛЕЛИВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ ОПЕРАЦИЙ НА ОСНОВЕ МОДУЛЯРНЫХ СТРУКТУР ДАННЫХ
Чернобровкин В. В.
ГБОУ ВПО Сургутский государственный университет, Сургут, e-mail: kooa@adm. surgu. ru_
В статье рассматриваются методы повышения скорости вычислительных операций над многоразрядными числами с помощью системы остаточных классов или модулярной системы счисления. Приведено доказательство одного из вариантов китайской теоремы об остатках, лежащей в основе модулярного представления чисел. Образование цифр модулярного представления проводится независимо и каждый разряд несет информацию обо всем числе, что позволяет проводить параллельную обработку в независимых каналах, а также использовать новые методы арифметического контроля. Информация для обработки, представленная в виде вычетов, позволяет использовать исходные данные с большим или сверхбольшим количеством разрядов. Многоразрядные модулярные вычисления, применяемые для задач большой алгоритмической сложности позволяют периодически повышать производительность вычислительной техники.
Ключевые слова: Модулярная система счисления, Китайская теорема об остатках, сравнения, вычеты, вычислительные операции.
PARALLELIZATION OF COMPUTING OPERATIONS ON THE BASIS OF MODULAR DATA STRUCTURES
Chernobrovkin V.V.
SEIHPE «Surgut State University», Suugut, e-maUikooa@adm. surgu. ru_
This article discusses methods to improve the computational speed of operations on multi-bit numbers using a system of residual classes or modular system value. It is given the proof of one embodiment of the Chinese Remainder Theorem, the underlying modular representations of numbers. Spawn figures modular presentation conducted independently and each category contains information about everything including that allows parallel processing of independent channels, as well as the use of new methods of arithmetic control. Information processing, presented in the form of deductions, the original data can be used with large or super- large number of bits. Modular multi-bit computing, applied to problems of great algorithmic complexity, allow increasing productivity calculated inflammatory technology for periodic.
Keywords: system of residual classes, Chinese remainder theorem, comparison, deductions, computing operations. Введение
Основной стратегией теоретических и практических исследований, осуществляемых в настоящее время, является применение подходов, базирующихся на интенсивном использовании различных форм параллелизма на алгоритмическом, программном и аппаратном уровнях. В связи с чем исключительно большое значение имеют исследования, ориентированные на применение нетрадиционных способов кодирования числовой информации и соответствующих им параллельных вариантов компьютерной арифметики [6]. Возможность применения модулярной системы счисления [1−3,5−10] в вычислительных алгоритмах обусловливается наличием изоморфизма между математическими операциями над целыми числами и соответствующими операциями над системой целых неотрицательных вычетов по взаимно-простым модулям. Сложение, умножение, возведение в целую положительную степень целых положительных чисел сводятся к соответствующим
операциям, выполняемым над множеством вычетов, — представлением этих чисел в модулярной системе счисления.
Целью исследования является исследование вопросов повышения скорости выполнения арифметических операций над многоразрядными числами с применением возможностей модулярной системы счисления, выявление зависимости объема обрабатываемых данных от нетрадиционных способов их представления и времени выполнения вычислительных операций с ними. Это является особенно важным при разработке алгоритмов для решения задач большой вычислительной сложности.
Методы исследования для решения поставленной задачи основываются на системном анализе, теории сравнений, теории чисел и алгоритмов, численных методах.
Фундаментом теоретико-числовой базой модулярной системы является теория сравнений, основы которой были разработаны Эйлером и отечественным математиком П. Л. Чебышевым. Применительно к обработке информации модулярными кодами теория опирается на следующее утверждение. Пусть, А и р — два произвольных целых числа, причем р — положительное число, тогда в результате деления числа, А на число р получаются частное и остаток [8]. Делимость, А нар удовлетворяет равенству
*АЕг1А = ]Л + а (1)
и неравенству 0 & lt- а & lt- р, (2)
где I — частное, а — остаток.
Согласно (1), величина, а называется наименьшим неотрицательным вычетом [1, 3, 47, 8] целого числа, А по модулю р и обозначается символом ^ '-р.
Для дальнейшего понимания вычислительных операций в модулярной системе проведем доказательство одного из вариантов китайской теоремы об остатках [2−4, 7, 10, которая является фундаментальным положением в основе модулярного представления чисел.
Теорема 1 (Китайская теорема об остатках). Любое целое положительное число, А в модулярной системе счисления можно представить в виде набора остатков (вычетов) от деления этого числа на выбранные основания (модули) системы.
Доказательство.
Пусть число, А представлено в системе остаточных классов следующим образом:
А -н" (а^а-, (3)
где аж. а2,…, а" _ наименьшие, неотрицательные вычеты, образованные путем целочисленного деления числа, А на выбранные основания

р = Рл*Рж*& gt-- = Пр*
и, (4)
где Р: — взаимно простые числа.
Если ^ '- ^ /, 1 ^ т е взаимн0 простые, то представление числа (3)
является единственным, при условии
0 & lt- А& lt- р. (5)
Тогда число, А может быть представлено следующим образом:
.4 = Л ! О--& quot-
А = • (6)
= Л —
Теорема доказана.
Формула (6) определяют сравнения, которые показывают, что каждый вычет, а получается независимо, а значит параллельно от других и содержит информацию обо всём числе. Данное обстоятельство определяет, если для таких вычислений организовать программно-аппаратную вычислительную базу, то вычеты могут образовываться параллельно.
Цифры, а представления (3) по выбранным модулям образуются следующим образом:
а.{ = А (таскр$ = А —
Р
, С
VI Е

(7)
где И — целочисленное частное- Р- - взаимно простые числа (основания системы).
Приведем пример, в котором рассмотрим кодирование чисел в модулярной системе
счисления на конкретном примере. Пусть даны основания Р± = 2, Р = 3, Р, а = 5, тогда. Отображение всех тридцати чисел в системе оснований Рь-Ра-Ра приведено в таблице.
Отображение чисел в системе остаточных классов
Десятичное представление числа 0 1 2 3 4 5 6 7 8 9
Изображение чисел в остатках по модулям 2, 3, 5 (0,0,0) (1,1,1) (0,2,2) (1,0,3) (0,1,4) (1,2,0) (0,0,1) (1,1,2) (0,2,3) (1,0,4)
Десятичное представление числа 10 11 12 13 14 15 16 17 18 19
Изображение чисел в остатках по модулям 2, 3, 5 (0,1,0) (1,2,1) (0,0,2) (1,1,3) (0,2,4) (1,0,0) (0,1,1) (1,2,2) (0,0,3) (1,1,4)
Десятичное представление числа 20 21 22 23 24 25 26 27 28 29
Изображение чисел в остатках по модулям 2, 3, 5 (0,2,0) (1,0,1) (1,0,2) (1,2,3) (0,0,4) (1,1,0) (0,2,1) (1,0,2) (0,1,3) (1,2,4)
Как видно из таблицы, все остатки в модулярной системе одноразрядные, что дает преимущества для вычислительных операций перед обычной позиционной системой счисления (ОПСС), особенно если величина разрядов в числах значительно растет.
Над вычетами можно выполнять арифметические операции сложения, вычитания и умножения в кольце вычетов. Все они относятся к модульным операциям, то есть не требуют вычисления позиционных характеристик (ПХ) обрабатываемых чисел и поэтому считаются быстрыми.
Отношение сравнения по модулю натурального числа обладает следующими свойствами:
1) симметричность: а =
2) рефлексивность: а = ?Стой т) — Ъ = аЬпоОпО
3) транзитивность'- а = гпЬ = с (тос1 т), тоа = с ЬпоЛ т)
Множество вычетов по модулю натурального числа с двумя операциями обладает кольцевыми свойствами:
, ч [ Ь, с С 1, а + (Ы- с) = (а + А) + с
1) ассоциативность по сложению: — ¦ -
(?о Ёг",)Гуа еги], я + о = о+ы = а
2) существование нулевого элемента: * ч г) —
(уяе 2ц) ГзЬ Е, а+Ь=Ь+ н = 0
3) существование обратного элемента:^ V —
4) ассоциативность по умножению: СУя'- с е, а — (Ь — с} - (& quot-а Ь& quot-) с.
г (Уа-Ь, с? I, я ¦ (Ь + с} = я ¦ Ъ Л- а, — с. Оз + с) — а= Ь • а+ с — а
5) дистрибутивность: V И-
Рассматривая вычисления в кольце вычетов ^'-^г с помощью модулярной арифметики все операции можно разбить на две группы. Пусть операнды, А и В, а также результаты операций А±В и, А -В представлены соответственно остатками яг А, Уг, по основаниям Рг, где е [1- -ч^]) Причём оба числа и результаты находятся в диапазоне [О, Р], то есть
л

! = L
А±Б=А±3Р = & amp- -mi -Ft ± ^|п|[0|[11р.]. п1ГРЕ
Зтр. 1-шгР. :

IP[:] mi -Pi
При этом
А, Б& gt- A + В, А-В,

— кольцо целых чисел.
Так как выражение (8) является прямым следствием фактов теории чисел [2, 3, 5], то результаты аддитивной и мультипликативной операций можно переписать в виде, А ± Б = Я- + jS- (mod рг) АБ = яг-/?г- Сmod рг-} ПрИ vi G Если положить
Yi = в| + & amp- {mod Si = ffli-/?? {mod pi) Vi = дг- - & amp- (r
то цифрами результата являются, соответственно,
.
,
(9)
(10)
П = щ ± ft —
= я-Фг —
Pi
1? i = Щ — Pi —
Pi
-Pi-
?
eii-fa
•Pi
(11)
Pi
¦Pi
Выражения (11) могут быть получены на основании выражения (6). Из вышеизложенного очевидно, что все вычислительные операции в кольце
щ
полностью распараллеливаются с помощью модулярной системы.
Перейдем к немодульной операции деления в модулярной системе. Если рассматривать представление (3) с условием Д? = (? = 1Д- то операцию деления
можно проводить в модулярной системе счисления поразрядно. Пусть числа, А и В представлены по основаниям Р^Р =г ¦¦¦ /Рп- Тогда они будут иметь представления:
А = (я^я., … гяп}- В = яг- ф О, @2 Ф 0 VI е [1, …, я]
Л
Результат деления Б ~ & quot-"-*, (12)
где ^ е
определяются как решения сравнения- 4i = Pi)1 = ^-^тосЕ (moci р{) Vi е [1,
п
. (13)
Очевидно, что деление без остатка двух чисел в модулярной системе осуществляется путем модульного умножения делимого на мультипликативную обратную величину делителя.
у = - то& lt-1
Величина Р: является решением сравнения
у/?? = 1 & lt-тойргО (14)
и однозначно определена, если А'- и Рг — взаимно простые числа.
Сравнения (13) имеют единственные решения в том случае, когда А& quot- 0 — дг может принимать значение 0, поэтому от ограничения Ф 0 можно отказаться.
Если число, А делится нацело на В, то представление (7) дает истинное значение для А
дроби С = В, где С — некоторое целое число- если число, А не делится нацело на В, то
А

представление (7) будет формальным представлением дроби Б- в этом случае В (той Р).
Модульные операции и их результаты называются формальными, если при выполнении этих операций пренебрегают возможным выходом за пределы вычислительного диапазона.
Если, А делится на В и среди цифр & amp- имеются нулевые значения, то из делимости, А на В следует, что и яг = 0. Таким образом, при поразрядном делении в 7-м представлении (7) имеет место неопределенность типа, для раскрытия которой необходимо знание о всем числе [1].
Согласно китайской теореме об остатках все операции проходят по п каналам. Для этого построим параллельную вычислительную схему следующего вида (рис. 1):
Вход __А__I
+, —, *, А, /.
Ж
и
О
и
Ч о №
и
и
Г и
— В
в к
п
к 8
а о
м й Ч ^
& amp- 8
О — о Г и
в
л о
Ч о н н и 8
ев и
й: =
О О
м й 8
& amp- 8
О О
о 8
о Я
а 8
к м О
к

Вычислительный канал по
модулю
Вычислительный канал по модулю Ря
Вычислительный канал по модулю Рт:
м и
8 и
Ч о К
и 8 в
Г и
И о
— 8 и
Ч
К в
& amp- м ев & amp- О — о и и ев
О Я И
— 8
л Г
ч О
о н
н ев
ев Н
в и
О О
м ев
& amp- О
о н

а 8
к и
Выход В
Рис. 1. Обобщенная схема обработки многоразрядных чисел в модулярной системе
На схеме показано как, А — входные многоразрядные данные — преобразуются на основе системы остаточных классов и подаются в n каналов обработки. Каждый из n каналов вычисляет по выбранному модулю (основанию) Pi входные данные. Затем вычисленные значения поступают в «обратный» преобразователь и выходят в виде результата B.
На сравнительных графиках показана зависимость времени выполнения вычислительных операций от разрядности входных данных (рис. 2). Преимущества по времени и объему обрабатываемых данных при параллельной обработке возникают при следующих условиях:
1) разрядность обрабатываемых данных значительная-
2) количество и разрядность выбранных модулей (оснований) унифицированы под обрабатываемые данные.
Все вычислительные операции проводились на процессорах одного класса Intel Core2
Quad.
Рис. 2. Сравнительная схема выполнения вычислительных операций
На рис. 2 видно, что график при параллельной обработке данных похож на график функции у = о%(х}и лежит ниже линейной зависимость последовательной обработки, что свидетельствует о преимуществах параллельной обработки на основе модулярного представления данных.
Выводы
1. Применение системы остаточных классов для вычислительных операций с многоразрядными данными дает значительное преимущество перед позиционными системами, так как имеет естественную по своей природе параллельность.
2. Вычисление цифр модулярного представления проводится независимо, и каждый вычет несёт информацию обо всём числе, что позволяет проводить параллельную обработку вычетов в независимых каналах и использовать методы арифметического контроля.
3. На основе модулярной системы представления данных возможны разработки параллельных алгоритмов для решения задач большой алгоритмической сложности.
Список литературы
1. Акушский И. Я., Юдицкий Д. М. Машинная арифметика в остаточных классах. — М.: Советское радио, 1968. — 440 с.
2. Бухштаб А. А. Теория чисел. — М: Наука, 1977. — 368 с.
3. Виноградов И. М. Основы теории чисел. — М.: Наука, 1981. — 176 с.
4. Инютин С. А. Модулярные вычисления в сверх больших компьютерных диапазонах // Известия высших учебных заведений. — Электроника. — № 6. — 2001. — С. 81−87.
5. Инютин С. А. Вычислительные задачи большой алгоритмической сложности и модулярная арифметика // Вестник Тюменского государственного университета. — 2002. — № 3. — С. 14−23.
6. Коутинхо С. Введение в теорию чисел. Алгоритм RSA. — М.: Постмаркет, 2001. — 45 с.
7. Лобес М. В. Разработка методов и алгоритмов модулярных вычислений для задач большой алгоритмической сложности: дис. … канд. физ. -мат. наук. — Ставрополь, 2009. — 192 с.
8. Модулярные параллельные вычислительные структуры нейропроцессорных систем / Н. И. Червяков. — М.: Физматлит, 2003. — 43с.
9. Ноден П., Ките К. Алгебраическая алгоритмика. — М.: Мир, 1999. — 720 с.
10. Основы теории делимости чисел, решение уравнений в целых числах. Факультативный курс МГИЭТ (ТУ) / В В. Бардушкин [и др.]. — М., 2003. — 100 с.
Рецензенты:
Бахарев М. С., д.т.н., профессор, профессор кафедры «Нефтегазовое дело» Федеральное государственное бюджетное образовательное учреждение высшего профессионального
образования Сургутский институт нефти и газа, (филиал) Тюменского государственного нефтегазового университета, г. Сургут.
Инютин С. А., д.т.н., профессор, профессор кафедры «Проектирование вычислительных комплексов» ФГБОУ ВПО «МАТИ — Российский государственный технологический университет им. К. Э. Циолковского (МАТИ)» г. Москва.

ПоказатьСвернуть
Заполнить форму текущей работой