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

This paper introduces THEMIS, an enhanced fair scheduling algorithm for multi-tenant FPGAs that improves upon existing methods by incorporating spatiotemporal fairness, energy efficiency, and hardware heterogeneity constraints, resulting in significant gains in fairness and energy-fairness trade-offs.

The Gist

Imagine a massive, high-tech kitchen (the FPGA) where many different chefs (tenants) want to cook their meals at the same time. In the past, the head chef (the scheduler) had a very simple rule: "Everyone gets an equal amount of counter space."

The problem with this old rule was that it ignored two huge factors:

1. Time: One chef might need a tiny cutting board but cook for 10 hours, while another needs a huge stove but only cooks for 5 minutes. The old rule gave them the same "score" for fairness, which meant the long-cooking chef unfairly hogged the kitchen.
2. Energy: Every time the head chef swapped a chef out to let someone else in, it took a lot of effort and energy (like a heavy door slamming shut). The old rules didn't care about this energy cost.

The authors of this paper, Emre Karabulut and his team, built a new, smarter system called THEMIS (named after the Greek goddess of justice). They wanted to make sure the kitchen is fair, efficient, and doesn't waste energy.

Here is how THEMIS works, broken down into three simple ideas:

1. The "Time and Space" Scorecard (Spatiotemporal Fairness)

In the old system, if Chef A needed a small space but cooked for a long time, they were treated the same as Chef B who needed a big space but cooked for a short time. This was unfair because Chef A was sitting there for hours, blocking the kitchen.

THEMIS's Fix: THEMIS looks at the total workload, which is a mix of Space (how much counter they need) and Time (how long they cook).

• Analogy: Imagine a ticket system. If you have a small table but stay for 10 hours, your "ticket cost" is high. If you have a huge table but leave in 5 minutes, your ticket cost is lower. THEMIS ensures that no one can "hoard" the kitchen just because they have a small table but a long cooking time. It balances the bill based on both size and duration.

2. The "Energy vs. Fairness" Dial

The old system checked the kitchen every few minutes to see who should be cooking. But checking the kitchen takes energy (like waking up a sleeping guard).

• The Dilemma: If you check too often, you are very fair (everyone gets their turn quickly), but you waste a lot of energy. If you check rarely, you save energy, but some chefs might wait too long (unfair).
• THEMIS's Fix: THEMIS has a dial. The cloud provider can turn the dial to decide what they care about more.
  • Turn it toward Fairness: Check the kitchen often. Everyone gets a turn quickly, but the system uses more energy.
  • Turn it toward Energy: Check the kitchen less often. It saves power, but you might wait a bit longer for your turn.
  • The Result: The paper shows you can trade off about 55 times more energy for 69 times more fairness, or find a happy middle ground.

3. Respecting the "Odd-Shaped" Kitchen (Heterogeneity)

Real kitchens aren't perfect squares. Some counters have a sink built-in, some have a stove, and some are just plain wood. You can't just slide a big counter into a spot meant for a small sink.

• The Old Mistake: Previous systems assumed all kitchen spots were identical and could be easily merged or split whenever they wanted.
• THEMIS's Fix: THEMIS knows the kitchen is messy. It knows that a "Slot 1" might be different from "Slot 2." It doesn't try to force a square peg into a round hole. It respects the physical limits of the hardware and only moves chefs when absolutely necessary, avoiding the "heavy door slamming" (energy waste) of unnecessary swaps.

The Results: Did it work?

The team tested THEMIS on a real piece of hardware (a Xilinx Zedboard) with real cooking tasks (like encryption and math problems).

• Fairness: THEMIS was 24% to 98% fairer than previous methods. It stopped chefs from unfairly hogging the kitchen.
• Energy: By not swapping chefs out when they didn't need to be, they saved a lot of energy (up to 52.7% in some tests).
• Flexibility: Even when chefs arrived at random times (instead of a perfect schedule), THEMIS adapted quickly without breaking the system.

