Analyzing Algorithms on Real World Data
summary
Work on Google traces builds a replay simulator from checkpoint files, tests 11 algorithms on CPU/RAM/disk multi‑dimensional packing, and shows that naive comparisons fail because traces only record completed jobs. Scaling by deleting machines distinguishes algorithms: best fit and sum of squares keep throughput highest as machines drop and best fit wins in practice because it’s simple and fast to implement. For the weapon‑maintenance problem the pipeline solves an LP and uses LP + alpha‑point rounding to generate many feasible schedules, cutting costs ~5–10%.
AI-written summary · about
chapters (7)
- 0:00Intro
- 1:31Algorithm Engineering Design experiments to learn about the performance of algorithms • Important . Data is typically given from real applications or comes from distributions . Not the main focus of this talk
- 3:44Dealing with Real World Problems You have a particular application to solve . How to schedule google's data centers • How to manage the maintainance of the U.S. nuclear weapons stockpile - High level questions . How do you provide a "good solution" • How do you test and evaluate . What is the value of theory
- 5:12How do you provide a good solution The solution should work for the problem at hand The solution should continue to work into the forseeable future You should be able to convince the people running your solution that it is a good solution
- 12:09What is the (non-obvious) value of theory Understanding the proper level of abstraction to design algorithms Designing algorithms that are general and not tailored to particular data Understanding worst case behavior Using properties of algorithms in ways different from worst case analysis - Learning more general lessons
- 31:17Scheduling Nuclear Weapons Maintance Work with E. Asgiersson J. Berry, D. Phillips, C. Phillips, J. Wein Jobs with multiple tasks with precedence Each needs to be run in • A subset of facilities • By workers with certifications Goal is to see if you have enough resources to schedule everything that needs to be scheduled in the next year.
- 33:04Alpha points Consider a non-preemptive scheduling problem of 1 machines with release dates, minimize average completion time . Solve preemptive version (or more generally LP relaxation) • Define the alpha(j) to be the earliest time at which an alpha fraction of job j finishes . Schedule the jobs in order by alpha(i). - Much is known about approximation ratios for many average completion time problems
related talks
31mAlgorithms to live by and why should we care
38mData Secrets from a Platform Engineer
50mProgram Analysis
20mSystems @Scale Summer Live Q&A Session #2
35mThe profession of solving (the wrong problem)
26mWeek 1 Live Q&A
44mThe Math behind Project Scheduling, Bug Tracking, and Triage
49mHow to get smarter while doing your job