Solution to Problem 5.11

Practice Problem 5.11

We saw that our measurements of the prefix-sum function psum1 (Figure 5.1) yield a CPE of 9.00 on a machine where the basic operation to be performed, floating-point addition, has a latency of just 3 clock cycles.

prefix-sum 함수 psum1의 성능을 측정해보니, 기본 연산인 부동소수점 덧셈의 지연 시간은 3사이클에 불과한데도 CPE는 9.00이나 나온다.

 

Let us try to understand why our function performs so poorly.

이 함수가 왜 이렇게 성능이 나쁜지 이해해보자.

 

The following is the assembly code for the inner loop of the function:

다음은 해당 함수의 내부 루프(inner loop)에 대한 어셈블리 코드이다.

// Inner loop of psum1
// a in %rdi, i in %rax, cnt in %rdx

.L5:
	vmovss  -4(%rsi,%rax,4), %xmm0         	 	// Get p[i-1]
	vaddss  (%rdi,%rax,4), %xmm0, %xmm0     	// Add a[i]
	vmovss  %xmm0, (%rsi,%rax,4)      		// Store at p[i]
	addq    $1, %rax                  		// Increment i
	cmpq    %rdx, %rax                		// Compare i, cnt
	jne     .L5                       		// If <, goto loop

 

Perform an analysis similar to those shown for combine3 (Figure 5.14) and for write_read (Figure 5.36) to diagram the data dependencies created by this loop, and hence the critical path that forms as the computation proceeds. Explain why the CPE is so high.

combine3(그림 5.14)와 write_read(그림 5.36)에서 보여준 것과 유사한 분석을 수행하여, 이 루프가 만들어내는 데이터 의존성을 도식화하고, 그 결과 계산이 진행되면서 형성되는 임계 경로를 보여라. 그리고 왜 CPE가 이렇게 높은지를 설명하라.

// 이 루프가 하는 일(C코드 관점)
p[i] = p[i-1] + a[i];

---

Solution to Problem 5.11

We can see that this function has a write/read dependency between successive iterations—the destination value p[i] on one iteration matches the source value p[i-1] on the next.

이 함수는 연속된 반복 사이에 write/read 의존성을 가진다. 한 반복에서의 결과 p[i]가, 다음 반복에서의 입력 p[i-1]이 되기 때문이다.

 

he CPE measurement of 9.0 is consistent with our measurement of 7.3 for the CPE of write_read when there is a data dependency, since write_read involves an integer addition (1 clock-cycle latency), while psum1 involves a floating-point addition (3 clock-cycle latency).

 

CPE가 9.0으로 측정된 것은, 데이터 의존성이 있는 write_read의 CPE가 7.3이었던 것과 일관된다.

왜냐하면 write_read는 정수 덧셈 (1사이클), psum1은 부동소수점 덧셈 (3사이클) 을 사용하기 때문이다.

---