Batchy: Batch-scheduling Data Flow Graphs with Service-level Objectives

Authors: 

Tamás Lévai, Budapest University of Technology and Economics & University of Southern California; Felicián Németh, Budapest University of Technology and Economics; Barath Raghavan, University of Southern California; Gábor Rétvári, MTA-BME Information Systems Research Group & Ericsson Research, Hungary

Abstract: 

Data flow graphs are a popular program representation in machine learning, big data analytics, signal processing, and, increasingly, networking, where graph nodes correspond to processing primitives and graph edges describe control flow. To improve CPU cache locality and exploit data-level parallelism, nodes usually process data in batches. Unfortunately, as batches are split across dozens or hundreds of parallel processing pathways through the graph they tend to fragment into many small chunks, leading to a loss of batch efficiency.

We present Batchy, a scheduler for run-to-completion packet processing engines, which uses controlled queuing to efficiently reconstruct fragmented batches in accordance with strict service-level objectives (SLOs). Batchy comprises a runtime profiler to quantify batch-processing gain on different processing functions, an analytical model to fine-tune queue backlogs, a new queuing abstraction to realize this model in run-to-completion execution, and a one-step receding horizon controller that adjusts backlogs across the pipeline. We present extensive experiments on five networking use cases taken from an official 5G benchmark suite to show that Batchy provides 2--3x the performance of prior work while accurately satisfying delay SLOs.

NSDI '20 Open Access Sponsored by NetApp

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {246322,
author = {Tam{\'a}s L{\'e}vai and Felici{\'a}n N{\'e}meth and Barath Raghavan and Gabor Retvari},
title = {Batchy: Batch-scheduling Data Flow Graphs with Service-level Objectives },
booktitle = {17th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 20)},
year = {2020},
isbn = {978-1-939133-13-7},
address = {Santa Clara, CA},
pages = {633--649},
url = {https://www.usenix.org/conference/nsdi20/presentation/levai},
publisher = {{USENIX} Association},
month = feb,
}

Presentation Video