Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers

Richard Cole, Vijaya Ramachandran

We analyze the caching overhead incurred by a class of multithreaded algorithms when scheduled by an arbitrary scheduler. We obtain bounds that match or improve upon the well-known…