Redes Neurais em IA e Deep Learning - página 29

Nuevo comentario
 

Lección 36: Alan Edelman y Julia Language



Lección 36: Alan Edelman y Julia Language

En este video, Alan Edelman analiza el poder de los lenguajes de programación para el aprendizaje automático y su importancia en las matemáticas. Destaca el desarrollo reciente del lenguaje Julia, reconocido por Google, por sus méritos técnicos y usabilidad en el aprendizaje automático. Edelman explica cómo funciona la diferenciación automática en Julia y da un ejemplo de cómo calcular la raíz cuadrada de x sin usar diferencias numéricas finitas a través del algoritmo babilónico. También analiza el uso de tipos en Julia para un cálculo eficiente y la simplificación del proceso de retropropagación con matrices de bloques. En general, Edelman enfatiza la importancia del álgebra lineal para los cálculos matemáticos y su papel en la comprensión de fenómenos complejos.

  • 00:00:00 En esta sección, Alan Edelman analiza una demostración del profesor Strang sobre el rango de fila es igual al rango de columna y cómo este concepto se aplica a la matriz cero. Luego habla sobre los desarrollos recientes en Julia, un lenguaje de programación que ha estado ganando terreno en el aprendizaje automático, y cómo Google ha reconocido su poder en este campo. Google publicó recientemente una publicación de blog que indica que solo hay dos lenguajes lo suficientemente poderosos para el aprendizaje automático, y Julia es uno de ellos. Edelman proporciona ejemplos para ilustrar este punto y alienta a los estudiantes a consultar la publicación del blog para obtener más información.

  • 00:05:00 En esta sección, Alan Edelman analiza la importancia de los lenguajes de programación en un sentido matemático y su capacidad para hacer algo más que implementar algoritmos. Explica que Julia, Swift, C++ y Rust son los cuatro lenguajes de programación que se consideran apropiados para el aprendizaje automático en función de sus méritos técnicos y usabilidad. Edelman destaca la importancia del álgebra lineal como base para todos los cursos de ingeniería y su desafortunado retraso en la historia. Luego profundiza en la diferenciación automática y cómo se relaciona con el cálculo, su escepticismo inicial hacia él y los detalles técnicos que ha explorado en su cuaderno sobre la diferenciación automática en modo directo.

  • 00:10:00 En esta sección, Alan Edelman analiza sus pensamientos iniciales sobre la diferenciación automática y cómo pensó que era como el cálculo que aprendió en la escuela, pero con una computadora. Sin embargo, pronto se dio cuenta de que había un tercer método que no eran las diferencias finitas ni la regla de la cadena, lo que lo fascinó. Luego comparte un ejemplo de cómo calculó la raíz cuadrada de x usando el algoritmo babilónico en Julia, y cómo pudo obtener la derivada de la raíz cuadrada sin escribir explícitamente la fórmula derivada, gracias a la función de diferenciación automática de Julia.

  • 00:15:00 En esta sección, el orador describe el uso del código de Julia para calcular la raíz cuadrada de un número sin usar cálculos de diferencias finitas. El código crea un tipo de variable llamada "número dual" que es un par de flotantes que representan una función numérica y su derivada. Luego, el hablante sobrecarga las operaciones de suma y división para implementar la regla del cociente, lo que permite el cálculo de la raíz cuadrada utilizando el algoritmo de Babilonia. El código funciona sin el uso de diferencias numéricas finitas, y el orador señala que Julia permite la reutilización del código existente en nuevos contextos para realizar "magia".

  • 00:20:00 En esta sección, Alan Edelman explica cómo el lenguaje de programación Julia puede calcular eficientemente la derivada usando el algoritmo babilónico en un número dual en código ensamblador. Demuestra cómo el mismo código ejecutado en el paquete de computación simbólica de Python proporciona computación simbólica con grandes coeficientes, lo cual es muy ineficiente. Luego revela el SVD, otro algoritmo que lo convenció de cómo funciona el algoritmo babilónico. Al tomar la derivada de cada línea del código, el algoritmo puede converger a la raíz cuadrada y la derivada de las raíces cuadradas. La derivada resultante no es simbólica ni numérica, sino que usa la regla del cociente y la regla de la suma en cada paso para obtener la respuesta.

  • 00:25:00 En esta sección, Alan Edelman, el creador del lenguaje Julia, analiza cómo funciona la diferenciación automática en el lenguaje. En lugar de derivar manualmente cada línea, Edelman sugiere que el software puede hacer esto automáticamente dejando que el compilador JIT lo maneje. Esto elimina la necesidad de escribir un traductor o escribir a mano, lo que simplifica mucho la codificación. Edelman señala que el aprendizaje automático se basa en gran medida en los problemas de optimización, que tienen que ver con la obtención de derivados, lo que hace que la diferenciación automática sea un componente esencial del proceso. Finalmente, explica cómo el uso de tipos puede simplificar la creación de matrices estructuradas para almacenar datos.

  • 00:30:00 En esta sección, Alan Edelman analiza el uso de tipos en Julia para almacenar eficientemente solo lo que se necesita al realizar cálculos, lo que lo diferencia de lenguajes como Python y MATLAB que tienen más sobrecarga. Luego aborda brevemente la idea de diferenciación de modo inmerso en redes neuronales, comenzando con un ejemplo escalar y generalizando a matrices y vectores. Escribe el álgebra lineal involucrada en este proceso, pero se le acaba el tiempo antes de que pueda explicarlo por completo.

  • 00:35:00 En esta sección, Edelman explica cómo usar matrices de bloques en Julia para realizar retropropagación sin tener que calcular manualmente las derivadas. Muestra cómo el uso de una matriz diagonal y una matriz triangular inferior puede simplificar el proceso de retropropagación y hacer uso de las funciones integradas de Julia. Mediante el uso de álgebra lineal, demuestra cómo una barra invertida puede resolver la matriz triangular inferior, lo que facilita mucho la tarea de calcular derivadas. Edelman enfatiza que el álgebra lineal es esencial para muchos cálculos matemáticos y es el secreto para comprender muchos fenómenos complejos.
 

MIT 6.172 Ingeniería de rendimiento de sistemas de software, otoño de 2018 - 1. Introducción y multiplicación de matrices



1. Introducción y multiplicación de matrices

En este video de YouTube titulado "1. Introducción y multiplicación de matrices", el disertante analiza la importancia de la ingeniería de rendimiento y cómo ha evolucionado con el tiempo. Utilizando el ejemplo de la multiplicación de matrices, el orador muestra cómo las técnicas de codificación y las especificaciones de la máquina pueden tener un gran impacto en el rendimiento. La discusión cubre temas como el orden de los bucles, el uso de caché y la programación paralela. El orador también explora formas de optimizar el código para diferentes procesadores y cálculos aritméticos. En general, el video brinda información valiosa sobre el mundo de la ingeniería de rendimiento y sus aplicaciones prácticas en los sistemas informáticos modernos.

  • 00:00:00 En esta sección, el disertante analiza la importancia de la ingeniería de rendimiento y por qué se estudia. El rendimiento no siempre es la principal prioridad cuando se trata de desarrollo de software. Sin embargo, es la moneda de la informática y se utiliza para comprar otras propiedades deseadas, como la facilidad de programación, la seguridad y la corrección. La degradación del rendimiento puede causar software inutilizable, y la principal queja de la gente sobre los sistemas informáticos es que son demasiado lentos. Por lo tanto, si bien el rendimiento puede no tener un valor intrínseco, contribuye a las cosas que preocupan a los desarrolladores.

  • 00:05:00 En esta sección, el orador analiza la historia de la ingeniería de rendimiento en computación y el cambio desde los primeros días de una ingeniería de rendimiento intensa debido a los recursos limitados de las máquinas, a la era de la Ley de Moore, donde las densidades de los chips se duplicaban cada dos años y esperaban que el hardware se pusiera al día era más beneficioso que optimizar el software. Sin embargo, el orador señala que la escala de Dennard, que permitía aumentar la velocidad del reloj al reducir la potencia, llegó a su fin en 2004 y, por lo tanto, la necesidad de ingeniería de rendimiento es más importante que nunca. El orador incluye citas de los informáticos Donald Knuth, Bill Wolfe y Michael Jackson sobre la importancia del código legible y las advertencias contra la optimización prematura.

  • 00:10:00 En esta sección, el orador analiza los límites en las velocidades de reloj que se alcanzaron a principios de la década de 2000 debido a la densidad de potencia, lo que resultó en el desarrollo de procesadores multinúcleo para escalar el rendimiento. Sin embargo, esto significó que el rendimiento ya no era gratuito y requería una programación paralela, algo que la industria no había hecho antes. A partir de ese momento, el software tuvo que adaptarse a las nuevas configuraciones de hardware para ser efectivo y, como resultado, hubo un mayor enfoque en el rendimiento en los trabajos de desarrollo de software.

  • 00:15:00 En esta sección, el ponente comienza explicando la importancia práctica y teórica de aprender a escribir software que utilice eficientemente el hardware moderno. Luego brindan un ejemplo de ingeniería de rendimiento utilizando el problema bien estudiado de la multiplicación de matrices, analizando la máquina que usarán, incluidas sus especificaciones y capacidades, como procesamiento paralelo, tamaño de caché y capacidad de memoria, y concluyendo con una explicación de el código básico de Python para la multiplicación de matrices. El orador enfatiza el poder de la máquina y el potencial para proyectos divertidos que utilizan sus capacidades.

  • 00:20:00 En esta sección, el disertante analiza el rendimiento de Python, Java y C++ en el contexto de la multiplicación de matrices. La lección demuestra que Python es demasiado lento para la multiplicación de matrices grandes, con un tiempo de ejecución de aproximadamente 21 000 segundos, Java es más rápido y produce casi nueve veces más velocidad que Python, y C++ es el más rápido con un tiempo de ejecución de aproximadamente 1100 segundos. , que es el doble de rápido que Java y 18 veces más rápido que Python.

  • 00:25:00 En esta sección, el orador analiza las diferencias de rendimiento entre lenguajes interpretados como Python, lenguajes compilados como C y lenguajes como Java que se compilan en código de bytes y luego se interpretan. Los intérpretes como Python son versátiles pero lentos, mientras que los compiladores como C aprovechan el hardware y las instrucciones de la máquina para optimizar el rendimiento. Los compiladores JIT, como los que se usan en Java, recuperan algo de rendimiento al compilar solo las piezas de código que se ejecutan con mayor frecuencia. El orador señala que el modelo de rendimiento de Python es difícil de entender, razón por la cual usarán C para las comparaciones de rendimiento en el curso. Sin embargo, habrá una conferencia invitada en la que hablarán sobre la ingeniería de rendimiento en lenguajes administrados como Python.

  • 00:30:00 En esta sección, se analiza la importancia del orden de bucle para el rendimiento en la multiplicación de matrices. El orden de los bucles afecta la ubicación de la memoria caché, lo que afecta el tiempo de ejecución. Las matrices se disponen en la memoria en orden de fila principal en C y en orden de columna principal en Fortran. El patrón de acceso para order ijk tiene una localidad espacial buena para C pero una localidad espacial deficiente para B. La herramienta "cachegrind" es útil para determinar las tasas de error del código, y los cambios simples, como ajustar los indicadores del compilador, también pueden mejorar el rendimiento.

  • 00:35:00 En esta sección, el orador analiza cómo optimizar el código para obtener un mejor rendimiento de una máquina. Es importante elegir un buen indicador de optimización, como -O2 o -O3, pero a veces un indicador de optimización más bajo puede optimizar mejor según el código. Además, los procesadores multinúcleo se pueden utilizar con bucles paralelos utilizando la infraestructura de seda, lo que da como resultado una aceleración de casi 18x en 18 núcleos. El orador enfatiza que paralelizar los bucles externos es más efectivo que paralelizar los bucles internos, lo que en realidad puede ralentizar el programa. Sin embargo, todavía hay fuentes de oportunidad para la optimización, como errores de caché y no usar instrucciones vectorizadas de manera efectiva.

  • 00:40:00 En esta sección, el orador analiza cómo administrar mejor las fallas de la memoria caché al reestructurar el cálculo para reutilizar los datos en la memoria caché tanto como sea posible. Mediante el uso de un esquema de mosaico, las matrices se dividen en submatrices más pequeñas y se multiplican en bloques para reducir la cantidad de accesos a la memoria necesarios. El orador explica que es necesario un parámetro de ajuste para determinar el tamaño de las submatrices y sugiere que la experimentación es la mejor manera de encontrar el valor óptimo. A través de este enfoque, el orador demuestra que es posible reducir significativamente la cantidad de accesos a la memoria necesarios para calcular el mismo tamaño de huella, lo que hace que el cálculo sea más eficiente.

  • 00:45:00 En esta sección, el orador analiza los beneficios de usar bloques o mosaicos al realizar la multiplicación de matrices, como un mejor uso de caché y un tiempo de ejecución más rápido. Explican los diferentes niveles de caché que tienen los chips y cómo los programadores pueden usar los parámetros de ajuste para optimizar su código para cada nivel de caché. Sin embargo, el proceso de ajuste se vuelve más complejo con cada nivel de caché y el código puede volverse difícil de leer y comprender. El orador sugiere un enfoque de divide y vencerás que utiliza la programación paralela para resolver recursivamente subproblemas más pequeños. Aunque este método mejora el uso de la memoria caché, la sobrecarga de las llamadas a funciones ralentiza el cálculo, lo que destaca la necesidad de una ingeniería de rendimiento inteligente.

  • 00:50:00 En esta sección, el orador analiza la optimización de la multiplicación de matrices utilizando la técnica divide y vencerás y el ajuste del umbral para usar el algoritmo. Se establece un caso base para cuando el umbral está por debajo de un cierto número, y el algoritmo utiliza la multiplicación de matrices ordinaria. Se encontró que el mejor valor para el caso base era 32, lo que resultó en un tiempo de ejecución de 1,3 segundos y un 12 % de rendimiento máximo. Además, el orador introduce el concepto de vectorización utilizando el hardware de vector, que procesa datos en una sola instrucción, formato de datos múltiples. El orador describe diferentes formas de optimizar la vectorización, incluido el uso de informes de vectorización, indicadores para arquitecturas específicas y el indicador matemático rápido, que permite al compilador reordenar las asociaciones. El uso de matemáticas rápidas y nativas de la arquitectura da como resultado el doble de rendimiento cuando se usa cualquier vectorizador compilador.

  • 00:55:00 En esta sección del video, el orador analiza los diversos tamaños de bits utilizados para los cálculos aritméticos, siendo el de 64 bits el más común para los cálculos de álgebra lineal. También mencionan que se puede usar aritmética de menor precisión para aplicaciones de IA para mejorar el rendimiento. El orador continúa hablando sobre el uso de instrucciones vectoriales y los intrínsecos AVX, que proporcionan un rendimiento máximo de hasta el 41 % y una aceleración de alrededor de 50 000. Advierten que es posible que no se vean mejoras en el rendimiento similares a las logradas en la multiplicación de matrices en otras áreas, pero este curso enseñará a los estudiantes cómo lograr mejoras sustanciales en el rendimiento por sí mismos. Además, el curso se centrará en la informática multinúcleo en lugar de GPU u otras áreas.
 

