13. The Cilk Runtime System

TL;DR

The Cilk runtime system uses a separate deque data structure and implements a work-first principle to optimize the parallel execution of Cilk code.

Transcript

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation or to view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu. PROFESSOR: Hey, everybody. It's my pleasure once again ... Read More

Key Insights

• 🧑‍⚕️ The Cilk runtime system implements a deque data structure for each worker to efficiently steal computation.
• 😒 The thief uses a different stack and long jump routine to jump into the middle of an executing function.

Questions & Answers

Q: How does the Cilk runtime system handle stealing of computation?

The thief grabs a lock on the deque, pops the top frame, and updates the current stack frame to point to the stolen frame.

Q: How does the Cilk runtime system optimize the stealing of computation?

The thief uses a different stack and long jump routine, which allows it to resume a stolen continuation and execute the stolen computation.

Q: What is the work-first principle in the Cilk runtime system?

The work-first principle prioritizes optimized serial execution over stealing computation, ensuring that workers spend most of their time doing useful work.

Summary & Key Takeaways

• The Cilk runtime system implements a separate deque data structure for each worker, which allows for efficient stealing of computation.

• Each worker maintains a current stack frame and uses set jump and long jump routines to jump into the middle of an executing function.

• The Cilk runtime system follows the work-first principle, prioritizing the optimization of ordinary serial execution over stealing computation.