Try   HackMD

資訊科技產業專案設計 作業3

contributed by <魏昇芷 - tissue>

NVIDIA - Embedded Software Engineer

What we need to see:

  • Experience in relevant domain.
  • Good English language skills to work effectively with global teams.
  • Full experience at Linux, QNX or Android.
  • Excellent C skills.
  • Experience working on embedded systems and ARM processor specific.

問題一

下面的程式碼是在做 str 的初始化，請問可能有什麼潛在的問題？

char c;
char str[128];
for (c = 0; c < 128; c++)
  str[c] = 0;

取自 https://www.pttweb.cc/bbs/Tech_Job/M.1612848862.A.6D2

試答

C 語言中的 char 是一個 8 bit 的有號數，其範圍為 127 ~ -128，因此這個迴圈會成為無迴圈，因為其數值永遠不會超過 128。

問題二

如果硬體不支援乘法，那 x = y * 200 要怎麼改才能得到正確答案

取自 https://www.pttweb.cc/bbs/Tech_Job/M.1612848862.A.6D2

試答

首先先將 200 轉成 2 進位，

20010 =
110010002，由 2 進位可知 200 = 128 + 64 + 8。 接著我們可以反覆 y + y = 2y, 2y + 2y = 4y …，過程中我們可以得到 8y、64y、128y，將這三個數字相加 8y + 64y + 128y 即可得到 200y。 也可以用 shift 的。

問題三

實作一個 function，參數是 32-bit integer，回傳共有幾個 bits 是 1

取自 https://www.pttweb.cc/bbs/Tech_Job/M.1612848862.A.6D2

試答

用一個 for loop 逐一走訪 32 個 bit，並計算有幾個 bit 是 1

int countBit(int input) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if (input & 1)
            count ++;
        input >>= 1;
    }
    return count;
}

問題四

承上題，有沒有什麼更快的做法

取自 https://www.pttweb.cc/bbs/Tech_Job/M.1612848862.A.6D2

試答

改成一次走訪 2 個 bit，並利用建表的方式快速得知該數字有幾個 bit 是 1

int countBit(int input) {
    int num[4] = {0, 1, 1, 2};
    int count = 0;
    for (int i = 0; i < 16; i++) {
        count += num[input & 3];
        input >>= 2;
    }
    return count;
}

另外，也可以繼續延伸成 1 次走訪 4、8、16、32 個 bit，一次走訪的 bit 數量越多，要建的表就越大，花費的記憶體資源就越多，因此必須在效能與記憶體空間之間做取捨。

更佳解法

int hammingWeight(uint32_t n) {
    n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
    n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
    n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
    n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
    n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);
    return n; 
}

GOOGLE - Software Engineer, Embedded Systems, Silicon

Minimum qualifications:

  • Master's degree in Electrical Engineering, Computer Science, relevant technical field or equivalent practical experience.
  • Experience coding in C or C++.

Preferred qualifications:

  • Experience in ARM architecture and standard interfaces, bare-metal programming, bootloader, and firmware.
  • Experience in Linux kernel, device drivers, and Android system programming.
  • Experience in software/hardware integration.
  • Experience in optimizing algorithms with OpenGL/OpenCL/NEON/LLVM on CPU/TPU/GPU/DSP.
  • Verification experience using FPGAs and/or emulation platforms.
  • Familiarity with computer architecture, compilers, machine learning, or image processing.

相關面試經驗

Last changed by 
 
陳彥甫
0
477

Read more

實作 Thread package

contributed by < qwe661234 >

Oct 8, 2023
Cache Coherency & I/O ordering

在多處理器的機器上，每個 CPU 都有自己的 cache，以彌補 CPU 和主記憶體(Main memory) 之間較慢的存取速度，當一個特定資料首次被特定的 CPU 讀取時，此資料顯然不存在於該 CPU 的 cache 中 (即 cache miss)，意味著 CPU 需要自主記憶體中讀取資料 (為此，CPU 通常要等待數百個 cycle)，此資料最終將會存放於 CPU 的 cache 中，這樣後續就能直接自 cache 上快速存取，不需要再透過主記憶體。因為每個 CPU 上的 cache 資料是 private 的，因此在進行寫入操作時，會造成其他 CPU 上的 cache 資料不一致的問題。

Oct 2, 2023
CO Final

(15pt) 1. Assume there is no forwarding in a 5-stage pipline processor 1 (1) (5pt) Please indicate all the potential hazards in the following instruction sequence ? xori x1, x1, 2 addi x6, x5, -4 lw x10, 8(x6) add x5, x6, x6 sub, x2, x2, x1 Ans: addi && lw (2.5pt)

Jun 8, 2023
New EBB Strategy

考量到 JIT 中 codegen 以及 compilation 的 overhead 過高，我們需要讓一個 EBB 含有更多的指令，理想是希望將一整個 loop body 涵蓋在一個 EBB 中。 我們參考 rvemu， rvemu 先將 block 以 unconditional jump 作切分，接著將其 block 中所有 branch taken 會走到的 block 都涵蓋進來，一個 block 含有大量的指令且有好的效能表現。 我們的新策略也是希望一個 block 中含有大量的指令，所以我們 trace 整個 control flow graph 並把 trace 過的 block 都涵蓋進來。 control flow graph 的終點有兩種情形，一種是 unconditional jump，而另一個則是遇到 back edge，也就是指向已經 trace 過的節點，下圖展示一個簡單的 EBB 案例。 過去的策略我們是直接指向某個 block 的 ir，一旦 block 被 cache 置換掉，EBB 就會變小。過去的另一個策略是用 memcpy，然而頻繁的 memcpy 成本過高，導致效能沒有很好的提昇。於是我們選用成本較低的 instruction fetch & decode，將 trace 到的 block 使用 instruction fetch & decode 存到 EBB 中，這個作法也不用擔心其他 block 被 cache 置換掉使 EBB 變小的問題。 另外，過去 EBB 有兩種版本，一種是 for interpter 而另一種是 for JIT 的，這導致作 JIT 時還要重新 extend 一次，現在則統一一種版本。 original EBB vs new EBB 指令數量

May 10, 2023
Read more from 陳彥甫
Published on HackMD