Search

In deep submicron and nanometer designs for battery driven portable applications, the minimization of total energy, average power, peak power, and peak power differential are equally important. In this paper, we propose a framework for simultaneous reduction of these energy and transient power components during behavioral synthesis. A new parameter called "Cycle Power Profile Function" (CPF) is defined which captures the transient power characteristics as a weighted sum of mean cycle power and mean cycle differential power. Minimizing this parameter using multiple voltages and dynamic clocking results in reduction of both energy and transient power. Based on the above, a datapath scheduling algorithm called "CPF-Scheduler" is developed which attempts to minimize the CPF. Experimental results show that for two voltage levels, three operating frequencies, switching activity of 0.5 and power profiling factor of 0.5, the scheduler achieves (i) total energy reductions in the range of 27 - 53%, (ii) average power reductions in the range of 40 - 73% (iii) peak power reductions in the range of 58 - 78% and (iv) peak power differential reductions in the range of 60 - 97%. Further, the impact of switching, profiling factor and resource constraints on the power profile is studied in detail.

In this paper, an empirically optimized channel-matched quantizer, and a joint stochastic-control based rate controller and channel estimator for H.261 based video transmission over a noisy channel is proposed. The rate controller adaptively learns to choose the correct channel matched quantizer using a stochastic learning algorithm. The stochastic automaton based learning algorithm aids in estimating the channel bit error rate based on a one bit feedback from the decoder. The algorithm is observed to converge to the optimal choice of the quantizer very quickly for various channel bit error probabilities and for different video sequences. When compared to traditional channel estimation schemes the proposed technique has several advantages. First, the proposed method results in a significant reduction in the delay and bandwidth requirement for channel estimation when compared to pilot symbol aided channel estimation schemes. Next, the stochastic learning algorithm used to estimate the channel bit error rate has simple computations. This makes it attractive for low power applications such as wireless video communications. This is in contrast to traditional blind channel estimation schemes that are computationally expensive, in general.

In CMOS circuits, the reduction of the threshold voltage due to voltage scaling leads to increase in subthreshold leakage current and hence static power dissipation. We propose a novel technique called LECTOR for designing CMOS gates which significantly cuts down the leakage current without increasing the dynamic power dissipation. In the proposed technique, we introduce two leakage control transistors (a p-type and a n-type) within the logic gate for which the gate terminal of each leakage control transistor (LCT) is controlled by the source of the other. In this arrangement, one of the LCTs is always "near its cutoff voltage" for any input combination. This increases the resistance of the path from V/sub dd/ to ground, leading to significant decrease in leakage currents. The gate-level netlist of the given circuit is first converted into a static CMOS complex gate implementation and then LCTs are introduced to obtain a leakage-controlled circuit. The significant feature of LECTOR is that it works effectively in both active and idle states of the circuit, resulting in better leakage reduction compared to other techniques. Further, the proposed technique overcomes the limitations posed by other existing methods for leakage reduction. Experimental results indicate an average leakage reduction of 79.4% for MCNC'91 benchmark circuits.

In this paper, we describe a new methodology based on game theory for minimizing the average power of a circuit during scheduling and binding in behavioral synthesis. The problems are formulated as auction-based noncooperative finite games for which solutions are proposed based on the Nash equilibrium. In the scheduling algorithm, a first-price sealed-bid auction approach is used while, for the binding algorithm, each functional unit in the datapath is modeled as a player bidding for executing an operation with the estimated power consumption as the bid. Further, the techniques of functional unit sharing, path balancing, and register assignment are incorporated within the binding algorithm for power reduction. The combined scheduling and binding algorithm is formulated as a single noncooperative auction game with the functional units in the datapath modeled as players bidding for executing the operation in a particular control cycle. The proposed algorithms yield power reduction without any increase in area overhead and only a slight increase in the latency for some of the benchmark circuits. Experimental results indicate that the proposed game theoretic solution for binding yields an improvement of 13.9% over the linear programming (LP) method, while the scheduling and the combined scheduling and binding algorithms yield average improvements of 6.3% and 11.8%, respectively, over the integer-linear programming (ILP) approach.

Switching activity estimation is an important step in average power estimation of VLSI circuits at the gate level. In this paper, we present a novel approach based on Petri net modeling for real delay switching activity and power estimation of CMOS circuits, considering both gate and interconnect delays. We propose a new type of Petri net called hierarchical colored hardware Petri net (HCHPN), which accurately captures the spatial and temporal correlations in modeling switching activity. The logic circuit is first modeled as a gate signal graph (GSG) which is then converted into the corresponding HCHPN and simulated as a Petri net to obtain the switching activity estimates and the power values. The proposed method is accurate and fast compared to other simulative methods. Experimental results are provided for ISCAS '85 and ISCAS '89 benchmark circuits and compared with the commercial tools, PowerMill, and Prime Power.

