6533b852fe1ef96bd12ab36e

RESEARCH PRODUCT

Fast prototyping of parallel image processing applications using functional skeletons

subject

description

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.