WorksComputer Science
HeteroTask: Multi-Variant Task Scheduling and Execution on Distributed Heterogeneous Clusters
Abstract
Heterogeneous systems that combine CPUs and GPUs across multiple servers offer substantial compute capability but complicate scheduling. For DAG-based applications with multiple task implementations, effective execution requires coordinating variant selection, device placement, and data movement. Offline planning can exploit global dependency information, yet plans derived from isolated kernel profiles may diverge from execution because of runtime overheads. We introduce HeteroTask, a framework integrating kernel-wise profiling, PEFT-based multi-variant planning, host-buffer lifetime modeling, and schedule-driven MPI execution. A Bayesian-optimization loop calibrates empirical overhead corrections for repeated, fixed-DAG workflows on exclusively allocated nodes. We evaluate five benchmark and workflow-derived applications on up to six 8-GPU nodes. On two 8-GPU nodes, HeteroTask reduces application-level completion time by 19.7-72.1% relative to the compared StarPU implementations. For Canny Edge Detection, calibration reduces task-window makespan by 25.0% relative to planning without overhead corrections. Combined with CPU/GPU variant selection, calibration reduces it by 58.9% relative to an uncalibrated GPU-only execution.
Introduction
Heterogeneous systems combine CPUs and GPUs to accelerate applications with different computational requirements [1], [2]. For a workflow represented as a directed acyclic graph (DAG), each task may have several implementations with different costs. Scheduling must decide which implementation to run, where, and how to move its inputs across devices and servers. These decisions interact: a fast kernel can be a poor placement if its transfers delay downstream tasks or its intermediate buffers increase memory pressure.
When the full DAG and input shapes are known, offline planning can coordinate these choices across the application. Its effectiveness, however, depends on how well the planned execution survives contact with the runtime. Isolated kernel measurements do not capture every launch, synchronization, and data-management cost. Figure 1 illustrates this gap for ten batched Canny Edge Detection (CED) instances on two 8-GPU nodes. A plan based on isolated profiles and a zero-overhead vector predicts 4.584 s, whereas its execution takes 11.334 s. Closing this gap requires attention to both the planning model and the executor that realizes its decisions.
Figure 1. (a) PEFT schedule without overhead calibration. (b) Actual runtime execution by applying the same schedule. Uncalibrated plan/execution gap on two 8-GPU nodes. Total spans are 4.584 s (plan) and 11.334 s (execution), including two virtual tasks omitted from the 50 visible rows. Rows are ordered by task name, not topological ID.
Offline heuristics such as HEFT and PEFT exploit complete dependency and cost information [3], [4]. Task runtimes such as
as StarPU, Taskflow, PaRSEC, and Legion provide mechanisms for heterogeneous execution and runtime placement [5]–[8]. Static knowledge and online adaptation offer complementary advantages [9], [10]. HeteroTask focuses on repeated workflows whose DAG structure, task shapes, and available implementations are fixed, on exclusively allocated nodes. Under these conditions, an offline plan can be reused, and a schedule-driven runtime can preserve its placement decisions while resolving dependencies and communication.
We present HeteroTask, an end-to-end framework that connects kernel-wise multi-variant profiling, PEFT-based planning, host-buffer lifetime modeling, and distributed MPI execution. A runtime-feedback loop uses Bayesian optimization (BO) to calibrate empirical overhead terms and regenerate plans. The framework carries task, buffer, and placement information through these stages, connecting the scheduler’s view of a workflow to the operations needed to execute it. HeteroTask builds on established PEFT and BO methods. Its contribution is their integration with multi-variant profiling, buffer modeling, and MPI execution, together with an evaluation of the integrated system.
Our evaluation covers five benchmark and workflow-derived DAGs on up to six nodes and 48 GPUs. On two 8-GPU nodes, the selected HeteroTask executions have lower application-level completion times than the compared StarPU configurations across all five workloads. The reductions range from 19.7% to 72.1% when the additional faster CED baseline is included. § 7-D describes the conditions of that baseline. The CED study also shows the value of exposing both CPU and GPU variants and of accounting for overheads in planning. At the same time, the measurements distinguish three objectives that need not improve together: model agreement, task-window makespan, and application-level completion time.
The paper makes three contributions:
An integrated execution framework for fixed heterogeneous workflows. HeteroTask connects per-variant profiles, communication estimates, and host-buffer metadata to placement and schedule-driven MPI execution.
A runtime-feedback calibration mechanism. Empirical corrections account for effects beyond isolated profiles. For CED, the selected vector reduces task-window makespan by 25.0% relative to the zero-overhead vector and by 3.5% relative to the initial nonzero vector.
A system-level evaluation across five workflows. End-to-end timing, a CPU/GPU variant study, and fixed-work resource sweeps show where integrated planning and execution are effective. They show that model agreement, task-window makespan, and application completion time respond differently to calibration and allocation.
Section IV defines how executions were measured and selected, and Section VI states the scope of the evidence. Profiling and calibration are preparation costs, so the value of plan reuse depends on the per-invocation savings and on how often the workflow runs.
Related Work
Offline DAG Scheduling
HEFT ranks tasks and then selects processors using estimated finish times [3]. PEFT adds optimistic downstream-cost lookahead [4]. Other heuristics explore placement consequences [11], constrained critical paths [12], prediction-based prioritization [13], or task duplication [14]. Genetic algorithms [15] and hybrid discrete particle-swarm optimization [16] search a broader space of candidate schedules. These methods provide different ways to construct an assignment from a cost model. HeteroTask uses PEFT as its planning substrate and focuses on supplying that model with multi-variant profiles and runtime-calibrated costs, then realizing the resulting plan in a distributed executor.
Task Runtimes and Variant Selection
StarPU expresses heterogeneous tasks as multi-variant codelets and uses performance models to guide runtime decisions [5]. Taskflow, PaRSEC, and Legion provide related mechanisms for task-based execution, dependency management, and heterogeneous placement [6, 7, 8]. Such runtimes can react to observed readiness and resource availability. HeteroTask instead preserves an offline mapping under a fixed-workflow, exclusive-allocation contract. Comparative work on heterogeneous Cholesky factorization shows the value of static knowledge even under estimation error [9], while recent WORKS research adapts classic heuristics to online execution with partial graph knowledge [10]. These studies place HeteroTask within a broader spectrum of trade-offs between global planning and runtime adaptation.
Variant selection also arises below the distributed workflow level. MLCD selects code-version/device pairs using input characteristics [17], and FlexTensor explores tensor implementation schedules on heterogeneous hardware [18]. HeteroTask coordinates the selection of available task variants with placement and communication across a complete DAG.
Workflow Systems and Performance Calibration
Pegasus manages distributed scientific workflows [19]. Ray supports distributed task and actor execution [20], and Dask distributed schedules task graphs with data-locality awareness [21]. These systems address broader orchestration needs, while HeteroTask concentrates on kernel-wise placement and execution within an allocated CPU–GPU cluster. Workflow performance-characterization research combines task provenance with I/O and operating-system observations [22], reinforcing the importance of measuring the whole application rather than its task region alone.
Gaussian-process BO provides a method for tuning expensive black-box objectives [23], and constrained BO incorporates uncertain feasibility conditions [24]. HeteroTask applies these principles to empirical overhead parameters: each candidate generates a plan whose execution supplies timing and alignment feedback. The resulting loop connects the planning model to observed system behavior. Our evaluation studies this integration with PEFT and the MPI runtime.
HeteroTask Framework Design
Overview
Figure 2 shows the overall workflow of HeteroTask. Given a fixed DAG-form application and an exclusively allocated heterogeneous system, HeteroTask follows an end-to-end profile–schedule–execute pipeline. The profiler first measures kernel-wise properties of each task variant on each device, including execution cost, resource metadata, and dataflow information. These measurements are then used by the offline scheduler, which decides task placement across servers and devices, code-variant selection, and data movement with communication estimates and host-buffer lifetime checks. The scheduling design space includes code variants for different backends, such as CPU/OpenMP, GPU/OpenMP, and CUDA.

