Evaluation of the SynDEx Software for Fast Prototyping of Image Processing Applications on a MIMD-DM Architecture
Évaluation de L'Outil SynDEx Envuede Prototypage Rapide D'Applications Detraitement D'Images sur Machine MIMD-DM
OPEN ACCESS
The goal of this paper is to evaluate the SynDEx system-level CAD tool in order to estimate its usefulness for fast prototyping of image processing applications on a MIMD-DM architecture. This software can assist the programmer during the implementation of image processing applications in his constrained search for an efficient matching between algorithm and architecture. Two main conclusions were drawn from this work. First, the implementation of a connected component labeling algorithm on a multitransputer architecture allowed us to quantify the gap between the estimated performances predicted by SynDEx and the effective performances measured on the generated executives . This gap- initially pointed out in the v3 release - is largely reduced in the v4. As part of this work, the v4 executive has been ported to T800 and T9000 targets. Second, the strong impact of the process granularity both on the easiness of the specification and the efficiency of the implementation has been evidenced. From a pragmatic point of view, this second conclusion clearly shows the advantages of a tool such as SynDEx, allowing to quickly evaluate these criterions at many granularity levels . From a more prospectivepoint of view, the formalisation of some recurrent graph transformation rules, appearing when searching an optimal granularity, led us to the concept of algorithmic skeletons.
Résumé
Cet article a pour objectif d'évaluer l'outil de distribution-ordonnancement statique SynDEx en vue d'estimer ses performances de prototypage rapide d'applications dans le domaine du traitement d'images à fortes contraintestemporelles sur une machine MIMD-MD. Les retombées de ce travail sont de plusieurs ordres. Premièrement, l'implantation d'un algorithme d'étiquetage en composantes connexes sur multi-transputer a permis de quantifier l'écart attendu entre prédictions de performances, calculées à partir du modèle d'exécutif de SynDEx, et mesures de performances, obtenues à partir des exécutifs générés par SynDEx . Cet écart- initialement observé avec la version v3 - est nettement réduit avec la version v4, dont l'exécutif a fait l'objet d'un portage sur Transputer dans le cadre de ce travail. Deuxièmement, il a été mis en évidencele rôle crucial joué par la granularité de traitement tant au niveau de la facilité d'expression des algorithmes que de l'efficacité des implantations résultantes. Cet aspect confirme l'intérêt d'un outil permettant d'évaluer rapidement ces critères pour plusieurs niveaux de granularité. D'un point de vue plus prospectif, la formalisation de certaines opérations de transformation de graphe associées à cette recherche d'une granularité optimale nous a d'ailleurs conduits à la notion de squelettes de parallélisation.
Image processing, parallelism, MIMD, SynDEx, granularity, algorithmic skeletons
Mots clés
Traitement d'images, parallélisme, MIMD, SynDEx, granularité, squelettes de parallélisation.
[1] M. Cole,Algorithmic skeletons :structured management of parallel computations, Pitman/MIT Press, 1989.
[2] R. Cypher and J.L.C. Sanz and L. Snyder, Algorithms for image componed labeling on SIMD mesh connected computers. In IEEE Trans. Computers, volume 32, Feb. 1990.
[3] J.P. Derutin and B. Besserer and J. Gallice, A parallel Vision Machine Transvision, Computer Architecture for Machine Perception - CAMP'91, pages 241-251, Paris Déc. 1991.
[4] M. Eccher,Architecture parallèle dédiée àl'étude d'automatesde vision en temps réel, PhD thesisUniversité de Franche Comté, Nov. 1992.
[5] F. Ennesser and C. Lavarenne and Y . Sorel, Méthode chronométrique pour l'optimisation du temps de réponse des exécutifs SynDEx, Rapport de recherche 1769, I.N.R.I.A.Institut National de Rechercheen Informatiqueet en Automatique, Octobre 1992.
[6] D. Ginhac, Spécification et implantation d'un algorithme flots de données d'Etiquetage en Composantes Connexes sur la machine multiprocesseurs à mémoire distribuée Transvision, Mémoire de DEA d'Electronique et Systèmes, Université BlaisePascal deClermont-Ferrand, juin 1995.
[7] P. Le Guernic and M.Le Borgneand T.Gautierand C.Le Maire,Programming real-time applications with Signal. Rapport de recherche 1446, LN.R.I.A. InstitutNational de Rechercheen Informatique et en Automatique, Juin 1991.
[8] H.T. Nguyen and K.K. Jung and R. Raghavan, Fast parallel algorithms : from images to level sets and labels, In Parallel Architectures forImage Processing, volume 1246, pages 162-176, 1990.
[9] S. Praud, Implantationd'un algorithme d'étiquetageencomposantes connexes sur le calculateur fonctionnel, Mémoire de DEA,Université ParisSudCentre d'Orsay, 1993.
[10] Selkow, One pass complexity analysis of digital picture properties . InJACM, S. volume 2, pages 283-295, Apr. 1972.
[11] D. Linhac and J. Serot and J.P Derutin, Utilisation desquelettes fonctionnels au sein d'un outil d'aide à la parallélisation, 4ème journées Adéquation Algorithme Architectureen Traitementdu Signal et des Images, Saclay, 28-30 Janvier 1998, pp. 43-51.
[12] Y. Sorel, Massively Parallel Systems with Real Time Constraints . The «Algorithm Architecture Adequation» Methodology. In Proc. Massively Parallel Computing Systems, IschiaItaly, may 1994.