九州大学 研究者情報
発表一覧
松永 裕介(まつなが ゆうすけ) データ更新日:2019.06.21

准教授 /  システム情報科学研究院 情報知能工学部門 先端情報・通信機構


学会発表等
1. 松永 裕介, 論理暗号化に対する効率的なSAT攻撃アルゴリズムの評価, 電子情報通信学会VLD研究会, 2019.03, 本稿では論理IPの剽窃や盗用を防ぐための論理暗号化手法に対する攻撃手法
であるSAT攻撃の効率的なアルゴリズムの評価結果について報告する.
既存のSAT攻撃アルゴリズムと,
追加する節の元となっている論理回路の等価性を調べることで
重複した節の追加を行わない改良版のSAT攻撃アルゴリズム
をベンチマーク回路に適用して計算時間などの評価を行った.
ほとんどの例で生成される変数や節の数,計算時間などが
削減されており,提案手法の有効性を明らかにしている..
2. 松永 裕介, 論理暗号化に対するSAT攻撃の効率的なアルゴリズムについて, 電子情報通信学会VLD研究会, 2018.12, 本稿では論理IPの剽窃や盗用を防ぐための論理暗号化手法に対する攻撃手法
であるSAT攻撃の効率的なアルゴリズムについて述べる.
既存のSAT攻撃アルゴリズムは従来の暗号化手法のほとんどを解読することが
可能であるが,
多大な計算時間を要する場合もある.
これはSAT問題を繰り返し解いていく際に追加される節の数が膨大になってい
ることに起因する.
そこで,追加する節の元となっている論理回路の等価性を調べることで
重複した節の追加を行わない改良版のSAT攻撃アルゴリズムを開発した.
実験結果によればほとんどの例題に対してより短い時間で処理を行っており,
最大で35倍の高速化を達成している..
3. 松永 裕介, テストセット最小化問題の両立集合被覆問題への定式化とその解法, 情報処理学会DAシンポジウム, 2018.08, 本稿ではLSIの製造故障に対するテストパタン集合の最小化問題に対する新しい定式化を示す.
通常,一つのテストパタンは複数の故障を検出することができる.この特徴を考慮すると
テストパタン集合の最小化問題は集合被覆問題と考えることができる.
一方,不定値('X')を含む複数のテストパタンは同じビット位置に相反する値を持たない限りマージして
一つのテストパタンにまとめることが可能である.
この特徴を考慮するとテストパタンの最小化問題は
グラフ彩色問題とみなすことができる.
実際には,この2つの特徴を同時に考慮する必要があるため既存の組み合わせ最適化問題として定式化することは
難しい.そこで両立集合被覆問題と名付けた新たな組み合わせ最適化問題を定義する.
また,この問題に対するヒューリスティック解法を提案する..
4. 松永 裕介, 論理合成の誤り修正手法を用いた論理暗号化手法の評価, 電子情報通信学会VLD研究会, 2018.03.
5. 松永 裕介, SATソルバを用いた低消費電力向けテストパタン圧縮手法について, 電子情報通信学会VLD研究会, 2017.11, 本稿ではSATソルバを用いた低消費電力向けテストパタン圧縮手法の提案を行
う.
基本となるアイデアは,元の制約式に複数の変数のXORで構成された制約式を追加することで
SAT問題のサンプリングを行う手法を用いて候補となるパタンを生成し,
そのなかから与えられた信号遷移回数の制約を満たしつつ要素数が少なくなる
テストパタン集合を最小集合被覆問題を解くことで得るというものである.
実験結果より,サンプリングの数を増やすことでより要素数の少ないテストパ
タン集合が得られることが確認されている.
提案するヒューリスティックの有効性およびロバスト性を示している. .
6. 松永 裕介, XOR制約を用いたSAT問題のサンプリングとテストパタン生成への応用, 情報処理学会DAシンポジウム, 2017.09.
7. 松永 裕介, 信号遷移回数を考慮したテストパタン生成のためのSAT問題のサンプリング手法について, 電子情報通信学会VLD研究会, 2017.06, 本稿では信号遷移回数を考慮した遷移故障向けテストパタンを生成する
SATソルバを用いた手法について考察を行う.
通常のSATソルバを用いた手法では故障を検出する論理的な制約を
満たすテストパタンが唯一得られるだけで信号遷移回数のコントロールを
行うことはできない.
そこで,テストパタン生成問題を表すCNF式にランダムに生成した式を追加
することで元の問題に対するランダムサンプリングを行う手法を用いて
テストパタンのランダムサンプリングを行うアルゴリズムを提案する.
生成された複数のパタンの中から信号遷移回数や消費電力などの尺度
で優れたパタンを選択することで従来不可能であったSATソルバを
用いたテストパタン生成において解の質をコントロールすることが
可能となっている. .
8. 松永 裕介, SATソルバを用いた信号遷移回数を考慮した遷移故障向けテストパタン生成手法について, 電子情報通信学会VLD研究会, 2016.11, 本稿では信号遷移回数を考慮した遷移故障向けテストパタンを生成する
SATソルバを用いた手法について考察を行う.
通常のSATソルバを用いた手法では故障を検出する論理的な制約を
満たすテストパタンが唯一得られるだけで信号遷移回数のコントロールを
行うことはできない.
そこで,SATを用いたテストパタン生成アルゴリズムに修正を行って,
故障検出を行うパタンの集合を積和形論理式の形で出力し,
そこからランダムサンプリングを行い,
そのなかから信号遷移回数の少ないパタンを選択する手法を提案する.
.
9. 松永 裕介, モンテカルロ木探索法を用いたテクノロジマッピングアルゴリズムについて, 情報処理学会DAシンポジウム, 2016.09, 本稿ではモンテカルロ木探索をLUT型FPGA向けテクノロジマッピングに応用し
たアルゴリズムについて述べる.
テクノロジマッピング問題が複雑になる原因はファンアウト部分の取り扱いに
ある.
そこで,予め回路のどの部分がファンアウト境界になるかを決めた上で
既存のテクノロジマッピングのアルゴリズムであるDAG Coveringアルゴリズム
を適用することで解空間を区切って探索する方法を考案した.
このアルゴリズムとモンテカルロ木探索を組み合わせたテクノロジマッピング
アルゴリズムの紹介を行う.
.
10. 松永 裕介, 信号遷移回数を考慮したランダムテストパタン生成法について, 電子情報通信学会VLD研究会, 2016.06, 本稿ではランダムパタンを用いて遷移故障向けのテストパタン生成をする際に,
信号遷移回数を考慮する手法について提案する.
具体的には各々のパタンを印加した時の信号遷移回数に基づいた確率分布を持
つマルコフ連鎖モデルを構築し,
そのマルコフモデル上でランダムサンプリングを行うことで信号遷移回数を考
慮したランダムパタンの生成を行うものである.
ベンチマークを用いた実験の結果,提案手法で生成されたパタンは検出する故
障数では信号遷移回数に制限を設けない単純な手法の結果とほぼ同等の結果を
得られることがわかった.
ただしパタン数は多くなる傾向にある.
.
11. 松永 裕介, モンテカルロ木探索のCAD問題への応用について, 電子情報通信学会VLD研究会, 2015.12, [URL].
12. 松永 裕介, ナンバーリンク問題に対する命題論理式のエンコーディング法に評価について, 電子情報通信学会VLD研究会, 2015.12.
13. 松永 裕介, SATソルバによる両立故障集合検査を用いたテストパタン圧縮手法について, 情報処理学会DAシンポジウム, 2015.08.
14. 松永 裕介, 大規模回路向けテストパタン集合最小化手法の高速化について, 電子情報通信学会VLD研究会, 2015.06, [URL], 本稿では大規模回路に適用可能なテストパタン集合最小化手法の高速化技術につ
いて述べる.
具体的には,故障もしくは故障集合の検出条件に対する,十分割り当てと必要割
り当てという概念を提案し,それらを用いて,故障間の支配関係や両立関係の
検査を効率よく行うアルゴリズムを提案している.
ベンチマーク回路を用いた評価実験の結果,
同様の処理を行う既存手法に比べて同等の解をはるかに高速に求めることに成功している.
特に大規模な回路に対して高速化の効果が大きい. .
15. 松永 裕介, 大規模回路向け最小テストパタン生成手法について, 電子情報通信学会VLD研究会, 2015.05, [URL].
16. Yusuke Matsunaga, Accelerating SAT-based Boolean matching for heterogeneous FPGAs using one-hot encoding and CEGAR technique, 2015 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015, 2015.03, [URL], This paper describes two speed-up techniques for Boolean matching of LUT-based circuits. One is one-hot encoding technique for variables representing input assignments. Though it requires more variables than existing binary encoding technique, almost all added clauses using one-hot encoding are binary clauses, which are suitable for efficient Boolean constraint propagation. The other is CEGAR (counter example guided abstraction refinement) technique which reduces the CPU time significantly. With both techniques, we can solve Boolean matching problem with 9 input function in 20 milliseconds on average, which is faster than the existing algorithms more than one order of magnitude..
17. 松永 裕介, インデックス生成合成のためのベクトル対集合の非明示的列挙手法について, 電子情報通信学会VLD研究会, 2014.11, [URL], 本稿では並列インデックス生成器を合成する際に必要となるベクタ集合の分割を効率よく表現する手法に
ついて述べる.具体的には,分割により区別されるベクタ対の集合を2 分決定グラフを用いて非明示的に列挙し,分
割に関する演算を2 分決定グラフを用いた論理演算で実現するものである..
18. 松永 裕介, 並列インデックス生成器のための線形変換回路合成手法, 電子情報通信学会VLD研究会, 2014.10, [URL], 本稿では並列インデックス生成器を用いた実
現を対象にした入力変換回路の合成手法について提案を行う.
実験の結果,提案した合成手法で生成した変換回路を並列イン
デックス生成器の入力として用いることで,均一に分布してい
ない例に対しても下限に近いサイズのメモリ量でインデックス
生成器を構成できることが示されている..
19. 松永 裕介, CEGAR法を用いたLUT回路のブーリアンマッチングの高速化手法, 電子情報通信学会VLD研究会, 2014.07, [URL], 本稿では複数のLUT からなる回路が与えられた論理関数を実現できるかどうかを調べるブーリアンマッチ
ングの高速化手法について述べる.従来の手法ではナイーブな段階的探索を用いていたのに対して,本稿で提案する
改良アルゴリズムはCEGAR(counter example guided abstraction refinment: 反例に基づく段階的抽象化) と呼ばれる手法
を用いてさらなる高速化を達成している..
20. 松永 裕介, Synthesis Algorithm of Parallel Index Generation Units, Design, Automation & Test in Europe (DATE-2014), 2014.03, The index generation function is a multi-valued logic function which checks if the given input vector is a registered or not, and returns its index value if the vector is registered. If the latency of the operation is critical, dedicated hardware is used for implementing the index generation functions. This paper proposes a new method implementing the index generation functions. This method requires only one memory access while the existing method requires twice. The proposed method also has an advantage for total memory size against to the existing method..
21. 松永 裕介, LUT回路のブーリアンマッチング手法について, 電子情報通信学会VLD研究会, 2014.01, [URL], 本稿では複数のLUTからなる回路が与えられた論理関数を実現できるかどうかを
調べるブーリアンマッチングの高速化手法について述べる.
高速化手法は2つある.1つは入力順序の割り当てをone-hot符号化された変数を
用いて表す手法であり,従来の2進符号化に比べると必要となる変数の数は増え
るが,ほとんどの制約が2項節の形で与えられるため,
SATソルバにおいて効率的な値の伝搬が行える.
もう1つは段階的探索手法で,マッチングが失敗する例において,
部分的な制約式のみを評価することで早めに充足不能と判定を行い,無駄な探
索を省いている.充足可能となる場合でも以前の評価の結果得られた学習節が
後の評価の際にも用いられるのでオーバーヘッドは少ない. .
22. Yusuke Matsunaga, Synthesis algorithm of parallel index generation units, 17th Design, Automation and Test in Europe, DATE 2014, 2014, [URL], The index generation function is a multi-valued logic function which checks if the given input vector is a registered or not, and returns its index value if the vector is registered. If the latency of the operation is critical, dedicated hardware is used for implementing the index generation functions. This paper proposes a method implementing the index generation functions using parallel index generation units. A novel and efficient algorithm called 'conflict free partitioning' is proposed to synthesis parallel index generation units. Experimental results show the proposed method outperforms other existing methods..
23. 松永 裕介, 並列インデックス生成器の合成アルゴリズムについて, 電子情報通信学会VLD研究会, 2013.11, [URL], インデックス生成関数とは,与えられた入力ベクタが既に登録されたものであるかを調べ,もし登録されていた場合にはそのインデックス番号を返すたち論理関数である.
本稿では複数のインデックス生成器を並列に構成してインデックス生成関数を実現する場合の合成アルゴリズムについて述べる.
具体的には,``コンフリクトフリー分割''と呼ばれる新規の効果的なアルゴリズムを提案している.実験結果によれば既存手法に比べて約半分程度のメモリ容量でインデックス生成関数を実現できている. .
24. 松永 裕介, 完全ハッシュ関数のハードウェア向け実装について, 情報処理学会DAシンポジウム, 2013.08, 与えられたデータの集合に対して重複しないインデックスを返す関数を完全ハッシュ関数と呼ぶ.
本稿では,ハードウェアの実装に適した完全ハッシュ関数の構成法について述べ る.
.
25. 松永 裕介, 面積および遅延を削減したインデックス生成関数の構成法について, 電子情報通信学会VLSI設計技術研究会, 2013.07, インデックス生成関数とは,与えられた入力ベクタが既に登録されたものであるかを調べ,もしも登録されていた場合にはそのインデックス番号を返す多値論理関数である.インデックス生成関数の応答時間が重要な場合には,専用のハードウェアを用いた実現方法が用いられる.本稿では,従来手法では連続した2回のメモリアクセスを必要としてのに対して,1回のメモリアクセスで結果を出力するインデックス生成関数の実現方法について述べる.本手法は総メモリ量の面においても従来手法よりも効率的である.
.
26. 松永 裕介, An Efficient Implementation of The Index Generation Functions, International Workshop on Logic and Synthesis (IWLS2013), 2013.06, The index generation function is a multi-valued logic function which checks if the given input vector is a registered or not, and returns its index value if the vector is registered. If the latency of the operation is critical, dedicated hardware is used for implementing the index generation functions. This paper proposes a new method implementing the index generation functions. This method requires only one memory access while the existing method requires twice. The proposed method also has an advantage for total memory size against to the existing method.
.
27. 松永 裕介, SATソルバを用いたテスト生成の高速化手法について, 電子情報通信学会ディペンダブルコンピューティング研究会, 2013.02, SATソルバを用いてテスト生成を行なう場合,単純な方法では1つの故障に対するテスト生成問題を1つの充足可能性判定問題として表してSATソルバを起動する.本稿では複数の故障に対するテスト生成問題をいくつかの制御変数を付加した1つの充足可能性判定問題として表すことで,テスト生成全体にかかる計算時間の短縮を行なう手法について述べる.いくつかの工夫を行なうことで,数倍から10倍程度の高速化を達成している.
.
28. 松永裕介, DAGパタンを効率よく共有するためのデータ構造の提案, 情報処理学会システムLSI設計技術研究会(デザインガイア), 2012.11, 論理合成処理のテクノロジマッピングやローカルリライティングではサイズの小さな多数のパタンを用いている.メモリの使用を効率化するために,複数のパタン中の同形の部分グラフを共有しているが,それでも多くのメモリ領域を必要とする場合が多い.そこで,本稿では枝に入力変数の反転と置換を行なうNP変換の属性を付加することでより多くの部分グラフ共有可能とするデータ構造について提案を行なう..
29. 松永 裕介, 効率的な間接含意の計算アルゴリズムについて, 電子情報通信学会VLSI設計技術研究会, 2012.07, 本稿では,論理回路の2つの信号線間に成り立つ含意関係のうち,直接的な操作では求めることのできない間接含意を効率よく求めるアルゴリズムについて述べる.本アルゴリズムは個々の信号線の値を0または1に決定する原因となる値の割り当てリストを推移的に計算することによって高速に多くの間接含意を求めるものである.また,比較のためにSAT(充足可能性判定問題)ソルバを用いて全ての間接含意を列挙する実験を行い,提案アルゴリズムの効率性と効果を確認した.
.
30. 髙田 大河, Yoshimura Masayoshi, Yusuke Matsunaga, An Efficient Fault Simulation Algorithm for Analyzing Incorrect State Transitions induced by Soft Errors in Sequential Circuits, International Workshop on Logic and Synthesis (IWLS2012), 2012.06.
31. Taiga Takata and Yusuke Matsunaga, A Quantitative Analysis of Soft Error Propagation in Sequential Circuits, 8th Workshop on Silicon Errors in Logic - System Effects (SELSE8), 2012.03.
32. 髙田 大河, Yusuke Matsunaga, A Quantitative Analysis of Soft Error Propagation in Sequential Circuits, (th Workshop on Silicon Errors in Logic - System Effects (SELESE8), 2012.03.
33. 高田大河、松永裕介, 順序回路におけるソフトエラーの論理マスク効果の効果的な解析手法について, VLSI設計技術研究会, 2012.03.
34. Shusuke Yoshimoto, Takuro Amashita, Masayoshi Yoshimura, Yusuke Matsunaga, Hiroto Yasuura, Shintaro Izumi, Hiroshi Kawaguchi, Masahiko Yoshimoto, Neutron-induced soft error rate estimation for SRAM using PHITS, 2012 IEEE 18th International On-Line Testing Symposium, IOLTS 2012, 2012, [URL], This paper presents a novel neutron-induced soft-error-rate (SER) estimation tool with a particle transport code: PHITS. The proposed tool can calculate the SER according to various data patterns and the layout of the memory cells in an SRAM. As layouts, two kinds of an NMOS-PMOS-NMOS 6T and an inside-out PMOS-NMOS-PMOS versions are considered. The proposed tool distinguishes a single-event-upset (SEU) SER, a horizontal multiple-cell-upset (MCU) SER, and a vertical MCU SER using an extracting function. The horizontal MCU SER in the inside-out version of the PMOS-NMOS-PMOS 6T SRAM cell layout was expected to be 26-41% less than that of the general NMOS-PMOS-NMOS 6T cell layout..
35. 松永裕介, 論理合成・検証の研究開発用インフラストラクチャYmtoolsの開発, VLSI設計技術研究会, 2011.11.
36. Masayoshi Yoshimura, Yusuke Akamine and Yusuke Matsunaga, A Soft Error Tolerance Estimation Method for Sequential Circuits, EEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems 2011 (DFT 2011), 2011.10.
37. 綾部 秀紀, 吉村正義, 松永裕介 , 組み合わせ回路のソフトエラー耐性評価における近似手法の統計科学的な精度評価
, VLSI設計技術研究会, 2011.09.
38. Taiga Takata, Yusuke Matsunaga, A robust algorithm for pessimistic analysis of logic masking effects in combinational circuits, 2011 IEEE 17th International On-Line Testing Symposium, IOLTS 2011, 2011.09, [URL], Analyzing logic masking effects in combinational circuits is an important key to evaluate soft error tolerance of circuits. Logic masking effects can be analyzed exactly with employing fault simulation. The computing complexity of a fault-simulation-based algorithm, however, is proportional to the square of circuit size, which might be unacceptable to achieve a scalable analyzer. On the other hand, a heuristic algorithm AnSER can analyze logic masking effects approximately in runtime proportional to circuit size. AnSER, however, is possible to analyze logic masking effects optimistically especially for circuits protected with spatial redundancy, which might not be suitable for soft error tolerant designs. This paper shows a robust algorithm to analyze logic masking effects pessimistically. Pessimistic analysis is guaranteed with employing the proposed algorithm, while the computing complexity of the proposed algorithm is proportional to circuit size. Experimental results show that the proposed algorithm runs about 91 times faster than a fault-simulation-based exact algorithm with 11.5% overestimate for average susceptibility to errors. For circuits partially protected with spatial redundancy, the proposed algorithm has estimated average susceptibility with 37.9% overestimates on average, while AnSER has estimated average susceptibility with 96% underestimates on average..
39. S. Yoshimoto, T. Amashita, D. Kozuwa, T. Takata, M. Yoshimura, Yusuke Matsunaga, Hiroto Yasuura, H. Kawaguchi, M. Yoshimoto, Multiple-bit-upset and single-bit-upset resilient 8T SRAM bitcell layout with divided wordline structure, 2011 IEEE 17th International On-Line Testing Symposium, IOLTS 2011, 2011.09, [URL], This paper presents a new 8T (8-transistor) SRAM cell layout mitigating multiple-bit upset (MBU) in a divided wordline structure. Because bitlines along unselected columns are not activated, the divided wordline structure eliminates a half-select problem and achieves low-power operation, which is often preferred for low-power / low-voltage applications. However, the conventional 8T SRAM with the divided wordline structure engenders MBUs because all bits in the same word are physically adjoining. Consequently, error correction coding (ECC) techniques are difficult to apply. This paper presents a new 8T cell layout pattern that separates internal latches in SRAM cells using both an n-well and a p-substrate. We investigated an SEU cross section of nMOS that is 3.5-4.5 times higher than that of pMOS. Using an iRoC TFIT simulator, we confirmed that the proposed 8T cell has better neutron-induced MBU tolerance. The MBU in the proposed 8T SRAM is improved by 90.70% and the MBU soft error rate (SER) is decreased to 3.46 FIT at 0.9 V when ECC is implemented. Additionally, we conducted Synopsys 3-D TCAD simulation, which indicates that the LET threshold (LETth) in single-event upset (SEU) is also improved by 66.47% in the proposed 8T SRAM by a common-mode effect..
40. Taiga Takata and Yusuke Matsunaga, A Robust CODC-based Heuristic to Extract Observability Don't Care
Set, 20th International Workshop on Logic and Synthesis 2011 (IWLS 2011), 2011.08.
41. Taeko Matsunaga, Shinji Kimura and Yusuke Matsunaga, Synthesis of GPC-based Compressor Trees Targeting Delay and Power Aware Implementation on FPGAs, 20th International Workshop on Logic and Synthesis 2011 (IWLS 2011), 2011.08.
42. Taeko Matsunaga, Shinji Kimura and Yusuke Matsunaga, Power and Delay Aware Synthesis of Multi-Operand Adders Targeting LUT-based FPGAs, International Symposium on Low Power Electronics and Design 2011 (ISLPED 2011), 2011.08.
43. Shusuke Yoshimoto, Takuro Amashita, Daisuke Kozuwa, Taiga Takata, Masayoshi Yoshimura, Yusuke Matsunaga, Hiroto Yasuura, Hiroshi Kawaguchi and Masahiko Yoshimoto , Multiple-Bit-Upset and Single-Bit-Upset Resilient 8T SRAM Bitcell Layout with Divided Wordline Structure
, 17th IEEE International On-Line Testing Symposium 2011 (IOLTS 2011), 2011.07.
44. Taiga Takata and Yusuke Matsunaga, A Robust Algorithm for Pessimistic Analysis of Logic Masking Effects
in Combinational Circuits, 17th IEEE International On-Line Testing Symposium 2011 (IOLTS 2011), 2011.07.
45. Yusuke Matsunaga, An EDA tool chain for soft-error tolerant VLSI design, VLSI Test Symposium (VTS2011), 2011.05.
46. Masayoshi Yoshimura, Yusuke Akamine, Yusuke Matsunaga, A soft error tolerance estimation method for sequential circuits, 2011 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, DFT 2011, 2011, [URL], In advanced technology, soft error tolerance of VLSIs decreases. Soft errors might cause VLSIs to failure. However, there is no exact method to estimate soft error tolerance for sequential circuits of VLSIs. We propose an exact method to estimate soft error tolerance for sequential circuits. The failure due to soft errors in sequential circuits is defined by using the modified product machine. The behavior of the modified product machine is analyzed using Markov model strictly. We also propose two acceleration techniques to apply the exact method to larger scale circuits. Two acceleration techniques reduce the number of variables of simultaneous linear equations. We apply the proposed method to ISCAS'89 and MCNC benchmark circuits and estimate soft error tolerance for sequential circuits. Experimental results shows that two acceleration techniques reduce up to 10 times from its original execution time..
47. Taeko Matsunaga, Shinji Kimura, Yusuke Matsunaga, Power and delay aware synthesis of multi-operand adders targeting LUT-based FPGAs, 17th IEEE/ACM International Symposium on Low Power Electronics and Design, ISLPED 2011, 2011, [URL], Recent researches have indicated that multi-operand addition on FPGAs can be efficiently realized as the architecture consisting of a compressor tree which reduces the number of operands and a carry-propagate adder like ASIC by utilizing generalized parallel counters(GPCs). This paper addresses power and delay aware synthesis of GPC-based compressor trees. Based on the observation that dynamic power would correlate to the number of GPCs and the levels of GPCs, our approach targets to minimize the maximum levels and the total number of GPCs, and an ILP-based algorithm and heuristic approaches are proposed. Several experiments targeting Altera Stratix III architecture show that the proposed approach reduced the delay by up to 20% under a slight increase in total power dissipation..
48. 城林 直樹、赤峰 悠介、吉村 正義、松永 裕介, 順序回路のソフトエラー耐性評価における高精度な近似手法, 電子情報通信学会VLD研究会, 2010.05.
49. 長谷川 創、赤峰 悠介、吉村 正義、松永 裕介, 有限状態機械の分割に基づく定常状態確率の近似計算手法, 電子情報通信学会VLD研究会, 2010.05.
50. 松永 裕介, 高位合成における種々の最適化手法について, 第23回 回路とシステム軽井沢ワークショップ, 2010.04.
51. Taeko Matsunaga, Shinji Kimura, Yusuke Matsunaga, Multi-operand adder synthesis on FPGAs using generalized parallel counters, 2010 15th Asia and South Pacific Design Automation Conference, ASP-DAC 2010, 2010.04, [URL], Multi-operand adders usually consist of compression trees which reduce the number of operands per a bit to two, and a carry-propagate adder for the two operands in ASIC implementation. The former part is usually realized using full adders or (3;2) counters like Wallace-trees in ASIC, while adder trees or dedicated hardware are used in FPGA. In this paper, an approach to realize compression trees on FPGAs is proposed. In case of FPGA with m-input LUT, any counters with up to m inputs can be realized with one LUT per an output. Our approach utilizes generalized parallel counters (GPCs) with up to m inputs and synthesizes high-performance compression trees by setting some intermediate height limits in the compression process like Dadda's multipliers. Experimental results show its effectiveness against existing approaches at GPC level and on Altera's Stratix III..
52. 赤峰 悠介、吉村 正義、松永 裕介, 順序回路のソフトエラー耐性評価手法の状態数削減による高速化, 電子情報通信学会VLD研究会, 2010.03.
53. 高田 大河、松永 裕介, フレックスマージ:LUT削減を目的としたLUT型FPGA向け論理最適化手法, 電子情報通信学会VLD研究会(デザインガイア), 2009.12.
54. 赤峰 悠介、吉村 正義、松永 裕介, 順序回路のソフトエラー耐性評価における近似手法の計算精度および実行時間の評価, 電子情報通信学会VLD研究会(デザインガイア), 2009.12.
55. 松永 多苗子, 木村 晋二, 松永 裕介, FPGAを対象としたマルチオペランド加算器合成手法, 情報処理学会DAシンポジウム, 2009.09.
56. 松永 裕介、赤峰 悠介, 順序回路のソフトエラー率解析手法の非明示的列挙による高速化について
, 電子情報通信学会VLD研究会, 2009.09.
57. 赤峰 悠介, 吉村 正義, 松永 裕介, マルコフモデルを用いた順序回路のソフトエラー耐性評価手法, 情報処理学会DAシンポジウム, 2009.08.
58. Taiga Takata and Yusuke Matsunaga, A Power-aware Post-processing under depth constraint for LUT-based FPGA Technology Mapping, International Workshop on Logic and Synthesis 2009, 2009.08.
59. Taeko Matsunaga, Shinji Kimura, and Yusuke Matsunaga, Multi-Operand Adder Synthesis on FPGAs using Generalized Parallel Counters, International Workshop on Logic and Synthesis 2009, 2009.07.
60. Taiga Takata and Yusuke Matsunaga, An efficient cut enumeration for depth-optimum technology mapping for LUT-based FPGAs, ACM Great Lakes Symposium on VLSI, 2009.05.
61. 原田 翔次、赤峰 悠介、吉村 正義、松永 裕介, SER評価のための論理回路におけるパルスの伝搬解析, 電子情報通信学会DC研究会, 2009.04.
62. 平田 元春、吉村 正義、松永 裕介、安浦 寛人, 算術演算器を含む回路に対する高速なソフトエラー率評価手法, 電子情報通信学会DC研究会, 2009.04.
63. 小津和 大昌、吉村 正義、松永 裕介, セルベース設計に適したSER評価の為のパルス発生確率解析手法, 電子情報通信学会DC研究会, 2009.04.
64. 松永裕介、安浦寛人、馬場謙介、吉村正義、佐藤寿倫、杉原真, ディペンダブルVLSI設計技術への挑戦, 電子情報通信学会全国大会, 2009.03.
65. 小玉翔、松永裕介, イニシエーション・インターバルとアロケーションの制約下における総面積最小を目的としたパイプライン・スケジューリング手法, 電子情報通信学会VLD研究会, 2009.03.
66. 高田大河、松永裕介, FPGA向けテクノロジ・マッピングにおける深さ最小ネットワーク生成のための効率的なカット列挙手法, 情報処理学会SLDM研究会, 2009.01.
67. Taiga Takata, Yusuke Matsunaga, An efficient cut enumeration for depth-optimum technology mapping for LUT-based FPGAs, 19th ACM Great Lakes Symposium on VLSI, GLSVLSI '09, 2009, [URL], Recent technology mappers for LUT based FPGAs employ cut enumeration. Although many cuts are often needed to find good network, enumerating all cuts with large size consumes run-time very much. The number of cuts exponentially increases with the size of cuts, which causes long runtime. Furthermore, an inefficiency of bottom-up merging in existing algorithms makes the run-time much longer. This paper presents a novel cut enumeration. The proposed algorithm is efficient because it enumerates cuts without bottomup merging. Our algorithm has two modes; exhaustive enumeration and partial enumeration. Exhaustive enumeration enumerates all cuts. Partial enumeration enumerates partial cuts with a guarantee that a depth-minimum network can be constructed. The experimental results show that exhaustive enumeration runs about 3 times and 8 times faster than existing bottom-up algorithm [1] [2] for K = 8, 9, respectively. The quality of network are the same. Furthermore, partial enumeration runs about 6 times and 18 times faster than bottom-up algorithm for K = 8, 9, respectively. Area of network derived by the set of cuts enumerated by partial enumeration is only 4 % larger than that derived by exhaustive enumeration on average, and the depth is the same..
68. Taeko Matsunaga, Sinji Kimura, and Yusuke Matsunaga, Synthesis of parallel prefix adders considering switching activities, International Conference on Computer Design, 2008.10.
69. 松永裕介, 組み合わせ論理回路におけるソフトエラーの論理マスク効果の正確な見積もり手法について, 情報処理学会SLDM研究会, 2008.10.
70. 松永多苗子、木村晋二、松永裕介, FPGAを対象とした部分積加算回路の合成について, 情報処理学会SLDM研究会, 2008.10.
71. 赤峰悠介、松永裕介, 組み合わせ回路のおけるソフトエラー伝播率計算手法の評価, 電気関連学会九州支部大会, 2008.09.
72. 高田大河、松永裕介, 深さ最小かつLUTの信号遷移確率の総和最小なLUT型FPGA向けテクノロジマッピング, 情報処理学会DA シンポジウム, 2008.08.
73. Taiga Takata, Yusuke Matsunaga, Area recovery under depth constraint by cut substitution for technology mapping for LUT-based FPGAs, 2008 Asia and South Pacific Design Automation Conference, ASP-DAC, 2008.08, [URL], In this paper we present the post-processing algorithm, Cut Substitution, for technology mapping for LUT-based FPGAs to minimize the area under depth minimum constraint. The problem to generate a LUT's network whose area is minimum under depth minimum costraint seems to be as difficult as NP-Hard class problem. Cut Substitution is the process to generate a local optimum solution by eliminating redundant LUTs while the depth of network is maintained. The experiments shows that the proposed method derives the solutions whose area are 9% smaller than the solutions of a previous state-of-the-art, DAOmap on average..
74. 小玉翔、松永裕介, マルチプレクサの削減を目的としたバインディング改善手法, 電子情報通信学会VLD研究会, 2008.05.
75. 松永多苗子、木村晋二、松永裕介, スイッチング確率を考慮した prefix graph 合成手法の改良について, 電子情報通信学会VLD研究会, 2008.05.
76. Tsuyoshi Sadakata and Yusuke Matsunaga, An Efficient Performance Improvement Method Utilizing Specialized Functional Units in behavioral Synthesis, 13th Asia and South Pacific Design Automation Conference, 2008.01.
77. Taiga Takata and Yusuke Matsunaga, Area Recovery under Depth Constraint by Cut Substitution for Technology Mapping for LUT-based FPGAs, 13th Asia and South Pacific Design Automation Conference, 2008.01.
78. Tsuyoshi Sadakata, Yusuke Matsunaga, An efficient performance improvement method utilizing specialized functional units in Behavioral Synthesis, 2008 Asia and South Pacific Design Automation Conference, ASP-DAC, 2008, [URL], This paper proposes a novel Behavioral Synthesis method that improves performance of synthesized circuits utilizing specialized functional units effectively. Specialized functional units (e.g. Multiply-Accumulator) are designed for specific operation patterns to achieve shorter delay and/or smaller area than cascaded basic functional units. Almost all conventional methods cannot use specialized functional units effectively under a total area constraint because of their less flexibility for resource sharing. The proposed method makes it possible to solve module selection, scheduling, and functional unit allocation problems utilizing specialized functional units in practical time with some heuristics, and to reduce the number of clock cycles under total area and clock cycle time constraints. Experimental results show that the proposed method has achieved up to 35% and on average 14% reduction of the number of cycles with specialized functional units in practical time..
79. Taeko Matsunaga, Shinji Kimura, Yusuke Matsunaga, Synthesis of parallel prefix adders considering switching activities, 26th IEEE International Conference on Computer Design 2008, ICCD, 2008, [URL], This paper addresses parallel prefix adder synthesis which targets minimization of the total switching activities under bitwise timing constraints. This problem is treated as synthesis of prefix graphs which represent global structures of parallel prefix adders at technology-independent level. An approach for timing-driven area minimization has been proposed which first finds the exact minimum solution on a specific subset of prefix graphs by dynamic programming, then restructures the result for further reduction by removing restriction on the subset. This approach can be applied for switching cost minimization almost directly, though it is not so effective as area minimization in some cases. In this paper, a heuristic is proposed which estimates the effect of the restructuring phase and improve cost calculation fo some specific cases. Through various kinds of experiments, conditions where this approach can be executed effectively is also discussed. & copy; 2008 IEEE..
80. Taeko Matsunaga, Shinji Kimura, and Yusuke Matsunaga, Power-Conscious Synthesis of Parallel Prefix Adders under Bitwise Timing Constraints, The 14th Workshop on Synthesis and System Integration of Mixed Information technologies, 2007.10.
81. Tsuyoshi Sadakata and Yusuke Matsunaga, Performance Improvement Methods Utilizing Complex Functional Units in Behavioral Synthesis, 2007 IFIP International Conference on Very Large Scale Integration, 2007.10.
82. Taeko Matsunaga and Yusuke Matsunaga, Timing-constrained Area Minimization Algorithm for Parallel Prefix Adders, International Workshop on Logic and Synthesis , 2007.05.
83. Taeko Matsunaga and Yusuke Matsunaga, Area Minimization Algorithm for Parallel Prefix Adders under Bitwise Delay Constraints, ACM Great Lakes Symposium on VLSI, 2007.03.
84. Taeko Matsunaga, Yusuke Matsunaga, Area minimization algorithm for parallel prefix adders under bitwise delay constraints, 17th Great Lakes Symposium on VLSI, GLSVLSI'07, 2007, [URL], This paper addresses parallel prefix adder synthesis which targets area minimization under given timing constraints. This problem is treated as synthesis of prefix graphs which represent global structures of parallel prefix adders, and a two-folded robust heuristic is proposed. The first process is dynamic programming based area minimization (DPAM), where the search space is limited to a specific subset of the whole set of prefix graphs by imposing some restrictions on structure of prefix graphs, and an exact minimum prefix graph for the limited space can be found efficiently by dynamic programming. The second process is area reduction with re-structuring (ARRS),which removes imposed restrictions on structure, and restructures the result of DPAM for further area reduction. Experimental results show that the size of prefix graph can be reduced by about 10% compared to an existing approach, and area at gate level can also be reduced by more than 30% compared to a commercial tool in some case..
85. Makoto Sugihara, Taiga Takata, Kenta Nakamura, Ryoichi Inanami, Hiroaki Hayashi, Katsumi Kishimoto, Tetsuya Hasebe, Yukihiro Kawano, Yusuke Matsunaga, Kazuaki Murakam, Katsuya Okumura, A character size optimization technique for throughput enhancement of character projection lithography, ISCAS 2006: 2006 IEEE International Symposium on Circuits and Systems, 2006.12, We propose a character size optimization technique to enhance the throughput of maskless lithography as well as photomask manufacture. The number of electron beam shots to draw the patterns of circuits is a dominant factor in the manufacture time and the cost for devices. Our technique is capable of drastically reducing them by optimizing the size of characters, which are the patterns to project and are placed on CP masks. Experimental results show that our technique reduced 72.0% of EB shots in the best case, comparing with the ad hoc character sizing..
86. Makoto Sugihara, Kenta Nakamura, Yusuke Matsunaga, Kazuaki Murakami, CP mask optimization for enhancing the throughput of MCC systems, 26th Annual BACUS Symposium on Photomask Technology 2006, 2006.12, [URL], The character projection (CP) is utilized for maskless lithography and is a potential for the future photomask manufacture because the CP lithography can project ICs much faster than point beam projection or variable-shaped beam (VSB) projection. In this paper, we present CP mask optimization for multi-column-cell (MCC) systems, in which column-cells can project patterns in parallel with the CP and the VSB, so that their throughput is maximized. This paper presents an MINLP (mixed integer nonlinear programming) model as well as an MIP (mixed integer programming) model for optimizing a CP mask set of an MCC projection system so that projection time is minimized. The experimental results show that our optimization has achieved 71.3% less projection time for a two-column-cell system than that for a single-column-cell (SCC) system. For the two-column-cell system, it has also achieved 42.6% less projection time than a naive CP mask development approach. The experimental results denote that our optimization achieves projection time reduction more than parallelizing two column-cells by virtually increasing logic cells which are placed on CP masks and decreasing VSB projection..
87. Masayoshi Yoshimura, Yusuke Matsunaga, Development of practical ATPG tool with flexible interface, 15th Asian Test Symposium 2006, 2006.12, [URL], An ATPG tool is constructed by many functions which are pattern generation functions, fault simulation functions, static compaction functions, etc. For evaluating new idea of only one subfunction accurately, it is necessary to develop all functions of the ATPG tool. It is a serious problem for evaluating new ideas. Many of efficient techniques like static learning don't satisfy all evaluation standards of ATPG tools (high fault efficiency, short length of test patterns, and short CPU time, etc.). Effectiveness of these efficient techniques is according to the structure of circuits. If ATPG tools aren't practical, these techniques are not accurately evaluated. In FLEETS, practical and open EDA tools include ATPG tool have been developed for evaluating new ideas. The purpose of developing these EDA tools is to provide environment that facilitates evaluating new ideas. An ATPG tool which has flexible interfaces is developed as a part of environment for developing EDA tools. This ATPG tool has been developed for evaluating new ideas. To achieve this propose, new algorithms as well as the existing algorithms have been developed. Flexible command interfaces are designed to facilitate adding new ideas in the future. The command interface has been written in Tcl/TK[2]. Table 1 shows the command interfaces. A flexible interface was added to this ATPG tool to conduct various experiments. One of examples is that relations between order of selecting faults, number of patterns and CPU Time are examined. Another is that correlation of the number of test patterns and processing time to combination of each algorithm of pattern generation, static compaction, and fault simulation is examined. And, relations between results of static learning and pattern generation are examined. This ATPG tool has been written in C language and can be executed on Linux and Solaris. This ATPG tool was evaluated to combinational circuits of ITC99 benchmark circuits [1]. A fault model was the single stuck-at fault model. The ATPG tool was executed on Pentium4 3.05GHz with 1GB Memory running Linux OS. In the result to 21 all circuits, the number of patterns was 776, processing time were 459.3 seconds and fault efficiency were 99.74% on average. Practical and open ATPG tool for evaluating new ideas has been described. New ideas of ATPG tools can be easily evaluated in a short term. One of the problems in the future is to enable an addition of the algorithm by the user. For solving this problem, it will be designed APIs of ATPG tool which is used by users when users will develop the new algorithms..
88. Makoto Sugihara, Taiga Takata, Kenta Nakamura, Ryoichi Inanami, Hiroaki Hayashi, Katsumi Kishimoto, Tetsuya Hasebe, Yukihiro Kawano, Yusuke Matsunaga, Kazuaki Murakami, Katsuya Okumura, Technology mapping technique for throughput enhancement of character projection equipment, Emerging Lithographic Technologies X, 2006.07, [URL], The character projection is utilized for maskless lithography and is a potential for the future photomask manufacture. The drawback of the character projection is its low throughput and leads to a price rise of ICs. This paper discusses a technology mapping technique for enhancing the throughput of the character projection. The number of EB shots to draw an entire chip determines the fabrication time for the chip. Reduction of the number of EB shots, therefore, increases the throughput of character projection equipment and reduces the cost to produce ICs. Our technology mapping technique aims to reduce the number of EB shots to draw an entire chip for increasing the throughput of character projection equipment. Our technique treats the number of EB shots as an objective to minimize. Comparing with an conventional technology mapping, our technology mapping technique achieved 19.6% reduction of the number of EB shots without any performance degradation of ICs. Moreover, our technology mapping technique achieved 48.8% reduction of the number of EB shots under no performance constraints. Our technique is easy for both IC designers and equipment developers to adopt because it is a software approach with no additional modification on character projection equipment..
89. Makoto Sugihara, Taiga Takata, Kenta Nakamura, Ryoichi Inanami, Hiroaki Hayashi, Katsumi Kishimoto, Tetsuya Hasebe, Yukihiro Kawano, Yusuke Matsunaga, Kazuaki Murakami, Katsuya Okumura, Cell library development methodology for throughput enhancement of electron beam direct-write lithography systems, 2005 International Symposium on System-on-Chip, 2005.12, We propose a cell library development methodology for throughput enhancement of electron beam direct-write (EBDW) systems. First, an ILP (Integer Linear Programming)-based cell selection is proposed for EBDW systems in which both of the character projection (CP) and the variable shaped beam (VSB) methods are available, in order to minimize the number of electron beam (EB) shots, that is, time to fabricate chips. Secondly, the influence of cell directions on area and delay time of chips is examined. The examination helps to reduce the number of EB shots with a little deterioration of area and delay time because unnecessary directions of cells can be removed to increase the number of cells on a CP aperture mask Finally, a case study is shown in which the numbers of EB shots are examined under several cases..
90. Makoto Sugihara, Kazuaki Murakami, Yusuke Matsunaga, Practical test architecture optimization for system-on-a-chip under floorplanning constraints, Proceedings - IEEE Computer Society Annual Symposium on VLSI: Emerging Trends in VLSI Systems Design, 2004.09, [URL], In testing system-on-a-chip (SOC), external pins for test are getting more and more precious hardware resources because the number of external pins is strongly restricted. Cores, which are basic components to build SOCs, are tested via test access mechanisms (TAMs) such as a test bus architecture. When cores are tested via TAMs, test stimuli and test responses for cores have to be transported over these TAMs. There is often the difference between the numbers of input/output ports of cores and the widths of TAMs. This difference causes the serialization of test patterns. It is probable that some parts of TAMs are unused because of the difference. This is a wasteful usage of TAMs. Test scheduling should be done in order to remove such a wasteful usage of TAMs. In this paper, a novel and practical test architecture optimization is proposed such that test time is minimized with floorplanning constraints abided. In this proposal, the computation time for the optimization can be alleviated by floorplanning manipulation. Several experimental results to this optimization are shown to validate this proposal using a commercial LP solver..
91. Hiroyuki Higuchi, Yusuke Matsunaga, Enhancing the performance of multi-cycle path analysis in an industrial setting, Proceedings of the ASP - DAC 2004 Asia and South Pacific Design Automation Conference - 2004, 2004.06, In this paper we enhance the performance of multi-cycle path analysis in an industrial setting. Industrial designs are, in general, more complicated, but contain more information than fundamental sequential circuits. We show how such information is used for improving the quality and the efficiency of multi-cycle path analysis. Specifically, we propose local FSM learning to take into account reachability information. We also propose FF enable learning to accelerate multi-cycle path analysis. Experimental results show that our methods can handle large industrial designs with tens of thousands of FFs and detects more multi-cycle paths faster than conventional ones..
92. Ei Ando, Masafumi Yamashita, Toshio Nakata, Yusuke Matsunaga, The Statistical Longest Path Problem and its Application to Delay Analysis of Logical Circuits, ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, 2002, This paper presents an algorithm for estimating, in the sense below, the length of a longest path of a given directed acyclic graph (DAG) whose edge lengths are given as random variables with normal distributions. Let F(x) be the distribution function of the length of a longest path of a given DAG. The algorithm computes a normal distribution function F̃(x) such that F̃(x) ≤ F(x) if F(x) ≥ α, given a constant α (0.5 ≤ α < 1.0). We conduct two experiments to demonstrate the accuracy of F̃(x)..
93. Yusuke Matsunaga, An Exact and Efficient Algorithms for Disjunctive Decomposition, Synthesis And System Integration of Mixed Technologies (SASIMI'98), 1998.10.
94. Hiroyuki Higuchi, Yusuke Matsunaga, Fast state reduction algorithm for incompletely specified finite state machines, Proceedings of the 1996 33rd Annual Design Automation Conference, 1996.01, This paper proposes a state reduction algorithm for incompletely specified FSMs. The algorithm is based on iterative improvements. When the number of compatibles is likely to be too large to handle explicitly, they are represented by a BDD. Experimental results are given to demonstrate that the algorithm described here is faster and obtains better solutions than conventional methods..
95. Hiroyuki Higuchi, Yusuke Matsunaga, Implicit prime compatible generation for minimizing incompletely specified finite state machines, Proceedings of the 1995 Asia and South Pacific Design Automation Conference, ASP-DAC'95, 1995.12, This paper proposes a new implicit algorithm for excluding dominated compatibles. The algorithm utilizes a novel notion of signatures of compatibles to exclude dominated compatibles efficiently. Though this dominance check is weaker than the conventional one, experimental results show that in many cases the number of excluded compatibles is the same as that by class sets. Proposed method computes prime compatibles more efficiently than conventional methods for many tested large ISFSM's..
96. Yusuke Matsunaga, Patrick C. McGeer, Robert K. Brayton, Computing the transitive closure of a state transition relation, Proceedings of the 30th ACM/IEEE Design Automation Conference, 1993, We describe a new, recursive-descent procedure for the computation of the transitive closure of a transition relation. This procedure is the classic binary matrix procedure of [1], adapted to a BDD data structure, We demonstrate its efficacy when compared to standard iterative methods..
97. Masahiro Fujita, Yusuke Matsunaga, Multi-level logic minimization based on minimal support and its application to the minimization of look-up table type FPGAs, 1991 IEEE International Conference on Computer-Aided Design - ICCAD-91, 1992, The authors present a method for multilevel logic minimization which is particularly suitable for the minimization of look-up table type FPGAs (field programmable gate arrays). Given a set of nodes to be minimized, one first calculates sets of supports which are necessary to construct the functions for the given nodes by applying functional reduction. The functional reduction process guarantees that one can get the minimal support for each node. One then makes a covering table for the set of nodes to be minimized so that one can get the minimal supports to cover all the functions for the given set of nodes to be minimized. The authors present a preliminary implementation and its results for ISCAS combinational benchmark circuits combined with MIS2.1 standard script and a Boolean resubstitution minimizer, and show the effectiveness of the presented method..
98. Masahiro Fujita, Yusuke Matsunaga, Taeko Kakuda, On variable ordering of binary decision diagrams for the application of multi-level logic synthesis, Proceedings the European Conference on Design Automation, 1992, We have developed multi-level logic minimization programs using Binary Decision Diagram (BDD). Here we present variable ordering methods of BDD. The variable ordering algorithm for two-level circuits is based on cover patterns and selects most binate variables first, and the one for multi-level circuits is based on depth first traverse of circuits. In both cases, the acquired variable orderings are optimized by exchanging a variable with its neighbor in the ordering..
99. Kuang Chien Chen, Yusuke Matsunaga, Masahiro Fujita, Saburo Muroga, A resynthesis approach for network optimization, Proceedings of the 28th ACM/IEEE Design Automation Conference, 1991.06, An algorithm, RENO (resynthesis for network optimization), for the optimization of multilevel combinational networks is presented. In RENO, a given network is minimized for area by optimally resynthesizing each gate, using other existing gates in the network. The resynthesis process is based on a covering-set algorithm, which enables one to resynthesize using complex gates instead of only simple gates (e.g., NAND and NOR), thereby exploring more reconfiguration possibilities. Due to the reconfiguration ability of the RENO algorithm, networks optimized by RENO have good quality, even if no network don't-care is used. The RENO algorithm has been implemented in both cube and shared-OBDD data structures. Experimental results obtained by RENO for benchmark functions and comparison with the optimization algorithm used in MIS 2.2 show that RENO is effective for multilevel network optimization..
100. Hitomi Sato, Noboru Takahashi, Yusuke Matsunaga, Masahiro Fujita, Boolean technology mapping for both ECL and CMOS circuits based on permissible functions and binary decision diagrams, Proceedings of the 1990 IEEE International Conference on Computer Design: VLSI in Computers and Processors - ICCD '90, 1990.09, A Boolean technology mapping with permissible functions is presented. This technique makes use of complementary intermediate logic functions of circuits. Therefore, complementary outputs of ECL gates can be easily handled. High-quality synthesized ECL circuits and CMOS circuits free of logical redundancies are generated. Technology-independent networks are converted into technology-dependent virtual gates network. Virtual gates have an arbitrary number of fan-ins. CMOS virtual networks consist of only NOR and NAND gates, while ECL virtual networks consists of only OR gates (but each gate has complementary outputs). By considering logic function and the device restrictions these virtual gate networks are translated into cell networks using permissible functions..
101. Masahiro Fujita, Yusuke Matsunaga, Taeko Kakuda, Automatic and semi-automatic verification of switch-level circuits with temporal logic and binary decision diagrams, 1990 IEEE International Conference on Computer-Aided Design - ICCAD-90, 1990, Automatic and semi-automatic verification methods for switch-level circuits are presented. Switch-level circuits with no delay (but with/without charge effects) are automatically verified using a formalism with binary decision diagrams (BDD) and temporal logic. Purely bidirectional transistors, such as those whose signal directions are dynamically determined in operations, are treated in the uniform way as nonbidirectional transistors. In the case of switch-level circuits with arbitrary delays, based on the work by M. E. Leeser (1989), the authors present a semi-automatic verification method which uses a propositional theorem prover using BDD. First some assignments of propositional variables to terms of temporal logic are manually given, and then the automatic theorem prover does verification..
102. Hitomi Sato, Yoshihiro Yasue, Yusuke Matsunaga, Masahiro Fujita, Boolean resubstitution with permissible functions and binary decision diagrams, 27th ACM/IEEE Design Automation Conference, 1990, A new Boolean resubstitution technique with permissible functions and ordered binary decision diagrams (OBDDs) is presented. Boolean resubstitution is one technique for multilevel logic optimization. Permissible functions are special don't care sets. The data structure of permissible functions and logic functions at each node in Boolean networks is represented in terms of OBDD. Therefore, logic functions can be flexibly manipulated and rapidly executed. Boolean resubstitution was also applied to a multilevel logic synthesis. Results of experiments employing the improved OBDD operation and Boolean resubstitution techniques are presented..
103. Yusuke Matsunaga, Masahiro Fujita, Taeko Kakuda, Multi-level logic minimization across latch boundaries, 1990 IEEE International Conference on Computer-Aided Design - ICCAD-90, 1990, A method to minimize sequential circuits is presented. It uses permissible functions extended for sequential circuits, and can make use of don't cares derived from network topology. Also, an efficient binary decision diagram (BDD) implementation of the extended permissible functions is presented by introducing edge attributes that indicate time label to the BDD. Circuits including latches can be efficiently minimized with the proposed method..
104. Yusuke Matsunaga, Masahiro Fujita, Multi-level logic optimization using binary decision diagrams, IEEE International Conference on Computer-Aided Design (ICCAD-89): Digest of Technical Papers, 1989, A multilevel logic optimizer, which is based on the transduction method, is introduced. The original transduction method is good for optimization, but its calculation time and storage area increase exponentially with the number of inputs because of the use of truth tables. To save CPU time and memory space, the authors implemented this algorithm using ordered binary decision diagrams (OBDD) as the data structure for representing logic functions. Since OBDD does not become as large as other representations, it can handle large circuits without partitioning..

九大関連コンテンツ

pure2017年10月2日から、「九州大学研究者情報」を補完するデータベースとして、Elsevier社の「Pure」による研究業績の公開を開始しました。
 
 
九州大学知的財産本部「九州大学Seeds集」