Vectorized C++ Parallel Algorithms with HPX

In preparation for my talk at CppCon 2016 last week I decided to have a closer look at the possibility to add vectorization to HPX’s parallel abstractions1The slides for this talk can be downloaded here. The goal was to avoid using compiler specific extensions while enabling vectorization support. At the same time, I wanted to be able to integrate this with the already existing parallel algorithms in HPX, proving again that higher level APIs and best possible performance go hand in hand in HPX.

Notes

Notes
1 The slides for this talk can be downloaded here

HPX and Index-based C++ Parallel Loops

In Jacksonville at the winter 2016 C++ standardization meeting, Intel presented the second revision of their standardization proposal targeting index-based parallel for-loops (the latest document at the time of this writing is P0075R1). This document describes a couple of basic parallel for-loop constructs which complement the existing parallel algorithms which we have already implemented for quite some time in HPX. The following is taken from this document:

HPX and C++17

During the Jacksonville meeting of the C++ standards committee last week the so called Parallelism TS was accepted into the next official International Standard, also known as C++17. We can now expect for all major vendors of C++ compilers to implement the very same parallelism facilities as HPX has exposed for almost 2 years already!

A while back, we wrote about how HPX implements parallel algorithms. At the time of that writing, these parallel algorithms were freshly published as a WG21 Technical Specification with the goal of moving them into the main C++ International Standard at some point in the future. Since then, we have continued to work hard on implementing HPX versions of the proposed algorithms. In addition, we have added extensions in our implementation such as the “task” policy which enables asynchronous execution of the algorithm. We have also spent a lot of time tuning our implementation to make it as performant as possible. For instance, we have shown that it is possible for the relatively higher-level parallelization abstractions in HPX to match or to even outperform the performance of equivalent applications based on well-known and well-honed technologies like OpenMP.

The STE||AR Group is proud of the fact that our implementation in HPX has provided implementation, usage experience, and early feedback to the C++ committee. These contributions have helped to get this specification into the new standard. We hope to continue to be a flexible and valuable testbed for all future standardization proposals relating to parallelism and concurrency.

C++ and the Heterogeneous Challenge

As HPC shifts its long range focus from peta- to exascale, the need for programmers to be able to efficiently utilize the entirety of a machine’s compute resources has become more paramount. This has grown increasingly difficult as most of the Top500 machines utilize, in some capacity, hardware accelerators like GPUs and coprocessors which often require special languages and APIs to take advantage of them. In C++ the concept of executors, as currently discussed by the C++ standardization committee, has created a possibility for a flexible, and dynamic choice of the execution platform for various types of parallelism in C++, including the execution of user code on heterogeneous resources like accelerators and GPUs in a portable way. This will also allow to develop a solution that seamlessly integrates iterative execution (parallel algorithms) with other types of parallelism, such as task-based parallelism, asynchronous execution flows, continuation style computation, and explicit fork-join control flow of independent and non-homogeneous code paths.

HPX and C++ Parallel Algorithms

In Lenexa (May 2015), the C++ standardization committee has finalized the work related to the Technical Specification for C++ Extensions for Parallelism (the latest document at the time of this writing is N4507) . This document describes parallel algorithms which will extend and complement the (sequential) standard library algorithms we all love and use for over a decade now. This is an important – albeit only first – step towards standardizing higher level abstractions for parallelism and concurrency in C++.

HPX and C++ Task Blocks

The quest for finding efficient, convenient, and widely usable higher level parallelization constructs in C++ is continuing. With the standardization document N4411, a group of authors from Intel and Microsoft propose thetask_blockfacility which formalizes fork-join parallelism. From the paper (slightly edited):

HPX and C++ Executors

The STE||AR Group has implemented executors in HPX which, as proposed by the C++ standardization proposal called ‘Parallel Algorithms Need Executors’ (document number N4406), are objects that choose where and how a function call is completed. This is a step in the right direction for HPX and parallelism because executors give more flexibility on how and where task based work should be accomplished and gives the programmer a means to compose executors nicely with execution policies inside of algorithm implementations.