九州大学大学院システム情報科学研究院情報工学部門 松永 裕介 2018/11/9 テクノロジマッピング 九州大学大学院システム情報科学研究院情報工学部門 松永　裕介 2018/11/9

2018/11/9 論理合成の流れ 2018/11/9

セルベース設計手法 あらかじめ設計されたセルを利用して回路を作る（組み立てる）。 トランジスタレベルの設計は必要ない。 2018/11/9 セルベース設計手法 あらかじめ設計されたセルを利用して回路を作る（組み立てる）。 トランジスタレベルの設計は必要ない。 自動合成向き⇒テクノロジマッピング 2018/11/9

「テクノロジ」とは 使用可能なセルの種類および特性 遅延時間の計算モデル 最大駆動能力のような設計規則 … 2018/11/9 「テクノロジ」とは 使用可能なセルの種類および特性 遅延時間の計算モデル 最大駆動能力のような設計規則 … 半導体ベンダ、用途などに応じて千差万別 2018/11/9

テクノロジ非依存／依存処理 テクノロジごとに論理合成システム全体を作り直していたら、プロセス技術の進歩に追いつかない 2018/11/9 テクノロジ非依存／依存処理 テクノロジごとに論理合成システム全体を作り直していたら、プロセス技術の進歩に追いつかない テクノロジに依存しない部分（多段論理合成、最適化）とテクノロジに依存する部分（テクノロジマッピング）に分離する。 テクノロジマッピングにおいても基本アルゴリズムは共通化して、さまざまなセルライブラリ、設計規則に対応できるようにする。←コンパイラ技術とのアナロジー 2018/11/9

テクノロジマッピングの歴史 ルールベースに基づく手法 Tree covering タイミング最適化 LSS(IBM, ’84) 2018/11/9 テクノロジマッピングの歴史 ルールベースに基づく手法 LSS(IBM, ’84) Socrates(GE, ’86)　⇒　現Synopsys LORES/EX(三菱,‘88) Tree covering DAGON(AT&T Bell Labs., ’87) タイミング最適化 （UCB,’90, ’91) 2018/11/9

ルールベースを用いた手法 テクノロジ毎にルールを用意することでシステムそのものは汎用化できる 2018/11/9 ルールベースを用いた手法 テクノロジ毎にルールを用意することでシステムそのものは汎用化できる ルールを作り、その一貫性を保ち、かつチューニングすることは容易ではない 局所変換の繰り返しでは大局的な最適化は行えない ⇒今ではアルゴリズム的に処理することが難しい特定の回路以外は用いられていない 2018/11/9

Tree covering 歴史的にみて最初のテクノロジマッピングのアルゴリズム 2018/11/9 Tree covering 歴史的にみて最初のテクノロジマッピングのアルゴリズム 基本アイデアはコンパイラのコード生成アルゴリズム（Bell Labs.のAho） ブーリアンネットワークを細かな単位ノードに分解して、セルによるカバーを求める 面積、遅延時間、消費電力などを目的関数、制約条件にして（ある尺度での）最適解を求めることができる 今日の実用的なシステムで広く用いられる 2018/11/9

タイミング最適化問題 Tree coveringアルゴリズムの拡張 ファンアウト最適化問題 上記２つを統合した大局的な処理 2018/11/9 タイミング最適化問題 Tree coveringアルゴリズムの拡張 ファンアウト最適化問題 上記２つを統合した大局的な処理 2018/11/9

2018/11/9 サブジェクトグラフ 2018/11/9

多入力ノードの分解 任意の論理関数はAND/OR/NOTで表現可能 任意のAND/ORは2入力NANDの木に分解可能 2018/11/9 多入力ノードの分解 任意の論理関数はAND/OR/NOTで表現可能 任意のAND/ORは2入力NANDの木に分解可能 しかし、解は唯一ではない 2018/11/9

セルの情報 機能を表す論理式⇒2入力NANDに分解 面積 入力端子から出力端子までの遅延時間の計算モデル 入力端子の負荷容量 2018/11/9 セルの情報 機能を表す論理式⇒2入力NANDに分解 面積 配線領域の面積の考慮 入力端子から出力端子までの遅延時間の計算モデル 配線遅延の考慮 入力端子の負荷容量 消費電力の計算モデル 2018/11/9

2018/11/9 パタングラフ 2018/11/9

2018/11/9 パタングラフ 2018/11/9

