basic research in computer science and software engineering at sklcs

The State Key Laboratory of Computer Science (SKLCS) is committed to basic research in computer science and software engineering. The research topics of the laboratory include: concurrency theory, theory and algorithms for real-time systems, formal specifications based on context-free grammars, semantics of programming languages, model checking, automated reasoning, logic programming, software testing, software process improvement, middleware technology, parallel algorithms and parallel software, computer graphics and human-computer interaction. This paper describes these topics in some detail and summarizes some results obtained in recent years.

Parallel optical negabinary arithmetic based on logic operations

On the basis of signed-digit negabinary representation, parallel two-step addition and one-step subtraction can be performed for arbitrary-length negabinary operands.; The arithmetic is realized by signed logic operations and optically implemented by spatial encoding and decoding techniques. The proposed algorithm and optical system are simple, reliable, and practicable, and they have the property of parallel processing of two-dimensional data. This leads to an efficient design for the optical arithmetic and logic unit. (C) 1997 Optical Society of America.

Compact parallel optical modified-signed-digit arithmetic-logic array processor with electron-trapping device

A compact two-step modified-signed-digit arithmetic-logic array processor is proposed. When the reference digits are programmed, both addition and subtraction can be performed by the same binary logic operations regardless of the sign of the input digits. The optical implementation and experimental demonstration with an electron-trapping device are shown. Each digit is encoded by a single pixel, and no polarization is included. Any combinational logic can be easily performed without optoelectronic and electro-optic conversions of the intermediate results. The system is compact, general purpose, simple to align, and has a high signal-to-noise ratio. (C) 1999 Optical Society of America.

Logic-operated mathematical morphology and its optical implementation

A more powerful tool for binary image processing, i.e., logic-operated mathematical morphology (LOMM), is proposed. With LOMM the image and the structuring element (SE) are treated as binary logical variables, and the MULTIPLY between the image and the SE in correlation is replaced with 16 logical operations. A total of 12 LOMM operations are obtained. The optical implementation of LOMM is described. The application of LOMM and its experimental results are also presented. (C) 1999 Optical Society of America.

Two-step digit-set-restricted modified signed-digit addition-subtraction algorithm and its optoelectronic implementation

A novel, to our knowledge, two-step digit-set-restricted modified signed-digit (MSD) addition-subtraction algorithm is proposed. With the introduction of the reference digits, the operand words are mapped into an intermediate carry word with all digits restricted to the set {(1) over bar, 0} and an intermediate sum word with all digits restricted to the set {0, 1}, which can be summed to form the final result without carry generation. The operation can be performed in parallel by use of binary logic. An optical system that utilizes an electron-trapping device is suggested for accomplishing the required binary logic operations. By programming of the illumination of data arrays, any complex logic operations of multiple variables can be realized without additional temporal latency of the intermediate results. This technique has a high space-bandwidth product and signal-to-noise ratio. The main structure can be stacked to construct a compact optoelectronic MSD adder-subtracter. (C) 1999 Optical Society of America.

Parallel optical negabinary signed-digit computing: algorithm and optical implementation

Negabinary is a component of the positional number system. A complete set of negabinary arithmetic operations are presented, including the basic addition/subtraction logic, the two-step carry-free addition/subtraction algorithm based on negabinary signed-digit (NSD) representation, parallel multiplication, and the fast conversion from NSD to the normal negabinary in the carry-look-ahead mode. All the arithmetic operations can be performed with binary logic. By programming the binary reference bits, addition and subtraction can be realized in parallel with the same binary logic functions. This offers a technique to perform space-variant arithmetic-logic functions with space-invariant instructions. Multiplication can be performed in the tree structure and it is simpler than the modified signed-digit (MSD) counterpart. The parallelism of the algorithms is very suitable for optical implementation. Correspondingly, a general-purpose optical logic system using an electron trapping device is suggested. Various complex logic functions can be performed by programming the illumination of the data arrays without additional temporal latency of the intermediate results. The system can be compact. These properties make the proposed negabinary arithmetic-logic system a strong candidate for future applications in digital optical computing with the development of smart pixel arrays. (C) 1999 Society of Photo-Optical Instrumentation Engineers. [S0091-3286(99)00803-X].

Code conversion from signed-digit to complement representation based on look-ahead optical logic operations

We present, for the first time to our knowledge, a generalized lookahead logic algorithm for number conversion from signed-digit to complement representation. By properly encoding the signed-digits, all the operations are performed by binary logic, and unified logical expressions can be obtained for conversion from modified-signed-digit (MSD) to 2's complement, trinary signed-digit (TSD) to 3's complement, and quarternary signed-digit (QSD) to 4's complement. For optical implementation, a parallel logical array module using an electron-trapping device is employed and experimental results are shown. This optical module is suitable for implementing complex logic functions in the form of the sum of the product. The algorithm and architecture are compatible with a general-purpose optoelectronic computing system. (C) 2001 Society of Photo-Optical Instrumentation Engineers.

Compact Reconfigurable Binary-Decision-Diagram Logic Circuit on a GaAs Nanowire Network