Switching activity estimation is an important aspect of power estimation at circuit level. Switching activity in a node is temporally correlated with its previous value and is spatially correlated with other nodes in the circuit. It is important to capture the effects of such correlations while estimating the switching activity of a circuit. In this paper, we propose a new switching probability model for combinational circuits that uses a logic-induced directed-acyclic graph (LIDAG) and prove that such a graph corresponds to a Bayesian network (BN), which is guaranteed to map all the dependencies inherent in the circuit. BNs can be used to effectively model complex conditional dependencies over a set of random variables. The BN inference schemes serve as a computational mechanism that transforms the LIDAG into a junction tree of cliques to allow for probability propagation by local message passing. The proposed approach is accurate and fast. Switching activity estimation of ISCAS and MCNC circuits with random and biased input streams yield high accuracy (average mean error=0.002) and low computational time (average elapsed time including CPU, memory access and I/O time for the benchmark circuits=3.93 s).

In this paper, we address the problem of routing nets on field programmable gate arrays (FPGAs) interconnected by a switch matrix. We extend the switch matrix architecture proposed by Zhu et al. (1993) to route nets between FPGA chips in a multi-FPGA system. Given a limited number of routing resources in the form of programmable connection points within a two-dimensional switch matrix, this problem examines the issue of how to route a given net traffic through the switch matrix structure. First, we define the problem as a general undirected graph in which each vertex has one single color among six possible colors and formulate it as a constraint satisfaction problem. This is further modeled as a 0-1 multidimensional knapsack problem for which a fast approximate solution is applied. Experimental results show that the accuracy of our proposed heuristic is quite high for moderately large switch matrices.

Multi-FPGA (field-programmable gate arrays) systems are used as custom computing machines to solve compute-intensive problems and also in the verification and prototyping of large circuits. In this paper, we address the problem of routing multiterminal nets in a multi-FPGA system that uses partial crossbars as interconnect structures. First, we model the multiterminal routing problem as a partitioned bin-packing problem and formulate it as an integer linear programming problem where the number of variables is exponential. A fast heuristic is applied to compute an upper bound on the routing solution. Then, a column generation technique is used to solve the linear relaxation of the initial master problem in order to obtain a lower bound on the routing solution. This is followed by an iterative branch-and-price procedure that attempts to find a routing solution somewhere between the two established bounds. In this regard, the proposed algorithm guarantees an exact-routing solution by searching a branch-and-price tree. Due to the tightness of the bounds, the branch-and-price tree is small resulting in shorter execution times. Experimental results are provided for different netlists and board configurations in order to demonstrate the algorithms performance. The obtained results show that the algorithm finds an exact routing solution in a very short time.

The estimation of average-power dissipation of a circuit through exhaustive simulation is impractical due to the large number of primary inputs and their combinations. In this work, two algorithms based on least square estimation are proposed for determining the average power dissipation in complementary metal-oxide-semiconductor (CMOS) circuits. Least square estimation converges faster by attempting to minimize the mean square error value during each iteration. Two statistical approaches namely, the sequential least square (SLS) estimation and the recursive least square estimation are investigated. The proposed methods are distribution independent in terms of the input samples, unbiased and point estimation based. Experimental results presented for the MCNC'91 and the ISCAS'89 benchmark circuits show that the least square estimation algorithms converge faster than other statistical techniques such as the Monte Carlo method and the DIPE.

For distributed shared memory multiprocessors, the choice and the design of interconnection networks have a significant impact on their performance. Bidirectional ring networks are considered to be physically fast due to their simple structure, but topologically slow since their communication latency grows proportionally to the number of nodes. In this paper, we will present a quantitative measure to the question of how physically fast a bidirectional ring has to be to overcome its topologically slow communication latency by comparing it to the crossbar, an interconnection network that has opposite characteristics to the ring network. A hybrid method, in which workload parameters extracted from memory traces are given to an analytical model is used for performance evaluation. Our study shows for 16 nodes configuration, the performance of two networks are similar. For 32 and 64 nodes configurations, the bidirectional ring outperforms the crossbar by 21% and 61% respectively, on the average of four parallel applications.

The design of systems for intelligent control of urban traffic is important in providing a safe environment for pedestrians and motorists. Artificial neural networks (ANNs) (learning systems) and expert systems (knowledge-based systems) have been extensively explored as approaches for decision-making. While the ANNs compute decisions by learning from successfully solved examples, the expert systems rely on a knowledge base developed by human reasoning for decision making. It is possible to integrate the learning abilities of an ANN and the knowledge-based decision-making ability of the expert system. This paper presents a real-time intelligent decision-making system, IDUTC, for urban traffic control applications. The system integrates a backpropagation-based ANN that can learn and adapt to the dynamically changing environment and a fuzzy expert system for decision-making. The performance of the proposed intelligent decision-making system is evaluated by mapping the adaptable traffic light control problem. The application is implemented using the ANN approach, the FES approach, and the proposed integrated system approach. The results of extensive simulations using the three approaches indicate that the integrated system provides better performance and leads to a more efficient implementation than the other two approaches.

Previous research advances have shown that wavelet-based image-compression techniques offer several advantages over traditional techniques in terms of progressive transmission capability, compression efficiency, and bandwidth utilization. The embedded zerotree wavelet (EZW) coding technique suggested by Shapiro (1992), and its modification-set partitioning in hierarchical trees (SPIHT), suggested by Said and Pearlman (19996)-demonstrate the competitive performance of wavelet-based compression schemes. The EZW-based lossless image coding framework consists of three stages: (1) reversible discrete wavelet transform; (2) hierarchical ordering and selection of wavelet coefficients; and (3) context-modeling-based entropy (arithmetic) coding. The performance of the compression algorithm depends on the choice of various parameters and the implementation strategies employed in all the three stages. This paper proposes different context modeling and selection techniques for efficient entropy encoding of wavelet coefficients, along with the modifications performed to the SPIHT algorithm. The results of several experiments presented in this paper demonstrate the importance of context modeling in the EZW framework. Furthermore, this paper shows that appropriate context modeling improves the performance of compression algorithm after a multilevel subband decomposition is performed.

