2020q3 Homework6 (quiz6)

contributed by < Holycung >
2020q3 Homework6 (quiz6) 題目

測驗 1

題目

bfloat16 浮點數格式由 Google 公司發展，最初用於該公司第三代 Tensor 處理單元 (Cloud TPU)。bfloat16 的主要想法是提供 16 位元浮點數格式，其動態範圍與標準 IEEE 754 的 FP32 (Single-precision floating-point format) 相同，但精度較低，相當於指數區和 FP32 保持相同的 8 位元，並將 FP32 的 fraction 區域縮減到 7 位元。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

下列是個轉換程式:





















float fp32tobf16(float x) {
    float y = x;
    int *py = (int *) &y;
    unsigned int exp, man;
    exp = *py & 0x7F800000u;
    man = *py & 0x007FFFFFu;
    if (!exp && !man) /* zero */           
        return x;
    if (exp == 0x7F800000u) /* infinity or NaN */
        return x;

    /* Normalized number. round to nearest */
    float r = x;
    int *pr = (int *) &r;
    *pr &= BB1;
    r /= 256;
    y = x + r;

    *py &= BB2;
    return y;
}

作答

先了解一下 bfloat16 的目的跟特點。

參考 BFloat16: The secret to high performance on Cloud TPUs 自行擷取翻譯中文如下。

這個特製畫的浮點數格式全名叫做 Brain Floating Point Format 簡稱 bfloat16，名字構想來自 Google 人工智慧團隊 "Google Brain"。

Google 為了因應 ML 的計算量日益龐大，為了加速運算時間發展出客製化的處理器叫做 Tensor Processing Units (TPU)，使用更低的成本給出更高的效能

為了確保 bfloat16 會和 FP32 有相同的 exponent 大小和相同的行為對於 underflowd, overflows, NaNs。但是 bfloat16 處理 denormals 會有不同，在 bfloat16 會直接被 flush 成零。

可以在 tensorflow 原始程式碼當中看到 bfloat16 的使用

第 5~6 行是取出 exponent 和 mantissa 的部分，第 7~10 行則是判斷是否為 zero、infinity、NaN，是了話就回傳原本的值。






    /* Normalized number. round to nearest */
    float r = x;
    int *pr = (int *) &r;
    *pr &= BB1;
    r /= 256;
    y = x + r;

接下來處理 normalized number，要處理 rounding 的部分，要做 0 捨 1 入到 fraction 的最低位，也就是從最低位開始算的第 17 個位元，看到第 17 行 y = x + r，所以推測我們這邊的 r 就應該是
r = ( SEEEE EEEE 0000 000 1000 0000 0000 0000 )

\begin{aligned} r & = 0.00000001 \times 2^{E - b i a s} \\ = 1 \times 2^{(E - b i a s) - 8} \\ = (1 \times 2^{(E - b i a s)}) \div 2^{8} \end{aligned}

一開始變數

r = 1. F \times 2^{E - b i a s}

，第 15 行是先把前面的 sign bit 和 exponent 的部分保存下來，

r = 1 \times 2^{E - b i a s}

，所以 BB1 = 0xff800000，然後再做 r /= 256，要注意的是這邊浮點數的除法不是移位，而是把 exponent 減掉，所以

r = 1 \times 2^{(E - b i a s) - 8}

，最後把處理好的 r 加上原本的 x，y = x + r，就完成了 rounding。

最後要把最後 16 bits 全部變成 0，所以第 19 行 *py &= BB2， BB2 = 0xffff0000。

延伸問題

TODO

改進上述程式碼，實作 DP/SP 轉換程式，並針對 BFloat16 撰寫測試程式，應儘量涵蓋有效的數值輸入和輸出範圍;
考慮批次轉換 FP32/FP64 為 BFloat16 的需求，請改進上述程式碼，得以提高轉換的效率;

測驗 2

題目

考慮以下 ring buffer 的實作:













































#define RINGBUF_DECL(T, NAME) \
    typedef struct {          \
        int size;             \
        int start, end;       \
        T *elements;          \
    } NAME

#define RINGBUF_INIT(BUF, S, T)             \
    {                                       \
        static T static_ringbuf_mem[S + 1]; \
        BUF.elements = static_ringbuf_mem;  \
    }                                       \
    BUF.size = S;                           \
    BUF.start = 0;                          \
    BUF.end = 0;

#define NEXT_START_INDEX(BUF) \
    (((BUF)->start != (BUF)->size) ? ((BUF)->start + RB1) : 0)
#define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + RB2) : 0)