We describe a reconfigurable binary-decision-diagram logic circuit based on Shannon's expansion of Boolean logic function and its graphical representation on a semiconductor nanowire network. The circuit is reconfigured by using programmable switches that electrically connect and disconnect a small number of branches. This circuit has a compact structure with a small number of devices compared with the conventional look-up table architecture. A variable Boolean logic circuit was fabricated on an etched GaAs nanowire network having hexagonal topology with Schottky wrap gates and SiN-based programmable switches, and its correct logic operation together with dynamic reconfiguration was demonstrated.

Smart universal multiple-valued logic gates by transferring single electrons

This paper proposes smart universal multiple-valued (MV) logic gates by transferring single electrons (SEs). The logic gates are based on MOSFET based SE turnstiles that can accurately transfer SEs with high speed at high temperature. The number of electrons transferred per cycle by the SE turnstile is a quantized function of its gate voltage, and this characteristic is fully exploited to compactly finish MV logic operations. First, we build arbitrary MV literal gates by using pairs of SE turnstiles. Then, we propose universal MV logic-to-value conversion gates and MV analog-digital conversion circuits. We propose a SPICE model to describe the behavior of the MOSFET based SE turnstile. We simulate the performances of the proposed gates. The MV logic gates have small number of transistors and low power dissipations.

Compact universal logic gates realized using quantization of current in nanodevices

This paper proposes novel universal logic gates using the current quantization characteristics of nanodevices. In nanodevices like the electron waveguide (EW) and single-electron (SE) turnstile, the channel current is a staircase quantized function of its control voltage. We use this unique characteristic to compactly realize Boolean functions. First we present the concept of the periodic-threshold threshold logic gate (PTTG), and we build a compact PTTG using EW and SE turnstiles. We show that an arbitrary three-input Boolean function can be realized with a single PTTG, and an arbitrary four-input Boolean function can be realized by using two PTTGs. We then use one PTTG to build a universal programmable two-input logic gate which can be used to realize all two-input Boolean functions. We also build a programmable three-input logic gate by using one PTTG. Compared with linear threshold logic gates, with the PTTG one can build digital circuits more compactly. The proposed PTTGs are promising for future smart nanoscale digital system use.

Photonic switch and NOT logic gate based on the hybrid integration of a GaAsVCSEL and a GaAs MISS

The hybrid integrated photonic switch and not logic gate based on the integration of a GaAs VCSEL (Vertical Cavity Surface Emitting Lasers) and a MISS (Metal-Insulator-Semiconductor Switches) device are reported. The GaAs VCSEL is fabricated by selective etching and selective oxidation. The Ultra-Thin semi-Insulating layer (UTI) of the GaAs MISS is formed by using oxidation of A1As that is grown by MBE. The accurate control of UTI and the processing compatibility between VCSEL and MISS are solved by this procedure. Ifa VCSEL is connected in series with a MISS, the integrated device can be used as a photonic switch, or a light amplifier. A low switching power (10 mu W) and a good on-off ratio (17 dB contrast) have been achieved. If they are connected in parallel, they perform a photonic NOT gate operation.

Packing LUT clusters with network flow programming

This paper describes a two-step packing algorithm for LUT clusters of which the LUT input multipliers are depopulated. In the first step, a greedy algorithm is used to search for BLE locations and cluster inputs. If the greedy algorithm fails, the second step with network flow programming algorithm is employed. Numerical results illustrate that our two-step packing algorithm obtains better packing density than one-step greedy packing algorithm.

Monostable-Bistable Transition Logic Element (MOBILE) Model for Single-Electron Transistors

The traditional monostable-bistable transition logic element (MOBILE) structure is usually composed of resonant tunneling diodes (RTD). This letter describes a new type MOBILE structure consisting of single-electron transistors (i.e. SET-MOBILE). The analytical model of single-electron transistors ( SET) has been considered three states (including an excited state) of the discrete quantum energy levels. The simulation results show negative differential conductance (NDC) characteristics in I-DS-V-DS curve. The SET-MOBILE utilizing NDC characteristics can successfully realize the basic logic functions as the RTD-MOBILE.

Design and Verification of the Programming Circuit in an Application-Specific FPGA

In this paper we present a methodology and its implementation for the design and verification of programming circuit used in a family of application-specific FPGAs that share a common architecture. Each member of the family is different either in the types of functional blocks contained or in the number of blocks of each type. The parametrized design methodology is presented here to achieve this goal. Even though our focus is on the programming circuitry that provides the interface between the FPGA core circuit and the external programming hardware, the parametrized design method can be generalized to the design of entire chip for all members in the FPGA family. The method presented here covers the generation of the design RTL files and the support files for synthesis, place-and-route layout and simulations. The proposed method is proven to work smoothly within the complete chip design methodology. We will describe the implementation of this method to the design of the programming circuit in details including the design flow from the behavioral-level design to the final layout as well as the verification. Different package options and different programming modes are included in the description of the design. The circuit design implementation is based on SMIC 0.13-micron CMOS technology.