Calculer la sum d’un grand vecteur en parallèle

Problème de fond

J’ai un programme qui prend actuellement trop de temps pour résumer de gros std::vector s de ~ 100 millions d’éléments en utilisant std::accumulate , ce qui constitue un goulot d’étranglement.

Je veux que ce soit plus rapide et que ce soit un calcul asynchrone pour que l’interface graphique / serveur ne bloque pas. Le calcul devrait également utiliser le multithreading afin que je puisse réduire le temps nécessaire pour résumer un vecteur.

Je souhaite fractionner la sum de manière à ce que chaque thread additionne une partie du vecteur, puis lorsque toutes les sums partielles sont calculées, la sum partielle de chaque thread doit être additionnée pour obtenir la sum totale.

Boost.Asio?

Je me demandais comment je pourrais y arriver dans Boost.Asio ? Mon programme doit idéalement réutiliser les threads (comme un groupe de threads ), sans savoir comment stocker et récupérer les sums partielles et enfin récupérer la sum des sums partielles.

Je pensais créer un groupe de threads appelé boost::asio::io_service::run , en passant un gestionnaire pour calculer les sums partielles, mais je ne suis pas sûr de savoir comment passer les sums partielles à un autre gestionnaire et append toutes les données partielles. sums ensemble.

Ce serait formidable si quelqu’un montrait un code squelette de la façon dont je pouvais m’y prendre.

Est-ce que Boost.Asio convient à ce problème?

Boost.Asio a pour objective principal de fournir un modèle asynchrone pour la programmation réseau et les E / S , et le problème que vous décrivez ne semble pas avoir grand chose à voir avec le réseau et les E / S.

Je pense que la solution la plus simple consiste à utiliser les primitives de thread fournies par Boost ou par la bibliothèque standard C ++.

Un algorithme parallèle

Voici un exemple de version parallèle de accumulate créée en utilisant uniquement la bibliothèque standard.

 /* Minimum number of elements for multithreaded algorithm. Less than this and the algorithm is executed on single thread. */ static const int MT_MIN_SIZE = 10000; template  auto parallel_accumulate(InputIt first, InputIt last, T init) { // Determine total size. const auto size = std::distance(first, last); // Determine how many parts the work shall be split into. const auto parts = (size < MT_MIN_SIZE)? 1 : std::thread::hardware_concurrency(); std::vector> futures; // For each part, calculate size and run accumulate on a separate thread. for (std::size_t i = 0; i != parts; ++i) { const auto part_size = (size * i + size) / parts - (size * i) / parts; futures.emplace_back(std::async(std::launch::async, [=] { return std::accumulate(first, std::next(first, part_size), T{}); })); std::advance(first, part_size); } // Wait for all threads to finish execution and accumulate results. return std::accumulate(std::begin(futures), std::end(futures), init, [] (const T prev, auto& future) { return prev + future.get(); }); } 

Exemple en direct (la version parallèle fonctionne à peu près de la même manière que la commande séquentielle sur Coliru, probablement un seul cœur disponible)

Les horaires

Sur ma machine (utilisant 8 threads), la version parallèle donnait en moyenne un gain de performances d’environ 120%.

Somme séquentielle:
Temps pris: 46 ms
5000000050000000
——————————–
Somme parallèle:
Temps pris: 21 ms
5000000050000000

Cependant, le gain absolu pour 100 000 000 d’éléments n’est que marginal (25 ms). Cependant, le gain de performance peut être supérieur lors de l’accumulation d’un type d’élément différent de celui d’ int .

OpenMP

Comme mentionné par @sehe dans les commentaires, il convient de mentionner qu’OpenMP pourrait fournir une solution simple à ce problème, par exemple

 template  auto omp_accumulate(const std::vector& v, U init) { U sum = init; #pragma omp parallel for reduction(+:sum) for(std::size_t i = 0; i < v.size(); i++) { sum += v[i]; } return sum; } 

Sur ma machine, cette méthode fonctionnait de la même manière que la méthode parallèle en utilisant des primitives de thread standard.

Somme séquentielle:
Temps pris: 46 ms
5000000050000000
--------------------------------
Somme parallèle:
Temps pris: 21 ms
Somme: 5000000050000000
--------------------------------
Somme OpenMP:
Temps pris: 21 ms
Somme: 5000000050000000

Vous pouvez utiliser Boost Asio en tant que pool de threads. Mais cela n’a pas beaucoup de sens sauf si vous avez … des opérations d’E / S asynchrones à coordonner.

Dans cette réponse à ” files de travail c ++ avec blocage “, je montre deux implémentations de thread_pool :

  • Solution n ° 1: basée sur boost::asio::io_service
  • Solution n ° 2: l’autre basée sur les primitives boost::thread

Les deux acceptent toute tâche compatible avec la signature void() . Cela signifie que vous pouvez encapsuler votre fonction “qui renvoie” les résultats importants dans une future packaged_task<...> et en extraire la future .