TFHE実装入門

9.Circuit Execution

松岡　航太郎

背景

  • TFHEは論理ゲートを実行することができる
    • 論理回路を実行しようと思ったらもっと上のレイヤーが必要
      • ここではそのレイヤーの作り方のアイデアを喋る
    • 同時に実行可能なゲートを並列で実行したい
  • １つの方法は作りたい回路をソースコードに直書きする
    • 当然複雑な回路になったら死ぬ
    • 並列性の管理も難しい
  • もう１つの方法は論理合成ソフトの出力を受け取るようにする
    • VerilogやChiselなどのHardware Discription Languageで論理回路を記述できるようになる
    • 論理回路の最適化もできる

Yosys

  • オープンソースの論理合成ソフト
    • BerkleyのABCという論理合成ソフトのwrapper
    • 秘密計算系の論文ではよく使われている
  • 出力フォーマットはいくつか選べる
    • ここではJSONを扱う
      • 比較的人間がよめるフォーマットなので

Workflow

  • HDLの書き方とかは適当な資料を見てほしい
  • 3.から先が作らないといけない所
  1. HDLで論理回路を記述する
  2. Yosysで論理回路を合成してJSONを出力する
  3. JSONを読み込んでTFHEの論理ゲートによるグラフを構築
  4. 入力を受け取って展開する
  5. グラフに基づいて依存関係を解決しながら実行する(順序回路なら指定された回数繰り返し)
  6. 出力ポートの内容を吐く

Yosysのフォーマット

  • よく出てくるものだけ表示
  • <module_name>はTopモジュールの名前
  • portsとcellは次スライド以降
    {
      "modules": {
        <module_name>: {
          "ports": {
            <port_name>: <port_details>,
            ...
          },
          "cells": {
            <cell_name>: <cell_details>,
            ...
          },
        }
      },
    }

portsの形式

  • モジュールの外につながっている部分
    • inputには入力データを展開する
    • outputに出ているデータをまとめて出力データを作る
    • inoutは見たことがない
  • <bit_vector>には各Portの各bitについている固有の番号が入っている
    • この数字はゲートの入力や出力にもついている
    • 同じ数字を指していればつながっている
    {
      "direction": <"input" | "output" | "inout">,
      "bits": <bit_vector>
    }

cellの形式

  • 論理ゲートを表現しているデータ
  • <cell_type>は$_AND_とかが入る
  • "port_directions"と"connections"を合わせることでゲートやポートとの接続に関する情報を得ることができる
    {
      "hide_name": <1 | 0>,
      "type": <cell_type>,
      "port_directions": {
        <port_name>: <"input" | "output">,
        ...
      },
      "connections": {
        <port_name>: <bit_vector>,
        ...
      },
    }

JSONを読み込んで行う処理

  • cellとportのbit_vectorやdirectionsを見てグラフを作る
    • どのゲートはどのゲートの実行が終わると実行可能になるのかを示す依存関係のグラフ
    • 最初の入力をどのゲートに渡して、出力をどこから集めてくればいいのかも示すことになる
    • グラフは次に説明する実行の部分で使いやすい形式にすることが望ましい
      • 何かしらの解析をするならそれがしやすいほうがいいだろうし、外部のライブラリを使いたいならそれに合わせるのが良い

実行の方法について

  • 外部のライブラリに頼るか自前で実装するか
    • 実行するタスクをDirected Acyclic Graphで表現して実行するライブラリはいくつか存在する
      • C++ならtaskflowが使いやすい(Sudachiで使っている)
      • PythonだとCeleryが有名だがWeb向けなのでオーバヘッドが大きいかも？
        • paradagはシンプルだけど更新が止まってる
      • RustだとTokioが有名？
        • futures-dagtaskも使いやすそうではある(更新止まってるけど)
    • 自前で実装する場合についてはデータ形式の話をしたあとに

データ形式

  • ゲートやポートの間でデータを受け渡さないといけない
    • HomNANDとかだけを考えるならTLWE(整数の配列)が受け渡される
    • Bootstrapping Keyとかは共通なのであまり考えることはない
  • データ形式は大別すると２つに分かれる
    • 受け渡しが必要なときだけメモリ領域を確保する
      • 回路の途中のデータは破棄しても問題ない
      • メモリ消費は抑えられるがmalloc freeに相当するオーバーヘッドがある
    • ゲート間の接続ごとにデータを保持する領域を確保する
      • IyokanもSudachiもこれに入る
        • Iyokanはゲートがデータを保持し、SudachiはTLWEの配列を用意するのは異なる
      • メモリ消費は増えるが、どこに置くかを事前に決めておけるのでオーバヘッドが少ない

実行エンジンのアルゴリズム

  • ここからは実行エンジンを自前で作る場合のアルゴリズムについて説明する
    • 扱うのはList Schedulingアルゴリズム
      • 実行すべきタスクを優先順位付きの1次元のListに入れて実行していく
    • 近代的なDAGで書かれたタスクを処理する外部ライブラリは大抵work stealing
      • これは動的にタスク自体や処理時間が変わる場合に対応できる
      • 今考えるのは事前にタスクが決まっていて処理時間も変わらないと想定できるので問題ない

具体的なList Schedulingアルゴリズム

  • スケジューリング専用のスレッドを用意する
  • 各ワーカスレッドの状態(Idle,Run,Fin)を管理する配列を用意する
    • この配列(スレッド)それぞれにアルゴリズムを適用する
  • 実行可能なタスクだけの配列も用意する
  1. Finなら以下を実行
    1.1 実行していたタスクに依存するタスクに終了通知を送る
    1.2 通知で実行可能になるものを優先度に従って配列に追加
    1.3 状態をIdleに変更
  2. Idleで実行可能なタスクがあるなら以下を実行
    2.1 状態をRunに変更
    2.2 一番優先度が高い実行可能タスクを発行

自前で実装する場合のワーカの作り方

  • 大抵の場合スレッドプールを使うことになる
  • OSの標準のスレッド作成機能ほぼそのまま
  • タスクを実行するたびにスレッドを作り直すのは重いので使い回す
  • C++ならThreadPoolをIyokanは使っている(更新止まってるけどシンプル)
    • 最近のだとthread-poolも良いかも(C++17の機能を使っている)
  • Pythonだと標準のconcurrent.futuresでいいはず
  • Rustだとrust-threadpoolが良いか？

参考文献(1/2)

参考文献(2/2)

page_number: true