Oct 2, 2015 課程紀錄

[2015q3 Week #3] [編輯共筆內容]

課程公告

Git

ARM 與 MIPS

ARM Processor Architecture

ARMv8 中文翻譯可見此:http://wiki.csie.ncku.edu.tw/embedded/ARMv8

A64 is a new 32-bit fixed length instruction set to support the AArch64  execution state. The following is a summary of the A64 ISA features.  

ARM, generically known as A32, is a fixed-length (32-bit) instruction  set. It is the base 32-bit ISA used in the ARMv4T, ARMv5TEJ and  ARMv6 architectures.  In these architectures it is used in applications  requiring high performance, or for handling hardware exceptions such as  interrupts and processor start-up.

The ARM ISA is also supported in the Cortex™-A and Cortex-R  profiles of the Cortex architecture for performance critical  applications, and for legacy code.  Most of its functionality is  subsumed into the Thumb instruction set with the introduction of Thumb-2  technology. Thumb (T32) benefits from improved code density. 

ARM instructions are 32-bits wide, and are aligned on 4-byte boundaries. 

Most ARM instructions can be "conditionalized" to only execute when  previous instructions have set a particular condition code. This means  that instructions only have their normal effect on the programmers’  model operation, memory and coprocessors if the N, Z, C and V flags in  the Application Program Status Register satisfy a condition specified in  the instruction. If the flags do not satisfy this condition, the  instruction acts as a NOP, that is, execution advances to the next  instruction as normal, including any relevant checks for exceptions  being taken, but has no other effect.  This conditionalization of  instructions allows small sections of if- and while-statements to be  encoded without the use of branch instructions.  

==>

A64’s Key differences from A32 are: 

==> 64-bit data model

ARM Architecture

ARM 是在全球中被廣泛使用的 processor cores,像是 PDA、手機、多媒體播放器、數位電視、相機等等。ARM processors 有許多 family,如 ARM7、 ARM9、 ARM11、ARMv7,同一個 family 的設計使用相似的設計原則及同一個common instruction set。他的設計哲學是用有限的硬體( 有限的 memory 和 physical size restrictions )資源達到 high code density,除此之外,還

ARM 的命名方式 - ARMxyzTDMIEJFS

(在 ARM Cortex-A/R/M之前的 "ARM Classic")

ps : TDMI 這四項基本功能成了任何新產品的標準配備,於是就不再使用這4個後綴。但是新的後綴不斷加入,包括定義存儲器界面的,定義高速快取的,以及定義"緊耦合存儲器(TCM)"的,於是形成了新一套命名法,這套命名法一直使用至今。比如ARM1176JZF-S,它實際上預設就支持TDMI功能,除此之外還支持JZF。

這套命名機制在 ARM Cortex-A/R/M 之後,徹底棄置。以 MMU 來說,ARM Cortex-A 系列都有 MMU,而 Cortex-M0/M0+/M3/M4 均缺乏 MMU,僅有選擇性的 MPU。Cortex-M7 開始提供 cache 和 TCM

ARM Classic

(在 ARM Cortex 系列出現之前)

ARM 採用 RISC

xARM architecture 從 Berkeley RISC design合併了幾個特點,但也有些並無採用。

  • Features used
  • Features rejected
  • ARM 的架構

    註: MAC = Multiply–accumulate operation

    ARM Register

    以下是ARM的 register,在User/System Mode時,可以使用r0~r15,其中r13為stack pointer,r14為link register,r15為program counter

    Current Program Status Register(CPSR) : 在user-level時,用於存取condition code bits

    溢位複習:

  • 1、輸入的數是無符號整數,我們通過觀察C判斷是否溢出
  • a) C=1

    i)如果是加法操作,結果不正確,結果溢出

    ii)如果是減法操作,結果正確,結果未溢出

    b) C=0

    i)如果是加法操作,結果正確,結果未溢出

    ii)如果是減法操作,結果不正確,結果未溢出。在這種情況下,結果是負數。然而,在無符號整數世界裡,負數不存在,我們認識這樣的操作是非法的。當然,如果認為答案是以有符號整數補碼的形式出現,則結果正確。

  • 2、輸入的數是有符號整數,我們通過觀察V判斷是否溢出
  • a) V=1,結果不正確,結果溢出

    b) V=0,結果正確,結果未溢出

    通用暫存器有6種 data types ( signed / unsigned) ( word /Half word/ byte),而在所有ARM的運算為32-bit,比較小的資料型態只有在資料傳送的運算中被支援。

    Program Counter ( PC ) 是儲存要被執行的位址,而所有指令皆為 32-bit wide 且 word aligned

    在 ARM 架構中支援了 ( 7+1  )種模式,如圖:

    Instruction sets

    裡面有 ARM / Thumb / Jazelle ,下圖為簡單介紹:

    (實際上 ARM 的 extension 遠比以下列出的多)

    Pipeline

    在執行時, PC 是 8 bytes ahead,也就是說 Pipeline 準備要做 Execute級( 位址是 0x8000)時,要讀取的下一個位置是 PC + 8 的位置(從範例中可清楚看見,即 DCD 指令的位址 0x8008)

    他有以下幾點特點:

    Interrupts

    當發生 exception 或 interrupt 時,會觸發 Interrupt handler,此時,他會尋找 vector table 去做中斷時所要處理的 routine.

    下圖為中斷定義及其跳躍的起始位址:

    在 user-mode program 中,可以看到 15 個 32-bit general purpose registers (R0-R14), program counter (PC) 及 CPSR,在指令集中有定義一些指令可以改變 state。

    在開始深入探討前,先來看看他的 Memory system吧~

    Memory system

    剛剛有提到 Little Endian,他其實是 Byte ordering 的其中一種方式,endian指的是當物理上的最小單元比邏輯上的最小單元還要更小時,邏輯單元對映到物理單元的排佈關係。舉例來說:

    如果你在文件上看到一個雙字組的data,Ex: long MyData=0x12345678,要寫到從0x0000開始的記憶體位址時。

    1. 如果是Big Endian的系統:
    1. 如果是Little Endian的系統:

    比較的結果就是這樣:

    big-endian little-endian
    0x0000 0x12 0x78
    0x0001 0x34 0x56
    0x0002 0x56 0x34
    0x0003 0x78 0x12

    Features of ARM instruction set

    Instruction set

    可分成三大項:

    Data processing

    資料處理指令包含對資料做 移動、算數、邏輯、比較、乘法 的指令,且大部分的 data processing instructions 可以對一個 operand 做 shift,如圖:

  • Arithmetic operations:
  • Bit-wise logical operations:
  • Register movement operations:
  • Comparison operations:
  • 只設定在CPSR的 condition code bits(N, Z, C and V)

  • Immediate operands:
  • Reference: https://sourceware.org/ml/binutils/2014-02/msg00157.html

    Shifted register operands:

    舉例來說:

    位移 (shift) 主要分兩種:

    簡單來說,邏輯移位無論左移右移,一律都是把多出來的位數填零。算術運算左移跟邏輯移位一樣填零,右移需要考慮到 singed 的屬性,假若最高位是 1,則填補1,反之若最高位是 0,則填補0。

    範例:

    注意: ARM Toolchain (包含 arm-none-eabi/linux-gnueabi) 預設將 "int" 視為 "unsigned"

     

  • Condition flags
  • If S is specified, these instructions update the condition code bits 

    Ex:

  • Multiplies:
  • Encoding data processing instructions
  • 這裡可以看第 25-bit(#) 決定 operand 2 是以何種格式,如果 # = 1 就如圖下只有 1 種對應格式,如果 # = 0就需要再比對位置在第四個bit ( 決定2種格式 )

    Flow Control 

    決定哪一條指令將被執行

    B branch pc = label pc-relative offset within 32MB
    BL branch with link pc = label
    BX branch exchange pc = Rm & 0xfffffffe, T = Rm & 1
    BLX branch exchange with link pc = label, T = 1

    Mnemonic Name Condition flags
    EQ equal Z
    NE not equal z
    CS HS carry set/unsigned higher or the same C
    CC LO carry clear/unsigned lower c
    MI minus/negative N
    PL plus/positive or zero n
    VS overflow V
    VC no overflow v
    HI unsigned higer zC
    LS unsigned lower or same Z or c
    GE signed greater than or equal NV or nv
    LT signed less than Nv or nV
    GT signed greater than NzV or nzv
    LE signed less than or equal Z or Nv or nV
    AL always (unconditional) ingnored

    Branch Interpretation Normal uses
    B BAL Unconditional Always take this branch
    BEQ Equal Comparison equal or zero result
    BNE Not equal Comparison not eaual or non-zero result
    BPL Plus Result positive or zero
    BMI Minus Result minus or zero
    BLO Lower Unsigned comparison gave lower
    BHS or the same Unsigned comparison gave higher or same
    BVC Overflow clear Signed integer operation; no overflow occured
    BVS Overflow set Signed integer operation; overflow occured
    BGT Greater than Signed integer comparison gave greater than
    BGE Greater than or equal Signed integer comparison gave greater than or equal
    BLT Less than Signed integer comparison gave less than
    BLE Less or equal Signed integer comparison gave less than or equal
    BHI Higher Unsigned comparison gave higher
    BLS Lower or the same Unsigned comparison gave lower or same

    Data transfer instructions

    data processing 的 mov 指令是暫存器間互相傳送資料,而 data transfer instructions 是暫存器與 memory 間互相傳遞資料,而 data transfer instructions 有三種基本形式

    1. Single register load/store ,也就是對單一暫存器做 load/store
    2. Multiple register load/store,可以對多個暫存器做 load/store
    3. Single register swap: SWP(B), atomic instruction for semaphore
  • Syntax:
  • LDR load word into a register Rd <-- mem32[address]
    STR save byte or word from a register Rd --> mem32[address]
    LDRB load byte into a register Rd <-- mem8[address]
    STRB save byte from a register Rd --> mem8[address]
    LDRH load halfword into a register Rd <-- mem16[address]
    STRH save halfword into a register Rd --> mem16[address]
    LDRSB load signed byte into a register Rd <-- SignExtend
    LDRSH load signed halfword into a register Rd <-- SignExtend

    ps. 沒有 STRSB/STRSH 是因為 STRB/STRH 儲存 signed/unsigned 到記憶體位置( 存進去就不管他是有號無號,讀出來才要判別)

    Memory 定址可以透過暫存器和 offset,例:

    他有三種 Addressing modes

    Index method Data Base address register Example
    Preindex with writeback mem[ base + offset ] base + offset LDR r0,[r1, #4]!
    Preindex mem[ base + offset ] not updated LDR r0, [r1, #4]
    Postindex mem[ base ] base + offset LDR r0, [r1], #4
  • 圖解 Addressing modes
  • 以上是有 offset 的三種 addressing modes,接下來來看看 Register 的 addressing modes

    ps.有一個 pseudo instruction ADR 可以 load and address 到一個暫存器裡

  • Multiple register load/store
  • 意思就是一次可以存取很多個暫存器的值

    簡單的範例:

  • Syntax:
  • 用上表有點難看出變化,以下用圖來表示

    其中 R1 = 10, R2 = 20, R3 = 30,更新後的 R0 = 0x01c

    從這裡可以看到依序從最低位開始存,存完才將R0 + 4 ,最後,當存完R3的值之後,R0更新成 0x01c,因為上面指令有 `!` ,所以將最後值存在 R0中

    ps.: 如果沒有`!` ,則最後R0 = 0x010,後面的範例也是如此

    其中 R1 = 20, R2 = 30, R3 = 40,更新後的 R0 = 0x01c

    從這裡可以看到先將R0 + 4 後才開始存,然後依序往上加 ,最後,當R0更新成 0x01c也存完R3的值之後,因為上面指令有 `!` ,所以將最後值存在 R0中

    其中 R1 = 40, R2 = 50, R3 = 60,更新後的 R0 = 0x018

    從這裡可以看到依序從最位開始存,存完才將R0 - 4 ,最後,當存完R1的值之後,R0更新成 0x018,因為上面指令有 `!` ,所以將最後值存在 R0中

    其中 R1 = 30, R2 = 40, R3 = 50,更新後的 R0 = 0x018

    從這裡可以看到先將R0 - 4 後才開始存 ,最後,當R0更新成 0x018也存完R1的值之後,因為上面指令有 `!` ,所以將最後值存在 R0中

  • Multiple load/store registers 的應用
  • mode POP =LDM PUSH =STM
    Full ascending (FA) LDMFA LDMDA STMFA STMIB
    Full descending (FD) LDMFD LDMIA STMFD STMDB
    Empty ascending (EA) LDMEA LDMDB STMEA STMIA
    Empty descending (ED) LDMED LDMIB STMED STMDA

    Linux 效能分析工具: Perf

    簡介

    Perf 全名是 Performance Event,是在 Linux 2.6.31 以後內建的系統效能分析工具,它隨著核心一併釋出。藉由 perf,應用程式可以利用 PMU (Performance Monitoring Unit), tracepoint 和核心內部的特殊計數器 (counter) 來進行統計,另外還能同時分析運行中的核心程式碼,從而更全面了解應用程式中的效能瓶頸。

    相較於 OProfileGProf ,perf 的優勢在於與 Linux Kernel 緊密結合,並可受益於最先納入核心的新特徵。perf 基本原理是對目標進行取樣,紀錄特定的條件下所偵測的事件Branch Prediction是否發生以及發生的次數。例如根據 tick 中斷進行取樣,即在 tick 中斷內觸發取樣點,在取樣點裡判斷行程 (process) 當時的 context。假如一個行程 90% 的時間都花費在函式 foo() 上,那麼 90% 的取樣點都應該落在函式 foo() 的上下文中。

    Perf 可取樣的事件非常多,可以分析 Hardware event,如 cpu-cycles、instructions 、cache-misses、branch-misses ...等等。可以分析 Software event,如 page-faults、context-switches ...等等,另外一種就是 Tracepoint event。知道了 cpu-cycles、instructions 我們可以了解 Instruction per cycle 是多少,進而判斷程式碼有沒有好好利用 CPU,cache-misses 可以曉得是否有善用 Locality of reference ,branch-misses 多了是否導致嚴重的 pipeline hazard ?另外 Perf 還可以對函式進行採樣,了解效能卡在哪邊。

    安裝

    首先利用以下指令查看目前的 Kernel config 有沒有啟用 Perf。如果 PC 上是裝一般 Linux distro,預設值應該都有開啟。

    如果自己編譯核心可以參照這篇文章啟用 perf。

    參考的環境是 `Ubuntu 14.04`,kernel 版本 `3.16.0`。有兩種方法可以安裝

    1.  前面講到,perf 是 Linux 內建支持的效能優化工具,在`2.6.31`版本之後,我們可以直接進到`/usr/src/<kernel version>/tools/perf`,然後`$ make` 和 `$ make install`來安裝 。

    2. 使用`apt-get install`進行安裝。 

    `$ sudo apt-get install linux-tools-common`

    接著輸入`perf list`或`perf top`檢查一下 perf 可不可以使用。

    如果出現以下的訊息,表示還漏了些東西。(底下的 Kernel 版本可能和你不一樣,根據指示安裝起來即可。不放心的話可以使用`$ uname -r`確認。)

    `$ sudo apt-get install linux-tools-3.16.0-50-generic linux-cloud-tools-3.16.0-50-generic`

    3. 到這裡 perf 的安裝就完成了。不過這裡我再稍微補充一下,如果你不是切換到 root 的情況下輸入`$ perf top`,其實會出現以下錯誤畫面。

    `kernel.perf_event_paranoid`是用來決定你在沒有 root 權限下 (Normal User) 使用 perf 時,你可以取得哪些 event data。預設值是`kernel.perf_event_paranoid=1`,你可以輸入`$ cat /proc/sys/kernel/perf_event_paranoid`來查看權限值。一共有四種權限值

    1. `2` : 不允許任何量測。但部份用來查看或分析已存在的紀錄的指令仍可使用,如 perf ls、perf report、perf timechart、 perf trace。
    2. `1` : 不允許 CPU events data。但可以使用 perf stat、perf record 並取得 Kernel profiling data。
    3. `0` : 不允許 raw tracepoint access。但可以使用 perf stat、perf record 並取得 CPU events data。
    4. `-1`: 權限全開。

    最後如果要檢測 cache miss event ,需要先取消 kernel pointer 的禁用。

    `$ sudo sh -c " echo 0 > /proc/sys/kernel/kptr_restrict" `

    先來個範例暖身吧!

    一開始,我們先使用第一次作業 「計算圓周率」 的程式來體會一下 perf 使用。

    [perf_top_example.c]

    執行上述程式後,根據 pid 輸入 `perf top -p $pid`。應該會得到類似下面的結果:

    預設的 performance event 是 「cycles」,所以這條指令可以分析出消耗 CPU 週期最多的部份,結果顯示函式 compute_pi_baseline() 佔了近 99.9%,跟預期一樣,此函式是程式中的「熱點」!有了一些感覺後,後面會詳細一點介紹 perf 用法。

    背景知識

    以下節錄上海交大通信與電子工程系的劉明寫的文章: 

    (本課程斟酌修改詞彙,`==>` 開頭表示補充)

  • 背景知識
  • 有些背景知識是分析性能問題時需要瞭解的。比如硬件 cache;再比如作業系統核心。應用程式的行為細節往往是和這些東西互相牽扯的,這些底層的東西會以意想不到的方式影響應用程式的性能,比如某些程式無法充分利用 cache,從而導致性能下降。比如不必要地呼叫過多的系統呼叫,造成頻繁的核心 / 使用者層級的切換 ...等等。這裡只是為本文的後續內容做些概述,關於效能調校還有很多東西。

  • 效能相關的處理器硬體特性,PMU 簡介
  • 當演算法已趨於最佳化,程式碼不斷精簡,人們調到最後,便需要斤斤計較了。cache、pipeline 等平時不大注意的東西也必須精打細算了。

  • 硬體特性之 cache
  • 記憶體存取很快,但仍無法和處理器的指令執行速度相提並論。為了從記憶體中讀取指令 (instruction) 和資料 (data),處理器需要等待,用處理器的時間來衡量,這種等待非常漫長。cache 是一種 SRAM,它的存取速率非常快,與處理器處理速度較為接近。因此將常用的資料保存在 cache 中,處理器便無須等待,從而提高效能。cache 的尺寸一般都很小,充分利用 cache 是軟體效能改善過程中,非常重要的部分。

  • 硬體特性之 pipeline, superscalar, out-of-order execution
  • 提昇效能最有效的方式之一就是平行 (parallelism)。處理器在設計時也儘可能地平行,比如 pipeline, superscalar, out-of-execution。

    處理器處理一條指令需要分多個步驟完成,比如 fetch 指令,然後完成運算,最後將計算結果輸出到匯流排 (bus) 上。在處理器內部,這可以看作一個三級 pipeline,如下圖處理器 pipeline 所示:

    指令從左邊進入處理器,上圖中的 pipeline 有三級,一個時鐘週期內可以同時處理三條指令,分別被 pipeline 的不同部分處理。

    superscalar 指一個時鐘週期觸發 (issue) 多條指令的 pipeline機器架構,比如 Intel 的 Pentium 處理器,內部有兩個執行單元,在一個時鐘週期內允許執行兩條指令。

    ==> 這樣稱為 dual-issue,可想像為一個 packet 裡同時有兩組 pipelined 的 instruction

    ==> 比方說,Cortex-A5 和 Cortex-A8 一樣採用 ARMv7-A 指令集,但是 Cortex-A5 是 Cortex-A8/A9 的精簡版,有以下差異:

    此外,在處理器內部,不同指令所需要的執行時間和時鐘週期是不同的,如果嚴格按照程序的執行順序執行,那麼就無法充分利用處理器的 pipeline。因此指令有可能被亂序執行 (out-of-order execution)。

    上述三種平行技術對所執行的指令有一個基本要求,即相鄰的指令相互沒有依賴關係。假如某條指令需要依賴前面一條指令的執行結果數據,那麼 pipeline 便失去作用,因為第二條指令必須等待第一條指令完成。因此好的軟體必須儘量避免產生這種程式碼。

  • 硬體特性之 branch prediction
  • branch prediction 指令對軟體效能影響較大。尤其是當處理器採用流水線設計之後,假設 pipeline 有三級,且目前進入 pipeline 的第一道指令為分支 (branch) 指令。假設處理器順序讀取指令,那麼如果分支的結果是跳躍到其他指令,那麼被處理器 pipeline 所 fetch 的後續兩條指令勢必被棄置 (來不及執行),從而影響性能。為此,很多處理器都提供了 branch prediction,根據同一條指令的歷史執行記錄進行預測,讀取最可能的下一條指令,而並非順序讀取指令。

    ==> 搭配簡報: Branch Prediction

    branch prediction 對軟體架構有些要求,對於重複性的分支指令序列,branch prediction 硬體才能得到較好的預測結果,而對於類似 switch-case 一類的程式結構,則往往不易得到理想的預測結果。

    ==> 對照閱讀: Fast and slow if-statements: branch prediction in modern processors

    ==> 編譯器提供的輔助機制: Branch Patterns, Using GCC

    上面介紹的幾種處理器特性對軟體效能影響很大,然而依賴時鐘進行定期採樣的 profiler 模式無法闡述程式對這些處理器硬體特性的使用情況。處理器廠商針對這種情況,在硬體中加入了 PMU (performance monitor unit)。PMU 允許硬體針對某種事件設置 counter,此後處理器便開始統計該事件的發生次數,當發生的次數超過 counter 內設定的數值後,便產生中斷。比如 cache miss 達到某個值後,PMU 便能產生相應的中斷。一旦捕獲這些中斷,便可分析程式對這些硬體特性的使用率了。

  • Tracepoints
  • Tracepoint 是散落在核心原始程式碼的一些 hook,一旦使能,在指定的程式碼被運行時,tracepoint 就會被觸發,這樣的特性可被各種 trace/debug 工具所使用,perf 就是這樣的案例。若你想知道在應用程式執行時期,核心記憶體管理模組的行為,即可透過潛伏在 slab 分配器中的 tracepoint。當核心運行到這些 tracepoint 時,便會通知 perf。

    Perf 將 tracepoint 產生的事件記錄下來,生成報告,通過分析這些報告,效能分析調校的工程人員便可瞭解程式執行時期的核心種種細節,也能做出針對效能更準確的診斷。

    ===  Perf -- Linux下的系統性能調優工具 (END) ===

    Perf 基本使用

    前面有提到,Perf 能觸發的事件分為三類:

    1. [ hardware ]: 由 PMU 產生的事件,比如 cache-misses、cpu-cycles、instructions、branch-misses ...等等,通常是當需要瞭解程序對硬體特性的使用情況時會使用。
    2. [ software]: 是核心程式產生的事件,比如 context-switches、page-faults、cpu-clock、cpu-migrations ...等等。
    3. [ tracepoint ]: 是核心中的靜態 tracepoint 所觸發的事件,這些 tracepoint 用來判斷在程式執行時期,核心的行為細節,比如 slab 記憶體配置器的配置次數等。

    Perf 包含 20 幾種子工具集,不過我還沒碰過很多,我根據目前理解先介紹以下。

  • 如果想看第一手資料 :`$ perf help <command>`
  • 這應該是大部分的人第一次安裝 perf 後所下的第一個指令,它能印出 perf 可以觸發哪些 event,不同 CPU 可能支援不同 hardware event,不同 kernel 版本支援的 software、tracepoint event 也不同。我的 perf 版本是`3.19.8`,所支援的 event 已經超過 1400 項(另外要列出 Tracepoint event 必須開啟 root 權限)。

    `$ perf list`

     其實跟平常 Linux  內建的 top 指令很相似。它能夠「即時」的分析各個函式在某個 event 上的熱點,找出拖慢系統的兇手,就如同上面那個範例一樣。甚至,即使沒有特定的程序要觀察,你也可以直接下達 `$ perf top` 指令來觀察是什麼程序吃掉系統效能,導致系統異常變慢。譬如我執行一個無窮迴圈:

    可以發現紅色熱點就出現了。右邊第一列為各函式的符號,左邊第一行是該符號引發的 event 在整個「監視域」中佔的比例,我們稱作該符號的熱度,監視域指的是 perf 監控的所有符號,預設值包括系統所有程序、核心以及核心 module 的函式,左邊第二行則為該符號所在的 Shared Object 。若符號旁顯示`[.]`表示其位於 User mode,`[k]`則為 kernel mode。 

    (當你關掉該程序之後,這個監視畫面 (tui 界面) 裡的該程序不會「馬上」消失,而是其 overhead 的比例一直減少然後慢慢離開列表)。

    按下 `h`可以呼叫 help ,它會列出 perf top 的所有功能和對應按鍵。

    我們來試看看 Annotate(註解),這功能可以進一步深入分析某個符號。使用方向鍵移到你有興趣的符號按下`a`。 它會顯示各條指令的 event 取樣率(耗時較多的部份就容易被 perf 取樣到)。

    最後若你想要觀察其他 event ( 預設 cycles ) 和指定取樣頻率 ( 預設每秒4000次 ) :

    `$ perf top -e cache-misses -c 5000`

    相較於 top,使用 perf stat 往往是你已經有個要優化的目標,對這個目標進行特定或一系列的 event 檢查,進而瞭解該程序的效能概況。(event 沒有指定的話,預設會有十種常用 event。)

    我們來對以下程式使用 perf stat 工具 分析 cache miss 情形

    `$ perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./perf_stat_cache_miss`

    `--repeat <n>`或是`-r <n>` 可以重複執行 n 次該程序,並顯示每個 event 的變化區間。

    `cache-misses,cache-references`和 `instructions,cycles`類似這種成對的 event,若同時出現 perf 會很貼心幫你計算比例。

    根據這次 perf stat 結果可以明顯發現程序有很高的 cache miss,連帶影響 IPC 只有`0.65`。如果我們善用一下存取的局部性,將 `i,j`對調改成`array[i][j]++`。

    cache-references 從 `128,483,262`下降到 `2,414,202`,差了五十幾倍,執行時間也縮短為原來的三分之一!

    有別於 stat,reocrd 可以針對函式級別進行 event 統計,方便我們對程序「熱點」作更精細的分析和優化。

    我們來對以下程式,使用 perf record 進行 branch 情況分析

    perf 操作:

    `:u`是讓 perf 只統計發生在 user space 的 event。最後可以觀察到迴圈展開前後 branch-instructions 的差距。

    另外,使用 record 有可能會碰到的問題是取樣頻率太低,有些函式的訊息沒有沒顯示出來(沒取樣到),這時可以使用 `-F <frequcncy>`來調高取樣頻率,可以輸入以下查看最大值,要更改也沒問題,但能調到多大可能還要查一下。

    `$ cat /proc/sys/kernel/perf_event_max_sample_rate`

    參考資料

    案例分析: Phone Book

    Week #1 課程說明中,介紹過的電話簿搜尋程式,cache miss 對於整體效能有顯著影響

    題目說明

    思考以下程式碼可能存在的問題,並著手改善效能。

    Hint: cache miss

    未優化版本

    程式碼: phonebook

  • 測試檔:
    1. 男生 + 女生英文名字的攻擊字典檔。約 16,750 個。
    2. 英文單字表,約 350,000 個。

    `$ perf stat -r 10 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./main_origin`

           

    `$ perf record -F 12500 -e cache-misses ./main_origin && perf report`

    優化版本

    程式碼:embedded-summer2015/phonebook (Github)

    查看電腦 cache 大小 `$ lscpu | grep cache`

  • 第一種優化方式:使用體積較小的 struct。
  • 根據題目要求,我們只需要知道「有沒有找到 last name」,對於 email、phone number、address、zip 等等資訊是可以在搜尋過程中忽略不看。另外我又希望能不改變原本 phonebook entry 的結構,所以我另

    外設計一個 struct 只儲存 last name,並用一個指向 phonebook entry 的指標叫 *detail 來儲存詳細資訊,新的 struct 大小只有 32 bytes,這樣搜尋的過程中,cache 就可以塞進 (32 * 1024) / (32*8) = 128 個單字,增加 cache hit 的機率。

    不過我在這裡實作 appendOptimal() 中,*detail 並沒有沒指向一塊空間,我想專心讓 appendOptimal() 產生含有 lastName 的節點就好。為什麼呢?因為若在 append 過程中 malloc() 空間給 *detail,會增加很多 cache miss,嚴重影響到效能表現,經過實測,總體效能甚至比原始版本還差一點。目前想法是將 *detail 的 assign (當有需要時)交給另外一個 function 處理,畢竟我們一開始只有 last name 的資訊。 

    `$ perf stat -r 10 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./main_optimal`

            

    `$ perf record -F 12500 -e cache-misses ./main_optimal && perf report`

  • 第二種優化方式:使用 hash function
  • 第一種方式已經見到不錯的效能成長了!findName() 的 CPU time 從 `0.050462` 變成`0.023803`,進步一倍以上。另外 cache miss 的次數從 `3,519,048`降到 `486,127`!

    不過 35 萬個單字量畢竟還是太大,如果利用字串當作key,對 hash table 作搜尋顯然比每次從頭開始查找快多了。所以接下來的問題就是,如何選擇 hash function?如何減少碰撞發生呢?我選了兩種 hash function。不過以下先用 hash2() 和上面的結果作比較。另外 table size 我使用 42737,挑選的原因是因為有約35萬個英文單字,為了減少碰撞機會,挑了一了蠻大的「質數」。

    `$ perf stat -r 10 -e cache-misses,cache-references,L1-dcache-load-misses,L1-dcache-store-misses,L1-dcache-prefetch-misses,L1-icache-load-misses ./main_hash`

     

     `$ perf record -F 12500 -e cache-misses ./main_hash && perf report`

    討論與分析

  • 執行時間分析
  • cache miss 情形
  • perf 能偵測的 cache miss 種類非常多,基本上分為 load-miss、store-miss、prefetch-miss 三種,而再根據 cache 種類又分 Level 1 cache 和 Last Level cache,instruction cache 和 data cache,TLB cache。

    我們最關心的是`L1-dcache-load-misses`,也就是要尋找的 data 不在 Level 1 cache,要往更下層的 memory (我的電腦有 L2、L3)。經過縮小 entry後,version 1 的`L1-dcache-load-misses`減少了 0.4 倍,而 hash 版本則因為查找的數量從 242.6 萬次降到不到 20 次,如下表。進而讓 cache miss 再更減少了近 0.8 倍!不過當然這樣的成果要歸功於一開始辛苦建立 Hash table。

  • 不同 Table size 對效能的影響
  • Hash function 裡常會對字串作很多次的加法或乘法,以這邊 hash2() 來說除了加法還有乘32,如果我取的不是質數,剛好是某些數字的倍數,譬如 2 或 3 等等,mod 之後就會很容易往某個幾個 bucket 集中,若很不巧我找的字剛好在這幾的 bucket 裡,平均來講效能就不好了,list會很長,所以 table size 我會選用質數。

    另外一件事情是, Table size 使用 42737,選用這麼大的數字的考量在 data set 有 35 萬個,size 越大的話,每個 bucket 的 linked list 才不會太長,findName() 起來才會快。

    就前面結果我們已經知道 hash 版本速度很快,cache miss 也很低。剩下能主導效能就是查找次數了,以下列出幾個 size 的結果。而當 Table size 大於 7919 時,其查找的次數差異已經非常小了。

  • 不同的 hash function 對效能的影響
  • hash2() 是有名的 djb2,兩者差別是 `hashVal << 5` ,也就是 hashVal * 32的意思。ASCII 字元的數值最大為 127 的整數,不管是人名還是英文單字當作輸入,平均鍵值長度大約 6~10,所以 hashVal 最多也只有 1270 種可能,不是一個均勻分佈,而在效能表現上可能就有很大的差異

    `$ ./main_hash ` with hash1()

    ==> 共 552 次

    `$ ./main_hash `with hash2()

    ==> 共 19 次

    Jakub Jelinek 針對不同的 hash function 所作的分析:

    ==> 應用於 GNU Hash ELF Sections,加速動態函式庫的載入時間

    ==> 延伸閱讀: Optimizing Linker Load Times

    http://hackathon.nctu.edu.tw/ http://hackathon.nctu.edu.tw/