Accelerating SAT-Based Boolean Matching for Heterogeneous FPGAs Using One-Hot Encoding and CEGAR Technique

• MATSUNAGA Yusuke

  Department of Advanced Information Technology, Faculty of Information Science and Electronical Engineering, Kyushu University

抄録

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.

収録刊行物

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E99.A (7), 1374-1380, 2016

  一般社団法人 電子情報通信学会

キーワード

• logic synthesis
• technology mapping
• FPGA
• SAT

詳細情報

• CRID: 1390282681287665280
• NII論文ID: 130005159597
• DOI: 10.1587/transfun.e99.a.1374
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E99.A/7/E99.A_1374/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可