On-chip multiprocessor can be an alternative to the wide-issue superscalar processor approach which is currently the mainstream to exploit the increasing number of transistors on a silicon chip. Utilization of the cache, especially for the remote data is important in the system using such on-chip multiprocessors since the ratio of the off-chip and the on-chip memory access latencies is higher than traditional board-level implementation of the cache coherent non-uniform memory access (CC-NUMA) multiprocessors. We examine two options to utilize the cache resource of the on-chip multiprocessors whose size is restrained by the die area: (1) the instruction and/or private data are only cached at the L1 cache to leave more space on the L2 cache for the shared data; (2) divide cache area into the L2 and the remote victim caches or use all the area for the L2 cache. Results of execution-driven simulations show that the first option improved the performance up to 15%. For the second option, a remote victim cache with 1/8 of the L2 cache size improved three out of four benchmark programs by 4–8%. However, the combination of L2 and victim caches that divide the cache area into two halves of the same size was outperformed by the L2 cache occupying the entire cache area in three out of four benchmark programs.

The efficient transportation of real-time Variable Bit Rate (VBR) video traffic in the high-speed networks has been an area of active research. An important issue is the simplicity with which the bandwidth allocation and scheduling schemes can be executed online with real-time constraints in the future high-speed networks. The correlation properties of the VBR video traffic make the predictor-based online traffic adaptation techniques attractive. We developed a novel predictor-based dynamic bandwidth allocation (PDBA) scheme for short-term resource management and studied its queuing performance. In order to reduce the effects of the prediction errors on the queuing system and hence the underutilization of reserved bandwidth, a novel short-term controller (STC) that works at the cell-level has been introduced and the system has been called the PDBA-STC system. This online VBR video traffic prediction-based traffic management scheme has low complexity and is suitable for implementation in high-speed networks Ranganathan et al. [N. Ranganathan, R. Anand, G. Chiruvolu, A VLSI ATM architecture for VBR traffic, Proc. IEEE International Conference on VLSI Design, 1998, pp. 420-427] and has been demonstrated to provide better performance than other existing simple schemes. This paper also investigates the predictability of VBR video traffic that exhibits long-range dependence (LRD) based on a fractional ARIMA (1,d,0) model. The short-range dependent (SRD) Auto Regressive (AR) model for prediction of VBR video traffic has also been considered for evaluation of the proposed dynamic bandwidth allocation scheme and the performance has been compared to that of LRD-based prediction. Finally, a summary and future research have been discussed.

Tree matching is an important problem used for three-dimensional object recognition in image understanding and vision systems. The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree. In this paper, we describe the design and implementation of a very large scale integration (VLSI) chip for tree pattern matching. The architecture is based on an iterative algorithm that is mapped to a systolic array computational model and takes O(t(n+a)) time to profess a subject of size n using a processors where a is the length of the largest substring in the pattern and t is the number of substrings in the pattern. The variables and nonvariables of the pattern tree are processed separately, which simplifies the hardware in each processing element. The proposed partitioning strategy is independent of the problem size and allows larger strings to be processed based on the array size. A prototype CMOS VLSI chip has been designed using the Cadence design tools and the simulation results indicate that it will operate at 33.3 MHz.

The VBR video traffic exhibits high burstiness and correlation properties that are quite complex to be captured by a single traffic model. Efficient resource management based on few parameters of the source traffic is highly desirable. The real-time VBR video traffic has stringent quality of service (QoS) requirements such as delay (few milliseconds) and cell loss (1 in 10 -5 ) that are difficult to achieve with good utilization (> 0.6) by static bandwidth allocation schemes. In order to satisfy such QoS constraints with good utilization, proper adaptive mechanisms have to be devised. This paper presents a dynamic bandwidth allocation scheme for VBR video traffic based on buffer monitoring and a simple LMS (least mean square) traffic prediction system. The goal is to reduce the frequency of the bandwidth reallocations and at the same time reduce the Cell-loss Ratio (CLR) with increased utilization. Simulation results indicate that utilization up to 0.8 can be achieved by the proposed scheme even under high source alignment [26] for bursty VBR video traffic. It is found that the proposed adaptive scheme outperforms the static FCFS allocation scheme with lower buffer requirements and fewer (< 5%) bandwidth reallocations.

Scene matching is the problem of matching regions of two images of the same scene taken by different sensors at different times or under different viewing conditions. In this paper, we describe an efficient architecture for scene matching called SMAC (Scene Matching ArChitecture). The architecture achieves a significant amount of speedup by utilizing a large amount of parallelism and pipelining. Such an architecture can be used to compute the exhaustive search task of hierarchical scene matching, a technique used to reduce the amount of computations involved in scene matching applications. A prototype very large scale integration (VLSI) chip implementing a scaled down version of the proposed architecture has been designed and built. The prototype chip has been tested to be fully functional at a frequency of 50 MHz with a clock cycle of 20 ns. Based on the prototype design, it is estimated that the proposed architecture can process a 512 × 512 image with an 128 × 128 size template in about 15.36 μs, which corresponds to a rate of 65K frames per second.