Figure 2. HeteroTask’s profile–schedule–execute pipeline on an exclusively allocated heterogeneous system. The runtime preserves the offline mapping and uses host-buffer metadata to construct dependency-driven allocation/release events. Plan–trace comparison feeds overhead calibration and regeneration of the offline plan.
The resulting schedule is executed by a lightweight C++/MPI runtime that preserves the offline assignments, manages buffers and transfers, and enforces dependencies and synchronization. Runtime traces then feed a BO loop that adjusts overhead parameters and regenerates the plan. Offline-Runtime Co-Validation in Figure 2 is this plan–trace comparison: predicted and observed timings for a candidate plan are compared during calibration. This feedback connects the planner’s cost estimates to the executor’s behavior.
Kernel-wise Profiling Design
HeteroTask uses kernel-wise profiling to feed the offline scheduler with device-specific execution data. An MPI-based workflow automatically traverses all server nodes, profiles all hardware components, and merges the results into a single profile description, giving the user a unified interface.
For each task variant on each device, the profiler logs latency and resource metadata. CPU variants also capture thread configuration, while GPU variants are bound to explicit devices per server. The profiled task input sizes are part of the scheduling contract and must match the later execution. Device-transfer and inter-server bandwidth measurements are stored in the system configuration and reused by the scheduler. Beyond timing measurements, HeteroTask constructs task-level dataflow metadata that describes input/output buffers, dependency destinations, and buffer sizes. Consequently, the profiling phase returns both execution costs and the graph structure needed for the planner.
Offline Scheduling Design
The offline scheduler takes per-variant profiling data, the application DAG, the target system configuration, and a tunable overhead vector (calibrated in Section III-E) as inputs. Represent the application DAG as , where is the set of tasks and is the set of directed data-dependency edges. For each task , let be its available code variants, and let be the set of CPU and GPU resources across all servers. Let denote a complete assignment, where and , and let be the assignment space defined by precedence, resource–variant compatibility, and communication requirements. The planning objective is
where is the predicted finish time of task under assignment and overhead vector , and is the resulting predicted makespan of the plan.
For a candidate placement , communication time is the buffer size divided by the measured bandwidth of each segment on the transfer path, summed over the segments. A transfer between two GPUs on one server passes through host memory. A cross-server transfer adds a device-to-host copy at a GPU source and a host-to-device copy at a GPU destination around the network segment. Runtime buffers reside in host memory, so an edge between consecutive tasks on the same GPU is also charged both copies. HeteroTask applies overhead corrections separately to dependency readiness and task duration. Let denote the partial schedule and let collect the fixed setup, source-buffer scheduling-progress, cross-device transition, and cross-server corrections associated with a predecessor edge. Then the dependency-ready time is
Here is the bandwidth-based transfer estimate, excluding the empirical corrections. The buffer term depends on the number of source-server output buffers whose consumers have not yet been assigned. It adds per buffer up to buffers and per buffer beyond . The progress term is times the fraction of tasks already scheduled. These quantities describe the partial plan: the former is distinct from simultaneous live-buffer count, and the latter from elapsed execution time. The availability search starts from and checks resource occupancy and provisional host-buffer intervals. Let be the returned start time and the isolated profile. For an ordinary computational task, the candidate finish time is
where is zero for CPU placements and the configured GPU-task correction otherwise, while is the CPU-or GPU-transition correction. Virtual entry/exit tasks receive separate handling. This separation lets the model account for overheads that delay input readiness as well as those that extend execution on a worker.
The planner also maintains output-buffer lifetime intervals for each server. During candidate evaluation, it compares the total buffer volume over these intervals with host-memory capacity:
where is the buffer’s server and is its host-memory capacity. GPU kernel variants allocate and release their own device storage. Thus, this server-level check is not a per-GPU live-residency constraint. For every plan evaluated in this paper that has a retained planning log, the post-planning scan reports no host-capacity violation. (7) is a planning check, not a certified bound on execution memory.
PEFT ranks tasks using an optimistic cost table (OCT) and chooses placements by combining candidate finish time with downstream lookahead. HeteroTask evaluates resource–variant pairs using the profiled costs, empirical corrections, and host-buffer checks above. It can additionally compare enabled CPU-only and GPU-only plans by predicted makespan. Algorithm 1 summarizes candidate evaluation for ordinary tasks. Virtual entry and exit tasks are anchored to the master CPU. The output consists of the selected mapping, predicted timing, and buffer metadata consumed by the runtime.
Runtime Execution Design
The HeteroTask runtime executes the offline schedule and associated memory timeline while handling dependency tracking, communication, and synchronization across MPI ranks. MPI rank 0 maintains global state and dispatches tasks. Each server contributes one CPU worker rank and one worker rank per selected GPU. The CPU worker invokes the configured threaded variant internally. This centralized design provides a simple schedule-preserving control path for the evaluated applications. Dispatch follows three principles:
Dependency and Communication Orchestration: Before dispatch, the master checks predecessor completion, buffer allocation, and input locality, then issues the required point-to-point transfers and prefetches.
Schedule-Preserving Delay Propagation: In the default schedule-timed mode, tasks wait for their planned start and dependencies. Delays postpone dependents without
Algorithm 1 Multi-variant candidate evaluation with PEFT.
Input: DAG, resources, variants, profiles, bandwidths, host capacities,
Output: mapping, predicted times, provisional host-buffer timeline
Compute OCT and a precedence-respecting PEFT order
Initialize resource intervals, host-buffer intervals, and partial schedule
for each ordinary task in order do
for each compatible resource–variant pair do
if then
Record as the best candidate
Commit candidate and update resource and host-buffer intervals
return mapping, times, and host-buffer metadata
changing placement. The optional smart mode can release ready tasks earlier but does not remap them.
Dependency-Driven Host-Buffer Management: Producer and consumer metadata define when buffers must be available and can be released. Allocation and release events are ordered by these dependencies, so buffer lifetimes follow actual progress rather than predicted timestamps. Worker buffers reside in host memory, while GPU variants manage their own device allocations.
In the C++/MPI runtime, large point-to-point transfers are automatically split into multiple MPI messages and reassembled at the receiver, avoiding single-message limits while preserving the applications’ logical buffer abstraction.
Runtime-Feedback Calibration via Bayesian Optimization
Real executions introduce launch, buffer-management, device-switch, and cross-server effects that isolated profiles do not capture. HeteroTask represents them with and calibrates this vector through the offline–runtime Bayesian-optimization (BO) loop in Figure 3.