Lección 2. Reglas de Bentley para optimizar el trabajo



2. Reglas de Bentley para optimizar el trabajo

Este video de YouTube analiza varias técnicas de optimización para programas informáticos. Se presentan las reglas de Bentley para optimizar el trabajo y las optimizaciones se agrupan en estructuras de datos, bucles, lógica y funciones. Se analizan diferentes técnicas como la codificación de valores, el aumento de la estructura de datos, el cálculo previo, el almacenamiento en caché y la utilización de matrices dispersas. El orador también se refiere a los beneficios de usar una representación de matriz dispersa para gráficos, optimización lógica y optimización de detección de colisiones en programas de gráficos. La implementación de estas técnicas de optimización ayuda a reducir el tiempo de ejecución de los programas, haciéndolos más eficientes.

La segunda parte del video cubre varias categorías de técnicas de optimización, incluido el levantamiento de bucles, el uso de centinelas en bucles, el desenrollado y la fusión de bucles y la incorporación de funciones. El orador desaconseja la optimización prematura y enfatiza la importancia de mantener la corrección y usar pruebas de regresión. El video también describe las Reglas de Bentley para optimizar el trabajo, una guía de seis pasos para aumentar la productividad y lograr objetivos de manera eficiente. Estas reglas incluyen establecer objetivos claros, desglosar tareas, planificar y organizar, priorizar tareas, minimizar las distracciones y revisar y ajustar periódicamente el enfoque propio.

  • 00:00:00 En esta sección, el disertante introduce el concepto de optimizar el trabajo en los programas de computadora y explica cómo reducir el trabajo de un programa puede mejorar su rendimiento. También habla de las reglas de Bentley para optimizar el trabajo, que llevan el nombre de John Lewis Bentley, quien escribió un libro sobre cómo escribir programas eficientes. Las optimizaciones se agrupan en cuatro categorías: estructuras de datos, bucles, lógica y funciones, y el disertante planea cubrir las 22 reglas en una serie de mini conferencias a lo largo del curso. Si bien reducir el trabajo de un programa es una buena heurística para mejorar su tiempo de ejecución, la naturaleza compleja del hardware de la computadora significa que no siempre se traduce en una reducción del tiempo de ejecución, por lo que el disertante también cubrirá las optimizaciones específicas de la arquitectura más adelante en el curso.

  • 00:05:00 En esta sección del video, el orador analiza el concepto de empaquetar y codificar estructuras de datos para almacenar más de un valor de datos en una palabra de máquina y convertir valores de datos en una representación que requiere menos bits. Al reducir la cantidad de cosas que se mueven en la memoria, se convierte en una buena heurística para disminuir el tiempo de ejecución de un programa. El orador proporciona un ejemplo de codificación de fechas para almacenarlas usando menos bits para que sea más fácil obtener el mes, el año o el día de una fecha específica. El orador sugiere usar instalaciones de campos de bits en C para almacenar los datos estructurados, haciéndolos más accesibles. Esta representación requiere un poco más de bits pero es mucho más eficiente para acceder a valores de datos específicos dentro de la estructura.

  • 00:10:00 En esta sección, el video analiza tres técnicas de optimización. La primera técnica es decidir si codificar valores como enteros secuenciales o descomprimirlos para un acceso más rápido. La segunda técnica es el aumento de la estructura de datos, donde agregar información a una estructura de datos puede optimizar las operaciones comunes. Un ejemplo es agregar un puntero de cola a una lista enlazada individualmente para agregar dos listas de manera más eficiente. La tercera técnica es el cálculo previo, que consiste en realizar cálculos por adelantado para evitar realizar los cálculos en momentos de misión crítica. Un ejemplo es usar el triángulo de Pascal para precalcular coeficientes binomiales para acelerar el programa que los usa.

  • 00:15:00 En esta sección, el orador explica cómo precalcular el triángulo de Pascal usando una fórmula recursiva y código C. Explican que la fórmula recursiva implica llamar a la función de elección y cómo calcular previamente la tabla en tiempo de ejecución mediante un bucle. Además, analizan cómo inicializar la tabla en tiempo de compilación colocando los valores de la tabla en el código fuente, lo que ahorra tiempo durante la ejecución del programa. Finalmente, proporcionan una tabla de ejemplo de coeficientes binomiales hasta 10 a la que se puede acceder durante la ejecución del programa.

  • 00:20:00 En esta sección, el orador presenta el concepto de metaprogramación como una forma de evitar escribir manualmente tablas grandes de valores constantes en un programa. Al escribir un programa que genera el código necesario, la tediosa tarea se puede realizar automáticamente. El orador proporciona un fragmento de código de Python como ejemplo. También se introduce el tema del almacenamiento en caché, como una técnica para evitar la repetición de cálculos costosos al almacenar los resultados a los que se accedió recientemente en un caché. El ejemplo dado es calcular la hipotenusa de un triángulo rectángulo usando el operador de raíz cuadrada, donde el caché almacena previamente las hipotenusas anteriores, junto con los valores de a y b. La función de hipotenusa primero verifica si los valores de entrada coinciden con los de la memoria caché y, de ser así, devuelve el valor de la memoria caché sin tener que volver a calcular la raíz cuadrada.

  • 00:25:00 En esta sección, el orador analiza el concepto de almacenamiento en caché para optimizar el trabajo en un programa. Al almacenar valores comúnmente calculados en un caché, los programas pueden ahorrar tiempo al no tener que calcular repetidamente los mismos valores. Si bien el hardware también realiza el almacenamiento en caché, el software también puede hacerlo, con un caché de tamaño 1000 que almacena los 1000 valores calculados más recientemente como ejemplo. La optimización puede acelerar un programa en aproximadamente un 30 % si se calculan repetidamente los mismos valores. Luego, el orador presenta la idea de explotar la escasez en una entrada para evitar calcular en cero elementos de esa entrada, ahorrando así tiempo de cálculo. Demuestran esto con un ejemplo de multiplicación de vectores de matriz e introducen la estructura de datos de fila dispersa comprimida (CSR) que puede acelerar la multiplicación de matrices.

  • 00:30:00 En esta sección, el orador analiza cómo optimizar el almacenamiento y la eficiencia computacional de matrices dispersas utilizando el formato Compressed Sparse Row (CSR). El formato CSR almacena los elementos distintos de cero de una matriz en tres matrices: la matriz de valores, la matriz de columnas y la matriz de filas. El orador explica cómo calcular la longitud de una fila y cómo realizar la multiplicación matriz-vector utilizando el formato CSR. El formato CSR puede ser más eficiente en cuanto al espacio que la representación de matriz densa si el número de elementos distintos de cero es significativamente menor que N^2. Sin embargo, para matrices relativamente densas, la representación de la matriz densa puede ocupar menos espacio. El orador proporciona un ejemplo de código para realizar la multiplicación de matrices y vectores utilizando el formato CSR.

  • 00:35:00 En esta sección, el instructor analiza los beneficios de usar una matriz dispersa para representar un gráfico y cómo se puede utilizar para ejecutar algoritmos gráficos clásicos, como la búsqueda en amplitud y PageRank, de manera más eficiente. La representación gráfica dispersa consta de dos matrices: compensaciones y bordes, donde los grados de cada vértice se pueden obtener tomando la diferencia entre compensaciones consecutivas. El peso de los bordes también puede almacenarse en una matriz separada o intercalarse con los bordes para mejorar la localidad de caché. La sección finaliza con una breve introducción a las optimizaciones lógicas, específicamente el plegado y la propagación constantes, que evalúa expresiones constantes durante la compilación para reducir el tiempo de ejecución.

  • 00:40:00 En esta sección del video, el orador analiza diferentes técnicas de optimización para el código, incluido el plegamiento y la propagación constantes, la eliminación de subexpresiones comunes y la explotación de identidades algebraicas. Al definir constantes en tiempo de compilación, el compilador puede evaluarlas y ahorrar tiempo durante el tiempo de ejecución. La eliminación de subexpresiones comunes permite evitar calcular la misma expresión varias veces almacenando el resultado para uso futuro. Explotar identidades algebraicas implica reemplazar expresiones más caras con alternativas más baratas. El orador enfatiza que, si bien el compilador suele ser bueno para implementar estas optimizaciones, aún es importante conocerlas en situaciones en las que el compilador no lo hace automáticamente.

  • 00:45:00 En esta sección del video, el orador analiza dos técnicas de optimización. El primero es reducir el uso del operador de raíz cuadrada, que es computacionalmente costoso, mediante el uso de identidades algebraicas para evitar las raíces cuadradas. La segunda técnica de optimización es el cortocircuito, que consiste en detener una serie de pruebas tan pronto como se conoce el resultado, en el caso de que una matriz contenga números enteros no negativos y la suma de los valores de la matriz deba compararse con una límite. La optimización puede eliminar la necesidad de mirar todos los elementos en la matriz y puede acelerar la ejecución del programa, pero debe usarse con prudencia en función de la frecuencia con la que la prueba puede sufrir un cortocircuito.

  • 00:50:00 En esta sección, el video analiza el concepto de cortocircuitar los operadores lógicos y su utilidad para optimizar el código. El ampersand doble y la barra vertical doble son operadores lógicos de cortocircuito que pueden ahorrar tiempo y recursos al evaluar solo un lado del argumento. Además, el video sugiere ordenar las pruebas en función de su frecuencia de éxito y costo de ejecución. Este enfoque puede aprovechar el cortocircuito para omitir pruebas costosas si las menos costosas ya fallan. Finalmente, el video presenta la idea de crear una ruta rápida mediante el uso de comprobaciones para salir antes de tiempo de un programa si ya se conoce un resultado. Un ejemplo de esto es verificar si los cuadros delimitadores de dos bolas se cruzan antes de verificar otras condiciones de colisión.

  • 00:55:00 En esta sección, Bentley analiza formas de optimizar las pruebas para la detección de colisiones en programas de gráficos. Sugiere una prueba de ruta rápida para determinar si los cuadros delimitadores se cruzan antes de realizar la prueba más costosa de colisión. Esta prueba consiste en comprobar el valor absoluto de la diferencia en cada coordenada y comprobar si es mayor que la suma de los dos radios. Bentley también señala que la combinación de pruebas a través de una sola declaración de cambio o incluso búsquedas en tablas puede mejorar en gran medida el rendimiento. En general, estas optimizaciones pueden ser beneficiosas para muchas aplicaciones y programas gráficos.
  • 01:00:00 En esta sección, el video cubre la tercera categoría de optimizaciones, que está relacionada con los bucles. La primera optimización de bucle discutida es el levantamiento, que implica evitar volver a calcular el código invariable del bucle cada vez que se pasa por el cuerpo de un bucle. Al calcular una expresión una vez y almacenarla en una variable, en lugar de volver a calcularla en cada iteración, puede ahorrar tiempo de ejecución. La segunda optimización del bucle es el uso de centinelas, valores ficticios especiales colocados en estructuras de datos para simplificar el manejo de las condiciones de contorno y la lógica del manejo de las pruebas de salida del bucle. Al modificar el programa para usar dos entradas adicionales en la matriz, se puede usar un centinela para que solo necesite realizar una verificación en cada iteración del bucle.

  • 01:05:00 En esta sección, el orador analiza dos técnicas para optimizar el código: condiciones de contorno y desarrollo de bucles. Para las condiciones de contorno, muestra cómo modificar un ciclo para manejar eficientemente el caso especial cuando todos los elementos de la matriz de entrada son cero. Al agregar un elemento ficticio al final de la matriz y verificar si hay un desbordamiento, el código puede detectar cuándo debe detenerse. Para el desenrollado de bucles, explica dos tipos: completo y parcial. Si bien el desenrollado completo del bucle es raro debido a los tamaños de bucle más grandes, el desenrollado parcial del bucle reduce la cantidad de iteraciones de un bucle al combinar varias en una, lo que puede mejorar el rendimiento al reducir la cantidad de instrucciones de flujo de control ejecutadas.

  • 01:10:00 En esta sección, el instructor analiza las optimizaciones de desenrollado y fusión de bucles. El desenrollado de bucles implica combinar varias iteraciones de un bucle en una única iteración, lo que reduce la sobrecarga del control de bucles y permite más optimizaciones del compilador. Sin embargo, desenrollar demasiado puede afectar negativamente el rendimiento al contaminar la memoria caché de instrucciones. La fusión de bucles, por otro lado, combina múltiples bucles sobre el mismo rango de índice en un solo bucle, lo que reduce la sobrecarga de control de bucles y mejora la localidad de caché. El instructor también analiza la eliminación de iteraciones desperdiciadas mediante la modificación de los límites del bucle para evitar ejecutar iteraciones de bucle sobre cuerpos de bucle vacíos.

  • 01:15:00 En esta sección, Bentley analiza las optimizaciones de funciones, específicamente el concepto de inserción para evitar la sobrecarga de una llamada de función. Al declarar una función como estática en línea, el compilador intentará reemplazar una llamada a la función con el cuerpo de la función misma, lo que elimina la necesidad de una llamada de función separada. Si bien las macros también podrían hacer esto, las funciones en línea están más estructuradas y evalúan todos sus argumentos, lo que evita el riesgo de que una macro pegue una expresión costosa varias veces en el código. Bentley desaconseja la optimización prematura y alienta a los desarrolladores a que primero se aseguren de que su programa sea correcto y utilicen pruebas de regresión para mantener la corrección. Finalmente, señala que el compilador puede automatizar muchos niveles de optimización, y verificar el código ensamblador puede revelar tales optimizaciones.

  • 01:20:00 En esta sección, las reglas de Bentley para optimizar el trabajo se describen en una serie de seis pasos. Estas reglas consisten en establecer objetivos claros, dividir las tareas en partes más pequeñas, tomarse el tiempo para planificar y organizar, priorizar tareas, minimizar las distracciones y revisar y ajustar periódicamente su enfoque. Siguiendo estas pautas, puede aumentar su productividad y lograr sus objetivos de una manera más eficiente. Además, incorporar estas estrategias en su rutina diaria puede ayudarlo a mantener una sólida ética de trabajo y concentrarse en sus objetivos.
 

