병렬 사칙연산 알고리즘
2005-20356 김지훈 2007 년 12 월 19 일
1 서론
빠른 계산을 위해서는 빠른 알고리즘과 하드웨어가 필요하다. 특히 최근 컴퓨 터업체들은 개별 CPU 의 성능을 높이는데에는 현실적인 어려움이 많아져서 그 대안으로 여러개의 CPU 를 좀더 작은 공간에 집적시키는 방식으로 성능 향상 을 도모하고 있다. 또한 최근에는 일반적인 컴퓨터가 아닌 다기능을 가진 CPU 와 기능은 적지만 계산이 빠른 전용칩을 조합해서 사용하는 경우도 많이 있다.
따라서 이제는 알고리즘은 빠른 Time Complexity 도 필요할뿐더러 병렬화 가 쉬워야 한다.
이 보고서에서는 덧셈, 곱셈, 나눗셈에 대한 병렬화가 쉬운 빠른 알고리즘 들을 개괄하고자 한다.
2 정수와 실수
현대에는 32 비트 컴퓨터가 많이 쓰기 때문에 보통 사용하는 정수의 크기도 32 비트 혹은 64 비트 이다. 이보다 큰 정수를 나타내기 위해서는 정수의 배열을 사용하는것이 보통이다.
한편 실수의 경우에는 64 비트 실수 (double precision floating porint) 보다 더 큰 유효숫자를가진 실수를 표현하기 위해서는 64 비트 실수의 배열보다는 유효숫자와 지수를 정수 (의 배열) 로 나타내는것이 더 효율적이고 프로그램을 짜는데에도 더 쉽다.
64 비트 실수의 경우 유효숫자를 나타내는데 52 비트, 지수를 나타내는데 11 비트, 부호를 나타내는데 1 비트를 사용하는데 지수는 2211 = 22048만 되도 충 분히 크기 때문에 실수의 배열을 사용할경우 지수를 나타내는데에 필요이상의 공간을 할애하게 되기 때문이다. a = aint∗ Babase( aint= (ak−1, · · · , a0)B) 일 때 (aint, abase) 형태로 컴퓨터에 저장하면 된다.
이경우 실수의 사칙연산은 자리수를 맞추는 과정이 추가되는것 빼고는 정 수의 연산과 같아진다.
3 병렬 덧셈 알고리즘
편의상 B = 2k, L = max(len(a), len(b)), a = (aL−1, · · · , a0)B, b = (bL−1, · · · , b0)B 이라고 하겠다.
a + b 를 구하는 알고리즘을 병렬화 하는데 가장 중요한것이 carry 를 처리 하는 문제이다. [1] 에서는 ai+ bi, ai+ bi+ 1 둘다 미리 계산해 놓은 후 carry 에 따라 적절한 값을 선택하는 방식으로 이 문제를 해결하였다.
예를 들어 carry1 = ⌊(ai−1+ bi−1)/B⌋, carry2 = ⌊(ai−1+ bi−1+ 1)/B⌋
라 하자. (carry1, carry2) = (1, 1) 일경우 ci는 ci−1, · · · c0의 carry 와 관계없이 ai+ bi+ 1 이다. caryy 가 (0, 0) 일경우도 마찬가지고 문제가 되는 경우는 (0, 1) 인 경우다. 이경우 ci−2, ci−3등의 carry 도 봐야 할 수 있기 때문이다. 하지만 이러한 carry 가 나올 확률은 P [ai+ bi= B − 1] = 1/B 이므로 매우 낮다.
1: for i = 0 to L-1 do ◃ Run parallelly
2: c(1)i = ˜ai+ ˜bi
3: c(2)i = ˜ai+ ˜bi+ 1
4: c˜(1)i = ⌊(ai−1+ bi−1)/B⌋, ◃ ˜c(j)i is carry of c(j)i
5: c˜(2)i = ⌊(ai−1+ bi−1+ 1)/B⌋
6: end for
7: Distribute vector c, ˜c to each CPU
8: for i = 0 to L-1 do ◃ Run parallelly
9: ctmp ← i
10: if (˜c(1)i , ˜c(2)i ) = (0, 0) then
11: ci= c(1)i
12: else if (˜c(1)i , ˜c(2)i ) = (1, 1) then
13: ci= c(2)i
14: else ◃ Occure very rare times( ∼ 1/B)
15: ctmp ← ctmp − 1
16: (˜c(1)i , ˜c(2)i ) ← (˜c(1)ctmp, ˜c(2)ctmp)
17: Goto 10
18: end if
19: end for
4 병렬 곱셈 알고리즘
4.1 FFT with complex number
이번절과 다음절에서는B = 2k, L = 2 ∗ max(len(a), len(b)) ≡ 2l (1) a = (aL−1, · · · , a0)B (2) b = (bL−1, · · · , b0)B (3)
이라고 하겠다. L 이 2l꼴이 아닐경우 2l−1< L ≤ 2l인 l 을 구하고 aL−1, · · · , alen(a) 등을 0 으로 두면 된다.
Fast Fourier transform(FFT) 을 이용하면 효율적인 곱셈을 계산할 수 있다.
w = exp(2πi/L) (4)
˜ ai =
L−1
X
s=0
wisai (5)
˜
ci≡ ˜aib˜i (6) 라 두면
cr = 1 L
L−1
X
i=0
˜
crw−ri = 1 L
L−1
X
i=0
˜
ar˜brw−ri = 1 L
X
i,j,k
w−riajwrjbkwrk (7)
=X
j,k
δr,j+kajbk = X
j+k≡r mod L
ajbk=
r−1
X
j=0
ajbr−j (8)
이 되기 때문이다. 식8 에서 마지막 부호는 i + j = L + r 일경우 i 나 j 가 L/2 보다 큰데 k > L/2 면 ak = bk= 0 이라서 i + j = r 인항만 살아남기에 성립하 는것이다.
FFT 는 O(L log L) 인 알고리즘이 이미 있기때문에 a 와 ˜a 사이의 변환은 O(L log L) 에 할 수 있고, ˜a, ˜b 로부터 ˜c 를 계산하고 자릿수를 맞추는것은 O(L) 에 할 수 있으므로 O(L log L) 의 시간에 곱셈을 할 수 있게 된다. 구체적인 FFT 를 알고리즘은 다음장에서 다룰 Zp∗ Field 에서의 FFT 을 이용한 곱셈 알 고리즘 에서 다루도록 하겠다.
한편 a 와는 달리 ˜a 는 정수가 아니라 복소수이기 때문에 어느정도의 유효숫 자가 필요한지를 아는것이 매우 중요하다. 다음장에서 실수연산 없이 정수연산
만을 이용하는 알고리즘을 소개하기때문에 자세한 증명은 다루지 않겠지만, [2]
의 4.3.3 장에 따르면 m = 4l + 2k 의 유효숫자가 있으면 된다고 한다. 64 비트 컴퓨터에서는 128 비트 실수연산이 가능하기 때문에 k 를 8 정도로 작게 잡으면 아주 큰 크기의 정수가 아니면 컴퓨터의 기본 실수형 만으로도 220비트의 정 수연산도 계산이 가능하다.
4.2 FFT with Polynomial on Field
앞서 다룬 FFT 를 이용한 곱셈알고리즘의 단점은 정수계산을 위해 실수계산도 해야 한다는것이다. 이러한 단점은 Field, 특히 그중에서도 Zp∗에서의 연산을 이용하면 해결할 수 있다.
이때 적절한 p 를 선택하는것이 중요한데
• ci를 정확히 계산할 수 있으려면 ci< p 임이 보장되야 한다.
• w2/L̸= 1, wL≡ 1 mod n 즉 order 가 L 인 w 가 있어야 한다.
한가지 방법은 ci < LB2 = 2l+2k므로 적절한 m 을 선택해서 p = q ∗ 2m+ 1 꼴의 소수를 찾아 Zp∗을 이용하는 것이다. 이경우 중간에 ˜ci등을 계산하는 과 정에서는 p 보다 큰 수가 나올 수 있어도 마지막에 ci는 올바른 값을 구할 수 있다.
1: Make table of w2, w4, w8, · · · , wL2 ◃ for compute wn efficiently.
2: Compute ˜a, ˜b.
3: for i = 0 to L-1 do
4: c˜i← ˜aib˜i
5: Compute c.
6: end for
7: carry ← 0
8: for i = 0 to L-1 do
9: tmp ← ci+ carry
10: (carry, ci) ← (⌊tmp/B⌋, tmp mod B)
11: end for
ai↔ ˜ai간의 변환알고라즘은 다음과 같다.([2] 4.3.3 장 참고)
1: A[0](tl−1, · · · , t0) ← at, where t = (tl−1, · · · , t0)2.
2: A[1](sl−1, tl−2, · · · , t0) ← A[0](0, tl−2, · · · , t0) + w2l−1sl−1A[0](1, tl−2, · · · , t0)
3: A[2](sl−1, sl−2, tl−3, · · · , t0) ←
A[1](sl−1, 0, tl−3, · · · , t0) + w2l−2(sl−2sl−1)2A[1](sl−1, 1, tl−3, · · · , t0)
4: . . .
5: A[l](sl−1, · · · , s1, s0) ←
A[l−1](sl−1, · · · , s1, 0) + w(s0s1···sl−1)2A[l−1](sl−1, · · · , s1, 1)
수학적 귀납법을 사용하면 s = (sl−1, · · · , s0)2, t = (tl−1, · · · , t0)2 라 할때
A[j](sl−1, · · · , sl−j, tl−j−1, · · · , t0) = X
0≤tl−1,···,tl−j≤1
w2l−j(sl−j···sl−1)2(tl−1···tl−j)2at
(9) 라서 A[l](sl−1, · · · , s1, s0) =P
twstat= ˜at 임을 알 수 있다.
이 알고리즘은 각각의 단계에서 A[i]들을 병렬로 계산할 수가 있어서 계산 을병렬화 하는데 별다른 노력을 들이지 않아도 된다는 장점도 있다.
실행시간을 생각해보면, l(= log L) 단계가 있고 각 단계마다 2l−1번의 곱 셈, 덧셈을 하므로 O(L log L) = O(len(a) · len(len(a))) 의 시간에 계산을 할 수 있다.
5 병렬 나눗셈 알고리즘
일반적으로 컴퓨터는 나눗셈속도가 곱셈보다 몇배 이상 느리다. Newton’s it- eration 은 나눗셈 연산을 동등한 곱셈문제로 치환해서 계산하는 알고리즘이다.
병렬 곱셈알고리즘만 있으면 자동적으로 나눗셈도 병렬화 된다는 장점도 가지 고 있다.
실수 수열인
xn= xn−1(2 − bxn−1) (10) 은 1/b 값으로 수렴한다. 따라서 a = bq + r 에서 p, q 값을 계산하려면 우선 64- 비트 실수 연산으로 1/b 의 근사값을 구한 후 이 수열의 극한값을 |xn− 1/b| <
1/2q 의 오차내에서 구하면 된다. 이경우 |xn− q| < 1 이 되므로 p, q 를 금방 구할 수 있다.
ϵ ← 2len(a)−len(b)+1(< 1q)
tmp ← (double precision approximaion of) b x ← 1.0/tmp
while x −1b < ϵ do x ← x(2 − bx) end while
tmp ← xb
if a − tmp > b then q ← tmp + 1
else if a − tmp < 0 then q ← tmp − 1
else
q ← tmp end if r ← a − bq 라고 할 수 있다.
실행시간을 가늠해보면. xi =1b(1 + ϵ) 이라 할때, xi+1=1b(1 − ϵ2), xi+2 =
1
b(1 − ϵ4), · · · 이므로 ϵ2n < 2−len(q)일때 끝난다. 즉 n = O(len(len(q))) 면 p,q 를 구할 수 있다.
앞서 구했듯이 곱셈은 O(len(a)·len(len(a))) 이므로 나눗셈은 O(len(len(q))·
len(a) · len(len(a))) 의 시간이 걸린다.
위 알고리즘에서 x0일때의오차가 대략 250이므로 (64 비트 실수의 유효숫 자가 52 비트므로) q 가 3000 비트라고 하여도 n = 6 번의 곱셈으로도 나눗셈을 정확히 계산할 수 있다.
6 결론
덧셈은 O(L) 시간에 계산이 가능하며, n 개의 CPU 를 사용할경우 n/2 배 정도 의 성능향상을 기대할 수 있다. 곱셈은 O(L · logL) 시간에 계산이 가능하며, n 개의 CPU 를 사용할경우 n 배 정도의 성능향상을 기대할 수 있다. 나눗셈은 동 치인 덧셈과 곱셈 문제로 치환할 수 있으며 O(L · logL · loglogq) 시간에 계산이 가능하다. n 개의 CPU 를 사용할경우 n/2 ∼ n 배 정도의 성능향상을 기대할 수 있다.
참고 문헌
[1] Lars Lundberg, “Distributed high performance large integer arithmetic”
Parallel Processing Workshops, 2002. Proceedings. International Confer- ence on (doi=10.1109/ICPPW.2002.1039739)
[2] Donald E. Knuth, “Art of Computer Programming, Volume 2: Seminu-
merical Algorithms” Addison-Wesley Professional; 3rd edition (1997)
