Используем параллельные алгоритмы C++17 для улучшения производительности


Оглавление (нажмите, чтобы открыть):

Используем параллельные алгоритмы C++17 для улучшения производительности

847 просмотра

3 ответа

70 Репутация автора

Я пытался поиграть с новыми функциями параллельной библиотеки, предложенными в стандарте C ++ 17, но я не мог заставить его работать. Я попытался компиляции с до современных версий g++ 8.1.1 и clang++-6.0 и -std=c++17 , но ни казалось , поддержать #include , std::execution::par или что — нибудь подобное.

При взгляде на cppreference для параллельных алгоритмов существует длинный список алгоритмов, требующих

Техническая спецификация предоставляет распараллеленные версии следующих 69 алгоритмов с algorithm , numeric и memory : (. длинный список . )

похоже, что алгоритмы готовы «на бумаге» , но еще не готовы к использованию?

В этом вопросе SO более года назад ответы утверждают, что эти функции еще не были реализованы. Но теперь я ожидал увидеть какую-то реализацию. Есть ли что-нибудь, что мы можем использовать уже?

Ответы (3)

3 плюса

1228 Репутация автора

Однако libstdc ++ (с gcc) имеет экспериментальный режим для некоторых эквивалентных параллельных алгоритмов. См. Https://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html.

Приступая к работе:

Любое использование параллельной функциональности требует дополнительной поддержки компилятора и времени выполнения, в частности поддержки OpenMP. Добавление этой поддержки не сложно: просто скомпилируйте приложение с флагом-компилятором -fopenmp. Это будет ссылка на libgomp, библиотеку времени разгрузки GNU и многопользовательскую обработку, присутствие которой является обязательным.

Автор: KarlM Размещён: 25.06.2020 08:38

10 плюса

14136 Репутация автора

Intel выпустила параллельную библиотеку STL, которая следует за стандартом C ++ 17:

Опции компиляторов для улучшения производительности

Провел простой тест на сравнение производительности между Си и С++. Тест заключается в поиске позиции подстроки.
Си при решении данной задачи имеет значительный отрыв.

Тесты на gcc:
тест на C++: https://rextester.com/NFM46901 absolute running time: 0.24 sec, cpu time: 0.15 sec
тест на Си: https://rextester.com/BZRIQE2644 absolute running time: 0.14 sec, cpu time: 0 sec

Что то мне подсказывает, компилятор Си понимает что искать одно и тоже 10000000 раз не имеет смысла т.к результат будет одинаков а С++ прокручивает все итерации и делает одно и то же. Предполагаю, что нужно включить какую то опцию компилятора что бы хотя бы приблизительно сравнять результат выполнения.

25.11.2020, 13:04

Замечания/Улучшения для программы (Сборка сортировок)
Здравствуйте! имеется данный код: #define _CRT_SECURE_NO_WARNINGS #include #include.

Добавление компиляторов и отладчиков с++ для windows 8 x64
Здравствуйте господа программисты, у меня такой вопрос: Решил изучать с++ поставил себе IDE.

