This paper introduces COST (literal: Configuration that Outperforms a Single Thread) for big-data platforms.
If parallel algorithms outperform a well-thought single thread implementation only after given 16 CPU cores, then its COST is 16. COST can also be unbounded, meaning you should always use the single thread algorithm.
The paper surveys how a single-thread PageRank implementation outperforms parallel algorithms run on big data platforms with hundreds of core. OR how a single threaded Union Find implementation outperforms parallel label-propagation algorithms for quickly finding connected components.
Takeaway: Optimize for single thread as a baseline.
https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-mcsherry.pdf
This paper introduces COST (literal: Configuration that Outperforms a Single Thread) for big-data platforms. If parallel algorithms outperform a well-thought single thread implementation only after given 16 CPU cores, then its COST is 16. COST can also be unbounded, meaning you should always use the single thread algorithm.
The paper surveys how a single-thread PageRank implementation outperforms parallel algorithms run on big data platforms with hundreds of core. OR how a single threaded Union Find implementation outperforms parallel label-propagation algorithms for quickly finding connected components.
Takeaway: Optimize for single thread as a baseline.