Skip navigation
Please use this identifier to cite or link to this item: https://libeldoc.bsuir.by/handle/123456789/48300
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKarasik, O. N.-
dc.contributor.authorPrihozhy, А. А.-
dc.coverage.spatialМинск-
dc.date.accessioned2022-10-03T06:18:45Z-
dc.date.available2022-10-03T06:18:45Z-
dc.date.issued2022-
dc.identifier.citationKarasik, 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.ru_RU
dc.identifier.urihttps://libeldoc.bsuir.by/handle/123456789/48300-
dc.description.abstractThe 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.ru_RU
dc.language.isoenru_RU
dc.publisherБестпринтru_RU
dc.subjectматериалы конференцийru_RU
dc.subjectshortest pathru_RU
dc.subjectFloyd-Warshall algorithmru_RU
dc.subjectblocked algorithmru_RU
dc.subjectmultithreaded applicationru_RU
dc.subjectmultiprocessor systemru_RU
dc.subjecthierarchical cache memoryru_RU
dc.subjectparallelismru_RU
dc.subjectthroughputru_RU
dc.subjectкэш-памятьru_RU
dc.subjectблочные алгоритмыru_RU
dc.subjectмногопоточные алгоритмыru_RU
dc.subjectмногопроцессорные системыru_RU
dc.titleParallel blocked all-pair shortest path algorithm: block size effect on cache operation in multi-core systemru_RU
dc.title.alternativeБлочно-параллельный алгоритм поиска кратчайших путей: влияние размера блока на функционирование кэш-памяти многоядерной системыru_RU
dc.typeArticleru_RU
local.description.annotationЗадача нахождения всех кратчайших путей в графе является классической задачей информатики, имеющей многочисленные практические применения в самых различных областях. В статье выполнены профилирование и анализ блочно-параллельной версия алгоритма поиска кратчайшего пути между вершинами графа с целью оценки влияния параметров алгоритма на использование иерархической кэш-памяти на многоядерных системах. Вычислительные эксперименты, проведенные с использованием профилировщика, на различных размерах графов, убедительно показали, что использование алгоритмом кэшпамяти не зависят от размера графа, а определяется только выбранным размером блока. Полученные результаты показывают, что для каждой многоядерной системы оптимальный размер блока может быть найден единожды (если количество вершин в графе делится на выбранный размер блока и размер графа в памяти превышает объем кэш последнего уровня). После этого, найденный оптимальный размер блока может быть повторно использован для эффективного решения задачи кратчайших путей на графах большего размера.-
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 simple item record Google Scholar

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