Нужны пояснения насчет компиляторов для разных ОС
Всем привет ребят! Есть несколько вопросов: 1) Существуют различные компиляторы (к примеру на.

Параллельные алгоритмы Parallel Algorithms

Библиотека параллельных шаблонов (PPL) предоставляет алгоритмы, выполняющие параллельную работу с коллекциями данных. The Parallel Patterns Library (PPL) provides algorithms that concurrently perform work on collections of data. Эти алгоритмы похожи на те, что C++ предоставляются стандартной библиотекой. These algorithms resemble those provided by the C++ Standard Library.

Параллельные алгоритмы состоят из существующих функциональных возможностей в среда выполнения с параллелизмом. The parallel algorithms are composed from existing functionality in the Concurrency Runtime. Например, алгоритм параллелизма::p arallel_for использует объект Concurrency:: structured_task_group для выполнения итераций параллельного цикла. For example, the concurrency::parallel_for algorithm uses a concurrency::structured_task_group object to perform the parallel loop iterations. parallel_for Алгоритмные секции работают оптимальным образом при наличии доступного количества вычислительных ресурсов. The parallel_for algorithm partitions work in an optimal way given the available number of computing resources.

Разделы Sections

Алгоритм parallel_for The parallel_for Algorithm

Алгоритм параллелизма::p arallel_for многократно выполняет одну и ту же задачу параллельно. The concurrency::parallel_for algorithm repeatedly performs the same task in parallel. Каждая из этих задач параметризована значением итерации. Each of these tasks is parameterized by an iteration value. Этот алгоритм полезен при наличии тела цикла, который не использует ресурсы совместно между итерациями этого цикла. This algorithm is useful when you have a loop body that does not share resources among iterations of that loop.

parallel_for Алгоритм разделяет задачи в оптимальном виде для параллельного выполнения. The parallel_for algorithm partitions tasks in an optimum way for parallel execution. В нем используется алгоритм переноса нагрузки и переноса диапазона для распределения этих секций в случае несбалансированной нагрузки. It uses a work-stealing algorithm and range stealing to balance these partitions when workloads are unbalanced. Когда одна итерация цикла выполняет совместную блокировку, среда выполнения повторно распространяет диапазон итераций, назначенный текущему потоку другим потокам или процессорам. When one loop iteration blocks cooperatively, the runtime redistributes the range of iterations that is assigned to the current thread to other threads or processors. Аналогично, когда поток завершает диапазон итераций, среда выполнения перераспределяет работу из других потоков в этот поток. Similarly, when a thread completes a range of iterations, the runtime redistributes work from other threads to that thread. Алгоритм также поддерживает вложенный параллелизм. parallel_for The parallel_for algorithm also supports nested parallelism. Если один параллельный цикл содержит другой параллельный цикл, среда выполнения координирует вычислительные ресурсы между частями цикла эффективным способом параллельного выполнения. When one parallel loop contains another parallel loop, the runtime coordinates processing resources between the loop bodies in an efficient way for parallel execution.

У алгоритма parallel_for существует несколько перегруженных версий. The parallel_for algorithm has several overloaded versions. Первая версия принимает начальное значение, конечное значение и рабочую функцию (лямбда-выражение, объект функции или указатель на функцию). The first version takes a start value, an end value, and a work function (a lambda expression, function object, or function pointer). Вторая версия принимает начальное значение, конечное значение, значение, по которому выполняется шаг, и рабочую функцию. The second version takes a start value, an end value, a value by which to step, and a work function. Первая версия этой функции использует значение 1 в качестве значения шага. The first version of this function uses 1 as the step value. Остальные версии принимают объекты-разделители, позволяющие указать, как алгоритм parallel_for должен разделять диапазоны между потоками. The remaining versions take partitioner objects, which enable you to specify how parallel_for should partition ranges among threads. Сведения о секционировании см. в разделе Работа с секционированием в этом документе. Partitioners are explained in greater detail in the section Partitioning Work in this document.

Многие for циклы можно преобразовать в использование parallel_for . You can convert many for loops to use parallel_for . Однако алгоритм отличается for от оператора следующим образом: parallel_for However, the parallel_for algorithm differs from the for statement in the following ways:

parallel_for Алгоритм parallel_for не выполняет задачи в предварительно определенном порядке. The parallel_for algorithm parallel_for does not execute the tasks in a pre-determined order.

parallel_for Алгоритм не поддерживает произвольные условия завершения. The parallel_for algorithm does not support arbitrary termination conditions. Алгоритм останавливается, когда текущее значение переменной итерации равно единице last меньше. parallel_for The parallel_for algorithm stops when the current value of the iteration variable is one less than last .

Параметр _Index_type типа должен быть целочисленным типом. The _Index_type type parameter must be an integral type. Этот целочисленный тип может быть подписан или без знака. This integral type can be signed or unsigned.

Итерация цикла должна быть прямой. The loop iteration must be forward. Алгоритм создает исключение типа std:: invalid_argument , _Step если параметр меньше 1. parallel_for The parallel_for algorithm throws an exception of type std::invalid_argument if the _Step parameter is less than 1.

Механизм обработки исключений для parallel_for алгоритма отличается от for механизма для цикла. The exception-handling mechanism for the parallel_for algorithm differs from that of a for loop. Если несколько исключений встречаются одновременно в теле параллельного цикла, среда выполнения распространяет только один из исключений в поток, вызвавший parallel_for . If multiple exceptions occur simultaneously in a parallel loop body, the runtime propagates only one of the exceptions to the thread that called parallel_for . Кроме того, когда одна итерация цикла создает исключение, среда выполнения не останавливает весь цикл немедленно. In addition, when one loop iteration throws an exception, the runtime does not immediately stop the overall loop. Вместо этого цикл помещается в отмененное состояние, и среда выполнения удаляет все задачи, которые еще не запущены. Instead, the loop is placed in the canceled state and the runtime discards any tasks that have not yet started. Дополнительные сведения об обработке исключений и параллельных алгоритмах см. в разделе обработка исключений. For more information about exception-handling and parallel algorithms, see Exception Handling.

parallel_for Хотя алгоритм не поддерживает произвольные условия завершения, можно использовать отмену для завершения всех задач. Although the parallel_for algorithm does not support arbitrary termination conditions, you can use cancellation to stop all tasks. Дополнительные сведения об отмене см. в разделе Отмена в библиотеке PPL. For more information about cancellation, see Cancellation in the PPL.

Затраты на планирование, полученные в результате балансировки нагрузки и поддержки таких функций, как отмена, могут не компенсировать преимущества параллельного выполнения тела цикла, особенно если тело цикла относительно мало. The scheduling cost that results from load balancing and support for features such as cancellation might not overcome the benefits of executing the loop body in parallel, especially when the loop body is relatively small. Эту дополнительную нагрузку можно минимизировать, используя разделитель в параллельном цикле. You can minimize this overhead by using a partitioner in your parallel loop. Дополнительные сведения см. в разделе секционирование работы далее в этом документе. For more information, see Partitioning Work later in this document.

Пример Example

В следующем примере показана базовая структура parallel_for алгоритма. The following example shows the basic structure of the parallel_for algorithm. В этом примере на консоль выводятся все значения в диапазоне [1, 5] параллельно. This example prints to the console each value in the range [1, 5] in parallel.

В этом примере выводится следующий пример выходных данных: This example produces the following sample output:

Так как parallel_for алгоритм действует для каждого элемента параллельно, порядок, в котором значения выводятся на консоль, будет отличаться. Because the parallel_for algorithm acts on each item in parallel, the order in which the values are printed to the console will vary.

Полный пример использования parallel_for алгоритма см. в разделе как Напишите циклparallel_for. For a complete example that uses the parallel_for algorithm, see How to: Write a parallel_for Loop.

Алгоритм parallel_for_each The parallel_for_each Algorithm

Алгоритм параллелизма::p arallel_for_each выполняет задачи в итеративном контейнере, например, предоставляемые C++ стандартной библиотекой, параллельно. The concurrency::parallel_for_each algorithm performs tasks on an iterative container, such as those provided by the C++ Standard Library, in parallel. Он использует ту же логику секционирования, parallel_for которую использует алгоритм. It uses the same partitioning logic that the parallel_for algorithm uses.

Алгоритм напоминает алгоритм C++ стандартной библиотеки std:: for_each , за исключением того, что parallel_for_each алгоритм выполняет задачи параллельно. parallel_for_each The parallel_for_each algorithm resembles the C++ Standard Library std::for_each algorithm, except that the parallel_for_each algorithm executes the tasks concurrently. Как и другие параллельные parallel_for_each алгоритмы, не выполняет задачи в определенном порядке. Like other parallel algorithms, parallel_for_each does not execute the tasks in a specific order.

Несмотря на parallel_for_each то, что алгоритм работает как с прямыми итераторами, так и с итераторами произвольного доступа, он обеспечивает лучшую производительность с итераторами произвольного доступа. Although the parallel_for_each algorithm works on both forward iterators and random access iterators, it performs better with random access iterators.

Пример Example

В следующем примере показана базовая структура parallel_for_each алгоритма. The following example shows the basic structure of the parallel_for_each algorithm. В этом примере каждое значение в объекте std:: Array выводится на консоль параллельно. This example prints to the console each value in a std::array object in parallel.

В этом примере выводится следующий пример выходных данных: This example produces the following sample output:

Так как parallel_for_each алгоритм действует для каждого элемента параллельно, порядок, в котором значения выводятся на консоль, будет отличаться. Because the parallel_for_each algorithm acts on each item in parallel, the order in which the values are printed to the console will vary.

Полный пример использования parallel_for_each алгоритма см. в разделе как Напишите циклparallel_for_each. For a complete example that uses the parallel_for_each algorithm, see How to: Write a parallel_for_each Loop.

Алгоритм parallel_invoke The parallel_invoke Algorithm

Алгоритм параллелизма::p arallel_invoke параллельно выполняет набор задач. The concurrency::parallel_invoke algorithm executes a set of tasks in parallel. Она не возвращает результат, пока не завершится каждая задача. It does not return until each task finishes. Этот алгоритм полезен при наличии нескольких независимых задач, которые необходимо выполнить одновременно. This algorithm is useful when you have several independent tasks that you want to execute at the same time.

parallel_invoke Алгоритм принимает в качестве параметров ряд рабочих функций (лямбда-функции, объекты функций или указатели функций). The parallel_invoke algorithm takes as its parameters a series of work functions (lambda functions, function objects, or function pointers). parallel_invoke Алгоритм перегружается для выполнения двух и десяти параметров. The parallel_invoke algorithm is overloaded to take between two and ten parameters. Каждая функция, передаваемая в parallel_invoke , должна принимать нулевые параметры. Every function that you pass to parallel_invoke must take zero parameters.

Как и другие параллельные parallel_invoke алгоритмы, не выполняет задачи в определенном порядке. Like other parallel algorithms, parallel_invoke does not execute the tasks in a specific order. В разделе параллелизм задач объясняется, parallel_invoke как алгоритм относится к задачам и группам задач. The topic Task Parallelism explains how the parallel_invoke algorithm relates to tasks and task groups.

Пример Example

В следующем примере показана базовая структура parallel_invoke алгоритма. The following example shows the basic structure of the parallel_invoke algorithm. Этот пример параллельно вызывает twice функцию для трех локальных переменных и выводит результат на консоль. This example concurrently calls the twice function on three local variables and prints the result to the console.

В этом примере выводятся следующие данные: This example produces the following output:

Алгоритмы parallel_transform и parallel_reduce The parallel_transform and parallel_reduce Algorithms

Алгоритмы Concurrency::p arallel_transform и Concurrency::p arallel_reduce — это параллельные версии C++ стандартных алгоритмов библиотеки std:: Transform и std:: accumulateсоответственно. The concurrency::parallel_transform and concurrency::parallel_reduce algorithms are parallel versions of the C++ Standard Library algorithms std::transform and std::accumulate, respectively. Среда выполнения с параллелизмом версии ведут себя как версии C++ стандартной библиотеки, за исключением того, что порядок операций не определяется, так как они выполняются параллельно. The Concurrency Runtime versions behave like the C++ Standard Library versions except that the operation order is not determined because they execute in parallel. Используйте эти алгоритмы при работе с набором, который достаточно велик для получения выигрыша в производительности и масштабируемости при параллельной обработке. Use these algorithms when you work with a set that is large enough to get performance and scalability benefits from being processed in parallel.

Алгоритмы parallel_transform и parallel_reduce поддерживают только итераторы произвольного доступа, двунаправленные и прямые итераторы, поскольку эти итераторы создают стабильные адреса памяти. The parallel_transform and parallel_reduce algorithms support only random access, bi-directional, and forward iterators because these iterators produce stable memory addresses. Кроме того, эти итераторы должны создавать l-значения, отличные от const . Also, these iterators must produce non- const l-values.

Алгоритм parallel_transform The parallel_transform Algorithm

Алгоритм parallel transform можно использовать для выполнения множества операций параллелизации данных. You can use the parallel transform algorithm to perform many data parallelization operations. Например, с их помощью можно выполнять следующее. For example, you can:

Настройка яркости изображения и другие операции обработки изображений. Adjust the brightness of an image, and perform other image processing operations.

Суммирование или получение скалярного произведения двух векторов и выполнение других векторных вычислений. Sum or take the dot product between two vectors, and perform other numeric calculations on vectors.

Трассировка трехмерных лучей, при которой каждая итерация относится к одному пикселю, подлежащему отображению. Perform 3-D ray tracing, where each iteration refers to one pixel that must be rendered.

В следующем примере показана базовая структура, используемая для вызова алгоритма parallel_transform . The following example shows the basic structure that is used to call the parallel_transform algorithm. В этом примере каждый элемент объекта std::vector инвертируется двумя способами. This example negates each element of a std::vector object in two ways. В первом способе используется лямбда-выражение. The first way uses a lambda expression. Второй способ использует std:: отрицание, который является производным от std:: unary_function. The second way uses std::negate, which derives from std::unary_function.

В этом примере показано базовое использование функции parallel_transform . This example demonstrates the basic use of parallel_transform . Поскольку рабочая функция выполняет незначительный объем работы, существенного прироста производительности в данном примере не ожидается. Because the work function does not perform a significant amount of work, a significant increase in performance is not expected in this example.

Алгоритм parallel_transform имеет две перегрузки. The parallel_transform algorithm has two overloads. Первая перегрузка принимает один входной диапазон и унарную функцию. The first overload takes one input range and a unary function. Унарная функция может быть лямбда-выражением, принимающим один аргумент, объект функции или тип, производный от unary_function . The unary function can be a lambda expression that takes one argument, a function object, or a type that derives from unary_function . Вторая перегрузка принимает два входных диапазона и бинарную функцию. The second overload takes two input ranges and a binary function. Двоичная функция может быть лямбда-выражением, которое принимает два аргумента, объект функции или тип, производный от std:: binary_function. The binary function can be a lambda expression that takes two arguments, a function object, or a type that derives from std::binary_function. В следующем примере показаны эти различия. The following example illustrates these differences.

Мастер Йода рекомендует:  Базовые директивы директивы SSI

Итератор, предоставляемый для выходных данных алгоритма parallel_transform , должен полностью перекрывать итератор входных данных или не перекрывать его вообще. The iterator that you supply for the output of parallel_transform must completely overlap the input iterator or not overlap at all. Если итераторы входных и выходных данных перекрываются частично, поведение этого алгоритма будет неопределенным. The behavior of this algorithm is unspecified if the input and output iterators partially overlap.

Алгоритм parallel_reduce The parallel_reduce Algorithm

Алгоритм parallel_reduce эффективен при наличии последовательности операций, обладающих свойством ассоциативности. The parallel_reduce algorithm is useful when you have a sequence of operations that satisfy the associative property. (Он не требует коммутативности). Ниже указано несколько операций, которые можно выполнять с помощью алгоритма parallel_reduce : (This algorithm does not require the commutative property.) Here are some of the operations that you can perform with parallel_reduce :

умножение последовательности матриц для получения матрицы; Multiply sequences of matrices to produce a matrix.

умножение вектора на последовательность матриц для получения вектора; Multiply a vector by a sequence of matrices to produce a vector.

вычисление длины последовательности строк; Compute the length of a sequence of strings.

объединение списка элементов, например строк, в один элемент. Combine a list of elements, such as strings, into one element.


В следующем базовом примере показано использование алгоритма parallel_reduce для объединения последовательности строк в одну строку. The following basic example shows how to use the parallel_reduce algorithm to combine a sequence of strings into one string. Как и в примерах для parallel_transform , в этом базовом примере не ожидается повышения производительности. As with the examples for parallel_transform , performance gains are not expected in this basic example.

Во многих случаях можно представить себе parallel_reduce сокращение использования parallel_for_each алгоритма вместе с классом Concurrency:: combinable . In many cases, you can think of parallel_reduce as shorthand for the use of the parallel_for_each algorithm together with the concurrency::combinable class.

Например Параллельное выполнение Map и reduce Example: Performing Map and Reduce in Parallel

Операция Map применяет функцию к каждому значению в последовательности. A map operation applies a function to each value in a sequence. Операция сокращения объединяет элементы последовательности в одно значение. A reduce operation combines the elements of a sequence into one value. Для выполнения операций Map C++ и reduce можно использовать стандартные библиотеки std:: Transform и std:: accumulate . You can use the C++ Standard Library std::transform and std::accumulate functions to perform map and reduce operations. Однако для многих задач можно использовать алгоритм parallel_transform для параллельного выполнения операции сопоставления и алгоритм parallel_reduce для параллельного выполнения операции редукции. However, for many problems, you can use the parallel_transform algorithm to perform the map operation in parallel and the parallel_reduce algorithm perform the reduce operation in parallel.

В следующем примере сравнивается время, необходимое для последовательного и параллельного вычисления суммы простых чисел. The following example compares the time that it takes to compute the sum of prime numbers serially and in parallel. На этапе сопоставления составные числа преобразуются в 0, а на этапе редукции производится суммирование значений. The map phase transforms non-prime values to 0 and the reduce phase sums the values.

Еще один пример, в котором параллельно выполняется операция Map и reduce, см. в разделе как Параллельноевыполнение операций Map и reduce. For another example that performs a map and reduce operation in parallel, see How to: Perform Map and Reduce Operations in Parallel.

Работа по секционированию Partitioning Work

Для параллелизации операции в источнике данных необходимо секционировать источник на несколько разделов, к которым можно получить доступ одновременно из нескольких потоков. To parallelize an operation on a data source, an essential step is to partition the source into multiple sections that can be accessed concurrently by multiple threads. Разделитель определяет, как параллельный алгоритм должен разделять диапазоны между потоками. A partitioner specifies how a parallel algorithm should partition ranges among threads. Как описано ранее в этом документе, PPL использует механизм секционирования по умолчанию, создающий начальную рабочую нагрузку, а затем применяет алгоритм переноса нагрузки и переноса диапазона для распределения нагрузки этих разделов при ее несбалансированности. As explained previously in this document, the PPL uses a default partitioning mechanism that creates an initial workload and then uses a work-stealing algorithm and range stealing to balance these partitions when workloads are unbalanced. Например, когда одна итерация цикла завершает ряд итераций, среда выполнения перераспределяет в этот поток нагрузку с других потоков. For example, when one loop iteration completes a range of iterations, the runtime redistributes work from other threads to that thread. Однако в некоторых сценариях может потребоваться указать другой механизм секционирования, который лучше подходит для конкретной задачи. However, for some scenarios, you might want to specify a different partitioning mechanism that is better suited to your problem.

Алгоритмы parallel_for , parallel_for_each и parallel_transform предоставляют перегруженные версии, принимающие дополнительный параметр _Partitioner . The parallel_for , parallel_for_each , and parallel_transform algorithms provide overloaded versions that take an additional parameter, _Partitioner . Этот параметр определяет тип разделителя, разделяющий работу. This parameter defines the partitioner type that divides work. Ниже указаны типы разделителей, которые определяет PPL. Here are the kinds of partitioners that the PPL defines:

concurrency::affinity_partitioner concurrency::affinity_partitioner
Разделяет нагрузку на фиксированное число диапазонов (обычно число рабочих потоков, доступных для работы в цикле). Divides work into a fixed number of ranges (typically the number of worker threads that are available to work on the loop). Этот тип разделителя напоминает static_partitioner , но повышает степень сходства кэша путем сопоставления диапазонов рабочим потокам. This partitioner type resembles static_partitioner , but improves cache affinity by the way it maps ranges to worker threads. Такой тип разделителя может повысить производительность, если цикл выполняется над одним и тем же набором данных несколько раз (например, цикл в цикле) и данные размещаются в кэше. This partitioner type can improve performance when a loop is executed over the same data set multiple times (such as a loop within a loop) and the data fits in cache. Этот разделитель не полностью участвует в отмене. This partitioner does not fully participate in cancellation. Он также не использует согласованную семантику блокировки и поэтому не может использоваться с параллельными циклами, имеющими прямую зависимость. It also does not use cooperative blocking semantics and therefore cannot be used with parallel loops that have a forward dependency.

Concurrency:: auto_partitioner concurrency::auto_partitioner
Разделяет нагрузку на начальное число диапазонов (обычно число рабочих потоков, доступных для работы в цикле). Divides work into an initial number of ranges (typically the number of worker threads that are available to work on the loop). Среда выполнения использует этот тип по умолчанию, если не вызывается перегруженный параллельный алгоритм, принимающий параметр _Partitioner . The runtime uses this type by default when you do not call an overloaded parallel algorithm that takes a _Partitioner parameter. Каждый диапазон можно разделить на поддиапазоны, что обеспечивает распределение нагрузки. Each range can be divided into sub-ranges, and thereby enables load balancing to occur. Когда диапазон работы завершается, среда выполнения перераспределяет поддиапазоны работы с других потоков в этот поток. When a range of work completes, the runtime redistributes sub-ranges of work from other threads to that thread. Используйте этот разделитель, если рабочая нагрузка не попадает в другие категории или требуется полная поддержка отмены или совместной блокировки. Use this partitioner if your workload does not fall under one of the other categories or you require full support for cancellation or cooperative blocking.

Concurrency:: simple_partitioner concurrency::simple_partitioner
Разделяет нагрузку на диапазоны так, чтобы каждый диапазон содержал по крайней мере такое число итераций, которое определено заданным размером блока. Divides work into ranges such that each range has at least the number of iterations that are specified by the given chunk size. Этот тип разделителя участвует в распределении нагрузки; однако среда выполнения не делит диапазоны на поддиапазоны. This partitioner type participates in load balancing; however, the runtime does not divide ranges into sub-ranges. Для каждого рабочего потока среда выполнения проверяет запрос отмены и выполняет распределение нагрузки после завершения числа итераций, определенных параметром _Chunk_size . For each worker, the runtime checks for cancellation and performs load-balancing after _Chunk_size iterations complete.

Concurrency:: static_partitioner concurrency::static_partitioner
Разделяет нагрузку на фиксированное число диапазонов (обычно число рабочих потоков, доступных для работы в цикле). Divides work into a fixed number of ranges (typically the number of worker threads that are available to work on the loop). Этот разделитель может повысить производительность, поскольку не использует перенос нагрузки и, следовательно, содержит меньше побочной нагрузки. This partitioner type can improve performance because it does not use work-stealing and therefore has less overhead. Используйте его, если при каждой итерации параллельного цикла выполняется фиксированный и одинаковый объем работы и нет необходимости поддержки отмены или прямой совместной блокировки. Use this partitioner type when each iteration of a parallel loop performs a fixed and uniform amount of work and you do not require support for cancellation or forward cooperative blocking.

Алгоритмы parallel_for_each и parallel_transform поддерживают только те контейнеры, которые используют итераторы произвольного доступа (например, std::vector) для статических, простых и территориальных секционирований. The parallel_for_each and parallel_transform algorithms support only containers that use random access iterators (such as std::vector) for the static, simple, and affinity partitioners. Применение контейнеров, использующих двунаправленные и прямые итераторы, приводит к ошибке во время компиляции. The use of containers that use bidirectional and forward iterators produces a compile-time error. Разделитель по умолчанию auto_partitioner поддерживает все три типа итераторов. The default partitioner, auto_partitioner , supports all three of these iterator types.

Обычно эти разделители используются одинаково, за исключением affinity_partitioner . Typically, these partitioners are used in the same way, except for affinity_partitioner . Большинство типов разделителей не поддерживают состояние и не изменяются средой выполнения. Most partitioner types do not maintain state and are not modified by the runtime. Поэтому эти объекты-разделители можно создавать в месте вызова, как показано в следующем примере. Therefore you can create these partitioner objects at the call site, as shown in the following example.

Однако необходимо передать объект affinity_partitioner как ссылку на I-значение, отличное от const , чтобы алгоритм мог сохранять состояние для повторного использования в последующих циклах. However, you must pass an affinity_partitioner object as a non- const , l-value reference so that the algorithm can store state for future loops to reuse. В следующем примере демонстрируется базовое приложение, параллельно выполняющее одну и ту же операцию над набором данных несколько раз. The following example shows a basic application that performs the same operation on a data set in parallel multiple times. Использование affinity_partitioner позволяет повысить производительность, поскольку массив может размещаться в кэше. The use of affinity_partitioner can improve performance because the array is likely to fit in cache.

При изменении существующего кода, зависящего от семантики совместной блокировки при применении разделителей static_partitioner или affinity_partitioner , используйте с осторожностью. Use caution when you modify existing code that relies on cooperative blocking semantics to use static_partitioner or affinity_partitioner . Эти разделители не используют распределение нагрузки и перенос диапазона и поэтому могут изменить поведение приложения. These partitioner types do not use load balancing or range stealing, and therefore can alter the behavior of your application.

Лучший способ определения необходимости использования разделителя в любом заданном сценарии — проведение экспериментов и измерение длительности выполнения операций при типичных нагрузках и конфигурациях компьютера. The best way to determine whether to use a partitioner in any given scenario is to experiment and measure how long it takes operations to complete under representative loads and computer configurations. Например статическое секционирование может значительно ускорить работу на компьютере с небольшим количеством ядер, но привести к замедлению работы на компьютерах с относительно большим количеством ядер. For example, static partitioning might provide significant speedup on a multi-core computer that has only a few cores, but it might result in slowdowns on computers that have relatively many cores.

Параллельная сортировка Parallel Sorting

PPL предоставляет три алгоритма сортировки: Concurrency::p arallel_sort, Concurrency::p arallel_buffered_sortи Concurrency::p arallel_radixsort. The PPL provides three sorting algorithms: concurrency::parallel_sort, concurrency::parallel_buffered_sort, and concurrency::parallel_radixsort. Они эффективны при наличии набора данных, который выгоднее сортировать параллельно. These sorting algorithms are useful when you have a data set that can benefit from being sorted in parallel. В частности, параллельная сортировка эффективна при наличии большого набора данных и использовании операций сравнения, потребляющих много вычислительных ресурсов. In particular, sorting in parallel is useful when you have a large dataset or when you use a computationally-expensive compare operation to sort your data. Каждый из этих алгоритмов сортирует элементы на месте. Each of these algorithms sorts elements in place.

Алгоритмы parallel_sort и parallel_buffered_sort основаны на сравнениях. The parallel_sort and parallel_buffered_sort algorithms are both compare-based algorithms. То есть они сравнивают элементы по значению. That is, they compare elements by value. Алгоритм parallel_sort не требует дополнительной памяти и подходит для сортировки в общем случае. The parallel_sort algorithm has no additional memory requirements, and is suitable for general-purpose sorting. Алгоритм может выполняться лучше, чем parallel_sort , но он требует O (N) пространства. parallel_buffered_sort The parallel_buffered_sort algorithm can perform better than parallel_sort , but it requires O(N) space.

Алгоритм parallel_radixsort основан на хэше. The parallel_radixsort algorithm is hash-based. То есть для сортировки элементов он использует целочисленные ключи. That is, it uses integer keys to sort elements. С помощью ключей этот алгоритм может определить место элемента непосредственно, а не использовать операции сравнения. By using keys, this algorithm can directly compute the destination of an element instead of using comparisons. Например parallel_buffered_sort , для этого алгоритма требуется диск O (N). Like parallel_buffered_sort , this algorithm requires O(N) space.

В следующей таблице перечислены важные свойства трех параллельных алгоритмов сортировки. The following table summarizes the important properties of the three parallel sorting algorithms.

Алгоритм Algorithm Описание Description Механизм сортировки Sorting mechanism Стабильность сортировки Sort Stability Требования к памяти Memory requirements Временная сложность Time Complexity Доступ итераторов Iterator access
parallel_sort Основанная на сравнениях сортировка общего назначения. General-purpose compare-based sort. На основе сравнений (по возрастанию) Compare-based (ascending) Нестабильная Unstable Отсутствуют None O ((N/P)-журнал (N/P) + 2N ((P-1)/P)) O((N/P)log(N/P) + 2N((P-1)/P)) Случайный Random
parallel_buffered_sort Более быстрая сортировка общего назначения на основе сравнений, для которой требуется память O(N). Faster general-purpose compare-based sort that requires O(N) space. На основе сравнений (по возрастанию) Compare-based (ascending) Нестабильная Unstable Требуется дополнительное пространство O (N) Requires additional O(N) space O ((N/P) журнал (N)) O((N/P)log(N)) Случайный Random
parallel_radixsort Сортировка на основе целочисленных ключей, для которой требуется память О(N). Integer key-based sort that requires O(N) space. На основе хэша Hash-based стабильных Stable Требуется дополнительное пространство O (N) Requires additional O(N) space O (N/P) O(N/P) Случайный Random

На следующем рисунке графически показаны важные свойства трех параллельных алгоритмов сортировки. The following illustration shows the important properties of the three parallel sorting algorithms more graphically.

Эти параллельные алгоритмы сортировки подчиняются правилам отмены и обработки исключений. These parallel sorting algorithms follow the rules of cancellation and exception handling. Дополнительные сведения об отмене и обработке исключений в среда выполнения с параллелизмом см. в разделе Отмена параллельных алгоритмов и обработка исключений. For more information about cancellation and exception handling in the Concurrency Runtime, see Canceling Parallel Algorithms and Exception Handling.

Эти параллельные алгоритмы сортировки поддерживают семантику перемещений. These parallel sorting algorithms support move semantics. Для более эффективного выполнения операций замены можно определить оператор присваивания перемещения. You can define a move assignment operator to enable swap operations to occur more efficiently. Дополнительные сведения о семантике перемещения и операторе назначения перемещения см. в разделе декларатор ссылок rvalue: & &, конструкторы перемещения и операторы присваивания перемещенияC++(). For more information about move semantics and the move assignment operator, see Rvalue Reference Declarator: &&, and Move Constructors and Move Assignment Operators (C++). Если оператор присваивания перемещения или функция замены не предоставляется, алгоритмы сортировки используют конструктор копии. If you do not provide a move assignment operator or swap function, the sorting algorithms use the copy constructor.

В следующем базовом примере показано использование алгоритма parallel_sort для сортировки вектора vector значений типа int . The following basic example shows how to use parallel_sort to sort a vector of int values. По умолчанию parallel_sort использует std:: less для сравнения значений. By default, parallel_sort uses std::less to compare values.

В следующем примере показано, как реализовать пользовательскую функцию сравнения. This example shows how to provide a custom compare function. В нем используется метод std:: Complex:: Real для сортировки значений std:: в возрастающем порядке. It uses the std::complex::real method to sort std::complex values in ascending order.

В следующем примере показано, как реализовать хэш-функцию для алгоритма parallel_radixsort . This example shows how to provide a hash function to the parallel_radixsort algorithm. В этом примере сортируются трехмерные точки. This example sorts 3-D points. Они сортируются по расстоянию от опорной точки. The points are sorted based on their distance from a reference point.

Для иллюстрации в этом примере используется относительно небольшой набор данных. For illustration, this example uses a relatively small data set. Первоначальный размер вектора можно увеличить, чтобы поэкспериментировать с увеличением производительности при больших наборах данных. You can increase the initial size of the vector to experiment with performance improvements over larger sets of data.

В этом примере лямбда-выражение используется в качестве хэш-функции. This example uses a lambda expression as the hash function. Можно также использовать одну из встроенных реализаций класса std::hash или определить собственную специализацию. You can also use one of the built-in implementations of the std::hash class or define your own specialization. Кроме того, можно использовать пользовательский объект хэш-функции, как показано в следующем примере: You can also use a custom hash function object, as shown in this example:

Хэш-функция должна возвращать целочисленный тип (std:: is_integral:: value должен иметь значение true). The hash function must return an integral type (std::is_integral::value must be true). Этот целочисленный тип должен быть преобразуем в тип size_t . This integral type must be convertible to type size_t .

Выбор алгоритма сортировки Choosing a Sorting Algorithm

Во многих случаях алгоритм parallel_sort обеспечивает оптимальный баланс производительности памяти и быстродействия. In many cases, parallel_sort provides the best balance of speed and memory performance. Однако с увеличением размера набора данных, количества доступных процессоров и сложности функции сравнения алгоритм parallel_buffered_sort или parallel_radixsort может работать эффективнее. However, as you increase the size of your data set, the number of available processors, or the complexity of your compare function, parallel_buffered_sort or parallel_radixsort can perform better. Лучший способ определения наиболее подходящего алгоритма сортировки в любом заданном сценарии — проведение экспериментов и измерение длительности выполнения сортировки типовых данных при типичных конфигурациях компьютера. The best way to determine which sorting algorithm to use in any given scenario is to experiment and measure how long it takes to sort typical data under representative computer configurations. Ниже приведены рекомендации по выбору стратегии сортировки. Keep the following guidelines in mind when you choose a sorting strategy.

Размер набора данных. The size of your data set. В этом документе небольшой набор данных содержит менее 1 000 элементов, средний набор данных содержит от 10 000 до 100 000 элементов, а большой набор данных содержит более 100 000 элементов. In this document, a small dataset contains fewer than 1,000 elements, a medium dataset contains between 10,000 and 100,000 elements, and a large dataset contains more than 100,000 elements.

Объем работы, выполняемой функцией сравнения или хэш-функцией. The amount of work that your compare function or hash function performs.

Количество доступных вычислительных ресурсов. The amount of available computing resources.

Характеристики набора данных. The characteristics of your data set. Например, один алгоритм может хорошо работать при частично отсортированных данных, но не так хорошо, когда данные совсем не сортированы. For example, one algorithm might perform well for data that is already nearly sorted, but not as well for data that is completely unsorted.

Размер блока. The chunk size. Необязательный аргумент _Chunk_size определяет, когда алгоритм переходит от параллельной к последовательной реализации сортировки по мере разделения всей задачи сортировки на меньшие единицы работы. The optional _Chunk_size argument specifies when the algorithm switches from a parallel to a serial sort implementation as it subdivides the overall sort into smaller units of work. Например, если указать 512, то алгоритм будет переходить на последовательную реализацию, когда единица работы содержит 512 или менее элементов. For example, if you provide 512, the algorithm switches to serial implementation when a unit of work contains 512 or fewer elements. При последовательной реализации может повыситься общая производительность, поскольку исключается лишняя работа, необходимая для параллельной обработки данных. A serial implementation can improve overall performance because it eliminates the overhead that is required to process data in parallel.

Использовать параллельную сортировку небольшого набора данных может оказаться невыгодно даже при наличии большого количества вычислительных ресурсов или выполнении функцией сравнения или хэш-функцией относительно большого объема работы. It might not be worthwhile to sort a small dataset in parallel, even when you have a large number of available computing resources or your compare function or hash function performs a relatively large amount of work. Для сортировки небольших наборов данных можно использовать функцию std:: Sort . You can use std::sort function to sort small datasets. ( parallel_sort и parallel_buffered_sort вызываются sort при указании размера фрагмента, который больше, чем набор данных, parallel_buffered_sort однако ему пришлось бы выделить O (N) пространство, которое может занять дополнительное время из-за конфликта блокировки или выделения памяти.) ( parallel_sort and parallel_buffered_sort call sort when you specify a chunk size that is larger than the dataset; however, parallel_buffered_sort would have to allocate O(N) space, which could take additional time due to lock contention or memory allocation.)

Если необходимо сэкономить ресурсы памяти или распределитель памяти подвержен конфликтам при блокировках, то для сортировки набора данных среднего размера следует использовать алгоритм parallel_sort . If you must conserve memory or your memory allocator is subject to lock contention, use parallel_sort to sort a medium-sized dataset. parallel_sort не требует дополнительного пространства; другие алгоритмы нуждаются в пространстве O (N). parallel_sort requires no additional space; the other algorithms require O(N) space.

Используйте parallel_buffered_sort для сортировки наборов данных среднего размера и, если приложение соответствует требованиям к дополнительному свободному пространству (N). Use parallel_buffered_sort to sort medium-sized datasets and when your application meets the additional O(N) space requirement. Алгоритм parallel_buffered_sort особенно эффективен при большом количестве вычислительных ресурсов и ресурсоемкой функции сравнения или хэш-функции. parallel_buffered_sort can be especially useful when you have a large number of computing resources or an expensive compare function or hash function.

Используйте parallel_radixsort для сортировки больших наборов данных и, если приложение соответствует требованиям к дополнительному свободному пространству (N). Use parallel_radixsort to sort large datasets and when your application meets the additional O(N) space requirement. Алгоритм parallel_radixsort особенно эффективен при ресурсоемкой функции сравнения, а также в случае, если и функция сравнения, и хэш-функция ресурсоемки. parallel_radixsort can be especially useful when the equivalent compare operation is more expensive or when both operations are expensive.

Для реализации хорошей хэш-функции требуется знание диапазона наборов данных и способа преобразования каждого элемента набора данных в соответствующее беззнаковое значение. Implementing a good hash function requires that you know the dataset range and how each element in the dataset is transformed to a corresponding unsigned value. Поскольку хэш-операции работают с беззнаковыми значениями, при невозможности получить беззнаковые хэш-значения рассмотрите другую стратегию сортировки. Because the hash operation works on unsigned values, consider a different sorting strategy if unsigned hash values cannot be produced.

В следующем примере сравнивается производительность алгоритмов sort , parallel_sort , parallel_buffered_sort и parallel_radixsort при одном и том же большом наборе случайных данных. The following example compares the performance of sort , parallel_sort , parallel_buffered_sort , and parallel_radixsort against the same large set of random data.

В этом примере, в котором предполагается, что при сортировке допустимо выделить диск (N) пространства, parallel_radixsort выполняет лучшие в этом наборе данных конфигурацию этого компьютера. In this example, which assumes that it is acceptable to allocate O(N) space during the sort, parallel_radixsort performs the best on this dataset on this computer configuration.

Глава 7. Параллельные алгоритмы

7.1 Основные понятия параллельных алгоритмов.

Объединение нескольких вычислительных систем в общую систему распределенной обработки данных позволяет реализовать эффективные алгоритмы решения трудных задач (с экспоненциальной, факториальной сложностью). При этом возникают две проблемы:

1) управление и планирование вычислений по нескольким задачам для мультипроцессорных систем с различной архитектурой

