[CSAPP] 5.11 Some Limiting Factors(일부 제한 요인들)

5.11 Some Limiting Factors(일부 제한 요인들)

 

위 throughput bound 말고도 성능을 제한시킬 수 있는 여러 요소들을 살펴보자.

5.11.1 register Spilling(레지스터 넘기기)

위에서 k X k의 unrolling을 살펴봤다. 이것의 아이디어는 다음과 같았다.

• k개의 연산에 k개의 서로 다른 register를 사용해서 dependency를 없애고 병렬적으로 실행시키자.

하지만 이 k가 이 현재 아키텍쳐의 register 수를 넘긴다면 어떻게 될까? 이에 대해 살펴볼 것이다.

• YMM register의 수는 총 16개 이므로, k가 16을 넘긴 20 X 20 unrolling이라면, register의 수를 넘겼다고 할 수 있다.
• 이 때, 10 X 10 unrolling보다 더 성능이 안나오는 모습을 볼 수 있다. 왜 이런 현상이 발생했는가?

register spilling

만약 parallel 하게 연산되는 곳에서 쓰이는 register의 수가 늘어나서 register의 수를 넘긴다면?

→ register가 아닌 memory에 저장하게 된다. runtime에 stack을 할당하는 방식

→ 따라서 성능이 더 느려지게 된다.

assembly code를 보면 다음과 같다.

10 X 10 unrolling

20 X 20 unrolling

20 X 20 unrolling에서 memory reference에 대한 code가 더해진 것을 알 수 있다. 따라서 성능이 더 안좋아졌다.

X86-64에서의 register spilling?

현재 processor의 경우 register 수가 많이 늘어났기 때문에 웬만큼 k를 늘리지 않는 이상 보통의 최적화에선 이런 spilling을 겪지는 않을 것이다.

5.11.2 Branch Prediction and Misprediction Penalties(분기예측과 예측 비용)

위에서 misprediction을 하게 되면 penalty가 존재하는 것을 언급했었다. 여기서는 구체적으로 어디서 penalty가 발생하는지를 살펴볼 예정이다.

• 여기서는 conditional jump에 대해서만 살펴볼 것이다(indirect jump 또는 procedure return은 관심 밖)

Speculative Execution

5.7장에서 봤듯이, prediction이 올바르다고 확정이 되어야 memory 또는 register에 결과를 저장할 수가 있다.

만약 올바르지 않다고 확정이 되면, 결과를 전부 폐기 & 올바른 위치(insturction 주소)에서 instruction fetch process를 재시작 해야 한다.

그럼 구체적으로 어디서 penalty가 발생했다고 볼 수 있는가?

instruction들은 pipeline을 다 채우면서 실행이 된다. 하지만 misprediction이 발생하게 되면, 새로운 instruction 부터 해서 비워진 pipeline을 다시 전부 채워야 하기 때문이다.

Conditional move

3.6.6장에서 봤듯이 최신 x86 processor들은 conditional move 명령어를 가지고 있다. GCC는 조건문이나 조건식들을 컴파일 할 때, 이 instruction을 생성할 수도 있다.

conditional move의 장점?

• 기존 : 조건에 따라 실행해야 하는 instruction이 달라진다.
• cmov : branch prediction이 필요가 없다. 왜냐하면, 조건식의 결과에 따라 알맞은(desired) 값이 move되기 때문이다.
  • 즉, misprediction에 대한 penalty가 없다.

어떻게 GCC가 conditional move를 생성하도록 프로그래머가 코드를 짤 수 있을까? → 정확한 원리가 있는 것은 아니다. 하지만 이 아래에서는 일반적으로 conditional move가 생성되는 몇가지 방식을 소개할 것이다.

Do Not Be Overly Concerned about Predictable Branches

직역하자면 branch prediction에 대해 막 그렇게 걱정하지 마라. 라는 뜻이 된다. 앞에선 penalty라고 언급을 해놓고 왜 이런 말을 하는가? → 걱정하지 않아도 될 어떤 패턴에 대해 살펴보려 한다.

loop-closing branches

루프를 탈출할지 말지에 대한 prediction은 전부 탈출하지 않는다고 predict한다.

• 실제로 루프는 탈출할 때 딱 한번 빼고는 전부 이 prediction이 정확하게 예측을 한다.

combine2의 bound checking

• 위 combine3에서는 combine2 코드에서의 get_vec_element 함수를 루프 밖으로 뺀 코드로 변형시켰었다. 이 get_vec_element 함수 안에선 접근하려는 index가 배열의 범위를 넘어갔는지 아닌지를 체크하는 bound check 조건문이 있었다.
• 하지만 combine3의 성능이 향상되지 않았던 것을 기억할 것이다.
• 이는 bound check의 경우 항상 success된다고 predict된다. 또한 combine2의 경우 항상 올바른 index를 넣었기 때문에 penalty가 하나도 발생하지 않았던 것이다.

Write Code Suitable for Implementation with Conditional Moves

위에서의 predictable branch 외에, unpredictable branch의 경우에 대해 살펴볼 것이다.

unpredictable branch의 경우, conditional move(conditional data trasfer) 코드가 생성되도록 하는 것이 성능에 큰 도움이 된다.

→ 이는 프로그래머가 직접 control 할 수 있는 부분이 아니다. 하지만 더 잘 생성되도록 하는 코드 style이 있고, 이를 살펴볼 것이다.

p.588 & p.599

imperative style

functional style

이 functional style이 cmov instruction을 더 잘 생성하도록 했다.