2019年8月14日 星期三

有限狀態機


每一個有限狀態機 (Finite State Machine, FSM) 通常包含了以下幾個組成要件:輸入字母表、狀態集合、轉移函數、輸出子母表、輸出函數,而根據輸出的產生方式不同,FSM 又可以分為以下兩種模型。

Mealy Machine

Mealy Machine [1] 的輸出和目前的狀態以及輸入有關。

數學模型 (S, S0, Σ, Λ, T, G)
S:狀態集合
S0:初始狀態
Σ:輸入子母表
Λ:輸出子母表
T:轉移函數 (T: S×Σ → S)
G:輸出函數 (G: S×Σ → Λ)

Moore Machine

Moore Machine [2] 的輸出只和目前的狀態有關。

數學模型 (S, S0, Σ, Λ, T, G)
S:狀態集合
S0:初始狀態
Σ:輸入子母表
Λ:輸出子母表
T:轉移函數 (T: S×Σ → S)
G:輸出函數 (G: S → Λ)

從輸出函數 G 的差異可以看出,Moore Machine 的輸出只和目前的狀態有關,而Mealy Machine 的輸出和目前的狀態以及輸入都有關。

FSM 設計流程

  1. 畫 State diagram
  2. 建立兩個真值表 (truth table),一個是 next state 和 present state 及 input 的關係,另一個是 output 和 present state 及 input (Mealy machine only) 的關係
  3. 運用 Karnaugh map 進行邏輯化簡,得到 next state 和 output 的布林函數
  4. 使用 combinational circuit 實現布林函數,用 DFF 存放 FSM 狀態
  5. 決定是否要在 output 之後加上一個額外的 DFF,以消除 glitch 或實現 pipelining
其他在設計上需注意之重點:
  • Mealy machine 和 Moore machine 可以互相轉換,並且 Mealy machine 的狀態數量會小於或等於 Moore machine
  • 需檢查是否存在 under- or overspecified state transition diagram
  • Transition 種類:{conditional, timed, conditional-timed, unconditional}
  • FSM 種類:{regular machine, timed machine, recursive machine}

FSM 種類

  • Regular machine:State machine 的轉移函數與時間無關,且輸出函數與先前的 output 無關
  • Timed machine:State machine 的轉移函數與時間有關,但輸出函數與先前的 output 無關
  • Recursive machine:State machine 的轉移函數與時間有關,且輸出函數與先前的 output 有關
在 timed machine 中,由於轉移函數與時間有關,所以在硬體上需要一個 counter,在每一次狀態轉換的時候,counter 會歸零,並且當處在轉移函數與時間有關的狀態中時,counter 會在每一個 clock cycle 遞增。

而在 recursive machine 中,由於輸出函數與先前的 output 有關,因此需要額外的 memory 用來儲存先前的 output。

FSM 結合/分解 (Association/Decomposition)

當我們要實現一個較複雜的功能時,可以先實現多個較簡單的 FSMs,並且將這些 FSMs 結合起來。也可以看做是將一個複雜 FSM,拆解成多個簡單的 FSMs。

FSM 結合的方法有以下三種:
  1. 序列結合式 (Serial association)
  2. 平行結合式 (Parallel association)
  3. 內部結合式 (Internal association)

Datapath 控制單元 (Control Unit)

無論是簡單的算數邏輯運算,或是較複雜的演算法,其實都是一個資料流動的過程,資料從一個輸入端進入,在資料路徑中傳遞,經過不同的功能單元 (functional unit),直到從輸出離開為止,也有可能這個資料路徑是有回饋的、或者是一個封閉的迴圈。而為了實現複雜的運算功能,我們可以利用 FSM 來進行資料路徑的控制。

在資料路徑中,常見的功能單元有:
  • 暫存器 (Register):由 DFFs 所組成。
  • 記憶體 (Memory):由 SRAM 儲存單元組成,儲存運算當中所產生的資料。
  • 多工器 (Multiplexer):藉由一個選擇訊號來從多工器的多個輸入路徑中選擇一條作為輸出。
  • 算術邏輯單元 (Arithmetic logic unit; ALU):進行加、減、乘、除等算術運算,或者是 and、or、not 等邏輯運算。
在 FSM 的設計中,則需要注意以下幾個重點:
  • FSM 通常只負責產生控制訊號,而不會直接存取資料。
  • 需注意資料間相互依賴關係 (data dependency)。

Reference [3] 是很好的教材,推薦給大家。


Reference
[1] Mealy, G. H. (1955). A method for synthesizing sequential circuits. The Bell System Technical Journal, 34(5), 1045-1079.
[2] Moore, E. F. (1956). Gedanken-experiments on sequential machines. Automata studies, 34, 129-153.
[3] Pedroni, V. A. (2013). Finite state machines in hardware: theory and design (with VHDL and SystemVerilog). MIT press.

2019年8月13日 星期二

半導體製程演進