The distance between two labeled ordered trees, /spl alpha/ and /spl beta/, is the minimum cost sequence of editing operations (insertions, deletions, and substitutions) needed to transform a into /spl beta/ such that the predecessor-descendant relation between nodes and the ordering of nodes is not changed. Approximate tree matching has applications in genetic sequence comparison, scene analysis, error recovery and correction in programming languages, and cluster analysis. Edit distance computation is a computationally intensive task, and the design of special purpose hardware could result in a significant speed up. This paper proposes a VLSI architecture for computing the distance between ordered h-ary trees, as well as arbitrary ordered trees. This is the very first special purpose architecture that has been proposed for this important problem. The architecture is a parallel realization of a dynamic programming algorithm and makes use of simple basic cells and requires regular nearest-neighbor communication. The architecture has been simulated and verified using the Cadence design tools.

There has been an outburst of research in image and video compression for transmission over noisy channels. Channel matched source quantizer design has gained prominence. Further, the presence of variable-length codes in compression standards like the JPEG and the MPEG has made the problem more interesting. Error-resilient entropy coding (EREC) has emerged as a new and effective method to combat catastrophic loss in the received signal due to burst and random errors. We propose a new channel-matched adaptive quantizer for JPEG image compression. A slow, frequency-nonselective Rayleigh fading channel model is assumed. The optimal quantizer that matches the human visibility threshold and the channel bit-error rate is derived. Further, a new fast error-resilient entropy code (FEREC) that exploits the statistics of the JPEG compressed data is proposed. The proposed FEREC algorithm is shown to be almost twice as fast as EREC in encoding the data, and hence the error resilience capability is also observed to be significantly better. On average, a 5% decrease in the number of significantly corrupted received image blocks is observed with FEREC. Up to a 2-dB improvement in the peak signal-to-noise ratio of the received image is also achieved.

Reversible logic is gaining significant consideration as the potential logic design style for implementation in modern nanotechnology and quantum computing with minimal impact on physical entropy. Recent advances in reversible logic allow schemes for computer architectures using improved quantum computer algorithms. We present a VHDL behavioral model for the design and simulation of the quantum interactions of qubits in theoretical reversible logic structures. Modeling IQ gates, as opposed to only Control-V gates or Toffoli gates, allows for a more robust model that more accurately reflects a theoretical reversible computing structure. This method is an extension to existing programming language and modeling method that allows for reversible logic structures to be designed, simulated, and verified. To the best of our knowledge, this is the first work in the behavioral model of integrated qubit gates.

The recognition of polygons in 3-D space is an important task in robot vision. Advances in VLSI technology have now made it possible to implement inexpensive, efficient and very fast custom designs. The authors have earlier proposed a class of VLSI architectures for this computationally intensive task, which makes use of a set of local shape descriptors for polygons which are invariant under affine transformations, i.e. translation, scaling, rotation and orthographic projection from 3-D to any 2-D plane. This paper discusses the design and implementation of PMAC, a prototype for polygon matching, as a custom CMOS VLSI chip. The recognition procedure is based on the matching of edge-length ratios using a simplified version of the dynamic programming procedure commonly employed for string matching. The matching procedure also copes with partial occlusions of polygons. The implemented architecture is systolic and fully utilizes the principles of pipelining and parallelism in order to obtain high speed and throughput.

Connected components detection and labeling is an essential step in many image analysis techniques. The efficiency of the connected components labeling algorithm is critical for many image processing and machine vision applications that require real time response. The advances in the areas of parallel processing and VLSI technology can be exploited in designing hardware algorithms of high speed and throughput. In this paper, the authors propose a systolic algorithm and architecture for finding connected components in an image. The architecture is simple and can be implemented as a special purpose VLSI chip. Although, the algorithm has a time complexity of O(N/sup 2/), this is in terms of the actual clock cycle which is estimated as 25 nano seconds. The proposed hardware can process a 128/spl times/128 image in 0.85 msec and uses 128 processors whereas the MPP requires 94.6 msec with 16384 processors. The only special purpose hardware that exists requires 300 msec to label a 512/spl times/512 image which can be accomplished in 13.5 msec using the authors' proposed hardware. >

The edit distance between two strings a1, ..., a/sub m/ and b/sub 1/, ..., b/sub n/ is the minimum cost s of a sequence of editing operations (insertions, deletions and substitutions) that convert one string into the other. This paper describes the design and implementation of a linear systolic array chip for computing the edit distance between two strings over a given alphabet. An encoding scheme is proposed which reduces the number of bits required to represent a state in the computation. The architecture is a parallel realization of the standard dynamic programming algorithm proposed by Wagner and Fischer (1974), and can perform approximate string matching for variable edit costs. More importantly, the architecture does not place any constraint on the lengths of the strings that can be compared. It makes use of simple basic cells and requires regular nearest neighbor communication, which makes it suitable for VLSI implementation. A prototype of this array has been built at the University of South Florida. >

