https://scholars.lib.ntu.edu.tw/handle/123456789/634615
標題: | A Decentralized Frontier Queue for Improving Scalability of Breadth-First-Search on GPUs | 作者: | Hsieh, Chou Ying Cheng, Po Hsiu CHIA-MING CHANG SY-YEN KUO |
關鍵字: | breadth-first-search | GPU | parallel computing | queue | scalability | 公開日期: | 1-一月-2023 | 卷: | 2023-April | 來源出版物: | Proceedings -Design, Automation and Test in Europe, DATE | 摘要: | Breath-first-search (BFS) algorithm is the fundamen-tal building block of broad applications from the electronic design automation (EDA) field to social network analysis. With the targeting data set size growing considerable, researchers have turned to developing parallel BFS (PBFS) algorithms and accelerating them with graph processing units (GPUs). The frontier queue, the core idea among state-of-the-art designs of PBFS, opens the door to neighbor visiting parallelism. However, the traditional centralized frontier queue in PBFS suffers from a dramatic collision and explosive growth of memory space when excessive threads simultaneously operate on it. Therefore, we identify the challenges of current frontier queue implementations. To solve these challenges, we proposed the decentralized frontier queue (DFQ), which separates a centralized queue into multiple tiny sub-queues for scattering the atomic operation collision on these queues. We also developed the novel overflow-free enqueue and asynchronous sub-queue drain methods to avoid dramatic growing size of the frontier queue and the overflow issue on the naive sub-queue design. In our experiments, we showed that our design could have better scalability and grain averagely 1.04x speedup on the execution in the selected benchmark suit with considerable memory space efficiency. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/634615 | ISBN: | 9783981926378 | ISSN: | 15301591 | DOI: | 10.23919/DATE56975.2023.10137054 |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。