C++ High Performance/

...

/

Divide and Conquer

Divide and Conquer

Learn about the divide and conquer strategy, its implementation, and its performance evaluation.

We'll cover the following...

Overview

An algorithm technique for dividing a problem into smaller subproblems is called divide and conquer. We will here implement another version of a parallel transform algorithm using divide and conquer. It works as follows: if the input range is smaller than a specified threshold, the range is processed; otherwise, the range is split into two parts:

  • The first part is processed on a newly branched task
  • The other part is recursively processed at the calling thread

The following illustration shows how the divide and conquer algorithm would recursively transform a range using the following data and parameters:

  • Range size: 16
  • Source range contains floats from 1.0
...