SHF: Small: Toward True Heterogeneous Computing: Concurrent Data Structure Design and Optimization

图形处理单元(GPU)的引入改变了并行计算的格局，用于处理现代计算机中的密集计算任务。这一现象的核心是大规模多线程、数据并行的计算机体系结构，具有令人印象深刻的加速评级，提供低成本的超级计算以及诱人的功率预算。虽然GPU可以处理计算密集型任务，提供高通量，但计算机的大脑，即中央处理器(CPU)，擅长处理以延迟为导向的任务。CPU和GPU通过共享数据结构相互通信，当处理在不同级别对CPU和GPU造成负担的异类应用时，需要有效地设计这些共享数据结构，以避免CPU和GPU的使用不匹配。该项目力求通过设计和实施高度可伸缩的并发数据结构(CDS)，确保无论工作量大小，这种效率始终存在。所开发的CDSS通过开发库和真实世界的真实异构性工作负载进行了实际测试。该项目的结果、发现和成果被贡献给开源社区，并通过学术出版物、在线材料和网站向社区传播。最近，在基于GPU的计算平台上支持细粒度数据共享和线程通信，使应用程序能够通过共享虚拟内存中的数据结构，从简单、廉价、多样化的CPU和GPU协作模型中受益。在新启用的CPU-GPU协作模型中，面向延迟的CPU线程和面向吞吐量的GPU线程通过共享数据结构相互同步和通信。因此，这些数据结构的效率对于真正的异构式计算的成功至关重要。众所周知，设计跨不同并发级别进行良好伸缩的CDS是一项非常具有挑战性的任务。在异类平台上增加的并发性使得它在性能和正确性方面更具挑战性。虽然在传统CPU的背景下已经进行了大量的研究，但在异质平台的背景下却知之甚少。当与硬件共同设计时，高度可扩展的CDS设计的全部潜力可以实现；当前的硬件是第一代设计，没有很好地理解处理器间的细粒度数据共享和线程通信。虽然该项目的主要目标是设计高效的CDS，其性能可以很好地扩展到不同平台上的一系列并发需求，但另一个重要目标是改进和优化对高效细粒度数据共享线程通信至关重要的硬件支持，例如处理器间高速缓存一致性、GPU线程调度和SIMD感知优化。为此，本研究采用软硬件协同设计的方法，通过六个具体的研究目标(减少负载、开发争用管理方案、优化CPU-GPU高速缓存一致性协议、SIMD感知优化、架构感知操作映射、库和真实世界应用程序开发)来解决三个基本挑战(顺序瓶颈、内存争用和架构异构性)。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The introduction of Graphics Processing Units (GPU) for handling intensive computing tasks in modern-day computers has changed the landscape for parallel computing. At the core of this phenomenon are massively-multithreaded, data-parallel computer architectures with impressive acceleration ratings, offering low-cost supercomputing together with attractive power budgets. While the GPU can handle computation-intensive tasks providing high through, the computer's brains, the Central Processing Unit (CPU), is good at handling latency-oriented tasks. The CPU and GPU communicate with each other through shared data structures that need to be efficiently designed in order to avoid mismatch in the use of the CPU and GPU when handling heterogeneous applications that tax the CPU and GPU at different levels. This project seeks to ensure such efficiencies always exist regardless of workload, through the design and implementation of highly-scalable Concurrent Data Structures (CDSs). The developed CDSs are practically tested by developing library and real-world true heterogeneous workloads. The results, findings, and outcomes of the project are contributed to open-source community and disseminated through scholarly publications, online materials, and websites to the community.The recent support of fine-grained data sharing and thread communication on GPU-powered computing platforms allows applications to benefit from easy, cheap, diverse CPU and GPU collaboration models through data structures in shared virtual memory. In newly enabled CPU-GPU collaboration models, latency-oriented CPU threads and throughput-oriented GPU threads synchronize and communicate with one another through shared data structures. Therefore, the efficiency of these data structures is crucial for the success of true heterogeneous computing. Designing a CDS that scales well across different concurrency levels is known to be a very challenging task. The increased concurrency on heterogeneous platforms makes it even more challenging with respect to performance and correctness. While a significant amount of research has been done in the context of traditional CPUs, there is very little known in the context of heterogeneous platforms. The full potential of a highly-scalable CDS design can be achieved when co-designed with hardware; current hardware is the first generation designs that have not benefited from a good understanding of inter-processor fine-grained data sharing and thread communication. While the primary objective of the project is designing efficient CDSs whose performance scales well across a spectrum of concurrency demands on heterogeneous platforms, the other important target is to improve and optimize hardware support crucial for efficient fine-grained data sharing thread communication, such as inter-processor cache coherence, GPU thread scheduling, and SIMD aware optimizations. To that end, this research takes software-hardware co-design approach using six specific research aims (reducing loads, developing contention management schemes, optimizing CPU-GPU cache coherence protocol, SIMD aware optimization, architecture aware operation mapping, library and real-world application development) to address three fundamental challenges (sequential bottlenecks, memory contention, and architectural heterogeneity).This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.