Computer Logical Design Laboratory

V. B. Marakhovsky Professor	Hiroshi Saito Assistant Professor

In 2005, the laboratory research has been conducting in two directions: CMOS Neuro-Fuzzy Circuits and Devices, and Synthesis of Asynchronous Circuits from Behavioral Specifications. The second direction is connected with the problem of designing CMOS NeuroFuzzy Circuits and Devices. During several last decades for solving sophisticated control problems and data processing neuromorphic methods have been effectively developing, i.e. methods inspired with knowledge of processes in a nervous system. The special place among these methods took ANN (Artificial Neural Networks). ANN can be realized as software implementation on universal or specialized processors. Alternative to this is an analog-digital hardware implementation of the ANN. The main advantage of such implementation is the high value relation throughput/complexity. The main lack of this implementation is the limitation on implementability, i.e. on complexity of functions implemented by one element. Increasing above relation is the main result of the beta-driven circuitry application. The niche for analog-digital ANN actuates: image preprocessing (artificial retina etc.), intellectual fuzzy controllers, robotic control (locomotion, scrub moving etc.), pattern recognition, fault detection, and many others. The research in this direction implies the creation of methods and tools of designing full and semicustom neuro-fuzzy VLSI and embedded devices and systems. These methods and tools include creating threshold elements and devices, learnable beta-driven artificial neurons, fuzzy threshold elements and devices; embedded neuro-processors, neuro-arrays and fuzzy controllers and correspondent IP (intellectual properties); design methods and design know-how for analog/digital devices and systems. The third direction is the development of a synthesis method for asynchronous circuits. Starting from a behavioral description written in C language, the method synthesizes area/performance optimum asynchronous circuits. As a result, asynchronous circuits can be synthesized by designers easily without knowing the detail of asynchronous circuits.The main archeivements of 2005 are: Development of a scheduling method Development of a control synthesis method

Refereed Journal Papers

[hiroshis-01:2005]	H. Saito T. Matsumoto and M. Fujita. An Equivalence Checking Method for C Descriptions Based on Symbolic Simulation with Textual Differences. IEICE Transaction, E88-A(12):3315-3323, 2005.
	In this paper, an efficient equivalence checking method for two C descriptions is described. The equivalence of two C descriptions is proved by symbolic simulation. Symbolic simulation used in this paper can prove the equivalence of all of the variables in the descriptions. However, it takes long time to verify the equivalence of all of the variables if large descriptions are given. Therefore, in order to improve verification, our method identifies textual differences between descriptions. The identified textual differences are used to reduce the number of equivalence checking among variables. The proposed method has been implemented in C language and evaluated with several C descriptions.
[marak-01:2005]	V. Varshavsky, V. Marakhovsky, and I. Levin. CMOS Fuzzification Circuits for Linear Membership Functions. WSEAS Transactions on Systems, 4(4):238-243, 2005.
	The subject of the study was hardware implementations of fuzzy controllers as CMOS analog devices on the base of implementation of fuzzy inference rules as multi-valued logic functions using summing amplifiers as building blocks. Earlier a functional completeness of summing amplifier with saturation in an arbitrary-valued logic was proven that gave a theoretical background for analog implementation of fuzzy controllers. In previous works it was suggested to put into accordance to input and output linguistic variables of a controller description logical values of some multi-valued variables and instead of fuzzification and defuzzification procedures to apply piecewise-linear approximation between variable logical levels. In the case when derived logical levels were not evenly distributed in the range of an analog signal change it was suggested to increase the number of logical levels to reach even distribution. Such approach leaded to decreasing controller acc! uracy. This paper suggested instead of increasing logical levels to use special devices transforming analog input variables into multi-valued variables with even distribution of logical levels and output multivalued variables into analog view. For these devices the names fuzzifier and defuzzifier were kept. The paper illustrated a design example for real industrial fuzzy controller and provided SPICE simulation results of its functioning.
[marak-02:2005]	V. Varshavsky and V. Marakhovsky. Self-Timed Finite State Machine: from Example to Synthesis. Informational and Controll Systems, 4(17):33-37, 2005.
	In the article the problems of self-timed devices synthesis and the methods of their solution are discussed. It is shown that the widely used language of finite automata can be successfully applied for designing such devices. The appearing problems of synthesis and the methods of their solution are illustrated on the base of the example of designing self-synchronous buffer memory of the STACK type.
[marak-03:2005]	V. Varshavsky, V. Marakhovsky, and I. Levin. Informational and Controll Systems, 4(17):38-50, 2005.
	The beta-driven implementation is based on using summarized conductivities of n-and p-chains of a CMOS gate as the ratio of weighted sums. The threshold element has a wider functional capability in comparison with the traditional functional basis. A method for increasing the functional capability of the threshold element by introducing so-called functional inputs is proposed. Each functional input corresponds to a Boolean sum (or product) of a particular subset of input variables. It is shown that introducing functional inputs enables expansion of the functional capability of beta-driven elements up to the capability to implement an arbitrary monotonic function. The CMOS based implementation of the beta-driven threshold element with newly proposed functional inputs is presented. Methods of the current stabilization of functional inputs are proposed. The paper presents examples of the SPICE simulation of behavior of the proposed threshold element.

