版本 7e4d7c5f9ed511ec0ce8b1b787a582b3fb529113

ARM-Linux

協作者
共筆
硬體及測試平台
編譯arm-Linux(Angstrom)給BeagleBone Black
Lmbench 3.0 測試方法分析
Context Switch Latency on BeagleBone Black(Linux)
Context Switch Latency 測試理論
Context Switch Latency 理論與實際的結合
Context Switch Latency 實驗過程
Context Switch Latency 實驗結果及分析

協作者

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

Environment

.. code-block:: txt

$sudo apt-get install   zlib1g-dev   libsdl1.2-dev   build-essential   ddd   cpio   libncurses5-dev  u-boot-tools
$sudo apt-get install   lib32gcc1 ( 64-bit required)
$sudo apt-get install gcc-arm-linux-gnueabi
$sudo apt-get install lzop

切割SD card
- mkcard.sh<https://github.com/nmenon/uomapfs/blob/master/scripts/mkcard.sh>_
- $sh –x mkcard.sh<https://github.com/nmenon/uomapfs/blob/master/scripts/mkcard.sh>_ /dev/sdX;X為主機內看到的sd 卡掛載點 ex.sdb
Bootloader

.. code-block:: txt

抓source檔
$ git clone git://git.denx.de/u-boot.git
$ cd u-boot/
$ git checkout v2015.01 -b tmp
下載一個屬於am335x的環境patch檔
$ wget -c https://raw.githubusercontent.com/eewiki/u-boot-patches/master/v2015.01/0001-am335x_evm-uEnv.txt-bootz-n-fixes.patch
編譯
make ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- distclean
make ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- am335x_evm_defconfig
make ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- -j4

Kernel

.. code-block:: txt

抓source檔
$ git clone git://github.com/beagleboard/kernel.git
$ cd kernel
$ git checkout 3.8
$ ./patch.sh    ##This step may take 10 minutes or longer
編譯
$ cp configs/beaglebone kernel/arch/arm/configs/beaglebone_defconfig
$ wget http://arago-project.org/git/projects/?p=am33x-cm3.git\;a=blob_plain\;f=bin/am335x-pm-firmware.bin\;hb=HEAD -O kernel/firmware/am335x-pm-firmware.bin
$ cd kernel
$ make ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- beaglebone_defconfig
$ make ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- uImage dtbs
$ make ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- uImage-dtb.am335x-boneblack 
$ make ARCH=arm CROSS_COMPILE=arm-linux-gnueabi- modules -j4

uEnv.txt

.. code-block:: txt

mmcroot=/dev/mmcblk0p2 rw
mmcrootfstype=ext4 rootwait 
console=ttyO0,115200n8
kernel_file=zImage
fdtfile=am335x-boneblack.dtb
loadaddr=0x80008000
fdtaddr=0x88000000
initrd_high=0xffffffff
fdt_high=0xffffffff
ipaddr=192.168.0.25
serverip=192.168.0.20
rootpath=/home/andy/beaglebone/nfs
loadfdt=fatload mmc 0:1 ${fdtaddr} ${fdtfile}
loadkernel=fatload mmc 0:1 ${loadaddr} ${kernel_file}

#boot from nfs
#netargs=setenv bootargs console=${console} ${optargs} root=/dev/nfs nfsroot=${serverip}:${rootpath},${nfsopts} rw ip=${ipaddr}:${serverip}::255.255.255.0:
#netboot=echo Booting from network ...;run netargs; bootz ${loadaddr} - ${fdtaddr}
#uenvcmd=run loadkernel;run loadfdt;run netboot; 

#boot from sdcard

loadfiles=run loadkernel; run loadfdt
uenvcmd=mmc rescan;run loadkernel;run loadfdt; run fdtboot
fdtboot=run mmc_args; bootz ${loadaddr} - ${fdtaddr}
mmc_args=setenv bootargs console=${console} root=${mmcroot} rootfstype=${mmcrootfstype}

Filesystem

.. code-block:: txt

到此網站抓取檔案系統 :http://downloads.angstrom-distribution.org/demo/beaglebone/
選擇 : Angstrom-systemd-image-eglibc-ipk-v2012.12-beaglebone-2013.09.12.rootfs.tar.xz 
$tar –Jxvf Angstrom-systemd-image-eglibc-ipk-v2012.12-beaglebone-2013.09.12.rootfs.tar.xz

將此filesystem放入rootfs磁區
將以下檔案放入到boot磁區
- uEnv.txt
- MLO
- u-boot.img
- zImage({kernel}/arch/arm/boot/zImage)
- am335x-boneblack.dtb({kernel}/arch/arm/boot/dts/am335x-boneblack.dtb)

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)
可以看出average CPI = 1.5
GCD 為 5.55ns，平均一個指令執行1.5*5.55ns , 其倒數(1/1.5*5.55)即為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-

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(代表從主記憶體讀取資料然後恢復執行的時間)
- 現代的cache不以byte為單位了，以cache line為一次抓取資料的單位，故2.a方法已經不再討論，也無法驗證，但是可以驗證line size(如下驗證)

驗證line size造成的miss的影響：

test_line.c

.. code-block:: c

