Apprentissage Automatique et Réseaux Neuronaux - page 30

MetaQuotes 2023.05.03 17:00 #291

Cours 7. Races et parallélisme

La vidéo couvre une gamme de sujets liés aux races, au parallélisme et aux dags de calcul dans la programmation Silk. Certains concepts clés couverts incluent les instructions spawn et sync pour une exécution simultanée, l'importance d'éviter les conditions de concurrence et l'utilisation du détecteur de course de Silk pour les identifier. La vidéo couvre également la loi d'Amdahl, la loi de travail et la loi d'étendue comme moyens de quantifier la quantité de parallélisme dans un programme, ainsi que des moyens d'analyser le travail et l'étendue des calculs. L'accélération et le parallélisme potentiels des algorithmes de tri parallèle et le concept de la théorie de l'ordonnancement sont également discutés, en mettant l'accent sur le théorème de l'ordonnanceur glouton. Dans l'ensemble, la vidéo fournit des informations précieuses sur la compréhension et l'optimisation des performances du programme dans la programmation Silk.

La vidéo explique les corollaires de la limite de l'ordonnanceur gourmand, qui stipule essentiellement que tout ordonnanceur gourmand atteint une accélération linéaire presque parfaite tant que T1/Tinfinity est supérieur ou égal à P^2. Le planificateur de soie, qui utilise un planificateur de vol de travail, peut atteindre une accélération linéaire presque parfaite tant que le nombre de processeurs est bien inférieur à T1/Tinfinity. Le système d'exécution de la soie fonctionne en maintenant un pont de travail de brins prêts et manipule le bas du pont comme une pile. La vidéo traite également de Cactus Stack, qui permet plusieurs vues de piles en parallèle et rend possible les appels de fonctions parallèles. La limite supérieure de l'espace de pile requis par l'exécution du processeur P est souvent beaucoup plus lâche que la quantité réelle nécessaire, car chaque processeur n'a peut-être pas besoin de parcourir tout le graphe de calcul à chaque fois qu'il vole du travail.

00:00:00 Dans cette section, l'instructeur présente le sujet des courses et du parallélisme dans Silk, qui sera important pour le devoir et le projet à venir. Les bases des instructions spawn et sync de Silk sont passées en revue, ce qui permet l'exécution simultanée des fonctions parent et enfant. L'instructeur souligne également l'importance de rencontrer les membres de la politique du MIT et d'éviter les conditions de concurrence dans le code, ce qui peut entraîner des conséquences désastreuses, comme le montrent les exemples passés. Les bugs de course les plus difficiles à trouver sont ceux qui ont provoqué des événements catastrophiques, et les tests conventionnels ne sont souvent pas efficaces. Silk offre un outil pour aider à identifier les bugs de course potentiels dans le code.
00:05:00 Dans cette section, la vidéo explique comment les courses sont l'un des bogues les plus difficiles à trouver pour les développeurs, car elles ne peuvent se produire que dans de rares cas lorsque des codes logiquement parallèles accèdent au même emplacement mémoire et qu'au moins un enregistre une écriture. à elle. À titre d'exemple, la vidéo montre un code simple qui utilise un graphique de dépendance pour montrer comment le bug de course partagé entre deux chemins parallèles ne se produit pas toujours. La course se produit lorsque les deux magasins écrivent dans le même emplacement mémoire, ce qui peut entraîner des sorties différentes selon le chemin d'exécution qui s'exécute entièrement en premier.
00:10:00 Dans cette section, l'orateur explique le concept de courses de détermination, qui se produisent lorsque deux instructions accèdent au même emplacement mémoire et qu'au moins une des instructions est une opération d'écriture, entraînant un comportement non déterministe dans le programme. L'orateur donne des conseils sur la façon d'éviter les courses, par exemple en s'assurant que les itérations d'une boucle for Silk sont indépendantes et en s'assurant que le code entre une instruction d'apparition Silk et l'instruction de synchronisation Silk correspondante est également indépendant. L'orateur note également que la taille du mot machine est importante et qu'il convient d'être prudent lors de la lecture et de l'écriture dans des structures de données compressées qui utilisent des types non standard.
00:15:00 Dans cette section, la vidéo traite du "détecteur de course" de la plate-forme Silk, qui peut aider à identifier les conditions de course potentielles dans un programme. En utilisant l'indicateur "-f aseptisé égal à soie" pour générer un programme instrumenté, Silk peut signaler et localiser les races incriminées, ce qui aide à déboguer le code. La vidéo explique également le concept de parallélisme et comment le modèle d'exécution Silk utilise des graphes de calcul pour illustrer le déroulement du calcul pendant l'exécution. Ces concepts sont importants à comprendre lorsque vous essayez d'optimiser et d'améliorer les performances du programme.
00:20:00 types de sommets dans le dag de calcul : le brin initial, les brins de continuation, les brins d'appel de fonction et les brins finaux. Le brin initial contient la première instruction à exécuter et le brin final contient la dernière instruction exécutée dans le programme. Les brins de continuation représentent la continuation d'une opération d'apparition, tandis que les brins d'appel de fonction représentent l'exécution d'un appel de fonction. Il est important de noter que le dag de calcul se déroule dynamiquement pendant l'exécution et est insensible au processeur, ce qui signifie que le système d'exécution détermine comment mapper les tâches aux processeurs au moment de l'exécution. En résumé, le calcul dag est un outil puissant pour comprendre le parallélisme et la concurrence d'un programme.
00:25:00 Dans cette section, nous en apprenons davantage sur les dags de calcul et comment ils peuvent être utilisés pour analyser le parallélisme dans un programme. Le dag de calcul représente les dépendances entre les différentes parties du programme et a différents types d'arêtes, y compris les arêtes d'apparition, les arêtes d'appel, les arêtes de retour et les arêtes de continuation. Il est possible d'utiliser des dags de calcul pour analyser le degré de parallélisme dans un programme, et nous utilisons la loi d'Amdahl pour quantifier le degré de parallélisme. Dans l'exemple fourni, moins de sept nœuds doivent être exécutés séquentiellement, ce qui indique qu'il existe un certain degré de parallélisme dans le calcul.
00:30:00 Dans cette section, le concept de la loi d'Amdahl est présenté comme un moyen de déterminer l'accélération maximale possible dans le traitement parallèle. Il est déterminé que la fraction série du programme est de 3/18, ce qui donne une accélération maximale de 6. Alors que la loi d'Amdahl fournit une limite supérieure sur le parallélisme, elle est souvent trop lâche dans les cas pratiques. La loi de travail et la loi d'envergure sont introduites comme définitions alternatives du parallélisme, la loi de travail indiquant que le temps d'exécution sur P processeurs est supérieur ou égal au travail du programme divisé par P, et la loi d'envergure indiquant que le temps d'exécution sur P processeurs est au moins le temps d'exécution sur un nombre infini de processeurs. Ces lois fournissent de meilleures limites supérieures sur l'accélération maximale que la loi d'Amdahl dans de nombreux cas.
00:35:00 Dans cette section, l'orateur explique comment composer le travail et couvrir les quantités de différents calculs. Ils expliquent que lors de l'exécution de deux calculs parallèles, le travail est toujours la somme du travail des calculs individuels, et la durée est le maximum de la durée des calculs individuels. L'orateur définit également l'accélération sur les processeurs P et discute de l'accélération sous-linéaire, linéaire et superlinéaire. Ils notent que l'accélération maximale possible est égale au parallélisme du calcul, qui est égal à la quantité moyenne de travail par étape le long du calcul. Dans l'ensemble, cette section donne un aperçu de la composition des calculs et de la façon de mesurer leur parallélisme.
00:40:00 Dans cette section, l'orateur explique comment analyser le travail et la durée des calculs pour calculer le parallélisme maximal, en utilisant des exemples tels qu'un DAG de calcul et un algorithme de tri rapide parallèle. L'orateur présente l'analyseur d'évolutivité Silk Scale, qui utilise l'instrumentation du compilateur pour analyser l'exécution en série d'un programme et dériver des limites supérieures sur l'accélération parallèle du programme. L'orateur mentionne également que l'analyse manuelle du parallélisme de grands calculs peut être fastidieuse, mais Silk Scale peut y contribuer.
00:45:00 Dans cette section, la vidéo traite des résultats de l'exécution d'un calcul parallèle et de la génération d'un tracé qui montre l'accélération observée, ainsi que les limites des lois d'envergure et de travail. Le graphique montre que l'accélération maximale est d'environ 5, ce qui indique que le parallélisme dans le programme est faible. L'analyse révèle que le goulot d'étranglement du parallélisme est l'exécution séquentielle de la fonction de partition, et que le travail et l'étendue attendus de la version parallèle de quicksort sont de l'ordre de n log n. Le parallélisme maximal pouvant être atteint est de l'ordre de log log n, ce qui n'est pas très élevé. Pour augmenter le parallélisme, la fonction de partition doit être parallélisée.
00:50:00 Dans cette section, l'orateur discute de l'importance de la mise en œuvre du parallélisme dans les algorithmes de partition et de tri par fusion afin de voir une accélération significative. Les versions parallèles de ces algorithmes ont une portée globale liée à log au carré n et un parallélisme élevé de n sur log n. De plus, il existe de nombreux autres algorithmes parallèles pratiques qui ont un parallélisme élevé et une limite de travail asymptotiquement égale à celle de l'algorithme séquentiel correspondant. L'orateur introduit également le concept de théorie de l'ordonnancement, expliquant qu'un ordonnanceur centralisé peut mapper des DAG de calcul sur des processeurs disponibles au moment de l'exécution, tandis qu'un ordonnanceur distribué est utilisé dans la programmation Silk. Un ordonnanceur gourmand, qui fait le maximum à chaque étape du calcul, est utilisé comme exemple.
00:55:00 Dans cette section, le concept d'un ordonnanceur gourmand est introduit, qui effectue autant de travail que possible dans le pas de temps actuel sans penser au futur. Une étape complète, où au moins les brins P sont prêts, et une étape incomplète, où moins de brins P sont prêts, sont définies. Le célèbre théorème, montré pour la première fois par Ron Graham en 1968, stipule que la limite de temps atteinte par un ordonnanceur glouton est inférieure ou égale à T1/P + T infini, T1 étant le travail et T infini étant la durée. La preuve de ce théorème est fournie, et il est montré que tout ordonnanceur glouton réalise dans un facteur de deux le temps d'exécution optimal.
01:00:00 Dans cette section, la vidéo explique les corollaires de l'ordonnanceur glouton lié, qui atteint dans un facteur de deux l'ordonnanceur optimal. Le corollaire indique que tout ordonnanceur gourmand atteint une accélération linéaire presque parfaite lorsque T1/Tinfinity est supérieur ou égal à P^2, où T1/P fois Tinfinity mesure la quantité de parallélisme dans le calcul par rapport au nombre de processeurs disponible. Le planificateur de soie utilise un planificateur de vol de travail, qui a un temps d'exécution prévu de TP égal à T1/P plus l'ordre T infini, avec un Big O devant le T infini pour tenir compte des frais généraux de planification, et peut atteindre près de - accélération linéaire parfaite tant que le nombre de processeurs est bien inférieur à T1/Tinfinity. Le système d'exécution de la soie fonctionne en maintenant un pont de travail de brins prêts et manipule le bas du pont comme une pile. L'instrumentation de l'échelle de soie permet de mesurer les termes de travail et d'envergure pour déterminer le parallélisme dans le programme.
01:05:00 Dans cette section, l'orateur discute du concept de frai et de parallélisme dans les processeurs. Ils expliquent que lorsqu'un processeur appelle une fonction, il place le cadre de cette fonction au bas de sa pile et peut générer des cadres au bas de la pile. Plusieurs processus peuvent se produire en parallèle et des retours peuvent être effectués à partir de spawns et d'appels. Lorsque les travailleurs manquent de travail à faire, ils volent du haut du pont d'un autre processeur. Le célèbre théorème stipule que les travailleurs volent très rarement, ce qui donne une accélération quasi linéaire. L'orateur note également que Silk prend en charge les règles de C pour les pointeurs, où un pointeur vers un espace de pile peut être passé d'un parent à un enfant, mais pas d'un enfant à un parent.
01:10:00 Dans cette section de la vidéo, l'orateur discute de la pile Cactus, qui est la pile qui peut être vue par une tâche dans le graphe de calcul des ancêtres d'un programme Silk. Cette pile permet plusieurs vues de piles en parallèle, ce qui rend possible les appels de fonctions parallèles. L'orateur explique que l'espace de pile requis par un programme Silk peut être trouvé en prenant l'espace de pile requis par une exécution en série du programme (S sub 1) et en le multipliant par le nombre de processeurs (P) qui seront utilisés (S sous P ≤ P x S sous 1). L'orateur fournit une preuve de haut niveau de ce concept et note que la limite supérieure de l'espace de pile requis par l'exécution du processeur P est souvent beaucoup plus lâche que la quantité réelle nécessaire puisque chaque processeur peut ne pas avoir besoin d'aller jusqu'au bout du graphe de calcul chaque le temps qu'il vole du travail.

OpenCL dans le Trading Tutoriels de programmation Trading Quantitatif

MetaQuotes 2023.05.03 17:01 #292

Cours 8. Analyse des algorithmes multithreads

Cours 8. Analyse des algorithmes multithreads

Cette vidéo présente la méthode principale d'analyse des récurrences de diviser pour mieux régner et l'applique aux algorithmes multithreads en comparant la base logarithmique B de n à la base logarithmique B de A avec F de N pour déterminer leur croissance en n et le travail requis. La vidéo présente une feuille de triche avec des solutions pour les algorithmes multithreads de base et couvre des sujets tels que l'analyse du travail et de la durée, l'efficacité du travail et la maîtrise des frais généraux grâce à l'optimisation de la taille du grain. L'importance de l'empathie lors de la communication de sujets techniques est soulignée, et le concept d'un DAG est introduit comme moyen d'équilibrer le travail et la portée pour augmenter le parallélisme et réduire le temps d'exécution.

La vidéo traite également de l'analyse des algorithmes multithreads, en se concentrant sur le travail et l'étendue, et sur la façon de maximiser le parallélisme tout en minimisant l'étendue pour obtenir une accélération linéaire presque parfaite. L'orateur suggère une approche diviser pour mieux régner pour les algorithmes multithreads, où le nombre de tâches attribuées aux threads est suffisamment important, et met en garde contre la génération de nombreuses petites tâches en raison des frais généraux de planification. L'exemple de code présenté en comprend un efficace et un moche. L'orateur explique également comment représenter les sous-matrices dans le codage et l'indexation bidimensionnels et met l'accent sur l'utilisation de « restreindre » dans le code de multiplication matricielle diviser pour régner pour améliorer les performances.

