S’il est toujours difficile d’optimiser un code existant, une méthodologie appropriée permet d’obtenir des résultats probants, durables et reproductibles. Le mois dernier, nous avons vu que la définition de bons jeux de tests était une base indispensable à la validation et à l’évaluation des résultats d’optimisation, puis nous nous sommes penchés sur la bonne utilisation des compilateurs pour optimiser et vectoriser le code. Dans cette seconde partie, regardons comment l’organisation des données impacte la performance…

Romain Dolbeau – HPC Fellow, CAPS Entreprise.

Nous l’avons déjà mentionné : un minimum de connaissance du matériel est essentiel pour réussir à utiliser au mieux les ressources de calcul. Avant même que Wulf and McKeen [1] n’inaugurent le terme “memory wall”, les accès mémoire étaient connu comme facteur limitant sur la performance pour beaucoup de codes. Les algorithmes aux limites de la bande passante (“bandwidth bound”) provoquent généralement des insomnies chez quiconque entreprend de les optimiser. Le facteur limitant dans ce cas n’est pas la rapidité d’exécution mais la rapidité d’accès aux données, du CPU jusqu’à la mémoire centrale. Comme nous allons le voir maintenant, il est pourtant possible de modifier les codes de ce type sans avoir pour autant à repenser totalement les algorithmes.
 

1 – Les structures de données

Le principal problème avec la bande passante mémoire est qu’elle peut être facilement surexploitée par des flux de données eux-mêmes sous-utilisés. Bien que ce ne soit pas nouveau (Truong et al. [2] par exemple ont déjà couvert ce problème), beaucoup de développeurs n’en sont pas conscients. Hennessy et Patterson [3], notamment, nous le rappellent : le mécanisme qui permet d’économiser des centaines de cycles CPU pour accéder à la mémoire principale est la mémoire cache. Petite, très rapide et proche des unités d’exécution, son existence est bien connue des développeurs. Son fonctionnement, en revanche, l’est moins. De sorte de beaucoup d’algorithmes, au lieu de l’utiliser à leur profit, inhibent son efficacité.

1.1 – Structures de tableaux ou tableaux de structures ? – Les caches ne mettent pas seulement en mémoire des unités élémentaires de données telles que des valeurs en simple ou double précision. Cette caractéristique aide avec la localité temporelle (lorsqu’une donnée va être réutilisée) mais pas avec la localité spatiale (lorsque les données utilisées sont voisines d’une autre précédemment calculée). C’est pour cette raison que la granularité des caches descend au niveau de la “ligne”, une zone de mémoire contiguë bien alignée (c’est-à-dire dont l’adresse du premier octet est un multiple de la taille de la ligne de cache).

Les lignes de cache font typiquement 32 ou 64 octets. Lorsqu’une donnée est accédée depuis la mémoire principale, la ligne entière est chargée dans le cache. Si une donnée voisine et présente dans le cache est ensuite requise alors l’accès est un cache hit, très rapide.

Bien que ce mécanisme soit bien enseigné dans les formations pour informaticiens, ses implications ne sont en revanche pas forcément bien saisies. Si l’on considère une ligne de cache de 64 octets, toutes les transactions mémoire vont concerner l’ensemble des 64 octets et non pas seulement quelques-uns, indépendamment des besoins du code. Concrètement, si seule une donnée double précision sur 8 octets est utilisée par ligne de cache, alors 87,5 % de la bande passante mémoire est gaspillée. Il est donc impératif de maximiser l’utilisation des octets des lignes de cache ou, pour le dire autrement, de faire en sorte qu’aussi peu d’octets que possible restent inutilisés.

Pourtant, la plupart des programmes utilisent des structures ou des objets qui vont à l’encontre de ce principe. Il y a bien sûr beaucoup d’avantages à utiliser les structures, mais ce n’est pas le sujet qui nous concerne ici. Nous allons plutôt nous attarder sur leurs inconvénients et voir notamment comment elles peuvent dans certains cas sous-utiliser la bande passante mémoire. Une structure contient beaucoup d’informations relatives à un concept logique abstrait tel qu’une particule dans une simulation d’écoulement de fluide, l’état d’un point dans un espace discrétisé, ou encore une voiture entière. Toutes les instantiations de structures sont stockées dans ce que l’on appelle des tableaux de structures. C’est ainsi que les données de toutes ces instanciations sont parcourues dans une boucle comme celle-ci :

foreach particle in charged_particles
  update_velocity(particle, electric_field)

