When to Give Up on a Parallel Implementation
When to Give Up on a Parallel Implementation
In the Serial Parallel Decision Problem (SPDP), introduced by Kuszmaul and Westover [SPAA'24], an algorithm receives a series of tasks online, and must choose for each between a serial implementation and a parallelizable (but less efficient) implementation. Kuszmaul and Westover describe three decision models: (1) \defn{Instantly-committing} schedulers must decide on …