Android 軟體架構轉變的進行式

今日在 Google 的 Android Developer Blog 上貼出了篇名為的 "Here comes Treble: A modular base for Android" 貼文, 這是一件對於 Android 生態系統的大事, 也是 Google 方面嘗試來解決 Android 的碎片化與安全性上的問題.

這件事必須先從 Android 裝置的軟體是經過什麼樣的流程抵達每個使用者手上, 在這篇文章中即是一開始的五步驟圖:

1. Android 團隊向世界發佈最新版本的原始程式碼
2. 晶片製造公司為了讓他們各自的晶片在 Android 裝置上俱備更多優勢, 針對他們特定的硬體, 修改了來自 1. 的原始碼與增添驅動程式.
3. 這些晶片製造商接著將這些修改提供給他們的客戶 - 也就是那些設計與生產 Android 裝置的品牌商. 這時裝置生產商再次針對他們的產品對 1. 的軟體做了修改.
4. 裝置生產商與電信網路商測試與驗證新的版本.
5. 裝置生產商與電信網路商提供新的版本給他們的使用者

 在以往 Android 裝置間是透過相容性文件 Compatibility Definition Document (CDD) 所規範的介面以及現在已經涵蓋上百萬對應測項的相容性測試套件 Compatibility Test Suite (CTS) 來避免軟體相容性上的問題. 然而面對來自上述 2. ~ 5. 項目的修改與限制, 造成了 Android 軟體層上碎片化不容易解決, 1. ~ 3. 表示裝置生產商會 follow 的不是 1. 的官方實作而是 2. 的 chip vendor 的 Android Framework 的修改, 此外 4. 與 5. 反映了 Android 裝置的安全性修正完全取決於裝置生產商自己的更新意願(特別是裝置生產商不願意透入成本在維護已發售許久的裝置).

為此 Google 在 Android O 開始要著手解決這樣的問題, 提出了 Project Treble, 其目的在於強化對於 Android 系統軟體這塊的控制與掌握, 這必須談到在以往即已經存在, 但是界線並沒有明確規範的 Vendor Implementation (廠商實作層), 現在 Google 將明確的對 Android Framework 與 Vendor Implementation 切出這一條線:

因此先前所採用的 CDD + CTS 方式, 將轉為 Vendor Interface + Vendor Test Suite(VTS), 這件事最大的意義在於 Chip Vendor(晶片商) (或是很有可能以後包含 Device Vendor(裝置生產商) )將不再能夠直接修改上述五步驟中 1. 裡面的 Android Framework 的原始碼, 而優化與性能提升的方式也被限縮在圖中灰黑色(這顏色是不是特別選過阿...) 的 Vendor Implementation 這一層, 介面也是所定義規範出的 Vendor Interface.

藉由明確規範 Vendor Interface 的好處如上圖, 也就是 Android OS framework 的更新將獨立於 Vendor Implementation, 而在該篇文章是這麼說的 "device makers can choose to deliver a new Android release to consumers by just updating the Android OS framework without any additional work required from the silicon manufacturers", 翻成中文就是裝置生產商能夠無需藉助於晶片商額外的處理下, 就能夠自行更新 Android OS framework 的部分(這或多或少都是裝置商對於更新推托的理由與藉口). 是的, 目前 Project Treble 並沒有強勢到一次將 Android Framework 客製的權力全部收回, 這或多或少是出於市場考量, 但是至少讓 Google 頭疼的源頭 - Chip Vendor 的客製已然受限, 當然這樣作法背後還是在於 Google 對於 Chip Vendor 的客製只能道德勸說並無其他的約束能力, 而 Chip Vendor 還是會嘗試對客戶提供他們自己客製的 Android Framework, 一方面這樣介面的建立會讓裝置系統商意識到不正確與不當的客製修改, 另一方面來說對於裝置生產商來說來自 Google 相關的軟體生態系(Google Play)的授權是相當重要的, 因此 Google 還是有一定其他要求與控制能力. 一旦架構建立了 Treble Architecture, Google 即更能順利的要求裝置廠商去提供裝置的軟體更新(而以往的理由會凸顯背後的問題, 讓 Google 更能第一時間掌握有問題的平台).