La fonction update_velocity peut par exemple changer la vitesse d’une particule dans le champ électrique. Mais le problème est ici que, bien que la vitesse, définie sur quelques valeurs telles que la vélocité X,Y et Z, soit la seule donnée modifiée à cette étape du calcul, c’est l’ensemble de la structure avec toutes les autres données qu’elle contient qui est également chargé. Comme les structures sont contiguës en mémoire, toutes ces données sont finalement chargées dans la même ligne de cache. Si l’on considère que chaque particule est définie par 16 valeurs en double précision, soit 128 octets au total, alors une structure occupera deux lignes de cache à elle seule.

Maintenant, en imaginant que les trois valeurs de vélocité soient sur la même ligne de cache, alors à chaque mise à jour de ces valeurs, les opérations réalisées par le CPU sont :

1 – chargement d’une ligne de cache de 64 octets contenant les trois valeurs de vélocité (24 octets) ;
2 – calcul sur la vélocité et mise à jour dans le cache ;
3 – sauvegarde en mémoire de la ligne de cache.

Dans ce cas, c’est 62,5 % de la bande passante mémoire qui est utilisée pour stocker des octets inutiles. Si les valeurs de vélocité étaient réparties non pas sur une mais sur deux lignes de cache, alors l’utilisation de la bande passante serait doublée pour la même quantité de données. Le gaspillage serait alors de 81,25 %.

Une solution à ce problème est l’utilisation de structures de tableaux, qui consiste à allouer toutes les données élémentaires telles que la vélocité des particules dans un tableau puis de grouper ces tableaux dans des structures. Ainsi, plutôt que d’avoir des structures de particules, chacune avec ses vélocités, nous utilisons trois tableaux, un pour chaque vélocité X, Y et Z de toutes les particules. Au final, ce sont trois lignes de cache, une pour chaque valeur X, Y et Z, qui sont requises pour la fonction update_velocity au lieu d’une seule. Bien que cela ne paraisse pas optimal à première vue, l’utilisation du cache s’en voit grandement améliorée : le calcul sur la première particule va nécessiter un premier chargement dans le cache de 192 octets, c’est à dire 8 éléments de chacun des trois tableaux, mais les calculs sur les 7 particules suivantes n’utiliseront pas la bande passante mémoire puisque les vélocités auront déjà été chargées en cache. En moyenne, la bande passante requise aura été fortement réduite (à 24 octets par particule), grâce à la localité spatiale. Si la fonction de calcul n’était limitée que par la bande passante mémoire, alors le gain en performance serait d’un facteur 2,66, juste en réorganisant les données.

1.2 – Tableaux multidimensionnels vs tableaux de pointeurs – Penchons-nous maintenant sur un problème inconnu en Fortran, où les tableaux multidimensionnels sont la norme, mais propre à la famille des langages C avec lesquels la question revient fréquemment. Beaucoup de codes n’utilisent pas de tableaux multidimensionnels, préférant des tableaux de pointeurs qui apportent des chargements inutiles. Le listing 1 illustre cette forme d’écriture avec des données référencées via un pointeur de pointeur. Cette syntaxe semble a priori plutôt bonne avec ses deux paires de crochets pour accéder à un élément de tableau à deux dimensions, comme en Fortran. Mais la performance de ce code est en réalité loin d’être optimale puisque les accès sont effectués non pas en un chargement mais en deux chargements successifs. Il y a d’abord l’évaluation de A[i] qui représente un pointeur sur une valeur de type double, puis l’évaluation de ce dernier pointeur pour accéder à la donnée elle-même. Il s’agit en réalité d’un accès indirect.

Sans avoir à changer le corps de la fonction, une manière plus efficace de l’implémenter consiste tout simplement à déclarer le bon type de pointeur sur les données. Nous illustrons cette pratique au listing 2 où la dimension des tableaux est cette fois explicitement déclarée dans la liste des paramètres. Cette forme d’écriture est en apparence identique au double déréférencement évoqué précédemment, mais c’est une notation multidimensionnelle plus propre du langage C et qui permet de ne réaliser qu’un seul accès linéaire à la mémoire après avoir évalué i * n+j.

Avec cette forme d’écriture, l’allocation des données est également différente : plutôt que d’allouer d’abord le tableau de pointeurs puis tous les pointeurs sur les données à l’aide d’une boucle itérative, l’allocation de toutes les données est ici réalisée en une seule fois. C’est exactement la même allocation qui aurait été réalisée dans la version du listing 3 où les accès mémoire sont explicitement linéarisés. Mais cette écriture très laide est bien naturellement évitée par les programmeurs.
 