Lección 3. Bit Hacks



3. Trucos de bits

Este video de YouTube cubre una variedad de temas de manipulación de bits, incluida la representación binaria, el complemento a dos, los operadores bit a bit, el intercambio de variables sin una variable temporal y la optimización de código. El video muestra varios trucos de bits, como encontrar el mínimo de dos enteros sin usar declaraciones if-else y cómo intercambiar dos enteros sin usar una variable temporal. El orador analiza las bifurcaciones impredecibles y presenta un truco de bit mínimo sin bifurcación para cuando las bifurcaciones predecibles no están disponibles, y muestra cómo los trucos de bit pueden optimizar el código al reemplazar operaciones costosas como la división con operaciones bit a bit simples. El video también analiza la secuencia de Bruijn y su aplicación para resolver problemas como el problema de N Queens.

La segunda parte trata sobre cómo resolver el problema de N Queens usando vectores de bits y contando eficientemente el número de bits 1 en una palabra binaria. El retroceso se usa para implementar el problema de N Queens, y los vectores de bits se usan para representar eficientemente el tablero. Se describen tres comprobaciones para colocar con seguridad una reina en el problema de N reinas y se presenta un método para contar el número de bits 1 en una palabra mediante la eliminación recursiva del bit 1 menos significativo. Además, se analiza el uso de la búsqueda en tablas y la manipulación de registros para contar el número de bits 1. El video termina con una demostración de un enfoque de divide y vencerás para contar 1 bits que tiene un rendimiento proporcional al logaritmo en base dos de la longitud de la palabra. También se proporcionan recursos para seguir aprendiendo.

  • 00:00:00 En esta sección, aprendemos sobre la representación binaria de palabras y cómo calcular valores enteros a partir de ellas. También aprendemos sobre la representación del complemento a dos para enteros con signo y los casos especiales de la palabra todos ceros y todos unos. Además, vemos una identidad importante para el complemento a uno de X y su relación con el negativo de X en la representación del complemento a dos.

  • 00:05:00 En esta sección, el presentador explica el Complemento a Unos y cómo obtener el negativo de un número sumando 1 al Complemento a Unos. También repasa el uso de números hexadecimales para representar grandes constantes binarias y proporciona una tabla para convertir entre hexadecimal y binario. Luego, el video repasa los operadores bit a bit en C++ y muestra ejemplos de cómo usarlos para operaciones lógicas y, lógicas o, exclusivas o, y desplazamiento a la izquierda y a la derecha.

  • 00:10:00 En esta sección, el video analiza varios modismos comunes que se pueden implementar usando operadores bit a bit en C. Un ejemplo es configurar o borrar el bit de mayúsculas y minúsculas en una palabra X usando un cambio seguido de un O o NO y un Y, respectivamente. Otro ejemplo es extraer un campo de bits de una palabra X generando una máscara con unos en las posiciones de los bits deseados y ceros en cualquier otro lugar, luego haciendo AND en la máscara con X y desplazando a la derecha los bits extraídos. El video también menciona que usar estos trucos puede ser particularmente útil cuando se trabaja con datos comprimidos o codificados.

  • 00:15:00 En esta sección, el video explica cómo intercambiar dos números enteros sin usar una variable temporal usando algunos trucos de bits. El código implica establecer X igual a X XOR Y, luego Y igual a X XOR Y, y finalmente X igual a X XOR Y. Esto funciona porque XOR es su propio inverso y la primera línea genera una máscara con unos donde los bits en X e Y difieren, que luego se usa para voltear los bits en Y que son diferentes de X. Esto permite el intercambio sin el uso de una variable temporal. El video también enfatiza la importancia del enmascaramiento para garantizar la seguridad al trabajar con estos trucos.

  • 00:20:00 En esta sección, el orador analiza trucos de dos bits. El primer truco es un método para intercambiar dos variables sin usar una variable temporal. El truco consiste en usar XOR y una máscara para cambiar los bits que difieren entre las dos variables. Si bien este truco es genial, no es la forma más eficiente de intercambiar variables debido al bajo paralelismo del nivel de instrucción. El segundo truco es una forma de encontrar el mínimo de dos números enteros sin usar declaraciones if-else, lo que puede causar problemas de rendimiento debido a una predicción errónea de la bifurcación. En cambio, el orador muestra cómo usar operaciones bit a bit para comparar los números enteros y calcular el mínimo sin bifurcarse.

  • 00:25:00 En esta sección, el orador analiza la optimización del código y el uso de la palabra clave "restringir" en una subrutina que fusiona dos matrices ordenadas. El proceso se explica a través de un ejemplo en el que dos matrices verdes se fusionan en una matriz azul. También se analiza la previsibilidad de cada rama en el código, siendo la primera rama predecible mientras que la segunda es impredecible.

  • 00:30:00 En esta sección, el video analiza las bifurcaciones predecibles e impredecibles en la programación y presenta un truco de bit mínimo sin bifurcación como solución al problema de la bifurcación impredecible. El truco implica usar una variable llamada "comp" para almacenar el resultado de la comparación entre el primer elemento de a y b y obtener el mínimo de a y b usando un truco de bits. Luego, el valor mínimo se coloca en C, y el valor de A o B se incrementa o decrementa en función del valor de "comp". El video señala que, si bien es posible que el truco no funcione en algunos casos, es útil comprender lo que está haciendo el compilador y que muchos trucos de bits para palabras pueden extenderse a trucos de bits y palabras para vectores, por lo que es útil conocer estos trucos.

  • 00:35:00 En esta sección, el video analiza los trucos de bits y su utilidad en la programación. El ejemplo dado es un pequeño truco para la suma modular que permite operaciones más rápidas sin usar la división. Al establecer Z en la suma de X e Y, y luego verificar si es menor o mayor que N, el programa puede devolver Z si está dentro del rango o el resultado de Z menos N para devolverlo al rango. El programa utiliza una lógica similar al mínimo y tiene una bifurcación impredecible que puede resultar en una predicción errónea de la bifurcación. Otro ejemplo dado es una forma de redondear un valor a la potencia de dos más cercana mediante la manipulación de bits al disminuir N, realizar operaciones bit a bit o con N desplazado a la derecha por diferentes valores y luego incrementar al final.

  • 00:40:00 En esta sección del video, el orador discute problemas de manipulación de dos bits. El primer problema consiste en encontrar la potencia más pequeña de dos que sea mayor que un valor n dado. El orador explica cómo lograr esto mediante la manipulación de bits y la disminución de n si ya es una potencia de dos para garantizar que se establezca el logaritmo de n menos un bit. El segundo problema consiste en calcular la máscara del menos significativo en una palabra X, y el hablante explica cómo lograr esto estableciendo el resultado en X y usando la operación bit a bit y con X negativa. El hablante también presenta código para encontrar el índice del bit multiplicando X por una constante y buscando el resultado en una tabla. La sección termina con el orador realizando un truco de magia matemática que implica la manipulación de bits.

  • 00:45:00 En esta sección, un video de YouTube muestra a un grupo realizando un truco de magia con cartas y una campana. El artista afirma leer la mente de la audiencia y les pide que corten la baraja de cartas antes de distribuirlas. El ejecutante predice el palo y el número de la carta de cada persona y aparentemente tiene éxito. Atribuyen sus habilidades a usar un "mono impresionante" y un sombrero mágico, además de limpiar el aire con una campana.

  • 00:50:00 En esta sección, aprendemos sobre la secuencia de De Bruyne y su correlación con el cálculo del logaritmo en base 2 de una potencia de 2. La secuencia de De Bruyne es una secuencia de bits cíclica donde cada posible cadena de bits de longitud K ocurre exactamente una vez como una subcadena en la secuencia. Usando una tabla de conversión, podemos multiplicar la constante de secuencia de De Bruyne por una potencia de 2 y extraer la subcadena que aparece al comienzo de la secuencia para calcular el logaritmo en base 2 de la potencia de 2. Desplazando la secuencia a la izquierda y luego mirando arriba de la posición inicial de la subcadena en la tabla de conversión, podemos determinar el logaritmo base 2 del entero con el que comenzamos, lo que resuelve el truco de cartas que se demostró anteriormente.

  • 00:55:00 En esta sección, el orador analiza la secuencia de De Bruijn, que es una secuencia cíclica de un alfabeto binario que contiene cada posible cadena de n bits exactamente una vez. La secuencia se puede usar para resolver problemas como el problema de N Queens y se puede generar usando un truco de magia. El orador también explica cómo funciona el truco de los bits para determinar la posición de una subcadena de una secuencia de De Bruijn después de un desplazamiento a la izquierda. El rendimiento de este truco de bits está limitado por el rendimiento de la multiplicación y la consulta de tablas, pero ahora hay una instrucción de hardware para calcularlo.

  • 01:00:00 En esta sección, el disertante analiza el problema de N Queens, que implica colocar N reinas de ajedrez en un tablero de ajedrez NxN de modo que no haya dos reinas que se amenacen entre sí. El problema a menudo se implementa utilizando el retroceso, donde las reinas se colocan fila por fila y el programa retrocede cuando no se puede encontrar una posición válida. También se analizan diferentes representaciones de la placa, siendo la más compacta un conjunto de vectores de tres bits. El vector hacia abajo almacena la presencia de reinas en cada columna, el vector de la diagonal izquierda almacena la presencia de reinas en cada diagonal izquierda y el vector de la diagonal derecha almacena la presencia de reinas en cada diagonal derecha. El uso de vectores de bits permite una implementación más eficiente del algoritmo.

  • 01:05:00 En esta sección, se describe el proceso de verificar si una posición es segura para colocar una reina en un problema de n-reinas usando vectores de bits. Las tres verificaciones implican verificar si ya hay una reina en la misma fila, la misma columna y la misma diagonal que la posición. Este método es eficiente y garantiza que una reina pueda colocarse de manera segura si pasa los tres controles. Otro problema discutido es el conteo de población, que implica contar el número de bits 1 en una palabra X. El método presentado elimina repetidamente el bit 1 menos significativo en X hasta que se convierte en cero, y el número de iteraciones requeridas es proporcional al número de 1 bits en X.

  • 01:10:00 En esta sección, el orador analiza el uso de la tabla de búsqueda para contar eficientemente el número de bits 1 en una palabra binaria. El método de búsqueda de tabla implica crear una tabla de tamaño 256 que almacene el número de unos en cada palabra de 8 bits y luego buscar el recuento de cada subcadena de 8 bits en la palabra binaria. El orador señala que el rendimiento de este método se ve obstaculizado por las operaciones de memoria necesarias para acceder a la tabla. El orador continúa presentando una tercera forma de contar el número de bits 1 usando registros, donde crean máscaras y ejecutan instrucciones específicas que les permiten contar el número de unos en una palabra binaria sin acceder a la memoria. El presentador analiza un ejemplo para explicar cómo funciona este método.

  • 01:15:00 En esta sección, el orador demuestra cómo contar el número de 1 en una palabra de entrada usando un método paralelo de divide y vencerás, donde el rendimiento es proporcional al logaritmo en base dos de la longitud de la palabra, W. Es señaló que la mayoría de las máquinas modernas tienen una instrucción intrínseca de conteo de pops que es más rápida que cualquier cosa que se pueda codificar, accesible a través de los intrínsecos del compilador. Sin embargo, esto puede hacer que el código sea menos portátil entre diferentes máquinas. El orador proporciona algunos recursos para aprender más sobre trucos de bits, incluido un sitio web, un libro de texto, un sitio web de programación de ajedrez y un libro llamado Hacker's Delight.
 

Lección 4. Lenguaje ensamblador y arquitectura informática



Lección 4. Lenguaje ensamblador y arquitectura informática

Este video proporciona una descripción general completa del lenguaje ensamblador y la arquitectura de la computadora. El lenguaje ensamblador es una interfaz importante para optimizar el rendimiento del código, y comprender la arquitectura de la computadora es esencial para dominar el lenguaje ensamblador. El orador explica la historia de la arquitectura x86 64 y su desarrollo, sus registros clave, tipos de datos, modos de direccionamiento de memoria y arquitectura de conjunto de instrucciones, incluidas pilas, lógica entera y binaria, lógica booleana y subrutinas. También discuten extensiones como cero y extensión de signo y varios modos de direccionamiento en lenguaje ensamblador. Además, el video analiza los tipos de coma flotante, los vectores y las unidades vectoriales, las instrucciones SSE y tradicionales, y las características de diseño de la arquitectura de la computadora, como el procesamiento superescalar, la ejecución fuera de orden y la predicción de bifurcaciones.

