Optimizing and Scheduling DSP Programs for High Performance VLSI Designs

Frederico Buchholz MACIEL  Yoshikazu MIYANAGA  Koji TOCHINAI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E75-A   No.10   pp.1191-1201
Publication Date: 1992/10/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
high-level synthesis,  optimization,  retiming,  iteration bound,  scheduling,  

Full Text: PDF>>
Buy this Article

The throughput of a parallel execution of a Digital Signal Processing (DSP) algorithm is limited by the iteration bound, which is the minimum period between the start of consecutive iterations. It is given by T=max (Ti/Di), where Ti and Di are the total time of operations and the number of delays in loop i, respectively. A schedule is said rate-optimal if its iteration period is T. The throughput of a DSP algorithm execution can be increased by reducing the Ti's, which can be done by taking as many operations as possible out of loops without changing the semantic of the calculation. This paper presents an optimization technique, called Loop Shrinking, which reduces the iteration bound this way by using commutativity, associativity and distributivity. Also, this paper presents a scheduling method, called Period-Driven Scheduling, which gives rate-optimal schedules more efficiently than existing approaches. An implementation of both is then presented for a system in development by the authors. The system shows reduction in the iteration bound near or equal to careful hand-tunning, and hardware-optimal designs in most of the cases.