2020q3 Homework10 (quiz10)

contributed by < RusselCK >

tags: RusselCK

Arm 處理器 & dynamic programming 練習題

Q1. 彩色圖片轉灰階

• ARM NEON 範例
• Neon Intrinsics

使用 float 來保存像素

#include <stdint.h>
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

uint8_t *to_rgb(const float *m, int w, int h, uint8_t *rgb)
{
    int size = w * h;
    const float *ptr0 = m + (0 * size);
    const float *ptr1 = m + (1 * size);
    const float *ptr2 = m + (2 * size);
    uint8_t *ret = rgb;

#define SATURATE_CAST_UCHAR(X) (uint8_t) MIN(MAX((int) (X), 0), 255);
    for (int remain = size; remain > 0; remain--) {
        rgb[0] = SATURATE_CAST_UCHAR(*ptr0);
        rgb[1] = SATURATE_CAST_UCHAR(*ptr1);
        rgb[2] = SATURATE_CAST_UCHAR(*ptr2);
        rgb += 3;
        ptr0++, ptr1++, ptr2++;
    }
#undef SATURATE_CAST_UCHAR

    return ret;
}

針對 Aarch64 (Arm 64-bit) 架構 (假設為 little-endian) 的程式碼

#include <arm_neon.h>
float *rgb_to_gray(const uint8_t *rgb, int w, int h, float *m)
{
    const uint8_t Y_shift = 8;
    const uint8_t R2Y = 77, G2Y = 151, B2Y = 28;
    float *ptr = m;
    int size = w * h;

    int nn = size >> 3;
    int remain = size - (nn << 3);

    uint8x8_t _R2Y = vdup_n_u8(R2Y);
    uint8x8_t _G2Y = vdup_n_u8(G2Y);
    uint8x8_t _B2Y = vdup_n_u8(B2Y);

    for (; nn > 0; nn--) {
        uint8x8x3_t _rgb = vld3_u8(rgb);

        uint16x8_t y16 = vmull_u8(_rgb.val[0], _R2Y);
        y16 = vmlal_u8(y16, _rgb.val[1], _G2Y);
        y16 = vmlal_u8(y16, _rgb.val[2], _B2Y);
        y16 = vshrq_n_u16(y16, Y_shift);

        float32x4_t _ylow = vcvtq_f32_u32(vmovl_u16(vget_low_u16(y16)));
        float32x4_t _yhigh = vcvtq_f32_u32(vmovl_u16(vget_high_u16(y16)));

        vst1q_f32(ptr + OFFSET1, _ylow);     // OFFSET1 = 0
        vst1q_f32(ptr + OFFSET2, _yhigh);    // OFFSET2 = 4

        rgb += 3 * 8, ptr += 8;
    }

    for (; remain > 0; remain--) {
        *ptr = (rgb[0] * R2Y + rgb[1] * G2Y + rgb[2] * B2Y) >> Y_shift;
        rgb += 3, ptr++;
    }

    return m;
}

Q1. 整合 libattopng，輸出 RGBA 和灰階的 PNG 圖片

Set up ARM playground

• How to set up an ARM64 playground on Ubuntu 18.04

• How to launch ARM aarch64 VM with QEMU from scratch.

• 確認是否準備成功

$ uname -m         
aarch64            

• lab0 - 開發環境設定

• Linux Command 命令列指令與基本操作入門教學
• GNU Debugger Tutorial

• git 上傳

• Git 使用教學
• GitHub 設定指引

$ git add .
$ git status
$ git commit -m "..."
$ git push

ImageMagick

• Install ImageMagick from Source

$ sudo apt-get install imagemagick

• Getting started with ImageMagick

libattopng

Usage
Using libattopng is as simple as adding both libattopng.h and libattopng.c to your project.

開始作業

• /quiz10/rgb_to_gray.c

編譯

$ gcc -o rgb_to_gray rgb_to_gray.c -mfpu=neon

出現錯誤

In file included from rgb_to_gray.c:3:
In function ‘vshrq_n_u16’,
    inlined from ‘rgb_to_gray’ at rgb_to_gray.c:30:9:
/usr/lib/gcc/arm-linux-gnueabihf/8/include/arm_neon.h:4394:22: error: argument 2 must be a constant immediate
   return (uint16x8_t)__builtin_neon_vshru_nv8hi ((int16x8_t) __a, __b);
                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Q1. 引入 loop unrolling 和 prefetch 指令，嘗試改進 NEON 程式碼效率

Raspberry Pi 4 B

• Installing operating system images
• [基礎] 從序列埠登入到 Raspberry Pi

  透過 USB 轉 TTL 序列傳輸線，就可以在不需要螢幕和鍵盤滑鼠的情況下登入 Raspberry Pi

  • PL2303 Windows Driver Download

• 如何在沒有螢幕或鍵盤的情況下設置Raspberry Pi
• [基礎] 以 VNC 和 Raspberry Pi 連線
• 如何设置树莓派 VNC 的分辨率

Prefetch

• 数据预取 __builtin_prefetch()
• How to use pld instruction in ARM

Q2. LeetCode 1617. Count Subtrees With Max Distance Between Cities

