⁉️ 지난번에는

지금까지는 루프 혹은 호출 등에서 불필요한 반복 제거와 메모리 참조 최적화를 통해
프로그램을 더 가볍게 만드는 방법을 살펴보았다.
하지만 “가볍게 만드는 것”만으로는 한계가 있다.
현대 프로세서가 가진 병렬 실행 능력을 최대한 활용하기 위해서는
루프 자체의 구조를 변형하여 더 많은 연산을 동시에 진행할 수 있도록 만들어야 한다.

그 대표적인 기법이 바로 루프 풀기(loop unrolling)와 다중 누산기(multiple accumulators)를
활용한 명령 수준 병렬성(ILP, Instruction-Level Parallelism) 확대 이다.

🔄 루프 풀기

루프의 매 반복실행마다 계산되는 원소의 수 자체를 증가시켜서
루프에서의 총 반복 실행 횟수를 줄이는 프로그램 변환

이는 두가지 측면에서 이루어질 수 있다.

• 인덱스 계산, 조건부 분기 등 프로그램의 결과와는 직접적으로 관련이 없는 연산들의 수를 줄인다.
• 전체 계산의 핵심 경로에 있는 연산의 수를 줄이기 위한 추가 코드변환을 할 수 있는 방법을 적용한다.

💬 루프 풀기의 기본 아이디어를 살펴보았으니, 이제 실제 코드 예제를 통해
얼마나 반복 횟수를 줄이고 병렬성을 끌어낼 수 있는지 단계별로 확인해 보자.

---

📝 combine 4

👩🏻‍💻 코드 설명

acc = acc OP data[i]

• 반복문에서 매번 하나의 원소를 load 후 누적값(acc)에 연산
• 모든 연산이 이전 결과(acc)에 의존하기 때문에 병렬성이 낮고 CPE가 높다.

💾 레지스터 역할

%rax : data 배열 시작 주소
%rbp : 종료 인덱스 조건
%rdx : 현재 인덱스
%xmm0 : 누적값(acc) 저장

🧩 데이터 흐름

• load_1 : %rdx → 이번 인덱스에 대한 주소 계산
• mul_1 :%xmm0에 저장되어 있는 누적값 acc와 새 값 연산 후 저장
• add, cmp, jne : %rdx 증가, %rbp 비교로 루프 제어

---

📝 combine 5

👩🏻‍💻 코드 설명

acc = (acc OP data[i]) OP data[i+1]

2 * 1 loop unrolling

• 2의 배수에 대해 계산을 진행하지만 단일 변수에 누적한다.
• 루프 언롤링 덕분에 한 번 반복에서 load → mul → load → mul 순서로 실행되므로,
  CPU 파이프라인이 로드와 곱셈을 겹쳐서 수행할 수 있다.
• i번째 데이터와 누적값의 곱셈후에야 다음 결과를 누적할 수 있으므로 데이터 종속성이 남아 있다.
• 한번의 루프에서 2개의 데이터에 대한 연산을 진행하므로 반복실행 횟수는 절반으로 줄었다.

💾 레지스터 역할

%rax : data 배열 시작 주소
%rbp : 종료 인덱스 조건
%rdx : 현재 인덱스
%xmm0 : 누적값(acc) 저장

🧩 데이터 흐름

• load_1 : %rax, %rdx → i 번째 인덱스에 대한 주소 계산
• mul_1 :%xmm0에 저장되어 있는 누적값 acc와 새 값 연산 후 %xmm0 에 저장
• load_2 : %rax, %rdx → i+1 번째 인덱스에 대한 주소 계산
• mul_2 :%xmm0에 저장되어 있는 누적값 acc(i번째 값 포함)와 새 값 연산 후 %xmm0 에 저장
• add, cmp, jne : %rdx 증가, %rbp 비교로 루프 제어

👍🏻 성능 개선

📌 k × 1 루프 풀기와 성능 한계

🔍 k × 1 루프 풀기란?

• 한 루프에서 k개의 원소를 순차적으로 처리하는 방식
• 예시:
  • 2×1 unrolling (combine5)

    acc = (acc OP data[i]) OP data[i+1];

  • 3×1 unrolling

    acc = ((acc OP data[i]) OP data[i+1]) OP data[i+2];