2 – Du côté des algorithmes

Selon qui l’utilise, le terme “algorithme” désigne différentes notions. Pour les ingénieurs informaticiens, il s’agit de techniques de programmation de base, très bien exposées par Aho et al. [4]. Pour d’autres scientifiques en lien avec le calcul intensif, le terme concerne plutôt l’analyse numérique telle qu’introduite par Atkinson [5]. Dans tous les cas, l’algorithmique vise à résoudre un problème avec le minimum de complexité, c’est à dire avec le minimum d’effort supplémentaire lorsqu’on augmente la taille du problème. La complexité est également une notion bien enseignée dans les formations en sciences et la littérature la traite de manière abondante (cf. par exemple Arora et al. [6]).

Il est difficile pour un informaticien de changer un algorithme de simulation par un autre qui serait meilleur tant les connaissances requises n’appartiennent pas seulement au domaine informatique mais aussi au domaine scientifique concerné. La stabilité numérique, les approximations, les conditions aux bords, etc., sont autant de considérations qui doivent être prises en compte en collaboration avec un spécialiste de la discipline. Et la plupart du temps, les contraintes sur l’algorithme numérique sont telles qu’il ne peut même pas être modifié.

En revanche, c’est sur l’implémentation qu’il y a moyen d’intervenir. Celle-ci est très souvent construite à partir d’autres algorithmes de base du domaine informatique tels que l’inversion ou la multiplication de matrices, la recherche d’une valeur maximum, les transformées de Fourier, etc. Or, ces briques de base sont tout à fait propices à des améliorations, substitutions ou à des optimisations bien connues.

Dans les efforts d’optimisation, une des tâches essentielles consiste à identifier ces algorithmes de base et à s’assurer que l’implémentation choisie est la meilleure pour le code sur lequel on travaille. Ce choix est en général assez facile puisque les constructeurs fournissent leurs propres bibliothèques contenant ces algorithmes. C’est le cas par exemple de la Math Kernel Library, incluse dans les versions récentes du compilateur Intel. Activable avec l’option -mkl, elle contient toutes les implémentation de BLAS, LAPACK [7], les transformées de Fourier compatibles avec FFTW3 [8], etc.

Cela étant posé, il est important de bien connaître le spectre d’efficacité de ces bibliothèques. En règle générale, elles ne sont pas adaptées aux problèmes de très petite taille car le coût de leur utilisation est alors supérieur au gain. Ainsi, les multiplications de grandes matrices devraient être réalisées par une fonction optimisée telle que dgemm, tandis que les multiplications de petites matrices de constantes telles que celles utilisées dans la rotation de l’espace euclidien (3×3) devraient être calculées par de petites fonctions écrites à la main et pouvant être agressivement inlinées.

De la même manière, alors que de larges FFT peuvent être laissées à FFTW3 ou son équivalent MKL, les petites FFT peuvent parfois être facilement implémentées par le générateur de codelets FFTW [9]. La spécialisation d’algorithmes à des données d’entrée constantes est une autre optimisation qui demande plus d’effort. Par exemple, si la matrice 3×3 dont nous venons de parler concerne une rotation dans un espace 3D, alors la présence de 0 et de 1 dans la matrice peut très bien être fixée dans la fonction de calcul afin que toutes les opérations inutiles puissent être supprimées.
 

3 – Les code parallèles

La parallélisation de code est un des problèmes les plus riches et en même temps les plus complexes de la programmation. Nous ne l’aborderons pas ici, la littérature regorgeant d’excellents ouvrages sur le sujet (cf. les références [10] [11] [12] [13]). En revanche, dans notre optique d’optimisation et de performance, attardons-nous sur les bonnes pratiques d’exécution de codes parallèles sur les machines contemporaines, pour éviter les écueils les plus fréquemment rencontrés.

