2018年11月16日 星期五

Spatial Tutorial - Control Flow

在這一節中, 將介紹撰寫良好 Spatial 應用所需要的概念, 精確地說, 內如涵蓋:


  • Control Level (inner vs outer)
  • Control Style (Pipe, Sequential, Parallel, and Stream annotations)
  • Retiming and Initiation Interval
  • Finite State Machine (FSM)

Overview

Spatial 應用是以層級控制結構與指令所組成. 在後續的教學中, 將會學習到此語言的特定的語法與結構體, 但在這一節中將摘要多數的細節來表達關鍵的概念. 專精這些概念是自此語言榨出最佳效能的主要因素, 以及後續的教學將會以具體的方式應用這裡所討論的. 此外並不會花太多時間在討論也相當重要的 banking, buffering 與 duplication 的細節.

Control Level (控制層級)


在 Spatial 中一個 controller 不是 "outer" controller 就是 "inner" controller. 一個 controller  在這個情況本質上為軟體世界所稱的一個迴圈. 在此語言中它們的實體化是藉由 counter chain 與/或 state machine, 以及包含此語言中其他節點的集合. 精確地說:
  • Inner controllers 僅包含指令 (i.e.- arithmetic, memory access, muxing, etc.)
  • Outer controllers 包含至少一個其他 controller (i.e. Foreach, Reduce, FSM etc.) 並且 "短暫的" 無需消耗 FPGA 資源的運算 (i.e.- bit slicing, struct concatenation, etc.) 
在下圖的中顯示一個用以後續反覆討論的 controller tree 範例. 而片段的部份只是一小段 Spatial 用以生成這個 tree 的示範程式.
    Foreach(M by 1){j =>
      Foreach(K by 1){k => ... }
      Foreach(Q by 1){q => ... }
      Foreach(R by 1){r => ... }
    }
https://static1.squarespace.com/static/5a8dbb09bff2006c33266320/t/5be1f7924d7a9ca42e726d13/1541535638177/Screenshot+from+2018-11-06+12-20-24.png?format=1000w

Control Schedule (控制排程)

一共有五種 schedule 能被 outer controller 所使用. 後續的數個動畫演示這些 controller 在先前的範例中如何運作. 這裡的一個例外為 FSM controller, 將在稍候的段落說明. 
https://static1.squarespace.com/static/5a8dbb09bff2006c33266320/t/5be20ead70a6add349e19062/1541541551287/vokoscreen-2018-11-06_13-52-00.gif?format=1000w
  • Pipelined - 若沒有指令, 此為所有 controller 的預設 schedule. 此 controller 的 children 將以 pipelined 型式執行. 此 controller 的 counter 只會在所有啟動的 children 都完成工作時才增加數值. 基於在 children 中序列的位置, 每個 child 各自觀察來自 parent 一個不同的 counter 數值. 第一個 child 接收最新的數值, 序列中第 N 個 child 將會觀察一個來自之前 N 個 interation 的 counter 數值. 也就是說 controller 的 initiation interval 時間相當於在指定 iteration 下狀態為 active 而有著最長的運作時間的 child. 在 steady-state 下, 最慢的 child  完全決定了 iteration 的執行時間.  請注意此 schedule 有著在後續效能教學中會討論到的 loop carry dependencies 以及 area usage 的影響.  強這使用這個 control schedule, 以  Pipe.<control>  來標明此 controller.
https://static1.squarespace.com/static/5a8dbb09bff2006c33266320/t/5be20cb18a922dd662bbb5b9/1541541044676/?format=1000w
  • Sequenced - 此 controller 的 children 在任一時間僅只有一個在運作. 只有在最後一個 child 完成 iteration i 後, parent 的 counter 才會增加並且發出 iteration i+1 給第一個 child.  也就是說此 controller 的 initiation interval 時間相當於所有 children 執行時間的總和. 儘管相較於 Pipe 較慢, 其消耗的資源較少並且能夠作為 loop-carry dependency 問題的解決方案. 每個 child 都對 controller 的 runtime 有相同的貢獻.
    以 Sequential.<control> 標明 controller 來強制使用此 control schedule.
https://static1.squarespace.com/static/5a8dbb09bff2006c33266320/t/5be20cbd89858378d8e52aba/1541541082303/vokoscreen-2018-11-06_13-44-06.gif?format=1000w
  • ForkJoin - 此 controller 的 children 以平行的方式運作. 每個 child 將自己維護來自 parent counter 的複製, 並且當完成時增加 counter 的數值作為自身本地的用途. 此 controller 的運作時間由執行時間最長的 child 所決定.
    以 Parallel.<control> 標明 controller 來強制使用此 control schedule. 請注意, 僅使用 Paralle{} 為縮寫來產生一個其 children 是以此 schedule 運作的迴圈.
