Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке
Развивается идея создания единого вычислительного (технологического) потока в организации параллельных вычислений на уровне сложных структур данных как способа повышения производительности устройств, включающих скалярный умножитель. Предполагается исключение деления на каждой итерации. Розвивається...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2013 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84270 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке / Ю.Я. Ледянкин // Математичні машини і системи. — 2013. — № 4. — С. 38-49. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84270 |
|---|---|
| record_format |
dspace |
| spelling |
Ледянкин, Ю.Я. 2015-07-05T07:17:56Z 2015-07-05T07:17:56Z 2013 Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке / Ю.Я. Ледянкин // Математичні машини і системи. — 2013. — № 4. — С. 38-49. — Бібліогр.: 10 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/84270 681.3 Развивается идея создания единого вычислительного (технологического) потока в организации параллельных вычислений на уровне сложных структур данных как способа повышения производительности устройств, включающих скалярный умножитель. Предполагается исключение деления на каждой итерации. Розвивається ідея створення єдиного обчислювального (технологічного) потоку в організації паралельних обчислень на рівні складних структур даних як способу підвищення продуктивності пристроїв, що включають скалярний помножувач. Передбачається виключити операції ділення на кожній ітерації. It is developed the idea of creating a single computational (technological) thread to organize parallel calculations at the level of complex data structures as a way to improve the performance of devices which include a scalar multiplier. It is expected to exclude the division operations at each iteration. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке Спосіб паралельної реалізації методу Ньютона-Рафсона на спецпроцесорі в єдиному обчислювальному потоці A way of parallel implementation of the Newton-Raphson method on specialized processor in a single computational thread Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке |
| spellingShingle |
Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке Ледянкин, Ю.Я. Обчислювальні системи |
| title_short |
Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке |
| title_full |
Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке |
| title_fullStr |
Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке |
| title_full_unstemmed |
Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке |
| title_sort |
способ параллельной реализации метода ньютона-рафсона на спецпроцессоре в едином вычислительном потоке |
| author |
Ледянкин, Ю.Я. |
| author_facet |
Ледянкин, Ю.Я. |
| topic |
Обчислювальні системи |
| topic_facet |
Обчислювальні системи |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Спосіб паралельної реалізації методу Ньютона-Рафсона на спецпроцесорі в єдиному обчислювальному потоці A way of parallel implementation of the Newton-Raphson method on specialized processor in a single computational thread |
| description |
Развивается идея создания единого вычислительного (технологического) потока в организации параллельных вычислений на уровне сложных структур данных как способа повышения производительности устройств, включающих скалярный умножитель. Предполагается исключение деления на каждой итерации.
Розвивається ідея створення єдиного обчислювального (технологічного) потоку в організації паралельних обчислень на рівні складних структур даних як способу підвищення продуктивності пристроїв, що включають скалярний помножувач. Передбачається виключити операції ділення на кожній ітерації.
It is developed the idea of creating a single computational (technological) thread to organize parallel calculations at the level of complex data structures as a way to improve the performance of devices which include a scalar multiplier. It is expected to exclude the division operations at each iteration.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84270 |
| citation_txt |
Способ параллельной реализации метода Ньютона-Рафсона на спецпроцессоре в едином вычислительном потоке / Ю.Я. Ледянкин // Математичні машини і системи. — 2013. — № 4. — С. 38-49. — Бібліогр.: 10 назв. — рос. |
| work_keys_str_mv |
AT ledânkinûâ sposobparallelʹnoirealizaciimetodanʹûtonarafsonanaspecprocessorevedinomvyčislitelʹnompotoke AT ledânkinûâ sposíbparalelʹnoírealízacíímetodunʹûtonarafsonanaspecprocesorívêdinomuobčislûvalʹnomupotocí AT ledânkinûâ awayofparallelimplementationofthenewtonraphsonmethodonspecializedprocessorinasinglecomputationalthread |
| first_indexed |
2025-11-25T22:31:41Z |
| last_indexed |
2025-11-25T22:31:41Z |
| _version_ |
1850566087252377600 |
| fulltext |
38 © Ледянкин Ю.Я., 2013
ISSN 1028-9763. Математичні машини і системи, 2013, № 4
УДК 681.3
Ю.Я. ЛЕДЯНКИН*
СПОСОБ ПАРАЛЛЕЛЬНОЙ РЕАЛИЗАЦИИ МЕТОДА НЬЮТОНА-РАФСОНА НА
СПЕЦПРОЦЕССОРЕ В ЕДИНОМ ВЫЧИСЛИТЕЛЬНОМ ПОТОКЕ
*МП «ПАК» Института кибернетики имени В.М. Глушкова АН УССР, Киев, Украина
Анотація. Розвивається ідея створення єдиного обчислювального (технологічного) потоку в
організації паралельних обчислень на рівні складних структур даних як способу підвищення
продуктивності пристроїв, що включають скалярний помножувач. Передбачається виключити
операції ділення на кожній ітерації.
Ключові слова: задачі математичної фізики, єдиний технологічний потік, поліноми, складні
структури даних, паралельні обчислення, спецпроцесор, скалярний помножувач.
Аннотация. Развивается идея создания единого вычислительного (технологического) потока в
организации параллельных вычислений на уровне сложных структур данных как способа повыше-
ния производительности устройств, включающих скалярный умножитель. Предполагается ис-
ключение деления на каждой итерации.
Ключевые слова: задачи математической физики, единый технологический поток, полиномы,
сложные структуры данных, параллельные вычисления, спецпроцессор, скалярный умножитель.
Abstract. It is developed the idea of creating a single computational (technological) thread to organize
parallel calculations at the level of complex data structures as a way to improve the performance of de-
vices which include a scalar multiplier. It is expected to exclude the division operations at each iteration.
Keywords: problems of mathematical physics, single technological thread, polynomials, complex data
structures, parallel calculations, specialized processor, scalar multiplier.
1. Введение
Поскольку современная вычислительная математика в основном ориентирована на после-
довательное выполнение арифметических операций, а возникает потребность в переходе к
обработке сложных структур данных (ССД), необходимо разрабатывать новые методы,
способы реализации существующих с их трансформацией под аппаратную реализацию в
параллельной структуре.
В [1, 2] автором рассмотрены различные задачи математической физики (МФ) как
стационарные, так и нестационарные, с различными краевыми условиями, с аппроксима-
цией явными и неявными схемами на различных сетках с методами конечно-разностной
аппроксимации (МКР) с реализацией их на спецпроцессоре параллельного типа.
В [3] предложен и описан метод решения задач МФ методом конечных элементов
(МКЭ) с аппроксимацией кусочно-гладкими полиномиальными функциями (сплайнами) в
едином технологическом потоке (ЕТП) в математическом плане с последующим отобра-
жением структуры решаемой задачи на структуру устройства.
Основная цель, которая ставилась в этих работах, определить основной набор
арифметико-логических операций, которые следует заложить в спецпроцессор (СП) парал-
лельного типа, чтобы он смог решать такие задачи в ЕТП (в математическом плане). От-
сюда следует, что и оборудование СП, реализующее такой ЕТП (в техническом плане), бу-
дет максимально технологически однотипным и будет его отражать. А это определит и
экономическую составляющую проекта. Желательно, чтобы операнды в виде ССД обраба-
тывались за время, соизмеримое со временем выполнения арифметической операции. То-
гда повышение производительности спецпроцессора будет гарантировано.
Такого рода ЕТП был предложен в [3]. В основу ЕТП заложена идея аппроксимации
исходных аналитических уравнений с помощью сплайнов, записываемых в виде регуляр-
ISSN 1028-9763. Математичні машини і системи, 2013, № 4 39
ного матричного представления (РМП). За время, соизмеримое со временем выполнения
одной арифметической операции, скалярный умножитель (СУ) в составе процессорного
элемента (ПЭ) СП параллельного типа вычисляет сумму парных произведений [2] коэф-
фициентов полиномов (обрабатывается ССД).
Разработке и созданию архитектур на базе спецпроцессоров, ориентированных на
класс конкретных задач, всегда сопутствовало естественное желание разработчиков рас-
ширить круг решаемых задач. При решении практических задач часто возникает потреб-
ность в решении нелинейных уравнений, нахождении корней полиномов, поиске общего
решения двух уравнений, которые в общем случае, являясь нелинейными, описываются
полиномами. Тем более, что точные формулы, как правило, не позволяют находить корни
полиномов высших порядков.
С этой целью часто используют итерационный метод Ньютона-Рафсона (МНР), ко-
торый эффективен в плане точности и скорости нахождения решения.
Но в том виде, в котором метод представлен и описан в [4, 5], он больше рассчитан
на использование в машинах с последовательной обработкой данных. Это плохо подходит
для СП параллельного типа, предложенного в [3], в котором предполагается обработка
информации на уровне ССД.
2. Постановка задачи
Трансформировать метод Ньютона-Рафсона таким образом, чтобы его можно было ис-
пользовать в структурах параллельного типа.
В общем виде итерационный процесс по методу Ньютона-Рафсона записывают так:
1+rx rx= − )(/)( '
rr xfxf . (1)
Обозначим:
( )rf x (2)
– значение функции ( )rf x в точке ( rx , ( )rf x );
'( )rf x (2а)
– значение производной '[ ( )]rf x от функции в точке ( rx , '( )rf x ).
Обозначим:
)(xf �[Ф ]γ , )(| xf � ]Ф[ |
r (2б)
– значение функции и производной от нее в виде РМП;
| 1
r[Ф ]− (2в)
– обратная матрица от ]Ф[ |
r такая, что
]Ф[ |
r ∗ | 1
r[Ф ] E− = . (3)
Рассмотрим метод на примере, взятом из [4]. Будем искать точку пересечения пря-
мой
2y x= + (4)
c кубической кривой
3 2 3 1y x x x= − + + . (5)
40 ISSN 1028-9763. Математичні машини і системи, 2013, № 4
Точка пересечения этих двух линий имеет x -координату, определяемую из соот-
ношения
3 22 3 1x x x x+ = − + + , (6)
( ) 3 2 2 1 0p x x x x= − + − = , ( )0 1p = − , ( )1 1p = . (7)
3. Запись полиномов в виде РМП
Запишем полином )(xf
=)(xf 0 1 2
0 1 2 ... k
ka x a x a x a x+ + + + (8)
в виде [3] циклической матрицы [ ( )]f x с РМП:
)(xf �[ ( )]f x =
−
−
0
20
110
210
......
...
...
...
a
aa
aaa
aaaa
k
k
k
. (9)
Тогда матрица, транспонированная к [ ( )]f x , будет
=Txf )]([
− 0111
012
01
0
...
............
...
...
...
aaaa
aaa
aa
a
k
(10)
с записью в виде вектора-столбца ( )*[ ]f x от функции, представленной в матричном виде:
( )*
0 1 2[ ] [ ... ]T
kf x a a a a= . (11)
Произведение )(1 xf и )(2 xf c коэффициентами b равно
( ) ( )1 2f x f x∗ =
...
...
...
0
10
210
a
aa
aaa
∗
...
...
...
0
10
210
b
bb
bbb
=
...
...
...
0
10
210
g
gg
ggg
=
=
+
+++
...)(
...)()(
...)()()(
00
100100
021120100100
ba
bababa
babababababa
(12)
или
Txf )]([
11
*
2[ ( )]f x∗ =
−− 021
012
01
0
...
...
aaaa
aaa
aa
a
kkk
∗
kb
b
b
b
...
2
1
0
=
kg
g
g
g
...
2
1
0
kx
x
x
x
...
2
1
0
. (12а)
ISSN 1028-9763. Математичні машини і системи, 2013, № 4 41
Зададим оператор дифференцирования функции в матричном виде [ ]A так:
0 1 0 0
0 2 0
[ ] .
0 3
... ... ... ...
A dx
=
(13)
Применительно к рассматриваемым уравнениям (4), (5), с учетом (2) и (3), запишем
функцию )(xp (8) в виде РМП:
( )0f x �
0[Ф ] =
−
−
1
31
131
1131
. (14)
4. Решение поставленной задачи
Рассмотрим выражение (1) в такой записи:
1+rx = | |( ( ) ( )) / ( )r r rx f x f x f x− . (15)
Выражение (15) в общем виде с применением РПМ можно записать:
1+rx '
r[Ф ]= rx '
r[Ф ] r[Ф )− . (15а)
Умножив все члены левой и правой частей полученного выражения справа на об-
ратную матрицу ' 1
r[Ф ]− , получим
1+rx '
r[Ф ] ∗ ' 1
r[Ф ]− = rx '
r[Ф ] ∗ ' 1
r[Ф ]− '
r[Ф ]− ∗ ' 1
r[Ф ]− (16)
или
[ ] ' 1
1 [ ]r r r rx E x E −
+ ∗ = ∗ − Φ ∗ Φ . (17)
Рассмотрим пример (4), (5).
Точка пересечения этих двух линий имеет x координату, определяемую из соотношения
3 22 3 1x x x x+ = − + + (18)
или
( ) 3 2 3 1 0p x x x x= − + + = , (0) 1p = − , (1) 1p = . (19)
Применительно к рассматриваемым выражениям, с учетом (9), положив
( )p x ≡ )(xf , будем рассматривать функцию )(xp в виде РМП:
0( )f x �
0[Ф ] =
−
−
1
31
131
1131
= ]Ф[ *
0 � )(* xf . (20)
Продифференцируем функцию )( rxf , получив )(' rxf в виде РМП по правилу
[12а] с учетом, что оператор дифференцирования определен матрицей (13):
)(' rxf �
'
r[Ф ] [ ]A= [Ф ]r dx∗ =
42 ISSN 1028-9763. Математичні машини і системи, 2013, № 4
[ ]
1 3 1 1
1 3 1
1 3
1
−
−
= Α ∗
[ ]
0
1
2
3
1 2
2 2
1 3
1 0
x
x
dx
x
x
−
−
= Α ∗ =
−
�
'
r[Ф ] =
=[2-2 3 0]
T { }x . (21)
После этого уравнение (17) можно записать таким образом:
1'
0001 ][][ −∗−∗= ФФExx . (22)
Обозначим величину приращения )( rxδ , nr ,...,1,0= на каждой итерации:
)( rxδ = ' 1[Ф ] [ ]r r
−∗ Φ . (23)
Замечание
В структурах вычислительной техники из набора арифметических операций (сложение,
вычитание, умножение и деление) наиболее тяжелой (по длительности выполнения) и по
наименьшей точности (по погрешности округления) является операция деления. От нее в
спецпроцессорах стремятся (по возможности) избавляться (в крайнем случае, не делать ее
базовой).
Заменив '
r[Ф ] , находящуюся в (1, 13) в знаменателе (делитель на каждой итерации),
на обратную ' 1
r[Ф ]− к производной функции (сделав ее таким образом сомножителем) в
уравнении (22), мы на каждой итерации заменим выполнение операции деления на умно-
жение.
Далее вся процедура вычисления нового значения 1+rx сводится к выполнению ите-
рационного процесса
( )1r r rx x x+ = − δ (24)
над ССД, то есть к процедуре вычисления сумм парных произведений. К ним сводится
решение задач МФ [3] с помощью МКЭ или метода конечных разностей (МКР). Это прак-
тически отвечает общей идеологии построения параллельного спецпроцессора из ПЭ с СУ
в его основе.
Вычислим матрицу ' 1
r[Ф ]− , обратную к матрице от производной '
r[Ф ] для рассмат-
риваемого выше примера (с помощью метода факторизации без деления на прямом ходе
[10]):
' 1
r[Ф ]− = =
−
−
−
10002
010022
0010322
00010322
−
−−
2/1000
2/12/100
4/12/12/10
14/12/12/1
j
j
j
j
x
x
x
x
4
3
2
1
14/12/12/1
4/12/12/10
2/12/100
2/1000
−−
−
. (25)
ISSN 1028-9763. Математичні машини і системи, 2013, № 4 43
(Перемножение матриц дает единичную матрицу '
r[Ф ] ∗ ' 1
r[Ф ] )E− = .
Произведем вычисления на основе изложенного способа и примера (4), (5).
Зададим начальное приближение 0 0,5x = и вычислим раздельно значения
r[Ф ] и
'
r[Ф ] :
0[Ф ] =
−
−
−−
−−
1
21
121
1121
=
=
=
=
8/1
4/1
2/1
1
3
0
2
0
1
0
0
0
x
x
x
x
=(( 11∗− )+(2 2/1∗ )-(1 4/1∗ )+(1 8/1∗ ))=
= -1/8=-0,125= 0[Ф ]T
. (26)
' 1
r[Ф ]− =
−
−−
2/1000
2/12/100
4/12/12/10
14/12/12/1
∗
=
=
=
=
8/1
4/1
2/1
1
3
0
2
0
1
0
0
0
x
x
x
x
=
=((1/2∗ 1⋅ )+(1/2 2/1∗ )-(1/4 4/1∗ )-(1 8/1∗ )=-9/16=-0,5625=[ |
0Ф ]
1−
. (27)
После вычисления
0[Ф ] и ' 1
0[Ф ]− по их произведению определим приращение на
первой итерации:
)( 1xδ =[ 0Ф ] ∗ [ Ф '
0 ]
1−
= -0,125 ∗ 0,5625= -0,0703125 (28)
и коррекцию (24) начального значения 0x =0,5.
После первой итерации первое приближенное решение 1x равно:
1x = 0x ( )1x−δ = 0,5–(-0,0703125)=0,5703125, (29)
что практически близко к значениям, приведенным в [4].
Следующие итерации вычисляют по аналогии, используя на второй итерации зна-
чение
1x , полученное в (29) на первой итерации, и т.д.
В результате имеем:
2x =0,5698634;
3x =56984141;
4x =569878258;
5x =0,569842131;
6x =0,56984038;
7x =0,569840295,
что совпадает со значением, вычисленным в исходном примере [4].
Замечания
1. Вычисления, проведенные по уравнениям (21) – (29), сведены к раздельному получению
на каждой итерации значения функции [ ]rΦ и значения производной от нее [Ф '
r ].
Значения 0 1 2 3, , ,r r r rx x x x (которые использовались при вычислении в (26), 27)), вычис-
ляются с помощью СУ путем умножения соответствующих компонент 2( )r r rx x x∗ = ,
44 ISSN 1028-9763. Математичні машини і системи, 2013, № 4
( )2 3
r r rx x x∗ = , … в двоичном дополнительном, например, коде методом умножения млад-
шими разрядами обоих сомножителей вперед. Это позволит получить младшие разряды на
первом микротакте умножения с тем, чтобы использовать их на следующем микротакте в
качестве исходных данных в других СУ при получении 2
r rx x∗ или 2 2
r rx x∗ .
2. Вычисление обратной матрицы ' 1[Ф ]r
− , которая определяет полином в записи РМП про-
ще. Оно предполагает циклическую запись коэффициентов полинома, что в результате да-
ет верхнюю треугольную матрицу. На главной диагонали ее стоит число, которое равно
значению коэффициента при неизвестном полиноме в нулевой степени. За счет этого мы,
применяя для обращения матрицы метод исключения, на практике исключаем прямой ход
процедуры факторизации матрицы, на котором формируется нулевая нижняя треугольная
матрица. Выполняется только обратный ход, на котором надо выполнить единственное де-
ление (или взятие обратной величины от коэффициента на главной диагонали 1 /mm mml k= ,
m – показатель степени полинома )(xf ). Но при РМП диагональный элемент для
mmii kkk ==11 (одинаков). Далее на mml следует умножать столбцы матрицы ' 1[Ф ]r
− .Таким
образом, значения коэффициентов обратной матрицы ' 1[Ф ]− будут вычислены.
Отметим, что вычисление обратной матрицы ' 1[Ф ]r
− в нашем случае оправдано мно-
гократным использованием ее в ходе итерационного процесса. Обычно считают, что про-
ще получить решение yAx = сразу, без обращения матрицы.
3. Раздельное вычисление [ ]rΦ , '[ ]rΦ , как было показано ранее в (26) – (27), обеспечивает
понижение порядка результирующей Rm матрицы и матриц сомножителей 1m и 2m :
Rm = 1m + 2m +1,
где 1m и 2m – порядки полиномов функции и производной от нее (порядок результирую-
щего полинома на единицу больше суммы порядков перемножаемых полиномов).
Предлагается и другой вариант вычисления приращения ( )rx итерационного процесса по
методу Ньютона-Рафсона.
Второй вариант вычислительного процесса
Положим начальное значение 0x =0,5 и запишем уравнение (23) по выражению (21), когда
вычисление величины 1( )x выполняется сразу путем перемножения матриц
0[Ф ] и | 1
0[Ф ]− :
δ 1( )x � 0[Ф ]T ∗ | 1
0[Ф ]− =
=
−−
−−
−−
−−
−−
−
−
1211000
121100
12110
1211
121
12
1
∗
−
−
0
0
0
1
4/1
2/1
2/1
=
0
0
1
0
2
0
3
0
4
0
5
0
6
0
1
1/ 2 0,5
1/ 4 0,25
1/ 8 0,125
1/16 0,0625
1/ 32 0,03125
1/ 64 0,015625
x
x
x
x
x
x
x
=
= =
= =
= =
= =
= =
= =
=
=(-0,5+0,25+0,1875+0,0625–0,078125+0,0234375–0,015625)=-0,0703125. (31)
ISSN 1028-9763. Математичні машини і системи, 2013, № 4 45
1x =0,5+0,0703125=0,5703125. (32)
Следующая итерация начинается с возведения с помощью СУ значения 1x
=0,5703125 в степени n =2, 3, 4, 5, 6, на которые следует умножить вектор
)(xδ =[-1/2+1/2+3/4+1/2-5/4 3/4-1], чтобы получить новое значение 2x , то есть вычислить
)( 2xδ и в целом по (29) – значение 2x .
Расчеты, проведенные по обоим вариантам, совпадают. Меняются порядок вычис-
ления поправки и размерность матриц. Их размерность определяется величиной показате-
ля степени полинома.
Вариант вычислений, который следует применить, зависит от разработчика спец-
процессора или от программиста, который применяет уже готовое устройство.
К вопросу о вычислении функции и производной от неё применительно к методу
Ньютона-Рафсона с РМП полиномов заметим следующее.
Следуя Д. Мак-Кракену и Х. Дорну [5, с. 104], для вычисления полиномов по опти-
мальному правилу Горнера требуется n умножений и n сложений. Число умножений при
вычислении по формуле (1) составляет ( )1 / 2n n+ , если каждая степень получена последо-
вательным способом.
В нашем случае производится параллельная обработка сомножителей. Это позволя-
ет перевести вычислительный процесс с уровня обработки значений чисел на уровень об-
работки ССД, которые представлены числами.
Затем, если в СУ заложено выполнение операции умножения чисел, начиная с
младших разрядов, вперед обоих сомножителей, то после первого микротакта будут полу-
чены значения младших разрядов результата произведения. Вычисление значений
2x xx ∗= , 4 2 2x x x= ∗ , 8 4 4x x x= ∗ , 10 8 2x x x= ∗ , а также получение в параллель нечетных
значений степеней 3 2 1x x x= ∗ , 5 3 2x x x= ∗ 5
, 7 5 2x x x= ∗ , 9 5 4x x x= ∗ , полагает задержку
всего на четыре микротакта. Для чисел, представленных в форме фиксированной запятой с
разрядностью, например, n =128 и при обработке чисел с удвоенным числом разрядов, до-
полнительные задержки при умножении еще на 4 микротакта составят около ≤ 2 %, что
можно считать несущественным. При одновременном сложении сомножителей, которое
выполняется параллельно с умножением как одно сложение, такое решение дает неоспо-
римый выигрыш.
Отметим также, что если процедура выполняется на оборудовании, предназначен-
ном для решения задач в ЕТП, то она вписывается в процесс, обеспечивая дополнительные
преимущества.
Особо следует сказать, что в течение всего итерационного процесса необходимо
выполнить только одно деление при вычислении обратной величины от диагонального
элемента при обращении матрицы (производной от функции, записанной в циклическом
виде). Традиционные методы требуют выполнения тяжелой и всегда менее точной опера-
ции деления на каждой итерации.
5. Выводы
1. Предлагаемый способ решения уравнений (или вычисления корней полиномов) по ме-
тоду Ньютона-Рафсона позволит использовать спецпроцессоры параллельного типа и вы-
полнять вычислительный процесс с использованием ССД на высокопроизводительных
структурах.
2. Эти структуры разработаны для решения уравнений, которыми описывают задачи МФ с
применением аппроксимаций, используемых в методах МКЭ, МКР и др. [3] с обработкой в
ЕТП.
46 ISSN 1028-9763. Математичні машини і системи, 2013, № 4
3. Предложенная выше процедура замены операции деления полиномиальных функций на
операцию умножения на матрицу, обратную к исходной матрице, может быть успешно
применима и в других случаях.
Для этого следует их описать в виде РМП, вычислить обратную матрицу и осуще-
ствить в таком виде операцию перемножения полиномов.
4. Применение предлагаемого подхода возможно и без использования в спецтехнике. В
таком случае выигрыш в повышении скорости вычислений можно ожидать меньше. Но
поскольку погрешность округления при умножении всегда меньше, чем при делении, сле-
дует ожидать повышения точности или сокращения количества итераций.
5. Предлагаемый способ еще раз напоминает о необходимости создания параллельных ме-
тодов вычисления уравнений и решения практических задач. Следует создавать новые ме-
тоды, искать способы преобразования существующих методов, что позволит реально от
машин с последовательной организацией вычислений при обработке чисел перейти к па-
раллельным структурам, с обработкой ССД. В процессе обсуждения статьи возникли во-
просы и замечания, на которые следует ответить.
1. Область применения МНР. Она уже определена и описана в научно-технической и
учебной литературе. Автор предложил и показал, как можно МНР реализовать на парал-
лельном спецпроцессоре для решения задач МФ в режиме ЕТП с обработкой информации
на уровне ССД. Это, естественно, расширит круг задач, решаемых на спецпроцессоре. Хо-
рошим примером могут служить архитектуры, которые развиваются в последнее время
фирмами nVidea Tesla, AMD, и др. на базе графических процессоров (GPU) и кластерных
систем классической структуры (CPU) [6, 7].
2. Вопрос: «Зачем применять МНР, если есть подпрограмма (ПП) ZEROIN [8]?». Из
машинных алгоритмов, предназначенных для нахождения действительного корня функ-
ции, подпрограмма ZEROIN является одной из лучших. Алгоритм сочетает безотказность
метода бисекции с асимптотической скоростью метода секущих (в случае гладких функ-
ций). ПП алгоритма ZEROIN хорошая, но она не может быть прямо поставлена на СП, ко-
торый реализует ЕТП с ПЭ с СУ в своей основе. Кроме того, иногда следует находить кор-
ни в комплексной области и не всегда функции бывают гладкие.
Тем не менее уравнения, заложенные в метод секущих ПП ZEROIN:
1+kx = kx ( )kx−δ , (33)
)( kxδ =
)(
)(
1
1
kk
kkk
ff
xxf
−
−∗
−
− , (34)
где kf = )( kxf – значение функции )( kxf в точке kx , по своей структуре записи мало от-
личается от выражения (24), рассмотренного ранее для МНР, где в качестве поправки
)( kxδ вычисляется отношение значения функции к производной от неё с помощью выра-
жения (23) в записи РМП:
)( kxδ =[Ф k ] ∗ [Ф k ] 1− , f ( x k )�[Ф k ]. (35)
Поскольку kx и 1−kx – это числовые значения абсцисс, а kf и 1−kf – значения функ-
ций )( kxf и )( 1−kxf в этих точках и представлены многочленом (полиномом), то возмож-
ность применения РМП не вызывает сомнений. Вычислению подлежит значение )( kxf
функции в точке kx , поскольку предыдущее значение в точке 1−kx ранее вычислено.
Для исключения на каждой итерации операции деления следует (по аналогии с (25))
один раз вычислить обратную (с единственным делением) матрицу от функции
ISSN 1028-9763. Математичні машини і системи, 2013, № 4 47
)(xf �[Ф 0] 1− . Она представлена верхней треугольной матрицей, на главной диагонали
которой стоит число, равное свободному члену многочлена (полинома).
Учитывая, что в конкретном случае пользователь исследует один многочлен, и
свойство ассоциативности многочленов, по которому их сложение (вычитание) сводится к
сложению (вычитанию) коэффициентов при неизвестных с одинаковой степенью, опера-
ция вычитания [ ] [ ]1k kФ Ф −− упрощается.
Замечание
Следует помнить, что методы МНР и секущих можно использовать в комплексной плоско-
сти [9]. На практике используют комбинированный метод хорд и касательных (МНР) в
разных сочетаниях значений произведения функции и второй производной относительно
нуля
)(xf ∗ 11( ) 0f x < , (36)
)(xf ∗ 11( ) 0f x > , (37)
когда для случая (36) метод хорд даёт приближение корня с недостатком, а метод каса-
тельных – с избытком. Или наоборот – для случая (37).
Выражения, которые применяют при вычислениях, по своей структуре аналогичные
с ранее приведенными (для МНР и ZEROIN). Так, для условия (36) они имеют вид [9]:
1na + = na ( )na−δ , (38а)
)( naδ = )( naf ∗ )( nn ab − /[ )( nbf ( )nf a− ], (38б)
1+nb =
nb − δ n(b ) , (38в)
(δ nb ) = )( nbf /[ )(1
nbf ]. (38г)
В этом случае приближения корня лежат со стороны b и получают по методу каса-
тельных, а со стороны a – значения, полученные по методу хорд.
Для условия (37) выражения аналогичные:
1+na = na - )( naδ , (39а)
)( naδ = )( naf /[ )(1
naf ],
1+nb =
nb − δ n(b ) , (39б)
δ n(b )= )( nbf ∗ )( nn ab − /[ )( nbf - )( naf ],
но приближения значения корня со стороны a получены по методу касательных, а со
стороны b – значения, полученные по методу хорд.
При этом для исключения операции деления необходимо от матрицы (с помощью
которой в знаменателе выражения (39б) записан полином) вычислить обратную (от 1
0[ ] −Φ
или 1 1
0[ ] −Φ ), а затем по выражению вида (35) вычислить поправку.
Вычисления прекращают, когда по методу бисекции достигается требуемая точ-
ность:
ξ =½ (
нx − изx ), (40)
где нx , изx – приближенные значения корня с недостатком и избытком соответственно.
48 ISSN 1028-9763. Математичні машини і системи, 2013, № 4
Поскольку вычисление значений (знаков) функции производной (первой от неё и
второй) с помощью РМП сводится к выполнению обычной операции умножения матрицы
(для дифференцирования [ A ]) (13) на вектор-столбец функции (или её первой производ-
ной), можно легко определить исходную точку. В качестве её следует выбирать тот конец
отрезка ],[ ba , где знаки функции и второй производной совпадают. А по времени такое
произведение в базисе РМП выполняется как обычная операция умножения, в то время как
для вычислительных машин классической структуры это сложная процедура.
Пример.
Значение функции (для
0 0,5x = , например) равно
=)(xf 1323 ++− xxx �[13-11]∗ [ 3210 xxxx ] T =
=[1 1 3 0,5 1 0,25 1 0,0625]∗ + ∗ − ∗ + ∗ =2,3125>0. (41)
В соответствии с (14) первая производная от исходной функции (8) равна произве-
дению матрицы [ A ] (13) на вектор )](*[ xf (20) от функции )(xf .
Для 0 0,5x = значение первой производной )(1 xf �
1
0[ ]Φ равно
)(1 xf �
1
0[ ]Φ = [ A ] ∗ [Ф 0] dx =[ A ] ∗ [1 3 -1 1] T dx =
−
0
3
2
3
3
2
1
0
x
x
x
x
=
=[13∗ 2 0,5− ∗ 3 0,25∗ ]= 2,75 0> , (42)
и значение второй производной от функции )(xf (8) равно
)(11 xf �[ Ф 11
0 ]=[ A ] ∗ [Ф1
0] dx =[ A ] ∗ [3-2 3 0]T dx =
−
0
6
2 0
1
2
1
0,5
0,25
x
x
x
=
=
=
=
=( 12∗− +6 0,5∗ )=1>0. (43)
Произведение значений функции )(xf и второй )(11 xf производной от неё (8) равно
)(xf ∗ )(11 xf =2,3125∗ 1=2,3125>0. (44)
Выполняется условие (37), которое и определяет исходную точку.
Рассмотренный выше материал по нахождению нулевых значений полиномов даёт
основание предполагать, что в такой постановке способ распараллеливания и обработки
исходных данных в виде ССД может быть применен при решении общих задач и на суще-
ствующих гетерогенных кластерных структурах типа GPU – CPU, выполняющих вектор-
ные операции. Требуется лишь доработка ПП.
СПИСОК ЛИТЕРАТУРЫ
1. Ледянкин Ю.Я. Вопросы создания спецпроцессоров, проблемно-ориентированных на решение
задач математической физики / Ледянкин Ю.Я. – Киев: ИК АН УССР, 1980. – 54 с. – (Препринт /
АН УССР, Ин-т кибернетики; 80-15).
2. Ледянкин Ю.Я. Принципы построения и структуры спецпроцессоров, ориентированных на ре-
шение задач математической физики / Ледянкин Ю.Я. – Киев: ИК АН УССР, 1981. – 45 с. – (Пре-
принт / АН УССР, Ин-т кибернетики; 81-41).
ISSN 1028-9763. Математичні машини і системи, 2013, № 4 49
3. Единый технологический поток в организации вычислений – способ повышения производитель-
ности параллельных структур на процессорных элементах транспьютерного типа / Ледянкин Ю.Я.
– Киев, 1989. – 20 с. – (Препринт / АН УССР, Ин-т кибернетики им. В.М. Глушкова; 89-57).
4. Фокс А. Вычислительная геометрия. Применение в проектировании и на производстве / А. Фокс,
М. Пратт; пер. с англ. – Л.: Мир, 1982. – 304 с.
5. Мак-Кракен Д. Численные методы и программирование на Фортране / Д. Мак-Кракен, У. Дорн;
пер. с англ. – М.: Мир, 1977. – 585 с.
6. Адинец А. Графический вызов суперкомпьютерам / А. Адинец, В. Воеводин // Открытые систе-
мы. – 2008. – № 4. – С. 35 – 41.
7. Губайдуллин Д.А. Об особенностях использования архитектуры гетерогенного кластера для ре-
шения задач механики сплошных сред / Д.А. Губайдуллин, А.И. Никифоров, Р.В. Садовников //
Вычислительные методы и программирование. – 2011. – № 12. – Р. 450 – 460.
8. Форсайт Дж. Машинные методы математических вичислений / Форсайт Дж., Малькольм М.,
Моулер К.; пер. с англ. – М.: Мир, 1980. – 280 с.
9. Численные методы / Н.И. Данилина, Н.С. Дубровская, О.П. Кваша [и др.]. – М.: Высшая школа,
1976. – 368 с.
10. Ледянкин Ю.Я. Способы параллельного решения систем bAx = в едином технологическом
потоке решения задач математической физики / Ю.Я. Ледянкин // Математичні машини і системи.
– 2013. – № 1. – С. 63 – 74.
Стаття надійшла до редакції 13.05.2013
|