Chaitali Chakrabarti
Professor

School of Electrical, Computer and Energy Engg.,
Ira A. Fulton Schools of Engineering
Arizona State University, Tempe Arizona 85287-5706
Phone: (480) 965-9516, Fax: (480) 965-8325, Email: chaitali@asu.edu

Research Areas

• Software Defined Radio
• Low Power Algorithm Design
• System-level Design of Emerging Memory Technologiesn
• Reliable Memory System Design
• Memory Design and Exploration
• Energy-Efficient Task Scheduling
• Task Scheduling for Fuel Cell-Battery Hybrid System
• Thermal-aware System Design
• Energy-Efficient Compilation
• High Level Synthesis for Low Power

VLSI Implementations of Signal Processing and Communication Systems

• Algorithms and Architectures for Portable Ultrasound
• Efficient Implementation of Neural Network Architectures
• Algorithms and Architectures for Speech Processing
• Automated Framework for Designing Signal Processing Systems
• Architectures for Efficient Transform Computation
• Algorithms and Architectures for Statistical Signal Processing
• Architectures for Image Processing
• Architectures for Communication Applications
• Algorithms and Architectures for Motion Estimation

Software Defined Radio

Design and Implementation of Turbo Decoders for Software Defined Radio
Y. Lin, S. Mahlke, T. Mudge, C. Chakrabarti, K. Flautner and A. Reid
Proc. of the IEEE Workshop on Design and Implementation of Signal Processing Systems, Oct 2006.

---

Low Power Algorithm Design

In the design of low power systems, power has to be reduced at all levels of the design -- from algorithm to architecture to circuit to logic to technology. However, the largest power savings are obtained at the highest levels, namely, the systems and the algorithm level. An important technique in algorithmic level power reduction is to use the data characteristics to simplify the algorithm (thereby reducing the power consumption). In this project, we apply the data-dependent technique on a large class of algorithms including DCT, IDCT in image processing, and Viterbi decoding, Turbo decoding and Turbo based space-time decoding in communication systems. For instance, while decoding convolutional codes using the Viterbi algorithm, we have shown how significant energy reduction (70-90%) can be achieved by exploiting real-time variation in system characteristics. The proposed approach adaptively approximates the Viterbi decoding by varying the truncation length and pruning threshold of the T-algorithm while employing trace-back memory management according to variations in SNR, code rate and maximum acceptable BER. Similarly, for the Turbo decoder we found that a judicious use of approximations on the log-MAP algorithm can be used to achieve more than 50% energy savings at a BER=10e-5 with less than a 1dB loss in SNR on a general purpose (superscalar) processor. More recently, we have developed energy-efficient video transmission schemes that reduce the front-end energy of wireless devices by controlling physical layer parameters given link layer specifications.

A Quality-Energy Tradeoff Approach for IDCT Computation in MPEG-2 Video Decoding
R. Henning and C. Chakrabarti
Proc. of IEEE Workshop on Signal Processing Systems, 2000.

---

System-level Design with Emerging Memory Technologies

A Multi-tiered Approach to Improving the Reliability of Multi-level Cell PRAM
C. Yang, Y. Emre, Y. Cao and C. Chakrabarti
Proc. of the IEEE Workshop on Signal Processing Systems, Oct 2012.

---

Reliable Memory System Design

Energy-aware Error Control Coding for Flash Memories
V. Papirla and C. Chakrabarti.
Proc. of the IEEE/ACM Design Automation Conference, July 2008.

---

Memory Design

In systems that involve multidimensional streams of signals such as images or video sequences, it has been shown that the majority of the power cost is not due to the datapath or controllers, but due to memory interactions. This implies that with proper design, reduction in the memory related power budget can far exceed the reduction due to voltage scaling and other popular power saving transformations. In the area of memory management for data-dominated applications, we have demonstrated the necessity of including energy in the performance metrics of a memory exploration procedure. The necessity arises from the fact that the variation in the number of processor cycles is quite different from the variation in the energy consumption for different cache configurations. We have also looked at developing architectural and circuit-level strategies to reduce leakage power consumption in direct mapped and set associative caches. More recently we have focused on low power techniques to correct or compensate for errors in memories. Specifically, we have been working on developing algorithm-specific techniques that have very low overhead and perform better than traditional ECC techniques for medium to high error rates.

An Efficient Control Point Insertion Technique for Leakage Reduction of Scaled CMOS Circuits
H. Rahman and C. Chakrabarti.
IEEE Trans on Circuits and Systems II, Aug 2005.

---

Energy-Efficient Task Scheduling