Refereed Proceeding Papers

[hiroshis-02:2005]	H. Saito, N. Jindapetch, T. Yoneda, C. Myers, and T. Nanya. A Scheduling Method for Asynchronous Bundled-Data Implementations Based on The Completion of Data Operations. In International Technical Conference on Circuit/Systems, Computers and Communications, pages 433-434, July 2005.
	In this work, we propose a scheduling method for asynchronous bundled-data implementations.
[hiroshis-03:2005]	N. Jindapetch, H. Saito, P. Phukapattranont, and K. Thongnoo. Area-Speed Ratio Productions for Data-Path Resource Sharing Decisions. In International Technical Conference on Circuit/Systems, Computers and Communications, pages 765-766, July 2005.
	This paper proposes a technique to estimate area-speed ration productions for data-path resource sharing decisions that can be performed before the operation scheduling. The ASAP (As Soon As Possible) scheduling algorithm is applied to schedule the operations under the decided resource constraint so that the best speed result will be obtained for each resource constraint. The experimental results confirm that the estimated are-speed ratio productions have the same trend as the area-speed ratio productions of the resulted circuits.
[hiroshis-04:2005]	H. Saito, N. Jindapetch, T. Yoneda, C. Myers, and T. Nanya. A Scheduling Method for Asynchronous Bundled-Data Implementations. In International Workshop on Logic and Synthesis, pages 341-348, June 2005.
	In this work, we propose a scheduling method for asynchronous bundled-data implementations. The scheduling method is based on a traditional scheduling method used for synchronous circuit designs. However, the direct application of it to asynchronous bundled-data implementations leads to several problems such as performance degradation and increase of scheduling cost. Therefore, to solve these problems, we propose a calculation method of control steps based on the completion of data operations. The traditional scheduling method is modified so that the calcualted control steps are used for scheduling of operations. Experimental results show that our method decides a schedule with more or less the same quality of circuits in short time compared to the traditional method. (Poster)
[hiroshis-05:2005]	T. Matsumoto, H. Saito, and M. Fujita. Equivalence Checking for Transformations and Optimizations in C Programs on Dependence Graphs. In International Workshop on Logic and Synthesis, pages 357- 364, June 2005.
	In this paper, we propose a formal equivalence checking method for source-tosource transformations and optimizations in C programs. In the method, the textual differences between given two C programs are identified at first to get hints where the equivalence must be checked. Then, the equivalence of differences is verified by using symbolic simulation and validity checking techniques. If the verification of a difference is not proved, our method incrementally expands statements to be verified to preceding and/or succeeding statements related to the difference and verifies again until the equivalence is proved or the limitation of extensions is archieved. For traversing, the method uses dependence graphs of the descriptions. Finally, we discuss some transformations and optimizations which are frequently happen in practice, where our method can prove the equivalence efficiently. (Poster)
[hiroshis-06:2005]	N. Jindapetch, H. Saito, K. Thongnoo, and T. Nanya. A Fair Overhead Comparison between Asynchronous Four-Phase Based Controllers and Local Controllers. In International Conference of Electrical Engineering/Electronics, Computer, Telecommunication, and Information, pages 791-794, May 2005.
	The four-phase handshake protocol allows asynchronous circuits achieve average-case performance, and bundled-data implementations allow the reuse of well-designed single-rail datapath modules. However, control-delay overhead of the four-phase handshake protocol and are overhead of the matched delay elements in bundled-data implementations limit the potential of such implementations. In this paper, we introduce a new bundled-data implementation, called local clock controllers, to minimize these limitations at gate-level design. A fair overhead comparison with four-phase protocol based controllers was performed to demonstrate the potential of the local clock controllers. The experimental results show that the local clock controllers are about 40are and about 20controllers.
[marak-04:2005]	V. Varshavsky, V. Marakhovsky, and H.Saito. Some Functional Problems in Experiments on Teaching Artificial Neurons. In 8-th International Conference on Humans and Computers, pages 339-344, AizuWakamatsu, Japan, August 31 - September 2 2005. The University of Aizu.
	Learning experiments with digital/analog artificial neuron by SPICEsimulation for limiting values of the parameters (such as the sum of input weights and/or threshold) requires long time that largely depends on the length of the teaching (test) sequence. We suggest to use as test functions a class of threshold functions the minimum forms of which can be represented in accordance with Horner's scheme (Horner's functions). These functions have shortest teaching sequences and provide the neuron parameters close to the biggest ones for a given number of variables. For Horner's function of n variables the values of the variable weights and threshold form the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 ... with the length of a unit teaching sequence equal to n+1.