00:00:00 Dans cette section, l'instructeur commence par rappeler aux étudiants les récurrences diviser pour mieux régner et la méthode générale pour les résoudre appelée méthode maître. La méthode traite des récurrences et de leur forme T(n) = a*T(n/B) + F(n), où a est une constante, B est le facteur de division et F(n) est la quantité totale de travail découper le problème en sous-problèmes de taille n/B. On rappelle aux élèves l'arbre de récurrence et comment chaque niveau se divise en sous-problèmes de taille n/B, ils ajoutent le temps d'exécution sur les lignes, calculent la hauteur de l'arbre et le multiplient par le nombre de sous-problèmes à chaque niveau (a ^k). Enfin, les élèves calculent que n^log base B de A est le temps d'exécution total de l'algorithme.
00:05:00 Dans cette section, l'orateur explique comment déterminer la croissance de n et le travail requis lors de l'évaluation d'algorithmes multithreads. La clé est de comparer le log base B de n au log base B de A avec F de N. Le locuteur couvre trois cas possibles, le premier étant lorsque le log base B n est beaucoup plus grand que F de n. Dans ce cas, la fraction constante du poids se trouve dans les feuilles, ce qui donne la réponse n au logarithme de base B de A. Le deuxième cas est lorsque le logarithme de base B n est approximativement égal à F de n. Pour cela, vous ajoutez un log supplémentaire, et la réponse est n au log base B d'un log au k plus 1 de n. Enfin, le troisième cas est celui où une base logarithmique B est bien inférieure à F de N, ce qui signifie que F doit satisfaire une condition de régularité, qui est satisfaite par toutes les fonctions qu'ils examineront comme les polynômes et les logarithmes.
00:10:00 Dans cette section, l'orateur présente une feuille de triche avec des solutions d'algorithmes multithreads de base couramment utilisées en informatique. Le premier algorithme, T(n) = T(n/2) + n, a une solution de Θ(n^2) car il relève du premier cas. Le deuxième algorithme, T(n) = T(n/2) + n^2logn, a une solution de Θ(n^2logn) car il relève du deuxième cas avec k = 0. Pour le troisième algorithme, T(n) = T(n/2) + n^2, la solution est Θ(n^2) car elle relève du premier cas. Le quatrième algorithme, T(n) = 2T(n/2) - n, est délicat car il ne relève d'aucun des cas de la méthode maîtresse et a une solution de Θ(n^2loglogn).
00:15:00 Dans cette section, l'orateur discute de la méthode Aqua Bazi et comment elle est plus compliquée que la méthode principale, qui est suffisante pour analyser la plupart des programmes. Ils fournissent ensuite un exemple de boucle parallèle avec un code de transposition matricielle en place où la boucle externe est parallélisée. L'intervenant insiste sur l'importance de définir correctement l'espace d'itération et l'équilibrage de charge pour un traitement parallèle efficace. Ils expliquent également comment les boucles sont implémentées par le compilateur Silk ouvert et le système d'exécution.
00:20:00 Dans cette section, l'orateur décrit un programme récursif pour une boucle qui utilise diviser pour régner pour diviser la boucle en deux parties et s'appeler récursivement de chaque côté jusqu'à ce qu'il atteigne une itération à un élément. Le travail de ce calcul est analysé en termes de travail et d'étendue, le travail des feuilles étant d'ordre n au carré et la partie supérieure étant thêta n car chaque niveau des feuilles à la racine n'a que n nœuds. Le système d'exécution de soie ouvert n'a pas de primitive de boucle, de sorte que les boucles sont effectivement traduites dans cette approche de division pour régner en parallèle.
00:25:00 Dans cette section, l'orateur discute du travail et de l'analyse de portée d'un algorithme multithread. Il explique que le travail total est Θ(n²) car un travail constant est effectué pour chacune des n feuilles de l'arbre binaire complet. L'étendue du contrôle de la boucle est log(n), ce qui signifie qu'un nombre infini de processeurs pourraient terminer la tâche en temps logarithmique. Cependant, comme il y a une composante linéaire dans le calcul (n), l'étendue totale est Θ(n). Par conséquent, le parallélisme est Θ(n), ce qui est une bonne quantité pour la plupart des systèmes pratiques. L'orateur explore ensuite le scénario dans lequel la boucle interne est également parallélisée et discute de la quantité de travail qui en résulte.
00:30:00 Dans cette section de la vidéo, le professeur aborde le concept d'efficacité du travail dans les algorithmes parallèles. La parallélisation des algorithmes ne change pas le travail, mais elle devrait, espérons-le, réduire la durée du calcul afin d'obtenir un grand parallélisme. Cependant, la parallélisation peut parfois entraîner l'ajout de plus de travail, ce qui peut être problématique car cela ralentit le programme par rapport à l'algorithme d'origine. Les algorithmes parallèles efficaces au travail sont ce que le professeur souhaite enseigner, car ils sont capables de réduire la portée pour obtenir un grand parallélisme sans ajouter plus de travail. Le professeur insiste sur l'importance de poser des questions et de faire des erreurs dans le processus d'apprentissage, car cela peut aider d'autres personnes qui peuvent avoir les mêmes questions mais qui ont peur de poser. Il encourage les étudiants à participer et à s'engager dans le processus d'apprentissage, même s'ils ne font pas partie des 10 % les plus performants.
00:35:00 Dans cette section, l'importance de l'empathie dans la communication lorsqu'il s'agit de sujets techniques est soulignée. Le professeur encourage les étudiants à être patients avec les autres membres de la classe qui ne connaissent peut-être pas le sujet traité. Passant à l'analyse des algorithmes multithreads, un algorithme de division pour régner pour l'addition de vecteurs est présenté, et le parallélisme s'avère être n sur log n. La relation entre le parallélisme et le nombre de processeurs est discutée, le professeur soulignant que si plus de parallélisme peut sembler préférable, il n'est bénéfique que jusqu'à un certain seuil.
00:40:00 Dans cette section, l'orateur discute de l'optimisation d'une partie de la surcharge dans un algorithme multithread, en particulier la surcharge d'appel de sous-programme. Ils introduisent le concept de "taille de grain", qui suggère au compilateur qu'il y ait jusqu'à G éléments par morceau aux feuilles du processus de division pour régner. Cela permet d'amortir la surcharge du sous-programme sur G itérations plutôt qu'une seule, ce qui se traduit par de meilleures performances. Si la taille de grain n'est pas spécifiée, le système fait sa meilleure estimation pour minimiser les frais généraux. L'orateur décompose les variables I, G et s pour analyser le travail dans ce contexte et le compare au travail dans le code d'origine sans le contrôle parallèle.
00:45:00 Dans cette section, l'orateur parle de l'analyse des algorithmes multithreads et de la façon dont le contrôle de boucle est bon marché sur un processeur moderne en panne. Ils examinent la durée, qui est le temps nécessaire pour exécuter l'algorithme avec un nombre infini de processeurs, et discutent des frais généraux par rapport au coût des itérations. L'orateur décompose la durée en termes de nombre de feuilles et d'opérations colorées, appelées « s », qui doivent être effectuées sur chacune d'elles. Ils répondent également aux questions sur le nombre de nœuds internes dans un arbre binaire complet et les chemins empruntés pour calculer l'étendue.
00:50:00 Dans cette section, l'orateur discute de l'analyse des algorithmes multithreads, en particulier du concept de DAG (graphe acyclique dirigé) et de la manière dont il affecte le chemin de l'algorithme. Ils soulignent le besoin d'indépendance entre les différents sous-arbres du DAG afin de permettre un traitement parallèle. L'objectif est d'équilibrer le travail et l'étendue de l'algorithme, car ces deux facteurs fonctionnent dans des directions opposées. La clé est d'avoir G (la quantité de parallélisme) bien supérieure à s sur I (la partie séquentielle de l'algorithme), ce qui permet une surcharge plus faible et un traitement plus rapide. L'orateur mentionne également une mise en œuvre de ce concept, mais note qu'il sera discuté plus tard dans la série de conférences.
00:55:00 Dans cette section, l'orateur présente une implémentation d'algorithmes multithread utilisant une boucle for pour ajouter deux vecteurs. La boucle utilise un opérateur appelé V add pour effectuer l'addition de vecteurs en série, et la boucle génère des ajouts dans des groupes de G en utilisant un vecteur de taille G. En supposant que G est égal à un, le travail des boucles est d'ordre n et la durée est également commande nf. Le parallélisme est mesuré en prenant le rapport du travail à l'étendue, qui est n divisé par n, ce qui se simplifie à 1. L'orateur souligne que le but de l'analyse des algorithmes multithreading est d'augmenter le parallélisme et de diminuer l'étendue pour minimiser le temps d'exécution, et met en évidence la technique appelé strip mining, où une boucle de longueur N est remplacée par une double boucle imbriquée pour paralléliser les calculs, comme un moyen d'améliorer les algorithmes multithreads.
01:00:00 Dans cette section, le conférencier analyse les performances des algorithmes multithreads en termes de travail et d'envergure. Ils discutent de la manière de minimiser l'étendue pour maximiser le parallélisme, car l'étendue est dans le dénominateur. La clé est de générer dix fois plus de parallélisme que les processeurs si l'on veut une accélération linéaire presque parfaite. L'orateur suggère également d'échanger un certain parallélisme pour réduire les frais généraux de travail si nécessaire. Ils encouragent à jouer avec la taille des grains pour ce faire, tant qu'un parallélisme suffisant est conservé.
01:05:00 Dans cette section, l'orateur discute de l'utilisation des stratégies de division pour régner dans les algorithmes multithreads, déconseillant de générer de nombreuses petites tâches les unes après les autres, à moins qu'elles ne soient regroupées en quelques tâches, auquel cas la surcharge c'est bien. Généralement, il devrait y avoir une approche diviser pour mieux régner, où le nombre de tâches confiées aux threads est suffisamment important. L'orateur avertit de faire attention aux frais généraux de planification et suggère de paralléliser la boucle externe au lieu des boucles internes, qui ont plus de frais généraux. Les exemples de codes présentés ici en montrent un efficace, où l'ordonnancement ne se produit qu'une seule fois, et un mauvais, où la surcharge se produit n fois. La multiplication matricielle est utilisée comme exemple d'algorithme multithread utilisant une stratégie de division pour régner pour multiplier n par n matrices en effectuant 8 multiplications de n sur 2 par n sur 2 matrices, puis en ajoutant deux matrices n par n.
01:10:00 Dans cette section, l'orateur explique comment représenter les sous-matrices dans le codage et l'indexation bidimensionnels, en particulier dans l'ordre des lignes principales et des colonnes principales pour des langages comme C et Fortran. L'idée est que chaque matrice bidimensionnelle peut être indexée comme une matrice unidimensionnelle, et lorsqu'il s'agit de sous-matrices, il faut ajouter le nombre de lignes et la longueur de la longue matrice pour savoir où se trouve l'élément IJ. De plus, lors de la mise en œuvre de diviser pour mieux régner, connaître les coins de départ de chacune des quatre sous-matrices est crucial. En fin de compte, l'orateur met l'accent sur l'utilisation de «restrict» dans le code de multiplication matricielle diviser pour régner pour indiquer au compilateur quels éléments peuvent ou ne peuvent pas être aliasés.
01:15:00 Dans cette section, l'orateur discute d'un algorithme multithread pour la multiplication matricielle. L'algorithme est basé sur une subdivision récursive des matrices en sous-matrices plus petites, chaque sous-matrice étant multipliée de manière récursive pour obtenir le résultat final. L'orateur met en avant une petite astuce pour déterminer rapidement si n est une puissance de deux, et utilise une macro pour simplifier l'indexation des matrices. L'algorithme présente un parallélisme élevé, qui peut être réduit pour améliorer les performances. D'autres algorithmes similaires sont également mentionnés.

Tutoriels de programmation OpenCL dans le Trading Trading Quantitatif

MetaQuotes 2023.05.03 17:02 #293

Cours 9. Ce que les compilateurs peuvent et ne peuvent pas faire

Cours 9. Ce que les compilateurs peuvent et ne peuvent pas faire

Cette vidéo explique comment les compilateurs peuvent optimiser le code, à l'aide de divers exemples. Il explique comment les compilateurs peuvent éliminer les références de stockage et de mémoire inutiles, et comment ils peuvent optimiser les boucles pour améliorer les performances.

Cette vidéo explique également le concept des passes d'optimisation du compilateur et comment elles peuvent être utilisées pour améliorer les performances du code. Il aborde également les limites des compilateurs, notamment en ce qui concerne la vectorisation. Les compilateurs ne peuvent vectoriser le code que s'ils peuvent déterminer que les pointeurs dans le code ne seront pas des alias. Si les pointeurs font des alias, le compilateur ne pourra pas vectoriser le code. En tant que programmeur, vous pouvez aider le compilateur en annotant vos pointeurs pour fournir plus d'informations sur leur utilisation.

00:00:00 Dans cette conférence, Tao Schardl explique ce que les compilateurs peuvent et ne peuvent pas faire. Il explique que l'étude des optimisations du compilateur peut aider les développeurs à comprendre comment écrire du code qui tire parti des optimisations et comment éviter d'optimiser manuellement le code que le compilateur peut déjà optimiser.
00:05:00 Le compilateur est un gros logiciel et il peut absolument aider au débogage lorsque le compilateur lui-même a des bogues. Cela aide à comprendre où le compilateur a pu faire une erreur ou où le compilateur n'a tout simplement pas fait ce que vous pensiez qu'il devrait être capable de faire.
00:10:00 Le compilateur peut faire beaucoup d'optimisations, mais il y a certaines choses qu'il ne peut pas faire. Par exemple, il ne peut pas toujours créer un chemin rapide ou optimiser les boucles.
00:15:00 Le compilateur peut faire beaucoup pour optimiser le code, mais il y a certaines choses qu'il ne peut pas bien faire. Un exemple est les structures de données - le compilateur n'est pas intelligent à leur sujet de la même manière qu'il l'est à propos des fonctions. Un autre est les boucles - le compilateur peut faire quelques optimisations dessus, mais il y a des restrictions.
00:20:00 Cette vidéo YouTube explique comment les compilateurs peuvent utiliser des opérations simples pour remplacer des opérations plus complexes. Par exemple, pour remplacer une opération de division, un compilateur peut multiplier par un nombre magique puis décaler le résultat. Cette vidéo explique également le fonctionnement du calculateur d'adresse.
00:25:00 La vidéo explique comment les compilateurs peuvent optimiser le code, en utilisant une simple fonction "vex scale" comme exemple. Le code est d'abord affiché sans optimisations, puis avec diverses optimisations appliquées. Les optimisations présentées incluent la réduction du nombre d'instructions, l'utilisation d'instructions vectorielles et l'utilisation de nombres magiques.
00:30:00 Cette vidéo explique comment les compilateurs peuvent optimiser le code en éliminant les opérations de mémoire inutiles. En particulier, il montre comment un compilateur peut optimiser une fonction qui multiplie deux valeurs scalaires en éliminant le besoin de stocker les valeurs en mémoire. Enfin, il montre comment un compilateur peut optimiser une fonction qui opère sur une structure en éliminant le besoin de stocker la structure en mémoire.
00:35:00 Dans cette vidéo YouTube, le conférencier explique comment les compilateurs peuvent optimiser le code en éliminant les références de stockage et de mémoire inutiles. Il utilise l'exemple d'une structure avec plusieurs champs et montre comment le compilateur peut optimiser le code en analysant attentivement les mathématiques impliquées dans les calculs d'adresse. En comprenant ce que fait chaque instruction, le compilateur peut optimiser le code et supprimer les opérations inutiles.
00:40:00 Le compilateur travaille dur pour transformer les structures de données et les valeurs scalaires pour stocker autant que possible uniquement dans des registres et éviter d'utiliser un stockage local si possible. Pour les appels de fonction, le compilateur voit l'instruction d'appel et le code de la fonction appelée. Il essaie ensuite de rendre la fonction dans le code ci-dessus encore plus rapide.
00:45:00 Le compilateur peut intégrer du code pour éviter la surcharge des appels de fonction, et il peut également optimiser le code en supprimant les opérations inutiles.
00:50:00 Dans cette vidéo YouTube, l'orateur explique qu'il existe trois raisons principales pour lesquelles un compilateur peut ne pas intégrer une fonction : si la fonction est récursive, si la fonction est dans une unité de compilation différente ou si la fonction peut augmenter la taille du code et nuisent aux performances. L'orateur donne également quelques conseils pour contrôler l'inlining des fonctions dans vos propres programmes.
00:55:00 Cette vidéo montre comment les compilateurs peuvent optimiser les boucles pour accélérer l'exécution des programmes. Le levage de code, ou mouvement de code invariant en boucle, est une optimisation qui peut être utilisée pour améliorer les performances.
01:00:00 Le compilateur peut optimiser le code en effectuant une séquence de passes de transformation. Ces passes sont conçues pour trouver des propriétés telles que des calculs d'adresses identiques et les remplacer par un code plus efficace.
01:05:00 Le compilateur est capable de vectoriser cette boucle, malgré le fait qu'il ne sait pas si les adresses de 'x' et 'y' se chevauchent. En effet, la structure du code compilé est plus compliquée que la fonction à deux lignes qui a été donnée en entrée.
01:10:00 Cette vidéo YouTube explique ce que les compilateurs peuvent et ne peuvent pas faire. Les compilateurs peuvent vectoriser le code si le code ne contient aucune boucle. Cependant, si le code contient des boucles, le compilateur ne peut vectoriser le code que si la boucle est pleine d'opérations vectorielles. Si la boucle n'est pas remplie d'opérations vectorielles, le compilateur ne pourra pas vectoriser le code.
01:15:00 La question de savoir si un compilateur peut ou non vectoriser du code est une question difficile, car elle dépend d'un certain nombre de facteurs. En particulier, le compilateur doit être capable de déterminer si oui ou non deux pointeurs seront alias, ce qui peut être une tâche difficile. En tant que programmeur, vous pouvez aider le compilateur en annotant vos pointeurs pour fournir plus d'informations sur leur utilisation.