Figure 3. Runtime-feedback calibration. Plan–trace errors guide search. The final selection rule determines whether model-alignment thresholds constrain the chosen plan.
For each candidate , let be the assignment produced by the offline scheduler and executed by the runtime. Define , and let be the measured runtime makespan of that assignment. The relative makespan error is
For task-level alignment, let be the tasks observed in both traces, with denoting their number. For each , let be its selected resource–variant pair in . Then and are its predicted start and finish times, while and are @page 4/11 starts_mid=1 ends_mid=1 the partial plan: the former is distinct from simultaneous live-buffer count, and the latter from elapsed execution time. The availability search starts from and checks resource occupancy and provisional host-buffer intervals. Let be the returned start time and the isolated profile. For an ordinary computational task, the candidate finish time is
where is zero for CPU placements and the configured GPU-task correction otherwise, while is the CPU-or GPU-transition correction. Virtual entry/exit tasks receive separate handling. This separation lets the model account for overheads that delay input readiness as well as those that extend execution on a worker.
The planner also maintains output-buffer lifetime intervals for each server. During candidate evaluation, it compares the total buffer volume over these intervals with host-memory capacity:
where is the buffer’s server and is its host-memory capacity. GPU kernel variants allocate and release their own device storage. Thus, this server-level check is not a per-GPU live-residency constraint. For every plan evaluated in this paper that has a retained planning log, the post-planning scan reports no host-capacity violation. (7) is a planning check, not a certified bound on execution memory.
PEFT ranks tasks using an optimistic cost table (OCT) and chooses placements by combining candidate finish time with downstream lookahead. HeteroTask evaluates resource–variant pairs using the profiled costs, empirical corrections, and host-buffer checks above. It can additionally compare enabled CPU-only and GPU-only plans by predicted makespan. Algorithm 1 summarizes candidate evaluation for ordinary tasks. Virtual entry and exit tasks are anchored to the master CPU. The output consists of the selected mapping, predicted timing, and buffer metadata consumed by the runtime.
Runtime Execution Design
The HeteroTask runtime executes the offline schedule and associated memory timeline while handling dependency tracking, communication, and synchronization across MPI ranks. MPI rank 0 maintains global state and dispatches tasks. Each server contributes one CPU worker rank and one worker rank per selected GPU. The CPU worker invokes the configured threaded variant internally. This centralized design provides a simple schedule-preserving control path for the evaluated applications. Dispatch follows three principles:
Dependency and Communication Orchestration: Before dispatch, the master checks predecessor completion, buffer allocation, and input locality, then issues the required point-to-point transfers and prefetches.
Schedule-Preserving Delay Propagation: In the default schedule-timed mode, tasks wait for their planned start and dependencies. Delays postpone dependents without
Algorithm 1 Multi-variant candidate evaluation with PEFT.
Input: DAG, resources, variants, profiles, bandwidths, host capacities,
Output: mapping, predicted times, provisional host-buffer timeline
Compute OCT and a precedence-respecting PEFT order
Initialize resource intervals, host-buffer intervals, and partial schedule
for each ordinary task in order do
for each compatible resource–variant pair do
if then
Record as the best candidate
Commit candidate and update resource and host-buffer intervals
return mapping, times, and host-buffer metadata
changing placement. The optional smart mode can release ready tasks earlier but does not remap them.
Dependency-Driven Host-Buffer Management: Producer and consumer metadata define when buffers must be available and can be released. Allocation and release events are ordered by these dependencies, so buffer lifetimes follow actual progress rather than predicted timestamps. Worker buffers reside in host memory, while GPU variants manage their own device allocations.
In the C++/MPI runtime, large point-to-point transfers are automatically split into multiple MPI messages and reassembled at the receiver, avoiding single-message limits while preserving the applications’ logical buffer abstraction.
Runtime-Feedback Calibration via Bayesian Optimization
Real executions introduce launch, buffer-management, device-switch, and cross-server effects that isolated profiles do not capture. HeteroTask represents them with and calibrates this vector through the offline–runtime Bayesian-optimization (BO) loop in Figure 3.
For each candidate , let be the assignment produced by the offline scheduler and executed by the runtime. Define , and let be the measured runtime makespan of that assignment. The relative makespan error is
For task-level alignment, let be the tasks observed in both traces, with denoting their number. For each , let be its selected resource–variant pair in . Then and are its predicted start and finish times, while and are their measured runtime counterparts. The normalized average start- and finish-time deviations, and , are
We use weights to give greater weight to overall makespan agreement. The start- and finish-time terms penalize a vector whose predicted makespan matches the execution while individual tasks start or finish at different times. Unlike the makespan-only error above, the makespan term inside alignment is normalized by the observed runtime makespan. The alignment error is
The search models task-window makespan and both errors with Gaussian-process regressors using Matérn kernels. It proposes candidates using expected improvement over the fastest observation that meets the current thresholds, or the fastest overall if none does, weighted by estimated threshold-feasibility probabilities, following established GP-based and constrained BO principles [23], [24]. The feasibility probability is the product of the probabilities that each error meets its threshold. Each observation requires generating and executing a plan, making sample efficiency an important consideration.
Search begins with loose error thresholds and expands parameter bounds when too few candidates satisfy them. Subsequent rounds narrow the bounds around promising groups and tighten the thresholds. This process combines exploration with progressively stronger requirements on model agreement. Each round refits the regressors to all earlier observations and reclassifies them under its own thresholds, so tightening the thresholds reuses earlier executions rather than discarding them.
Algorithm 2 Runtime-feedback calibration with BO.
Input: parameter bounds , seed parameters , threshold schedule
Output: selected overhead parameters
▷ initial vector, zero reference, and samples
for each threshold pair in the schedule do
while true do
for each do
if is too small then
else
break
\theta^*\leftarrow\operatorname{SelectFinalTheta}(D,\operatorname{final\mathchar`-choice}) ▷ fastest threshold-feasible or fastest observed
Save and its plan for subsequent executions
return
them. An execution marked as failed or timed out enters the dataset with penalty values and counts as infeasible. Table III lists the coefficients of and the initial bounds from which this refinement starts. The coefficients jointly correct the planning model rather than represent independently measured hardware latencies. For CED, the search evaluates 62 vectors in five rounds. The first round contains 22 vectors, including the initial nonzero vector and a zero-overhead reference, and each subsequent round evaluates ten. The thresholds on and are , , , , and in the five rounds.
| Symbol | Model role | Unit | Initial range | CED selected |
| Fixed dependency correction | ms | [0,1000] | 155.0 | |
| Buffer-count threshold | count | [0,20] | 2.0 | |
| Per-buffer correction | ms/buffer | [0,200] | 4.0 | |
| Buffer-cost growth factor | dimensionless | [0,10] | 1.2 | |
| GPU-task correction | ms | [0,500] | 14.9 | |
| Scheduling-progress multiplier | dimensionless | [0,5] | 0.0 | |
| Progress scale before multiplier | ms | [0,10000] | 1038.4 | |
| CPU-task transition correction | ms | [0,5000] | 288.9 | |
| GPU-task transition correction | ms | [0,5000] | 172.4 | |
| Cross-device edge correction | ms | [0,5000] | 641.1 | |
| Cross-server data correction | ms/GiB | [0,2000] | 231.0 |
Table III. Empirical overhead parameters: initial search ranges and selected CED values. Symbols name model coefficients, not independently measured hardware latencies.
Final selection depends on the objective of plan reuse. One option selects the fastest observed candidate satisfying both final error thresholds. Another selects the fastest observed execution regardless of alignment. The evaluated CED and two-node 3MM searches use the second option. CED’s selection also meets the error thresholds, while 3MM’s does not (§ 7). These thresholds concern model agreement, not execution correctness or memory capacity. Algorithm 2 makes the final selection rule explicit.
The selected vector and plan can be reused while the workflow, input shapes, allocation, and execution conditions remain sufficiently stable. This shifts profiling, search, and candidate execution into a preparation phase. § 7 considers the cost of this preparation alongside per-invocation performance.
Application Integration Example
To integrate an application, the developer supplies task variants, buffer declarations, and wrappers that connect inputs and outputs to each kernel. For CED, a Gaussian-filter task consumes an image buffer and produces an intermediate image for downstream stages. Profiling records the variants’ costs, buffer sizes, and consumers. The planner selects a server, device, and variant, and the runtime invokes that variant with its buffers while handling dependency events and inter-rank movement. The same task and dataflow description supports profiling, placement, and execution. Application kernels remain separate from distributed orchestration.

Figure 4. DAGs of the five C++ applications used in evaluation. 3MM, CED, and SBF are transformed into 10-instance batched DAGs via automatic pipeline unrolling. 3MM and SBF share the same unrolled topology, so it is shown once in (a). Montage and CyberShake use Pegasus-generated DAGs with irregular dependencies.
| Property | 3MM | CED | SBF | Montage | CyberShake |
| Domain | Dense LA | Image proc. | Image proc. | Sci. workflow | Sci. workflow |
| Tasks | 32 | 52 | 32 | 21 | 52 |
| Edges | 50 | 60 | 50 | 42 | 98 |
| Workload setting | 10-way batch | 10-image batch | 10-image batch | 1 workflow inst. | 1 workflow inst. |
| Declared output-buffer volume | 4.25 GiB | 68.16 GiB | 81.72 GiB | 949.31 MiB | 1.30 GiB |
| Largest buffer | 128.00 MiB | 2.71 GiB | 2.71 GiB | 98.88 MiB | 329.76 MiB |
Table 1. Workload characteristics. Declared output-buffer volume counts each task’s first available profile once. It is not the peak resident memory of an execution.
Experimental Setup
Platform and Workloads
We evaluate HeteroTask on allocations drawn from six nodes, each configured with an AMD EPYC 7763 64-core CPU, 1 TB of host memory, and eight NVIDIA A100-SXM4 GPUs with 80 GB each. Allocations range from one node with one GPU to six nodes with eight GPUs per node. The node type is uniform, so the evaluated heterogeneity is between CPU and GPU resources. The two-node CED execution uses 19 MPI ranks: a master and one CPU worker plus eight GPU workers per node. The inspected software snapshot specifies Clang 18.1.3, NVIDIA HPC SDK 26.1, CUDA 13.1, and a StarPU 1.4 interface. These versions describe that snapshot rather than a recovered binary manifest for each run.
CED, Sobel Filter (SBF), and 3MM use ten pipeline instances unrolled into a single DAG [25]. Montage and CyberShake retain Pegasus-generated dependency structures with workflow-derived operators [19]. They do not execute the complete production applications through Pegasus. The five DAGs contain 21–52 tasks, including virtual entry and exit tasks, and cover regular pipelines as well as irregular dependency structures. We size the DAGs so that repeated profiling, baseline tuning, and BO calibration fit within the cluster’s fixed job wall time, because a larger DAG leaves less time per kernel and makes kernel measurements more sensitive to noise. Table I reports their characteristics. Declared output-buffer volume describes the graph’s data objects, not live memory or peak GPU usage.
StarPU Baselines
The distributed StarPU implementations use the same underlying application kernels with StarPU-specific data-handle wrappers. We compare modes exposing CPU/OpenMP and CUDA codelets with modes restricted to CUDA codelets. The experiment protocol explores dmda, eager, and heft, with five warm-up runs followed by 8–15 formal runs and a stability check over the trailing five measurements. Policy names denote recorded configurations. Different names alone do not imply different scheduling algorithms.
CED and SBF use explicit data partitioning and bounded pipelining in StarPU. These choices make the large-image workloads executable but change task granularity and data placement. HeteroTask’s benchmark-style GPU variants include host–device transfers inside tasks, whereas StarPU can stage and reuse data outside codelet bodies. The application-level comparison therefore combines the effects of placement, data management, and runtime orchestration.
Measurements and Configuration Selection
Application end-to-end (E2E) time spans initialization and input setup through completion synchronization and output recovery. The task window spans the first scheduled task start to the last task completion. Start/setup and end/recovery are derived from each implementation’s trace markers and represent broad phases, not matched microcomponents. Profiling, offline planning, and BO calibration are excluded from invocation E2E and discussed separately as preparation costs.
The available results retain selected execution traces rather than the complete repeated-run series. We therefore report point measurements, without treating plotted bars as verified medians or adding confidence intervals. The CED result selected by HeteroTask is also an observation used during calibration, and independent post-selection repeats are unavailable. BO evaluations with different overhead vectors are different configurations, not repetitions of one configuration.
Figure 7 compares the selected CPU+GPU and CUDA-only StarPU executions with HeteroTask on two nodes. An additional CED execution has lower StarPU E2E and is shown to assess sensitivity to baseline selection. For the resource sweep, each allocation uses the lowest available StarPU E2E and the selected HeteroTask invocation. Full input, build, and correctness equivalence is not documented for every configuration, so these comparisons characterize the measured implementations rather than a best achievable baseline.
Figure 7. Application-level timing on two 8-GPU nodes. CPU+GPU and CUDA-only denote StarPU modes. Start/setup, task-window, and end/recovery boundaries follow each implementation’s markers. The hatched CED bar is the additional CUDA-only/heft execution. The CyberShake CPU+GPU result is unavailable and omitted.
We cross-check timing summaries against logs, verify phase sums, and recompute calibration errors from matched task traces. Reductions are calculated as , with the reference given for each comparison. All results are recomputed offline from the retained execution records, with no new application runs. Source code and supporting experiment materials have not yet been publicly released.
Results and Discussion
Calibration of Planning and Execution
The CED study connects the planning–execution gap in Figure 1 to the calibration mechanism. With zero overhead corrections, the plan predicts 4.584 s and executes in 11.334 s. After five search rounds evaluating 62 parameter vectors, the selected plan predicts 8.50346 s and executes in 8.50396 s. Figure 5 shows the resulting plan and execution timelines. In Figure 1 and Figure 5, the last visible computational task can end before the reported span, which includes the two omitted virtual tasks.

Figure 5. CED planning and variant-selection study on two 8-GPU nodes. The calibrated plan and CPU+GPU execution use the selected overhead vector, and the GPU-only execution uses the zero-overhead vector. Virtual entry/exit tasks are omitted from the visible rows but retained in the reported total spans. Rows use task-name ordering, not topological IDs. The CPU+GPU and GPU-only configurations differ in active computational resources.
The alignment errors in Table II cover all 52 CED tasks, including these two virtual tasks.
| Configuration | Task window (s) | Alignment error |
| Zero overhead | 11.334 | 2.293 |
| Initial nonzero | 8.814 | 0.108 |
| Selected | 8.504 | 0.111 |
Table II. CED configurations within the calibration study. Times are task-window measurements.
Relative to the zero-overhead configuration, the selected execution reduces task-window makespan by 25.0% and alignment error by 95.2%. The makespan error drops from 147.24% to 0.00592%. The planner predicts a longer execution after calibration because it accounts for additional costs, yet the resulting plan executes faster. This case illustrates why minimizing a prediction based only on isolated kernel costs can lead to a poor runtime result.
Table II also includes the initial nonzero vector, which already executes in 8.814 s. The final selection improves on this reference by 3.5%, while its alignment error is slightly larger. The 25.0% difference measures the benefit relative to the zero-overhead plan, whereas 3.5% measures the gain beyond the initial vector. The initial vector’s earlier preparation history is unknown. All three values are search observations. The near-zero final residual describes agreement on the selected execution, not prediction accuracy on unseen runs.
Calibration Search Trajectory
Table III gives the coefficient values of the selected CED vector. In this vector, the zero progress multiplier disables its progress-dependent term. Figure 6 shows the full search trajectory and the distinct behavior of execution time and alignment during tuning. The running minimum improves modestly, from 8.814 s for the initial nonzero vector to 8.560 s in the third round and 8.504 s in the fifth, while individual task windows reach 262.610 s. Every second-round candidate takes at least 47.178 s, whereas all 30 candidates in the last three rounds finish within 8.504–14.758 s. All 61 candidates other than the zero-overhead reference meet the final error thresholds, so these thresholds alone do not identify the fastest plan. This separation motivates evaluating measured speed alongside model agreement rather than using alignment alone to select a plan.
Figure 6. CED calibration over 62 candidate evaluations. Left: task-window makespan and running minimum. Right: alignment error. Vertical lines separate search rounds. The initial nonzero vector already has low execution time, while some slower candidates have small alignment errors.
Value of Heterogeneous Variant Selection
Restricting all computational CED tasks to GPU variants under the zero-overhead vector yields a task window of 20.703 s. Without calibration, enabling CPU variants on the same two-node allocation reduces the task window to 11.334 s, a 45.3% reduction. The calibrated CPU+GPU execution completes in 8.504 s and assigns to CPUs 14 computational tasks from all five CED stages (Gaussian filter 2, gradient 2, edge thinning 4, double thresholding 3, hysteresis 3), excluding the two virtual tasks. Relative to the uncalibrated GPU-only execution, its 58.9% reduction combines variant selection and calibration. The timelines in Figure 5 show how these assignments distribute work beyond the GPU workers and permit additional overlap.
This comparison demonstrates the value of exposing the full heterogeneous allocation, including its CPU cores as additional compute resources, to the planner for CED.
End-to-End Workflow Performance
On two 8-GPU nodes, the selected HeteroTask invocations have lower E2E than the compared StarPU configurations for all five workloads. Of the two selected StarPU modes, CUDA-only is faster for 3MM, CED, and SBF, whereas CPU+GPU is faster for Montage by only 0.4% and CyberShake has only a CUDA-only result. Against the faster selected StarPU mode, the reductions are 59.7% for 3MM, 54.7% for CED, 58.4% for SBF, 72.1% for Montage, and 59.1% for CyberShake. Including the additional faster CED baseline changes CED’s reduction to 19.7%, and the resulting five-workload range is 19.7–72.1%. SBF illustrates variant selection: the planner chooses its all-CPU plan, which runs on one node.
The phase breakdown explains why application-level timing matters. For 3MM, CED, and SBF, a compared StarPU configuration has a shorter task window but a longer E2E than HeteroTask. For Montage and CyberShake, HeteroTask also has the shorter task window: 2.290 s against 21.219 s and 22.110 s for the two StarPU modes, and 13.644 s against 30.807 s. Data movement and management occur at different points in the two implementations. HeteroTask’s selected CED invocation, for example, comprises 30.881 s of start/setup, 8.504 s of task execution, and 0.666 s of end/recovery. Its task window is only part of the total cost. Start/setup is the largest HeteroTask phase for four of the five workloads, at 77.1–92.1% of E2E, whereas CyberShake’s task window exceeds its 11.875 s start/setup. The E2E advantage thus reflects integration across planning, data handling, and execution, not the scheduling heuristic alone.
The two CED StarPU configurations make the selection issue concrete. The selected CUDA-only/dmda execution has a 0.926 s task window and 88.438 s E2E. The additional CUDA-only/heft execution has a longer task window of 1.643 s but a shorter E2E of 49.879 s. Both contain 800 partitioned task records for ten images. Figure 7 shows the phases of both executions. This supports using application E2E to choose a runtime configuration and prevents the shorter task window from being mistaken for the stronger baseline.
Resource Allocation at Fixed Workload Size
Figure 8 extends the comparison to all five workloads over allocations up to six nodes and 48 GPUs. Against the lowest available StarPU E2E at each allocation, HeteroTask has the lower measured E2E at 33 of the 35 plotted application–allocation points, including every plotted allocation for 3MM, SBF, Montage, and CyberShake. CED is more sensitive to allocation and baseline selection, and both exceptions are CED on one node: with one GPU, the times are 47.670 s for HeteroTask and 47.157 s for StarPU, and StarPU is also faster with two GPUs. Across the plotted allocations, the lowest available StarPU CED E2E ranges from 40.8 s at to 93.7 s at . HeteroTask reduces E2E by 43.5–72.6% across the five workloads at and by 49.3–76.6% at . CyberShake’s reduction ranges from 49.3% at to 62.7% at . At each allocation, the planner keeps the plan with the shortest predicted makespan among the enabled PEFT, all-CPU, and all-GPU plans. It keeps the PEFT plan except for SBF at , , , and , where it keeps the all-CPU plan, and for 3MM at , where it keeps the all-GPU plan.
Figure 8. Application E2E across resource allocations at fixed workload size. Labels denote nodes GPUs per node. Each point uses the selected HeteroTask execution and the lowest available StarPU E2E.
Adding resources does not uniformly shorten these fixed DAGs. HeteroTask’s CED E2E is 40.1 s on two 8-GPU nodes, 47.3 s on four, and 44.0 s on six. The six-node CED plan places all tasks on one node. Its task window is 11.0 s, compared with 8.5 s on two nodes and 12.1 s on four. CyberShake benefits more from additional resources, although its largest allocation is not the fastest either. Its HeteroTask E2E is 105.8 s at , 25.0 s at , and 30.0 s at .
These curves characterize resource choices for a fixed application, rather than weak scaling or growing-DAG scalability. Each allocation uses its own selected configuration. For six-node SBF, Montage, and CyberShake, the execution traces cannot be linked unambiguously to the final calibration selections. We retain the measured application times but do not attribute those points to particular calibrated vectors.
Calibration Trade-offs and Plan Reuse
The 3MM study shows why calibration quality and execution speed must be evaluated separately. Its fastest observed two-node execution uses the zero-overhead vector and takes 1.498 s. The makespan error is 109.9% and alignment error is 2.405, outside the signal error thresholds. The fastest candidate satisfying those thresholds takes 7.457 s. The final selection prioritizes execution speed, so HeteroTask can produce a fast execution without a closely aligned model. The 3MM two-node result in Figure 7 uses this zero-overhead vector.
Calibration also has a preparation cost. The 62 CED evaluations accumulate 3718.506 s of task-window time. This sum excludes profiling, planning, invocation setup, and unrecorded failed work, and it is not elapsed calibration wall time. The initial nonzero vector already performs well, so the modest improvement beyond it motivates considering search effort alongside final execution time.
For repeated workflows, preparation is useful when subsequent savings outweigh its cost. Let and denote preparation costs, and let and be representative perinvocation times for HeteroTask and a baseline. Reuse is beneficial when
where is the number of invocations under the same execution conditions. The current measurements identify the quantities needed to choose between additional calibration, reuse of an existing plan, and a fresh planning run.
Limitations and Scope
Measurement and comparison. The results are selected executions, and the selected CED result has no independent post-selection repetition (Section IV-C). Despite shared kernels, the implementations differ in wrappers, partitioning, transfers, and worker configuration. The gains are relative to the recorded StarPU implementations and configurations.
Workload and execution scope. The study covers five 21–52-task DAGs on one CPU–GPU node type, with up to six nodes. It evaluates fixed graphs, matching task shapes, and exclusive allocations. The runtime preserves assignments and resolves dependencies but does not remap tasks online or support dynamic DAGs and failure recovery. Larger graphs, other platforms, and more baselines are needed to assess broader applicability and centralized-dispatch scalability.
Memory and reuse. Host-buffer lifetime modeling guides planning and dependency-driven allocation, while GPU kernels manage their own device storage. The evaluation contains neither a memory-planning ablation nor measured peak GPU residency. Likewise, preparation costs and independent invocation measurements are insufficient to quantify amortization. Reusing a plan requires stable workflow and execution conditions. The calibration gains are measured on CED.
Conclusion and Future Work
HeteroTask brings multi-variant profiling, offline placement, host-buffer lifetime modeling, and schedule-driven MPI execution into one framework. Runtime feedback calibrates the costs supplied to the planner, while shared task and buffer metadata connect the assignments to distributed execution. It targets repeated CPU–GPU workflows with known graphs and task shapes on exclusively allocated nodes.
Across five workflows, the selected two-node executions reduce application E2E by 19.7–72.1% relative to the compared StarPU configurations when the additional CED baseline is included. The CED study shows a 25.0% task-window makespan reduction relative to a zero-overhead plan and a 3.5% improvement over the initial nonzero configuration. Combined with CPU/GPU variant selection, calibration yields a 58.9% reduction relative to the uncalibrated GPU-only execution. Together, these results show the benefit of coordinating variant selection, planning, and runtime execution at the application level. The resource sweeps and the 3MM calibration case further show that model agreement, task-window makespan, and application completion time are distinct objectives that respond differently to calibration and allocation.
Future work will evaluate independently repeated executions with matched inputs and correctness checks, account for complete preparation costs, and test larger DAGs and memory-intensive cases. These measurements will help determine when a fixed plan is worth reusing and when changing execution conditions call for renewed profiling or runtime adaptation.
Acknowledgement
Language-model tools assisted with language editing, source organization, and checks of data-processing procedures. The authors are responsible for the analysis and conclusions.
References
References
- [1]S. Mittal and J. S. Vetter, “A survey of CPU-GPU heterogeneous computing techniques,” ACM Computing Surveys, vol. 47, no. 4, pp. 1–35, Jul. 2015. [Online]. Available: https://doi.org/10.1145/2788396
- [2]M. Alaei and F. Yazdanpanah, “A survey on heterogeneous CPU–GPU architectures and simulators,” Concurrency and Computation: Practice and Experience, vol. 37, no. 1, p. e8318, 2025. [Online]. Available: https://doi.org/10.1002/cpe.8318
- [3]H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 3, pp. 260–274, 2002. [Online]. Available: https://doi.org/10.1109/71.993206
- [4]H. Arabnejad and J. G. Barbosa, “List scheduling algorithm for heterogeneous systems by an optimistic cost table,” IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 3, pp. 682–694, 2014. [Online]. Available: https://doi.org/10.1109/TPDS.2013.57
- [5]C. Augonnet, S. Thibault, R. Namyst, and P.-A. Wacrenier, “StarPU: A unified platform for task scheduling on heterogeneous multicore architectures,” Concurrency and Computation: Practice and Experience, vol. 23, no. 2, pp. 187–198, 2011. [Online]. Available: https://doi.org/10.1002/cpe.1631
- [6]T.-W. Huang, D.-L. Lin, C.-X. Lin, and Y. Lin, “Taskflow: A lightweight parallel and heterogeneous task graph computing system,” IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 6, pp. 1303–1320, Jun. 2022. [Online]. Available: https://doi.org/10.1109/TPDS.2021.304255
- [7]G. Bosilca, A. Bouteiller, A. Danalis, T. Herault, P. Lemarinier, and J. Dongarra, “DAGuE: A generic distributed DAG engine for high performance computing,” Parallel Computing, vol. 38, no. 1–2, pp. 37–51, 2012, extensions for Next-Generation Parallel Programming Models. [Online]. Available: https://doi.org/10.1016/j.parco.2011.10.003
- [8]M. Bauer, S. Treichler, E. Slaughter, and A. Aiken, “Legion: Expressing locality and independence with logical regions,” in SC ’12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, 2012, pp. 1–11. [Online]. Available: https://doi.org/10.1109/SC.2012.71
- [9]E. Agullo, O. Beaumont, L. Eyraud-Dubois, and S. Kumar, “Are static schedules so bad? A case study on Cholesky factorization,” in 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2016, pp. 1021–1030. [Online]. Available: https://doi.org/10.1109/IPDPS.2016.90
- [10]J. Chamorro, G. Twigg-Ho, J. Coleman, T. Coleman, B. Krishnamachari, and M. Khodabandehloo, “Adapting classic scheduling heuristics for online execution under uncertainty,” in SC Workshops ’25: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2025, pp. 2169–2180. [Online]. Available: https://doi.org/10.1145/3731599.3767581
- [11]L. F. Bittencourt, R. Sakellariou, and E. R. M. Madeira, “DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm,” in 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing, 2010, pp. 27–34. [Online]. Available: https://doi.org/10.1109/PDP.2010.56
- [12]M. A. Khan, “Scheduling for heterogeneous systems using constrained critical paths,” Parallel Computing, vol. 38, no. 4, pp. 175–193, 2012. [Online]. Available: https://doi.org/10.1016/j.parco.2011.01.001
- [13]H. Djigal, J. Feng, J. Lu, and J. Ge, “IPPTS: An efficient algorithm for scientific workflow scheduling in heterogeneous computing systems,” IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 5, pp. 1057–1071, 2021. [Online]. Available: https://doi.org/10.1109/TPDS.2020.3041829
- [14]M. Sulaiman, Z. Halim, M. Waqas, and D. Aydin, “A hybrid list-based task scheduling scheme for heterogeneous computing,” The Journal of Supercomputing, vol. 77, no. 9, pp. 10252–10288, Sep. 2021. [Online]. Available: https://doi.org/10.1007/s11227-021-03685-9
- [15]F. A. Omara and M. M. Arafa, “Genetic algorithms for task scheduling problem,” Journal of Parallel and Distributed Computing, vol. 70, no. 1, pp. 13–22, 2010. [Online]. Available: https://doi.org/10.1016/j.jpdc.2009.09.009
- [16]M. Hosseini Shirvani, “A hybrid meta-heuristic algorithm for scientific workflow scheduling in heterogeneous distributed computing systems,” Engineering Applications of Artificial Intelligence, vol. 90, p. 103501, 2020. [Online]. Available: https://doi.org/10.1016/j.engappai.2020.103501
- [17]K. Cao, H. Ye, Y. Pang, and D. Chen, “MLCD: Machine learning-based code version and device selection for heterogeneous systems,” IEEE Transactions on Computers, vol. 74, no. 7, pp. 2417–2430, 2025. [Online]. Available: https://doi.org/10.1109/TC.2025.3558606
- [18]S. Zheng, Y. Liang, S. Wang, R. Chen, and K. Sheng, “FlexTensor: An automatic schedule exploration and optimization framework for tensor computation on heterogeneous system,” in Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS ’20. New York, NY, USA: Association for Computing Machinery, 2020, pp. 859–873. [Online]. Available: https://doi.org/10.1145/3373376.3378508
- [19]E. Deelman, K. Vahi, M. Rynge, R. Mayani, R. F. da Silva, G. Papadimitriou, and M. Livny, “The evolution of the Pegasus workflow management software,” Computing in Science & Engineering, vol. 21, no. 4, pp. 22–36, 2019. [Online]. Available: https://doi.org/10.1109/MCSE.2019.2919690
- [20]P. Moritz, R. Nishihara, S. Wang, A. Tumanov, R. Liaw, E. Liang, M. Elibol, Z. Yang, W. Paul, M. I. Jordan, and I. Stoica, “Ray: A distributed framework for emerging AI applications,” in 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). USENIX Association, 2018, pp. 561–577. [Online]. Available: https://www.usenix.org/conference/osdi18/presentation/moritzarxiv.org/abs/1712.05889
- [21]Dask Development Team, “Dask distributed,” 2026, accessed: 2026-10-16. [Online]. Available: https://distributed.dask.org/en/stable/
- [22]A. Gueroudji, C. Phelps, T. Z. Islam, P. Carns, S. Snyder, M. Dorier, R. B. Ross, and L. C. Pouchard, “Performance characterization and provenance of distributed task-based workflows on HPC platforms,” in SC24-W: Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 2024, pp. 2032–2039. [Online]. Available: https://doi.org/10.1109/SCW63240.2024.00254
- [23]J. Snoek, H. Larochelle, and R. P. Adams, “Practical Bayesian optimization of machine learning algorithms,” in Advances in Neural Information Processing Systems, vol. 25, 2012. [Online]. Available: https://papers.nips.cc/paper_files/paper/2012/hash/05311655a15b75fab86956663e1819cd-Abstract.htmlarxiv.org/abs/1206.2944
- [24]M. A. Gelbart, J. Snoek, and R. P. Adams, “Bayesian optimization with unknown constraints,” in Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence. AUAI Press, 2014, pp. 250–259. [Online]. Available: https://arxiv.org/abs/1403.5607
- [25]H. Tian, A. Mishra, Z. Chen, R. P. Hong Enriquez, D. Milojicic, E. Frachtenberg, and S. Huang, “HeteroBench: Multi-kernel benchmarks for heterogeneous systems,” in Proceedings of the 16th ACM/SPEC International Conference on Performance Engineering, 2025, pp. 320–333. [Online]. Available: https://doi.org/10.1145/3676151.3719366



