正體中文資訊考古 - Microsoft Office 4.2 + 自然注音 3.11

Microsoft Office 4.2 中文版搭配自然注音輸入法, 

在小弟中學求學時期算很潮的軟體工具, 

如果有台噴墨印表機可以列印資料算是很前衛了.

個人那時很多的文件與資料準備, 

甚至到高中升大學的一些推甄/保送的文件都是這樣的環境趕出來的.

前一陣子因為找 OS/2 4.0 中文資訊而發現到, 

20~30 年前時代的資訊相當多已亡佚, 

看到很多國外年代久遠的軟體在 archive.org 都有上傳, 

很多人應該不希望那些就這樣只留在記憶之中, 

程式與人的使用與互動之間形成了生活與回憶. 

很可惜的台灣做相關收藏與整理的人並不多, 

這些生活足跡只能在新時代中慢慢流失.

 

下午與同事分享過當然那些日子已經離去很久, 

也是網路尚未發達的時代, 隨著新一代的網路服務/軟體的推陳出新, 

舊世代的軟體, 特別是那些有時代意義的中文化或是本土商的軟體, 

都慢慢隨著時間而逝去, 

除了少有人有動機從舊媒介上取下之外, 

從 Y2K 前後設立網站的關閉到空間消失, 

甚至每一次的搬家與整理, 

那些曾經那麼熟悉的事物, 

很可能很大一部份就因此不復重現, 

但其實它們是台灣文化的一部份, 

也是台灣資訊發展的歷史一環. 

能讓它們能展示運作會比只有 Wikipedia 上的只留一行註解來得有意義的多.

 

接著會嘗試把個人熟悉與持有的 CD or 資訊找出, 

分享或上傳 archive.org, 做個紀錄那段時代的見證者

Office 4.3 正體中文版

自然注音輸入法 3.11

 

 

 

 

  

正體中文資訊考古 - OS/2 T4.0 正體中文版

OS/2 4.0 正體中文版

後續會陸續把中文相關的檔案上傳 (4.0 的附屬光碟, 3.0 中文版光碟)

主要是最近找了一下 archive.org

發現 OS/2 4.0 原文的東西相當多

 

https://archive.org/details/IBMOS2Warp4Collection

像是這個 collection, 有人把很多語言版本都上傳了(但是沒有正體中文版)

加上近年其實可以感受到原有的網路資訊逐漸消失

為了做一些歷史資料保存與見證

就花了點時間把 OS/2 T4.0 iso 檔案上傳了

T4.0 真的就是懷舊了, 一點可用性都沒有

原以為更新到 fixpack 5 (OS/2 4.0 最後的 fixpack)就有機會能夠使用 SVGA

但 ... 果然我想太多了 (是說裡面的 telnet 還可以用)

裝了 Netscape Communicator 4.61, 但是因為 https 加密演算不支援, 加上也不支援 HTML4 所以寸步難行

 

話說 eCS 1.2 中文版不難找, 

主要是版本蠻新的, 

有些可能還有在使用 (甚至還能安裝 GCC 9.2)

所以不管是 eCS or OS/2 MCP2/4.52 暫時決定還是不要放到 archive.org 上

 (也的確 archive.org 上相關檔案不多)

 

 

 

 

 

 

 

以 halide 實作 block matching 演算法 - block matching with Halide language

由於 multi-frame 與 multi-view 的影像處理需求的提升,  image alignment 的需求日益提升, 而相關的演算也很多, 像是基於 pyramid-based, 9-steps, hexagon or diamond search. 而大小的部份也有著 match / apply 不同大小的 non-local means, 然而這些演算的基本還是源自於特定 search window 的 block matching. 本文重點在於以 Halide language 描述 matching algorithm, 至於 scheduling 的優化不在此文重點. (或是擇日分享)

Step 0 - 輸入格式 (input format - single channel as example)
首先假設要處理的是 image 的某個 channel, multi-channel 的影像則僅是套用到多個 frame 或是以 channel 輸入, 同常有一張是 base image 這裡以 in 代表, 另一張為 reference image 以 ref 代表.

Step 1 - 邊界處理, 用來避免 search block 範圍超過邊界 (boundary handling, to avoid error of part of target block is out of frame)

Func input = BoundaryConditions::repeat_edge(in);
Func refer = BoundaryConditions::repeat_edge(ref);

Step 2 - 用以代表 block 內所有 input 與 reference 的 pixel 的座標 (setup the RDom that represent all pixels of corresponding input & refer block)