The redundancy in digital image representation can be classified into two categories: local and global. In this paper, we present an analysis of two image characteristics that give rise to local and global redundancy in image representation. Based on this study, we propose a lossless image compression scheme that exploits redundancy both at local and global levels in order to obtain maximum compression efficiency. The proposed algorithm segments the image into variable size blocks and encodes them depending on the characteristics exhibited by the pixels within the block. The proposed algorithm is implemented in software and its performance is better than other lossless compression schemes such as the Huffman, the arithmetic, the Lempel-Ziv and the JPEG. >

In this paper, we describe a fully pipelined single chip VLSI architecture for implementing the JPEG baseline image compression standard. The architecture exploits the principles of pipelining and parallelism to the maximum extent in order to obtain high speed and throughput. The architecture for discrete cosine transform and the entropy encoder are based on efficient algorithms designed for high speed VLSI implementation. The entire architecture can be implemented on a single VLSI chip to yield a clock rate of about 100 MHz which would allow an input rate of 30 frames per second for 1024/spl times/1024 color images. >

Depth recovery from gray-scale images is an important topic in the field of computer and robot vision. Intensity gradient analysis (IGA) is a robust technique for inferring depth information from a sequence of images acquired by a sensor undergoing translational motion. IGA obviates the need for explicitly solving the correspondence problem and hence is an efficient technique for range estimation. Many applications require real time processing at very high frame rates. The design of special purpose hardware could significantly speed up the computations in IGA. In this paper, we propose two VLSI architectures for high-speed range estimation based on IGA. The architectures fully utilize the principles of pipelining and parallelism in order to obtain high speed and throughput. The designs are conceptually simple and suitable for implementation in VLSI. >

Significant debate exists in the literature with regards to the permissibility of feedback in reversible computing nanotechnologies. Feedback allows for reuse of logical subroutines, which is a desired functionality of any computational device. Determining whether loop back is allowed is paramount to assessing the robustness of reversible logic in any quantum design. In this paper, the fundamental discoveries in entropy and quantum mechanics that serve as the foundations for reversible logic are reviewed. The fundamentals for implementation of reversibility in computing are shown. Then, definitions are presented for a sequential reversible logic structure. A sequential reversible logic structure is proven to have an identical number of feedback-dependent inputs and feedback-producing outputs, and new metrics for measuring the probability of each output state are presented. Using these metrics, the reversibility of each clock cycle of such a device is verified. Therefore, we demonstrate that any reversible logic structure with feedback is physically reversible.

This paper addresses the problem of determining the reliability of individual sensors in a multi-sensor robotic system in an unknown environment. The inherent difficulty in this problem is that the decision must be based solely upon the data from the sensors themselves. While some previous research has considered unstructured environments (see Refs. 1 and 2 for examples) little if any consideration has been given to totally unknown environments. This problem has usually been avoided by assuming that the sensors would not provide erroneous data or ignoring sensors when they appeared to provide erroneous data. We believe a more robust solution is to consider each sensor’s performance over time compared to other sensors, and from this determine a measure of confidence in each sensor. This allows sensors which temporarily provide erroneous data to be accommodated. A system which can determine the reliability of its sensors is more robust since it can wisely decide which sensors are most appropriate for a given task and can also determine whether sensor conflicts are the result of poorly performing sensors.

The recognition of patterns is an important task in robot and computer vision. The patterns themselves could be one- or two-dimensional, depending upon the application. Pattern matching is a computationally intensive and time consuming operation. The design of special purpose hardware could speed up the matching task considerably, making real-time responses possible. Advances in parallel processing and VLSI technologies have made it possible to implement inexpensive, efficient and very fast custom designs. Many approaches and solutions have been proposed in the literature for hardware implementations of pattern matching techniques. In this paper, we present a detailed overview of some of the important contributions in the area of hardware algorithms and architectures for pattern matching.

Multiresolution representation in machine vision systems provides a means to detect, analyze and interpret the information content of an image at multiple resolutions. The pyramidal representation of images suggested by Burt and Crowley and the hierarchical construction of orientation and velocity tuned filters developed by Fleet and Jepson are some of the examples for multiresolution representation of image details. In recent years, Gabor filter based methods have been suggested by several researchers for machine vision applications such as edge detection, texture classification and optical flow estimation. These applications require generating a family of Gabor filters tuned to several resolutions and orientations and computing their responses. The computation of Gabor filter responses at multiple resolutions and orientations is a very computationally intensive task. Two efficient schemes for computing Gabor filter based multiresolution responses are proposed. The first scheme namely, recursive filtering method generates a family of Gabor filters and their responses starting from a high resolution and proceeding towards the lowest resolution in steps of an octave. The second approach namely, successive sampling method generates the same responses in the reverse order. In both these methods the symmetric, asymmetric and wavelet nature of Gabor filters are exploited in order to speed up the computation. The applicability and usefulness of the schemes are established through experimental results. Special purpose architectures are proposed to implement the proposed techniques in hardware in order to further speed up the computation.

The study of reversible circuits holds great promise for emerging technologies. Reversible circuits offer the possibility for great reductions in power consumption, and quantum computers will require logically reversible digital circuits. Many different reversible implementations of logical and arithmetic units have been proposed in the literature, but very few reversible floating-point designs exist. Floating-point operations are needed very frequently in nearly all computing disciplines, and studies have shown floating-point addition to be the most oft used floating-point operation. In this paper we present for the first time a reversible floating-point adder that closely follows the IEEE754 specification for binary floating-point arithmetic. Our design requires reversible designs of a controlled swap unit, a subtracter, an alignment unit, signed integer representation conversion units, an integer adder, a normalization unit, and a rounding unit. We analyze these major components in terms of quantum cost, garbage outputs, and constant inputs.