給定 n 個城市，編號為從 1 到 n，再給予一大小為 n−1 的陣列 edges，其中 edges[i]=[ui,vi] 表示城市 ui 和 vi 之間存在雙向邊。
題目保證任意城市之間有唯一的路徑，也就是說所城市構成一棵樹 (tree)。

一棵子樹 (subtree) 是上述所有城市的子集，在子集中，任意城市間可透過子集的其他城市和邊到達。
兩個子樹被認為不一樣的條件是，至少有個城市在其中一棵子樹中存在，卻又不存在於另一棵子樹中。

給定 d 範圍介於從 1 到 n−1，請你找出城市間 最大距離 恰好為 d 的所有子樹數目。

請你回傳一個小為 n−1 的陣列，其中第 d 個元素 （下標從 1 始） 是城市間 最大距離 恰好等於 d 的子樹數目。

兩個城市間 距離 定義是，它們之間需要經過的邊的數目。

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define MIN(a, b) (((a) < (b)) ? (a) : (b))

#define ITERATE(i, begin, end) \
    for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
  //for (int i = (begin); i < (end); i++)
    
int *countSubgraphsForEachDiameter(int n,
                                   int **edges,
                                   int edgesSz,
                                   int *edges0sz,
                                   int *rsz)
{
    uint8_t d[n][n]; /* distance */
    memset(d, 0xFF, sizeof(d));

d[n][n] : 任兩個城市的距離

• #18 : 距離初始為
  $\mathrm{\infty }$

  實際上只要大於 n-1 即可

• d[i][j] = d[j][i]，應該可以有更節省空間的方式

    uint16_t conn[n];
    ITERATE (i, 0, n)
        conn[i] = 1 << i;

conn[n] : 與城市n 相連的 bitmask

• #20、21 : (初始) 城市n 必定和自己相連

    for (int z = 0; z < edgesSz; z++) {
        int *e = edges[z];
        int u = e[0] - 1, v = e[1] - 1;
        d[u][v] = d[v][u] = 1;
        conn[u] |= 1 << v, conn[v] |= 1 << u;
    }
    

從 edges[] 中得到相連狀況並更新 d[][] 和 conn[]

• edges[z] 的內容是 1-indexed，因此需要 -1 改成 0-indexed

    ITERATE (k, 0, n) 
        ITERATE (i, 0, n)
            ITERATE (j, 0, n)
                d[i][j] = MIN(d[i][j], d[i][k] + d[k][j]);

更新 d[][]，將 兩步 以上可達的兩個城市的距離記錄下來

• 更新後，若 d[i][j] 仍為 0xFF，代表 城市i 無法到達 城市j，反之亦然

• 這部分還有更省時的作法嗎?

    int *rv = calloc(n - 1, sizeof(int));

rv : 要回傳的陣列

calloc(n - 1, sizeof(int)) : 配置 n - 1 個 int 的陣列，並初始為 0

• int *rv = calloc(n - 1, sizeof(int)); 可以改寫成下列形式嗎?

int rv[n - 1];
memeset(rv, 0, sizeof(rv));

• 不行，會出現 runtime error: load of null pointer of type 'int' 的錯誤

參考資料:

• runtime error: load of null pointer of type 'const int' 错误提示

窮舉法 + DFS/BFS

    ITERATE (S, 1, (1 << n)) {

窮舉所有的子樹 (bitmask 為 S)

        int ctmp = 1 << __builtin_ctz(S);
        while (1) {
            int conn_nxt = ctmp; 
            ITERATE (d, 0, n)
                if ((ctmp >> d) & 1)
                    conn_nxt |= conn[d];
            conn_nxt &= S;
            if (COND1) // COND1 = conn_nxt == ctmp
                break;
            ctmp = conn_nxt;
        }
        if (COND2) // COND2 = ~ctmp & S
            continue;

判斷 S 是否為合法的子樹 ( 即 是否為無環連通圖 )

BFS 非遞迴版本

• ctmp : 目前這層 ( k 步內 ) 可以走訪到的城市
• conn_nxt : 下一層 ( (k + 1) 步內 ) 可以走訪到的城市

#36 : 將 S 中編號最小的城市當作 root，並納入 ctmp
#39 ~ 41 : 走訪目前這一層可到的城市 (ctmp)，並將下一層可以走訪的城市納入 conn_nxt
#42 : conn_nxt &= S : 將下一層可走訪的城市先縮在 S 有涵蓋的城市
#43、44 : 若 conn_nxt == ctmp， 代表已經走訪完所有可走訪的城市，可以跳出 BFS
#45 : 若否，則 conn_nxt 設置成下一層的 ctmp

#47、48 : 若 ~ctmp & S ，代表 S 並非無環連通圖，即不為合法子樹

        uint8_t ret = 0;
        ITERATE (i, 0, n)
            if ((S >> i) & 1)
                ITERATE (j, 0, i)
                    if (((S >> j) & 1) && (ret < d[i][j]))
                        ret = d[i][j];
        if (!ret)
            continue;
        rv[ITER]++; //ITER = --ret
    }

找出 S 中的最長距離 (ret)，並更新 rv[--ret]

--ret 用意 : 改成 0-indexed

    *rsz = n - 1;
    return rv;
}

Q2. 進階題 (更有效率的實作)

Dynamic programming on tree