Skip navigation
Please use this identifier to cite or link to this item: https://libeldoc.bsuir.by/handle/123456789/48300
Title: Parallel blocked all-pair shortest path algorithm: block size effect on cache operation in multi-core system
Other Titles: Блочно-параллельный алгоритм поиска кратчайших путей: влияние размера блока на функционирование кэш-памяти многоядерной системы
Authors: Karasik, O. N.
Prihozhy, А. А.
Keywords: материалы конференций;shortest path;Floyd-Warshall algorithm;blocked algorithm;multithreaded application;multiprocessor system;hierarchical cache memory;parallelism;throughput;кэш-память;блочные алгоритмы;многопоточные алгоритмы;многопроцессорные системы
Issue Date: 2022
Publisher: Бестпринт
Citation: Karasik, O. N. Parallel blocked all-pair shortest path algorithm: block size effect on cache operation in multi-core system = Блочно-параллельный алгоритм поиска кратчайших путей: влияние размера блока на функционирование кэш-памяти многоядерной системы / O. N. Karasik , А. А. Prihozhy // BIG DATA and Advanced Analytics = BIG DATA и анализ высокого уровня : VIII Международная научно-практическая конференция : сборник материалов VIII Международной научно-практической конференции, Минск, 11–12 мая 2022 года / Белорусский государственный университет информатики и радиоэлектроники ; редкол.: В. А. Богуш [и др.]. – Минск, 2022. – С. 28–38.
Abstract: The problem of finding all-pairs of shortest path in a graph is a classical computer-science problem which has numerous practical applications in multiple domains. This paper analyzes a parallel version of the blocked all-pair shortest path algorithm at the aim of evaluating the influence of the hierarchical cache memory on the parameters of algorithm implementations on multi-processor/multi-core systems. Computational experiments carried out by means of a profiling tool on various graph sizes have convincingly shown that the behavior and parameters of the cache memory operation don’t depend on the graph size and are determined only by the distance matrix block size. Obtained results show, that for every target machine the optimal block size can be found once in the case the graph size isn’t high, it is divisible by the block size, and it is larger than the size of processor’s last level shared cache. After that the optimal block size can be reused for efficient solving of the shortest paths problem on all graphs of larger size.
Alternative abstract: Задача нахождения всех кратчайших путей в графе является классической задачей информатики, имеющей многочисленные практические применения в самых различных областях. В статье выполнены профилирование и анализ блочно-параллельной версия алгоритма поиска кратчайшего пути между вершинами графа с целью оценки влияния параметров алгоритма на использование иерархической кэш-памяти на многоядерных системах. Вычислительные эксперименты, проведенные с использованием профилировщика, на различных размерах графов, убедительно показали, что использование алгоритмом кэшпамяти не зависят от размера графа, а определяется только выбранным размером блока. Полученные результаты показывают, что для каждой многоядерной системы оптимальный размер блока может быть найден единожды (если количество вершин в графе делится на выбранный размер блока и размер графа в памяти превышает объем кэш последнего уровня). После этого, найденный оптимальный размер блока может быть повторно использован для эффективного решения задачи кратчайших путей на графах большего размера.
URI: https://libeldoc.bsuir.by/handle/123456789/48300
Appears in Collections:BIG DATA and Advanced Analytics = BIG DATA и анализ высокого уровня : материалы конференции (2022)

Files in This Item:
File Description SizeFormat 
Karasik_Parallel.pdf1.52 MBAdobe PDFView/Open
Show full item record


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.