Optimizing and Scheduling DSP Programs for High Performance VLSI Designs

Frederico Buchholz MACIEL; Yoshikazu MIYANAGA; Koji TOCHINAI

Optimizing and Scheduling DSP Programs for High Performance VLSI Designs

Frederico Buchholz MACIEL, Yoshikazu MIYANAGA, Koji TOCHINAI

Full Text Views

0

Cite this

Summary :

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 (T_i/D_i), where T_i and D_i 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 T_i'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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.10 pp.1191-1201

Publication Date: 1992/10/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

Category

Cite this

Copy

Frederico Buchholz MACIEL, Yoshikazu MIYANAGA, Koji TOCHINAI, "Optimizing and Scheduling DSP Programs for High Performance VLSI Designs" in IEICE TRANSACTIONS on Fundamentals, vol. E75-A, no. 10, pp. 1191-1201, October 1992, doi: .
Abstract: 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 (T_i/D_i), where T_i and D_i 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 T_i'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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e75-a_10_1191/_p

Copy

@ARTICLE{e75-a_10_1191,
author={Frederico Buchholz MACIEL, Yoshikazu MIYANAGA, Koji TOCHINAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Optimizing and Scheduling DSP Programs for High Performance VLSI Designs},
year={1992},
volume={E75-A},
number={10},
pages={1191-1201},
abstract={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 (T_i/D_i), where T_i and D_i 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 T_i'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.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Optimizing and Scheduling DSP Programs for High Performance VLSI Designs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1191
EP - 1201
AU - Frederico Buchholz MACIEL
AU - Yoshikazu MIYANAGA
AU - Koji TOCHINAI
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 1992
AB - 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 (T_i/D_i), where T_i and D_i 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 T_i'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.
ER -