2018/11/9 ナイーブなマッピング結果 2018/11/9

2018/11/9 複合セルを用いたマッピング結果（１） 2018/11/9

2018/11/9 複合セルを用いたマッピング結果（２） 2018/11/9

被覆問題としての定式化（１） パタングラフと一致するサブジェクトグラフの部分グラフをマッチと呼ぶ 2018/11/9 被覆問題としての定式化（１） パタングラフと一致するサブジェクトグラフの部分グラフをマッチと呼ぶ テクノロジマッピングとは、サブジェクトグラフ上の全ての節点を被覆するマッチの集合を求めること ただし、単純な被覆ではない⇒feasibility constraint マッチの入力は他のマッチの出力でなければならない 2018/11/9

2018/11/9 被覆問題としての定式化（２） 2018/11/9

2018/11/9 被覆問題としての定式化（３） 2018/11/9

2018/11/9 被覆問題としての定式化（４） 2018/11/9

2018/11/9 被覆問題としての定式化（５） 2018/11/9

2018/11/9 被覆問題としての定式化（６） 2018/11/9

2018/11/9 被覆問題としての定式化（７） このように条件式に否定のリテラルが含まれる被覆問題を binate covering 問題と呼ぶ←条件式が binate function binate covering問題はNP問題であることが知られており、実用的には変数の数が数十程度までしか解けない 2018/11/9

テクノロジマッピングの近似算法 binate covering問題を厳密に解くことは難しい←テクノロジマッピングの場合、変数の数は数千～数万 2018/11/9 テクノロジマッピングの近似算法 binate covering問題を厳密に解くことは難しい←テクノロジマッピングの場合、変数の数は数千～数万 ではbinate covering問題を解く近似アルゴリズムは？⇒あまり研究されていない 問題自体をより簡単な問題に近似してしまう⇒サブジェクトグラフをtree(木)の形に制限する 2018/11/9

木状回路への分割 複数のファンアウトを持つ部分で回路を分割 2018/11/9 木状回路への分割 複数のファンアウトを持つ部分で回路を分割 テクノロジマッピングの問題はDAG coveringからtree coveringとなる tree coveringには効率の良い厳密解法が存在する 2018/11/9

2018/11/9 分割の弊害 ファンアウトをまたいだセルの割り当てが行えない 分割の境界部分での位相合わせが行えない 2018/11/9

パタンマッチングアルゴリズム 基本的にはサブジェクトグラフ上の節点をたどって、パタングラフの節点と一致するか確かめる 2018/11/9 パタンマッチングアルゴリズム 基本的にはサブジェクトグラフ上の節点をたどって、パタングラフの節点と一致するか確かめる パタングラフの節点をたどる順を決めるため edge-list という枝のリストを用いる NANDの入力は２つあるのでサブジェクトグラフとパタングラフのマッチの仕方が2通り考えられる。そのため、各節点につき最悪2通りずつのマッチを試す必要がある 実際には対称な入力が多いので試すべきマッチの数はそれほど多くない 2018/11/9

2018/11/9 パタンマッチングの例 2018/11/9

2018/11/9 tree coveringアルゴリズム 2018/11/9

2018/11/9 tree coveringの例 2018/11/9

inverter-chainヒューリスティック 2018/11/9 inverter-chainヒューリスティック 2018/11/9

遅延最小解を求めるtree covering（１） 2018/11/9 遅延最小解を求めるtree covering（１） 目的関数を遅延時間とする 遅延時間がセルの種類のみに依存するモデルなら最小面積の場合と同様にtree coveringで最適解を求めることができる 遅延時間が駆動先の負荷容量に依存するモデルの場合、単純なtree coveringでは解は求められない 2018/11/9

遅延モデル 固定遅延 負荷依存 セルの種類のみに依存。昔はトランジスタの寄生容量が比較的大きかったので駆動先の負荷容量は無視できた 2018/11/9 遅延モデル 固定遅延 セルの種類のみに依存。昔はトランジスタの寄生容量が比較的大きかったので駆動先の負荷容量は無視できた 負荷依存 駆動先の負荷容量の線形関数／非線形関数 T = T0 + K * l 最も一般的（少なくとも’90年代は） 2018/11/9

