Picasso: Memory-Efficient Graph Coloring Using Palettes With Applications in Quantum Computing
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910328294473728 |
|---|---|
| author | Ferdous, S M Neff, Reece Peng, Bo Shuvo, Salman Minutoli, Marco Mukherjee, Sayak Kowalski, Karol Becchi, Michela Halappanavar, Mahantesh |
| author_facet | Ferdous, S M Neff, Reece Peng, Bo Shuvo, Salman Minutoli, Marco Mukherjee, Sayak Kowalski, Karol Becchi, Michela Halappanavar, Mahantesh |
| contents | A coloring of a graph is an assignment of colors to vertices such that no two neighboring vertices have the same color. The need for memory-efficient coloring algorithms is motivated by their application in computing clique partitions of graphs arising in quantum computations where the objective is to map a large set of Pauli strings into a compact set of unitaries. We present Picasso, a randomized memory-efficient iterative parallel graph coloring algorithm with theoretical sublinear space guarantees under practical assumptions. The parameters of our algorithm provide a trade-off between coloring quality and resource consumption. To assist the user, we also propose a machine learning model to predict the coloring algorithm's parameters considering these trade-offs. We provide a sequential and a parallel implementation of the proposed algorithm.
We perform an experimental evaluation on a 64-core AMD CPU equipped with 512 GB of memory and an Nvidia A100 GPU with 40GB of memory. For a small dataset where existing coloring algorithms can be executed within the 512 GB memory budget, we show up to 68x memory savings. On massive datasets we demonstrate that GPU-accelerated Picasso can process inputs with 49.5x more Pauli strings (vertex set in our graph) and 2,478x more edges than state-of-the-art parallel approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_06713 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Picasso: Memory-Efficient Graph Coloring Using Palettes With Applications in Quantum Computing Ferdous, S M Neff, Reece Peng, Bo Shuvo, Salman Minutoli, Marco Mukherjee, Sayak Kowalski, Karol Becchi, Michela Halappanavar, Mahantesh Distributed, Parallel, and Cluster Computing A coloring of a graph is an assignment of colors to vertices such that no two neighboring vertices have the same color. The need for memory-efficient coloring algorithms is motivated by their application in computing clique partitions of graphs arising in quantum computations where the objective is to map a large set of Pauli strings into a compact set of unitaries. We present Picasso, a randomized memory-efficient iterative parallel graph coloring algorithm with theoretical sublinear space guarantees under practical assumptions. The parameters of our algorithm provide a trade-off between coloring quality and resource consumption. To assist the user, we also propose a machine learning model to predict the coloring algorithm's parameters considering these trade-offs. We provide a sequential and a parallel implementation of the proposed algorithm. We perform an experimental evaluation on a 64-core AMD CPU equipped with 512 GB of memory and an Nvidia A100 GPU with 40GB of memory. For a small dataset where existing coloring algorithms can be executed within the 512 GB memory budget, we show up to 68x memory savings. On massive datasets we demonstrate that GPU-accelerated Picasso can process inputs with 49.5x more Pauli strings (vertex set in our graph) and 2,478x more edges than state-of-the-art parallel approaches. |
| title | Picasso: Memory-Efficient Graph Coloring Using Palettes With Applications in Quantum Computing |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2401.06713 |