Dependency-Aware Scheduling for Parallel Nonlinear System Solving on Multicore Architectures
Informatica · 06.08.2026 · 50 (14)
DOI: 10.31449/inf.v50i14.10751 ↗Kurz gefasst
Fachartikel in der Zeitschrift Informatica, online erschienen am 06.08.2026. Verfasst von Adel Moussaoui und 4 weiteren Autor:innen.
Abstract (Originalsprache)
This paper presents a comprehensive experimental evaluation of ten Directed Acyclic Graph (DAG) scheduling algorithms for the parallel solution of decomposed nonlinear equation systems on multicore processors. Because parallel execution fundamentally depends on system decomposition, we abstract the decomposition stage and model the resulting task structures as DAGs. This abstraction enables systematic evaluation across diverse dependency patterns without restricting the study to a specific decomposition technique. We compare critical-path-aware, heuristic-based, and baseline schedulers across sparse, balanced, and dense DAGs on a multicore platform with 1, 2, 4, and 8 cores using real polynomial systems with O(n^3) computational complexity. Results show that structural decomposition alone yields speedups of 65–185× over monolithic solving, while parallel scheduling further amplifies these gains by 1.13–1.53x, producing total accelerations of 74–283x and reducing multi-hour computations to practical runtimes on commodity multicore hardware. No single scheduler consistently dominates across all structural regimes. Parallel efficiency is strongly dependency-dependent: sparse graphs scale effectively up to 4 cores, whereas balanced and dense graphs exhibit limited scalability beyond 2 cores as structural coupling and shared-memory constraints restrict available concurrency. These findings indicate that optimal performance requires aligning scheduler selection and core allocation with the dependency structure induced by decomposition.
Zitieren
APA
Moussaoui, A., Belhadj, F., Gueddoudj, E. Y., Bouamama, S., & Boukhari, N. (2026). Dependency-Aware Scheduling for Parallel Nonlinear System Solving on Multicore Architectures. Informatica, 50(14). https://doi.org/10.31449/inf.v50i14.10751
Vancouver
Moussaoui A, Belhadj F, Gueddoudj EY, Bouamama S, Boukhari N. Dependency-Aware Scheduling for Parallel Nonlinear System Solving on Multicore Architectures. Informatica. 2026;50(14). doi:10.31449/inf.v50i14.10751
BibTeX
@article{Moussaoui2026,
author = {Moussaoui, Adel and Belhadj, Foudil and Gueddoudj, El Yazid and Bouamama, Salim and Boukhari, Nawel},
title = {Dependency-Aware Scheduling for Parallel Nonlinear System Solving on Multicore Architectures},
journal = {Informatica},
year = {2026},
volume = {50},
number = {14},
doi = {10.31449/inf.v50i14.10751}
}
EUVIMED