最後 Google 還在文末說道目前 Pixel 上運作的 Developer Preview of O 已經採用了這樣的架構方式.

有趣的 cache line 效應

在忙著處理一些個人事務的時候, Jim Huang 請我幫忙回覆學弟妹碰到的 一些問題
主要是 Jim Huang 修改了之前 Matrix Transpose 的例子作為範例給學弟妹們練功使用
而學弟妹碰到了一個問題, 就是對於 Matrix Transpose 的寬做調整時
執行時間與長寬度的調整的分佈圖如下:

如上圖所示, 隨著對寬作 4096 + (i*64)的調整時經分佈呈現鋸齒狀的變化!
依照文中敘述的實驗平台為俱備 6MB cache 的 Core-i5 6300HQ
以 Intel Skylake 架構而言, 為 64 bytes cache line, 8-way associative cache
基本上俱備 6MB/64/8 = 12288 sets (entries)
以這個 int matrix 而言, 原始的寬度為 4096x4=16384 bytes
16384/64 = 256
因此每增加一行記憶體基本上會跳躍 256 cache line index

接著再觀察 naive transpose 的實作:
https://github.com/yangyang95/prefetcher/blob/master/impl/naive_transpose.c
若 buffer 對應的 cache line index offset 為 X

首先考慮最簡單的 i == 0 的情況
對於第 n 行的 cache line index 計算為: (X + 256*n) % 12288
1. 12288 / 256 = 48 (自 cache line 0 ~ 12288, 每次跳 256 可以消耗 48 行)
2. 12288 % 256 = 0 (每次的 cache line index shift)
所以填完 output 第一行來說, 這也代表著當資料(二維座標以(x,y)表示)自 (0, 0), (0, 1) .... (0, 4095) 要讀 (1, 0) 時
而相關的 cache line 早已被反覆地填入了 4096/48 = 85.33次 > 8
當 CPU 需要讀入 (1, 0) 時, 因為讀入 (0, 0) 所讀入的 cache line 有相當高的機會早已被 replace

接著當每次寬度增加 64 時(也就是 256 byte, 4 cache lines)
這裡我們先考慮 i == 1 的情況
對於第 n 行的 cache line index 計算為: (X + 260*n) % 12288
1. 12288 / 260 = 47.26 ...
2. 12288 % 260 = 68
260 與 68 兩者最小公倍數為 4420
4420/68 = 65  (表示反覆繞 cache line index 0 ~ 12288 到第 65 次才開始 cache line index 有所重疊)
而 4160/47.25 約為 88.02, 88.02 / 65 = 1.35 < 8
這表示在讀取 (1, 0) 時, 有很大的機會 (0, 0) 所填入的 cache line 還在

再考慮 i == 8 的情況
對於第 n 行的 cache line index 計算為: (X + 288*n) % 12288
1. 12288 / 288 = 42.6666....
2. 12288 % 288 = 192
而 288 與 192 兩者最小公倍數為 576
576/192 = 3 (表示反覆繞填 cache line index 0 ~ 12288 到第 3 次 cache line index 就有所重疊)
而 4608/42.666 約為 108, 108 / 3 = 36 > 8
這表示在讀取 (1, 0) 時, (0, 0) 所填入的 cache line 有相當高的機會早已被 replace

由類似的計算可以得知, 造成這樣的時間分佈的原因, 而 SSE 版本的成因也是基於相同道理
而這樣的效應更顯示程式的記憶體使用方式, data layout 與 cache 影響程式的效能甚巨

Blocks 初探與 multithreading 應用

近日由於個人一項工作的緣故, 為了能在短時間內能夠加速複雜程式的運作
因此現學現賣地採用了 OpenMP 做快速的優化實作, 最後得到 3倍左右的加速

