Réorganisation efficace de grands ensembles de données pour maximiser l'efficacité de la mémoire cache

Question

J'ai travaillé sur un problème qui, à mon avis, pourrait sembler intéressant aux yeux des gens (et peut-être que quelqu'un connaît une solution préexistante).

J'ai un grand ensemble de données composé d'une longue liste de paires de pointeurs sur des objets, comme ceci:

[
  (a8576, b3295), 
  (a7856, b2365), 
  (a3566, b5464),
  ...
]

Il y a beaucoup trop d'objets à conserver en mémoire à la fois (potentiellement des centaines de gigaoctets). Ils doivent donc être stockés sur le disque, mais peuvent être mis en cache en mémoire (probablement à l'aide d'un cache LRU).

Je dois parcourir cette liste en traitant chaque paire, ce qui nécessite que les deux objets de la paire soient chargés en mémoire (s'ils ne sont pas déjà mis en cache là-bas).

Alors, la question: existe-t-il un moyen de réorganiser les paires dans la liste afin de maximiser l'efficacité d'un cache en mémoire (en d'autres termes: minimiser le nombre d'erreurs dans le cache)?

Notes

1. Évidemment, l'algorithme de réorganisation devrait être aussi rapide que possible et ne devrait pas dépendre de la possibilité d'avoir toute la liste en mémoire en une fois (car nous n'avons pas assez de RAM pour cela) - mais il pourrait parcourir la liste plusieurs fois si nécessaire.

2. Si nous avions affaire à des objets individuels et non à des paires, la réponse simple serait alors de les trier. Cela ne fonctionnera évidemment pas dans cette situation car vous devez prendre en compte les deux éléments de la paire.

3. Le problème peut être lié à celui de la recherche d'un coupe de graphe minimale , mais même si les problèmes sont équivalents, je ne pense pas que les solutions pour min-cut se rencontrent

4. Mon hypothèse est que l'heuristique heurterait les données du disque et les réécrirait par morceaux dans un meilleur ordre. Il peut être nécessaire de parcourir plusieurs fois cette opération.

5. En fait, il ne s’agit peut-être pas uniquement de paires, mais de triplés, de quadruplés ou plus. J'espère qu'un algorithme qui fait cela pour les paires peut être facilement généralisé.

Answer 1

Votre problème est lié à un problème similaire concernant le matériel graphique:

Lors du rendu des sommets indexés dans un maillage triangulaire, le matériel dispose généralement d'un cache des derniers sommets transformés (~ 128 la dernière fois que je devais m'en préoccuper, mais soupçonnez que le nombre est plus grand ces jours-ci). Les vertices non mis en cache nécessitent une opération de transformation relativement coûteuse à calculer. " Optimisation du maillage " Restructurer les maillages triangulaires afin d'optimiser l'utilisation du cache était un sujet de recherche particulièrement brûlant. Googler   optimisation du cache de vertex (ou optimisation: ^) pourrait vous trouver du matériel intéressant en rapport avec votre problème. Comme d’autres affiches le suggèrent, j’imagine que pour y parvenir efficacement, il faudra exploiter toute cohérence inhérente dans vos données.

Une autre chose à garder à l'esprit: lorsqu'un cache LRU devient surchargé, il peut être intéressant de passer à une stratégie de remplacement MRU pour au moins conserver certains éléments en mémoire (au lieu de retourner l'intégralité du cache à chaque passage). Il me semble que John Carmack a écrit de bons documents sur ce sujet en rapport avec les stratégies de mise en cache de texture Direct3D.

Answer 2

Pour commencer, vous pouvez mmap la liste. Cela fonctionne s'il y a suffisamment d'espace d'adressage, pas de mémoire, par exemple. sur les processeurs 64 bits. Cela facilite l'accès aux éléments dans l'ordre.

Vous pouvez trier cette liste en fonction d'une distance minimale dans le cache, qui prend en compte les deux éléments, ce qui fonctionne bien si les objets se trouvent dans un espace contigu. La fonction de tri pourrait être quelque chose comme: comparez (a, b) à (c, d) = (a - c) + (b - d) (qui ressemble à une distance de Hamming). Ensuite, vous extrayez des tranches du magasin d’objets et procédez en fonction de la liste.

EDIT: correction d'une erreur de distance.

Answer 3

Même si vous n'êtes pas simplement en train de trier cette liste, le schéma général d'un le type de fusion multivoie peut être applicable - en d’autres termes, envisagez un type de décomposition (éventuellement récursive) de l’ensemble en ensembles plus petits pouvant être traités en mémoire séparément, puis une seconde phase où de petits morceaux des ensembles précédemment traités peuvent tous être combinés ensemble. Même en ne sachant pas la nature spécifique de ce que vous faites avec les paires, il est sûr de dire que de nombreux problèmes d’algorithmique sont beaucoup plus simples lorsque vous traitez avec des données triées (y compris des problèmes de graphes, ce qui pourrait être ce que vous avez sur votre les mains ici).

Answer 4

Je pense que la réponse à cette question dépendra beaucoup du modèle d’accès de la paire d’objets. Comme vous l'avez dit, il serait préférable de trier les pointeurs dans un cas simple et non jumelé. Dans un cas plus complexe, il peut toujours être judicieux de trier par l’une des moitiés de la paire si le motif est tel que la localité de ces valeurs est plus importante (si, par exemple, il s’agit de paires clé / valeur et beaucoup de recherches, la localité pour les clés est infiniment plus importante que pour les valeurs).

Donc, vraiment, ma réponse est qu'il est impossible de répondre à cette question dans un cas général.

Pour stocker votre structure, ce que vous souhaitez réellement est probablement un arbre B . . Celles-ci sont conçues pour ce dont vous parlez - garder une trace des grandes collections pour lesquelles vous ne voulez pas (ou ne pouvez pas) tout garder en mémoire.