Compact DAG representation and its dynamic scheduling
Identifieur interne : 000A98 ( PascalFrancis/Checkpoint ); précédent : 000A97; suivant : 000A99Compact DAG representation and its dynamic scheduling
Auteurs : M. Cosnard [France] ; E. Jeannot [France]Source :
- Journal of parallel and distributed computing [ 0743-7315 ] ; 1999.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
Scheduling large task graphs is an important issue in parallel computing. In this paper we tackle the two following problems: (1) how to schedule a task graph, when it is too large to fit into memory? (2) How to build a generic program such that parameter values of a task graph can be given at run-time? Our answers feature the parameterized task graph (PTG), which is a symbolic representation of the task graph. We propose a dynamic scheduling algorithm which takes a PTG as an entry and allows us to generate a generic program. We present a theoretical study which shows that our algorithm finds good schedules for coarse-grain task graphs, has a low memory cost, and a low computational complexity. When the average number of operations of each task is large enough, we prove that the scheduling overhead is negligible with respect to the makespan. We also provide experimental results that demonstrate the feasibility of our approach using several compute-intensive kernels found in numerical scientific applications.
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
Pascal:99-0459957Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Compact DAG representation and its dynamic scheduling</title><author><name sortKey="Cosnard, M" sort="Cosnard, M" uniqKey="Cosnard M" first="M." last="Cosnard">M. Cosnard</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA-INRIA Lorraine, 615, rue du Jardin Botanique</s1><s2>54602 Villiers Les Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Villiers Les Nancy</settlement></placeName></affiliation></author><author><name sortKey="Jeannot, E" sort="Jeannot, E" uniqKey="Jeannot E" first="E." last="Jeannot">E. Jeannot</name><affiliation wicri:level="3"><inist:fA14 i1="02"><s1>LIP, ENS de Lyon, 46, allée d'Italie</s1><s2>69364 Lyon</s2><s3>FRA</s3><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region><settlement type="city">Lyon</settlement></placeName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">99-0459957</idno><date when="1999">1999</date><idno type="stanalyst">PASCAL 99-0459957 INIST</idno><idno type="RBID">Pascal:99-0459957</idno><idno type="wicri:Area/PascalFrancis/Corpus">000B03</idno><idno type="wicri:Area/PascalFrancis/Curation">000D67</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000A98</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000A98</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Compact DAG representation and its dynamic scheduling</title><author><name sortKey="Cosnard, M" sort="Cosnard, M" uniqKey="Cosnard M" first="M." last="Cosnard">M. Cosnard</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA-INRIA Lorraine, 615, rue du Jardin Botanique</s1><s2>54602 Villiers Les Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Villiers Les Nancy</settlement></placeName></affiliation></author><author><name sortKey="Jeannot, E" sort="Jeannot, E" uniqKey="Jeannot E" first="E." last="Jeannot">E. Jeannot</name><affiliation wicri:level="3"><inist:fA14 i1="02"><s1>LIP, ENS de Lyon, 46, allée d'Italie</s1><s2>69364 Lyon</s2><s3>FRA</s3><sZ>2 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region><settlement type="city">Lyon</settlement></placeName></affiliation></author></analytic><series><title level="j" type="main">Journal of parallel and distributed computing</title><title level="j" type="abbreviated">J. parallel distrib. comput.</title><idno type="ISSN">0743-7315</idno><imprint><date when="1999">1999</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Journal of parallel and distributed computing</title><title level="j" type="abbreviated">J. parallel distrib. comput.</title><idno type="ISSN">0743-7315</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Coarse grain structure</term><term>Dynamic allocation</term><term>Parallelism</term><term>Scheduling</term><term>Shared memory</term><term>Tree(graph)</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Ordonnancement</term><term>Arbre graphe</term><term>Parallélisme</term><term>Allocation dynamique</term><term>Mémoire partagée</term><term>Structure gros grain</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Scheduling large task graphs is an important issue in parallel computing. In this paper we tackle the two following problems: (1) how to schedule a task graph, when it is too large to fit into memory? (2) How to build a generic program such that parameter values of a task graph can be given at run-time? Our answers feature the parameterized task graph (PTG), which is a symbolic representation of the task graph. We propose a dynamic scheduling algorithm which takes a PTG as an entry and allows us to generate a generic program. We present a theoretical study which shows that our algorithm finds good schedules for coarse-grain task graphs, has a low memory cost, and a low computational complexity. When the average number of operations of each task is large enough, we prove that the scheduling overhead is negligible with respect to the makespan. We also provide experimental results that demonstrate the feasibility of our approach using several compute-intensive kernels found in numerical scientific applications.</div></front></TEI><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0743-7315</s0></fA01><fA03 i2="1"><s0>J. parallel distrib. comput.</s0></fA03><fA05><s2>58</s2></fA05><fA06><s2>3</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>Compact DAG representation and its dynamic scheduling</s1></fA08><fA11 i1="01" i2="1"><s1>COSNARD (M.)</s1></fA11><fA11 i1="02" i2="1"><s1>JEANNOT (E.)</s1></fA11><fA14 i1="01"><s1>LORIA-INRIA Lorraine, 615, rue du Jardin Botanique</s1><s2>54602 Villiers Les Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></fA14><fA14 i1="02"><s1>LIP, ENS de Lyon, 46, allée d'Italie</s1><s2>69364 Lyon</s2><s3>FRA</s3><sZ>2 aut.</sZ></fA14><fA20><s1>487-514</s1></fA20><fA21><s1>1999</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>20948</s2><s5>354000089877120060</s5></fA43><fA44><s0>0000</s0><s1>© 1999 INIST-CNRS. All rights reserved.</s1></fA44><fA45><s0>27 ref.</s0></fA45><fA47 i1="01" i2="1"><s0>99-0459957</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>Journal of parallel and distributed computing</s0></fA64><fA66 i1="01"><s0>USA</s0></fA66><fC01 i1="01" l="ENG"><s0>Scheduling large task graphs is an important issue in parallel computing. In this paper we tackle the two following problems: (1) how to schedule a task graph, when it is too large to fit into memory? (2) How to build a generic program such that parameter values of a task graph can be given at run-time? Our answers feature the parameterized task graph (PTG), which is a symbolic representation of the task graph. We propose a dynamic scheduling algorithm which takes a PTG as an entry and allows us to generate a generic program. We present a theoretical study which shows that our algorithm finds good schedules for coarse-grain task graphs, has a low memory cost, and a low computational complexity. When the average number of operations of each task is large enough, we prove that the scheduling overhead is negligible with respect to the makespan. We also provide experimental results that demonstrate the feasibility of our approach using several compute-intensive kernels found in numerical scientific applications.</s0></fC01><fC02 i1="01" i2="X"><s0>001D02B04</s0></fC02><fC03 i1="01" i2="X" l="FRE"><s0>Ordonnancement</s0><s5>02</s5></fC03><fC03 i1="01" i2="X" l="ENG"><s0>Scheduling</s0><s5>02</s5></fC03><fC03 i1="01" i2="X" l="SPA"><s0>Ordonamiento</s0><s5>02</s5></fC03><fC03 i1="02" i2="X" l="FRE"><s0>Arbre graphe</s0><s5>03</s5></fC03><fC03 i1="02" i2="X" l="ENG"><s0>Tree(graph)</s0><s5>03</s5></fC03><fC03 i1="02" i2="X" l="SPA"><s0>Arbol grafo</s0><s5>03</s5></fC03><fC03 i1="03" i2="X" l="FRE"><s0>Parallélisme</s0><s5>04</s5></fC03><fC03 i1="03" i2="X" l="ENG"><s0>Parallelism</s0><s5>04</s5></fC03><fC03 i1="03" i2="X" l="SPA"><s0>Paralelismo</s0><s5>04</s5></fC03><fC03 i1="04" i2="X" l="FRE"><s0>Allocation dynamique</s0><s5>05</s5></fC03><fC03 i1="04" i2="X" l="ENG"><s0>Dynamic allocation</s0><s5>05</s5></fC03><fC03 i1="04" i2="X" l="SPA"><s0>Asignación dinámica</s0><s5>05</s5></fC03><fC03 i1="05" i2="X" l="FRE"><s0>Mémoire partagée</s0><s5>06</s5></fC03><fC03 i1="05" i2="X" l="ENG"><s0>Shared memory</s0><s5>06</s5></fC03><fC03 i1="05" i2="X" l="SPA"><s0>Memoria compartida</s0><s5>06</s5></fC03><fC03 i1="06" i2="X" l="FRE"><s0>Structure gros grain</s0><s5>07</s5></fC03><fC03 i1="06" i2="X" l="ENG"><s0>Coarse grain structure</s0><s5>07</s5></fC03><fC03 i1="06" i2="X" l="SPA"><s0>Estructura grano grueso</s0><s5>07</s5></fC03><fN21><s1>291</s1></fN21></pA></standard></inist><affiliations><list><country><li>France</li></country><region><li>Auvergne-Rhône-Alpes</li><li>Grand Est</li><li>Lorraine (région)</li><li>Rhône-Alpes</li></region><settlement><li>Lyon</li><li>Villiers Les Nancy</li></settlement></list><tree><country name="France"><region name="Grand Est"><name sortKey="Cosnard, M" sort="Cosnard, M" uniqKey="Cosnard M" first="M." last="Cosnard">M. Cosnard</name></region><name sortKey="Jeannot, E" sort="Jeannot, E" uniqKey="Jeannot E" first="E." last="Jeannot">E. Jeannot</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000A98 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Checkpoint/biblio.hfd -nk 000A98 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Checkpoint
|type= RBID
|clé= Pascal:99-0459957
|texte= Compact DAG representation and its dynamic scheduling
}}
| This area was generated with Dilib version V0.6.33. |  |