Data-Parallel Algorithms for Efficient Query Processing on Modern Hardware

现代硬件上高效查询处理的数据并行算法

• 批准号: RGPIN-2020-06639
• 负责人: Chester, Sean
• 金额: $ 1.75万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749788
• 关键词: Data; Parallel; Algorithms; Efficient; Query

The United Nations has highlighted a Sustainable Development Goal (8.4) to improve global resource efficiency and "decouple economic growth from environmental degradation" by 2030. Data analytics is a characteristic example of this challenge: it is an impetus of the knowledge economy, but it also is growing at an exponential scale. Our current solution to manage the energy demands of exponential growth is to gain efficiency by moving analytics into hyperscale data centres, like Amazon EC2. However, according to the International Energy Agency's latest digilisation report, this move will be half complete by 2020 (measured in terms of TWh); that is to say, this source for efficiency gains will soon be exhausted. Data analytics imminently needs another source. All computers today are complex, including those that form hyperscale clouds. Fully utilising a modern computer, however, is very difficult: it automatically reorders computations, executes multiple instructions simultaneously, and coordinates computation across multiple processors and specialised accelerators. Furthermore, a "modern computer" is a moving target, as manufacturers such as Intel, AMD, and Nvidia tirelessly innovate. Unsurprisingly, then, there are computational tasks---particularly those involving high-value text, spatio-temporal, and social data sources---that squander most of the opportunities inside each computer for parallel computing. We need novel algorithms and data structures that more efficiently utilise all of a complex, modern computer and can scale in the cloud so that individual analytics queries do not scale out so unnecessarily far. Perhaps even moreso, we need diverse highly qualified personnel with sufficiently advanced skills to apply these ideas to an even more resource-efficient and innovative Canadian industry. Concretely, this research program will design novel algorithms and data structures to democratise access to additional parallelism in modern computers and dedicated graphics processing units (GPUs). We will create parallel-friendly data structures for text that support recent advances in natural language processing (NLP) so that parallel analytics and modern NLP can co-develop. We will define a simpler computational paradigm for graph processing on GPUs that allows analysts to benefit from GPU "latency hiding" while focusing on higher-level algorithmic concepts. And we will define new GPU-centric data structures for multi-dimensional data that scales across servers so that traditional data analytics can better exploit multiple levels of parallelism. In all, this research will broaden the scope of what types of data can effectively leverage modern computing platforms. As a result, scientists and industry professionals alike can generate more knowledge faster, with more data, in a more resource-efficient manner.

联合国强调了一个可持续发展的目标（8.4），以提高全球资源效率并“使环境退化使经济增长与2030年的经济增长相距。我们当前管理指数增长的能源需求的解决方案是通过将分析转移到超大数据中心（例如亚马逊EC2）来提高效率。但是，根据国际能源机构的最新二元报告，该举动将在2020年完成一半（以TWH衡量）；也就是说，这种提高效率的来源很快就会耗尽。数据分析迫在眉睫需要另一个来源。当今的所有计算机都是复杂的，包括形成高度云的计算机。但是，充分利用现代计算机非常困难：它会自动重新计算，同时执行多个指令，并在多个处理器和专业加速器之间进行协调计算。此外，“现代计算机”是一个移动的目标，因为英特尔，AMD和Nvidia等制造商不懈地创新。因此，毫不奇怪，有一些计算任务 - 尤其是涉及高价值文本，时空和社交数据源的任务 - 浪费了每台计算机内的大部分机会进行并行计算。我们需要新颖的算法和数据结构，这些算法和数据结构更有效地利用了所有复杂的现代计算机，并且可以在云中扩展，以使单个分析查询不会那么不必要地扩展。也许即使是Moreso，我们也需要具有足够高级技能的高素质高素质的人员，才能将这些想法应用于更具资源效率和创新性的加拿大行业。具体而言，该研究计划将设计新颖的算法和数据结构，以民主化现代计算机和专用图形处理单元（GPU）中其他并行性的访问。我们将为文本创建并行友好的数据结构，以支持自然语言处理（NLP）的最新进展（NLP），以便并行分析和现代NLP可以共同开发。我们将在GPU上定义一个更简单的计算范式，以使分析师从GPU“潜伏期隐藏”中受益，同时着眼于高级算法概念。我们将为多维数据定义新的以GPU为中心的数据结构，该数据跨服务器扩展，以便传统的数据分析可以更好地利用多个级别的并行性。总的来说，这项研究将扩大哪些类型的数据可以有效利用现代计算平台的范围。结果，科学家和行业专业人员都可以以更高的资源有效的方式来更快地产生更多的知识。