Поиск :
Личный кабинет :
Электронный каталог: Prihozhy, A. A. - New blocked all-pairs shortest paths algo-rithms operating on blocks of unequal sizes
Prihozhy, A. A. - New blocked all-pairs shortest paths algo-rithms operating on blocks of unequal sizes
Статья
Автор: Prihozhy, A. A.
Системный анализ и прикладная информатика: New blocked all-pairs shortest paths algo-rithms operating on blocks of unequal sizes
Новые блочные алгоритмы поиска кратчайших путей между всеми парами вершин графа, работающие на блоках неравных размеров
б.г.
ISBN отсутствует
Автор: Prihozhy, A. A.
Системный анализ и прикладная информатика: New blocked all-pairs shortest paths algo-rithms operating on blocks of unequal sizes
Новые блочные алгоритмы поиска кратчайших путей между всеми парами вершин графа, работающие на блоках неравных размеров
б.г.
ISBN отсутствует
На полку
Статья
Prihozhy, A. A.
New blocked all-pairs shortest paths algo-rithms operating on blocks of unequal sizes = Новые блочные алгоритмы поиска кратчайших путей между всеми парами вершин графа, работающие на блоках неравных размеров / A. A. Prihozhy, O. N. Karasik. – DOI 10.21122/2309-4923-2023-4-4-13 // Системный анализ и прикладная информатика. – 2023. – № 4. – P. 4-13. – Режим доступа : https://rep.bntu.by/handle/data/139561. – На англ. яз.
In real-world networks, many problems imply finding the All-Pairs Shortest Paths (APSP) and their distances in a graph. Solving the large-scale APSP problem on modern muti-processor (multi-core) systems is the key for various ap-plication domains. The computational cost of solving the problem is high, therefore in many cases approximate solu-tions are considered as acceptable.The blocked APSP algorithms are a promising approach which can exploit many processors (cores) and their caches in parallel mode efficiently. At the same time, to our best knowledge, all blocked algorithms of the Floyd-Warshall family use blocks of equal sizes. This property limits application of the algorithms. In this paper we propose new blocked algorithms which divide the input graph into unequal subgraphs and divide the matrix of distances between pairs of vertices into blocks of unequal sizes. The algorithms describe the dense subgraphs by the adjacency matrix and describe sparse subgraphs and connections between them by the adjacency list. This ap-proach allows the Floyd-Warshall family algorithms to be used together with Dijkstra family algorithms. It can be ap-plied to large graphs decomposed into dense (clusters) and sparse subgraphs. A new heterogeneous algorithm can significantly reduce the computation time of blocks depending on the block type and size. The contribution of the pa-per is the development of a new family of blocked APSP algorithms which can handle blocks of unequal sizes, save and extend the advantages of the state-of-the-art algorithms operating on blocks of equal sizes. The proposed algorithms are implemented as single- and multiple-threaded parallel applications for multi-core systems.
Многие задачи на реальных сетях предполагают поиск кратчайших путей между всеми парами вершин графа и расстояний между вершинами (APSP). Решение крупномасштабной задачи APSP на современных многопроцессорных (многоядерных) системах является ключевым для различных областей применения. Вычислительные затраты на ее решение высоки, поэтому во многих случаях приемлемыми считаются приближенные решения. Перспективным подходом, позволяющим эффективно использовать множество процессоров (ядер) и их кэши в параллельном режиме, являются блочные алгоритмы APSP. В то же время, насколько нам известно, в блочных алгоритмах семейства Флойда-Уоршалла все блоки имеют одинаковый размер. Это свойство ограничивает применение алгоритмов. В статье предлагаются новые блочные алгоритмы, которые разбивают граф на неравные подграфы и разбивают матрицу расстояний между парами вершин на блоки неравного размера. Алгоритмы описывают плотные подграфы матрицей смежности, а разреженные подграфы и связи между ними ‒ списком смежности. Такой подход позволяет совместно использовать алгоритмы семейства Флойда-Уоршалла с алгоритмами семейства Дейкстры. Он может быть применен к большим графам, декомпозированным на плотные (кластеры) и разреженные подграфы. Новый гетерогенный алгоритм может существенно сократить время вычисления блоков в зависимости от типа и размера. Вклад статьи заключается в разработке нового семейства блочных алгоритмов APSP, которые работают с блоками неравных размеров, сохраняют и расширяют преимущества алгоритмов, работающих с блоками равных размеров. Предложенные алгоритмы реализованы в виде одно- и многопоточных параллельных приложений для многоядерных систем.
004.021
общий = БД Труды научных работников БНТУ : 2023г.
труды сотрудников БНТУ = Факультет информационных технологий и робототехники : кафедра "Программное обеспечение информационных систем и технологий"
труды сотрудников БНТУ = Автоматика. Вычислительная техника (труды)
общий = АЛГОРИТМЫ (мат., информатика)
общий = МНОГОЯДЕРНЫЕ ПРОЦЕССОРЫ
общий = МНОГОПОТОЧНОСТЬ
общий = АЛГОРИТМЫ ПОИСКА ДАННЫХ
общий = РАСПАРАЛЛЕЛИВАНИЕ (программирование)
Prihozhy, A. A.
New blocked all-pairs shortest paths algo-rithms operating on blocks of unequal sizes = Новые блочные алгоритмы поиска кратчайших путей между всеми парами вершин графа, работающие на блоках неравных размеров / A. A. Prihozhy, O. N. Karasik. – DOI 10.21122/2309-4923-2023-4-4-13 // Системный анализ и прикладная информатика. – 2023. – № 4. – P. 4-13. – Режим доступа : https://rep.bntu.by/handle/data/139561. – На англ. яз.
In real-world networks, many problems imply finding the All-Pairs Shortest Paths (APSP) and their distances in a graph. Solving the large-scale APSP problem on modern muti-processor (multi-core) systems is the key for various ap-plication domains. The computational cost of solving the problem is high, therefore in many cases approximate solu-tions are considered as acceptable.The blocked APSP algorithms are a promising approach which can exploit many processors (cores) and their caches in parallel mode efficiently. At the same time, to our best knowledge, all blocked algorithms of the Floyd-Warshall family use blocks of equal sizes. This property limits application of the algorithms. In this paper we propose new blocked algorithms which divide the input graph into unequal subgraphs and divide the matrix of distances between pairs of vertices into blocks of unequal sizes. The algorithms describe the dense subgraphs by the adjacency matrix and describe sparse subgraphs and connections between them by the adjacency list. This ap-proach allows the Floyd-Warshall family algorithms to be used together with Dijkstra family algorithms. It can be ap-plied to large graphs decomposed into dense (clusters) and sparse subgraphs. A new heterogeneous algorithm can significantly reduce the computation time of blocks depending on the block type and size. The contribution of the pa-per is the development of a new family of blocked APSP algorithms which can handle blocks of unequal sizes, save and extend the advantages of the state-of-the-art algorithms operating on blocks of equal sizes. The proposed algorithms are implemented as single- and multiple-threaded parallel applications for multi-core systems.
Многие задачи на реальных сетях предполагают поиск кратчайших путей между всеми парами вершин графа и расстояний между вершинами (APSP). Решение крупномасштабной задачи APSP на современных многопроцессорных (многоядерных) системах является ключевым для различных областей применения. Вычислительные затраты на ее решение высоки, поэтому во многих случаях приемлемыми считаются приближенные решения. Перспективным подходом, позволяющим эффективно использовать множество процессоров (ядер) и их кэши в параллельном режиме, являются блочные алгоритмы APSP. В то же время, насколько нам известно, в блочных алгоритмах семейства Флойда-Уоршалла все блоки имеют одинаковый размер. Это свойство ограничивает применение алгоритмов. В статье предлагаются новые блочные алгоритмы, которые разбивают граф на неравные подграфы и разбивают матрицу расстояний между парами вершин на блоки неравного размера. Алгоритмы описывают плотные подграфы матрицей смежности, а разреженные подграфы и связи между ними ‒ списком смежности. Такой подход позволяет совместно использовать алгоритмы семейства Флойда-Уоршалла с алгоритмами семейства Дейкстры. Он может быть применен к большим графам, декомпозированным на плотные (кластеры) и разреженные подграфы. Новый гетерогенный алгоритм может существенно сократить время вычисления блоков в зависимости от типа и размера. Вклад статьи заключается в разработке нового семейства блочных алгоритмов APSP, которые работают с блоками неравных размеров, сохраняют и расширяют преимущества алгоритмов, работающих с блоками равных размеров. Предложенные алгоритмы реализованы в виде одно- и многопоточных параллельных приложений для многоядерных систем.
004.021
общий = БД Труды научных работников БНТУ : 2023г.
труды сотрудников БНТУ = Факультет информационных технологий и робототехники : кафедра "Программное обеспечение информационных систем и технологий"
труды сотрудников БНТУ = Автоматика. Вычислительная техника (труды)
общий = АЛГОРИТМЫ (мат., информатика)
общий = МНОГОЯДЕРНЫЕ ПРОЦЕССОРЫ
общий = МНОГОПОТОЧНОСТЬ
общий = АЛГОРИТМЫ ПОИСКА ДАННЫХ
общий = РАСПАРАЛЛЕЛИВАНИЕ (программирование)
