CAJ | 학술논문

近年来，基于图形处理器 GPU 的通用计算逐渐成为主流计算模式。为了降低 GPU 程序设计的难度，提出一种适合于GPU 体系结构的非阻塞并行队列数据结构。通过对并行队列进行语义松弛，该数据结构能够有效利用队列操作的并行性。同时，还提出了高速并行队列插入和删除算法。使用线性化准则对该并行队列的正确性进行验证。实验表明，所提出的并发队列能够达到远高于目前多核 CPU 和 GPU 并行队列的性能，分别超越现有最好结果20倍和200倍以上。
근년래，기우도형처리기 GPU 적통용계산축점성위주류계산모식。위료강저 GPU 정서설계적난도，제출일충괄합우GPU 체계결구적비조새병행대렬수거결구。통과대병행대렬진행어의송이，해수거결구능구유효이용대렬조작적병행성。동시，환제출료고속병행대렬삽입화산제산법。사용선성화준칙대해병행대렬적정학성진행험증。실험표명，소제출적병발대렬능구체도원고우목전다핵 CPU 화 GPU 병행대렬적성능，분별초월현유최호결과20배화200배이상。
Recent years have witnessed a strong momentum of general purpose computing on graphics processing units (GPUs).To ease the difficulty of developing highly efficient massively parallel programs on GPU,this paper introduces a non-blocking concurrent queue data structure suitable for GPUs architecture.By applying semantic-relaxation on concurrent queue,the proposed data structure is able to effectively make use of the concurrency of queuing operations.Meanwhile this paper also presents efficient insert and delete algorithms of high-speed concurrent queues.Experiments indicate that our concurrent queue significantly outperforms the performances of existing multi-core CPU and GPU concurrent queue data structures by 20 and 200 fold respectively.The correctness of the proposed concurrent queue is validated by the linearisability criteria.