遅延最小解を求める tree covering（２） 2018/11/9 遅延最小解を求める tree covering（２） とにかく駆動先の負荷が決まらないと遅延時間は計算できない 仮に決めておいてそのときの最適解を持つ そのような仮の値をN種類、試しておき、後で実際の値に近いものを選ぶ tree coveringの処理を１つの節点についてN回繰り返すようなもの Nを大きくすれば解の精度は良くなるが、計算時間と使用メモリ量も比例して大きくなる 2018/11/9

遅延最小解を求めるtree covering（３） 2018/11/9 遅延最小解を求めるtree covering（３） 遅延最小解は駆動先の負荷の関数 しかも負荷の区間の関数なので解が切り替わる点のみを覚えておけばよい 負荷の値の区間[si, ei]とそのときの最適解miの組をリストの形で保持しておく 後で実際の負荷が確定したときに該当する区間を探してその区間の最適解miを返す 処理は複雑だが厳密解を求めることができる。区間の数Nをあらかじめ与えなくて良い 2018/11/9

2018/11/9 遅延制約下での面積最小解（１） 出力までのマッピングが確定しないと部分解が制約を満たしているかどうかが分からない←部分的な制約（required time）が与えられないから 2018/11/9

遅延制約下での面積最小解（２） required time（以降RT）を仮の値でN個、計算しておいてあとでもっとも実際の値に近いものを選ぶ 2018/11/9 遅延制約下での面積最小解（２） required time（以降RT）を仮の値でN個、計算しておいてあとでもっとも実際の値に近いものを選ぶ RTの下限は遅延最小解の遅延時間←これより速い遅延時間は実現できない RTの上限は面積最小解の遅延時間←これより遅い遅延時間は役に立たない 2018/11/9

2018/11/9 遅延制約下での面積最小解（３） (面積, 遅延) = (a1, d1) の解と (a2, d2) の解に対して、次式が成り立つ時(a2, d2) の解は最適解として用いられない。 a1 <= a2, d1 <= d2 最適解の可能性がある解のみをリストで保持 遅延 面積 2018/11/9 39

低消費電力向けのマッピング 直感的には面積を最小化すればよいように思えるが、、、、 ゲートで消費される電力とは 2018/11/9 低消費電力向けのマッピング 直感的には面積を最小化すればよいように思えるが、、、、 ゲートで消費される電力とは P = CV2f C:このゲートの駆動する容量 V:電源電圧 f:スイッチング周波数 Cは概ね面積に比例するが、fは回路の構造できまる 2018/11/9

低消費電力向けのマッピング例（１） 2NANDの出力の1の出現確率は Po = 1 – (Pa × Pb) 2018/11/9 低消費電力向けのマッピング例（１） 2NANDの出力の1の出現確率は　Po = 1 – (Pa × Pb) 出現確率Pより遷移確率Qは Q = P × (1 – P) 2018/11/9

低消費電力向けのマッピング例（２） 使用するセルが同じでも信号遷移確率が異なれば消費電力が異なる。 2018/11/9 低消費電力向けのマッピング例（２） 使用するセルが同じでも信号遷移確率が異なれば消費電力が異なる。 大まかに言って遷移確率の高い信号と0とのANDをとれば(1とのORでも可)、その遷移をマスクすることができるので消費電力を下げることができる。 2018/11/9

FPGA用EDA技術 やはり少量生産にとってマスクコストの高騰は致命的 仕様変更やバグ修正のためのリメイクなどもってのほか 2018/11/9 FPGA用EDA技術 やはり少量生産にとってマスクコストの高騰は致命的 仕様変更やバグ修正のためのリメイクなどもってのほか ⇒チップ製造後にプログラムできるFPGAの優位性 微細化の恩恵で大容量化・高速化（低消費電力化は未だ） FPGA用のEDA技術はますます重要 2018/11/9

2018/11/9 LUT（look-up table） 2018/11/9

2018/11/9 クラスタ 入力が共通ないくつかのLUTをひとまとめにする。 2018/11/9

Island Style Architecture 2018/11/9 Island Style Architecture クラスタの外側に配線・接続用のスイッチが並ぶ。 2018/11/9

FPGAの設計フロー 論理設計（ASICと同様、、、でいいのか？） LUTへのマッピング クラスタへのパッキング 配置・配線 2018/11/9 FPGAの設計フロー 論理設計（ASICと同様、、、でいいのか？） LUTへのマッピング クラスタへのパッキング 配置・配線 遅延時間・消費電力ともにグローバル配線（スイッチ）の削減が鍵→EDA技術＆FAPGAアーキテクチャ 2018/11/9