1965年,Intel 創辦人之一 Gordon E. Moore 根據對半導體發展的觀察,提出了摩爾定律 (Moore's Law):「在積體電路上可容納的電晶體數量每18個月增加一倍。」

這也是為何在半導體製程節點 (technology node) 中,每一代是前一代的 0.7 倍,例如 90nm、65nm、45nm、32nm、22nm、16nm、10nm、7nm、5nm、3nm。

其中 0.7 倍的縮小倍數,指的是電晶體的長、寬都縮小 0.7 倍,因此面積就是縮小 0.7 * 0.7 = 0.5倍,隨著電晶體的微縮,在電氣特性上,也會隨之改變。

Width (W) = 0.7X
Length (L) = 0.7X
Die area = 0.7 * 0.7 = 0.5X
Oxide thickness (tox) = 0.7X
Area capacitance (Ca) = (0.7 * 0.7) / 0.7 = 0.7X
Fringing capacitance (Cf) = 0.7X
Total capacitance (C) = 0.7X
Delay = 0.7X
Operation frequency (f) = 1 / 0.7 = 1.43X

因此,在原有晶片設計不改變的情況下,如果我們將它轉移到新一代的製程上製造,就可以得到 performance 的提升 (f = 1.43X)。

由於晶片所消耗的 power 和操作電壓 (VDD) 有關係,因此分成 constant voltage scaling 和 constant electric field scaling 兩種情況。

(1) Constant voltage scaling
VDD = 1X
Power = C * V² * f = 0.7 * 1 * 1.43 = 1X

(2) Constant electric field scaling
VDD = 0.7X
Power = C * V² * f = 0.7 * 0.7² * 1.43 = 0.49X


Reference
Borkar, S. (1999). Design challenges of technology scaling. IEEE micro, 19(4), 23-29.
Keyes, R. W. (2006). The impact of Moore's Law. IEEE solid-state circuits society newsletter, 11(3), 25-27.

2019年8月10日 星期六

IBM TrueNorth

硬體

IBM TrueNorth 晶片使用 Samsung 28 nm 製程,每個晶片中有 540 萬個電晶體,面積為 4.3 cm²,功耗密度為 20 mW / cm²。相較之下,傳統的 CPU 功耗密度為 50-100 W / cm²。

每一個晶片中包含 4096 個 neurosynaptic core,每一個 core 當中都包含 256 個神經元,以及 256×256 個突觸。這些 core 組成了一個二維的 mesh 網路,當用它來處理 400×240 pixels (RGB) 的 30 fps 影片時,僅消耗 63 mW。

每一個 core 當中有許多可被定址的突觸前軸突 (presynaptic axons),一個 synaptic crossbar array,以及許多可被程式化的神經元。神經元的動態模型的 time step 是 1 ms,當 spike 在系統上的不同晶片之間傳遞時,可被視為是在 long-distance axon 上傳遞,其時間上的延遲也被考慮進去了,是介於 1~15 個 time steps。

當一個神經元產生 spike 時,它會在local memory 中查表得到 4 bits 軸突延遲 (axonal delay)、8 bits 目的地軸突位址、兩個 9 bits 相對位址 (用來在64×64 個 core 組成的 mesh 網路中進行跳躍傳遞。每一個 core 當中的 router,會負責將上述資訊所組成的 packet 在 mesh 網路中傳遞,且每一個 router 都有五個傳遞方向可以選擇,包含東、西、南、北、本地。

每一個突觸前軸突都有一個可調整的權重,是有號整數 (signed integer)。而突觸權重則只有一個 bit 儲存,因此只有連接和非連接兩種狀態。

每一個 core 上分別有 104448 個 bits 的 SRAM,其中 65536 bits 用來儲存突觸狀態,31232 bits 用來儲存神經元狀態和參數,6656 bits 用來儲存目的地位址,1024 bits 用來儲存軸突延遲。

其功耗是一個和 spike rate、spike 平均傳遞距離、單一神經元的平均活躍 synape 個數有關的函數。

軟體

除了設計 TrueNorth 晶片以外,IBM 也建立一個軟體生態系統,相關的軟體包含 Compass 及 Corelet。

Compass 是一個用 C++ 開發,可以對 neurosynaptic cores 網路結構進行模擬的軟體。透過 Compass,可以在晶片的設計階段,對晶片進行邏輯驗證。此外,Compass 也可以提供一個環境給 neural network 應用的開發者,在硬體尚未完成前,評估應用的可能性;也可以用來分析和優化硬體功耗。

Corelet 則是一個程式語言及開發環境 (Programming language and environment)。Corelet 將硬體進行抽象化,使用者可以用程式語言建立一個網路結構,並且可以調整相關的參數,接著這個程式就可以在 TrueNorth 上執行。

IBM 使用 off-line learning 的方式,已將一些常見的問題 map 到 TrueNorth 架構上,例如:CNN、liquid state machine、restricted Boltzmann machine、hidden Markov model、SVM、optical flow 以及 multi-modal classification。


Reference
Merolla, P. A., Arthur, J. V., Alvarez-Icaza, R., Cassidy, A. S., Sawada, J., Akopyan, F., ... & Brezzo, B. (2014). A million spiking-neuron integrated circuit with a scalable communication network and interface. Science, 345(6197), 668-673.