3.1 – NUMA – Les systèmes récents x86_64 multisockets sont des systèmes NUMA (Non Uniform Memory Access) où la latence d’une instruction de chargement dépend de l’adresse de la donnée accédée. Les processeurs AMD Opteron et Intel Xeon, depuis la version 55xx de la famille Nehalem-EP, contiennent au minimum un contrôleur mémoire par socket, chaque socket étant connecté au travers un réseau dédié à cohérence de cache. Chez AMD, la technologie d’interconnexion s’appelle HyperTransport ; chez Intel, elle se nomme QPI (Quick Path Interconnect). Dès qu’un accès mémoire est réalisé sur un autre socket, la requête et la donnée doivent traverser le réseau, ce qui engendre des latences supplémentaires. De tels accès sont donc moins rapides qu’un accès local à la mémoire du même socket. C’est ce que montre la Fig. 1 avec les latences moyennes des accès mémoire selon la taille variable d’un tableau sur un système dual-socket Xeon X5680 Westmere-EP. Les trois premiers plateaux correspondent à des accès lorsque tout le tableau tient dans les trois niveaux de cache tandis que les plateaux supérieurs, pour des tailles de tableaux supérieures à 12 MiB, correspondent à des temps d’accès à la mémoire principale. Les quatre lignes représentent les configurations possibles entre calcul et mémoire : 0/0 et 1/1 sont des accès à la mémoire locale tandis que 1/0 et 0/1 sont des accès à la mémoire de l’autre socket. Au final, on remarque qu’entre 65 et 106 ns, l’augmentation de latence est de 63 % pour accès à la mémoire distante.

3.2 – NUMA sur Linux – Bien comprendre comment la mémoire est allouée (physiquement ou virtuellement) par l’OS, et s’assurer que les pages mémoires sont physiquement proches du CPU qui les utilise, permet de parer à ces problèmes de latence. Le concept de pagination est expliqué par Tanenbaum [14], entre autres. Sous Linux, les tailles de pages font 4 KiB ou 2 MiB. Cette dernière taille est la plus efficace pour le TLB (Translation Lookaside Buffer, cf. [3]) mais n’est pas encore totalement supportée. La taille de page représente donc la granularité de placement des données dans la mémoire physique disponible.

Sous Linux, toujours, ce placement est réalisé en indiquant le nœud NUMA sur lequel la page physique doit résider. Le comportement par défaut n’est cependant pas pleinement satisfaisant. Au moment de l’allocation mémoire, l’espace virtuel est réservé mais la page physique n’est pas réellement allouée. Lors de la première écriture dans la page, celle-ci est finalement allouée sur le nœud qui a initié l’écriture ou sur un autre nœud si la mémoire est pleine. Ce comportement est déterminant car si pour une raison ou une autre la mémoire est écrite par un seul thread, alors toutes les pages physiques résideront dans le nœud NUMA où le thread est exécuté. Bien sûr, en suivant les conseils de placement des threads détaillés dans la première partie de cet article, on peut bloquer (pin) le thread considéré sur le CPU. Ce faisant, tous les autres accès mémoire réalisés par ce même thread auront une latence minimale – ce qui correspond assez exactement au but recherché !

Autre conséquence de ce qui précède, dans un système dual-socket (deux nœuds NUMA), seule la moitié de la mémoire est utilisée par un processus monothread, sauf si celui-ci consomme beaucoup de mémoire. Autrement dit, seule la moitié de la bande passante mémoire est exploitée, le deuxième contrôleur sur l’autre socket n’étant alors pas utilisé. Si plus tard dans l’exécution le code devait devenir multithreads, par exemple par la présence de directives OpenMP, alors la moitié des threads utiliserait la mémoire distante de façon exclusive, ce qui dégraderait sensiblement la performance.

Selon la nature du programme parallèle, il existe tout de même quelques heuristiques qui permettent de limiter les effets dégradants de NUMA en fonction du nombre de processus et de threads :

– Processus unique, un seul thread : comme indiqué précédemment, par défaut, seul le nœud NUMA local est utilisé. L’avantage, c’est que la latence est optimale ; l’inconvénient, c’est que la bande passante mémoire est divisée par 2. Certains codes s’exécuteront mieux avec des pages mémoire entrelacées sur tous les nœuds. Pour ce faire, on peut préfixer la commande d’exécution de l’application avec numactl –interleave=all

ou utiliser numa_alloc_interleaved, la fonction d’allocation spécifique à NUMA, à la place de malloc.

– Plusieurs processus, un seul thread chacun : c’est la configuration typique des codes MPI non multithreadés. La répartition proposée par défaut sur Linux est excellente à condition d’avoir bloqué (pin) les processus sur leur CPU. Dans ce cas, tous les processus bénéficient de faibles latences mémoire et, mieux encore, la multitude de processus fait que tous les contrôleurs et toute la bande passante mémoire sont utilisés.

