Comment et quand s'aligner à la taille de la ligne de cache?

Dans Dmitry Vyukov excellent délimitée mpmc file d'attente écrit en C++ Voir: http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue

il ajoute quelques variables de rembourrage. Je présume que c'est pour s'aligner à une ligne de cache pour la performance.

j'ai quelques questions.

  1. Pourquoi fait-on cela de cette façon?
  2. est-ce une méthode portable qui sera toujours travailler
  3. dans quels cas serait-il préférable d'utiliser __attribute__ ((aligned (64))) à la place.
  4. pourquoi un rembourrage devant un pointeur de tampon aiderait-il à la performance? le pointeur n'est-il pas chargé dans la cache, donc il n'a que la taille d'un pointeur?

    static size_t const     cacheline_size = 64;
    typedef char            cacheline_pad_t [cacheline_size];
    
    cacheline_pad_t         pad0_;
    cell_t* const           buffer_;
    size_t const            buffer_mask_;
    cacheline_pad_t         pad1_;
    std::atomic<size_t>     enqueue_pos_;
    cacheline_pad_t         pad2_;
    std::atomic<size_t>     dequeue_pos_;
    cacheline_pad_t         pad3_;
    

ce concept fonctionnerait-il sous gcc pour le code c?

54
demandé sur JackyZhu 2011-12-12 06:50:08

2 réponses

C'est fait de cette façon pour que les différents noyaux modifiant des champs différents n'aient pas à faire rebondir la ligne de cache contenant les deux entre leurs caches. En général, pour qu'un processeur accède à certaines données en mémoire, toute la ligne de cache qui les Contient doit se trouver dans le cache local du processeur. S'il s'agit de modifier ces données, cette entrée cache doit généralement être la seule copie dans n'importe quel cache du système (Mode exclusif dans le style MESI / MOESI protocoles de cohérence de cache ). Lorsque des noyaux séparés tentent de modifier des données différentes qui vivent sur la même ligne de cache, et donc de perdre du temps à déplacer cette ligne entière d'avant en arrière, c'est ce qu'on appelle faux partage .

dans l'exemple particulier que vous donnez, un noyau peut demander une entrée (lecture (partagée) buffer_ et l'écriture (exclusive) seulement enqueue_pos_ ) tandis qu'une autre série (partagée buffer_ et exclusive dequeue_pos_ ) sans que l'un ou l'autre noyau ligne de cache appartenant à l'autre.

le rembourrage au début signifie que buffer_ et buffer_mask_ finissent sur la même ligne de cache, plutôt que de se diviser en deux lignes et donc d'avoir besoin du double du trafic mémoire pour accéder.

Je ne sais pas si la technique est entièrement portable. l'hypothèse est que chaque cacheline_pad_t sera lui-même aligné sur une limite de ligne de cache de 64 octets (sa taille), et donc ce qui suit sera sur la ligne de cache suivante. Pour autant que je sache, les normes de langage C et C++ n'exigent que des structures entières, de sorte qu'elles puissent vivre dans des tableaux correctement, sans violer les exigences d'alignement de leurs membres. (voir commentaires)

l'approche attribute serait plus spécifique au compilateur, mais pourrait réduire la taille de cette structure de moitié, puisque le remplissage serait limité à arrondir chaque élément à une ligne de cache complète. Cela pourrait être assez bénéfique si l'on avait beaucoup de ces.

le même concept s'applique en C comme en C++.

36
répondu Phil Miller 2014-02-18 22:59:56

vous devrez peut-être vous aligner à une limite de ligne de cache, qui est généralement de 64 octets par ligne de cache, lorsque vous travaillez avec des interruptions ou des lectures de données haute performance, et ils sont obligatoires à utiliser lorsque vous travaillez avec des sockets interprocess. Avec les sockets Interprocess, il y a des variables de contrôle qui ne peuvent pas être étalées sur plusieurs lignes de cache ou des mots de RAM DRD sinon cela va faire fonctionner la mémoire L1, L2, etc ou des caches ou DRD comme un filtre passe-bas et filtrer vos données d'interruption! CE QUI EST MAUVAIS!!! Cela signifie que vous obtenez des erreurs bizarres quand votre algorithme est bon et il a le potentiel de vous rendre fou!

