Query: Degree of-Node Task Scheduling of Fine-Grained Parallel Programs on Heterogeneous Systems

Candidate papers:

abstract: Processor specialization has become the development trend of modern processor industry. It is quite possible that this will still be the main stream in the next decades of semiconductor era. As the diversity of heterogeneous systems grows, organizing computation efficiently on systems with multiple kinds of heterogeneous processors is a challenging problem and will be a normality. In this paper, we analyze some state of the art task scheduling algorithms of heterogeneous computing systems and propose a Degree of Node First (DONF) algorithm for task scheduling of fine grained parallel programs on heterogeneous systems. The major innovations of DONF include: 1) simplifying task priority calculation for directed acyclic graph (DAG) based fine grained parallel programs which not only reduces the complexity of task selection but also enables the algorithm to solve the scheduling problem for dynamic DAGs; 2) building a novel communication model in the processor selection phase that makes the task scheduling much more efficient. They are achieved by exploring finegrained parallelism via a dataflow program execution model, and validated through experimental results with a selected set of benchmarks. The results on synthesized and real world application DAGs show a very good performance. The proposed DONF algorithm significantly outperforms all the evaluated state of the art heuristic algorithms in terms of scheduling length ratio (SLR) and efficiency.
author_names: Han Lin

Mingfan Li

Chengfan Jia

Junnan Liu

Hong An
title: Degree of Node Task Scheduling of Fine Grained Parallel Programs on Heterogeneous Systems
venue: Journal of Computer Science and Technology
year: 2019

