Cachegrind - cache, branch prediction 측정/분석/프로파일링

프로그램을 최적화하다가 if문 순서에 따른 성능이 이상하게 나와서 branch hazard와 관련한 성능 측정이 필요한 일이 생겼다. 구글링 결과 Valgrind를 이용하면 측정할 수 있을 것 같다.

 

Valgrind

Valgrind는 동적 분석 도구를 구축하기 위한 프레임 워크이다. 메모리 관리, 스레딩 버그 등등을 감지하고 프로그램을 자세하게 프로파일링 할 수 있는 도구들이 있다.

 

그중에서도 CacheGrind 기능을 이용하면 캐시 미스(cache miss), branch mis-prediction 등 cpu 단에서의 오버헤드들을 관찰할 수 있고, 성능 향상에 이용할 수 있다.

 

Valgrind는 오픈소스로 GNU Genral Public License 2에 따라 무료로 이용할 수 있다.

 

사전 지식

일반적으로 프로세서가 메모리 시스템에 데이터나 명령어를 요청할 때 L1 캐시를 찾고, 없을 경우 L2, L3 혹은 그 이상까지 찾게 된다. CPU 종류에 따라 최대 레벨 Cache가 다른데, 가장 마지막 캐시를 Last Level(LL) 캐시라고 한다. (보통 2나 3이다.) 속도는 L1이 가장 빠르고 용량은 적다. 레벨이 올라갈수록 느리고, 커진다.

 

어쨌든, 프로세서에서 데이터/명령어를 요청할 때 캐시에 데이터가 미리 준비되어 있다면 Hit이 발생하고, 없다면 Miss가 발생하는데, Miss가 발생하면 상위 Level 혹은 RAM까지 올라가 데이터를 가져와야 하기 때문에 페널티가 발생한다.

L1 Cache Miss penalty = 10 cycle

LL Cache Miss penalty = 300 cycle

 

또한, CPU에서는 Branch가 발생할 때, 미리 분기할 곳을 예측해서 연산을 하는데, 이때 잘못된 위치를 예측해서 mispredicted branch가 발생하기도 한다.

Mispredicted branch penalty = 10~30 cycle

* 페널티는 고정된 값이 아니라 통상적인 수치이다.

 

약어 설명

CacheGrind에서는 약어로 결과를 출력을 한다. 약어는 다음과 같다.

Ir	명령어 Read 캐시
Iw	명령어를 쓸 일은 없으므로 Iw는 없음
Dr	데이터 Read 캐시
Dw	데이터 Write 캐시
Bc	조건 분기(Conditional branch)
Bi	간접분기(Indirect branch)
I1mr	명령어 Read시 Level 1 I-Cache miss
ILmr	명령어 Read시 Last Level Cache miss
D1mr	데이터 Read시 Level 1 D-Cache miss
DLmr	데이터 Read시 Last Level 1 Cache miss
D1mw	데이터 Write시 Level 1 D-Cache miss
DLmw	데이터 Write시 Last Level Cache miss
Bcm	잘못 예측된 곳으로 조건(conditional) 분기
Bim	잘못 예측된 곳으로 간접(Indirect) 분기

* 보통 I-Cache(명령어 캐시)와 D-Cache(데이터 캐시)는 Level 1에서만 나누어짐

* Level 1 Cache = L1 cache

 

설치

sudo apt-get install valgrind

위 스크립트로 간단하게 설치할 수 있다.

 

사용법

Profile Cache Miss 

기본적인 사용법은 다음과 같다.

valgrind --tool=cachegrind <측정프로그램>

내가 만든 간단한 프로그램으로 실행해보자.

 

실행결과

각각을 설명해보자면, 우선 맨 좌측의 숫자는 실행했을 때의 프로세스 번호(PID)이고, 

 

이 부분은 명령어를 읽을 때의 Cache miss 발생량과 발생률이다.

 

이 부분은 데이터를 읽고 쓸 때의 Cache miss 발생량과 발생률이다.

 

이 부분은 데이터/명령어를 읽고 쓸 때의 Last-Level Cache miss 발생량과 발생률이다.

이 부분이 가장 크리티컬 하므로 rate가 높다면 최우선으로 원인을 분석해볼 필요가 있다.

 

Profile Branch misprediction

분기 예측 관련 프로파일링을 하려면, 측정 시 --branch-sim=yes 옵션을 추가해주면 된다.

* 옵션 추가 평균 25% 정도 느려진다고 한다.

valgrind --tool=cachegrind --branch-sim=yes <측정프로그램>

 

결과를 살펴보자.

실행 결과

위와 같이 분기 예측 실패량과 실패율 추가되어 출력된다.

 

결과를 파일로 저장하려면 다음과 같은 옵션을 추가하면 된다.

valgrind --tool=cachegrind --branch-sim=yes --cachegrind-out-file=<결과파일>  <측정프로그램>

 

측정 결과는 과 파일에 저장되고, cg_annotate를 이용해서 볼 수 있다.

cg_annotate <결과파일> <측정프로그램>

 

실행 결과

cg_annotate를 이용하면 위와 같이 결과를 함수 단위로 볼 수 있다.

* 함수명이???로 뜨는 것은 대부분 컴파일 시 -g 옵션을 추가하면 없어진다.

 

만약 작성 코드 단위로 보고 싶다면 컴파일 시 -g 옵션을 추가하고 cg_annotate에 --auto=yes 옵션을 추가해보자.

cg_annotate --auto=yes <결과파일> <측정프로그램>

실행 결과

위와 같은 결과가 추가로 측정된다.

어떤 연산, 어떤 분기문에서 miss/misprediction 이 많이 발생하는지 확인할 수 있다.

 

마치며

간단히 if문 순서 최적화를 알아보다가 오히려 정반대의 상황이 나와서 cache/branch 분석까지 오게 되었다. 생각 외로 간단히 분석할 수 있고 상세한 정보가 많이 들어 있다. 종종 CacheGrind로 분석해서 최적화를 시도해봐야겠다.

 

Reference

• valgrind.org/docs/manual/cg-manual.html