Mapping Unstructured Parallelism to Series-Parallel DAGs
Many parallel programming languages allow programmers to describe parallelism by using constructs such as fork/join. When executed, such programs can be modeled as directed graphs, with nodes representing a computation and edges representing the sequence and dependency. However, because it does not...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | en_US |
| Published: |
2003
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/3862 |
| _version_ | 1811081438426038272 |
|---|---|
| author | Pan, Yan Hsu, Wen Jing |
| author_facet | Pan, Yan Hsu, Wen Jing |
| author_sort | Pan, Yan |
| collection | MIT |
| description | Many parallel programming languages allow programmers to describe parallelism by using constructs such as fork/join. When executed, such programs can be modeled as directed graphs, with nodes representing a computation and edges representing the sequence and dependency. However, because it does not coerce regularity in the computation, the general model is not amenable to efficient execution of the resulting program. Therefore, a more restrictive model called Series-Parallel DAG (Directed Acyclic Graph) has been proposed and adopted by several major parallel languages. As reported by the Cilk developers, many parallel computations can be easily expressed in the series-parallel model, and there are provably efficient scheduling algorithms for the SP DAGs. Nevertheless, it remains open how much inherent parallelism will be lost when conforming to the model, because expressing a computation in the series-parallel model may also induce performance losses. We will show that any general DAG can be converted into an SP DAG without violating the original precedence relations; moreover, the conversion can be carried out in essentially linear time and space, and the resulting DAG exhibits little loss in the parallelism. Since the resulting SP DAG can then be executed with high efficiency, it implies that the languages based on SP DAGs are not as restrictive as they were thought to be. |
| first_indexed | 2024-09-23T11:46:41Z |
| format | Article |
| id | mit-1721.1/3862 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:46:41Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | mit-1721.1/38622019-04-12T13:40:55Z Mapping Unstructured Parallelism to Series-Parallel DAGs Pan, Yan Hsu, Wen Jing parallel computing Series-Parallel Directed Acyclic Graph Cilk SP DAG Many parallel programming languages allow programmers to describe parallelism by using constructs such as fork/join. When executed, such programs can be modeled as directed graphs, with nodes representing a computation and edges representing the sequence and dependency. However, because it does not coerce regularity in the computation, the general model is not amenable to efficient execution of the resulting program. Therefore, a more restrictive model called Series-Parallel DAG (Directed Acyclic Graph) has been proposed and adopted by several major parallel languages. As reported by the Cilk developers, many parallel computations can be easily expressed in the series-parallel model, and there are provably efficient scheduling algorithms for the SP DAGs. Nevertheless, it remains open how much inherent parallelism will be lost when conforming to the model, because expressing a computation in the series-parallel model may also induce performance losses. We will show that any general DAG can be converted into an SP DAG without violating the original precedence relations; moreover, the conversion can be carried out in essentially linear time and space, and the resulting DAG exhibits little loss in the parallelism. Since the resulting SP DAG can then be executed with high efficiency, it implies that the languages based on SP DAGs are not as restrictive as they were thought to be. Singapore-MIT Alliance (SMA) 2003-12-13T19:25:20Z 2003-12-13T19:25:20Z 2004-01 Article http://hdl.handle.net/1721.1/3862 en_US Computer Science (CS); 12433 bytes application/pdf application/pdf |
| spellingShingle | parallel computing Series-Parallel Directed Acyclic Graph Cilk SP DAG Pan, Yan Hsu, Wen Jing Mapping Unstructured Parallelism to Series-Parallel DAGs |
| title | Mapping Unstructured Parallelism to Series-Parallel DAGs |
| title_full | Mapping Unstructured Parallelism to Series-Parallel DAGs |
| title_fullStr | Mapping Unstructured Parallelism to Series-Parallel DAGs |
| title_full_unstemmed | Mapping Unstructured Parallelism to Series-Parallel DAGs |
| title_short | Mapping Unstructured Parallelism to Series-Parallel DAGs |
| title_sort | mapping unstructured parallelism to series parallel dags |
| topic | parallel computing Series-Parallel Directed Acyclic Graph Cilk SP DAG |
| url | http://hdl.handle.net/1721.1/3862 |
| work_keys_str_mv | AT panyan mappingunstructuredparallelismtoseriesparalleldags AT hsuwenjing mappingunstructuredparallelismtoseriesparalleldags |