In big data systems, the infrastructure is such that large amounts of data are hosted away from the users. In such a system information security is considered as a major challenge. From a customer perspective, one of the big risks in adopting big data systems is in trusting the provider who designs and owns the infrastructure from accessing user data. Yet there does not exist much in the literature on detection of insider attacks. In this work, we propose a new system architecture in which insider attacks can be detected by utilizing the replication of data on various nodes in the system. The proposed system uses a two-step attack detection algorithm and a secure communication protocol to analyze processes executing in the system. The first step involves the construction of control instruction sequences for each process in the system. The second step involves the matching of these instruction sequences among the replica nodes. Initial experiments on real-world hadoop and spark tests show that the proposed system needs to consider only 20 percent of the code to analyze a program and incurs 3.28 percent time overhead. The proposed security system can be implemented and built for any big data system due to its extrinsic workflow.

Big data platforms like Hadoop and Spark are being widely adopted both by academia and industry. In this paper, we propose a runtime intrusion detection technique that understands and works according to the memory properties of such distributed compute platforms. The proposed method is based on runtime analysis of memory access patterns of tasks running on the slave nodes of a distributed compute cluster. First, every slave node of the cluster creates a behavior profile for each task it executes. A behavior profile includes information representing the sizes of private & shared memory accesses made by a task during execution. Then, each process behavior profile is shared with other replica nodes that are scheduled to execute the same task on their copy of the same data. Next, these replica nodes verify their local tasks with the help of the information embedded in the received behavior profiles. This step is realized by running Principal Component Analysis (PCA) on the memory access patterns. Finally, nodes share their observations for consensus and report a possible intrusion to the master node if they find any discrepancy. This is a position paper and hence the proposed solution was tested and proved to work in real-time while executing the terasort mapreduce example on a small hadoop cluster.

Cyber attacks are becoming a threat to the proliferation of big data services. Security in big data services is primarily implemented through software that is maintained by service providers which makes it easier for insider attacks. In this paper, we introduce a novel hardware driven framework for mitigating insider attacks in big data systems. The key idea is to delegate security to special purpose hardware that is capable of detecting an attack on the primary copy of data and preventing that attack on the replicas. In the proposed framework, the assembly code of a process running on the primary copy is analyzed and an attack probability score (APS) is derived which captures in some sense the control structure of the code. The APS of a process is unique to the structure of that process and is derived from the control-flow instructions and their data (if applicable). This score along with the control and data stacks are maintained in the replica nodes. Now, at the replica nodes when the same code is executed, the APS is computed dynamically on the fly and matched with the stored APS. If there is a mismatch indicating a possible attack, the control and data flow stacks are matched in sequence to detect attacks. Our proposed framework was simulated on a virtual cluster and verified using open benchmarks. Experimental results prove that our framework can be implemented with negligible time overhead. Results indicate that the average time overhead is about 0.01% of the total execution time.

Production of cost-effective secure integrated chips, such as smart cards, requires hardware designers to consider tradeoffs in size, security, and power consumption. To design successful security-centric designs, the low-level hardware must contain built-in protection mechanisms to supplement cryptographic algorithms, such as advanced encryption standard and triple data encryption standard by preventing side-channel attacks, such as differential power analysis (DPA). Dynamic logic obfuscates the output waveforms and the circuit operation, reducing the effectiveness of the DPA attack. For stronger mitigation of DPA attacks, we propose the implementation of adiabatic dynamic differential logic (ADDL) for applications in secure integrated circuit (IC) design. Such an approach is effective in reducing power consumption, demonstrated using HSPICE simulations with 22-nm predictive technology. The benefits of our design are demonstrated by comparing instantaneous power waveforms and observing the magnitude of differential power spikes during switching events. First, simulation results for body biasing on subthreshold adiabatic inverters show an improvement in differential power up to 43.28% for similar inverters without body biasing. Then, a high-performance ADDL is presented for an implementation in high-frequency secure ICs. This method improves the differential power over previous dynamic and differential logic methods by up to 89.65%. Finally, we propose a body-biased ADDL for ultralow power applications. Simulation results show that the differential power was improved upon by a factor of 199.16.

Programmable reversible logic is emerging as a prospective logic design style for implementation in low power, low frequency applications where minimal impact on circuit heat generation is desirable, such as mitigation of differential power analysis attacks. Adiabatic logic is an implementation of reversible logic in CMOS where the current flow through the circuit is controlled such that the energy dissipation due to switching and capacitor dissipation is minimized. Recent advances in dual-rail adiabatic logic show reduction in average and differential power, making this design methodology advantageous in applications where security is the primary design metric and operating frequency is slower, such as Smart Cards. In this paper, we present an algorithm for synthesis of adiabatic circuits in CMOS. Then, using the ESPRESSO heuristic for minimization of Boolean functions method on each output node, we reduce the size of the synthesized circuit. Our approach correlates the horizontal offsets in the permutation matrix with the necessary switches required for synthesis instead of using a library of equivalent functions. The synthesis results show that, on average, the proposed algorithm represents an improvement of 36% over the best known reversible designs with the optimized dual-rail cell libraries. Then, we present an adiabatic S-box which significantly reduces energy imbalance compared to previous benchmarks. The design is capable of forward encryption and reverse decryption with minimal overhead, allowing for efficient hardware reuse.

Reversible logic is gaining significance in the context of emerging technologies such as quantum computing since reversible circuits do not lose information during computation and there is one-to-one mapping between the inputs and outputs. In this work, we present a class of new designs for reversible binary and BCD adder circuits. The proposed designs are primarily optimized for the number of ancilla inputs and the number of garbage outputs and are designed for possible best values for the quantum cost and delay. In reversible circuits, in addition to the primary inputs, some constant input bits are used to realize different logic functions which are referred to as ancilla inputs and are overheads that need to be reduced. Further, the garbage outputs which do not contribute to any useful computations but are needed to maintain reversibility are also overheads that need to be reduced in reversible designs. First, we propose two new designs for the reversible ripple carry adder: (i) one with no input carry c 0 and no ancilla input bits, and (ii) one with input carry c 0 and no ancilla input bits. The proposed reversible ripple carry adder designs with no ancilla input bits have less quantum cost and logic depth (delay) compared to their existing counterparts in the literature. In these designs, the quantum cost and delay are reduced by deriving designs based on the reversible Peres gate and the TR gate. Next, four new designs for the reversible BCD adder are presented based on the following two approaches: (i) the addition is performed in binary mode and correction is applied to convert to BCD when required through detection and correction, and (ii) the addition is performed in binary mode and the result is always converted using a binary to BCD converter. The proposed reversible binary and BCD adders can be applied in a wide variety of digital signal processing applications and constitute important design components of reversible computing.

Peak power reduction has been a critical challenge in the design of integrated circuits impacting the chip's performance and reliability. The reduction of peak power also reduces the power density of integrated circuits. Due to large IR-voltage drops in circuits, transistor switching slows down giving rise to timing violations and logic failures. In this paper, we present a new clock control strategy for peak-power reduction in VLSI circuits. In the proposed method, the simultaneous switching of combinational paths is minimized by taking advantage of the delay slacks among the paths and clustering the paths with similar slack values. Once the paths are identified based on the path delays and their slack values, the clustering algorithm determines the ideal number of clusters for the given circuit and for each cluster the maximum possible phase shift that can be applied to the clock. The paths are assigned to clusters in a load balanced manner based on the slack values and each cluster will have a phase shift possible on its clock depending on the slack. Thus, the proposed register-transfer level (RTL) method takes advantage of the logic-path timing slack to re-schedule circuit activities at optimal intervals within the unaltered clock period. When switching activities are redistributed more evenly across the clock period, the IC supply-current consumption is also spread across a wider range of time within the clock period. This has the beneficial effect of reducing peak-current draw in addition to reducing RMS power draw without having to change the operating frequency and without utilizing additional power supply voltages as in dual or multi VT approaches. The proposed method is implemented and tested through simulations using an experimental setup with Synopsys Tools Suite and Cadence Tools on the ISCAS'85 benchmark circuits, OpenCore circuits and LEON processor multiplier circuit. Experimental results indicate that peak power can be reduced significantly to at least 72% depending on the number of clusters and the phase-shifted clock identified as suitable for the given circuit by the proposed algorithms. Although the proposed method incurs some power overhead compared to the traditional clocking method, the overhead can be made negligible compared to the peak-power reduction as seen in the experimental results presented.

In this paper, we propose the design of two vectors testable sequential circuits based on conservative logic gates. The proposed sequential circuits based on conservative logic gates outperform the sequential circuits implemented in classical gates in terms of testability. Any sequential circuit based on conservative logic gates can be tested for classical unidirectional stuck-at faults using only two test vectors. The two test vectors are all 1's, and all 0's. The designs of two vectors testable latches, master-slave flip-flops and double edge triggered (DET) flip-flops are presented. The importance of the proposed work lies in the fact that it provides the design of reversible sequential circuits completely testable for any stuck-at fault by only two test vectors, thereby eliminating the need for any type of scan-path access to internal memory cells. The reversible design of the DET flip-flop is proposed for the first time in the literature. We also showed the application of the proposed approach toward 100% fault coverage for single missing/additional cell defect in the quantum-dot cellular automata (QCA) layout of the Fredkin gate. We are also presenting a new conservative logic gate called multiplexer conservative QCA gate (MX-cqca) that is not reversible in nature but has similar properties as the Fredkin gate of working as 2:1 multiplexer. The proposed MX-cqca gate surpasses the Fredkin gate in terms of complexity (the number of majority voters), speed, and area.

In recent years reversible logic has emerged as a promising computing model for applications in dissipation less optical computing, low power CMOS, quantum computing, etc. In reversible circuits there exist a one-to-one mapping between the inputs and the outputs resulting in no loss of information. Researchers have implemented reversible logic gates in optical computing domain as it can provide high speed and low energy requirement along with easy fabrication at the chip level [1]. The all optical implementation of reversible gates are based on semiconductor optical amplifier (SOA) based Mach-Zehnder interferometer (MZI) due to its significant advantages such as high speed, low power, fast switching time and ease in fabrication. In this work we present the all optical implementation of an n bit reversible ripple carry adder for the first time in literature. The all optical reversible adder design is based on two new optical reversible gates referred as optical reversible gate I (ORG-I) and optical reversible gate II (ORG-II) and the existing all optical Feynman gate. The two new reversible gates ORG-I and ORGI-I are proposed as they can implement a reversible adder with reduced optical cost which is the measure of number of MZIs switches and the propagation delay, and with zero overhead in terms of number of ancilla inputs and the garbage outputs. The proposed all optical reversible adder design based on the ORG-I and ORG-II reversible gates are compared and shown to be better than the other existing designs of reversible adder proposed in non-optical domain in terms of number of MZIs, delay, number of ancilla inputs and the garbage outputs. The proposed all optical reversible ripple carry adder will be a key component of an all optical reversible ALU that can be applied in a wide variety of optical signal processing applications.

