Date Added: Sep 2011
While Graphics Processing Units (GPUs) show high performance for problems with regular structures, they do not perform well for irregular tasks due to the mismatches between irregular problem structures and SIMD-like GPU architectures. In this paper, the authors explore software approaches for improving the performance of irregular parallel computation on graphics processors. They propose general approaches that can eliminate the branch divergence and allow runtime load balancing. They evaluate the optimization rules and approaches with the n-queens problem benchmark. The experimental results show that the proposed approaches can substantially improve the performance of irregular computation on GPUs.