Parallélisation BLAKE

Question

J'ai un gros problème pour paralléliser BLAKE en utilisant OMP. Ils ont soutenu dans la spécification qu'il est possible de paralléliser "étape de la colonne" et "étape diagonale". J'essaye de faire ceci mais les résultats sont opposés que je m'attendais (10 fois plus lent que one-threaded). Je besoin d'un peu d'aide des utilisateurs plus expérimentés de OMP, parce que maintenant je ne sais pas comment paralléliser cette boucle :(

Mise à jour:

Je sais que les auteurs de BLAKE publiés BLAKE2, qui est améliorée (plus rapide) BLAKE, mais son implémentation est différente de celle de BLAKE, ce qui est assez difficile à comprendre pour moi: ma tâche est de comparer les implémentations mono-thread et multi-thread avec OMP. Je ne suis pas expert en OMP, je veux faire BLAKE multi-thread de la manière la plus simple possible, je dois faire une implémentation correcte avec OMP même si la performance n'est pas meilleure (désolé pour mon anglais, je j'espère que vous me comprenez) Cela fait partie de mon code:

#pragma omp parallel shared(n) 
    { 
for(round=0; round<n; ++round) 
{ 
/* column step, I want to run this 4 G32 functions in parallel, but don't know, 
    that is proper approach to this problem */ 
     #pragma omp critical 
    G32(0, 4, 8,12, 0); 
     #pragma omp critical 
    G32(1, 5, 9,13, 1); 
     #pragma omp critical 
    G32(2, 6,10,14, 2); 
     #pragma omp critical 
    G32(3, 7,11,15, 3);  

/* diagonal step, and same here */ 
     #pragma omp critical 
    G32(0, 5,10,15, 4); 
     #pragma omp critical 
    G32(1, 6,11,12, 5); 
     #pragma omp critical 
    G32(2, 7, 8,13, 6); 
     #pragma omp critical 
    G32(3, 4, 9,14, 7); 
} 
} 

Et ceci est fonction G32:

#define G32(a,b,c,d,i)\ 
do { \ 
v[a] = ADD32(v[a],v[b])+XOR32(m[sigma[round][2*i]], c32[sigma[round][2*i+1]]);\ 
v[d] = ROT32(XOR32(v[d],v[a]),16);\ 
v[c] = ADD32(v[c],v[d]);\ 
v[b] = ROT32(XOR32(v[b],v[c]),12);\ 
v[a] = ADD32(v[a],v[b])+XOR32(m[sigma[round][2*i+1]], c32[sigma[round][2*i]]);\ 
v[d] = ROT32(XOR32(v[d],v[a]), 8);\ 
v[c] = ADD32(v[c],v[d]);\ 
v[b] = ROT32(XOR32(v[b],v[c]), 7);\ 
} while (0) 

Answer 1

Je pense que le genre de parallélisation qu'ils avaient à l'esprit exploitait instrctions SIMD dans les processeurs modernes. Le problème avec parallélisation style OMP dans ce cas est double:

• Les tâches G32 sont trop « petit » ou « court » de sorte que les frais généraux par rapport au démarrage des tâches dans différents threads et rejoindre est trop super en comparaison.
• Faux partage: Les emplacements de mémoire qui sont lus et modifiés dans les tâches sont trop rapprochés. Ils partagent probablement une ligne de cache. Ceci est mauvais car cela nécessite une synchronisation spéciale et rend très lent la lecture/écriture de différents threads.