In this work we focus on task scheduling algorithms for DVS processor based systems. First we derive algorithms to minimize energy or minimize peak power of the CPU given the task specifications (arrival times, deadline times, execution times, periods) and dependencies. We use the Lagrange multiplier method to theoretically determine the relation between the task voltages such that the energy or power is minimum, and then develop an iterative algorithm that tries to satisfy the relation. We show experimentally (random experiments as well as real-life cases), that the voltage assignment obtained by the proposed low complexity algorithm is very close to that of the optimal energy (0.1\% error) and optimal peak power (1\% error) assignment. Next we design dynamic task scheduling algorithms that minimize the system-level energy (defined by CPU energy + device energy). These algorithms utilize the concepts of optimal scaling factor which minimizes the system-level energy, and dynamic speed setting which is based on processor utilization and remaining workload estimation. We have also developed task scheduling algorithms for battery-operated systems. The important design metric here is maximization of battery lifetime or maximization of battery residual charge. Since the battery lifetime is directly dependent on the battery discharge profile, our approach to lifetime maximization is based on shaping the profile of the load current.

Voltage Scaling for Energy Minimization with QoS Constraints
A. Manzak and C. Chakrabarti
Proc. of International Conference on Computer Design, 2001.

---

Task Scheduling for Fuel Cell-Battery Hybrid Systems

The energy consumption of many embedded systems used in portable applications has increased significantly in the last decade. As a result, there is a steady demand for a power supply that has higher energy density. Fuel cell (FC) is a viable power source that is clean and has significantly higher energy density compared to batteries. Since FCs cannot follow the rapid change in the power demand of an embedded system, we consider an FC-battery hybrid source in which the FC provides the steady power and the battery follows the variation in the load power. The optimization metric here is minimization of the fuel consumption and not just energy minimization of the embedded system. The optimization framework is utilized to develop FC-aware task scheduling algorithms for embedded systems that consist of DVS and DPM-enabled components.

Extending the LIfetime of Fuel Cell Based Hybrid Systems
J. Zhuo, C. Chakrabarti, N. Chang and S. Vrudhula.
Proc. of the Design Automation Conference, July 2006.

---

Thermal-Aware Design

An Optimal Analytical Solution for Processor Speed Control with Thermal Constraints
R. Rao, S. Vrudhula, C. Chakrabarti and N. Chang.
Proc. of the Int. Symp. on Low Power Electronics and Design, Oct 2006.

---

Energy-Efficient Compilation

An ever-increasing portion of the functionality of today's system is in the form of software. So in order to develop efficient low power systems, it is imperative that the power cost due to the software component be minimized as well. Our aim in this project is to develop compilers that generate low energy machine code without sacrificing performance. We consider processors that support packing (ie., execution of multiple instructions in a single cycle). Our approach is to (i) increase the number of `packed' instructions and (ii) to minimize the number of additional address instructions during address code generation. More recently, we have looked at developing dataflow language extensions for streaming systems such as software defined radio.

Instruction-level power model of microcontrollers
C. Chakrabarti and D. Gaitonde
Proc. of the International Symposium on Circuits and Systems, 1999

---

High Level Synthesis for Low Power

In scheduling and allocation of the datapath, we have shown how significant power savings can be obtained by using resources that operate at multiple voltages and by exploiting correlation in the data. The latency-constrained, resource-constrained, and latency and resource constrained algorithms that we developed all have polynomial time complexity and produce results comparable to the ones produced by ILP and dynamic programming. In order to exploit the correlation in the data, we have developed a statistical model that relates data characteristics to the transition activity in the nodes of a CMOS circuit. The model is intuitive, easy to use and performs as well as the Dual Bit Type model. We have also demonstrated the effectiveness of this model in guiding scheduling and allocation during high level synthesis of a low power speech codec.

Scheduling for Minimizing the Number of Memory Accesses in Low Power Applications
R. Saied and C. Chakrabarti
Proc. of the VLSI Signal Processing Workshop, 1996

---

VLSI Implementations of Signal Processing and Communication Systems

Efficient Implementation of Neural Network Architectures

Efficient Function Evaluations with Lookup tables for Structured Matrix Operations
K. Sobti, L. Deng, C. Chakrabarti, N. Pitsianis, X. Sun, J. Kim, P. Mangalgiri, V. Narayanan and M. Kandemir.
Proc. of the IEEE Workshop on Design and Implementation of Signal Processing Systems, Oct 2007.

---

Architectures for Efficient Transform Computation

In this work, we developed specialized architectures for some important transforms, namely, the Discrete Cosine Transform (DCT), the Discrete Hartley Transform (DHT), the Discrete Wavelet Transform (DWT), and more recently, the Discrete Fourier Transform (DFT). We developed systolic array architectures for computing one-dimensional DHT and DCT over N points, when N is factorizable into mutually prime factors. The factorization resulted in the hardware requirements being significantly reduced. Next we, developed a family of optimal architectures with area-time trade-offs for the more general problem of computing any (NxNx ...xN) d-dimensional linear separable transform. In our work on architectures for the DWT, we showed that while the traditional Mallat's algorithm mapped well to a SIMD array of processors and processors with large on-chip memory, new on-line algorithms have to be developed for single chip implementations with limited memory. These on-line algorithms are based on interleaving computations of different octave outputs and allow the algorithm to be folded onto a simple architecture with limited memory, without sacrificing the throughput requirements. We also developed specialized architectures for forward and inverse wavelet transforms using a lifting based scheme for the seven filters proposed in JPEG 2000. Our work on DFT has been on developing architecture-aware algorithm transformations that enable efficient implementation. For instance, we have developed DFT decompositions that take into account the FPGA available resources and the characteristics of off-chip memory access, namely, the burst access pattern of SDRAM memories. The resulting implementation for multidimensional DFT can maintain the maximum memory bandwidth throughout the whole procesure while avoiding matrix transpose operations used in most other existing implementations.

