Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.12470 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910305993359360 |
|---|---|
| author | Cummins, Chase Veras, Richard |
| author_facet | Cummins, Chase Veras, Richard |
| contents | Register allocation is one of the most important problems for modern compilers. With a practically unlimited number of user variables and a small number of CPU registers, assigning variables to registers without conflicts is a complex task. This work demonstrates the use of casting the register allocation problem as a graph coloring problem. Using technologies such as PyTorch and OpenAI Gymnasium Environments we will show that a Proximal Policy Optimization model can learn to solve the graph coloring problem. We will also show that the labeling of a graph is critical to the performance of the model by taking the matrix representation of a graph and permuting it. We then test the model's effectiveness on each of these permutations and show that it is not effective when given a relabeling of the same graph. Our main contribution lies in showing the need for label reordering invariant representations of graphs for machine learning models to achieve consistent performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_12470 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reinforcement Learning for Graph Coloring: Understanding the Power and Limits of Non-Label Invariant Representations Cummins, Chase Veras, Richard Machine Learning Artificial Intelligence Register allocation is one of the most important problems for modern compilers. With a practically unlimited number of user variables and a small number of CPU registers, assigning variables to registers without conflicts is a complex task. This work demonstrates the use of casting the register allocation problem as a graph coloring problem. Using technologies such as PyTorch and OpenAI Gymnasium Environments we will show that a Proximal Policy Optimization model can learn to solve the graph coloring problem. We will also show that the labeling of a graph is critical to the performance of the model by taking the matrix representation of a graph and permuting it. We then test the model's effectiveness on each of these permutations and show that it is not effective when given a relabeling of the same graph. Our main contribution lies in showing the need for label reordering invariant representations of graphs for machine learning models to achieve consistent performance. |
| title | Reinforcement Learning for Graph Coloring: Understanding the Power and Limits of Non-Label Invariant Representations |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2401.12470 |