[marak-05:2005]	V. Varshavsky, V. Marakhovsky, and I. Levin. CMOS Fuzzification Circuits for Linear Membership Functions. In 6th WSEAS Int. Conf. on Neural Networks (NN05), Fuzzy Systems (FS05), CD edition, page 6, Lisbon, Portugal, June 2005. WSEAS, WSEAS.
	The subject of the study was hardware implementations of fuzzy controllers as CMOS analog devices on the base of implementation of fuzzy inference rules as multi-valued logic functions using summing amplifiers as building blocks. Earlier a functional completeness of summing amplifier with saturation in an arbitrary-valued logic was proven that gave a theoretical background for analog implementation of fuzzy controllers. In previous works it was suggested to put into accordance to input and output linguistic variables of a controller description logical values of some multi-valued variables and instead of fuzzification and defuzzification procedures to apply piecewise-linear approximation between variable logical levels. In the case when derived logical levels were not evenly distributed in the range of an analog signal change it was suggested to increase the number of logical levels to reach even distribution. Such approach leaded to decreasing controller acc! uracy. This paper suggested instead of increasing logical levels to use special devices transforming analog input variables into multi-valued variables with even distribution of logical levels and output multi-valued variables into analog view. For these devices the names fuzzifier and defuzzifier were kept. The paper illustrated a design example for real industrial fuzzy controller and provided SPICE simulation results of its functioning.

Unrefereed Papers

[hiroshis-07:2004]

H. Saito and T. Yoneda. Asynchronous Data-Path Circuit Synthesis by Using Force-Directed Scheduling Algorithm and Consideration to Improve Efficiency. In IEICE Tech. Report VLP, pages 115-120. IEICE, December 2004.

Grants

[hiroshis-07:2005]

H. Saito, T. Yoneda, and T. Nanya. Application and Evaluation of the Force-Directed Scheduling Method for Asynchronous Circuits. In DA symposium, pages 37-42. IPSJ, Aug. 2005.

Chapters in Book

[hiroshis-08:2005]	H. Saito. The Basis of System LSI Design Automation Technologies: Chapter 5 Asynchronous Logic Synthesis Tool Petrify (Japanese), pages 44-58. Baifu-kan, 2005.
[hiroshis-09:2005]	M. Fujita, S. Komatsu, and H. Saito. Dependable Computing Systems: Chapter 1 Formal Verification Techniques for Digital Systems, pages 3-25. Wiley-Interscience, 2005.

Grants

[hiroshis-10:2005]

H. Saito. Ministry of Education Scientific Research Fund, 2004-2005.

Academic Activities

[hiroshis-11:2005]	Hiroshi Saito, 2005. Committee member, IPSJ SIGSLDM
[marak-06:2005]	V. Marakhovsky, 2004. Member of IEEE
[marak-07:2005]	V. Marakhovsky, 2004. Member of ACM

Ph.D and Other Theses

[hiroshis-12:2005]	Takao Konishi. Graduation Thesis: Implementation and Evaluation of an Asynchronous Control Circuit Synthesis Method Based on Cell Controllers, University of Aizu, 2005. Thesis Advisor: H. Saito
[hiroshis-13:2005]	Yuusuke Nomoto. Graduation Thesis: Evaluation of Synchronizers for GALS Architectures on a Commertial FPGA, University of Aizu, 2005. Thesis Advisor: H. Saito
[hiroshis-14:2005]	Yuki Kunisawa. Graduation Thesis: Implementing Asynchronous Circuits on a Commertial FPGA, University of Aizu, 2005. Thesis Advisor: H. Saito
[hiroshis-15:2005]	Naohiro Hamada. Graduation Thesis: Considering Register and Multiplexor Costs in Force-Directed Scheduling Algorithm for Asynchronous Circuits, University of Aizu, 2005. Thesis Advisor: H. Saito
[hiroshis-16:2005]	Sakae Kawakami. Graduation Thesis: Evaluation of Improved Force-Directed Scheduling Algorithm for Asynchronous Circuits, University of Aizu, 2005. Thesis Advisor: H. Saito
[marak-08:2005]	Hiroshi Shirai. Graduation Thesis: CMOS Fuzzification Circuits for Linear Membership Functions, University of Aizu, 2006. Thesis Advisor: Marakhovsky, V.
[marak-09:2005]	Toshikatsu Sato. Graduation Thesis: Hardware Implementation of the Cannon Fuzzy Controller for Printer, University of Aizu, 2006. Thesis Advisor: Marakhovsky, V.
[marak-10:2005]	Sadao Niitsuma. Master Thesis: Fuzzy Controller Implementations as Analog Devices, University of Aizu, 2006. Thesis Advisor: Marakhovsky, V.

2007 THE UNIVERSITY OF AIZU ALL RIGHTS RESERVED