Solution to Problem 5.10

shy3939 2026. 1. 18. 16:02

2026. 1. 18. 16:02

Practice Problem 5.10

As another example of code with potential load-store interactions, consider the following function to copy the contents of one array to another:

load–store 상호작용이 발생할 가능성이 있는 또 다른 코드 예로서,한 배열의 내용을 다른 배열로 복사하는 다음 함수를 살펴보자.

load-store 상호작용 : "이전에 메모리에 쓴 값이 다음에 다시 읽혀서 반복 간 의존성이 생기는 상황"을 말한다.

src : 원본 배열

dest : 복사 대상 배열

n : 원소의 개수

Example A : 주소가 겹치지 않는 경우

<의미>

store 주소 ≠ 다음 load 주소
즉, 쓴 곳을 다시 읽지 않음

<결과>

임계 경로는 카운터 감소(sub) 쪽만 남음
load와 store가 서로 독립
CPU가 겹쳐서 실행 가능

>> CPE 낮음

Example B : 주소가 겹치는 경우

<의미>

store 주소 == 다음 iteration의 load 주소
즉, 이전에 쓴 값을 바로 다음에 읽음

<결과>

의존성 체인 : store -> load -> add -> store -> load -> ....
이 체인이 임계 경로가 됨
반복 간(loop-carried) write/read 의존성 발생

>> CPE 높음

A. copy_array(a+1, a, 999)의 효과는?

// 실제 동작
dest = a
src = a+1

i=0일 때, a[0] = a[1]
i=1일 때, a[1] = a[2]
...
i=998일 때, a[998] = a[999]

// 결과
모든 a[i]가 원래 a[i+1]값이 됨

초기값이 모두 i라면:
a[0] = 1, a[1] = 2, ... ,a[998] = 999

B. copy_array(a, a+1, 999)의 효과는?

// 실제 동작
dest = a+1
src = a

i=0일 때, a[1] = a[0]
i=1일 때, a[2] = a[1] // 방금 쓴 값을 읽음

// 결과
a 전체가 0으로 수렴(초기 a[0] = 0이라면)

C. 왜 A는 CPE 1.2 -> 1.0으로 개선되는데, B는 CPE 5.0이 나오는가?

// A의 경우(a+1 -> a)
- 주소 겹침x
- load와 store 독립
- 언롤링하면:
	- load 여러 개 미리 수행 가능
    - 파이프라인 잘 채워짐
CPE ≈ 1.0

// B의 경우(a-> a+1)
- 주소 겹침o
- 이전 iteration의 store 결과를 다음 iteration에서 반드시 load

stroe->load->store->load-> ....

// 임계 경로가 메모리까지 포함
// 언롤링해도 소용 없음
CPE ≈ 5.0

D. copy_array(a, a, 999)의 성능은?

// 실제 동작
a[i] = a[i]

// 논리적 결과
값 변화 없음

// 하지만 성능은?
store 주소 == load 주소(완전 동일)
매 iteration:
	store(a[i]) -> load(a[i])      // 가장 강한 load->store 의존성

// 예상 CPE
빠를 것으로 예상