CPU cycle에 대한 고찰

 

 

What is retired instruction?

Modern processors execute much more instructions that the program flow needs. This is called a speculative execution. Instructions that were “proven” as indeed needed by the program execution flow are “retired”.

What is reference cycle?

Having a snippet A to run in 100 core clocks and a snippet B in 200 core clocks means that B is slower in general (it takes double the work), but not necessarily that B took more time than A since the units are different. That’s where the reference clock comes into play - it is uniform. If snippet A runs in 100 ref clocks and snippet B runs in 200 ref clocks then B really took more time than A. I did this experiment on Skylake i7-6000 process, which base frequency is 3.4 GHz. So, ref-cycles event counts cycles as if there were no frequency scaling. This also matches with clock multiplier for that processor, which can find in the specs (it’s equal to 34). Usually system clock has frequency of 100 MHz, and if we multiply it by clock multiplier we will receive the base frequency of the processor. 

What is mispredicted branch?

Modern CPUs try to predict the outcome of a branch instruction (taken or not taken). For example, when processor see a code like that:

dec eax jz .zero # eax is not 0 ... zero: # eax is 0

Instruction jz is a branch instruction and in order to increase performance modern CPU architectures try to predict the result of such branch. This is also called speculative execution. Processor will speculate that, for example, branch will not be taken and will execute the code that corresponds to the situation when eax is not 0. However, if the guess was wrong, this is called “branch misprediction” and CPU is required to undo all the speculative work that it has done lately. This may involve something between 10 and 20 clock cycles.

You can check how much branch mispredictions there were in the workload by using perf:

$ perf stat -e branches,branch-misses ls Performance counter stats for 'ls': 358209 branches 14026 branch-misses # 3,92% of all branches 0,009579852 seconds time elapsed or simply $ perf stat ls

More information like history, possible and real world implementations and more can be found on wikipedia and in Agner’s Fog microarchitecture manual, chapter 3 “Branch prediction”.

What is CPI & IPC?

Those two are derivative metrics that stand for:

• CPI - Cycles Per Instruction (how much cycles it took to execute one instruction on the average?)
• IPC - Instructions Per Cycle (how much instructions were retired per one cycle on the average?)

There are lots of other analysis that can be done based on those metrics. But in the nutshell, you want to have low CPI and high IPC.

Formulas:

IPC = INST_RETIRED.ANY / CPU_CLK_UNHALTED.THREAD CPI = 1 / IPC

Let’s look at the example:

$ perf stat -e cycles,instructions ls Performance counter stats for 'ls': 2369632 cycles 1725916 instructions # 0,73 insn per cycle 0,001014339 seconds time elapsed

Notice, perf tool automatically calculates IPC metric for us.

Process의 idle state와 CPU halt state의 연관관계

Process는 메모리로부터 읽어서 필요한 데이터를 task를 수행한다. 이때 Register, L1 cache, L2 cache, LLC(Last Level Cache), DRAM, Storage 순서로 해당 데이터가 있는지 여부를 확인하고, 필요한 데이터가 충족되면 cache를 업데이트하며 register로 데이터를 가지고 와서 task를 마무리 한다. 데이터가 메모리에 존재하

I/O 작업을 요청하고 필요한 데이터가 

 

Counting Stall Cycles on the Intel Sandy Bridge Processor - Posted by John D. McCalpin, Ph.D. on June 4, 2014

프로세서에서 "stall cycle"이 무엇인지는 명료하게 정의될 필요가 있다. 특히 매우 적은 수의 execution unit과 non-piprelined instruction이 있는 in-order 프로세서의 경우에는 직관적으로 받아들일 만큼 간단해야 한다. 최신의 out-of-order 프로세서의 경우 "stall"에 대한 정확하고 정량적인 정의를 도출하기도 어렵고 이러한 stall을 측정하는 방법을 도출하기는 훨씬 더 어려워진다.

아래는 Xeon E5-2680 (“Sandy Bridge EP”)를 사용하여 stall 에 대한 몇가지 테스트를 수행한 결과이다.

프로세서의 파이프라인 중에서 stall 이 계산되는 구간이 2개인 것을 발견했다.

 

RAT(Register Alias Table)에서 RS(Reservation Station)으로 보내지지않은 uop에 관련된 cycle을 집계하는 이벤트 2종류

RAT: register renaming unit

RS: source operand를 정의하는 instruction이 전달될 때까지 uop를 큐에 넣은 다음 execution port에 "ready" uop을 전달