OpenCL dans le Trading Tutoriels de programmation Apprendre ONNX pour le

MetaQuotes 2023.05.03 17:03 #294

Cours 10. Mesure et chronométrage

Cours 10. Mesure et chronométrage

Dans cette vidéo, les conférenciers discutent de divers aspects de la mesure et de la synchronisation en informatique, y compris les facteurs externes qui peuvent affecter la précision. Ils soulignent la nécessité de modèles et d'une compréhension claire des données, de la réduction de la variance pour compenser les erreurs et de l'utilisation d'appels de synchronisation appropriés pour garantir la fiabilité. Ils discutent également des défis liés à la mesure précise des performances logicielles, tels que la loi de puissance et les facteurs non déterministes, tout en mettant en évidence des outils tels que la modélisation des performances, les appels de synchronisation, les compteurs matériels et les simulateurs. Enfin, ils mettent en garde contre le recours à un seul outil, recommandant la triangulation et l'adaptation comme techniques pour garantir des résultats précis.

Le conférencier explique l'importance d'une mesure de performance fiable dans l'ingénierie logicielle de performance. Il recommande l'utilisation de statistiques pour mesurer avec précision les performances et discute de divers types de statistiques récapitulatives telles que la moyenne, qui peuvent fournir des mesures utiles des performances dans différents contextes. Il souligne que prendre la moyenne arithmétique des rapports n'est pas une approche valable et suggère d'utiliser plutôt la moyenne géométrique. L'orateur souligne l'importance de choisir la bonne façon d'agréger les données lors de la comparaison des programmes et suggère de prendre la statistique d'ordre inférieur, comme le minimum ou 10 %, de plusieurs exécutions pour comparer plus précisément les performances. L'orateur discute également de différentes méthodologies pour mesurer et comparer les performances, y compris la comparaison directe et l'ajustement d'un modèle pour dériver des statistiques, mais met en garde contre le problème de l'ajustement excessif dans la modélisation. Dans l'ensemble, la vidéo souligne l'importance d'une mesure fiable du rendement pour améliorer le rendement du programme.

00:00:00 Dans cette section, l'orateur discute d'une étude sur le code de tri qui a été réalisée par l'un de ses anciens étudiants. Le code utilise le fichier d'en-tête time.h pour accéder à la routine d'obtention de l'horloge pour les mesures de synchronisation. Une routine de tri est chronométrée et le temps écoulé est calculé et imprimé. Le graphique des temps d'exécution mesurés montre que la routine de tri suit principalement une croissance N log N, mais les temps mesurés sont lents même pour les plus grands tableaux.
00:05:00 Dans cette section, un professeur discute de l'importance d'avoir un modèle pour les données observées. Il présente un exemple où les données mesurées s'écartent significativement de ce qui était attendu et demande aux élèves de suggérer des hypothèses possibles pour cet écart. Alors que certains pensaient que cela pouvait être un problème avec le cache ou la précision du timing, le professeur souligne qu'il pourrait y avoir des processus non liés en cours d'exécution sur la machine qui causent l'écart. Dans ce cas, le problème est lié à la multilocation, où la machine est utilisée par plusieurs processus simultanément. Le professeur insiste sur la nécessité d'avoir des mesures de qualité et d'avoir une compréhension claire de ce que signifient les données.
00:10:00 Dans cette section, les conférenciers discutent de la mesure et de la synchronisation en informatique, et de la manière dont les facteurs externes peuvent affecter la précision des mesures. Ils se concentrent spécifiquement sur la façon dont les changements de fréquence d'horloge peuvent se produire en raison de la température du système et des techniques d'économie d'énergie, ce qui peut affecter considérablement les résultats de mesure. Les haut-parleurs introduisent le concept de mise à l'échelle dynamique de la fréquence et de la tension, qui est une technique permettant de réduire la puissance en ajustant la fréquence d'horloge et la tension des transistors. Ils soulignent qu'il est crucial de tenir compte des facteurs externes lors de la prise de mesures pour éviter des résultats inexacts.
00:15:00 Dans cette section, l'orateur aborde les défis de la mesure des performances logicielles en raison de la loi de puissance utilisée par les ingénieurs électriciens. La loi de puissance indique que la puissance est égale à CV au carré F, où C est la capacité dynamique, V est la tension d'alimentation et F est la fréquence d'horloge. Pour réduire la puissance et la chaleur, on peut réduire la fréquence et la tension, ce qui entraîne une réduction cubique de la puissance. Cela présente un défi pour mesurer les performances des logiciels de manière fiable, et l'orateur suggère de mettre les systèmes au repos en se débarrassant d'une partie du bruit pour prendre des mesures précises. Ils discutent également des outils de mesure des performances logicielles, tels que la modélisation des performances.
00:20:00 Dans cette section, l'orateur discute de l'importance de réduire la variance en matière de mesure et de synchronisation, en particulier dans le contexte de l'ingénierie des performances. En réduisant la variabilité, il est possible de compenser les erreurs de mesure systématiques et aléatoires et d'exiger moins d'essais pour comparer les programmes. L'orateur souligne également diverses sources de variabilité dans les systèmes informatiques, notamment les travaux d'arrière-plan, les interruptions et le placement des threads, entre autres. Enfin, il souligne l'importance de se concentrer sur la réduction de la variance avant de tenter d'apporter des modifications au système, car la mesure pendant une forte variance peut conduire à des résultats peu fiables.
00:25:00 Dans cette section, l'orateur parle du concept d'hyper-threading dans les processeurs et comment il peut conduire à des mesures inexactes dans les systèmes cloud. L'hyper-threading exécute deux flux d'instructions via une unité fonctionnelle, apparaissant comme deux processeurs, mais ne fournit en fait qu'une accélération de 20% plutôt que deux processeurs distincts. Le conférencier aborde également d'autres techniques telles que le turbo boost et la mise au repos d'un système, qui peuvent affecter considérablement les résultats de mesure. En désactivant l'hyper-threading et le turbo boost et en mettant au repos tous les démons, l'orateur et son groupe ont pu obtenir des mesures remarquablement fiables qui étaient moins de 1 % plus lentes que la durée d'exécution minimale.
00:30:00 Dans cette section, l'orateur parle de divers facteurs qui peuvent affecter le déterminisme d'un programme exécuté sur du matériel moderne. Bien qu'il existe certaines mesures que l'on peut prendre pour rendre le programme plus déterministe, il est impossible d'éliminer complètement les facteurs non déterministes. La plupart des facteurs non déterministes qui peuvent survenir pendant l'exécution du programme, tels que la mise en cache, les interruptions, les threads et la prédiction de branche, sont des processus déterministes. Cependant, le caractère aléatoire du matériel échappe au contrôle de l'utilisateur et peut entraîner une erreur de mémoire. L'orateur suggère que l'alignement du code peut faire une différence dans le déterminisme du programme, et toute modification apportée au code peut provoquer un changement dans l'alignement du cache, affectant le déterminisme du programme.
00:35:00 Dans cette section, l'orateur explique comment de petits changements peuvent avoir un impact important sur les performances d'un programme. Par exemple, l'insertion d'un octet peut entraîner un impact linéaire sur tout ce qui suit, et la modification de l'ordre dans lequel les fichiers point o apparaissent sur la ligne de commande de l'éditeur de liens peut avoir un effet plus important que d'aller entre -OH- et -O3. Pour résoudre ces problèmes, les compilateurs reconnaissent le problème et font plus d'alignement. LLVM a des commutateurs qui peuvent aligner toutes les fonctions et tous les blocs d'une fonction, mais l'alignement peut ralentir le programme. De plus, le nom du programme peut avoir un impact sur sa vitesse car le nom de l'exécutable se retrouve dans une variable d'environnement qui se retrouve sur la pile des appels.
00:40:00 Dans cette section, l'orateur discute de divers outils et méthodes pour mesurer les performances du logiciel, notamment mesurer le programme en externe avec la commande time, placer des appels de synchronisation dans le programme à l'aide de l'heure d'horloge ou d'autres méthodes, interrompre le programme avec gdb pour identifier quelle routine prend le plus de temps, en exploitant le matériel et le support du système d'exploitation tels que ceux utilisés dans l'ensemble d'outils de performance ou en simulant le programme pour obtenir une compréhension plus approfondie mais à une vitesse plus lente. L'orateur explique la différence entre le temps écoulé, le temps utilisateur et le temps système lors de l'utilisation de la commande time, et comment ils peuvent ne pas correspondre au temps total en raison de l'allocation du processeur.
00:45:00 Dans cette section, l'orateur aborde les différents types de synchronisation et de mesure, y compris le temps d'horloge, le temps processeur passé en mode utilisateur et le temps passé dans le noyau. L'appel de synchronisation recommandé pour l'utilisation est l'heure d'obtention de l'horloge avec l'option monotonique d'horloge qui garantit de ne jamais revenir en arrière. Bien que son exécution puisse prendre un temps non déterministe, il est plus fiable que d'autres temporisateurs tels que RTIDTSC qui peuvent donner des réponses différentes sur différents cœurs et peuvent fonctionner à l'envers. L'orateur met en garde contre l'utilisation de get time of day.
00:50:00 Dans cette section, l'orateur discute de différentes manières de mesurer et de chronométrer des événements dans la programmation, notamment en utilisant clock_gettime et en mesurant avec la commande time. Ils avertissent qu'avec le temps, les techniques peuvent changer et les ingénieurs peuvent avoir besoin de s'adapter. L'orateur suggère également d'interrompre le code à des moments aléatoires comme technique de profilage simple et mentionne que de grandes entreprises telles que Facebook utilisent cette méthode. De plus, l'orateur introduit l'idée des compteurs matériels et de la bibliothèque livepFM4, qui permet d'accéder à ces compteurs par processus. Ils soulignent qu'un ingénieur n'a pas toujours besoin d'outils de précision chirurgicale et que parfois un simple outil peut suffire pour le travail.
00:55:00 Dans cette section, l'orateur aborde les différentes manières de collecter des mesures, y compris les compteurs matériels et les simulateurs. Ils avertissent que de nombreux compteurs matériels sont mal documentés et que certains outils partagent la bande passante si plus de quatre ou cinq compteurs sont utilisés. Les simulateurs sont loués pour leur répétabilité mais peuvent ne pas tout modéliser dans le cache. L'orateur recommande la triangulation et l'utilisation d'au moins deux mesures pour garantir l'exactitude. Ils soulignent également l'importance d'avoir un modèle de performance pour guider l'interprétation des données.
01:00:00 Dans cette section, l'orateur explique le processus d'ingénierie logicielle de performance, qui consiste à prendre un programme, à y apporter des modifications et à mesurer ses performances pour produire un programme plus rapide. Cependant, une mesure fiable des performances est essentielle pour apporter de petits changements qui s'additionnent et tirer des conclusions précises. Par conséquent, l'orateur recommande d'utiliser des statistiques pour obtenir une image précise de ce qui se passe. Il propose également un casse-tête impliquant la mesure des performances brutes d'un programme déterministe et conclut que l'utilisation du minimum est le meilleur moyen de rejeter le bruit et de déterminer les performances matérielles sous-jacentes du programme.
01:05:00 Dans cette section, divers types de statistiques récapitulatives sont abordés, y compris la moyenne, qui peut fournir des mesures utiles des performances dans différents contextes. Lors de l'évaluation des serveurs Web, l'utilisation du processeur et le temps total d'exécution des tâches peuvent être mesurés à l'aide de la moyenne arithmétique, tandis que le temps d'horloge et le comportement en centile peuvent être plus pertinents pour optimiser la satisfaction des demandes. Cependant, lors de la synthèse des ratios, comme la comparaison des performances des programmes A et B, la moyenne arithmétique n'est pas une approche valable, même si elle est souvent mal utilisée. En effet, la moyenne des ratios n'est pas la même que le ratio lui-même, comme illustré dans l'exemple donné dans la vidéo.
01:10:00 Dans cette section, l'orateur aborde les problèmes de comparaison des ratios et des moyennes lors de la mesure des performances. Ils démontrent que prendre la moyenne arithmétique des ratios peut conduire à des résultats suspects, et qu'il est préférable d'utiliser la moyenne géométrique. De plus, ils notent que lors de la comparaison des taux, la moyenne harmonique est souvent utile. L'importance de choisir la bonne façon d'agréger les données lors de la comparaison des programmes est soulignée, et l'orateur suggère de prendre la statistique d'ordre inférieur, comme le minimum ou 10 %, de plusieurs exécutions pour comparer plus précisément les performances.
01:15:00 Dans cette section, l'orateur discute de différentes méthodologies pour mesurer et comparer les performances. Une approche consiste à comparer les 10 % d'options les moins chères et à effectuer une réduction du bruit pour comparer les moyens, bien que cela puisse ne pas fournir de preuves concluantes. Alternativement, une comparaison directe peut être effectuée entre A et B pour voir lequel gagne le plus fréquemment. Grâce à cela, l'hypothèse nulle peut être testée et la valeur p peut être calculée pour déterminer si l'écart est significatif. Cette méthode est couramment utilisée en sciences sociales et peut être utile dans des environnements bruyants. Enfin, l'orateur aborde brièvement l'idée d'ajuster un modèle pour dériver des statistiques et discute de l'utilisation de l'approximation des moindres carrés.
01:20:00 Dans cette section, l'orateur discute de la question du sur-ajustement dans la modélisation et de la façon dont l'ajout de fonctions de base peut améliorer l'ajustement des données, mais également conduire à un sur-ajustement. La solution consiste à supprimer une fonction de base et à vérifier si elle affecte la qualité du modèle. L'orateur mentionne également Lord Kelvin, connu comme le gourou de la mesure, qui a déclaré que mesurer, c'est savoir et que si l'on ne peut pas mesurer, on ne peut pas s'améliorer. La vidéo se termine avec le conférencier souhaitant bonne chance à un quiz mardi.

Apprendre ONNX pour le Trading Quantitatif OpenCL dans le Trading

MetaQuotes 2023.05.03 17:04 #295

Cours 11. Allocation de stockage

Cours 11. Allocation de stockage

Le conférencier discute de l'allocation de stockage dans cette vidéo, couvrant à la fois l'allocation et la libération de mémoire. Différents types de stockage sont abordés, y compris la pile et le tas, ainsi que des schémas d'allocation de taille fixe et variable. La fragmentation externe causée par l'étalement des blocs de mémoire est également abordée, avec des solutions telles que des listes libres ou des bitmaps par page de disque. Le concept de ramasse-miettes est également introduit, y compris le comptage de références et les limites de cet algorithme. Les procédures de récupération de place « marquer et balayer » et « arrêter et copier » sont également expliquées, en mettant l'accent sur la façon dont cette dernière traite la fragmentation et le problème d'exactitude possible créé par les mises à jour de pointeur. La vidéo se termine par des notes sur la complexité temporelle et spatiale de l'algorithme d'arrêt et de copie et son élimination de la fragmentation externe.

Cette vidéo couvre divers sujets liés à l'allocation de stockage dynamique, notamment le système Buddy, les procédures de marquage et de balayage, les optimisations, la récupération de place générationnelle et en temps réel, l'allocation de stockage multithread et la récupération de place parallèle. Le conférencier explique que la récupération de place générationnelle est basée sur l'idée que les objets plus jeunes sont analysés plus fréquemment, tandis que la récupération de place en temps réel s'exécute en arrière-plan pendant l'exécution du programme, mais peut entraîner des problèmes d'exactitude si le graphique d'objet et de pointeur continue de changer. Enfin, la conférence résume différents types d'allocation de stockage, y compris la pile et le tas, et différentes méthodes de récupération de place, telles que le comptage de références, le marquage et le balayage et l'arrêt et la copie. Le conférencier mentionne que les étudiants pourront essayer certaines de ces méthodes dans leur prochain devoir.

