Karl Taht's Research Paper Blog

Authors: Kay Ousterhout, Patrick Wendell, Matei Zaharia, Ion Stoica Venue:    SOSP 2013 This work presents Sparrow, a stateless, decentralized scheduler for cluster scheduling. The scheduling component uses two key ideas: batch sampling and late binding. Batch sampling is an extension of the power of two choices [1], which shows that the "tail" can quickly be cut off by simply sampling between two machines versus randomly selecting one. Batch sampling generalizes this by sampling dm machines, and placing the m   tasks on the machine with the lowest load. Late binding delays the actual task transfer until the machine is ready to process the request. This can be thought of as having a place holder in the worker's queue, and when the worker is finally ready to process it, the actual task is transferred from the scheduler to the worker. This avoids having to rely on inaccurate metrics such as queue depth. Each worker maintains its "instance" of Sparrow, which us...

Authors: Luiz Barroso, Mike Marty, David Patterson, and Parthasarathy Ranganathan Venue:    CACM (Magazine) This work shows that while architects have tackled problems and the nanosecond scale, and software has optimized for the millisecond scale, there exists a significant void in microsecond operation optimization. The result is that many operations which take in the order of a few microseconds degenerate into millisecond operations, or at least, reduce efficiency by up to or more than an order of magnitude in many cases. One such example is an RDMA, which by itself is only a ~2us operation. However, after dispatching, kernel-scheduling, interrupt-based notifications, and a TCP/IP stack, the transportation blows up to ~75us. The authors imply that this area is prime for research to optimize warehouse-scale computing. Such areas include reduced lock contention, lower-overhead interrupt handling, improved scheduling, and hardware-offloading in the mi...