Memory Assignment for Multiprocessor Caches Through Graph Coloring
It has become apparent that the achieved performance of multiprocessors is heavily dependent upon the quality of the availabel compilers. In this paper we are concerned with compile-time techniques that can be used to achieve better performance by improving cache utilization. Specifically, we invest...
| Main Authors: | , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149191 |
| _version_ | 1826207690406232064 |
|---|---|
| author | Agarwal, Anant Guttag, John Papaefthymiou, Marios |
| author_facet | Agarwal, Anant Guttag, John Papaefthymiou, Marios |
| author_sort | Agarwal, Anant |
| collection | MIT |
| description | It has become apparent that the achieved performance of multiprocessors is heavily dependent upon the quality of the availabel compilers. In this paper we are concerned with compile-time techniques that can be used to achieve better performance by improving cache utilization. Specifically, we investigate the problem of assigning data chunks to memory in a way that will minimize collisions in direct-mapped multiprocessor caches. We show that while this problem is computationally intractable, there are interesting special cases that can be solved in polynomial time. We also present several techniques that can be used when conflict-free assignment is not possible, or when finding a conflict-free assignment is computationally infeasible. These techniques include uniform decaching, which involves not caching specific data blocks, and data replication, which involves making multiple copies of read-only data. Finally, we present a memory assigment technique, grey coloring, that reduces latency in the presence of collisions by distributing cache misses among processors in a way that minimized the total number of cache misses in any specific cache. |
| first_indexed | 2024-09-23T13:53:27Z |
| id | mit-1721.1/149191 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:53:27Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1491912023-03-30T03:35:05Z Memory Assignment for Multiprocessor Caches Through Graph Coloring Agarwal, Anant Guttag, John Papaefthymiou, Marios It has become apparent that the achieved performance of multiprocessors is heavily dependent upon the quality of the availabel compilers. In this paper we are concerned with compile-time techniques that can be used to achieve better performance by improving cache utilization. Specifically, we investigate the problem of assigning data chunks to memory in a way that will minimize collisions in direct-mapped multiprocessor caches. We show that while this problem is computationally intractable, there are interesting special cases that can be solved in polynomial time. We also present several techniques that can be used when conflict-free assignment is not possible, or when finding a conflict-free assignment is computationally infeasible. These techniques include uniform decaching, which involves not caching specific data blocks, and data replication, which involves making multiple copies of read-only data. Finally, we present a memory assigment technique, grey coloring, that reduces latency in the presence of collisions by distributing cache misses among processors in a way that minimized the total number of cache misses in any specific cache. 2023-03-29T14:35:56Z 2023-03-29T14:35:56Z 1992-02 https://hdl.handle.net/1721.1/149191 MIT-LCS-TM-465 application/pdf |
| spellingShingle | Agarwal, Anant Guttag, John Papaefthymiou, Marios Memory Assignment for Multiprocessor Caches Through Graph Coloring |
| title | Memory Assignment for Multiprocessor Caches Through Graph Coloring |
| title_full | Memory Assignment for Multiprocessor Caches Through Graph Coloring |
| title_fullStr | Memory Assignment for Multiprocessor Caches Through Graph Coloring |
| title_full_unstemmed | Memory Assignment for Multiprocessor Caches Through Graph Coloring |
| title_short | Memory Assignment for Multiprocessor Caches Through Graph Coloring |
| title_sort | memory assignment for multiprocessor caches through graph coloring |
| url | https://hdl.handle.net/1721.1/149191 |
| work_keys_str_mv | AT agarwalanant memoryassignmentformultiprocessorcachesthroughgraphcoloring AT guttagjohn memoryassignmentformultiprocessorcachesthroughgraphcoloring AT papaefthymioumarios memoryassignmentformultiprocessorcachesthroughgraphcoloring |