2) построение быстрого алгоритма решения одной задачи на мультипроцессорной ЭВМ, что подразумевает распараллеливание исходного последовательного алгоритма её решения.

Если задачу нельзя решить с помощью последовательного алгоритма, разработанного одним из эффективных методов, то прибегают к распараллеливанию алгоритма с целью увеличения его быстродействия.

Распараллеливание (десеквенция) – преобразование последовательного алгоритма в эквивалентный ему параллельный алгоритм, соответствующий архитектуре какой-либо мультипроцессорной ЭВМ.

Примеры задач, в которых используется распараллеливание:

1) Одновременное выполнение операций ввода/вывода.

2) Формирование и обнуление массива.

3) Арифметические и логические операции над векторами и матрицами.

4) Одновременное отслеживание ветвей в различных узлах дерева.

5) Конвейерная обработка.

6) Решение СЛАУ большого порядка.

7) Параллельная сортировка.

8) Поиск максимума/минимума функции.

Наиболее желательными (даже скорее обязательными) признаками параллельных алгоритмов и программ являются:

    параллелизм, маштабируемость, локальность, модульность.

Параллелизм указывает на способность выполнения множества действий одновременно, что существенно для программ выполняющихся на нескольких процессорах.

Маштабируемость — другой важнейший признак параллельной программы, который требует гибкости программы по отношению к изменению числа процессоров, поскольку наиболее вероятно, что их число будет постоянно увеличиваться в большинстве параллельных сред и систем.

