Prototypage rapide d'applications parallèles de vision artificielle par squelettes fonctionnels

We present SKiPPER, a software dedicated to the fast prototyping of vision algorithms on MIMD/DM platforms. This software is based upon the concept of algorithmic skeletons, i.e. higher order program constructs encapsulating recurring forms of parallel computations and hiding their low-level implementation details. Examples of such skeletons in low- to mid-level image processing include such as geometric decompositions, data or task farming. Each skeleton is given an architecture-independant functional (but executable) specification, a portable implementation as a process template and an analytic performance model. The source program is a purely functional specification of the algorithm in which all parallelism is made explicit be means of composing instances of selected skeletons, each instance taking as parameters user-specific sequential functions written in C. This specification is turned into a process graph in which nodes correspond to sequential functions and/or skeleton control processes and edges to communications. This graph is mapped onto the actual physical topology using a third-party CAD software (SynDEx). The result is a dead-lock free, optimized (but still portable) distributed executive which can be run straightly on the target platform. The initial specification, written in ML language, can also be executed on any sequential platform to check the correctness of the parallel algorithm and to predict performances. In that case, the applicative semantics of skeletons guarantees the equivalence between sequential and parallel results. The applicability of SkiPPER concepts and tools has been assessed by parallelizing several realistic real-time vision applications both on a multi-DSP platform and a network of workstations (connected component labeling, road tracking algorithm based upon marking detection). This experiment showed a dramatic reduction in development times (hence the term fast prototyping) with measured performances staying on the on the par with those obtained with hand-crafted parallel versions.Les travaux présentés dans ce mémoire s'inscrivent dans la problématique dite d'adéquation algorithme architecture. Ils concernent la conception et le développement d'outils logiciels permettant de faire du prototypage rapide d'applications parallèles de vision artificielle sur des architectures de type MIMD à mémoire distribuée. De tels outils ont pour objectif de faciliter l'évaluation rapide d'un ensemble de solutions vis à vis d'un problème donné en diminuant de manière drastique les temps de cycle conception-implantation-validation des applications. L'outil SKiPPER développé dans le cadre de ces travaux est basé sur le concept des squelettes de parallélisation. Ceux-ci représentent des constructeurs génériques de haut niveau encapsulant des formes communes de parallélisme tout en dissimulant les détails relatifs à l'exploitation de ce parallélisme sur la plate-forme cible. Au niveau langage, la spécification des squelettes est réalisée au sein du langage fonctionnel Caml sous la forme de fonctions d'ordre supérieur. Ainsi, la spécification d'une application est un programme purement fonctionnel dans lequel l'expression du parallélisme est limitée au choix et à l'instanciation des squelettes choisis dans une base pré-définie. L'environnement de développement SKiPPER est organisé autour de trois modules réalisant respectivement l'expansion du code fonctionnel en un graphe flot de données (outil Dromadaire), le placement-ordonnancement de ce graphe sur l'architecture matérielle (outil SynDEx développé à l'INRIA) et la génération de code cible final pour l'architecture cible (la machine Transvision du LASMEA dans notre cas). L'applicabilité des concepts mis en \oe uvre dans SKiPPER et des outils développés conjointement est démontrée également dans les travaux présentés dans ce mémoire. Diverses applications de complexité réaliste (étiquetage en composantes connexes, détection et suivi de signalisation horizontale autoroutière) ont été parallélisées automatiquement par l'environnement SKiPPER validant ainsi l'objectif initial de prototypage rapide d'applications parallèles de vision artificielle à fortes contraintes temporelles sur architecture dédiée