Une méthode de conception d'algorithmes systoliques, résultats théoriques et réalisation
Identifieur interne : 000231 ( Crin/Curation ); précédent : 000230; suivant : 000232Une méthode de conception d'algorithmes systoliques, résultats théoriques et réalisation
Auteurs : C. MongenetSource :
English descriptors
Abstract
Le travail présenté dans cette thèse se situe dans le cadre de la conception d'algorithmes systoliques. Les architectures systoliques proposées par H.T. KUNG sont des systèmes spécialisés, caractérisés par une structure planaire régulière de processeurs élémentaires connectés localement, à travers lesquels circulent les données de facon rythmée. Ces caractéristiques facilitent leur réalisation par un circuit VLSI. La conception "à la main" de tels systèmes n'est pas simple. La méthode proposée répond à cette difficulté en déterminant automatiquement, à partir de l'énoncé d'un problème, un ensemble de réseaux systoliques, solutions de ce problème. Une architecture systolique est adaptée à la résolution de problèmes pouvant s'exprimer par des systèmes d'équations récurrentes. On peut, de manière simple, déduire de ces équations l'ensemble des informations constituant la "spécification systolique" du problème. Cette spécification sert de point de départ de la méthode. La méthode présentée dans cette thèse permet de déterminer\, : \begin{itemize} \item un ensemble de "représentations" - ou ordonnancements temporels des calculs élémentaires - obtenues par application de transformations affines, \item puis, pour chaque représentation, un ensemble de réseaux. Un tel réseau est obtenu en allouant (avec une fonction d'allocation) l'ensemble des calculs élémentaires à un ensemble fini de processeurs et en déterminant les connexions nécessaires. \end{itemize} Cette méthode est mise en œuvre dans un logiciel appelé SYSTOL, qui, à partir de la spécification systolique d'un problème, détermine un ensemble de réseaux et permet la simulation pas à pas de leur exécution. La structure de chaque réseau (processeurs et connexions) est visualisée sur un écran bitmap sous une forme schématique du type de celle présentée par KUNG\, : sa configuration initiale est définie par la disposition des données sur les flots d'entrée des boites représentant les processeurs. La simulation d'exécution est réalisée par la visualisation du déplacement pas à pas de ces données sur le graphe de connexions. Outre l'automatisation de la conception, le logiciel permet donc la sélection par l'utilisateur du "meilleur" réseau selon ses propres critères\, : nombre minimal de processeurs, temps minimal d'exécution, simplicité du graphe de connexion, taux de parallélisme, etc. Si cette méthode présente des points communs avec d'autres méthodes existantes, elle s'en distingue essentiellenent par le non-rejet systématique de la diffusion de données et par les outils utilisés pour définir l'ordonnancenent temporel des calculs élémentaires.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000231
Links to Exploration step
CRIN:mongenet85bLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="fr" wicri:score="-200">Une méthode de conception d'algorithmes systoliques, résultats théoriques et réalisation</title>
</titleStmt>
<publicationStmt><idno type="RBID">CRIN:mongenet85b</idno>
<date when="1985" year="1985">1985</date>
<idno type="wicri:Area/Crin/Corpus">000231</idno>
<idno type="wicri:Area/Crin/Curation">000231</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">000231</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="fr">Une méthode de conception d'algorithmes systoliques, résultats théoriques et réalisation</title>
<author><name sortKey="Mongenet, C" sort="Mongenet, C" uniqKey="Mongenet C" first="C." last="Mongenet">C. Mongenet</name>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>automated algorithm design</term>
<term>parallelism</term>
<term>specialised architectures</term>
<term>systolic networks</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="fr" wicri:score="-7215">Le travail présenté dans cette thèse se situe dans le cadre de la conception d'algorithmes systoliques. Les architectures systoliques proposées par H.T. KUNG sont des systèmes spécialisés, caractérisés par une structure planaire régulière de processeurs élémentaires connectés localement, à travers lesquels circulent les données de facon rythmée. Ces caractéristiques facilitent leur réalisation par un circuit VLSI. La conception "à la main" de tels systèmes n'est pas simple. La méthode proposée répond à cette difficulté en déterminant automatiquement, à partir de l'énoncé d'un problème, un ensemble de réseaux systoliques, solutions de ce problème. Une architecture systolique est adaptée à la résolution de problèmes pouvant s'exprimer par des systèmes d'équations récurrentes. On peut, de manière simple, déduire de ces équations l'ensemble des informations constituant la "spécification systolique" du problème. Cette spécification sert de point de départ de la méthode. La méthode présentée dans cette thèse permet de déterminer\, : \begin{itemize} \item un ensemble de "représentations" - ou ordonnancements temporels des calculs élémentaires - obtenues par application de transformations affines, \item puis, pour chaque représentation, un ensemble de réseaux. Un tel réseau est obtenu en allouant (avec une fonction d'allocation) l'ensemble des calculs élémentaires à un ensemble fini de processeurs et en déterminant les connexions nécessaires. \end{itemize} Cette méthode est mise en œuvre dans un logiciel appelé SYSTOL, qui, à partir de la spécification systolique d'un problème, détermine un ensemble de réseaux et permet la simulation pas à pas de leur exécution. La structure de chaque réseau (processeurs et connexions) est visualisée sur un écran bitmap sous une forme schématique du type de celle présentée par KUNG\, : sa configuration initiale est définie par la disposition des données sur les flots d'entrée des boites représentant les processeurs. La simulation d'exécution est réalisée par la visualisation du déplacement pas à pas de ces données sur le graphe de connexions. Outre l'automatisation de la conception, le logiciel permet donc la sélection par l'utilisateur du "meilleur" réseau selon ses propres critères\, : nombre minimal de processeurs, temps minimal d'exécution, simplicité du graphe de connexion, taux de parallélisme, etc. Si cette méthode présente des points communs avec d'autres méthodes existantes, elle s'en distingue essentiellenent par le non-rejet systématique de la diffusion de données et par les outils utilisés pour définir l'ordonnancenent temporel des calculs élémentaires.</div>
</front>
</TEI>
<BibTex type="phdthesis"><ref>mongenet85b</ref>
<crinnumber>85-T-067</crinnumber>
<category>9</category>
<equipe>INCONNUE</equipe>
<author><e>Mongenet, C.</e>
</author>
<title>Une méthode de conception d'algorithmes systoliques, résultats théoriques et réalisation</title>
<school>Inconnue</school>
<year>1985</year>
<address>Nancy</address>
<month>may</month>
<keywords><e>parallelism</e>
<e>specialised architectures</e>
<e>systolic networks</e>
<e>automated algorithm design</e>
</keywords>
<abstract>Le travail présenté dans cette thèse se situe dans le cadre de la conception d'algorithmes systoliques. Les architectures systoliques proposées par H.T. KUNG sont des systèmes spécialisés, caractérisés par une structure planaire régulière de processeurs élémentaires connectés localement, à travers lesquels circulent les données de facon rythmée. Ces caractéristiques facilitent leur réalisation par un circuit VLSI. La conception "à la main" de tels systèmes n'est pas simple. La méthode proposée répond à cette difficulté en déterminant automatiquement, à partir de l'énoncé d'un problème, un ensemble de réseaux systoliques, solutions de ce problème. Une architecture systolique est adaptée à la résolution de problèmes pouvant s'exprimer par des systèmes d'équations récurrentes. On peut, de manière simple, déduire de ces équations l'ensemble des informations constituant la "spécification systolique" du problème. Cette spécification sert de point de départ de la méthode. La méthode présentée dans cette thèse permet de déterminer\, : \begin{itemize} \item un ensemble de "représentations" - ou ordonnancements temporels des calculs élémentaires - obtenues par application de transformations affines, \item puis, pour chaque représentation, un ensemble de réseaux. Un tel réseau est obtenu en allouant (avec une fonction d'allocation) l'ensemble des calculs élémentaires à un ensemble fini de processeurs et en déterminant les connexions nécessaires. \end{itemize} Cette méthode est mise en œuvre dans un logiciel appelé SYSTOL, qui, à partir de la spécification systolique d'un problème, détermine un ensemble de réseaux et permet la simulation pas à pas de leur exécution. La structure de chaque réseau (processeurs et connexions) est visualisée sur un écran bitmap sous une forme schématique du type de celle présentée par KUNG\, : sa configuration initiale est définie par la disposition des données sur les flots d'entrée des boites représentant les processeurs. La simulation d'exécution est réalisée par la visualisation du déplacement pas à pas de ces données sur le graphe de connexions. Outre l'automatisation de la conception, le logiciel permet donc la sélection par l'utilisateur du "meilleur" réseau selon ses propres critères\, : nombre minimal de processeurs, temps minimal d'exécution, simplicité du graphe de connexion, taux de parallélisme, etc. Si cette méthode présente des points communs avec d'autres méthodes existantes, elle s'en distingue essentiellenent par le non-rejet systématique de la diffusion de données et par les outils utilisés pour définir l'ordonnancenent temporel des calculs élémentaires.</abstract>
</BibTex>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000231 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Curation/biblio.hfd -nk 000231 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Crin |étape= Curation |type= RBID |clé= CRIN:mongenet85b |texte= Une méthode de conception d'algorithmes systoliques, résultats théoriques et réalisation }}
This area was generated with Dilib version V0.6.33. |