Hybrid Static/Dynamic Scheduling for Task Dataflow Parallel Programs

任务数据流并行程序的混合静态/动态调度

• 批准号: EP/L027402/1
• 负责人: Hans Vandierendonck
• 金额: $ 12.26万
• 依托单位: Queen's University Belfast
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2014
• 资助国家: 英国
• 起止时间: 2014 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FL027402%2F1
• 关键词: Hybrid; Static; Dynamic; Scheduling; Task

Traditionally, software development has benefit tremendously from the exponential performance increase that processors, the central computing units in computers, have witnessed. Up until about 2004, processor performance doubled about every 18 to 24 months. This trend could however not be sustained due to physical limitations, most importantly constraints on energy consumption. For this reason, processor manufacturars have switched to integrating multiple processor cores on a chip. These processors still allow an overall performance growth at similar rates as before 2004. However, software must be rewritten to utilize all processing cores in order to benefit from this performance potential. The pressure is now on software development as software must have several independent threads of execution, i.e., software must be parallel (or concurrent). The development of high-performance parallel software is non-trivial and is a specialisation of its own. The key problem with parallelism is that it must be taken into account throughout the design of software. Moreover, optimising the performance of parallel software requires many code changes that often increase performance only on specific computers. Parallelism in software imposes a dual expertise on software developers: expertise in the problem domain and expertise in parallel programming. Such a dual expertise is counterproductive in many respects and potentially leads to more costly, less effective and less functional software.This project aims to alleviate the dual expertise problem by advancing knowledge and technology on parallel programming models based on task dataflow. These programming models separate the specification of the program from the detection of parallelism, thus shifting the focus towards correctness of software and ease of development. Task dataflow models however depend on dynamic analysis of parallelism, which adds to the execution time overhead and restricts the model to programs with coarse-grain parallelism. In contrast, it is known that statically scheduled programs (where parallelism has been decided and mapped out before the program executes) allow considerably finer-grain parallelism.This project will investigate techniques to reconcile the benefits of dynamically scheduled task dataflow programs with the benefits of static scheduling. To this end, we will investigate compilation techniques and extensions to dynamic schedulers that allow embedding statically scheduled fine-grain parallel components inside coarse-grain dynamically scheduled programs.If successful, this project will generate both scientific knowledge and long-term practical value for the ICT industry. This research programme will also make initial steps in the philosophically important issue of recompiling parallel programs, an issue that has been largely ignored in the past due to its sheer complexity. This research programme furthermore aligns with the EPSRC ICT capability priority on Many-core architectures and concurrency in distributed and embedded systems".

传统上，软件开发从处理器（计算机中的中央计算单元）所见证的指数级性能增长中受益匪浅。直到2004年，处理器的性能大约每18到24个月就翻一番。然而，由于物理限制，最重要的是能源消耗的限制，这种趋势无法持续下去。由于这个原因，处理器制造商已经转向在一个芯片上集成多个处理器内核。这些处理器仍然允许整体性能以类似于2004年之前的速度增长。但是，为了从这种性能潜力中获益，必须重写软件以利用所有处理核心。现在软件开发的压力在于软件必须有几个独立的执行线程，也就是说，软件必须是并行的（或并发的）。高性能并行软件的开发是非常重要的，它本身就是一个专业领域。并行性的关键问题是在整个软件设计过程中必须考虑到它。此外，优化并行软件的性能需要更改许多代码，而这些代码通常只会在特定的计算机上提高性能。软件中的并行性要求软件开发人员具备双重专业知识：问题领域的专业知识和并行编程方面的专业知识。这样的双重专业知识在许多方面是适得其反的，并且可能导致成本更高、效率更低和功能更差的软件。本项目旨在通过推进基于任务数据流的并行编程模型的知识和技术来缓解双专家问题。这些编程模型将程序规范与并行性检测分离开来，从而将焦点转移到软件的正确性和开发的便利性上。然而，任务数据流模型依赖于并行性的动态分析，这增加了执行时间开销，并将模型限制在具有粗粒度并行性的程序中。相比之下，我们知道静态调度程序（在程序执行之前已经确定并规划了并行性）允许相当细粒度的并行性。本项目将研究协调动态调度任务数据流程序的优点与静态调度优点的技术。为此，我们将研究允许在粗粒度动态调度程序中嵌入静态调度的细粒度并行组件的编译技术和动态调度程序的扩展。如果成功，该项目将为ICT行业带来科学知识和长期实用价值。这个研究项目也将在重新编译并行程序这一哲学上重要的问题上迈出第一步，这个问题在过去由于其纯粹的复杂性而在很大程度上被忽视了。该研究计划进一步与EPSRC在分布式和嵌入式系统中的多核架构和并发性方面的ICT能力优先级保持一致。”

项目成果

Fast load balance parallel graph analytics with an automatic graph data structure selection algorithm

• DOI: 10.1016/j.future.2020.06.005
• 发表时间: 2020-11
• 期刊: Future Gener. Comput. Syst.
• 作者: Jiawen Sun;Hans Vandierendonck;Dimitrios S. Nikolopoulos

A scalable and composable map-reduce system

可扩展且可组合的映射缩减系统

• DOI: 10.1109/bigdata.2016.7840854
• 发表时间: 2016
• 作者: Arif M

Reducing the burden of parallel loop schedulers for many-core processors

减轻多核处理器并行循环调度程序的负担

• DOI: 10.1145/3178487.3178517
• 发表时间: 2018
• 作者: Arif M

Accelerating Graph Analytics by Utilising the Memory Locality of Graph Partitioning

• DOI: 10.1109/icpp.2017.27
• 发表时间: 2017-09
• 期刊: 2017 46th International Conference on Parallel Processing (ICPP)
• 作者: Jiawen Sun;Hans Vandierendonck;Dimitrios S. Nikolopoulos

OpenMP: Heterogenous Execution and Data Movements

OpenMP：异构执行和数据移动

• DOI: 10.1007/978-3-319-24595-9_16
• 发表时间: 2015
• 作者: Alessi F