El video también cubre varios temas relacionados con el lenguaje ensamblador y la arquitectura de la computadora. Uno de los temas centrales es el paralelismo de nivel de instrucción (ILP) y las paradas de canalización, que son causadas por peligros como las dependencias de datos. El orador analiza las dependencias de datos verdaderos, anti y de salida y cómo los procesadores superescalares pueden explotar más paralelismo en el hardware para ejecutar múltiples instrucciones a la vez. Sin embargo, para evitar peligros, los arquitectos han implementado estrategias como renombrar y reordenar, así como ejecución especulativa para adivinar el resultado de una rama y ejecutarla de antemano. El orador alienta a la audiencia a comprender estos métodos para comprender mejor las optimizaciones de software.

  • 00:00:00 En esta sección, el instructor habla sobre el lenguaje ensamblador y la arquitectura informática, que a menudo no se tratan en los cursos de software modernos. Comprender estos conceptos es necesario para optimizar el rendimiento del código y el lenguaje ensamblador es la mejor interfaz para hacerlo. El proceso de compilación de código implica varias etapas, incluido el preprocesamiento, la compilación, el ensamblaje y la vinculación. El lenguaje ensamblador es una estructura mnemotécnica del código de la máquina que lo hace más legible por humanos, y el ejecutable final se produce a través de una etapa de enlace usando el comando LD.

  • 00:05:00 En esta sección, el orador explica que el código ensamblador y el de máquina tienen una estructura muy similar, con códigos OP en ensamblador que corresponden a patrones de bits específicos en el código de máquina. El orador presenta el programa ABS, que puede producir un desensamblaje de código de máquina, revelando el código ensamblador mnemotécnico y legible por humanos. Luego, el orador analiza varias razones por las que alguien podría querer ver el código ensamblador, incluida la revelación de lo que hizo y lo que no hizo el compilador, la depuración de errores del compilador y la ingeniería inversa de un programa sin acceso a su fuente.

  • 00:10:00 En esta sección, el orador explica las expectativas de la clase, que incluyen comprender cómo un compilador implementa construcciones lingüísticas con instrucciones x86, ser capaz de leer el lenguaje ensamblador x86 y comprender las implicaciones de rendimiento de los patrones de ensamblaje comunes. Los estudiantes también deben ser capaces de escribir código desde cero si es necesario, y adquirir dominio a un nivel en el que esto sea factible. Luego, el orador se sumerge en la arquitectura del conjunto de instrucciones x86 64, incluidos registros, instrucciones, tipos de datos y modos de direccionamiento de memoria. Los registros clave incluyen registros de propósito general y el registro de banderas, que rastrea operaciones aritméticas y acarreos. El puntero de instrucciones guía al hardware a través de la secuencia de instrucciones en un programa en lenguaje ensamblador.

  • 00:15:00 En esta sección, el orador analiza la historia de la arquitectura x86 64 y su desarrollo desde máquinas de palabras de 16 bits con memoria limitada hasta palabras más amplias para la indexación a medida que se disponía de más memoria. El orador también explica la adición de registros vectoriales, como los registros xmm y AVX para la vectorización, y cómo se utilizan. También tocan el tema de los registros de propósito general y cómo sus propósitos funcionales han cambiado significativamente con el tiempo, pero sus nombres se han mantenido por razones históricas. Además, el orador explica cómo ciertos registros se asocian a la misma cosa para las mitades inferior y superior de la palabra corta, palabras de 32 o 64 bits.

  • 00:20:00 En esta sección, el orador explica los conceptos básicos del lenguaje ensamblador x86 64 y cómo funciona. Los registros tienen diferentes nombres según la parte del registro a la que se acceda, y algunos tienen propósitos específicos, como el uso de RSP como puntero de pila. El formato de un código de instrucción x86 64 es tener un código de operación y una lista de operandos, generalmente con 0-3 operandos que pueden ser fuentes o destinos. El orador explica la diferencia entre la sintaxis de AT&T y la sintaxis de Intel para referirse a las operaciones y proporciona una lista de códigos de operación comunes como "mover" y "movimiento condicional". Además, el orador explica la importancia de extender el signo al pasar de un registro de valor de 32 bits a un registro de 64 bits.

  • 00:25:00 En esta sección, el orador analiza los diversos tipos de instrucciones en lenguaje ensamblador, incluidas las instrucciones para pilas, aritmética de enteros, lógica binaria, lógica booleana, saltos y subrutinas. Los códigos de operación se pueden aumentar con un sufijo que describe el tipo de datos de la operación o un código de condición. Por ejemplo, un movimiento con una "señal" indica que los datos que se mueven son una palabra cuádruple, que consta de 8 bytes o 64 bits. También se analizan los tipos de datos x86 64 y sus sufijos de ensamblaje, y se dan ejemplos para ilustrar cómo funciona la extensión de signos. La presencia o ausencia de determinados códigos de operación y mnemónicos en lenguaje ensamblador puede resultar confuso, pero el compilador debe comprender estas instrucciones para ejecutar el programa correctamente.

  • 00:30:00 En esta sección, el orador analiza las extensiones como la extensión cero y la extensión de signo que ocurren cuando se mueven operaciones de 32 bits a operaciones de 64 bits. También mencionan cómo el conjunto de instrucciones de Intel puede volverse más complicado con la adición de nuevas instrucciones. El orador continúa explicando los diferentes códigos de condición utilizados en saltos condicionales y movimientos condicionales y las banderas que se usan con ellos, como la bandera cero y la bandera de desbordamiento. También se analiza el motivo por el que determinados códigos de condición marcan el indicador cero.

  • 00:35:00 En esta sección, el orador analiza los diferentes modos de direccionamiento directo e indirecto en lenguaje ensamblador. Los modos de direccionamiento directo incluyen memoria inmediata, directa y uso de un registro. Los modos de direccionamiento indirecto por registro e indexado por registro permiten acceder a la memoria proporcionando la dirección en un registro o compensando la dirección. El orador señala que acceder a la memoria puede ser lento y costoso, por lo que es importante almacenar valores en registros siempre que sea posible para acelerar el proceso. También mencionan la importancia del almacenamiento en caché para optimizar el acceso a la memoria.

  • 00:40:00 En esta sección, el video analiza el uso de la indexación relativa de puntero, donde el puntero de instrucción se usa para indexar datos en lugar de un registro de propósito general. También se presenta el método de direccionamiento de desplazamiento de escala de índice base, que es una instrucción complicada que admite la indexación suave a partir de un puntero base. El video proporciona una descripción general de algunos modismos del lenguaje ensamblador, incluido el código de operación XOR, que se usa para poner a cero los registros, y el código de operación de prueba, que calcula el bit a bit y de dos valores y conserva las banderas de registro. Por último, el video toca las instrucciones de salto y las etiquetas, que permiten controlar el flujo en el código.

  • 00:45:00 En esta sección, el video analiza el lenguaje ensamblador y la arquitectura de la computadora, incluidos varios conjuntos de instrucciones y la historia del punto flotante. Los conjuntos de instrucciones x86, incluidos x87 y SSE, admiten aritmética de punto flotante escalar de precisión simple y doble e instrucciones vectoriales. Los compiladores generalmente prefieren las instrucciones SSE a las x87 debido a su simplicidad en la compilación y optimización. También se explica el propósito de usar instrucciones sin operación (nop) en el ensamblaje, como la optimización de la alineación.

  • 00:50:00 En esta sección, el disertante analiza los tipos de punto flotante, los vectores y las unidades vectoriales que se utilizan en la arquitectura informática. El orador explica que la forma en que funcionan las unidades vectoriales es que el procesador emite instrucciones a todas las unidades vectoriales, cada una de las cuales se denomina carril. Los carriles contienen la aritmética de números enteros o de punto flotante y todos funcionan al unísono, lo que significa que todos hacen lo mismo. Pueden realizar varias operaciones a la vez, y todo esto se puede hacer con una sola instrucción. El orador explica que algunas arquitecturas requieren que se alineen los operandos vectoriales, mientras que otras pueden cambiar los vectores en la memoria, lo que resulta en una diferencia de rendimiento entre los dos. Además, hay arquitecturas que admiten operaciones entre carriles, como permutación, barajado y dispersión.

  • 00:55:00 En esta sección, el orador analiza las diferencias entre las instrucciones tradicionales y SSE y cómo se pueden usar. También mencionan el truco del alias donde ymm registra alias xmm y los extiende a 512 bits con avx-512. Luego pasan a una discusión sobre la arquitectura de la computadora, específicamente la diferencia entre una canalización de cinco etapas y un procesador moderno con 14 a 19 etapas de canalización. Las características de diseño que analizan incluyen vector o Hardware I, procesamiento superescalar, ejecución fuera de orden y predicción de bifurcación, pero mencionan que no profundizarán en la ejecución fuera de orden debido a limitaciones de tiempo.

  • 01:00:00 En esta sección del video, el instructor analiza el paralelismo de nivel de instrucción (ILP) y las paradas de canalización. ILP implica encontrar oportunidades para ejecutar múltiples instrucciones simultáneamente para mejorar el rendimiento. Sin embargo, las paradas de la tubería pueden ocurrir cuando una instrucción no se puede ejecutar debido a un peligro, como un peligro estructural, un peligro de datos o un peligro de control, siendo los peligros de datos los más comunes. Una verdadera dependencia ocurre cuando una instrucción lee después de una dependencia de escritura, mientras que una antidependencia ocurre cuando una instrucción quiere escribir en una ubicación pero tiene que esperar hasta que la instrucción anterior haya leído el valor. El compilador intenta reducir las paradas de la canalización optimizando el código para evitar peligros.

  • 01:05:00 En esta sección, se discute el concepto de dependencias de datos en lenguaje ensamblador. Hay tres tipos de dependencias de datos: verdadero, anti y de salida. Las operaciones aritméticas, especialmente las complejas como la aritmética de punto flotante, tienen una latencia más larga y requieren unidades funcionales separadas en el procesador, a veces con registros separados. Para aumentar el paralelismo del nivel de instrucción, los arquitectos han implementado técnicas como emitir múltiples instrucciones por ciclo para explotar más paralelismo en el hardware.

  • 01:10:00 En esta sección, el video explica cómo los procesadores superescalares pueden ejecutar múltiples instrucciones a la vez, usando el ejemplo de Haswell dividiendo las instrucciones en operaciones más simples llamadas micro operaciones y emitiendo hasta cuatro micro operaciones por ciclo. Luego, el video detalla estrategias para liberar a los procesadores de la ejecución de instrucciones en orden, incluida la omisión y el cambio de nombre de registro, lo que permite que las instrucciones no dependientes se ejecuten fuera de orden, lo que resulta en tiempos de procesamiento más rápidos. Estas estrategias requieren realizar un seguimiento de las dependencias y ejecutar el código de una manera que evite peligros como las dependencias de datos.

  • 01:15:00 En esta sección, el orador analiza el cambio de nombre y el reordenamiento, que son dos métodos importantes utilizados en los procesadores modernos para evitar riesgos de datos. El ponente también habla de la ejecución especulativa, que se utiliza en la predicción de bifurcaciones para adivinar el resultado de una bifurcación y ejecutarla de antemano, para evitar estancamientos. Sin embargo, si la suposición es incorrecta, costará entre 15 y 20 ciclos deshacer el cálculo. El orador menciona brevemente cómo funcionan los predictores de rama, pero señala que es complicado y requiere más estudio. A pesar del final apresurado, el orador alienta a la audiencia a comprender los diversos métodos, lo que ayudará a comprender por qué ciertas optimizaciones de software funcionan y no funcionan.
 

Lección 5. C a Asamblea



Lección 5. C a Asamblea

En esta parte del video, se analiza la importancia de comprender C en lenguaje ensamblador, además de cómo se implementa el código C en lenguaje ensamblador usando un compilador. La atención se centra específicamente en cómo LLVM IR se traduce en ensamblaje en la convención de llamadas Linux x86 64. El presentador explica los componentes básicos de LLVM IR y cómo las construcciones en el lenguaje de programación C se traducen a LLVM IR. El video también cubre el diseño de la memoria virtual, el tema de la coordinación de llamadas de funciones entre múltiples funciones y el uso de dos punteros en la convención de llamadas Linux x86 64, el BP y el SP, para administrar todos los marcos de pila.

