期刊名称：International Journal of Computer Science and Information Technologies
电子版ISSN：0975-9646
出版年度：2014
卷号：5
期号：6
页码：8198-8204
出版社：TechScience Publications
摘要：All-pairs shortest path problem(APSP) finds a large number of practical applications in real world. We owe to present a highly parallel and recursive solution for solving APSP problem based on Kleene’s algorithm. The proposed parallel approach for APSP is implemented using an open standard framework OpenCL which provides a development environment for utilizing massive parallel capabilities of Multi core CPU and Many-Core-Processors such as Graphics Processing Unit (GPU). Moreover due to inherent nature of data reuse in the algorithm, shared memory of these processors is exploited to achieve considerable speedup. Our experiments demonstrate a speedup gain up to 521x over NVIDIA GeForce GT 630M GPU and a speedup up to 10x over Intel Core i3-2310M CPU.The proposed OpenCL solution for APSP is for directed and dense graphs with no negative cycles. Like Floyd-Warshall (FW), this approach is also in-place in nature and therefore requires no extra space.
关键词：OpenCL; Graphics processing Unit (GPU);All;Pairs Shortest Path( APSP); in-place; FW(Flowd Warshall);RK (Recursive Kleene); Many Core Processors
