Dependency-Aware Scheduling for Parallel Nonlinear System Solving on Multicore Architectures
Abstract
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.References
[1] S. C. Chapra and R. P. Canale, Numerical Methods for Engineers, McGraw-Hill, New York, 1988.
[2] S. H. Strogatz, Nonlinear Dynamics and Chaos with Student Solutions Manual: With Applications to Physics, Biology, Chemistry, and Engineering, CRC Press, 2018. DOI: 10.1201/9780429492563
[3] J. D. Anderson Jr, Fundamentals of Aerodynamics, McGraw-Hill, New York, 1991.
[4] G. Payette and J. Reddy, "A nonlinear finite element framework for viscoelastic beams based on the high-order Reddy beam theory," J. Eng. Mater. Technol., vol. 135, no. 1, p. 011005, 2013. DOI: 10.1115/1.4007562
[5] M. C. Boyce and E. M. Arruda, "Constitutive models of rubber elasticity: a review," Rubber Chem. Technol., vol. 73, no. 3, pp. 504–523, 2000. DOI: 10.5254/1.3547602
[6] L. M. P. Ghilardi, S. Naik, E. Martelli, F. Casella, and L. T. Biegler, "Economic Nonlinear Model Predictive Control for cyclic gas pipeline operation," Comput. Chem. Eng., p. 109039, 2025. DOI: 10.1016/j.compchemeng.2025.109039
[7] H. K. Khalil and J. W. Grizzle, Nonlinear Systems, vol. 3, Prentice Hall, Upper Saddle River, NJ, 2002.
[8] C. T. Kelley, Iterative Methods for Linear and Nonlinear Equations, SIAM, 1995. DOI: 10.1137/1.9781611970944
[9] R. Burden and J. Faires, Numerical Analysis, Brooks/Cole, Cengage Learning, Boston, USA, 2011.
[10] W. H. Press, Numerical Recipes 3rd Edition: The Art of Scientific Computing, Cambridge University Press, 2007.
[11] C. G. Broyden, "A class of methods for solving nonlinear simultaneous equations," Math. Comput., vol. 19, no. 92, pp. 577–593, 1965. DOI: 10.2307/2003941
[12] J. E. Dennis Jr and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, SIAM, 1996. DOI: 10.1137/1.9781611971200
[13] D. W. Marquardt, "An algorithm for least-squares estimation of nonlinear parameters," J. Soc. Ind. Appl. Math., vol. 11, no. 2, pp. 431–441, 1963. DOI: 10.1137/0111030
[14] A. Morgan, Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems, SIAM, 2009. DOI: 10.1137/1.9780898719031
[15] J. Nocedal and S. J. Wright, Numerical Optimization, Springer, 1999. DOI: 10.1007/b98874
[16] S. P. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. DOI: 10.1017/CBO9780511804441
[17] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013. DOI: 10.56021/9781421407944
[18] J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, SIAM, 2000. DOI: 10.1137/1.9780898719468
[19] S. Zhao, X. Dai, and I. Bate, "DAG scheduling and analysis on multi-core systems by modelling parallelism and dependency," IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 12, pp. 4019–4038, Dec. 2022, DOI: 10.1109/TPDS.2022.3177046.
[20] L. Bendiaf, A. Harbouche, M. A. Tahraoui, and F. Z. Lebbah, "An innovative task scheduling method utilizing the knapsack algorithm in heterogeneous computing systems," Informatica, vol. 48, pp. 89–104, 2024. DOI: 10.31449/inf.v48i16.5765
[21] S. Chang, X. Zhao, Z. Liu, and Q. Deng, "Realtime scheduling and analysis of parallel tasks on heterogeneous multi-cores," Journal of Systems Architecture, vol. 105, p. 101704, Apr. 2020, DOI: 10.1016/j.sysarc.2019.101704.
[22] X. Feng, C. Shushan, H. Xingxing, H. Shujuan, and Z. Wenjuan, "A new direct acyclic graph task scheduling method for heterogeneous MultiCore processors," Computers and Electrical Engineering, vol. 104, p. 108464, Dec. 2022, DOI: 10.1016/j.compeleceng.2022.108464.
[23] P. D. Michailidis and K. G. Margaritis, "Parallel direct methods for solving the system of linear equations with pipelining on a multicore using OpenMP," Journal of Computational and Applied Mathematics, vol. 236, no. 3, pp. 326–341, Nov. 2011, DOI: 10.1016/j.cam.2011.07.002.
[24] X. Xiao, "ILS-YOLO: An improved list scheduling algorithm for YoloLite DAGs in vehicular edge computing," Informatica, vol. 49, pp. 237–250, 2025. DOI: 10.31449/inf.v49i29.11851
[25] J. Kurzak, H. Ltaief, J. Dongarra, and R. M. Badia, "Scheduling dense linear algebra operations on multicore processors," Concurrency and Computation: Practice and Experience, vol. 22, no. 1, pp. 15–44, Jan. 2010, doi: 10.1002/cpe.1467.
[26] A. Haidar, H. Ltaief, A. YarKhan, and J. Dongarra, "Analysis of dynamically scheduled tile algorithms for dense linear algebra on multicore architectures," Concurrency and Computation: Practice and Experience, vol. 24, no. 3, pp. 305–321, Mar. 2012, doi: 10.1002/cpe.1829.
[27] F. Song, A. YarKhan, and J. Dongarra, "Dynamic task scheduling for linear algebra algorithms on distributed-memory multicore systems," in Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (SC '09), 2009, pp. 1–11, doi: 10.1145/1654059.1654079.
[28] D. Lukarski, "Parallel sparse linear algebra for multicore and many-core platforms: Parallel solvers and preconditioners," Ph.D. dissertation, Karlsruhe Institute of Technology, Karlsruhe, Germany, 2012.
[29] P. D'Ambra, F. Durastante, and S. Filippone, "Parallel Sparse Computation Toolkit," Software Impacts, vol. 15, p. 100463, 2023, DOI: 10.1016/j.simpa.2022.100463.
[30] M. Belmabrouk and M. Marrakchi, "Design, analysis and performance evaluation of parallel algorithms for solving triangular linear systems on multicore platforms," RAIRO - Operations Research, vol. 55, no. 2, pp. 545–559, Mar. 2021, DOI: 10.1051/ro/2019114.
[31] S. Marrakchi and M. Jemni, "Static scheduling with load balancing for solving triangular band linear systems on multicore processors," Fundamenta Informaticae, vol. 179, no. 1, pp. 35–58, Jan. 2021, DOI: 10.3233/FI-2021-2012.
[32] L. Mochurad and N. Boyko, "Solving systems of nonlinear equations on multi-core processors," in Proceedings of the Conference on Computer Science and Information Technologies, 2019, pp. 90–106, DOI: 10.1007/978-3-030-33695-0_8.
[33] V. Tavakkoli, K. Mohsenzadegan, J. C. Chedjou, and K. Kyamakya, "Contribution to speeding-up the solving of nonlinear ordinary differential equations on parallel/multi-core platforms for sensing systems," Sensors, vol. 20, no. 21, p. 6130, Oct. 2020, DOI: 10.3390/s20216130.
[34] F. González, A. Luaces, U. Lugrís, and M. González, "Non-intrusive parallelization of multibody system dynamic simulations," Computational Mechanics, vol. 44, no. 4, pp. 493–504, Oct. 2009, doi: 10.1007/s00466-009-0386-3.
[35] S. Ait-Aoudia, R. Jegou, and D. Michelucci, "Reduction of constraint systems," in Proceedings of the International Conference on Computational Graphics and Visualization Techniques (COMPUGRAPHICS'93), Alvor, Portugal, 1993, pp. 331–340.
[36] A. L. Dulmage and N. S. Mendelsohn, "Coverings of bipartite graphs," Can. J. Math., vol. 10, pp. 517–534, 1958. DOI: 10.4153/CJM-1958-052-0
[37] O. Sinnen, "Task Scheduling for Parallel Systems," John Wiley & Sons, 2007. DOI: 10.1002/9780470170575
[38] H. Topcuoglu, S. Hariri, and M.-Y. Wu, "Performance-effective and low-complexity task scheduling for heterogeneous computing," IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 3, pp. 260–274, 2002. DOI: 10.1109/71.993206
[39] J.-J. Hwang, Y.-C. Chow, F. D. Anger, and C.Y. Lee, "Scheduling precedence graphs in systems with interprocessor communication times," SIAM J. Comput., vol. 18, no. 2, pp. 244–257, 1989. DOI: 10.1137/0218016
[40] Kwok, Y. K. and Ahmad, I. (1999). Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, 31(4):406–471. DOI 10.1145/344588.344618
[41] R. Bajaj and D. P. Agrawal. Improving scheduling of tasks in a heterogeneous environment. IEEE Transactions on Parallel and Distributed Systems, 15(2):107–118, 2004. DOI: 10.1109/TPDS.2004.1264795
[42] L.-C. Canon and E. Jeannot. Evaluation and optimization of the robustness of DAG schedules in heterogeneous environments. IEEE Transactions on Parallel and Distributed Systems, 21(4):532–546, 2010. DOI: 10.1109/TPDS.2009.84
[43] A. Moussaoui, F. Belhadj, E. Y. Gueddoudj, S. Bouamama and N. Boukhari. ParallelEqSolver: Parallel nonlinear equations solver with dependency-aware scheduling. GitHub repository, 2025. https://github.com/adelmoussaoui/paralleleqsolver
[44] P. Virtanen et al., "SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python," Nature Methods, vol. 17, pp. 261–272, 2020.
[45] S. Williams, A. Waterman, and D. Patterson, "Roofline: An insightful visual performance model for multicore architectures," Communications of the ACM, vol. 52, no. 4, pp. 65–76, 2009. DOI: 10.1145/1498765.1498785
[46] O. Mutlu, "Memory scaling: A systems architecture perspective," in Proceedings of the 5th IEEE International Memory Workshop (IMW), 2013, pp. 21–25. DOI: 10.1109/IMW.2013.6582088
[47] C. R. Harris et al., "Array programming with NumPy," Nature, vol. 585, pp. 357–362, 2020. DOI: 10.1038/s41586-020-2649-2
[48] A. A. Hagberg, D. A. Schult, and P. J. Swart, "Exploring network structure, dynamics, and function using NetworkX," in Proceedings of the 7th Python in Science Conference (SciPy 2008), Pasadena, CA, 2008, pp. 11–15. DOI: 10.25080/TCWV9851
DOI:
https://doi.org/10.31449/inf.v50i14.10751Keywords:
Nonlinear Systems of Equations, Task Scheduling, DAG Algorithms, Parallel Computing, Multicore Architectures, Critical Path Method, Dependency-Aware DecompositionDownloads
Published
Issue
Section
License
Authors retain copyright in their work. By submitting to and publishing with Informatica, authors grant the publisher (Slovene Society Informatika) the non-exclusive right to publish, reproduce, and distribute the article and to identify itself as the original publisher.
All articles are published under the Creative Commons Attribution license CC BY 3.0. Under this license, others may share and adapt the work for any purpose, provided appropriate credit is given and changes (if any) are indicated.
Authors may deposit and share the submitted version, accepted manuscript, and published version, provided the original publication in Informatica is properly cited.
