Abstract: Histogram generation is an inherently sequential loop computation with irregular data dcpcndcncc,which has a full range of applications in diverse fields. However, the presence of irregular memory access in histogram loop nest poses an obstacle to its paralleled execution using a massive number of fincgrained threads due to access latency leaded by bank conflicts. It is non-trivial to accelerate histogram generation algorithm on parallel platform, particularly on the state-of-the-art parallel platform, graphics processing unit (GPU). For reducing bank conflicts, utilization of padding technique can evenly distribute shared memory access of multiple threads to different banks and largely exploit GPU's potential on accelerating histogram generation. Moreover, efficient near-optimal configuration search model can guide programmers choosing appropriate GPU execution parameters for higher performance. Experimental result demon- strates the improved histogram generation algorithm has approximate 42 0 o to 88 0 o speedups than traditional histogram generation algorithm on GPU.

Key words: GPU, CUIDA，Histogram, Padding