遅延最小を目的とした LUT型FPGAのテクノロジ・マッピング 2018/11/9 遅延最小を目的とした LUT型FPGAのテクノロジ・マッピング 入力：Kバウンデッド・ネットワーク ノードがK入力以下の論理関数を持つような ループを持たない有向グラフ 出力：LUTからなる等価なネットワーク LUTからなるネットワークの遅延見積もり： LUTの段数 LUT内部の遅延: ほぼ均一 LUT間の配線遅延: 一定の固有遅延を仮定 LUTの個数も少ない方が望ましい 配線の自由度を高めるため LUTの段数最小で個数が少ないネットワークを 生成するテクノロジ・マッピング 2018/11/9

Ｋバウンデッド・ネットワーク ループを持たない有向グラフ ノード 入力数がK以下 K入力以下の論理関数を持つ 辺 2018/11/9 Ｋバウンデッド・ネットワーク ループを持たない有向グラフ ノード 入力数がK以下 K入力以下の論理関数を持つ 辺 ノード i の出力が ノード j の入力であるとき 有向辺 (i, j) が存在 プライマリインプット 入力辺を持たないノード プライマリアウトプット 出力辺を持たないノード 2018/11/9

Kフィージブル・カットとマッチ Kフィージブル・カット t から入力側へ辿って 得られるネットワークに おけるノードの分割 2018/11/9 Kフィージブル・カットとマッチ K=3 Kフィージブル・カット　 t から入力側へ辿って 得られるネットワークに おけるノードの分割 カットの境界における 入力側のノード数がK以下 マッチ Ｋフィージブル・カットの の誘導グラフ K入力LUTで被覆できる k-feasible cut マッチ LUTに対応 t 2018/11/9

ネットワークの段数 POからPIまでの 経路のうち ノード数が最大である 経路上のノード数 段数 : 3 2018/11/9

段数最小テクノロジ・マッピング アルゴリズム：FlowMap 2018/11/9 段数最小テクノロジ・マッピング アルゴリズム：FlowMap FlowMap: 段数最小ネットワークを生成するアルゴリズム ネットワークの各部が段数最小な解を生成 LUTの個数が少なくなるようなヒューリスティック 出力における段数を保つ範囲で LUTの個数を改善するための後処理 近傍に存在するLUTを出来る限りまとめる 手順 ラベルづけ マッピング 個数改善の後処理 2018/11/9

FlowMap : ラベルづけ ラベル ： ノードをPOとみなしたときの LUTからなる段数最小ネットワークの段数 2018/11/9 FlowMap : ラベルづけ ラベル ： ノードをPOとみなしたときの LUTからなる段数最小ネットワークの段数 　　　　　　：ノード t における 　　　　　Kフィージブル・カット　　　　　　　　 プライマリ・インプットからプライマリ・アウトプットへ順に ノードごとにラベルの計算を行う 2018/11/9

FlowMap : ラベルづけの例 t t 2 1 1 1 1 1 1 k-フィージブル・カット 1 1 2 2 k-フィージブル・カット 2018/11/9 FlowMap : ラベルづけの例 1 1 1 1 1 1 k-フィージブル・カット 1 1 2 2 k-フィージブル・カット 2 2 2 2 k-フィージブル・カット t t 2 2018/11/9

FlowMap : マッピング PO側からPI側へ ラベルに対応する マッチを選択 全てのノードにおいて 段数が最小 2018/11/9 FlowMap : マッピング PO側からPI側へ ラベルに対応する マッチを選択 全てのノードにおいて 段数が最小 出力における 段数最小が保証される ラベルに対応するマッチが 複数存在した場合 マッチに被覆されるノード数が 最大のマッチを選択 1 1 1 1 2 2 2 2 2018/11/9

FlowMap : LUTの個数を改善するための後処理 2018/11/9 FlowMap : LUTの個数を改善するための後処理 LUTの個数を減らすためのヒューリスティック LUTとその近傍に存在する他のLUTを 可能であれば1つのLUTにまとめる LUTネットワークの出力における段数が増えない範囲で行う LUTの段数が最小かつ個数が最小である 厳密解が得られる保証はない 2018/11/9

2018/11/9 その他のトピックス ファンアウト最適化 タイミング最適化 配線遅延の考慮⇒レイアウトとの融合 2018/11/9