A Graph Grammar to Transform a Dataflow Graph into a Multithread Graph and its Application in Task Scheduling

dc.contributorCNPqpt-BR
dc.contributorFAPERGSpt-BR
dc.creatorCamargo, Cícero Augusto de S.
dc.creatorCavalheiro, Simone André da Costa
dc.creatorFoss, Luciana
dc.creatorCavalheiro, Gerson Geraldo H.
dc.date2013-01-14
dc.date.accessioned2018-11-07T21:08:48Z
dc.date.available2018-11-07T21:08:48Z
dc.identifierhttps://seer.ufrgs.br/rita/article/view/rita_v20_n1_p140
dc.identifier10.22456/2175-2745.25210
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/2187469
dc.descriptionThe scheduling of tasks in a parallel program is an NP-complete problem, where scheduling tasks over multiple processing units requires an effective strategy to maximize the exploitation of the parallel hardware. Several studies focus on the scheduling of parallel programs described into DAGs (Directed Acyclic Graphs). However, this representation does not describe a multithreaded program suitably. This paper shows the structure and semantics of a DCG, an abstraction which describes a multithreaded program, and proposes standards to map structures found in DAGs into segments of a DCG. A graph grammar has been developed to perform the proposed transformation and case studies using DAGs found in the literature validate the transformation process. Besides the automatic translation and precise definition of the mapping, the use of a formal language also allowed the verification of the existence and uniqueness of the out coming model. pt-BR
dc.formatapplication/pdf
dc.languagepor
dc.publisherInstituto de Informática - Universidade Federal do Rio Grande do Sulen-US
dc.relationhttps://seer.ufrgs.br/rita/article/view/rita_v20_n1_p140/23797
dc.relationhttps://seer.ufrgs.br/rita/article/downloadSuppFile/rita_v20_n1_p140/15619
dc.relationhttps://seer.ufrgs.br/rita/article/downloadSuppFile/rita_v20_n1_p140/15620
dc.relationhttps://seer.ufrgs.br/rita/article/downloadSuppFile/rita_v20_n1_p140/15621
dc.relationhttps://seer.ufrgs.br/rita/article/downloadSuppFile/rita_v20_n1_p140/15622
dc.rightsDireitos autorais 2018 Cícero Augusto de S. Camargo, Simone André da Costa Cavalheiro, Luciana Foss, Gerson Geraldo H. Cavalheiropt-BR
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/4.0pt-BR
dc.sourceRevista de Informática Teórica e Aplicada; v. 20, n. 1 (2013); 140-179en-US
dc.sourceRevista de Informática Teórica e Aplicada; v. 20, n. 1 (2013); 140-179pt-BR
dc.source21752745
dc.source01034308
dc.subjectformal methods; graph grammar; parallel programmingpt-BR
dc.titleA Graph Grammar to Transform a Dataflow Graph into a Multithread Graph and its Application in Task Schedulingpt-BR
dc.typeArtículos de revistas
dc.typeArtículos de revistas
dc.coveragept-BR
dc.coveragept-BR
dc.coveragept-BR


Este ítem pertenece a la siguiente institución