Master’s Thesis Presentation • Networks and Distributed Systems — FlexQueue: Simple and Efficient Priority Queue for System SoftwareExport this event to calendar

Tuesday, May 15, 2018 — 10:00 AM EDT

Yifan Zhang, Master’s candidate
David R. Cheriton School of Computer Science

Existing studies of priority queue implementations often focus on improving canonical operations such as insert and deleteMin, while sacrificing design simplicity and predictable worst case latency. Design simplicity is sacrificed as the algorithm becomes more and more optimized, taking into account characteristics of the input workload distribution. Predictable worst case latency is sacrificed when operations such as memory allocation and structural re-organization are deferred until absolutely necessary. 

While these techniques often yield performance improvement to some degree, one might want to take a step back and ask a more basic question: is it possible to achieve similar performance while retaining a simple design? By combining techniques such as hierarchical bit vector and dynamic horizon resizing, all of which are straight-forward in principle, this thesis presents a new priority queue design called FlexQueue, that answers this question with a definitive “yes”.

Location 
DC - William G. Davis Computer Research Centre
2314
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
  1. 2019 (196)
    1. October (3)
    2. September (20)
    3. August (18)
    4. July (12)
    5. June (23)
    6. May (23)
    7. April (32)
    8. March (25)
    9. February (16)
    10. January (24)
  2. 2018 (220)
    1. December (16)
    2. November (19)
    3. October (26)
    4. September (22)
    5. August (17)
    6. July (20)
    7. June (13)
    8. May (25)
    9. April (34)
    10. March (24)
    11. February (3)
    12. January (1)
  3. 2017 (36)
  4. 2016 (21)
  5. 2015 (36)
  6. 2014 (33)
  7. 2013 (23)
  8. 2012 (4)
  9. 2011 (1)
  10. 2010 (1)
  11. 2009 (1)
  12. 2008 (1)