Apprentissage Automatique et Réseaux Neuronaux - page 29

[MetaQuotes]

Cours 33. Les réseaux de neurones et la fonction d'apprentissage

33. Les réseaux de neurones et la fonction d'apprentissage

Dans cette vidéo, le conférencier discute de la construction de la fonction d'apprentissage f pour les réseaux de neurones, qui est optimisée par descente de gradient ou descente de gradient stochastique et appliquée aux données d'apprentissage pour minimiser la perte. Il explique l'utilisation d'une image dessinée à la main pour illustrer le concept de réseaux de neurones et la fonction d'apprentissage, ainsi que diverses fonctions de perte utilisées dans l'apprentissage automatique, y compris la perte d'entropie croisée. L'orateur évoque également le problème de la recherche des positions des points compte tenu de leurs distances, qui est un problème classique aux applications diverses, comme par exemple pour déterminer la forme des molécules par résonance magnétique nucléaire. Il conclut en évoquant la construction de X, dernière étape pour obtenir la structure d'un réseau de neurones, et évoque un appel à volontaires pour discuter d'un projet vendredi.

• 00:00:00 Dans cette section, l'orateur discute de la construction de la fonction d'apprentissage f pour les réseaux de neurones, qui est optimisée par descente de gradient ou descente de gradient stochastique et appliquée aux données d'apprentissage pour minimiser la perte. La fonction d'apprentissage est une fonction de deux ensembles de variables, X et V, où X sont les poids et V sont les vecteurs caractéristiques des données d'apprentissage. La structure du réseau neuronal implique de prendre f d'un ensemble de poids et de vecteurs d'échantillons, de produire des étapes non linéaires et de répéter le processus jusqu'à atteindre la sortie souhaitée. L'étape linéaire consiste à prendre l'entrée V0, à la multiplier par des matrices AK et à ajouter des vecteurs de biais BK pour décaler l'origine.
  
  
• 00:05:00 Dans cette section, l'orateur explique comment fonctionnent les réseaux de neurones en prenant un ensemble d'entrées, en appliquant des poids (qui sont choisis à l'aide de la descente de gradient au chapitre 6) et en prenant une étape non linéaire pour produire une nouvelle sortie. Ce processus est répété à travers de nombreuses couches jusqu'à la sortie finale, qui est la prédiction du réseau neuronal pour l'entrée. Le nombre de pondérations peut souvent largement dépasser le nombre d'entités dans l'entrée, créant une situation sous-déterminée.
  
  
• 00:10:00 Dans cette section, l'orateur explique l'utilisation d'une image dessinée à la main pour illustrer le concept de réseaux de neurones et la fonction d'apprentissage. Il dessine une image où il y a un échantillon d'entraînement de composants multiplié par v1, qui est le premier en couche qui peut avoir un nombre différent de neurones dans la première couche, et chacun vient de l'eze by. La fonction de perte est la fonction que nous voulons minimiser en choisissant x2, qui est tous les As et Bs. La fonction de perte est souvent une somme finie sur tout F, qui peut être calculée pour tout I, mais le gradient stochastique est utilisé à la place pour n'en choisir qu'un ou un petit nombre. La fonction de perte serait moins le vrai résultat de l'échantillon I, qui peut être élevé au carré pour obtenir la somme des carrés des erreurs au carré sur tous les échantillons.
  
  
• 00:15:00 Dans cette section, l'orateur discute de diverses fonctions de perte utilisées dans l'apprentissage automatique, en particulier dans les réseaux de neurones. La fonction de perte est une mesure de la correspondance entre la prédiction du réseau neuronal et la valeur réelle. Le haut-parleur fournit quatre fonctions de perte populaires, notamment la perte carrée, la perte L1, la perte de charnière et la perte d'entropie croisée. La perte d'entropie croisée est la plus importante pour les réseaux de neurones et est la fonction de perte la plus couramment utilisée. L'orateur aborde également brièvement les matrices de distance et le processus de détermination des positions des points dans l'espace en utilisant les distances mesurées entre eux.
  
  
• 00:20:00 Dans cette section, l'orateur introduit une question mathématique qui consiste à trouver des positions dans l'espace compte tenu des distances entre les points. La question est simple et a des applications dans divers domaines. La section ne prend que deux pages dans le livre, mais la solution est détaillée et complète. Le conférencier encourage également les étudiants à poser des questions sur leurs projets et suggère de lui envoyer un courriel directement. Il mentionne également une question sur les cours à suivre après celui-ci et demande aux étudiants s'ils prévoient de suivre d'autres cours dans ce domaine. L'orateur reconnaît qu'il existe des cours dans d'autres départements, mais il n'a trouvé une liste que pour le cours six.
  
  
• 00:25:00 Dans cette section, l'orateur parle du Centre de recherche opérationnelle du MIT et de ses offres de cours, y compris l'optimisation, l'analyse de données, les statistiques et la recherche opérationnelle. L'orateur fait également référence à une conférence de Sir Tim Berners-Lee, le créateur du World Wide Web, et sa responsabilité pour les lettres excessives dans les URL. Ensuite, l'orateur discute des matrices de distance et du problème de trouver la matrice de position à partir des distances données. Le conférencier mentionne plusieurs applications, notamment les réseaux de capteurs sans fil, où les distances peuvent être mesurées entre les capteurs, et les systèmes GPS, qui peuvent calculer la position en utilisant un principe similaire.
  
  
• 00:30:00 Dans cette section, l'orateur discute du problème de trouver les positions des points compte tenu de leurs distances, qui est un problème classique avec une solution soignée. Les positions ne sont pas uniques car elles peuvent subir des translations et des rotations, mais l'orateur suggère de supprimer les translations en centrant le barycentre à l'origine. Le problème de la recherche des positions est applicable dans diverses situations, telles que la détermination des formes de molécules à l'aide de la résonance magnétique nucléaire. L'apprentissage automatique peut également être décrit comme la recherche d'une surface de faible dimension dans un espace de grande dimension, ce qui équivaut mathématiquement à la recherche d'une variété courbe qui correspond le mieux aux points donnés. Ce processus implique de découvrir la dimensionnalité du problème et de la linéariser, ce qui réduit la dimensionnalité de l'espace de grande dimension d'origine à la véritable dimensionnalité du problème.
  
  
• 00:35:00 Dans cette section, l'orateur explique comment trouver une matrice X étant donné une matrice de produit scalaire G. Il commence par analyser deux matrices de rang un, l'une dépendant uniquement des lignes et l'autre dépendant uniquement des colonnes, et explique que ces matrices produisent la majeure partie de la partie significative de la matrice du produit scalaire. Ils introduisent ensuite une matrice diagonale avec les produits internes de XI avec lui-même sur la diagonale et notent que cette matrice est liée à la matrice D donnée. À partir de là, ils montrent comment dériver l'équation de la matrice du produit scalaire et expliquent qu'une fois qu'ils ont G, ils peuvent trouver X. Cependant, X n'est pas unique car il peut être tourné sans changer le produit scalaire, donc leur prochaine étape est pour comprendre comment factoriser la rotation.
  
  
• 00:40:00 Dans cette section, l'orateur discute d'une équation liée à la matrice de produit scalaire qui peut être utilisée pour trouver le produit croisé de la matrice d'identité et de la matrice de transposition X dans les réseaux de neurones. La matrice du produit scalaire est une combinaison de la matrice D diagonale, d'une matrice constante avec toutes les lignes identiques et d'une matrice constante avec toutes les colonnes identiques. L'orateur parcourt l'équation étape par étape et décompose chaque composant pour révéler que la matrice X transposée X provient de ces endroits de rang 1 et de ces produits croisés. Ils explorent ensuite la signification de la moitié dans l'équation mais concluent finalement qu'il est nécessaire d'obtenir le bon résultat.
  
  
• 00:45:00 Dans cette section, l'orateur explique comment écrire une équation donnée en langage matriciel et comment trouver finalement la matrice X étant donné X transposer X. Ils utilisent l'algèbre linéaire pour trouver la solution et notent que X peut être trouvé jusqu'à à une transformation orthogonale. Les deux principales méthodes abordées sont l'utilisation des valeurs propres ou l'élimination sur X transpose X. L'intervenant souligne l'importance de ces méthodes dans le domaine des réseaux de neurones et de l'apprentissage automatique.
  
  
• 00:50:00 Dans cette section, l'orateur discute de la construction de X, qui est symétrique et semi-définie positive, et de deux manières de la trouver. La première approche est la construction des valeurs propres, qui consiste à calculer les valeurs propres et les vecteurs propres de X transposer X, puis à conserver les vecteurs propres tout en prenant les racines carrées des valeurs propres. La deuxième approche est la factorisation de Cholesky, qui consiste à effectuer une élimination sur la matrice définie positive symétrique, puis à utiliser la matrice triangulaire inférieure résultante L et la matrice diagonale D pour calculer X comme le produit de L racine carrée DL transposée. La factorisation de Cholesky est plus rapide que la construction des valeurs propres et plus facile à calculer, ce qui en fait une option plus pratique.
  
  
• 00:55:00 Dans cette section, l'orateur conclut la discussion sur les matrices de distance, qui était l'étape finale pour obtenir la structure d'un réseau de neurones, en séparant les vecteurs échantillons des poids. L'orateur mentionne également les deux morceaux de l'algèbre linéaire : trouver des choses pour les réduire à une forme triangulaire ou pour les relier à des matrices symétriques. Enfin, l'orateur évoque un appel à volontaires pour discuter d'un projet vendredi.

[MetaQuotes]

Cours 34. Matrices de distance, problème de Procuste

34. Matrices de distance, problème de Procuste

L'orateur discute du problème de Procuste, qui consiste à trouver la meilleure transformation orthogonale qui rapproche le plus possible un ensemble de vecteurs d'un autre ensemble de vecteurs. Ils expliquent différentes expressions pour calculer la norme de Frobenius d'une matrice de distance et sa connexion au problème de Procuste. L'orateur introduit également le concept de la trace des matrices et trouve le bon Q dans le problème de Procuste. De plus, ils abordent la question de savoir si l'apprentissage en profondeur fonctionne réellement et présentent la solution à un problème matriciel impliquant de trouver la meilleure matrice orthogonale, ce qui implique de calculer le SVD du produit scalaire de deux matrices et d'utiliser les matrices orthogonales du SVD.

• 00:00:00 Dans cette section, l'orateur aborde une question soulevée dans une discussion précédente sur la recherche de points qui satisfont une matrice de distance donnée, et comment résoudre l'échec de l'inégalité triangulaire. L'orateur explique que la matrice des produits scalaires qui provient directement de la matrice des distances est semi-définie positive, mais si l'inégalité triangulaire échoue, la matrice des produits scalaires ne sortira pas définie positive. Ce problème ne peut pas être résolu en modifiant les dimensions, car l'inégalité triangulaire est toujours valable quelle que soit la dimensionnalité.
  
  
• 00:05:00 Dans cette section, le conférencier parle du problème de Procuste, qui consiste à faire correspondre quelque chose à autre chose. Le problème tire son nom d'un mythe grec sur Procuste qui avait un lit d'une certaine longueur et ajustait la longueur du visiteur pour s'adapter au lit. Le problème consiste à trouver un moyen d'ajuster deux ensembles de données ensemble, et le conférencier explique que si l'inégalité triangulaire est satisfaite par les nombres dans la matrice de distance, la matrice qui sort de l'équation est semi-définie positive. Cependant, si l'inégalité triangulaire est violée, la matrice n'est pas semi-définie positive et a des valeurs propres négatives, et il est impossible de trouver le point. Le conférencier fait également allusion à une grande question de savoir si l'apprentissage en profondeur fonctionne réellement, qu'il abordera plus tard.
  
  
• 00:10:00 Dans cette section, le problème de Procuste est discuté, qui consiste à trouver la meilleure transformation orthogonale qui amène un ensemble de vecteurs aussi près que possible d'un autre ensemble de vecteurs. Si les deux ensembles de vecteurs étaient tous les deux des bases orthogonales, il serait facile de les ramener l'un dans l'autre avec une matrice orthogonale Q, mais ce n'est pas toujours le cas. Par conséquent, le problème est de minimiser sur toutes les matrices orthogonales Q dans la norme de Frobenius au carré, et de traiter la matrice comme un long vecteur. Une façon de faire est de regarder une transposée a, d'en prendre la trace, puis de trouver la somme de tous les carrés pour obtenir la norme de Frobenius d'une matrice.
  
  
• 00:15:00 Dans cette section, le conférencier discute de différentes expressions pour calculer la norme de Frobenius d'une matrice de distance. Ils montrent que la norme de Frobenius au carré peut s'exprimer comme la somme des carrés de toutes les valeurs singulières, comme la trace du produit de la matrice et de sa transposée, ou la trace du produit de la transposée de la matrice et de la matrice elle-même . Ils expliquent ensuite comment ces expressions sont liées les unes aux autres et mentionnent que la résolution de ce problème nécessite divers faits importants, tels que le fait que multiplier chaque colonne d'une matrice par Q ne change pas la norme de Frobenius, et multiplier la matrice par Q ne change pas. t affecter les valeurs singulières.
  
  
• 00:20:00 Dans cette section, l'orateur discute des propriétés de la norme de Frobenius, y compris le fait qu'elle reste inchangée lorsqu'elle est multipliée par un facteur orthogonal ou lorsqu'elle est multipliée de l'autre côté par le même facteur ou un facteur différent. L'orateur introduit également le concept de la trace des matrices, soulignant le fait que la trace ne change pas lorsque l'ordre des matrices est inversé. L'orateur explique ensuite les étapes pour obtenir le bon Q dans le problème de Procuste.
  
  
• 00:25:00 Dans cette section, l'orateur discute de la question de savoir si l'apprentissage en profondeur fonctionne réellement et suggère qu'il s'agit d'une question importante à aborder. Ils mentionnent que bien qu'il y ait eu beaucoup de publicité et de battage médiatique autour de l'apprentissage en profondeur et des réseaux de neurones, il n'est pas automatique que la structure du réseau réussisse, même avec plusieurs couches. L'orateur présente ensuite la solution d'un problème matriciel impliquant de trouver la meilleure matrice orthogonale, ce qui implique de calculer la SVD du produit scalaire de deux matrices, et d'utiliser les matrices orthogonales de la SVD.

[MetaQuotes]

Cours 35. Trouver des clusters dans les graphes

35. Trouver des clusters dans les graphiques

Cette vidéo traite du clustering dans les graphiques et de la manière de trouver des clusters à l'aide de différents algorithmes tels que K-means et le clustering spectral. La matrice laplacienne est utilisée dans le clustering spectral et peut fournir des informations sur les clusters dans le graphique via ses vecteurs propres. Le vecteur propre de Fiedler, qui est le vecteur propre de la plus petite valeur propre positive, est important pour le regroupement. L'orateur souligne également l'importance que les vecteurs propres soient orthogonaux pour identifier les différents clusters. De plus, il y a un bref aperçu de la prochaine conférence, qui couvrira la rétro-propagation à l'aide de Julia en algèbre linéaire. Les étudiants sont encouragés à soumettre leurs projets en ligne ou à l'extérieur du bureau de l'instructeur.

• 00:00:00 Dans cette section, l'orateur discute du regroupement dans les graphiques, qui est le processus de subdivision d'un grand graphique en groupes plus petits et plus gérables. Le problème est de trouver deux clusters de taille raisonnablement égale, et pour ce faire, un algorithme doit être utilisé pour déterminer la position des points centraux X et Y. L'objectif est de minimiser la somme des distances entre les points centraux et le nœuds dans le graphe, tout en s'assurant que le nombre de nœuds dans chaque cluster est raisonnablement proche. Il existe plusieurs algorithmes qui peuvent être utilisés pour accomplir cela, y compris certains qui utilisent des matrices associées au graphique.
  
  
• 00:05:00 ans cette section, l'orateur discute de l'algorithme de clustering K-means pour diviser un ensemble de points, certains étiquetés A et d'autres étiquetés B, en clusters ou groupes. L'algorithme commence par identifier les centroïdes, qui sont les points médians des groupes A et B, puis tente de former les meilleurs clusters en fonction de ces centroïdes. Ce processus est répété jusqu'à ce que l'algorithme converge vers les meilleurs clusters possibles pour les données. L'orateur introduit également le concept de centroïde, qui est le point qui minimise la somme des distances entre tous les points du groupe et le centroïde.
  
  
• 00:10:00 Dans cette section, l'instructeur discute de deux méthodes pour résoudre le problème de recherche de clusters dans les graphiques. La première méthode est appelée K-means, qui consiste à trouver le centroïde de cluster le plus proche pour chaque point, à réaffecter les points à leurs clusters respectifs et à répéter le processus jusqu'à convergence. La deuxième méthode est appelée regroupement spectral et consiste à utiliser les valeurs propres d'une matrice pour regrouper des points similaires. Le terme "spectral" fait référence aux valeurs propres de la matrice et au théorème spectral en algèbre linéaire. L'instructeur insiste sur le fait que le théorème spectral s'applique aux matrices symétriques et indique que les valeurs propres sont réelles et que les vecteurs propres sont orthogonaux.
  
  
• 00:15:00 Dans cette section, l'orateur discute de la matrice laplacienne graphique, qui est le lien clé entre l'algèbre linéaire et la théorie des graphes. Ils décrivent cette matrice comme une matrice semi-définie positive symétrique, et il y a quatre matrices associées à tout graphe : la matrice d'incidence, la matrice de degré, la matrice d'adjacence et la matrice laplacienne. L'orateur réalise un exemple à l'aide d'un graphique simple pour expliquer chacune de ces matrices. La matrice laplacienne est utilisée dans le regroupement spectral et peut avoir des vecteurs propres orthogonaux qui vont avec une multiplicité de valeurs propres, connue sous le nom de théorème spectral.
  
  
• 00:20:00 Dans cette section, l'orateur explique le concept de regroupement de graphes en trouvant des clusters dans un graphe donné à l'aide de la matrice laplacienne. La matrice laplacienne est obtenue en soustrayant la matrice d'incidence de la matrice des degrés. La matrice résultante est semi-définie positive et ses vecteurs propres fournissent des informations sur les clusters du graphique. La première valeur propre est toujours zéro et la valeur propre suivante est importante pour le clustering. L'orateur souligne l'importance du vecteur de Fiedler, le vecteur propre de la plus petite valeur propre positive, et explique sa signification dans le regroupement de graphes.
  
  
• 00:25:00 Dans cette section, l'orateur explique pourquoi la matrice laplacienne est nommée ainsi lors de la recherche de clusters dans un graphique. La matrice laplacienne a une diagonale de degré 4 et permet de trouver des clusters à travers ses vecteurs propres. Plus précisément, le vecteur propre de Fiedler peut déterminer les composantes positives et négatives partitionnant le graphique en deux groupes. Cette approche fournit une méthode pour décider quels nœuds appartiennent à quel cluster en utilisant le graphe Laplacien.
  
  
• 00:30:00 Dans cette section, l'orateur discute du regroupement dans les graphiques et de la manière de trouver des clusters à l'aide de différents algorithmes tels que les k-moyennes et le regroupement spectral. Il explique que les vecteurs propres d'une matrice symétrique sont orthogonaux, ce qui signifie qu'ils totalisent zéro, ce qui peut être utilisé pour identifier différents clusters. Il mentionne également qu'il existe d'autres algorithmes proposés pour le même problème, et donne un bref aperçu de la prochaine conférence qui couvrira la rétro-propagation en utilisant Julia en algèbre linéaire. Le conférencier encourage les étudiants à soumettre leurs projets en ligne ou à l'extérieur de son bureau.

[MetaQuotes]

Cours 36 : Alan Edelman et Julia Language

Cours 36 : Alan Edelman et Julia Language

Dans cette vidéo, Alan Edelman discute de la puissance des langages de programmation pour l'apprentissage automatique et de leur importance en mathématiques. Il met en avant le développement récent du langage Julia, reconnu par Google, pour ses mérites techniques et sa facilité d'utilisation en machine learning. Edelman explique comment fonctionne la différenciation automatique dans Julia et donne un exemple de calcul de la racine carrée de x sans utiliser de différences finies numériques via l'algorithme babylonien. Il discute également de l'utilisation des types dans Julia pour un calcul efficace et pour simplifier le processus de rétropropagation avec des matrices de blocs. Dans l'ensemble, Edelman souligne l'importance de l'algèbre linéaire pour les calculs mathématiques et son rôle dans la compréhension des phénomènes complexes.

• 00:00:00 Dans cette section, Alan Edelman discute d'une démonstration du professeur Strang sur le rang de ligne égal au rang de colonne et comment ce concept s'applique à la matrice zéro. Il parle ensuite des développements récents de Julia, un langage de programmation qui gagne du terrain dans l'apprentissage automatique, et comment Google a reconnu sa puissance dans ce domaine. Google a récemment publié un article de blog indiquant qu'il n'y a que deux langages suffisamment puissants pour l'apprentissage automatique, et Julia en fait partie. Edelman fournit des exemples pour illustrer ce point et encourage les étudiants à consulter le blog pour plus d'informations.
  
  
• 00:05:00 Dans cette section, Alan Edelman discute de l'importance des langages de programmation au sens mathématique et de leur capacité à faire plus que simplement implémenter des algorithmes. Il explique que Julia, Swift, C++ et Rust sont les quatre langages de programmation jugés appropriés pour l'apprentissage automatique en fonction de leurs mérites techniques et de leur convivialité. Edelman souligne l'importance de l'algèbre linéaire comme base de tous les cours d'ingénierie et son regrettable retard dans l'histoire. Il se penche ensuite sur la différenciation automatique et son lien avec le calcul, son scepticisme initial à son égard et les détails techniques qu'il a explorés dans son cahier sur la différenciation automatique en mode direct.
  
  
• 00:10:00 Dans cette section, Alan Edelman discute de ses réflexions initiales sur la différenciation automatique et comment il pensait que c'était comme le calcul qu'il avait appris à l'école, mais avec un ordinateur. Cependant, il s'est vite rendu compte qu'il existait une troisième méthode qui n'était ni les différences finies ni la règle de la chaîne, ce qui le fascinait. Il partage ensuite un exemple de la façon dont il a calculé la racine carrée de x en utilisant l'algorithme babylonien dans Julia, et comment il a pu obtenir la dérivée de la racine carrée sans taper explicitement la formule dérivée, grâce à la fonction de différenciation automatique de Julia.
  
  
• 00:15:00 Dans cette section, l'orateur décrit l'utilisation du code Julia pour calculer la racine carrée d'un nombre sans utiliser de calculs de différences finies. Le code crée un type de variable appelé "nombre double" qui est une paire de flottants représentant une fonction numérique et sa dérivée. Le locuteur surcharge ensuite les opérations de plus et de division pour implémenter la règle du quotient, permettant le calcul de la racine carrée à l'aide de l'algorithme babylonien. Le code fonctionne sans l'utilisation de différences finies numériques, et l'orateur note que Julia permet la réutilisation du code existant dans de nouveaux contextes pour effectuer de la "magie".
  
  
• 00:20:00 Dans cette section, Alan Edelman explique comment le langage de programmation Julia peut calculer efficacement la dérivée à l'aide de l'algorithme babylonien sur un nombre double en code assembleur. Il montre comment le même code exécuté dans le package de calcul symbolique de Python donne un calcul symbolique avec de gros coefficients, ce qui est très inefficace. Il révèle ensuite le SVD, un autre algorithme qui l'a convaincu du fonctionnement de l'algorithme babylonien. En prenant la dérivée de chaque ligne du code, l'algorithme peut converger vers la racine carrée et la dérivée des racines carrées. La dérivée résultante n'est ni symbolique ni numérique, mais utilise la règle du quotient et la règle d'addition à chaque étape pour obtenir la réponse.
  
  
• 00:25:00 Dans cette section, Alan Edelman, le créateur du langage Julia, explique comment la différenciation automatique fonctionne dans le langage. Au lieu de prendre manuellement les dérivées de chaque ligne, Edelman suggère que le logiciel puisse le faire automatiquement en laissant le compilateur JIT le gérer. Cela élimine le besoin d'écrire un traducteur ou une écriture manuscrite, ce qui rend le codage beaucoup plus simple. Edelman note que l'apprentissage automatique s'appuie fortement sur des problèmes d'optimisation, qui consistent tous à prendre des dérivés, faisant de la différenciation automatique un élément essentiel du processus. Enfin, il explique comment l'utilisation de types peut simplifier la création de matrices structurées pour stocker des données.
  
  
• 00:30:00 Dans cette section, Alan Edelman discute de l'utilisation des types dans Julia pour stocker efficacement uniquement ce qui est nécessaire lors de l'exécution de calculs, ce qui le distingue des langages comme Python et MATLAB qui ont plus de surcharge. Il aborde ensuite brièvement l'idée de différenciation des modes immergés dans les réseaux de neurones, en partant d'un exemple scalaire et en généralisant aux matrices et aux vecteurs. Il écrit l'algèbre linéaire impliquée dans ce processus, mais manque de temps avant de pouvoir l'expliquer complètement.
  
  
• 00:35:00 Dans cette section, Edelman explique comment utiliser les matrices de blocs dans Julia pour effectuer une rétropropagation sans avoir à calculer manuellement les dérivées. Il montre comment l'utilisation d'une matrice diagonale et d'une matrice triangulaire inférieure peut simplifier le processus de rétropropagation et utiliser les fonctions intégrées de Julia. En utilisant l'algèbre linéaire, il démontre comment une barre oblique inverse peut résoudre la matrice triangulaire inférieure, ce qui facilite grandement le calcul des dérivées. Edelman souligne que l'algèbre linéaire est essentielle pour de nombreux calculs mathématiques, et c'est le secret de la compréhension de nombreux phénomènes complexes.

[MetaQuotes]

MIT 6.172 Ingénierie des performances des systèmes logiciels, automne 2018 - 1. Introduction et multiplication matricielle

1. Introduction et multiplication matricielle

Dans cette vidéo YouTube intitulée "1. Introduction et multiplication matricielle", le conférencier discute de l'importance de l'ingénierie de la performance et de son évolution au fil du temps. En utilisant l'exemple de la multiplication matricielle, l'orateur montre comment les techniques de codage et les spécifications de la machine peuvent avoir un impact important sur les performances. La discussion couvre des sujets tels que l'ordre des boucles, l'utilisation du cache et la programmation parallèle. Le conférencier explore également les moyens d'optimiser le code pour différents processeurs et calculs arithmétiques. Dans l'ensemble, la vidéo fournit des informations précieuses sur le monde de l'ingénierie des performances et ses applications pratiques dans les systèmes informatiques modernes.

• 00:00:00 Dans cette section, le conférencier discute de l'importance de l'ingénierie de la performance et pourquoi elle est étudiée. La performance n'est pas toujours la priorité absolue en matière de développement de logiciels. Cependant, c'est la monnaie de l'informatique et elle est utilisée pour acheter d'autres propriétés souhaitées telles que la facilité de programmation, la sécurité et l'exactitude. La dégradation des performances peut rendre les logiciels inutilisables, et la principale plainte des utilisateurs à propos des systèmes informatiques est qu'ils sont trop lents. Par conséquent, même si les performances n'ont pas de valeur intrinsèque, elles contribuent aux choses qui intéressent les développeurs.
  
  
• 00: 05: 00 Dans cette section, l'orateur discute de l'histoire de l'ingénierie des performances en informatique et du passage des premiers jours d'une ingénierie des performances intense en raison de ressources machines limitées à l'ère de la loi de Moore où les densités de puces doublaient tous les deux ans et attendaient pour que le matériel rattrape était plus avantageux que l'optimisation du logiciel. Cependant, l'orateur note que la mise à l'échelle de Dennard, qui permettait d'augmenter les vitesses d'horloge en réduisant la puissance, a pris fin en 2004 et que le besoin d'ingénierie des performances est donc plus important que jamais. L'orateur inclut des citations d'informaticiens Donald Knuth, Bill Wolfe et Michael Jackson sur l'importance d'un code lisible et sur la mise en garde contre une optimisation prématurée.
  
  
• 00: 10: 00 Dans cette section, l'orateur discute des limites des vitesses d'horloge qui ont été atteintes au début des années 2000 en raison de la densité de puissance, ce qui a entraîné le développement de processeurs multicœurs pour faire évoluer les performances. Cependant, cela signifiait que la performance n'était plus gratuite et nécessitait une programmation parallèle, ce que l'industrie n'avait pas fait auparavant. À partir de ce moment, les logiciels ont dû s'adapter aux nouvelles configurations matérielles pour être efficaces et, par conséquent, l'accent a été mis sur les performances dans les travaux de développement de logiciels.
  
  
• 00:15:00 Dans cette section, l'orateur commence par expliquer l'importance pratique et théorique d'apprendre à écrire des logiciels qui utilisent efficacement le matériel moderne. Ils fournissent ensuite un exemple d'ingénierie des performances utilisant le problème bien étudié de la multiplication matricielle, discutant de la machine qu'ils utiliseront, y compris ses spécifications et capacités telles que le traitement parallèle, la taille du cache et la capacité de la mémoire, et concluant par une explication de le code de base de Python pour la multiplication matricielle. L'orateur met l'accent sur la puissance de la machine et le potentiel de projets amusants qui utilisent ses capacités.
  
  
• 00:20:00 Dans cette section, le conférencier discute des performances de Python, Java et C++ dans le contexte de la multiplication matricielle. La conférence démontre que Python est trop lent pour la multiplication de grandes matrices, avec un temps d'exécution d'environ 21 000 secondes, Java est plus rapide et produit une accélération presque neuf fois supérieure à Python, et C++ est le plus rapide avec un temps d'exécution d'environ 1 100 secondes. , qui est deux fois plus rapide que Java et 18 fois plus rapide que Python.
  
  
• 00: 25: 00 Dans cette section, l'orateur discute des différences de performances entre les langages interprétés comme Python, les langages compilés comme C et les langages comme Java qui sont compilés en bytecode puis interprétés. Les interpréteurs comme Python sont polyvalents mais lents, tandis que les compilateurs comme C tirent parti des instructions matérielles et machine pour optimiser les performances. Les compilateurs JIT, comme ceux utilisés en Java, récupèrent certaines performances en ne compilant que les morceaux de code les plus fréquemment exécutés. L'orateur note que le modèle de performance de Python est difficile à comprendre, c'est pourquoi ils utiliseront C pour les comparaisons de performances dans le cours. Cependant, il y aura une conférence invitée où ils discuteront de l'ingénierie des performances dans des langages gérés comme Python.
  
  
• 00:30:00 Dans cette section, l'importance de l'ordre des boucles pour les performances dans la multiplication matricielle est abordée. L'ordre des boucles affecte la localité du cache qui a un impact sur le temps d'exécution. Les matrices sont disposées en mémoire dans l'ordre des lignes majeures en C et dans l'ordre des colonnes majeures en Fortran. Le modèle d'accès pour l'ordre ijk a une bonne localité spatiale pour C mais une mauvaise localité spatiale pour B. L'outil "cachegrind" est utile pour déterminer les taux d'échec pour le code, et des changements simples tels que l'ajustement des drapeaux du compilateur peuvent également améliorer les performances.
  
  
• 00:35:00 Dans cette section, le conférencier explique comment optimiser le code pour obtenir de meilleures performances d'une machine. Il est important de choisir un bon indicateur d'optimisation, tel que -O2 ou -O3, mais parfois un indicateur d'optimisation inférieur peut en fait mieux optimiser en fonction du code. De plus, les processeurs multicœurs peuvent être utilisés avec des boucles parallèles utilisant l'infrastructure en soie, ce qui entraîne une accélération de près de 18 fois sur 18 cœurs. L'orateur souligne que la parallélisation des boucles externes est plus efficace que la parallélisation des boucles internes, ce qui peut en fait ralentir le programme. Cependant, il existe encore des sources d'opportunités d'optimisation, telles que les échecs de cache et la non-utilisation efficace des instructions vectorisées.
  
  
• 00:40:00 Dans cette section, l'orateur explique comment mieux gérer les cache miss en restructurant le calcul pour réutiliser au maximum les données du cache. En utilisant un schéma de tuilage, les matrices sont divisées en sous-matrices plus petites et multipliées en blocs pour réduire le nombre d'accès mémoire nécessaires. L'orateur explique qu'un paramètre de réglage est nécessaire pour déterminer la taille des sous-matrices et suggère que l'expérimentation est le meilleur moyen de trouver la valeur optimale. Grâce à cette approche, le conférencier démontre qu'il est possible de réduire considérablement le nombre d'accès mémoire nécessaires pour calculer la même taille d'empreinte, rendant le calcul plus efficace.
  
  
• 00: 45: 00 Dans cette section, l'orateur discute des avantages de l'utilisation du blocage ou de la mosaïque lors de l'exécution de la multiplication matricielle, tels qu'une utilisation améliorée du cache et une exécution plus rapide. Ils expliquent les différents niveaux de caches des puces et comment les programmeurs peuvent utiliser des paramètres de réglage pour optimiser leur code pour chaque niveau de cache. Cependant, le processus de réglage devient plus complexe avec chaque niveau de cache, et le code peut devenir difficile à lire et à comprendre. L'orateur suggère une approche diviser pour mieux régner qui utilise la programmation parallèle pour résoudre de manière récursive des sous-problèmes plus petits. Bien que cette méthode améliore l'utilisation du cache, la surcharge des appels de fonction ralentit le calcul, soulignant la nécessité d'une ingénierie intelligente des performances.
  
  
• 00: 50: 00 Dans cette section, l'orateur discute de l'optimisation de la multiplication matricielle à l'aide de la technique diviser pour mieux régner et de l'ajustement du seuil d'utilisation de l'algorithme. Un cas de base est défini lorsque le seuil est inférieur à un certain nombre et l'algorithme utilise une multiplication matricielle ordinaire. La meilleure valeur pour le cas de base s'est avérée être 32, ce qui a entraîné une durée d'exécution de 1,3 seconde et 12 % de performances de pointe. De plus, l'orateur introduit le concept de vectorisation à l'aide du matériel vectoriel, qui traite les données dans une seule instruction, plusieurs formats de données. L'orateur décrit différentes manières d'optimiser la vectorisation, y compris l'utilisation de rapports de vectorisation, d'indicateurs pour des architectures spécifiques et de l'indicateur mathématique rapide, qui permet au compilateur de réorganiser les associations. L'utilisation de mathématiques natives et rapides pour l'architecture double les performances lors de l'utilisation de n'importe quel vectoriseur de compilateur.
  
  
• 00: 55: 00 Dans cette section de la vidéo, l'orateur discute des différentes tailles de bits utilisées pour les calculs arithmétiques, le 64 bits étant le plus courant pour les calculs d'algèbre linéaire. Ils mentionnent également que l'arithmétique de moindre précision peut être utilisée pour les applications d'IA afin d'améliorer les performances. L'orateur poursuit en parlant de l'utilisation des instructions vectorielles et des intrinsèques AVX, qui offrent jusqu'à 41 % de performances de pointe et une accélération d'environ 50 000. Ils avertissent que des améliorations de performances similaires à celles obtenues dans la multiplication matricielle peuvent ne pas être observées dans d'autres domaines, mais ce cours apprendra aux étudiants comment obtenir eux-mêmes des améliorations substantielles de performances. De plus, le cours se concentrera sur l'informatique multicœur plutôt que sur les GPU ou d'autres domaines.

[MetaQuotes]

Cours 2. Règles de Bentley pour optimiser le travail

2. Règles de Bentley pour optimiser le travail

Cette vidéo YouTube traite de diverses techniques d'optimisation pour les programmes informatiques. Les règles de Bentley pour l'optimisation du travail sont introduites et les optimisations sont regroupées en structures de données, boucles, logique et fonctions. Différentes techniques telles que l'encodage des valeurs, l'augmentation de la structure des données, le pré-calcul, la mise en cache et l'utilisation de matrices creuses sont discutées. Le conférencier aborde également les avantages de l'utilisation d'une représentation matricielle creuse pour les graphiques, l'optimisation logique et l'optimisation de la détection des collisions dans les programmes graphiques. La mise en œuvre de ces techniques d'optimisation permet de réduire le temps d'exécution des programmes, les rendant plus efficaces.

La deuxième partie de la vidéo couvre plusieurs catégories de techniques d'optimisation, notamment le levage de boucles, l'utilisation de sentinelles dans les boucles, le déroulement et la fusion de boucles et l'inlining de fonctions. L'orateur déconseille une optimisation prématurée et souligne l'importance de maintenir l'exactitude et d'utiliser des tests de régression. La vidéo décrit également les règles Bentley pour l'optimisation du travail, un guide en six étapes pour augmenter la productivité et atteindre les objectifs de manière efficace. Ces règles comprennent l'établissement d'objectifs clairs, la répartition des tâches, la planification et l'organisation, la hiérarchisation des tâches, la minimisation des distractions et la révision et l'ajustement réguliers de son approche.

• 00:00:00 Dans cette section, le conférencier introduit le concept d'optimisation du travail dans les programmes informatiques et explique comment la réduction du travail d'un programme peut améliorer ses performances. Il parle également des règles de Bentley pour optimiser le travail, du nom de John Lewis Bentley, qui a écrit un livre sur l'écriture de programmes efficaces. Les optimisations sont regroupées en quatre catégories : structures de données, boucles, logique et fonctions, et le conférencier prévoit de couvrir les 22 règles dans une série de mini-conférences tout au long du cours. Bien que la réduction du travail d'un programme soit une bonne heuristique pour améliorer son temps d'exécution, la nature complexe du matériel informatique signifie qu'elle ne se traduit pas toujours par une réduction du temps d'exécution, de sorte que le conférencier couvrira également les optimisations spécifiques à l'architecture plus tard dans le cours. cours.
  
  
• 00:05:00 Dans cette section de la vidéo, l'orateur aborde le concept de conditionnement et d'encodage des structures de données pour stocker plusieurs valeurs de données dans un mot machine et convertir les valeurs de données en une représentation nécessitant moins de bits. En réduisant le nombre de choses à déplacer en mémoire, cela devient une bonne heuristique pour diminuer le temps d'exécution d'un programme. L'orateur fournit un exemple d'encodage des dates pour les stocker en utilisant moins de bits afin de faciliter la récupération du mois, de l'année ou du jour pour une date spécifique. L'orateur suggère d'utiliser les installations de champs de bits en C pour stocker les données structurées, les rendant plus accessibles. Cette représentation nécessite un peu plus de bits mais est beaucoup plus efficace pour accéder à des valeurs de données spécifiques au sein de la structure.
  
  
• 00:10:00 Dans cette section, la vidéo traite de trois techniques d'optimisation. La première technique consiste à décider s'il faut coder les valeurs sous forme d'entiers séquentiels ou les décompresser pour un accès plus rapide. La deuxième technique est l'augmentation de la structure de données, où l'ajout d'informations à une structure de données peut optimiser les opérations courantes. Un exemple consiste à ajouter un pointeur de queue à une liste liée individuellement pour rendre plus efficace l'ajout de deux listes. La troisième technique est le pré-calcul, qui consiste à effectuer des calculs à l'avance pour éviter d'effectuer les calculs à des moments critiques pour la mission. Un exemple utilise le triangle de Pascal pour pré-calculer les coefficients binomiaux afin d'accélérer le programme qui les utilise.
  
  
• 00:15:00 Dans cette section, l'orateur explique comment pré-calculer le triangle de Pascal à l'aide d'une formule récursive et du code C. Ils expliquent que la formule récursive implique l'appel de la fonction de choix et comment pré-calculer la table au moment de l'exécution à l'aide d'une boucle. De plus, ils expliquent comment initialiser la table au moment de la compilation en plaçant les valeurs de la table dans le code source, ce qui permet de gagner du temps lors de l'exécution du programme. Enfin, ils fournissent un exemple de table de coefficients binomiaux jusqu'à 10 accessible pendant l'exécution du programme.
  
  
• 00:20:00 Dans cette section, l'orateur introduit le concept de méta-programmation comme moyen d'éviter de saisir manuellement de grands tableaux de valeurs constantes dans un programme. En écrivant un programme qui génère le code nécessaire, la tâche fastidieuse peut être effectuée automatiquement. L'orateur fournit un extrait de code Python à titre d'exemple. Le sujet de la mise en cache est également introduit, en tant que technique pour éviter de répéter des calculs coûteux en stockant les résultats récemment consultés dans un cache. L'exemple donné est le calcul de l'hypoténuse d'un triangle rectangle à l'aide de l'opérateur racine carrée, où le cache pré-stocke les hypoténuses précédentes, ainsi que les valeurs de a et b. La fonction hypoténuse vérifie d'abord si les valeurs d'entrée correspondent à celles du cache et, si c'est le cas, renvoie la valeur mise en cache sans avoir à recalculer la racine carrée.
  
  
• 00:25:00 Dans cette section, l'orateur aborde le concept de mise en cache pour optimiser le travail dans un programme. En stockant les valeurs couramment calculées dans un cache, les programmes peuvent gagner du temps en n'ayant pas à calculer à plusieurs reprises les mêmes valeurs. Alors que le matériel effectue également la mise en cache, le logiciel peut également le faire, avec un cache de taille 1 000 stockant les 1 000 valeurs les plus récemment calculées en étant un exemple. L'optimisation peut accélérer un programme d'environ 30 % si les mêmes valeurs sont calculées à plusieurs reprises. L'orateur introduit ensuite l'idée d'exploiter la parcimonie dans une entrée pour éviter de calculer sur des éléments nuls de cette entrée, économisant ainsi du temps de calcul. Ils le démontrent avec un exemple de multiplication de vecteurs matriciels et introduisent la structure de données CSR (compresser sparse Row) qui peut accélérer la multiplication des matrices.
  
  
• 00:30:00 Dans cette section, le conférencier explique comment optimiser le stockage et l'efficacité de calcul des matrices creuses à l'aide du format Compressed Sparse Row (CSR). Le format CSR stocke les éléments non nuls d'une matrice dans trois tableaux : le tableau des valeurs, le tableau des colonnes et le tableau des lignes. L'orateur explique comment calculer la longueur d'une ligne et comment effectuer une multiplication matrice-vecteur en utilisant le format CSR. Le format CSR peut être plus économe en espace que la représentation matricielle dense si le nombre d'éléments non nuls est nettement inférieur à N^2. Cependant, pour les matrices relativement denses, la représentation matricielle dense peut prendre moins de place. L'orateur fournit un exemple de code pour effectuer une multiplication matrice-vecteur à l'aide du format CSR.
  
  
• 00:35:00 Dans cette section, l'instructeur explique les avantages de l'utilisation d'une matrice creuse pour représenter un graphique et comment elle peut être utilisée pour exécuter plus efficacement des algorithmes de graphique classiques tels que la recherche en largeur et le PageRank. La représentation graphique clairsemée se compose de deux tableaux : les décalages et les arêtes, où les degrés de chaque sommet peuvent être obtenus en prenant la différence entre les décalages consécutifs. Le poids des bords peut également être stocké soit dans un tableau séparé, soit entrelacé avec les bords pour améliorer la localité du cache. La section se termine par une brève introduction aux optimisations logiques, en particulier le pliage et la propagation constants, qui évaluent les expressions constantes lors de la compilation pour réduire le temps d'exécution.
  
  
• 00:40:00 Dans cette section de la vidéo, l'orateur discute de différentes techniques d'optimisation du code, y compris le pliage et la propagation constants, l'élimination des sous-expressions communes et l'exploitation des identités algébriques. En définissant des constantes au moment de la compilation, le compilateur peut les évaluer et gagner du temps lors de l'exécution. L'élimination commune des sous-expressions permet d'éviter de calculer la même expression plusieurs fois en stockant le résultat pour une utilisation future. L'exploitation des identités algébriques consiste à remplacer des expressions plus coûteuses par des alternatives moins chères. L'orateur souligne que si le compilateur est généralement bon pour implémenter ces optimisations, il est toujours important de les connaître pour les situations où le compilateur ne le fait pas automatiquement.
  
  
• 00:45:00 Dans cette section de la vidéo, le conférencier discute de deux techniques d'optimisation. La première consiste à réduire l'utilisation de l'opérateur racine carrée, qui est coûteux en calcul, en utilisant des identités algébriques pour éviter les racines carrées. La deuxième technique d'optimisation est le court-circuit, qui consiste à arrêter une série de tests dès que le résultat est connu, dans le cas où un tableau contient des entiers non négatifs et qu'il faut comparer la somme des valeurs du tableau à une limite. L'optimisation peut éliminer le besoin d'examiner tous les éléments du tableau et peut accélérer l'exécution du programme, mais doit être utilisée judicieusement en fonction de la fréquence à laquelle le test peut être court-circuité.
  
  
• 00:50:00 Dans cette section, la vidéo traite du concept de court-circuit des opérateurs logiques et de leur utilité dans l'optimisation du code. La double esperluette et la double barre verticale sont des opérateurs logiques de court-circuit qui peuvent économiser du temps et des ressources en n'évaluant qu'un côté de l'argument. De plus, la vidéo suggère de commander des tests en fonction de leur fréquence de réussite et de leur coût d'exécution. Cette approche peut tirer parti des courts-circuits pour ignorer des tests coûteux si des tests moins coûteux échouent déjà. Enfin, la vidéo introduit l'idée de créer un chemin rapide en utilisant des contrôles pour quitter un programme plus tôt si un résultat est déjà connu. Un exemple de ceci est de vérifier si les boîtes englobantes de deux balles se croisent avant de vérifier d'autres conditions de collision.
  
  
• 00:55:00 Dans cette section, Bentley discute des moyens d'optimiser les tests de détection de collision dans les programmes graphiques. Il suggère un test de chemin rapide pour déterminer si les boîtes englobantes se croisent avant d'effectuer le test de collision le plus coûteux. Ce test consiste à vérifier la valeur absolue de la différence sur chaque coordonnée et à vérifier si elle est supérieure à la somme des deux rayons. Bentley note également que la combinaison de tests via une seule instruction switch ou même des recherches de table peut considérablement améliorer les performances. Dans l'ensemble, ces optimisations peuvent être bénéfiques pour de nombreuses applications et programmes graphiques.
  
  
• 01:00:00 Dans cette section, la vidéo couvre la troisième catégorie d'optimisations, qui est liée aux boucles. La première optimisation de boucle discutée est le levage, qui consiste à éviter de recalculer le code invariant de la boucle à chaque fois dans le corps d'une boucle. En calculant une expression une fois et en la stockant dans une variable, plutôt que de la recalculer à chaque itération, cela peut économiser du temps d'exécution. La deuxième optimisation de la boucle est l'utilisation de sentinelles, des valeurs fictives spéciales placées dans les structures de données pour simplifier la gestion des conditions aux limites et la logique de gestion des tests de sortie de boucle. En modifiant le programme pour utiliser deux entrées supplémentaires dans le tableau, une sentinelle peut être utilisée pour n'avoir besoin d'effectuer qu'une seule vérification à chaque itération de la boucle.
  
  
• 01:05:00 Dans cette section, l'orateur aborde deux techniques d'optimisation du code : les conditions aux limites et le déroulement de boucle. Pour les conditions aux limites, il montre comment modifier une boucle pour gérer efficacement le cas particulier où tous les éléments du tableau d'entrée sont nuls. En ajoutant un élément factice à la fin du tableau et en vérifiant un débordement, le code peut détecter quand il doit s'arrêter. Pour le déroulement de boucle, il explique deux types : complet et partiel. Alors que le déroulement complet de la boucle est rare en raison des tailles de boucle plus grandes, le déroulement partiel de la boucle réduit le nombre d'itérations d'une boucle en combinant plusieurs en une seule, ce qui peut améliorer les performances en réduisant le nombre d'instructions de flux de contrôle exécutées.
  
  
• 01:10:00 Dans cette section, l'instructeur traite des optimisations de déroulement de boucle et de fusion de boucle. Le déroulement de boucle implique la combinaison de plusieurs itérations d'une boucle en une seule itération, réduisant ainsi la surcharge du contrôle de boucle et permettant davantage d'optimisations du compilateur. Cependant, trop dérouler peut affecter négativement les performances en polluant le cache d'instructions. La fusion de boucles, d'autre part, combine plusieurs boucles sur la même plage d'index en une seule boucle, réduisant la surcharge de contrôle de boucle et améliorant la localité du cache. L'instructeur aborde également l'élimination des itérations inutiles en modifiant les limites de boucle pour éviter d'exécuter des itérations de boucle sur des corps de boucle vides.
  
  
• 01:15:00 Dans cette section, Bentley aborde les optimisations de fonction, en particulier le concept d'inlining pour éviter la surcharge d'un appel de fonction. En déclarant une fonction comme statique en ligne, le compilateur essaiera de remplacer un appel à la fonction par le corps de la fonction elle-même, ce qui élimine le besoin d'un appel de fonction séparé. Bien que les macros puissent également le faire, les fonctions en ligne sont plus structurées et évaluent tous leurs arguments, évitant ainsi le risque qu'une macro colle plusieurs fois une expression coûteuse dans le code. Bentley déconseille l'optimisation prématurée et encourage les développeurs à s'assurer d'abord que leur programme est correct et à utiliser des tests de régression pour maintenir l'exactitude. Enfin, il souligne que de nombreux niveaux d'optimisation peuvent être automatisés par le compilateur et que la vérification du code d'assemblage peut révéler de telles optimisations.
  
  
• 01:20:00 Dans cette section, les règles de Bentley pour l'optimisation du travail sont décrites dans une série de six étapes. Ces règles consistent à établir des objectifs clairs, à décomposer les tâches en plus petites parties, à prendre le temps de planifier et d'organiser, à hiérarchiser les tâches, à minimiser les distractions et à revoir et ajuster régulièrement votre approche. En suivant ces directives, vous pouvez augmenter votre productivité et atteindre vos objectifs de manière plus efficace. De plus, l'intégration de ces stratégies dans votre routine quotidienne peut vous aider à maintenir une solide éthique de travail et à rester concentré sur vos objectifs.

[MetaQuotes]

Cours 3. Bit Hacks

3. Bit Hacks

Cette vidéo YouTube couvre une variété de sujets de manipulation de bits, y compris la représentation binaire, le complément à deux, les opérateurs au niveau du bit, l'échange de variables sans variable temporaire et l'optimisation du code. La vidéo montre diverses astuces telles que trouver le minimum de deux entiers sans utiliser d'instructions if-else et comment échanger deux entiers sans utiliser de variable temporaire. L'orateur discute des branches imprévisibles et présente une astuce binaire minimale sans branche lorsque les branches prévisibles ne sont pas disponibles, et montre comment les piratages binaires peuvent optimiser le code en remplaçant des opérations coûteuses telles que la division par de simples opérations au niveau du bit. La vidéo traite également de la séquence de Bruijn et de son application pour résoudre des problèmes tels que le problème de N Queens.

La deuxième partie traite de la résolution du problème de N Queens à l'aide de vecteurs de bits et du comptage efficace du nombre de bits 1 dans un mot binaire. Le retour en arrière est utilisé pour implémenter le problème de N Queens, et des vecteurs de bits sont utilisés pour représenter efficacement la carte. Trois vérifications sont décrites pour placer en toute sécurité une reine dans le problème N Queens, et une méthode pour compter le nombre de bits 1 dans un mot en éliminant récursivement le bit 1 le moins significatif est présentée. De plus, l'utilisation de la consultation de table et de la manipulation de registre pour compter le nombre de bits 1 est discutée. La vidéo se termine par une démonstration d'une approche diviser pour régner pour compter 1 bits qui a une performance proportionnelle au logarithme de base deux de la longueur du mot. Des ressources pour un apprentissage plus approfondi sont également fournies.

• 00:00:00 Dans cette section, nous apprenons la représentation binaire des mots et comment calculer des valeurs entières à partir d'eux. Nous apprenons également la représentation du complément à deux pour les nombres entiers signés et les cas particuliers du mot composé uniquement de zéros et de uns. De plus, nous voyons une identité importante pour le complément à un de X et sa relation avec le négatif de X dans la représentation en complément à deux.
  
  
• 00:05:00 Dans cette section, le présentateur explique le complément à un et comment obtenir le négatif d'un nombre en ajoutant 1 au complément à un. Il passe également en revue l'utilisation des nombres hexadécimaux pour représenter de grandes constantes binaires et donne un tableau pour la conversion entre hexadécimal et binaire. La vidéo passe ensuite en revue les opérateurs au niveau du bit en C++ et montre des exemples sur la façon de les utiliser pour les opérations logiques et, logiques ou, exclusives ou et décalage gauche et droite.
  
  
• 00:10:00 Dans cette section, la vidéo traite de divers idiomes courants pouvant être implémentés à l'aide d'opérateurs au niveau du bit en C. Un exemple consiste à définir ou à effacer le bit de casse dans un mot X en utilisant un décalage suivi d'un OU ou NON et d'un ET, respectivement. Un autre exemple consiste à extraire un champ de bits d'un mot X en générant un masque avec des uns dans les positions des bits souhaités et des zéros ailleurs, puis en effectuant un ET du masque avec X et en décalant vers la droite les bits extraits. La vidéo mentionne également que l'utilisation de ces astuces peut être particulièrement utile lorsque vous travaillez avec des données compressées ou encodées.
  
  
• 00:15:00 Dans cette section, la vidéo explique comment échanger deux entiers sans utiliser de variable temporaire en utilisant quelques astuces. Le code implique de définir X égal à X XOR Y, puis Y égal à X XOR Y, et enfin X égal à X XOR Y. Cela fonctionne car XOR est son propre inverse et la première ligne génère un masque avec ceux où les bits de X et Y diffèrent, qui est ensuite utilisé pour inverser les bits de Y qui sont différents de X. Cela permet l'échange sans l'utilisation d'une variable temporaire. La vidéo souligne également l'importance du masquage pour assurer la sécurité lors de l'utilisation de ces astuces.
  
  
• 00:20:00 Dans cette section, l'orateur discute de deux hacks. Le premier hack est une méthode pour échanger deux variables sans utiliser de variable temporaire. Le hack consiste à utiliser XOR et un masque pour inverser les bits qui diffèrent entre les deux variables. Bien que ce hack soit cool, ce n'est pas le moyen le plus efficace d'échanger des variables en raison d'un mauvais parallélisme au niveau des instructions. Le deuxième hack est un moyen de trouver le minimum de deux entiers sans utiliser d'instructions if-else, ce qui peut entraîner des problèmes de performances en raison d'une mauvaise prédiction de branche. Au lieu de cela, l'orateur montre comment utiliser des opérations au niveau du bit pour comparer les nombres entiers et calculer le minimum sans branchement.
  
  
• 00:25:00 Dans cette section, l'orateur discute de l'optimisation du code et de l'utilisation du mot clé "restrict" dans une sous-routine qui fusionne deux tableaux triés. Le processus est expliqué à travers un exemple où deux tableaux verts sont fusionnés en un tableau bleu. La prévisibilité de chaque branche du code est également discutée, la première branche étant prévisible tandis que la seconde est imprévisible.
  
  
• 00:30:00 Dans cette section, la vidéo traite des branches prévisibles et imprévisibles dans la programmation et présente une astuce minimale sans branche comme solution au problème de branche imprévisible. L'astuce consiste à utiliser une variable appelée "comp" pour stocker le résultat de la comparaison entre le premier élément de a et b et à obtenir le minimum de a et b à l'aide d'une petite astuce. Ensuite, la valeur minimale est placée dans C, et la valeur de A ou B est incrémentée ou décrémentée en fonction de la valeur de "comp." La vidéo note que même si l'astuce peut ne pas fonctionner dans certains cas, il est utile de comprendre ce que fait le compilateur et que de nombreux hacks de bits pour les mots peuvent s'étendre aux hacks de bits et de mots pour les vecteurs, ce qui rend utile de connaître ces astuces.
  
  
• 00:35:00 Dans cette section, la vidéo traite des hacks binaires et de leur utilité dans la programmation. L'exemple donné est une petite astuce pour l'addition modulaire qui permet des opérations plus rapides sans utiliser de division. En définissant Z sur la somme de X et Y, puis en vérifiant s'il est inférieur ou supérieur à N, le programme peut renvoyer Z s'il se trouve dans la plage ou le résultat de Z moins N pour le ramener dans la plage. Le programme utilise une logique similaire au minimum et a une branche imprévisible qui peut entraîner une erreur de prédiction de branche. Un autre exemple donné est un moyen d'arrondir une valeur à la puissance de deux la plus proche en utilisant la manipulation de bits en décrémentant N, en effectuant des opérations au niveau du bit ou avec N décalé à droite de différentes valeurs, puis en incrémentant à la fin.
  
  
• 00:40:00 Dans cette section de la vidéo, l'orateur discute des problèmes de manipulation de deux bits. Le premier problème consiste à trouver la plus petite puissance de deux supérieure à une valeur donnée n. L'orateur explique comment y parvenir en utilisant la manipulation de bits et en décrémentant n s'il est déjà une puissance de deux pour garantir que le logarithme de n moins un bit est défini. Le deuxième problème consiste à calculer le masque du moins significatif dans un mot X, et l'orateur explique comment y parvenir en définissant le résultat sur X et en utilisant l'opération au niveau du bit et avec X négatif. L'orateur présente également le code pour trouver l'index du bit en multipliant X par une constante et en recherchant le résultat dans un tableau. La section se termine par l'exécution par l'orateur d'un tour de magie mathématique impliquant la manipulation de bits.
  
  
• 00:45:00 Dans cette section, une vidéo YouTube montre un groupe exécutant un tour de magie avec des cartes et une cloche. L'interprète prétend lire dans les pensées du public et lui demande de couper le jeu de cartes avant de le distribuer. L'interprète prédit la couleur et le numéro de la carte de chaque personne et réussit apparemment. Ils attribuent leurs capacités au port d'une "grenouillère géniale" et d'un chapeau magique, ainsi qu'à la purification de l'air avec une cloche.
  
  
• 00:50:00 Dans cette section, nous apprenons la séquence de Bruyne et sa corrélation avec le calcul de la base log 2 d'une puissance de 2. La séquence de Bruyne est une séquence de bits cyclique où chaque chaîne de bits possible de longueur K se produit exactement une fois comme sous-chaîne dans la séquence. À l'aide d'une table de conversion, nous pouvons multiplier la constante de séquence de Bruyne par une puissance de 2 et extraire la sous-chaîne qui apparaît au début de la séquence pour calculer la base logarithmique 2 de la puissance de 2. En déplaçant la séquence vers la gauche, puis en regardant jusqu'à la position de départ de la sous-chaîne dans la table de conversion, nous pouvons déterminer la base de log 2 de l'entier avec lequel nous avons commencé, ce qui résout le tour de carte qui a été démontré précédemment.
  
  
• 00:55:00 Dans cette section, l'orateur discute de la séquence de Bruijn, qui est une séquence cyclique d'un alphabet binaire qui contient chaque chaîne de n bits possible exactement une fois. La séquence peut être utilisée pour résoudre des problèmes tels que le problème de N Queens et peut être générée à l'aide d'un tour de magie. L'orateur explique également comment le bit trick fonctionne pour déterminer la position d'une sous-chaîne d'une séquence de de Bruijn après un décalage vers la gauche. Les performances de cette astuce binaire sont limitées par les performances de multiplication et de recherche de table, mais il existe désormais une instruction matérielle pour la calculer.
  
  
• 01:00:00 Dans cette section, l'orateur discute du problème des N reines, qui consiste à placer N reines d'échecs sur un échiquier NxN afin que deux reines ne se menacent pas. Le problème est souvent mis en œuvre en utilisant le retour en arrière, où les reines sont placées rangée par rangée et le programme revient en arrière lorsqu'aucune position valide ne peut être trouvée. Différentes représentations de la carte sont également discutées, la plus compacte étant un ensemble de vecteurs à trois bits. Le vecteur bas stocke la présence de reines dans chaque colonne, le vecteur diagonal gauche stocke la présence de reines sur chaque diagonale gauche et le vecteur diagonal droit stocke la présence de reines sur chaque diagonale droite. L'utilisation de vecteurs de bits permet une mise en œuvre plus efficace de l'algorithme.
  
  
• 01:05:00 Dans cette section, le processus de vérification de la sécurité d'une position pour placer une reine dans un problème de n-reines à l'aide de vecteurs de bits est décrit. Les trois vérifications consistent à vérifier s'il y a déjà une reine dans la même ligne, la même colonne et la même diagonale que la position. Cette méthode est efficace et garantit qu'une reine peut être placée en toute sécurité si elle passe les trois contrôles. Un autre problème discuté est le comptage de la population, qui consiste à compter le nombre de bits 1 dans un mot X. La méthode présentée élimine à plusieurs reprises le bit 1 le moins significatif dans X jusqu'à ce qu'il devienne zéro, et le nombre d'itérations nécessaires est proportionnel au nombre de 1 bits dans X.
  
  
• 01:10:00 Dans cette section, l'orateur discute de l'utilisation de la recherche de table pour compter efficacement le nombre de 1 bits dans un mot binaire. La méthode de recherche de table implique la création d'une table de taille 256 qui stocke le nombre de uns dans chaque mot de 8 bits, puis la recherche du nombre de chaque sous-chaîne de 8 bits dans le mot binaire. L'orateur note que les performances de cette méthode sont entravées par les opérations de mémoire nécessaires pour accéder à la table. L'orateur poursuit en présentant une troisième façon de compter le nombre de bits 1 à l'aide de registres, où ils créent des masques et exécutent des instructions spécifiques qui leur permettent de compter le nombre de uns dans un mot binaire sans accéder à la mémoire. Le présentateur passe par un exemple pour expliquer comment cette méthode fonctionne.
  
  
• 01:15:00 Dans cette section, l'orateur montre comment compter le nombre de 1 dans un mot d'entrée à l'aide d'une méthode parallèle de division et de conquête, où la performance est proportionnelle au logarithme de base deux de la longueur du mot, W. C'est a souligné que la plupart des machines modernes ont une instruction de comptage de pop intrinsèque qui est plus rapide que tout ce qui peut être codé, accessible via les intrinsèques du compilateur. Cependant, cela peut rendre le code moins portable sur différentes machines. L'orateur fournit des ressources pour en savoir plus sur les astuces, y compris un site Web, un manuel, un site Web de programmation d'échecs et un livre intitulé Hacker's Delight.

[MetaQuotes]

Cours 4. Langage d'assemblage et architecture informatique

Cours 4. Langage d'assemblage et architecture informatique

Cette vidéo fournit un aperçu complet du langage d'assemblage et de l'architecture informatique. Le langage d'assemblage est une interface importante pour optimiser les performances du code, et la compréhension de l'architecture informatique est essentielle pour maîtriser le langage d'assemblage. L'orateur explique l'histoire de l'architecture x86 64 et son développement, ses registres clés, les types de données, les modes d'adressage mémoire et l'architecture du jeu d'instructions, y compris les piles, la logique entière et binaire, la logique booléenne et les sous-programmes. Ils discutent également des extensions telles que l'extension zéro et signe et divers modes d'adressage en langage assembleur. En outre, la vidéo traite des types à virgule flottante, des vecteurs et des unités vectorielles, des instructions traditionnelles et SSE, ainsi que des fonctionnalités de conception d'architecture informatique telles que le traitement superscalaire, l'exécution dans le désordre et la prédiction de branche.

La vidéo couvre également plusieurs sujets liés au langage d'assemblage et à l'architecture informatique. L'un des thèmes centraux est le parallélisme au niveau des instructions (ILP) et les décrochages de pipeline, qui sont causés par des dangers tels que les dépendances de données. L'orateur discute des dépendances vraies, anti et de données de sortie et comment les processeurs superscalaires peuvent exploiter plus de parallélisme dans le matériel pour exécuter plusieurs instructions à la fois. Cependant, pour éviter les aléas, les architectes ont mis en place des stratégies telles que le renommage et la réorganisation, ainsi que l'exécution spéculative pour deviner le résultat d'une branche et l'exécuter au préalable. Le conférencier encourage l'auditoire à comprendre ces méthodes pour mieux appréhender les optimisations logicielles.

• 00:00:00 Dans cette section, l'instructeur parle du langage d'assemblage et de l'architecture informatique, qui ne sont souvent pas couverts dans les cours de logiciels modernes. Comprendre ces concepts est nécessaire pour optimiser les performances du code, et le langage d'assemblage est la meilleure interface pour le faire. Le processus de compilation du code implique plusieurs étapes, notamment le prétraitement, la compilation, l'assemblage et la liaison. Le langage d'assemblage est une structure mnémonique du code machine qui le rend plus lisible par l'homme, et l'exécutable final est produit via une étape de liaison à l'aide de la commande LD.
  
  
• 00:05:00 Dans cette section, l'orateur explique que l'assemblage et le code machine ont une structure très similaire, les codes OP en assemblage correspondant à des modèles de bits spécifiques dans le code machine. L'orateur présente le programme ABS, qui peut produire un désassemblage de code machine, révélant le code d'assemblage mnémotechnique lisible par l'homme. L'orateur discute ensuite de plusieurs raisons pour lesquelles quelqu'un pourrait vouloir regarder le code assembleur, y compris révéler ce que le compilateur a fait et n'a pas fait, déboguer les erreurs du compilateur et rétroconcevoir un programme sans accès à sa source.
  
  
• 00:10:00 Dans cette section, l'orateur explique les attentes de la classe, notamment comprendre comment un compilateur implémente des constructions linguistiques avec des instructions x86, être capable de lire le langage d'assemblage x86 et comprendre les implications en termes de performances des modèles d'assemblage courants. Les étudiants doivent également être capables d'écrire du code à partir de zéro si nécessaire et d'acquérir une maîtrise à un niveau où cela est faisable. L'orateur plonge ensuite dans l'architecture du jeu d'instructions x86 64, y compris les registres, les instructions, les types de données et les modes d'adressage de la mémoire. Les registres de clé comprennent les registres à usage général et le registre des drapeaux, qui suit les opérations arithmétiques et les porte. Le pointeur d'instruction guide le matériel à travers la séquence d'instructions dans un programme en langage assembleur.
  
  
• 00:15:00 Dans cette section, l'orateur discute de l'histoire de l'architecture x86 64 et de son développement à partir de machines à mots 16 bits avec une mémoire limitée à des mots plus larges pour l'indexation à mesure que plus de mémoire devenait disponible. L'orateur explique également l'ajout de registres vectoriels tels que les registres xmm et AVX pour la vectorisation, et leur utilisation. Ils abordent également le sujet des registres à usage général et comment leurs objectifs fonctionnels ont considérablement changé au fil du temps, mais leurs noms sont restés pour des raisons historiques. De plus, l'orateur explique comment certains registres sont associés à la même chose pour les moitiés inférieure et supérieure du mot court, des mots 32 bits ou 64 bits.
  
  
• 00:20:00 Dans cette section, l'intervenant explique les bases du langage d'assemblage x86 64 et son fonctionnement. Les registres ont des noms différents selon la partie du registre à laquelle on accède, et certains ont des objectifs spécifiques comme RSP utilisé comme pointeur de pile. Le format d'un code d'instruction x86 64 est d'avoir un opcode et une liste d'opérandes, généralement avec 0-3 opérandes qui peuvent être des sources ou des destinations. L'orateur explique la différence entre la syntaxe AT&T et la syntaxe Intel pour faire référence aux opérations et fournit une liste de codes d'opération courants tels que "déplacement" et "déplacement conditionnel". De plus, l'orateur explique l'importance d'étendre le signe lors du passage d'un registre de valeurs 32 bits à un registre 64 bits.
  
  
• 00:25:00 Dans cette section, l'orateur aborde les différents types d'instructions en langage d'assemblage, y compris les instructions pour les piles, l'arithmétique entière, la logique binaire, la logique booléenne, les sauts et les sous-routines. Les opcodes peuvent être complétés par un suffixe qui décrit le type de données de l'opération ou un code de condition. Par exemple, un déplacement avec un "cue" indique que les données déplacées sont un mot quadruple, qui se compose de 8 octets ou 64 bits. Les types de données x86 64 et leurs suffixes d'assemblage sont également abordés, et des exemples sont donnés pour illustrer le fonctionnement de l'extension de signe. La présence ou l'absence de certains opcodes et mnémoniques en langage assembleur peut prêter à confusion, mais le compilateur doit comprendre ces instructions pour exécuter correctement le programme.
  
  
• 00:30:00 Dans cette section, l'orateur discute des extensions telles que l'extension zéro et l'extension de signe qui se produisent lors du déplacement d'opérations 32 bits vers des opérations 64 bits. Ils mentionnent également comment le jeu d'instructions Intel peut devenir plus compliqué avec l'ajout de nouvelles instructions. L'orateur poursuit en expliquant les différents codes de condition utilisés dans les sauts conditionnels et les mouvements conditionnels et les drapeaux qui sont utilisés avec eux, tels que le drapeau zéro et le drapeau de débordement. La raison pour laquelle certains codes de condition vérifient le drapeau zéro est également discutée.
  
  
• 00:35:00 Dans cette section, l'intervenant aborde les différents modes d'adressage direct et indirect en langage assembleur. Les modes d'adressage direct incluent la mémoire directe immédiate et l'utilisation d'un registre. Les modes d'adressage indirect par registre et indexé par registre permettent d'accéder à la mémoire en fournissant l'adresse dans un registre ou en décalant l'adresse. L'orateur note que l'accès à la mémoire peut être lent et coûteux, il est donc important de stocker les valeurs dans des registres chaque fois que possible pour accélérer le processus. Ils mentionnent également l'importance de la mise en cache dans l'optimisation de l'accès à la mémoire.
  
  
• 00:40:00 Dans cette section, la vidéo traite de l'utilisation de l'indexation relative du pointeur, où le pointeur d'instruction est utilisé pour indexer les données plutôt qu'un registre à usage général. La méthode d'adressage de déplacement d'échelle d'index de base est également introduite, qui est une instruction compliquée qui prend en charge une indexation douce à partir d'un pointeur de base. La vidéo donne un aperçu de certains idiomes du langage d'assemblage, y compris l'opcode XOR, qui est utilisé pour la mise à zéro des registres, et l'opcode de test, qui calcule le bit à bit et de deux valeurs et préserve les indicateurs de registre. Enfin, la vidéo aborde les instructions de saut et les étiquettes, qui permettent de contrôler le flux dans le code.
  
  
• 00:45:00 Dans cette section, la vidéo traite du langage d'assemblage et de l'architecture informatique, y compris divers jeux d'instructions et l'histoire de la virgule flottante. Les jeux d'instructions x86, y compris x87 et SSE, prennent en charge l'arithmétique à virgule flottante scalaire simple et double précision et les instructions vectorielles. Les instructions SSE sont généralement préférées par les compilateurs à x87 en raison de leur simplicité de compilation et d'optimisation. Le but de l'utilisation d'instructions sans opération (nop) dans l'assemblage, telles que l'optimisation de l'alignement, est également expliqué.
  
  
• 00:50:00 Dans cette section, l'orateur discute des types à virgule flottante, des vecteurs et des unités vectorielles qui sont utilisés dans l'architecture informatique. L'orateur explique que la façon dont les unités vectorielles fonctionnent est que le processeur envoie des instructions à toutes les unités vectorielles, chacune étant appelée une voie. Les voies contiennent l'arithmétique entière ou à virgule flottante et fonctionnent toutes en parallèle, ce qui signifie qu'elles font toutes la même chose. Ils peuvent effectuer plusieurs opérations à la fois, et tout cela peut être fait avec une seule instruction. L'orateur explique que certaines architectures nécessitent l'alignement des opérandes vectoriels, tandis que d'autres peuvent décaler les vecteurs en mémoire, ce qui entraîne une différence de performances entre les deux. De plus, il existe des architectures qui prennent en charge les opérations inter-voies, telles que la permutation, le brassage et le scatter-gather.
  
  
• 00:55:00 Dans cette section, l'orateur discute des différences entre les instructions traditionnelles et SSE et comment elles peuvent être utilisées. Ils mentionnent également l'astuce d'aliasing où ymm enregistre les registres alias xmm et les étend à 512 bits avec avx-512. Ils abordent ensuite une discussion sur l'architecture informatique, en particulier sur la différence entre un pipeline à cinq étages et un processeur moderne comportant 14 à 19 étages de pipeline. Les fonctionnalités de conception dont ils discutent incluent le vecteur ou le matériel I, le traitement superscalaire, l'exécution dans le désordre et la prédiction de branche, mais ils mentionnent qu'ils n'approfondiront pas l'exécution dans le désordre en raison de contraintes de temps.
  
  
• 01:00:00 Dans cette section de la vidéo, l'instructeur discute du parallélisme des niveaux d'instruction (ILP) et des décrochages de pipeline. L'ILP consiste à trouver des opportunités d'exécuter plusieurs instructions simultanément afin d'améliorer le débit. Cependant, des blocages de pipeline peuvent se produire lorsqu'une instruction ne peut pas être exécutée en raison d'un danger, tel qu'un danger structurel, un danger de données ou un danger de contrôle, les risques de données étant les plus courants. Une véritable dépendance se produit lorsqu'une instruction lit après une dépendance en écriture, tandis qu'une anti-dépendance se produit lorsqu'une instruction veut écrire dans un emplacement mais doit attendre que l'instruction précédente ait lu la valeur. Le compilateur tente de réduire les blocages de pipeline en optimisant le code pour éviter les dangers.
  
  
• 01:05:00 Dans cette section, le concept de dépendances de données en langage assembleur est abordé. Il existe trois types de dépendances de données : true, anti et output. Les opérations arithmétiques, en particulier les opérations complexes telles que l'arithmétique à virgule flottante, ont une latence plus longue et nécessitent des unités fonctionnelles distinctes dans le processeur, parfois avec des registres séparés. Pour augmenter le parallélisme du niveau d'instruction, les architectes ont mis en œuvre des techniques telles que l'émission de plusieurs instructions par cycle pour exploiter davantage de parallélisme dans le matériel.
  
  
• 01:10:00 Dans cette section, la vidéo explique comment les processeurs superscalaires peuvent exécuter plusieurs instructions à la fois, en utilisant l'exemple de Haswell décomposant les instructions en opérations plus simples appelées micro-opérations et émettant jusqu'à quatre micro-opérations par cycle. La vidéo détaille ensuite les stratégies pour libérer les processeurs de l'exécution des instructions dans l'ordre, y compris le contournement et le renommage des registres, ce qui permet aux instructions non dépendantes d'être exécutées dans le désordre, ce qui entraîne des temps de traitement plus rapides. Ces stratégies nécessitent de suivre les dépendances et d'exécuter le code de manière à éviter les risques tels que les dépendances de données.
  
  
• 01:15:00 Dans cette section, l'orateur discute du changement de nom et de la réorganisation, qui sont deux méthodes importantes utilisées dans les processeurs modernes pour éviter les risques liés aux données. L'orateur parle également d'exécution spéculative, qui est utilisée dans la prédiction de branche pour deviner le résultat d'une branche et l'exécuter au préalable, pour éviter de caler. Cependant, si l'estimation est erronée, il faudra environ 15 à 20 cycles pour annuler le calcul. L'orateur mentionne brièvement le fonctionnement des prédicteurs de branche, mais souligne qu'il est compliqué et nécessite une étude plus approfondie. Malgré la fin précipitée, le conférencier encourage l'auditoire à comprendre les différentes méthodes, ce qui aidera à comprendre pourquoi certaines optimisations logicielles fonctionnent et ne fonctionnent pas.

[MetaQuotes]

Cours 5. C à l'Assemblée

Cours 5. C à l'Assemblée

Dans cette partie de la vidéo, l'importance de comprendre le langage C par rapport au langage d'assemblage est discutée, ainsi que la façon dont le code C est implémenté dans le langage d'assemblage à l'aide d'un compilateur. L'accent est mis spécifiquement sur la façon dont LLVM IR est traduit en assemblage dans la convention d'appel Linux x86 64. Le présentateur explique les composants de base de LLVM IR et comment les constructions du langage de programmation C sont traduites en LLVM IR. La vidéo couvre également la disposition de la mémoire virtuelle, la question de la coordination des appels de fonction entre plusieurs fonctions et l'utilisation de la convention d'appel Linux x86 64 de deux pointeurs - le BP et le SP - pour gérer tous les cadres de pile.

La vidéo explique également les stratégies de gestion des états de registre dans la programmation C to Assembly, telles que la sauvegarde des registres en tant que sauvegarde de l'appelant ou de l'appelé, et comment la convention d'appel x86 évite le gaspillage de travail. Il couvre le fonctionnement des appels de fonction en C et en assembleur, discute du processus d'enregistrement des arguments et des variables locales sur la pile, ainsi que de l'optimisation courante consistant à utiliser le pointeur de pile au lieu du pointeur de base. La vidéo montre également le processus de compilation de LV miR en code d'assemblage, discutant du prologue de la fonction, de la sauvegarde des registres, des conditions de traitement et de la conversion du code C en code d'assemblage à l'aide d'un graphe de flux de contrôle. Enfin, il parle de la fonction épilogue utilisée pour restaurer les registres avant de retourner les résultats.

• 00:00:00 Dans cette section de la vidéo, TB Shuttle explique l'importance de comprendre le C pour le langage d'assemblage. Il note que le langage d'assemblage fournit une plus grande précision que le code C et peut révéler des détails sur un programme qui ne sont pas évidents à partir du code C. L'examen de l'assemblage peut également permettre aux développeurs de déterminer ce que le compilateur a fait ou n'a pas fait lors de l'optimisation d'un programme. De plus, des bogues peuvent survenir qui ne créeraient qu'un comportement inattendu lors de l'optimisation du code à certains niveaux, ce qui rend difficile la détection de ces bogues. Enfin, comprendre l'assemblage peut permettre aux développeurs de modifier le code d'assemblage à la main ou de procéder à l'ingénierie inverse du code.
  
  
• 00:05:00 Dans cette section, la vidéo explique comment le code C est implémenté en langage assembleur grâce à l'utilisation d'un compilateur qui doit prendre des décisions complexes concernant les instructions d'assemblage à utiliser, comment implémenter les conditions et les boucles C, et comment coordonner les appels de fonction. Pour comprendre le processus de traduction, la vidéo présente le LVM IR, qui est un assemblage simplifié que le compilateur utilise pour raisonner sur le programme. La vidéo explique ensuite comment les constructions du langage de programmation C, telles que les fonctions, les conditions et les boucles, sont traduites en LVM IR. La section se termine par une brève mention des attributs LVM IR.
  
  
• 00:10:00 Dans cette section, l'accent est mis sur le processus de traduction de LLVM ir en assembleur, en particulier dans la convention d'appel Linux x86 64. Le présentateur fournit une brève introduction sur LLVM ir, expliquant ses composants de base de fonctions, d'instructions et de registres, qui ressemblent à une version plus simple de l'assemblage. Les registres LLVM ir sont similaires aux variables c et se distinguent par leurs noms, et chaque fonction a ses propres noms de registres locaux. Le présentateur met en évidence les registres dans un exemple d'extrait de code et note que la syntaxe des registres est détournée lorsqu'il fait référence à différents blocs de base dans LLVM. L'exposé se termine par une étude de cas sur la façon dont ce processus fonctionne pour un code simple pour calculer les nombres de Fibonacci.
  
  
• 00:15:00 Dans cette section, l'orateur explique la syntaxe des instructions LV Mir, qui implique un nom de registre, un symbole égal, un opcode et une liste d'opérandes. Alors que certaines instructions renvoient une valeur qui est stockée dans un registre local, d'autres non. Le jeu d'instructions LV Mir est plus petit que celui de x86 car il ne contient que quelques instructions pour les mouvements de données, les opérations arithmétiques et logiques et le flux de contrôle. Dans LV Mir, tout est exposé sous forme de types, qui incluent des entiers (avec un nombre défini de bits), des types à virgule flottante, des types pointeurs, des types vectoriels et des types d'étiquettes pour les blocs de base. L'orateur mentionne également que les opérations vectorielles LV Mir ne ressemblent pas à SSE ou AVX, mais plutôt à des opérations ordinaires qui fonctionnent sur un type de vecteur.
  
  
• 00:20:00 Dans cette section, la vidéo explique comment les séquences d'opérations en code C sont traduites en LLVM IR, et les règles empiriques pour interpréter le code en IR. L'extrait explique également comment LLVM IR gère les types primitifs et agrégés, tels que les tableaux et les structures, et montre des exemples de la façon dont l'accès aux éléments d'un tableau implique le calcul des adresses en mémoire. De plus, la vidéo explique comment les fonctions C sont traduites dans LLVM IR, avec les instructions de retour correspondantes dans les deux langues.
  
  
• 00:25:00 Dans cette section, la vidéo explique comment les fonctions et les paramètres en C se traduisent en LV Mir. Les fonctions dans LV Mir sont similaires aux fonctions en C, mais les paramètres C deviennent des listes de paramètres dans LV Mir. Cependant, la lecture de LV Mir peut être difficile car les registres ne sont pas bien nommés, ce qui les rend difficiles à déchiffrer. La vidéo traite également des blocs de base dans LV Mir, qui sont des morceaux de code partitionnés en fonction des instructions de flux de contrôle. Les connexions entre les blocs de base sont basées sur des fronts induits par des instructions de branchement. Enfin, la vidéo aborde les conditions dans LV Mir, où les instructions if-then-else deviennent des instructions de branche conditionnelles qui induisent des blocs de base et contrôlent les bords de flux.
  
  
• 00:30:00 Dans cette section, la vidéo explique le fonctionnement des opérations conditionnelles et des branches dans LLVM IR. Le processus commence par une comparaison entre une valeur littérale et une valeur stockée dans un registre, ce qui crée un entier d'un bit ou un résultat booléen. Ce résultat est ensuite transmis à une action de branche conditionnelle avec deux étiquettes de blocs de base indiquant où aller si le prédicat est vrai ou faux. S'il existe une branche inconditionnelle avec un opérande, le résultat est un saut direct vers un bloc de base spécifique. La vidéo montre également comment créer une forme de losange dans le graphe de flux de contrôle chaque fois qu'il y a une instruction conditionnelle et fournit un exemple de boucle écrite en code C.
  
  
• 00:35:00 Dans cette section, la vidéo traite des composants d'une boucle C, qui incluent le corps de la boucle et le contrôle de la boucle. Le corps de la boucle est exécuté à chaque itération, tandis que le contrôle de boucle gère toutes les itérations de la boucle. La boucle AC produit un motif de boucle dans le graphe de flux de contrôle, qui à son tour crée une structure de boucle dans le LLVM ir. La vidéo analyse ensuite le code ir LLVM pour le contrôle de boucle, où il y a une instruction fie bizarre qui se produit couramment lorsqu'il s'agit de boucles. L'instruction fie tente de résoudre un problème avec la représentation LLVM du code, où I est représenté par tout un tas de registres différents, ce qui ne permet pas de savoir où je suis réellement allé.
  
  
• 00:40:00 Dans cette section, la vidéo traite du mappage de la variable d'induction dans une boucle à divers emplacements dans LLVM, ce qu'elle fait en raison des valeurs changeantes de la variable au fil des itérations de la boucle. Cela conduit à l'invariant "d'affectation unique statique" dans LLVM selon lequel chaque instruction ne définit qu'une seule fois la valeur d'un registre, ce qui pose un problème pour les variables d'induction. L'instruction "phi" résout ce problème en définissant une valeur de registre qui dépend de la façon dont le flux de contrôle fusionne au point d'entrée d'une boucle. La vidéo traite également des attributs dans LLVM et de la manière dont ils peuvent fournir des informations supplémentaires pour les constructions LLVM, telles que l'attribut NSW attaché à l'instruction "add".
  
  
• 00:45:00 Dans cette section de la vidéo, l'accent est mis sur LLVM IR, qui est similaire à l'assemblage mais plus simple à bien des égards, car toutes les valeurs calculées sont stockées dans des registres qui ressemblent à des variables C ordinaires. LLVM IR utilise le paradigme d'affectation unique statique où chaque variable est écrite par au plus une instruction. La vidéo décrit comment traduire le code C en LLVM IR puis en assemblage, avec quelques complexités supplémentaires dans le processus. Le compilateur sélectionne les instructions d'assemblage réelles nécessaires aux opérations LLVM IR, décide quels registres à usage général sont utilisés et coordonne les appels de fonction entre différents fichiers source et bibliothèques binaires. La discussion se tourne ensuite vers la convention d'appel Linux x86 64.
  
  
• 00:50:00 Dans cette section, la disposition de la mémoire virtuelle pour un programme est discutée. La mémoire virtuelle est divisée en segments, tels que les segments de pile et de tas, qui sont organisés à l'aide de directives assembleur dans le code assembleur. De plus, différents types de directives de stockage sont abordés, tels que la directive space et le segment long, qui allouent de la mémoire et stockent des valeurs. L'attention est ensuite tournée vers le segment de pile où les données sont stockées pour gérer les appels et les retours de fonction, ce qui inclut le stockage des variables locales, des arguments de fonction, de l'adresse de retour et éventuellement des résultats intermédiaires.
  
  
• 00:55:00 Dans cette section de la vidéo, le présentateur aborde le problème de la coordination des appels de fonction entre plusieurs fonctions, dont certaines peuvent provenir de différents fichiers ou bibliothèques. Pour s'assurer que toutes les fonctions fonctionnent bien ensemble, une convention d'appel a été établie à laquelle toutes les fonctions doivent obéir. La convention d'appel Linux x86 64 utilise deux pointeurs - le BP et le SP - pour gérer tous les cadres de pile pour chaque instanciation de fonction. Lorsqu'une instruction d'appel est exécutée, la valeur actuelle de l'adresse IP est poussée sur la pile en tant qu'adresse de retour, et l'instruction d'appel saute à l'adresse d'une fonction dans la mémoire du programme. L'instruction de retour annule les opérations de l'instruction d'appel et extrait l'adresse de retour de la pile pour revenir à l'exécution de l'appelant. Pour gérer le problème de plusieurs fonctions voulant utiliser le même
  registres, la convention d'appel détaille les règles pour lesquelles chaque fonction peut utiliser les registres et comment elles doivent préserver ces registres via des appels de fonction.
  
  
• 01:00:00 Dans cette section, la vidéo traite des stratégies de maintien des états de registre lors de l'utilisation de différentes fonctions dans la programmation C à Assembly. Il mentionne les deux méthodes qui peuvent être utilisées, l'une où l'appelant enregistre l'état du registre avant d'invoquer un appel, et l'autre où l'appelé enregistre tout l'état du registre. La convention d'appel x86 implique les deux, en spécifiant certains registres comme callee-save et d'autres comme caller-save pour éviter de gaspiller du travail. La vidéo explore également l'organisation de la mémoire de la pile et la croissance de la pile. Enfin, il traite de la coordination de la façon dont les fonctions vont utiliser les parties qui se chevauchent de la mémoire de la pile.
  
  
• 01:05:00 Dans cette section, la vidéo explique comment fonctionne un appel de fonction en C et en assembleur. Avant d'appeler la fonction C, la fonction B place des arguments non enregistrés pour la fonction C sur un bloc de liaison réservé dans sa propre mémoire de pile sous ses variables locales. Il accédera à ces arguments avec des décalages négatifs. Lorsque la fonction C démarre, elle exécute un prologue de fonction qui enregistre le pointeur de base pour le cadre de pile de B et définit BP égal à SP car il entre dans un nouveau cadre. Il alloue ensuite de l'espace sur la pile pour ses propres variables locales ainsi que l'espace que B utilisera pour tous les blocs de liaison qu'il crée pour ses appelants ou pour les choses qu'il appelle. La vidéo mentionne également une optimisation courante dans laquelle le compilateur peut se débarrasser de BP et effectuer toute l'indexation basée sur le pointeur de pile RSP pour obtenir un registre à usage général supplémentaire.
  
  
• 01:10:00 Dans cette section, l'instructeur guide le public à travers le processus de compilation de LV miR jusqu'au code d'assemblage. La première étape consiste à définir la fonction 'fib' comme une fonction accessible globalement à l'aide de certaines directives d'assembleur telles que la directive globale fib et l'alignement. Ensuite, le prologue de la fonction est enregistré avec une file d'attente push de var BP et une file d'attente mob de RSP rbp. Le code assembleur pousse également quelques registres sur la pile, qui sont des registres de sauvegarde Kali, avant de déplacer l'argument vers la fonction, RTI, et de le déplacer dans le registre RBX. Enfin, une instruction de comparaison est évaluée pour vérifier si la valeur de N est inférieure à deux, et si c'est le cas, elle renvoie la valeur d'entrée. Sinon, il passe par un code linéaire pour calculer fib de n moins un et fib de n moins deux, les additionner et renvoyer ce résultat.
  
  
• 01:15:00 Dans cette section, la vidéo traite des sauts conditionnels et des différents comportements qui se produisent ensuite dans le code en fonction des résultats de la comparaison. L'instruction JGE saute à l'étiquette du faux côté de l'opération de branchement LLVM lorsque n est supérieur ou égal à 2, tandis que les opérations correspondent au vrai côté de l'opération lorsque n est inférieur à 2. L'instruction LEA est utilisée pour calcul d'adresse, tandis que l'opération de déplacement enregistre le résultat de l'appel de la fonction dans R14. Le prochain ensemble d'instructions calcule la valeur de n-2, la stocke dans RDI, puis appelle fib sur n-2, renvoyant le résultat dans notre AX. Enfin, l'opération ajoute R14 à notre AX.
  
  
• 01:20:00 Dans cette section, la vidéo traite de la conversion du code C en code assembleur. L'orateur explique que le processus utilise un graphe de flux de contrôle, composé de blocs de base reliés par des arêtes de flux de contrôle, pour représenter le code. Ils mentionnent également la complexité de la gestion des conventions d'appel dans le code assembleur. La fonction epilogue est utilisée pour restaurer les registres avant quoi que ce soit dans le cadre de la pile, avant de retourner le résultat. La vidéo se termine en résumant les principaux sujets abordés tout au long de la section.

[MetaQuotes]

Cours 6. Programmation multicœur

Cours 6. Programmation multicœur

Cette conférence vidéo traite de la programmation multicœur et de l'émergence des processeurs multicœurs en raison de la loi de Moore et de la fin de la mise à l'échelle des fréquences d'horloge. L'orateur explique le problème de densité de puissance auquel sont confrontés les processeurs et comment cela a conduit à l'ajout de plusieurs cœurs aux puces pour suivre la loi de Moore. La conférence couvre également les bases des protocoles de cohérence de cache dans le matériel de mémoire partagée et les plates-formes de concurrence telles que Pthreads, TBB, OpenMP et Silk qui fournissent des abstractions pour la programmation parallèle. Les avantages et les inconvénients de chaque plate-forme sont discutés et démontrés avec des exemples de mise en œuvre de programmes de Fibonacci. La vidéo donne un aperçu complet de la programmation multicœur et des défis et solutions auxquels sont confrontés les programmeurs.

La vidéo couvre également divers aspects de Silk, un outil d'abstraction pour gérer le traitement parallèle. L'orateur aborde des sujets tels que la soie imbriquée pour les boucles, la génération de code d'assemblage, la réduction à l'aide de réducteurs, le planificateur et l'optimisation des performances. Ils fournissent également un aperçu de l'écosystème Silk et des outils associés tels que le désinfectant pour soie et l'échelle de soie pour le débogage et l'analyse de l'évolutivité, respectivement. Le principal point à retenir est que l'écriture de programmes parallèles pour les processeurs multicœurs peut être difficile, mais Silk simplifie le processus en gérant efficacement les tâches complexes, ce qui donne aux programmeurs plus de contrôle sur l'exécution de leur code.

• 00:00:00 Dans cette section, l'instructeur discute de la programmation multicœur et des raisons de l'émergence des processeurs multicœurs. Avec l'avènement de la loi de Moore, qui prétend que le nombre de transistors pouvant tenir sur une puce double tous les deux ans, et la fin de la mise à l'échelle des fréquences d'horloge vers 2004-2005, les fournisseurs de semi-conducteurs ont commencé à produire des puces avec plusieurs cœurs de processeur. Cela était dû au fait qu'il n'était plus possible d'augmenter la fréquence des cœurs uniques sur une puce, ce qui obligeait à passer à un modèle de conception permettant un traitement parallèle. L'instructeur clarifie également la relation entre le nombre de transistors sur une puce et la fréquence maximale du processeur.
  
  
• 00:05:00 Dans cette section, l'orateur discute du problème de densité de puissance auquel sont confrontés les processeurs, où l'augmentation de la fréquence d'horloge entraîne une augmentation exponentielle de la densité de puissance. Cela a conduit à l'ajout de plusieurs cœurs aux puces pour suivre la loi de Moore et ne pas dépasser les limites de densité de puissance. L'orateur présente ensuite l'architecture multicœur abstraite, connue sous le nom de multiprocesseur à puce, et décrit les conférences sur les défis matériels et les solutions logicielles pour programmer des programmes parallèles sur des machines multicœurs en utilisant différentes plates-formes de concurrence telles que les threads P, les threads winAPI, les threads Intel. blocs de construction, openmp, etc.
  
  
• 00:10:00 Dans cette section, l'orateur explique comment fonctionnent les caches dans la programmation multicœur. Lorsqu'un processeur charge une valeur dans son cache à partir de la mémoire principale, il conservera cette valeur dans le cache au cas où il aurait besoin d'y accéder à nouveau à l'avenir. Si un autre processeur souhaite charger la même valeur, il peut également l'obtenir via le cache du premier processeur au lieu d'aller jusqu'à la mémoire principale. Cependant, un problème survient lorsqu'un processeur met à jour la valeur dans son propre cache, rendant obsolète la valeur dans le cache d'un autre processeur. Le protocole MSI est une solution de base à ce problème, qui étiquette les lignes de cache avec trois états possibles (M, S et I) pour assurer la cohérence entre les caches.
  
  
• 00:15:00 Dans cette section, la conférence aborde les bases des protocoles de cohérence de cache dans le matériel de mémoire partagée, en particulier comment les modifications apportées à une ligne de cache dans le cache d'un processeur peuvent invalider les copies d'autres caches de la même ligne. La conférence présente un protocole simple et explique comment d'autres protocoles plus complexes existent dans la pratique. Le matériel est responsable de la gestion des conflits lorsque plusieurs processeurs modifient la même ligne de cache, mais cela peut entraîner une "tempête d'invalidation" et ralentir les performances. La conférence note également que les plates-formes de concurrence peuvent résumer ces complexités et aider à la synchronisation et à la communication dans la programmation parallèle.
  
  
• 00:20:00 Dans cette section, l'orateur discute de différentes plates-formes de concurrence en utilisant l'exemple des nombres de Fibonacci. Le programme de Fibonacci est implémenté à l'aide d'un algorithme récursif qui calcule plusieurs fois les nombres de Fibonacci, ce qui en fait un algorithme médiocre. Les deux appels récursifs peuvent être parallélisés car ce sont des calculs complètement indépendants. Pthreads, une API standard pour les threads, peut être utilisée pour implémenter cette parallélisation.
  
  
• 00:25:00 Dans cette section, l'orateur discute de Pthreads, une bibliothèque de fonctions qui permettent la simultanéité dans la programmation. Pthreads fournit une plate-forme de concurrence à faire soi-même, car elle vous permet de spécifier la concurrence dans votre code à l'aide d'une bibliothèque de fonctions avec une sémantique spéciale. Chaque thread dans Pthreads implémente une abstraction d'un processeur et est multiplexé sur les ressources réelles de la machine. Pthreads fournit également des masques qui simplifient les protocoles impliqués dans la coordination des threads internes. La bibliothèque Pthreads a des fonctions clés telles que pthread_create, qui stocke et identifie le nouveau thread créé par pthread, et pthread_join, qui attend que le thread se termine avant de continuer dans le code. L'orateur montre comment implémenter une série de Fibonacci à l'aide de Pthreads.
  
  
• 00:30:00 Dans cette section, le présentateur discute de l'implémentation du code Pthreads pour exécuter la séquence de Fibonacci en parallèle. Ils expliquent que si la taille d'entrée est suffisamment petite, il est préférable d'exécuter le programme de manière séquentielle en raison du coût de création de threads en parallèle. Le code rassemble l'argument d'entrée dans le thread et le stocke dans la structure arguments. Le présentateur discute de la création de Pthread, de la jointure de Pthread et de certains de ses inconvénients, comme devenir beaucoup plus compliqué si le code doit créer des threads de manière récursive. Ils mentionnent également que ce code ne crée qu'un seul thread, donc l'accélération maximale possible est de deux s'il est exécuté sur quatre processeurs.
  
  
• 00:35:00 Dans cette section de la vidéo, les problèmes avec les Pthreads et le code de la séquence de Fibonacci sont discutés. La surcharge élevée liée à la création d'un thread entraîne une concurrence grossière, et le problème d'évolutivité est que les deux cœurs n'effectuent pas la même quantité de travail. Le code manque également de modularité, car la logique de Fibonacci n'est pas bien encapsulée dans une fonction, ce qui la rend difficile à maintenir et à modifier. Le code devient également compliqué en raison du marshalling des arguments, ce qui revient à devoir écrire du code en assembleur. La vidéo présente ensuite Threading Building Blocks (TBB), une bibliothèque développée par Intel pour apporter une solution à ces problèmes.
  
  
• 00:40:00 Dans cette section, la vidéo traite de l'utilisation de la bibliothèque Intel Thread Building Blocks (TBB), une bibliothèque C++ conçue pour permettre aux programmeurs d'utiliser des threads natifs et un algorithme de vol de travail sans avoir à gérer directement les threads. En spécifiant les tâches, la charge TBB les équilibre entre les threads, ce qui rend le code plus simple à écrire et plus performant que l'utilisation de threads POSIX. La vidéo montre un exemple de mise en œuvre d'un programme Fibonacci à l'aide de TBB, démontrant comment il crée de manière récursive des tâches enfants, permettant plus de parallélisme et d'évolutivité sur plusieurs processeurs. TBB fournit également des modèles pour le parallélisme de boucles, l'agrégation de données et le pipelining de logiciels, ainsi que des classes de conteneurs simultanées pour un accès simultané sécurisé aux données partagées.
  
  
• 00:45:00 Dans cette section, l'intervenant présente deux solutions linguistiques au problème de concurrence : OpenMP et Silk. OpenMP est une spécification qui fournit des extensions linguistiques à C et C++, ainsi qu'à Fortran, en utilisant des pragmas de compilateur pour spécifier quels morceaux de code doivent s'exécuter en parallèle. Il prend en charge le parallélisme de boucle, le parallélisme de tâche et le parallélisme de pipeline, et dispose de nombreuses directives de planification et de partage de données, ainsi que de constructions de synchronisation. L'orateur donne un exemple d'implémentation de Fibonacci dans OpenMP, qui est plus simple et plus performant que d'utiliser Pthreads ou TBB. OpenMP est une solution populaire pour écrire des programmes parallèles car il fournit de nombreuses fonctionnalités et simplifie le code.
  
  
• 00:50:00 Dans cette section, l'orateur discute de la plate-forme de programmation Silk, qui prend en charge le parallélisme conjoint et vectoriel et comprend un ordonnanceur de vol de travail dont l'efficacité est prouvée. Le programme dispose également d'une bibliothèque d'hyper objets pour paralléliser le code avec des variables globales et est livré avec des outils de programmation tels qu'un détecteur de course d'écran en soie et un analyseur d'évolutivité appelé Silk View. L'orateur note également que même s'ils n'utiliseront pas Silk Plus dans la classe, ils utiliseront un meilleur compilateur connu sous le nom de taper LLVM, qui produit un meilleur code par rapport à son compilateur de base que toutes les autres implémentations de Silk.
  
  
• 00:55:00 Dans cette section, l'utilisation des instructions Silk spawn et Silk Sync pour activer l'exécution parallèle est abordée à travers des exemples. Le premier exemple est le manteau de sel pour Fibonacci, qui inclut des instructions d'apparition de soie et de synchronisation de soie pour suggérer que fib de n-1 peut être exécuté en parallèle avec la fonction qui l'appelle pendant que fib de n-2 est en cours d'exécution. Cependant, le système d'exécution décide d'exécuter ou non ces tâches en parallèle. Un autre exemple discuté est le parallélisme de boucle, où l'instruction Silk for est utilisée pour exécuter une boucle for en parallèle avec le compilateur divisant de manière récursive l'espace d'itération en deux et utilisant les instructions Silk spawn et Silk Sync jusqu'à ce que la plage devienne trop petite pour être exécutée en parallèle. Il est important de garantir que les itérations sont indépendantes pour des résultats corrects, et l'utilisation de la soie ajoute des frais généraux supplémentaires.
  
  
• 01:00:00 Dans cette section, la vidéo traite de l'utilisation de soie imbriquée pour les boucles et des détails de la génération de code d'assemblage à l'aide d'un indicateur dans le compilateur clang. L'exemple de code pour une sommation de valeurs à l'aide d'une boucle Silk for soulève le problème de la course à la détermination lorsque plusieurs processeurs écrivent dans le même emplacement mémoire. Silk résout ce problème en utilisant des réducteurs, qui sont des hyper objets qui gèrent la fonction d'addition pour une variable donnée, tout en enregistrant et désenregistrant les macros de réducteur. C'est une façon de traiter le problème de la réduction, qui peut survenir dans la programmation multicœur, avec de nombreux autres opérateurs de réduction également disponibles.
  
  
• 01:05:00 Dans cette section, l'orateur discute des réducteurs dans Silk - des structures algébriques qui ont une opération binaire associative et un élément d'identité. Silk a plusieurs réducteurs prédéfinis, y compris l'addition, la multiplication, min, max et XOR, et vous pouvez définir votre propre réducteur. L'un des avantages de Silk est qu'il existe toujours une interprétation série valide du programme, ce qui facilite le débogage, et qu'il dispose d'un planificateur d'exécution qui surveille et mappe le programme sur les cœurs de processeur disponibles, en utilisant un algorithme de planification voleur de travail pour équilibrer les tâches. uniformément. Contrairement aux autres plates-formes de concurrence, le planificateur de Silk est théoriquement efficace.
  
  
• 01:10:00 Dans cette section, le conférencier donne un aperçu de haut niveau de l'écosystème Silk pour la programmation multicœur, y compris comment compiler le code source Silk, comparer les performances parallèles et série et déboguer les problèmes à l'aide d'outils tels que le désinfectant pour soie et la soie escalader. Ils soulignent également l'importance d'optimiser les performances du programme série et la façon dont le planificateur de Silk peut gérer différentes tâches pendant l'exécution du programme. De plus, le conférencier explique comment l'échelle de soie peut déterminer le nombre maximal de processeurs dont un code peut tirer parti, ce qui en fait un outil utile pour analyser l'évolutivité.
  
  
• 01:15:00 Dans cette section, l'orateur résume les principaux enseignements de la conférence sur la programmation multicœur. Ils expliquent que la plupart des processeurs modernes ont plusieurs cœurs, ce qui rend nécessaire l'écriture de programmes parallèles pour des performances élevées. Cependant, écrire de tels programmes peut être difficile, et c'est là que Silk entre en jeu. Cet outil extrait les cœurs de processeur du programmeur et gère la synchronisation, les protocoles de communication et l'équilibrage de charge. L'orateur mentionne également un futur projet où les étudiants mettront en œuvre leur propre économiseur d'écran parallèle à l'aide de Silk.