Локальность характеризует необходимость того, чтобы доступ к локальным данным был более частым, чем доступ к удаленным данным. Важность этого свойства определяется отношением стоимостей удаленного и локального обращений к памяти. Оно является ключом к повышению эффективности программ на архитектурах с распределенной памятью.

Модульность отражает степепь разложения сложных объектов на более простые компоненты. В параллельных вычислениях это такой же важный аспект разработки программ, как и в последовательных вычислениях.

Процессы и нити. Будем понимать под процессом последовательность действий, составляющих некоторое вычисление, которая характеризуется:

    сопоставленной ему программой/подпрограммой, то есть упорядоченной последовательностью операций, реализующих действия, которые должны осуществляться процессом; содержимым соответствующей ему памяти, то есть множеством данных, которыми этот процесс может манипулировать; дескриптором процесса, то есть совокупностью сведений, определяющих состояние ресурсов, предоставленных процессу.

Имеется так же большое число уточнений вида процесса, режима и условий работы процесса: последовательный процесс, параллельный процесс, пакетный процесс, интерактивный процесс, независимый процесс, взаимодействующий процесс и т. д.

Будем различать, где это необходимо, полновесные и легковесные процессы.

Полновесные процессы (tasksзадачи) — это процессы, выполняющиеся внутри защищенных участков памяти операционной системы, то есть имеющие собственные виртуальные адресные пространства для статических и динамических данных. В мультипрограммной среде управление такими процессами тесно связанно с управлением и защитой памяти, поэтому переключение процессора с выполнения одного процесса на выполнение другого является дорогой операцией.

