Fast Reducer Hyperobjects

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.

Name thesis:degree_name

Engineer

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Kilgore, Matthew

Advisor dc:contributor.advisor

• Leiserson, Charles E.

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/143321

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/143321