版本 d902ac23ee7b8727b643e2b884d4d7686a467c0f
Changes from d902ac23ee7b8727b643e2b884d4d7686a467c0f to c42af77f733fa23ad21df88e12522a10b0b50320
---
title: ARM-Linux
categories: embedded, arm, cortex-a, cortex-a8, linux
...
協作者
------
* 2015 年春季
- 洪文麟, 蔣亞翰, 邱酩仁, 張家榮, 顧又榮
共筆
----
* 2015 年春季: `hackpad <https://embedded2015.hackpad.com/Team6--D3q9lvQUPDH>`_
硬體及測試平台
------------------------------------------------
- 電腦端:
- Intel i5/i7
- Ubuntu 14.10 64 bit
- Lubuntu 14.10 64 bit
- 測試硬體:
- BeagleBone Black:
- ARM Cortex A8
- AM3358
- 測試平台:
- Linux
- `Angstrom<https://github.com/beagleboard/kernel/tree/3.8>`_
- Kernel version:3.8
編譯Linux(Angstrom)給BeagleBone Black
------------------------------------------------
Lmbench 3.0 測試方法分析
------------------------------------------------
- 簡介
- Lmbench 3 是一套可移植性高的benchmark，由許多小的benchmark module組成，具有不少測試功能
- Bandwidth benchmarks
- Cached file read
- Memory copy (bcopy)
- Memory read
- Memory write
- Pipe
- TCP
- Latency benchmarks
- Context switching.
- Networking: connection establishment, pipe, TCP, UDP, and RPC hot potato
- File system creates and deletes.
- Process creation.
- Signal handling
- System call overhead
- Memory read latency
- Miscellanious
- Processor clock rate calculation
- 簡易說明lmebnch測量latency方式:
- 一次的測試，latency = (執行時間/iterations)
- iterations為mhz benchmark module測量，故不是定值，用以確保執行時間夠長，具有代表意義。
- repetition
- (執行"repetition次"結果的加總，在除以"repetition次")，就當作真正的結果
- (執行"repetition次"結果的加總，在除以"repetition次")，就當作"這次"測量的結果
- 一次的測試，latency = (執行時間/iterations)
- iterations為`mhz benchmark<http://www.bitmover.com/lmbench/mhz-usenix.pdf>`_測量，故不是定值，用以確保執行時間夠長，具有代表意義。
- 執行時間不同當然是因為硬體不同所造成，然而影響最多的就是CPU架構，為了量測出準確的執行時間，必須將不確定因素降到最低，且時間與時脈(倒數關係)息息相關。
- GCD法(最大公因數)，必須挑選互相有相依性的指令，因為pipeline的關係，導致cycles變少，且必須防止compiler優化，導致指令不按照預期執行:
.. code-block:: txt
如果一個CPU時脈為120Mhz，且執行以下兩個指令
1. SHR (2 cycles)
2. SHR;ADD (3 cycles)
如果執行時間為:
1. SHR 11.1ns (2 cycles)
2. SHR;ADD 16.6ns (3 cycles)
GCD 為 5.55ns，其倒數即為120Mhz，與原先假設相同
compiler的優化例子:
a+=a; // ADD optimized to a=0
a&=a; // AND optimized away completely
a^=a; // XOR optimized to a=0
a+=b; // ADD optimized to a+=b+b+b+…
因此mhz挑選了9組指令:
1. p=*p;
2. a^=a+a;
3. a^=a+a+a;
4. a>>=b;
5. a>>=a+a;
6. a^=a<<b;
7. a^=a+b;
8. a+=(a+b)&07;
9. a++;a^=1;a<<=1;
實際上在source code發現，iterations的值是經由一個迴圈去不斷測試值是否大於需求(根據`mhz benchmark作者自己說<http://www.bitmover.com/lmbench/mhz-usenix.pdf>`_，是150ms)
.. code-block:: c
#define BENCH_INNER(loop_body, enough) { \
static iter_t __iterations = 1; \
int __enough = get_enough(enough); \
iter_t __n; \
double __result = 0.; \
\
while(__result < 0.95 * __enough) { \
start(0); \
for (__n = __iterations; __n > 0; __n--) { \
loop_body; \
} \
__result = stop(0,0); \
if (__result < 0.99 * __enough \
|| __result > 1.2 * __enough) { \
if (__result > 150.) { \
double tmp = __iterations / __result; \
tmp *= 1.1 * __enough; \
__iterations = (iter_t)(tmp + 1); \
} else { \
if (__iterations > (iter_t)1<<27) { \
__result = 0.; \
break; \
} \
__iterations <<= 3; \
} \
} \
} /* while */ \
save_n((uint64)__iterations); settime((uint64)__result); \
}
1<<27 : MAX_ITER
1.1 : CORRECTION_RATE
3 : INCREASE_RATE
Context Switch Latency on BeagleBone Black(Linux)
-----------------------------------------------------
- 取得lmbench並編譯給BBB
- 由於lmbench 3已經很久沒有更新，lmbench-next為基於Linux的優化開源專案，並不保證能夠正常運作於non-Linux system
- git clone https://github.com/el8/lmbench-next.git
- cd lmbench-next
- make ARCH=arm CROSS_COMPILE=arm-linux-gnueabi-
.. code-block:: txt
git clone https://github.com/el8/lmbench-next.git
cd lmbench-next
make ARCH=arm CROSS_COMPILE=arm-linux-gnueabi-
Context Switch Latency 測試理論
=================================================
**Abstract Machine Model:**
.. image:: /embedded/arm_linux/Abstract_Machine_Model_1.png
- 方程式(1):
- TA,M: <程式A>在<機器M>上執行的總時間
- Ci,A: <程式A><執行的次數i>
- Pi,M: <執行次數i>在<機器M>上
.. image:: /embedded/arm_linux/Abstract_Machine_Model_2.png
- 方程式(2):(多了cahce/TLB miss)
- Fi,A (faults):為記憶體階層的第i層的miss次數
- Di,M (delay):每次miss所付出的懲罰
**論文實驗方法:**
- 測試參數:
- Stride: s
- Array size : one-dimensional array of N k-bytes
- Cache/TLB size: C k-bytes
- Cache Line size:b words
- Cache Associativity: a
- 基本假設:
- 只有L1 cache
- Instruction Cache與Data Cache為獨立的
- Data Cache可用Virtual Address(以後皆稱VA)定址:意思就是記憶體為"連續的區域"
- 子集合的基本單位(by sequence number): 1, s + 1, 2s + 1, ..., N - s + 1.
- Cache更新的機制為write-through
- Tno-miss可能包含處理器被強制等待write buffer back up的時間
**論文實驗分類與討論:**
.. image:: /embedded/arm_linux/tlb_experiment_table.png
- REGIME 1:
- N <= C
- C為cache的容量
- N為array size
- 只要array被載入，就不再有cache miss出現，也就是永遠只有第一次載入時，會有cache miss
- 每次遞迴的執行時間(Tno-miss)包含讀取一個Array的子集合的基本單位(stride),計算,以及將結果存回Cache
- REGIME 2.a :
- array比cahce size大，所以一次沒有辦法全部讀進cahce
- stride比line size小，所以取一次array不一定會超過cache的大小，會有s/b次miss
- b/s個連續存取到同一個 cache line.
- 第一次載入array，總是Cache miss,REGIME 2 三種討論皆是如此，不再重述。
- 因此執行時間為Tno-miss + D*s/b ;D為delay penalty(代表從主記憶體讀取資料然後恢復執行的時間)
- REGIME 2.b :
- Array size 比 cache容量大
- stride比line size大(意思是每次都會miss)
- stride比array size小
- 每次遞迴都會有cache miss,也就是說每個Array的子集合的基本單位(stride)對應到一個不同的cache line.
- 每次遞迴的執行時間為Tno-miss + D
- REGIME 2.c :
- array size比cache大
- stride介於array size 的1/2~1倍,所以第一次沒有讀進來的array，就再也讀不到了
- 記憶體位置映射到一個單位子集合的次數一定少於associativity,也就是這個情況下(2.c)，除了第一次載入Array會有miss之外，就沒有miss了
- 如果array有N elements,只有N/s < a可以被實驗到,且他們個別都可以被放入一個單一的子集合(stride),也就是說N/a <= s.
- 每次遞迴的執行時間為Tno-miss
- 結論
- TLB的行為可視為與Cache一樣
- Cache/TLB size可藉由測試，當發現Latency time大幅上升時，藉由比較array size(實際上的情況下面會談到)可以知道，因為D(cache miss penality)通常大於Tno-miss
- Regime 2.a與2.b相較於2.c方法，可以用來解釋為什麼在`維基百科 wiki :CPU cache<http://en.wikipedia.org/wiki/CPU_cache>`_ 中，有一張圖及內容談到當cache associativity(也就是a)越大時，miss rate越小。
.. image:: /embedded/arm_linux/tlb_wiki_associativity.png
- 參考資料：
- `Measuring cache and TLB performance and their effect on benchmark runtimes<http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=467697&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D467697>`_
- `整理這篇論文的過程<https://embedded2015.hackpad.com/Team6-ARM-Linux-lmbench-Rlcb2b5Bw6O#:h=IV.-EXPERIMENTAL-RESULTS-FOR-C>`_
Context Switch Latency 理論與實際的結合
=================================================
- BBB的AM3358:
.. image:: /embedded/arm_linux/BBB_hardware_1.png
- L1 Data Cache與Instruction Cache互相獨立，均為32KB
- L2 Cache為256KB
.. image:: /embedded/arm_linux/BBB_hardware_2.png
**對應"Context Switch Latency 測試理論"**
.. image:: /embedded/arm_linux/partical_theory.png
.. image:: /embedded/arm_linux/partical_theory_2.png
Context Switch Latency 實驗過程
=================================================
- 因為Linux無法關閉L2 cache，且要將其他程式對cache的影響降到最低，使用sync及drop_caches
- sync && echo 3 > /proc/sys/vm/drop_caches
- 但還是有些許影響，因為清完cache後，Linux還是有其他程式使用cahce，無法避免
**shell script for 巨觀**
.. code-block:: txt
#!/bin/sh
WARMUPS=0
REPETITIONS=11
CTX="0 2 4 8 16 24 32"
N="2 4 6 8 10 12 16 24 32 48 64 72 96"
set -x
for size in $CTX
do
#flush cache
sync && echo 3 > /proc/sys/vm/drop_caches
bin/arm/lat_ctx \
-W $WARMUPS -N $REPETITIONS -s $size $N
done
echo "" 1>&2
**shell script for 微觀**
.. code-block:: txt
#!/bin/bash
WARMUPS=0
REPETITIONS=11
CTX="2 4 8 16 24 32"
N="2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35"
file_dest="./test_results/"
extension="k.txt"
mkdir -p $file_dest
set -x
for size in $CTX
do
for pnumber in $N
do
RUN="bin/arm/lat_ctx -W $WARMUPS -N $REPETITIONS -s $size $pnumber"
#flush cache
sync && echo 3 > /proc/sys/vm/drop_caches
file=$file_dest$size$extension
if test -s $file
then
$RUN >> $file 2>&1
else
$RUN > $file 2>&1
fi
done
done
echo "" 1>&2
Context Switch Latency 實驗結果 及 分析
=================================================
**折線圖可由斜率， 得到rate of time to Size(process number * process size)，斜率突然暴增就是cache miss開始發生**
**長條圖可直接比較Y軸(時間)，發現cache miss開始**
- L1 cache miss
- 採用Harvard architecture(data/instruction cache分開)，分析起來相對於L2 cache容易
- 巨觀
.. image:: /embedded/arm_linux/2k_Macroscopic.png
- 理論推算表格(僅取部分，作為代表，可依此類推)
.. image:: /embedded/arm_linux/partical_theory_2k_table.png
- 微觀折線圖
.. image:: /embedded/arm_linux/2k_Microcosmic.png
- 微觀長條圖-相較於折線圖，可以更明顯看到，當process number接近16(2k*16=32k,用接近是因為可能有其他程式也使用L1 cache)時，latency大幅上升
.. image:: /embedded/arm_linux/2k_Microcosmic_histogram.png
- L2 cache miss
- 由於L2 cahce採用von Neumann architecture(與L1 cache不同！)，將data與instruction混合，不易分析，不過我們可以由實驗結果，看出一些端倪。
- process size=24k與32k之長條圖比較
.. image:: /embedded/arm_linux/24k_32k_histogram.png
- process size=24k與32k之折線圖比較
.. image:: /embedded/arm_linux/24k_32k.png
- 由以上2組比較圖，可以看出
- process size=24k時，process number=8,N=24*8=192，latency大幅上升，合理推測這時候L2 cache miss
- process size=32k時，process number=5,N=32*5=160，latency大幅上升，合理推測這時候L2 cache miss
- 這個範圍的變動除了L2 cache除了有其他程式使用外，相較於L1的單純，還要多考慮Instruction的影響。
- 巨觀整體趨勢圖
.. image:: /embedded/arm_linux/lat_ctx_all_Macroscopic.png
- 微觀整體趨勢圖
.. image:: /embedded/arm_linux/lat_ctx_all_Microcosmic.png
**Context Switch Latency 結論**
- 當(process size)*(process number)+(other program cache) > 32kb(L1 cache size)
- 比較=32kb與下一筆稍大於32kb的數據和下下一筆稍大於32kb的數據可以發現latency time是可以看出latency時間增幅會比較大的趨勢
- L1 cache miss penality影響甚巨。
- 當(process size)*(process number)+(other program cache)+(Instruction cache affect) > 256kb(L2 cache size)
- 相較於L1 cache的Harvard architecture，採用von Neumann architecture的L2確實比較難以測試出L2 cache的大小，但仍可看出，L2 cache miss的penality不容小覷，比L1 cache miss penality影響更多。
- 可以從整體趨勢發現，當N(process number * process size)大到某個程度後，latency的時間就趨近於固定的數字
- 可以看出如果process size越大，會越早到達"飽和"(就是比較快到他最終趨近的latency time)
- 注意事項：
- 這個測試必須注意BBB的散熱，吹冷氣＋電風扇才不會造成異常結果。
System Call Latency on BeagleBone Black(Linux)
------------------------------------------------
Unix Latency on BeagleBone Black(Linux)
------------------------------------------------
Memory Read Latency on BeagleBone Black(Linux)
------------------------------------------------
Ftrace
------------------------------------------------
KernelShark
------------------------------------------------
Linux Kernel Timer Interrupt
------------------------------------------------
Linux Scheduler 行為分析
------------------------------------------------