In this paper, we propose a novel microarchitectural technique for run-time power-gating caches of GPUs to save leakage energy. The L1 cache (private to a core) can be put in a low-leakage sleep mode when there are no ready threads to be scheduled, and the L2 cache can be put in sleep mode when there is no memory request. The sleep mode is state-retentive, which precludes the necessity to flush the caches after they are woken up. The primary reason for the effectiveness our technique lies in the fact that the latency of detecting cache inactivity, putting a cache to sleep and waking it up before it is accessed, is completely hidden microarchitecturally. The technique incurs insignificant overheads in terms of power and area. Experiments were performed using the GPGPU-Sim simulator on benchmarks that was set up using the CUDA framework. The power and latency modeling of the cache arrays for measuring the wake-up latency and the break-even periods is performed using a 32-nm SOI IBM technology model. Based on experiments on 16 different GPU workloads, the average energy savings achieved by the proposed technique is 54%.

In the nanometer era, process, voltage, and temperature variations are dominating circuit performance, power, and yield. Over the past few years, statistical optimization methods have been effective in improving yield in the presence of uncertainty due to process variations. However, statistical methods overconsume resources, even in the absence of variations. Hence, to facilitate a better performance-power-yield trade-off, techniques that can dynamically enable variation compensation are becoming necessary. In this article, we propose a dynamic technique that controls the instance of data capture in critical path memory flops, by delaying the clock edge trigger. The methodology employs a dynamic delay detection circuit to identify the uncertainty in delay due to variations and stretches the clock in the destination flip-flops. The delay detection circuit uses a latch and set of combinational gates to dynamically detect and create the slack needed to accommodate the delay due to variations. The Clock Stretching Logic (CSL) is added only to paths, which have a high probability of failure in the presence of variations. The proposed methodology improves the timing yield of the circuit without significant overcompensation. The methodology approach was simulated using Synopsys design tools for circuit synthesis and Cadence tools for placement and routing of the design. Extraction of parasitic of timing information was parsed using Perl scripts and simulated using a simulation program generated in C++. Experimental results based on Monte-Carlo simulations on benchmark circuits indicate considerable improvement in timing yield with negligible area overhead.

Reversible logic is one of the emerging technologies having promising applications in quantum computing. In this work, we present new design of the reversible BCD adder that has been primarily optimized for the number of ancilla input bits and the number of garbage outputs. The number of ancilla input bits and the garbage outputs is primarily considered as an optimization criteria as it is extremely difficult to realize a quantum computer with many qubits. As the optimization of ancilla input bits and the garbage outputs may degrade the design in terms of the quantum cost and the delay, thus the quantum cost and the delay parameters are also considered for optimization with primary focus towards the optimization of the number of ancilla input bits and the garbage outputs. Firstly, we propose a new design of the reversible ripple carry adder having the input carry Co and is designed with no ancilla input bits. The proposed reversible ripple carry adder design with no ancilla input bits has less quantum cost and the logic depth (delay) compared to its existing counterparts. The existing reversible Peres gate and a new reversible gate called the TR gate is efficiently utilized to improve the quantum cost and the delay of the reversible ripple carry adder. The improved quantum design of the TR gate is also illustrated. Finally, the reversible design of the BCD adder is presented which is based on a 4 bit reversible binary adder to add the BCD number, and finally the conversion of the binary result to the BCD format using a reversible binary to BCD converter.

The trends in technology scaling and the reduction in supply voltages have significantly improved the performance and energy consumption in modern microprocessors. Microprocessors are being built with higher degrees of spatial parallelism and deeper pipelines to improve performance, which, however, makes them more susceptible to transient faults. Radiation causes "transient faults” or "single-event transients” in logic, which, once propagated and latched, become full cycle errors or soft errors. If radiation hits memory elements, this is usually called an "single-event upset” or "soft error” as it can further propagate as a full cycle error. The problem of soft errors is further exacerbated in large multiprocessors employed in servers in which reliability is a key concern. In the past, the technique of lockstep execution of the original and the duplicate instructions has been used for error detection in multiprocessors. However, the execution of redundant threads in the on-chip multiprocessor (CMP) provides error detection at lower overheads, since the branch outcomes of the leading thread can be exploited during the execution of the trailing thread, and also because the interprocessor communication latency is a key concern for lockstepping. In this paper, we show that by mining various redundancies inherent within a single core, the interprocessor communication can be brought down to a minimum. Toward this, we propose techniques based on 1) temporal redundancy, 2) data value redundancy, and 3) information redundancy for error detection in multicore designs. We exploit temporal redundancy by using the "latency slack cycles” (LSC) of an instruction, which we define as the number of cycles before the computed result from the instruction becomes the source operand of a subsequent instruction. The value-based detection technique is explored by exploiting the width of the operands with small data values and information redundancy is exploited by the generation of residue code check bits for the source operands. We show that with a clustered core multiprocessor, the interprocessor communication overhead can be significantly reduced. In our proposed multicore design, when a soft error is detected, error correction is achieved by rolling back the execution to a previous checkpoint state and re-executing the instructions. The proposed techniques have been implemented on the RSIM simulation framework and validated using the SPLASH benchmarks. Experimental results indicate that the soft error detection schemes proposed in this work, can be implemented, on the average, with less than 10 percent increase in CPI on modern multicore designs.

In this work, we investigate state-retentive power gating of register files for leakage reduction in multicore processors supporting multithreading. In an in-order core, when a thread gets blocked due to a memory stall, the corresponding register file can be placed in a low leakage state through power gating for leakage reduction. When the memory stall gets resolved, the register file is activated for being accessed again. Since the contents of the register file are not lost and restored on wakeup, this is referred to as state-retentive power gating of register files. While state-retentive power gating in single cores has been studied in the literature, it is being investigated for multicore architectures for the first time in this work. We propose specific techniques to implement state-retentive power gating for three different multicore processor configurations based on the multithreading model: 1) coarse-grained multithreading, 2) fine-grained multithreading, and 3) simultaneous multithreading. The proposed techniques can be implemented as design extensions within the control units of the in-order cores. Each technique uses two different modes of leakage states: low-leakage savings and low wake-up and high-leakage savings and high wake-up latency. The overhead due to wake-up latency is completely avoided in two techniques while it is hidden for most part in the third approach, either by overlapping the wake-up process with the thread context switching latency or by executing instructions from other threads ready for execution. The proposed techniques were evaluated through simulations with multiprogrammed workloads comprised of SPEC 2000 integer benchmarks. Experimental results show that in an 8-core processor executing 64 threads, the average leakage savings were 42 percent in coarse-grained multithreading, while they were between seven percent and eight percent for finegrained and simultaneous multithreading.

The rate of soft errors have been significantly increasing due to the aggressive scaling trends in the nanometer regime. Several circuit optimization techniques have been proposed in literature for preventing such transient faults, however, to the best of our knowledge, the reduction of soft error rate at the layout level has not been attempted in logic circuits. In this work, we show that transient glitches due to cosmic strikes can be sufficiently reduced by intelligently modifying the placement stage in cell based designs to selectively assign larger wirelengths to certain critical nets. Towards this, we propose a computationally efficient placement algorithm based on quadratic programming that significantly reduces the soft error rates of logic circuits. The algorithm tries to assign higher wirelengths for nets with low glitch masking probabilities for higher reduction in soft error rates (SER), while maintaining low delay and area penalty for the overall circuit. Experimental results on the ISCAS'85 benchmark circuits indicate that such a placement algorithm can significantly improve the soft error immunity in logic circuits without much delay and area overheads.

In this paper, we propose a novel gate sizing approach for circuit optimization in the presence of scarce information about the distributions of the process variations. The proposed methodology relies upon the concepts of utility theory and risk minimization for multimetric optimization of delay, dynamic power, leakage power, and crosstalk noise, via gate sizing. A deterministic linear equivalent model from a fundamentally stochastic design optimization problem, ensuring high levels of expected utility and significant speedup in the optimization process for large circuits is derived in this work. Experimental results indicate that the proposed algorithm is efficient in terms of optimization results with multifold speedup in execution times compared to the traditional approaches.

Reversible logic has shown potential to have extensive applications in emerging technologies such as quantum computing, optical computing, quantum dot cellular automata as well as ultra low power VLSI circuits. Recently, several researchers have focused their efforts on the design and synthesis of efficient reversible logic circuits. In these works, the primary design focus has been on optimizing the number of reversible gates and the garbage outputs. The number of reversible gates is not a good metric of optimization as each reversible gate is of different type and computational complexity, and thus will have a different quantum cost and delay. The computational complexity of a reversible gate can be represented by its quantum cost. Further, delay constitutes an important metric, which has not been addressed in prior works on reversible sequential circuits as a design metric to be optimized. In this work, we present novel designs of reversible sequential circuits that are optimized in terms of quantum cost, delay and the garbage outputs. The optimized designs of several reversible sequential circuits are presented including the D Latch, the JK latch, the T latch and the SR latch, and their corresponding reversible master-slave flip-flop designs. The proposed master-slave flip-flop designs have the special property that they don't require the inversion of the clock for use in the slave latch. Further, we introduce a novel strategy of cascading a Fredkin gate at the outputs of a reversible latch to realize the designs of the Fredkin gate based asynchronous set/reset D latch and the master-slave D flip-flop. Finally, as an example of complex reversible sequential circuits, the reversible logic design of the universal shift register is introduced. The proposed reversible sequential designs were verified through simulations using Verilog HDL and simulation results are presented.

Data and object clustering techniques are used in a wide variety of scientific applications such as biology, pattern recognition, information systems, etc. Traditionally, clustering methods have focused on optimizing a single metric, however, several multidisciplinary applications such as robot team deployment, ad hoc networks, facility location, etc., require the simultaneous examination of multiple metrics during clustering. In this paper, we propose a novel approach for spatial data clustering based on the concepts of microeconomic theory, which can simultaneously optimize both the compaction and the equipartitioning objectives. The algorithm models a multistep, normal form game consisting of randomly initialized clusters as players that compete for the allocation of data objects from resource locations. A Nash-equilibrium-based methodology is used to derive solutions that are socially fair for all the players. After each step, the clusters are updated using the KMeans algorithm, and the process is repeated until the stopping criteria are satisfied. Extensive simulations were performed on several real data sets as well as artificially synthesized data sets to evaluate the efficacy of the algorithm. Experimental results indicate that the proposed algorithm yields significantly better results as compared to the traditional algorithms. Further, the proposed algorithm yields a high value of fairness, a metric that indicates the quality of the solution in terms of simultaneous optimization of the objectives. Also, the sensitivity of the various design parameters on the performance of our algorithm is analyzed and reported.

Optical flow computation in vision-based systems demands substantial computational power and storage area. Hence, to enable real-time processing at high resolution, the design of application-specific system for optic flow becomes essential. In this paper, we propose an efficient VLSI architecture for the accurate computation of the Lucas-Kanade (L-K)-based optical flow. The L-K algorithm is first converted to a scaled fixed-point version, with optimal bit widths, for improving the feasibility of high-speed hardware implementation without much loss in accuracy. The algorithm is mapped onto an efficient VLSI architecture and the data flow exploits the principles of pipelining and parallelism. The optical flow estimation involves several tasks such as Gaussian smoothing, gradient computation, least square matrix calculation, and velocity estimation, which are processed in a pipelined fashion. The proposed architecture was simulated and verified by synthesizing onto a Xilinx Field Programmable Gate Array, which utilize less than 40% of system resources while operating at a frequency of 55 MHz. Experimental results on benchmark sequences indicate 42% improvement in accuracy and a speed up of five times, compared to a recent hardware implementation of the L-K algorithm.