#define is_ringbuf_empty(BUF) ((BUF)->end == (BUF)->start)
#define is_ringbuf_full(BUF) (NEXT_END_INDEX(BUF) == (BUF)->start)

#define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end]
#define ringbuf_write_skip(BUF)                   \
    do {                                          \
        (BUF)->end = NEXT_END_INDEX(BUF);         \
        if (is_ringbuf_empty(BUF))                \
            (BUF)->start = NEXT_START_INDEX(BUF); \
    } while (0)

#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]
#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);

#define ringbuf_write(BUF, ELEMENT)        \
    do {                                   \
        ringbuf_write_peek(BUF) = ELEMENT; \
        ringbuf_write_skip(BUF);           \
    } while (0)

#define ringbuf_read(BUF, ELEMENT)        \
    do {                                  \
        ELEMENT = ringbuf_read_peek(BUF); \
        ringbuf_read_skip(BUF);           \
    } while (0)

其測試程式如下:
























#include <assert.h>

RINGBUF_DECL(int, int_buf);

int main()
{
    int_buf my_buf;
    RINGBUF_INIT(my_buf, 2, int);
    assert(is_ringbuf_empty(&my_buf));

    ringbuf_write(&my_buf, 37);
    ringbuf_write(&my_buf, 72);
    assert(!is_ringbuf_empty(&my_buf));

    int first;
    ringbuf_read(&my_buf, first);
    assert(first == 37);

    int second;
    ringbuf_read(&my_buf, second);
    assert(second == 72);

    return 0;
}

請補完程式碼，使得測試程式得以正確執行。

作答

在看程式碼之前要先了解到一些 macro 的用法，在 macro 當中有使用到參數(arguments) 了話，要加上括號，引用 C/Macros 當中的例子，假設我們要用 macro 來實踐一個 square 的功能如下


#define Square(x) ((x)*(x))

如果我們使用這個 macro，Square(foo) 展開會變成 ((foo)*(foo))，注意到這邊有使用括號可以避免 operator precedence 的問題，如果沒有使用了話如下


#define BadSquare(x) x*x

如果我們使用 BadSquare(3+4) 將會展開成 3+4*3+4 導致錯誤的結果 19。

再來這邊有用到你所不知道的C語言：技巧篇提到的 do { ... } while(0) 巨集 是為了避免 dangling else 問題，也可以參考這篇 macro do{}while(0) 更詳細的解釋。

接下來了解到 ring buffer 是一個環狀的結構，通常會運用 start end 記錄下 buffer 位置，好處是當一個元素被使用(consumed)，其他元素不需要改動(shuffled around)，很適合用在 FIFO 的 buffer 中。

a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.

看到程式碼的部分。

RINGBUF_DECL(int, int_buf) 這邊的 DECL 代表 declare 也就是先宣告我們需要的結構體，會有 size、start、end、elements。
RINGBUF_INIT
- 初始化結構當中的變數，這邊第 10 行使用了 static，推測是因為靜態變數的存取範圍是 local scope，且其 lifetime 不會消失直到程式結束，所以在這邊用 buf 的指標指完之後，離開大括號後就不會存取到，也能避免撞名。
- 這邊可以注意到在初始化陣列大小 static_ringbuf_mem 是宣告了 S+1 的大小，這個我們在後面的時候會討論。
NEXT_START_INDEX、NEXT_END_INDEX 是把 start end 移動往下一個，如果超過 size 大小就回到 0，所以這邊 RB1、RB2 都是 1。
is_ringbuf_empty 如果 end 等於 start 代表 buffer 是空的。
is_ringbuf_full 如果下一個 end 等於 start 就代表 buffer 是滿的。
ringbuf_write 使用到兩個 macro
- ringbuf_write_peek 把新的 element 寫進 end 的位置。
- ringbuf_write_skip 把 end 更新到下一個 buffer 位置，然後這邊比較不直覺，會先判斷 is_ringbuf_empty，是的話會把 end 移到下一個。這邊我會把他理解成是 buffer 已經寫滿了，所以會覆蓋掉最舊的值讓 start 更新到下一個。
ringbuf_read 使用到兩個 macro
- ringbuf_read_peek 會去讀取 buffer 上面 start 位置的值，並放到變數 ELEMENT 當中。
- ringbuf_read_skip 把 start 更新到下一個 buffer 位置。

因此我們可以得知 start 指向要讀的位置，讀完再移動到下一個，end 永遠會指向空的位置，寫完之後就移到下一個空的位置，所以這邊我們會需要比給定的大小 S 再多一個空間，因此也可以解釋我們上面宣告了 S+1 大小的原因，用測試的程式來圖解一下整個流程。