00:00:00 Dans cette section, le conférencier discute de l'allocation de stockage, qui inclut à la fois l'allocation et la libération de mémoire. La forme de stockage la plus simple est une pile, où la mémoire est allouée en incrémentant le pointeur de pile et libérée en décrémentant le pointeur de pile. Cependant, la pile a une applicabilité limitée car elle ne peut libérer que la dernière chose qui a été allouée et ne peut rien libérer au milieu de la région utilisée. L'enseignant note également que pour des raisons d'efficacité, le débordement de pile n'est généralement pas vérifié par les compilateurs.
00:05:00 Dans cette section, le conférencier parle de deux types de stockage : la pile et le tas. La pile est un stockage de taille fixe qui est efficace mais ne peut pas être utilisé pour tout, tandis que le tas est plus général mais difficile à organiser et à utiliser efficacement. Pour l'allocation de tas, les fonctions malloc et free C peuvent être utilisées, mais comme C et C++ ne fournissent pas de ramasse-miettes, les programmeurs doivent gérer eux-mêmes la mémoire, ce qui peut entraîner des fuites de mémoire, des pointeurs pendants et une double libération. Le conférencier suggère d'utiliser des vérificateurs de mémoire comme l'assainisseur d'adresses et Valgrind pour réduire le nombre de bogues de mémoire dans le programme.
00:10:00 Dans cette section, l'orateur discute de différentes manières d'allouer le stockage, en commençant par l'allocation de taille fixe, dans laquelle chaque élément de stockage a la même taille et certains blocs sont utilisés tandis que d'autres ne sont pas utilisés. Les blocs inutilisés sont conservés dans une liste appelée la liste libre, et chaque bloc de la liste libre a un pointeur vers le bloc suivant dans la liste. Pour allouer un objet de la liste libre, le programme définit le pointeur comme étant libre, puis définit le pointeur libre pour qu'il pointe vers l'élément suivant dans la liste libre, renvoyant le pointeur vers le premier objet de la liste libre. Pour désallouer, il suffit de définir le prochain pointeur de l'objet sur free et de définir free égal à l'objet à libérer. Avec la liste libre, allouer et libérer prennent un temps constant, et on obtient aussi une bonne localité temporelle.
00:15:00 Dans cette section, le concept de fragmentation externe est introduit, qui se produit lorsque des blocs de mémoire utilisée sont répartis dans l'espace de toute la mémoire. Cela peut conduire à une table de pages plus volumineuse, ce qui peut entraîner un vidage du disque et rendre moins efficace la recherche de traductions. Pour atténuer la fragmentation externe, une liste libre ou un bitmap par page de disque peut être utilisé, et l'allocation à partir de la page la plus complète, la libération de blocs d'histoires et la pagination des pages vides peuvent être effectuées. L'allocation de tas de taille fixe peut également être utile pour réduire la fragmentation externe. Enfin, l'allocation de tas de taille variable peut être utilisée avec des listes libres de bacs, qui tirent parti de l'efficacité des listes libres pour différentes tailles de mémoire allouée.
00:20:00 Dans cette section, un schéma de stockage de blocs de mémoire de différentes tailles dans un système d'allocation de mémoire est présenté. Le schéma consiste à diviser les blocs en bacs en fonction de leur taille, chaque bac contenant des blocs d'une taille spécifiée qui sont des puissances de deux. Lors de l'allocation de mémoire, le bac approprié est sélectionné en fonction de la taille demandée, et s'il est vide, un bac non vide plus grand est divisé en plus petits morceaux pour obtenir la taille souhaitée. Cependant, ce schéma peut entraîner une fragmentation interne de la mémoire, ce qui est un gaspillage, de sorte que le nombre de bacs utilisés est limité et que de petits blocs sont regroupés en pages pour réduire la surcharge. Le système d'exploitation peut être utilisé pour fournir plus de mémoire si nécessaire, et des appels système sont disponibles à cet effet.
00:25:00 Dans cette section, la vidéo explique comment fonctionne l'allocation de mémoire et note que les implémentations standard de 'malloc' reposent sur des commandes telles que 'break' pour obtenir de la mémoire du système d'exploitation. Le système d'exploitation fournit une grande partie de la mémoire, et c'est au système d'allocation de stockage de la décomposer en blocs plus petits. Cette section couvre également les variantes de l'allocateur de mémoire, y compris les différents schémas de stockage des tailles de bloc et la façon dont l'espace d'adressage de la mémoire virtuelle est disposé dans un programme. Il note que la pile et le tas grandissent l'un vers l'autre mais ne se croisent jamais. Enfin, il est mentionné que le pré-calcul de grands tableaux de constantes dans un programme peut augmenter le temps de chargement car il nécessite la lecture du segment de données.
00:30:00 Dans cette section, le problème de la fragmentation avec la mémoire virtuelle est abordé, ce qui peut entraîner une fragmentation externe, une dégradation des performances de la table des pages, un écrasement du disque et de faibles taux de succès TLB si la mémoire est étalée. L'objectif de l'allocation de stockage est d'utiliser le moins de mémoire virtuelle possible tout en gardant les portions de mémoire utilisées compactes. Le schéma d'allocation de liste libre de bacs est analysé, avec un théorème indiquant que la quantité de mémoire virtuelle consommée par le stockage en tas est supérieure à M log M. La fusion de blocs plus petits en blocs plus grands peut améliorer le schéma de liste libre de bacs, mais la surcharge de cette méthode peut être élevée par rapport à l'algorithme standard de liste libre de bacs, qui n'est qu'un facteur constant pire que l'allocateur optimal, selon un article de Charles Leiserson.
00:35:00 Dans cette section, l'orateur explique le concept d'allocation de stockage et comment il peut réduire la fragmentation lorsqu'il s'agit de stockage en tas. Il discute également de l'idée du ramasse-miettes, qui évite au programmeur d'avoir à libérer manuellement des objets. L'orateur explique les trois types d'objets de mémoire - les racines, les objets vivants et les objets morts - et comment le ramasse-miettes peut recycler ces derniers. Enfin, il décrit le comptage de références, une forme simple de ramasse-miettes qui compte le nombre de pointeurs référençant un objet pour déterminer s'il peut être libéré.
00:40:00 Dans cette section, l'orateur présente le concept de comptage de références en tant que schéma de récupération de place et explique comment fonctionne l'algorithme de comptage de références. Cependant, une limitation de l'algorithme est signalée, où les cycles dans le graphe de référence ne peuvent pas être collectés. L'orateur discute ensuite de l'utilisation de pointeurs forts et faibles dans certains langages de programmation pour éviter cette limitation. Enfin, l'orateur présente deux autres schémas de récupération de place, "marquer et balayer" et "arrêter et copier", qui évitent la limitation du comptage de références lorsqu'il s'agit de cycles dans le graphe de référence.
00:45:00 Dans cette section, l'orateur discute de l'utilisation d'un algorithme de recherche en largeur d'abord pour trouver tous les objets vivants en mémoire. Un tableau avec deux pointeurs est utilisé pour représenter une file d'attente FIFO pour la recherche, et l'algorithme marque chaque objet actif accessible à partir des racines. Une fois la recherche terminée, les objets non marqués sont disponibles pour être récupérés. La procédure de marquage et de balayage comprend deux étapes : l'étape marquée, qui implique l'algorithme de recherche en largeur d'abord, et l'étape de balayage, qui implique le balayage de la mémoire pour libérer les objets non marqués. Cependant, ce schéma présente des limites, telles que la nécessité d'analyser toute la mémoire et la surcharge associée à l'examen d'objets non référencés.
00:50:00 Dans cette section, la vidéo présente la procédure de récupération de place "arrêter et copier" qui traite de la fragmentation. Cette procédure est similaire à l'algorithme de marquage et de balayage, mais adopte une approche différente pour garantir que les objets actifs sont contigus en mémoire. La procédure utilise deux espaces mémoire distincts - l'espace de départ et l'espace de destination - et alloue et libère des objets de l'espace de départ jusqu'à ce qu'il soit plein. Ensuite, l'algorithme de récupération de place est exécuté et les deux espaces sont utilisés comme file d'attente pour la recherche en largeur d'abord pour identifier les objets actifs, qui seront placés de manière contiguë en mémoire dans les deux espaces. Cependant, l'utilisation de cet algorithme peut entraîner un problème d'exactitude possible où les pointeurs qui pointent vers des objets dans l'espace de départ peuvent ne plus être corrects. Pour résoudre ce problème, la procédure stocke un pointeur de transfert dans l'objet correspondant dans l'espace de départ et met à jour tous les pointeurs en suivant ces pointeurs de transfert lors de la suppression d'un objet de la file d'attente dans la recherche en largeur d'abord.
00:55:00 Dans cette section, l'orateur discute de l'algorithme d'arrêt et de copie de la récupération de place, de sa complexité temporelle et de la manière dont il traite la fragmentation externe. L'algorithme d'arrêt et de copie implique la copie d'objets de l'espace de vers l'espace de destination, puis la mise à jour des pointeurs de ces objets dans l'espace de destination. Cet algorithme est linéaire dans le temps et dans l'espace, ce qui en fait un moyen de récupération de place plus efficace et efficient. Lorsque l'espace de départ est plein, l'utilisateur peut demander un nouvel espace de tas et doubler la taille de l'espace de départ. L'espace de mémoire virtuelle requis par ce schéma est constant fois optimal, et cet algorithme élimine la fragmentation externe.
01:00:00 Dans cette section, l'orateur aborde d'autres sujets liés à l'allocation de stockage dynamique, tels que le système Buddy pour effectuer la fusion, les variantes de la procédure de marquage et de balayage, les optimisations pour améliorer les performances, le ramasse-miettes générationnel, le ramasse-miettes en temps réel , l'allocation de stockage multithread et la récupération de place parallèle. Le ramasse-miettes générationnel est basé sur l'idée que de nombreux objets ont une durée de vie courte, donc seuls les objets plus jeunes sont analysés la plupart du temps. La récupération de place en temps réel fonctionne en arrière-plan pendant l'exécution du programme, mais cela peut entraîner des problèmes d'exactitude si le graphique des objets et des pointeurs change. L'allocation de stockage multithread et la récupération de place parallèle ont plusieurs threads en cours d'exécution, ce qui rend les algorithmes plus difficiles à gérer les courses et autres problèmes d'exactitude. L'orateur résume également les différents types d'allocation de stockage, y compris la pile et le tas, et les différentes façons de procéder à la récupération de place, telles que le comptage de références, le marquage et le balayage et l'arrêt et la copie.
01:05:00 Dans cette section, l'instructeur a mentionné qu'il approfondira les schémas d'allocation de stockage et que les étudiants auront l'occasion d'en essayer certains dans leur prochain devoir. L'instructeur a ensuite mis fin à la conférence et a ouvert la parole pour d'autres questions.

Tutoriels de programmation OpenCL dans le Trading Python dans le Trading

MetaQuotes 2023.05.03 17:05 #296

Cours 12. Allocation de stockage parallèle

Cours 12. Allocation de stockage parallèle

La vidéo présente diverses stratégies d'allocation de mémoire et leurs compromis. L'utilisation de malloc et l'allocation alignée, ainsi que l'importance d'une désallocation de mémoire appropriée avec free, sont expliquées. L'utilisation de Mmap pour l'allocation de mémoire virtuelle est également couverte, ainsi que les problèmes de fragmentation externe et de ralentissement des performances. Le concept de piles dans la programmation C et C++ est exploré, l'accent étant mis sur une approche de pile de cactus basée sur le tas pour l'allocation des cadres de pile, ce qui peut conduire à de meilleures preuves liées à l'espace et à des limites supérieures. L'utilisation d'un pool de piles linéaires est également discutée, ainsi que l'importance de l'optimisation pour les petits blocs afin de minimiser la fragmentation. La vidéo se termine par une discussion sur les approches de tas globales et locales et leurs problèmes potentiels, ainsi que sur des approches telles que les listes de bacs libres et le rééquilibrage périodique de la mémoire pour résoudre ces problèmes.

La vidéo aborde également les solutions d'allocation de stockage parallèle et présente l'allocateur Hoard en tant que solution. L'allocateur Hoard utilise une combinaison de tas locaux et globaux et de grands super blocs qui peuvent être déplacés entre les tas pour réduire le faux partage, améliorer l'évolutivité et réduire la fragmentation externe. Le stockage maximal alloué dans le tas global est au maximum le stockage maximal alloué dans les tas locaux, et l'empreinte est limitée par l'empreinte utilisateur plus le stockage alloué mais inutilisé dans les tas locaux. La vidéo aborde également brièvement d'autres allocateurs tels que Je malloc et Super malloc, avec des résultats de référence indiquant que Super malloc a mieux performé que Je malloc et Hoard. La discussion se termine par une référence aux diapositives en ligne pour les détails de la collecte des ordures.

