Paper Info
Title
A Graph Grammar to Transform DAGs into Graphs Describing Multithreaded Programs
Abstract
The 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 DAG found in the literature, validate the transformation process.
Year
DOI
Venue
2011
10.1109/WEIT.2011.25
WEIT
Keywords
Field
DocType
scheduling task,multithreaded program,transformation process,multithreaded program suitably,parallel program,case study,multithreaded programs,transform dags,proposed transformation,parallel hardware,graph grammar,directed acyclic graphs,np-complete problem,multi threading,computational complexity,process scheduling,np complete problem,scheduling,grammar,directed acyclic graph,directed graphs,instruction sets,algebra
Multithreading,Programming language,Instruction set,Scheduling (computing),Computer science,Directed graph,Grammar,Theoretical computer science,Directed acyclic graph,Semantics,Computational complexity theory
Conference
Citations 
PageRank 
References 
0
0.34
3
Authors
4
Name
Order
Citations
PageRank
Cicero Augusto de S. Camargo121.12
Gerson Geraldo H. Cavalheiro2153.31
Luciana Foss39414.44
Simone Andre da Costa Cavalheiro4206.53