先宣告一個大小為 2 的 ring buffer，所以陣列大小會是 3 個，初始化後都指向一開始的位置。

寫入 37。

寫入 72。這時候 buf 已經是滿的狀態，如果再寫入一個值假設是 3 如下圖。

此時，因為判斷 buf 已經滿了，所以把 start 往下一個，也就是覆蓋掉最開始的 37 的意思，所以這時候如果再做 read 了話就會得到 72 的值。

延伸問題

題目

研讀 Super Fast Circular Ring Buffer Using Virtual Memory trick，指出效能改善的機制並用 C99/C11 (可搭配 GNU extension) 重新實作;

作答

研讀了那篇文章，如果我們今天要實作，一次寫很多個的功能，最 naive 的版本是用一個迴圈，但是這樣可能會有過多 modulo 或是無效率的迴圈導致效率不佳(我們這邊的版本沒有使用到 modulo)。







#define ringbuf_write_array_for(BUF, ELEMENTS, SIZE)                \
    do {                                                           \
        for (int i = 0; i < SIZE; i++) { \
            ringbuf_write_peek(BUF) = ELEMENTS[i]; \
            ringbuf_write_skip(BUF); \
        } \
    } while(0)

因此我們這邊可以透過 memcpy 來取代迴圈，這樣只要用兩次 memcpy 就可以完成，實作如下。










#define ringbuf_write_array(BUF, ELEMENTS, SIZE, T)                \
    do {                                                           \
        size_t part1, part1_sz, part2_sz;                          \
        part1 = min(SIZE, (BUF).size + 1 - (BUF).end);             \
        part1_sz = part1 * sizeof(T);                              \
        part2_sz = SIZE * sizeof(T) - part1_sz;                    \
        memcpy((BUF).elements + (BUF).end, ELEMENTS, part1_sz);    \
        memcpy((BUF).elements, ELEMENTS + part1, part2_sz);        \
        (BUF).end = ((BUF).end + SIZE) % ((BUF).size + 1);         \
    } while(0)

接下來可以再繼續優化這個方法，最終只使用一次 memcpy。我們可以運用硬體的特性配置兩個連續的 virtual memory 空間，再 mapping 到同一個地址，圖示如下。

這個概念我們可以透過 mmap 來完成，相關的用法可以參考 mmap基礎概念，mmap 是一種內存(memory)映射(mapping)文件的方法，即將一個文件或者其它對象映射到進程的地址空間，實現文件磁碟地址和進程虛擬地址空間中一段虛擬地址的一一對映關係。

因此我們可以透過 mmap 把兩段連續相鄰的 virtual address 透過 mapping 到同一塊實體的地址，這樣就當我們要寫入的長度超過大小後，就可以直接寫下去，也就可以減少到只用一次 memcpy，詳細的實作如下。






























#define V_RINGBUF_INIT(BUF, S, T)                                             \
    do {                                                                      \
        const size_t pagesize = getpagesize();                                \
        size_t size = ((float)(S * sizeof(T)) / pagesize) * (pagesize + 1);   \
        const int fd = fileno(tmpfile());                                     \
        if (fd == -1) {                                                       \
            fprintf(stderr, "error on open temporary file");                  \
            exit(1);                                                          \
        }                                                                     \
        ftruncate(fd, size);                                                  \
        BUF.elements = mmap(NULL, 2 * size, PROT_NONE,                        \
                       MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);                   \
        if (BUF.elements == MAP_FAILED) {                                     \
            fprintf(stderr, "error on mapping");                              \
            exit(1);                                                          \
        }                                                                     \
        mmap(BUF.elements, size, PROT_READ | PROT_WRITE,                      \
                       MAP_SHARED | MAP_FIXED, fd, 0);                        \
        mmap(BUF.elements + size / sizeof(T), size,                           \
                       PROT_READ | PROT_WRITE, MAP_SHARED | MAP_FIXED, fd, 0);\
        BUF.size = size / sizeof(T);                                          \
        BUF.start = 0;                                                        \
        BUF.end = 0;                                                          \
    } while(0)                                                                \

#define v_ringbuf_write_array(BUF, ELEMENTS, SIZE, T)                        \
    do {                                                                   \
        memcpy((BUF).elements + (BUF).end, ELEMENTS, SIZE * sizeof(T));  \
        (BUF).end = ((BUF).end + SIZE) % ((BUF).size + 1);              \
    } while(0)