In the nanometer regime, the effects of variations are having an increasing impact on the delay, power, and yield characteristics of devices. In this paper, we propose the use of fuzzy and stochastic mathematical programming techniques for variation aware timing-based incremental placement. The uncertainty due to process variations in these techniques, are modeled using fuzzy numbers and probabilistic constraints, respectively. The objective is to minimize the critical path delay of the circuit in the presence of variations considering gate and interconnect delays. In the fuzzy approach, the average and worst case deterministic optimizations are performed to identify the bounds and convert the uncertain fuzzy problem into a crisp nonlinear problem. The stochastic optimization framework, on the other hand, transforms the probabilistic constraints into a second-order conic program (SOCP) with explicit mean and variance values. The fuzzy and stochastic approaches tested on ITC'99 benchmark circuits yielded around 12.60% and 10.53% improvements in timing, when compared to optimization with the worst case process variations setting.

Compiler-directed power gating is an approach in which sleep instructions are inserted appropriately at compile time into the application code to selectively deactivate the functional units in microprocessors during their idle periods to reduce power dissipation due to leakage. Although the effect of code transformations on dynamic and system power has been investigated and reported in the literature, such a study is lacking in the context of power gating. In this paper, we investigate and report how the leakage savings in both integer and floating point units can be improved using machine-dependent and independent optimizations in a compiler-directed power gating framework. In our study, it is ensured that power gating is applied only when the leakage savings are considerably more than the various overheads incurred in its implementation. The target embedded processor is modeled on the ARMv4 architecture, which is modified to support the power gating of its arithmetic functional units. For experimentation, GCC is used as the compiler infrastructure and Simplescalar-ARM is used as the detailed architectural simulator for reporting power and performance metrics for embedded applications belonging to the MiBench and MediaBench benchmark suites. Experimental results suggest that the additional savings in leakage energy due to one or more of the optimizations may vary largely depending on the benchmark. Moreover, the overhead of sleep instructions can be reduced by up to 50 times by performing procedure inlining.

The computation of optical flow in video sequences is a challenging task in most camera based scene interpretation systems. In the past, most optical flow computation algorithms has been either implemented in software running on general purpose processors or designed as an application specific hardware. However, these implementations either cannot support real-time processing requirements or result in excessive inaccuracies in the computed velocity values. In this work, we propose a efficient VLSI system architecture for computing the optical flow in video sequences using the Lucas-Kanade (L-K) algorithm. The algorithm is converted into high speed RTL implementation by exploiting the inherent paralellism in the data flow graph. Clever pipelining strategies has been used throughout the design to further improve the speedup of velocity computation. We have mapped the RTL design on a Xilinx Virtex II Field Programmable Gate Arrays (FPGA) supported with Kingston DIMM DDR memory module, and a Pixel-Plus 2.0 Mega-pixel camera on the XUPV2P FPGA board. Experimental results of our proposed design showed significant improvements in accuracy with a speedup of five times when compared with other recent hardware implementations.

With the continuous decrease in the minimum feature size and increase in the chip density, modern processors are being increasingly susceptible to soft errors. In the past, the technique of lockstep execution with redundant threads on duplicated pipelines have been used for soft error rate reduction which can achieve high error coverage but at the cost of large overheads in terms of area and performance. In this paper, we propose techniques for protection against soft errors in multi-core designs using (i) the properties of spatial and temporal redundancy and (ii) value based detection. We utilize temporal redundancy by using the ldquolatency use slackrdquo (LSC) of an instruction, which we define as the number of cycles before the computed result from the instruction becomes the source operand of a subsequent instruction, while spatial redundancy is exploited by duplicating the instruction to a nearby idle processor core. Further, the value based detection technique is explored by exploiting the width of the operands with small data values and the generation of residue code check bits for the source operands. When a soft error is detected, error correction is achieved by rolling back the execution to a previous checkpoint state and re-executing the instructions. The proposed techniques have been implemented on the RSIM simulation framework and validated using the SPLASH benchmarks. Our results indicate that the soft error detection schemes proposed in this work, can be implemented, on average, with less than 10% increase in CPI on modern multi-core designs.

Power gating is a circuit level technique for reducing standby leakage in a circuit block by cutting off paths in it between the supply and the ground. A processor architecture that supports power gating of its resources may provide instructions that activate and deactivate those resources as part of the instruction set architecture level. Adequate compiler support is then required so that the power gating instructions can be inserted into the code to deactivate the resources that remain idle for long periods of time during program execution. However, the resource usage in a program depends on the code generated by the compiler. Thus, the code transformations performed by the compiler has an influence on the power gating opportunities of the processor resources. In this work, we explore target independent compiler optimizations that modify the functional unit usage in the loops of a procedure to enhance the opportunities to deactivate functional units in an embedded processor architecture. The optimizations performed on the code are sparse conditional constant propagation, lazy code motion, weak strength reduction, and operator strength reduction. Insertion of power gating instructions is performed by inspecting the idleness of the units in the regions enclosed within loops. We model the processor architecture with power gating support around an ARM core and use the SUIF framework for compiler support. Finally, we use the Simplescalar-ARM distribution to perform power and performance evaluation with a set of benchmarks from MiBench and MediaBench suites. Experimental results indicate that the integer multiplier in the processor core can be power gated for upto 99% of its idle cycles, for integer benchmarks, and upto 93%, for floating point benchmarks, when all the optimizations are performed. Moreover, the energy due to leakage in the functional units for the code with all the optimizations performed can be upto 51% lower, for integer benchmarks, and upto 21% lower, for floating point benchmarks, than that for the unoptimized code.

Reversible logic is attracting the researchers attention for fault susceptible nanotechnologies including molecular QCA. In this paper, we propose concurrently testable FPGA design for molecular QCA using conservative reversible Fredkin gate. Fredkin gate is conservative reversible in nature, in which there would be an equal number of 1s in the outputs as there would be on the inputs, in addition to one-to-one mapping. Fault patterns in Fredkin gate are analyzed using HDLQ tool due to a single missing/additional cell defect in molecular QCA. Exhaustive simulation shows that if there is a fault in molecular QCA implementation of Fredkin gate, there is a parity mismatch between the inputs and the outputs; otherwise the inputs parity is same as outputs parity. Thus, any permanent and transient fault in molecular QCA that results in parity mismatch can be concurrently detected. The logic block and the routing fabric (both are programmable) are the two key components of an FPGA. Thus, we have shown the Fredkin gate based concurrently testable designs of the configurable logic block (CLB) and the routing switch of a molecular QCA-based FPGA. Analysis of power dissipation in the proposed FPGA is also shown.

The aggressive scaling of technology has not only accentuated the effects of intradie parametric variations in devices, but it has also impacted the effects of optimizing a certain performance metric on the optimality of other metrics. Thus, there is a need for optimization methods that can perform the simultaneous optimization of multiple metrics considering the effects of process variations. In this article, a novel variation-aware gate sizing framework has been developed that can perform simultaneous optimization of multiple performance metrics. In this framework, the relationships between the optimization metrics (like dynamic power, leakage power, and crosstalk noise) are modeled as a function of the gate sizes in the objective function. The delay values obtained from unconstrained delay optimization and the noise margins derived from coupling capacitance information form the constraints for the multimetric optimization problem. As an abstract framework, it is independent of the type of mathematical programming approach as well as the metrics chosen to be optimized. The framework has been implemented using a mathematical programming approach and has been tested on ITC'99 benchmarks for different combinations of multimetric and single-metric optimizations of delay, dynamic power, leakage power, and crosstalk noise. The results indicate that the framework identifies good solution points, and is efficient for postlayout optimization via gate sizing.

With the continuous decrease in the minimum feature size and increase in the chip density due to technology scaling, on-chip L2 caches are becoming increasingly susceptible to multi-bit soft errors. The increase in multi-bit errors could lead to higher risk of data corruption and potentially result in the crashing of application programs. Traditionally, the L2 caches have been protected from soft errors using techniques such as: 1) error detection/correction codes; 2) physical interleaving of cache bit lines to convert multi-bit errors into single-bit errors; and 3) cache scrubbing. While the first two methods incur large area overheads for multi-bit errors, identifying the time interval for scrubbing could be tricky. In this paper, we investigate in detail the multi-bit soft error rates in large L2 caches and propose a framework of solutions for their correction based on the amount of redundancy present in the memory hierarchy. We investigate several new techniques for reducing multi-bit errors in large L2 caches, in which, the multi-bit errors are detected using simple error detection codes and corrected using the data redundancy in the memory hierarchy. We also propose several techniques to control/mine the redundancy in the memory hierarchy to further improve the reliability of the L2 cache. The proposed techniques were implemented in the Simplescalar framework and validated using the SPEC 2000 integer and floating point benchmarks for L2 cache vulnerability, global cache miss-rate, average cycle count and main memory write back rate, considering the area and power overheads. Experimental results indicate that the vulnerability of L2 caches can be decreased by 40% on the average for integer benchmarks and 32% on the average for floating point benchmarks, with an average multi-bit error coverage of about 96%, with significantly less area and power overheads and with virtually no performance penalty. The proposed techniques are applicable to both single and multi-core processor-based systems.

Power gating is a technique commonly used for leakage reduction in integrated circuits. In microprocessors, power gating is implemented by using sleep transistors to selectively deactivate circuit modules that remain idle for sustained periods of time during program execution. In this work, we develop a new framework for power gating the functional units in embedded system microprocessors without degradation in performance. The proposed framework includes an efficient algorithm for idle time estimation, appropriate insertion of sleep instructions within the code, and a method for reactivating the sleeping units only when needed without the use of wakeup instructions. We introduce the notion of loop hierarchy trees (LHTs) to represent the partial ordering of the nested loops within the program. From the control flow graph (CFG) representation of the source program, a forest of LHTs is constructed and is used to identify the maximal subgraphs representing the long idle periods for the functional units. For each subgraph thus identified, a sleep instruction is introduced in the program with a list of corresponding functional units to be deactivated. When an instruction is decoded, the functional units needed for that instruction are automatically activated by the control unit such that the units are ready before the instruction reaches the execute stage. This eliminates the need for wakeup instructions to be inserted into the object code reducing the overheads. In our implementation, the ARM processor architecture was modified and resynthesized to include power gating by developing a CMOS cell library of functional units with the above capabilities. Experimental results are reported for a set of 12 benchmarks chosen from the MiBench suite, which indicate that, on average, our technique reduces the leakage energy in functional units by 31.1% for integer benchmarks and 26.8% for floating-point benchmarks.

Differential power analysis (DPA) has been shown to be the dominant type of side-channel attacks that significantly jeopardize the security in integrated circuits. It has been shown that the data, the functional unit operations as well as the internal micro-architectures can be detected through current and power analysis. Subsequently, different CMOS logic styles have been proposed in the literature for performing computations in such a manner that the current and power signatures can be concealed through reduction of the variance in transient power dissipation. In this work, we propose a gate sizing formulation based on traditional static CMOS standard cells that improves the security of the circuits while maintaining low overheads in terms of area, power and delay. The proposed algorithm considers all disjoint paths from primary inputs to the primary outputs, performing gate sizing with the objective of balancing the switched path capacitances among the various paths making it difficult to extract power or current signatures through current or power profiling. Further, we show that the path based security aware gate sizing formulation is NP-complete and propose a greedy approximation algorithm based on linear programming. The proposed algorithm has been implemented and validated on the ISCAS85 benchmarks and the experimental results indicate a reduction of the variance of transient dynamic power by about 40% with very low overhead in terms of delay, area and power.

