Real-time Scheduling of Concurrent\nTransactions in Multi-domain Ring Buses

Bach D. Bui, Rodolfo Pellizzoni, Marco CaccamoIllinois 2010

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.

Bus Architecture and Acyclic Transaction Set

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.

  1. POBase: A first-fit algorithm designed for acyclic transaction sets with identical periods. It is proven to be optimal for this specific configuration.
  2. 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.
  3. 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.
Example Schedule for Transactions

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

Abstract

We address the problem of scheduling concurrent periodic real-time transactions on Multi-Domain Ring Bus (MDRB).
\nThe problem is challenging because although the bus allows multiple non-overlapping transactions to be executed concurrently, the
\ndegree of concurrency depends on the topology of the bus and of executed transactions. This is a different challenge compared to
\nthat of multi-processor real-time task scheduling. To solve this problem, first, we propose two novel efficient scheduling algorithms
\nfor topographically-acyclic transaction sets. The first algorithm is optimal for transaction sets under restrictive assumptions while
\nthe second one induces a competitive sufficient schedulable utilization bound for more general transaction sets. Then, we extend
\nthese two algorithms for the scheduling of topographically-cyclic transaction sets. Extensive simulations show that the proposed
\nalgorithm can schedule transaction sets with high bus utilization and is better than that of related works in most practical settings.
\nThe implementation of the algorithms in a real test-bed shows that they have relatively low execution-time overhead.
BibTeX
@inproceedings{bui2010real,
  author = {Bach D. Bui and Rodolfo Pellizzoni and Marco Caccamo},
  title = {{Real-time Scheduling of Concurrent\textbackslash\{\}nTransactions in Multi-domain Ring Buses}},
  booktitle = {Illinois},
  year = {2010},
}
Figure