Операция деления для параллельных вычислительных систем. Ч. 1
Предлагается цифровой метод выполнения арифметической операции деления (ОД). Алгоритм обеспечивает распараллеливание вычислительного процесса, ускорение его и повышение точности ОД. Он основан на выполнении этапов операций в алгебре матриц и реализации методов цифровой арифметики в булевой (возможно...
Gespeichert in:
| Veröffentlicht in: | Математичні машини і системи |
|---|---|
| Datum: | 2014 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84330 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Операция деления для параллельных вычислительных систем. Ч. 1 / Ю.Я. Ледянкин // Математичні машини і системи. — 2014. — № 1. — С. 36-49. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859675558971965440 |
|---|---|
| author | Ледянкин, Ю.Я. |
| author_facet | Ледянкин, Ю.Я. |
| citation_txt | Операция деления для параллельных вычислительных систем. Ч. 1 / Ю.Я. Ледянкин // Математичні машини і системи. — 2014. — № 1. — С. 36-49. — Бібліогр.: 10 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | Предлагается цифровой метод выполнения арифметической операции деления (ОД). Алгоритм обеспечивает распараллеливание вычислительного процесса, ускорение его и повышение точности ОД. Он основан на выполнении этапов операций в алгебре матриц и реализации методов цифровой арифметики в булевой (возможно, многозначной) алгебре. Рассмотрены варианты выполнения ОД и примеры решения. Предполагается развитие аналогичных работ в плане создания и использования комбинированных алгоритмов обработки данных путём применения других алгебр в сочетании с методами цифровой арифметики.
Пропонується цифровий метод виконання арифметичної операції ділення (ОД). Алгоритм забезпечує розпаралелювання обчислювального процесу, прискорення його і підвищення точності. Він заснований на виконанні етапів операцій в алгебрі матриць і реалізації методів цифрової арифметики в булевій (можливо, у багатозначній) алгебрі. Розглянуто варіанти виконання операції та приклади рішення. Передбачається розвиток аналогічних робіт у плані створення і використання комбінованих алгоритмів обробки даних шляхом застосування інших алгебр у поєднанні з методами цифрової арифметики.
It is proposed the digital method of performing arithmetic division operations (DO). Algorithm provides the parallelizing of computing process, its acceleration and accuracy increase. It is based on carrying out the steps of operations in the matrix algebra and realization of digital arithmetic in Boolean (possibly multi-valued) algebra. Variants of the execution of operation and examples of solutions are regarded. The development of similar projects for the creation and use of combined data processing algorithms by applying other algebras in combination with the methods of digital arithmetic is suggested.
|
| first_indexed | 2025-11-30T15:57:09Z |
| format | Article |
| fulltext |
36 © Ледянкин Ю.Я., 2014
ISSN 1028-9763. Математичні машини і системи, 2014, № 1
УДК 681.3
Ю.Я. ЛЕДЯНКИН*
ОПЕРАЦИЯ ДЕЛЕНИЯ ДЛЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.
Ч. 1
*
МП «ПАК» Института кибернетики имени В.М. Глушкова АН УССР, Киев, Украина
Анотація. Пропонується цифровий метод виконання арифметичної операції ділення (ОД). Алго-
ритм забезпечує розпаралелювання обчислювального процесу , прискорення його і підвищення точ-
ності. Він заснований на виконанні етапів операцій в алгебрі матриць і реалізації методів цифро-
вої арифметики в булевій (можливо, у багатозначній) алгебрі. Розглянуто варіанти виконання
операції та приклади рішення. Передбачається розвиток аналогічних робіт у плані створення і
використання комбінованих алгоритмів обробки даних шляхом застосування інших алгебр у поєд-
нанні з методами цифрової арифметики.
Ключові слова: цифровий метод, операція ділення, паралельні обчислення, обчислювальні системи.
Аннотация. Предлагается цифровой метод выполнения арифметической операции деления (ОД).
Алгоритм обеспечивает распараллеливание вычислительного процесса, ускорение его и повышение
точности ОД. Он основан на выполнении этапов операций в алгебре матриц и реализации мето-
дов цифровой арифметики в булевой (возможно, многозначной) алгебре. Рассмотрены варианты
выполнения ОД и примеры решения. Предполагается развитие аналогичных работ в плане созда-
ния и использования комбинированных алгоритмов обработки данных путём применения других
алгебр в сочетании с методами цифровой арифметики.
Ключевые слова: цифровой метод, операция деления, параллельные вычисления, вычислительные
системы.
Abstract. It is proposed the digital method of performing arithmetic division operations (DO). Algorithm
provides the parallelizing of computing process, its acceleration and accuracy increase. It is based on
carrying out the steps of operations in the matrix algebra and realization of digital arithmetic in Boolean
(possibly multi-valued) algebra. Variants of the execution of operation and examples of solutions are re-
garded. The development of similar projects for the creation and use of combined data processing algo-
rithms by applying other algebras in combination with the methods of digital arithmetic is suggested.
Keywords: digital method, division operation, parallel computing, computing systems.
1. Введение
Создание гетерогенных вычислительных систем (ГВС) высокой производительности, па-
раллельных структур (ПС), особенно для обработки информации, представленной в виде
сложных структур данных (ССД) для реализации вычислительных алгоритмов в едином
технологическом (вычислительном) потоке (ЕТП) с помощью процессорных элементов
(ПЭ) со скалярным умножителем (СУ), в своём составе требует нового подхода к числен-
ным и арифметическим методам, закладываемым в структуры спецпроцессора (СП) и всей
вычислительной системы (ВС) [1–3].
Один из подходов в трансформации численных методов для реализации алгоритмов
решения задач математической физики (МФ) с помощью метода конечных элементов
(МКЭ) предложен и описан в [1, 4–7]. Такой подход предполагает обработку ССД и реше-
ние систем линейных алгебраических уравнений (СЛАУ) в режиме ЕТП. Он обеспечивает
переход к построению высокопроизводительных архитектур гетерогенного типа на базе
ПЭ с СУ в своем составе с HOST процессором в виде центральной интеллектуальной ма-
шины (ЦИМ).
ISSN 1028-9763. Математичні машини і системи, 2014, № 1 37
При построении СУ в основу арифметических операций, которые он должен реали-
зовывать, закладывают операции сложения, вычитания, умножения, деления. Это основа
всех одно- и многоядерных процессоров, работающих в составе кластерных структур (КС).
Операция деления (ОД), которая часто является неотъемлемой частью алгоритма
вычислительного эксперимента (ВЭ), записанного в аналитическом виде, является частью
набора операций, которые впоследствии необходимо реализовывать с помощью процессо-
ра ЭВМ. Но ОД в цифровом виде является менее точной и выполняется за большее время
(по отношению ко времени выполнения операции умножения). Поэтому её реализацию в
АУ процессора стараются избегать, а на уровне алгоритма её выполнение в ЭВМ часто
реализуют при помощи стандартных подпрограмм, основанных на операциях сложения,
вычитания и умножения (или с помощью спецпроцессора, который реализует ОД). Для па-
раллельных устройств ограничения связаны и с последовательным выполнением ОД, по-
скольку каждая новая цифра частного, как и новый остаток, не могут быть вычислены
раньше, чем будет получен и проанализирован предыдущий остаток.
Статья состоит из двух частей. В первой части статьи излагается цель работы, суть
предлагаемого метода замены ОД методом определения обратной величины (ОВ) кода
числа с последующим умножением ОВ на код числа делимого. На конкретных примерах
показывается возможность выполнения предлагаемой операции способом определения ОВ
кода числа, опираясь на математический аппарат матричной алгебры.
Во второй части статьи показаны правомочность и целесообразность использования
аппарата матричной алгебры на первом этапе решения задачи к возможности сочетания на
втором этапе аппарата матричной алгебры с математикой числовой арифметики. Показаны
варианты сочетания методов алгебр на разных этапах формирования обратного значения
числа. Доказывается правомочность и даны условия использования числовой арифметики
в сочетании с математическим аппаратом матричной алгебры. Предложены и описаны ва-
рианты вычисления ОВ кода числа. На конкретных примерах рассмотрены: возможность
реализации поставленной задачи вообще и на параллельных ГВС, в частности; преимуще-
ства предлагаемого решения для замены ОД в классическом понимании операции деления.
Цель работы
Для решения задач вычислительной математики, к которым на практике сводится аппрок-
симация практически всех задач, а особенно для решения СЛАУ, следует разработать ме-
тод и алгоритм реализации ОД чисел или способ вычисления ОВ кода числа (1/С). В гете-
рогенных системах он должен заменять ОД и выполнять её аналог с помощью СУ, закла-
дываемых в ПЭ, для реализации режима ЕТП. Метод должен позволить в параллельном
режиме работы СП реализовать процедуру факторизации матрицы жесткости с помощью
алгоритмов, предложенных и описанных в [2]. Взамен решения исходной матрицы с по-
мощью выражения, свойственного методу Гаусса, связанного с делением на ведущий эле-
мент строки (или столбца) и со сложностями метода (по выбору ведущего элемента, про-
верки его на ноль, перестановками строк (или столбцов) и проч.) предлагается перейти к
реализации уравнения вида
1,1 −−
∗−∗
←
jj
ijiij
i a
aaaa
a j
��
�
. (1)
Запись вида
jijjjii aaaaa
��� ∗−∗← (2)
позволяет известную формулу факторизации по Гауссу для матрицы nnA с коэффициента-
ми ,ija nji ,1, = :
38 ISSN 1028-9763. Математичні машини і системи, 2014, № 1
j
jj
ij
ii a
a
a
aa
��� ∗−← (3)
заменить алгоритмом реализации выражения:
.)( 1
1,1
−
−−∗∗−∗← jjjijijji aaaaaa
���
(4)
Замена в выражении (4) ОД операцией умножения на ОВ 1
1,1
−
−− jja :
11,1 =−− jjL / 1,1 −− jja = 1
1,1
−
−− jja (5)
от значения диагонального коэффициента предыдущей 1,1 −− jja , ранее вычисленной строки
(при условии, что 111 ≡a ), позволяет исключать традиционное выполнение ОД из алго-
ритма решения СЛАУ по ЕТП.
Для решения итерационным методом Ньютона-Рафсона нелинейных уравнений ви-
да
)(/)( '
1 rrrr xfxfxx −=+ , (6)
где )( rxf – значение функции )( rxf в точке ( rx ( ))rf x ;
)(' rxf – значение производной в точке ( rx , '( ))rf x .
В работе [8 ] предложен и рассмотрен метод решения уравнения (6). Согласно методу, ис-
ходное уравнение (6) предлагается записывать в виде РПМ и операцию деления функции
)( rxf на производную )(' rxf от неё заменять умножением функции на обратное значение
производной от нее. Для этого после вычисления 1
r
' ]Ф[ − необходимо выполнять операции
=rδ 1
r
'
r ]Ф[]Ф[ −∗ с помощью функций, записанных в виде РМП.
Постановка задачи
Разработать метод и алгоритм реализации ОД на структуре типа СУ. С этой целью опера-
цию деления числа B на число С с получением частного от деления A
ACB =: (7)
предлагается выполнять так:
}{B ∗ }{ 1−C = }{A . (7а)
Для решения (7а) следует вычислить обратную от делителя ][C матрицу ][ 1−C и
матрицу делимого ][B умножить на обратную от делителя матрицу ][ 1−C , получив в ре-
зультате ОВ частного ][A от деления (7).
Решение задачи
Известно, что последовательность
},...,,,{ 210 nccccC = (8)
в двоичной, например, позиционной системе счисления определяет число C :
=C n
n
i
i ccccc −−−− +++++ 2...2...222 2
2
1
1
0
0 , (9)
а полином )(xp вида
ISSN 1028-9763. Математичні машини і системи, 2014, № 1 39
n
n xaxaxaxaxP ++++= ...)( 2
2
1
100 (10)
в виде аппроксимирующего ряда
...,)(
3
3
2
21 +++≈
x
c
x
c
x
c
xf →x ∞ (11)
можно записать, положив ,...2,2,2 332211 −−−−−− === xxx .
Тогда рассмотрим двоичное представление числа в позиционной системе в виде по-
линомиального кода
0
0 2{cC ≈ 1
1 2−c i
ic −2 … }2 n
nc − , ∞→n . (12)
Запишем его с помощью РМП в матричном виде и будем рассматривать выполне-
ние алгебраических операций по алгоритму факторизации матрицы над соответствующи-
ми полиномами, используя методы алгебры матриц. При этом число C (12) можно запи-
сать [1, 2] в виде
][)( CCf → �
−
−
0
20
110
210
......
...
...
...
c
cc
ccc
cccc
n
n
n
. (13)
Для матрицы ][C будем рассматривать TC][ , транспонированную к матрице ][C :
)(Cf T
� =TC][
−− 021
012
01
0
......
............
cccc
ccc
cc
c
nnn
, (14)
а также вектор ]С[ * :
)(* Cf � ]С[ * =
nc
c
c
c
...
2
1
0
= [ ]T
ncccc ...210 = )]([ * Cf , (15)
как это предложено в [1] и рассмотрено в [4–7] для функций с записью полиномов в виде
РМП.
В (13–15) число, аналогично полиному, записано c помощью РМП по принципу
циклической записи битов (разрядов) с учетом их веса в виде верхне треугольной матри-
цы. В записи на месте 11c (на главной диагонали) матрицы ][C всегда стоит старший раз-
ряд 1
1 2−∗c мантиссы числа, записанного в устройстве в виде ПЗ, а на месте nc1 – младший
разряд числа n
nc −∗ 21 . На главной iic диагонали матрицы ][C всегда стоят «1». Это сле-
дует из того, что iic = ,1 , ni ,1= – старшая значащая цифра нормализованной мантиссы чис-
40 ISSN 1028-9763. Математичні машини і системи, 2014, № 1
ла весом 2/112/12 1
1 =∗=− c . Далее, в 1-й строке матрицы ]C (в сторону убывания), стоят
разряды с меньшим весом 2
22( c− 3
32 c− … )2 n
n c− , то есть следующие биты числа с учетом
их веса в пределах разрядной сетки.
На практике это означает, что вычисление обратной матрицы 1][ −C по правилам ал-
гебры матриц методом факторизации по Гауссу сводится к исключению прямого хода, на
котором формируется верхне треугольная матрица. При этом заранее определено, что раз-
мерность cm матрицы ][C (делителя), матрицы ][B (делимого) Bm , а также вектора
столбца ][ *C совпадает. Кроме того, поскольку мантиссы чисел, представленных в прямом
коде в форме ПЗ, равны «1», а их вес равен 2/1 , то произведение
4/12/12/11 =∗=∗ −
iiii cb даёт смещение в пределах разрядной сетки на единицу в сторону
младшего разряда и в принятом формате чисел гарантирует от переполнения.
2. Получение обратной 1][ −C матрицы от числа в РМП
Пусть матрица ][C представляет число
== }110{.C 8/68/104/112/11}222{ 3
3
2
2
1
1 =∗++∗=++ −−−
�ccc (16)
с записью в форме РМП:
=][C
1
11
011
. (17)
Вычислим обратную 1][ −C матрицу традиционным способом:
jc1 jc2 jc3 1je 2je 3je (18)
=−1][C
1001
01011
001011
�
−
−
100
110
111
−
−
1111
1101
1001
.
Полученная матрица 1][ −C записана в виде РМП, также верхне треугольная имеет
целочисленные значения, но отдельные биты числа C (коэффициенты ijc ) имеют отрица-
тельные значения, некоторые из них отличны от 1± и являются многозначными числами.
Естественно, что произведение матрицы ][C на обратную 1][ −C даёт единичную
][E матрицу.
Появление отрицательных значений битов (коэффициентов матрицы) в 1][ −C требу-
ет изменения в традиционном двухпозиционном представлении битов "0" и "1" и иден-
тификации их как разрядов числа, а не как коэффициентов полинома.
ISSN 1028-9763. Математичні машини і системи, 2014, № 1 41
Далее при рассмотрении способов получения ОВ для упрощения изложения пред-
лагаемых решений используется десятичная запись отдельных разрядов ОВ при двухпози-
ционном представлении числа в целом.
Рассмотрим выполнение ОД традиционным методом и варианты получения ОВ ко-
да числа предлагаемыми способами.
3. Примеры
Выполнение ОД традиционным ⊗ ) методом «углом»
Разделим число 01111.32/15 ==B (делимое) на число 11000.32/244/3 ===C (дели-
тель), получая в результате A (частное):
01010.32/208/5 ===A (19)
(частное) [9, 10].
Деление 1-го остатка )(B 01111.
11110. 1100.
.11000 01010 (A)
00110. второй остаток
01100. удвоение 2-го остатка
11000. удвоение 3-го остатка
11000.− 4-й остаток
00000. 5-й остаток
00000. удвоение 5-го остатка
00000.− 6-й остаток.
4. Выполнение операции (вычисление ОВ кода числа) предлагаемым способом
Рассмотрим умножение делимого )(B на обратную 1][ −C матрицу от числа ][C .
Представим делимое B с помощью РМП в виде матрицы ][ 1B , в которой число
...}2222{ 3
3
2
2
1
1
0
0 bbbbB = сдвинуто влево на один разряд в сторону старшего )(B
разряда (нормализовано):
1B �
=
1
11
111
1111
01111
][ 1B , (20)
а делитель C с помощью РМП представим в виде матрицы
C �
=
1
11
011
0011
00011
][C (20а)
и записываем его без сдвига (поскольку C представлено в нормализованном виде).
42 ISSN 1028-9763. Математичні машини і системи, 2014, № 1
Произведем вычисление обратной 1][ −C от матрицы ][C (с присоединенной к ней
единичной матрицей ][E той же размерности):
=−1][C
1 1 0 0 0 1 0 0 0 0
1 1 0 0 0 1 0 0 0
1 1 0 0 0 1 0 0
1 1 0 0 0 1 0
1 0 0 0 0 1
�
1 1 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 1
0 0 0 0 1
− −
− −
−
−
−−
−−
−
−
111111
111101
111001
110001
100001
. (21)
Легко проверить, что произведение матриц ][C ∗ 1][ −C дает единичную матрицу ][E :
][C ∗ =−1][C
1
11
011
0011
00011
∗
−
−
−−
−−
10000
11000
11100
11110
11111
=
10000
01000
00100
00010
00001
][E= . (22)
Выполним ОВ путем умножения матрицы ][B )11110( =B � )01111( 1 =B
][ 1B (делимое) на обратную матрицу 1][ −C (делитель):
][ 1B ∗ =−1][C
1
11
111
1111
01111
∗
−
−
−−
−−
10000
11000
11100
11110
11111
=
1
01
101
0101
00101
, (23)
Произведение даёт результат, равный числу 2∗A = 10100. в двоичной записи (учи-
тывая сдвиг в сторону старшего на один разряд (20)) при записи числа B в матричном ви-
де ][ 1B , то есть тождественный результат. Деление B на C в матричном виде даёт (анало-
гично с (19)) частное A :
1
1
−∗ CB �
TB ][ 1 =∗ −1*][C
11110
1111
111
11
1
∗
−
−
1
1
1
1
1
=
ISSN 1028-9763. Математичні машини і системи, 2014, № 1 43
=
=∗+−∗+∗+−∗+∗
=−∗+∗+−∗+∗
=∗+−∗+∗
=−∗+∗
=∗
031)2(110)1(110
0)2(111)1(011
011)1(110
0)1(111
111
0
0
0
0
1
5
4
3
2
1
−
−
−
−
−
x
x
x
x
x
.= ]00101.[ = }{A � 1A , (24)
которое после денормализации (числа 1A ) будет 1A � A ={ 01010 }.
Полученные таким образом результаты равны
A� ][B ∗ 1][ −C = 01010 =5/8 /B C= . (25)
5. Варианты вычисления ОВ
Рассмотрение процедуры вычисления ОВ (21) по типу обратного хода метода факториза-
ции матрицы показывает дополнительные (в вычислительном плане) возможности. Мат-
рица 1][ −C в форме РМП может формироваться из одного n -го (правого крайнего) столбца
единичной матрицы, с помощью которого она вычисляется. Покажем это на примере.
Для числа
C = [ ]01011. (26)
выполним обращение матрицы ][C путем введения вектор-столбца ,ijE 1,ni = , nj = для
матрицы nnE , , присоединенной к матрице ][ ,nnC , с последующим вычислением значений
iic , 1,ni = в виде j -х вектор столбцов и с коррекцией значений
jic , , ,nj = 1,...,1, −ii .
Запишем первый столбец (правую часть для вычисляемой обратной матрицы):
1
1][ −C =
100001
0100011
00100011
000101011
0000101011
�
11
011
0011
01011
001011
�
1
2][ −C . (26а)
Вычислим пятый столбец матрицы ][C и запишем его в качестве правой части об-
ратной матрицы:
1c 2,ic … 1, −nic nni ec ∗,
)(
1,
)(
,
)(
,
211 )( j
ni
j
nni
j
ni eece −=∗− , nnn ec =,
1
2][ −C =
⇒
−⇒=∗
⇒=∗
−⇒=∗
⇒=∗
11
1]1)11[(1
0]0)10[(11
1]1)11[(011
0]0)10[(1011
=
⇒
−⇒
⇒
−⇒
⇒
1
11
011
1011
01011
�
1
3][ −C . (26б)
Вычислим четвертый столбец матрицы ][C и запишем его в качестве правой части
обратной матрицы:
44 ISSN 1028-9763. Математичні машини і системи, 2014, № 1
=−1
3][C
⇒
−⇒
⇒=−−−=−∗
−⇒−=−−=−∗
⇒=−−−=−∗
1
1
11))1(0(]1))1(1[(1
11)0)1(]0))1(0[(11
11))1(0(]1))1(1[(011
�
1
4][ −C . (26в)
Вычислим третий столбец матрицы ][C и запишем его в качестве правой части об-
ратной матрицы:
=−1
4][C
−
−⇒−=−−=∗
⇒=−=∗
1
1
1
22)11(1)11(1
11)01(0)10(11
�
1
5][ −C . (26г)
Вычислим второй столбец матрицы ][C и запишем его в качестве правой части об-
ратной матрицы:
=−1
5][C
−
−
⇒=−−−=−∗
1
1
1
2
33)2(12)2(111
. (25д)
В итоге получим вектор-столбец, который является первой строкой вычисляемой
обратной матрицы 1][ −C . В ней, по аналогии с записью полиномов в виде РМП, на месте
ne1 – стоит младший разряд )2( n
nc −∗ обратного числа, а на месте nne – старший разряд
)2( 1
1
−∗c обратного числа:
=−1][C
11
011
0011
01011
001011
�
−
−
−−
−−
1
11
111
2111
32111
=
−
−
3
2
1
1
1
5
4
3
2
1
−
−
−
−
−
x
x
x
x
x
= (26е)
= [ ] =∗−− − }{32111 iT X .][ * TC (26ж)
Алгоритм формально можно записать так.
1. ,1)1(
, == nnn ec .
2. Умножив −i е )2,( ni = элементы )( ,nic ведущего столбца на )1(
ne
nic , =∗ )1(
ne
− )( ,
)1(
nin ce , 1,ni = ,
ISSN 1028-9763. Математичні машини і системи, 2014, № 1 45
получим вычисленный ведущий столбец.
3. Из вектор-столбца nie , (уменьшаемое) вычтем вектор ведущего столбца (вычитаемое):
)( j
ie -
∗ )(
,
j
nni ec =
∗− )( , nnii ece .
4. Из уравнения следующей )1( −n -й строки матрицы ][C , где выполняется равенство
− nnc ,1 =∗ −1ne
− ∗− ),1(
nennn ce ,
определяем очередное )1( −n -е значение разряда ОВ кода числа 1][ −C .
5. ).( ,11 nnnnn ecec ∗−= −−
В отличие от алгоритма решения уравнения bAx = правую часть уравнения (п. 5) не делим
на величину )1( 1,1 =−− nnc в силу отсутствия смысла в делении на 1.
6. Делаем )1( −n -й столбец ведущим. Умножаем его элементы 1, −nic )1),2(( −= ni на зна-
чение .1−ne Получим значение соответствующего разряда ведущего )1( −n -го столбца мат-
рицы ].[C
7.
∗ −− 1,1 nin ce =
∗ −− )( 11, nni ec 1),1( −= ni .
Запоминаем их значения взамен соответствующих предыдущего вектор-столбца.
8. Вычисляем вектор ОВ кода числа. Для i -й строки )1),2(( −= ni матрицы ][C он равен
)( j
ie =
∗− ∑
+=
n
ij
jij
j
i ece
1
)( )( , 2),1( −= nj , 1),1( −= ni .
9. Текущее i -е значение ОВ разряда кода числа 1][ −C для i -й строки:
∑
+=
− ∗−=
n
ij
jij
j
i
j
i ecee
1
)1()( )( , 2),1( −= nj , 1),2( −= ni ,
причем в отличие от алгоритма решения системы bAx = по методу, предложенному и
описанному в [2], правую часть уравнения по п. 9 нет смысла делить на 1=ijc (диагональ-
ные элементы матрицы для нормализованного числа в записи РМП всегда равны “1”) и т.д.
То есть автоматически срабатывает приведенная в [2] коррекция алгоритма:
10.
.
,1
,1/1
)()(
1
j
i
j
i
iinn
iiiiii
ec
Lec
ccL
=
=∗=
=== −
46 ISSN 1028-9763. Математичні машини і системи, 2014, № 1
Алгоритм вычисления обратного значения 1][ −C , таким образом, заключается в следую-
щем:
а) умножить вектор-столбец ,ic 1,1,...,1, nnni =−= на значение ic , 1,ni = , вычис-
ленное на i -м шаге;
б) положить 1, == nnn ec ;
в) приравнять с обратным знаком значения ic -го ( )1,1( −= ni столбца матрицы ][C
к правой части матрицы ][][ neE = , то есть ][][ ,, nini ec =− ( )1,1( −= ni , что равносильно вы-
читанию из правой части матрицы вычисленного значения текущего столбца;
в) вычислить значения )1( −i -столбца по п. а) Алгоритма и так далее до 11c ;
г) вычисленный на n -м шаге вектор-столбец после транспонирования его является
обратным числом 1}{ −C от исходного }{C , каждый из коэффициентов вектора является це-
лочисленным коэффициентом i
ic −∗ 2 , ni ,1= числа }{C (10), взятым со своим весом i−2 .
Замечание
Следует учитывать, что число TC*][ получено с помощью выражения (21–26) как полином
вида (10–11) в соответствии с правилами алгебры матриц с РМП. Поэтому, если операции
c ним выполнять, как с вектором, в соответствии с правилами алгебры матриц, то следует
помнить правило, что операнды в алгебре матриц не коммутативны. Но если его рассмат-
ривать как число, то на него будет распространяться правило коммутативности операции
умножения.
Рассмотрим некоторый набор структур матрицы ][ ,nnC , который образуется при вы-
числении матрицы 1][ −C :
TC*][ =[10000]=(16/32=0,5)� =−1][C [10000]=(16/32=05),
).5,01024/512(]1000000000[][ 1
1 ===−C 000,0=δ ,
TC*][ =[10001]=(17/32=0,53125)� =−1][C [1000-1]=(15/32=0,46875),
).470703125,01024/482(]1000101000[][ 1
1 ==−=−C 001953125,0=δ ,
TC*][ =[10010]=(18/3=0/5625)� =−1][C [100-10]=(14/32=0,4375),
.)444335937,01024/455(]1100100100[][ 1
1 ==−−=−C 006835937,0=δ ,
TC*][ =[10011]=(19/32=0,59375)� =−1][C [100-1-1]=(13/32=0,40625),
=−1
1 ][C [100-110101-1]=(410/1024=0,400390625), 005859375,0−=δ
TC*][ =[10100]=(20/32=0,625)� =−1][C [10-101]=(13/32=0,40625),
=−1
1 ][C [10-1010-1010]=(489/1024=0,400390625). 005859375,0−=δ ,
TC*][ =[10101] =(21/32=0,65625)� =−1][C [10100]=(12/32=0,375),
.)380859375,01024/390(]1010001010[][ 1
1 ==−−=−C 005859375,0=δ ,
TC*][ =[10110]=(22/32=0,6875)� =−1][C [10-111]=(11/32=0,34375),
=−1
1 ][C [10-1-1120-3-23]=(371/1024 =0,368164062 ), 024414062,0+=δ ,
ISSN 1028-9763. Математичні машини і системи, 2014, № 1 47
TC*][ =[10111]=(23/32=0,71875)� =−1][C [10-1-10]=(10/32=0,3125),
=−1
1 ][C [10-1-1022-1-4-3]=(353/1024=0344726562), ,032226562,0+=δ
TC*][ =[11000]=(24/32=0,75)� =−1][C [1-11-11]=(11/32=0,34375),
=−1
1 ][C [1-11-11-11-11-1]=(341/1024=0,333007812), ,010742187,0−=δ
TC*][ =[11001]=(5/32=0,78125)� =−1][C [1-11-10]=(10/32=0,3125),
=−1
1 ][C [1-11-10-10-110]=(302/1024=0,30078125), 01171875,0−=δ ,
TC*][ =[11010]=(26/32=0,8125)� =−1][C [1-11-23]=(11/32=0,34375),
=−1
1 ][C [1-11-23-46-913-19]=(307/1024=0,299804687), ,043945312,0−=δ
TC*][ =[11011] =(27/32=0,84375)� =−1][C [1-11-22]=(10/32=0,3125),
=−1
1 ][C [1-11-22-23-33-4]=(334 /1024=0,294921875), ,017578125,0−=δ
TC*][ =[11100]=(28/32=0,875)� =−1][C [1-101-1]=(9/32=0,28125),
=−1
1 ][C [1-10-101-101]=(293/1024=0,286132812), ,001882812,0+=δ
TC*][ =[11101]=(29/32=0,90625)� =−1][C [1-101-2]=(8/32=0,25)
=−1
1 ][C [1-101-220-35-4]=(282/1024=0,275390625), ,025390625,0+=δ
TC*][ =[11110]=(30/32=0,9375)� =−1][C [1-1001]=(/32=0,28125),
=−1
1 ][C [1-101-220-35-4]=(273/1024=0,266601562), ,014698437,0−=δ
TC*][ =[11111]=(31/32=0,96875)� =−1][C [1-1000]=(8/32=0,25)
=−1
1 ][C [1-101-220-35-4]=(264/1024=0,2578125). 0078125,0+=δ . (27)
Анализ структур TC*][ и 1][ −C показывает:
– значительную погрешность при вычислении обратного значения от числа, пред-
ставленного только пятью разрядами, но точность возрастает на величину δ с увеличением
разрядности вдвое;
– отдельные разряды обратного числа, оставаясь в целочисленном представлении,
кроме изменения знака, выходят из двухпозиционного представления его. Но вес каждого
i -го разряда соответствует его весу i−2 (положению) в пределах разрядной сетки исходно-
го числа с двоичным представлением. Это указывает на возможные отклонения, которые
возникнут при реализации операции умножения множимого (делимого), представленного
числом с разрядами в двухпозиционном виде (“0” и “1”), на множитель (делитель), струк-
тура которого представлена также в виде двухпозиционного числа, но:
– каждый из разрядов может быть со знаком плюс или минус;
– значение каждого текущего разряда (кроме первых двух вычисляемых), оставаясь
целым числом, может отличаться от “0” и “1”.
48 ISSN 1028-9763. Математичні машини і системи, 2014, № 1
6. Выводы
1. Предлагаемый метод вычисления ОВ кода числа, выполненный в алгебре матриц, реали-
зует операцию деления (в классическом понимании операции), используя операцию умно-
жения кода делимого на обратное значение кода делителя.
2. Замена операции деления на умножение обеспечивает правило коммутативности исход-
ных данных, что даёт дополнительные преимущества при реализации операции в СП.
3. Операцию выполняем над числами в позиционной (например, двоичной) системе счис-
ления. Результат по методу определения ОВ кода числа совпадает с результатом ОД, полу-
ченным классическим методом. При этом частное от деления (число) сохраняет позицион-
ное представление числа, в котором и заданы исходные операнды (делимое и делитель).
Но каждый разряд определяемой ОВ кода числа может принимать значения "0" , "1"± или
другое многозначное число с разными знаками и “весом”, равным номеру позиции данного
разряда позиционно представленного числа.
4. Определение ОВ кода числа по предлагаемому алгоритму для замены операции деления
основано на использовании методов алгебры матриц. Оно базируется на использовании
процедуры, аналогичной выполнению обратного хода метода факторизации матрицы с за-
писью числа как полинома в формате РМП.
5. Операцию можно упростить. Частично это будет показано во второй части статьи. Но
дополнительные исследования и анализ предложенных решений выполнения операции (по
замене традиционной ОД и отдельных этапов её) следует провести. Поиски и разработки в
плане комбинирования методов алгебр матриц и цифровой арифметики могут дать новые
интересные решения.
Заключение
В рамках выделяемого для статьи объёма трудно предложить и изложить метод решения, а
также все нюансы отдельных этапов метода. Предполагается, что метод даст толчок для
дальнейшего его продвижения специалистами в области разработки, адаптации вычисли-
тельных методов для создания высокопроизводительных параллельных структур, особен-
но архитектур гетерогенного типа, обеспечивающих сверхвысокую производительность
при снижении затрат на обработку единицы информации.
Идея выполнения операции деления (как и метода факторизации матрицы [2]) была
предложена автором во время работы в МП ПАК “Вычислительные средства, программи-
рование и технология“ Института кибернетики им. В.М. Глушкова АН УССР, организо-
ванном в конце 80-х годов прошлого столетия для создания спецпроцессора новой архи-
тектуры, и проработана в ТОО “ФИРМА “ПАК”. В силу форсмажорных обстоятельств ра-
боты по спецпроцессору были остановлены. По этой причине была задержана и публика-
ция. Настоящая статья подготовлена к передаче в печать в год 90-летия светлой памяти
академика В.М. Глушкова – талантливого ученого-кибернетика и алгебраиста, менеджера
и человека, которому наука и мы во многом обязаны.
Считаю приятным долгом выразить свою признательность В.П. Клименко, который
стимулировал написание и оказал содействие в издании цикла статей [2–8] в направлении
работ, поддержанном в своё время В.М. Глушковым.
СПИСОК ЛИТЕРАТУРЫ
1. Ледянкин Ю.Я. Единый технологический поток в организации вычислений – способ повышения
производительности параллельных структур на процессорных элементах транспьютерного типа. –
Киев, 1989. – 20 с. – (Препр. /АН УССР. Ин-т кибернетики им. В.М. Глушкова; 89-57).
2. Ледянкин Ю.Я. Способы параллельного решения систем bAx = в едином технологическом по-
токе решения задач математической физики / Ю.Я. Ледянкин // Математичні машини і системи. –
2013. – № 1. – С. 63 – 74.
ISSN 1028-9763. Математичні машини і системи, 2014, № 1 49
3. Клименко В.П. Вычислительные системы. Тенденции развития архитектуры гетерогенных
структур / В.П. Клименко, Ю.Я. Ледянкин // Математичні машини і системи. – 2013. – № 2. – С. 19
– 31.
4. Ледянкин Ю.Я. К вопросу преобразования и параллельного ввода граничных условий при реше-
нии краевых задач в едином вычислительном потоке / Ю.Я. Ледянкин // Математичні машини і
системи. – 2012. – № 1. – С. 28 – 25.
5. Ледянкин Ю.Я. Методы взвешенных невязок, колллокаций, моментов. Способ параллельной
реализации в едином вычислительном потоке решения задач математической физики / Ю.Я. Ле-
дянкин // Математичні машини і системи. – 2012. – № 2. – С. 17 – 28.
6. Ледянкин Ю.Я. Метод Галеркина. Способ параллельной реализации задач математической фи-
зики в едином вычислительном потоке / Ю.Я. Ледянкин // Математичні машини і системи. – 2012.
– № 3. – С. 69 – 80.
7. Ледянкин Ю.Я. Метод наименьших квадратов. Способ параллельной реализации в едином вы-
числительном потоке решения задач математической физики / Ю.Я. Ледянкин // Математичні ма-
шини і системи. – 2012. – № 4. – С. 59 – 69.
8. Ледянкин Ю.Я. Способ параллельной реализации метода Ньютона-Рафсона в едином технологи-
ческом потоке на спецпроцессоре для решения задач математической физики / Ю.Я. Ледянкин //
Математичні машини і системи. – 2013. – № 4. – С. 38 – 49.
9. Карцев М.А. Арифметика цифровых машин / Карцев М.А. – М.: Гл. ред. Физ.-мат. лит., Наука,
1969. – 576 с.
10. Карцев М.А. Вычислительные системы и синхронная арифметика / М.А. Карцев, В.А. Брик. –
М.: Радио и связь, 1981. – 360 с.
Стаття надійшла до редакції 13.11.2013
|
| id | nasplib_isofts_kiev_ua-123456789-84330 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-11-30T15:57:09Z |
| publishDate | 2014 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Ледянкин, Ю.Я. 2015-07-06T15:58:44Z 2015-07-06T15:58:44Z 2014 Операция деления для параллельных вычислительных систем. Ч. 1 / Ю.Я. Ледянкин // Математичні машини і системи. — 2014. — № 1. — С. 36-49. — Бібліогр.: 10 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/84330 681.3 Предлагается цифровой метод выполнения арифметической операции деления (ОД). Алгоритм обеспечивает распараллеливание вычислительного процесса, ускорение его и повышение точности ОД. Он основан на выполнении этапов операций в алгебре матриц и реализации методов цифровой арифметики в булевой (возможно, многозначной) алгебре. Рассмотрены варианты выполнения ОД и примеры решения. Предполагается развитие аналогичных работ в плане создания и использования комбинированных алгоритмов обработки данных путём применения других алгебр в сочетании с методами цифровой арифметики. Пропонується цифровий метод виконання арифметичної операції ділення (ОД). Алгоритм забезпечує розпаралелювання обчислювального процесу, прискорення його і підвищення точності. Він заснований на виконанні етапів операцій в алгебрі матриць і реалізації методів цифрової арифметики в булевій (можливо, у багатозначній) алгебрі. Розглянуто варіанти виконання операції та приклади рішення. Передбачається розвиток аналогічних робіт у плані створення і використання комбінованих алгоритмів обробки даних шляхом застосування інших алгебр у поєднанні з методами цифрової арифметики. It is proposed the digital method of performing arithmetic division operations (DO). Algorithm provides the parallelizing of computing process, its acceleration and accuracy increase. It is based on carrying out the steps of operations in the matrix algebra and realization of digital arithmetic in Boolean (possibly multi-valued) algebra. Variants of the execution of operation and examples of solutions are regarded. The development of similar projects for the creation and use of combined data processing algorithms by applying other algebras in combination with the methods of digital arithmetic is suggested. Считаю приятным долгом выразить свою признательность В.П. Клименко, который стимулировал написание и оказал содействие в издании цикла статей [2–8] в направлении работ, поддержанном в своё время В.М. Глушковым. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Операция деления для параллельных вычислительных систем. Ч. 1 Операція поділу для паралельних обчислювальних систем. Ч. 1 Division operation for parallel computing systems Article published earlier |
| spellingShingle | Операция деления для параллельных вычислительных систем. Ч. 1 Ледянкин, Ю.Я. Обчислювальні системи |
| title | Операция деления для параллельных вычислительных систем. Ч. 1 |
| title_alt | Операція поділу для паралельних обчислювальних систем. Ч. 1 Division operation for parallel computing systems |
| title_full | Операция деления для параллельных вычислительных систем. Ч. 1 |
| title_fullStr | Операция деления для параллельных вычислительных систем. Ч. 1 |
| title_full_unstemmed | Операция деления для параллельных вычислительных систем. Ч. 1 |
| title_short | Операция деления для параллельных вычислительных систем. Ч. 1 |
| title_sort | операция деления для параллельных вычислительных систем. ч. 1 |
| topic | Обчислювальні системи |
| topic_facet | Обчислювальні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84330 |
| work_keys_str_mv | AT ledânkinûâ operaciâdeleniâdlâparallelʹnyhvyčislitelʹnyhsistemč1 AT ledânkinûâ operacíâpodíludlâparalelʹnihobčislûvalʹnihsistemč1 AT ledânkinûâ divisionoperationforparallelcomputingsystems |