PhD: Global Optimisation of DSP Application Mapping onto Parallel Architectures using Constraint Logic Programming

========================================================================


Global Optimisation of DSP Application Mapping onto Parallel
Architectures using Constraint Logic Programming


------------------------------------------------------------------------


The efficient use of parallel machines requires both a perfect
knowledge of the target architecture and the ability to find good
ressources allocation. Programming an application necessitates the
definition of a schedule ant the partitionning of the computation.
Those problems are known as NP-hard by scientific and are rarely
considered simultaneously.


Right now, the global problem is characterized by numerous ressources
(number of processors, bandwidth, memory size), real-time constraints
(latency, sampling) and many non-linear constraints. The research work,
carried out at the Corporate Research Laboratory of Thomson and at the
Centre de Recherches en Informatique de l'Ecole des Mines de Paris,
considers the applicative class of Digital Signal Processing. In that
context, the global mapping problem is decomposed in models and
relations, thus formalised using state-of-the-art technology of the
High Performance Computing domain.


Unlike integer linear programming or operational research approaches
the global modelisation and resolution relies on Constraint Logic
Programming. Given the kind of formalisms considered, its ability to
solve combinatorial problems and its capacity to compose several
concurrent models are essential. Global resolution strategies including
domain heuristics are designed to control and assist the search over
all models.


A prototype based on multi-models has been implemented. Beside the
automatic computation of global solutions, the different parameters of
the problem can be constrained or optimised (latency, architecture
cost, speed-up). The prototype is optimal on short examples and
efficient on real DSP applications (embedded radars, sonar systems,
...). In the last case, the prototype gives solutions equivalent to
those designed by hand by DSP experts.




Ecole des Mines de Paris
Boulevard Saint Michel, Paris
December, the 12 th 1997, 15h, room V334


For more information, send e-mail to :


guettier@cri.ensmp.fr
========================================================================


Optimisation globale du placement d'applications de traitement du
signal sur des architectures paralleles en utilisant la Programmation
Logique avec Contraintes.


L'exploitation des machines paralleles requiert non seulement une
parfaite connaissance de l'architecture ciblee, mais aussi l'emploi au
mieux du potentiel des ressources materielles. Programmer une
application necessite de definir finement le partitionnement et
l'ordonnancement des calculs, l'allocation, les communications de
donnees. Ces problemes de placement sont reconnus par les scientifiques
comme NP-difficiles et sont rarement consideres simultanement.


Or, le probleme global est caracterise par des ressources multiples
(nombre de processeurs, bande passante, memoire), des contraintes
temps-reel (latence, acquisition) et de nombreuses contraintes
non-lineaires. La these, menee conjointement au Laboratoire Central de
Recherches de Thomson-CSF et au Centre de Recherches en Informatique de
l'Ecole des Mines de Paris, considere la classe applicative du
traitement du signal numerique. Dans ce cadre, le probleme global du
placement est decompose en plusieurs modeles et relations, et
formalises en utilisant l'etat de l'art en matiere de calcul de hautes
performances.


Contrairement aux approches basees sur la programmation lineaire en
nombres entiers ou sur des techniques de recherche operationnelle, la
modelisation comme la resolution globale s'appuie sur la Programmation
Logique avec Contraintes. Celle-ci s'impose par la nature des
formalismes consideres, sa capacite a resoudre des problemes
combinatoires, enfin par son aptitude a combiner plusieurs modeles
concurrents. Des strategies globales de resolution incluant des
heuristiques de domaines coordonnent et supervisent la recherche de
solutions sur l'ensemble des modeles.


Un environnement permettant de prototyper la fonction
placement a partir de caracteristiques de l'architecture
materielle a ete concu. Outre le calcul automatique de solutions
globales, les differents parametres du probleme peuvent etre contraints
ou faire l'objet d'optimisations (latence, cout de l'architecture,
efficacite de la solution). Le prototype se revele optimal sur des cas
d'ecoles et efficace sur des applications reelles (radars embarques,
sonars, ...). Pour ces dernieres, le prototype produit des solutions
equivalentes a celles obtenues manuellement par les experts.


Ecole des Mines de Paris
Boulevard Saint Michel, Paris
le 12 Decembre 1997, 15h, salle V334


Pour plus d'informations envoyez un e-mail a :


guettier@cri.ensmp.fr
--

Return to the comp.compilers page.
Search the comp.compilers archives again.