テクノロジマッピング九州大学大学院システム情報科学研究院情報工学部門松永裕介 2015/10/1 1 論理合成の流れ 2015/10/1 2 セルベース設計手法 • あらかじめ設計されたセルを利用して回路を作る（組み立てる）。 • トランジスタレベルの設計は必要ない。 • 自動合成向き⇒テクノロジマッピング 2015/10/1 3 「テクノロジ」とは • • • • • 使用可能なセルの種類および特性遅延時間の計算モデル最大駆動能力のような設計規則 … 半導体ベンダ、用途などに応じて千差万別 2015/10/1 4 テクノロジ非依存／依存処理 • テクノロジごとに論理合成システム全体を作り直していたら、プロセス技術の進歩に追いつかない • テクノロジに依存しない部分（多段論理合成、最適化）とテクノロジに依存する部分（テクノロジマッピング）に分離する。 • テクノロジマッピングにおいても基本アルゴリズムは共通化して、さまざまなセルライブラリ、設計規則に対応できるようにする。←コンパイラ技術とのアナロジー 2015/10/1 5 テクノロジマッピングの歴史 • ルールベースに基づく手法 – LSS(IBM, ’84) – Socrates(GE, ’86) ⇒ 現Synopsys – LORES/EX(三菱,‘88) • Tree covering – DAGON(AT&T Bell Labs., ’87) • タイミング最適化 – （UCB,’90, ’91) 2015/10/1 6 ルールベースを用いた手法 • テクノロジ毎にルールを用意することでシステムそのものは汎用化できる • ルールを作り、その一貫性を保ち、かつチューニングすることは容易ではない • 局所変換の繰り返しでは大局的な最適化は行えない • ⇒今ではアルゴリズム的に処理することが難しい特定の回路以外は用いられていない 2015/10/1 7 Tree covering • 歴史的にみて最初のテクノロジマッピングのアルゴリズム • 基本アイデアはコンパイラのコード生成アルゴリズム（Bell Labs.のAho） • ブーリアンネットワークを細かな単位ノードに分解して、セルによるカバーを求める • 面積、遅延時間、消費電力などを目的関数、制約条件にして（ある尺度での）最適解を求めることができる • 今日の実用的なシステムで広く用いられる 2015/10/1 8 タイミング最適化問題 • Tree coveringアルゴリズムの拡張 • ファンアウト最適化問題 • 上記２つを統合した大局的な処理 2015/10/1 9 サブジェクトグラフ 2015/10/1 10 多入力ノードの分解 • 任意の論理関数はAND/OR/NOTで表現可能 • 任意のAND/ORは2入力NANDの木に分解可能 • しかし、解は唯一ではない 2015/10/1 11 セルの情報 • 機能を表す論理式⇒2入力NANDに分解 • 面積 – 配線領域の面積の考慮 • 入力端子から出力端子までの遅延時間の計算モデル – 配線遅延の考慮 • 入力端子の負荷容量 • 消費電力の計算モデル 2015/10/1 12 パタングラフ 2015/10/1 13 パタングラフ 2015/10/1 14 ナイーブなマッピング結果 2015/10/1 15 複合セルを用いたマッピング結果（１） 2015/10/1 16 複合セルを用いたマッピング結果（２） 2015/10/1 17 被覆問題としての定式化（１） • パタングラフと一致するサブジェクトグラフの部分グラフをマッチと呼ぶ • テクノロジマッピングとは、サブジェクトグラフ上の全ての節点を被覆するマッチの集合を求めること • ただし、単純な被覆ではない⇒feasibility constraint • マッチの入力は他のマッチの出力でなければならない 2015/10/1 18 被覆問題としての定式化（２） 2015/10/1 19 被覆問題としての定式化（３） 2015/10/1 20 被覆問題としての定式化（４） 2015/10/1 21 被覆問題としての定式化（５） 2015/10/1 22 被覆問題としての定式化（６） 2015/10/1 23 被覆問題としての定式化（７） • このように条件式に否定のリテラルが含まれる被覆問題を binate covering 問題と呼ぶ← 条件式が binate function • binate covering問題はNP問題であることが知られており、実用的には変数の数が数十程度までしか解けない 2015/10/1 24 テクノロジマッピングの近似算法 • binate covering問題を厳密に解くことは難しい←テクノロジマッピングの場合、変数の数は数千～数万 • ではbinate covering問題を解く近似アルゴリズムは？⇒あまり研究されていない • 問題自体をより簡単な問題に近似してしまう ⇒サブジェクトグラフをtree(木)の形に制限する 2015/10/1 25 木状回路への分割 • 複数のファンアウトを持つ部分で回路を分割 • テクノロジマッピングの問題はDAG coveringから tree coveringとなる • tree coveringには効率の良い厳密解法が存在する 2015/10/1 26 分割の弊害 • ファンアウトをまたいだセルの割り当てが行えない • 分割の境界部分での位相合わせが行えない 2015/10/1 27 パタンマッチングアルゴリズム • 基本的にはサブジェクトグラフ上の節点をたどって、パタングラフの節点と一致するか確かめる • パタングラフの節点をたどる順を決めるため edgelist という枝のリストを用いる • NANDの入力は２つあるのでサブジェクトグラフとパタングラフのマッチの仕方が2通り考えられる。そのため、各節点につき最悪2通りずつのマッチを試す必要がある • 実際には対称な入力が多いので試すべきマッチの数はそれほど多くない 2015/10/1 28 パタンマッチングの例 2015/10/1 29 tree coveringアルゴリズム 2015/10/1 30 tree coveringの例 2015/10/1 31 inverter-chainヒューリスティック 2015/10/1 32 遅延最小解を求めるtree covering（１） • 目的関数を遅延時間とする • 遅延時間がセルの種類のみに依存するモデルなら最小面積の場合と同様にtree coveringで最適解を求めることができる • 遅延時間が駆動先の負荷容量に依存するモデルの場合、単純なtree coveringでは解は求められない 2015/10/1 33 遅延モデル • 固定遅延 – セルの種類のみに依存。昔はトランジスタの寄生容量が比較的大きかったので駆動先の負荷容量は無視できた • 負荷依存 – 駆動先の負荷容量の線形関数／非線形関数 – T = T0 + K * l – 最も一般的（少なくとも’90年代は） 2015/10/1 34 遅延最小解を求める tree covering（２） • とにかく駆動先の負荷が決まらないと遅延時間は計算できない • 仮に決めておいてそのときの最適解を持つ • そのような仮の値をN種類、試しておき、後で実際の値に近いものを選ぶ • tree coveringの処理を１つの節点についてN回繰り返すようなもの • Nを大きくすれば解の精度は良くなるが、計算時間と使用メモリ量も比例して大きくなる 2015/10/1 35 遅延最小解を求めるtree covering（３） • 遅延最小解は駆動先の負荷の関数 • しかも負荷の区間の関数なので解が切り替わる点のみを覚えておけばよい • 負荷の値の区間[si, ei]とそのときの最適解miの組をリストの形で保持しておく • 後で実際の負荷が確定したときに該当する区間を探してその区間の最適解miを返す • 処理は複雑だが厳密解を求めることができる。区間の数Nをあらかじめ与えなくて良い 2015/10/1 36 遅延制約下での面積最小解（１） • 出力までのマッピングが確定しないと部分解が制約を満たしているかどうかが分からない←部分的な制約（required time）が与えられないから 2015/10/1 37 遅延制約下での面積最小解（２） • required time（以降RT）を仮の値でN個、計算しておいてあとでもっとも実際の値に近いものを選ぶ • RTの下限は遅延最小解の遅延時間←これより速い遅延時間は実現できない • RTの上限は面積最小解の遅延時間←これより遅い遅延時間は役に立たない 2015/10/1 38 遅延制約下での面積最小解（３） • (面積, 遅延) = (a1, d1) の解と (a2, d2) の解に対して、次式が成り立つ時(a2, d2) の解は最適解として用いられない。 – a1 <= a2, d1 <= d2 遅延 • 最適解の可能性がある解のみをリストで保持面積 2015/10/1 39 39 低消費電力向けのマッピング • 直感的には面積を最小化すればよいように思えるが、、、、 • ゲートで消費される電力とは – – – – P = CV2f C:このゲートの駆動する容量 V:電源電圧 f:スイッチング周波数 • Cは概ね面積に比例するが、fは回路の構造できまる 2015/10/1 40 低消費電力向けのマッピング例（１） •2NANDの出力の1の出現確率は Po = 1 – (Pa × Pb) •出現確率Pより遷移確率Qは Q = P × (1 – P) 2015/10/1 41 低消費電力向けのマッピング例（２） • 使用するセルが同じでも信号遷移確率が異なれば消費電力が異なる。 • 大まかに言って遷移確率の高い信号と0との ANDをとれば(1とのORでも可)、その遷移をマスクすることができるので消費電力を下げることができる。 2015/10/1 42 FPGA用EDA技術 • やはり少量生産にとってマスクコストの高騰は致命的 • 仕様変更やバグ修正のためのリメイクなどもってのほか • ⇒チップ製造後にプログラムできるFPGAの優位性 • 微細化の恩恵で大容量化・高速化（低消費電力化は未だ） • FPGA用のEDA技術はますます重要 2015/10/1 43 LUT（look-up table） 2015/10/1 44 クラスタ • 入力が共通ないくつかのLUTをひとまとめにする。 2015/10/1 45 Island Style Architecture • クラスタの外側に配線・接続用のスイッチが並ぶ。 2015/10/1 46 FPGAの設計フロー • • • • 論理設計（ASICと同様、、、でいいのか？） LUTへのマッピングクラスタへのパッキング配置・配線 • 遅延時間・消費電力ともにグローバル配線（スイッチ）の削減が鍵→EDA技術＆FAPGA アーキテクチャ 2015/10/1 47 遅延最小を目的とした LUT型FPGAのテクノロジ・マッピング • 入力：Kバウンデッド・ネットワーク LUTの段数最小で個数が少ないネットワークを – ノードがK入力以下の論理関数を持つような生成するテクノロジ・マッピングループを持たない有向グラフ • 出力：LUTからなる等価なネットワーク • LUTからなるネットワークの遅延見積もり： LUTの段数 – LUT内部の遅延: ほぼ均一 – LUT間の配線遅延: 一定の固有遅延を仮定 • LUTの個数も少ない方が望ましい – 配線の自由度を高めるため 2015/10/1 48 Ｋバウンデッド・ネットワーク • ループを持たない有向グラフ – ノード • 入力数がK以下 • K入力以下の論理関数を持つ – 辺 • ノード i の出力がノード j の入力であるとき有向辺 (i, j) が存在 – プライマリインプット • 入力辺を持たないノード – プライマリアウトプット • 出力辺を持たないノード 2015/10/1 49 Kフィージブル・カットとマッチ K=3 • Kフィージブル・カット (X , X ) – t から入力側へ辿って得られるネットワークに k-feasible cut おけるノードの分割 – カットの境界における入力側のノード数がK以下 X X マッチ • マッチ – Ｋフィージブル・カットの X の誘導グラフ – K入力LUTで被覆できる 2015/10/1 LUTに対応 t 50 ネットワークの段数 POからPIまでの経路のうちノード数が最大である経路上のノード数段数 : 3 2015/10/1 51 段数最小テクノロジ・マッピングアルゴリズム：FlowMap • FlowMap: 段数最小ネットワークを生成するアルゴリズム 1. ネットワークの各部が段数最小な解を生成 • LUTの個数が少なくなるようなヒューリスティック 2. 出力における段数を保つ範囲で LUTの個数を改善するための後処理 • 近傍に存在するLUTを出来る限りまとめる • 手順 – ラベルづけ – マッピング – 個数改善の後処理 2015/10/1 52 FlowMap : ラベルづけ • ラベル：ノードをPOとみなしたときの LUTからなる段数最小ネットワークの段数 C (t ) ：ノード t における l ( x) m( X , X )  max x X Kフィージブル・カット l (t )  min m( X , X )  1 ( X , X )C ( t ) • プライマリ・インプットからプライマリ・アウトプットへ順にノードごとにラベルの計算を行う 2015/10/1 53 FlowMap : ラベルづけの例 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 k-フィージブル・カット 1 0 0 1 1 2 2 k-フィージブル・カット 2 2 2 2 k-フィージブル・カット t 2015/10/1 t 2 54 FlowMap : マッピング • PO側からPI側へラベルに対応するマッチを選択 – 全てのノードにおいて段数が最小 • 出力における段数最小が保証される – ラベルに対応するマッチが複数存在した場合 • マッチに被覆されるノード数が最大のマッチを選択 2015/10/1 0 0 0 1 0 1 0 1 1 2 2 2 2 55 FlowMap : LUTの個数を改善するための後処理 • LUTの個数を減らすためのヒューリスティック – LUTとその近傍に存在する他のLUTを可能であれば1つのLUTにまとめる • LUTネットワークの出力における段数が増えない範囲で行う • LUTの段数が最小かつ個数が最小である厳密解が得られる保証はない 2015/10/1 56 その他のトピックス • ファンアウト最適化 • タイミング最適化 • 配線遅延の考慮⇒レイアウトとの融合 2015/10/1 57