Parallel Computation of the Minimal Elements of a Poset
Computing the minimal elements of a partially ordered finite set (poset) is a fundamental problem in combinatorics with numerous applications such as polynomial expression optimization, transversal hypergraph generation and redundant component removal, to name a few. We propose a divide-and-conquer...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72131 |
| _version_ | 1826199379153780736 |
|---|---|
| author | Leiserson, Charles E. Maza, Marc Moreno Li, Liyun Xie, Yuzhen |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Leiserson, Charles E. Maza, Marc Moreno Li, Liyun Xie, Yuzhen |
| author_sort | Leiserson, Charles E. |
| collection | MIT |
| description | Computing the minimal elements of a partially ordered finite set (poset) is a fundamental problem in combinatorics with numerous applications such as polynomial expression optimization, transversal hypergraph generation and redundant component removal, to name a few. We propose a divide-and-conquer algorithm which is not only cache-oblivious but also can be parallelized free of determinacy races. We have implemented it in Cilk++ targeting multicores. For our test problems of sufficiently large input size our code demonstrates a linear speedup on 32 cores. |
| first_indexed | 2024-09-23T11:19:17Z |
| format | Article |
| id | mit-1721.1/72131 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:19:17Z |
| publishDate | 2012 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/721312022-10-01T02:46:43Z Parallel Computation of the Minimal Elements of a Poset Leiserson, Charles E. Maza, Marc Moreno Li, Liyun Xie, Yuzhen Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Leiserson, Charles E. Leiserson, Charles E. Computing the minimal elements of a partially ordered finite set (poset) is a fundamental problem in combinatorics with numerous applications such as polynomial expression optimization, transversal hypergraph generation and redundant component removal, to name a few. We propose a divide-and-conquer algorithm which is not only cache-oblivious but also can be parallelized free of determinacy races. We have implemented it in Cilk++ targeting multicores. For our test problems of sufficiently large input size our code demonstrates a linear speedup on 32 cores. National Science Foundation (U.S.). (Grant number CNS-0615215) National Science Foundation (U.S.). (Grant number CCF- 0621511) 2012-08-15T12:35:22Z 2012-08-15T12:35:22Z 2010-07 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-0067-4 http://hdl.handle.net/1721.1/72131 Leiserson, Charles E. et al. “Parallel Computation of the Minimal Elements of a Poset.” PASCO '10 Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, 2010. 53-62. en_US http://dx.doi.org/10.1145/1837210.1837221 PASCO '10 Proceedings of the 4th International Workshop on Parallel and Symbolic Computation Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery (ACM) Other University Web Domain |
| spellingShingle | Leiserson, Charles E. Maza, Marc Moreno Li, Liyun Xie, Yuzhen Parallel Computation of the Minimal Elements of a Poset |
| title | Parallel Computation of the Minimal Elements of a Poset |
| title_full | Parallel Computation of the Minimal Elements of a Poset |
| title_fullStr | Parallel Computation of the Minimal Elements of a Poset |
| title_full_unstemmed | Parallel Computation of the Minimal Elements of a Poset |
| title_short | Parallel Computation of the Minimal Elements of a Poset |
| title_sort | parallel computation of the minimal elements of a poset |
| url | http://hdl.handle.net/1721.1/72131 |
| work_keys_str_mv | AT leisersoncharlese parallelcomputationoftheminimalelementsofaposet AT mazamarcmoreno parallelcomputationoftheminimalelementsofaposet AT liliyun parallelcomputationoftheminimalelementsofaposet AT xieyuzhen parallelcomputationoftheminimalelementsofaposet |