« zurück

Kolloquium | 23.06. - 17.00 Uhr c.t. | Rotunde
Masahiro Fujita
VLSI Design and Education Center, University of Tokyo

A Formal Approach for Debugging Arithmetic Circuits

Abstract
This talk presents an automatic debugging algorithm for a post synthesis combinational arithmetic circuit. The approach is robust under wide varieties of arithmetic circuit architectures and design optimizations. The debugging algorithm in this article consists of three phases of partial product initialization, XOR extraction and carry-signal mapping. The run-time complexity of the conventional carry signal mapping algorithms like the approaches proposed by Prof. Kunz and others is exponential. In the proposed algorithm, however, by making use of important design issues we categorize the extracted XORs into half/full-adders to make a very fast debugging algorithm. This approach is robust under multi-operand adders, pin- swap techniques, optimizations concerning carry signals or XOR terms and irregularities like commutative and associative laws. Moreover, the XOR extraction in the proposed algorithm is much faster than the conventional techniques as it does not evaluate the whole net-list. The bugs detected in the partial product initialization and the carry-signal mapping can be replaced with proper logics automatically. On the other hand, during the XOR extraction phase, the problematic XORs are only reported by the algorithm and no automatic replacement is performed for such logic gates. In order to evaluate the effectiveness of our approach, we run it on several arithmetic circuits.

Biography
Masahiro Fujita received his Ph.D. degree in Information Engineering from the University of Tokyo in 1985 and shortly after joined Fujitsu Laboratories Ltd. From 1993 to 2000, he had been assigned to Fujitsu's US research office and directed the CAD research and development group. In March 2000, he joined the department of Electronic Engineering in the University of Tokyo as a professor. He is now a professor at VLSI Design and Education Center (VDEC) in the university. He has co-authored 7 books, and has over 150 publications. He has received several awards from Japanese major scientific societies on his works in formal verification and logic synthesis. His doctor degree thesis was written in early 80's and on model checking. Since then he has been involved in many research projects on various aspects of formal verification. His current research interests include synthesis and verification in higher level design stages, hardware/software co-designs and also digital/analog co-designs.