Source-linked AI summary
RunSoC 2.0: Scheduling and Allocating Automotive Software Tasks to Hardware Partitions in Heterogeneous MPSoCs
Daniel Krüger, Lucas Mauser, Stefan Wagner
TL;DR
Centralized heterogeneous MPSoCs create difficult automotive scheduling problems under timing, memory, communication, and affinity constraints. RunSoC 2.0 addresses them with multi-objective task-level allocation and scheduling across multiple solver backends. CP-SAT showed the strongest overall behavior, while memory pressure emerged as the dominant bottleneck and the evaluation remains bounded by its modeled constraints and synthetic workloads.
Problem
Heterogeneous MPSoC task allocation and scheduling must satisfy processor-specific execution, affinity, end-to-end latency, memory, and communication constraints.
Method
RunSoC 2.0 models these constraints in multi-objective scheduling and allocation and compares CBC, CP-SAT, and GA backends.
Results
CP-SAT showed the strongest overall behavior, scaling to the largest task sets while maintaining practical runtimes and high solution quality.
Takeaways & Limitations
Memory-aware mapping is essential for centralized automotive MPSoCs because memory pressure emerged as the dominant bottleneck.
Takeaways & Limitations
The current evaluation uses synthetic workloads and omits memory bandwidth, bus contention, finer-grained communication, mixed-criticality, and cache-preemption effects from the platform model.
Abstract
from arXiv · showhide
Centralized automotive architectures increasingly consolidate compute-intensive workloads onto heterogeneous Multi-Processor System-on-Chip (MPSoC), creating strict execution, memory, and communication constraints. This paper presents RunSoC 2.0, a customizable framework for early-stage design-space exploration of task scheduling and allocation on heterogeneous MPSoCs. Building on RunSoC 1.0, which targeted allocation on homogeneous hardware, RunSoC 2.0 extends the framework to heterogeneous platforms by modeling processor-specific execution times, cluster-level organization, and domain-specific processing properties. It represents task sets as directed acyclic graphs (DAGs) subjected to strict end-to-end latency and core-affinity constraints, and formulates task scheduling and allocation as a multi-objective optimization problem that minimizes hierarchical memory-budget violations and inter-core/inter-cluster communication penalties. The framework supports multiple solving backends, including COIN-OR Branch and Cut (CBC), Google OR-Tools CP-SAT, and a Genetic Algorithm (GA), enabling comparative evaluation of exact, constraint-programming, and meta-heuristic approaches. We evaluate RunSoC 2.0 using synthetic automotive task sets ranging from 10 to 500 tasks, mapped to representative heterogeneous MPSoCs, including the Renesas R-Car V4H, NVIDIA Jetson AGX Orin, and TI TDA4VM. The results show that RunSoC 2.0 can generate feasible and optimal schedules, expose architectural bottlenecks, and support rapid comparison of platform alternatives. Notably, CP-SAT consistently outperforms both CBC and the GA across tightly constrained hard real-time scheduling instances. By incorporating cluster-aware communication and memory modeling, RunSoC 2.0 improves the realism of early-stage MPSoC analysis while retaining practical solution times for large automotive workloads. (..)
1 Introduction
Centralized heterogeneous MPSoCs consolidate demanding automotive workloads but introduce strict timing, memory, communication, and mixed-criticality constraints. RunSoC 2.0 addresses the resulting task allocation and scheduling problem with heterogeneous, solver-based optimization.
- Centralized automotive platforms combine CPU, GPU, DSP, and specialized accelerators for demanding automotive workloads.
- Consolidation creates mixed-criticality environments where safety-critical and best-effort tasks coexist under strict timing, memory, and communication constraints.
- Automotive workloads are modeled as DAGs whose tasks must map to eligible processing elements while satisfying end-to-end latency bounds and avoiding resource contention.
- RunSoC 2.0 replaces RunSoC 1.0’s homogeneous heuristic allocation with multi-objective solver-based scheduling and allocation for heterogeneous MPSoCs.It models processor-specific execution times, cluster-aware memory and communication costs, task affinities, and end-to-end latency constraints.
2 Research Method and Related Work
RunSoC 2.0’s design was informed by literature and expert evidence, then positioned against existing modeling infrastructures. Its distinguishing feature is unified solver-based optimization across allocation, scheduling, memory, communication, and latency constraints.
- The framework design used a rapid literature review and semi-structured expert interviews conducted at Daimler Truck AG.The review followed PICOC criteria and examined task-core affinities, MPSoC partition properties, and scheduling/allocation approaches.
- The synthesized evidence identified metaheuristics as promising for scalability and hierarchical memory contention as a design-time bottleneck.
- AMALTHEA APP4MC provides extensive multicore modeling and analysis support but primarily functions as an infrastructure rather than an integrated optimization framework.
- RunSoC 2.0 combines task allocation, scheduling, memory-budget violations, communication costs, and end-to-end latency constraints in one solver-based optimization.
3 RunSoC 2.0 Framework Overview
RunSoC 2.0 converts structured task and platform descriptions into constrained scheduling instances, performs a utilization-based feasibility pre-check, and solves task-level allocation and scheduling jointly. Its objective penalizes hierarchical memory overflow and communication costs while hard constraints enforce assignment, timing, precedence, and non-overlap.
- The framework pipeline comprises platform and task description, problem parsing, feasibility pre-checking, and solver execution.
- Platform inputs capture clusters, cores, execution-time scalars, memory budgets, supported domains, and optional communication paths, while tasks specify execution and dependency properties.
- Periodic tasks define chain releases, while event-triggered successors activate after predecessor completion; dependency chains must meet end-to-end latency constraints.
- Optional parameters tune memory-penalty scaling, default communication penalties, and maximum task-chain release jitter.
- A utilization-bounded bin-packing pre-check balances maximum core utilization and can provide the main solver with an initial hint.
- The objective minimizes weighted memory overflows at core and cluster levels plus communication penalties scaled by hardware locality.
- Hard constraints enforce exact assignment, resource accounting, release and deadline bounds, precedence, and non-overlap of jobs on each core.Memory demand is counted once per task assignment, whereas timing constraints apply to each generated job.
- CBC and CP-SAT translate the ILP formulation directly, whereas GA requires task schedules to be encoded as chromosomes.
4 Experimental Design
The evaluation uses synthetic automotive DAG workloads spanning 10 to 500 tasks and maps them onto three representative heterogeneous MPSoCs. Solver comparison measures feasibility and solution quality under a 1000-second timeout, with non-completions treated as timeout-related rather than proven infeasibility.
- Synthetic DAG workloads derived from WATERS15 statistical properties were used because production automotive task sets are largely proprietary.
- Workloads span task-set sizes of 10, 25, 50, 100, 200, and 500 tasks to test framework scalability.
- Generated task WCETs follow a realistic Weibull distribution, and DAGs include cause-effect chains to test hard real-time requirements.
- The workloads are mapped onto Renesas R-Car V4H, NVIDIA Jetson AGX Orin, and Texas Instruments TDA4VM heterogeneous MPSoC models.
- Platform modeling enforces processor-domain and core-affinity constraints while targeting hierarchical memory-budget violations and cross-core or cross-cluster communication penalties.
- 1000 seconds was the solver timeout, and runs without feasible solutions were counted as unsuccessful feasibility results rather than proven infeasible.Runtime plots requiring completed results omit timeout cases.
- The experiments compare CBC, CP-SAT, and GA on feasible, optimal, or near-optimal schedules within the timeout.
5 Results
CP-SAT showed the strongest scalability and feasibility across the benchmark, while GA and CBC were limited to smaller instances. Objective comparisons require caution because solver coverage differed, and memory pressure dominated returned schedules.
- CP-SAT was the only solver to scale across the full benchmark range, solving all instances up to 100 tasks and retaining 93.3% feasibility at 500 tasks.Its median runtime increased from 0.043s at 10 tasks to 202.71s at 500, remaining below the 1000s timeout.
- GA was competitive only on small instances, while CBC frequently timed out and was usable only on very small cases.GA succeeded only through 50 tasks; CBC reached median runtimes of 30s and 100s at 10 and 25 tasks.
- CP-SAT’s scalability advantage persisted after periodic chains were expanded into concrete jobs, while GA and CBC terminated at substantially smaller schedules.
- Feasibility and runtime are the primary scalability metrics because CBC and GA did not cover the same instance set as CP-SAT.Objective quality was considered only for instances where a solver returned a feasible schedule, avoiding right-censored aggregate comparisons.
- CP-SAT consistently matched the best-known objective values on commonly solved small instances, whereas GA’s solution quality degraded as task count increased.GA’s limitation combined poor runtime scaling with increasing failure to converge to competitive schedules under the fixed timeout.
- Memory pressure dominated soft-constraint costs, while communication penalties were negligible in most returned schedules.For CP-SAT, the median memory penalty rose from 82 at 10 tasks to 85,820 at 500; this reflects the current benchmark and penalty calibration.
6 Conclusion and Outlook
RunSoC 2.0 supports early-stage scheduling and allocation analysis for heterogeneous automotive MPSoCs, while comparing solver backends and exposing architectural bottlenecks. CP-SAT showed the strongest overall behavior, and memory pressure emerged as the dominant cross-platform bottleneck.
- Conclusion: RunSoC 2.0 generates feasible schedules, compares solver backends, and exposes architectural bottlenecks during early design.The framework models heterogeneous platforms with processor-specific execution times, task affinities, cluster-aware communication costs, hierarchical memory budgets, and end-to-end latency constraints.
- Solver comparison: CP-SAT scaled to the largest task sets while maintaining practical runtimes and high solution quality.CBC’s low returned-feasible-solution rate mainly reflected early timeouts, whereas the GA degraded in runtime and solution quality on larger instances.
- Architectural bottlenecks: Memory pressure emerged as the dominant bottleneck across evaluated platforms, making memory-aware mapping essential for centralized automotive MPSoCs.
- Outlook: Future work will extend the platform model with memory-bandwidth constraints, bus contention, finer-grained communication semantics, and additional workload characteristics.Planned extensions include sporadic and interrupt-driven tasks, mixed-criticality constraints, cache-related preemption delays, industrial task sets, and hybrid solving strategies.