CS Events

Qualifying Exam

Dynamic Heavy-Case Balls-and-Bins, Low-Associativity Paging, and the Address Translation Problem


Download as iCal file

Wednesday, October 21, 2020, 04:00pm - 06:00pm



Guido Tagliavini Ponce

Location : Remote via Webex


Prof. Martin Farach-Colton (Advisor)

Prof. Aaron Bernstein

Prof. Yongfeng Zhang

Prof. Sepehr Assadi

Event Type: Qualifying Exam

Abstract: Balls-and-bins games are a powerful mathematical abstraction that are used to model a wide variety of scenarios. We consider bounds on the fullest bin in the dynamic case of an unrestricted oblivious adversary: balls can be inserted and deleted in any order and they can be reinserted. There are n bins and at no point does the system has more than m balls. We give a bin-selection rule using d + 1 ≥ 3 hash functions that achieves a maximum load of at most (1 + o(1))m/n + (log log n)/d + O(1), with high probability in n, against any oblivious adversary in the dynamic setting. This result settles a long-standing open question and is tight up to low-order terms when m = ω(n log log n). We apply this result to a paging problem that requires a tight analysis in this range. Specifically, we use this balls-and-bins rule to show that for any fully-associative paging algorithm on a memory of size M, there is a (1 + o(1))-competitive paging algorithm with (1 + o(1))-memory augmentation that has nearly log log M associativity, where the associativity of an algorithm is the maximum number of memory locations in which a page can be placed. This low-associativity paging algorithm is in turn used to reduce the number of bits a translation lookaside buffer (TLB) needs to encode every virtual-to-physical address translation. We show how to pack these small encodings into a TLB and implement what we call hashed huge pages. These do not suffer from the main drawbacks of standard huge pages. We prove that hashed huge pages are (2 + o(1))-competitive with the optimal offline TLB/paging algorithm that uses standard huge pages.


Meeting link: https://rutgers.webex.com/rutgers/j.php?MTID=m3179c082dd60aeb96ada577a74842442

Meeting number: 120 866 3355
Password: 1234