Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Belarusian National Technical University
2021-10-01
|
| Series: | Системный анализ и прикладная информатика |
| Subjects: | |
| Online Access: | https://sapi.bntu.by/jour/article/view/522 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832543670229794816 |
|---|---|
| author | A. A. Prihozhy |
| author_facet | A. A. Prihozhy |
| author_sort | A. A. Prihozhy |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-d4326ebad4f7432e96ae22225d3f5806 |
| institution | Kabale University |
| issn | 2309-4923 2414-0481 |
| language | English |
| publishDate | 2021-10-01 |
| publisher | Belarusian National Technical University |
| record_format | Article |
| series | Системный анализ и прикладная информатика |
| spelling | doaj-art-d4326ebad4f7432e96ae22225d3f58062025-02-03T11:37:39ZengBelarusian National Technical UniversityСистемный анализ и прикладная информатика2309-49232414-04812021-10-0103405010.21122/2309-4923-2021-3-40-50395Optimization of data allocation in hierarchical memory for blocked shortest paths algorithmsA. A. Prihozhy0Belarusian National Technical UniversityThis 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.https://sapi.bntu.by/jour/article/view/522shortest paths algorithmhierarchical memorydirect mapped cacheperformanceblock conflict graphdata allocationequitable coloringdefective coloring |
| spellingShingle | A. A. Prihozhy Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms Системный анализ и прикладная информатика shortest paths algorithm hierarchical memory direct mapped cache performance block conflict graph data allocation equitable coloring defective coloring |
| title | Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms |
| title_full | Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms |
| title_fullStr | Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms |
| title_full_unstemmed | Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms |
| title_short | Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms |
| title_sort | optimization of data allocation in hierarchical memory for blocked shortest paths algorithms |
| topic | shortest paths algorithm hierarchical memory direct mapped cache performance block conflict graph data allocation equitable coloring defective coloring |
| url | https://sapi.bntu.by/jour/article/view/522 |
| work_keys_str_mv | AT aaprihozhy optimizationofdataallocationinhierarchicalmemoryforblockedshortestpathsalgorithms |