El video también explica las estrategias para mantener los estados de registro en la programación de C a ensamblador, como guardar registros como guardado de llamadas o guardado de llamadas, y cómo la convención de llamadas x86 evita la pérdida de trabajo. Cubre cómo funcionan las llamadas a funciones en C y ensamblador, analizando el proceso de guardar argumentos y variables locales en la pila, así como la optimización común de usar el puntero de pila en lugar del puntero base. El video también muestra el proceso de compilación de LV miR hasta código ensamblador, analizando el prólogo de la función, guardando registros, manejando condiciones y convirtiendo código C en código ensamblador usando un gráfico de flujo de control. Finalmente, habla de la función epilogue utilizada para restaurar registros antes de devolver resultados.

  • 00:00:00 En esta sección del video, TB Shuttle analiza la importancia de comprender C para el lenguaje ensamblador. Señala que el lenguaje ensamblador proporciona mayor precisión que el código C y puede revelar detalles sobre un programa que no son obvios a partir del código C. Observar el ensamblaje también puede permitir a los desarrolladores determinar qué hizo o no hizo el compilador al optimizar un programa. Además, pueden surgir errores que solo crearían un comportamiento inesperado al optimizar el código en ciertos niveles, lo que dificulta la detección de estos errores. Por último, comprender el ensamblaje puede permitir a los desarrolladores modificar el código de ensamblaje a mano o aplicar ingeniería inversa al código.

  • 00:05:00 En esta sección, el video analiza cómo se implementa el código C en lenguaje ensamblador mediante el uso de un compilador que tiene que tomar decisiones complejas con respecto a qué instrucciones de ensamblador usar, cómo implementar condicionales y bucles C, y cómo llamadas a funciones de coordenadas. Para comprender el proceso de traducción, el video presenta LVM IR, que es un ensamblaje simplificado que el compilador usa para razonar sobre el programa. Luego, el video explica cómo las construcciones en el lenguaje de programación C, como funciones, condicionales y bucles, se traducen a LVM IR. La sección finaliza con una breve mención de los atributos LVM IR.

  • 00:10:00 En esta sección, la atención se centra en el proceso de cómo LLVM ir se convierte en ensamblador, específicamente en la convención de llamadas Linux x86 64. El presentador brinda una breve introducción a LLVM ir, explicando sus componentes básicos de funciones, instrucciones y registros, que se asemejan a una versión más simple de ensamblaje. Los registros ir de LLVM son similares a las variables c y se distinguen por sus nombres, y cada función tiene sus propios nombres de registros locales. El presentador destaca los registros en un fragmento de código de ejemplo y señala que la sintaxis de los registros está secuestrada cuando se hace referencia a diferentes bloques básicos en LLVM. La charla concluye con un estudio de caso sobre cómo funciona este proceso para un código simple para calcular números de Fibonacci.

  • 00:15:00 En esta sección, el orador explica la sintaxis de las instrucciones LV Mir, que involucra un nombre de registro, un símbolo igual, un código de operación y una lista de operandos. Mientras que algunas instrucciones devuelven un valor que se almacena en un registro local, otras no. El conjunto de instrucciones LV Mir es más pequeño que el de x86, ya que contiene solo unas pocas instrucciones para movimientos de datos, operaciones aritméticas y lógicas y flujo de control. En LV Mir, todo se expone como tipos, que incluyen números enteros (con un número definido de bits), tipos de punto flotante, tipos de puntero, tipos de vectores y tipos de etiquetas para bloques básicos. El orador también menciona que las operaciones de vector LV Mir no se parecen a SSE o AVX, sino a operaciones ordinarias que funcionan en un tipo de vector.

  • 00:20:00 En esta sección, el video analiza cómo las secuencias de operaciones en código C se traducen a LLVM IR y las reglas generales para interpretar el código en IR. El extracto también explica cómo LLVM IR maneja tipos primitivos y agregados, como arreglos y estructuras, y muestra ejemplos de cómo acceder a elementos en un arreglo implica calcular direcciones en la memoria. Además, el video explica cómo se traducen las funciones de C a LLVM IR, con las declaraciones de retorno correspondientes en ambos idiomas.

  • 00:25:00 En esta sección, el video explica cómo las funciones y los parámetros en C se traducen a LV Mir. Las funciones en LV Mir son similares a las funciones en C, pero los parámetros de C se convierten en listas de parámetros en LV Mir. Sin embargo, leer LV Mir puede ser un desafío ya que los registros no están bien nombrados, lo que dificulta su desciframiento. El video también analiza los bloques básicos en LV Mir, que son fragmentos de código divididos en función de las instrucciones del flujo de control. Las conexiones entre bloques básicos se basan en aristas inducidas por instrucciones de bifurcación. Finalmente, el video toca los condicionales en LV Mir, donde las declaraciones if-then-else se convierten en instrucciones de ramificación condicional que inducen bloques básicos y controlan los bordes del flujo.

  • 00:30:00 En esta sección, el video explica cómo funcionan las operaciones condicionales y las bifurcaciones en LLVM IR. El proceso comienza con una comparación entre un valor literal y un valor almacenado en un registro, lo que crea un resultado booleano o entero de un bit. Luego, este resultado se pasa a una acción de bifurcación condicional junto con dos etiquetas de bloques básicos que indican a dónde ir si el predicado es verdadero o falso. Si hay una bifurcación incondicional con un operando, el resultado es un salto directo a un bloque básico específico. El video también muestra cómo crear una forma de diamante en el gráfico de flujo de control siempre que haya una declaración condicional y proporciona un ejemplo de un bucle escrito en código C.

  • 00:35:00 En esta sección, el video analiza los componentes de un bucle C, que incluyen el cuerpo del bucle y el control del bucle. El cuerpo del bucle se ejecuta en cada iteración, mientras que el control del bucle gestiona todas las iteraciones del bucle. El bucle de CA produce un patrón de bucle en el gráfico de flujo de control, que a su vez crea una estructura de bucle en el LLVM ir. Luego, el video analiza el código ir de LLVM para el control de bucle, donde hay una instrucción de archivo extraña que surge comúnmente cuando se trata de bucles. La instrucción fie intenta resolver un problema con la representación LLVM del código, donde I está representado por un montón de registros diferentes, lo que hace que no quede claro a dónde fui realmente.

  • 00:40:00 En esta sección, el video analiza el mapeo de la variable de inducción en un ciclo a varias ubicaciones en LLVM, lo cual se debe a los valores cambiantes de la variable a lo largo de las iteraciones del ciclo. Esto conduce a la invariante de "asignación única estática" en LLVM de que cada instrucción solo define el valor de un registro una vez, lo que plantea un problema para las variables de inducción. La instrucción "phi" resuelve este problema al definir un valor de registro que depende de cómo se fusiona el flujo de control en el punto de entrada de un bucle. El video también analiza los atributos en LLVM y cómo pueden proporcionar información adicional para las construcciones de LLVM, como el atributo NSW adjunto a la instrucción "agregar".

  • 00:45:00 En esta sección del video, la atención se centra en LLVM IR, que es similar al ensamblaje pero más simple en muchos aspectos, ya que todos los valores calculados se almacenan en registros que son como variables C ordinarias. LLVM IR utiliza el paradigma de asignación única estática en el que cada variable está escrita por una instrucción como máximo. El video describe cómo traducir código C a LLVM IR y luego a ensamblaje, con algunas complejidades adicionales en el proceso. El compilador selecciona las instrucciones de ensamblado reales necesarias para las operaciones LLVM IR, decide qué registros de uso general se utilizan y coordina las llamadas a funciones entre diferentes archivos fuente y bibliotecas binarias. Luego, la discusión gira en torno a la convención de llamadas de Linux x86 64.

  • 00:50:00 En esta sección, se discute el diseño de la memoria virtual para un programa. La memoria virtual se divide en segmentos, como los segmentos de pila y montón, que se organizan con el uso de directivas de ensamblador en código ensamblador. Además, se analizan diferentes tipos de directivas de almacenamiento, como la directiva de espacio y el segmento largo, que asignan memoria y almacenan valores. Luego, se dirige la atención al segmento de la pila donde se almacenan los datos para administrar las llamadas y devoluciones de funciones, lo que incluye el almacenamiento de variables locales, argumentos de funciones, la dirección de retorno y posiblemente resultados intermedios.

  • 00:55:00 En esta sección del video, el presentador analiza el tema de la coordinación de llamadas a funciones entre múltiples funciones, algunas de las cuales pueden originarse en diferentes archivos o bibliotecas. Para garantizar que todas las funciones funcionen bien juntas, se ha establecido una convención de llamadas que todas las funciones deben obedecer. La convención de llamadas de Linux x86 64 utiliza dos punteros, el BP y el SP, para administrar todos los marcos de pila para cada instanciación de función. Cuando se ejecuta una instrucción de llamada, el valor actual de la IP se coloca en la pila como dirección de retorno y la instrucción de llamada salta a la dirección de alguna función en la memoria del programa. La instrucción de retorno deshace las operaciones de la instrucción de llamada y extrae la dirección de retorno de la pila para volver a la ejecución de la persona que llama. Para manejar el problema de múltiples funciones que desean usar los mismos registros, la convención de llamadas detalla las reglas para qué registros puede usar cada función y cómo deben preservar esos registros a través de llamadas a funciones.
  • 01:00:00 En esta sección, el video analiza las estrategias para mantener los estados de registro cuando se opera con diferentes funciones en la programación C a Assembly. Menciona los dos métodos que se pueden usar, uno en el que la persona que llama guarda el estado del registro antes de invocar una llamada, y el otro en el que la persona que llama guarda todo el estado del registro. La convención de llamadas x86 involucra ambos, especificando algunos registros como guardado de llamadas y otros como guardado de llamadas para evitar perder trabajo. El video también explora cómo se organiza la memoria de la pila y cómo crece la pila. Finalmente, analiza la coordinación de cómo las funciones van a utilizar partes superpuestas de la memoria de pila.

  • 01:05:00 En esta sección, el video explica cómo funciona una llamada de función en C y ensamblador. Antes de llamar a la función C, la función B coloca argumentos que no son de registro para la función C en un bloque de vinculación reservado en su propia memoria de pila debajo de sus variables locales. Accederá a esos argumentos con compensaciones negativas. Cuando se inicia la función C, ejecuta un prólogo de función que guarda el puntero base para el marco de pila de B y establece BP igual a SP porque está ingresando a un nuevo marco. Luego asigna espacio en la pila para sus propias variables locales, así como el espacio que B usará para cualquier bloque de vinculación que cree para sus llamadores o para las cosas que llama. El video también menciona una optimización común en la que el compilador podría deshacerse de BP y realizar toda la indexación en función del puntero de pila RSP para obtener un registro más de propósito general.

  • 01:10:00 En esta sección, el instructor lleva a la audiencia a través del proceso de compilación de LV miR hasta el código ensamblador. El primer paso consiste en definir la función 'fib' como una función accesible globalmente utilizando algunas directivas del ensamblador, como la directiva global fib y la alineación. Luego, el prólogo de la función se guarda con una cola push de var BP y una cola mob de RSP rbp. El código ensamblador también empuja un par de registros a la pila, que son registros guardados de Kali, antes de mover el argumento a la función, RTI, y lo guarda en el registro RBX. Por último, se evalúa una instrucción de comparación para comprobar si el valor de N es menor que dos y, en caso afirmativo, devuelve el valor de entrada. De lo contrario, pasa por un código de línea recta para calcular fib de n menos uno y fib de n menos dos, sumarlos y devolver ese resultado.

  • 01:15:00 En esta sección, el video analiza los saltos condicionales y los distintos comportamientos que ocurren a continuación en el código según los resultados de la comparación. La instrucción JGE salta a la etiqueta del lado falso de la operación de bifurcación LLVM cuando n es mayor o igual a 2, mientras que las operaciones corresponden al lado verdadero de la operación cuando n es menor que 2. La instrucción LEA se utiliza para cálculo de dirección, mientras que la operación de movimiento guarda el resultado de la llamada de función en R14. El siguiente conjunto de instrucciones calcula el valor de n-2, lo almacena en RDI y luego llama a fib en n-2, devolviendo el resultado a nuestro AX. Finalmente, la operación agrega R14 a nuestro AX.

  • 01:20:00 En esta sección, el video analiza la conversión de código C a código ensamblador. El orador explica que el proceso utiliza un gráfico de flujo de control, compuesto por bloques básicos conectados por aristas de flujo de control, para representar el código. También mencionan la complejidad de tratar con convenciones de llamada en código ensamblador. La función epílogo se usa para restaurar registros antes que nada en el marco de la pila, antes de devolver el resultado. El video concluye resumiendo los principales temas tratados a lo largo de la sección.
 

Lección 6. Programación multinúcleo



Lección 6. Programación multinúcleo

Esta videoconferencia analiza la programación multinúcleo y la aparición de procesadores multinúcleo debido a la Ley de Moore y el final del escalado de frecuencias de reloj. El orador explica el problema de la densidad de potencia que enfrentan los procesadores y cómo llevó a la adición de múltiples núcleos a los chips para mantenerse al día con la Ley de Moore. La conferencia también cubre los conceptos básicos de los protocolos de coherencia de caché en hardware de memoria compartida y plataformas de concurrencia como Pthreads, TBB, OpenMP y Silk que brindan abstracciones para la programación paralela. Los pros y los contras de cada plataforma se analizan y demuestran con ejemplos de implementación de programas de Fibonacci. El video proporciona una descripción general completa de la programación multinúcleo y los desafíos y soluciones que enfrentan los programadores.