1. 0x01c3010e: UOPS_ISSUED(Event 0x0E, Umask 0x01) CMASK, INVERT flag - Intel VTune에는 UOPS_ISSUED.STALL_CYCLES 라고 표현함
2. RESROUCE.STALLS.ANY(Event 0xA2, Umask: 0x01) - 일관적으로 UOPS_ISSUED.STALL_CYCLES 보다 1~3% 낮은 값이 나타남

RS에서 execution unit(aka port)로 전달한 no uops의 cycle을 집계하는 이벤트 2종류

1. 0x044304a3: CYCLE_ACTIVITY.CYCLES_NO_DISPATCH(Event 0xA3, Umask 0x04) CMASK=4
   • Intel VTune document에서 cmask 값을 찾음. SDM vol.3 에서는 찾을 수 없었음
2. 0x01c302b1: UOPS_DISPATCHED.STALL_CYCLES_CORE(Event 0xB1, Umask: 0x02)
   • This is very similar to an event used by VTune, but I use Umask 0x02 rather than 0x01. This will only make a difference on a system with HyperThreading enabled, and I don’t have any systems configured that way to test right now.
   • 두 이벤트의 차이는 매우 적음 (1PPM 만큼 적었다..)

Intel forum(link)에서 논의된 것처럼 처음 두 이벤트는 "stall-free" IPC가 4미만인 코드에서 stall을 overcount 할 가능성이 있다. 예를 들어 "stall-free" IPC가 1인 코드는 이 이벤트를 사용하여 75% stall cycle을 표시할 수 있으며, 이는 4개의 uops 집합이 RAT에서부터 RS로 매 4 cycle마다 전달되기 때문이다. (3 cycle은 idle 상태로 유지됨)

두 번째의 두 이벤트는 일반적으로 어떠한 종류이든 uop가 RS에서 execution unit으로 dispatch되는 경우에는 "non-stall" cycle로 간주하기 때문에 stall을 undercount 할 수 있다. 이는 이러한 uop가 이후에 input 데이터가 캐시에 없어서 거부되고 재시도되는 경우 또한 마찬가지로 발생할 수 있다. STREAM 벤치마크를 통해 테스트 해보았을 때 execution port로 dispatch된 총 uops의 수가 RAT에서 RS로 발행된 uops 수보다 20%-50% 더 높은 것을 확인하였다. (이것은 uop retry의 upper bound에 접근하도록 의도되지 않은 소수의 테스트 케이스를 기반으로 했기 때문에 retry의 worst case 비율은 훨씬 더 높을 수 있다고 생각한다. 12x를 초과하는 부동 소수점 명령어로 retry를 확인했을 때에도 worst-case upper bound 는 의도되지 않았다.)

불행히도 이러한 execution retry를 직접 계산할 방법이 없으며, reject 그리고 retry 된 모든 instruction에 대한 cycle 수를 확인할 방법도 없다.

 

추가로 instruction이 retired 되지 않은 cycle도 계산할 수 있다. 하지만 프로세서는 cycle당 최소 4개의 instruction를 retire할 수 있으므로, non-stalled IPC가 4개 미만인 경우 instruction retirement의 burstiness로 인해 매 cycle마다 실행하는 일부 instruction이 있더라도 non-zero stall cycle을 카운트하는 결과가 발생할 수 있다는 이론적인 문제가 있다.

지금까지 이 논의 중 어느 것도 stall의 원인을 명시적으로 다루지 못했다. Intel은 이 문제에 대한 통찰력을 제공하는 매우 흥미로운 performance counter event를 제공한다. CYCLE_ACTIVITY(Event 0xA3)에는 "CYCLES_L2_PENDING"(0x01) 및 "CYCLES_NO_DISPATCH"(0x04)에 대한 Umask가 있다. SDM Vol 3은 이 unit을 프로그래밍하는 방법을 이해하기에 적절하지 않지만 다행히 Intel의 VTune이 예제를 제공한다.

VTune에서 이벤트 CYCLE_ACTIVITY.STALL_CYCLES_L2_PENDING은 두 Umask를 결합하고 CMASK 값 5이 적용된 0x054305a3을 인코딩 값으로 이 이벤트를 생성된다. (이 경우 CMASK 값이 5여야 하는 이유가 전혀 명확하지 않지만, 결합된 Umask 값이 일반적으로 결합된 Umask에 대해 가정되는 논리적 OR이 아니라 논리적 AND로 처리되기 때문에 이벤트는 분명히 비표준이다.)

