¿Cómo determinan los algoritmos de C++ STL (ExecutionPolicy) cuántos hilos paralelos usar?

5 minutos de lectura

C++17 actualizó 69 algoritmos STL para admitir el paralelismo mediante el uso de un parámetro ExecutionPolicy opcional (como primer argumento). p.ej.

std::sort(std::execution::par, begin(v), end(v));

Sospecho que el estándar C++17 deliberadamente no dice nada sobre cómo para implementar los algoritmos de subprocesos múltiples, dejando que los escritores de la biblioteca decidan qué es lo mejor (y permitiéndoles cambiar de opinión, más adelante). Aún así, estoy interesado en comprender a un alto nivel qué problemas se están considerando en la implementación de los algoritmos STL paralelos.

Algunas preguntas en mi mente incluyen (¡pero no se limitan a!):

  • ¿Cómo se relaciona la cantidad máxima de subprocesos utilizados (por la aplicación C++) con la cantidad de núcleos de CPU y/o GPU en la máquina?
  • ¿Qué diferencias hay en el número de subprocesos que utiliza cada algoritmo? (¿Cada algoritmo usará siempre la misma cantidad de subprocesos en todas las circunstancias?)
  • ¿Se tienen en cuenta otras llamadas STL paralelas en otros subprocesos (dentro de la misma aplicación)? (por ejemplo, si un subproceso invoca std::for_each(par,…), utilizará más/menos/mismos subprocesos dependiendo de si un std::sort(par,…) ya se está ejecutando en algún otro subproceso (s)? ¿Hay un grupo de subprocesos tal vez?)
  • ¿Se tiene en cuenta lo ocupados que están los núcleos debido a factores externos? (por ejemplo, si 1 núcleo está muy ocupado, digamos analizando señales SETI, ¿reducirá la aplicación C++ la cantidad de subprocesos que usa?)
  • ¿Algunos algoritmos solo usan núcleos de CPU? o solo núcleos GPU?
  • Sospecho que las implementaciones variarán de una biblioteca a otra (¿compilador a compilador?), Incluso los detalles sobre esto serían interesantes.

Me doy cuenta de que el objetivo de estos algoritmos paralelos es proteger al programador de tener que preocuparse por estos detalles. Sin embargo, cualquier información que me brinde una imagen mental de alto nivel de lo que sucede dentro de las llamadas de la biblioteca sería apreciada.

  • Aunque su pregunta es bastante interesante, probablemente sea demasiado amplia. La mejor manera de responder a sus preguntas sería mirar las implementaciones de libstdc++ y libc++.

    – Rakete1111

    31 de octubre de 2017 a las 5:58

  • Una implementación sencilla utiliza un grupo de subprocesos con un subproceso por núcleo de CPU y una cola de tareas que envía tareas a los subprocesos a pedido.

    – Pete Becker

    31 de octubre de 2017 a las 12:11

avatar de usuario
Fusho

La mayoría de estas preguntas no pueden ser respondidas por el estándar a día de hoy. Sin embargo, tu pregunta, según tengo entendido, mezcla dos conceptos:

C1. Restricciones en algoritmos paralelos

C2. Ejecución de algoritmos

Todo lo relacionado con STL paralelo de C++17 se trata de C1: establece restricciones sobre cómo funcionan las instrucciones y/o los subprocesos. podría ser intercalado/transformado en un cómputo paralelo. Por otro lado, C2 se trata de estar estandarizado, la palabra clave es executor (más sobre esto más adelante).

Para C1, hay 3 pólizas estándar (en std::execution::seq, par y par_unseq) que corresponden a cada combinación de paralelismo de tareas e instrucciones. Por ejemplo, al realizar una acumulación de enteros, par_unseq podría usarse, ya que el orden no es importante. Sin embargo, para la aritmética de coma flotante, donde la suma no es asociativa, un mejor ajuste sería seq para, al menos, obtener un resultado determinista. En resumen: las políticas establecen restricciones en el cómputo paralelo y estas restricciones podrían ser potencialmente explotadas por un compilador inteligente.

Por otro lado, una vez que tenga un algoritmo paralelo y sus restricciones (y posiblemente después de alguna optimización/transformación), el executor encontrará una manera de ejecutarlo. Hay ejecutores predeterminados (para la CPU, por ejemplo) o puede crear los suyos propios, luego, se puede establecer toda esa configuración con respecto a la cantidad de subprocesos, la carga de trabajo, la unidad de procesamiento, etc.

A partir de hoy, C1 está en el estándar, pero no C2, por lo que si usa C1 con un compilador compatible, no podrá especificar qué perfil de ejecución desea y la implementación de la biblioteca decidirá por usted (tal vez a través de extensiones).

Entonces, para responder a sus preguntas:

(Con respecto a sus primeras 5 preguntas) Por definición, la biblioteca STL paralela de C ++ 17 no define ningún cálculo, solo dependencia de datos, para permitir posibles transformaciones de flujo de datos. Todas estas preguntas serán respondidas (con suerte) por executorpuedes ver la propuesta actual aquí. Se verá algo como:

executor = get_executor();
sort( std::execution::par.on(executor), vec.begin(), vec.end());

Algunas de sus preguntas ya están definidas en esa propuesta.

(Para el 6) Hay una serie de bibliotecas que ya implementan conceptos similares (C++ executor se inspiró en algunos de ellos), AFAIK: hpx, Thrust o Boost.Compute. No sé cómo se implementan realmente los dos últimos, pero para hpx usan subprocesos ligeros y puedes configurar el perfil de ejecución. Además, la sintaxis esperada (aún no estandarizada) del código anterior para C ++ 17 es esencialmente la misma que en hpx (fue fuertemente inspirada por).

Referencias:

  1. Algoritmos paralelos de C++17 y más allá por Bryce Adelstein Lelbach
  2. El futuro de la computación heterogénea ISO C++ por Michael Wong
  3. Ejecutores de Keynote C++ para permitir hoy la computación heterogénea en el C++ del mañana por Michael Wong
  4. Ejecutores para C++: una larga historia por Detlef Vollmann

Borrador prefinal de C++17 no dice nada sobre “cómo implementar los algoritmos de subprocesos múltiples“, eso es cierto. Los propietarios de la implementación deciden por sí mismos cómo hacerlo. Por ejemplo STL paralelo usos TBB como back-end de subprocesamiento y MP abierto como back-end de vectorización. Supongo que para saber cómo esta implementación coincide con su máquina, debe leer el específico de la implementación documentación

¿Ha sido útil esta solución?