Поиск :
Личный кабинет :
Электронный каталог: Prihozhy, A. A. - Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms
Prihozhy, A. A. - Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms
Статья
Автор: Prihozhy, A. A.
Системный анализ и прикладная информатика: Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms
Оптимизация размещения данных в иерархической памяти для блочных алгоритмов поиска кратчайших путей
б.г.
ISBN отсутствует
Автор: Prihozhy, A. A.
Системный анализ и прикладная информатика: Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms
Оптимизация размещения данных в иерархической памяти для блочных алгоритмов поиска кратчайших путей
б.г.
ISBN отсутствует
На полку
Статья
Prihozhy, A. A.
Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms = Оптимизация размещения данных в иерархической памяти для блочных алгоритмов поиска кратчайших путей / A. A. Prihozhy // Системный анализ и прикладная информатика / гл. ред. Сергей Васильевич Харитончик; учредитель Белорусский национальный технический университет (Минск). – 2021. – №3. – P. 40-50. – Режим доступа : https://rep.bntu.by/handle/data/102995. – На англ. яз.
This paper is devoted to the reduction of data transfer between the main memory and direct mapped cache for blocked shortest paths algorithms (BSPA), which represent data by a D[M×M] matrix of blocks. For large graphs, the cache size S = δ×M2, δ < 1 is smaller than the matrix size. The cache assigns a group of main memory blocks to a single cache block. BSPA performs multiple recalculations of a block over one or two other blocks and may access up to three blocks simultaneously. If the blocks are assigned to the same cache block, conflicts occur among the blocks, which imply active transfer of data between memory levels. The distribution of blocks on groups and the block conflict count strongly depends on the allocation and ordering of the matrix blocks in main memory. To solve the problem of optimal block allocation, the paper introduces a block conflict weighted graph and recognizes two cases of block mapping: non-conflict and minimum-conflict. In first case, it formulates an equitable color-class- size constrained coloring problem on the conflict graph and solves it by developing deterministic and random algorithms. In second case, the paper formulates a problem of weighted defective color-count constrained coloring of the conflict graph and solves it by developing a random algorithm. Experimental results show that the equitable random algorithm provides an upper bound of the cache size that is very close to the lower bound estimated over the size of a complete subgraph, and show that a non-conflict matrix allocation is possible at δ = 0.5 for M = 4 and at δ = 0.1 for M = 20. For a low cache size, the weighted defective algorithm gives the number of remaining conflicts that is up to 8.8 times less than the original BSPA gives. The proposed model and algorithms are applicable to set-associative cache as well.
Статья посвящена сокращению обмена данными между основной памятью и кэш прямого сопоставления при выполнении блочных алгоритмов поиска кратчайших путей, представляющих данные матрицей блоков D[M×M]. Для больших графов размер кэш S = δ×M2, δ < 1 меньше размера матрицы. Кэш назначает группу блоков основной памяти на один блок кэш. Алгоритмы пересчитывают блок матрицы через один или два других блока и могут обращаться сразу к трем блокам. Если эти блоки назначены на один блок кэш, между ними возникает конфликт, приводящий к активному обмену данными между уровнями памяти. Распределение блоков по группам и число конфликтов сильно зависят от размещения и упорядочения блоков матрицы в основной памяти. В статье предлагается решать проблему оптимального размещения на взвешенном графе конфликтов блоков и различать два случая назначения блоков на кэш: бесконфликтного и минимально-конфликтного. В первом случае формулируется проблема равномерной раскраски графа конфликтов, предлагаются детерминированный и случайный алгоритмы ее решения. Во втором случае формулируется проблема взвешенной дефектной раскраски графа при ограничении на число цветов, предлагается случайный алгоритм ее решения. Экспериментальные результаты показывают, что случайный алгоритм равномерной раскраски дает верхнюю границу размера кэш очень близкую к нижней границе, оцениваемой через полный подграф, и показывает, что бесконфликтное размещение матрицы возможно при δ = 0.5 для M = 4 и при δ = 0.1 для M = 20. Для малого размера кэш взвешенный дефектный алгоритм дает число оставшихся конфликтов до 8.8 раз меньшее чем начальное размещение. Предложенные модель и алгоритмы применимы также к k-канальному ассоциативному кэш.
004.272.2
труды сотрудников БНТУ = Факультет информационных технологий и робототехники : кафедра "Программное обеспечение информационных систем и технологий"
труды сотрудников БНТУ = Автоматика. Вычислительная техника (труды)
общий = ОБМЕН ДАННЫМИ
общий = ИЕРАРХИЧЕСКИЕ СИСТЕМЫ (систем. анализ; кибернет.)
общий = КЭШ-ПАМЯТЬ
общий = ОПЕРАТИВНАЯ ПАМЯТЬ
Prihozhy, A. A.
Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms = Оптимизация размещения данных в иерархической памяти для блочных алгоритмов поиска кратчайших путей / A. A. Prihozhy // Системный анализ и прикладная информатика / гл. ред. Сергей Васильевич Харитончик; учредитель Белорусский национальный технический университет (Минск). – 2021. – №3. – P. 40-50. – Режим доступа : https://rep.bntu.by/handle/data/102995. – На англ. яз.
This paper is devoted to the reduction of data transfer between the main memory and direct mapped cache for blocked shortest paths algorithms (BSPA), which represent data by a D[M×M] matrix of blocks. For large graphs, the cache size S = δ×M2, δ < 1 is smaller than the matrix size. The cache assigns a group of main memory blocks to a single cache block. BSPA performs multiple recalculations of a block over one or two other blocks and may access up to three blocks simultaneously. If the blocks are assigned to the same cache block, conflicts occur among the blocks, which imply active transfer of data between memory levels. The distribution of blocks on groups and the block conflict count strongly depends on the allocation and ordering of the matrix blocks in main memory. To solve the problem of optimal block allocation, the paper introduces a block conflict weighted graph and recognizes two cases of block mapping: non-conflict and minimum-conflict. In first case, it formulates an equitable color-class- size constrained coloring problem on the conflict graph and solves it by developing deterministic and random algorithms. In second case, the paper formulates a problem of weighted defective color-count constrained coloring of the conflict graph and solves it by developing a random algorithm. Experimental results show that the equitable random algorithm provides an upper bound of the cache size that is very close to the lower bound estimated over the size of a complete subgraph, and show that a non-conflict matrix allocation is possible at δ = 0.5 for M = 4 and at δ = 0.1 for M = 20. For a low cache size, the weighted defective algorithm gives the number of remaining conflicts that is up to 8.8 times less than the original BSPA gives. The proposed model and algorithms are applicable to set-associative cache as well.
Статья посвящена сокращению обмена данными между основной памятью и кэш прямого сопоставления при выполнении блочных алгоритмов поиска кратчайших путей, представляющих данные матрицей блоков D[M×M]. Для больших графов размер кэш S = δ×M2, δ < 1 меньше размера матрицы. Кэш назначает группу блоков основной памяти на один блок кэш. Алгоритмы пересчитывают блок матрицы через один или два других блока и могут обращаться сразу к трем блокам. Если эти блоки назначены на один блок кэш, между ними возникает конфликт, приводящий к активному обмену данными между уровнями памяти. Распределение блоков по группам и число конфликтов сильно зависят от размещения и упорядочения блоков матрицы в основной памяти. В статье предлагается решать проблему оптимального размещения на взвешенном графе конфликтов блоков и различать два случая назначения блоков на кэш: бесконфликтного и минимально-конфликтного. В первом случае формулируется проблема равномерной раскраски графа конфликтов, предлагаются детерминированный и случайный алгоритмы ее решения. Во втором случае формулируется проблема взвешенной дефектной раскраски графа при ограничении на число цветов, предлагается случайный алгоритм ее решения. Экспериментальные результаты показывают, что случайный алгоритм равномерной раскраски дает верхнюю границу размера кэш очень близкую к нижней границе, оцениваемой через полный подграф, и показывает, что бесконфликтное размещение матрицы возможно при δ = 0.5 для M = 4 и при δ = 0.1 для M = 20. Для малого размера кэш взвешенный дефектный алгоритм дает число оставшихся конфликтов до 8.8 раз меньшее чем начальное размещение. Предложенные модель и алгоритмы применимы также к k-канальному ассоциативному кэш.
004.272.2
труды сотрудников БНТУ = Факультет информационных технологий и робототехники : кафедра "Программное обеспечение информационных систем и технологий"
труды сотрудников БНТУ = Автоматика. Вычислительная техника (труды)
общий = ОБМЕН ДАННЫМИ
общий = ИЕРАРХИЧЕСКИЕ СИСТЕМЫ (систем. анализ; кибернет.)
общий = КЭШ-ПАМЯТЬ
общий = ОПЕРАТИВНАЯ ПАМЯТЬ