Technology scaling has not only magnified the effects of device process variations, but it has also precipitated the need for simultaneous optimization of several performance metrics. In this paper, we propose a novel gate sizing approach for multi-metric optimization of delay, power, and crosstalk noise. The algorithm is based on the concepts of mathematical programming, and models the process variation uncertainty considering spatial correlations. The approach identifies leakage power, dynamic power, and crosstalk noise as the objectives, and the optimized gate delays are kept as constraints. Initially, the deterministic upper and lower bounds of the objectives are identified, and during the final step, a crisp non-linear programming problem is formulated using these boundary values. The problem is solved using KNITRO, an interior-point based optimization solver. The proposed model maximizes the variation resistance, thus providing higher yield. ITC'99 benchmarks were used to test the proposed approach, and the results indicate that our algorithm identifies the solution points that are closest to the nominal bounds, while maintaining high timing yield.

Application of clustering approaches in cross-disciplinary domains has necessitated the identification of new methods capable of simultaneous examination of multiple conflicting metrics during optimization. In this work, we propose a novel multi-objective clustering approach based on the concepts of microeconomic theory. In a multi-step, normal form game theoretic setup, each randomly initialized cluster is categorized as either a player or a resource in the game. The players in the game compete against each other for allocation of resources, and try to maximize their own utilities. The utility for a strategy of a player is a function of the clustering objectives. A Nash equilibrium based methodology is used to identify a solution that is socially fair. The algorithm is tested on real as well as artificially synthesized spatial data sets to evaluate the efficacy of the algorithm, and the quantitative measure of the quality of clusters in terms of fairness.