#include<stdio.h>
#include<sys/time.h>
#include<unistd.h>
#include<stdlib.h>
int arr[64 * 1024 * 80] = { 2 };//just for big enough
int test_line(int step)
{
struct timeval start;
struct timeval end;
long unsigned int i = 0;
gettimeofday(&start, NULL);
for (; i < (int)(sizeof(arr)/sizeof(int)); i += step) 
{
arr[i] *= arr[i];
}
gettimeofday(&end, NULL);
return ( 1000000*(end.tv_sec - start.tv_sec)+ (end.tv_usec - start.tv_usec) ) ;
}
int main(int argc, char *argv[])
{
int test_step = atoi(argv[1]);
printf("%d %d\n", test_step, test_line(test_step));
return 0;
}

shell script

.. code-block:: txt

#!/bin/bash
K="1 4 6 8 10 12 14 16 32 64 128 256"
#set -x
for size in $K
do
    ./test_line $size
done
echo "" 1>&2

.. image:: /embedded/arm_linux/line_size_compare.png - 會同時放上BBB和i7-5500U的結果是因為，cache line miss的overhead固然不小，但由於BBB的CPU運算較慢，較不明顯，所以放上較快的i7-5500U做為比較，且兩者的L1 cache line size均為64bytes。

原因：

由於BBB的line size為64byte = 16個INT，今天以一個迴圈，對其值做動作，然後每次跳躍“K”個記憶體位置，消耗的時間為CPU運算時間+cache line miss的時間，從圖中可發現，K <=16時，斜率較低，但消耗時間仍然有下降，可以發現是因為實質上CPU所運算的對象的確較少，然而到K=32時，CPU雖然運算比先前更少，但是可以看出line(cache) miss的影響比較大，因為同樣都是少了一半CPU運算的對象（k=8與k=16 vs k=16與k=32 vs k=32與k=64），但斜率下降更明顯，就是由於miss的次數少了一半。依此類推，K=64為K=16的miss次數的1/4，但是K=1到K=16的miss次數是一樣的，至於為什麼會這樣，見下圖說明。今天cache一次抓取line size大小的資料，所以64bytes以下的資料都會被抓進來，只是當K!=1且K<16時，會比K=1的情況下，運算較少次，但是miss次數是一樣的! - 說明圖片:(int的大小為4 bytes時) - 32byte為k=8的情況 - 64byte為k=16的情況 - 256byte為k=64的情況 - 碰到紅色代表會miss

.. image:: /embedded/arm_linux/line_size_illustrate.png

- 今天如果有一個夠大的array，一個line是64byte，那麼如果小於等於64bytes的K，會踩到N次<假設>的cache line miss，但是如果K=128bytes，由於會"跨過"某些cache line miss的"點"(因為沒有要用到那邊的資料)，所以時間會大幅降低（因為cache miss的overhead很大，實際上是少了1/2的miss次數），若是K=256bytes，則為少了1/4的miss次數（相較於K<=64bytes）
- 在參考資料1中的example2，它也有說明。

參考資料1<http://igoro.com/archive/gallery-of-processor-cache-effects/>_
參考資料2<https://www.scss.tcd.ie/Jeremy.Jones/CS3021/5%20caches.pdf>_
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)

Lmbench3 lat_unix:
- lat_unix - 測量interprocess communication latency透過UNIX sockets
- “hot potato” benchmark
  - benchmark不斷的在2個process間來回傳遞message
- process裡面沒有做任何事情

-測量出的數據( 第一欄為message size,第二欄為latency )

.. code-block:: txt

0 3.9333
1 45.2623
2 45.3115
3 45.5246
4 45.4098
5 45.5410
6 45.5702
7 45.5246
8 45.7870
10 45.5000
12 45.5289
16 45.7156
20 45.6694
24 45.7523
32 45.7870
48 46.1574
64 45.9752
96 45.9091
128 46.0965
196 46.2689
256 46.4434
384 46.6555
512 47.1887

.. image:: /embedded/arm_linux/lat_unix_LMA_RMI.png

左邊為巨觀，右邊為微觀，可以看出斜率均趨近於0。

結論

不論傳遞的message多大(除了0之外)，overhead都大約是46 microseconds

版本 7e4d7c5f9ed511ec0ce8b1b787a582b3fb529113

ARM-Linux

協作者

共筆

硬體及測試平台

編譯arm-Linux(Angstrom)給BeagleBone Black

Lmbench 3.0 測試方法分析

Context Switch Latency on BeagleBone Black(Linux)

Context Switch Latency 測試理論

Context Switch Latency 理論與實際的結合

Context Switch Latency 實驗過程

Context Switch Latency 實驗結果及分析

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 行為分析

版本 7e4d7c5f9ed511ec0ce8b1b787a582b3fb529113

ARM-Linux

協作者

共筆

硬體及測試平台

編譯arm-Linux(Angstrom)給BeagleBone Black

Lmbench 3.0 測試方法分析

Context Switch Latency on BeagleBone Black(Linux)

Context Switch Latency 測試理論

Context Switch Latency 理論與實際的結合

Context Switch Latency 實驗過程

Context Switch Latency 實驗結果 及 分析

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 行為分析

Context Switch Latency 實驗結果及分析