Design Methodologies
for Signal Processing
Our research in design
methodologies for signal and image processing is concerned with development
of algorithms and design tools for rapid prototyping of these algorithms
using either dedicated VLSI chips or commercially available programmable
digital signal processors or using field-programmable systems.
We have addressed different
implementation styles for dedicated VLSI implementation of signal processing
algorithms. In particular, we proposed a systematic unfolding technique
to implement digit-serial architectures. Our technique can unfold
any bit-serial architecture to a digit-serial architecture in a systematic
way. Previous adhoc approaches limited the digit-size to be a divisor
of word-length. Our technique accommodates arbitrary digit sizes. Our technique
also accommodates multiple rate signal processing algorithms, such as interpolation
and decimation. We have also proposed folding techniques to design
bit-serial architectures from digit-serial or bit-parallel, and to design
digit-serial architectures from bit-parallel ones. The digit-serial circuits
designed by unfolding or folding cannot be pipelined at sub-digit levels.
To this end, novel digit-serial circuits have been developed which can
be pipelined at sub-digit levels.
The folding technique
is the reverse of the unfolding technique. The folding technique automatically
pipelines and retimes the architecture for folding, and then performs folding.
The folding technique has been extended to multirate and multi-dimensional
cases also. In this context, an approach to two-dimensional retiming has
also been developed.
In hardware system
prototyping, we are concerned with high-level hardware synthesis of specified
algorithms for specified sample rate constraints, with the objective of
minimizing the number of functional units (such as adders, multipliers,
latches, buses, and interconnections etc.). We have developed the MARS
(Minnesota ARchitecture Synthesis) system for hardware synthesis of signal
processing problems. The MARS system makes use of a novel concurrent loop
scheduling and resource allocation technique. In addition, MARS reduces
the cost of synthesized architecture by accommodating heterogeneous functional
types. We have also addressed systematic pipelining, retiming, and unfolding
of data-flow graphs for unraveling the hidden concurrency in algorithms.
We have also addressed scheduling and resource allocation for fixed multiprocessor
architectures for software system prototyping of signal processing problems.
In the context of register minimization, we have proposed life time
analysis techniques to minimize the number of registers in a data path.
We have used this technique to design speech and video data format converter
architectures using minimum number of registers. The life time analysis
technique can calculate closed form expressions for the minimum number
of registers needed for a converter. We have proposed forward-backward
register allocation scheme for area-efficient design of converter architectures
using minimum number of registers.
We have also proposed
optimal synthesis approaches using integer linear programming which peforms
synthesis to minimize the total cost of the system in a heterogeneous synthesis
environment where some processors could be implemented in bit-serial while
others may be implemented in bit-parallel or digit-serial. This model minimizes
the cost of data format converters and includes the effect of the latency
of these converters on system iteration period. This is the first approach
for generalized synthesis of DSP systems using an optimal approach. The
MARS system work has also been extended to handle heterogeneous implementation
styles.
In the area of fundamental
algorithm performance, we have proposed a new algorithm for faster determination
of the iteration bound in recursive loops.
In the area of testing,
we have examined C-testing of carry-free dividers. Previous C-testing of
dividers only considered carry-ripple dividers.
Selected
Publications
-
R.I. Hartley, and K.K.
Parhi, Digit-Serial Computation, Kluwer Academic Publishers, 1995
-
K.K. Parhi, VLSI Digital
Signal Processing Systems: Design and Implementation, Wiley, NY 1999
-
K.K. Parhi, and D.G. Messerschmitt,
"Static Rate-Optimal Scheduling of Iterative Data Flow Programs via Optimum
Unfolding", IEEE Trans. on Computers, Vol. 40(2), February
1991, pp. 178-195.
-
K.K. Parhi, "A
Systematic Approach for Design of Digit-Serial Signal Processing Architectures",
IEEE Trans. on Circuits and Systems, Vol. 38, No. 4, April
1991, pp. 358-375
-
K.K. Parhi, C.Y.
Wang, A.P. Brown, "Synthesis of Control Circuits in Folded Pipelined DSP
Architectures", IEEE Journal of Solid State Circuits, Vol. 27,
No. 1, January 1992, pp. 29-43
-
K.K. Parhi, "Video Data
Format Converters Using Minimum Number of Registers", IEEE Transactions
on Circuits and Systems For Video Technology, Vol. 2, No. 2,
June 1992, pp. 255-267.
-
K.K. Parhi, "Systematic
Synthesis of DSP Data Format Converters using Life-Time Analysis and Forward-Backward
Register Allocation", IEEE Trans. on Circuits and Systems, Part II:
Analog and Digital Signal Processing, Vol. 39, No. 7, July 1992,
pp. 423-440.
-
L.E. Lucke, and K.K. Parhi,
"Data-Flow Transformations for Critical Path Time Reduction For High-Level
DSP Synthesis", IEEE Transactions on Computer Aided Design of Integrated
Circuits And Systems, 12(7), July 1993, pp. 1063-1068.
-
K.K. Parhi, "Calculation
of Minimum Number of Registers in Arbitrary Life Time Chart", IEEE Circuits
and Systems Transactions - Part II: Analog and Digital Signal Processing,
41(6), pp. 434-436, June 1994.
-
H.R. Srinivas, B. Vinnakota,
and K.K. Parhi, "A C-Testable Carry-Free Divider", IEEE Trans. on VLSI
Systems, 2(4), December 1994.
-
K.K. Parhi, "High-Level
Algorithm and Architecture Transformations for DSP Synthesis", Journal
of VLSI Signal Processing, 9(1), pp. 121-143, Jan. 1995.
-
C.-Y. Wang, and K.K. Parhi,
"High-Level DSP Synthesis using Concurrent Transformations, Scheduling,
and Allocation", IEEE Transactions on Computer Aided Design, 14(3),
pp. 274-295, March 1995.
-
C.-Y. Wang, and K.K. Parhi,
"Resource Constrained Loop List Scheduler for DSP Algorithms", Journal
of VLSI Signal Processing, 11(1/2), pp. 75--96 October 1995.
-
K.
Ito and K.K. Parhi, "Determining the Minimum Iteration Period of an Algorithm",
Journal of VLSI Signal Processing, 11(3), pp. 229-244, December
1995
-
T.C.
Denk and K.K. Parhi, "Lower Bounds on Memory Requirements for Statically
Scheduled DSP Programs", Journal of VLSI Signal Processing, 12(3),
pp. 247-264. June 1996
-
K.
Ito and K.K. Parhi, "A Generalized Technique for Register Counting and
its Application to Cost-Optimal DSP Architecture Synthesis", Journal
of VLSI Signal Processing, 16(1), pp. 57-72, May 1997
-
M.
Majumdar and K.K. Parhi, "Synthesis of Low-Area Data Format Converters",
IEEE Trans. on Circuits and Systems, Part II: Analog and Digital Signal
Processing, 45(4), pp. 504-508, April 1998
-
T.C.
Denk and K.K. Parhi, "Exhaustive Scheduling and Retiming of Digital Signal
Processing Systems", IEEE Trans. on Circuits and Systems, Part II: Analog
and Digital Signal Processing, 45(7), pp. 821-838, July 1998
-
Y.-N.
Chang, C.Y. Wang, and K.K. Parhi, "Loop-List Allocation and Scheduling
with using Heterogene ous Functional Units", Journal of VLSI Signal
Processing,19(3), pp. 243-256, Aug. 1998
-
K.
Ito, L.E. Lucke and K.K. Parhi, "ILP Based Cost-Optimal DSP Synthesis with
Module Selection and Data Format Conversion", IEEE Trans. on VLSI Systems,
6(4), pp. 582-594, Dec. 1998
-
T.C.
Denk and K.K. Parhi, "Synthesis of Folded Pipelined Architectures for Multirate
DSP Algorithms", IEEE Trans. on VLSI Systems, 6(4),
pp. 595-607, Dec.98
-
Y.-N.
Chang, J.H. Satyanarayana and K.K. Parhi, "Systematic Design of High-Speed
and Low-Power Digit-Serial Multipliers", Submitted to IEEE Trans. on
Circuits and Systems, Part II: Analog and Digital Signal Processing,
to appear
-
T.C.
Denk and K.K. Parhi, "Two-Dimensional Retiming", IEEE Trans. on VLSI
Systems, to appear March 1999
-
V. Sundararajan and K.K.
Parhi, "Synthesis of Folded, Pipelined Architectures for Multi-Dimensional
Multirate Systems", in Proc. of IEEE Int. Conf. on Acoustics, Speech
and Signal Processing , pp. 3089-3092, May 1998, Seattle
-
V. Sundararajan and K.K.
Parhi, "Synthesis of Folded Multi-Dimensional DSP Systems", Proc. of
IEEE Int. Symp. on Circuits and Systems , pp. II-433-II-436, Monterey,
May 31 - June 3, 1998
[Bac
k page] [Prof.
Parhi's homepage]