分享到plurk 分享到twitter 分享到facebook

版本 ebd6da6499a9777e7823e450dfc2d4b6bb13659a

ARM-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

Lmbench 3.0 測試方法分析

Context Switch Latency on BeagleBone Black(Linux)

  • 取得lmbench並編譯給BBB
    • 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: 在上執行的總時間
    • Ci,A:
    • Pi,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 行為分析