00:00:00 Dans cette section, le conférencier passe en revue les primitives d'allocation de mémoire, y compris malloc et l'allocation alignée. L'allocation alignée peut être utilisée pour aligner la mémoire sur les lignes de cache afin que l'accès à un objet dans une ligne de cache ne nécessite qu'un seul accès au cache, réduisant ainsi le nombre d'échecs de cache. Le conférencier discute également de l'importance de désallouer correctement la mémoire avec la fonction libre et d'éviter les fuites de mémoire et la double libération. Enfin, le conférencier présente l'appel système Mmap, qui peut être utilisé pour allouer de la mémoire virtuelle sans fichier de sauvegarde.
00:05:00 Dans cette section, l'orateur explique le processus d'allocation de mémoire à l'aide de M map, qui est un appel système qui trouve une région inutilisée contiguë dans l'espace d'adressage de l'application suffisamment grande pour contenir la taille de mémoire demandée et met à jour le table de pages pour contenir une entrée pour les pages allouées. Contrairement à malloc, qui est un appel de bibliothèque et une partie du code de gestion de tas de la bibliothèque C, M map n'alloue pas immédiatement de mémoire physique pour la mémoire demandée mais remplit la table des pages avec des entrées pointant vers une page zéro spéciale qui est modifiée et traduit en mémoire physique uniquement lorsque l'utilisateur y écrit pour la première fois. De plus, M map est responsable de l'obtention de la mémoire du système d'exploitation, tandis que malloc est responsable de la réutilisation de la mémoire précédemment allouée pour réduire la fragmentation et améliorer la localité temporelle.
00:10:00 Dans cette section, la vidéo traite des différences entre l'utilisation de MMAP et de MALLOC pour l'allocation de stockage, en soulignant que MMAP est relativement lourd et alloue des pages entières même pour de petites allocations, entraînant une fragmentation externe et des performances lentes. La vidéo passe également en revue le processus de traduction d'adresse, où l'adresse virtuelle est utilisée pour accéder à la mémoire et le matériel recherche l'adresse physique appropriée dans la table des pages. La vidéo explique comment les TLB fonctionnent en mettant en cache les recherches récentes dans la table des pages et note que les programmes avec une localité spatiale ou temporelle auront de nombreux accès récents stockés dans le TLB, ce qui accélérera les performances.
00:15:00 Dans cette section, l'orateur explique comment fonctionne la traduction d'adresses dans les machines modernes et se penche également sur le concept de piles dans la programmation C et C ++. Les piles sont utilisées pour garder une trace des appels de fonction et des variables locales et suivre un ordre linéaire. L'orateur met l'accent sur une règle des pointeurs dans les piles linéaires traditionnelles : un parent peut transmettre des pointeurs vers ses variables de pile à ses enfants, mais pas l'inverse, pour éviter d'écraser les variables. L'orateur suggère également des options, telles que l'allocation de mémoire sur le tas ou sur la pile du parent, pour transmettre la mémoire d'une fonction enfant au parent.
00:20:00 l'allocation de tas parallèle est correcte, le problème potentiel avec l'utilisation d'une pile de cactus basée sur le tas est la fragmentation de la mémoire, où il peut ne pas y avoir assez de mémoire contiguë pour les futures allocations, ce qui entraîne un gaspillage d'espace et potentiellement un manque de mémoire ou faire planter le programme. Alors que les premiers systèmes de programmation parallèle utilisaient cette stratégie, il est important d'optimiser le code pour minimiser l'impact sur les performances et tenir compte des conséquences de la fragmentation de la mémoire.
00:25:00 Dans cette section, la vidéo traite de l'utilisation d'une approche de pile de cactus basée sur le tas pour allouer des cadres de pile sans imposer de limite supérieure à la profondeur maximale. Cependant, l'interopérabilité est un problème lorsque vous essayez d'utiliser le code de pile linéaire traditionnel avec cette pile de cactus basée sur le tas. Cela peut être résolu à l'aide d'une approche appelée mappage de la mémoire locale des threads, mais cette approche nécessite des modifications du système d'exploitation. Malgré cela, l'approche de la pile de cactus basée sur le tas est toujours bonne dans la pratique et peut être utilisée pour prouver l'espace d'un programme Silk qui l'utilise. Cette limite d'espace montre que l'espace de pile d'une exécution de travailleur P utilisant une pile de cactus basée sur le tas est limité supérieur par P fois s1, où s1 est l'espace de pile requis par une exécution en série du programme Silk. C'est une fonctionnalité intéressante de l'approche de la pile de cactus basée sur le tas.
00:30:00 Dans cette section, le code de multiplication matricielle diviser pour mieux régner est analysé pour comprendre comment il peut être appliqué au théorème du compromis espace-temps. Le code effectue huit appels récursifs, chacun de taille N/2, et avant chaque appel, il effectue un malloc pour obtenir un espace temporaire d'ordre de taille N au carré, qui est ensuite libéré juste avant le retour de la fonction. Étant donné que les allocations suivent une discipline de pile, même lors de l'allocation hors du tas, l'espace lié à la diapositive précédente peut être utilisé pour limiter l'espace de travail P. Le travail est N au cube et la portée est d'ordre log au carré N. La récurrence pour l'espace est s de N/2 + thêta de N au carré, ce qui se résout en N au carré. Par conséquent, la propriété des feuilles occupées et le théorème de la borne d'espace montrent que sur P processeurs, l'espace est borné par P fois N au carré.
00:35:00 Dans cette section, l'orateur explique au public comment prouver un espace plus fort lié à l'algorithme discuté dans la section précédente. En analysant la structure de l'algorithme et en se concentrant sur la ramification autant que possible près du sommet de l'arbre de récursivité, le locuteur est capable de démontrer une borne spatiale de P au tiers de fois N au carré, ce qui est meilleur que les bornes supérieures précédentes. . L'orateur note que l'analyse de la structure d'un algorithme peut conduire à des preuves liées à l'espace plus solides que la simple application d'un théorème général. La section se termine en expliquant comment les fonctions parallèles ne parviennent pas à interagir avec les binaires série hérités et tiers.
00:40:00 Dans cette section, l'orateur discute de l'utilisation d'un pool de piles linéaires dans l'allocation de stockage, qui peut être utilisé pour maintenir un pool de piles pour le code hérité. Le nombre de piles dans le pool doit être constant multiplié par le nombre de processeurs afin que l'espace lié soit préservé. Cependant, cette stratégie peut avoir un impact sur la limite temporelle de l'algorithme de vol de travail, car le travailleur peut ne pas être en mesure de voler s'il n'y a plus de piles disponibles. L'orateur parle ensuite des propriétés de base des allocations de stockage de tas, y compris la vitesse de l'allocation et l'encombrement de l'utilisateur, en soulignant l'importance de l'optimisation pour les petits blocs en raison du potentiel de fragmentation et de surcharge lors de l'allocation. La fragmentation est définie comme l'empreinte de l'allocateur divisée par l'empreinte de l'utilisateur.
00:45:00 Dans cette section de la vidéo, l'orateur explique comment maintenir l'empreinte allouée aussi proche que possible de l'empreinte de l'utilisateur afin de minimiser le rapport des deux. Une solution consiste à utiliser quelque chose appelé M advisor, qui indique au système d'exploitation qu'une certaine page de mémoire n'est plus nécessaire mais doit être conservée dans la mémoire virtuelle. L'orateur mentionne également le théorème de la conférence précédente selon lequel la fragmentation des listes libres de bacs est la base deux du journal d'ordre de U, où U est la quantité totale de mémoire allouée, et explique les différences entre la surcharge d'espace, la fragmentation interne et la fragmentation externe. Enfin, l'orateur note que les processeurs 64 bits modernes fournissent environ 2 à 48 octets d'espace d'adressage virtuel, ce qui est suffisant pour la plupart des programmes mais toujours plus que la mémoire physique d'une machine typique.
00:50:00 Dans cette section, la vidéo explore une stratégie d'allocation de tas parallèle utilisant un tas global avec protection mutex, c'est ainsi que fonctionne l'allocateur C++ par défaut. L'explosion de cette stratégie en est une, car elle ne nécessite pas d'espace supplémentaire par rapport à un répartiteur en série. Cependant, le problème potentiel de cette approche est l'impact sur les performances, car l'acquisition du verrou pour chaque allocation et désallocation est lente et s'aggrave avec l'augmentation du nombre de processeurs. Les conflits de verrouillage sont la principale raison d'une mauvaise évolutivité, qui est plus problématique pour les petites allocations en raison de taux de demandes plus élevés, et les allocations de blocs volumineux nécessitent plus de travail.
00:55:00 Dans cette section, la vidéo traite du problème potentiel lié à l'utilisation d'une approche de tas local, à savoir qu'elle peut entraîner une dérive de la mémoire et une explosion illimitée. Essentiellement, si vous allouez toute votre mémoire dans un thread mais que vous la libérez dans un autre, il peut y avoir de la mémoire inutilisée dans le système que l'allocateur n'est pas assez intelligent pour réutiliser. Par conséquent, votre programme exécuté sur plusieurs processeurs pourrait éventuellement manquer de mémoire, mais cela ne se produira pas s'il n'est exécuté que sur un seul cœur. La vidéo suggère d'utiliser une approche de liste libre pour résoudre ce problème, qui implique de définir des pointeurs dans la structure de données de la liste libre afin que le bloc libéré puisse apparaître dans l'une des listes liées. Une autre stratégie consiste à rééquilibrer périodiquement la mémoire, mais une approche plus simple est également discutée.
01:00:00 Dans cette section, la vidéo explique comment modifier l'allocateur de mémoire pour obtenir le comportement souhaité consistant à ce que chaque thread accède à son propre tas sans avoir besoin d'un tas global. Une approche consiste à étiqueter chaque objet avec un propriétaire et à le renvoyer dans le tas du propriétaire lorsqu'il est libéré. De cette façon, les objets locaux obtiennent une allocation et une libération rapides, tandis que les objets distants nécessitent une certaine synchronisation, mais pas autant qu'avec un tas global. La quantité maximale de mémoire pouvant être allouée est limitée par X, la quantité utilisée par le programme séquentiel, et le taux d'agrandissement est limité par P, le nombre de tas. Cette approche est également résistante au faux partage, qui se produit lorsque plusieurs processeurs accèdent à différents emplacements de mémoire mais sur la même ligne de cache.
01:05:00 Dans cette section, l'orateur explique comment l'allocation de tas parallèle peut conduire à un faux partage et présente l'allocateur de trésor comme solution. L'allocateur de trésor utilise une combinaison de tas locaux et globaux, organisant la mémoire en grands super blocs qui peuvent être déplacés entre les tas. Cette approche est rapide, évolutive et résistante aux faux partages. Lorsqu'une allocation est effectuée, l'allocateur recherche un objet libre dans le tas local et l'obtient s'il en existe un. Sinon, il va au tas global pour obtenir plus de mémoire.
01:10:00 Dans cette section, l'orateur explique comment l'allocateur Horde réduit la fragmentation externe en allouant un objet libre du super bloc non plein le plus plein pour densifier le mouvement des super blocs. Si l'objet n'est pas trouvé dans le tas local, il vérifie le tas global, et si le tas global est vide, il appelle un nouveau super bloc depuis le système d'exploitation. L'allocateur Horde maintient un invariant où le tas est au plus à moitié utilisé, et s'il détecte que le tas est sous-utilisé, il déplace un superbloc à moitié vide vers le tas global. L'orateur présente alors un lemme indiquant que le stockage maximum alloué dans le tas global est au plus le stockage maximum alloué dans les tas locaux. Enfin, l'orateur prouve le théorème selon lequel l'empreinte de l'allocateur Horde est limitée par l'ordre u plus SP, où u est l'empreinte utilisateur pour le programme, et SP est le stockage alloué mais inutilisé dans les tas locaux. L'éclatement est alors calculé comme étant un ordre plus SP divisé par u.
01:15:00 Dans cette section, le conférencier discute de différents répartiteurs dont Je malloc et Super malloc. Je malloc a des verrous globaux distincts pour différentes tailles d'allocation et libère les pages vides en utilisant les conseils em, ce qui le rend robuste aux différentes traces d'allocation. D'un autre côté, Super malloc a très peu de lignes de code et se développe très rapidement. L'orateur partage des résultats de référence où Super malloc a mieux performé que J malloc, qui a mieux performé que Horde, tandis que l'allocateur par défaut avait de mauvaises performances. La discussion s'étend également à la collecte des ordures, cependant, l'orateur reporte les détails de cela aux diapositives en ligne.

OpenCL dans le Trading Tutoriels de programmation Python dans le Trading

MetaQuotes 2023.05.03 17:07 #297

Cours 13. Le système d'exécution Cilk

Cours 13. Le système d'exécution Cilk

Le système d'exécution Cilk est responsable de la planification et de l'équilibrage de charge des calculs sur des processeurs parallèles, en utilisant un planificateur de vol de travail aléatoire pour mapper les calculs sur les processeurs au moment de l'exécution. Le système est conçu pour optimiser l'exécution en série du programme, même au prix d'un coût supplémentaire pour les vols. Le travailleur maintient une structure de données de pont séparée qui contient des pointeurs vers les cadres de pile et utilise des pointeurs de tête et de queue. Les trames qui sont disponibles pour être volées ont une structure locale supplémentaire qui contient les informations nécessaires pour que le vol se produise alors que le pont est externe à la pile d'appels. La section explique comment le système permet aux processeurs de commencer à s'exécuter à partir du milieu d'une fonction en cours d'exécution et comment la synchronisation entre les processeurs devient compliquée lorsqu'elle atteint une instruction de synchronisation qui ne peut pas s'exécuter au-delà du point car des processeurs spécifiques attendent toujours la fin des calculs. De plus, le conférencier aborde les performances du système, les considérations de conception et les structures de données, et comment le système optimise l'exécution à l'aide du protocole THC, impliquant deux ensembles de protocoles, un pour le travailleur exécutant le travail et un pour le voleur.

Le système d'exécution Cilk utilise un protocole de saut défini et de saut long pour gérer le vol de calculs à partir des ponts d'exécution des processus victimes. L'abstraction Cactus Stack permet au processus voleur d'avoir sa propre pile d'appels pour empêcher la corruption des piles de la victime. Le protocole de synchronisation du système utilise une arborescence de calculs et une pile Cactus pour garantir que la synchronisation ne se produit qu'entre les calculs imbriqués dans une fonction. L'arborescence complète maintient les relations parent-enfant entre les calculs avec des sous-calculs en suspens pour simplifier le processus de synchronisation. De plus, le système d'exécution optimise le cas courant où la fonction actuelle n'a pas de calculs enfants en attente et où tous les travailleurs sont occupés. Les autres fonctionnalités prises en charge incluent les exceptions C++, les hyper-objets réducteurs et les pedigrees.