– Processus unique, plusieurs threads : c’est la configuration des codes OpenMP et leur fonctionnement par défaut est généralement mauvais. Souvent, l’allocation des pages physiques est réalisée sur le nœud maître alors que les segments parallèles sont exécutés sur les autres CPU. Que ce soit la lecture des données depuis un fichier, la réception des données par le réseau, la mise à zéro ou l’initialisation explicite et non parallèle de la mémoire allouée, tous ces événements amènent à une allocation sur un seul nœud. Forcer l’entrelacement peut aider car toute la bande passante mémoire est alors utilisée. Cela étant, on n’est pas dans l’optimal pour autant : les latences seront moyennes plutôt que petites. C’est tout de même une option à tenter compte tenu de sa facilité de mise en œuvre. Au final, la solution idéale consiste à placer chaque page sur le nœud exécutant les threads qui utilisent le plus la page en question mais la tâche est loin d’être simple !

– Plusieurs processus, plusieurs threads : si cette configuration semble la plus complexe à gérer, elle ne l’est pourtant pas vraiment. Les processus sont en général placés sur chaque socket et exécutent autant de threads qu’il y a de cœurs sur chacun d’entre eux. Ce placement par défaut est optimal car peu importe le thread qui alloue la mémoire, tous les threads d’un même processus auront de parfaites latences mémoire.

3.3 – Le faux partage – Le faux partage est un problème connu de longue date sur les machines multicœurs à cohérence de cache. Il est même décrit comme “sérieux” par Bolosky et Scott [15]. La plupart des processeurs modernes utilisent un protocole de cohérence basé sur l’invalidation (tous les détails dans Culler et al. [16]) alors que chaque écriture mémoire requiert que la ligne de cache correspondante soit dans le CPU avec un accès exclusif en écriture. De ce fait, aucun des autres caches ne dispose d’une copie valide.

Le “vrai partage” apparaît lorsqu’une donnée est utilisée simultanément par plus d’un processeur. Une synchronisation précise doit être réalisée pour assurer une exécution correcte. Mais chaque mise à jour demande l’invalidation de la ligne de cache des autres processeurs, ce qui engendre des pénalités de performance. Tous ces va-et-vient requis par le code sont très coûteux et ne peuvent malheureusement pas être supprimés, sauf à changer la nature de l’algorithme.

Le “faux partage” apparaît quant à lui lorsque deux données différentes sont utilisées par deux processeurs différents et sont présentes dans la même ligne de cache. Il n’y a alors pas besoin de synchronisation. Pourtant, simplement parce que l’invalidation touche l’intégralité d’une ligne de cache, chaque mise à jour par un processeur invalide la copie de tous les autres processeurs. Là encore, ces coûteux va-et-vient de lignes de cache affectent la performance tout en étant totalement inutiles : si les deux données résidaient dans différentes lignes de cache, il n’y aurait pas d’invalidation et la performance serait maximale.

Dans le cas des toutes petites structures telles que les compteurs par thread, le faux partage peut être un problème très important dans la mesure où chaque mise à jour engendre une invalidation inutile. Par exemple, si la structure du listing 4 ne contenait pas le remplissage (padding) intermédiaire avec le tableau pad, alors les deux éléments neg et pos partageraient la même ligne de cache. Si par ailleurs ils étaient utilisés par deux threads, la performance serait largement impactée. Ce padding permet ici de placer les éléments sur deux lignes de cache.

Un benchmark synthétique qui utiliserait cette structure et qui serait exécuté sur un système Xeon dual-socket avec deux threads sur deux sockets différents verrait son temps d’exécution augmenter de 50 % sans le recours au padding. L’utilisation de compteurs matériels montrerait au niveau de la modification d’état le remplacement d’un très grand nombre de lignes de cache – contre un nombre négligeable avec padding. NB : la cohérence de cache et la modification d’état sont très bien expliquées par Culler et al. [16].

Dans le cas de gros tableaux mis à jour en parallèle par plusieurs threads, la distribution des données entre threads est un facteur important. Avec une distribution round-robin où le thread n sur un nombre total de threads N met à jour les éléments d’indice m tel que n – – – m (mod N), alors un faux partage apparaît à chaque mise à jour, ce qui est très mauvais. En revanche, avec une distribution par bloc où chaque thread accède 1/N éléments dans un seul bloc continu, alors le faux partage n’apparaît que pour les lignes de cache sur les frontières de blocs. C’est au maximum une ligne de cache qui contiendra des données partagées entre deux threads. Cette fois, non seulement le nombre d’invalidations inutiles est faible au regard du nombre total d’accès, mais ces invalidations sont également masquées la plupart du temps : un thread réalise une mise à jour au début du calcul, l’autre à la fin, ce qui minimise les effets. Enfin, pour assurer des accès sans conflits, la taille des blocs gérés par chaque thread peut être arrondie à un entier multiple de la taille de la ligne de cache – au prix toutefois d’une répartition de charge entre threads légèrement moins efficace.
 
