확장 가능한 지역

컴퓨터 소프트웨어는 메모리 시스템을 앞지르는 프로세서를 계속 사용할 수 있다면 더 큰 문제를 해결하기 위해 확장 가능한^[1] 로컬리티를 보여준다고 합니다.이 용어는 확장 가능한 병렬 처리를 사용하는 고성능 단일 프로세서 유사체이며, 더 큰 문제에 대해 더 많은 수의 프로세서를 사용할 수 있는 소프트웨어를 나타냅니다.

개요

다음 루프 네스트의 메모리 사용 패턴을 검토합니다(2차원 스텐실 계산 반복).

위해서 t := 0 로. T 하다     위해서 i := 1 로. N-1 하다         위해서 j := 1 로. N-1 하다             신규(i,j) := (A(i-1,j) + A(i,j-1) + A(i,j) + A(i,j+1) + A(i+1,j)) * .2         끝.     끝.      위해서 i := 1 로. N-1 하다         위해서 j := 1 로. N-1 하다             A(i,j) := 신규(i,j)         끝.     끝. 끝. 

루프 네스트 전체가 약 2*N*2개의 어레이 요소에 대응하여 약 5*T*N*2개의 부동소수점 연산을 수행합니다.따라서, 이 루프 네스트 전체의 계산 밸런스(사용되는 부동 소수점 메모리 셀에 대한 부동 소수점 계산 비율)는 약 5T/2입니다.여기서와 같이 컴퓨팅 밸런스가 문제 크기의 함수인 경우 코드는 확장 가능한 컴퓨팅 밸런스를 가지고 있다고 합니다.여기서는 충분한 사이즈를 선택하는 것만으로 원하는 컴퓨팅 밸런스를 실현할 수 있습니다.T.

단, 언제N이 코드는 크지만 참조 위치가 낮기 때문에 캐시 재사용이 양호하지 않습니다.두 번째 할당에 new(1,1)가 필요하거나 첫 번째 할당의 두 번째 스텝 실행 시 new(1,1)를 유지하는 캐시 행이 어레이의 다른 일부와 덮어쓰기됩니다.

첫 번째 i/j 루프 네스트를 타일링하면 캐시 성능이 향상되지만 캐시 성능의 균형은 약 5/2이므로 제한적입니다.예를 들어 500과 같이 매우 높은 수준의 로컬리티를 생성하려면(RAM에 맞지 않고 가상 메모리로 밀려난 어레이로 이 코드를 효율적으로 실행하려면) 시간 스텝에 걸쳐 값을 재사용해야 합니다.

시간별 최적화는 여러 연구 컴파일러에서 검토되고 있습니다. 시간 타일링에 대한 일부 접근법에 대한 자세한 내용은 Wonnacott,^[1][2] Song and ^[3]Li 또는 Sadayappan ^[4]등의 작업을 참조하십시오.Wonnacott는^[1] 코어 외 데이터 세트를 최적화하기 위해 시간 타일을 사용할 수 있음을 입증했습니다.원칙적으로 이러한 접근법^[2][3][4] 중 어느 것이든 어레이 전체를 캐시에 넣을 필요 없이 임의로 높은 메모리 인접성을 달성할 수 있어야 합니다(단, 캐시 요건은 필요한 인접성에 따라 증가합니다).위에서 언급한^[2][4] 멀티프로세서 기술은 원칙적으로 확장 가능한 로컬성과 확장 가능한 병렬성을 동시에 생성해야 합니다.

레퍼런스