00:00:00 Dans cette section, Tibi explique le système d'exécution Cilk, qui est responsable de la planification et de l'équilibrage de charge des calculs sur les processeurs parallèles. Le système d'exécution utilise un planificateur de vol de travail aléatoire pour mapper les calculs sur les processeurs au moment de l'exécution, garantissant une exécution efficace. Tibi note que le système d'exécution Cilk est un logiciel complexe, mais sa magie sous-jacente est mise en œuvre grâce à la collaboration du compilateur Cilk et de la bibliothèque d'exécution. De plus, il montre le pseudocode d'un programme Cilk simple après la compilation, ce qui met en évidence le processus complexe sous-jacent au système d'exécution de Cilk.
00:05:00 Dans cette section, l'orateur explique les fonctionnalités requises pour le système d'exécution Cilk, ainsi que les considérations de performances. Il utilise un exemple de routine Fibonacci parallélisée pour illustrer comment le programme Cilk exécute un calcul dag, qui se déroule dynamiquement lorsque le programme s'exécute sur un processeur. Cependant, lorsque l'instruction silk spawn est rencontrée, une nouvelle trame est créée pour fib of 3, et un autre brin est disponible pour s'exécuter en parallèle. Le processeur commence alors à exécuter fib of 3 comme s'il s'agissait d'un appel de fonction ordinaire. Le processus se répète lorsque le pointeur d'instruction revient au début de la routine fib.
00:10:00 Dans cette section, nous voyons comment plusieurs processeurs exécutent une routine fib en parallèle à l'aide du système d'exécution Cilk. Chaque processeur saute au milieu d'une fonction en cours d'exécution et commence à l'exécuter, malgré des registres indépendants, ce qui soulève la question de savoir comment le système Silk permet aux processeurs de commencer à s'exécuter à partir du milieu d'une fonction en cours d'exécution. De plus, la synchronisation entre les processeurs devient compliquée lorsqu'elle atteint une instruction de synchronisation qui ne peut pas s'exécuter au-delà du point car des processeurs spécifiques attendent toujours la fin des calculs, ce qui nécessite une synchronisation fine au sein du modèle imbriqué.
00:15:00 Dans cette section, l'orateur discute des considérations d'implémentation pour le système d'exécution Cilk. Ils mentionnent trois considérations principales : un seul travailleur capable d'exécuter le programme, la possibilité de sauter au milieu de l'exécution des fonctions et de reprendre là où les autres processeurs se sont arrêtés, et la synchronisation. De plus, Silk a une notion de pile de cactus, qui doit être implémentée correctement pour rendre toutes les vues de la pile disponibles et cohérentes. Enfin, le système doit permettre le vol de travail en permettant aux processeurs de se voler des trames les uns aux autres.
00:20:00 Dans cette section, l'orateur discute des fonctionnalités requises pour le système d'exécution Cilk, qui comprend l'exécution en série, les voleurs sautant au milieu des fonctions en cours d'exécution, les synchronisations pour synchroniser de manière imbriquée à grain fin, une pile de cactus pour tous les travailleurs à voir, et traitant des mélanges de cadres d'apparition et de cadres appelés qui peuvent être disponibles lorsqu'ils volent le calcul. La section passe ensuite à l'examen des performances du système, où nous avons besoin d'un parallélisme suffisant, T1 sur T infini devrait être beaucoup plus grand que P, et nous voulons une accélération linéaire lors de l'augmentation du nombre de processeurs pour exécuter le programme. La section couvre également le temps d'exécution attendu de TCP sur les processeurs P, qui est proportionnel au travail de calcul divisé par le nombre de processeurs plus quelque chose de l'ordre de la durée du calcul.
00:25:00 Dans cette section, nous découvrons le système d'exécution Cilk et son objectif de maintenir une efficacité de travail élevée dans les programmes avec un parallélisme suffisant. Le Silk Runtime System respecte le principe du travail d'abord en optimisant l'exécution en série du programme, même au prix d'un coût supplémentaire pour les aciers. La bibliothèque du système d'exécution gère les problèmes d'exécution parallèle et gère les chemins d'exécution plus lents lorsque des aciers se produisent. Le travailleur maintient une structure de données de pont séparée qui contient des pointeurs vers les cadres de pile et utilise des pointeurs de tête et de queue. Les trames qui sont disponibles pour être volées ont une structure locale supplémentaire qui contient les informations nécessaires pour que le vol se produise alors que le pont est externe à la pile d'appels.
00:30:00 Dans cette section, nous découvrons la conception du système d'exécution Cilk et ses structures de données de base. Le système génère une fonction d'assistance d'apparition pour chaque calcul, qui maintient une structure de travail et une structure de cadre de pile Silk pour chaque instanciation d'une fonction d'apparition et d'un assistant d'apparition, respectivement. Le cadre de pile Silk RTS contient des champs tels qu'un tampon et un entier d'indicateurs pour résumer l'état du cadre de pile Silk, et un pointeur vers un cadre de pile Silk parent dans la pile d'appels. La structure de travail conserve un pont et un pointeur vers le cadre de pile Silk RTS actuel. Ces structures de données sont les éléments essentiels du système d'exécution Cilk sur lequel le système d'exécution Intel so+ élabore.
00:35:00 Dans cette section, la vidéo explore le code de la fonction spawn "foo" et de la fonction spawn helper. Le code pour "foo" inclut un appel pour initialiser le cadre de la pile, configuré pour un spawn avec la routine set jump, un appel à la fonction d'assistance spawn "spawn bar", un bloc de code conditionnel pour un puits dans le Silk RTS, et des appels aux cadres pop et leaf pour le nettoyage. Le code de l'assistant de spawn comprend un appel pour initialiser le cadre de la pile et un appel pour détacher le Silk RTS avec des fonctions de nettoyage supplémentaires pour la structure de la pile. La routine d'établissement est décrite comme une fonction qui permet à des voleurs de voler la suite de la fonction, en prenant comme argument un tampon pour stocker les informations nécessaires à la reprise de l'emplacement de la fonction.
00:40:00 Dans cette section, l'orateur explique comment restreindre l'ensemble de registres et les enregistrer dans un ensemble prédéterminé pour un appel de fonction. La responsabilité de sauvegarder les registres incombe à la fonction, mais le pointeur d'instruction et les pointeurs de pile sont sauvegardés dans le tampon. La section traite ensuite d'une fonction d'assistance de spawn et de la manière dont elle met à jour les structures de travail et les cadres de pile actuels. Enfin, la section explique comment la routine rapide d'entrée de cadre établit un pointeur parent dans la pile d'appels et met à jour le cadre de pile actuel du travailleur pour qu'il pointe vers le bas.
00:45:00 Dans cette section, la transcription de la vidéo YouTube intitulée "The Cilk Runtime System" explique comment la fonction de détachement de Silk RTS permet de voler des calculs, où une fois l'exécution artistique de Silk terminée, un voleur pourrait venir voler la poursuite de la ponte de la soie. Le cadre contextuel est responsable du nettoyage de la structure du cadre de pile et de la mise à jour du cadre de pile actuel pour qu'il pointe vers le parent. Cet appel de fonction peut ou non revenir, et lequel de ces deux cas est le plus important à optimiser pour le système d'exécution est le cas de réussite, basé sur les deux qui fonctionnent en premier principe.
00:50:00 Dans cette section, l'orateur discute de l'optimisation du système d'exécution Cilk sur l'exécution des travailleurs dans le premier cas, où les travailleurs sont supposés effectuer une exécution en série régulière. Ils expliquent également comment fonctionne le vol de travailleurs, le voleur ciblant le haut du deck de la victime, sortant l'objet de la file d'attente et mettant à jour la tête du deck et le pointeur de cadre de pile actuel. Le résultat de la fonction générée est renvoyé au cadre de pile parent dans le code SIL d'origine.
00:55:00 Dans cette section, l'orateur explique l'approche du système d'exécution Cilk dans la gestion des accès simultanés impliquant plusieurs processeurs à l'aide d'un protocole appelé protocole THC. Le protocole implique deux ensembles de protocoles, un pour le travailleur exécutant le travail et un pour le voleur. Le protocole du travailleur est optimisé en essayant de faire éclater quelque chose du bas du pont, et ce n'est qu'en cas d'échec qu'il acquiert un verrou sur le pont, tandis que le voleur attrape toujours un verrou avant d'effectuer toute opération sur le pont. Le voleur reprend alors comme par magie une continuation volée en appelant la fonction de saut long, en passant le tampon de trame de pile récupéré à partir de la fonction de saut défini et en définissant son état de registre comme celui de la continuation volée.
01:00:00 Dans cette section, l'orateur discute de l'interaction entre les appels de saut défini et de saut en longueur dans le système d'exécution de Cilk. Ils expliquent comment, lorsqu'une routine de saut en longueur est appelée, elle revient effectivement du saut défini une deuxième fois, cette fois avec une valeur différente spécifiée dans le deuxième argument. En utilisant le tampon et le deuxième argument appropriés, le voleur peut exécuter un saut en longueur pour ignorer un certain calcul dans le code de la victime. L'orateur note qu'il est possible de calculer de manière statique la distance nécessaire pour sauter par-dessus un appel et d'utiliser une approche différente, mais le protocole de saut défini et de saut en longueur sert de méthode plus flexible pour le système d'exécution Cilk. Dans l'ensemble, l'orateur met en évidence les différentes techniques disponibles pour que le voleur vole les calculs du jeu de la victime à l'aide de Cilk.
01:05:00 Dans cette section, la nécessité d'une abstraction de pile de cactus pour le système d'exécution Cilk est discutée. Il est expliqué que l'utilisation de la pile de la victime peut entraîner la corruption de la pile de la victime et causer des problèmes de maintien de la cohérence entre tous les travailleurs. Par conséquent, une pile d'appels distincte pour le voleur est nécessaire. L'implémentation de la pile de cactus implique que le voleur vole la suite et positionne son pointeur de pile sur sa propre pile tout en pouvant toujours accéder à l'état de la fonction sur la pile de la victime via des décalages de RB p.
01:10:00 Dans cette section, l'orateur explique comment le système d'exécution SIL gère la synchronisation des calculs sur différents processeurs. Le système utilise la pile de cactus et un arbre de calculs pour garantir que la synchronisation ne se produit qu'entre les sous-calculs imbriqués sous une fonction, et non le programme en général. Lorsqu'un travailleur atteint une instruction Silk Sync avant le retour de tous les sous-calculs, il devient un voleur et continue de travailler sur le cadre de pile d'un calcul volé. Cela permet au système d'éviter de gaspiller des travailleurs et de s'assurer que les calculs imbriqués sont correctement synchronisés. Le système demande spécifiquement au compilateur de ne pas utiliser une optimisation qui pourrait entrer en conflit avec cette approche.
01:15:00 Dans cette section, le système d'exécution Cilk est décrit comme maintenant un arbre d'états appelés trames complètes, qui garde une trace des calculs en attente sur lesquels les autres calculs doivent se terminer. Ce système utilise une arborescence de cadres complète pour garder une trace de charges d'informations pour une exécution parallèle, y compris des pointeurs vers des cadres parents, potentiellement vers des cadres enfants, et comment les sous-calculs en cours sont liés les uns aux autres. Lorsqu'un travailleur rencontre une synchronisation, s'il a un calcul enfant en attente, il ne peut pas se synchroniser et doit suspendre son image complète jusqu'à ce qu'il puisse devenir un voleur pour voler plus de travail. Ce système permet à un programme d'avoir un parallélisme suffisant et simplifie les protocoles de synchronisation.
01:20:00 Dans cette section, l'orateur explique comment le système d'exécution Cilk optimise le cas courant où la fonction d'exécution n'a pas d'enfants en suspens et où tous les travailleurs du système sont occupés par leurs propres tâches. Le système d'exécution utilise des bits du champ d'indicateur d'un cadre de pile associé pour évaluer si la synchronisation est nécessaire pour une synchronisation Silk. L'orateur mentionne également plusieurs autres fonctionnalités prises en charge par le système d'exécution, notamment les exceptions C++, les hyper-objets réducteurs et les pedigrees.

OpenCL dans le Trading Tutoriels de programmation Python dans le Trading

MetaQuotes 2023.05.03 17:08 #298

Cours 14. Mise en cache et algorithmes efficaces en cache

Cours 14. Mise en cache et algorithmes efficaces en cache

Dans la vidéo sur la mise en cache et les algorithmes efficaces en matière de cache, l'instructeur explique la hiérarchie des caches des machines modernes, les différences entre les caches mappés entièrement associatifs et directs, ainsi que les avantages et les inconvénients des caches associatifs définis. La vidéo présente également le modèle de cache idéal et le concept d'algorithmes efficaces en matière de cache. L'orateur discute du lemme d'absence de cache, de l'hypothèse de cache grand et du lemme de mise en cache de la sous-matrice. Ils analysent également les échecs de cache lors de la lecture d'une sous-matrice et lors de la multiplication de la matrice. La vidéo se termine en présentant le concept de multiplication matricielle tuilée et comment elle peut améliorer considérablement les performances, mais note également qu'elle n'est pas portable et peut être coûteuse à optimiser pour plusieurs niveaux de cache.

Le cours couvre la mise en cache et les algorithmes efficaces de mise en cache, en utilisant la multiplication matricielle récursive comme exemple. L'orateur souligne l'importance d'analyser séparément les défauts de travail et de cache et note que les algorithmes prenant en charge le cache peuvent ne pas être optimaux pour toutes les machines en raison de tailles de cache différentes. L'orateur discute également des algorithmes inconscients du cache qui s'ajustent automatiquement pour n'importe quelle taille de cache et mentionne les développements dans le code parallèle oublieux du cache. Enfin, l'objectif est de concevoir des algorithmes qui sont soit conscients du cache, soit inconscients du cache, et la discussion sur la conception d'algorithmes inconscients du cache se poursuivra dans la conférence suivante.

00:00:00 Dans cette section sur la mise en cache et les algorithmes efficaces en matière de cache, l'instructeur aborde la hiérarchie des caches des machines modernes, qui comprend des données L1 privées et des caches d'instructions pour chaque processeur, un cache L2 privé et un cache de dernier niveau qui est partagé entre tous les processeurs. La taille de ces caches augmente à mesure que l'on monte dans la hiérarchie de la mémoire, la DRAM étant la plus lente et la plus grande. L'associativité du cache et la latence augmentent également à mesure que l'on monte dans la hiérarchie de la mémoire, le cache L1 étant le plus rapide et le plus associatif. L'instructeur mentionne également l'importance des protocoles de cohérence de cache pour assurer la cohérence des accès aux adresses mémoire pour le traitement parallèle. Comprendre comment tirer parti de la localité dans les programmes peut aider à utiliser efficacement les caches mémoire plus rapides.
00:05:00 Dans cette section, les différences entre les caches mappés entièrement associatifs et directs sont abordées. Un cache entièrement associatif nécessite de rechercher l'intégralité du cache afin de trouver un bloc, ce qui peut être lent et inefficace car la recherche d'un bloc peut nécessiter l'accès à plusieurs lignes. Le cache mappé direct, en revanche, n'a qu'un seul emplacement possible pour chaque bloc, ce qui rend l'accès aux blocs beaucoup plus rapide, avec moins de conflits. Les trois composants de l'espace d'adressage, le décalage, l'ensemble et la balise sont également expliqués lors de la division de l'adresse de mémoire virtuelle pour déterminer l'emplacement du bloc de cache. L'étiquette identifie à quel bloc de mémoire correspond le bloc de cache, et l'ensemble détermine la position dans le cache dans laquelle le bloc va, avec un espace d'adressage total de W bits.
00:10:00 Dans cette section, la vidéo traite des avantages et des inconvénients des caches mappés directs, qui sont rapides car un seul emplacement dans le cache doit être recherché, mais sont sujets à des échecs de conflit où les blocs de cache continuent à s'évincer, réduction des performances. La vidéo présente ensuite les caches associatifs d'ensemble, une solution hybride où chaque ensemble contient plusieurs lignes, permettant plus d'un emplacement possible dans le cache pour chaque bloc de cache. La vidéo mentionne également une taxonomie de différents types d'échecs de cache, y compris les échecs à froid qui se produisent lors du premier accès à un bloc de cache et qui ne peuvent être évités.
00:15:00 Dans cette section, la vidéo traite de différents types d'échecs de cache, y compris les échecs de capacité, les échecs de conflit et les échecs de partage. Les échecs de capacité se produisent lorsque le cache est plein et ne peuvent pas contenir tous les blocs de cache auxquels il faut accéder, tandis que les échecs de conflit se produisent dans les caches associatifs d'ensemble lorsque trop de blocs du même ensemble mappent au cache. Enfin, les échecs de partage se produisent dans un contexte parallèle lorsque plusieurs processeurs accèdent à la même ligne de cache et qu'au moins l'un d'entre eux y écrit. La vidéo fournit également un exemple de mauvais cas de conflit manqué lors de l'accès à une sous-matrice dans une matrice plus grande stockée dans l'ordre principal des lignes.
00:20:00 Dans cette section, l'orateur discute de la mise en cache et des algorithmes efficaces de mise en cache. Ils utilisent un exemple d'accès à une sous-matrice dans une matrice plus grande et comment des échecs de conflit peuvent se produire lorsque le cache n'est qu'associatif à 4 voies. L'orateur suggère d'ajouter une quantité constante d'espace à la fin de chaque ligne de la matrice, de sorte que chaque ligne soit plus longue que 2 ^ 15 octets, ce qui peut aider à réduire les échecs de conflit.
00:25:00 Dans cette section, l'orateur discute du modèle de cache idéal qui est un modèle utilisé pour analyser les performances du cache des algorithmes. Ce modèle suppose une hiérarchie de cache à deux niveaux, un cache entièrement associatif et une politique de remplacement Nishant optimale. L'orateur explique que les deux mesures de performance qui comptent sont l'ordre de N et le nombre d'échecs de cache, où le scénario idéal est d'avoir un faible nombre d'échecs de cache sans augmenter le travail de l'algorithme standard traditionnel. Le lemme LRU , qui a été prouvé en 1985, est également mentionné, qui stipule qu'un algorithme qui entraîne des échecs de cache Q sur un cache idéal de taille M entraînera des échecs de cache 2Q sur un cache entièrement associatif de taille 2M qui utilise la politique LRU.
00:30:00 Dans cette section, l'orateur présente le concept d'algorithmes efficaces en cache et comment ils peuvent améliorer les performances du programme en minimisant le nombre d'échecs de cache. Il explique la politique de remplacement la moins récemment utilisée (LRU), qui stipule qu'un cache entièrement associatif deux fois la taille du cache idéal utilisant LRU n'entraînera pas plus de deux fois le nombre d'échecs de cache. Cela permet une analyse plus facile des échecs de cache lors de l'exécution d'une analyse asymptotique. Le locuteur présente également un lemme de manque de cache, indiquant que si un programme lit un ensemble de segments de données dont la taille est inférieure à un tiers de la taille du cache et dont la taille moyenne est au moins la taille d'une ligne de cache, alors le nombre de le cache manque pour tous les lire est au plus trois fois la taille totale des segments divisée par la taille d'une ligne de cache.
00:35:00 Dans cette section, la vidéo traite de deux hypothèses liées à la mise en cache : le lemme d'absence de cache et l'hypothèse de cache haut. Le lemme d'absence de cache indique que si la longueur moyenne des segments de données est supérieure à la taille d'un bloc de cache, le nombre d'échecs de cache n'augmente que d'un facteur constant. L'hypothèse de cache haut suppose que le cache est plus haut que large et est généralement satisfaite dans la pratique. La vidéo explique également le lemme de mise en cache des sous-matrices, qui traite du problème des caches courts lors de l'ajustement des sous-matrices dans les lignes de cache et explique pourquoi l'hypothèse de cache haut est utile pour résoudre ce problème.
00:40:00 Dans cette section, l'orateur discute de la mise en cache et des algorithmes efficaces de mise en cache. Ils analysent le nombre d'échecs de cache lors de la lecture d'une sous-matrice carrée dans le cache et utilisent le lemme d'échec de cache pour montrer que le nombre d'échecs de cache requis pour lire tous les éléments de la matrice dans le cache est au plus 3n ^ 2 / B . Ils analysent ensuite le nombre d'échecs de cache encourus dans l'algorithme de multiplication de matrice de travail cubique standard, en supposant que la matrice est dans l'ordre majeur des lignes et qu'ils satisfont à l'hypothèse de cache élevé. Ils considèrent trois cas et supposent LRU pour les deuxième et troisième cas, montrant finalement l'importance de l'optimisation du cache dans la conception d'algorithmes.
00:45:00 Dans cette section, le conférencier discute de la mise en cache et des algorithmes efficaces de mise en cache. Ils analysent deux cas de multiplication matricielle, où n est supérieur à M sur B et lorsque n est inférieur à C fois M sur B. Ils utilisent une politique de remplacement LRU et calculent le nombre d'échecs de cache encourus lors de l'accès à la matrice B. Dans le premier Dans ce cas, ils constatent qu'ils ont besoin de thêta de n échecs de cache au cube, ce qui n'apporte aucun gain à la localité dans l'algorithme. Dans le second cas, ils peuvent exploiter la localité spatiale et réduire le nombre d'échecs de cache d'un facteur B, ce qui entraîne un thêta de n au cube sur B échecs de cache, ce qui est plus efficace.
00:50:00 Dans cette section de la vidéo, l'orateur discute de la mise en cache et des algorithmes efficaces en matière de cache. Ils analysent d'abord le cas où la matrice entière rentre dans le cache, ce qui entraîne un nombre total d'échecs de cache de thêta de n au carré sur B. Ils discutent ensuite d'une optimisation en échangeant l'ordre des deux boucles internes pour bénéficier de la localité spatiale et réduire le nombre total d'échecs de cache à thêta de n au cube sur B. Cependant, ils notent qu'il est possible de faire mieux en utilisant une optimisation appelée mosaïque, où six boucles for sont utilisées pour boucler sur les tuiles et le calcul est effectué pour chaque sous -matrice avant de passer à la suivante. Le travail pour une sous-matrice de taille s par s est alors s au cube.
00:55:00 Dans cette section, le concept de multiplication matricielle tuilée est présenté et discuté en détail. Le but de cet algorithme est d'insérer les sous-matrices dans le cache afin que tous les calculs puissent être effectués dans le cache sans plus de ratés de cache. Le nombre d'échecs d'antémémoire est analysé et il s'avère que le nombre d'échecs d'antémémoire est n/s^3 fois s^2/B, pour un total de n^3/B * sqrt(M) échecs d'antémémoire. Ce nombre est très important pour améliorer les performances du code de multiplication matricielle. Cependant, un problème se pose avec l'algorithme : il n'est pas portable car il dépend fortement de la taille du cache de la machine sur laquelle il est exécuté. De plus, l'optimisation du réglage multidimensionnel devient beaucoup plus coûteuse et le code devient plus désordonné lors de l'optimisation pour plusieurs niveaux de cache.
01:00:00 Dans cette section, la conférence explore la mise en cache et les algorithmes efficaces de mise en cache. L'orateur discute des défis liés au réglage des paramètres d'un algorithme efficace en matière de cache et à son optimisation pour une machine particulière. Ils introduisent un algorithme de multiplication matricielle récursive où les matrices d'entrée sont divisées en quatre sous-matrices ou quadrants. Pour chaque quadrant de la matrice de sortie, une somme de deux multiplications matricielles se produit de manière récursive. Enfin, l'orateur analyse le travail de cet algorithme et conclut qu'il s'agit d'une conception plus simple qui maintient toujours de bonnes performances de cache.
01:05:00 Dans cette section, l'orateur discute de la mise en cache et des algorithmes efficaces de mise en cache, et utilise l'exemple de la multiplication matricielle pour expliquer la différence entre l'analyse du travail et les échecs de cache. L'orateur dessine un arbre de récursivité pour visualiser le problème de la taille et des sous-problèmes de branchement, et note que le nombre de niveaux jusqu'aux feuilles est log base 2 de n. Le nombre de feuilles est calculé comme huit au logarithme de base 2 de n, qui est le même que n au cube. La quantité de travail est simplement thêta n au cube, et les échecs de cache sont analysés avec un cas de base différent, où la sous-matrice tient dans le cache, et le thêta de N au carré sur les échecs de cache est utilisé. L'orateur souligne que le nombre de niveaux n'est pas seulement logarithmique de base 2 de n, mais dépend également de la taille du cache, ce qui donne un nombre différent de feuilles, thêta de n au cube sur m aux trois moitiés.
01:10:00 Dans cette section, le conférencier explique comment analyser le nombre de défauts de cache dans un algorithme efficace en cache en utilisant l'exemple d'un code de multiplication matricielle récursive. Le code est inconscient du cache, ce qui signifie qu'il n'a aucune connaissance explicite des caches et qu'il s'auto-ajuste passivement pour la taille de cache particulière de la machine sur laquelle il s'exécute. L'orateur mentionne également que les meilleurs codes inconscients du cache fonctionnent aujourd'hui sur des matrices rectangulaires arbitraires et effectuent une division binaire au lieu d'une division à huit voies. L'orateur discute du contexte parallèle et explique comment analyser le nombre d'échecs de cache dans un calcul de cellule déterministe qui s'exécute sur plusieurs processeurs avec des caches privés.
01:15:00 Dans cette section, l'orateur discute de la mise en cache et des algorithmes efficaces de mise en cache. En minimisant les échecs de cache dans l'illusion en série, nous pouvons essentiellement les minimiser dans l'exécution parallèle pour les algorithmes à faible portée. Le haut-parleur fournit une limite d'absence de cache pour un algorithme de multiplication matricielle récursive parallèle, qui est identique à l'exécution en série. L'objectif est de concevoir des algorithmes qui ont une connaissance explicite du cache ou qui sont inconscients du cache. L'orateur fournit des exemples des deux et mentionne qu'il y aura une discussion plus approfondie sur la conception d'algorithmes sans mémoire cache dans la conférence suivante.