The reliability against transient faults poses a significant challenge due to technology scaling trends. Several circuit optimization techniques have been proposed in the literature for preventing soft errors in logic circuits. However, most approaches do not incorporate the effects of other design metrics like delay and power while optimizing the circuit for soft error protection. In this work, we develop a first order model of the soft error phenomenon in logic circuits and incorporate power and delay metrics to formulate a convex programming based reliability-centric gate sizing technique. The proposed algorithm has been implemented and validated on the ISCAS`85 benchmarks. Experimental results indicate that our multi-objective optimization technique can achieve significant reductions in soft error rate with simultaneous optimization of delay and power.

In this research, we propose a novel approach for simultaneous optimization of power, crosstalk noise and delay via gate sizing, in the presence of scarce information about the distribution of the variations. The methodology uses the concepts of utility theory and risk minimization to identify a deterministic equivalent model of the stochastic problem, ensuring high levels of expected utilities of constraints, and significant speedup in the optimization process for large circuits. A comparative study with an existing gate sizing methodology shows that our method is multi-fold faster as well as comparable in terms of the optimization.

Technology scaling in the nanometer era has increased the transistor's susceptibility to process variations. The effects of such variations are having a huge impact on the yield of the integrated circuits and need to be considered early in the design flow. Traditional corner based deterministic methods are no longer effective and circuit optimization methods require reinvention with a statistical perspective. In this paper, we propose a new gate sizing algorithm using fuzzy linear programming in which the uncertainty due to process variations is modeled using fuzzy numbers. The variations in gate delay which is a function of the gate sizes and the fan-outs of the gates are represented using triangular fuzzy numbers with linear membership functions. Initially, as a preprocessing step for fuzzy optimization, we perform deterministic optimizations by fixing the fuzzy parameters to the worst and the average case values, the results of which are used to convert the fuzzy optimization problem into a crisp nonlinear problem. The crisp problem with delay and power as constraints is then formulated to maximize the robustness, i.e., the variation resistance of the circuit. The fuzzy optimization approach was tested on ITC'99 benchmark circuits and the results were validated for timing yield using Monte Carlo simulations. The proposed approach is shown to achieve better power reduction than the worst case deterministic optimization as well as the stochastic programming based gate sizing methods, while having comparable runtimes.

The reliability of large on-chip L2 cache poses a significant challenge due to technology scaling trends. As the minimum feature size continues to decrease, the L2 caches become more vulnerable to multi-bit soft errors. Traditionally, L2 caches have been protected from multi-bit soft errors using techniques like using error detection/correction codes or employing physical interleaving of cache bit lines to convert multi-bit errors into single-bit errors. These methods, however, incur large overheads in area and power. In this work, we investigate several new techniques for reducing multi-bit errors in large L2 caches, in which the multi-bit errors are detected using simple error detection codes and corrected using the data redundancy in the memory hierarchy. Further, we develop a reliability aware replacement policy that dynamically trades performance for reliability whenever the soft-error budget is exceeded. In order to further improve reliability, we propose the duplication of the data values in cache lines by exploiting their small data widths. The proposed techniques were implemented in the Simplescalar framework and validated using the SPEC 2000 integer and floating point benchmarks. The proposed techniques improve the reliability of L2 caches by 40% and 32% on the average, for integer and floating point applications respectively, with little impact on performance and area.

The aggregation of robots into teams is necessitated due to the limited power and communication capabilities in emergency environments. The formation of robot teams significantly enhances the performance and efficiency of search and rescue missions in such environments. As opposed to the classical partitioning application domains, the robot aggregation requires multiple confticting objectives to be optimized. We propose a novel microeconomic methodology for simultaneous multi-objective partitioning of robots. The method utilizes the strengths of K-Means algorithm, game theoretic modeling, and Nash equilibrium methodology for fast and socially fair partitioning. In this work, partitions are created on the basis of compaction and equipartitioning objectives to identify decentralized robot teams with each robot in a team closest to its communication gateway, as well as each team equally represented in terms of strength. Rigorous simulations were performed to evaluate the performance of the method, and the results indicate that the proposed method performs significantly better than the K-Means methodology, and identifies good solution points.

The optimal allocation of resources to emergency locations in the event of multiple crises in an urban environment is an intricate problem, especially when the available resources are limited. In such a scenario, it is important to allocate emergency response units in a fair manner based on the criticality of the crisis events and their requests. In this research, a crisis management tool is developed which incorporates a resource allocation algorithm. The problem is formulated as a game-theoretic framework in which the crisis events are modeled as the players, the emergency response centers as the resource locations with emergency units to be scheduled, and the possible allocations as strategies. The payoff is modeled as a function of the criticality of the event and the anticipated response times. The game is played assuming a specific region within a certain locality of the crisis events to derive an optimal allocation. If a solution is not feasible, the perimeter of the locality in consideration is increased and the game is repeated until convergence. Experimental results are presented to illustrate the efficacy of the proposed methodology and metrics are derived to quantify the fairness of the solution. A regression analysis is performed to establish the statistical significance of the results.

Increasing dominance of process variations in the nanometer designs are posing significant challenges for circuit design and optimization. The variations in parameters such as channel length and the gate oxide thickness impacts circuit delay and power. In this paper, we propose a new gate sizing algorithm using fuzzy mathematical programming (FMP) in which the uncertainty due to process variations is modeled using fuzzy numbers. The variations in gate delay, which is a function of gate sizes and the fan-outs of the gate, are represented using triangular fuzzy numbers with linear membership functions. The variation aware gate sizing problem is formulated as a fuzzy mathematical program to perform a delay constrained power minimization in the presence of variations. Initially, a deterministic optimization is performed by fixing the fuzzy parameters to the worst and the average case values and the results are used to convert the fuzzy optimization problem into a crisp non-linear problem which is then solved using a non-linear optimization solver. The above model with delay and power as constraints, maximizes the robustness, i.e., the variation resistance of the circuit and thus the yield. The proposed approach was tested on ISCAS '85 benchmarks and the results were validated for timing yield using monte-carlo simulations. The fuzzy approach yields significantly better results compared to stochastic programming based gate sizing approach with a comparable runtime.

Resource management is a well studied field. Existence of multiple emergencies in a locality, in a time overlapped manner, demands an optimal allocation of required resources to the emergencies. This is an intricate problem if the availability of resources is limited. Involvement of human lives in such situations poses a very important constraint of social fairness on the optimality criteria of allocation. Hence, these situations necessitate an allocation methodology that could allocate the requested resources to the emergencies such that even a lower criticality emergency is serviced in a socially optimal manner. In this research, an emergency management tool is developed that models the problem as a game theoretic framework in which the crisis events are modeled as the players, the emergency response centers as the resource locations with the possible emergency unit allocations as strategies. The pay-off is modeled as a function of the criticality of the event and the anticipated response times. A single step, non-cooperative, normal form game is formulated and a Nash equilibrium based solution methodology is implemented to provide fair allocation of resources to the emergencies. Experimental results are presented to illustrate the efficacy of the proposed methodology and metrics are derived to quantify the fairness of the solution. A regression analysis is performed to establish the statistical significance of the results.

The continuous scaling trends of interconnect wires in deep submicron (DSM) circuits result in increased interconnect delay and crosstalk noise. In this work, we develop a new postlayout gate sizing algorithm for simultaneous optimization of interconnect delay and crosstalk noise. The problem of postlayout gate sizing is modeled as a normal form game and solved using Nash equilibrium. The crosstalk noise induced on a net depends on the size of its driver gate and the size of the gates driving its coupled nets. Increasing the gate size of the driver increases the noise induced by the net on its coupled nets, whereas increasing the size of the drivers of coupled nets increases the noise induced on the net itself, resulting in a cyclic order dependency leading to a conflicting situation. It is pointed out that solving the postroute gate sizing problem for crosstalk noise optimization is difficult due to its conflicting nature. Game theory provides a natural framework for handling such conflicting situations and allows optimization of multiple parameters. By utilizing this property of game theory, the cyclic dependency of crosstalk noise on its gate sizes can be solved as well as the problem of gate sizing for simultaneous optimization of interconnect delay and crosstalk noise can be effectively modeled, whose objective function is again conflicting in nature. We have implemented two different strategies in which games are ordered according to 1) the noise criticality and 2) delay criticality of nets. The time and space complexities of the proposed gate sizing algorithm are linear in terms of the number of gates in the design. Experimental results for a noise critically ordered game theoretic approach on several medium and large open core designs indicate average improvements of 15.48 percent and 18.56 percent with respect to Cadence place and route tools in terms of interconnect delay and crosstalk noise, respectively, without any area overhead or the need for rerouting. Further, the algorithm performs significantly better than simulated annealing and genetic search as established through experimental results. A mathematical proof of existence for the Nash equilibrium solution for the proposed gate sizing formulation is also provided

Logarithmic number systems (LNS) offer a viable alternative in terms of area, delay, and power to binary number systems for implementing multiplication and division operations for applications in signal processing. The Mitchell algorithm (MA), proposed, reduces the complexity of finding the logarithms and the antilogarithms using piecewise straight line approximations of the logarithm and the antilogarithm curves. The approximations, however, result in some loss of accuracy. Thus, several methods have been proposed in the literature for improving the accuracy of Mitchell's algorithm. In this work, we investigate a new method based on operand decomposition (OD) to improve the accuracy of Mitchell's algorithm when applied to logarithmic multiplication. In the OD technique proposed, for reducing the amount of switching activity in binary multiplication, the two inputs to be multiplied are together decomposed into four binary operands and the product is expressed as the sum of the products of the decomposed numbers. We show that applying operand decomposition to the inputs as a preprocessing step to Mitchell's multiplication algorithm significantly improves the accuracy. Experimental results indicate that the proposed algorithm for logarithmic multiplication reduces the error percentage of Mitchell's algorithm by 44.7 percent on the average. It is also shown that the OD method yields further improvement when combined with the other correction methods proposed in the literature

We propose a novel, nonsimulative probabilistic model for switching activity in sequential circuits, capturing both spatio-temporal correlations at internal nodes and higher order temporal correlations due to feedback. This model, which we refer to as the temporal dependency model (TDM), can be constructed from the logic structure and is shown to be a dynamic Bayesian network. Dynamic Bayesian networks are extremely powerful in modeling high order temporal, as well as spatial, correlations; TDM is an exact model for the underlying conditional independencies. The attractive feature of this graphical representation of the joint probability function is not only that it makes the dependency relationships amongst nodes explicit, but it also serves as a computational mechanism for probabilistic inference. We report average errors in switching probability of 0.006, with errors tightly distributed around mean error values, on ISCAS'89 benchmark circuits involving up to 10000 signals.

The continuous scaling of interconnect wires in deep submicron (DSM) circuits results in increased interconnect delay, power, and crosstalk noise. In this work, we develop a game-theoretic framework and multimetric optimization algorithms for the simultaneous optimization during wire sizing of (i) interconnect delay and crosstalk noise, and (ii) interconnect delay, power, and crosstalk noise. We formulate the wire sizing optimization problem as a normal form-game model and solve it using Nash equilibrium theory. Game theory allows the optimization of multiple metrics with conflicting objectives. This property is exploited in modeling the wire sizing problem while simultaneously optimizing various design parameters like interconnect delay, power, and crosstalk noise, which are conflicting in nature. The nets connecting the driving cell and the driven cell are divided into net segments. The net segments within a channel are modeled as players and the range of possible wire sizes forms the set of strategies. The payoff function is modeled (i) as the geometric mean of interconnect delay and crosstalk noise in the case of first formulation, and (ii) as the weighted sum of interconnect delay, power, and crosstalk noise in the second formulation. The net segments are optimized from the ones closest to the driven cell towards the ones at the driving cell. Complete information about the coupling effects among the nets is extracted after the detailed routing phase. The time and space complexities of the proposed wire sizing formulations are linear in terms of the number of net segments. Experimental results on several medium and large open-core designs indicate that the proposed algorithm for simultaneous optimization of interconnect delay and crosstalk noise yields an average reduction of 21.48% in interconnect delay and a 26.25% reduction in crosstalk noise without any area overhead, over and above the optimization from the Cadence place and route tools. It is shown through experimental results that the algorithm performs significantly better than simulated annealing and genetic search. Further, new simple but accurate models are developed for three parallel interconnect net segments. It is shown that these models yield the same level of accuracy with significantly better run times compared to the models reported in Chen et al. [2004]. A mathematical proof of existence for the Nash equilibrium solution for the proposed wire sizing formulation is also provided.

In low-power design for battery-driven portable applications, the reduction of peak power, peak power differential, cycle difference power, average power and energy are equally important. These are different forms of dynamic power dissipation of a CMOS circuit, which is predominant compared to static power dissipation for higher switching activity. The peak power, the cycle difference power, and the peak power differential drive the transient characteristic of a CMOS circuit. In this article, we propose an ILP-based framework for the reduction of energy and transient power through datapath scheduling during behavioral synthesis. A new metric called “modified cycle power function” (CPF*) is defined that captures the above power characteristics and facilitates integer linear programming formulations. The ILP-based datapath scheduling schemes with CPF* as objective function are developed assuming three modes of datapath operation, such as, single supply voltage and single frequency (SVSF), multiple supply voltages and dynamic frequency clocking (MVDFC), and multiple supply voltages and multicycling (MVMC). We conducted experiments on selected high-level synthesis benchmark circuits for various resource constraints and estimated power, energy and energy delay product for each of them. Experimental results show that significant reductions in power, energy and energy delay product can be obtained.

Recently, dynamic frequency scaling has been explored at the CPU and system levels for power optimization. Low-power datapath scheduling using multiple supply voltages has been well researched. In this work, we develop new datapath scheduling algorithms that use multiple supply voltages and dynamic frequency clocking in a coordinated manner in order to reduce the energy consumption of datapath circuits. In dynamic frequency clocking, the functional units can be operated at different frequencies depending on the computations occurring within the datapath during a given clock cycle. The strategy is to schedule high-energy units, such as multipliers at lower frequencies, so that they can be operated at lower voltages to reduce energy consumption and the low-energy units, such as adders at higher frequencies, to compensate for speed. The proposed time- and resource-constrained algorithms have been applied to various high-level synthesis benchmark circuits under different time and resource constraints. The experimental results show significant reduction in energy for both the algorithms.

Watermarking is the process that embeds data called a watermark, a tag, or a label into a multimedia object, such as images, video, or text, for their copyright protection. According to human perception, the digital watermarks can be divided into four categories.. A watermark is a secondary translucent image overlaid into the primary image and appears to a viewer on a careful inspection. The in watermark is embedded in such a way that the modifications made to the pixel value is perceptually not noticed, and it can be recovered only with an appropriate decoding mechanism. This paper presents a new very large scale integration (VLSI) architecture for implementing two digital image watermarking schemes. The proposed architecture is designed to aim at easy integration into any existing digital camera framework. To the authors' knowledge, this is the first VLSI architecture for implementing watermarking schemes. A prototype chip consisting of 28 469 gates is implemented using 0.35-/spl mu/ technology, which consumes 6.9-mW power while operating at 292 MHz.

Watermarking is the process that embeds data called a watermark, a tag, or a label into a multimedia object, such as images, video, or text, for their copyright protection. According to human perception, the digital watermarks can either be visible or invisible. A visible watermark is a secondary translucent image overlaid into the primary image and appears visible to a viewer on a careful inspection. The invisible watermark is embedded in such a way that the modifications made to the pixel value is perceptually not noticed, and it can be recovered only with an appropriate decoding mechanism. This paper presents a new very large scale integration (VLSI) architecture for implementing two visible digital image watermarking schemes. The proposed architecture is designed to aim at easy integration into any existing digital camera framework. To the authors' knowledge, this is the first VLSI architecture for implementing visible watermarking schemes. A prototype chip consisting of 28 469 gates is implemented using 0.35-/spl mu/m technology, which consumes 6.9-mW power while operating at 292 MHz.

In this paper, we investigate the estimation of switching activity in VLSI circuits using a graphical probabilistic model based on cascaded Bayesian networks (CBNs). First, we develop a theoretical analysis for Bayesian inferencing of switching activity and then derive upper bounds for certain circuit parameters which, in turn, are useful in establishing the cascade structure of the CBN model. We formulate an elegant framework for maintaining probabilistic consistency in the interfacing boundaries across the CBNs during the inference process using a tree-dependent (TD) probability distribution function. A TD distribution is an approximation of the true joint probability function over the switching variables, with the constraint that the underlying BN representation is a tree. The tree approximation of the true joint probability function can be arrived at by using a maximum weight spanning tree (MWST) built using pairwise mutual information about the switching occurring at pairs of signal lines on the boundary. Further, we show that the proposed TD distribution function can be used to model correlations among the primary inputs which is critical for accuracy in modeling of switching activity. Experimental results for ISCAS circuits are presented to illustrate the efficacy of the proposed CBN models.

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 battery driven portable applications, the minimization of energy, average power, peak power, and peak power differential are equally important to improve reliability and efficiency. The peak power and the peak power differential drive the transient characteristics of a CMOS circuit. In this paper, we propose a framework for the simultaneous reduction of energy and transient power during behavioral synthesis. A new metric called "cycle power function" (CPF) is defined which captures the transient power characteristics as an equally weighted sum of the normalized mean cycle power and the normalized mean cycle differential power. Minimizing CPF using multiple supply voltages and dynamic frequency clocking under resource constraints results in the reduction of both energy and transient power. Based on the above, we develop a new datapath scheduling algorithm called CPF-scheduler which attempts at power and energy minimization by minimizing the CPF parameter during the scheduling process. The type and number of functional units available become the set of resource constraints for the scheduler. Experimental results indicate that the proposed scheduler achieves significant reductions in terms of power and energy.

The use of multiple supply voltages for energy and average power reduction is well researched and several works have appeared in the literature. However, in low power design using deep submicron and nanometer technology, the peak power, peak power differential, average power and total energy are equally critical design constraints. In this work, we propose datapath scheduling algorithms for simultaneous minimization of peak and average power while maintaining performance by use of dynamic frequency clocking and multiple supply voltages. The algorithms use integer linear programming based models. The dynamic frequency clocking methodology is more useful for data intensive signal processing applications. The effectiveness of our scheduling technique is measured by estimating the peak power consumption, the average power consumption and the power delay product of the datapath circuit. Furthermore, the proposed scheduling scheme is compared with combined multiple supply voltages and multicycling scheme. Experimental results show that combined multiple supply voltages (3.3V,2.4V) and dynamic frequency clocking scheme achieves significant reductions in peak power (72% on the average), average power (71% on the average) and power delay product (54% on the average).

We model the power fluctuation as cycle-to-cycle power gradient and minimize the mean of the power gradients using ILP. We propose scheduling schemes for three modes of datapath design: single supply voltage and single frequency (SVSF), multiple supply voltages and dynamic frequency clocking (MVDFC), and multiple supply voltages and multicycling (MVMC). Various experiments are conducted on selected high-level synthesis benchmarks. Experimental results in terms of several parameters, such as mean power gradient, mean cycle power, peak power, and power delay product, are presented.

We investigate the problem of dynamic power optimization through gate sizing and voltage scaling under a given delay constraint. Several algorithms have been proposed in the literature to handle gate sizing and voltage scaling independently or together with the goal of satisfying certain power budget constraints without affecting the timing constraints. Decentralized algorithms have been proposed in the literature for distributing a divisible resource among the components of the system. We formulate the problems as economic models that attempt to distribute the delay among the gates of the circuit such that the dynamic power of the circuit is optimized. Since, optimizing all the gates in the circuit at the same time can be computationally intensive, the gates in a given path are handled together. The circuits are represented as economic models and mathematical formulations are developed which are further transformed as game theoretic models for which Nash equilibrium based solutions are investigated. Thus, the main contribution of this work is the application of microeconomic models and game theory for these VLSI CAD problems. Models are developed for the gate sizing, voltage scaling and simultaneous gate sizing and voltage scaling problems. The algorithms are iterative, fast, simple and can lead to rapid convergence. Competition among the gates can provide the best overall optimization. In the proposed algorithms, the gates compete against each other to optimize their power consumption and hence that of the entire circuit. The proposed solutions yield better power optimization than other methods as shown in the experimental results for MCNC '91 benchmark circuits.

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).

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.

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.

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.

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.

The problem of tree pattern matching for object recognition in images is computationally intensive in nature. In two-dimensional images, the objects can be represented through multiscale decomposition as tree structures. The pattern tree representing an object can be matched with a subject tree representing an image in order to detect the objects within the image. In this paper, we describe a new systolic algorithm and its realization as a VLSI chip for tree pattern matching. The hardware algorithm is based on a linear array of processing elements (PEs) where the pattern matching is done in a pipelined fashion relying on nearest-neighbor communication between the PEs and the subject and pattern trees of arbitrary length can be processed using a fixed size PE array. The algorithm has an improved execution time of O(/spl lceil/m/a/spl rceil/n) required to perform the matching where in, a and n are the sizes of the pattern tree, processor array, subject tree respectively. A prototype CMOS VLSI chip implementing the proposed algorithm has been designed and verified It is shown that the hardware algorithm proposed in this work represent a significant improvement in terms of computational complexity, data flow, and architecture over the ones previously proposed for this problem.

In this paper, a new type of Petri net called Hierarchical Colored Hardware Petri net, to model real-delay switching activity for power estimation is proposed. The logic circuit is converted into a HCHPN and simulated as a Petri net to get the switching activity estimate and thus the power values. The method is accurate and is significantly faster than other simulative methods. The HCHPN yields an average error of 4.9% with respect to Hspice for the ISCAS '85 benchmark circuits. The per-pattern simulation time is about 46 times lesser than PowerMill.

We represent switching activity in VLSI circuits using a graphical probabilistic model based on cascaded Bayesian networks (CBNs). We develop an elegant method for maintaining probabilistic consistency in the interfacing boundaries across the CBNs during the inference process using a tree-dependent (TD) probability distribution function. A tree-dependent (TD) distribution is an approximation of the true joint probability function over the switching variables, with the constraint that the underlying Bayesian network representation is a tree. The tree approximation of the true joint probability function can be arrived at using a maximum weight spanning tree (MWST) built using pairwise mutual information between switchings at two signal lines. Further we also develop a TD distribution based method to model correlations among the primary inputs which is critical for accuracy in Bayesian modeling of switching activity. Experimental results for ISCAS circuits are presented to illustrate the efficacy of the proposed methods.

A hierarchical colored hardware Petri net (HCHPN) based model was proposed in (A. K. Murugavel et al, Proc. of Intl. Conf. on VLSI Design, pp. 181-186, 2001) for estimating switching activity in combinational circuits. In this paper, we model sequential circuits as HCHPNs incorporating real delays for both gates and interconnects. Thus, the given sequential circuit is first modeled as a HCHPN and simulated for switching activity estimation in the Petri net domain which leads to better accuracy and faster simulation. Experimental results for ISCAS'89 benchmark circuits show that the proposed HCHPN model yields accuracy on an average within 4.4% of that of PowerMill. The per-pattern simulation time for HCHPNs is about 2.4 times less than that of PowerMill.

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.

We propose a new switching probability model for combinational circuits using aLogic-Induced-Directed-Acyclic-Graph(LIDAG) and prove that such a graph corresponds to aBayesian Networkguaranteed to map all the dependencies inherent in the circuit. This switching activity can be estimated by capturing complex dependencies (spatio-temporal and conditional) among signals efficiently by local message-passing based on the Bayesian networks. Switching activity estimation of ISCAS and MCNC circuits with random input streams yield high accuracy (average mean error=0.002) and low computational time (average time=3.93 seconds).

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.

Autonomous underwater vehicles (AUVs) have been used extensively in deep sea research. Failure detection and control is an important issue in maintaining the stability of an AUV. In most AUVs, the vehicle resurfaces in the event of minor failures such as in the depth sensor, the inclinometer, etc. The paper proposes an intelligent system for failure detection and control in AUVs where the vehicle could continue exploration in case of minor failures in the sensors and control surfaces. The intelligent system, based on the model proposed in Patel and Ranganathan (1996), integrates the adaptability of an artificial neural network (ANN) and the inferencing ability of a fuzzy rule based expert system on a single VLSI chip. The associative function of the ANN is used to recognize and detect the failures by observing the various changing parameters of the dynamic vehicle. The inferencing ability of an expert system suggests ways to control the failure and indicates the subsequent status of the vehicle. The entire system could be used as a low level diagnoser in an overall control system for AUVs.

Reconfigurable single-chip emulation systems were proposed as an alternative to multichip emulation systems. Because they cannot be emulated on a single chip at once, large designs are sliced into partitions that are downloaded and executed sequentially on the same reconfigurable emulation chip. In this paper, we address the problem of partitioning a design on a reconfigurable single-chip emulator under resource constraints. First, we extract an acyclic flow graph of the design to be emulated. Then, we model the problem as an integer linear programming problem (IP) based on the acyclic flow graph of the design where the structure of the assignment and precedence constraints produce a tight formulation. To partition a design, our algorithm uses two distinct steps with different objectives. In the first step, we minimize the number of cycles needed to schedule every look-up table (LUT) in the circuit. Then flip-flops (FFs) are inserted into the appropriate cycles of the schedule in the second step. Experiments are conducted on small- and medium-size circuits from the MCNC Partitioning93 benchmark suite. The obtained results show that our algorithm produces optimal partitioning schedules.

Multi-FPGA 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 multi-terminal nets in a multi-FPGA system that uses partial crossbars as interconnect structures. First, we model the multi-terminal 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 algorithm’s performance. The obtained results show that the algorithm finds an exact routing solution in a very short time. Keywords FPGA routing, FPGA architecture, layout synthesis, interconnect optimization, branch-and-price, integer programming. 1.

The EZW lossless coding framework consists of three stages: (i) a reversible wavelet transform, (ii) an EZW data structure to order the coefficients and (iii) an arithmetic coding using context modeling. In this work, we discuss the various experiments conducted on context modeling of wavelet coefficients for arithmetic coding to optimize the compression efficiency. The context modeling of wavelet coefficients can be classified into two parts: (i) context modeling of significance information and (ii) context modeling of the remaining or residue information. It was observed from our experiments while context modeling of residue helped in achieving considerable compression efficiency, the context modeling of significance information helped only to a modest extent.

In signal processing applications, it is often required to compute the integral of the bivariate Gaussian probability density function (PDF) over the four quadrants. When the mean of the random variables are nonzero, computing the closed form solution to these integrals with the usual techniques of integration is infeasible. Many numerical solutions have been proposed; however, the accuracy of these solutions depends on various constraints. In this work, we derive the closed form solution to this problem using the characteristic function method. The solution is derived in terms of the well-known confluent hypergeometric function. When the mean of the random variables is zero, the solution is shown to reduce to a known result for the value of the integral over the first quadrant. The solution is implementable in software packages such as MAPLE.

Accurate switching-activity estimation is crucial for power budgeting. It is impractical to obtain an accurate estimate by simulating the circuit for all possible inputs. An alternate approach would be to compute tight bounds for the switching activity. In this paper, we propose a nonsimulative decision theoretic method to compute the lower bound for switching activity. First, we show that the switching activity can be modeled as the decision error of an abstract two-class problem. It is shown that the Bayes error L* is a lower bound for the switching activity. Further, we improve L* to obtain a tighter bound L/sub 1/, which is based on the one-nearest neighbor classification error. The proposed lower bounds are used for switching-activity characterization at the register transfer (RT) level. Experimental results for the RT-level switching-activity estimates for ISCAS'85 circuits are presented. This technique is simple and fast and produces accurate estimates.

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.

Summary form only given. Channel matched quantization for image transmission over time varying channels reduces the effects of channel errors. The presence of variable length codes in compression standards like the JPEG cause error propagation due to bit errors. Unequal error protection (UEP) schemes have emerged as an effective method to combat catastrophic loss in the received signal due to burst and random errors. An empirical channel matched quantizer design algorithm that jointly optimizes the distortion due to quantization-channel noise and a new efficient UEP scheme for image transmission are proposed. The baseline JPEG encoder is used to compress the 8-bit gray level images before transmission. A slow frequency non-selective Rayleigh fading channel is considered in this study. A quantization table optimized for human visual quality is used for very low channel bit error rates. For higher bit error rates, the quantization table is matched to the channel conditions by multiplying its entries by the optimal quantization multiplication factor, M/sup */ such that the average number of received image blocks in error is minimized. M/sup */ is computed for each bit error rate ranging from 10/sup -4/ to 10/sup -1/ through empirical modeling of the trade-off between the quantization and the channel noise. In order to enhance the performance of the proposed system, a new UEP scheme that limits the error propagation due to variable length encoding is used. This scheme works by packing the output bits of the JPEG coder into slots of fixed size.

Effective power reduction can be achieved at higher levels of design abstraction. A number of such techniques have been proposed for power optimization in the literature. These techniques use RT level templates which characterize the area, delay and power of the design. The templates are based on some knowledge of the logic block such as the number of nodes, levels and their interconnections. Methods which model the power consumption of a logic block whose internal details are not known are desirable to explore trade-offs early on in the design cycle. Recently, lower bounds for switching activity at the gate level based on decision theory have been proposed by the authors. This has been extended to derive the average switching activity of a module based solely on its functionality. The experimental results on ISCAS '85 benchmark circuits indicate that the approach gives reasonably accurate estimates at low computational cost. In this paper, we use the RT level estimates for pourer exploration at the behavioral level for various high level synthesis benchmarks. The experimental results show that appropriate design decisions can be taken at the high level to reduce the cost of redesigning which would be incurred if committed to a particular circuit structure.

The efficient transportation of real-time variable bit rate (VBR) video traffic in high-speed networks has been an area of active research. The VBR video traffic characteristics having heavy tail distribution, high variance and correlation properties are quite complex. These characteristics of VBR video (MPEG) traces are studied and a new traffic model for VBR video is proposed. A modulating Markov chain model is employed in which each state represents the I, B, P frames (pictures) of a group of pictures (GOP). From the video traces, we classify the scenes (collection of GOPs) into high- and low-activity scenes, based on the average number of bits generated during the scenes. The scene activity is modeled by an auxiliary Markov chain wherein each state represents the degree of activity (high/low). The transitions of the auxiliary Markov chain represent scene changes of a video sequence. The bit generation during a low-activity scene is modeled by independent AR processes for I, P, B frames. The cross-correlation with the I frames is taken into account by the AR(1) processes for the P and B frames during the high-activity scenes. The traffic thus generated by the model is analyzed and its characteristics are found to be in close agreement with those exhibited by the real traces. The proposed model is quite flexible in order to model scene changes and the autocorrelation characteristics that are common to all packetized broadcast video sequences. The parameters of the scene changes in the proposed traffic model can be appropriately tuned, so that, even the teleconferencing video traffic that involves few scene changes, can be modeled.

This paper describes a new adaptive wormhole routing algorithm for distributed memory MIMD systems. The algorithm uses the absolute sum of the difference in the coordinates of the nodes, as a measure to determine which of the available output channels the packet must be routed through. Thus, the routing decision is local, involves simple computations and provides maximum adaptivity to the traffic. The adaptivity of the packets that have resided in the network for a long time, is restricted to the shortest path to their destination, which ensures livelock freedom. In order to avoid deadlock, packets are buffered and then reintroduced when routing paths become available. The algorithm maps to a simple architecture.

Optimal quantization and channel estimation are one among the main issues in low bit-rate video transmission over time varying noisy channels. Previous approaches to these issues were mainly based on quantizers optimized for parametric channel models and pilot symbol aided techniques for channel identification. However, this optimality may not hold when the randomly varying channel behavior deviates from these models. Also, the cost involved in terms of delay could be large for pilot symbol based channel estimation. We propose a new empirically optimized channel matched quantizer and a stochastic learning algorithm that estimates and tracks the channel with minimal additional delay and overhead. Performance analysis of the algorithm shows that the new adaptive quantizer results in a better quality video. The learning algorithm converges very fast.

The efficient transportation of real-time variable bit rate (VBR) video traffic in high-speed networks is critical for current multimedia applications. The real-time VBR video traffic has stringent delay and cell-loss requirements. The high burstiness of the correlated VBR video traffic makes the adaptive resource management, highly desirable. This paper presents a dynamic bandwidth allocation scheme for VBR video traffic based on buffer monitoring and a simple least mean square (LMS) traffic prediction system. The goal is to reduce the frequency of the bandwidth changes and at the same time reduce the cell-loss rate (CLR) with better bandwidth utilization. Simulation results indicate that utilization of up to 0.8 can be achieved by the proposed scheme even under high source alignment for bursty VBR video traffic, with less frequent reallocations.

In this paper, a rate controller for a H.261 based video encoder is proposed. The rate controller adaptively chooses the optimal channel matched quantizer using a stochastic learning automaton. The automaton learns the channel characteristics based on a one bit feedback from the decoder. The rate control algorithm is shown to converge to the optimal choice of the quantizer very quickly for various channel bit error probabilities and for different video sequences. The adaptation can be achieved in real-time. The peak signal to noise ratio of the received video signal is seen to be better using the proposed approach.

It is known that for fixed error probabilities sequential signal detection based on the sequential probability ratio test (SPRT) is optimum in terms of the average number of signal samples for detection. But, often suboptimal detectors like the sequential sign detector are preferred over the optimal SPRT. When the additive noise statistic is independent and identically distributed (i.i.d.), the sign detector is preferred for its simplicity and nonparametric properties. However, in many practical applications such as the usage of high speed sampling devices the noise is correlated. A generalized sequential sign detector for detecting binary signals in stationary, first-order Markov dependent noise is studied. Under the i.i.d. assumptions, this reduces to the usual sequential sign detector. The optimal decision thresholds and the average sample number for the test to terminate are derived. Numerical results are given to show that the proposed detector exploits the correlation in the noise and hence results in quicker detection. The method can also be extended to Mth order Markov dependence by converting it to a first-order dependence in an extended state space.

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.

The need for high-performance image processing systems has led to the design and development of several application-specific parallel processing systems. An SIMD linear array processor with dynamic frequency clocking is proposed for real-time image processing applications. The architecture uses a novel concept called dynamic frequency clocking which allows the processor to vary the clock frequency dynamically based on the operation being performed. A VLSI chip based on the proposed architecture has been designed and verified using the Cadence design tools. The chip will operate at between 400 and 50 MHz based on the operation being performed. Several low-level image processing tasks have been mapped onto the architecture to evaluate the system performance and to demonstrate the effectiveness of the dynamic frequency clocking scheme.

This paper presents a comparative study of the performance of the bidirectional ring and the unidirectional ring multiprocessor, with emphasis on the effect of system parameters, specifically, the message length and the relative processor speed. The choice of these parameters may not be optimum due to the performance cost tradeoffs in practice. Our study shows that the use of bidirectional ring is more effective in such suboptimum system configurations and can improve the processor utilization by up to 35%.

The framework for an image coding system based on embedded zerotrees consists of three stages: (i) wavelet transform (ii) embedded zerotree encoding and (iii) adaptive arithmetic encoding. In this framework, the selection of the wavelet filter becomes an important issue. In this paper, we present a modification to the scanning approach in the set partitioning algorithm proposed in Said and Pearlman (1996) to exploit the correlation in a local neighborhood. Two new criteria are proposed for evaluating the performance of wavelets in lossless image compression applications: zero tree count and monotone spectral ordering of subbands produced after the wavelet transform in a multiresolution scheme. We evaluate several wavelet filters to test the evaluation criteria and present experimental results to justify the proposed performance criteria.

In this paper, we describe a VLSI system architecture for real-time intelligent decision making. The architecture integrates the adaptability of a backpropagation based neural network and the decision making ability of a rule based fuzzy expert system on a chip. The intelligent decision making system consists of a back-propagation based neural network for adaptive learning and a rule-based fuzzy expert system for decision making. Both the neural network and the expert system are realized as linear systolic arrays. Thus, the entire system can be implemented in VLSI with a few basic cells. The architecture exploits the principles of pipelining and parallelism to the maximum possible extent in order to achieve high speed and throughput. The proposed hardware can yield a real-time decision every 5ns based on a 200 MHz clock. Currently, a prototype CMOS VLSI chip implementing the proposed architecture is being built and verified.

This paper describes the design of a linear systolic array algorithm and a VLSI architecture for finding the maximum matching in a convex bipartite graph. The 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 is scalable and the algorithm is partitionable, i.e., large size problems can be partitioned and executed on a fixed sized array. The PE organization is simple and the architecture does not require any local or global memory. The proposed hardware could be used in various applications such as logic synthesis and channel routing in VLSI CAD, collision avoidance in robotics etc. The proposed chip is estimated to operate at a frequency of 100 MHz based on 1-micron SCMOS technology.

The paper describes a VLSI architecture for lossless image compression based on the Variable Block Size Segmentation (VBSS) scheme. The VBSS scheme segments the image into variable size blocks, extracts the redundancy features in them, and encodes the blocks using suitable coding techniques in order to obtain maximum compression. The scheme is computationally intensive and time consuming when implemented in software. The proposed architecture fully utilizes the principles of parallelism and pipelining in order to obtain high speed and throughput. It requires simple basic cells and regular nearest-neighbor communication making it suitable for VLSI implementation. A prototype CMOS VLSI chip implementing the image characteristics extraction subsystem has been designed and verified using the Cadence design tools at the University of South Florida. The chip can be used to process an image of 1024/spl times/ 1024 pixels in 1.3 ms operating at a frequency of 100 MHz.

In this paper, we describe the concept of dynamic frequency clocking and the design of a linear VLSI array processor, DFLAP, for use in image processing applications. Dynamic frequency clocking enables the chip to operate at different frequencies switching dynamically depending on the instruction being executed. Such a technique facilitates better management of throughput and power requirements in a VLSI system. The applicability of dynamic clocking in pipelined systems is also investigated. The effectiveness of the dynamic frequency architecture is illustrated by mapping several tasks for image processing applications.

A novel dynamic frequency based SIMD linear array processor (DFLAP) for image processing applications is proposed. The operating clock frequency of the processor is varied dynamically between 400 MHz and 50 MHz based on the operation performed in order to enhance the processor throughput. An efficient implementation for the dynamic clocking unit (DCU) which enables dynamic switching of clock frequencies is presented. Each processing element in the linear array contains an 8-bit arithmetic/logic unit, an 8/spl times/8 single-cycle multiplier, a shifter, a bidirectional neighbor communication unit, a 32/spl times/8 dual port SRAM, and a DCU. The architecture was designed and implemented using CADENCE design tools. Several low-level image processing tasks have been mapped onto the architecture to demonstrate the effectiveness of the dynamic frequency based architecture.

In this paper, new parallel algorithms for single and complete link hierarchical agglomerative clustering are presented. The parallel algorithms have been mapped on a SIMD machine model with a linear interconnection network. The model consists of a linear array of N PE's, where N is the number of patterns, interfaced with a global host machine and the interconnection network provides inter-PE and PE-to-host/host-to-PE communication. The proposed algorithms are faster than previously known algorithms for hierarchical clustering. For clustering a data set with N patterns, using N PE's, the computation time for the single link clustering algorithm is shown to be O(NlogN) and that for the complete link clustering algorithm is shown to be O(N/sup 2/). The parallel algorithms have been verified through simulations on the Intel's iPSC/2 concurrent supercomputer.

This paper describes a VLSI architecture for lossless image compression based on the variable block size segmentation (VBSS) scheme. The VBSS scheme segments the image into variable size blocks, extracts the redundancy features in them, and encodes the blocks using suitable coding techniques in order to obtain maximum compression. The scheme is computationally intensive and time consuming when implemented in software. The proposed architecture fully utilizes the principles of parallelism and pipelining in order to obtain high speed and throughput. It requires simple basic cells and regular nearest-neighbor communication making it suitable for VLSI implementation.

Medical images such as mammograms and chest X-rays require resolution of the the order of 4096/spl times/4096 pixels with 10 to 16 bits per pixel. Because of the poor visualization and extreme sensitive nature of the information content, any information loss in storage and retrieval of medical information may not be acceptable. In this paper, an efficient lossless image compression scheme is proposed for high resolution medical images. The proposed method is based on two concepts: multibit plane slicing and variable block segmentation. It exploits the two basic image characteristics smoothness and similarity to achieve high compression efficiency. The proposed algorithm is applied to 12 and 16 bit mammogram images. The compression efficiency of the proposed algorithm is better than that obtained by other lossless compression schemes including the scheme based on the JPEG standard.

From a multiresolution perspective, a wavelet decomposition of an image f(x,y) at a resolution. 2/sup j/, consists of an approximated image at a resolution 2/sup j-1/ and three detail images along the horizontal, vertical and diagonal directions. In the first scheme, the approximated wavelet coefficients are encoded using variable block size segmentation (VBSS) algorithm and the detail signals are encoded using directional prediction and categorization. The residual error due to the finite precision arithmetic is significant and is encoded using adaptive arithmetic encoding technique. In the alternate scheme, we propose a new concept of multiresolution which avoids the finite precision arithmetic errors. The approximated image in the alternate scheme is a decimated version of the original image. The equivalence of the alternate multiresolution scheme to the original multiresolution scheme is also analyzed mathematically. The performance of scheme one is comparable to that exhibited by JPEG lossless schemes.

In this paper, we propose a dynamic frequency linear array processor, DFLAP, for real-time image processing applications. The architecture uses a novel concept of dynamic frequency clocking which allows the chip to operate between, a maximum frequency of 400 MHz and a minimum frequency of 50 MHz based on the operation being performed. The dynamic clocking scheme is especially useful in the contest of image processing applications where certain tasks require only logic functions while others require only additions and certain others multiplication or division. The proposed architecture provides speedup by supporting two levels of parallelism and using variable frequency single clock cycle operations. DFLAP provides parallelism at the array level using multiple processing elements (PEs) and at a functional level allowing concurrent use of various units in the PE. The array architecture contains N PEs, where the image size is N/spl times/N and each PE in turn contains an a-bit arithmetic/logic unit, an 8/spl times/8 single-cycle multiplier, a shifter, a neighbor communication unit, a 32/spl times/8 dual port SRAM and a dynamic clocking unit (DCU). The DCU an each PE enables dynamic switching of clock frequencies. The dynamic clocking scheme provided a speedup ranging from 1.5 to 3 over the uni-frequency clocking for various low level pattern recognition and image processing algorithms that were mapped onto the chip.

In this paper, we describe a new special purpose VLSI architecture for image thinning. The architecture is systolic and is based on an algorithm that achieves a high degree of parallelism. The proposed algorithm computes the skeleton of multiple objects in an image in linear time by making 2 scans over the 4-distance transform of the image. The algorithm is mapped onto a linear systolic array of simple processing elements (PEs) and for an N/spl times/N image, the architecture requires N PE's. The entire array can be realized in a single VLSI chip. The proposed hardware can perform thinning on a 512/spl times/512 image in 2.59 msec and on a 256/spl times/256 image in 0.327 msec. Currently, a prototype CMOS VLSI chip implementing the proposed architecture is being designed and built at the University of South Florida.

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 or 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 determination is a computationally intensive task, and the design of special purpose hardware could result in a significant speed up. This paper describes in detail a VLSI architecture for computing the edit distance between arbitrary ordered trees, based on a parallel, systolic realization of the dynamic programming algorithm proposed by S.Y. Lu (1979). This architecture represents a significant improvement over that described by Sastry and Ranganathan (1994), which restricted the type of trees that could be processed by it. Two partitioning strategies to process trees of arbitrary sizes and structures on a fixed size implementation in multiple passes are proposed and analyzed.>

The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree. Several sequential and parallel algorithms have been proposed in the literature for this compute bound problem. Most of the parallel algorithms are based on the theoretical PRAM model of computation. In this paper, we propose two efficient parallel algorithms for tree pattern matching based on the linear systolic array model. The algorithms can be mapped onto any SIMD machine. The algorithms require O(n+m) time to perform the matching using either n or m processors, where n is the size of the subject tree and m is the size of the pattern tree. The algorithms represent a significant improvement over the existing ones in view of implementation.

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.

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.>

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.>

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.>

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.

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.>

We describe the design and implementation of a VLSI chip for image template matching. The hardware algorithm and architecture for template matching are based on a technique known as moment preserving pattern matching. The architecture fully utilizes the principles of parallelism and pipelining in order to obtain high speed and throughput. The proposed VLSI system is much simpler, achieves higher speed, has a lower hardware complexity and utilizes lesser memory than other hardware architectures proposed for template matching in the literature. The architecture was simulated using Verilog HDL. A prototype CMOS VLSI chip implementing the proposed architecture has been designed and verified using the Cadence Opus tools. The chip can process a 512/spl times/512 image and 64/spl times/64 template in 1.35 msec operating at a frequency of 100 MHz.>

In this paper, we describe a new special purpose VLSI architecture for template matching, based on a technique known as moment preserving pattern matching (MPPM). This technique first converts the given gray scale image and template into binary form using the moment preserving quantization method and then uses a pairing function to compute the similarity measure. The technique yields accurate results comparable to other approaches but involves simpler computations. The proposed architecture is systolic in nature and achieves a high degree of parallelism and pipelining. It is shown that the proposed architecture is much simpler, achieves higher speed, has a lower hardware complexity and utilizes lesser memory than other special purpose architectures for template matching.

In this paper, we present an analysis of two image characteristics which give rise to local and global redundancy in image representation. Based on this study, we propose a lossless image compression scheme which exploits both types of redundancy. The algorithm segments the image into variable size blocks and encodes them depending on characteristics exhibited by the pixels within the block. The performance of the proposed algorithm is studied by software implementation. The proposed algorithm works better than other lossless compression schemes such as the Huffman, the arithmetic, the Lempel-Ziv and the JPEG.

In this paper, we describe the design of an efficient VLSI architecture for image template matching. The hardware algorithm and architecture for template matching are based on a technique known as moment preserving pattern matching, which is proposed by Chon-Chen (1990). The architecture fully utilizes the principles of parallelism and pipelining in order to obtain high speed and throughput. The proposed VLSI system is much simpler, achieves higher speed, has a lower hardware complexity and utilizes lesser memory than other hardware architectures proposed for template matching in the literature.

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.

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. Hierarchical scene matching is a technique for reducing the amount of computation involved in scene matching applications. Most of the past research on this problem has concentrated on efficient software algorithms, and very little effort has been expended on custom hardware solutions. We describe the design of SMAC, a new VLSI architecture for Hierarchical Scene Matching. This architecture achieves a significant amount of speedup by utilizing a large amount of parallelism and pipelining. The paper also describes the design and implementation of a prototype CMOS VLSI chip that implements the exhaustive search task of the scene matching algorithm.>

The edit distance between two strings is defined as the minimum cost of a sequence of editing operations (insertions, deletions and substitutions) that convert one string into the other. This paper presents a linear systolic array 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 is currently being built.>

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.>

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.>

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.>

The design and implementation of a CMOS VLSI chip for data compression and decompression, using tree-based codes are described. The chip, called MARVLE, implements a memory-based architecture, for variable length encoding and decoding based on tree-based codes. The chip implements an architecture that is based on an efficient scheme for mapping the tree representing any binary code onto a memory device. A prototype 2- mu m chip has been designed and verified, and fabricated by MOSIS. The chip can yield a compression rate of 57 Mb/s and a decompression rate of 31 Mb/s with a clock rate of 50 MHz. The VLSI hardware can be used to implement the JPEG baseline compression scheme.>

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 1-D Gabor filter-based edge detector is derived. It is shown that this design criterion holds good for a 2-D Gabor filter-based edge detector as well. Experimental results are presented to demonstrate the significance of the proposed design criterion.>

Describes the design and implementation of a two-dimensional systolic array processor for applications in image processing and computer vision. The processor architecture is based on a SIMD array of 4-bit processing elements, interconnected by a mesh network with four nearest neighbors. The PE array is programmable allowing the user to develop application-specific algorithms for performing analysis on image data. A prototype VLSI chip has been designed implementing a single PE and has been submitted for fabrication. The chip is expected to operate at 25 MHz.>

Describes an area and time efficient systolic array architecture for computations in Dynamic Time Warping (DTW). The special purpose architecture is used to perform the band matrix multiplication in order to compute the local distance metric based on Itakura's log likelihood distance. The time complexity of the algorithm is O(nk) where n and k are the number of elements in the row of the first and second input matrices. The number of processors is equal to the bandwidth w of the output band matrix. The speedup of the parallel algorithm compared to the sequential algorithm is wz where z is the multiplier stages within a PE. The parallel algorithm can be implemented as a single VLSI chip.>

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. Hierarchical scene matching generates a multiresolution pyramid of the images to be matched. The authors describe hierarchical scene matching technique, related work and their proposed VLSI architecture. They present a description of the three subsystems-pyramid generation block, exhaustive search block and template match block. Then they briefly describe the performance attainable with the proposed architecture which uses a large amount of parallelism and pipelining.>

This paper discusses an approach to mo- bile robot path planning which utilizes a wavefront- like propagation method for determining near-optimal paths. This approach is different from previous wave propagation methods in three aspects: it attempts to find near-optimal paths from all locations in the free space to the destination instead of one optimal path from the source location to the destination, may per- form repeated propagations to converge to a solution, and is composed of simplified computations based on local information to facilitate a VLSI implementation. I. INTRODUCTION Wavefront propagation methods for robot path plan- ning have been proposed by other researchers. The tradi- tional approach is to start with a list containing only the destination point (or a region representing a small area around the destination point) and propagate a value rep- resenting the cost of traveling between the two regions to each unvisited neighbor of the region. The region is removed from the list and all its newly visited neighbors are added to the list. The list is sorted by increasing cost and the process is repeated with the lowest cost region in the list. This process terminates when the source region is reached. The actual path is then constructed between the endpoints using the computed cost values. Jahanbin and Fallside(l) have presented some wavefront propagation path planning algorithms consisting only of free-space and obstacles in configuration space. They pre- sented two solutions to the planning problem, one for uniform region sizes and another for non-uniform region sizes. The propagation was performed by the use of a mask which was placed over successive positions on the wavefront. Various shape wavefronts could be propagated depending on the weights in the mask. Once the propa- gation was completed the path was constructed from the source to the lowest cost neighbor and this process was repeated until the destination was reached. There are two

Gabor filters have been applied in several image processing applications such as motion analysis, texture discrimination, and image coding, etc. The authors propose a computationally efficient scheme to compute Gabor filter responses at multiple resolutions and orientations. An architecture is proposed to compute the responses of these filters in 2-D domain by utilizing the symmetric, antisymmetric, and wavelet characteristics of Gabor filters.>

The design and implementation of SAP chip, a systolic array processor for computations in vision, is described. The chip can be used to implement the Gaussian filter, the Laplacian of the Gaussian filter, and scale space generation. The architecture is based on an algorithm that can provide speeds an order of magnitude higher than the speeds of other systems previously proposed. The algorithm utilises the three properties of Gaussian: symmetry, separability, and scaling. The algorithm and the architecture exploit a high degree of pipelining and parallelism in order to obtain high speed, efficiency, and throughput. The architecture is adaptable for masks of any size, and the weights are not restricted to powers of two. The processor was designed using CMOS technology, fabricated, and tested. The chip is fully functional and operates at a rate of 10 MHz.>

Computing optical flow from a given sequence of images is computationally a very expensive task. Spatio-temporal filtering technique is one of the approaches to this task. This approach requires convolution of 3-D input with several 3-D Gabor filters. An efficient technique to compute the responses of Gabor filters by utilizing the functional characteristics of the filters is proposed. The technique significantly reduces the time complexity of computing the spatio-temporal responses. The pyramid structure of Gabor filters is discussed, and an implementation to generate the pyramid of filter responses is described. A VLSI pipelined architecture which effectively utilizes the characteristics of Gabor filters is proposed.>

An efficient parallel architecture that exploits the parallelism and pipelining possible in the difference picture-based technique (IEEE Trans. on Pattern Analysis and Machi Intelligence, vol. PAMI-3, no.5, p.489-543, (1981); Computer, p.12-18, Aug. (1981)) is presented for dynamic scene analysis. Each processor is organized as a pipeline, and the processor architecture is simple enough that the motion detection and classification system can be implemented on a single VLSI chip. The proposed VLSI architecture and the design of the various components of the basic processor are described. VLSI chip implementation issues are discussed.>

A new class of VLSI architectures for data transformation of tree-based codes is proposed. The focus is on transformation functions used for data compression and decompression. The encoding algorithm is based on a pipeline architecture and can generate the code bits in parallel. The algorithms use the principle of propagation of a token in a reverse binary tree constructed from the original codes. The design approaches are applicable to any binary codes, although static Huffman code is used as an illustration. A new hardware algorithm for generating adaptive Huffman codes is proposed and a VLSI architecture for implementing the algorithm is described. The high speed of the new algorithms ensures that data transformation is done as data are being transferred from/to high-speed I/O communication devices.>

Methods are discussed to enhance the efficiency and speed of data compression techniques in DBMS (database management systems). Arithmetic coding utilizes the skewness of character distribution by assigning larger intervals (code ranges) to characters having higher probabilities of occurrence. A scheme is presented which effectively increases the code ranges of individual characters by splitting the interval assignment into different groups. This decreases the rate of interval narrowing and hence improves the compression efficiency. Hardware assistance for arithmetic and tree-based coding is also discussed and high-speed VLSI algorithms for data compression are presented. The proposed algorithms give rates that are an order of magnitude faster than currently attainable encoding speeds.>

A compression algorithm that is tailored to utilize the enormous speed and memory size of supercomputers is presented. It utilizes an enhanced arithmetic coding scheme. Efficient VLSI designs for the enhanced scheme are given. The designs are suitable for inclusion in disk and communication controllers of supercomputers and would provide a practical way to increase thresholds of data transfer rates and communication bandwidth effectively.>