Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
https://elib.belstu.by/handle/123456789/55724
Название: | Advanced heterogeneous block-parallel all-pairs shortest path algorithm |
Авторы: | Prihozhy, Anatoly Alekseevich Karasik, Oleg Nikolayevich |
Ключевые слова: | shortest path blocked algorithm heterogeneous algorithm multi-core system throughput |
Дата публикации: | 2023 |
Издательство: | БГТУ |
Библиографическое описание: | Prihozhy А. А., Karasik O. N. Advanced heterogeneous block-parallel all-pairs shortest path algorithm. Труды БГТУ. Сер. 3, Физико-математические науки и информатика, 2023, no. 1 (266), pp. 77–83. DOI: 10.52065/2520-6141-2023-266-1-13. |
Краткий осмотр (реферат): | The problem of finding shortest paths between all pairs of vertices in a large-size graph has many application domains in industry, technology, science, economics, and society. The algorithms solving the problem and proposed in the literature target either lowering a computational complexity or efficient exploitation of computational resources. This paper proposes the advanced heterogeneous block-parallel shortest paths algorithm that is a result of further development and improvement of known blocked algorithms. Starting from the homogeneous blocked algorithm, it distinguishes four types of blocks: diagonal, vertical of cross, horizontal of cross, and peripheral. To speed up the computations, separate algorithms for all block types have been developed, which reduce the number of iterations in nested loops and account for the sequential reference locality of data in CPU caches. The algorithms improve the spatial and temporal reference locality in big data processing. Experiments carried out on a server equipped with two Intel Xeon E5-2620 v4 processors have shown the speedup of up to 60−70% the proposed single- and multi-threaded advanced heterogeneous blocked algorithms yield over the singleand multiple-threaded homogeneous blocked Floyd – Warshall algorithms. |
URI (Унифицированный идентификатор ресурса): | https://elib.belstu.by/handle/123456789/55724 |
ISSN: | 10.52065/2520-6141-2023-266-1-13 |
Располагается в коллекциях: | выпуск журнала постатейно |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
13. Prihozhy.pdf | 736.36 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.