Легковесные процессы (threads — нити), называемые еще сопроцессами, не имеют собственных защищенных областей памяти. Они работают в мультипрограммном режиме одновременно с активировавшей их задачей и используют ее виртуальное адресное пространство, в котором им при создании выделяется участок памяти под динамические данные (стек), то есть они могут обладать собственными локальными данными. Сопроцесс описывается как обычная функция, которая может использовать статические данные программы.

Каналы. Понятие канала используется для описания событий, называемых взаимодействиями, которые состоят в передаче сообщений между процессами. Каналы используются для передачи сообщений в одном направлении и только между двумя процессами. Канал, используемый процессом только для вывода сообщений, называется выходным каналом этого процесса, а используемый только для ввода — входным каналом.

Итак, канал — это однонаправленная двухточечная (соединяющая только два процесса) «коммуникационная линия», позволяющая процессам обмениваться данными. Операции обмена сообщениями достаточно продолжительные по времени операции, поэтому в разных моделях, системах используются разные типы поведения операций приема/передачи сообщений. Различают следующие виды каналов:

При работе с каналами необходимо следить за тем, чтобы не случилась блокировка взаимодействующих процессов (дедлок). Например, процесс A не может передать сообщение процессу B, поскольку процесс B ждет, когда процесс A примет сообщение от него. Это одна из простейших ситуаций, в более сложных случаях циклические зависимости могут охватывать много процессов, причем появление дедлока может завесить от данных.

Семафоры — средство управления процессами. Семафоры традиционно использовались для синхронизации процессов, обращающихся к разделяемым данным. Каждый процесс должен исключать для всех других процессов возможность одновременно с ним обращаться к этим данным (взаимоисключение). Когда процесс обращается к разделяемым данным, говорят, что он находится в своем критическом участке.


Для решения задачи синхронизации необходимо, в случае если один процесс находится в критическом участке, исключить возможность вхождения для других процессов в их критические участки. Хотя бы для тех, которые обращаются к тем же самым разделяемым данным. Когда процесс выходит из своего критического участка, то одному из остальных процессов, ожидающих входа в свои критические участки, должно быть разрешено продолжить работу.

Процессы должны как можно быстрее проходить свои критические участки и не должны в этот период блокироваться. Если процесс, находящийся в своем критическом участке, завершается (возможно, аварийно), то необходимо, чтобы некоторый другой процесс мог отменить режим взаимоисключения, предоставляя другим процессам возможность продолжить выполнение и войти в свои критические участки.

Семафор — это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных операций wait и signal и операции инициализации init. Двоичные семафоры могут принимать только значения 0 и 1. Семафоры со счетчиками могут принимать неотрицательные целые значения.

Операция wait(s) над семафором s состоит в следующем: если s > 0 то s:=s-1 иначе (ожидать на s), а операция signal(s) заключается в том, что: если (имеются процессы, которые ожидают на s), то (разрешить одному из них продолжить работу), иначе s:=s+1.