Conclusion

Nous voilà arrivés au terme de cet article dont l’objectif était de proposer un certain nombre de clés d’optimisation de code. Résumons notre propos par quelques recommandations concises. Avant tout, il faut pouvoir justifier de la validation du travail accompli sur trois critères : les choix techniques, la performance et la fiabilité. Il est par ailleurs nécessaire d’exploiter l’ensemble des outils d’analyse à disposition avant d’entreprendre des modifications sur le code. A ce stade, bien comprendre la relation entre structures de données et performance est un pré-requis indispensable. Dans tous les cas, exploiter les implémentations optimisées d’algorithmes (lorsqu’elles existent) est très recommandé, de même que l’adaptation fine de l’exécution des codes parallèles à la machine cible.

Nous espérons que le partage de ces bonnes pratiques aidera programmeurs et scientifiques à obtenir de leurs applications les meilleures performances avec le minimum d’efforts.

Bons développements !

[1] W. A. Wulf and S. A. McKee, Hitting the memory wall: implications of the obvious,  SIGARCH Comput. Archit. News, vol. 23, no. 1, pp. 20–24, Mar. 1995.

[2] D. Truong, F. Bodin, and A. Seznec, Improving cache behavior of dynamically allocated data structures, in Parallel Architectures and Compilation Techniques, 1998. Proceedings. 1998 International Conference on, 1998, pp. 322–329.

[3] J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach. San Mateo, CA: Morgan Kaufmann, 1990.

[4] A. V. Aho and J. E. Hopcroft, The Design and Analysis of Computer Algorithms, 1st ed. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1974.

[5] K. E. Atkinson, An Introduction to Numerical Analysis. New York: Wiley, 1978.

[6] S. Arora and B. Barak, Computational Complexity: A Modern Approach, 1st ed. New York, NY, USA: Cambridge University Press, 2009.

[7] E. Anderson, Z. Bai, J. Dongarra, A. Greenbaum, A. McKenney, J. Du Croz, S. Hammerling, J. Demmel, C. Bischof, and D. Sorensen, Lapack: a portable linear algebra library for high-performance computers, in Proceedings of the 1990 ACM/IEEE conference on Supercomputing, ser. Supercomputing ’90. Los Alamitos, CA, USA: IEEE Computer Society Press, 1990, pp. 2–11.

[8] M. Frigo and S. G. Johnson, The design and implementation of FFTW3, Proceedings of the IEEE, vol. 93, no. 2, pp. 216–231, 2005, special issue on “Program Generation, Optimization, and Platform Adaptation”.

[9] M. Frigo, A fast Fourier transform compiler, in Proc. 1999 ACM SIGPLAN Conf. on Programming Language Design and Implementation, vol. 34, no. 5. ACM, May 1999, pp. 169–180.

[10] M. Herlihy and N. Shavit, The Art of Multiprocessor Programming. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2008.

[11] T. Mattson, B. Sanders, and B. Massingill, Patterns for parallel programming, 1st ed. Addison-Wesley Professional, 2004.

[12] B. Chapman, G. Jost, and R. v. d. Pas, Using OpenMP: Portable Shared Memory Parallel Programming (Scientific and Engineering Computation). The MIT Press, 2007.

[13] W. Gropp, E. Lusk, and A. Skjellum, Using MPI (2nd ed.): portable parallel programming with the message-passing interface. Cambridge, MA, USA: MIT Press, 1999.

[14] A. S. Tanenbaum, Modern operating systems. Englewood Cliffs, N.J.: Prentice Hall, 1992.

[15] W. J. Bolosky and M. L. Scott, False sharing and its effect on shared memory performance, in USENIX Systems on USENIX Experiences with Distributed and Multiprocessor Systems – Volume 4, ser. Sedms’93. Berkeley, CA, USA: USENIX Association, 1993, pp. 3–3.

[16] D. E. Culler, A. Gupta, and J. P. Singh, Parallel Computer Architecture: A Hardware/Software Approach, 1st ed. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1997.