close

Вход

Забыли?

вход по аккаунту

?

Способы увеличения производительности алгоритмов для отказоустойчивых систем хранения данных.

код для вставкиСкачать
??? 004.056.3?+?004.056.4
?. ?. ????????1, ?. ?. ????????2, ?. ?. ??????3
1
?Институт автоматизации проектирования РАН
ул. 2-я Брестская, 19/18, Москва, 123056, Россия
E-mail: __vm@mail.ru
?Московский физико-технический инстиут (государственный университет)
пер. Институтский, 9, Долгопрудный, Московская обл., 141700, Россия
E-mail: 2?kason@yandex.ru, 3?kobets@sw.ru
2, 3
??????? ?????????? ?????????????????? ??????????
??? ???????????????? ?????? ???????? ??????
??????????? ?????????????? ??????? ???????????? ??? ???????????? ?????? ??????, ??????? ??????? ??? ????? ??? ????????, ??? ? ??????? ?????????? ??????????? ???
???????? ?? ????. ??? ??????????? ??????????? ?????? ??????????? ????????? ???????,
?????????? ? ?????? ??????? ?? ???????? ? ????????????? (??? ???????, ????? n????????? ??????????? ??? ? ?????????????? ??????? ???????????? ???? ???????? ????????????
[Patterson, 1988]).
????? ??? ????????? ?????? [???????? ? ??., 2001; ???????, ????????, 2006], ?????????? ?? ^n, k h?????????? ?????, ??????????? ????? ????? ????????? ????????????? ????????
??????. ??????, ?????? ????????????????? ? n ?????? («????????»), ?? ????? k ???????
????? ???????????? ???????? ?????? («??????»). ??? ???? ??????????? ???????? ??????????? ????? ??????????? ? ???????????? ??? ???????? ???????. ???????? ???????????? ??
????????????? ??????? ??????? ???????????, ????? k ?? n ????? ??????? ???????? ???????
????????????. ??????? ??????????? ???????? n # k ???????? ?? n ????????? ??????????? ????????? pi , ??????????????? ?????????? ? ???????: aij = pij - 1, i ! 71; nA, j ! 71; k A.
???????? ???? ??????????? ?? ?????????????????? ????? xi , ?????????? ? ???????, ? ?????????? ????? ?? ??????? ???????????:
J y
yn + 1 y2n + 1 fN JK1 p1 f p1k - 1NOJ
K 1
O
x1 xk + 1 x2k + 1 fN
k-1
K
O
y
y
y
f
1
p
f
p
K
O
K 2
O
n+2
2n + 2
2
2
K x2 xk + 2 x2k + 2 fO.
K
O
K h
O
h
h
f = h
h j h K
O h
h
h
fO
K
O K
y
y
y
f
1
p
pnk -- 11OK
O
n-1 f
K n - 1 2n - 1 3n - 1
O K
x2k
x3k f
k - 1O xk
K y
O
K
P
y2n
y3n f
1 pn f pn L
L n
P L
P
?????? ?????????? ?????? (????????) ?????? ? ??????????????? ?? ??????????? ????????? ??????????? ? ????????? ?????.
??? ?????????? ????????? ?????????????? ?????­???? ????? k ???????? ?????? ?? ?????????? pi , ???????????­?????? ??? ?? ??????????. ?? ???????????? pi ?? ???­???? ???~
??????? ???????? ??????? M ???????????? ??????? M . ??? ??? ??????????? ???????
???? ???????? ?????­??? ???????????, ?? ??? ?? ?????? ??????? ??????­????. ??????? ?????
~ -1
????????? ???????? ? ??? ??????? M . ????? ???????? ??????? x j ?????????? ?? ???~ -1
???? x j = M y j :
Jx x
x
K 1 k + 1 2k + 1
x
x
x
K 2 k + 2 2k + 2
Kh
h
h
K
x x2k
x3k
L k
fN J1 pa
O K
fO K1 pa
=
fO K h h
O KK
f
1 pak
P L
1
2
-1
f pak - 1NO JK ya
f pak - 1O K ya
j h O Kh
O K
f pakk- 1O K ya
P L
1
1
2
2
k
yn + a
yn + a
h
yn + a
1
2
k
y2n + a
y2n + a
h
y2n + a
1
2
k
fN
O
fO
.
fO
O
fO
P
ISSN 1818-7900. Вестник НГУ. Серия: Информационные технологии. 2007. Том 5, выпуск 1
© В. М. Пименов, Е. В. Соколов, А. Л. Кобец, 2007
Увеличение производительности алгоритмов для систем хранения данных
33
???????? ???????? ? ?????????????? ??????? ????????? ??????? ??????????????? nk,
? ?????? ? k 2 , ?, ???? ???????? ????????, ????? ???????? ???????? ??????, ??????? ?????? ?? n/k . ??????? ???????? ?????????? ?????? ? ?????? ??????????? ?? ???????????????
(?? ??????????? ????? ??????????? ???????).
?????? ^n, k h-????? ?????????????? ?????????? ??????? ???????????, ?? ?????? ?? ?????
?????????????? ???????? ????????????? ??????? ? ???? ????, ??? ?? ????????? ????????????, ? ? ?????????????? ??????? ??????????? ???????? ?????. ??????? ? ???????? ?????
?????? ???????????? ???????? ????? ?????, ?????????? ? ??????? ?????????? ?????????.
? ?????? ??????????????? ???? GF ^28h , ???????????? ? ???? ??????????? 7 ??????? ? ?????????????? ?? ???? GF ]2g. ???????? ????? ???? ????? ?????????? ???????, ??? ??????
?????? ?????? ??????????? ??? ??????????????? ???????. ? ????? ?????? ???????? ??????????? ????????? «??????????? ???», ? ????????? ? ?? ???????? ???????????? ??????????? ?? ?????? ??????-???? ????????????? ?????????? 8 ???????.
? ???????????? ??????????? ?????? ?????????? ??????????? ???????, ???????????
????????? ? ????? ?????. ??????????? ?????????? «? ???» ?? ???????? ????????????
??????????? ??????????? ????????. ???????????? ???????? ??????????? ????? ??????????? ??? GF ^28h ???????? ????????????? ?????? ????????? ? ???????, ?????????? ??????? ??????????? ???????? ??????????????? ?????????. ?????? ???????? ?????? ????????
?????????? ????? ????????? ?????? ??????? (???. 1).
? ????????? ?????? ??????????? ????????? ??????? ?????????? ???????? ?????????????? ?? ^n, k h-????? ?? ??????????? ?????? ?????????? ? ????????????? intel?/?amd x86?/?x64 ???
?? ???? ????????????? ?????????????? ??????? ???????????, ??? ? ?? ???? ????????? ???????
??????????, ? ????? ????????? ????????? ?????????? ? ????? ?????.
?????????????? ??????
??? ?????????? ??????????? ?????????????? (????? ??????? ?????????????? M ???
?????????????) ????? ???????????? ????????? ??????? ?????????, ?????????? ???????????? ?? ????? ??????? ?????, ??????????????? ??????????????? ? M ?????????,
? ???? ?????? ???? ?? ??????. ??? ????????? ??????????? ??????? ? ??????? ???????? ????????? ????? ???? ? ?????? (? ??????? ?? ?????? ???????, ??? ???????????? ? ?????????????? ?????? ??????????). ??? ???????? ? ????? ???????????? ????????????? ?????
??????????, ? ????? ????????? ????? ???????????? ????? ??????? ?????????. ????? ????,
??? ??? ????? ???????? ??????? M ??? ????????, ????? ??????????? «??????????????»
??????????? ????? (loop unrolling)?, ??????????? ?? ?????? ?? ?? ?????, ????????? ???????. ??? ????????? i-? ???????? ???????????? ?????? ???? ?????? ??????? ??????????????
_1 pi f pik - 1i " ^0 1 f k - 1h . ?? ??????? ????????? ? ?????????? ?????? ??????????
???? ??????????????? ? ?????????????? ??????:
J m1
m12 f m1256 NO
K 1
f f f O
K f
K m1p
O.
m 2p f m 256
p
K
O
f f f O
K f
K m1
O
m 2p
f m 256
p
p
L
P
???????? ????? ?????????? ????????? ????? ???????: _1 pi f pik - 1i " ^0 1 f k - 1h ,
? ?????? ????? ?? k ????? ???? ???? ????? ???????????? k ???, ? ?????????????? ????? ????????.
?????????? ?????????? ??????? «?????????????? ??????» ????????? ?? ???. 1 ? ????????? ? ???????? ??????????? ^n, k h-?????.
i
i
k-1
i
k-1
i
i
k-1
i
????? ????????? ? ??????? ???????? ????? ????? ? [???????, ????????, 2006].
????????????? «??????? ?????????» ???? 22-??????? ??????? ???????? ???????? ?? x86 ???????????.
Intel architecture software developer?s manual. Vol. 3: system programming guide, 1999. http://www.intel.com/
design/pentiumii/manuals/243192.htm.
34
В. М. Пименов, Е. В. Соколов, А. Л. Кобец
????????? ??????? ??????????????
«???????????????» ???????? ????????? ???????? ??????????????? ????????? ???????
???????????, ??????? ??????????? ? ???????? ????????????? ???????????????? ???????
~
M ? ??????? M ???? E , ??? E ? ????????? ???????:
K
J 1
0
f
0 N
K
O
1
f
0 O
K 0
K h
h
j
h O
~
K
O
M =K 0
0
f
1 O.
K ak + 1, 1 ak + 1, 2 f ak + 1, k O
K
O
h
j
h O
KK h
a
an, 2 f an, k O
L n, 1
P
~
?????????? ??????? M ???????? ???? ?? ??????????, ???????????? ??? ??????????
^n, k h-?????, ??? ? ???????? M (????? n ?? k ????? ???????? ??????? ???????????? ? ????? ?????????? ????? ? k-?????? ????????????).
? ???????? ????????? ??? ?????????? Y = M X ??????????? kn ???????? ?????????.
????? ?????????????? ??????? M ????? ??????????? ?????????? Y - = E X Y- = E X
? Y . = K X . ??? ??? ??????????????? ? ??????? ????????? ??????? ?????? ?????????
Opteron x86
Opteron x64
(10,5)
(15,10)
(10,5)-unroll
(15,10)-unroll
0
10
20
30
40
50
???. 1. ???????? ?????? ???????? ?????? ? ???????? ? ?????????? ???????????, ??/?
Opteron x86
Opteron x64
(10,5)
(15,10)
0
10
20
30
40
50
???. 2. ???????? ?????? ???????? ?????? ??? ????????????? «??????????» ??????? ??????????????, ??/?
Увеличение производительности алгоритмов для систем хранения данных
35
? ?????????, ???????? ????????? ?????? ?????? ????? ??????? Y ., ? ??????? ??????????
????????? ???????? ????????? ??????????? ?? k ^ n - k h .
????????? ?? ????????? ??????? ?????????? ???????????? ????? ???????????, ?? ? ????
?????????? ??????? ?????????? ???????? ?????? ? ????????, ?????????????? ?????????????????. ??? ???? ????? ???????? ??????????? ???? ??????????, ??????? ??????????
???????? ?????? ?????????? (???. 2):
J y
y2
y3
fN JK1 p1 f p1k - 1NOJ
1
K
O
x
x2
x3 fN
O
ym + 2
ym + 3
fO K1 p2 f p2k - 1OK 1
K ym + 1
x
x
x
f
K
O
m
1
m
2
m
3
+
+
+
K
h
h
h
fO = K h
h j h OK
O.
O
h
h
h
f
K
O K
k-1
O
K ym ^n - 1h + 1 ym ^n - 1h + 2 ym ^n - 1h + 3 fO K1 pn - 1 f pn - 1OKK x
xmk + 2 xmk + 3 fO
mk + 1
k - 1O
K
K y
O
L
P
ymn + 2
ymn + 3 f
1 pn f pn
P
L mn + 1
P L
???????? ?????? ? ?????????????? «??????????» ??????? ??????? ?? ?????????? ????????. ??? ?????????? ??-?? ????, ??? ????? ?????, ?????????? ?? ????????? ???????,
~
~ -1
? M ? M ?????????, ??????? ?????? ???? ?????? ??????????, ???? ????????????? ? ?????????????? ???????? ? ????? ????? (???. 3).
??????? ?????????????? ? ????????? ?????????
???????? ????????????? ????? ??????? ???????????, ???? ????? ?????? ??????? ????????? ?? ???????????? ???????????. ??????? ?? ????? ?????????, ???????????? ??? ???????????? ?????? ????? ?? ???????
bij = aij a1j, k + 1 # n, 1 # j # k .
????? ??????? ??????? ????????? ???
J1
0
f
0 N
K
O
1
f
0 O
K0
Kh
h
j
h O
K
O
0
f
1 O,
K0
K 1 bk + 1, 2 f bk + 1, k O
K
O
h
j
h O
KK h
1 bn, 2 f bn, k O
L
P
? ?????????? ????????? ??????????? ?? n - k (???. 4).
?????????? ? ????? GF ^2 4h
??? ??????????? ?????????????????? ? ????????? ???????? ???????? ?????? ???????
???????????? RAID-???????, ????????? ?? ?????????? ??????. ? ???????? ???????? ???????? ????????????? ^n, k h-????? ?? ?????? GF ^2 4h ?, ??? ???? ??????? n ? k (?????????Opteron x86
Opteron x64
1?5 ????????
5?10 ????????
0
50
100
150
200
250
300
350
???. 3. ???????? ?????? ?????? ?????? ??? ?????????????
«??????????» ??????? ?????????????? ??? ^n, k h = ^10, 5h , ??/?
400
450
???? ???????? ????????? ???????? ?? ????? ???? ???????? ??? ??????.
????? ????????? ???????? ?????????? ???????? ? ???? ????? ????? ????? ? ??????? [Mastrovito, 1991;
Paar, 1994]. ??. ?????: Advanced encryption standard (AES) / National Institute of Standards and Technology (NIST),
2001. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf.
36
В. М. Пименов, Е. В. Соколов, А. Л. Кобец
??? 15) ?????? ?????????? ??? ??????. ? ???? ?????? ???????? ????????? ??????????
?????????? ???????? ????? ?????????????????? «???????» ?????????????? ????????
(????????? ? ? SIMD-????????), ? ????????????? ????????????? ??????? ????????? ????????. ??? ?????????? ?????????????? ????????? ???????.
???????? ???? GF ^2 4h ????? ??????????? ? ???? ??????????? 3-? ???????:
a ^ xh = a3x3 + a2x 2 + ax
1 + a0,
????????? ?? ?????????:
b ^ xh = b3x3 + b2x 2 + bx
1 + b0.
c ^ xh = a ^ xh b ^ xh mod p ^ xh ,
??? p ^ xh ? ????? ???????????? ????????? 4-? ???????, ????????, x 4 + x + 1. ? ????? ??????
c ^ xh = c3x3 + c2x 2 + cx
1 + c0,
c0 = _ a0 7 b0i 5 _ a3 7 b1i 5 ^a2 7 b2h 5 _ a1 7 b3i,
1 4444444
42
4444444
43
~
c0
~
c1 = _ a1 7 b0i 5 _ a0 7 b1i 5 _ a3 7 b2i 5 _ a2 7 b3i 5 c0,
1 4444
42
4444 3
~
c1
~
c2 = _ a2 7 b0i 5 ^a1 7 b1h 5 _ a0 7 b2i 5 _ a3 7 b3i 5 c1,
\
~
c2
~
c3 = _ a3 7 b0i 5 ^a2 7 b1h 5 ^a1 7 b2h 5 _ a0 7 b3i 5 c2,
Opteron x86
Opteron x64
(10,5)
(15,10)
0
10
20
30
40
50
60
???. 4. ???????? ?????? ???????? ?????? ??? ????????????? ??????? ?????????????? ? ????????? ????????, ??/?
Opteron x86
Opteron x64
(10,5) ??? SIMD
(15,10) ??? SIMD
(10,5) c SIMD
(15,10) c SIMD
0
20
40
60
80
???. 5. ???????? ?????? ???????? ?????? ??? ????????????? GF ]2 g
????????? ? «??????????» ???????? ?? ??????? ? SSE-?????????, ??/?
4
100
120
Увеличение производительности алгоритмов для систем хранения данных
37
??? ????????????? ?????????? ?????????. ??? ?????????? b ^ xh ????? ??????????? ????????? ? ????????? ?????:
Jc N Ja a a a N
J
N
0
K 0O K 0 3 2 1O J N K
O
K c1O K a1 a0 a3 a2O K b0O K_ a3 7 b1i 5 ^a2 7 b2h 5 _ a1 7 b3iO
K c2O K a2 a1 a0 a3O K b1O K
O
_ a3 7 b2i 5 _ a2 7 b3i
K O= K
O7 K O5 K
O.
_ a3 7 b3i
K c~3O K a~3 a~2 a~1 a~0O K b2O K
O
K c O K a a a a O b3
K
O
0
KK 0OO KK 0 3 2 1OO L P K
O
h
L
P
Lh P Lh h h h P
????? ????? ?????? ??????? ??????? aij ?????????? ? ????????? ??????? ? ???????
?????????? ?? ???? ?????? b j . ????? ???????????? ???????????? ??? ?????????? ???????
??????? (? ?????????????? ???????????? ?????? ? ???????????? «?????????? ?»), ???????????? ? ??? ? ??????????? ? ??????????? ??????????. ????? ?????????? ???? ???????? ???
???? ???????? ??????? aij ?????????? ??????? c j ? ???????????.
???????? ?????????? ? ?????????????? ??????? ???? (64 ???????) ? SSE-????????? ? ?????? (128 ????????). ?????????? ?????? ????????? ????????? ?? ???. 5.
???????????? ??????????
?????????????? ?? ^n, k h-????? ???????. ??????? ????? ????????? ??? ?????? ?? ?????
? ????????? ?? ??????????? ?? ?????????? ???????????. ?? ???. 6 ????????? ?????????????????? ????????? ? ??????????? ?? ?????????? ???????????? ??????????? ??????? ??
???????????????? ??????.
??????
????? ?????? ?????????????????? ???????? (??/?) ?????? ?????????? ??????????? ??
???. 7. ??????? ??????? ?????????? ????????? ?????????? ? ???????? ?????????????? ???????? ????????. ????????????? ?????????? ???? ??????????? «?????????????? ??????» ?
«????????? ???????». ????? ?? ?????? «?????????? ???????» ??????????? «??????? ? ????????? ????????». ?? ?????? ?????????? ??????? ??? ?????????? GF ^2 4h . «?????????????????» ??????????? ?? ?????? «GF ^2 4h ??? SIMD».
Opteron x86
Opteron x64
1
2
4
8
0
20
40
60
80
100
120
140
???. 6. ???????? ?????? ???????? ?????? ??? ???????????? ?????????? ??????????
? GF ]2 4g ????????? ? «??????????» ???????? ?? ???????????????? ?????? ??? ^ n, k h = ^10, 5h
? ??????????? ?? ?????????? ???????????? ?????????? ???????, ??/?
38
В. М. Пименов, Е. В. Соколов, А. Л. Кобец
Opteron x86
Opteron x64
??????????????
????????
?
??????????????
??????
??????????
???????
??????????
???????
? ?????????
????????
GF(2 )
??? SIMD
4
GF(2 )
c SIMD
4
?????????????????
(?? 4 ??????
?? ????????????????
??????)
0
20
40
60
??/???
80
100
120
Opteron x86
Opteron x64
??????????????
????????
??????????????
??????
?
??????????
???????
??????????
???????
? ?????????
????????
GF(2 )
??? SIMD
4
GF(2 )
c SIMD
4
?????????????????
(?? 4 ??????
?? ????????????????
??????)
0
20
40
60
80
??/???
100
120
???. 7. ????? ?????? ?????????????????? ??????????: ? ? ??? ^ n, k h = ^10, 5h ; ? ? ??? ^ n, k h = ^15, 10h .
1 40
Увеличение производительности алгоритмов для систем хранения данных
39
? ??? ????????????????? ?????????? ????????? ?? 3-? ?? 5-?? ??? ? ??????????? ?? ??????
n ? k;
? ????????????????? ???? ?????????????? ????????? ? 1,6 ??? ?? ????????????????
??????;
? ?? ???? ???????? ??????? ???????? ??? ?????? ????? ?????????? ??????? ????????;
???????? ????????????? ???????? ?????? k ????????;
? ??????????? ???????? ????????? ?????????? ???????????? ^n, k h-????? ? ??????????
????? ??? ??????????????? ???????? ??????.
?????? ??????????
??????? ?. ?., ???????? ?. ?. ????????????? ??????????????? ??????????? ??????????? ? ??????? ???????? ?????? // ???????? ?????????????? ??????????, ???????????????
????????????? ? ???????????. ?.: ?? ?????, 2006. ?. 138?157.
???????? ?. ?., ????? ?. ?., ??????? ?. ?. ?????? ???????????­???? ???????? ??????
? ???????????? ?????????­???? // ??????????? ?????? «??????????? ? ??????». ?. 4. 2001.
?. 355?364. http://zhurnal.ape.relarn.ru/articles/2001/035.pdf.
Mastrovito E. D. VLSI Architectures for Computation in Galois Fields. PhD thesis. Linkцping
Univ., Sweden, 1991.
Patterson D., Gibson G., Katz R. A Case for Redundant Arrays of Inexpensive Disks (RAID) //
Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data. Chicago:
1988. P. 109?116.
Paar C. Efficient VLSI Architectures for Bit-Parallel Computation in Galois Fields. PhD thesis
(English translation). Inst. for Experimental Math., Univ. of Essen. Essen, 1994.
???????? ???????? ? ??????????? 20.04.2007
Документ
Категория
Без категории
Просмотров
3
Размер файла
860 Кб
Теги
отказоустойчивых, данных, способы, хранение, алгоритм, увеличение, производительность, система
1/--страниц
Пожаловаться на содержимое документа