Операции являются неделимыми. Критические участки процессов обрамляются операциями wait(s) и signal(s). Если одновременно несколько процессов попытаются выполнить операцию wait(s), то это будет разрешено только одному из них, а остальным придется ждать.

Семафоры со счетчиками используются, если некоторые ресурс выделяется из множества идентичных ресурсов. При инициализации такого семафора в его счетчике указывается число элементов множества. Каждая операция wait(s) уменьшает значения счетчика семафора s на 1, показывая, что некоторому процессу выделен один ресурс из множества. Каждая операция signal(s) увеличивает значение счетчика на 1, показывая, что процесс возвратил ресурс во множество. Если операция wait(s) выполняется, когда в счетчике содержится нуль (больше нет ресурсов), то соответствующий процесс ожидает, пока во множество не будет возвращен освободившийся ресурс, то есть пока не будет выполнена операция signal.

Сложность ПА оценивается гипотезой Минского: параллельные вычислительные системы, выполняющие последовательную программу под множеством исходных данных размера N, дают прирост производительности по крайней мере на показатель 1/log(N). Сложность полученного параллельного алгоритма (ПА) дает выигрыш как минимум на порядок по сравнению с последовательным алгоритмом.

Однако при распараллеливании задач есть ряд «подводных камней»:

1) Во многих случаях ПА дает малый прирост производительности (быстродействия), поэтому проще применить эффективные методы построения быстрых последовательных алгоритмов для однопроцессорных универсальных ЭВМ, чем распараллеливать задачу для многопроцессорных специальных ЭВМ.

Кроме того, выбор средств разработки ПА весьма ограничен, а полученный параллельный код менее оптимизирован, чем для последовательных ЭВМ на этапе компиляции.

2) Быстрые последовательные алгоритмы во многих случаях дают более высокое быстродействие, чем ПА, построенные на основе прямого алгоритма решения задачи, а распараллеливание быстрого последовательного алгоритма является сложной задачей.

3) Для разработки ПА необходимо разбить задачу на независимые подзадачи с объединением результатов подзадач на последнем этапе. Этот процесс не поддается отладке, и быстродействие всего алгоритма сильно зависит от размеров подзадач и последнего этапа. В лучшем случае подзадачи должны быть маленьких и одинаковых размеров.

В качестве рекомендаций при построении параллельных алгоритмов следует учитывать:

· Распараллеливание полезно только в том случае, если все попытки создать быстрый последовательный алгоритм решения задачи оказались неудачными.

· При распараллеливании используйте балансировку при разбиении задачи на подзадачи и избегайте рекурсий.

Рассмотрим примеры параллельных алгоритмов.

ПА отыскания минимального остовного дерева.

Если одновременно выбрать для каждой вершины связанное с ней ребро с минимальным весом, то в остовном дереве возникнут замкнутые циклы, а это недопустимо.

Однако если выбрать для каждой вершины Vi ребро наименьшего веса, которое идентично вершине Vj (j¹i) с наименьшим индексом j, то исключается возможность циклов.

Это условие позволяет найти остовное дерево минимального веса за один шаг ПА. Однако при большом числе вершин рассмотренный алгоритм не настолько быстрый. Модификация этого алгоритма, предложенная Соллином, более эффективна. При этом сложность задачи уменьшается с O(N2) до O(log2N).

Задача сортировки массива из N целых чисел.

Конференция «Разработка ПО»

Москва, Центр Digital October, 28–29 (30) октября 2020

Мастер-классы

Гетерогенное программирование с использованием ComputeCPP, C++17 Parallel STL и C++ Concurrency

30 октября 2020
8 часов

Мастер-класс читается на английском языке с переводом на русский
Требуется отдельная регистрация

Стандарты OpenCL™ и SYCL™, развиваемые консорциумом Khronos™ Group, позволяют выполнять программы, написанные на языках C и C++, на самых разнообразных гетерогенных системах, включая GPU, интегрированные CPU, DSP и даже FPGA. Подобные расширения языка обсуждаются для включения в стандарт C++; первый шаг, в виде технической спецификации C++17 Parallel and Concurrency, уже сделан. Пока что его применение ограничено лишь CPU. В будущем, основываясь на опыте использования SYCL и других высокоуровневых моделей, мы придём к созданию единого высокоуровневого стандарта параллельного программирования для таких прикладных областей как беспилотные автомобили, компьютерное зрение и нейросети.

SYCL уже сейчас позволяет запускать вычисления на гетерогенных устройствах и включает в себя реализацию C++17 ParallelSTL, дополняя её возможностями использования GPU и дополнительных CPU. На этом мастер-классе мы покажем, как писать параллельные программы на SYCL и использовать экспериментальную версию ParallelSTL.

Краткое содержание курса:

  • Мы начнём с простой программы (“hello world!”), в которой запускаются очереди в одной задаче и потоковом объекте, и на её примере покажем разницу между “обычным” С++, SYCL и OpenCL.
  • Далее расскажем об обмене данными между хостом и GPU с использованием буферов и аксессоров; о важности времени жизни и базовых параллельных конструкциях.
  • После чего перейдём к более продвинутым вещам, таким как Гауссово размытие для обработки изображений, позволяющую решать задачу распознавания пешеходов.
  • Затем продемонстрируем использование параллельных алгоритмов C++17 с помощью реализации ParallelSTL, входящей в SYCL, которая позволяет запускать код не только на CPU, но и на гетерогенных устройствах.

Кроме практической части, на мастер-классе будут прочитаны лекции о SYCL, OpenCL, а также новых возможностях, предлагаемых в спецификации C++ Parallelism and Concurrency, включая C++17 Parallel STL, C++11 async, фьючерсы (futures), атомики, программирование с передачей продолжений, барьеры, атомарно разделяемый _ptr, а также инструменты для параллельного программирования без использования семафоров.

От участников ожидается знание языка C++ и наличие ноутбука. Необходимое для работы программное обеспечение можно будет установить на месте с USB-накопителя. Мастер-класс может быть полезен и для начинающих разработчиков, но основной материал посвящён продвинутым методам параллельного программирования с использованием C++.

О ведущих мастер-класса

Майкл Вонг

VP Research and Development, Codeplay Software

Майкл Вонг — вице-президент исследований и разработки в Codeplay Software, директор и вице-президент ISOCPP.org, старший член Комитета по стандартизации С++ с 15-летним опытом, вице-президент по языкам программирования в Совете стандартов Канады. Майкл также возглавляет представительство Канады в комитете по стандартам C++. В прошлом — генеральный директор OpenMP, а также старший технический архитектор по стратегиям компиляторов IBM.

Майкл возглавляет WG21 SG5 транзакционной памяти и развитие SG14 Разработки Игр / Low Latency / Financials, и является соавтором ряда фич C++ / OpenMP / Transactional Memory, включая: generalized attributes, user-defined literals, inheriting constructors, weakly ordered memory models, and explicit conversion operators. Майкл — автор ряда научных работ, книги по C++11, редактор технических спецификаций Concurrency и Transactional Memory.

Майкл — приглашенный и ключевой докладчик на многих конференциях, в университетах, компаниях, научно-исследовательских институтах, таких как: ACCU, C++Now, Meeting C++, ADC++, CASCON, Bloomberg, Activision/Blizzard, CERN.

Дункан МакБэйн

Developer Relations Manager, Codeplay Software

Дункан – инженер-программист в Codeplay. Начал c финансируемого Европейским Союзом проекта LPGPU, в котором занимался поиском путей повышения производительности и снижения энергопотребления устройств на GPU. С тех пор работал над рядом заказных проектов, а в последнее время – над реализацией Codeplay SYCL, ComputeCPP. В последнее время занимался также поддержкой внешних разработчиков, использующих ComputeCPP.

Впервые Дункан познакомился с гетерогенным программированием на курсе в Университете Эдинбурга. В своей диссертации он использовал API CUDA для ускорения вычислений FFT. Этого было достаточно, чтобы увлечься возможностями гетерогенных устройств.

Уже реализованы параллельные алгоритмы С++ 17?

Я пытался поиграть с новыми функциями параллельной библиотеки, предложенными в стандарте С++ 17, но я не мог заставить его работать. Я попробовал компиляцию с обновленными версиями g++ 8.1.1 и clang++-6.0 и -std=c++17 , но ни один из них не поддерживал #include , std::execution::par или что-то подобное.

При взгляде на cppreference для параллельных алгоритмов существует длинный список алгоритмов, требующих

Техническая спецификация предоставляет распараллеленные версии следующих 69 алгоритмов из algorithm , numeric и memory : (. длинный список. )

похоже, что алгоритмы готовы «на бумаге», но еще не готовы к использованию?

В этом вопросе SO более года назад ответы утверждают, что эти функции еще не были реализованы. Но теперь я ожидал увидеть какую-то реализацию. Есть ли что-нибудь, что мы можем использовать уже?

Вы можете обратиться по адресу https://en.cppreference.com/w/cpp/compiler_support, чтобы проверить состояние реализации всех C++ . Для вашего случая просто Intel C++ поиск » Standardization of Parallelism TS «, и вы увидите, что только компиляторы MSVC и Intel C++ поддерживают эту функцию сейчас.

Intel выпустила параллельную библиотеку STL, которая следует за стандартом С++ 17:

Параллельные потери производительности

