{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/61575"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/61575","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Design and analysis of a nondeterministic parallel breadth-first search algorithm","abstract":"I have developed a multithreaded implementation of breadth-first search (BFS) of a sparse graph using the Cilk++ extensions to C++. My PBFS program on a single processor runs as quickly as a standard C++ breadth-first search implementation. PBFS achieves high workefficiency by using a novel implementation of a multiset data structure, called a \"bag,\" in place of the FIFO queue usually employed in serial breadth-first search algorithms. For a variety of benchmark input graphs whose diameters are significantly smaller than the number of vertices - a condition met by many real-world graphs - PBFS demonstrates good speedup with the number of processing cores. Since PBFS employs a nonconstant-time \"reducer\" - a \"hyperobject\" feature of Cilk++ - the work inherent in a PBFS execution depends nondeterministically on how the underlying work-stealing scheduler load-balances the computation. I provide a general method for analyzing nondeteriministic programs that use reducers. PBFS also is nondeterministic in that it contains benign races which affect its performance but not its correctness. Fixing these races with mutual-exclusion locks slows down PBFS empirically, but it makes the algorithm amenable to analysis. In particular, I show that for a graph G = (V, E) with diameter D and bounded out-degree. this data-race-free version of PBFS algorithm runs in time O((V +E)/P+DIg[supercript 3] (V/D)) on P processors, which means that it attains near-perfect linear speedup if P < (V +E)/DIg[supercript 3] (V/D).","abstract_html":"I have developed a multithreaded implementation of breadth-first search (BFS) of a sparse graph using the Cilk++ extensions to C++. My PBFS program on a single processor runs as quickly as a standard C++ breadth-first search implementation. PBFS achieves high workefficiency by using a novel implementation of a multiset data structure, called a &quot;bag,&quot; in place of the FIFO queue usually employed in serial breadth-first search algorithms. For a variety of benchmark input graphs whose diameters are significantly smaller than the number of vertices - a condition met by many real-world graphs - PBFS demonstrates good speedup with the number of processing cores. Since PBFS employs a nonconstant-time &quot;reducer&quot; - a &quot;hyperobject&quot; feature of Cilk++ - the work inherent in a PBFS execution depends nondeterministically on how the underlying work-stealing scheduler load-balances the computation. I provide a general method for analyzing nondeteriministic programs that use reducers. PBFS also is nondeterministic in that it contains benign races which affect its performance but not its correctness. Fixing these races with mutual-exclusion locks slows down PBFS empirically, but it makes the algorithm amenable to analysis. In particular, I show that for a graph G = (V, E) with diameter D and bounded out-degree. this data-race-free version of PBFS algorithm runs in time O((V +E)/P+DIg[supercript 3] (V/D)) on P processors, which means that it attains near-perfect linear speedup if P &lt; (V +E)/DIg[supercript 3] (V/D).","abstract_has_math":false,"creators":["Schardl, Tao Benjamin"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Charles E. Leiserson."],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010","date_published":"2010","updated_at":"2026-07-22T22:21:54Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/61575","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Charles E. Leiserson."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Schardl, Tao Benjamin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2011-03-07T15:17:33Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2011-03-07T15:17:33Z"]},{"key":"dc:date.issued","label":"Date","values":["2010"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/61575"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 75-77)."]},{"key":"dc:description.abstract","label":"Abstract","values":["I have developed a multithreaded implementation of breadth-first search (BFS) of a sparse graph using the Cilk++ extensions to C++. My PBFS program on a single processor runs as quickly as a standard C++ breadth-first search implementation. PBFS achieves high workefficiency by using a novel implementation of a multiset data structure, called a \"bag,\" in place of the FIFO queue usually employed in serial breadth-first search algorithms. For a variety of benchmark input graphs whose diameters are significantly smaller than the number of vertices - a condition met by many real-world graphs - PBFS demonstrates good speedup with the number of processing cores. Since PBFS employs a nonconstant-time \"reducer\" - a \"hyperobject\" feature of Cilk++ - the work inherent in a PBFS execution depends nondeterministically on how the underlying work-stealing scheduler load-balances the computation. I provide a general method for analyzing nondeteriministic programs that use reducers. PBFS also is nondeterministic in that it contains benign races which affect its performance but not its correctness. Fixing these races with mutual-exclusion locks slows down PBFS empirically, but it makes the algorithm amenable to analysis. In particular, I show that for a graph G = (V, E) with diameter D and bounded out-degree. this data-race-free version of PBFS algorithm runs in time O((V +E)/P+DIg[supercript 3] (V/D)) on P processors, which means that it attains near-perfect linear speedup if P < (V +E)/DIg[supercript 3] (V/D)."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["Design and analysis of a nondeterministic parallel breadth-first search algorithm"]}]}],"canonical_facts":{"dc:contributor.advisor":["Charles E. Leiserson."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Schardl, Tao Benjamin"],"dc:date.accessioned":["2011-03-07T15:17:33Z"],"dc:date.available":["2011-03-07T15:17:33Z"],"dc:date.issued":["2010"],"dc:description":["Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.","Cataloged from PDF version of thesis.","Includes bibliographical references (p. 75-77)."],"dc:description.abstract":["I have developed a multithreaded implementation of breadth-first search (BFS) of a sparse graph using the Cilk++ extensions to C++. My PBFS program on a single processor runs as quickly as a standard C++ breadth-first search implementation. PBFS achieves high workefficiency by using a novel implementation of a multiset data structure, called a \"bag,\" in place of the FIFO queue usually employed in serial breadth-first search algorithms. For a variety of benchmark input graphs whose diameters are significantly smaller than the number of vertices - a condition met by many real-world graphs - PBFS demonstrates good speedup with the number of processing cores. Since PBFS employs a nonconstant-time \"reducer\" - a \"hyperobject\" feature of Cilk++ - the work inherent in a PBFS execution depends nondeterministically on how the underlying work-stealing scheduler load-balances the computation. I provide a general method for analyzing nondeteriministic programs that use reducers. PBFS also is nondeterministic in that it contains benign races which affect its performance but not its correctness. Fixing these races with mutual-exclusion locks slows down PBFS empirically, but it makes the algorithm amenable to analysis. In particular, I show that for a graph G = (V, E) with diameter D and bounded out-degree. this data-race-free version of PBFS algorithm runs in time O((V +E)/P+DIg[supercript 3] (V/D)) on P processors, which means that it attains near-perfect linear speedup if P < (V +E)/DIg[supercript 3] (V/D)."],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/61575"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Design and analysis of a nondeterministic parallel breadth-first search algorithm"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:54Z"}