El video también cubre varios aspectos de Silk, una herramienta de abstracción para manejar el procesamiento paralelo. El orador analiza temas como la seda anidada para bucles, la generación de código ensamblador, la reducción mediante reductores, el planificador y la optimización del rendimiento. También brindan una descripción general del ecosistema Silk y las herramientas relacionadas, como el desinfectante de seda y la escala de seda para depurar y analizar la escalabilidad, respectivamente. La conclusión principal es que escribir programas paralelos para procesadores multinúcleo puede ser un desafío, pero Silk simplifica el proceso al manejar tareas complejas de manera eficiente, brindando a los programadores más control sobre la ejecución de su código.

  • 00:00:00 En esta sección, el instructor analiza la programación multinúcleo y las razones de la aparición de los procesadores multinúcleo. Con el advenimiento de la ley de Moore, que afirma que la cantidad de transistores que pueden caber en un chip se duplica cada dos años, y el final de la escala de frecuencias de reloj alrededor de 2004 a 2005, los proveedores de semiconductores comenzaron a producir chips con múltiples núcleos de procesador. Esto se debió al hecho de que ya no era posible aumentar la frecuencia de los núcleos individuales en un chip, por lo que fue necesario cambiar a un modelo de diseño que permitiera el procesamiento en paralelo. El instructor también aclara la relación entre la cantidad de transistores en un chip y la frecuencia máxima del procesador.

  • 00:05:00 En esta sección, el orador analiza el problema de la densidad de potencia que enfrentan los procesadores, donde el aumento de la frecuencia del reloj hace que la densidad de potencia aumente exponencialmente. Esto llevó a que se agregaran múltiples núcleos a los chips para mantenerse al día con la Ley de Moore y no exceder los límites de densidad de potencia. Luego, el orador presenta la arquitectura multinúcleo abstracta, conocida como multiprocesador de chip, y describe las conferencias sobre desafíos de hardware y soluciones de software para programar programas paralelos en máquinas multinúcleo utilizando diferentes plataformas de concurrencia, como subprocesos P, subprocesos winAPI, subprocesos Intel. bloques de construcción, openmp, etc.

  • 00:10:00 En esta sección, el orador explica cómo funcionan los cachés en la programación multinúcleo. Cuando un procesador carga un valor en su caché desde la memoria principal, mantendrá ese valor en caché en caso de que necesite acceder a él nuevamente en el futuro. Si otro procesador quiere cargar el mismo valor, también puede obtenerlo a través de la memoria caché del primer procesador en lugar de ir hasta la memoria principal. Sin embargo, surge un problema cuando un procesador actualiza el valor en su propio caché, lo que hace que el valor en el caché de otro procesador sea obsoleto. El protocolo MSI es una solución básica a este problema, que etiqueta las líneas de caché con tres estados posibles (M, S e I) para garantizar la coherencia entre los cachés.

  • 00:15:00 En esta sección, la conferencia analiza los conceptos básicos de los protocolos de coherencia de caché en hardware de memoria compartida, en particular cómo las modificaciones a una línea de caché en el caché de un procesador pueden invalidar las copias de la misma línea de otros cachés. La conferencia presenta un protocolo simple y explica cómo existen en la práctica otros protocolos más complejos. El hardware es responsable de gestionar los conflictos cuando varios procesadores modifican la misma línea de caché, pero esto puede provocar una "tormenta de invalidación" y ralentizar el rendimiento. La conferencia también señala que las plataformas de concurrencia pueden abstraer estas complejidades y ayudar con la sincronización y la comunicación en la programación paralela.

  • 00:20:00 En esta sección, el orador analiza diferentes plataformas de concurrencia usando el ejemplo de los números de Fibonacci. El programa de Fibonacci se implementa mediante un algoritmo recursivo que calcula los números de Fibonacci varias veces, lo que lo convierte en un algoritmo deficiente. Las dos llamadas recursivas se pueden paralelizar ya que son cálculos completamente independientes. Pthreads, una API estándar para subprocesos, se puede utilizar para implementar esta paralelización.

  • 00:25:00 En esta sección, el orador analiza Pthreads, una biblioteca de funciones que permiten la concurrencia en la programación. Pthreads proporciona una plataforma de concurrencia "hágalo usted mismo", ya que le permite especificar la concurrencia en su código utilizando una biblioteca de funciones con una semántica especial. Cada subproceso en Pthreads implementa una abstracción de un procesador y se multiplexa en los recursos reales de la máquina. Pthreads también proporciona máscaras que simplifican los protocolos involucrados en la coordinación de subprocesos internos. La biblioteca Pthreads tiene funciones clave como pthread_create, que almacena e identifica el nuevo subproceso que crea pthread, y pthread_join, que espera hasta que finaliza el subproceso antes de continuar con el código. El orador demuestra cómo implementar una serie de Fibonacci usando Pthreads.

  • 00:30:00 En esta sección, el presentador analiza la implementación del código Pthreads para ejecutar la secuencia de Fibonacci en paralelo. Explican que si el tamaño de entrada es lo suficientemente pequeño, es mejor ejecutar el programa secuencialmente debido al costo de crear hilos en paralelo. El código ordena el argumento de entrada al subproceso y lo almacena en la estructura de argumentos. El presentador analiza Pthread create, Pthread join y algunas de sus desventajas, como volverse mucho más complicado si el código necesita crear hilos recursivamente. También mencionan que este código solo crea un hilo, por lo que la máxima aceleración posible es dos si se ejecuta en cuatro procesadores.

  • 00:35:00 En esta sección del video, se discuten los problemas con Pthreads y el código para la secuencia de Fibonacci. La alta sobrecarga para crear un hilo da como resultado una simultaneidad de granularidad gruesa, y el problema de escalabilidad es que los dos núcleos no están haciendo la misma cantidad de trabajo. El código también carece de modularidad, ya que la lógica de Fibonacci no está bien encapsulada dentro de una función, lo que dificulta su mantenimiento y modificación. El código también se vuelve complicado debido a la ordenación de argumentos, que es similar a tener que escribir código en ensamblador. Luego, el video presenta Threading Building Blocks (TBB), una biblioteca desarrollada por Intel para brindar una solución a estos problemas.

  • 00:40:00 En esta sección, el video analiza el uso de la biblioteca Intel Thread Building Blocks (TBB), una biblioteca de C++ diseñada para permitir a los programadores usar hilos nativos y un algoritmo de robo de trabajo sin tener que lidiar con hilos directamente. Al especificar tareas, la carga de TBB las equilibra entre subprocesos, lo que hace que el código sea más sencillo de escribir y funciona mejor que el uso de subprocesos POSIX. El video muestra un ejemplo de implementación de un programa de Fibonacci usando TBB, demostrando cómo crea recursivamente tareas secundarias, lo que permite un mayor paralelismo y escalabilidad en múltiples procesadores. TBB también proporciona plantillas para el paralelismo de bucles, la agregación de datos y la canalización de software, así como clases de contenedores concurrentes para un acceso concurrente seguro a los datos compartidos.

  • 00:45:00 En esta sección, el ponente presenta dos soluciones lingüísticas al problema de la concurrencia: OpenMP y Silk. OpenMP es una especificación que proporciona extensiones lingüísticas a C y C++, así como a Fortran, utilizando pragmas de compilación para especificar qué piezas de código deben ejecutarse en paralelo. Admite el paralelismo de bucles, el paralelismo de tareas y el paralelismo de canalizaciones, y tiene muchas directivas de programación y uso compartido de datos, así como construcciones de sincronización. El orador brinda un ejemplo de implementación de Fibonacci en OpenMP, que es más simple y funciona mejor que usar Pthreads o TBB. OpenMP es una solución popular para escribir programas paralelos, ya que proporciona muchas funciones y simplifica el código.

  • 00:50:00 En esta sección, el orador analiza la plataforma de programación Silk, que admite el paralelismo conjunto y vectorial e incluye un programador de robo de trabajo demostrablemente eficiente. El programa también tiene una biblioteca de hiperobjetos para paralelizar código con variables globales y viene con herramientas de programación como un detector de carrera de pantalla de seda y un analizador de escalabilidad llamado vista de seda. El orador también señala que, si bien no usarán silk plus en la clase, usarán un mejor compilador conocido como taper LLVM, que produce un mejor código en relación con su compilador base que todas las demás implementaciones de silk disponibles.

  • 00:55:00 En esta sección, el uso de declaraciones de sincronización de seda y engendro de seda para habilitar la ejecución paralela se analiza a través de ejemplos. El primer ejemplo es la capa de sal para Fibonacci, que incluye seda spawn y declaraciones de sincronización de seda para sugerir que fib de n-1 se puede ejecutar en paralelo con la función que lo llama mientras se ejecuta fib de n-2. Sin embargo, el sistema de tiempo de ejecución decide si ejecutar o no estas tareas en paralelo. Otro ejemplo discutido es el paralelismo de bucles, donde la sentencia for de seda se usa para ejecutar un bucle for en paralelo con el compilador dividiendo recursivamente el espacio de iteración a la mitad y usando sentencias de sincronización de seda y engendro de seda hasta que el rango se vuelve demasiado pequeño para ejecutar en paralelo. Es importante garantizar que las iteraciones sean independientes para obtener resultados correctos, y el uso de seda agrega algunos gastos generales adicionales.

  • 01:00:00 En esta sección, el video analiza el uso de seda anidada para bucles y los detalles de la generación de código ensamblador usando una bandera en el compilador clang. El código de ejemplo para una suma de valores usando un bucle for de seda plantea el problema de la carrera de determinación cuando varios procesadores escriben en la misma ubicación de memoria. Silk aborda este problema mediante el uso de reductores, que son hiperobjetos que manejan la función de suma para una variable dada, mientras registran y anulan el registro de las macros reductoras. Esta es una forma de lidiar con el problema de la reducción, que puede surgir en la programación multinúcleo, con muchos otros operadores de reducción también disponibles para su uso.

  • 01:05:00 En esta sección, el orador analiza los reductores en Silk: estructuras algebraicas que tienen una operación binaria asociativa y un elemento de identidad. Silk tiene varios reductores predefinidos, que incluyen suma, multiplicación, mínimo, máximo y XOR, y puede definir su propio reductor. Uno de los beneficios de Silk es que siempre hay una interpretación en serie válida del programa, lo que facilita la depuración, y tiene un programador de tiempo de ejecución que supervisa y asigna el programa a los núcleos de procesador disponibles, utilizando un algoritmo de programación que roba trabajo para equilibrar las tareas. igualmente. A diferencia de otras plataformas de concurrencia, el programador de Silk es teóricamente eficiente.

  • 01:10:00 En esta sección, el orador brinda una descripción general de alto nivel del ecosistema Silk para la programación multinúcleo, que incluye cómo compilar el código fuente de Silk, comparar el rendimiento en paralelo y en serie y depurar problemas con herramientas como Silk Sanitizer y Silk escala. También enfatizan la importancia de optimizar el rendimiento del programa en serie y cómo el programador de Silk puede manejar diferentes tareas durante la ejecución del programa. Además, el ponente explica cómo la escala de seda puede determinar el número máximo de procesadores que puede aprovechar un código, lo que la convierte en una herramienta útil para analizar la escalabilidad.

  • 01:15:00 En esta sección, el orador resume los puntos clave de la conferencia sobre programación multinúcleo. Explican que la mayoría de los procesadores modernos tienen múltiples núcleos, lo que hace necesario escribir programas paralelos para un alto rendimiento. Sin embargo, escribir tales programas puede ser difícil, que es donde entra en juego Silk. Esta herramienta abstrae los núcleos del procesador del programador y maneja la sincronización, los protocolos de comunicación y el equilibrio de carga. El orador también menciona un proyecto futuro donde los estudiantes implementarán su propio protector de pantalla paralelo usando Silk.
 

Lección 7. Carreras y Paralelismo



Lección 7. Carreras y Paralelismo

El video cubre una variedad de temas relacionados con carreras, paralelismo y problemas de computación en la programación de Silk. Algunos conceptos clave cubiertos incluyen las declaraciones de generación y sincronización para la ejecución simultánea, la importancia de evitar las condiciones de carrera y el uso del detector de carreras de Silk para identificarlas. El video también cubre la ley de Amdahl, la ley del trabajo y la ley de amplitud como formas de cuantificar la cantidad de paralelismo en un programa, junto con formas de analizar el trabajo y la amplitud de los cálculos. También se analizan la posible aceleración y el paralelismo de los algoritmos de clasificación en paralelo y el concepto de la teoría de la programación, centrándose en el teorema del programador codicioso. En general, el video brinda información valiosa para comprender y optimizar el rendimiento del programa en la programación de Silk.