OpenCL dans le Trading Trading Quantitatif Tutoriels de programmation

MetaQuotes 2023.05.03 17:09 #299

Cours 15. Algorithmes Cache-Oblivious

Cours 15. Algorithmes Cache-Oblivious

La vidéo traite des algorithmes sans mémoire cache, qui peuvent automatiquement régler la taille du cache sur une machine, obtenir une bonne efficacité du cache et ne nécessitent pas de connaître les paramètres de cache de la machine. La vidéo montre comment écrire du code pour simuler la diffusion de la chaleur à travers des équations différentielles en utilisant la méthode du pochoir sur une matrice 2D. Le code a à la fois des versions en boucle et trapézoïdales, cette dernière étant plus efficace en termes de cache mais pas beaucoup plus rapide dans une simulation 2D en raison de la prévisibilité du modèle d'accès du code en boucle. La vidéo aborde également l'interaction entre la mise en cache et le parallélisme et le diagnostic des goulots d'étranglement potentiels d'accélération parallèle. Enfin, l'orateur explique les calculs de stencil et comment chaque point d'un tableau est mis à jour à l'aide d'un modèle fixe appelé stencil, qui peut souffrir de défauts de cache et a des besoins de stockage qui peuvent être réduits à l'aide d'algorithmes efficaces exploitant la localité temporelle et spatiale.

La deuxième partie de la vidéo traite des algorithmes sans mémoire cache pour le tri et la fusion. Plus précisément, la vidéo couvre la complexité du cache du tri par fusion, introduit le concept de fusion multivoie et explique la complexité du cache de l'algorithme de fusion multivoie. La vidéo traite également de l'algorithme de tri en entonnoir, qui est un algorithme de tri sans cache qui peut fusionner K éléments au carré et K listes triées. L'algorithme de tri en entonnoir est optimal et construit de manière récursive avec la racine carrée de K entonnoirs. La vidéo explique qu'il existe de nombreux autres algorithmes et structures de données inconscients du cache, tels que les b-trees, la maintenance ordonnée des fichiers et les files d'attente prioritaires. Dans l'ensemble, la vidéo fournit une introduction aux algorithmes sans cache pour ceux qui souhaitent en savoir plus sur le sujet.

00:00:00 Dans cette section, la vidéo traite des algorithmes d'oubli du cache, qui sont un algorithme qui règle automatiquement la taille du cache sur une machine et atteint une bonne efficacité du cache, sans que le code ait besoin de connaître les paramètres de cache de la machine. La vidéo utilise l'exemple de la simulation de la diffusion de la chaleur à travers des équations différentielles pour montrer comment le calcul scientifique s'appuie souvent sur des équations différentielles pour décrire les processus physiques et doit ensuite écrire un code efficace pour simuler le processus. La vidéo montre comment écrire du code basé sur la méthode d'approximation des différences finies pour simuler l'équation de la chaleur 1D.
00:05:00 Dans cette section, l'orateur explique comment écrire du code pour une équation de simulation qui permet une approximation aux différences finies à l'aide de la méthode du pochoir. L'équation utilise des dérivées partielles de U par rapport à T et X, et le conférencier montre comment obtenir ces dérivées partielles en utilisant des méthodes d'approximation. L'espace 2D est représenté à l'aide d'une matrice avec les valeurs X et T représentées horizontalement et verticalement, respectivement. L'orateur explique les limites de la matrice et calcule U à l'aide de l'équation.
00:10:00 Dans cette section, le présentateur explique les calculs au pochoir, une méthode largement utilisée en calcul scientifique à diverses fins. Dans cette méthode, chaque point d'un tableau est mis à jour à l'aide d'un motif fixe appelé gabarit. Le calcul dépend de trois autres valeurs, et c'est ce qu'on appelle une position en trois points. Bien que les calculs de stencil puissent être utilisés pour de grandes valeurs X, les performances peuvent souffrir en ce qui concerne la mise en cache, ce qui entraîne des échecs de cache. De plus, le stockage requis pour stocker les données peut être réduit en ne stockant que deux lignes, l'actuelle et la précédente, pour mettre à jour les valeurs des points.
00:15:00 fonctionne : à chaque pas de temps, nous ne mettons à jour que les valeurs de X pour une ligne spécifique en utilisant les valeurs de la ligne précédente. Ainsi, nous pouvons alterner la ligne que nous mettons à jour et la ligne que nous utilisons comme ligne précédente, et n'avoir besoin de conserver qu'une ligne supplémentaire de valeurs. Cependant, ce code n'est pas très efficace en termes de cache, et nous pouvons le rendre encore plus efficace en utilisant des algorithmes de mosaïque ou d'oubli du cache. Le modèle de cache idéal suppose un cache entièrement associatif avec une politique de remplacement optimale ou LRU, et capture les manques de capacité mais pas les manques de conflit dans une exécution en série. Néanmoins, il est toujours utile pour concevoir des algorithmes efficaces qui exploitent la localité temporelle et spatiale.
00:20:00 Dans cette section, l'orateur explique comment un algorithme sans cache peut être utilisé pour calculer des points à l'intérieur d'un espace trapézoïdal dans une matrice 2D sans regarder à l'extérieur. Le calcul implique une fonction noyau qui prend un pointeur vers UT mod vers X et renvoie W de 0 plus alpha fois W de moins 1 moins 2 fois W de 0 plus W de 1. Le comportement de mise en cache est analysé en supposant la politique de remplacement LRU, et le le nombre d'échecs de cache est Theta de NT sur B pour chaque ligne. Cependant, l'orateur note qu'une meilleure performance peut être obtenue avec la mosaïque, mais il continue de discuter de la version sans cache. Le trapèze a une base supérieure en T1 et une base inférieure en T0. L'algorithme calcule tous les points à l'intérieur du trapèze en utilisant des conditions d'inégalité qui impliquent T, t0, t1, X, x0, x1, DX0, DX1, où DX0 et DX1 sont soit -1, 0 ou 1 représentant des pentes.
00:25:00 Dans cette section, l'orateur décrit une approche diviser pour régner pour l'algorithme de règle trapézoïdale. L'approche a un cas de base où la hauteur du trapèze est 1, et une boucle calcule toutes les valeurs en fonction de l'ordre de calcul. L'algorithme a deux cas récursifs, à savoir la coupe spatiale et la coupe temporelle, qui dépendent respectivement de la largeur et de la hauteur du trapèze. Lorsque le trapèze est trop large, une coupe d'espace est appliquée là où le trapèze est coupé verticalement avec une ligne de pente un moins un passant par le centre du trapèze. En revanche, une coupe temporelle est appliquée lorsque le trapèze est trop grand, et il est coupé avec une ligne horizontale passant par le centre. L'algorithme récursif effectue deux appels qui traversent les côtés gauche et droit du trapèze et le bas et le haut, respectivement, dans un ordre spécifique pour empêcher l'interdépendance entre les points.
00:30:00 Dans cette section, l'orateur discute de la complexité du cache des algorithmes d'oubli du cache. Ils analysent l'approche de l'arbre de récursivité et constatent que l'algorithme se divise en deux sous-problèmes à chaque niveau jusqu'à ce qu'il atteigne le cas de base, qui représente le thêta des points HW où H est thêta de W. Le nombre d'échecs de cache par feuille est thêta W sur B, et le nombre de feuilles est Thêta de NT sur HW. Les nœuds internes ne contribuent pas substantiellement à la complexité du cache. La complexité du cache se généralise à plus d'une dimension, et si d vaut un, il en résulte NT sur Mo.
00:35:00 Dans cette section, l'orateur explique la différence entre le code en boucle et le code trapézoïdal, qui a une bien meilleure complexité de cache en économisant un facteur de M où M est le nombre de lignes de cache. La simulation démontre que le code trapézoïdal subit moins d'échecs de cache par rapport au code en boucle, ce qui permet de terminer le calcul beaucoup plus rapidement. Cependant, l'orateur note que cette simulation ne concernait qu'une seule dimension et poursuit en montrant une démonstration de ce qui se passe en deux dimensions.
00:40:00 Dans cette section, le présentateur fait la démonstration d'une simulation en temps réel de la diffusion de la chaleur dans un espace 2D, où les couleurs à l'écran correspondent aux températures. Le présentateur compare les performances du code en boucle et du code trapézoïdal, et révèle que bien que le code trapézoïdal entraîne beaucoup moins d'échecs de cache, il n'est que légèrement plus rapide que le code en boucle. Il est suggéré que cela pourrait être dû au préchargement matériel aidant le code en boucle, car son modèle d'accès est régulier et facile à prédire.
00:45:00 Dans cette section, l'orateur discute de l'interaction entre la mise en cache et le parallélisme. Ils expliquent un théorème selon lequel la minimisation des échecs de cache dans l'exécution en série peut essentiellement les minimiser dans l'exécution parallèle en supposant un algorithme à faible portée. Ils démontrent ensuite comment l'algorithme trapézoïdal peut fonctionner en parallèle à l'aide d'une coupe en V, où deux trapèzes indépendants s'exécutent en parallèle, et le trapèze gris s'exécute ensuite. Ils mentionnent également la coupe en V à l'envers qui est utilisée pour les trapèzes inversés.
00:50:00 Dans cette section, l'orateur discute des performances du code de boucle parallèle et du code trapézoïdal parallèle par rapport à leurs homologues en série. Le code de bouclage parallèle atteint moins de la moitié de l'accélération potentielle malgré un parallélisme potentiel supérieur à celui du code trapézoïdal. En effet, dans le cas parallèle, il existe un goulot d'étranglement de la bande passante mémoire, ce qui empêche la prélecture d'aider le code de bouclage parallèle, par rapport au cas série où il y a beaucoup de bande passante mémoire. En revanche, le code trapézoïdal atteint une accélération quasi linéaire, ce qui est cohérent avec le fait que l'efficacité du cache joue un rôle beaucoup plus important dans les grandes tailles d'entrée où le cache est si petit, par rapport à la taille d'entrée.
00:55:00 Dans cette section, l'orateur explique comment diagnostiquer un goulot d'étranglement d'accélération parallèle et identifie plusieurs éléments qui pourraient en être la cause, tels qu'un parallélisme insuffisant, une surcharge de planification, un manque de bande passante mémoire et des conflits. Ils suggèrent plusieurs façons de diagnostiquer ces problèmes, notamment l'utilisation de Silk Scale pour mesurer le parallélisme dans le code et l'exécution de compteurs matériels pour mesurer la bande passante mémoire. Cependant, diagnostiquer la contention est particulièrement difficile, et l'orateur conseille d'examiner les trois premières causes potentielles avant d'évaluer si la contention est le problème. Enfin, l'orateur passe à la discussion sur le calcul du stencil.
01:00:00 Dans cette section, l'orateur traite de l'analyse de la complexité du cache du tri par fusion en analysant d'abord la complexité de la fusion de deux tableaux d'entrée triés. Le temps nécessaire pour cela est proportionnel à la somme des tailles des tableaux d'entrée. Le nombre d'échecs de cache subis lors de la fusion de n éléments est thêta n sur B, où B est le nombre d'octets dans une ligne de cache. Le tri par fusion a deux appels récursifs sur des entrées de la moitié de la taille et fusionne les sorties triées de ses appels récursifs. Le travail global du tri par fusion est le thêta de n log n, qui est analysé à l'aide de la méthode de l'arbre de récursivité. La complexité du cache du tri par fusion est également discutée, et il est montré que le nombre d'échecs de cache est proportionnel au nombre de blocs de cache nécessaires pour stocker les données, qui est thêta n sur B log M, où M est la taille maximale a sous-bloc peut avoir.
01:05:00 Dans cette section, l'orateur explique la récurrence de la complexité du cache du tri par fusion. Le cas de base se produit lorsque la taille du problème rentre dans le cache, entraînant Θ(n/B) échecs de cache. Sinon, l'algorithme a deux appels récursifs de taille n/2 et Θ(n/B) manque le cache pour fusionner les résultats. L'analyse porte sur le nombre de niveaux d'un arbre de récurrence, qui est le logarithme de base 2 de n/CM, où CM est une constante. Le nombre d'échecs de cache par feuille est Θ(M/B * n/CM), ce qui donne un nombre total d'échecs de cache de Θ(n/B * log (n/CM)), économisant un facteur B au premier terme . Cependant, pour les problèmes de plus grande taille, nous n'économisons qu'un facteur B par rapport au travail, tandis que nous économisons un facteur B log n pour les problèmes de petite taille. L'orateur demande s'il existe une meilleure solution, et la réponse est toujours oui.
01:10:00 Dans cette section, l'orateur explique comment utiliser la fusion multi-voies pour fusionner des sous-tableaux triés et introduit l'idée d'un arbre de tournoi pour déterminer les éléments minimaux des sous-tableaux. Ils expliquent également les complexités du travail et du cache de cette approche, qui est utilisée dans les algorithmes sans cache pour le tri. La complexité du travail de la fusion multidirectionnelle est la même que celle du tri par fusion binaire, tandis que la complexité du cache est déterminée par le nombre d'échecs de cache requis pour remplir l'arborescence du tournoi et accéder aux tableaux d'entrée, qui peuvent être optimisés si R est inférieur à C*M/B pour une petite constante C.
01:15:00 Dans cette section, l'orateur discute de la complexité du cache de l'algorithme de tri par fusion multivoie et le compare à l'algorithme de tri par fusion binaire. L'algorithme multi-way merge sort consiste à diviser le problème en sous-problèmes de taille n/R et à payer n/B cache miss pour les fusionner. Le nombre de niveaux de l'arbre de récurrence est log base R de n/cm, et la taille des feuilles est cm. Le locuteur définit R égal au thêta de M/B, en le rendant aussi grand que possible, et analyse la complexité du cache, qui s'avère être thêta n log n divisé par B log M. Par rapport à l'algorithme de tri par fusion binaire, le multi L'algorithme de tri de fusion -way permet d'économiser un facteur de journal M dans les échecs de cache. Cependant, l'algorithme n'est pas insensible au cache et la valeur de R doit être ajustée pour une machine particulière, ce qui peut poser problème si d'autres travaux en cours d'exécution sont en concurrence pour le cache.
01:20:00 Dans cette section, l'orateur discute de l'algorithme de tri en entonnoir, qui est un algorithme de tri sans mémoire cache qui peut fusionner K éléments au carré et K listes triées. Le coût de cette fusion s'avère être le même que celui de l'algorithme de tri par fusion à plusieurs voies, mais l'algorithme de tri en entonnoir ne tient pas compte du cache et sa limite est optimale. L'orateur présente une image de ce à quoi ressemble un entonnoir K et explique que l'algorithme est construit de manière récursive avec la racine carrée des entonnoirs K qui alimentent en éléments les tampons, qui, à leur tour, alimentent en éléments la racine carrée de sortie finale de l'entonnoir K, produisant la sortie de l'entonnoir K. L'orateur mentionne également qu'il existe de nombreux autres algorithmes et structures de données inconscients du cache, tels que les b-trees, la maintenance ordonnée des fichiers et les files d'attente prioritaires, et invite les téléspectateurs à en savoir plus à leur sujet en ligne.