儘管 OpenMP 表現不俗, 然而在 Android 上的實作必須仰賴已經被 deprecated 的 GCC
讓現今預設使用 clang 的環境必須特別撰寫 makefile
而儘管亦能夠使用先前撰文介紹的 Grand Central Dispatch 作為方案
然而一方面 libdispatch 的 Android port 已經過舊
而官方版必須限定 Android API-level 21 外 (另外現在編譯也有問題)
另一個問題是 GCD 的實作規模不可以說小

由於 Blocks 的使用其簡潔與動態的特性對於個人而言是充滿魅力的
基於如此的動機便開始構思結合 thread pool 與 Blocks 的方式
以此來簡化 multi-threading 程式的撰寫, 並且得到能夠有效修改的實作
為此目的必須先去了解 Blocks 是如何運作的
儘管 clang 提供了 "Language Specification for Blocks" 的頁面
然而個人認為 Apple 的 Blocks Programming - Introduction 撰寫的比較淺顯易懂

基本上 Blocks 提供了將 C/C++ 的大括號內的 code 區塊轉化作為類似下列型別作為"變數"的能力

void (*func)(void);

而 Blocks 中最有趣以及最為實用的功能是對於使用 global/local variable 上數值的"擷取"
以 local variable 為例, 一般的 serial code 毫無疑問會在 stack memory 中
若使用了 Blocks 並於 Blocks 中使用了該 Block 區間外的 global/local variable
這時的流程會產生了類似 process fork 的分歧, 理解上應為未明確寫出的 call by value
Blocks 中對於外部的 global/local variable 本身的修改是不具有寫回的效果
除此之外型別為 Blocks 的變數在使用上的概念其實與一般變數無異
程式撰寫的過程中同樣地必須考量與處理 variable lifetime 的問題
這時就必須藉由使用 Block_copy/Block_release 來手動複製與釋放 Blocks 所含的內容
對於程式中 local/global variable 處理概念上的不同是 OpenMP 與 Blocks 最大差異
而兩者所使用的方式, 在應用上來說真的是各有優缺

透過閱讀上述的參考資料建立概念後
接著就動手來做類似於 GCD 的 Blocks dispatching 的功能

首先是建立等同於 GCD 中使用來作為 task dispatch 的 dispatch_block_t 的型別
接著就是增加 thread pool 的 dispatch function
基本上是將原本的介面的參數自 function pointer 與型別為 (void *) 的 argument
改為直接使用 Block 型別
可不用再撰寫型別為 void* func(void*) 的 pthread glue code 的好處不用再多說了

在建立概念之後, 動手實作上就簡單多了
為了快速而採用了現成的 thread pool 實作 - C-Thread-Pool
而 Blocks 的操作是基於 BlocksRuntime (提供了 Block_copy / Block_release)
而初步的成果我暫且名為 gunshot
請 git clone 後記得 git submodule init/update

修改的 example.c 中, 嘗試比較填入一個 buffer 數值

    for(int pidx = 0; pidx < TEST_DEPTH; pidx++){
        int *plane = buf0 + pidx*TEST_W*TEST_H;
        for(int yidx = 0; yidx < TEST_H; yidx++){
            for(int xidx = 0; xidx < TEST_W; xidx++){
                plane[yidx*TEST_W + xidx] = pidx*4096 + (yidx + xidx);
            }
        }
    }

而 thread pool + Blocks 的版本可以寫為

    for(int pidx = 0; pidx < TEST_DEPTH; pidx++){
        int *plane = buf1 + pidx*TEST_W*TEST_H;
        thpool_add_block(thpool, ^{
            for(int yidx = 0; yidx < TEST_H; yidx++){
                for(int xidx = 0; xidx < TEST_W; xidx++){
                    plane[yidx*TEST_W + xidx] = pidx*4096 + (yidx + xidx);
                }
            }
        });
    }

在個人使用的 Quad-Core A8-5545M 平台得到了以下結果
single thread - 34832 us
4 threads - 13129 us

得到了 2.65 倍的加速