THEMIS: Time, Heterogeneity, and Energy Minded Scheduling for Fair Multi-Tenant Use in FPGAs

Using correct design metrics and understanding the limitations of the underlying technology is critical to developing effective scheduling algorithms. Unfortunately, existing scheduling techniques used incorrect metrics and had <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">un-realistic</i> assumptions for fair scheduling of multi-tenant FPGAs where each tenant is aimed to share approximately the same number of resources both spatially (in space) and temporally (in time). <p xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">This paper proposes an improved fair scheduling algorithm that fixes earlier issues with metrics and assumptions for ‘fair’ multi-tenant FPGA use. Specifically, we claim three improvements. First, we consider both spatial and temporal aspects to provide spatiotemporal fairness—this improves a recent prior work that assumed all tasks would have the same latency. Second, we add the energy dimension to fairness: by calibrating the scheduling decision intervals and including their energy overhead, our algorithm offers trading off energy efficiency for fairness. Third, we consider previously ignored facts about FPGA multi-tenancy, such as the existence of heterogeneous regions and the inflexibility of run-time merging/splitting of partially reconfigurable regions.We develop and evaluate our improved fair scheduling algorithm with these three enhancements. Inspired by the Greek goddess of law and personification of justice, we name our fair scheduling solution THEMIS: <u>T</u>ime, <u>H</u>eterogeneity, and <u>E</u>nergy <u>Mi</u>nded <u>S</u>cheduling. <p xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">We implemented our solution on Xilinx Zedboard XC7Z020 with real hardware workloads and used real measurements on the FPGA to quantify the savings of our approach. Compared to previous algorithms, our improved scheduling algorithm enhances fairness between 24.2–98.4% and allows a trade-off between 55.3× in energy vs. 69.3× in fairness. The paper thus informs cloud providers about future scheduling optimizations for fairness with related challenges and opportunities.