abstract: The task based parallel programming model is widely used to parallelize dense linear algebra (DLA) [4] This model is utilized with tiled algorithms that divide DLA routines into small sub tasks with dependencies [2] This approach enables tasks to be executed asynchronously while preserving dependencies. Thus. it not only reduces synchronization points (a disadvantage of the fork join approach [4] but facilitates load balancing in a heterogeneous system. Fine grained partitioning by tiled algorithms achieves a high degree of parallelism, but it causes data communication overhead proportional in the number of tiles. This overhead is particularly noticeable with distributed systems, where nodes communicate via a network rather than shared memory. Therefore, a method to obtain a tile size that gives the best performance is required. In this paper, we reduce the data communication overhead by caching data inside nodes, and by finding the optimal tile size for partitioning data in the task based programming model.
author_names: Yonghyun Ryu
title: Node level optimization by caching data and choosing the optimal tile size for parallel dense linear algebra on distributed systems: student research abstract
venue: SAC
year: 2018

abstract: Exascale computers are expected to be made of millions of nodes and billions of threads of execution. To support high degrees of parallelism for various applications, the threads and task scheduling needs to be fine grained and should be able to execute in the order of tens to a few hundred CPU cycles. Overdecomposition of applications to fine grained applications is ideal to achieve maximum speed up and there is a need for a parallel runtime system which can launch tasks for execution and report the results with very low latency at high levels of concurrency. This work aims at enabling the launch of independent tasks on many core accelerator hardware architectures and mechanisms to support tasks of fine granularity on the order of tens of few hundreds of CPU cycles at a large scale. This work also focuses on analyzing the performance of various queue based data structures commonly used in parallel programming languages and runtime systems. This analysis is essential for designing an efficient runtime system for scheduling billions of tasks with very low latency and high throughput. Lastly, the runtime would also support data dependencies and task dependencies required for task based shared memory parallel programming.
author_names: Poornima Nookala

DR Peter Dinda

DR Kyle Hale
title: XTASK eXTreme fine grAined concurrent taSK invocation runtime
year: 2017

abstract: We describe a programming abstraction for heterogeneous parallel hardware, designed to capture a wide range of popular parallel hardware, including GPUs, vector instruction sets and multicore CPUs. Our abstraction, which we call HPVM, is a hierarchical dataflow graph with shared memory and vector instructions. We use HPVM to define both a virtual instruction set (ISA) and also a compiler intermediate representation (IR) The virtual ISA aims to achieve both functional portability and performance portability across heterogeneous systems, while the compiler IR aims to enable effective code generation and optimization for such systems. HPVM effectively supports all forms of parallelism used to achieve computational speedups (as opposed to concurrency) including task parallelism, coarse grain data parallelism, fine grain data parallelism, and pipelined parallelism. HPVM also enables flexible scheduling and tiling: different nodes in the dataflow graph can be mapped flexibly to different combinations of compute units, and the graph hierarchy expresses memory tiling, essential for achieving high performance on GPU and CPU targets.
author_names: Prakalp Srivastava

Maria Kotsifakou

Vikram S Adve
title: HPVM: A Portable Virtual Instruction Set for Heterogeneous Parallel Systems
venue: ArXiv
year: 2016

abstract: Modern GPUs are gradually used by more and more cluster computing systems as the high performance computing units due to their outstanding computational power, whereas bringing node level architectural heterogeneity to cluster. In this paper, based on MPI and CUDA programming model, we aim to investigate task scheduling for GPU heterogeneous cluster by taking into account the node level heterogeneous characteristics. At first, based on our GPU heterogeneous cluster, we classify executing tasks to six major classifications according to their parallelism degrees, input data sizes, and processing workloads. Then, aiming to realize optimal mapping between tasks and computing resources, a task scheduling strategy is presented. The strategy consists of two key algorithms. The first is packing task algorithm (PTA) used to pack multiple tasks into a single task, such packing provides us a way of task classification converting according to the characteristic of computing resources. The second is system level scheduling algorithm(SLSA) used to distribute parallel and sequential tasks to corresponding nodes, to maintain the load balance.
author_names: Keliang Zhang

Baifeng Wu
title: Task Scheduling for GPU Heterogeneous Cluster
venue: 2012 IEEE International Conference on Cluster Computing Workshops
year: 2012

abstract: The goal of this paper is to implement an efficient matrix inversion of symmetric positive definite matrices on heterogeneous GPU based systems. The matrix inversion procedure can be split into three stages: computing the Cholesky factorization, inverting the Cholesky factor and calculating the product of the inverted Cholesky factor with its transpose to get the final inverted matrix. Using high performance data layout, which represents the matrix in the system memory with an optimized cache aware format, the computation of the three stages is decomposed into fine grained computational tasks. The data flow programming model can then be represented as a directed acyclic graph, where nodes represent tasks and edges the dependencies between them. Standard implementations of matrix inversions as well as other numerical algorithms (e.g. linear and eigenvalue solvers) available in the state of theart numerical libraries (e.g. LAPACK) rely on the expensive fork join paradigm to achieve parallel performance and are characterized by artifactual synchronization points, which have to be removed to fully exploit the underlying hardware capabilities. Our tile algorithmic approach allows to remove those bottlenecks and to flawlessly execute the tasks, as soon as the data dependencies are satisfied. A hybrid runtime environment system becomes paramount to dynamically schedule the numerical kernels on the available processing units, whether it is a hardware accelerator (i.e, GPU) or a homogeneous multicore (i.e. x86) and this is transparently carried out from the user. Preliminary results are shown on a dual socket quadcore Intel Xeon 2.67GHz workstation with two nVIDIA Fermi C2070 GPU cards. Our implementation (448 Gflop/s) results in up to 5 and 6 fold improvement compared to the equivalent routines from MAGMA V1.0 and PLASMA V2.4, respectively, and 10 fold improvement compared to LAPACK V3.2 linked with multithreaded Intel MKL BLAS V10.2, with a matrix size of 24960x 24960. Keywords Matrix Inversion; Tile Algorithms; Dynamic LoadBalanced Scheduling; Heterogeneous CPU GPU Computing
author_names: Huda Ibeid

Dinesh K Kaushik

David E Keyes

Hatem Ltaief
title: Toward Accelerating the Matrix Inversion Computation of Symmetric Positive Definite Matrices on Heterogeneous GPU Based Systems
year: 2011

abstract: We present a runtime framework for the execution of work loads represented as parallel operator directed acyclic graphs (PO DAGs) on heterogeneous multi core platforms. PO DAGs combine coarse grained parallelism at the graph level with fine grained parallelism within each node, lending naturally to exploiting the intra and inter processing element parallelism present in heterogeneous platforms. We identify four important criteria Suitability, Locality, Availability and Criticality (SLAC) and show that all these criteria must be considered by a heterogeneous runtime framework in order to achieve good performance under varying application and platform characteristics. The proposed model driven runtime (MDR) considers all the aforementioned factors, and tradeoffs among them, by utilizing performance models. These performance models are used to drive key run time decisions such as mapping of tasks to PEs, scheduling of tasks on each PE, and copying data between memory spaces. We discuss the software architecture and implementation of MDR, and evaluate it using several benchmark programs on three different heterogeneous platforms that contain multi core CPUs and GPUs. The hardware platforms represent server, laptop, and netbook class systems. MDR achieves up to 4.2X speedup (1.5X on average) over the best of CPU only, GPU only, round robin, GPU first, and utilization driven schedulers. We also perform a sensitivity analysis that establishes the importance of considering all four SLAC criteria in order to achieve high performance execution in a heterogeneous runtime framework.
author_names: Jacques A Pienaar

Anand Raghunathan

Srimat T Chakradhar
title: MDR: performance model driven runtime for heterogeneous parallel platforms
venue: ICS '11
year: 2011

abstract: Recent and future parallel clusters and supercomputers use symmetric multiprocessors SMPs and multi core processors as basic nodes, providing a huge amount of parallel resources. These systems often have hierarchically structured interconnection networks combining computing resources at different levels, starting with the interconnect within multi core processors up to the interconnection network combining nodes of the cluster or supercomputer. The challenge for the programmer is that these computing resources should be utilized efficiently by exploiting the available degree of parallelism of the application program and by structuring the application in a way which is sensitive to the heterogeneous interconnect.In this article, we pursue a parallel programming method using parallel tasks to structure parallel implementations. A parallel task can be executed by multiple processors or cores and, for each activation of a parallel task, the actual number of executing cores can be adapted to the specific execution situation. In particular, we propose a new combined scheduling and mapping technique for parallel tasks with dependencies that takes the hierarchical structure of modern multi core clusters into account. An experimental evaluation shows that the presented programming approach can lead to a significantly higher performance compared to standard data parallel implementations.
author_names: Jorg Dummler

Thomas Rauber

Gudula Runger
title: Combined scheduling and mapping for scalable computing with parallel tasks
venue: BIOKDD 2012
year: 2012

abstract: Recent and future parallel clusters and supercomputers use symmetric multiprocessors (SMPs) and multi core processors as basic nodes, providing a huge amount of parallel resources. These systems often have hierarchically structured interconnection networks combining computing resources at different levels, starting with the interconnect within multi core processors up to the interconnection network combining nodes of the cluster or supercomputer. The challenge for the programmer is that these computing resources should be utilized efficiently by exploiting the available degree of parallelism of the application program and by structuring the application in a way which is sensitive to the heterogeneous interconnect. In this article, we pursue a parallel programming method using parallel tasks to structure parallel implementations. A parallel task can be executed by multiple processors or cores and, for each activation of a parallel task, the actual number of executing cores can be adapted to the specific execution situation. In particular, we propose a new combined scheduling and mapping technique for parallel tasks with dependencies that takes the hierarchical structure of modern multi core clusters into account. An experimental evaluation shows that the presented programming approach can lead to a significantly higher performance compared to standard data parallel implementations.
author_names: Jorg Dummler

Thomas Rauber

Gudula Runger
title: Combined scheduling and mapping for scalable computing with parallel tasks
venue: Sci. Program.
year: 2012

abstract: Current software and hardware limitations prevent Many Task Computing (MTC) workloads from leveraging hardware accelerators boasting Many Core Computing architectures. This work aims to address the programmability gap between MTC and accelerators, through the innovative CUDA middleware GeMTC. By working at the warp level, GeMTC enables heterogeneous task scheduling and 10x number of workers compared to CUDA. In order to span multiple accelerators across nodes, we have adopted the Swift parallel programming system, which can both support fine grained millisecond tasks and extreme scale supercomputers at 100K cores. Keywords Many Task Computing, Swift, GPGPU, CUDA
author_names: Scott J Krieder

Benjamin Grimmer

Dustin Shahidehpour

Jeffrey Johnson

Justin M Wozniak

Michael Wilde

Ioan Raicu
title: Towards Efficient Many Task Computing on Accelerators in High End Computing Systems
year: 2013