{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/143321"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/143321","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Fast Reducer Hyperobjects","abstract":"This thesis investigates the performance of reducer hyperobjects, a feature of the Cilk task-parallel runtime system that enables concurrent associative updates to nonlocal variables. Reducers are more performant than more traditional methods of enabling concurrent updates, such as locking and atomic updates. Unfortunately, existing reducer implementations can suffer a cost of up to 10 times that of a serial update, depending on the benchmark. This overhead incurred by reducers can be decreased by three approaches: runtime data structures, compiler-runtime integration, and compiler optimization. When these approaches are used to performance-engineer the OpenCilk runtime system's reducers, the overall performance of a benchmark suite designed to stress-test reducers sees a geometric average improvement of 25.74% and a maximum improvement of 88.32%. This thesis also investigates ``commutative'' reducers, a proposed reducer optimization premised on restricted semantics, but finds they yield a performance degredation while being linguistically unwieldy. The examination of commutative reducers leads to an empirical investigation of the scalability of traditional reducers, finding a quadratic upper bound on their performance to be loose. Parts of this thesis represent joint work with Charles E. Leiserson, Tim Kaler, William S. Moses, Qi Qi, and Tao B. Schardl of MIT and I-Ting Angelina Lee of Washington University in St .Louis.","abstract_html":"This thesis investigates the performance of reducer hyperobjects, a feature of the Cilk task-parallel runtime system that enables concurrent associative updates to nonlocal variables. Reducers are more performant than more traditional methods of enabling concurrent updates, such as locking and atomic updates. Unfortunately, existing reducer implementations can suffer a cost of up to 10 times that of a serial update, depending on the benchmark. This overhead incurred by reducers can be decreased by three approaches: runtime data structures, compiler-runtime integration, and compiler optimization. When these approaches are used to performance-engineer the OpenCilk runtime system's reducers, the overall performance of a benchmark suite designed to stress-test reducers sees a geometric average improvement of 25.74% and a maximum improvement of 88.32%. This thesis also investigates ``commutative'' reducers, a proposed reducer optimization premised on restricted semantics, but finds they yield a performance degredation while being linguistically unwieldy. The examination of commutative reducers leads to an empirical investigation of the scalability of traditional reducers, finding a quadratic upper bound on their performance to be loose. Parts of this thesis represent joint work with Charles E. Leiserson, Tim Kaler, William S. Moses, Qi Qi, and Tao B. Schardl of MIT and I-Ting Angelina Lee of Washington University in St .Louis.","abstract_has_math":false,"creators":["Kilgore, Matthew"],"institution":"Massachusetts Institute of Technology","degree_name":"Engineer","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Leiserson, Charles E."],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-02","date_published":"2022-02","updated_at":"2026-07-22T22:21:14Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/143321","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Leiserson, Charles E."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Kilgore, Matthew"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-06-15T13:12:22Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-06-15T13:12:22Z"]},{"key":"dc:date.issued","label":"Date","values":["2022-02"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Engineer","Engineer in Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/143321"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["This thesis investigates the performance of reducer hyperobjects, a feature of the Cilk task-parallel runtime system that enables concurrent associative updates to nonlocal variables. Reducers are more performant than more traditional methods of enabling concurrent updates, such as locking and atomic updates. Unfortunately, existing reducer implementations can suffer a cost of up to 10 times that of a serial update, depending on the benchmark. This overhead incurred by reducers can be decreased by three approaches: runtime data structures, compiler-runtime integration, and compiler optimization. When these approaches are used to performance-engineer the OpenCilk runtime system's reducers, the overall performance of a benchmark suite designed to stress-test reducers sees a geometric average improvement of 25.74% and a maximum improvement of 88.32%. This thesis also investigates ``commutative'' reducers, a proposed reducer optimization premised on restricted semantics, but finds they yield a performance degredation while being linguistically unwieldy. The examination of commutative reducers leads to an empirical investigation of the scalability of traditional reducers, finding a quadratic upper bound on their performance to be loose. Parts of this thesis represent joint work with Charles E. Leiserson, Tim Kaler, William S. Moses, Qi Qi, and Tao B. Schardl of MIT and I-Ting Angelina Lee of Washington University in St .Louis."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["E.C.S."]},{"key":"dc:title","label":"Title","values":["Fast Reducer Hyperobjects"]}]}],"canonical_facts":{"dc:contributor.advisor":["Leiserson, Charles E."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Kilgore, Matthew"],"dc:date.accessioned":["2022-06-15T13:12:22Z"],"dc:date.available":["2022-06-15T13:12:22Z"],"dc:date.issued":["2022-02"],"dc:description.abstract":["This thesis investigates the performance of reducer hyperobjects, a feature of the Cilk task-parallel runtime system that enables concurrent associative updates to nonlocal variables. Reducers are more performant than more traditional methods of enabling concurrent updates, such as locking and atomic updates. Unfortunately, existing reducer implementations can suffer a cost of up to 10 times that of a serial update, depending on the benchmark. This overhead incurred by reducers can be decreased by three approaches: runtime data structures, compiler-runtime integration, and compiler optimization. When these approaches are used to performance-engineer the OpenCilk runtime system's reducers, the overall performance of a benchmark suite designed to stress-test reducers sees a geometric average improvement of 25.74% and a maximum improvement of 88.32%. This thesis also investigates ``commutative'' reducers, a proposed reducer optimization premised on restricted semantics, but finds they yield a performance degredation while being linguistically unwieldy. The examination of commutative reducers leads to an empirical investigation of the scalability of traditional reducers, finding a quadratic upper bound on their performance to be loose. Parts of this thesis represent joint work with Charles E. Leiserson, Tim Kaler, William S. Moses, Qi Qi, and Tao B. Schardl of MIT and I-Ting Angelina Lee of Washington University in St .Louis."],"dc:description.degree":["E.C.S."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/143321"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Fast Reducer Hyperobjects"],"dc:type":["Thesis"],"thesis:degree_name":["Engineer","Engineer in Computer Science"]},"updated_at":"2026-07-22T22:21:14Z"}