today   2019-03-29

access_time  10 mins

ChiselでBF処理系を作る(3)

FIFOの実装

前回はボタン入力のチャタリング回路実装を行った。次は各モジュールをつなぐFIFOを実装する。

graph LR PC -- USB --- USB_Uart USB_Uart --Tx--> UartTxRx UartTxRx--Rx--> USB_Uart UartTxRx -- program/stdin -->FIFO_din FIFO_din -- program --> BF_Processor FIFO_din -- stdin--> BF_Processor BF_Processor -- stdout --> FIFO_dout FIFO_dout -- stdout --> UartTxRx External_SW --program/run -->UntiChatter UntiChatter -->BF_Processor style FIFO_din fill:#f66,stroke:#f33 style FIFO_dout fill:#f66,stroke:#f33

FIFOの実装方法

I/Fの方式

今回はReady/Valid/Ackの予備チャネルを備えたオレオレストリームインターフェースでやり取りする。

(一般的にはDestinationからreadyが出ていたらデータを流し続けてstart/endなどでフラグを立てるようなものが多い印象。今回のI/Fは作ってから思ったがAckはReadyと機能がかぶっていて、帯域を落とすだけで冗長だったと反省している)

ともあれ処理のフローは以下の通りである。

sequenceDiagram participant Source participant Destination loop Source not empty Source-->>+Destination: Ready? note right of Destination: Wait for Ready Destination-->>-Source:[Ready] Source->>Destination: [Data] activate Destination Source-->>Destination: [Valid] Source-->>+Destination: Ack? note right of Destination: Wait for Ack Destination-->>-Source: [Ack] deactivate Destination Source-->>Destination: not [Valid] end
  1. まずSource側に流せるデータが有るなら、DestinationからReadyが出るまで待機
  2. Readyが出ていたら、SourceからDataとValidを送る
  3. DestinationはDataとValidを受信したらAckを立てる
  4. SourceはDataとValidを引っ込めて、まだ流せるデータが有るなら1.に戻る

2回の書き込みフェーズと、dst側が(処理中やfullなどで)not readyな場合を示す。(前述の通りReady/Ackの機能がダブってる)

この方式のあまり良くない点(留意すべき点)はAckを出した次のクロックは無効データである点である。連続で受信できるようなDestinationを実装する場合は気をつける必要がある。(FIFO以外にもUartTxRx, BF Processorも同様のインターフェースを持つからである)

データの格納方式

C++などでも標準ライブラリとなっているFIFO(Queue)だが、組み込み環境で一番簡単な実装はリングバッファである。

大きめの配列と読み込み用のポインタ、書き込み用のポインタを用意する。書き込み時には書き込みポインタに値を書いたらポインタを進める、読み込みも同様。ただしポインタが配列の最後まで来たら先頭に戻す処理をする。

これについてはデータ構造とアルゴリズム周りの資料に記載されていると思うので、c++等での実装は割愛する。

重要なのは追加された要素の数が配列のサイズを超えない限りは問題なく動作するので、オーバーフローしないように先のインターフェースで正しくステータスを通知するようにする。

Chisel実装

実装全体を示す。

Fifo.scala - Github

package bf

import chisel3._
import chisel3.util._

class Fifo(width: Int = 8, depthWidth: Int = 4)  extends Module {
  val io = IO(new Bundle {
    val inData = Input(UInt(width.W))
    val inValid = Input(Bool())
    val inReady = Output(Bool())
    val inAck = Output(Bool())

    val outData = Output(UInt(width.W))
    val outValid = Output(Bool())
    val outReady = Input(Bool())
    val outAck = Input(Bool())
    
    val empty = Output(Bool())
    val full = Output(Bool())

    val inPtr = Output(UInt(depthWidth.W))
    val outPtr = Output(UInt(depthWidth.W))
  })
  val inReady = RegInit(Bool(), false.B)
  val inAck = RegInit(Bool(), false.B)
  val outData = RegInit(UInt(width.W), 0.U)
  val outValid = RegInit(Bool(), false.B)
  io.inReady := inReady
  io.inAck := inAck
  io.outData := outData
  io.outValid := outValid

  val depth: Int = scala.math.pow(2, depthWidth).toInt
  val mem = Mem(depth, UInt(width.W))

  val inPtr = RegInit(UInt(depthWidth.W), 1.U)
  val outPtr = RegInit(UInt(depthWidth.W), 0.U)
  io.inPtr := inPtr
  io.outPtr := outPtr

  val count = Mux(
    outPtr <= inPtr,
    inPtr - outPtr - 1.U,
    (depth.U - outPtr - 1.U) + inPtr
  )
  val empty = count === 0.U
  val full = count === (depth.U - 3.U)
  val inPtrNext = Mux(inPtr < depth.U - 1.U, inPtr + 1.U, 0.U)
  val outPtrNext = Mux(outPtr < depth.U - 1.U, outPtr + 1.U, 0.U)
  io.empty := empty
  io.full := full

  val inDelay = RegInit(Bool(), false.B)
  when(inDelay) {
    inDelay := false.B
  } .elsewhen(!full) {
    when(io.inValid) {
      mem.write(inPtr, io.inData)
      inPtr := inPtrNext
      inReady := true.B
      inAck := true.B
      inDelay := true.B
    } .otherwise {
      inReady := true.B
      inAck := false.B
      inDelay := false.B
    }
  } .otherwise {
    inReady := false.B
    inAck := false.B
    inDelay := false.B
  }