第 5 行 tmpfile() 會打開一個暫時的檔案直到程式結束，也就是我們的實體的位置，然後回傳 stream descriptor，再用 fileno() 把他轉成 file descriptor。
第 10 行 ftruncate() 是將檔案調整成指定的大小，對應我們需要的實際的地址空間。
第 11 行透過 mmap 的 MAP_ANONYMOUS 並且 fd 為 -1，要到一塊虛擬的 virtual address space，其大小是我們給定 buffer 大小的兩倍大。
第 17 行就是對剛剛拿到的 VAS 的第一段 map 到前面建立的實體檔案空間，第 19 行就是第二段 map 到同樣一個地方。

用以上三種版本來進行效能分析，先宣告大小為 1024 的 buffer，然後每次寫 1000 個進去 buffer 連續 100 次，詳細的程式可以參考 Github，結果如下圖。

可以看到 for 迴圈的版本效率最差，vas 的方法效率最佳，唯有再第一次寫入的時候會花上特別多時間，實驗了幾次都一樣，原因可能要詳細去看 mapping 的實作，或是再使用的時候都先初始 buffer。

下面是 buffer 大小改成 2048，也是一次寫入 1000 筆，連續做 100 次，結果與上述雷同。

測驗 3

題目

考慮到以下靜態初始化的 singly-linked list 實作:


















































#include <stdio.h>

/* clang-format off */
#define cons(x, y) (struct llist[]){{y, x}}
/* clang-format on */

struct llist {
    int val;
    struct llist *next;
};

void sorted_insert(struct llist **head, struct llist *node)
{
    if (!*head || (*head)->val >= node->val) {
        SS1;
        SS2;	
        return;
    }
    struct llist *current = *head;
    while (current->next && current->next->val < node->val)
        current = current->next;
    node->next = current->next;
    current->next = node;
}

void sort(struct llist **head)
{
    struct llist *sorted = NULL;
    for (struct llist *current = *head; current;) {
        struct llist *next = current->next;
        sorted_insert(&sorted, current);
        current = next;
    }
    *head = sorted;
}

int main()
{
    struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);
    struct llist *p;
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");

    sort(&list);
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");
    return 0;
}

其執行結果為:

9547
4579

請補完程式碼，使程式碼和執行結果相匹配。

作答

這題是你所不知道的C語言：技巧篇有提到的技巧，利用 compound literal 建立 static linked list。

可針對未知大小的 array/struct 初始化，也可以直接對特定位置的 array 或 struct 的內容賦值
compound literal 可以做 lvalue ，可以傳特定型別或自己定義的 struct

所以就先來看到 macro cons(x, y)。






#define cons(x, y) (struct llist[]){{y, x}}

struct llist {
    int val;
    struct llist *next;
};

這邊要先了解甚麼是 compound literal，根據 C 語言規格書 6.5.2.5 Compound literal。

C99 [6.5.2.5] Compound literals

The type name shall specify an object type or an array of unknown size, but not a variable length array type.

A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list.

If the type name specifies an array of unknown size, the size is determined by the initializer list as specified in 6.7.8, and the type of the compound literal is that of the completed array type. Otherwise (when the type name specifies an object type), the type of the compound literal is that specified by the type name. In either case, the result is an lvalue.

compound literal 的格式是 (){}，前面括號 () 中為型別名稱，後面接著大括號 {} 中是一個 list 的初始化，這樣會得到一個 unnamed object，其值為我們剛剛給的 initializer list。如果我們給定一個未知大小的陣列，大小會透過 initializer list 決定。

回來看 macro cons，型別名稱是 struct llist[]，initializer list 則是 {{y, x}}，陣列裡面只有一個物件，所以結構當中的 val 就是 y， *next 就是 x，再看到第 39 行就很好懂。


struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);

最裡面的 cons(NULL, A) 先建立了一個值為 A，next 指向 NULL 的 struct llist 物件。然後往外一層就是建立一個值為 B，next 指向上一個建立的 struct llist，以此類推，便會得到如下的 linked list。

+------+------+     +------+------+     +------+------+     +------+------+
|      |      |     |      |      |     |      |      |     |      |      |
|  D   | next +---->|  C   | next +---->|  B   | next +---->|  A   | NULL |
|      |      |     |      |      |     |      |      |     |      |      |
+------+------+     +------+------+     +------+------+     +------+------+
   ^
   |
  head

所以這邊的 ABCD = 7459。
























void sorted_insert(struct llist **head, struct llist *node)
{
    if (!*head || (*head)->val >= node->val) {
        SS1;
        SS2;	
        return;
    }
    struct llist *current = *head;
    while (current->next && current->next->val < node->val)
        current = current->next;
    node->next = current->next;
    current->next = node;
}