OpenCL dans le Trading Tutoriels de programmation Trading Quantitatif

MetaQuotes 2023.05.03 17:10 #300

Cours 16. Programmation parallèle non déterministe

Cours 16. Programmation parallèle non déterministe

Cette vidéo aborde divers concepts liés à la programmation parallèle déterministe et non déterministe. L'orateur insiste sur l'importance d'éviter le non-déterminisme car il peut conduire à des comportements anormaux et à un débogage difficile. Les stratégies de gestion du non-déterminisme comprennent l'utilisation de valeurs fixes, la relecture d'enregistrements, des outils d'analyse, l'encapsulation et les tests unitaires. L'utilisation des mutex est explorée en détail, y compris la rotation par rapport à la production, la réentrante par rapport à la non-réentrante et le juste par rapport à l'injuste. L'orateur aborde également le concept de changement de contexte et le "problème de location de ski" dans le cadre de la programmation parallèle. Le segment se termine par une discussion des principes de base de l'ingénierie des performances dans les processeurs multicœurs.

La deuxième partie de la vidéo aborde le problème du blocage en programmation parallèle et propose des solutions pour l'éviter, comme l'ordre linéaire des mutex qui garantit qu'il n'y a pas de cycle d'attente. De plus, l'orateur introduit le concept de mémoire transactionnelle, qui assure l'atomicité en représentant une région critique comme une transaction qui valide toutes les mises à jour en même temps. La vidéo présente ensuite un algorithme qui utilise une approche basée sur le verrouillage avec un tableau de propriété fini et une méthode de tri des versions requises pour éviter les blocages et la famine sans avoir besoin d'un verrou global. Enfin, l'algorithme release sort and reacquire est expliqué, ce qui empêche plusieurs verrous d'essayer d'acquérir un verrou simultanément, évitant ainsi les problèmes de performances.

00:00:00 Dans cette section, le conférencier présente le concept de déterminisme en programmation et son lien avec le calcul parallèle. Un programme est déterministe si chaque emplacement de mémoire est mis à jour avec la même séquence de valeurs à chaque exécution, et le programme se comporte toujours de la même manière. Les programmes déterministes ont l'avantage d'être reproductibles, ce qui facilite leur débogage. L'enseignant insiste sur l'importance de ne jamais écrire de programmes parallèles non déterministes car ils peuvent présenter des comportements anormaux difficiles à déboguer. Cependant, en pratique, il peut être difficile d'éviter le non-déterminisme dans le calcul parallèle.
00:05:00 Dans cette section, l'orateur discute de la programmation parallèle non déterministe et du fait qu'elle peut parfois conduire à de meilleures performances, mais qu'elle doit toujours être évitée sauf si nécessaire. L'orateur recommande de concevoir une stratégie de test pour gérer le non-déterminisme si vous devez écrire un programme de cette façon. Des exemples de stratégies incluent la désactivation du non-déterminisme, l'utilisation de la même graine pour les nombres aléatoires ou la fourniture de valeurs fixes pour les entrées de programme qui pourraient autrement changer de manière aléatoire. L'orateur souligne l'importance d'avoir un moyen de gérer les bogues dans le programme causés par le non-déterminisme.
00:10:00 Dans cette section, l'orateur parle de stratégies pour gérer la programmation non déterministe, telles que la relecture d'enregistrement, l'encapsulation du non-déterminisme, la substitution d'une alternative déterministe, l'utilisation d'outils d'analyse et les tests unitaires. L'orateur insiste sur l'importance de contrôler le non-déterminisme pour améliorer les chances d'attraper des bogues dans le code. L'orateur fournit également un exemple d'utilisation de l'exclusion mutuelle et de l'atomicité dans une table de hachage pour illustrer comment gérer la programmation non déterministe.
00:15:00 Dans cette section, l'orateur explique comment des instructions parallèles accédant au même emplacement peuvent entraîner des bugs de course et détruire l'intégrité du système. La solution standard consiste à rendre certaines instructions atomiques, ce qui signifie qu'elles sont considérées comme entièrement exécutées ou non exécutées du tout par le reste du système. Pour ce faire, un verrou d'exclusion mutuelle ou un verrou mutex est utilisé, qui est un objet avec des fonctions de membre de verrouillage et de déverrouillage. Chaque emplacement est transformé en une structure avec un verrou mutex et une tête de pointeur vers le contexte de l'emplacement, permettant d'utiliser les fonctions de verrouillage et de déverrouillage avant d'accéder à la liste, garantissant ainsi l'exactitude du système.
00:20:00 Dans cette section, la vidéo explore l'utilisation des mutex pour mettre en œuvre l'atomicité et son lien avec les courses à la détermination. Les verrous mutex peuvent garantir que les sections critiques sont atomiques, mais le code résultant est non déterministe en raison d'une course à la détermination qui peut être ce qui est souhaité dans certains cas. La vidéo souligne l'importance de comprendre la différence entre les courses de données et les courses de détermination, et note que le simple fait d'éliminer les courses de données ne signifie pas nécessairement qu'il n'y a pas de bogues présents dans le code. Il est important d'avoir un moyen de détecter le non-déterminisme afin d'éviter les faux positifs ou les bugs de race manquants dans le code.
00:25:00 Dans cette section, l'orateur explique que l'absence de courses de données ne signifie pas nécessairement que le code n'a pas de bugs. Bien qu'aucune course aux données ne soit un aspect positif du code, l'exemple du verrouillage pour fournir l'atomicité peut conduire à une violation de l'atomicité. De plus, des courses bénignes peuvent se produire, comme lorsque deux processus parallèles accèdent à la même valeur, ce qui peut entraîner le même résultat, mais cela peut également conduire à des valeurs incorrectes sur certaines architectures. L'orateur soutient que si certaines personnes considèrent les races bénignes comme inoffensives, il est toujours essentiel de les identifier et de les éviter.
00:30:00 Dans cette section, l'orateur explique les dangers de la programmation non déterministe, notamment en raison des conditions de concurrence qui peuvent survenir lorsque plusieurs processus tentent de définir des valeurs au même endroit. L'orateur introduit le concept de "Soies", qui permet des courses intentionnelles mais peut être dangereux s'il n'est pas utilisé correctement. La complexité des races peut également rendre le débogage difficile et confondre les outils destinés à aider à détecter le code correct. L'orateur explique également comment la mise en œuvre des mutex et leurs paramètres peuvent affecter leur comportement, par exemple s'ils cèdent ou tournent.
00:35:00 Dans cette section, la vidéo explique trois propriétés de base des mutex en programmation parallèle : rotation contre rendement, réentrant contre non réentrant et juste contre injuste. Le concept de rotation ou de rendement est l'idée qu'un thread ne restera pas inactif et ne vérifiera pas en permanence l'accès à un verrou, mais cédera plutôt le contrôle au système d'exploitation pour une exécution plus efficace. Le mutex réentrant permet à un thread qui détient déjà un verrou de l'acquérir à nouveau tandis que les verrous non réentrants se bloqueront si le thread tente de réacquérir un mutex qu'il possède déjà. Enfin, le mutex équitable garantit que le thread qui a attendu le plus longtemps obtient le verrou en premier pour éviter la possibilité d'un problème de famine. La vidéo fournit également une implémentation d'un simple mutex tournant en langage d'assemblage.
00:40:00 Dans cette section, la vidéo explique l'utilisation du mutex dans la programmation parallèle et pourquoi l'instruction d'échange est utilisée au lieu d'obtenir simplement le mutex. Il est expliqué que l'opération d'échange s'apparente à un droit, et pour exécuter un droit, la ligne de trésorerie sur laquelle il se trouve doit être invalidée sur les autres et détenue dans un état modifié ou exclusif. Cela crée du trafic sur le réseau mémoire et ralentit le processus. D'autre part, en utilisant l'instruction d'échange, les lignes de cache sont mises en état partagé, ce qui maintient le processus plus rapide et génère moins de trafic.
00:45:00 Dans cette section, l'orateur discute de la différence entre un mutex tournant et un mutex cédant. Dans un mutex en rotation, le programme continue de vérifier si le mutex est déverrouillé, tandis que dans un mutex à rendement, le programme cède le contrôle au système d'exploitation, ce qui lui permet de planifier autre chose. L'orateur note qu'il existe également un autre type de mutex appelé mutex compétitif, qui atteint à la fois les objectifs d'un mutex tournant et d'un mutex productif. L'orateur explore également l'utilisation de la transmission de messages ou des interruptions pour informer les threads en attente, mais note que la solution la plus simple serait d'utiliser un mécanisme d'exclusion mutuelle.
00:50:00 Dans cette section, l'orateur explique le concept de changement de contexte, c'est-à-dire la fréquence à laquelle le système d'exploitation bascule entre les threads sur les processeurs disponibles. En règle générale, le système effectue une commutation de contexte environ 100 fois par seconde, ce qui signifie que chaque commutation prend environ 10 millisecondes. Cependant, c'est plus d'un ordre de grandeur supérieur au temps d'exécution d'une instruction simple, ce qui signifie que de nombreuses instructions peuvent s'exécuter avant que le thread n'ait la possibilité de revenir et de saisir un verrou. Ce problème peut être résolu en utilisant une combinaison de filage et de rendement. L'orateur appelle cela le "problème de location de ski" dans la littérature théorique.
00:55:00 Dans cette section, la vidéo traite du processus de décision d'achat ou de location d'équipement pour une tâche particulière, en utilisant l'exemple de l'achat ou de la location d'équipements sportifs. L'orateur encourage les téléspectateurs à considérer les coûts de location par rapport à l'achat et suggère de louer jusqu'à ce que le coût soit égal à celui de l'achat, puis de procéder à l'achat. La vidéo explore également le concept de temps de changement de contexte, le temps d'accès au disque et le problème de blocage lors du maintien de plusieurs verrous à la fois. Dans l'ensemble, ce segment couvre les principes de base de l'ingénierie des performances dans les processeurs multicœurs.
01:00:00 Dans cette section, l'orateur explique le blocage, c'est-à-dire lorsque deux threads contiennent des ressources qui sont toutes deux requises par l'autre thread, entraînant une perte de performances. Il existe trois conditions de base pour un blocage : l'exclusion mutuelle (contrôle exclusif sur les ressources), la non-préemption (ressources conservées jusqu'à la fin) et l'attente circulaire (un cycle de threads attendant les ressources détenues par le suivant). La suppression de l'une de ces contraintes peut résoudre le problème de blocage. L'orateur utilise "Dining Philosophers", une histoire racontée par Tony Hoare basée sur une question d'examen d'Edsger Dijkstra, pour illustrer le problème de l'impasse. L'histoire implique des philosophes assis autour d'une table, mangeant des nouilles avec des baguettes où chaque assiette de nouilles est située entre deux baguettes, et ils ont besoin de deux baguettes pour manger les nouilles. Les philosophes attrapent la baguette à gauche et à droite pour manger leurs nouilles. Cependant, s'ils ramassent tous la baguette gauche sur leur gauche, ils finiront par mourir de faim.
01:05:00 Dans cette section, l'orateur aborde la question de l'interblocage dans la programmation parallèle et propose une solution qui assure la non-préemption tout en évitant l'interblocage : l'ordonnancement linéaire des mutex. En numérotant chaque mutex et en les verrouillant stratégiquement en fonction de leur ordre numérique, les programmeurs peuvent garantir qu'un cycle d'attente (la condition nécessaire au blocage) ne peut pas se produire. Cependant, il avertit les programmeurs d'être conscients de l'encapsulation des verrous par le système d'exécution dans Silk, car l'introduction d'un non-déterminisme supplémentaire via ces verrous peut entraîner des problèmes. Il partage un exemple où un blocage peut se produire avec un seul verrou, soulignant l'importance d'une attention particulière lors de la conception de programmes parallèles.
01:10:00 Dans cette section, l'orateur se penche sur le sujet de la mémoire transactionnelle, une technique récente au niveau de la recherche qui implique d'avoir des transactions de base de données où l'atomicité se produit implicitement, sans qu'il soit nécessaire de spécifier des verrous. L'orateur donne un exemple de l'utilité de la mémoire transactionnelle dans le calcul de graphes simultanés, à savoir l'élimination gaussienne, où l'élimination simultanée de deux nœuds provoque des violations d'atomicité. L'idée derrière la mémoire transactionnelle est de représenter la région critique comme une transaction, et lors de la validation, toutes les mises à jour de la mémoire dans la région critique apparaissent comme si elles se produisaient en même temps.
01:15:00 Dans cette section, l'orateur discute de la résolution des conflits, de la résolution des conflits, de la progression vers l'avant et du débit dans la mémoire transactionnelle. Ils introduisent un algorithme qui utilise une approche basée sur les verrous avec un tableau de propriété fini et une méthode de tri des versions requises pour éviter les blocages et la famine sans avoir besoin d'un verrou global. L'algorithme enregistre les lectures et les écritures pour permettre la restauration ou la validation atomique lorsqu'une transaction est abandonnée. Le tableau de verrouillage est utilisé pour verrouiller un emplacement auquel une fonction de hachage correspond, permettant une acquisition équitable des verrous. Cet algorithme permet des transactions simultanées sans sacrifier les performances ni provoquer de blocages.
01:20:00 Dans cette section, l'orateur discute d'un algorithme appelé release sort and reacquire. L'algorithme fonctionne en essayant avidement d'acquérir un verrou d'un emplacement mémoire, et si un conflit survient, la transaction est annulée sans libérer les verrous qu'elle détient. Ensuite, l'algorithme libère tous les verrous avec des index supérieurs à l'index de l'emplacement auquel il tente d'accéder. Il acquiert ensuite le verrou souhaité et acquiert finalement les verrous libérés dans l'ordre trié. Ce processus est répété jusqu'à ce que la transaction soit réussie. L'algorithme est conçu pour empêcher plusieurs verrous d'essayer d'acquérir un verrou simultanément, ce qui peut entraîner des problèmes de performances.

OpenCL dans le Trading Python dans le Trading Trading Quantitatif

1 ...23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ...75

Nouveau commentaire