https://static1.squarespace.com/static/5a8dbb09bff2006c33266320/t/5be20ce04d7a9c4539ac9f50/1541541091284/?format=1000w
  • Fork - 此 controller 在任一時間僅會只有一個 child 在運行. 目前唯一建立這樣的 controller 的方式是使用 if-then-else, 如此建立的 controller 只會執行單一 interation. 可以將其視為對 children 的 one-hot mux.
https://static1.squarespace.com/static/5a8dbb09bff2006c33266320/t/5be20c73575d1fe71fff2250/1541540983177/vokoscreen-2018-11-06_13-45-04.gif?format=1000w
  • Stream - 此排程指的是一個 controller 是在 "資料" 層級 pipelined. 它與 ForkJoin 類似, 除了並非允許 children 以任意的方式運作, 一個 child 只有在其所有輸出 steam 為 "ready" 狀態, 並且所有的輸入 stream 為 "valid" 才能夠執行. 此 "ready" 訊號代表著輸出 stream 準備好接收至少一筆的資料, 而 "valid" 訊號表示輸入 stream 至少有著一筆資料尚未被取出. 符合此介面的結點包含類似 FIFO 的記憶體, 與像是 DRAM 或其他類似 AXI 介面的匯流排.
    由於這是了解與使用上最為棘手的 schedule, 且為了自 Spatial 獲取最佳的效能這可能是最重要的一個.
    以 Stream.<control> 標明 controller 來強制使用此 control schedule.
    請注意在動畫中最後一個 child 並沒有輸入或輸出 streams, 因此當 parent 被啟動後它被允許任意地執行.

Latency and Interval

https://static1.squarespace.com/static/5a8dbb09bff2006c33266320/t/5be21f4ff950b7cb173b3731/1541545818613/8d3q6-ufpxq.gif?format=750w
先前的篇幅介紹了 outer controller 的 schedule 選項. 由於這些 schedule 並沒有真正地對應 inner controller(除了 Sequential 與 Pipelined 之類的, 將會在後續討論), 這裡討論 inner controller 的 latency 與 initiation interval.  Spatial compiler 包含了一個 retiming pass, 這能讓產生的設計符合較高的頻率. 每個節點有著與其關聯的一個 latency model, 而 compiler 會使用這些 model 來計算在 dataflow graph 上的 retiming, 並且自動地加入適當的 delay line. 
  • Latency - 對於 datapath 啟動訊號的 rising edge 到達 controller 主體的最後一個指令所需的 cycle 數目. 對一個僅運作單一 iteration 的 controller 而言, 這等同於此 controller 運作所需要的 cycle 數目.
  • Initiation Interval - 在增加 counter 並發出下一個 iteration 所必須等待的 cycle 數目. 對於主體沒有 cycle 延遲的部份, initiation interval 將會被設為 1. 這表示 controller 能夠每個 cycle 都增加其 counter 並發出此新的數值到第一個指令. 剩餘的主體部份為完全地 pipelined, 因此在 latency 之後主體將在每個 cycle 產生一個結果. 對於 controller 而言, 哪裡有著循環 (i.e. 在寫入記憶體後讀取該數值), compiler 以考量記憶體存取的模式來計算最小需要的 cycle 來處理解決此相依性.
若以 Sequential 標示一個 inner controller, 這會自動地強制該 controller 的 initiation interval 等同於 latency. 也能夠使用 Pipe(ii=desired_cycs) 標示來強制該 controller 的 initiation interval 為一些指定的 cycle 數目. 由於 latency 事由 latency model 與 controller 中的節點所計算出的, 因此 controller 的 latency 是無法被控制的.

Finite State Machine (FSM)

https://static1.squarespace.com/static/5a8dbb09bff2006c33266320/t/5be878f940ec9a97ddc12695/1541961990923/vokoscreen-2018-11-11_10-40-43.gif?format=750w
https://static1.squarespace.com/static/5a8dbb09bff2006c33266320/t/5be8790f03ce64619f84adb6/1541962008049/vokoscreen-2018-11-11_10-41-20.gif?format=750w
Spatial 也支援任意的 FSM controllers. 若想要產生一個如同軟體的 while loop 的迴圈, 或是基於數值的狀態採取特定的動作, 這將非常有用.  這些類型的 controller 能夠作為 inner controller (action logic 與 next state logic 僅由指令所組成) 或是 outer controller (有著至少一個 controller 為 action logic 或是 next state logic)

對於 outer controller, FSM 的行為類似於 Sequential. 對於 inner controller, FSM 的行為類似於 inner pipe 而其 initiation interval 設為其 latency. 下一狀態的計算直到 action 指令完成前都不會開始.

沒有留言:

Chisel 學習筆記 - Scala 與 Chisel 基礎語法

標題為筆記, 但這篇比較屬於心得 延續 上一篇 的環境建立, 這次計劃藉由 Jserv 最新的 課程安排 來學習 Chisel, 當然個人目標是能夠按照 Jserv 的課程規劃在 期限之內 完成 Lab 3, 由於個人並非 digital designer (現在這年紀也算老貓學...