Stall cycle의 실제 수가 약 90%여야 하는 STREAM 벤치마크를 사용한 실험에서 CYCLE_ACTIVITY.STALL_CYCLES_L2_PENDING에 의해 생성된 값은 CYCLE_ACTIVITY.CYCLES_NO_DISPATCH (L2_PENDING qualifier 제외) 값의 30%에서 93% 사이로 다양하게 나타났다. streaming(non-temporal) store를 사용한 테스트에서 낮은 값이 나타났고 ordinary(allocating) store를 사용한 경우에는 높은 값이 나타났다.

 

이 패턴은 이 이벤트가 "L2_PENDING" 범주의 store misses(RFO's)를 계산하기 위해 만들어졌다고 보이지만 memory stall이 streaming store로 인한 경우에는 memory stall cycle 식별이 되지 않는다.

 

AVX 코드의 경우 Event 0xA2, Umask 0x08: RESOURCE_STALLS.SB(저장 버퍼가 가득 찼기 때문에 RAT에서 RS까지 문제가 없는 주기)는 총 주기의 70%-91%를 보여줍니다. 전체 저장소 버퍼로 인해 문제가 중단되었습니다. 따라서 CYCLE_ACTIVITY.STALL_CYCLES_L2_PENDING 및 RESOURCE_STALLS.SB의 최대값을 보면 저장소를 할당하거나 저장소를 스트리밍하는 코드의 메모리로 인한 지연을 잘 알 수 있습니다.
스트리밍 저장소가 있는 SSE 코드의 경우 RESOURCE_STALLS.SB 이벤트는 총 주기의 20%-37%에 불과합니다. CYCLE_ACTIVITY.STALL_CYCLES_L2_PENDING을 사용하여 이 숫자의 지연 비율을 지연 비율에 추가하더라도 총 주기의 45% – 59%만 얻게 되므로 모든 지연을 식별할 수 있는 이벤트 세트가 아직 없습니다. 주기는 실제로 메모리 스톨입니다. (이러한 방식으로 스톨 사이클을 추가하는 것은 일반적으로 좋은 생각이 아닙니다. 두 가지 이유로 사이클이 스톨될 수 있기 때문입니다. 여기서는 두 스톨 사이클을 모두 설명하기에는 너무 비중이 적어서 두 개만 추가합니다.)

Summary: 메모리 관련 stall cycle을 식별하는데 도움이 되는 리소스가 있지만 원하는 만큼 정확하지는 않다. 이러한 카운터는 실행 시간 중 memory stall이 발생하는 시점을 대부분의 경우 식별할 수 있으며 이것이 실제로 성능 분석가가 찾고 있는 것이다. 문제가 식별되면 관심있는 코드 부분의 실행 시간을 기반으로 튜닝 작업을 하며 hardware performance counter는 (기껏해야) 자문 역할 만을 할 수 있다.

 

https://techdecoded.intel.io/resources/understanding-the-instruction-pipeline/#gs.9qqini

 

 

어플리케이션의 성능을 profiling하기 위해서 CPU가 STALL 되어 있는 상태가 얼마나 지속되는지를 파악하는 것이 중요하다. 대표적으로 PMU에서 CYCLE_ACTIVITY.CYCLES_NO_EXECUTE 라는 mnemonic을 가진 이벤트가 이를 나타내준다. 또한 PMU에서는 CPU가 STALL된 원인을 세부적으로 나누어 집계해주는데 이러한 정보를 나타내는 mnemonic은 CYCLE_ACTIVITY.STALLS_L1D_PENDING, ...STALLS_L2_PENDING, and STALLS_LDM_PENDING 와 같은 이벤트들이 있다.

하지만 perf를 통해서 위의 metric들을 counting 해보면 CYCLE_ACTIVITY.CYCLES_NO_EXECUTE의 값이 세분화된 metric들의 합보다 더 작게 나타났다. 이를 이해하기 위해서 CPU가 STALL 되는 상태를 정리할 필요성이 인식되었다.

검색 결과 Intel community에 관련된 질문(Accounting for CYCLE_ACTIVITY.CYCLES_NO_EXECUTE)이 게재되어 있는 것을 확인하였고, 본 포스트는 해당 내용을 정리하기 위해 작성하였다.

 

McCalpinJohn 의 답변 (Intel community에서 performance counter 관련한 거의 모든 질문에서 이 아저씨의 답변을 볼 수 있다.. 되게 멋있는 분인것 같다.)

 

 

이 이벤트(CYCLE_ACTIVITY.CYCLES_NO_EXECUTE)에 대한 설명 중 일부는 지나치게 단순화되어 혼동을 줄 수 있습니다.
1. 프로세서는 파이프라인의 여러 위치에서 "stall" 될 수 있으므로 측정 대상을 명확히 하는 것이 중요합니다. 여기에 언급된 performance counter event는 모두 hardware event인 0xA3 "CYCLE_ACTIVITY"를 기반으로 합니다. SW Developer's Guide의 Volume 3에 있는 이 이벤트에 대한 설명은 파이프라인의 어느 부분이 모니터링되는지 지정하지 않지만 "nearby" 이벤트 0xA1 및 0xA6을 보면 이 이벤트가 RS(Reservation Station)부터 execution port 까지의 uops "dispatch"를 측정하고 있음을 분명히 알 수 있습니다(이는 Intel Optimization Reference Manual, document 248966-030의 Figure 2-1에 있는 "Scheduler" 블록에 해당함). CPU 파이프라인의 이 시점에서 "stall" cycle은 8개의 execution port 중 어떤 곳으로든 전달된 no uop를 의미한다.
2. Stall은 동시에 여러 원인으로 인해 발생할 수 있기 때문에 일반적으로 dispatch stall에 대해 "blame"을 명확하게 할당하는 것은 불가능합니다. 따라서 이 이벤트가 하는 일은 다릅니다. 많은 지연이 메모리 대기 시간을 허용하지 않아 발생하므로 지연과 (요구) 로드 누락이 모두 있는 cycle을 찾는 것이 도움이 됩니다. 이는 정확하지는 않지만 도움이 됩니다.

디스패치 지연의 다른 원인은 다음과 같습니다.
- 파이프라인 초기의 병목 현상으로 인해 예약 스테이션에 uops가 없습니다(명령 가져오기/디코딩/이름 바꾸기). 인텔은 이것을 "front-end stall"이라고 부릅니다. 이벤트 0xA6 "EXE_ACTIVITY"는 특히 RS가 비어 있지 않은 cycle을 제외하지만 이 추가 논리 비트는 이벤트 0xA3에 적용되지 않는 것으로 보입니다.
- 대기 시간이 긴 지침으로 인해 발행할 수 있는 예약 스테이션의 독립적인 uop가 없습니다. 예를 들어 코어가 FMA instruction의 종속 시퀀스를 계산하는 경우 처리량은 5사이클당 하나의 FMA 명령어에 불과하며 4 cycle의 dispatch stall이 남습니다.
- Intel Optimization Reference Manual의 부록 B에 논의된 다른 많은 예가 있으며 이들 중 많은 예에서는 demand load miss pending이 필요하지 않습니다.

요약하자면:
CYCLE_ACTIVITY.CYCLES_NO_EXECUTE는 원인에 관계없이 execution port에 dispatch된 모든 no uop에 대한 cycle을 계산합니다.
CYCLE_ACTIVITY.STALLS_*_PENDING은 캐시 계층의 L1, L2 또는 L3 수준에서 demand load miss pending이 또한 있는 경우에만 이러한 stall cycle를 계산합니다.

 

기타 주의사항:
프로세서 코어는 순서가 잘못된 명령을 실행할 수 있으므로 L2 캐시에 적중하는 L1 누락의 대기 시간을 숨길 수 있는 경우가 많습니다. 프로세서가 L2 미스 또는 L3 미스의 대기 시간을 숨길 가능성은 적습니다. 따라서 STALLS_L2_PENDING 및 STALLS_L3_PENDING은 STALLS_L1D_PENDING 이벤트보다 캐시 미스로 인한 *스톨과 관련될 가능성이 더 높습니다.
일부 명령은 데이터가 반환되기를 기다리는 동안 여러 번 디스패치되는 것처럼 보입니다. (Sandy Bridge와 Ivy Bridge의 부동 소수점 카운터가 이 범주에 속합니다.) 이런 일이 발생하면 이러한 이벤트로 인해 실제 지연 주기를 *놓칠 수 있습니다. -- uop가 임의의 포트에 전달되더라도 증가되지 않습니다. 그 uop가 거부되고 다시 시도되더라도. 대부분의 사람들은 이것을 "스톨"이라고 부르지만 하드웨어는 그렇게 계산하지 않습니다. 나는 이것을 Haswell에서 확인하지 않았지만 조심해야 할 사항입니다.

 

참조:

• https://easyperf.net/blog/2018/03/21/port-contention
• https://community.intel.com/t5/Analyzers/Accounting-for-CYCLE-ACTIVITY-CYCLES-NO-EXECUTE/td-p/998084
• https://community.intel.com/t5/Software-Tuning-Performance/Performance-counters-for-measuring-L2-and-L3-Hit-ratios/td-p/1132698