Adéquation d'un algorithme à une architecture, application à la transformée de Fourier

Adéquation d'un algorithme à une architecture, application à la transformée de Fourier

Adequacy of an Algorithm to an Architecture, an Application to the Fast Fourier Transform

Jean-Luc Philippe Olivier Sentieys  Eric Martin  Hélène Dubois 

LASTI–ENSSAT, Université de Rennes, 6, rue de Kérampont F-22300 Lannion

LESTER – UBS – 10, rue Jean Zay, F-56100 Lorient

Page: 
335-350
|
Received: 
5 January 1996
| |
Accepted: 
N/A
| | Citation

OPEN ACCESS

Abstract: 

The characteristics of the target architecture are very often taken into account late, at the time of the implementation step of a signal processing application design flow. Furthermore, the target architecture and the constraints may be time evolving, making the adequacy between architecture and algorithm, more and more difficult . In this paper, we propose a methodology that aims to guide algorithmic transformations by computing some metrics, thus improving the adequacy . The approach will be explained on a compute bound algorithm . The results are based on MIMD architecture, and heterogeneous architecture by the use of Asic.

Résumé

La prise en compte des caractéristiques de l'architecture cible est souvent effectuée tardivement lors du développement d'un algorithme de TDSI . De plus, la nature de l'architecture ainsi que la nature des contraintes liées à l'application pouvant varier au cours du temps, la difficulté de la maîtrise de cette interaction entre architecture et algorithme s'en trouve largement accrue. Nous proposons dans cet article, une formalisation de la démarche de conception qui permet de manière interactive, par le calcul de métriques, de guider les transformations à opérer sur un algorithme afin d'optimiser son adéquation à une architecture . La démarche sera exposée pour un algorithme orienté traitement, et une architecture comprenant des processeurs programmables auxquels seront associés, selon les besoins, des circuits dédiés.

Keywords: 

Heterogeneous architecture, Design cycle, Efficiency, FFT, Multiprocessor, High level synthesis, Transformations

Mots clés

Architecture hétérogène, Cycle de conception, Efficacité, FFT, multiprocesseur, Synthèse architecturale, Transformations

1. Introduction : CAO D'architectures Et Traitement Du Signal
2. Cycle De Conception
3. La Transformée de Fourier Rapide (TFR)
4. Analyse De Performances D'une Architecture Multiprocesseur
5. Application Des Transformations Lors De L'analyse
6. Migrations De Fonctions Vers Le Matériel
7. Conclusion
  References

[1] D. Gajsky & R . Kuhn, «New VLSI Tools », Guest Editors' Introduction, IEEE Computer, Vol . 6, n°12, Dec 1983, pp . 11—14 .

[2] P. Mitchel, U . Lauther, P. Duzy, The synthesis approach to digital design , Kluwr Academics 1992 .

[3] M . Potkonjak and J . Rabaey, «Optimizing Ressource Utilization Using Transformations », IEEE transactions on C .A .D. of LC., vol . 13, n°3, Mar. 94 .

[4] P. Marwedel, G . Goosens, Code generation for embedded processors, Kluwer Academic Publishers, 1995 .

[5] E . Martin, J .L . Philippe, H . Dubois « GAUT : An architectural synthesis tool for dedicated signal processor », EURODAC93, 20—24 septembre 1993 , Hambourg.

[6] J.Ph. Diguet, O. Sentieys, J.L . Philippe, E. Martin, «Probabilistic Resource Estimation for Pipeline Architectures under Latency Constraint », IEEE Workshop on VLSI Signal Processing, Japon .

[7] J. Rabaey, M . Pedram Schafer, Low power design methodologies, Kluwer Academic Publishers 1995 .

[8] C.C. Leiserson, F.M . Rose, J .B . Saxe, « Optimizing synchronous system » , 22''ß d Ann . Symp. on Foundations of computer science, 1981, pp. 23—36.

[9] D.A. Lobo, B .M . Pangrle, «Generating pipelined datapaths using reduction techniques to shorten critical paths », EDAC 92, pp . 390—395 .

[10] K.K Pahri, D.G . Messerschmitt, «Pipeline interleaving and parallelism in recursive digital filters—Part 1: Pipelining using scattered look—ahead and decomposition », IEEE trans. on CAD, vol. 37, N°7, july 89, pp. 1099—1117.

[11] K.K Pahri, D.G . Messerschmitt, « Pipeline interleaving and parallelism in recursive digital filters—Part 2 : Pipelined incremental block filtering », IEEE trans. on CAD, vol . 37, N°7, july 89, pp . 1118—1134 .

[12] Numero spécial, « Algorithmes adaptatifs et soustraction de bruit », Revue Traitement du Signal, vol . 6, n°5, 1989 .

[13] A. Gilloire, « Adéquation Algorithmes Architectures : Apllications en annulation d'écho acoustique », Conférence AAA, Lannion, 14—15 sept. 1992 .

[14] J .W. Cooley & J .W. Tuckey, «An Algorithm for the machine calculation of Complex Fourier Series », Mathematics of Computation , Vol . 15, N°9, April 1965, pp. 297—301 .

[15] O . Sentieys, E. Martin, H . Dubois, J .L . Philippe & M . Corazza, « Application de l'outil ESPION pour l'analyse des architectures multiprocesseurs au filtrage de Kalman 2—D rapide », Revue Traitement du Signal, Vol . 10, N°1 , ler trimestre 1993 .

[16] O . Sentieys, Analyse et synthèse d'architectures en TDSI : vers la conception d'architectures hétérogènes, Thèse Université de Rennes 1993 .

[17] A .V. Oppenheim & R .W. Schafer, Digital Signal Processing, Prentice—Hall , 1975 .

[18] M . Kunt, « Traitement numérique des signaux », Editions presses polytechniques romandes, Dunod . 1981 .

[19] H . De Man, « Silicon Compilation for real Time Signal Processing systems Tutorial on high Level Synthesis », EDAC, Glasgow 12—15 mars 1991 .

[20] J .L . Philippe, D . Chillet, O. Sentieys, « Memory aspect in signal processing and HLS tool : some results », EUSIPCO 1996 .

[21] J.L. Philippe, O . Sentieys, J .P. Diguet, E . Martin, « Synthesis : from digital signal processing to layout », Logic and architecture synthesis state of the art and novel approaches Chapman and Hall, 1995, pp . 307—313 .