Nowadays, GPU architecture is commonly exploited in various researches on computer graphic and other scientific computing areas. Parallel computing feature of GPU provides performance benefits for execution of many programs. However, as the parallel degree keeps extending, the number of active cores in GPU required for execution is also increasing. Therefore the rising of energy consumption caused by using large number of cores begins to draw attention. Previous research [1] reveals that given a multicore program, the curve of energy consumption first falls and then rises, as the number of active cores increases. That means we can have the minimum energy consumption if the number of active cores is properly configured. In this paper, we develop an instruction-level prediction mechanism to estimate the energy consumption of a given program under different numbers of cores. The prediction is based on the profile of Parallel Thread Execution (PTX) [2] codes generated during compilation of the original program. With the help of this mechanism, the energy-optimal number of cores can be found during compilation and used in execution, replacing the one given by programmer. Tests have been carried on several NVIDIA CUDA [10] benchmarks. The results show that the energy consumption is minimized without losing much performance. With the predicted energy-optimal number of active cores, we show that the energy consumption saving for the selected benchmarks is from 7.31% to 11.76% on average, with a worst case of performance lost 4.92%.

Reversible computation differs from traditional computation in that it preserves information while manipulating it. This new design paradigm has very attractive thermodynamic consequences and holds many applications in current and emerging technologies. Modern computers can reduce power consumption by taking advantage of reversibility, and quantum computers operate reversibly. Researchers have already proposed reversible designs of many common arithmetic and logical units, including adders, multipliers, shifters, and even registers. Very little focused work has been done specifically on reversible encoder/decoder design. In this paper we propose a novel reversible encoder/decoder design and analyze it in terms of its quantum cost, garbage outputs, constant inputs, and quantum delay.

Reversible logic is an emerging nanotechnology used in the design and implementation of nanotechnology and quantum computing with the main goal of reducing physical entropy gain. Significant work have been produced in the design of fundamental reversible logic structures and arithmetic units, and recent developments in sequential design of reversible circuits has opened new avenues in the implementation of reversible combinational circuits, such as the design and implementation of static (SRAM) and dynamic random-access memory (DRAM). In this paper, a novel 4*4 MLMR gate is presented which is used for controlling the read/write logic of a SRAM cell. Next, a reversible SRAM cell is designed and verified. Then, a novel 4*4 Reversible Decoder (RD) gate, implemented as a 2-to-4 decoder with low delay and cost is presented and verified, and its implementation shown in the construction of a 4×2 reversible SRAM array. Next, a dual-port SRAM cell is presented and verified, and its implementation in a synchronous n-bit reversible dual-port SRAM array is shown. Then, a reversible DRAM cell is presented and verified. The control logic for writing to the DRAM based on Peres gates is shown. The control logic and the DRAM cell are then implemented in a reversible 4×4 DRAM array.

In [1] we have presented the reversible subtractor designs based on a new reversible TR gate (TR refers to Thapliyal Ranganathan). In [1] as the quantum gates implementation of the TR gate was not known, only the upper bound on the quantum cost of the reversible subtractors units were established. In this work, we present a new design of the reversible half subtractor based on the quantum gates implementation of the reversible TR gate. The reversible TR gate is designed from 2×2 quantum gates such as CNOT and Controlled-V and Controlled-V+ gates. The design of the proposed reversible half subtractor is shown to be better than the design presented in [2], [1] in terms of the quantum cost and delay while maintaining the minimum number of garbage outputs. Further, we present a new design of the reversible full subtractor based on the proposed quantum gates implementation of the TR gate. The proposed reversible full subtractor is optimized in terms of quantum cost, delay and garbage outputs by utilizing the identity property of V and V+ reversible gates. The proposed reversible full subtractor is shown to be better than the existing design reported in [3], [1]. The reversible subtractors proposed in this work will be useful in a number of digital signal processing applications.

Reversible logic is an emerging nanotechnology widely being considered as the potential logic design and implementation of nanotechnology and quantum computing with the main goal of reducing physical entropy gain. Recent advances in reversible logic allow for new avenues in the implementation of reversible combinational circuits. Part of this advancement is the design and implementation of a finite state machine. A proposed novel 4*4 RD gate implemented as a 2-to-4 decoder with low delay and cost is presented, and a novel 4*4 R2D gate used in the implementation of a novel n-to-2n decoder with low cost and delay. A reversible synchronous up-down counter is presented and verified, and a reduced reversible implementation of a JK Flip Flop is implemented in a reduced reversible synchronous up-down counter. This decoder and counter are then utilized in the design of a reversible Moore finite state machine.

Reversible logic has promising applications in the field of quantum computing, optical computing, low power computing, and other emerging computing technologies. A barrel shifter that can shift and rotate multiple bits in a single cycle is an important component of many computing units. This paper presents the reversible design of bidirectional arithmetic and logical barrel shifter. The proposed design consists of the reversible Fredkin and Feynman gates. The Fredkin gate used in the design of reversible bidirectional arithmetic and logical barrel shifter can implement the 2∶1 MUX with minimum quantum cost, minimum number of ancilla bits and minimum number of garbage outputs while the Feynman gate is used to avoid the fanout as fanout is not allowed in the reversible logic. The design is evaluated in terms of number of garbage outputs, quantum cost and number of ancilla bits.

