Histogram generation is an inherently sequential loop computation with irregular data-dependence, 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 fine-grained 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 demonstrates the improved histogram generation algorithm has approximate 42% to 88% speedups than traditional histogram generation algorithm on GPU.%直方图生成算法(Histogram Generation)是一种顺序的非规则数据依赖的循环运算,已在许多领域被广泛应用.但是,由于非规则的内存访问,使得多线程对共享内存访问会产生很多存储体冲突(Bank Conflict),从而阻碍并行效率.如何在并行处理器平台,特别是当前最先进的图像处理单元(Graphic Processing Unit,GPU)实现高效的直方图生成算法是很有研究价值的.为了减少直方图生成过程中的存储体冲突,通过内存填充技术,将多线程的共享内存访问均匀地分散到各个存储体,可以大幅减少直方图生成算法在GPU上的内存访问延时.同时,通过提出有效可靠的近似最优配置搜索模型,可以指导用户配置GPU执行参数,以获得更高的性能.经实验验证,在实际应用中,改良后的算法比原有算法性能提高了42％～88％.
展开▼
