Team Hortons

Once upon a time there was a team. In their programs, they never used floats. They only used double doubles.

Parallelization of the C++ Standard Library: Intel Parallel STL, MCSTL, and C++17

Introduction: The Standard Template Library

The Standard Template Library (STL) for C++ is a library that provides a set of classes and functions for C++, like iterators and vectors. The STL is divided in four parts: algorithms, containers, functors, and iterators. For this project, we will focus on the algorithms library.

The algorithms library provides many functions to be used for ranges of elements, and use iterators or pointers to navigate through them. Some of these algorithms are:

• all_of - Tests if a condition is true for all the elements in the range
• for_each - Applies a function to all elements in the range
• find - Finds a value in the range
• sort - Sorts the elements in the range

These algorithms provide a functional way to work on collections, and are present in several programming languages. These algorithms replace what usually would be a for/while loop, shifting the attention from "how to loop" to "what to do".

<code>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
  vector<int> myVector = { 10, 6, 7, 8, 5, 4, 1, 2, 3, 9 };

  // Sorting the elements
  sort(myVector.begin(), myVector.end(), [](int a, int b) { return b < a; });

  cout << "== FOR EACH ==" << endl;
  for_each(myVector.begin(), myVector.end(), [](int i) { cout << "Element: " << i << endl; });
  cout << endl;


  cout << "== COUNTING NUMBERS LARGER THAN 6 ==" << endl;
  long nLt6 = count_if(myVector.begin(), myVector.end(), [](int i) { return i > 6; });
  cout << "There are " << nLt6 << " numbers larger than 6 in the vector" << endl << endl;


  cout << "== FINDING AN ELEMENT ==" << endl;
  vector<int>::iterator elFound = find_if(myVector.begin(), myVector.end(), [](int i) { return i > 4 && i % 6 == 0; });
  cout << "The element " << *elFound << " is the first that satisfies i > 4 && i % 6 == 0" << endl << endl;

  return 0;
}
</code>

Output:

== FOR EACH ==
Element: 10
Element: 9
Element: 8
Element: 7
Element: 6
Element: 5
Element: 4
Element: 3
Element: 2
Element: 1

== COUNTING NUMBERS LARGER THAN 6 ==
There are 4 numbers larger than 6 in the vector

== FINDING AN ELEMENT ==
The element 6 is the first that satisfies i > 4 && i % 6 == 0

These algorithms not only make the code easier to write and read, but it also tends to be faster: these algorithms are heavily optimized, making them much faster than for/while loops.

The execution for these algorithms, however, are not parallel by default: they are sequential. However, it is possible to parallelize many of these algorithms, making their execution much faster. This project will discuss three methods/implementations for parallelizing the STL: MCSTL, Intel Parallel STL, and Policy-based execution for C++17.

MCSTL

What is it?
How do we install it?
Is it free?
What algorithms are provided?

Intel Parallel STL

What is it?
How do we install it?
Is it free?
What algorithms are provided?

Policy-based execution for C++17

What is it?
How do we install it?
What algorithms are provided?

Benchmark

Benchmark results: C++17, Intel Parallel STL, MCSTL

Sources

• STL: https://en.wikipedia.org/wiki/Standard_Template_Library
• STL: http://www.cplusplus.com/reference/algorithm/
• Policy-Based execution for C++17: https://scs.senecac.on.ca/~oop345/pages/content/multi.html#alg
• Intel Parallel STL: https://software.intel.com/en-us/get-started-with-pstl*
• MCSTL: https://algo2.iti.kit.edu/singler/mcstl/

Group Members

1. Henrique Salvadori Coelho
2. Olga Belavina

Progress

-5%