Поиск :
Личный кабинет :
Электронный каталог: Karasik, O.N. - Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation
Karasik, O.N. - Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation
Статья
Автор: Karasik, O.N.
Системный анализ и прикладная информатика: Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation
Настройка блочно-параллельного алгоритма поиска кратких путей на эффективную многоядерную реализацию
б.г.
ISBN отсутствует
Автор: Karasik, O.N.
Системный анализ и прикладная информатика: Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation
Настройка блочно-параллельного алгоритма поиска кратких путей на эффективную многоядерную реализацию
б.г.
ISBN отсутствует
На полку
Статья
Karasik, O.N.
Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation = Настройка блочно-параллельного алгоритма поиска кратких путей на эффективную многоядерную реализацию / O. N. Karasik, A. A. Prihozhy. – DOI 10.21122/2309-4923-2022-3-57-65 // Системный анализ и прикладная информатика / гл. ред. Сергей Васильевич Харитончик; учредитель Белорусский национальный технический университет (Минск). – 2022. – № 3. – С. 57-65. – Режим доступа : https://rep.bntu.by/handle/data/123342. – На англ. яз.
Finding shortest paths in a weighted graph is one of the key problems in computer-science, which has numerous practical applications in multiple domains. This paper analyzes the parallel blocked all-pairs shortest path algorithm at the aim of evaluating the influence of the multi-core system and its hierarchical cache memory on the parameters of algorithm implementation depending on the size of the graph and the size of distance matrix’s block. It proposes a technique of tuning the block-size to the given multi-core system. The technique involves profiling tools in the tuning process and allows the increase of the parallel algorithm throughput. Computational experiments carried out on a rack server equipped with two intel xeon e5-2620 v4 processors of 8 cores and 16 hardware threads each have convincingly shown for various graph sizes that the behavior and parameters of the hierarchical cache memory operation don’t depend on the graph size and are determined only by the distance matrix’s block size. To tune the algorithm to the target multi-core system, the preferable block size can be found once for the graph size whose in-memory matrix representation is larger than the size of cache shared among all processor’s cores. Then this block-size can be reused on graphs of bigger size for efficient solving the all-pairs shortest path problem.
Поиск кратчайших путей во взвешенном графе — одна из ключевых задач компьютерных наук, которая имеет множество практических приложений в различных областях. В данной работе анализируется блочно-параллельный алгоритм поиска кратчайших путей с целью оценки влияния многоядерной системы и ее иерархической кэш-памяти на параметры реализации алгоритма в зависимости от размера графа и размера блока матрицы расстояний. В ней предлагается метод настройки размера блока на особенности многоядерной системы. Метод предполагает использование инструментов профилирования в процессе настройки и позволяет увеличить производительность параллельного алгоритма. Вычислительные эксперименты, проведенные на стоечном сервере, оснащенном двумя процессорами Intel Xeon E5-2620 v4, состоящих из 8 ядер и 16 аппаратных потоков каждый, убедительно показали для различных размеров графов, что поведение и параметры работы иерархической кэш-памяти слабо зависят от размера графа и определяются размером блока матрицы расстояний. Чтобы настроить алгоритм на целевую многоядерную систему, предпочтительный размер блока может быть найден один раз для графа, размер представления которого превышает размер кэша, совместно используемого ядрами процессора. После этого найденный размер блока можно многократно использовать для эффективного решения задачи о кратчайших путях на графах большего размера.
004.272.2
общий = БД Труды научных работников БНТУ : 2022г.
труды сотрудников БНТУ = Факультет информационных технологий и робототехники : кафедра "Программное обеспечение информационных систем и технологий"
труды сотрудников БНТУ = Автоматика. Вычислительная техника (труды)
общий = АЛГОРИТМИЧЕСКИЕ МЕТОДЫ
общий = МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ
общий = ИЕРАРХИЧЕСКИЕ СИСТЕМЫ (систем. анализ; кибернет.)
общий = ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ
общий = КЭШ-ПАМЯТЬ
общий = ГРАФЫ (мат.)
Karasik, O.N.
Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation = Настройка блочно-параллельного алгоритма поиска кратких путей на эффективную многоядерную реализацию / O. N. Karasik, A. A. Prihozhy. – DOI 10.21122/2309-4923-2022-3-57-65 // Системный анализ и прикладная информатика / гл. ред. Сергей Васильевич Харитончик; учредитель Белорусский национальный технический университет (Минск). – 2022. – № 3. – С. 57-65. – Режим доступа : https://rep.bntu.by/handle/data/123342. – На англ. яз.
Finding shortest paths in a weighted graph is one of the key problems in computer-science, which has numerous practical applications in multiple domains. This paper analyzes the parallel blocked all-pairs shortest path algorithm at the aim of evaluating the influence of the multi-core system and its hierarchical cache memory on the parameters of algorithm implementation depending on the size of the graph and the size of distance matrix’s block. It proposes a technique of tuning the block-size to the given multi-core system. The technique involves profiling tools in the tuning process and allows the increase of the parallel algorithm throughput. Computational experiments carried out on a rack server equipped with two intel xeon e5-2620 v4 processors of 8 cores and 16 hardware threads each have convincingly shown for various graph sizes that the behavior and parameters of the hierarchical cache memory operation don’t depend on the graph size and are determined only by the distance matrix’s block size. To tune the algorithm to the target multi-core system, the preferable block size can be found once for the graph size whose in-memory matrix representation is larger than the size of cache shared among all processor’s cores. Then this block-size can be reused on graphs of bigger size for efficient solving the all-pairs shortest path problem.
Поиск кратчайших путей во взвешенном графе — одна из ключевых задач компьютерных наук, которая имеет множество практических приложений в различных областях. В данной работе анализируется блочно-параллельный алгоритм поиска кратчайших путей с целью оценки влияния многоядерной системы и ее иерархической кэш-памяти на параметры реализации алгоритма в зависимости от размера графа и размера блока матрицы расстояний. В ней предлагается метод настройки размера блока на особенности многоядерной системы. Метод предполагает использование инструментов профилирования в процессе настройки и позволяет увеличить производительность параллельного алгоритма. Вычислительные эксперименты, проведенные на стоечном сервере, оснащенном двумя процессорами Intel Xeon E5-2620 v4, состоящих из 8 ядер и 16 аппаратных потоков каждый, убедительно показали для различных размеров графов, что поведение и параметры работы иерархической кэш-памяти слабо зависят от размера графа и определяются размером блока матрицы расстояний. Чтобы настроить алгоритм на целевую многоядерную систему, предпочтительный размер блока может быть найден один раз для графа, размер представления которого превышает размер кэша, совместно используемого ядрами процессора. После этого найденный размер блока можно многократно использовать для эффективного решения задачи о кратчайших путях на графах большего размера.
004.272.2
общий = БД Труды научных работников БНТУ : 2022г.
труды сотрудников БНТУ = Факультет информационных технологий и робототехники : кафедра "Программное обеспечение информационных систем и технологий"
труды сотрудников БНТУ = Автоматика. Вычислительная техника (труды)
общий = АЛГОРИТМИЧЕСКИЕ МЕТОДЫ
общий = МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ
общий = ИЕРАРХИЧЕСКИЕ СИСТЕМЫ (систем. анализ; кибернет.)
общий = ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ
общий = КЭШ-ПАМЯТЬ
общий = ГРАФЫ (мат.)
