טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentDmitry Basin
SubjectCAFE: Scalable Task Pools with Adjustable Fairness
and Contention
DepartmentDepartment of Electrical Engineering
Supervisor Full Professor Keidar Idit
Full Thesis textFull thesis text - English Version


Abstract

Task pools have many important applications in distributed and parallel computing. Pools are typically implemented using concurrent queues, which limits their scalability. We introduce CAFÉ, Contention and Fairness Explorer, a scalable and wait-free task pool which allows users to control the trade-off between fairness and contention. The main idea behind CAF?E is to maintain a list of TreeContainers, a novel tree-based data structure providing efficient task inserts and retrievals. TreeContainers don’t guarantee FIFO ordering on task retrievals. But by varying the size of the trees, CAFÉ can provide any type of pool, from ones using large trees with low contention but less fairness, to ones using small trees with higher contention but also greater fairness.

TreeContainer scalability of is shown by proving an O(log2 N) bound on the step complexity of insert operations when there are N inserts, as compared to an average of O(N) steps in a queue based implementation. A further proof shows that get operations are wait-free. Evaluations of CAFÉ show that it outperforms the Java SDK implementation of the Michael-Scott queue by a factor of 30, and is over three times faster than other state-of-the-art non-FIFO task pools.