Algoritmos Paralelos y Politicas de Ejecucion
Aprovecha la STL paralela de C++17 para paralelizar ordenamiento, transformacion y reduccion con politicas de ejecucion. Comprende cuando el paralelismo ayuda, la ley de Amdahl y el diseno practico de pools de hilos.
STL Paralela — Paralelismo Facil
C++17 agrego politicas de ejecucion a la mayoria de las funciones de
Esta es la forma mas facil de agregar paralelismo a C++: toma tu llamada existente a std::sort, std::transform o std::for_each, antepone std::execution::par, y deja que la implementacion haga el resto. Por supuesto, debes asegurarte de que tus operaciones sean seguras para ejecucion concurrente (sin carreras de datos en predicados, sin estado mutable compartido).
Politicas de Ejecucion Explicadas
Hay tres politicas de ejecucion estandar definidas en
#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>
#include <chrono>
int main() {
std::vector<int> data(10'000'000);
std::iota(data.begin(), data.end(), 0);
// Sequential — same as no policy
auto t1 = std::chrono::high_resolution_clock::now();
std::sort(std::execution::seq, data.begin(), data.end(),
std::greater<>{});
auto t2 = std::chrono::high_resolution_clock::now();
// Parallel — may use multiple threads
std::sort(std::execution::par, data.begin(), data.end());
auto t3 = std::chrono::high_resolution_clock::now();
// Parallel + vectorized — threads AND SIMD
std::sort(std::execution::par_unseq, data.begin(), data.end(),
std::greater<>{});
auto t4 = std::chrono::high_resolution_clock::now();
auto ms = [](auto a, auto b) {
return std::chrono::duration_cast<std::chrono::milliseconds>(b - a).count();
};
std::cout << "seq: " << ms(t1, t2) << "ms\n";
std::cout << "par: " << ms(t2, t3) << "ms\n";
std::cout << "par_unseq: " << ms(t3, t4) << "ms\n";
return 0;
}std::reduce vs std::accumulate
std::accumulate procesa elementos estrictamente de izquierda a derecha y no puede paralelizarse. std::reduce (C++17) permite que la implementacion procese elementos en cualquier orden y combine resultados parciales — habilitando la ejecucion paralela. La operacion debe ser asociativa y conmutativa para que reduce produzca resultados correctos.
#include <numeric>
#include <execution>
#include <vector>
#include <iostream>
int main() {
std::vector<double> data(1'000'000, 1.0);
// Sequential accumulate — always left-to-right
double sum1 = std::accumulate(data.begin(), data.end(), 0.0);
// Parallel reduce — may split and combine in any order
double sum2 = std::reduce(std::execution::par,
data.begin(), data.end(), 0.0);
// Transform-reduce: parallel dot product
std::vector<double> a(1'000'000, 2.0);
std::vector<double> b(1'000'000, 3.0);
double dot = std::transform_reduce(
std::execution::par,
a.begin(), a.end(), b.begin(),
0.0); // default: multiply + add
std::cout << "accumulate: " << sum1 << "\n";
std::cout << "reduce: " << sum2 << "\n";
std::cout << "dot product: " << dot << "\n"; // 6'000'000
return 0;
}Al usar politicas de ejecucion paralela, el llamable (predicado, funcion de transformacion, operador de reduccion) que pasas al algoritmo puede ser invocado concurrentemente desde multiples hilos. Si tu llamable accede a estado mutable compartido, tienes una carrera de datos:
int count = 0;
std::for_each(std::execution::par, v.begin(), v.end(),
[&count](int x) {
if (x > 0) ++count; // CARRERA DE DATOS! Multiples hilos incrementan count
});Usa std::atomic, acumuladores locales de hilo, o mejor aun, usa std::reduce / std::count_if que manejan la agregacion de forma segura.
Ley de Amdahl — Cuando el Paralelismo Ayuda
La ley de Amdahl establece que la aceleracion maxima del paralelismo esta limitada por la fraccion secuencial de tu programa. Si el 10% del trabajo debe hacerse secuencialmente, entonces incluso con infinitos hilos, la aceleracion maxima es de 10x.
Aceleracion = 1 / (S + P/N), donde S es la fraccion secuencial, P es la fraccion paralela y N es el numero de hilos.
El paralelismo tambien tiene sobrecarga: creacion de hilos, sincronizacion, contencion de cache y false sharing. Para conjuntos de datos pequenos, la sobrecarga puede exceder el beneficio. Reglas generales:
- Sort: El std::sort paralelo tipicamente ayuda por encima de ~100K elementos.
- Transform/for_each: Beneficia por encima de ~10K elementos con trabajo no trivial por elemento.
- Reduce: Beneficia por encima de ~100K elementos o con operaciones costosas.
- Siempre mide — perfila con y sin std::execution::par.
Vista General Practica del Pool de Hilos
El estandar C++ no proporciona un pool de hilos (hasta C++23), pero el patron es sencillo: un conjunto fijo de hilos trabajadores extrae tareas de una cola compartida. Aqui hay un bosquejo minimo.
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <functional>
#include <vector>
class ThreadPool {
std::vector<std::thread> workers_;
std::queue<std::function<void()>> tasks_;
std::mutex mtx_;
std::condition_variable cv_;
bool stop_ = false;
public:
explicit ThreadPool(size_t n) {
for (size_t i = 0; i < n; ++i) {
workers_.emplace_back([this] {
while (true) {
std::function<void()> task;
{
std::unique_lock lock(mtx_);
cv_.wait(lock, [this] {
return stop_ || !tasks_.empty();
});
if (stop_ && tasks_.empty()) return;
task = std::move(tasks_.front());
tasks_.pop();
}
task(); // run outside the lock
}
});
}
}
void enqueue(std::function<void()> task) {
{
std::lock_guard lock(mtx_);
tasks_.push(std::move(task));
}
cv_.notify_one();
}
~ThreadPool() {
{
std::lock_guard lock(mtx_);
stop_ = true;
}
cv_.notify_all();
for (auto& w : workers_) w.join();
}
};
int main() {
ThreadPool pool(4);
for (int i = 0; i < 20; ++i) {
pool.enqueue([i] {
std::cout << "Task " << i << " on thread "
<< std::this_thread::get_id() << "\n";
});
}
// pool destructor waits for all tasks
return 0;
}Prefiere std::execution::par sobre paralelismo escrito a mano para algoritmos estandar — la implementacion conoce tu hardware. Siempre verifica que tu llamable este libre de carreras de datos y efectos secundarios. Usa std::reduce en lugar de std::accumulate cuando necesites paralelismo. Mide con tamanos de datos realistas; para entradas pequenas, lo secuencial puede ser mas rapido. Recuerda que par_unseq prohibe llamar a cualquier cosa que adquiera un lock (incluyendo la asignacion de memoria en algunas plataformas).
- Las politicas de ejecucion de C++17 (
seq,par,par_unseq) agregan paralelismo a algoritmos estandar con cambios de codigo minimos std::reducees el reemplazo amigable con el paralelismo parastd::accumulate— tu operacion debe ser asociativa y conmutativa- La ley de Amdahl limita la aceleracion: la porcion secuencial de tu codigo se convierte en el cuello de botella
- Los algoritmos paralelos tienen sobrecarga — solo son beneficiosos para conjuntos de datos suficientemente grandes o trabajo costoso por elemento
- Siempre asegurate de que los llamables pasados a algoritmos paralelos esten libres de carreras de datos
- Los pools de hilos reutilizan un conjunto fijo de hilos para evitar el costo de la creacion de hilos para muchas tareas pequenas
Quiz — Pon a prueba tus conocimientos
(15 XP)1. Por que `std::accumulate` no puede usarse con politicas de ejecucion?
2. Que restriccion impone `std::execution::par_unseq` sobre el llamable?
3. Segun la ley de Amdahl, cual es la aceleracion maxima si el 20% de un programa es secuencial?