Synthesijer.Scalaでソーティングネットワークを書いてみる

Pocket

※ kick,busyのクロック遅延が気に入らなかったので若干回路を変更しました(8/19)

ネットワークの構成は,もっともシンプルな構成のひとつである,最大の要素を一番下に落としていくというタイプの実装です. ソーティングネットワーク(Wikipedia)で”バブルソートにあたる”と紹介されているもの,です.

構成要素の実装からはじめて,ネットワークの組み立て部分を紹介していきます.最後にコードの全容を掲載しています.

プリミティブ

ネットワークを構成するプリミティブは,2つの入力を受け取り,小さいほうを上に,大きいほうを下に出力する,というコンポーネントです.

Synthesijer.Scalaで書くとこんな感じです.

// プリミティブを生成するメソッド
// a, bはハードウェア世界の演算要素のインスタンス
def prim_net(a:ExprItem, b:ExprItem):(ExprItem, ExprItem) = {
  val s0, s1 = signal(32) // 新しいsignal(ハードウェア世界の変数)を生成する
  s0 := ?(a > b, b, a) // S0には小さい方を接続
  s1 := ?(a > b, a, b) // S1には大きい方を接続
  return (s0, s1)
}

signal(32)で32bitの信号(VHDLでいうsignal,Verilog HDLでいうwireかreg)をつくり,それぞれに比較器の出力を接続しています.メソッド自体の返り値は,ソート結果が格納された信号インスタンスのペアです.

ネットワークをくみたてる

複数データを取り扱うためにはプリミティブを適切につないであげる必要があります.こんな感じです.なんかScalaらしくないようなコードな気もしますが…

// プリミティブを組み立てるメソッド
// r signalの集合(この集合はScalaで扱われるだけでハードウェアは関係ない)
// s 状態遷移機械中の,あるステートに相当するインスタンス
// e signalの集合rの中のソート対象の最後の要素の番号
def chain_net(r:IndexedSeq[Signal], s:State, e:Int) = {
  var x:ExprItem = r(0) // 最初の比較要素はr0
  for(i <- 0 until e){ // 0からeまで,プリミティブを数珠つなぎにするループ
    val (a, b) = prim_net(x, r(i+1))
    r(i) <= s * a // 小さいほうの値を,状態sでの確定値にする
    x = b // 次のプリミティブに数珠つなぎにする
  }
  r(e) <= s * x // 最後の一つを確定させる
  for(i <- e + 1 until r.length){ // 残りは,単にコピーする
    r(i) <= s * r(i) // 状態sでの確定値として保存
  }
}

prim_netには,直前のネットワークで大きかった方と比較対象のデータを与えています.大きいほうの信号を数珠つなぎにしているわけですね.State型の変数sはステートマシンのステートに相当し,*はそのステートで値を代入することを意味しています.

全部を組み立てる

入力データ数分のクロックをかけて全データをソーティングすることにします.こんな感じ.またvarとか使ってしまった.

// 動作状態
private var cur = start
// 状態遷移機械を作るループ
private val steps = for(i <- 0 until n-1) yield{
  chain_net(registers, cur, n-i-1) // ネットワークを作る
  busy <= cur * HIGH // この状態ではbusy信号をHIGHにアサートする
  cur = cur -> seq.add() // 続く新しい状態を生成する
}
busy <= cur * LOW
valid <= cur * HIGH
cur -> seq.idle // 最後はアイドル状態に遷移

完成コード

入出力も含めた全体コードはこんな感じ.


import synthesijer.scala._ // Synthesijer.Scala関連をまとめてインポート

// ソーティングネットワークをつくるクラス
// Moduleを継承すると各種ユーティリティメソッドが直接使えて便利
class sorting_network(n:Int) extends Module("sorting_network", "clk", "reset"){

  val inputs = for(i <- 0 until n) yield inP("input_"+i, 32) // 入力
  val outputs = for(i <- 0 until n) yield outP("output_"+i, 32) // 出力
  val kick = inP("kick") // ソート開始用の信号
  // 動作中を意味する信号.特に指定がない時にはLOWに固定.リセット時はLOWで開始.
  val busy = outP("busy"); busy.default(LOW); busy.reset(LOW)
  