la RAM de DDR va presque toujours lire en 128 bits (mots de RAM de DDR), qui est de 16 octets, de sorte que les variables de tampon de bague ne doivent pas être étalées sur plusieurs mots de RAM de DDR. certains systèmes utilisent des mots de RAM DDR 64-bit et techniquement vous pourriez obtenir un mot de RAM DDR 32-bit sur un CPU 16-bit mais on utiliserait SDRAM dans la situation.

on peut également être simplement intéressé à minimiser le nombre de lignes de cache en usage lors de la lecture de données dans un algorithme de haute performance. Dans mon cas, j'ai développé l'algorithme entier-chaîne le plus rapide au monde (40% plus rapide que l'algorithme précédent le plus rapide) et je travaille sur l'optimisation de L'algorithme Grisu, qui est l'algorithme flottant le plus rapide au monde. Pour imprimer le nombre de virgule flottante vous devez imprimer l'entier, donc pour optimiser L'optimisation Grisu un j'ai implémenté est que j'ai aligné les tables de recherche (LUT) de cache-line pour Grisu dans exactement 15 lignes de cache, ce qui est assez étrange qu'il soit aligné comme ça. Cela prend les LUTs de la .sev section (c'est à dire de la mémoire statique) et les place sur la pile (ou d'un segment, mais la Pile est plus approprié). Je n'ai pas établi de comparaison, mais il est bon d'en parler, et j'ai beaucoup appris à ce sujet, est la façon la plus rapide de charger des valeurs est de les charger à partir de l'I-cache et non du d-cache. La différence est que l'I-cache est en lecture seule et a des lignes de cache beaucoup plus grandes parce qu'il est en lecture seule (2KB était ce qu'un professeur m'a cité une fois.). Vous allez donc en fait dégrader vos performances à partir de l'indexation des tableaux au lieu de charger une variable comme celle-ci:

int faster_way = 12345678;

par opposition à la voie lente:

int variables[2] = { 12345678, 123456789};
int slower_way = variables[0];

la différence est que le int variable = 12345678 sera chargé à partir des lignes I-cache en compensant la variable dans l'I-cache dès le début de la fonction, tandis que slower_way = int[0] sera chargé à partir des plus petites lignes d-cache en utilisant une indexation de tableaux beaucoup plus lente. Ce particulier subtilement comme je viens de découvrir ralentit en fait mon algorithme et beaucoup d'autres entier-à-chaîne. Je dis cela parce que vous pouvez chose que vous optimisez par cache-alignement des données en lecture seule quand vous n'êtes pas.

typiquement en C++, vous utiliserez la fonction std::align . Je conseillerais de ne pas utiliser cette fonction parce que ce n'est pas garantie de fonctionnement optimal . Voici le moyen le plus rapide pour s'aligner sur une ligne de cache, qui pour être à l'avant je suis l'auteur et c'est un plug sans vergogne:

Kabuki Toolkit Alignement De La Mémoire De L'Algorithme De

namespace _ {
/* Aligns the given pointer to a power of two boundaries with a premade mask.
@return An aligned pointer of typename T.
@brief Algorithm is a 2's compliment trick that works by masking off
the desired number of bits in 2's compliment and adding them to the
pointer.
@param pointer The pointer to align.
@param mask The mask for the Least Significant bits to align. */
template <typename T = char>
inline T* AlignUp(void* pointer, intptr_t mask) {
  intptr_t value = reinterpret_cast<intptr_t>(pointer);
  value += (-value ) & mask;
  return reinterpret_cast<T*>(value);
}
} //< namespace _

// Example calls using the faster mask technique.

enum { kSize = 256 };
char buffer[kSize + 64];

char* aligned_to_64_byte_cache_line = AlignUp<> (buffer, 63);

char16_t* aligned_to_64_byte_cache_line2 = AlignUp<char16_t> (buffer, 63);

et voici la plus rapide std:: remplacement d'alignement:

inline void* align_kabuki(size_t align, size_t size, void*& ptr,
                          size_t& space) noexcept {
  // Begin Kabuki Toolkit Implementation
  intptr_t int_ptr = reinterpret_cast<intptr_t>(ptr),
           offset = (-int_ptr) & (align - 1);
  if ((space -= offset) < size) {
    space += offset;
    return nullptr;
  }
  return reinterpret_cast<void*>(int_ptr + offset);
  // End Kabuki Toolkit Implementation
}
0
répondu 2018-08-22 17:28:44