非同期式回路の簡単化のための等価性判定アルゴリズムの改良 :条件ループの対応と適応的判定順序変更による高速化

摘要

非同期式回路では、ディジタル回路設計において主流である同期式回路とは異なり、クロック信号を用いずにハンドシェイクプロトコルを用いてタイミングの制御を行っている。ハンドシェイクプロトコルを用いることで、同期式回路と比べて非同期式回路は低消費電力、低ノイズ、高速性が実現できると期待されている。しかし、依存性グラフを用いてパイプライン化した非同期式回路を簡単化するための等価性判定アルゴリズムは、条件ループを持つ場合には対応できないという問題と等価性判定に長時間を要するという問題があった。本稿では、前者を解決するために、条件ループに対応可能なパイプラインイタレーションの境界を用いる手法を提案する。また、後者を解決するために、等価性判定が失敗する分岐系列の偏りに着目して、判定順序を変更することにより高速に判定する手法を提案する。