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

版本 2e473c1ae5142e02cbfb65126e9a6208c61000e3

embedded/arm-linux

Changes from 2e473c1ae5142e02cbfb65126e9a6208c61000e3 to 48881610988adb7d851371831a3f0bff1f9012f6

---
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
- 測試平台:
   - arm-Linux
       - `Angstrom<https://github.com/beagleboard/kernel/tree/3.8>`_
       - Kernel version:3.8

編譯arm-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方式:
    - 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);    \
    }


`參考資料<http://www.bitmover.com/lmbench/mhz-usenix.pdf>`_


Context Switch Latency on BeagleBone Black(Linux)
-----------------------------------------------------

- 取得lmbench並編譯給BBB(arm-linux)
    - 由於lmbench 3已經很久沒有更新,lmbench-next為基於Linux的優化開源專案,並不保證能夠正常運作於non-Linux system

.. code-block:: txt

    ``git clone https://github.com/el8/lmbench-next.git``
    ``cd lmbench-next``
    ``make ARCH=arm CROSS_COMPILE=arm-linux-gnueabi-``
    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 行為分析
------------------------------------------------