반복문을 네 개씩 펼쳤는데 메모리가 두 개만 주는 이유

반복문을 네 배로 펼쳤는데 처리 속도는 두 배만 좋아졌다. 네 개의 계산을 나란히 적는 것과 네 개에 필요한 데이터가 동시에 도착하는 것은 다르다. loop unrolling의 효과를 읽으려면 복제한 연산뿐 아니라 그 연산을 먹여 살리는 메모리와 의존 관계를 같이 봐야 한다.

반복 몸체를 복사하면 생기는 병렬화의 기회

서로 독립적인 입력 10개에 대해 y[i]=a[i]×a[i]를 계산한다고 하자. 입력 배열과 출력은 서로 겹치지 않으며 곱셈 결과를 담을 충분한 폭을 사용한다. 값을 일부러 좁혀 저장하는 효과는 제외한 자체 예제다.

factor=4로 펼친 몸체에는 i, i+1, i+2, i+3의 네 계산이 들어간다. 원래 10번의 반복은 시작 인덱스 0, 4, 8인 세 묶음으로 표현할 수 있다. 앞의 두 묶음에는 유효 계산이 네 개씩 있고 마지막에는 두 개만 있다.

마지막 묶음에서 i+2와 i+3은 배열 범위를 벗어난다. 각 복제본에 필요한 범위 조건을 남기면 유효 출력 10개만 만든다. 이 조건을 없애도 된다고 가정하면 존재하지 않는 입력 10, 11을 읽거나 잘못된 출력을 쓸 수 있다. ‘대부분의 묶음이 네 개’는 마지막 묶음의 조건을 지울 근거가 아니다.

AMD의 unrolling 설명은 반복 몸체의 복제와 자원 증가를 설명하고, 부분 unroll에서 반복 횟수가 factor로 나누어떨어지지 않을 때 종료 검사가 필요함을 다룬다. 실제 구현에서는 정적인 반복 범위, 도구의 변환과 인터페이스를 함께 확인해야 한다.

네 곱셈기가 같은 두 읽기 포트를 기다린다면

각 입력을 한 번씩 읽고, 곱셈기는 네 개이며 출력은 별도 자원으로 보낼 수 있다고 가정하자. 입력 메모리는 한 사이클에 서로 다른 주소 두 개만 읽는다. 이 메모리에서 네 입력을 가져오려면 최소 두 사이클이 필요하다.

unroll된 한 묶음을 매 사이클 시작하면 정상 구간에 읽기 네 번을 매 사이클 요구한다. 공급 가능한 두 번보다 많다. 같은 자원 모델에서 묶음의 시작 간격은 평균 대역폭만 보아도 최소 2다. 이때 숫자 2는 원래 입력 한 개의 시작 간격이 아니라 네 입력 묶음의 시작 간격이다.

원래 계산 한 개씩 두 사이클에 시작하던 구성이었다면 평균 입력량은 사이클당 0.5개다. 네 개를 두 사이클마다 시작하는 새 구성의 상한은 사이클당 2개다. ‘II=2로 그대로’라는 설명도 반복의 의미가 바뀌면 같은 처리량을 뜻하지 않는다. 실제 시간표에 충돌이 더 있다면 이 상한에도 도달하지 못할 수 있다.

메모리를 나누면 포트 수가 늘지만 접근 패턴이 맞아야 한다. 예를 들어 주소를 2로 나눈 나머지에 따라 두 단일 읽기 포트 뱅크로 나누자. 주소 0과 1은 다른 뱅크여서 함께 읽을 수 있다. 주소 0과 2는 같은 뱅크여서 충돌한다. 총 뱅크 수만으로 모든 두 접근의 병렬성을 보장하지 못한다.

AMD의 array partitioning 문서는 연속 구간을 나누는 방식과 인덱스를 교대로 나누는 방식을 구별한다. 어느 방식을 선택하든, 펼친 복제본이 실제로 요구하는 주소들을 뱅크에 대응시켜 보아야 한다. 레지스터로 완전히 나누면 다른 자원 비용도 생긴다.

처음의 10개 작업 전체에서도 포트 하한을 계산할 수 있다. 같은 두 읽기 포트라면 입력을 가져오는 데 최소 다섯 사이클이 필요하다. 네 개씩 펼친 세 묶음이 있다는 사실은 세 사이클 완료를 뜻하지 않는다. 이 다섯 사이클 역시 읽기만의 하한이므로 메모리 결과 지연, 곱셈과 마지막 출력 전달을 더 봐야 한다. 마지막 묶음의 빈 두 복제본은 남은 두 입력을 네 입력으로 늘리지 않는다.

몸체를 펼쳐도 값의 순서는 남을 수 있다

독립적인 제곱과 달리 상태를 갱신하는 반복은 이전 결과를 사용할 수 있다. 가상 연산으로 매번 state=clamp(state+a[i],−128,127)을 수행하고 그 상태를 출력한다고 하자. clamp는 범위를 넘으면 경계 값으로 포화시키는 규칙이다. 실제 언어의 기본 정수 덧셈이 이 규칙을 갖는다고 가정하지 않는다.

초기 상태 0에 입력 100, 100, −100을 순서대로 적용하면 상태는 100, 127, 27이다. 몸체를 세 개 복제해도 둘째는 첫째의 100을, 셋째는 둘째의 127을 사용해야 한다. 복제만으로 세 연산의 입력 상태가 동시에 준비되지는 않는다.

둘째와 셋째 입력을 먼저 더해 0을 만든 뒤 첫 입력과 결합하면 최종값은 100이다. 원래 결과 27과 다르다. 순차 갱신을 트리로 바꾸는 별도 최적화에는 연산 순서 변경의 정당성이 필요하다. 특히 반복별 상태 출력까지 요구하면 최종 합이 같다는 설명만으로 충분하지 않다.

loop unrolling을 적용한 뒤에는 복제된 연산 수, 유효한 마지막 반복, 메모리 공급량, 남은 상태 의존성을 연결해 확인할 수 있다. 네 배의 몸체가 네 배의 성능을 보장하지는 않지만, 병렬로 실행할 기회를 넓히는 것은 분명하다. 그 기회를 실제 처리량으로 바꾸는 데 필요한 데이터와 자원이 무엇인지 보이면 factor를 키울지, 접근 구조를 먼저 바꿀지 판단할 수 있다.