||松永 裕介, 田村 直之, ＬＳＩの配線問題-ＤＡシンポジウムの配線問題解法コンテスト- (3) ＳＡＴを用いた解法, 情報処理, 59, 3, 232-238, 2018.03, アルゴリズムデザインコンテスト(ADC)の問題は，マスとマスを結ぶ線を引くか引かないかという0/1の判断の結果が解となっているかを判定する問題とみなせるので，比較単純にSAT問題（充足可能性判定問題）に定式化することができる．ただし，ADCでは数十分で数十問の問題を解く必要があり，高速に解を求めるためにはいくつかの工夫が必要となっている．2014年，2015年のコンテストにおいてはSATソルバを用いたチームが最も多くの問題を解いて優勝しておりSATベースの手法の有効性が確認された．その後，2016年，2017年のコンテストにおいては問題が多層配線問題に拡張され，そのためのいくつかのヒューリスティックが提案されている．本稿では，ADCの配線問題をSATソルバを用いて効率よく解く場合に考慮すべき点や多層配線問題に対するヒューリスティックについて解説を行う．.
||松永 裕介, An Accelerating Technique for SAT-based ATPG, IPSJ Trans. System LSI Design Methodology, http://doi.org/10.2197/ipsjtsldm.10.39, 10, 39-44, 2017.03, This paper describes an accelerating technique for SAT based ATPG (automatic test pattern generation). The main idea of the proposed algorithm is representing more than one test generation problems as one CNF formula with introducing control variables, which reduces CNF generation time. Furthermore, learnt clauses of previously solved problems are effectively shared for other problems solving, so that the SAT solving time is also reduced. Experimental results show that the proposed algorithm runs more than 3 times faster than the original SAT-based ATPG algorithm..
||松永 裕介, Accelerating SAT-Based Boolean Matching for Heterogeneous FPGAs Using One-Hot Encoding and CEGAR Technique
, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E99-A, 7, 1374-1380, 2016.07, 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.
||松永 裕介, A test pattern compaction method using SAT-based fault grouping, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E99-A, 12, 2302-2309, 2015.12, This paper presents a test pattern compaction algorithm applicable for
large scale circuits.
The proposed methods formalizes the test pattern compaction problem as
a problem finding minimum set of compatible fault groups.
Also, an efficient algorithm checking compatibility of fault group
The experimental results show that the proposed algorithm achieves
similar or better results against a couple of existing methods,
especially for middle circuits.
||松永 裕介, Synthesis Algorithm for Parallel Index Generator, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E97, 12, 2451-2458, 2014.12, 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 generator. A novel and efficient
algorithm called ‘conflict free partitioning’ is proposed to synthesize
parallel index generators. Experimental results show the proposed method
outperforms other existing methods. Also, A novel architecture of index
generator which is suitable for parallelized implementation is introduced.
A new architecture has advantages in the sense of both area and delay..
||Taeko Matsunaga, Shinji Kimura, 松永 裕介, An Exact Approach for GPC-Based Compressor Tree Synthesis, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E96, 12, 2553-2560, 2013.12, Multi-operand adders that calculate the summation of more than two operands usually consist of compressor trees, which reduce the number of operands to two without any carry propagation, and carry-propagate adders for the two operands in the ASIC implementation. Compressor trees that consist of full adders and half adders cannot be implemented efficiently on LUT-based FPGAs, and carry-chains or dedicated structures have been utilized to produce multi-operand adders on FPGAs. Recent studies indicate that compressor trees can be implemented efficiently on LUTs using Generalized Parallel Counters (GPCs) as the building blocks of compressor trees. This paper addresses the problem of synthesizing compressor trees based on GPCs. Based on the observation that characteristics such as the area, power, and delay correlate roughly to the total number and the maximum level of GPCs, the target problem can be regarded as a minimization problem for the total number of GPCs and the maximum levels of the GPCs, for which an ILP-based approach is proposed. The key point of our formulation is not to model the problem based on the structures of compressor trees like the existing approach, but instead the compression process itself is used to reduce the number of variables and constraints in the ILP formulation. The experimental results demonstrate the advantage of our formulation in terms of the quality and runtime..
||髙田 大河, Yoshimura Masayoshi, 松永 裕介, Efficient Fault Simulation Algorithms for Analyzing Soft Error Propagation in Sequential Circuits, IPSJ Trans. System LSI Design Methodology, http://dx.doi.org/10.2197/ipsjtsldm.6.127, 6, 127-134, 2013.08, This paper presents two acceleration techniques of fault simulation for analyzing soft error propagation in sequential circuits. One is an exact technique and the other is a heuristic technique. Since these techniques are independent on how the logic functions of circuits are evaluated, they can be combined with other techniques which accelerate evaluations of the logic functions of circuits, such as event-driven simulation, single pattern parallel fault propagation (SPPFP). Experimental results show that applying the exact technique makes a fault simulator with event-driven simulation and SPPFP 30-143 times faster. A fault simulator with the exact technique finished for several large-scale circuits in 4.6 hours or less, while a fault simulator without the exact technique could not finish for such circuits in 72 hours. Furthermore, applying the heuristic technique makes a fault simulator with the exact technique about 7-17 times faster with only 0.5-2.2% estimation error..
||Masayoshi Yoshimura, Yusuke Akamine and Yusuke Matsunaga, An Exact Estimation Algorithm of Error Propagation Probability for Sequential Circuits, IPSJ Trans. System LSI Design Methodology, 10.2197/ipsjtsldm.5.63, 5, 63-70, 2012.02.
||Taiga Takata and Yusuke Matsunaga, "A Robust Algorithm for Pessimistic Analysis of Logic Masking Effects in Combinational Circuits, IPSJ Trans. System LSI Design Methodology, 10.2197/ipsjtsldm.5.55, 5, 55-62, 2012.02.
||Taeko Matsunaga, Shinji Kimura and Yusuke Matsunaga,, "Multi-Operand Adder Synthesis Targeting FPGAs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 10.1587/transfun.E94.A.2579, E94, 12, 2011.12.
||Taiga Takata, Yusuke Matsunaga, Efficient Cut Enumeration Heuristics for Depth-Optimum Technology Mapping for LUT-Based FPGAs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 96, 12, 3268-3275, 2009.12.
||Taeko Matsunaga, Shinji Kimura and Yusuke Matsunaga, Framework for Parallel Prefix Adder Synthesis Considering Switching Activities, IPSJ Transactions on System LSI Design Methodology, Vol. 2, pp.212-221, 2009.09.
||Taiga Takata and Yusuke Matsunaga, Area Recovery under Depth Constraint for Technology Mapping for LUT-based FPGAs, IPSJ Transactions on System LSI Design Methodology, Vol. 2, pp.200-211, 2009.09.
||Sho Kodama and Yusuke Matsunaga, Binding Refinement for Multiplexer Reduction, IPSJ Transaction on System LSI Design Methodology, 2009.02.
||Makoto SUGIHARA Yusuke MATSUNAGA Kazuaki MURAKAMI, Character Projection Mask Set Optimization for Enhancing Throughput of
MCC Projection Systems, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E91-A, No.12, pp.3451-5460, 2008.12.
||Tsuyoshi Sadakata and Yusuke Matsunaga, A Behavioral Synthesis Method with Special Functional Units, IEICE Trans. on Fundamentals, Vol. E91-A, No. 4, pp. 1084-1091, 2008.04.
||Taeko Matsunaga and Yusuke Matsunaga, Timing-Constrained Area Minimization Algorithm for Parallel Prefix Adders, IEICE Trans. on Fundamentals, Vol. E90-A, No. 12, pp.2770-2777, 2007.12.
||Tsuyoshi Sadakata and Yusuke Matsunaga, A Simultaneous Module Selection, Scheduling, and Allocation Method Considering Operation Chaining with Multi-Functional Units, IEICE Trans. on Fundamentals, Vol. E90-A, No. 4, pp.729-799, 2007.04.
||M. Sugihara, T. Takata, K. Nakamura, R. Inanami, H. Hayashi, K. Kishimoto, T. Hasebe, Y. Kawano, Y. Matsunaga, K. Murakami, and K. Okumura, Cell library development methodology for throughput enhancement of character projection equipment, IEICE Trans. on Electronics, Vol. E89-C, No. 3, pp. 377-383, 2006.03.
||松永 裕介, 関数分解に基づくLUT型FPGA用ブーリアンマッチングアルゴリズムについて, 情報処理学会論文誌, Vol. 45, No. 5, pp. 1300-1310, 2004.05.
||Yusuke Matsunaga, An Efficient Algorithm Finding Simple Disjoint Decompositions Using BDDs, IEICE Trans. on Fund., E85A, 12, 2715-2724, E85-A, No. 12, pp. 2715-2724, 2002.12.