Weitere Kapitel dieses Buchs durch Wischen aufrufen
Topological sort referred to as topo sort or topological ordering is defined as constraint-based ordering of nodes (vertices) of graph G or DAG (Directed Acyclic Graph). In other words, it gives a linearized order of graph nodes describing the relationship between the graph vertices. Many applications of various fields in computer science require a constraint-based ordering of tasks and, thus, topological sorting holds a big place of importance for many applications like semantic analysis in compiler design, Gantt chart generation in software project management and many more. In this paper, a parallel version of this ordering algorithm over CUDA (Compute Unified Device Architecture) has been discussed by identifying an approach to process-independent portions of the graph simultaneously for load flow analysis over radial distribution networks. The serial implementation of topological sort has been first discussed followed by its implementation on thread-block architecture of CUDA modifying the serial algorithm. Finally, the efficiency of this parallel version of topo sort has been investigated on various structures of graph modeled from radial distribution networks and has been reported.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
D. J. Pearce and P. H. J. Kelly, “A dynamic topological sort algorithm for directed acyclic graphs”, Journal of Experimental Algorithmics (JEA), Vol. 11, pp. 1–24, 2006.
A. B. Kahn, “Topological sorting of large networks”, Communications of the ACM, Vol. 5, pp. 558–562, 1962.
R. Fox, “Linux with operating system concepts” CRC Press, Pp. 544, 2014.
A. Jarry, H. Casanova and F. Berman. DAGsim, “A simulator for DAG scheduling Algorithms”, 2000.
E. Dekel, D Nassimi, S. Sahni. “Parallel Matrix and Graph Algorithms”, SIAM J. Computing, 10(4). pp 657–675, 1981.
M. C. Er.,” A Parallel Computation Approach to Topological Sorting”, The Computer Journal, 26(4). pp. 293–295, 1983.
J. Ma, K. Iwama, T. Takaoka, Q. Gu., “Efficient Parallel and Distributed Topological Sort Algorithms. Parallel Algorithms/Architecture Synthesis”,Proceedings, Second Aizu International Symposium. Pp. 378–383, 1997.
R.E. Tarjan, “Edge-disjoint spanning trees and depth-first search”, Acta Informatica. 6(2), pp. 171–185, 1976.
Harish P, Narayanan PJ, “Accelerating large graph algorithms on the GPU using CUDA In High performance computing”–HiPC 2007, Dec 18. pp. 197–208, 2007.
F. Dehne, K. Yogaratnam., “Exploring the Limits of GPUs with Parallel Graph Algorithms”, 2010.
V. W. Lee, C. Kim, J Chhugani, et al., “Debunking the 100X GPU vs. CPU Myth: An Evaluation of Throughput Computing on CPU and GPU”, ACM SIGARCH Computer Architecture News-ISCA ‘10, 38(3), pp. 451–460, 2010.
P. Harish, P.J Narayanan, “Accelerating large graph algorithms on GPU using CUDA. High Performance Computing”, HiPC 2007, Vol. 4873, pp 197–208, 2007.
Wen-mei W. Hwu, “GPU COMPUTING GEMS”, Emrald Edition, Published by Elsevier Inc, ISBN 978–0-12-384988-5, 2011.
David B. Kirk and Wen-mei W. Hwu, “Programming Massively Parallel Processors”, Published by Elsevier Inc, ISBN: 978–0-12-415992-1, 2013.
NVIDIA Corporation, CUDA Programming Guide 1.0, http://www.nvidia.com, 2007.
Rahul Saxena, Jaya Krishna, D.P. Sharma, “Faster Load Flow Analysis”, Proceedings of International Conference on ICT for Sustainable Development, Vol. 408 of series Advances in Intelligent Systems and Computing, pp. 45–54, 2016.
- GPU-Based Parallelization of Topological Sorting
D. P. Sharma
- Springer Singapore
Neuer Inhalt/© ITandMEDIA, Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung/© astrosystem | stock.adobe.com