  val waitAck = RegInit(Bool(), false.B)
  when(!empty) {
    when(io.outReady) {
      when (!waitAck) {
        outData := mem.read(outPtrNext)
        outPtr := outPtrNext
        outValid := true.B
        waitAck := true.B
      } .otherwise {
        when(io.outAck) {
          outData := 0.U
          outValid := false.B
          waitAck := false.B
        }
      }
    } .otherwise {
      outData := 0.U
      outValid := false.B
      waitAck := false.B
    }
  } .otherwise {
    when(io.outAck) {
      outData := 0.U
      outValid := false.B
      waitAck := false.B
    }
  }
}

これまでの内容に含まれていない要素と設計根拠的なところを解説する。

Mem

データを格納するメモリをChiselのMemを使って実装している。

class Fifo(width: Int = 8, depthWidth: Int = 4)  extends Module {
  ...

  val depth: Int = scala.math.pow(2, depthWidth).toInt
  val mem = Mem(depth, UInt(width.W))

Mem(<capacity>, <data type>)で初期化することができる。合成時の実態はregの配列になっているようだった

reg [7:0] mem [0:15];

verilog上の記述をベンダーの論理合成ツールが分散RAM等として実装してくれる。今回Vivado 2018.3でXC7A35T向けに合成したところ合成ログは以下のようになっていた。fifoUartToBfとfifoBfToUartが今回実装したFIFOである。

今回のように自力でFIFOを作らなくてもベンダーIPで合成することもできる。その場合はMem等は使わずに直接制御できるようなI/Fを実装すれば何ら問題はない。

+------------+---------------------------+-----------+----------------------+----------------------------------+
|Module Name | RTL Object                | Inference | Size (Depth x Width) | Primitives                       | 
+------------+---------------------------+-----------+----------------------+----------------------------------+
|top         | dap/fifoUartToBf/mem_reg  | Implied   | 16 x 8               | RAM32M x 2                       | 
|top         | dap/bf/instMem_reg        | Implied   | 16 K x 8             | RAM64X1D x 1024  RAM64M x 1024   | 
|top         | dap/bf/stackMem_reg       | Implied   | 1 K x 8              | RAM64X1D x 96  RAM64M x 96       | 
|top         | dap/fifoBfToUart/mem_reg  | Implied   | 16 x 8               | RAM32M x 2                       | 
|top         | dap/bf/branchStackMem_reg | Implied   | 16 x 14              | RAM32M x 3                       | 
+------------+---------------------------+-----------+----------------------+----------------------------------+

読み書きは以下のように行っている。

// write

mem.write(inPtr, io.inData)

// read

outData := mem.read(outPtrNext)

それぞれアドレスとデータ、アドレスを指定すればあとはRegの読み書きと何ら変わりなく扱うことができる。

FIFOの計算

inPtrがFIFOモジュールへのpush、outPtrがFIFOモジュールからのpopを示している。

val inPtr = RegInit(UInt(depthWidth.W), 1.U)
val outPtr = RegInit(UInt(depthWidth.W), 0.U)
io.inPtr := inPtr
io.outPtr := outPtr

val count = Mux(
  outPtr <= inPtr,
  inPtr - outPtr - 1.U,
  (depth.U - outPtr - 1.U) + inPtr
)
val empty = count === 0.U
val full = count === (depth.U - 3.U)
val inPtrNext = Mux(inPtr < depth.U - 1.U, inPtr + 1.U, 0.U)
val outPtrNext = Mux(outPtr < depth.U - 1.U, outPtr + 1.U, 0.U)

リングバッファが一周したときに備えて計算式を変更したり、空/満杯の通知が出せるようにしてある。なおfullに関して-3.Uしているがこれはマージンを見ているだけなので実際は-1.Uで動作する。

データ入力(push)

inがvalid(命名が良くなかったが、io.inValidと書いてある信号)になるまで待つ。 入力データがvalidになったら現在のinPtrにデータを書いてAckを返している。

また前述したとおりAckした次のクロックのデータは無効なので、読まないようにDelayで強制的に1clk待つように仕掛けてある。

val inDelay = RegInit(Bool(), false.B)
when(inDelay) {
  inDelay := false.B
} .elsewhen(!full) {
  when(io.inValid) {
    mem.write(inPtr, io.inData)
    inPtr := inPtrNext
    inReady := true.B
    inAck := true.B
    inDelay := true.B
  } .otherwise {
    inReady := true.B
    inAck := false.B
    inDelay := false.B
  }
} .otherwise {
  inReady := false.B
  inAck := false.B
  inDelay := false.B
}

データ出力(pop)

DestinationがReadyになるまではひたすら待つ。来たらデータを出力し今度はAckが出るのを待つ。 Ackが来たら(Readyであれば)次のデータの準備をする、といった具合である。

val waitAck = RegInit(Bool(), false.B)
when(!empty) {
  when(io.outReady) {
    when (!waitAck) {
      outData := mem.read(outPtrNext)
      outPtr := outPtrNext
      outValid := true.B
      waitAck := true.B
    } .otherwise {
      when(io.outAck) {
        outData := 0.U
        outValid := false.B
        waitAck := false.B
      }
    }
  } .otherwise {
    outData := 0.U
    outValid := false.B
    waitAck := false.B
  }
} .otherwise {
  when(io.outAck) {
    outData := 0.U
    outValid := false.B
    waitAck := false.B
  }
}

まとめ

ほぼ前回解説記事の内容でFIFOを設計することができた。かなり短かったが特別な要素はMemぐらいだったと思う。

次はUart送受信モジュールについて解説する。こちらも新しい要素はあまりないと思われる。

次回 - ChiselでBF処理系を作る(4)