ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
46
Для общего объема коммуникаций Com выполняются следующие
неравенства (под объемом коммуникаций подразумевается общее ко-
личество передаваемых между узлами разрядов):
1
1
(
)
Com ( ).
p
p
N
N
i
i
i
i
s k
s
=
=
− ≤ ≤
∑
∑
(27)
В худшем случае
,
i
s mk
=
i
∀
и оценки принимают вид
( 1)
Com .
p
p
N m k
N mk
− ≤ ≤
(28)
Приведенные в статье расчеты позволяют найти для каждого уз-
ла такое
значение
s
i
,
что вероятность того, что в матрице заданного
размера найдется
k
подходящих для этого узла строк близка к 1.
Значение
s
отличается для разных узлов, так как предполагается,
что первый узел выбирает из всех строк матрицы, второй из всех,
кроме выбранных первым, и т. д. На рисунках отображено измене-
ние отношения
s
i
к
mk
с номером узла для разного общего количе-
ства узлов. Фактически, это соотношение указывает какую часть
общего объема коммуникаций можно сэкономить за счет «опти-
мального» распределения строк по узлам по сравнению с наихудшим
вариантом.
Расчеты показывают, что потенциальная экономия составляет от
0,4
до 0,15 от объема в наихудшем случае, и уменьшается с ростом
количества узлов. Однако отметим, что из тех же расчетов следует,
что разница в значениях
s
i
для узла, для которого моделируется ситу-
ация выбора из всех строк матрицы, и для узла, у которого выбора,
фактически, нет, – невелика и также уменьшается с ростом количе-
ства узлов.
СПИСОК ЛИТЕРАТУРЫ
1.
R o b H. Bisseling. Multiplication by using sparse matrix partitioning. Society,
2009. 31(4). –
Р. 3128–3154.
2.
J o p p e W. B o s , P i e r r i c k G a u d r y , A l e x a n d e r K r u p p a , P e t e r L.
M o n t g o m e r y , D a g A r n e O s v i k , H e r m a n R i e l e , A n d r e y
T i m o f e e v , and P a u l Z i m m e r m a n n . Factorization of a 768-bit RSA
modulus. 2010. – Р. 1–22.
3.
C a v a l l a r S. Strategies in filtering in the number field sieve. Proceedings of the
4
th
International Symposium on Algorithmic Number Theory, 2000. – Р. 209–232.
4.
P i n a r A., M i c h a e l T. Heath. Improving performance of sparse matrix-vector
multiplication // Proceedings of the 1999 ACM/IEEE conference on Supercompu-
ting – Supercomputing ’99, 1999. – Р. 30.
Статья поступила в редакцию 14.05.2012