Zhao, Yan; Chen, Liping; Xie, Gang; Zhao, Jianjun; Ding, Jianwan GPU implementation of a cellular genetic algorithm for scheduling dependent tasks of physical system simulation programs. (English) Zbl 1393.90063 J. Comb. Optim. 35, No. 1, 293-317 (2018). Summary: This paper studies the problem of efficiently scheduling dependent computational tasks on heterogeneous computing systems. Computational tasks with precedence constraints are commonly represented by a directed acyclic graph (DAG). Four commonly used algorithms including a cellular genetic algorithm (CGA) are performed for scheduling a special type of DAGs derived from physical system simulation programs. Experimental results show that CGA outperforms the other three algorithms. However, when solving large instances of the dependent task scheduling problem, which are often the case for physical system simulation programs, a CPU implementation of the genetic algorithms can be extremely time consuming. The time complexity of producing a generation with a CPU is \(O(n_{cell}\; n^{2})\), where \(n\) is the size of DAG, and \(n_{cell}\) is the size of population. To improve runtimes, this paper presents a graphics processing unit (GPU) based implementation of the genetic algorithms. The time complexity of creating a new generation with a GPU is reduced to \(O(n)\). The experimental results show that significant speedups can be achieved by harnessing the power of a modern GPU. MSC: 90B35 Deterministic scheduling theory in operations research 90C59 Approximation methods and heuristics in mathematical programming Keywords:directed acyclic graph; heterogeneous scheduling; cellular genetic algorithm; GPU Software:CUDA PDFBibTeX XMLCite \textit{Y. Zhao} et al., J. Comb. Optim. 35, No. 1, 293--317 (2018; Zbl 1393.90063) Full Text: DOI References: [1] Ahmad SG, Munir EU, Nisar W (2012) PEGA: a performance effective genetic algorithm for task scheduling in heterogeneous systems. In: 2012 IEEE 14th international conference on high performance computing and communication & 2012 IEEE 9th international conference on embedded software and systems (HPCC-ICESS), 2012. IEEE, pp 1082-1087 [2] Alba E, Dorronsoro B (2005) The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Trans Evol Comput 9(2):126-142 [3] Alba E, Dorronsoro B (2009) Cellular genetic algorithms, vol 42. Springer, Heidelberg · Zbl 1211.90006 [4] Carl JD et al (2014) An approach to parallelizing the simulation of complicated modelica models. In: Proceedings of the 2014 summer simulation multiconference, 2014. Society for Computer Simulation International, San Diego, p 17 · Zbl 1341.68020 [5] Casella F (2013) A strategy for parallel simulation of declarative object-oriented models of generalized physical networks. In: 5th workshop on equation-based object-oriented modeling languages and tools EOOLT. Linköping Univ. Electronic Press, Nottingham, UK, 2013, pp 45-51 · Zbl 0815.90097 [6] Coffman EG, Bruno JL (1976) Computer and job-shop scheduling theory. Wiley, New York · Zbl 0359.90031 [7] Derler P, Lee E, Vincentelli AS (2012) Modeling cyber-physical systems. Proc IEEE 100(1):13-28 [8] Elmqvist H, Mattsson SE, Olsson H (2014) Parallel model execution on many cores. In: The 10th international modelica conference, Lund, Sweden, 2014, vol 2, pp 363-370 [9] Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco · Zbl 0411.68039 [10] Gebremedhin M (2015) Automatic and explicit parallelization approaches for mathematical simulation models. Thesis [11] Gebremedhin M, Fritzson P (2014) Automatic task based analysis and parallelization in the context of equation based languages. In: Proceedings of the 6th international workshop on equation-based object-oriented modeling languages and tools, 2014. ACM, New York, pp 49-52 [12] Gupta S, Agarwal G, Kumar V (2010) Task scheduling in multiprocessor system using genetic algorithm. In: 2010 second international conference on machine learning and computing (ICMLC), 2010. IEEE, New York, pp 267-271 · Zbl 1341.68020 [13] Hassani A, Treijs J (2009) An overview of standard and parallel genetic algorithms. In: IDT workshop on interesting results in computer science and engineering. Mälardalen University, Västerĺs, pp 1-7 [14] Holland JH (1992) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT Press, Cambridge [15] Hou ESH, Ansari N, Ren H (1994) A genetic algorithm for multiprocessor scheduling. IEEE Trans Parallel Distrib Syst 5(2):113-120 [16] Kyriakidis TS, Kopanos GM, Georgiadis MC (2012) MILP formulations for single- and multi-mode resource-constrained project scheduling problems. Comput Chem Eng 36:369-385 [17] Lenstra JK, Rinnooy Kan AHG (1978) Complexity of scheduling under precedence constraints. Oper Res 26(1):22-35 · Zbl 0371.90060 [18] Liu Y et al (2014) Novel list scheduling strategies for data parallelism task graphs. Int J Netw Comput 4(2):279-290 [19] Manderick B, Spiessens P (1989) Fine-grained parallel genetic algorithms. In: Proceedings of the third international conference on Genetic algorithms, 1989. Morgan Kaufmann Publishers Inc, Burlington, pp 428-433 [20] Naderi B, Azab A (2014) Modeling and heuristics for scheduling of distributed job shops. Expert Syst Appl 41(17):7754-7763 [21] NVIDIA (2014) Cuda programming guide [22] Pan C-H (1997) A study of integer programming formulations for scheduling problems. Int J Syst Sci 28(1):33-41 · Zbl 0873.90054 [23] Pinel F, Dorronsoro B, Bouvry P (2013) Solving very large instances of the scheduling of independent tasks problem on the GPU. J Parallel Distrib Comput 73(1):101-110 [24] Reeves CR (1995) A genetic algorithm for flowshop sequencing. Comput Oper Res 22(1):5-13 · Zbl 0815.90097 [25] Schulze C, Huhn M, Schüler M (2010) Profiling of modelica real-time models. EOOLT 2010:23-31 [26] Sinnen O (2014) Reducing the solution space of optimal task scheduling. Comput Oper Res 43:201-214 · Zbl 1348.90312 [27] Tiller M (2012) Introduction to physical modeling with Modelica, vol 615. Springer, New York [28] Topcuoglu H, Hariri S, Min-you W (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 13(3):260-274 [29] Venugopalan S, Sinnen O (2015) ILP formulations for optimal task scheduling with communication delays on parallel systems. IEEE Trans Parallel Distrib Syst 26(1):142-151 [30] Xie G et al. (2014) A high-performance DAG task scheduling algorithm for heterogeneous networked embedded systems. In: 2014 IEEE 28th international conference on advanced information networking and applications (AINA), 2014. IEEE, pp 1011-1016 [31] Xu Y et al (2013) A DAG scheduling scheme on heterogeneous computing systems using double molecular structure-based chemical reaction optimization. J Parallel Distrib Comput 73(9):1306-1322 [32] Xu Y et al (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inform Sci 270:255-287 · Zbl 1341.68020 [33] Zhao Y et al (2014) Preliminary study in parallel simulation of equation-based system-level physical models. In: ASME 2014 international design engineering technical conferences and computers and information in engineering conference, 2014. American Society of Mechanical Engineers, New York, pp V01AT02A023-V01AT02A023 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.