// the position in motion vector output table

Var bid_x, bid_y;

// variable for motion vector

Var mv_x, mv_y;

RDom rblk(0, BLOCK_SIZE, 0, BLOCK_SIZE)
// position in input frame
Expr blk_x = (bid_x * BLOCK_SIZE) + rblk.x;

Expr blk_y = (bid_y * BLOCK_SIZE) + rblk.y;
// position in reference frame

Expr ref_x = blk_x + mv_x;
Expr ref_y = blk_y + mv_y;

Step 3 - 建立比對標準, 這裡以 SAD 為例 ( matching criteria calculation (Sum of Absolute Difference(SAD) as example))

Expr in_val = i16(input(blk_x, blk_y);

Expr ref_val = i16(refer(ref_x, ref_y));

Func sad;

sad(mv_x, mv_y, bid_x, bid_y) = sum(abs(in_val - ref_val));

Step 4 - 搜尋與輸出, 這裡是透過 RDom + argmin 搭配來做比對搜尋並取得結果 (search and output, here we use RDom + argmin for matching and finding)

// setup search window
RDom search_win(-range/2, range, -range/2, range);

// argmin will find the one in search_window which get minimal sad.

Tuple me = argmin(sad(search_win.x, search_win.y, bid_x, bid_y));

// output the motion estimation result to MV table

Var ch;

out_mv(bid_x, bid_y, ch) = me[ch];

比較不直覺的地方在於兩個 RDom 套用的層次不同, 第一個 RDom 用來計算 matching criteria, 二個 RDom 是用來作為 motion estimation 尋找 mv, 總之這是以 search window 的方式作窮舉的 block matching 定義, 然而可以延伸與改進用在一開始所說的各種 matching 演算法上

撰寫各 x86 CPU 平台適用的 compiler vector extension code

在套用 gcc / clang 的 -ftree-vectorize or compiler vector extension 時來產生適當的 SIMD optimization 時,  同時會產生一個問題 - 當編譯時套用的 architecture 參數(e.g.: -mavx2) 所使用的指令集與運作時的 CPU 不一致時可能會出現 SIGILL (illegal instruction) 的問題. 過往可能會採用 CPU feature detection + dispatching code 的撰寫, 大致上邏輯如下:

// AVX-512 version

void __foo_avx512(void){  ... }

// AVX version

void __foo_avx2(void){ ... }

// SSE4 version

void __foo_sse4(void){  ... }

// C version

void __foo(void){  ... }

void foo(void)

{

    if(_avx512_available())

        __foo_avx512();

    else if(_avx2_available())

        __foo_avx2();

    else if(_sse4_available())

        __foo_sse4();

    else

        __foo();

}

這是過去長久以來很平常的作法, 而最近研究在接觸 Clear Linux, 研究了一下 Intel 採用的方式, 發現了有趣的事(這些 Intel 都有在 2016 年的簡報 - Improving Linux Performance with GCC latest technologies 中說明), 主要是 gcc 4.8 中已新增了 Function Multi-Versioning (FMV)的功能, 能透過函數屬性更方便地做到原本的目的, 以上述的例子來說就會變成:

// AVX-512 version

__attribute__ ((target ("avx512f")))

void foo(void){  ... }

// AVX2 version

__attribute__ ((target ("avx2")))

void foo(void){ ... }

// SSE4 version

__attribute__ ((target ("sse4.2")))

void foo(void){  ... }

// C version

__attribute__ ((target ("default")))

void foo(void){  ... }

使用 FMV 功能的好處首先所有的 function 都是相同的名稱, 僅是屬性中的 target 不同, 而GCC 會自動產生偵測 CPU 功能並從中選擇對應 foo 的 code, 這點可以省去維護上面 dispatching code 的問題(若有多個函數,  增刪都會是很冗長的工作). 使用 __attribute__ ((target ("TARGET_NAME"))) 的語法方式目前已被 gcc / icc / clang 所採用.

然而並不是所有人都有心力以 SIMD ISA 去實作版本, 這時複製多份相同的 C code 來做不同 SIMD ISA 的 auto-vectorization 似乎不是很實際的方式, 因此 gcc 進一步提供了有趣的屬性功能 - target_clones:

// C version

__attribute__ ((target_clones ("avx512f", "avx2", "sse4.2", "default")))

void foo(void){  ... }

而 GCC FMV 功能亦能夠與 compiler vector extension 合併使用, 因此以 compiler vector 實作後函數可以使用上述 target_clones 的方式, 如此 compiler 會自動針對不同的 SIMD ISA 生出多版本的, 以個人常用來教學的 tiled 8x8 gemm 來說就會像是:

#define TSIZE 8
#if defined (__clang__)
typedef float vfloat __attribute__((ext_vector_type(TSIZE)));
#else
typedef float vfloat __attribute__ ((vector_size (TSIZE*4)));
#endif

__attribute__ ((target_clones ("avx512f", "avx2", "avx", "sse4.2", "default")))
void gemm_vec(float *a, int sa, float *b, int sb, float *c, int sc)
{
    vfloat vb[TSIZE];
        for(int y = 0; y < TSIZE; y++){
            vb[y] = *((vfloat*)(b + sb*y));
        }
        for(int y = 0; y < TSIZE; y++){
            vfloat vc = *((vfloat*)(c + sc*y));
            vfloat va = *((vfloat*)(a + sa*y));
                for(int x = 0; x < TSIZE; x++){
            vc += va[x] * vb[x];
                }
                *((vfloat*)(c + sc*y)) = vc;
        }
}

接著以 gcc 編譯:

$ gcc -O3 -shared mm.c -o libgemm.so

透過 objdump 觀察

$ objdump -t libgemm.so

可以看到中間有如下的輸出:

0000000000001720 l     F .text    0000000000000c96 gemm_vec.default.4
00000000000023c0 l     F .text    00000000000005df gemm_vec.avx512f.0
00000000000029a0 l     F .text    00000000000005df gemm_vec.avx2.1
0000000000002f80 l     F .text    000000000000060c gemm_vec.avx.2
0000000000003590 l     F .text    0000000000000c95 gemm_vec.sse4_2.3

此外值得一提的是在 2019 年初 Clear Linux 計劃中 Intel 釋出了一個 FMV patch generator, 透過 make-fmv-patch 這個工具能針對  C/C++ code 自動產生對應的 FMV 屬性 patch, 套用後重新編譯即可產生一體適用的 SIMD optimized libraries / executables

Halide 與處理器架構上匹配性問題心得

老生常談, 老狗學不會新把戲 - 今晚來談談 Halide 與架構的匹配性

這幾年間 Halide 是個人常用的工具之一
上週與朋友一同用餐, 言談間討論到了 Halide
其中多少談論到一些處理器比較的部份
這文章分享的並非什麼新東西或是驚人的發現
基本上於不同地方的私下討論個人都早已分享過
在此僅是反覆說明自己對一件事情的看法 - 為何 Halide 套用在不同計算架構平台上效益落差很大

這個問題在不同場合, 不同的對象一同討論過(甚至當時在 MTK 工作時分析架構於內部都提及過)
個人的觀點是 - 不同平台上 locality 這部份的影響 (另外的 redundant work / parallelism 多數架構上這都不構成問題)
一言以蔽之 - memory model / architecture
必須說 locality 是 Halide 對於計算考量核心精神中 scheduling 三角的一角, 對於 Halide 而言而能凸顯這面向的還是以 transparent cache 為主, 任何需要透過搬動 (無論是額外的 SIMD, 俱備 DMA 與否) 來 reuse data 的 scratchpad / TCM ... 等等, 非 cache based 的方案都面臨幾個問題:

• reuse data 的額外開銷, 而且這部份隨著要使用的資料愈多 cost 也愈高 (house keeping code, 2D/3D DMA usage ... etc)
• cascade or fused kernel 每增加一級, data layout 的安排複雜度(無論對 compiler or coder 而言)呈指數增加
• 再者一旦決定了 scheduling, 基本上也不俱備 scalability. 增加 size 無法改善效率, 但是減少 size 會讓原有的 code 無法運行. (cache-based 架構則是會有隨著 size 不同而呈現的效能曲線)

這幾個因素讓 Halide 在一些架構上, 在這個 Halide 最重要概念的三角形中的 Y 軸 (也就是 locality) 僅僅存在著數量非常有限的選擇, 最終這個 scheduling space 的三角形因為 control & complexity 而退化為小面積, 線或更甚者為數點. 而最終還是會落入需要經驗導向的 flow 調整, 別出心裁的發想, 特殊指令的套用 .. 等等

 

 

clang & gcc vector extension 探究心得

這文章換整了把一個以前納悶許久的功能做了研究與釐清後的心得 - vector selection in GCC / Clang

在 GCC / Clang 的 vector extension 中 "?:" operation 的使用, 基本上搜尋 "gcc vector extension" or "clang vector extension" 你一定會看到文件對於 ?: 這操作寫著是支援的 甚至 clang 的文件 這麼列著.

 

 

然而按照常用的 CL 使用方式去寫 code 會發現沒有辦法編譯過.
對於 OpenCL 中的使用, 請參考 Programming with OpenCL C 一書的 Vector Operators - Conditional Operator

對於 gcc/clang 支援的 ?: 是指 a ? b : c 這樣的計算中
的 a 必須是 scalar type, b, c 可以是 scalar or vector ... 因此如此是無法達到最好用的 vector element selection 功能, 也就是當我們撰寫 c = a > b ? a : b; 時於 vector 上等同於:

u32x8 c = {
    a[0] > b[0] ? a[0] : b[0],
    a[1] > b[1] ? a[1] : b[1],
    a[2] > b[2] ? a[2] : b[2],
    a[3] > b[3] ? a[3] : b[3],
    a[4] > b[4] ? a[4] : b[4],
    a[5] > b[5] ? a[5] : b[5],
    a[6] > b[6] ? a[6] : b[6],
    a[7] > b[7] ? a[7] : b[7],
};

以這個例子來說當宣告:

u32x8 a, b, c;
...
c = a > b ? a : b;

對於 x86 AVX ISA 而言你會希望 compiler 能使用下列 intrinsics / instruction:
_mm256_max_epu32 / vpmaxud

但是很不幸的是在 gcc / clang 這樣的 code 無法被編譯, 在不考慮直接使用 AVX intrincs 的情況下, 搜尋後會得到兩個可能的建議

1. 使用 loop 讓 compiler 優化, 也就是:**

for(int i = 0; i < 8; i++)
    c[i] = a[i] > b[i] ? a[i] : b[i];

如此你會得到如下圖的使用 loop 結果, 雖然有使用 AVX register, 但是計算上完全沒有好處

 

 

2. 這個結果比較需要技巧才會找到, 也就是 bitwise operation:**

u32x8 d = (u32x8)(a > b);
u32x8 c = (d & a) | (~d & b);

如此你會得到圖三的結果, 以 code generation 的結果這可能是相對較好的方式

 

然而這完全比不上直接使用 avx intrinsics 的下圖的結果:

u32x8 c = _mm256_max_epu32(a, b);

g++/clang++

然而還是有最後希望 - GCC/g++, 事實上 gcc 文件中如下圖有提到 C++ 模式支援 element-wise

由於個人印象中並沒有這樣的方式, 查了一下 是 GCC 5 / Clang 10 開始支援這樣的模式 (只能說在最需要使用的時候 android gcc, Google 只用到了 4.9 ... 之後的版本 vector extension 沒特別去用, 加上逐漸重心轉到使用 clang), 如此可以支援一開始期望的語法, 而且 code generation是很漂亮的(g++:下圖1/clang++:下圖2, g++ 的比較好), 非 clang 不可時透過 g++/clang++ 編譯產生 .s 再整入 clang project 是唯一可以考慮的作法 (否則就是 code 可讀性與移植性變差 + 努力查 intrinsics table 了)

1. 

 

2.

 

除此之後後續做了些實驗額外得知了一些限制/資訊

gcc & clang compatibility

在先前 gcc / clang 各自有著自己的 vector extension 與宣告方式, 個人也針對兩者做了不同宣告, 然而有趣的地方是實驗過程中, 曾經忘了切換, 然而可以順利編譯過, 這也表示 gcc / clang 互相吃了對方的 vector extension 的宣告方式, 因此個人一開始以為在各自 compiler 上兩個 vector extension 應該是互通的. 這點在昨日得知 clang 在實作時會考量儘量與 gcc 一致, 猜想 gcc 在一些特性上也對 clang 做了類似的考量.

OpenCL-like vector swizzle

這是被詢問的問題, 因此注意到了差異, 基本上只有 clang 提供了接近 OpenCL 的 vector swizzle 方式:

u32x4 a, b, c;
...
c.s02 = a.s02; // or c.xz = a.xz;
c.s13 = b.s02; // or c.yw = b.xz;

當然還可以針對特定 vector lane 作 value assign.
比較麻煩的是 initial value, clang 並沒有提供如同 OpenCL 的彈性, 而且必須是以 { ... } 的方式一一擺放, 而不如 OpenCL 以 ( ... ) 且能夾雜大小不同的 vector 作為數個數值. 在 clang 上要使用這個特性, 必須使用 clang 專屬的 vector extension 宣告方式.

vector as array

最早是 clang 開始提供的, 而且不只是 vector extension, 對於 SIMD intrinsics 的 data type clang 都支援. 這個功能相當實用, 在 android 7 時期導入 clang 可以說幫了大忙, 這點對於 C Model 與 SIMD 版本實作的轉換與驗證簡化不少.
使用上類似:

u32x4 a, b, c, vout;
...
vout = fa*a + fb*b + c;
for(int i = 0; i < 4; i++){
    assert(out[ofs+i] == vout[i]);
}

而後續 gcc 也在 vector 支援了這個功能, 然而必須使用 gcc 自己的 vector extension 宣告方式

Sampling v. tracing 閱讀心得

對 2016 的 "Sampling v. tracing" 演講心得紀錄文有點相見恨晚, 昨日至今零碎時間內快速地研讀了兩次, 因此附上一下粗略心得分享:
系統效能分析是困難的, 近日因為效能分析方向自己想做的事情, 加上對目前在各大討論網站提倡的主流方法有一些疑惑沒解開, 因此做了一些 Google 搜尋而找到此篇
當然現在主流是 perf / eBPF 這類 sampling-based 分析工具, 而這些也是各大討論區與網站主要提倡的工具, 然而真正地面對效能分析時, 很多時候必須弄清楚要發覺與處理的的問題本質為何?

這篇首先指出一個關鍵:
"Sampling profilers, the most common performance debugging tool, are notoriously bad at debugging problems caused by tail latency because they aggregate events into averages. But tail latency is, by definition, not average."
再者在許多問題的分析上, 從搜尋結果有相當高的可能會得到使用 sampling profiler 的結果, 然而因為對要處理的問題了解不足的結果, 直接套用建議後會發現: "But tools like OProfile are useless since they'll only tell us what's going on when our RPC is actively executing. What we really care about is what our thread is blocked on and why."
在文中舉了一個 Google 內實際發生的例子 - disk read latency 分析, 看似正常的分佈圖然而有著不合理的高延遲存在, (BTW 個人特別喜歡這段的一句 "each of you think of a guess, and you'll find you're all wrong"), 進而發現長時間廣泛存在於系統層面的問題. 而修正的獲益足以支付分析者十年以上的人事成本. 而這分析的例子主要在於提出 - "is this because of some flaw in existing profilers, or can profilers provide enough information that you don't need to use tracing tools to track down rare, long-tail, performance bugs?"
在討論 sampling limitation 之後, 文末段最後有3個問題, 其中最引人注目應該是:
3. Why are sampling profilers dominant?
除了說明認為未來 profiler 會愈來愈像 tracing tool 外, 也直接的回答了 - "but if we look at the state of things today, the easiest options are all classical profilers.", perf 提供運作的時間, 其他的基本工具提供消耗了多少記憶體, 結由這兩個數值能處理主要的效能問題.
此外也指出將現有公開工具湊在一起追蹤效能問題將會是個很困難的體驗, 文中提了一個實際的 case 做例證.
對於 tracing 的問題在於建立的困難度 - 對此通常有兩個選擇
1. 自己實作 - 基本上當然是 event + timestamp, 然而這當中還有該如何針對你的問題建立真的需要存下的 trace.(像是 lock & waiting) 來減少 overhead.
2. 從既有工具挑選你所需要的 - 然而不幸的是這些 overhead 成本都很高, 因此無法在特定規模以上在背景運作來復現出現的問題.
個人觀點:
1. sampling profiler 主要還是建立在 "比較" 的基準上找尋問題點, 通常是版本變換造成行為不同的系統問題. 以此能以成本較低的方式找出, 但若認為一個 workload 是 "正常" 基本上要找出優化的是不容易的, 這類問題像是 task dispatch 與 thread synchronization.
2. profiling budget 觀念的建立 - 為了能在實際發生問題的當下作用而非事後的分析(因為很多可能是實驗環境而無法 reproducible), 對於產生需要的資訊建立 overhead 要求. 在此之下建立能達成目的的 framework.
3. 統計數據的解讀能力 - 對整體與極端數值的解讀能力是分析問的的根本. 文中對於 disk latency 的 histogram 解釋能力即是一例.
4. sampling 是個好工具, 但必須了解其極限, 以及發現可能問題開如何找下一步