El video explica los corolarios del límite del programador codicioso, que esencialmente establece que cualquier programador codicioso logra una aceleración lineal casi perfecta siempre que T1/Tinfinity sea mayor o igual a P^2. El programador de seda, que utiliza un programador de robo de trabajo, puede lograr una aceleración lineal casi perfecta siempre que la cantidad de procesadores sea mucho menor que T1/Tinfinity. El sistema de tiempo de ejecución de seda funciona manteniendo una plataforma de trabajo de hilos listos y manipula la parte inferior de la plataforma como una pila. El video también analiza Cactus Stack, que permite múltiples vistas de pilas en paralelo y hace posibles las llamadas a funciones paralelas. El límite superior en el espacio de pila requerido por la ejecución del procesador P a menudo es mucho más flexible que la cantidad real necesaria, ya que es posible que cada procesador no necesite recorrer todo el gráfico de cálculo cada vez que roba trabajo.

  • 00:00:00 En esta sección, el instructor introduce el tema de las carreras y el paralelismo en Silk, que será importante para la próxima tarea y proyecto. Se revisan los conceptos básicos de las declaraciones de generación y sincronización de Silk, que permiten la ejecución simultánea de funciones primarias y secundarias. El instructor también enfatiza la importancia de reunirse con los miembros de la política del MIT y evitar las condiciones de carrera en el código, lo que puede tener consecuencias desastrosas, como se vio en ejemplos anteriores. Los errores de carrera más difíciles de encontrar son aquellos que causaron eventos catastróficos, y las pruebas convencionales a menudo no son efectivas. Silk ofrece una herramienta para ayudar a identificar posibles errores de carrera en el código.

  • 00:05:00 En esta sección, el video explica cómo las carreras son uno de los errores más difíciles de encontrar para los desarrolladores porque pueden ocurrir solo en casos excepcionales cuando los códigos lógicamente paralelos acceden a la misma ubicación de memoria y al menos uno registra una escritura lo. Como ejemplo, el video muestra un código simple que utiliza un gráfico de dependencia para mostrar cómo el error de carrera compartido entre dos rutas paralelas no siempre ocurre. La carrera ocurre cuando ambas tiendas escriben en la misma ubicación de memoria, lo que podría dar como resultado diferentes salidas según la ruta de ejecución que se ejecute completamente primero.

  • 00:10:00 En esta sección, el orador explica el concepto de carreras de determinación, que ocurren cuando dos instrucciones acceden a la misma ubicación de memoria y al menos una de las instrucciones es una operación de escritura, lo que resulta en un comportamiento no determinista en el programa. El orador brinda consejos sobre cómo evitar las carreras, como garantizar que las iteraciones de un bucle for de Silk sean independientes y asegurarse de que el código entre una declaración de generación de Silk y la declaración de sincronización de Silk correspondiente también sea independiente. El orador también señala que el tamaño de la palabra de la máquina es importante, y se debe tener cuidado al leer y escribir en estructuras de datos empaquetados que utilizan tipos no estándar.

  • 00:15:00 En esta sección, el video analiza el "detector de carrera" de la plataforma Silk, que puede ayudar a identificar posibles condiciones de carrera en un programa. Mediante el uso de la bandera '-f sanitized equal to silk' para generar un programa instrumentado, Silk puede informar y localizar razas infractoras, lo que ayuda a depurar el código. El video también explica el concepto de paralelismo y cómo el modelo de ejecución de Silk utiliza gráficos de cálculo para ilustrar el desarrollo del cálculo durante la ejecución. Es importante comprender estos conceptos cuando se trata de optimizar y mejorar el rendimiento del programa.

  • 00:20:00 tipos de vértices en el dag de cálculo: el hilo inicial, los hilos de continuación, los hilos de llamada de función y los hilos finales. El hilo inicial contiene la primera instrucción a ejecutar, y el hilo final contiene la última instrucción ejecutada en el programa. Los hilos de continuación representan la continuación de una operación de generación, mientras que los hilos de llamada de función representan la ejecución de una llamada de función. Es importante tener en cuenta que el dag de cálculo se desarrolla dinámicamente durante la ejecución y no tiene en cuenta el procesador, lo que significa que el sistema de tiempo de ejecución descubre cómo asignar tareas a los procesadores en tiempo de ejecución. En resumen, el dag de computación es una herramienta poderosa para comprender el paralelismo y la concurrencia de un programa.

  • 00:25:00 En esta sección, aprendemos sobre dags de computación y cómo se pueden usar para analizar el paralelismo en un programa. El dag de cálculo representa las dependencias entre las diferentes partes del programa y tiene diferentes tipos de bordes, incluidos los bordes de generación, los bordes de llamada, los bordes de retorno y los bordes de continuación. Es posible usar dags de computación para analizar cuánto paralelismo hay en un programa, y usamos la ley de Amdahl para cuantificar la cantidad de paralelismo. En el ejemplo proporcionado, hay menos de siete nodos que deben ejecutarse secuencialmente, lo que indica que existe cierto grado de paralelismo en el cálculo.

  • 00:30:00 En esta sección, se introduce el concepto de la Ley de Amdahl como una forma de determinar la máxima aceleración posible en el procesamiento paralelo. Se determina que la fracción serial del programa es 3/18, lo que da como resultado una aceleración máxima de 6. Si bien la ley de Amdahl proporciona un límite superior para el paralelismo, a menudo es demasiado flexible en casos prácticos. La ley de trabajo y la ley de extensión se presentan como definiciones alternativas de paralelismo, donde la ley de trabajo establece que el tiempo de ejecución en los procesadores P es mayor o igual que el trabajo del programa dividido por P, y la ley de extensión establece que el tiempo de ejecución en procesadores P es al menos el tiempo de ejecución en un número infinito de procesadores. Estas leyes proporcionan mejores límites superiores para la aceleración máxima que la Ley de Amdahl en muchos casos.

  • 00:35:00 En esta sección, el orador analiza cómo componer el trabajo y abarcar cantidades de diferentes cálculos. Explican que cuando se ejecutan dos cálculos paralelos, el trabajo sigue siendo la suma del trabajo de los cálculos individuales, y el intervalo es el máximo del intervalo de los cálculos individuales. El orador también define la aceleración en los procesadores P y analiza la aceleración sublineal, lineal y superlineal. Señalan que la aceleración máxima posible es igual al paralelismo de la computación, que es igual a la cantidad promedio de trabajo por paso a lo largo de la computación. En general, esta sección proporciona información sobre la composición de los cálculos y cómo medir su paralelismo.

  • 00:40:00 En esta sección, el orador analiza cómo analizar el trabajo y el alcance de los cálculos para calcular el paralelismo máximo, utilizando ejemplos como un DAG de cálculo y un algoritmo de clasificación rápida en paralelo. El orador presenta el analizador de escalabilidad Silk Scale, que utiliza la instrumentación del compilador para analizar la ejecución en serie de un programa y derivar los límites superiores de la aceleración paralela del programa. El orador también menciona que analizar el paralelismo de grandes cálculos a mano puede ser tedioso, pero Silk Scale puede ayudar con esto.

  • 00:45:00 En esta sección, el video analiza los resultados de ejecutar un cálculo en paralelo y generar un gráfico que muestra la aceleración observada, así como los límites de las leyes de trabajo y lapso. El gráfico muestra que la aceleración máxima es de aproximadamente 5, lo que indica que el paralelismo en el programa es bajo. El análisis revela que el cuello de botella del paralelismo es ejecutar la función de partición secuencialmente, y el trabajo esperado y el intervalo de la versión paralela de ordenación rápida es del orden de n log n. El máximo paralelismo que se puede lograr es del orden de log log n, que no es muy alto. Para aumentar el paralelismo, la función de partición debe estar paralelizada.

  • 00:50:00 En esta sección, el orador analiza la importancia de implementar el paralelismo en los algoritmos de ordenación de partición y combinación para ver una aceleración significativa. Las versiones paralelas de estos algoritmos tienen un lapso general ligado con log cuadrado n y un alto paralelismo de n sobre log n. Además, existen muchos otros algoritmos paralelos prácticos que tienen un alto paralelismo y un límite de trabajo asintóticamente igual al del algoritmo secuencial correspondiente. El orador también presenta el concepto de la teoría de la programación y explica que un programador centralizado puede asignar los DAG de cómputo a los procesadores disponibles en tiempo de ejecución, mientras que en la programación Silk se utiliza un programador distribuido. Se utiliza como ejemplo un programador codicioso, que hace todo lo posible en cada paso del cálculo.

  • 00:55:00 En esta sección, se introduce el concepto de un planificador codicioso, que realiza la mayor cantidad de trabajo posible en el paso de tiempo actual sin pensar en el futuro. Se define un paso completo, en el que al menos las cadenas P están listas, y un paso incompleto, en el que están listas menos cadenas P. El famoso teorema, mostrado por primera vez por Ron Graham en 1968, establece que el límite de tiempo logrado por un programador codicioso es menor o igual a T1/P + T infinito, siendo T1 el trabajo y T infinito el lapso. Se proporciona la prueba de este teorema, y se muestra que cualquier programador codicioso logra dentro de un factor de dos del tiempo de ejecución óptimo.

  • 01:00:00 En esta sección, el video explica los corolarios del límite del programador codicioso, que logra dentro de un factor de dos del programador óptimo. El corolario establece que cualquier programador codicioso logra una aceleración lineal casi perfecta cuando T1/Tinfinity es mayor o igual a P^2, donde T1/P multiplicado por T infinito mide la cantidad de paralelismo en el cálculo en comparación con la cantidad de procesadores. disponible. El programador de seda utiliza un programador de robo de trabajo, que tiene un tiempo de ejecución esperado de TP igual a T1/P más orden T infinito, con una O grande delante de T infinito para dar cuenta de los gastos generales de programación, y puede lograr casi aceleración lineal perfecta siempre que el número de procesadores sea mucho menor que T1/Tinfinity. El sistema de tiempo de ejecución de seda funciona manteniendo una plataforma de trabajo de hilos listos y manipula la parte inferior de la plataforma como una pila. La instrumentación en la Escala de Seda permite medir términos de trabajo y vano para determinar el paralelismo en el programa.

  • 01:05:00 En esta sección, el orador analiza el concepto de generación y paralelismo en los procesadores. Explican que cuando un procesador llama a una función, coloca el marco de esa función en la parte inferior de su pila y puede generar marcos en la parte inferior de la pila. Pueden ocurrir múltiples procesos en paralelo, y se pueden realizar devoluciones a partir de engendros y llamadas. Cuando los trabajadores se quedan sin trabajo, roban de la parte superior de la plataforma de otro procesador. El famoso teorema establece que los trabajadores roban con muy poca frecuencia, lo que genera una aceleración casi lineal. El orador también señala que Silk admite las reglas de C para punteros, donde un puntero a un espacio de pila se puede pasar de un padre a un hijo, pero no de un hijo a un padre.

  • 01:10:00 En esta sección del video, el orador habla sobre la pila de cactus, que es la pila que puede ver una tarea en el gráfico de cálculo de ancestros de un programa Silk. Esta pila permite múltiples vistas de pilas en paralelo, lo que hace posibles las llamadas a funciones paralelas. El orador explica que el espacio de pila requerido por un programa Silk se puede encontrar tomando el espacio de pila requerido por una ejecución en serie del programa (S sub 1) y multiplicándolo por el número de procesadores (P) que se usarán (S sub P ≤ P x S sub 1). El orador proporciona una prueba de alto nivel de este concepto y señala que el límite superior en el espacio de pila requerido por la ejecución del procesador P a menudo es mucho más flexible que la cantidad real necesaria, ya que es posible que cada procesador no necesite recorrer todo el gráfico de cálculo cada vez. tiempo que roba trabajo.
 

Lección 8. Análisis de Algoritmos Multiproceso



Lección 8. Análisis de Algoritmos Multiproceso

Este video analiza el método maestro para analizar las recurrencias de divide y vencerás, y lo aplica a algoritmos de subprocesos múltiples comparando la base logarítmica B de n con la base logarítmica B de A con F de N para determinar su crecimiento en n y el trabajo requerido. El video presenta una hoja de trucos con soluciones para algoritmos básicos de subprocesos múltiples y cubre temas como el trabajo y el análisis de intervalos, la eficiencia del trabajo y la superación de los costos generales a través de la optimización del tamaño de grano. Se enfatiza la importancia de la empatía cuando se comunican temas técnicos y se introduce el concepto de un DAG como un medio para equilibrar el trabajo y la extensión para aumentar el paralelismo y disminuir el tiempo de ejecución.