void sort(struct llist **head)
{
    struct llist *sorted = NULL;
    for (struct llist *current = *head; current;) {
        struct llist *next = current->next;
        sorted_insert(&sorted, current);
        current = next;
    }
    *head = sorted;
}

看到 sort 這部分，這邊是用 insertion sort，先解說一下程式原理。

第 18 行的迴圈是把整個 list 走過一遍來排序，並且每次先透過指標 next 保存當前節點的下一個位置，再透過 sorted_insert 進行排序。
第 17 行指標 sorted 是用來記錄下整個 list 的開頭位置。
第 3 行是對當前節點 node 跟第一個節點 head 開始判斷，如果 head 的值大於等於 node 的值，就直接把 node 更新成第一個節點，然後結束換下一個，所以這邊 SS1=node->next = *head，SS2=*head = node。如果不是了話就開始跟每一個節點比較，直到找到一個節點的值大於等於 node，就把他更新到那個節點的前面一個位置。

延伸問題

TODO

研讀 Doubly Linked Lists in C 並比對 Linux 核心的 linked list 實作予以解說;
練習 LeetCode 148. Sort List，嘗試將 Optimizing merge sort 的手法引入到 C 程式中實作
- 用長度為 n 的 list* l，分析 sort(l) 的時間複雜度，得到
  $O (n^{2})$ 的結果
- Fundamental Sorting Algorithms 提到 tiled merge sort 此種 cache-aware 演算法的考量點，對於排序大量資料而言，quick sort 和 merge sort 勝過 insertion sort，對於小量資料則取決於執行環境。因此在 merge sort 將問題切成 L1 cache size 後，即不再往下遞迴，改用 insertion sort 進行排序。
- 交叉閱讀共筆 eecheng87/quiz3

測驗 4

題目

LeetCode 287. Find the Duplicate Number 給定一個整數序列，其中會有一個數值重複，請找出。
已知條件：

假設陣列長度為 n，數值的範圍是 1 到 n − 1

考慮以下程式碼是可能的解法:


















int findDuplicate(int *nums, int numsSize)
{
    int res = 0;
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
    for (size_t i = 0; i < log_2; i++) {
        int bit = 1 << i;
        int c1 = 0, c2 = 0;
        for (size_t k = 0; k < numsSize; k++) {
            if (k & bit)
                ++c1;
            if (nums[k] & bit)
                ++c2;
        }
        if (CCC)
            res += bit;
    }
    return res;
}

作答

這題的題目敘述是給定 nums 陣列，大小 n+1 個整數，且範圍是 [1,n] inclusive，然後會有一個數值重複。所以在陣列長度 numSize 下，1~numSize-1 都會出現一次，但是會有一個數字重複出現一次，舉例來說今天 numSize = 4，那 1、2、3 都會出現一次，其中一個數字會再出現一次。

因此我們可以對每個位元進行操作，用兩個變數 c1、c2 ，c1 是用來紀錄 0 ~ numSize-1 每個數字，在每個位元上為 1 的數量，c2 則是記錄陣列當中每個元素，在每個位元上為 1 的數量。所以如果 c2 > c1，就代表多出來的這個數字在這個位元上是 1，就把這個位元記錄下來，最後就可以找到這個數字。

舉例來說，今天陣列大小為 4，重複的數字為 2。

num	bit1	bit0
1	0	1
2	1	0
3	1	1
2	1	0

在 bit 0 的時候 c1 == c2，bit 1 的時候，因為 2 重複出現所以 c2 > c1，這時候就把第二個位元記錄下來，我們就可以知道重複的數字第二個位元是 1。

第 3 行是在計算最高位為 1 的位元位置，只需要從 LSB 計算到這個位置就可以結束了。
第 8 行的迴圈是計算該個位元的 c1 c2 數量，最後進行比較，也就是我們上述說的方法，因此 CCC = c1 < c2。

延伸問題

TODO

實作不同的程式碼 (合法的 C 程式，可運用 GNU extension)，使其表現優於上述程式碼;

hankluo6

2020q3 Homework6 (quiz6)

目錄

測驗 1

題目

作答

延伸問題

測驗 2

題目

作答

延伸問題

題目

作答

測驗 3

題目

作答

延伸問題

測驗 4

題目

作答

延伸問題

參考資料

2020q3 Homework6 (quiz6)

目錄

測驗 1

題目

作答

延伸問題

測驗 2

題目

作答

延伸問題

題目

作答

測驗 3

題目

作答

延伸問題

測驗 4

題目

作答

延伸問題

參考資料

Read more

2020q3 Homework5 (render)

研讀筆記: Raycasting

研讀筆記: Achieving polymorphism in C

研讀筆記 linenoise