• 단일 누산기만 사용하여, 루프 제어 횟수를 줄이는 효과가 있다.

⚠️ 성능 개선의 한계 이유

1. 데이터 의존성 유지

• 모든 연산이 acc에 의존 → acc = acc OP data[i]가 끝나야 다음 연산 시작 가능.
• 따라서 CPU의 여러 실행 유닛을 병렬로 활용 불가능.
• 결국 Latency bound(지연 한계) 이상으로는 성능 개선 불가.

2. 루프 오버헤드 감소 효과의 한계

• 언롤링(k 증가) → 루프 제어 비용(cmp, jne) 감소.
• 하지만 일정 지점 이후에는 루프 제어 비용이 전체 실행 시간에서 차지하는 비중이 작아짐.
• → 더 언롤해도 성능 개선 거의 없음.
• 실제로 combine5 (2×1)와 3×1의 성능이 동일한 이유.

3. 레지스터 압박 & 코드 크기 증가

• k가 커질수록 코드 크기가 커지고, 레지스터 사용이 늘어난다.
• 최적화 효과가 줄고, 오히려 성능 저하 가능성 있다.

---

✅ 요약

• k×1 언롤링은 루프 제어 오버헤드 감소 효과는 있지만,
  단일 누산기 사용으로 인해 데이터 의존성 문제를 해결하지 못한다..
• 따라서 일정 지점(k>2~4) 이상에서는 성능 개선이 멈춘다.

💬 즉, 방금 본 것 처럼 k * 1 루프 풀기 만으로는 성능 개선에 제한이 생긴다.
더 큰 개선을 원한다면 👉 다중 누산기(multiple accumulators) 기법이 필요하다.

---

🔄 병렬성 높이기

💬 위에서 본 것 처럼 지금까지 우리의 함수들은 산술연산 유닛들의 지연시간으로 인한 경계값을 가졌다. 지금부터 이 순차적 의존성을 깨고, 지연시간 경계값보다 좋은 성능을 얻을 수 있는 방법들을 살펴볼 것이다.

🧮 다중 누산기 사용

정수 덧셈이나 곱셈과 같이 교환성과 결합성이 있는 연결연산에 대해
연결연산의 집합을 여러 부분으로 나누고 결과를 마지막에 합치는 방법

즉, 반복실행마다 보다 많은 원소를 연결하기 위한 N중 루프 풀기와
교환, 결합성이 있는 연결연산의 집합을 나누어 누적 연산하는 N중 병렬성을 모두 사용할 것이다

📝 combine 6

👩🏻‍💻 코드 설명

acc0 = acc0 OP data[i];
acc1 = acc1 OP data[i];

2 * 2 loop unrolling

• 한 루프에서 짝수와 홀수 각각 1개씩 총 2개의 원소 처리
• 짝수 번호를 갖는 원소들을 위한%xmm0와 홀수 번호를 갖는 원소들을 위한 %xmm1
  총 두 개의 독립되어 있는 누적값 레지스터를 사용
• 데이터 의존성에 대해서 두 갈래로 나눠 일부 병렬화 가능

💾 레지스터 역할

%rax : data 배열 시작 주소
%rbp : 종료 인덱스
%rdx : 현재 인덱스
%xmm0 : 짝수 인덱스 누적값
%xmm1 : 홀수 인덱스 누적값

🧩 데이터 흐름

• load_1 : %rax, %rdx → i 번째 인덱스에 대한 주소 계산
• mul_1 : 짝수 인덱스를 위한 %xmm0에 저장되어 있는 누적값 acc와 새 값 연산 후 %xmm0 에 저장
• load_2 : %rax, %rdx → i +1 번째 인덱스에 대한 주소 계산
• mul_2 : 홀수 인덱스를 위한%xmm1에 저장되어 있는 누적값 acc(i번째 값 포함)와 새 값 연산 후 %xmm1 에 저장
• add, cmp, jne : %rdx 증가, %rbp 비교로 루프 제어

---

📈 k × k 루프 풀기의 실제 성능