El video también analiza el análisis de algoritmos de subprocesos múltiples, centrándose en el trabajo y el intervalo, y cómo maximizar el paralelismo y minimizar el intervalo para lograr una aceleración lineal casi perfecta. El orador sugiere un enfoque de divide y vencerás para los algoritmos de subprocesos múltiples, donde la cantidad de tareas asignadas a los subprocesos es lo suficientemente grande, y advierte contra la generación de numerosas tareas pequeñas debido a los gastos generales de programación. El código de ejemplo presentado incluye uno eficiente y uno pésimo. El orador también analiza cómo representar submatrices en la codificación e indexación bidimensional y enfatiza el uso de 'restringir' en el código de multiplicación de matrices divide y vencerás para mejorar el rendimiento.

  • 00:00:00 En esta sección, el instructor comienza recordando a los estudiantes sobre las recurrencias de divide y vencerás y el método general para resolverlas llamado método maestro. El método trata con las recurrencias y su forma T(n) = a*T(n/B) + F(n), donde a es una constante, B es el factor de división y F(n) es la cantidad total de trabajo para dividir el problema en subproblemas de tamaño n/B. A los estudiantes se les recuerda el árbol de recurrencia y cómo cada nivel se divide en subproblemas de tamaño n/B, suman el tiempo de ejecución a través de las filas, calculan la altura del árbol y lo multiplican por el número de subproblemas en cada nivel (un ^k). Finalmente, los estudiantes calculan que n^log base B de A es el tiempo total de ejecución del algoritmo.

  • 00:05:00 En esta sección, el orador explica cómo determinar el crecimiento de n y el trabajo requerido al evaluar algoritmos multiproceso. La clave es comparar la base logarítmica B de n con la base logarítmica B de A con F de N. El hablante cubre tres casos posibles, siendo el primero cuando la base logarítmica B n es mucho más grande que F de n. En este caso, la fracción constante del peso está en las hojas, lo que lleva a que la respuesta sea n al logaritmo base B de A. El segundo caso es cuando el logaritmo base B n es aproximadamente igual a F de n. Para esto, agrega un logaritmo adicional, y la respuesta es n al logaritmo base B de un logaritmo a la k más 1 de n. Por último, el tercer caso es cuando an para log base B es mucho menor que F de N, lo que significa que F tiene que satisfacer una condición de regularidad, que es satisfecha por todas las funciones que estarán viendo como polinomios y logaritmos.

  • 00:10:00 En esta sección, el orador presenta una hoja de trucos con soluciones de algoritmos multiproceso básicos que se usan comúnmente en informática. El primer algoritmo, T(n) = T(n/2) + n, tiene una solución de Θ(n^2) ya que cae en el caso uno. El segundo algoritmo, T(n) = T(n/2) + n^2logn, tiene una solución de Θ(n^2logn) ya que cae en el caso dos con k = 0. Para el tercer algoritmo, T(n) = T(n/2) + n^2, la solución es Θ(n^2) ya que cae en el caso uno. El cuarto algoritmo, T(n) = 2T(n/2) - n, es engañoso ya que no se incluye en ningún caso del método maestro y tiene una solución de Θ(n^2loglogn).

  • 00:15:00 En esta sección, el orador analiza el método Aqua Bazi y cómo es más complicado que el método maestro, que es suficiente para analizar la mayoría de los programas. Luego brindan un ejemplo de un bucle paralelo con código de transposición de matriz en el lugar donde el bucle externo está paralelizado. El orador enfatiza la importancia de definir correctamente el espacio de iteración y el equilibrio de carga para un procesamiento paralelo eficiente. También explican cómo se implementan los bucles mediante el compilador de seda abierto y el sistema de tiempo de ejecución.

  • 00:20:00 En esta sección, el orador describe un programa recursivo para un ciclo que utiliza divide y vencerás para dividir el ciclo en dos partes y llamarse recursivamente a sí mismo en cada lado hasta que alcance una iteración de un elemento. El trabajo de este cálculo se analiza en términos de trabajo y lapso, siendo el trabajo de la hoja orden n al cuadrado y la parte superior es theta n porque cada nivel desde las hojas hasta la raíz tiene solo n nodos. El sistema de tiempo de ejecución de seda abierto no tiene una primitiva de bucle, por lo que los bucles se traducen efectivamente en este enfoque de divide y vencerás en paralelo.

  • 00:25:00 En esta sección, el orador analiza el trabajo y el análisis de lapso de un algoritmo multiproceso. Explica que el trabajo total es Θ(n²) porque se realiza un trabajo constante para cada una de las n hojas del árbol binario completo. El lapso del control de bucle es log(n), lo que significa que un número infinito de procesadores podría completar la tarea en tiempo logarítmico. Sin embargo, dado que hay un componente lineal en el cálculo (n), el intervalo total es Θ(n). Por lo tanto, el paralelismo es Θ(n), que es una buena cantidad para la mayoría de los sistemas prácticos. Luego, el orador explora el escenario en el que también se paraleliza el bucle interno y analiza la cantidad de trabajo resultante.

  • 00:30:00 En esta sección del video, el profesor analiza el concepto de eficiencia del trabajo en algoritmos paralelos. Paralelizar los algoritmos no cambia el trabajo, pero es de esperar que reduzca el alcance del cálculo para lograr un gran paralelismo. Sin embargo, a veces, la paralelización puede generar más trabajo, lo que puede ser problemático porque ralentiza el programa en comparación con el algoritmo original. Los algoritmos paralelos eficientes en el trabajo son lo que el profesor está interesado en enseñar, ya que pueden reducir el lapso para lograr un gran paralelismo sin agregar más trabajo. El profesor enfatiza la importancia de hacer preguntas y cometer errores en el proceso de aprendizaje, ya que puede ayudar a otros que pueden tener las mismas preguntas pero tienen miedo de preguntar. Alienta a los estudiantes a participar y participar en el proceso de aprendizaje, incluso si no están en el 10% superior.

  • 00:35:00 En esta sección, se enfatiza la importancia de la empatía en la comunicación cuando se trata de temas técnicos. El profesor alienta a los estudiantes a ser pacientes con otros en la clase que pueden no estar familiarizados con el material que se está cubriendo. Pasando al análisis de algoritmos multiproceso, se presenta un algoritmo divide y vencerás para la suma de vectores, y se encuentra que el paralelismo es n sobre log n. Se analiza la relación entre el paralelismo y la cantidad de procesadores, y el profesor enfatiza que, si bien más paralelismo puede parecer mejor, solo es beneficioso hasta cierto umbral.

  • 00:40:00 En esta sección, el orador analiza la optimización de algunos de los gastos generales en un algoritmo de subprocesos múltiples, específicamente los gastos generales de llamadas a subrutinas. Introducen el concepto de "tamaño de grano", que sugiere al compilador que hay hasta G elementos por fragmento en las hojas del proceso divide y vencerás. Esto permite que la sobrecarga de la subrutina se amortice en iteraciones G en lugar de solo una, lo que resulta en un mejor rendimiento. Si no se especifica el tamaño de grano, el sistema hace su mejor estimación para minimizar la sobrecarga. El hablante desglosa las variables I, G y s para analizar el trabajo en este contexto y lo compara con el trabajo en el código original sin el control paralelo.

  • 00:45:00 En esta sección, el orador habla sobre el análisis de algoritmos de subprocesos múltiples y cómo el control de bucle es económico en un procesador moderno fuera de servicio. Observan el lapso, que es el tiempo que lleva ejecutar el algoritmo con una cantidad infinita de procesadores, y analizan el costo general frente al costo de las iteraciones. El hablante desglosa el lapso en términos del número de hojas y las operaciones de colores, denominadas 's', que deben realizarse en cada una de ellas. También responden preguntas sobre el número de nodos internos en un árbol binario completo y los caminos tomados para calcular el tramo.

  • 00:50:00 En esta sección, el disertante analiza el análisis de algoritmos de subprocesos múltiples, particularmente el concepto de un DAG (gráfico acíclico dirigido) y cómo afecta la ruta del algoritmo. Hacen hincapié en la necesidad de independencia entre diferentes subárboles del DAG para permitir el procesamiento paralelo. El objetivo es equilibrar el trabajo y la duración del algoritmo, ya que estos dos factores funcionan en direcciones opuestas. La clave es que G (la cantidad de paralelismo) sea mucho mayor que s sobre I (la parte secuencial del algoritmo), lo que permite una sobrecarga menor y un procesamiento más rápido. El orador también menciona una implementación de este concepto, pero señala que se discutirá más adelante en la serie de conferencias.

  • 00:55:00 En esta sección, el orador presenta una implementación de algoritmos multihilo usando un bucle for para sumar dos vectores. El bucle usa un operador llamado V add para realizar sumas de vectores en serie, y el bucle genera sumas en grupos de G usando un vector de tamaño G. Suponiendo que G es igual a uno, el trabajo de los bucles es de orden n, y el lapso también es pedido nm. El paralelismo se mide tomando la relación entre el trabajo y el lapso, que es n dividido por n, que se simplifica a 1. El orador enfatiza que el objetivo de analizar los algoritmos de subprocesos múltiples es aumentar el paralelismo y disminuir el lapso para minimizar el tiempo de ejecución, y destaca la técnica llamada minería a cielo abierto, donde un bucle de longitud N se reemplaza por un bucle anidado doble para paralelizar los cálculos, como una forma de mejorar los algoritmos de subprocesos múltiples.

  • 01:00:00 En esta sección, el ponente analiza el rendimiento de los algoritmos multiproceso en términos de trabajo y duración. Discuten cómo minimizar el intervalo para maximizar el paralelismo, ya que el intervalo está en el denominador. La clave es generar diez veces más paralelismo que los procesadores si uno quiere una aceleración lineal casi perfecta. El orador también sugiere intercambiar algo de paralelismo para reducir la sobrecarga de trabajo si es necesario. Fomentan jugar con el tamaño de grano para hacerlo, siempre que se mantenga suficiente paralelismo.

  • 01:05:00 En esta sección, el orador analiza el uso de estrategias de divide y vencerás en algoritmos de subprocesos múltiples, y desaconseja generar numerosas tareas pequeñas una tras otra, a menos que se dividan en unas pocas tareas, en cuyo caso la sobrecarga está bien. En general, debe haber un enfoque de divide y vencerás, donde la cantidad de tareas asignadas a los subprocesos es lo suficientemente grande. El orador advierte que tenga cuidado con los gastos generales de programación y sugiere paralelizar el bucle externo en lugar de los bucles internos, que tienen más gastos generales. Los códigos de ejemplo que se presentan aquí muestran uno eficiente, donde la programación ocurre solo una vez, y uno pésimo, donde la sobrecarga ocurre n veces. La multiplicación de matrices se usa como un ejemplo de un algoritmo de subprocesos múltiples que utiliza una estrategia de división y conquista para multiplicar matrices n por n haciendo 8 multiplicaciones de n sobre 2 por n sobre 2 matrices, y luego sumando dos matrices n por n.

  • 01:10:00 En esta sección, el orador analiza cómo representar submatrices en codificación e indexación bidimensional, particularmente en el orden principal de fila y columna principal para lenguajes como C y Fortran. La idea es que cada matriz bidimensional se pueda indexar como una matriz unidimensional y, cuando se trata de submatrices, es necesario sumar el número de filas y la longitud de la matriz larga para saber dónde está el elemento IJ. Además, al implementar divide y vencerás, es crucial conocer las esquinas iniciales de cada una de las cuatro submatrices. En última instancia, el orador enfatiza el uso de 'restringir' en el código de multiplicación de matrices divide y vencerás para decirle al compilador qué elementos pueden o no pueden ser alias.

  • 01:15:00 En esta sección, el orador analiza un algoritmo multiproceso para la multiplicación de matrices. El algoritmo se basa en la subdivisión recursiva de las matrices en submatrices más pequeñas, y cada submatriz se multiplica recursivamente para obtener el resultado final. El orador destaca un pequeño truco para determinar rápidamente si n es una potencia de dos y usa una macro para simplificar la indexación de las matrices. El algoritmo exhibe un alto paralelismo, que se puede reducir para mejorar el rendimiento. También se mencionan otros algoritmos similares.
 

Lección 9. Lo que pueden y no pueden hacer los compiladores



Lección 9. Lo que pueden y no pueden hacer los compiladores

Este video analiza cómo los compiladores pueden optimizar el código, usando varios ejemplos. Explica cómo los compiladores pueden eliminar el almacenamiento innecesario y las referencias a la memoria, y cómo pueden optimizar los bucles para mejorar el rendimiento.

Este video también explica el concepto de pases de optimización del compilador y cómo se pueden usar para mejorar el rendimiento del código. También analiza las limitaciones de los compiladores, específicamente en lo que respecta a la vectorización. Los compiladores solo pueden vectorizar el código si pueden determinar que los punteros en el código no tendrán alias. Si los punteros hacen alias, el compilador no podrá vectorizar el código. Como programador, puede ayudar al compilador anotando sus punteros para proporcionar más información sobre su uso.

  • 00:00:00 En esta conferencia, Tao Schardl analiza lo que los compiladores pueden y no pueden hacer. Explica que estudiar las optimizaciones del compilador puede ayudar a los desarrolladores a comprender cómo escribir código que aproveche las optimizaciones y cómo evitar optimizar manualmente el código que el compilador ya puede optimizar.

  • 00:05:00 El compilador es una gran pieza de software y puede ser absolutamente útil para la depuración cuando el compilador tiene errores. Ayuda a entender dónde el compilador pudo haber cometido un error o dónde el compilador simplemente no hizo lo que pensó que debería poder hacer.

  • 00:10:00 El compilador puede hacer muchas optimizaciones, pero hay algunas cosas que no puede hacer. Por ejemplo, no siempre puede crear una ruta rápida u optimizar bucles.

  • 00:15:00 El compilador puede hacer mucho para optimizar el código, pero hay algunas cosas que no puede hacer bien. Un ejemplo son las estructuras de datos: el compilador no es inteligente con respecto a ellas de la misma manera que lo es con las funciones. Otro son los bucles: el compilador puede hacer algunas optimizaciones en ellos, pero hay restricciones.

  • 00:20:00 Este video de YouTube explica cómo los compiladores pueden usar operaciones simples para reemplazar las más complejas. Por ejemplo, para reemplazar una operación de división, un compilador puede multiplicar por un número mágico y luego cambiar el resultado. Este video también explica cómo funciona la calculadora de direcciones.

  • 00:25:00 El video analiza cómo los compiladores pueden optimizar el código, usando una función simple de "escala vex" como ejemplo. El código se muestra primero sin optimizaciones y luego con varias optimizaciones aplicadas. Las optimizaciones que se muestran incluyen la reducción del número de instrucciones, el uso de instrucciones vectoriales y el uso de números mágicos.

  • 00:30:00 Este video analiza cómo los compiladores pueden optimizar el código eliminando operaciones de memoria innecesarias. En particular, muestra cómo un compilador puede optimizar una función que multiplica dos valores escalares al eliminar la necesidad de almacenar los valores en la memoria. Finalmente, muestra cómo un compilador puede optimizar una función que opera en una estructura al eliminar la necesidad de almacenar la estructura en la memoria.

  • 00:35:00 En este video de YouTube, el orador explica cómo los compiladores pueden optimizar el código al eliminar el almacenamiento innecesario y las referencias a la memoria. Utiliza el ejemplo de una estructura con múltiples campos y demuestra cómo el compilador puede optimizar el código analizando cuidadosamente las matemáticas involucradas en los cálculos de direcciones. Al comprender lo que hace cada instrucción, el compilador puede optimizar el código y eliminar operaciones innecesarias.

  • 00:40:00 El compilador trabaja duro para transformar estructuras de datos y valores escalares para almacenar tanto como sea posible puramente dentro de los registros y evitar el uso de cualquier almacenamiento local si es posible. Para las llamadas a funciones, el compilador ve la instrucción de llamada y el código de la función que se llama. Luego intenta hacer que la función en el código anterior sea aún más rápida.

  • 00:45:00 El compilador puede codificar en línea para evitar la sobrecarga de llamadas a funciones, y también puede optimizar el código eliminando operaciones innecesarias.

  • 00:50:00 En este video de YouTube, el orador explica que hay tres razones principales por las que un compilador no puede alinear una función: si la función es recursiva, si la función está en una unidad de compilación diferente o si la función podría aumentar el tamaño del código y perjudica el rendimiento. El orador también da algunos consejos para controlar funciones en sus propios programas.

  • 00:55:00 Este video muestra cómo los compiladores pueden optimizar los bucles para hacer que los programas se ejecuten más rápido. El levantamiento de código, o movimiento de código invariable en bucle, es una optimización que se puede utilizar para mejorar el rendimiento.

  • 01:00:00 El compilador puede optimizar el código realizando una secuencia de pasos de transformación. Estos pases están diseñados para encontrar propiedades como cálculos de direcciones idénticas y reemplazarlos con un código más eficiente.

  • 01:05:00 El compilador puede vectorizar este bucle, a pesar de que no sabe si las direcciones de 'x' e 'y' se superponen. Esto se debe a que la estructura del código compilado es más complicada que la función de dos líneas que se proporcionó como entrada.

  • 01:10:00 Este video de YouTube explica lo que los compiladores pueden y no pueden hacer. Los compiladores pueden vectorizar el código si el código no contiene bucles. Sin embargo, si el código contiene bucles, el compilador solo puede vectorizar el código si el bucle está lleno de operaciones vectoriales. Si el bucle no está lleno de operaciones vectoriales, el compilador no podrá vectorizar el código.

  • 01:15:00 La cuestión de si un compilador puede o no vectorizar código es difícil, ya que depende de varios factores. En particular, el compilador debe poder determinar si dos punteros crearán alias o no, lo que puede ser una tarea difícil. Como programador, puede ayudar al compilador anotando sus punteros para proporcionar más información sobre su uso.
1...222324252627282930313233343536...74
Nuevo comentario