A two-axis in-plane capacitive accelerometer fabricated on silicon-on-insulator (SOI) is developed. With each stationary electrode separated to two sub stationary electrodes by refilled isolation trench, the presented accelerometer has compact differential capacitance electrodes to improve capacitance sensitivity per sensing area. In addition, the overlap area-changed capacitor enables good linearity and low damping coefficient.

The building blocks of the 3-D IC integration technology are Through-Silicon Via (TSV) fabrication/implementation, thin wafer handling, low-temperature backside TSV revealing process, and electrical redistribution or connection of vertical circuitry or ICs. Of these elements, the scheme for wafer thinning and backside passivation is a crucial technology element of 3D integration. In this paper, novel backside via revealing and passivation for 3D IC application is proposed with newly developed process integration. Si/Cu CMP process is applied to overcome the practical limitations on the uniformity of the backside thinning originated from the blind thinning process. As such, the height variations associated with via etch non-uniformity and glue, carrier and grinding TTV's (Total Thickness Variation) are flattened out. In order to protrude the TSV from the backside, we demonstrated new spin wet etchback process with well-controlled repeatability, reduced process defect and copper contamination. For the low-k thick dielectric layer application (without photo-litho), Insulation layer on the back side is deposited over the protruded portion of the TSV structure. The deposited insulation layer is removed and TSV area is again exposed. The process for removing this insulation layer is the plasma etching or CMP polish.

Reversible logic has promising applications in emerging nanotechnologies, such as quantum computing, quantum dot cellular automata and optical computing, etc. Faults in reversible logic circuits that result in multi-bit error at the outputs are very tough to detect, and thus in literature, researchers have only addressed the problem of online testing of faults that result single-bit error at the outputs based on parity preserving logic. In this work, we propose a methodology for the concurrent error detection in reversible logic circuits to detect faults that can result in multi-bit error at the outputs. The methodology is based on the inverse property of reversible logic and is termed as 'inverse and compare' method. By using the inverse property of reversible logic, all the inputs can be regenerated at the outputs. Thus, by comparing the original inputs with the regenerated inputs, the faults in reversible circuits can be detected. Minimizing the garbage outputs is one of the main goals in reversible logic design and synthesis. We show that the proposed methodology results in 'garbageless' reversible circuits. A design of reversible full adder that can be concurrently tested for multi-bit error at the outputs is illustrated as the application of the proposed scheme. Finally, we showed the application of the proposed scheme of concurrent error detection towards fault detection in quantum dot cellular automata (QCA) emerging nanotechnology., Comment: H. Thapliyal and N.Ranganathan, "Reversible Logic Based Concurrent Error Detection Methodology For Emerging Nanocircuits", Proceedings of the 10th IEEE International Conference on Nanotechnology, Seoul, Korea, Aug 2010

A class of VLSI architectures is proposed for the computationally intensive task of polygon recognition in 3-D space. They make use of a set of local shape descriptors for polygons that are invariant under affine transformations. The recognition procedure is based on the matching of edge length ratios using a simplified version of the dynamic programming procedure commonly used for string matching. The matching procedure also copes with partial occlusion of polygons. The architectures are systolic and fully utilize the principles of pipelining and parallelism in order to obtain high speed and throughput. A prototype VLSI chip implementing one of the proposed architectures is currently being built. >

Describes the architecture and design of a CMOS VLSI chip for data compression and decompression using tree-based codes. The chip, called MARVLE, implements a memory-based architecture for variable length encoding and decoding based on tree-based codes. The architecture is based on an efficient scheme of mapping the tree representing any binary code onto a memory device. A prototype 2-mm CMOS VLSI chip has been designed, verified, and fabricated by the MOSIS facility. The chip has a 512*12 static RAM with an access time of 4 ns and logic circuitry for compression as well as decompression. The chip occupies a silicon area of 6.8 mm*6.9 mm and consists of 49695 transistors. The prototype chip yields a compression rate of 95.2 Mb/s and a decompression rate of 60.6 Mb/s with a clock rate of 83.3 MHz. The VLSI hardware can be used to implement the JPEG baseline compression scheme. >

Finite or Galois fields are used in numerous applications like error correcting codes, digital signal processing and cryptography. The design of efficient methods for Galois field arithmetic such as multiplication and division is critical for these applications. A new algorithm based on a pattern matching technique for computing multiplication and division in GF(2/sup m/) is presented. An efficient systolic architecture is described for implementing the algorithm which can produce a new result every clock cycle and the multiplication and division operations can be interleaved. The architecture has been implemented using 2- mu m CMOS technology. The chip yields a computational rate of 33.3 million multiplications/divisions per second. >

A class of hardware algorithms for implementing the Lempel-Ziv-based data compression technique is described. The Lempel-Ziv-based compression method is a powerful technique for lossless data compression that gives high compression efficiency for text as well as image data. The proposed hardware algorithms exploit the principles of pipelining and parallelism in order to obtain high speed and throughput. A prototype CMOS VLSI chip was designed and fabricated using 2- mu m CMOS technology implementing a systolic array of nine processors. The chip gives a compression rate of 13.3 MB/s operating at 40 MHz. Two hardware algorithms for the decompression process are also described. The data compression hardware can be integrated into real-time systems so that data can be compressed and decompressed on-the-fly. >