🔹 예제 결과 요약

• 정수 덧셈(Integer +)
  • k ≥ 7일 때 CPE ≈ 0.54 → 이론적 throughput bound (0.50)에 근접
• 정수 곱셈(Integer ×), 부동 덧셈(FP +)
  • k ≥ 3일 때 CPE ≈ 1.01 → throughput bound (1.0)에 근접
• 부동 곱셈(FP ×)
  • k ≥ 10일 때 CPE ≈ 0.51 → throughput bound (0.50)에 근접

➡️ 즉, k를 충분히 키우면 CPE가 거의 throughput bound에 가까워짐을 알 수 있다.

---

🔹 성능이 개선되는 이유

• 루프 제어 오버헤드가 분산되어 CPE가 낮아진다.
• 파이프라인을 더 효율적으로 채워서 여러 실행 유닛을 활용할 수 있게 된다.

---

🔹 성능 개선의 조건

• 어떤 연산의 latency = L
• 해당 연산을 처리할 수 있는 유닛의 개수 = C
• 최대 처리량을 내려면 언롤링 factor k ≥ L × C 필요.

즉, L 시간이 걸리는 기계가 C개 있으니 최대 처리량을 내려면 L * C 개의 작업을 한번에 맡겨야한다.

---

⚠️ 주의할 점

• 루프 풀기만으로 성능이 올라가는 건, 파이프라인이 충분히 독립적 연산으로 채워질 때에 한정된다.
• 하지만 acc 하나만 쓰면 여전히 데이터 의존성이 존재하므로, 완벽한 성능 개선은 어렵다.
• 따라서, 루프 풀기를 다중 누산기(multiple accumulators)와 결합해야 더 큰 개선을 얻을 수 있다.

---

🔄 Reassociation Transformation (재결합 변환)

🔹 아이디어

• 단순히 k×1 언롤링만으로는 데이터 의존성이 여전히 남는다.
• 연산의 괄호 위치(결합 순서)를 바꿔서,
  독립적인 연산을 먼저 수행한 뒤 마지막에 합치는 방식으로 전환.

📝 combine 7

👩🏻‍💻 코드 설명

acc = acc OP (data[i] OP data[i+1])

2 * 1a loop unrolling

• 한 루프에서 총 2개의 원소 처리
• 두 값의 연산을 위한 임시 레지스터%xmm0와 누적값 연산을 위한 %xmm1
  총 두 개의 독립되어 있는 누적값 레지스터를 사용
• 데이터 의존성을 해결하기 위해서 새로운 두 값에 대한 연산 후 누적값과 연산

💾 레지스터 역할

%rax : data 배열 시작 주소
%rbp : 종료 인덱스
%rdx : 현재 인덱스
%xmm0 : 임시 계산 결과(data[i] * data[i+1])
%xmm1 : 누적 결과 값

🧩 데이터 흐름

• load_1 : %rax, %rdx → i 번째 값 %xmm0에 로드
• load_2 : %rax, %rdx → i +1 번째 값 %xmm0에 로드된 값이랑 결합할 준비
• mul_1 : 임시 %xmm0에 저장되어 있는 두 값의 연산 결과값
• mul_2 : %xmm1에 누적값 갱신
• add, cmp, jne : %rdx 증가, %rbp 비교로 루프 제어

✅ 각 반복 실행에 대해서는 combine6나 combine7와 비슷하게 해독되지만,
다른 데이터 의존성을 보인다

⭐️ 즉, 루프안에서 해야 하는 연산 자체는 누적값에 의존하지 않고 전부 계산 후 재기록 할 뿐이다.

✅ 요약

• k×1 언롤링: 루프 오버헤드 줄이고, 일정 수준까지는 throughput bound 접근 가능.
• 하지만 단일 누산기만 사용 → 데이터 의존성 한계
• Reassociation + 다중 누산기: 데이터 의존성을 끊고, critical path를 줄여
  latency bound까지 돌파 가능.

이로써 루프 풀기는 “루프 제어 최적화 → 병렬 실행 극대화”라는 두 단계를 거쳐야 비로소 큰 최적화 효과를 낼 수 있다.