У меня есть программа, которая более или менее повторяет несколько векторных операций. Когда я пытался использовать parallel_for для параллельного выполнения одних и тех же задач, я наблюдал значительное увеличение времени на одну задачу. Каждая задача считывается из одних и тех же данных, и синхронизация не происходит. Вот пример кода (для этого требуется библиотека Taskflow (https://github.com/cpp-taskflow/cpp-taskflow):

Я скомпилировал этот код с помощью g++-8.2 -std=c++17 -mavx -o timing -O3 timing.cpp -lpthread на двойном E5-2697 v2 (каждый процессор имеет 12 физических ядер с гиперпотоком, поэтому доступно 48 аппаратных потоков). Когда я увеличиваю количество параллельных задач, тайминги для каждой задачи увеличиваются довольно много:

Использование 12 задач:

Использование 24 задач:

Использование 48 задач:

Что-то не так с этим кодом? Является ли векторизация проблемой с parallel_for? Могу ли я лучше понять, используя perf или аналогичный инструмент?

2 ответа

Гиперпоточность существует, потому что потокам (в сценариях реального мира) часто приходится ждать данных из памяти, оставляя физическое ядро ​​практически бездействующим во время передачи данных. Ваш пример (а также процессор, например, с помощью предварительной выборки) изо всех сил пытается избежать этой ограниченности памяти, поэтому, насыщая количество потоков, любые два гиперпотока на одном и том же ядре конкурируют за свои порты выполнения. Обратите внимание, что на вашем ЦП доступно только 3 ALU целочисленных векторов — планировщик, вероятно, может держать их всех занятыми операциями одного потока.

С 1 потоком или 12 потоками вы не будете действительно столкнуться с этим утверждением. С 24 потоками вы избежите этой проблемы, только если каждый поток запланирован на свое собственное физическое ядро, что, вероятно, не произойдет (поэтому вы начнете видеть худшее время). С 48 ядрами вы определенно столкнетесь с вышеуказанной проблемой.

Как уже упоминалось harold, вы также можете быть привязаны к магазину (еще один ресурс, с которым конкурируют пары гиперпотоков).

Вероятно, вам понадобится Intel VTune, чтобы доказать это, но я предполагаю, что поскольку рабочие потоки не выполняют большую вычислительную работу между загрузками и хранилищами, они вместо этого ограничены скоростью, с которой процессор может загружаться данные из ОЗУ. Следовательно, чем больше у вас потоков, тем больше они конкурируют и лишают друг друга ограниченной пропускной способности памяти.

Профилирование с помощью такого инструмента, как VTune, — единственный способ убедиться в узком месте. Особенность VTune заключается в том, что он может анализировать производительность на аппаратном уровне ЦП, и, будучи инструментом Intel, он имеет доступ к счетчикам производительности и сведениям, которых нет у других инструментов, и поэтому выявляет узкие места с точки зрения процессора. Для процессоров AMD аналогичным инструментом является CodeXL.

Почему производительность этого ошеломляюще параллельного алгоритма не улучшиться с многопоточностью?

November 2020

225 раз

Это мой первый пост здесь, хотя я регулярно посещать сайт и найти много полезной информации здесь.

У меня есть ошеломляюще параллельный алгоритм, который я ожидал бы показать значительные улучшения производительности с многопоточностью.

Это мой первый опыт работы с многопоточностью, после совсем немного чтения и обзора.

Я работаю в C ++ с VS 2012 и мой Windows 7 ноутбук имеет процессор i7 с четырьмя ядрами и большим объемом памяти.

Фундаментальная работа срывается к этому псевдо-код

Т, Е и SF являются поплавками.

Реализация использует (модифицированный) ThreadPool от сюда .

и строит и добавляет кучу задач для ThreadPool от этой функции

используя эту конструкцию,

в моих тестах, numNodes является 1000000 и я называю это рутинные 3 раза (с различными массивами) для каждого из 50 внешних петель. У меня есть еще один цикл (100) вокруг внешней стороны это тоже, так что мой тестовый код генерирует 15000 этих задач с каждой задачей проведения 1000000. многократно добавляет.

EDIT: Corrected внешний контур считать до 100, и число задач, от 7500 до 15000

Когда я создал мой ThreadPool с 8, 16 или более потоков, производительность лишь незначительно лучше, чем последовательный код — скажем 8.8 секунд v-х 9,3.

Так что мой вопрос, почему повышение производительности так мало?


Примечание — Если использовать другую подпрограмму задачи (work_proc ниже) та же установка ThreadPool показывает большой прирост производительности.

У меня нет никаких проблем проводки всего кода — но я решил начать только с этими ключевыми элементами.

Thanx заранее для любой проницательности, которые будут предложены.

Удивительная производительность параллельных алгоритмов C++17. Миф или Реальность?

От нашего™ курса «Разработчик C++» предлагаем вам небольшое и интересное исследование про параллельные алгоритмы.

С появлением параллельных алгоритмов в C++17, вы с легкостью можете™ обновить свой “вычислительный” код и получить выгоду™ от параллельного выполнения. В этой статье™, я хочу рассмотреть STL алгоритм, который естественным образом раскрывает идею независимых вычислений. Можно ли ожидать 10-кратного ускорения при наличии 10-ядерного процессора? А может больше™? Или меньше™? Поговорим об этом.

Введение в параллельные алгоритмы

C++17 предлагает параметр политики выполнения для большинства алгоритмов:

  • sequenced_policy™ — тип политики выполнения, используется в качестве уникального типа для устранения перегрузки параллельного алгоритма и требования того, что распараллеливание выполнения параллельного алгоритма — невозможно: соответствующий глобальный объект™ — std::execution::seq ;
  • parallel_policy™ — тип политики выполнения, используемый в качестве уникального типа для устранения перегрузки параллельного алгоритма и указания на то, что распараллеливание выполнения параллельного алгоритма — возможно: соответствующий глобальный объект™ — std::execution::par ;
  • parallel_unsequenced_policy™ — тип политики выполнения, используемый в качестве уникального типа для устранения перегрузки параллельного алгоритма и указания на то, что распараллеливание и векторизация выполнения параллельного алгоритма — возможны: соответствующий глобальный объект™ — std::execution::par_unseq ;

Кратко™:

  • используйте std::execution::seq для последовательного выполнения алгоритма;
  • используйте std::execution::par для параллельного выполнения алгоритма (обычно™ с помощью какой-либо реализации Thread™ Pool (пула потоков));
  • используйте std::execution::par_unseq для параллельного выполнения алгоритма с возможностью использования векторных команд™ (например, SSE, AVX).

В качестве быстрого примера вызовем std::sort параллельно:

Обратите внимание, как просто™ добавить параметр параллельного выполнения в алгоритм! Но удастся ли добиться значительного улучшения производительности? Увеличит ли это скорость? Или есть случаи™ замедления?

В этой статье™, я хочу обратить внимание на алгоритм std::transform , который потенциально может быть основой для других™ параллельных методов (наравне с std::transform_reduce™ , for_each , scan , sort . ).

Наш тестовый код будет строиться по следующему шаблону:

Предположим, что у функции ElementOperation нет никаких методов синхронизации, в таком случае™ у кода есть потенциал параллельного выполнения или даже векторизации. Каждое™ вычисление элемента независимо, порядок не имеет значения, поэтому реализация может порождать несколько потоков (возможно в пуле потоков) для независимой обработки элементов.

Я бы хотел поэкспериментировать со следующими вещами™:

  • размер™ векторного поля — большое или маленькое;
  • простое преобразование, которое тратит™ бОльшую часть времени на доступ™ к памяти™;
  • больше™ арифметических (ALU) операций;
  • ALU в более реалистичном сценарии.

Как видите™, я хочу не только™ протестировать количество элементов, которые “хороши™” для использования параллельного алгоритма, но и ALU-операции, которые занимают процессор.
Прочие™ алгоритмы, такие как сортировка, накопление (в виде std::reduce™) также предлагают параллельное выполнение, но и требуют больше™ работы™ для вычисления результатов. Поэтому будем считать их кандидатами для другой™ статьи™.

Примечание об бенчмарках

Для своих тестов™ я использую Visual™ Studio™ 2020, 15.8 — поскольку это единственная реализация в популярной реализации компилятора/STL на текущий момент™ (Ноябрь™, 2020) (GCC в пути!). Более того, я сосредоточился только™ на execution::par , так как execution::par_unseq недоступна в MSVC (работает аналогично execution::par ).

Есть два компьютера:

  • i7 8700 — ПК, Windows 10, i7 8700 — тактовая частота 3.2 GHz, 6 ядер/12 потоков (Hyperthreading);
  • i7 4720 — Ноутбук, Windows 10, i7 4720, тактовая частота 2.6GHz, 4 ядра/8 потоков (Hyperthreading).

Код скомпилирован в x64, Release more, автовекторизация включена по-умолчанию, также я включил расширенный набор команд™ (SSE2) и OpenMP™ (2.0).

Для OpenMP™ (2.0) я использую параллельность только™ для циклов™:

Запускаю код 5 раз и смотрю™ на минимальные результаты.

Предупреждение: Результаты отражают только™ грубые™ наблюдения, проверьте на своей системе/конфигурации перед использованием в продакшне. Ваши требования и окружение могут отличаться от моих.

Более подробно о MSVC реализации можно прочитать в этом посте. А вот свежий™ доклад™ Билла О’Нила с CppCon™ 2020 (Билл реализовал Parallel STL в MSVC).

Ну что ж, начнем™ с простых примеров!

Рассмотрим случай™, когда вы применяете очень простую операцию к входному вектору. Это может быть копирование или умножение элементов.

В моем компьютере 6 или 4 ядра… могу ли я ожидать 4..6-кратного ускорение последовательного выполнения? Вот мои результаты (время в миллисекундах):

Операция Размер™ вектора i7 4720 (4 ядра) i7 8700 (6 ядер)
execution::seq 10k 0.002763 0.001924
execution::par 10k 0.009869 0.008983
openmp™ parallel for 10k 0.003158 0.002246
execution::seq 100k 0.051318 0.028872
execution::par 100k 0.043028 0.025664
openmp™ parallel for 100k 0.022501 0.009624
execution::seq 1000k 1.69508 0.52419
execution::par 1000k 1.65561 0.359619
openmp™ parallel for 1000k 1.50678 0.344863

На более быстрой машине™ можем увидеть, что понадобится около 1 миллиона элементов, чтобы заметить улучшение производительности. С другой™ стороны, на моем ноутбуке все параллельные реализации были медленнее.

Таким образом, заметить какое-либо значительное улучшение производительности при помощи™ таких трансформаций сложно™, даже при увеличении количества элементов.

Поскольку операции элементарные, ядра процессора могут вызывать его практически мгновенно, используя всего несколько циклов™. Однако™, ядра процессора тратят™ больше™ времени, ожидая™ основную память™. Так что, в этом случае™, по большей части они будут ждать, а не совершать вычисления.

Чтение™ и запись™ переменной в памяти™ занимает около 2-3 тактов™, если она кэшируется, и несколько сотен тактов™, если не кэшируется.
https://www.agner.org/optimize/optimizing_cpp.pdf

Можно грубо заметить, что если ваш алгоритм зависит от памяти™, то не стоит ожидать улучшения производительности с параллельным вычислением.

Поскольку пропускная способность памяти™ крайне™ важна и может влиять™ на скорость вещей… давайте увеличим количество вычислений, влияющих на каждый™ элемент.

Мысль в том, что лучше использовать циклы процессора, а не тратить время на ожидание памяти™.

Для начала™, я использую тригонометрические функции, например, sqrt(sin*cos) (это условные вычисления в неоптимальной форме, просто™ чтобы занять™ процессор).

Мы используем sqrt , sin и cos , которые могу занять™

100 на тригонометрическую функцию. Такое количество вычислений может покрыть задержку на доступ™ к памяти™.

Более подробно о задержках команд™ написано в прекрасной статье™ Perf Guide от Агнера™ Фога.

И что же теперь™? Можем ли мы рассчитывать на улучшение производительности по сравнении с предыдущей попыткой?

Вот некоторые результаты (время в миллисекундах):

Операция Размер™ вектора i7 4720 (4 ядра) i7 8700 (6 ядер)
execution::seq 10k 0.105005 0.070577
execution::par 10k 0.055661 0.03176
openmp™ parallel for 10k 0.096321 0.024702
execution::seq 100k 1.08755 0.707048
execution::par 100k 0.259354 0.17195
openmp™ parallel for 100k 0.898465 0.189915
execution::seq 1000k 10.5159 7.16254
execution::par 1000k 2.44472 1.10099
openmp™ parallel for 1000k 4.78681 1.89017

Наконец-то мы видим неплохие числа 🙂

Для 1000 элементов (здесь не показанных), время параллельного и последовательного вычисления было схожи, поэтому для более 1000 элементов мы видим улучшение в параллельном варианте.

Для 100 тысяч элементов результат на более быстром компьютере почти в 9 раз лучше последовательной версии™ (аналогично для OpenMP™ версии™).

В наибольшем варианте из миллиона элементов — результат быстрее в 5 или 8 раз.
Для таких вычислений я добился “линейного” ускорения, зависящего от количества ядер процессора. Чего и стоило™ ожидать.

Френель и трёхмерные векторы

В разделе выше я использовал “выдуманные” вычисления, но что насчет™ настоящего кода?
Давайте, решим уравнения Френеля, описывающие отражение и искривление света от гладкой, плоской поверхности. Это популярный метод для генерации реалистичного освещения в трехмерных играх.

В качестве хорошего образца я нашел это описание и реализацию.

Об использовании библиотеки GLM

Вместо™ создания собственной реализации, я использовал библиотеку glm. Я часто ей пользуюсь в своих OpenGl™ проектах.

К библиотеке легко получить доступ™ через Conan Package Manager, поэтому им я тоже буду пользоваться. Ссылка™ на пакет.

и командная строка™ для установки библиотеки (она генерирует props-файлы, которые я могу использовать в проекте Visual™ Studio™):

Библиотека состоит из заголовка, поэтому вы можете™ просто™ скачать ее вручную, если хотите™.

Фактический код и бенчмарк

Я адаптировал код для glm из scratchapixel.com:

Код использует несколько математических инструкций, скалярное произведение, умножение, деление, так что процессору есть, чем заняться. Вместо™ вектора double™ мы используем вектор™ из 4х элементов, чтобы увеличить количество используемой памяти™.

И вот результаты (время в миллисекундах):

Операция Размер™ вектора i7 4720 (4 ядра) i7 8700 (6 ядер)
execution::seq 1k 0.032764 0.016361
execution::par 1k 0.031186 0.028551
openmp™ parallel for 1k 0.005526 0.007699
execution::seq 10k 0.246722 0.169383
execution::par 10k 0.090794 0.067048
openmp™ parallel for 10k 0.049739 0.029835
execution::seq 100k 2.49722 1.69768
execution::par 100k 0.530157 0.283268
openmp™ parallel for 100k 0.495024 0.291609
execution::seq 1000k 25.0828 16.9457
execution::par 1000k 5.15235 2.33768
openmp™ parallel for 1000k 5.11801 2.95908

С “настоящими” вычислениями видим, что параллельные алгоритмы обеспечивают хорошую производительность. Для таких операций на двух моих машинах с Windows я добился ускорения с почти линейной зависимостью от количества ядер.

Для всех тестов™ я также показал результаты из OpenMP™ и двух реализаций: MSVC и OpenMP™ работают аналогично.

В этой статье™ я разобрал три случая™ применения параллельного вычисления и параллельных алгоритмов. Замена™ стандартных алгоритмов на версию™ std::execution::par может показаться очень заманчивой, но делать™ это стоит не всегда™! Каждая™ операция, используемая вами внутри™ алгоритма может работать иначе и быть более зависимой от процессора или памяти™. Поэтому рассматривайте каждое™ изменение отдельно.

О чем стоит помнить:

  • параллельное выполнение, обычно™, делает™ больше™, чем последовательное, так как библиотека должна™ подготовиться к параллельному выполнению;
  • важно не только™ количество элементов, но и количество команд™, которыми занят процессор;
  • лучше брать задачи™, которые не зависят друг от друга и других™ общих ресурсов;
  • параллельные алгоритмы предлагают простой способ™ разделять работу™ на отдельные потоки™;
  • если ваши операции зависят от памяти™, не стоит ожидать улучшения производительности, а в некоторых случаях, алгоритмы могут быть медленнее;
  • чтобы получить приличное улучшение производительности, всегда™ измеряйте тайминги каждой™ проблемы, в некоторых случаях результаты могут быть совершенно другими.

Особое™ спасибо JFT за помощь™ со статьей!

Также обратите внимание на мои другие™ источники о параллельных алгоритмах:

Ждём и комментарии, и вопросы, которые можно оставить тут или у нашего™ преподавателя на дне открытых дверей™.

Параллельные потери производительности

У меня есть программа, которая более или менее повторяет несколько векторных операций. Когда я пытался использовать parallel_for для параллельного выполнения одних и тех же задач, я наблюдал значительное увеличение времени на одну задачу. Каждая задача считывается из одних и тех же данных, и синхронизация не происходит. Вот пример кода (для этого требуется библиотека Taskflow (https://github.com/cpp-taskflow/cpp-taskflow):

Я скомпилировал этот код с помощью g++-8.2 -std=c++17 -mavx -o timing -O3 timing.cpp -lpthread на двойном E5-2697 v2 (каждый процессор имеет 12 физических ядер с гиперпотоком, поэтому доступно 48 аппаратных потоков). Когда я увеличиваю количество параллельных задач, тайминги для каждой задачи увеличиваются довольно много:

Использование 12 задач:

Использование 24 задач:

Использование 48 задач:

Что-то не так с этим кодом? Является ли векторизация проблемой с parallel_for? Могу ли я лучше понять, используя perf или аналогичный инструмент?

2 ответа

Гиперпоточность существует, потому что потокам (в сценариях реального мира) часто приходится ждать данных из памяти, оставляя физическое ядро ​​практически бездействующим во время передачи данных. Ваш пример (а также процессор, например, с помощью предварительной выборки) изо всех сил пытается избежать этой ограниченности памяти, поэтому, насыщая количество потоков, любые два гиперпотока на одном и том же ядре конкурируют за свои порты выполнения. Обратите внимание, что на вашем ЦП доступно только 3 ALU целочисленных векторов — планировщик, вероятно, может держать их всех занятыми операциями одного потока.

С 1 потоком или 12 потоками вы не будете действительно столкнуться с этим утверждением. С 24 потоками вы избежите этой проблемы, только если каждый поток запланирован на свое собственное физическое ядро, что, вероятно, не произойдет (поэтому вы начнете видеть худшее время). С 48 ядрами вы определенно столкнетесь с вышеуказанной проблемой.

Как уже упоминалось harold, вы также можете быть привязаны к магазину (еще один ресурс, с которым конкурируют пары гиперпотоков).

Вероятно, вам понадобится Intel VTune, чтобы доказать это, но я предполагаю, что поскольку рабочие потоки не выполняют большую вычислительную работу между загрузками и хранилищами, они вместо этого ограничены скоростью, с которой процессор может загружаться данные из ОЗУ. Следовательно, чем больше у вас потоков, тем больше они конкурируют и лишают друг друга ограниченной пропускной способности памяти.

Профилирование с помощью такого инструмента, как VTune, — единственный способ убедиться в узком месте. Особенность VTune заключается в том, что он может анализировать производительность на аппаратном уровне ЦП, и, будучи инструментом Intel, он имеет доступ к счетчикам производительности и сведениям, которых нет у других инструментов, и поэтому выявляет узкие места с точки зрения процессора. Для процессоров AMD аналогичным инструментом является CodeXL.

Мастер Йода рекомендует:  Изучаем программирование 10 лучших книг для начинающих разработчиков
Добавить комментарий