Optimizing Parallel Performance with Work and Span in the OpenCilk Compiler

OpenCilk is the modern iteration of Cilk, a multithreaded programming environment designed for high-performance multicore computing. OpenCilk consists of a LLVM fork called Tapir and a runtime scheduler, which, together, allow for OpenCilk’s high performance in practice. However, there are many opportunities to improve on the implementation of OpenCilk. In particular, current grainsize calculations for OpenCilk rely on a notion of work that is limited in a few ways. In this thesis, I propose an alternate implementation that creates a first-class notion of work and span within the OpenCilk compiler that is then used to inform optimizations within OpenCilk. I then analyze the current formulas for grainsizes. I identify key scenarios where the compiler is unable to determine a suitable grainsize and use this to suggest improvements. Finally, I construct a benchmark of one of these scenarios using a Twitter follower dataset and empirically analyze optimal grainsizes for it.

Name thesis:degree_name

Master

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

• Reddy, Nikhil

Advisor dc:contributor.advisor

• Schardl, Tao B.

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/147495

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/147495