algorithm
멀티 스레드 알고리즘
수색…
소개
일부 멀티 스레드 알고리즘의 예.
통사론
- 루프가 루프 이전에 병렬 이라는 것은 루프의 각 반복이 서로 독립적이며 병렬로 실행될 수 있음을 의미합니다.
- 스폰 은 새 스레드 생성을 나타내는 것입니다.
- sync 는 생성 된 모든 스레드를 동기화하는 것입니다.
- 배열 / 매트릭스는 예제에서 1부터 n까지 인덱싱됩니다.
정사각형 행렬 곱셈 다중 스레드
multiply-square-matrix-parallel(A, B)
n = A.lines
C = Matrix(n,n) //create a new matrix n*n
parallel for i = 1 to n
parallel for j = 1 to n
C[i][j] = 0
pour k = 1 to n
C[i][j] = C[i][j] + A[i][k]*B[k][j]
return C
멀티플렉싱 매트릭스 벡터 멀티 스레드
matrix-vector(A,x)
n = A.lines
y = Vector(n) //create a new vector of length n
parallel for i = 1 to n
y[i] = 0
parallel for i = 1 to n
for j = 1 to n
y[i] = y[i] + A[i][j]*x[j]
return y
병합 - 정렬 다중 스레드
A 는 서브 어레이 A [p..r]를 정렬하는 것과 같은 배열의 p 와 q 인덱스입니다. B 는 정렬에 의해 채워질 하위 배열입니다.
p-merge-sort (A, p, r, B, s) 호출 은 A [p..r]의 요소를 정렬하여 B [s..s + rp]에 저장 합니다.
p-merge-sort(A,p,r,B,s)
n = r-p+1
if n==1
B[s] = A[p]
else
T = new Array(n) //create a new array T of size n
q = floor((p+r)/2))
q_prime = q-p+1
spawn p-merge-sort(A,p,q,T,1)
p-merge-sort(A,q+1,r,T,q_prime+1)
sync
p-merge(T,1,q_prime,q_prime+1,n,B,s)
병렬로 병합을 수행하는 보조 함수가 있습니다.
p-merge 는 병합 할 두 개의 하위 배열이 동일한 배열에 있다고 가정하지만 배열에서 인접하지 않다고 가정합니다. 그래서 p1, r1, p2, r2 가 필요합니다.
p-merge(T,p1,r1,p2,r2,A,p3)
n1 = r1-p1+1
n2 = r2-p2+1
if n1<n2 //check if n1>=n2
permute p1 and p2
permute r1 and r2
permute n1 and n2
if n1==0 //both empty?
return
else
q1 = floor((p1+r1)/2)
q2 = dichotomic-search(T[q1],T,p2,r2)
q3 = p3 + (q1-p1) + (q2-p2)
A[q3] = T[q1]
spawn p-merge(T,p1,q1-1,p2,q2-1,A,p3)
p-merge(T,q1+1,r1,q2,r2,A,q3+1)
sync
여기 보조 기능 dichotomic-search가 있습니다.
x 는 서브 배열 T [p..r]에서 찾을 키입니다.
dichotomic-search(x,T,p,r)
inf = p
sup = max(p,r+1)
while inf<sup
half = floor((inf+sup)/2)
if x<=T[half]
sup = half
else
inf = half+1
return sup
Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow