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年之前类似的速度实现总体性能增长。然而，软件必须重写以利用所有处理核心，以便从这种性能潜力中受益。由于软件必须具有几个独立的执行线程，因此现在软件开发面临压力，即，软件必须是并行的（或并发的）。高性能并行软件的开发是不平凡的，是它自己的专业化。并行性的关键问题是在整个软件设计中必须考虑到它。此外，优化并行软件的性能需要许多代码更改，这些更改通常仅在特定计算机上提高性能。软件中的并行主义给软件开发人员带来了双重专长：问题领域的专长和并行编程的专长。这种双重专门知识在许多方面会产生反作用，并可能导致软件成本更高、效率更低和功能更差，本项目旨在通过提高基于任务流程的并行编程模型的知识和技术来缓解双重专门知识问题。这些编程模型将程序的规范与并行性的检测分开，从而将焦点转移到软件的正确性和易于开发上。然而，任务并行模型依赖于并行性的动态分析，这增加了执行时间开销，并将模型限制为具有粗粒度并行性的程序。相比之下，它是已知的，静态调度程序（其中并行性已被决定，并映射出程序执行前）允许相当细粒度parallel.This项目将调查技术，以调和的好处，动态调度的任务并行程序的好处，静态调度。为此，我们将研究编译技术和扩展的动态编译器，允许嵌入静态调度的细粒度并行组件内粗粒度的动态调度programmes.If成功，这个项目将产生科学知识和长期的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