VLSI architectures for Multidimensional Transforms
C. Chakrabarti and J. J\'{a}J\'{a}.
IEEE Transactions on Computers, pp. 1053-1057, Sep 1991.

---

Algorithms and Architectures for Statistical Signal Processing

Our work focuses on efficient implementation of sequential Monte Carlo techniques, such as particle filtering (PF), to estimate state-space parameters in applications such as those in localization and tracking, PF sequentially estimates the states of a dynamic system based on received noisy measurements and is computationally very intensive. We have shown how Sample-Importace-Resampling PF can be parallelized with no loss in algorithm performance thereby enabling PF to be used in real-time tracking. The proposed algorithm has been used to speed up computations in waveform agile sensing and a multiple PF version has been used to efficently track neural activity in brain.

Efficient Mapping of Advanced Signal Processing Algorithms on MultiprocessorArchitectures
B. Manjunath, A. Williams, C. Chakrabarti and A. Papandreou-Suppappola.
Proc. of the IEEE Workshop on Design and Implementation of Signal Processing Systems, Oct 2008.

---

Architectures for Image Processing

Our work in this area can be classified into specialized architectures for non-linear filters, Canny edge detector, deblocking filter, color interpolation filters and system-level architectures for JPEG 2000 and H.264/SVC. In our work on architectures for non-linear filters, we showed how the sample rate can be increased by block processing, pipelining in non-recursive sections, applying approximate look ahead techniques to enable pipelining in the recursive sections, and reducing the precision in the data path. Our study included rank order filters such as median filters, morphological filters and weighted order statistic filters. We also looked at algorithm modifications that enable parallelization of computationally-intensive filters such as Canny edge detectors and deblocking filters used in H.264. We developed a comprehensive architecture for JPEG2000 that consists of accelerators for computing the Discrete Wavelet Transform (DWT), Bit Plane Coding (BPC) and Binary Arithmetic Coding (BAC) along with interfacing memories and a global controller. The DWT accelerator implements the transform using a lifting-based scheme. The BPC accelerator operates on the wavelet coefficients, along the bit planes, to generate a context and data bit pair using the EBCOT algorithm. The BAC accelerator then operates on the context and data bit pair using the MQ coder algorithm. Our recent efforts have focused on developing ultra low power image processing systems. We developed a low power, variation-tolerant architecture for color interpolation filtering that is based on a novel design methodology that allows intelligent trade-offs between power, quality and error resiliency. We also developed an ultra low power wide SIMD architecture for digital cameras.

A Parallel Programmable Architecture for Linear and Nonlinear Filters
L. Lucke and C. Chakrabarti.
1995 IEEE Workshop on on Nonlinear Signal and Image Processing, pp. 891-894, 1995.

---

Architectures for Communication Applications

Our work has been geared towards development of high throughput and low power architectures for Viterbi decoders, Turbo decoders, LDPC decoder and sphere decoders. We have also shown how the decoding algorithms can be parallelized for efficient implementations onto multiprocessor architectures.

A New Architecture for the Viterbi Decoder for Code Rate k/n
H. Li and C. Chakrabarti.
IEEE Trans on Communications, pp. 158-164, Feb 1996.

---

Algorithms and Architectures for Motion Estimation

In this project our aim was to develop algorithms and architectures for motion estimation, and also to demonstrate that algorithm and architecture development have to occur in an interactive manner for large complex systems. We considered both pixel-domain and feature-domain algorithms. We showed how the same architecture can be used to implement a variety of pixel-domain block matching algorithms, including full-search, 3-step search and 2-level 3-step hierarchical search. This enables the encoder to choose the block matching algorithm that is best suited, given the image characteristics. The large number of computations in these pixel-domain algorithms prompted us to study feature-domain algorithms for motion estimation. We chose to represent the object by straight-line approximations of the boundary using the Hough transform and estimated the motion parameters from shifts in the theta-p space. Both the software and the hardware implementations were successfully tested for a large number of computer generated objects, including those with highly curved boundaries and partially overlapped objects.

Architectures for Hierarchical and Other Block Matching Algorithms
G. Gupta and C. Chakrabarti.
IEEE Transactions on Circuits and Systems for Video Technology, pp. 477-489, Dec 1995.

---

Algorithms and Architectures for Portable Ultrasound

Design of Orthogonal Coded Excitation for Synthetic Aperture Imaging in Ultrasound Systems
M. Yang and C. Chakrabarti.
Proc. of Int. Symp. on Circuits and Systems, May 2012.

---

Architectures for Bio-informatic Applications

Protein structure prediction is one of the core research areas in bio-informatics. This work is on development of specialized architectures to speed up PSIPRED based protein secondary structure prediction algorithm.