다음 루프를 모두 병렬 처리 할 수 ​​있습니까?

Question

do i=2, n-1 
    y(i) = y(i+1) 
end do 

do i=2, n-1 
    y(i) = y(i+1) - y(i-1) 
end do 

안녕하세요, 둘 다 이러한 루프를 병렬 처리 할 수 ​​있는지 궁금하네요? y(i+1) 부분으로 인해 불가능합니다. 왜냐하면 그것은 아직 생성되지 않은 값에 의존하기 때문입니다.

Answer 1

y가 배열 (함수처럼 보이지만 함수 호출에 할당하려는 배열) 인 경우 y (i + 1) 부분은 이미 존재하지만 병렬 처리에는 여전히 문제가 있습니다.

Answer 2

물론 가능합니다.

각 병렬 작업이 다른 작업의 메모리를 "밟지"않는 방식으로 작성하면됩니다.

두 번째 경우에는 까다 롭지만 충분히 생각하면 가능할 것입니다.

Answer 3

첫 번째 경우 병렬 저장은 보조 저장 영역이있는 경우에만 가능합니다. 당신은 단지 두 개의 병렬 실행 유닛을 사용하려는 경우 배열의 한 요소에 대한 스토리지가 필요합니다

for all i in [2, n-2] in parallel do 
    y'(i) = y(i+1) 
end do 

: 당신이 필요로하는

e = y(n/2) 
for all i in [0, 1] in parallel do 
    for j in [1, n/2 - 1] do 
     y(i*n/2 + j) = (y(i*n/2 + j) 
    end do 
end do 
y(n/2 - 1) = e 

최대 병렬 처리를 위해, 당신은 완전히 별도의 배열이 필요합니다 이것은 상반기의 마지막 요소와 후반부의 첫 번째 요소에 대한 경쟁 조건을 피하기 위해서입니다. 사실 필요한 추가 저장 공간과 코드를 병렬화하는 요소 간에는 직접적인 관계가 있습니다.

y (i)를 계산하기 위해 y (i-1)를 계산 했으므로 두 번째 루프를 병렬 처리 할 수 ​​없습니다. 안돼. 이것은 루프가 시작되기 전에 결국 읽혀지는 모든 값이 올바른 값을 갖기 때문에 첫 번째 루프에서는 문제가되지 않습니다. 두 번째가 아닙니다!

이러한 루프는 순차적으로 실행해야하는 경우 결합 할 수 있습니다. 첫 번째 병렬 처리와 두 번째 혼자 처리보다 빠릅니다. 두 경우 모두

Answer 4

당신은 "루프 수행 의존성"

do i=2, n-1  
    y(i) = y(i+1) - y(i-1) 
end do 

Y (I)의 계산이라고 Y에 따라 무엇을 가지고 (내가 +/- 1) 병렬 루프에서 당신은을 guarentee 수 없기 때문에 y (i + 1)가 실행될 순서는 y (i)가 계산되기 전에 이미 새 값으로 업데이트되었을 수 있습니다. 더 나쁜 여전히 y (i + 1)은 한 스레드에서 업데이트되는 동안 다른 스레드가 손상된 값을 읽으려고 시도 할 수 있습니다 (데이터가 업데이트되는 과정의 절반 정도이기 때문에). 배열 Y는 병렬 루프에 의해 업데이트되지 않기 때문에 잘못된 답변.

여기에 가장 좋은 해결책은 읽기 전용 및 쓰기 가능한 배열을 가지고있다가

do i=2, n-1  
    yNew(i) = yOld(i+1) - yOld(i-1) 
end do 
swap(yOld, yNew) 

이제 문제는 사라집니다. 언어가 쉽게 할 수있는 포인터를 지원하는 경우 포인터를 유지하면서 새로운/이전 배열을 스왑하고 단순히 포인터를 바꾸면됩니다. 추가 오버 헤드는 참조 할 루프의 읽기 전용 복사본으로 데이터의 추가 복사본을 유지해야한다는 것입니다.