检索结果-内蒙古大学图书馆

53rd International Conference on Parallel Processing (ICPP)

作者： Srikanth, Mithinti Singh, Prashant Ramakrishna, G. Indian Inst Technol Tirupati Tirupati Andhra Pradesh India

ISBN: (纸本)9798400717932

This paper introduces the first gpu-based parallel algorithms to solve the fastest path duration (FPD) problem in temporal graphs. Fastest path duration in temporal graphs is a well studied problem that has multiple use cases in information diffusion, epidemic spreading, and route planning in public transportation. Given a temporal graph G in which each edge associates with a departure time and duration time, and a source vertex s, the Fastest Path Duration (FPD) problem is to compute the journey times from s to all the rest of the vertices in G. The existing multi-core algorithm for FPD by Delling et al. exhibits limited parallelism. In general, many parallel algorithms suffer from doing redundant work while pruning certain computations. Our research focuses on multiple algorithmic ways to avoid redundant work and perform pruning of computations effectively. We introduce three novel gpu-based parallel algorithms for FPD, namely Level Order (LO), Multiple Breadth First Search (MBFS), and Local Work-lists (LW) and implement them on a gpu architecture machine. Our algorithms demonstrate an average speedup of approximately 165 times and a maximum speedup of up to 1383 times over the current state-of-the-art algorithms. This paper provides a comprehensive explanation of various algorithm designs, their optimizations for gpuS, and an extensive evaluation of their performance across various temporal graph scenarios.

关键词： Temporal Graph Fastest Path gpu-algorithms Massively Parallel algorithms Transformed Graph Journey Time

来源：评论

学校读者我要写书评

暂无评论

Fast parallel gpu-sorting using a hybrid algorithm

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2008年第10期68卷 1381-1388页

作者： Sintorn, Erik Assarsson, Ulf Chalmers Univ Technol Dept Comp Sci & Engn S-41296 Gothenburg Sweden

This paper presents an algorithm for fast sorting of large lists using modern gpus. The method achieves high speed by efficiently utilizing the parallelism of the CPU throughout the whole algorithm. Initially, gpu-based bucketsort or quicksort splits the list into enough sublists;then to be sorted in parallel using merge-sort. The algorithm is of complexity n log n, and for lists of 8 M elements and using a single Geforce 8800 GTS-512, it is 2.5 times as fast as the bitonic sort algorithms, with standard complexity of n(log n)(2), which for a long time was considered to be the fastest for CPU sorting. It is 6 times faster than single CPU quicksort, and 10% faster than the recent gpu-based radix sort. Finally, the algorithm is further parallelized to utilize two graphics cards, resulting in yet another 1.8 times speedup. (c) 2008 Elsevier Inc. All rights reserved.

关键词： Parallelism Sorting gpu-algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：