  // 内部で使用するsignalの集合を生成
  private val registers = for(i <- 0 until n) yield signal("registers_"+i, 32)

  // 状態遷移機械を一つ用意する
  private val seq = sequencer("seq")
  // アイドル状態ではkickがHIGHならbusyをHIGHにする.(HDL的には<=はクロックに同期したノンブロッキング代入になる)
  busy <= seq.idle * kick

  // kickがHIGHになったら,状態繊維機械のアイドル状態から新しい状態に遷移する
  // 状態と信号の*は条件を意味する.->は状態遷移を作るメソッド
  private val start = seq.idle * kick -> seq.add
  // start状態ではbusyをHIGHにする.(HDL的には<=はクロックに同期したノンブロッキング代入になる)
  busy <= start * HIGH
  // アイドル状態でkickがHIGHになったら,入力信号をregistersにそれぞれコピーする
  (inputs zip registers).foreach(n => n._2 <= start * ?(kick, n._1, n._2))
  // 毎クロック,registersを出力信号に,それぞれコピーする
  (outputs zip registers).foreach(n => n._1 $ sysClk := n._2)

  // プリミティブを生成するメソッド
  def prim_net(a:ExprItem, b:ExprItem):(ExprItem, ExprItem) = {
    val s0, s1 = signal(32)
    s0 := ?(a < b, b, a) // smaller one
    s1 := ?(a < b, a, b) // bigger one
    return (s0, s1)
  }

  // ネットワークを生成するメソッド
  def chain_net(r:IndexedSeq[Signal], s:State, e:Int) = {
    var x:ExprItem = r(0)
    for(i <- 0 until e){
      val (a, b) = prim_net(x, r(i+1))
      r(i) <= s * a
      x = b // for next
    }
    r(e) <= s * x
    for(i <- e + 1 until r.length){
      r(i) <= s * r(i) // just copy
    }
  }

  // 全体を生成するループ
      
  private var cur = start
  private val steps = for(i <- 0 until n - 1) yield{
    chain_net(registers, cur, n-i-1)
	  busy <= cur * HIGH
	  cur = cur -> seq.add()
  }
  cur -> seq.idle
  busy <= cur * LOW
  valid <= cur * HIGH
}

// シミュレーション用のモジュールを生成するためのクラス
// SimModuleを継承してつくるのが便利
class sorting_network_sim(m:sorting_network) extends SimModule("sorting_network_sim"){
  // 立上がり/立下り10n秒のクロックの実行環境を用意する.clk,resetはクロックとリセット.
  // counterはclkに同期したカウンタ.
  val (clk, reset, counter) = system(10)
  // サブモジュールとしてテスト対象のsorting_networkのインスタンスを生成
  val inst = instance(m, "U", clk, reset)

  // sorting_networkのkickに相当する変数をcounterが10のときだけHIGHにする
  // counterが10のときにspring_networkを駆動させる,の意味
  inst.signalFor(m.kick) $ clk := ?(counter == 10, HIGH, LOW)

  // 入力にはあらかじめ逆順のデータを代入しておく
  val n = m.inputs.length
  for(i <- 0 until n){
    inst.signalFor(m.inputs(i)) := value(n-i, 32)
  }

}

// メインルーチン
object sorting_network{
  def main(args:Array[String]) = {
    val m = new sorting_network(4) // インスタンスを作って
    m.genVHDL() // VHDLコードを生成
    m.genVerilog() // Verilog HDLコードを生成
    (new sorting_network_sim(m)).genVHDL() // シミュレーション用コードを生成
    (new sorting_network_sim(m)).genVerilog() // シミュレーション用コードを生成
  }
}

このScalaプログラムを”実行”することでVHDLコードとVerilog HDLコードが生成できます.簡単なシミュレーション用のテストベンチも用意しました.Verilog版のコードをVivadoのシミュレータでシミュレーションするとこんな感じ.

sorting_network_result

で,何がうれしいの?

sorting_networkをnewするときの引数でネットワークのサイズを簡単に変更できます.また,chain_netを工夫することで,ネットワークの構成を変更したり,作る回路の構成を変更することができます.たとえばある個数以上なら複数ステートに分割する,などとして動作周波数を引き上げるなどの設計上の工夫も簡単に試すことができますね.