Nov 6, 2015 課程紀錄

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

課程公告

「真正的發現之旅不在於尋求新的風景,而是在於擁有新的眼光。」

“The real voyage of discovery consists not in seeking new landscapes, but in having new eyes.”

課程目標

回顧 C 語言

假設我們有兩個****有號整數***:

然後原本涉及到分支的陳述:

可更換為沒有分支的版本:

為什麼呢?一旦 b 右移 31 個 bit,在右移 `>>` 時在前面補上 sign bit ,所以移完會是 0xffff 也就是-1,故結果會是 `a -= -1`,即 `a++`,於是,原本為負數的值就變成 1 ,而原本正數的值就變成 0,又因為原本的行為是有條件的 a++,如此就是數值操作,沒有任何分支指令。

演算法:

  1. 大數 := 大數 - 小數
  2. 若「最大」和「最小」兩數相同,那麼它就是最大公因數,否則,回到第 1 步

示範:

GCD(48, 40)

48 - 40, 40 -> 8, 40

8 != 40, 於是重複上述動作: 40 - 8, 8 -> 32, 8

8 != 32, 於是重複上述動作: 32 - 8, 8 -> 24, 8

8 != 23, 於是重複上述動作: 24 - 8, 8 -> 16, 8

8 != 16, 於是重複上述動作: 16 - 8, 8 -> 8, 8

8 == 8 成立,於是 8 為 GCD

用 C 語言實現阿基米德法: (v1)

以 Intel C compiler 產生的機械碼來說: (Pentium 4)

指令 數量 延遲 cycle count
減法 5 1 5
比較 5 1 5
分支 14 1 14
其他 0 1 0
24

改成 mod 操作的 C 語言程式如下: (v2)

以 Intel C compiler 產生的機械碼來說:

指令 數量 延遲 cycle count
mod (整數除法) 2 68 136
比較 3 1 3
分支 3 1 3
其他 6 1 6
148

如果可排除整數除法和減法的負擔,得到以下實做: (v3)

可得到更快的實做:

reference: The Software Optimization Cookbook: High Performance Recipes for IA-32 Platforms, 2nd Edition

張家榮同學在 ARM Cortex-A8 1 GHz 上的實驗

平台:BeagleBone Black (ARMv7-A)

實驗程式碼:github

ARM vs.  Thumb instruction

Assembly

Euclidean(thumb) V.S. mod(thumb) V.S. mod_minus(thumb)

Euclidean(arm) V.S. mod(arm) V.S. mod_minus(arm)

C語言

效能分析: Prefetching

[ source

接著參考 Programming trivia: 4x4 integer matrix transpose in SSE2 實作 Intel SSE2 加速的版本,由於先進處理器架構有著 automatic/speculative prefetcher 所以這裡我們故意寫得比較 CPU-unfriendly 一些:

我們來撰寫一個使用 SSE prefetch 指令的加速版本:

接著是測試程式:

存成 test.c, 並且按照下列方式編譯

在 Intel Core i7 3612QM 執行得到下列結果:

儘管現今 CPU 有著強大的 auto-prefetcher,但是並不是所有的演算都有著規律或是線型的記憶體存取模式, 如此透過優化 prefetching 依然是能夠有相當的效能增進.

在 EeePC 900 (Intel Celeron M 900 MHz) 仍有 22% 的效能差異:

ARM 架構

https://commons.wikimedia.org/wiki/File:Pipeline_MIPS.png

[ Introduction to ARM Architecture ]

 

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

p.121 gdb arm 的 objectfile 有需要注意的事項嗎?

[ Introduction: the ARM Cortex-M3 Exception / Interrupt ]

此簡報撰寫於 2012 年,部份資訊過時,請留意

ARM Cortex-M0, M0+, M3, M4, M7

[ ARM Cortex-M3 ]

CP15: ARMv5

ARM instruction: MRC, MCR

p.7 NVIC

interrupt controller (之前各廠商自己做, 現在ARM提供)

p.17 CPU modes

Handler mode and Thread mode

p.31

Cortex-A : Generic Timer

Cortex-M : System Timer

p.35 interrupt handling

減少interrupt成本 : for real-time control

p.65

執行WFI/WFE ->  enter low power mode

CPU clusters間:透過IPI