Reinforcement Learning for Graph Coloring: Understanding the Power and Limits of Non-Label Invariant Representations
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
DAOP: 효율적인 MoE 추론을 위한 데이터 인지 오프로딩 및 예측 사전 계산
DAOP: Data-Aware Offloading and Predictive Pre-Calculation for Efficient MoE Inference
전문가 혼합(Mixture-of-Experts, MoE) 모델은 다양한 머신러닝 작업에서 매우 효과적이지만, 메모리가 제한된 기기에 배포할 때 상당한 어려움을 겪는다. GPU는 빠른 추론을 제공하지만 CPU에 비해 메모리가 제한적이어서 모든 전문가(expert)를 GPU에 동시에 저장할 수 없으며, 이로 인해 CPU 메모리로부터 비용이 큰 데이터 전송이 빈번하게 필요해지고 이는 종종 GPU의 속도 이점을 상쇄한다. 이를 해결하기 위해 우리는 GPU-CPU 병렬 실행을 최적화하는 온디바이스 MoE 추론 엔진인 DAOP를 제안한다. DAOP는 시퀀스별 활성화 패턴에 따라 전문가를 CPU와 GPU 간에 동적으로 할당하고, 예측된 전문가를 CPU에서 선택적으로 사전 계산하여 전송 지연 시간을 최소화한다. 이 접근 방식은 새로운 점진적 성능 저하(graceful degradation) 메커니즘을 통해 모델 정확도를 유지하면서도 다양한 전문가 캐시 비율에서 효율적인 자원 활용을 가능하게 한다. 다양한 데이터셋에 대한 종합적인 평가 결과, DAOP는 기존의 전문가 캐싱 및 프리페칭 방법보다 최대 8.20배, 오프로딩 기법보다 1.35배 더 우수한 성능을 보이면서도 정확도를 유지하는 것으로 나타났다.
MathOptAI.jl: Embed trained machine learning predictors into JuMP models
LIGHTHOUSE: Fast and precise distance to shoreline calculations from anywhere on earth
ConsumerBench: Benchmarking Generative AI Applications on End-User Devices
Versatile and Fast Location-Based Private Information Retrieval with Fully Homomorphic Encryption over the Torus
SecONNds: Secure Outsourced Neural Network Inference on ImageNet
토론
이 논문과 연결된 포럼 글이 아직 없습니다.