In this work we proposed designs and demonstrated the fabrication of silicon microprobes for neural prosthesis. Silicon probes of various sizes, cross-sectional shapes and involving different probe encapsulation bio-compatible materials such as Polyimide were fabricated. Especially, isotropically etched (for Si) probes find significant application to reduce tissue trauma during implant. Our approach of using fully CMOS compatible silicon wafer processing with 200mm diameter silicon wafers is to subsequently serve as an enabling platform for manufacture-able process leading to low cost neurodevices. Silicon probes thus fabricated were packaged in order to demonstrate the complete product cycle- “Design-to-Packaging”.

Multiple-valued reversible logic is emerging as a promising computing paradigm as it helps in reducing the width of the reversible or quantum circuits. Further, a barrel shifter that can shift and rotate multiple bits in a single cycle forms the essence of many computing systems. In this paper, we propose an efficient architecture and design of a reversible ternary barrel shifter. The ternary barrel shifter is realized using the Modified Fredkin gates (MFG) and the ternary Feynman gates. The design is evaluated in terms of quantum cost, the number of garbage outputs and the number of ancilla bits. To our knowledge, the use of multiple valued reversible logic for the design of a barrel shifter is being attempted for the first time in the literature.

The ex i sting design of reversible n-bit binary comparator that compares two n-bit numbers is a serial design [1] having the latency of O(n). In this work, we present a new reversible n-bit binary comparator based on binary tree structure that has the latency of O(log 2 (n)). The reversible designs are based on a new reversible gate called the TR gate, the improved quantum cost of which is also derived in this work. In the proposed reversible binary tree comparator each node consists of a 2-bit reversible binary comparator that can compare two 2-bit numbers x(x i , x i −1) and y(y i , y i −1), to generate two 1-bit outputs Y and Z. Y will be 1 if x(x i , x i −1)> y(y i , y i −1), and Z will be 1 if x(x i , x i −1)y or xy) and O 2 (x=y).

Reversible logic is a promising field of research that finds applications in low power computing, quantum computing, optical computing, and other emerging computing technologies. Further, floating point multiplication is one of the major operations in image and digital signal processing applications. The single precision floating-point multiplier requires the design of efficient 24×24 bit integer multiplier. In this work, we propose a new reversible design of single precision floating point multiplier based on operand decomposition approach. To design the reversible 24×24 (A×B) bit multiplier (assume A and B are of 24 bits each), the operands are decomposed into three partitions of 8 bits each. Thus, the 24×24 bit reversible multiplication is performed through nine reversible 8×8 bit Wallace tree multipliers, whose outputs are then summed. We propose a new reversible design of the 8×8 bit Wallace tree multiplier that has been optimized in terms of quantum cost, delay, and number of garbage outputs. Wallace tree multiplication consists of three conceptual stages: Partial product generation, partial product compression using 4∶2 compressors, full adders, and half adders, and then the final addition stage to generate the product. In this work we perform optimization at each of these three stages. For the first stage, we have proposed a new generalized reversible partial product generation circuitry. For the second stage we have proposed a new reversible 4∶2 compressor design for use in the compression tree. Finally, for the summation stage we have carefully chosen and arranged the reversible half adders and full adders in such a way to yield an efficient multiplier optimized in terms of quantum cost, delay, and garbage outputs. We have also illustrated the reversible design of 24×24 bit multiplier using the proposed 8×8 bit reversible Wallace tree multiplier.

It is common practice to utilize evidence from biological and psychological vision experiments to develop computational models for low-level feature extraction. The receptive profiles of simple cells in mammalian visual systems have been found to closely resemble Gabor filters. Daugman proved that Gabor filters achieve joint minimal joint uncertainty. These results led researchers to develop computational models based on Gabor filters for several low-level vision applications such as edge detection, texture classification, optical flow estimation and data compression. In this paper, the performance of a Gabor odd filter-based edge detector is investigated using the measures proposed by Canny. Based on this performance analysis a design criterion for one-dimensional (1D) Gabor filter-based edge detector is derived. It is shown that this design criterion also holds good for a two-dimensional (2D) Gabor filter-based edge detector. Experimental results are presented to demonstrate the performance of the Gabor filter-based edge detector.

In this paper, we describe the design and implementation of a VLSI chip for computing joins in a relational database that uses attribute-based storage schema. The chip design is based on a systolic architecture that fully utilizes the principles of pipelining and parallelism in order to obtain high speed and throughput. The architecture implements an improved version of the algorithm previously proposed by Kung and Lehman 1 . A partitioning technique proposed in Leiserson and Saxe 2 is incorporated in the algorithm in order to derive maximum utilization of the processors. Although the time complexity of the algorithm is O ( n 2 / k ), where n is the number of attribute values and k is the number of processors, each step is a hardware clock cycle of 25 ns. Thus, a single chip can yield a throughput rate of 2.56 giga results per second operating at a rate of 40 MHz. Higher throughputs can be obtained by cascading multiple chips in a serial fashion.