Summary

Think of THEMIS as a smart kitchen manager who:

1. Counts both how much space you use and how long you stay.
2. Lets the owner choose between saving electricity or being super fair.
3. Knows the kitchen has weird shapes and doesn't try to force things where they don't fit.

The paper concludes that this approach is a practical, real-world solution for cloud providers who want to share their expensive FPGA computers fairly without wasting money on energy or letting users get angry about unfair wait times.

Technical Summary

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

1. Problem Statement

The integration of Field-Programmable Gate Arrays (FPGAs) into cloud infrastructure offers significant cost and performance benefits through multi-tenancy, where multiple users (tenants) share the same hardware resources. However, achieving fairness in this environment is complex. Existing scheduling techniques for multi-tenant FPGAs have primarily focused on resource efficiency, often neglecting fairness or relying on flawed metrics and unrealistic assumptions.

The paper identifies critical limitations in prior work, specifically the recent Spatiotemporal FPGA Scheduling (STFS) framework:

• Incorrect Metrics: Prior algorithms often calculate fairness based solely on spatial resource allocation (area) while ignoring temporal aspects (computation time/latency). This allows a tenant with a small area footprint but a long execution time to unfairly monopolize resources. Furthermore, energy consumption associated with scheduling decisions is ignored.
• Unrealistic Assumptions: Existing models frequently assume that Partial Reconfiguration (PR) regions are homogeneous, can be dynamically merged or split at runtime, and that scheduling decisions occur at fixed intervals. In reality, commercial FPGAs feature heterogeneous resource distributions (BRAMs, LUTs, DSPs), and PR slots are statically defined with fixed boundaries that cannot be altered during execution.
• Energy Overhead: The power-hungry nature of PR operations is often unaccounted for, leading to inefficient energy usage when scheduling decisions are made too frequently.

2. Methodology

The authors propose THEMIS (Time, Heterogeneity, and Energy Minded Scheduling), a fair scheduling algorithm designed to address the aforementioned limitations through three core enhancements:

A. Latency-Aware Fair Scheduling

THEMIS introduces a new metric for "average allocation" that incorporates both spatial demand (area, $A$) and temporal demand (computation time, $CT$).

• Workload Definition: A tenant's workload is defined as the product of area and time ($A \times CT$).
• Target Allocation: The algorithm calculates a "Desired Average Allocation" ($AAD$) by determining the Least Common Multiple (LCM) of all tenants' area-time products. This ensures that tenants with longer execution times receive proportionally more resource slots to achieve fairness, preventing "unfair hoarding" by low-area, high-latency tasks.
• Formula: The desired allocation is calculated as:
  $$AAD = \frac{(A \times CT \times HMTA)}{\text{Total Execution Time}}$$
  Where $HMTA$ is "how many times allocated" and Total Execution Time is the sum of all tenants' $CT \times HMTA$.

B. Heterogeneous Region Management

Unlike prior works that assume uniform slots, THEMIS operates under the realistic constraints of commercial FPGAs:

• Static Allocation: It acknowledges that PR slot sizes are fixed at design time and cannot be dynamically resized or merged.
• Resource Heterogeneity: The algorithm accounts for the fact that two slots of the same physical size may contain different amounts of specific resources (e.g., DSPs vs. LUTs).
• Bitstream Constraints: It recognizes that bitstreams generated for one slot cannot be reused for another, even if sizes match, due to layout differences.

C. Energy-Aware Scheduling with Variable Intervals

THEMIS introduces flexibility in the scheduling decision interval (the time between re-evaluating tenant allocations).

• Trade-off Mechanism: Shorter intervals improve fairness by allowing the scheduler to correct imbalances quickly but increase energy consumption due to frequent PR operations. Longer intervals reduce energy overhead but may lead to temporary unfairness.
• Adaptive Policy: The system allows cloud providers to calibrate the interval length based on specific design goals, enabling a trade-off between energy efficiency and fairness.
• PR Optimization: The algorithm only triggers a PR operation if the tenant assigned to a slot changes from the previous interval, minimizing unnecessary reconfiguration overhead.

