Normal view MARC view ISBD view

Optimisation globale du placement d'applications de traitement du signal sur architectures parallèles en utilisant la programmation logique avec contraintes / Christophe Guettier ; sous la direction de François Irigoin

Auteur principal : Guettier, Christophe, 19..-...., InformaticienAuteur secondaire : : Irigoin, François, Directeur de thèseAuteur secondaire collectivité : École nationale supérieure des mines, Paris, Organisme de soutenance;Centre de recherche en informatique, Fontainebleau, Seine et Marne, Organisme de soutenancePublication : 1997Description : 1 vol. (330 p.) : ill. ; 30 cmClassification : 001.D.04.A.04.H ; 620Résumé : Le traitement du signal digital numérique exige dorénavant des machines parallèles spécialisées de hautes performances. Leur exploitation exige de la part des experts non seulement une parfaite connaissance de l'architecture mais aussi l'emploi au mieux du potentiel des ressources matérielles (taille mémoire, puissance de calcul, réseau de communications), tout en satisfaisant les contraintes temps-réels et de coût. Les performances sont donc difficiles à obtenir, de par la finesse et le nombre des optimisations à réaliser comme par la quantité et la diversité des contraintes à satisfaire. Bien connus des chercheurs, ces problèmes de placement ont fait l'objet de nombreuses techniques spécifiques : partitionnement, alignement ou ordonnancement. Selon les approches, la résolution automatique tient compte de manière indépendante, soit de l'allocation des données, soit des communications, soit des paramètres temps-réels. Cependant, la résolution s'avère dans la plupart des cas np-difficile et les techniques n'adressent qu'une partie du problème général. aborder globalement le problème du placement automatique revient à considérer simultanément les différents formalismes sous-jacents aux techniques mentionnées ci-dessus. Le problème général est décomposé en différents modèles (partitionnement, ordonnancement, alignement, communications, architecture, allocation mémoire), chacun d'eux disposant d'une combinatoire propre. La programmation logique par contraintes (PLC) s'impose alors de par la nature des formalismes considérés, par sa capacité à résoudre des problèmes combinatoires, enfin par son aptitude à supporter des modèles concurrents. Nous montrons sous quelles conditions chaque modèle peut-être raffiné et exprimé en PLC à partir des formalismes issus de l'état de l'art en calcul de haute performance. De plus, il est nécessaire de garantir la coopération et la concurrence entre les modèles pour obtenir une solution globale cohérente. Pour cela, les contraintes non-linéaires formalisant les relations entre les différents modèles sont mises en évidences. Des stratégies globales, combinées à différentes heuristiques, coordonnent et supervisent la recherche de solutions sur l'ensemble des modèles. Un prototype de placement a été réalisé qui exploite la modélisation multiple. Outre le calcul automatique de solutions, il permet l'optimisation de paramètres-clefs comme la latence, le coût de l'architecture ou bien l’efficacité du placement tout en considérant les contraintes de ressources (mémoires, processus, bande passante). Le prototype se révèle optimal sur des cas d’écoles et efficace sur des applications réelles. Ces dernières optimisations fournissent des solutions équivalentes à celles obtenues manuellement par les experts en traitement du signal.; The efficient use of parallel machines requires both a perfect knowledge of the target architecture and the ability to find good ressourcdes allocation. Programming an applictaion necessitates the definition of a schedule and 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 resources (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 bu hand by DSP experts..Bibliographie: Bibliogr. p. [320-327], 134 réf..Thèse : .Sujet - Nom d'actualité : Temps réel (informatique) -- Thèses et écrits académiques ;Programmation logique -- Thèses et écrits académiques ;Traitement du signal -- Thèses et écrits académiques Sujet : TEMPS REEL ;PARTITIONNEMENT ;ORDONNANCEMENT ;PROGRAMMATION LOGIQUE ;COMPILATION ;Traitement signal ;Configuration parallèle ;Calcul parallèle ;Programmation logique ;Traitement du signal Sujet Catégorie : H-LOGICIEL
Current location Call number Status Date due Barcode
Bib. Paris
EMP 146.211 CCL.TH.887 En numérisation EMP54382D
Bib. Paris
EMP 146.212 CCL.TH.887 Available EMP54383D
Centre de recherche en informatique
EM AI CI200-2379 Sur demande CRI03572D

Bibliogr. p. [320-327], 134 réf.

Thèse de doctorat Informatique Temps Réel, Robotique et Automatique ENSMP 1997

Le traitement du signal digital numérique exige dorénavant des machines parallèles spécialisées de hautes performances. Leur exploitation exige de la part des experts non seulement une parfaite connaissance de l'architecture mais aussi l'emploi au mieux du potentiel des ressources matérielles (taille mémoire, puissance de calcul, réseau de communications), tout en satisfaisant les contraintes temps-réels et de coût. Les performances sont donc difficiles à obtenir, de par la finesse et le nombre des optimisations à réaliser comme par la quantité et la diversité des contraintes à satisfaire. Bien connus des chercheurs, ces problèmes de placement ont fait l'objet de nombreuses techniques spécifiques : partitionnement, alignement ou ordonnancement. Selon les approches, la résolution automatique tient compte de manière indépendante, soit de l'allocation des données, soit des communications, soit des paramètres temps-réels. Cependant, la résolution s'avère dans la plupart des cas np-difficile et les techniques n'adressent qu'une partie du problème général. aborder globalement le problème du placement automatique revient à considérer simultanément les différents formalismes sous-jacents aux techniques mentionnées ci-dessus. Le problème général est décomposé en différents modèles (partitionnement, ordonnancement, alignement, communications, architecture, allocation mémoire), chacun d'eux disposant d'une combinatoire propre. La programmation logique par contraintes (PLC) s'impose alors de par la nature des formalismes considérés, par sa capacité à résoudre des problèmes combinatoires, enfin par son aptitude à supporter des modèles concurrents. Nous montrons sous quelles conditions chaque modèle peut-être raffiné et exprimé en PLC à partir des formalismes issus de l'état de l'art en calcul de haute performance. De plus, il est nécessaire de garantir la coopération et la concurrence entre les modèles pour obtenir une solution globale cohérente. Pour cela, les contraintes non-linéaires formalisant les relations entre les différents modèles sont mises en évidences. Des stratégies globales, combinées à différentes heuristiques, coordonnent et supervisent la recherche de solutions sur l'ensemble des modèles. Un prototype de placement a été réalisé qui exploite la modélisation multiple. Outre le calcul automatique de solutions, il permet l'optimisation de paramètres-clefs comme la latence, le coût de l'architecture ou bien l’efficacité du placement tout en considérant les contraintes de ressources (mémoires, processus, bande passante). Le prototype se révèle optimal sur des cas d’écoles et efficace sur des applications réelles. Ces dernières optimisations fournissent des solutions équivalentes à celles obtenues manuellement par les experts en traitement du signal.

The efficient use of parallel machines requires both a perfect knowledge of the target architecture and the ability to find good ressourcdes allocation. Programming an applictaion necessitates the definition of a schedule and 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 resources (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 bu hand by DSP experts.

Powered by Koha