Exploration into the performance of asymmetric d-ary heap-based algorithms for the HSA architecture.

详细信息   

• 作者：Adams ; Stephen Blake.
• 学历：M.S.
• 年：2014
• 毕业院校：The University of Mississippi
• Department：Computer Science
• ISBN：9781321045666
• CBH：1560785
• Country：USA
• 语种：English
• FileSize：2501039
• Pages：95

文摘

Heterogeneous computing is a fairly recent trend in both hardware and software design； based around identifying the opportunities presented by utilizing all available hardware components in a computing system to perform a computationally intensive task in the most efficient way possible. One incredibly interesting field of the heterogeneous computing paradigm is general purpose computing on the graphic processing unit. General purpose computing on the graphic processing unit consists of utilizing the hardware capabilities of the graphic processing unit to perform computationally intensive tasks which exhibit many opportunities for parallel execution. While many vector or matrix-based data structures and algorithms showcase the performance benefits through this computing paradigm,many graph/tree-based data structures and algorithms are understood to be unsuitable for the nature of the GPGPU computing paradigm. The d-heap,a tree-based data structure,has undergone many design changes to take advantage of different trends in computer technology. The introduction of the memory hierarchy and the popularity of varying levels of data caches presented the development of the implicit d-heap which ensured that child nodes would not span across cache blocks. Based upon the general structural design of the implicit d-heap,is the asymmetric d-heap,introduced by Brian Vinter and Weifeng Liu. The asymmetric d-heap seeks a heterogeneous solution to the common heap data structure that utilizes both the throughput oriented processing cores of the graphic processing unit and the latency oriented processing cores of the central processing unit. We explore both the limitations of current GPGPU computing solutions and the possible performance benefit opportunities of a truly heterogeneous system in understanding the nature of the ad-heap data structure which is designed specifically for the tightly coupled THCTruly Heterogeneous Computing) architectural concept promoted by the HSAHeterogeneous Systems Architecture) Foundation. Using the batch \textit{k}-selection algorithm,the behavior behind the design of the \textit{ad}-heap presents a great deal of interesting information which can be utilized in the design of future heterogeneous solutions for existing data structures and associated algorithms which would normally not benefit from current GPGPU technology. Using both a loosely coupled discrete-GPU based experimental platform and a more tightly-coupled accelerated processing unit-based platform； we explore many of the limitations concerning the asymmetric \textit{d}-heap design by understanding the performance and behavior of the design on both platforms. We do so by presenting a more accurate and practical implementation of the \textit{ad}-Heap design for both experimental platforms and addressing the performance metrics and limitations uncovered by the series of experiments. By understanding these limitations and analyzing the different aspects of the general design； we begin to understand many of the design decisions and other general details that have to be considered when distributing the computational workload between both devices on a HSA-based architecture.