D. Algorithm Implementation

The scheduling process involves four stages:

1. Configuration: Profiling slots and tenants (Area and Time).
2. Initialization: Assigning tenants to the smallest available slot they fit into.
3. Competition: Tenants compete for slots based on their current allocation scores. A tenant with a lower average allocation score (adjusted by their $A \times CT$ product) gains priority. If a tenant loses a slot, they are returned to the queue.
4. PR Execution: Reconfiguration occurs only when a slot's tenant changes.

3. Key Contributions

The paper claims three primary contributions:

1. Latency-Aware Fairness: Moving beyond area-only metrics to include computation time, ensuring that tenants are compensated for both the space they occupy and the duration of their execution.
2. Energy-Fairness Trade-off: Introducing a tunable scheduling interval that allows system designers to balance energy consumption against fairness, a dimension previously ignored in FPGA scheduling.
3. Realistic Heterogeneity Handling: Developing a scheduling policy that respects the static, non-mergeable, and heterogeneous nature of commercial FPGA PR regions, making the solution deployable on real hardware rather than just theoretical models.

4. Experimental Results

The authors evaluated THEMIS on a Xilinx Zedboard XC7Z020 (Zynq-7000 SoC) using real hardware workloads derived from the MachSuite benchmarks (e.g., AES, FFT, SHA, GEMM).

• Fairness Improvement: Compared to STFS and Round-Robin variants (RRR, PRR, DRR), THEMIS improved fairness by 24.2% to 98.4%. This was measured using the Sum of Differences (SOD) between actual and desired allocations.
• Energy vs. Fairness Trade-off: The study demonstrated a tunable trade-off where the system could achieve a 55.3× difference in energy consumption versus a 69.3× difference in fairness by adjusting the scheduling interval.
  • At a fairness level of 160 SOD, THEMIS consumed 0.33mJ compared to STFS's 1.20mJ.
  • At a constant energy of 1.10mJ, THEMIS achieved an SOD of 161, while STFS resulted in 191 (higher unfairness).
• Resource Utilization: By supporting short intervals and minimizing idle times, THEMIS reduced slot idle time from 89.1% to 1.3% on average.
• Energy Savings: The algorithm achieved up to 52.7% energy savings by avoiding unnecessary PR operations.
• Robustness: The algorithm maintained high fairness under both "always-demand" (continuous requests) and "random-demand" (sporadic, unpredictable requests) scenarios, outperforming STFS which struggled with random order due to its reliance on fixed, long intervals.
• Overhead: THEMIS incurred approximately 10% higher timing overhead (clock cycles) compared to STFS due to the complexity of the new metrics, but this was deemed acceptable given the significant gains in fairness and energy efficiency.

5. Significance and Claims

The paper positions THEMIS as a necessary evolution in cloud FPGA scheduling, moving from theoretical models to practical, deployable solutions.

• Practicality: By adhering to the physical limitations of commercial FPGAs (heterogeneity, static slots), THEMIS offers a solution that can be implemented in real-world cloud environments (e.g., AWS, Azure) rather than remaining a hypothetical algorithm.
• System Design Guidance: The work informs cloud providers and system designers that fairness is a multi-objective problem requiring the consideration of time, heterogeneity, and energy. It highlights that ignoring computation time or energy overhead leads to suboptimal and unfair resource distribution.
• Future Optimization: The authors suggest that while the current implementation is serial, the algorithm is scalable and could be further optimized using multi-threaded approaches on the processor side (PS) to reduce timing overhead.

In conclusion, the paper argues that effective multi-tenant FPGA scheduling requires a paradigm shift from simple spatial allocation to a holistic spatiotemporal and energy-aware approach, which THEMIS successfully demonstrates through rigorous hardware evaluation.