Y a-t-il des algorithmes concurrents en cours d'utilisation qui fonctionnent correctement sans aucune synchronisation?

Question

Tous les programmes concurrents que j'ai vus ou dont j'ai entendu parler (admettant que c'est un petit ensemble) utilisent à un moment donné des fonctionnalités de synchronisation matérielle, généralement sous forme de compare-and-swap. La question est : y a-t-il des programmes concurrents dans la nature où les threads interagissent tout au long de leur vie sans aucune synchronisation ?

Voici des exemples auxquels je pense :

Un programme qui se résume à un seul thread exécutant un test oui/non sur un grand ensemble de cas et un grand nombre de threads étiquetant les cas en fonction d'un test peut-être/non. Cela ne nécessite pas de synchronisation car les données non fiables n'affecteront que les performances et non la correction.

Un programme dans lequel de nombreux threads mettent à jour une structure de données où tout état valide maintenant le restera toujours, donc les lectures ou écritures non fiables ne rendent rien invalide. Un exemple de ceci est (je pense) la compression de chemin dans l'algorithme union-find.

Answer 1

Si vous pouvez diviser le travail en morceaux complètement indépendants, alors oui, il existe des algorithmes concurrents dont le seul point de synchronisation est celui à la fin du travail où tous les threads se rejoignent. L'accélération parallèle dépend alors de la capacité à diviser les tâches en morceaux de taille aussi similaire que possible.

Answer 2

Certaines méthodes indirectes pour résoudre des systèmes d'équations linéaires, comme la relaxation successive (http://en.wikipedia.org/wiki/Successive_over-relaxation), n'ont pas vraiment besoin que les itérations soient synchronisées.

Answer 3

Je pense que c'est une question un peu complexe car, par exemple, si vous programmez en C, malloc() doit être multi-thread sécurisé et utiliser une synchronisation matérielle, et en Java, le collecteur de déchets nécessite de toute façon une synchronisation matérielle. Tous les programmes Java nécessitent le GC, et presque aucun programme C ne peut s'en passer de malloc() (ou un programme C++ / opérateur new()).

Answer 4

Il existe toute une classe d'algorithmes qui sont parfois appelés "embarallel" (contraction de "embarrassingly parallel"). De nombreux algorithmes de traitement d'image entrent dans cette classe, où chaque pixel peut être traité indépendamment (ce qui facilite l'implémentation avec par exemple SIMD ou GPGPU).

Answer 5

Eh bien, sans aucune synchronisation du tout (même à la fin de l'algorithme), vous ne pouvez évidemment rien faire de utile car vous ne pouvez même pas transférer les résultats des calculs concurrents au thread principal : supposez qu'ils se trouvaient sur des machines distantes sans aucun canal de communication vers la machine principale.