Abstract
We address the problem of scheduling concurrent periodic real-time transactions on Multi-Domain Ring Bus (MDRB). The problem is challenging because although the bus allows multiple non-overlapping transactions to be executed concurrently, the degree of concurrency depends on the topology of the bus and of executed transactions. This is a different challenge compared to that of multi-processor real-time task scheduling. To solve this problem, first, we propose two novel efficient scheduling algorithms for topographically-acyclic transaction sets. The first algorithm is optimal for transaction sets under restrictive assumptions while the second one induces a competitive sufficient schedulable utilization bound for more general transaction sets. Then, we extend these two algorithms for the scheduling of topographically-cyclic transaction sets. Extensive simulations show that the proposed algorithm can schedule transaction sets with high bus utilization and is better than that of related works in most practical settings. The implementation of the algorithms in a real test-bed shows that they have relatively low execution-time overhead.
Introduction
In modern many-core Systems-on-Chip (SoC), such as the IBM Cell Broadband Engine, processing cores are typically interconnected via high-speed ring buses. Traditional real-time scheduling often treats the bus as a single shared resource, permitting only one transaction at a time. However, a Multi-Domain Ring Bus (MDRB) architecture allows for significant spatial parallelism, where multiple transactions can occur simultaneously provided they do not share the same physical segments.
The primary challenge in MDRB scheduling is the variable "degree of concurrency." Unlike multiprocessor systems with a fixed number of CPUs, the capacity for concurrent transactions on a ring bus depends on the bus topology and the specific paths of the data transfers. Scheduling these transactions to meet hard real-time deadlines while maximizing spatial parallelism is a complex combinatorial problem that traditional fixed-priority models fail to address efficiently.
Proposed Scheduling Algorithms
To maximize MDRB utilization, this paper introduces a suite of dynamic-priority scheduling algorithms—POBase, POGen, and cPOGen—based on a slot-based model where time is divided into discrete, synchronized intervals.
- POBase: A first-fit algorithm designed for acyclic transaction sets with identical periods. It is proven to be optimal for this specific configuration.
- POGen: An online algorithm for acyclic sets with varying periods. It utilizes a "lag" function to ensure transaction progress tracks a theoretical "fluid" schedule. The problem of determining feasible loads for each interval is mapped to a circulation problem in a directed graph, solved efficiently via the Ford-Fulkerson algorithm.
- cPOGen: An extension for cyclic transaction sets. It manages transactions that wrap around the bus by "splitting" them at a specific element and using a buffer to handle dependencies, effectively transforming cyclic problems into acyclic ones.
The core innovation lies in treating the bus as a collection of segments rather than a single resource. By defining "PO-sets"—groups of interfering transactions—the authors demonstrate that the system is schedulable as long as no single PO-set exceeds 100% utilization.
Experimental Evaluation
The proposed algorithms were evaluated through synthetic simulations and a real-world test-bed implementation.
- Simulations: 1,000 random transaction sets were generated with varying parameters. POGen and cPOGen consistently achieved higher acceptance rates than state-of-the-art Fixed-Priority Algorithms (FPA), particularly when bus utilization exceeded 80%.
- Hardware Implementation: The algorithms were implemented on an IBM Cell Broadband Engine (CellBE). The POGen scheduler demonstrated an execution-time overhead of less than 0.03ms for a 1ms interval (under 3%), confirming its practicality for real-time systems.
Conclusion
This work demonstrates that dynamic-priority scheduling can significantly enhance the performance of Multi-Domain Ring Buses by exploiting spatial parallelism. While currently tailored for ring topologies, the underlying principles of mapping spatial constraints to network flow problems provide a foundation for future extensions to 2D topologies like mesh and torus networks.
Summary updated