연산기가 비어 있어도 누적 루프가 기다리는 이유

같은 덧셈기를 매 사이클 사용할 수 있는데도 누적 루프의 시작 간격은 세 사이클이라고 하자. 연산기가 놀고 있는 것처럼 보이지만, 다음 덧셈에 넣을 누적값이 아직 나오지 않았을 수 있다. loop-carried dependence는 이처럼 한 반복의 결과가 다른 반복의 입력이 되는 관계다.

빈 연산기보다 아직 없는 입력이 문제다

설명용 누적 계산을 s = s + a[i]로 쓰자. 초기 s는 0이고 입력은 모두 준비되어 있다. 덧셈기는 결과 지연 3사이클, 입력 수락 간격 1사이클이라고 가정한다. 수치 연산은 이 예제에서 오버플로 없는 정수 덧셈이다.

첫 반복을 시각 0에 시작하면 새 s는 3에 나온다. 두 번째 반복은 그 s를 읽으므로 가장 빨라도 3에 시작해 6에 끝난다. 세 번째는 6에 시작한다. 덧셈기 내부에 빈 단계가 있어도 같은 누적값의 다음 갱신을 시각 1에 시작할 수 없다.

독립적인 다른 누적 계산을 함께 처리한다면 빈 자리를 사용할 여지가 있다. 그러나 그것은 다른 상태를 읽는 계산이다. 단일 누적값의 의존성 자체가 사라졌다고 해석하면 안 된다. 필요한 데이터가 준비되는 시각과 하드웨어가 입력을 받을 수 있는 시각 중 늦은 쪽이 실제 시작을 제한한다.

예를 들어 독립 상태 A, B, C가 각각 세 사이클마다 갱신된다면 한 덧셈기에 A를 0, B를 1, C를 2에 보낼 수 있다. A의 결과가 준비되는 3에는 다시 A를 보낸다. 자원 전체는 매 사이클 시작하지만 각 상태의 연속 갱신 간격은 여전히 3이다. 이런 교차 배정은 세 개의 독립 요청을 가진 경우의 선택이며, 단일 요청의 누적 지연을 줄였다고 보고해서는 안 된다.

의존 거리를 넣으면 하한이 보인다

반복 사이에 d칸 떨어진 의존성을 생각해 보자. 연산 u의 결과를 d번째 뒤 반복의 v가 읽는다면, 정해진 반복 간격 II에는 다음 조건이 필요하다.

S(v)+d×II ≥ S(u)+L(u)

S는 한 반복 안에서의 시작 위치, L은 결과 지연이다. CIRCT의 실제 precedence 검증 코드의 CyclicProblem도 이 관계를 검사한다. 같은 연산으로 돌아오는 단순한 자기 의존성에서는 S가 양쪽에서 없어져 d×II≥L이 된다.

앞의 누적은 L=3, d=1이므로 II≥3이다. 다른 프로그램인 s[i]=s[i−2]+a[i]를 만들고 처음 두 상태를 준비해 두면, 같은 덧셈 지연에서도 d=2여서 정수 간격 하한은 II≥2다. 반복 시작을 0, 2, 4, 6으로 두면 세 번째는 첫 결과가 나온 3 이후인 4에 시작한다. 네 번째도 둘째 결과가 나온 5 이후인 6에 시작할 수 있다.

일반적인 순환 경로에는 여러 연산이 들어간다. 그 경로의 지연 합과 의존 거리 합을 비교해야 하며, 덧셈 한 개의 지연만으로 전체 하한을 정할 수 없다. 메모리 읽기와 쓰기가 순환에 들어가면 그 시간도 포함된다. 자원 충돌과 클록 조건이 더해지면 이 하한보다 긴 II가 필요할 수 있다.

의존 거리를 늘리면 프로그램도 달라질 수 있다

앞의 두 식에 입력 1, 2, 3, 4, 5, 6을 넣어 보자. 단일 누적의 반복별 결과는 1, 3, 6, 10, 15, 21이다. 두 칸 전의 결과를 쓰고 두 초기 상태를 0으로 둔 계산은 1, 2, 4, 6, 9, 12다. 짝수와 홀수 위치가 각각 별도의 누적 경로를 이룬다.

두 마지막 값 9와 12를 더하면 총합 21을 얻는다. 하지만 중간 결과는 원래의 누적과 다르다. 최종 총합만 요구하는 문제라면 여러 부분 합과 마지막 결합을 검토할 수 있어도, 각 입력까지의 누적값이 필요한 문제에 같은 변환을 그대로 쓸 수는 없다. 부동소수점이나 포화 연산에서는 결합 순서가 최종 결과에도 영향을 줄 수 있으므로 산술 계약까지 확인해야 한다.

즉 더 짧은 II를 얻는 구조가 있다는 사실과 원래 프로그램을 보존하는 구조라는 사실을 함께 증명해야 한다. 성능 숫자가 좋아졌는데 필요한 출력의 의미가 바뀌었다면 개선으로 쓸 수 없다.

추정된 의존성과 실제 의존성을 구분한다

배열의 런타임 주소가 복잡하면 컴파일러가 두 접근의 충돌 가능성을 보수적으로 남길 수 있다. 접근이 실제로 분리되어 있다는 계약을 증명하면 이 제약을 완화할 여지가 있다. AMD의 DEPENDENCE 설명은 반복 안팎의 의존성을 구별하며, 존재하는 의존성을 없다고 지정하면 잘못된 하드웨어가 나올 수 있다고 설명한다.

가령 같은 주소 k의 값이 10이고 연속해서 두 번 1을 더한다면 결과는 12여야 한다. 두 반복이 오래된 10을 동시에 읽어 각각 11을 써 버리면 마지막 값은 11이다. 두 입력 주소가 언제나 다르다는 보장은 이 입력에서는 성립하지 않는다. 빠른 시간표에 맞추기 위해 false를 지정할 근거가 없는 셈이다.

loop-carried dependence를 줄이려면 먼저 어떤 값이 어느 반복에서 나와 어디로 돌아가는지 그릴 수 있다. 가짜 충돌은 주소 계약으로 풀고, 실제 순환은 필요한 결과를 보존하는 알고리즘 변경으로 풀어야 한다. 빈 연산기의 존재보다 아직 준비되지 않은 상태가 중요하다는 점을 이해하면, 세 사이클 간격의 이유와 바꿀 수 있는 범위가 함께 보인다.