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

MetaQuotes 2023.04.26 14:28 #291

Lección 10. Medición y tiempo

En este video, los oradores analizan varios aspectos de la medición y el tiempo en la informática, incluidos los factores externos que pueden afectar la precisión. Hacen hincapié en la necesidad de modelos y una comprensión clara de los datos, reduciendo la varianza para compensar los errores y utilizando llamadas de sincronización adecuadas para garantizar la confiabilidad. También analizan los desafíos para medir el rendimiento del software con precisión, como la ley de potencia y los factores no deterministas, al tiempo que destacan herramientas como el modelado de rendimiento, las llamadas de tiempo, los contadores de hardware y los simuladores. Finalmente, advierten que no se debe confiar en una sola herramienta y recomiendan la triangulación y la adaptación como técnicas para garantizar resultados precisos.

El ponente explica la importancia de una medición fiable del rendimiento en la ingeniería de software de rendimiento. Recomienda el uso de estadísticas para medir con precisión el rendimiento y analiza varios tipos de estadísticas resumidas, como la media, que pueden proporcionar medidas útiles de rendimiento en diferentes contextos. Señala que tomar la media aritmética de las proporciones no es un enfoque válido y sugiere usar la media geométrica en su lugar. El orador enfatiza la importancia de elegir la forma correcta de agregar datos al comparar programas y sugiere tomar la estadística de orden inferior, como el mínimo o el 10 %, de varias ejecuciones para comparar el rendimiento con mayor precisión. El orador también analiza diferentes metodologías para medir y comparar el desempeño, incluida la comparación directa y el ajuste de un modelo para derivar estadísticas, pero advierte sobre el problema del ajuste excesivo en el modelado. En general, el video enfatiza la importancia de una medición confiable del desempeño para mejorar el desempeño del programa.

00:00:00 En esta sección, el orador analiza un estudio sobre código de clasificación realizado por uno de sus antiguos alumnos. El código usa el archivo de encabezado time.h para obtener acceso a la rutina de obtención de tiempo del reloj para las mediciones de tiempo. Se cronometra una rutina de clasificación y se calcula e imprime el tiempo transcurrido. El gráfico de los tiempos de ejecución medidos muestra que la rutina de clasificación sigue principalmente un crecimiento de N log N, pero los tiempos medidos son lentos incluso para las matrices más grandes.
00:05:00 En esta sección, un profesor analiza la importancia de tener un modelo para los datos que se observan. Presenta un ejemplo en el que los datos medidos se desvían significativamente de lo que se esperaba y pide a los estudiantes que sugieran posibles hipótesis para esta desviación. Si bien algunos pensaron que podría ser un problema con el caché o la precisión con el tiempo, el profesor señala que podría haber procesos no relacionados ejecutándose en la máquina que están causando la desviación. En este caso, el problema es con la tenencia múltiple, donde la máquina está siendo utilizada por más de un proceso simultáneamente. El profesor enfatiza la necesidad de mediciones de calidad y tener una comprensión clara de lo que significan los datos.
00:10:00 En esta sección, los oradores discuten la medición y el tiempo en la computación, y cómo los factores externos pueden afectar la precisión de las mediciones. Se enfocan específicamente en cómo pueden ocurrir cambios en la frecuencia del reloj debido a la temperatura del sistema y las técnicas de ahorro de energía, lo que puede afectar significativamente los resultados de la medición. Los altavoces introducen el concepto de escalado dinámico de frecuencia y voltaje, que es una técnica para reducir la potencia ajustando la frecuencia del reloj y el voltaje a los transistores. Destacan que es fundamental tener en cuenta los factores externos al tomar medidas para evitar resultados inexactos.
00:15:00 En esta sección, el orador analiza los desafíos de medir el rendimiento del software debido a la ley de potencia que utilizan los ingenieros eléctricos. La ley de potencia establece que la potencia es igual a CV al cuadrado de F, donde C es la capacitancia dinámica, V es la tensión de alimentación y F es la frecuencia del reloj. Para reducir la potencia y el calor, se puede reducir la frecuencia y el voltaje, lo que da como resultado una reducción cúbica de la potencia. Esto presenta un desafío para medir el rendimiento del software de manera confiable, y el orador sugiere desactivar los sistemas eliminando parte del ruido para tomar medidas precisas. También analizan las herramientas para medir el rendimiento del software, como el modelado de rendimiento.
00:20:00 En esta sección, el orador analiza la importancia de reducir la varianza en lo que respecta a la medición y el tiempo, especialmente en el contexto de la ingeniería de rendimiento. Al reducir la variabilidad, es posible compensar los errores de medición sistemáticos y aleatorios y requerir menos ensayos para comparar programas. El orador también señala varias fuentes de variabilidad en los sistemas informáticos, incluidos los trabajos en segundo plano, las interrupciones y la colocación de subprocesos, entre otros. Finalmente, enfatiza la importancia de centrarse primero en reducir la varianza antes de intentar realizar cambios en el sistema, ya que la medición durante una varianza alta puede conducir a resultados poco confiables.
00:25:00 En esta sección, el orador habla sobre el concepto de hiperprocesamiento en los procesadores y cómo puede conducir a mediciones inexactas en los sistemas en la nube. Hyper-threading ejecuta dos flujos de instrucciones a través de una unidad funcional, que parecen dos procesadores, pero en realidad solo proporciona un 20% de aceleración en lugar de dos procesadores separados. El orador también analiza otras técnicas, como el impulso turbo y la inactividad de un sistema, que pueden afectar significativamente los resultados de la medición. Al desactivar Hyper-Threading y Turbo Boost y silenciar a todos los demonios, el orador y su grupo pudieron lograr mediciones notablemente confiables que fueron menos del 1% más lentas que el tiempo de ejecución mínimo.
00:30:00 En esta sección, el orador habla sobre varios factores que pueden afectar el determinismo de un programa que se ejecuta en hardware moderno. Si bien hay ciertas medidas que se pueden tomar para hacer que el programa sea más determinista, es imposible eliminar por completo los factores no deterministas. La mayoría de los factores no deterministas que pueden surgir durante la ejecución del programa, como el almacenamiento en caché, las interrupciones, los subprocesos y la predicción de bifurcaciones, son procesos deterministas. Sin embargo, la aleatoriedad en el hardware está fuera del control del usuario y puede provocar un error de memoria. El orador sugiere que la alineación del código puede marcar una diferencia en el determinismo del programa, y cualquier cambio realizado en el código puede causar un cambio en la alineación de la memoria caché, lo que afecta el determinismo del programa.
00:35:00 En esta sección, el orador analiza cómo los pequeños cambios pueden tener un gran impacto en el rendimiento de un programa. Por ejemplo, insertar un byte puede hacer que todo lo que se encuentre después de él se vea afectado linealmente, y cambiar el orden en que aparecen los archivos punto o en la línea de comando del enlazador puede tener un efecto mayor que cambiar entre -OH- y -O3. Para abordar estos problemas, los compiladores están reconociendo el problema y haciendo más alineación. LLVM tiene interruptores que pueden alinear todas las funciones y bloques en una función, pero la alineación puede ralentizar el programa. Además, el nombre del programa puede afectar su velocidad ya que el nombre del ejecutable termina en una variable de entorno que termina en la pila de llamadas.
00:40:00 En esta sección, el orador analiza varias herramientas y métodos para medir el rendimiento del software, incluida la medición externa del programa con el comando de tiempo, la colocación de llamadas de tiempo en el programa mediante clock get time u otros métodos, la interrupción del programa con gdb para identificar qué rutina está tomando la mayor parte del tiempo, explotando el hardware y el soporte del sistema operativo, como los que se usan en el conjunto de herramientas perf, o simulando el programa para obtener una comprensión más profunda pero a una velocidad más lenta. El orador explica la diferencia entre el tiempo transcurrido, el tiempo del usuario y el tiempo del sistema cuando se usa el comando de tiempo, y cómo es posible que no sumen el tiempo total debido a la asignación del procesador.
00:45:00 En esta sección, el orador analiza los diferentes tipos de sincronización y medición, incluido el tiempo del reloj de pared, el tiempo del procesador en modo usuario y el tiempo en el núcleo. La llamada de temporización recomendada para su uso es clock get time con la opción monótona de reloj que garantiza que nunca se ejecutará hacia atrás. Si bien puede tardar una cantidad de tiempo no determinista en ejecutarse, es más confiable que otros temporizadores como RTIDTSC, que puede dar diferentes respuestas en diferentes núcleos y puede funcionar al revés. El hablante advierte contra el uso de obtener la hora del día.
00:50:00 En esta sección, el orador analiza varias formas de medir y cronometrar eventos en la programación, incluido el uso de clock_gettime y la medición con el comando time. Advierten que con el tiempo, las técnicas pueden cambiar y los ingenieros pueden necesitar adaptarse. El ponente también sugiere interrumpir el código en momentos aleatorios como una simple técnica de creación de perfiles y menciona que grandes empresas como Facebook utilizan este método. Además, el orador presenta la idea de los contadores de hardware y la biblioteca livepFM4, que permite el acceso a estos contadores por proceso. Hacen hincapié en que es posible que un ingeniero no siempre necesite herramientas quirúrgicamente precisas y que, a veces, una herramienta simple puede ser suficiente para el trabajo.
00:55:00 En esta sección, el orador analiza las diferentes formas de recopilar medidas, incluidos los contadores de hardware y los simuladores. Advierten que muchos contadores de hardware están mal documentados y que algunas herramientas comparten el tiempo de ancho de banda si se utilizan más de cuatro o cinco contadores. Los simuladores son elogiados por su repetibilidad, pero es posible que no modelen todo en el caché. El orador recomienda la triangulación y el uso de al menos dos medidas para garantizar la precisión. También enfatizan la importancia de tener un modelo de desempeño para guiar la interpretación de datos.
01:00:00 En esta sección, el orador explica el proceso de ingeniería de software de rendimiento, que implica tomar un programa, hacerle cambios y medir su rendimiento para producir un programa más rápido. Sin embargo, la medición confiable del desempeño es vital para hacer pequeños cambios que sumen y sacar conclusiones con precisión. Por lo tanto, el orador recomienda usar estadísticas para lograr una imagen precisa de lo que está sucediendo. También ofrece un acertijo que implica medir el rendimiento bruto de un programa determinista y concluye que usar el mínimo es la mejor manera de rechazar el ruido y determinar el rendimiento del hardware subyacente del programa.
01:05:00 En esta sección, se analizan varios tipos de estadísticas de resumen, incluida la media, que pueden proporcionar medidas útiles de rendimiento en diferentes contextos. Al evaluar los servidores web, la utilización de la CPU y el tiempo total de finalización de la tarea se pueden medir mediante la media aritmética, mientras que el tiempo del reloj de pared y el comportamiento del percentil pueden ser más relevantes para optimizar la satisfacción de las solicitudes. Sin embargo, al resumir proporciones, como comparar el rendimiento de los programas A y B, tomar la media aritmética no es un enfoque válido, aunque comúnmente se usa incorrectamente. Esto se debe a que la media de las razones no es lo mismo que la razón en sí, como se ilustra en el ejemplo que se muestra en el video.
01:10:00 En esta sección, el orador analiza los problemas relacionados con la comparación de proporciones y medias al medir el desempeño. Demuestran que tomar la media aritmética de las proporciones puede conducir a resultados sospechosos, y es mejor usar la media geométrica. Además, señalan que al comparar tasas, la media armónica suele ser útil. Se enfatiza la importancia de elegir la forma correcta de agregar datos cuando se comparan programas, y el orador sugiere tomar la estadística de orden inferior, como el mínimo o el 10 %, de varias ejecuciones para comparar el rendimiento con mayor precisión.
01:15:00 En esta sección, el orador analiza diferentes metodologías para medir y comparar el desempeño. Un enfoque es comparar el 10 % de las opciones más baratas y reducir el ruido para comparar los medios, aunque es posible que no proporcione pruebas concluyentes. Alternativamente, se puede realizar una comparación cara a cara entre A y B para ver cuál gana con más frecuencia. A través de esto, se puede probar la hipótesis nula y se puede calcular el valor p para determinar si la desviación es significativa. Este método se usa comúnmente en ciencias sociales y puede ser útil en entornos ruidosos. Finalmente, el disertante toca brevemente la idea de ajustar un modelo para derivar estadísticas y discute el uso de la aproximación de mínimos cuadrados.
01:20:00 En esta sección, el orador analiza el problema del sobreajuste en el modelado y cómo agregar más funciones básicas puede mejorar el ajuste de los datos, pero también conducir a un sobreajuste. La solución es eliminar una función base y verificar si afecta la calidad del modelo. El orador también menciona a Lord Kelvin, conocido como el Gurú de la medición, quien afirmó que medir es saber y si uno no puede medir, no puede mejorar. El video concluye con el orador deseando suerte en un cuestionario el martes.

Estudiamos ONNX para aplicarlo OpenCL en el trading Comercio Cuantitativo

MetaQuotes 2023.04.26 14:28 #292

Lección 11. Asignación de almacenamiento

Lección 11. Asignación de almacenamiento

El disertante analiza la asignación de almacenamiento en este video, cubriendo tanto la asignación como la liberación de memoria. Se abordan diferentes tipos de almacenamiento, incluidos la pila y el montón, así como esquemas de asignación de tamaño fijo y variable. También se analiza la fragmentación externa provocada por la distribución de bloques de memoria, con soluciones como listas libres o mapas de bits por página de disco. También se introduce el concepto de recolección de basura, incluido el conteo de referencias y las limitaciones de este algoritmo. También se explican los procedimientos de recolección de basura "marcar y barrer" y "detener y copiar", con un enfoque en cómo este último aborda la fragmentación y el posible problema de corrección creado por las actualizaciones de puntero. El video concluye con notas sobre la complejidad temporal y espacial del algoritmo de parada y copia y su eliminación de la fragmentación externa.

Este video cubre varios temas relacionados con la asignación de almacenamiento dinámico, incluido el sistema Buddy, los procedimientos de marcado y barrido, las optimizaciones, la recolección de basura generacional y en tiempo real, la asignación de almacenamiento de subprocesos múltiples y la recolección de basura paralela. El disertante explica que la recolección de basura generacional se basa en la idea de que los objetos más jóvenes se escanean con mayor frecuencia, mientras que la recolección de basura en tiempo real se ejecuta en segundo plano durante la ejecución del programa, pero puede generar problemas de corrección si el objeto y el gráfico del puntero siguen cambiando. Finalmente, la lección resume los diferentes tipos de asignación de almacenamiento, incluidos los de pila y pila, y los diferentes métodos de recolección de elementos no utilizados, como el recuento de referencias, marcar y barrer y detener y copiar. El disertante menciona que los estudiantes podrán probar algunos de estos métodos en su próxima tarea.

00:00:00 En esta sección, el disertante analiza la asignación de almacenamiento, que incluye tanto la asignación como la liberación de memoria. La forma más simple de almacenamiento es una pila, donde la memoria se asigna incrementando el puntero de la pila y se libera al disminuir el puntero de la pila. Sin embargo, la pila tiene una aplicabilidad limitada porque solo puede liberar lo último que se asignó y no puede liberar nada en el medio de la región utilizada. El disertante también señala que, por razones de eficiencia, los compiladores generalmente no verifican el desbordamiento de pila.
00:05:00 En esta sección, el disertante habla de dos tipos de almacenamiento: la pila y el montón. La pila es un almacenamiento de tamaño fijo que es eficiente pero no se puede usar para todo, mientras que el montón es más general pero difícil de organizar y usar de manera eficiente. Para la asignación de almacenamiento dinámico, se pueden usar las funciones malloc y free C, pero dado que C y C++ no proporcionan un recolector de basura, los programadores tienen que administrar la memoria ellos mismos, lo que puede provocar pérdidas de memoria, punteros colgantes y doble liberación. El disertante sugiere usar verificadores de memoria como el desinfectante de direcciones y Valgrind para reducir la cantidad de errores de memoria en el programa.
00:10:00 En esta sección, el orador analiza diferentes formas de asignar almacenamiento, comenzando con la asignación de tamaño fijo, en la que cada pieza de almacenamiento tiene el mismo tamaño y algunos bloques se usan mientras que otros no se usan. Los bloques no utilizados se guardan en una lista llamada lista libre, y cada bloque de la lista libre tiene un puntero al siguiente bloque de la lista. Para asignar un objeto de la lista libre, el programa configura el puntero para que esté libre y luego establece el puntero libre para que apunte al siguiente objeto de la lista libre, devolviendo el puntero al primer objeto de la lista libre. Para desasignar, uno simplemente establece el siguiente puntero del objeto para liberar y libera igual al objeto que se liberará. Con la lista libre, la asignación y la liberación toman un tiempo constante y también se obtiene una buena localidad temporal.
00:15:00 En esta sección, se introduce el concepto de fragmentación externa, que ocurre cuando los bloques de memoria utilizada se distribuyen por el espacio de toda la memoria. Esto puede llevar a una tabla de páginas más grande, lo que puede causar problemas en el disco y hacer que sea menos eficiente buscar traducciones. Para mitigar la fragmentación externa, se puede usar una lista libre o mapa de bits por página de disco, y se puede realizar la asignación desde la página más completa, liberar bloques de historias y paginar páginas vacías. La asignación de almacenamiento dinámico de tamaño fijo también puede ser útil para reducir la fragmentación externa. Por último, la asignación de almacenamiento dinámico de tamaño variable se puede usar con listas bin free, que aprovechan la eficiencia de las listas free para diferentes tamaños de memoria asignada.
00:20:00 En esta sección, se presenta un esquema para almacenar bloques de memoria de diferentes tamaños en un sistema de asignación de memoria. El esquema consiste en dividir los bloques en contenedores en función de su tamaño, y cada contenedor contiene bloques de un tamaño específico que son potencias de dos. Al asignar memoria, se selecciona el contenedor adecuado en función del tamaño solicitado y, si está vacío, se divide un contenedor no vacío más grande en partes más pequeñas para obtener el tamaño deseado. Sin embargo, este esquema puede resultar en la fragmentación interna de la memoria, lo que es un desperdicio, por lo que la cantidad de contenedores utilizados es limitada y los bloques pequeños se agrupan en páginas para reducir la sobrecarga. El sistema operativo se puede utilizar para proporcionar más memoria si es necesario, y hay llamadas al sistema disponibles para este fin.
00:25:00 En esta sección, el video analiza cómo funciona la asignación de memoria y señala que las implementaciones estándar de 'malloc' se basan en comandos como 'romper' para obtener memoria del sistema operativo. El sistema operativo brinda una gran cantidad de memoria y depende del sistema de asignación de almacenamiento dividirla en bloques más pequeños. Esta sección también cubre variantes del asignador de memoria, incluidos diferentes esquemas para almacenar tamaños de bloque y cómo se distribuye el espacio de direcciones de memoria virtual en un programa. Observa que la pila y el montón crecen uno hacia el otro pero nunca se cruzan. Finalmente, se menciona que pre-computar grandes tablas de constantes en un programa puede aumentar el tiempo de carga ya que requiere lectura del segmento de datos.
00:30:00 En esta sección, se analiza el problema de la fragmentación con la memoria virtual, que puede generar fragmentación externa, rendimiento degradado de la tabla de páginas, hiperactividad del disco y bajas tasas de aciertos de TLB si la memoria está dispersa. El objetivo de la asignación de almacenamiento es usar la menor cantidad de memoria virtual posible y mantener compactas las porciones de memoria usadas. Se analiza el esquema de asignación de la lista libre de contenedores, con un teorema que establece que la cantidad de memoria virtual consumida por el almacenamiento dinámico tiene un límite superior de M log M. La fusión de bloques más pequeños en bloques más grandes puede mejorar el esquema de la lista libre de contenedores, pero la sobrecarga de este método puede ser alto en comparación con el algoritmo de lista libre de contenedores estándar, que es solo un factor constante peor que el asignador óptimo, según un artículo de Charles Leiserson.
00:35:00 En esta sección, el orador explica el concepto de asignación de almacenamiento y cómo puede reducir la fragmentación cuando se trata de almacenamiento en montón. También analiza la idea de la recolección de basura, que libera al programador de tener que liberar objetos manualmente. El orador explica los tres tipos de objetos de memoria: raíces, objetos vivos y objetos muertos, y cómo la recolección de basura puede reciclar estos últimos. Por último, describe el conteo de referencias, una forma simple de recolección de basura que cuenta la cantidad de punteros que hacen referencia a un objeto para determinar si se puede liberar.
00:40:00 En esta sección, el orador introduce el concepto de conteo de referencia como un esquema de recolección de basura y explica cómo funciona el algoritmo de conteo de referencia. Sin embargo, se señala una limitación del algoritmo, donde no se pueden recolectar ciclos en el gráfico de referencia. Luego, el orador analiza el uso de punteros fuertes y débiles en algunos lenguajes de programación para evitar esta limitación. Finalmente, el orador presenta una vista previa de otros dos esquemas de recolección de basura, "marcar y barrer" y "detener y copiar", que evitan la limitación del conteo de referencias cuando se trata de ciclos en el gráfico de referencia.
00:45:00 En esta sección, el disertante analiza el uso de un algoritmo de búsqueda primero en amplitud para encontrar todos los objetos vivos en la memoria. Se utiliza una matriz con dos punteros para representar una cola FIFO para la búsqueda, y el algoritmo marca cada objeto vivo al que se puede acceder desde las raíces. Una vez completada la búsqueda, los objetos no marcados están disponibles para la recolección de elementos no utilizados. El procedimiento de marcar y barrer consta de dos etapas: la etapa marcada, que involucra el algoritmo de búsqueda primero en amplitud, y la etapa de barrido, que involucra escanear la memoria para liberar objetos no marcados. Sin embargo, existen limitaciones en este esquema, como la necesidad de escanear toda la memoria y la sobrecarga asociada con la búsqueda de objetos sin referencia.
00:50:00 En esta sección, el video presenta el procedimiento de recolección de basura "detener y copiar" que se ocupa de la fragmentación. Este procedimiento es similar al algoritmo de marcar y barrer, pero adopta un enfoque diferente para garantizar que los objetos vivos sean contiguos en la memoria. El procedimiento utiliza dos espacios de memoria separados, el espacio from y el espacio to, y asigna y libera objetos del espacio from hasta que se llena. Luego, se ejecuta el algoritmo de recolección de elementos no utilizados y el espacio dos se utiliza como cola para la búsqueda en amplitud para identificar objetos vivos, que se colocarán de forma contigua en la memoria en los dos espacios. Sin embargo, el uso de este algoritmo puede dar lugar a un posible problema de corrección en el que los punteros que apuntan a objetos en el espacio de origen ya no sean correctos. Para abordar esto, el procedimiento almacena un puntero de reenvío en el objeto correspondiente en el espacio desde y actualiza todos los punteros siguiendo estos punteros de reenvío al eliminar un objeto de la cola en la búsqueda en amplitud.
00:55:00 En esta sección, el disertante analiza el algoritmo de recolección de basura de parada y copia, su complejidad de tiempo y cómo trata la fragmentación externa. El algoritmo de parada y copia implica copiar objetos del espacio de origen al espacio de destino y luego actualizar los punteros de estos objetos en el espacio de destino. Este algoritmo es lineal en el tiempo y el espacio, lo que lo convierte en una forma más eficiente y efectiva de recolección de basura. Cuando el espacio from se llena, el usuario puede solicitar un nuevo espacio de almacenamiento dinámico y duplicar el tamaño del espacio from. El espacio de memoria virtual requerido por este esquema es óptimo en tiempos constantes, y este algoritmo elimina la fragmentación externa.
01:00:00 En esta sección, el orador analiza más temas relacionados con la asignación de almacenamiento dinámico, como el sistema Buddy para realizar fusiones, variantes del procedimiento de marcado y barrido, optimizaciones para mejorar el rendimiento, recolección de basura generacional, recolección de basura en tiempo real , asignación de almacenamiento de subprocesos múltiples y recolección de basura paralela. La recolección de elementos no utilizados generacionales se basa en la idea de que muchos objetos son de corta duración, por lo tanto, solo los objetos más jóvenes se escanean la mayor parte del tiempo. La recolección de basura en tiempo real funciona en segundo plano mientras se ejecuta el programa, pero podría generar problemas de corrección si el gráfico de objetos y punteros está cambiando. La asignación de almacenamiento de subprocesos múltiples y la recolección de elementos no utilizados en paralelo tienen varios subprocesos en ejecución, lo que hace que los algoritmos sean más complicados para lidiar con las carreras y otros problemas de corrección. El orador también resume los diferentes tipos de asignación de almacenamiento, incluida la pila y el montón, y las diferentes formas de realizar la recolección de elementos no utilizados, como el recuento de referencias, marcar y barrer y detener y copiar.
01:05:00 En esta sección, el instructor mencionó que profundizarán más en los esquemas de asignación de almacenamiento y que los estudiantes tendrán la oportunidad de probar algunos de ellos en su próxima tarea. Luego, el instructor terminó la conferencia y abrió el piso para cualquier otra pregunta.

OpenCL en el trading Tutoriales de programación Python para el trading

MetaQuotes 2023.04.26 14:29 #293

Lección 12. Asignación de almacenamiento en paralelo

Lección 12. Asignación de almacenamiento en paralelo

El video analiza varias estrategias de asignación de memoria y sus compensaciones. Se explica el uso de malloc y asignación alineada, así como la importancia de la desasignación de memoria adecuada con libre. También se cubre el uso de Mmap para la asignación de memoria virtual, junto con los problemas de fragmentación externa y rendimiento lento. Se explora el concepto de pilas en la programación C y C++, con énfasis en un enfoque de pila de cactus basado en montón para asignar marcos de pila, lo que puede conducir a mejores pruebas limitadas al espacio y límites superiores. También se analiza el uso de un conjunto de pilas lineales, junto con la importancia de optimizar los bloques pequeños para minimizar la fragmentación. El video concluye con una discusión sobre los enfoques de montones globales y locales y sus problemas potenciales, junto con enfoques como las listas de contenedores libres y el reequilibrio periódico de la memoria para abordar estos problemas.

El video también analiza soluciones para la asignación de almacenamiento en paralelo y presenta el asignador Hoard como una solución. El asignador de tesoros utiliza una combinación de montones locales y globales y grandes superbloques que se pueden mover entre montones para reducir el uso compartido falso, mejorar la escalabilidad y reducir la fragmentación externa. El almacenamiento máximo asignado en el almacenamiento dinámico global es, como máximo, el almacenamiento máximo asignado en los almacenamientos dinámicos locales, y el espacio está limitado por el espacio ocupado por el usuario más el almacenamiento asignado pero no utilizado en los almacenamientos dinámicos locales. El video también analiza brevemente otros asignadores como Je malloc y Super malloc, con resultados de referencia que indican que Super malloc se desempeñó mejor que Je malloc y Hoard. La discusión concluye con una referencia a las diapositivas en línea para obtener detalles sobre la recolección de elementos no utilizados.

00:00:00 En esta sección, el disertante revisa las primitivas de asignación de memoria, incluyendo malloc y asignación alineada. La asignación alineada se puede usar para alinear la memoria con las líneas de caché, de modo que acceder a un objeto dentro de una línea de caché solo requiera un acceso a la memoria caché, lo que reduce la cantidad de errores de memoria caché. El disertante también analiza la importancia de desasignar correctamente la memoria con la función libre y evitar fugas de memoria y doble liberación. Finalmente, el disertante presenta la llamada al sistema Mmap, que se puede usar para asignar memoria virtual sin un archivo de respaldo.
00:05:00 En esta sección, el orador explica el proceso de asignación de memoria mediante el mapa M, que es una llamada al sistema que encuentra una región no utilizada contigua en el espacio de direcciones de la aplicación lo suficientemente grande como para contener el tamaño de memoria solicitado y actualiza la tabla de páginas para contener una entrada para las páginas asignadas. A diferencia de malloc, que es una llamada de biblioteca y parte del código de administración de almacenamiento dinámico de la biblioteca C, el mapa M no asigna memoria física de inmediato para la memoria solicitada, sino que llena la tabla de páginas con entradas que apuntan a una página cero especial que se modifica y traducido a la memoria física solo cuando el usuario escribe por primera vez en él. Además, M map es responsable de obtener memoria del sistema operativo, mientras que malloc es responsable de reutilizar la memoria previamente asignada para reducir la fragmentación y mejorar la localidad temporal.
00:10:00 En esta sección, el video analiza las diferencias entre usar MMAP y MALLOC para la asignación de almacenamiento, enfatizando que MMAP es relativamente pesado y asigna páginas enteras incluso para asignaciones pequeñas, lo que genera fragmentación externa y un rendimiento lento. El video también repasa el proceso de traducción de direcciones, donde la dirección virtual se usa para acceder a la memoria y el hardware busca la dirección física adecuada en la tabla de páginas. El video explica cómo funcionan los TLB al almacenar en caché las búsquedas recientes en la tabla de páginas y señala que los programas con localidad espacial o temporal tendrán muchos accesos recientes almacenados en el TLB, lo que conduce a un rendimiento más rápido.
00:15:00 En esta sección, el orador analiza cómo funciona la traducción de direcciones en las máquinas modernas y también profundiza en el concepto de pilas en la programación C y C++. Las pilas se utilizan para realizar un seguimiento de las llamadas a funciones y variables locales y seguir un orden lineal. El orador enfatiza una regla de los punteros en las pilas lineales tradicionales: un padre puede pasar punteros a sus variables de pila a sus hijos, pero no al revés, para evitar sobrescribir variables. El hablante también sugiere opciones, como asignar memoria en el montón o en la pila principal, para pasar memoria de una función secundaria a la principal.
00:20:00 la asignación de almacenamiento dinámico paralelo es correcta, el problema potencial con el uso de una pila de cactus basada en almacenamiento dinámico es la fragmentación de la memoria, donde es posible que no quede suficiente memoria contigua para asignaciones futuras, lo que genera espacio desperdiciado y, potencialmente, quedarse sin memoria o bloquear el programa. Si bien los primeros sistemas de programación paralela usaban esta estrategia, es importante optimizar el código para minimizar el impacto en el rendimiento y considerar las consecuencias de la fragmentación de la memoria.
00:25:00 En esta sección, el video analiza el uso de un enfoque de pila de cactus basado en montón para asignar marcos de pila sin poner un límite superior en la profundidad máxima. Sin embargo, la interoperabilidad es un problema cuando se intenta utilizar código de pila lineal tradicional con esta pila de cactus basada en montón. Esto se puede arreglar usando un enfoque llamado mapeo de memoria local de subprocesos, pero este enfoque requiere cambios en el sistema operativo. A pesar de esto, el enfoque de pila de cactus basado en heap sigue siendo bueno en la práctica y se puede usar para probar un límite de espacio de un programa Silk que lo usa. Este límite de espacio muestra que el espacio de pila de una ejecución de trabajador P que usa una pila de cactus basada en montón tiene un límite superior de P multiplicado por s1, donde s1 es el espacio de pila requerido por una ejecución en serie del programa Silk. Esta es una buena característica del enfoque de pila de cactus basado en montón.
00:30:00 En esta sección, se analiza el código de multiplicación de matrices de divide y vencerás para comprender cómo se puede aplicar al Teorema de compensación del espacio-tiempo. El código realiza ocho llamadas recursivas, cada una de tamaño N/2, y antes de cada llamada, realiza un malloc para obtener un espacio temporal de orden de tamaño N al cuadrado, que luego se libera justo antes de que la función regrese. Dado que las asignaciones siguen una disciplina de pila, incluso cuando se asignan fuera del montón, el límite de espacio de la diapositiva anterior se puede usar para delimitar por arriba el espacio de trabajador P. El trabajo es N al cubo y el lapso es orden log N al cuadrado. La recurrencia para el espacio es s de N/2 + theta de N al cuadrado, que se resuelve en N al cuadrado. Por lo tanto, la propiedad de las hojas ocupadas y el teorema para el espacio acotado muestran que en P procesadores, el espacio está acotado por P multiplicado por N al cuadrado.
00:35:00 En esta sección, el orador explica a la audiencia cómo probar un límite espacial más fuerte para el algoritmo discutido en la sección anterior. Al analizar la estructura del algoritmo y enfocarse en ramificar tanto como sea posible cerca de la parte superior del árbol recursivo, el orador puede demostrar un límite espacial de P a un tercio por N al cuadrado, que es mejor que los límites superiores anteriores. . El orador señala que analizar la estructura de un algoritmo puede conducir a pruebas limitadas al espacio más sólidas que simplemente aplicar un teorema general. La sección concluye discutiendo cómo las funciones paralelas no interoperan con los binarios seriales heredados y de terceros.
00:40:00 En esta sección, el orador analiza el uso de un grupo de pilas lineales en la asignación de almacenamiento, que se puede usar para mantener un grupo de pilas para el código heredado. La cantidad de pilas en el grupo debe ser constante por la cantidad de procesadores para que se conserve el límite de espacio. Sin embargo, esta estrategia puede afectar el límite de tiempo del algoritmo de robo de trabajo porque es posible que el trabajador no pueda robar si no hay más pilas disponibles. Luego, el orador habla sobre las propiedades básicas de los asignadores de almacenamiento dinámico, incluida la velocidad del asignador y la huella del usuario, y enfatiza la importancia de optimizar para bloques pequeños debido al potencial de fragmentación y sobrecarga en la asignación. La fragmentación se define como la huella del asignador dividida por la huella del usuario.
00:45:00 En esta sección del video, el orador analiza cómo mantener la huella asignada lo más cerca posible de la huella del usuario para minimizar la proporción de los dos. Una solución es usar algo llamado aviso M, que le dice al sistema operativo que cierta página de memoria ya no es necesaria pero que debe mantenerse en la memoria virtual. El orador también menciona el teorema de la lección anterior de que la fragmentación de las listas bin free es orden log base dos de U, donde U es la cantidad total de memoria asignada, y explica las diferencias entre la sobrecarga de espacio, la fragmentación interna y la fragmentación externa. Finalmente, el orador señala que los procesadores modernos de 64 bits brindan entre 2 y 48 bytes de espacio de direcciones virtuales, que es suficiente para la mayoría de los programas, pero aún más que la memoria física en una máquina típica.
00:50:00 En esta sección, el video explora una estrategia de asignación de montones paralelos usando un montón global con protección mutex, que es cómo funciona el asignador predeterminado de C++. La explosión de esta estrategia es una, ya que no requiere espacio adicional en comparación con un asignador en serie. Sin embargo, el problema potencial con este enfoque es el impacto en el rendimiento, ya que adquirir el bloqueo para cada asignación y desasignación es lento y empeora con el aumento de procesadores. La contención de bloqueo es la razón principal de la escalabilidad deficiente, que es más problemática para las asignaciones pequeñas debido a las tasas de solicitud más altas, y las asignaciones de bloques grandes requieren más trabajo.
00:55:00 En esta sección, el video analiza el problema potencial con el uso de un enfoque de almacenamiento dinámico local, que es que puede conducir a la deriva de la memoria y a la expansión ilimitada. Esencialmente, si asigna toda su memoria en un subproceso pero la libera en otro, puede haber memoria no utilizada en el sistema que el asignador no es lo suficientemente inteligente como para reutilizarla. Como resultado, su programa que se ejecuta en múltiples procesadores podría eventualmente quedarse sin memoria, pero no sucederá si solo se ejecuta en un solo núcleo. El video sugiere utilizar un enfoque de lista libre de contenedores para abordar este problema, lo que implica establecer punteros en la estructura de datos de la lista libre de contenedores para que el bloque que se libera pueda aparecer en una de las listas vinculadas. Otra estrategia es reequilibrar periódicamente la memoria, pero también se analiza un enfoque más simple.
01:00:00 En esta sección, el video explica cómo cambiar el asignador de memoria para lograr el comportamiento deseado de que cada subproceso acceda a su propio montón sin necesidad de un montón global. Un enfoque es etiquetar cada objeto con un propietario y devolverlo al montón del propietario cuando se libera. De esta forma, los objetos locales se asignan y liberan rápidamente, mientras que los objetos remotos requieren cierta sincronización, pero no tanta como con un almacenamiento dinámico global. La cantidad máxima de memoria que se puede asignar está limitada por X, la cantidad utilizada por el programa secuencial, y la proporción de aumento está limitada por P, el número de montones. Este enfoque también tiene resistencia al uso compartido falso, que ocurre cuando varios procesadores acceden a diferentes ubicaciones de memoria pero en la misma línea de caché.
01:05:00 En esta sección, el orador explica cómo la asignación de montones en paralelo puede generar un uso compartido falso y presenta el asignador de reservas como una solución. El asignador de tesoros utiliza una combinación de montones locales y globales, organizando la memoria en grandes superbloques que se pueden mover entre montones. Este enfoque es rápido, escalable y resistente al uso compartido falso. Cuando se realiza una asignación, el asignador busca un objeto libre en el montón local y lo obtiene, si existe. Si no, va al montón global para obtener más memoria.
01:10:00 En esta sección, el orador explica cómo el asignador Horde reduce la fragmentación externa mediante la asignación de un objeto libre del superbloque no completo más completo para densificar el movimiento de los superbloques. Si el objeto no se encuentra en el montón local, comprueba el montón global y, si el montón global está vacío, llama a un nuevo superbloque desde el sistema operativo. El asignador Horde mantiene un invariante en el que el montón se utiliza como máximo a la mitad, y si detecta que el montón está infrautilizado, mueve un superbloque medio vacío al montón global. Luego, el orador presenta un lema que establece que el almacenamiento máximo asignado en el almacenamiento dinámico global es, como máximo, el almacenamiento máximo asignado en los almacenamientos dinámicos locales. Finalmente, el orador prueba el teorema de que la huella del asignador de Horde está limitada por el orden u más SP, donde u es la huella del usuario para el programa y SP es el almacenamiento asignado pero no utilizado en los montones locales. Entonces se calcula que la explosión es uno más el orden SP dividido por u.
01:15:00 En esta sección, el orador analiza diferentes asignadores, incluidos Je malloc y Super malloc. Je malloc tiene bloqueos globales separados para diferentes tamaños de asignación y libera páginas vacías utilizando consejos em, lo que lo hace resistente a diferentes seguimientos de asignación. Por otro lado, Super malloc tiene muy pocas líneas de código y se desarrolla muy rápido. El orador comparte resultados de referencia en los que Super malloc se desempeñó mejor que J malloc, que se desempeñó mejor que Horde, mientras que el asignador predeterminado tuvo un desempeño deficiente. La discusión también se extiende a la recolección de basura, sin embargo, el orador difiere los detalles de esto para las diapositivas en línea.

OpenCL en el trading Tutoriales de programación Estudiamos ONNX para aplicarlo

MetaQuotes 2023.04.26 14:30 #294

Lección 13. El sistema de tiempo de ejecución de Cilk

Lección 13. El sistema de tiempo de ejecución de Cilk

El sistema de tiempo de ejecución de Cilk es responsable de programar y equilibrar la carga de los cálculos en procesadores paralelos, utilizando un programador de robo de trabajo aleatorio para asignar los cálculos a los procesadores en tiempo de ejecución. El sistema está diseñado para optimizar la ejecución en serie del programa, incluso a expensas de un costo adicional a los robos. El trabajador mantiene una estructura de datos de cubierta separada que contiene punteros a los marcos de pila y utiliza punteros de cabeza y cola. Las tramas que están disponibles para ser robadas tienen una estructura local adicional que contiene la información necesaria para que ocurra el robo mientras la cubierta es externa a la pila de llamadas. La sección explica cómo el sistema permite que los procesadores comiencen a ejecutarse desde la mitad de una función en ejecución y cómo la sincronización entre procesadores se complica cuando se llega a una declaración de sincronización que no puede ejecutarse más allá del punto porque los procesadores específicos todavía están esperando que finalicen los cálculos. Además, el orador aborda el rendimiento del sistema, las consideraciones de diseño y las estructuras de datos, y cómo el sistema optimiza la ejecución utilizando el protocolo THC, que involucra dos conjuntos de protocolos, uno para el trabajador que ejecuta el trabajo y otro para el ladrón.

El sistema de tiempo de ejecución de Cilk utiliza un protocolo de salto fijo y de salto largo para manejar el robo de cálculos de las cubiertas de ejecución de los procesos víctimas. La abstracción Cactus Stack permite que el proceso ladrón tenga su propia pila de llamadas para evitar la corrupción de las pilas de la víctima. El protocolo de sincronización del sistema utiliza un árbol de cálculos y una pila de cactus para garantizar que la sincronización solo se produzca entre cálculos anidados dentro de una función. Full Frame Tree mantiene relaciones padre-hijo entre cálculos con subcálculos pendientes para simplificar el proceso de sincronización. Además, el sistema de tiempo de ejecución optimiza el caso común en el que la función actual no tiene cálculos secundarios pendientes y todos los trabajadores están ocupados. Otras funciones admitidas incluyen excepciones de C++, hiperobjetos reductores y genealogías.

00:00:00 En esta sección, Tibi explica el sistema de tiempo de ejecución Cilk, que es responsable de programar y equilibrar la carga de los cálculos en procesadores paralelos. El sistema de tiempo de ejecución utiliza un programador de robo de trabajo aleatorio para asignar los cálculos a los procesadores en tiempo de ejecución, lo que garantiza una ejecución eficiente. Tibi señala que el sistema de tiempo de ejecución de Cilk es una pieza de software compleja, pero su magia subyacente se implementa a través de la colaboración del compilador de Cilk y la biblioteca de tiempo de ejecución. Además, muestra el pseudocódigo de un programa Cilk simple después de la compilación, lo que destaca el complejo proceso que subyace al sistema de tiempo de ejecución de Cilk.
00:05:00 En esta sección, el orador explica la funcionalidad necesaria para el sistema de tiempo de ejecución de Cilk, así como las consideraciones de rendimiento. Utiliza un ejemplo de rutina de Fibonacci paralelizado para ilustrar cómo el programa Cilk ejecuta un dag de cálculo, que se desarrolla dinámicamente a medida que el programa se ejecuta en un procesador. Sin embargo, cuando se encuentra la declaración de engendro de seda, se crea un nuevo marco para fib de 3 y otra hebra está disponible para ejecutarse en paralelo. Luego, el procesador comienza a ejecutar fib de 3 como si fuera una llamada de función ordinaria. El proceso se repite cuando el puntero de instrucción regresa al comienzo de la rutina fib.
00:10:00 En esta sección, vemos cómo varios procesadores ejecutan una rutina fib en paralelo con la ayuda del sistema de tiempo de ejecución Cilk. Cada procesador salta a la mitad de una función en ejecución y comienza a ejecutarla, a pesar de tener registros independientes, lo que plantea la pregunta de cómo el sistema Silk permite que los procesadores comiencen a ejecutarse desde la mitad de una función en ejecución. Además, la sincronización entre procesadores se complica cuando se llega a una declaración de sincronización que no puede ejecutarse más allá del punto porque los procesadores específicos todavía están esperando que finalicen los cálculos, lo que requiere una sincronización de grano fino dentro del patrón anidado.
00:15:00 En esta sección, el orador analiza las consideraciones de implementación para el sistema de tiempo de ejecución de Cilk. Mencionan tres consideraciones principales: un solo trabajador que pueda ejecutar el programa, la capacidad de saltar en medio de la ejecución de funciones y continuar donde otros procesadores lo dejaron, y sincronización. Además, Silk tiene una noción de pila de cactus, que debe implementarse correctamente para que todas las vistas de la pila estén disponibles y sean coherentes. Finalmente, el sistema debe permitir el robo de trabajo al permitir que los procesadores se roben cuadros entre sí.
00:20:00 En esta sección, el orador habla sobre la funcionalidad requerida para Cilk Runtime System, que incluye la ejecución en serie, los ladrones saltan a la mitad de la ejecución de las funciones, sincroniza para sincronizar de manera detallada anidada, una pila de cactus para todos los trabajadores para ver, y lidiar con combinaciones de marcos de generación y marcos llamados que pueden estar disponibles cuando roban computación. Luego, la sección pasa a abordar el rendimiento del sistema, donde necesitamos un amplio paralelismo, T1 sobre T infinito debe ser mucho mayor que P, y queremos una aceleración lineal al aumentar la cantidad de procesadores para ejecutar el programa. La sección también cubre el tiempo de ejecución esperado de TCP en procesadores P, que es proporcional al trabajo del cálculo dividido por el número de procesadores más algo del orden del intervalo del cálculo.
00:25:00 En esta sección, aprendemos sobre Cilk Runtime System y su objetivo de mantener una alta eficiencia de trabajo en programas con suficiente paralelismo. El Silk Runtime System cumple con el principio de trabajo primero al optimizar la ejecución en serie del programa incluso a expensas de algún costo adicional para los aceros. La biblioteca del sistema de tiempo de ejecución maneja problemas con la ejecución paralela y maneja rutas de ejecución más lentas cuando se producen aceros. El trabajador mantiene una estructura de datos de cubierta separada que contiene punteros a los marcos de pila y utiliza punteros de cabeza y cola. Las tramas que están disponibles para ser robadas tienen una estructura local adicional que contiene la información necesaria para que ocurra el robo mientras la cubierta es externa a la pila de llamadas.
00:30:00 En esta sección, aprendemos sobre el diseño del sistema Cilk Runtime y sus estructuras de datos básicas. El sistema genera una función auxiliar de generación para cada cálculo, que mantiene una estructura de trabajador y una estructura de marco de pila Silk para cada instanciación de una función de generación y un auxiliar de generación, respectivamente. El marco de pila de Silk RTS contiene campos como un búfer y un número entero de indicadores para resumir el estado del marco de pila de Silk y un puntero a un marco de pila de Silk principal en la pila de llamadas. La estructura de trabajo mantiene una plataforma y un puntero al marco de pila actual de Silk RTS. Estas estructuras de datos son los elementos esenciales del sistema de tiempo de ejecución de Cilk que elabora el sistema de tiempo de ejecución Intel so+.
00:35:00 En esta sección, el video explora el código para la función de generación "foo" y la función auxiliar de generación. El código para "foo" incluye una llamada para inicializar el marco de la pila, configurado para una generación con la rutina de salto establecida, una llamada a la función auxiliar de generación "barra de generación", un bloque de código condicional para un sumidero en Silk RTS, y llama a los marcos pop y leaf para la limpieza. El código para el asistente de generación incluye una llamada para inicializar el marco de la pila y una llamada para separar el Silk RTS con funciones de limpieza adicionales para la estructura de la pila. La rutina de configuración se describe como una función que permite a los ladrones robar la continuación de la función, tomando como argumento un búfer para almacenar la información necesaria para reanudar la ubicación de la función.
00:40:00 En esta sección, el orador explica cómo restringir el conjunto de registros y guardarlos en un conjunto predeterminado para una llamada de función. La responsabilidad de guardar los registros recae en la función, pero el puntero de instrucción y los punteros de pila se guardan en el búfer. La sección continúa discutiendo una función auxiliar de generación y cómo actualiza las estructuras de trabajo y los marcos de pila actuales. Finalmente, la sección explica cómo la rutina rápida de ingresar marco establece un puntero principal en la pila de llamadas y actualiza el marco de pila actual del trabajador para que apunte en la parte inferior.
00:45:00 En esta sección, la transcripción del video de YouTube titulado "El sistema de tiempo de ejecución de Cilk" explica cómo la función de separación de Silk RTS permite el robo de la computación, donde una vez que Silk Art finaliza la ejecución, un ladrón podría venir y robar la continuación de la semilla de seda. El marco emergente es responsable de limpiar la estructura del marco de pila y actualizar el marco de pila actual para que apunte al padre. Esta llamada de función puede regresar o no, y cuál de estos dos casos es más importante para que el sistema de tiempo de ejecución optimice es el caso de éxito, según el principio de los dos que funcionan primero.
00:50:00 En esta sección, el orador analiza la optimización del sistema de tiempo de ejecución de Cilk en la ejecución de los trabajadores en el caso uno, donde se supone que los trabajadores realizan una ejecución en serie regular. También explican cómo funciona el robo de trabajadores, con el ladrón apuntando a la parte superior del mazo de la víctima, sacando el elemento de la cola y actualizando la cabeza del mazo y el puntero del marco de pila actual. El resultado de la función generada se devuelve al marco de la pila principal en el código SIL original.
00:55:00 En esta sección, el orador explica el enfoque del Sistema de tiempo de ejecución de Cilk en el manejo de accesos simultáneos que involucran múltiples procesadores usando un protocolo llamado protocolo THC. El protocolo involucra dos conjuntos de protocolos, uno para el trabajador que ejecuta el trabajo y otro para el ladrón. El protocolo del trabajador se optimiza al intentar sacar algo del fondo de la plataforma, y solo si falla adquiere un candado en la plataforma, mientras que el ladrón siempre agarra un candado antes de realizar cualquier operación en la plataforma. Luego, el ladrón reanuda mágicamente una continuación robada llamando a la función de salto largo, pasando el búfer de marco de pila recuperado de la función de salto establecido y configurando su estado de registro para que sea el de la continuación robada.
01:00:00 En esta sección, el orador analiza la interacción entre las llamadas de salto fijo y salto de longitud dentro del sistema de tiempo de ejecución de Cilk. Explican cómo, cuando se llama a una rutina de salto largo, regresa efectivamente del salto establecido por segunda vez, esta vez con un valor diferente especificado en el segundo argumento. Usando el búfer apropiado y el segundo argumento, el ladrón puede ejecutar un salto largo para saltarse un determinado cálculo en el código de la víctima. El orador señala que es posible calcular estáticamente la distancia necesaria para saltar una llamada y usar un enfoque diferente, pero el protocolo de salto fijo y salto largo sirve como un método más flexible para el sistema de tiempo de ejecución de Cilk. En general, el orador destaca las diversas técnicas disponibles para que el ladrón robe cálculos del mazo de la víctima usando Cilk.
01:05:00 En esta sección, se analiza la necesidad de una abstracción de pila de cactus para el sistema de tiempo de ejecución de Cilk. Se explica que el uso de la pila de la víctima puede provocar la corrupción de la pila de la víctima y causar problemas para mantener la coherencia entre todos los trabajadores. Por lo tanto, se necesita una pila de llamadas separada para el ladrón. La implementación de la pila de cactus implica que el ladrón robe la continuación y establezca su puntero de pila en su propia pila mientras aún puede acceder al estado de la función en la pila de la víctima a través de compensaciones de RB p.
01:10:00 En esta sección, el orador explica cómo el sistema de tiempo de ejecución SIL maneja la sincronización de la computación en diferentes procesadores. El sistema utiliza la pila de cactus y un árbol de cálculos para garantizar que la sincronización solo ocurra entre subcálculos anidados bajo una función, no el programa en general. Cuando un trabajador llega a una declaración de sincronización de seda antes de que regresen todos los subcálculos, se convierte en un ladrón y continúa trabajando en el marco de pila de un cómputo robado. Esto permite que el sistema evite desperdiciar trabajadores y garantizar que los cálculos anidados estén correctamente sincronizados. El sistema indica específicamente al compilador que no utilice una optimización que pueda entrar en conflicto con este enfoque.
01:15:00 En esta sección, el sistema de tiempo de ejecución de Cilk se describe como el mantenimiento de un árbol de estados denominado fotogramas completos, que realiza un seguimiento de qué cálculos están esperando a qué otros cálculos finalicen. Este sistema utiliza un árbol de fotogramas completo para realizar un seguimiento de una gran cantidad de información para la ejecución en paralelo, incluidos los punteros a los fotogramas principales, posiblemente a los fotogramas secundarios, y cómo se relacionan entre sí los subcálculos pendientes. Cuando un trabajador encuentra una sincronización, si tiene un cálculo secundario pendiente, no puede sincronizar y debe suspender su marco completo hasta que pueda convertirse en un ladrón para robar más trabajo. Este sistema permite que un programa tenga un amplio paralelismo y simplifica los protocolos de sincronización.
01:20:00 En esta sección, el orador analiza cómo Cilk Runtime System optimiza el caso común en el que la función de ejecución no tiene elementos secundarios pendientes y todos los trabajadores del sistema están ocupados con sus propias tareas. El sistema de tiempo de ejecución utiliza bits del campo de marca de un marco de pila asociado para evaluar si la sincronización es necesaria para una sincronización de seda. El orador también menciona varias otras funciones compatibles con el sistema de tiempo de ejecución, incluidas las excepciones de C++, los hiperobjetos reductores y las genealogías.

OpenCL en el trading Tutoriales de programación Estudiamos ONNX para aplicarlo

MetaQuotes 2023.04.26 14:30 #295

Lección 15. Algoritmos olvidados de la memoria caché

Lección 15. Algoritmos olvidados de la memoria caché

El video analiza los algoritmos que ignoran la memoria caché, que pueden ajustarse automáticamente al tamaño de la memoria caché en una máquina, lograr una buena eficiencia de la memoria caché y no requieren el conocimiento de los parámetros de la memoria caché de la máquina. El video muestra cómo escribir código para simular la difusión de calor a través de ecuaciones diferenciales utilizando el método de plantilla en una matriz 2D. El código tiene versiones en bucle y trapezoidal, siendo esta última más eficiente en caché pero no significativamente más rápida en una simulación 2D debido a la previsibilidad del patrón de acceso del código en bucle. El video también analiza la interacción entre el almacenamiento en caché y el paralelismo y el diagnóstico de posibles cuellos de botella de aceleración paralela. Finalmente, el orador explica los cálculos de plantillas y cómo se actualiza cada punto en una matriz utilizando un patrón fijo llamado plantilla, que puede sufrir fallas de caché y tiene requisitos de almacenamiento que pueden reducirse utilizando algoritmos eficientes que explotan la localidad temporal y espacial.

La segunda parte del video analiza los algoritmos que olvidan la memoria caché para clasificar y fusionar. Específicamente, el video cubre la complejidad de caché del ordenamiento por fusión, presenta el concepto de fusión multidireccional y explica la complejidad de caché del algoritmo de fusión multidireccional. El video también trata sobre el algoritmo de ordenación de embudo, que es un algoritmo de ordenación sin memoria caché que puede fusionar K elementos cuadrados y K listas ordenadas. El algoritmo de clasificación de embudo es óptimo y se construye recursivamente con la raíz cuadrada de K embudos. El video explica que hay muchos otros algoritmos y estructuras de datos que no tienen en cuenta la memoria caché, como árboles b, mantenimiento ordenado de archivos y colas de prioridad. En general, el video proporciona una introducción a los algoritmos que olvidan la memoria caché para aquellos interesados en aprender más sobre el tema.

00:00:00 En esta sección, el video analiza los algoritmos que ignoran el caché, que son un algoritmo que ajusta automáticamente el tamaño del caché en una máquina y logra una buena eficiencia del caché, sin que el código necesite tener ningún conocimiento de los parámetros del caché de la máquina. El video usa el ejemplo de la simulación de la difusión de calor a través de ecuaciones diferenciales para mostrar cómo la computación científica a menudo se basa en ecuaciones diferenciales para describir procesos físicos y luego debe escribir un código eficiente para simular el proceso. El video demuestra cómo escribir código basado en el método de aproximación de diferencias finitas para simular la ecuación de calor 1D.
00:05:00 En esta sección, el orador cubre cómo escribir código para una ecuación de simulación que permite la aproximación de diferencia finita usando el método de plantilla. La ecuación usa derivadas parciales de U con respecto a T y X, y el disertante muestra cómo obtener estas derivadas parciales usando métodos de aproximación. El espacio 2D se representa usando una matriz con los valores X y T representados horizontal y verticalmente, respectivamente. El hablante explica los límites de la matriz y calcula U usando la ecuación.
00:10:00 En esta sección, el presentador explica los cálculos de plantillas, un método ampliamente utilizado en la computación científica para diversos fines. En este método, cada punto de una matriz se actualiza utilizando un patrón fijo llamado plantilla. El cálculo depende de otros tres valores, y esto se conoce como una postura de tres puntos. Aunque los cálculos de plantilla se pueden usar para valores X grandes, el rendimiento puede verse afectado en relación con el almacenamiento en caché, lo que resulta en errores de caché. Además, el almacenamiento requerido para almacenar los datos se puede reducir almacenando solo dos filas, la actual y la anterior, para actualizar los valores de los puntos.
00:15:00 funciona: en cada paso de tiempo, solo estamos actualizando los valores de X para una fila específica usando los valores de la fila anterior. Por lo tanto, podemos alternar qué fila estamos actualizando y qué fila estamos usando como la fila anterior, y solo necesitamos mantener una fila adicional de valores. Sin embargo, este código no es muy eficiente en caché, y podemos hacerlo aún más usando mosaicos o algoritmos de almacenamiento en caché. El modelo de caché ideal asume una caché totalmente asociativa con una política de reemplazo LRU o óptima, y captura las fallas de capacidad pero no las fallas de conflicto en una ejecución en serie. Sin embargo, sigue siendo útil para diseñar algoritmos eficientes que exploten la localidad temporal y espacial.
00:20:00 En esta sección, el orador explica cómo se puede usar un algoritmo que no tiene en cuenta la memoria caché para calcular puntos dentro de un espacio trapezoidal en una matriz 2D sin mirar fuera de ella. El cálculo implica una función del núcleo que lleva un puntero a la modificación de UT a X y devuelve W de 0 más alfa multiplicado por W de 1 negativo menos 2 multiplicado por W de 0 más W de 1. El comportamiento del almacenamiento en caché se analiza suponiendo una política de reemplazo de LRU y el el número de errores de caché es Theta de NT sobre B para cada fila. Sin embargo, el orador señala que se puede lograr un mejor rendimiento con el mosaico, pero continúa discutiendo la versión sin memoria caché. El trapezoide tiene una base superior en T1 y una base inferior en T0. El algoritmo calcula todos los puntos dentro del trapezoide usando condiciones de desigualdad que involucran T, t0, t1, X, x0, x1, DX0, DX1, donde DX0 y DX1 son -1, 0 o 1 que representan pendientes.
00:25:00 En esta sección, el orador describe un enfoque de divide y vencerás para el algoritmo de la regla trapezoidal. El enfoque tiene un caso base donde la altura del trapezoide es 1 y un bucle calcula todos los valores según el orden de cálculo. El algoritmo tiene dos casos recursivos, a saber, el corte de espacio y el corte de tiempo, que dependen del ancho y la altura del trapezoide, respectivamente. Cuando el trapecio es demasiado ancho, se aplica un corte de espacio donde el trapezoide se corta verticalmente con una línea con pendiente uno negativo que pasa por el centro del trapezoide. Por el contrario, se aplica un corte de tiempo cuando el trapezoide es demasiado alto y se corta con una línea horizontal que pasa por el centro. El algoritmo recursivo realiza dos llamadas que atraviesan los lados izquierdo y derecho del trapezoide y la parte inferior y superior, respectivamente, en un orden específico para evitar la interdependencia entre los puntos.
00:30:00 En esta sección, el orador analiza la complejidad de la memoria caché de los algoritmos que olvidan la memoria caché. Analizan el enfoque del árbol de recurrencia y descubren que el algoritmo se divide en dos subproblemas en cada nivel hasta llegar al caso base, que representa el theta de los puntos HW donde H es Theta de W. El número de errores de caché por hoja es theta W sobre B, y el número de hojas es Theta de NT sobre HW. Los nodos internos no contribuyen sustancialmente a la complejidad de la memoria caché. La complejidad de la memoria caché se generaliza a más de una dimensión y, si d es una, da como resultado NT sobre MB.
00:35:00 En esta sección, el orador explica la diferencia entre el código de bucle y el código trapezoidal, que tiene una complejidad de caché mucho mejor al guardar un factor de M donde M es el número de líneas de caché. La simulación demuestra que el código trapezoidal incurre en menos errores de caché en comparación con el código de bucle, por lo que finaliza el cálculo mucho más rápido. Sin embargo, el orador señala que esta simulación fue solo para una dimensión y continúa mostrando una demostración de lo que sucede en dos dimensiones.
00:40:00 En esta sección, el presentador demuestra una simulación en tiempo real de la difusión del calor en un espacio 2D, donde los colores en la pantalla corresponden a las temperaturas. El presentador compara el rendimiento del código de bucle y el código trapezoidal, y revela que, aunque el código trapezoidal incurre en muchos menos errores de caché, es solo marginalmente más rápido que el código de bucle. Se sugiere que esto podría deberse a que la captación previa del hardware ayuda al código en bucle, ya que su patrón de acceso es regular y fácil de predecir.
00:45:00 En esta sección, el orador analiza la interacción entre el almacenamiento en caché y el paralelismo. Explican un teorema que establece que minimizar las fallas de caché en la ejecución en serie puede minimizarlas esencialmente en la ejecución en paralelo asumiendo un algoritmo de intervalo bajo. Luego demuestran cómo el algoritmo trapezoidal puede funcionar en paralelo usando un corte en V, donde dos trapecios independientes se ejecutan en paralelo y el trapezoide gris se ejecuta después. También mencionan el corte en V invertido que se usa para trapecios invertidos.
00:50:00 En esta sección, el orador analiza el rendimiento del código de bucle paralelo y el código trapezoidal paralelo en comparación con sus contrapartes en serie. El código de bucle paralelo logra menos de la mitad de la aceleración potencial a pesar de tener más paralelismo potencial que el código trapezoidal. Esto se debe a que, en el caso paralelo, hay un cuello de botella en el ancho de banda de la memoria, lo que evita que la captación previa ayude al código de bucle paralelo, en comparación con el caso en serie, donde hay mucho ancho de banda de memoria. Por el contrario, el código trapezoidal logra una aceleración casi lineal, lo que es consistente con el hecho de que la eficiencia de la memoria caché juega un papel mucho más importante en tamaños de entrada más grandes donde la memoria caché es tan pequeña, en comparación con el tamaño de entrada.
00:55:00 En esta sección, el orador analiza cómo diagnosticar un cuello de botella de aceleración paralela e identifica varias cosas que podrían causarlo, como paralelismo insuficiente, sobrecarga de programación, falta de ancho de banda de memoria y contención. Sugieren varias formas de diagnosticar estos problemas, incluido el uso de Silk Scale para medir el paralelismo en el código y realizar contadores de hardware para medir el ancho de banda de la memoria. Sin embargo, el diagnóstico de la contención es particularmente desafiante, y el orador aconseja analizar las primeras tres posibles causas antes de evaluar si la contención es el problema. Finalmente, el orador pasa a discutir el cálculo de la plantilla.
01:00:00 En esta sección, el orador analiza el análisis de la complejidad de caché de la ordenación por combinación analizando primero la complejidad de combinar dos matrices de entrada ordenadas. El tiempo para hacer esto es proporcional a la suma de los tamaños de las matrices de entrada. El número de errores de caché en los que se incurre al fusionar n elementos es theta n sobre B, donde B es el número de bytes en una línea de caché. Merge sort tiene dos llamadas recursivas en entradas de la mitad del tamaño y combina las salidas ordenadas de sus llamadas recursivas. El trabajo general del ordenamiento por fusión es theta de n log n, que se analiza utilizando el método del árbol de recursión. También se analiza la complejidad de caché de la ordenación por combinación y se muestra que la cantidad de errores de caché es proporcional a la cantidad de bloques de caché necesarios para almacenar los datos, que es theta n sobre B log M, donde M es el tamaño máximo a sub-bloque puede tener.
01:05:00 En esta sección, el orador explica la recurrencia de la complejidad de caché de ordenación por combinación. El caso base se produce cuando el tamaño del problema cabe en la memoria caché, lo que provoca errores de memoria caché Θ(n/B). De lo contrario, el algoritmo tiene dos llamadas recursivas de tamaño n/2 y fallas de caché Θ(n/B) para fusionar los resultados. El análisis implica el número de niveles de un árbol recursivo, que es log base 2 de n/CM, donde CM es una constante. El número de errores de caché por hoja es Θ(M/B * n/CM), dando un número total de errores de caché de Θ(n/B * log (n/CM)), ahorrando un factor de B en el primer término . Sin embargo, para tamaños de problemas más grandes, solo guardamos un factor de B en comparación con el trabajo, mientras que guardamos un factor de B log n para tamaños de problemas pequeños. El hablante pregunta si hay una solución mejor y la respuesta siempre es sí.
01:10:00 En esta sección, el orador explica cómo usar la fusión multidireccional para fusionar subarreglos ordenados y presenta la idea de un árbol de torneo para determinar los elementos mínimos de los subarreglos. También explican el trabajo y las complejidades de la memoria caché de este enfoque, que se utiliza en algoritmos que no tienen en cuenta la memoria caché para la clasificación. La complejidad del trabajo de la combinación multidireccional es la misma que la clasificación de combinación binaria, mientras que la complejidad de la caché está determinada por la cantidad de errores de caché necesarios para llenar el árbol del torneo y acceder a las matrices de entrada, que se pueden optimizar si R es menor que C*M/B para una pequeña constante C.
01:15:00 En esta sección, el disertante analiza la complejidad de la memoria caché del algoritmo de ordenación por fusión multidireccional y lo compara con el algoritmo de ordenación por fusión binaria. El algoritmo de ordenación de fusión multidireccional implica dividir el problema en subproblemas de tamaño n/R y pagar n/B errores de caché para fusionarlos. El número de niveles del árbol de recurrencia es logaritmo base R de n/cm, y el tamaño de la hoja es cm. El hablante establece R igual a theta de M/B, haciéndolo lo más grande posible, y analiza la complejidad de la memoria caché, que resulta ser theta n log n dividido por B log M. En comparación con el algoritmo de ordenación de combinación binaria, el multi El algoritmo de ordenación de combinación de vías ahorra un factor de registro M en errores de caché. Sin embargo, el algoritmo no ignora la memoria caché y el valor de R debe ajustarse para una máquina en particular, lo que puede ser un problema si se están ejecutando otros trabajos que compiten por la memoria caché.
01:20:00 En esta sección, el disertante analiza el algoritmo de ordenación de embudo, que es un algoritmo de ordenación que no tiene en cuenta la memoria caché y que puede fusionar K elementos cuadrados y K listas ordenadas. Se muestra que el costo de esta combinación es el mismo que el del algoritmo de clasificación de combinación multidireccional, pero el algoritmo de clasificación de embudo no tiene en cuenta la memoria caché y su límite es óptimo. El orador presenta una imagen de cómo se ve un embudo K y explica que el algoritmo se construye recursivamente con raíz cuadrada de K embudos que alimentan elementos a los búferes, que, a su vez, alimentan elementos a la raíz cuadrada de salida final del embudo K, produciendo la salida para el embudo K. El orador también menciona que hay muchos otros algoritmos y estructuras de datos que no tienen en cuenta la memoria caché, como árboles b, mantenimiento ordenado de archivos y colas de prioridad, e invita a los espectadores a aprender más sobre ellos en línea.

OpenCL en el trading Comercio Cuantitativo Tutoriales de programación

MetaQuotes 2023.04.26 14:31 #296

Lección 16. Programación paralela no determinista

Lección 16. Programación paralela no determinista

Este video analiza varios conceptos relacionados con la programación paralela determinista y no determinista. El ponente destaca la importancia de evitar el no determinismo, ya que puede dar lugar a comportamientos anómalos y una depuración difícil. Las estrategias para gestionar el no determinismo incluyen el uso de valores fijos, reproducción de registros, herramientas de análisis, encapsulación y pruebas unitarias. El uso de mutexes se explora en detalle, incluido giro frente a rendimiento, reentrante frente a no reentrante y justo frente a injusto. El ponente también toca el concepto de cambio de contexto y el "problema del alquiler de esquís" en el contexto de la programación paralela. El segmento concluye discutiendo los principios básicos de la ingeniería de rendimiento en procesadores multinúcleo.

La segunda parte del video cubre el problema del interbloqueo en la programación paralela y ofrece soluciones para evitarlo, como la ordenación lineal de mutexes que garantiza que no haya ciclos de espera. Además, el orador presenta el concepto de memoria transaccional, que garantiza la atomicidad al representar una región crítica como una transacción que confirma todas las actualizaciones a la vez. Luego, el video presenta un algoritmo que utiliza un enfoque basado en bloqueos con una matriz de propiedad finita y un método de solicitud de clasificación de liberación para evitar interbloqueos e inanición sin necesidad de un bloqueo global. Por último, se explica el algoritmo de liberación, ordenación y readquisición, que evita que varios bloqueos intenten adquirir un bloqueo simultáneamente, lo que evita problemas de rendimiento.

00:00:00 En esta sección, el disertante introduce el concepto de determinismo en la programación y cómo se relaciona con la computación paralela. Un programa es determinista si cada ubicación de memoria se actualiza con la misma secuencia de valores en cada ejecución y el programa siempre se comporta de la misma manera. Los programas deterministas tienen la ventaja de ser repetibles, lo que los hace más fáciles de depurar. El disertante enfatiza la importancia de nunca escribir programas paralelos no deterministas ya que pueden presentar comportamientos anómalos que son difíciles de depurar. Sin embargo, en la práctica, puede ser un desafío evitar el no determinismo en la computación paralela.
00:05:00 En esta sección, el orador analiza la programación paralela no determinista y el hecho de que a veces puede conducir a un mejor rendimiento, pero aún debe evitarse a menos que sea necesario. El orador recomienda diseñar una estrategia de prueba para manejar el no determinismo si debe escribir un programa de esa manera. Los ejemplos de estrategias incluyen desactivar el no determinismo, usar la misma semilla para números aleatorios o proporcionar valores fijos para las entradas del programa que, de lo contrario, podrían cambiar aleatoriamente. El orador enfatiza la importancia de tener una forma de manejar los errores en el programa causados por el no determinismo.
00:10:00 En esta sección, el orador habla sobre estrategias para lidiar con la programación no determinista, como la reproducción de registros, encapsular el no determinismo, sustituir una alternativa determinista, usar herramientas de análisis y pruebas unitarias. El orador enfatiza la importancia de controlar el no determinismo para mejorar las posibilidades de detectar errores en el código. El orador también brinda un ejemplo del uso de la exclusión mutua y la atomicidad en una tabla hash para ilustrar cómo manejar la programación no determinista.
00:15:00 En esta sección, el orador analiza cómo las instrucciones paralelas que acceden a la misma ubicación pueden provocar errores de carrera y destruir la integridad del sistema. La solución estándar es hacer que algunas instrucciones sean atómicas, lo que significa que el resto del sistema las ve como completamente ejecutadas o no ejecutadas en absoluto. Para lograr esto, se utiliza un bloqueo de exclusión mutua o bloqueo mutex, que es un objeto con funciones de miembro de bloqueo y desbloqueo. Cada ranura se convierte en una estructura con un bloqueo mutex y un puntero al contexto de la ranura, lo que permite usar las funciones de bloqueo y desbloqueo antes de acceder a la lista, lo que garantiza la corrección del sistema.
00:20:00 En esta sección, el video explora el uso de mutexes para implementar la atomicidad y cómo se relaciona con las carreras de determinación. Los bloqueos mutex pueden garantizar que las secciones críticas sean atómicas, pero el código resultante no es determinista debido a una carrera de determinación que puede ser lo que se desea en algunos casos. El video enfatiza la importancia de comprender la diferencia entre las carreras de datos y las carreras de determinación, y señala que simplemente eliminar las carreras de datos no significa necesariamente que no haya errores presentes en el código. Es importante tener una forma de detectar el no determinismo para evitar falsos positivos o errores de carrera faltantes en el código.
00:25:00 En esta sección, el orador explica que no tener carreras de datos no significa necesariamente que el código no tenga errores. Si bien las carreras de datos no son aspectos positivos del código, el ejemplo del bloqueo para proporcionar atomicidad puede conducir a una violación de la atomicidad. Además, pueden ocurrir carreras benignas, como cuando dos procesos paralelos acceden al mismo valor, lo que puede generar el mismo resultado, pero también podría generar valores incorrectos en algunas arquitecturas. El orador argumenta que, si bien algunas personas consideran que las razas benignas son inofensivas, aún es esencial identificarlas y evitarlas.
00:30:00 En esta sección, el orador explica los peligros de la programación no determinista, particularmente debido a las condiciones de carrera que pueden ocurrir cuando varios procesos intentan establecer valores en la misma ubicación. El orador presenta el concepto de "Silks", que permite carreras intencionales pero puede ser peligroso si no se usa correctamente. La complejidad de las carreras también puede dificultar la depuración y confundir las herramientas destinadas a ayudar a detectar el código correcto. El orador también analiza cómo la implementación de mutexes y sus parámetros pueden afectar su comportamiento, por ejemplo, si están cediendo o girando.
00:35:00 En esta sección, el video explica tres propiedades básicas de los mutexes en la programación paralela: girar frente a ceder, reentrante frente a no reentrante y justo frente a injusto. El concepto de girar frente a ceder es la idea de que un subproceso no permanecerá inactivo y verificará continuamente el acceso a un bloqueo, sino que cederá el control al sistema operativo para una ejecución más eficiente. La exclusión mutua reentrante permite que un subproceso que ya tiene un bloqueo lo adquiera de nuevo, mientras que los bloqueos no reentrantes se bloquean si el subproceso intenta volver a adquirir una exclusión mutua que ya tiene. Por último, fair mutex garantiza que el subproceso que ha estado esperando más tiempo obtenga el bloqueo primero para evitar la posibilidad de un problema de inanición. El video también proporciona una implementación de un mutex giratorio simple en lenguaje ensamblador.
00:40:00 En esta sección, el video analiza el uso de mutex en la programación paralela y por qué se usa la instrucción de intercambio en lugar de solo obtener el mutex. Se explica que la operación de cambio es similar a un derecho, y para ejercer un derecho, la línea de efectivo en la que se encuentra debe invalidarse sobre las demás y mantenerse en estado modificado o excluyente. Esto crea tráfico en la red de memoria y ralentiza el proceso. Por otro lado, al usar la instrucción de intercambio, las líneas de caché se ponen en estado compartido, lo que mantiene el proceso más rápido y genera menos tráfico.
00:45:00 En esta sección, el disertante discute la diferencia entre un mutex giratorio y un mutex cedente. En un mutex giratorio, el programa sigue comprobando que se desbloquee el mutex, mientras que en un mutex cediendo, el programa cede el control al sistema operativo, lo que le permite programar otra cosa. El orador señala que también hay otro tipo de mutex llamado mutex competitivo, que logra los objetivos de un mutex giratorio y un mutex cedente. El orador también explora el uso del paso de mensajes o interrupciones para informar a los hilos en espera, pero señala que la solución más simple sería usar un mecanismo de exclusión mutua.
00:50:00 En esta sección, el orador explica el concepto de cambio de contexto, que es la frecuencia con la que el sistema operativo cambia entre subprocesos en los procesadores disponibles. Normalmente, el sistema cambia de contexto unas 100 veces por segundo, lo que significa que cada cambio tarda unos 10 milisegundos. Sin embargo, esto es más de un orden de magnitud mayor que el tiempo de ejecución de una instrucción simple, lo que significa que hay muchas instrucciones que pueden ejecutarse antes de que el subproceso tenga la oportunidad de volver y obtener un bloqueo. Este problema se puede resolver usando una combinación de hilado y cedencia. El orador llama a esto el "problema del alquiler de esquís" en la literatura de Teoría.
00:55:00 En esta sección, el video analiza el proceso de decidir si comprar o alquilar equipos para una tarea en particular, usando el ejemplo de comprar o alquilar equipos deportivos. El orador alienta a los espectadores a considerar los costos de alquilar versus comprar, y sugiere alquilar hasta que el costo sea igual al de comprar, y luego realizar la compra. El video también explora el concepto de tiempo de cambio de contexto, tiempo de acceso al disco y el problema del interbloqueo cuando se mantienen varios bloqueos a la vez. En general, este segmento cubre los principios básicos de la ingeniería de rendimiento en procesadores multinúcleo.
01:00:00 En esta sección, el orador explica el interbloqueo, que es cuando dos subprocesos contienen recursos que el otro subproceso requiere, lo que genera una pérdida de rendimiento. Hay tres condiciones básicas para el interbloqueo: exclusión mutua (control exclusivo sobre los recursos), no preferencia (recursos retenidos hasta que finalicen) y espera circular (un ciclo de subprocesos esperando recursos retenidos por el siguiente). La eliminación de cualquiera de estas restricciones puede resolver el problema del interbloqueo. El orador usa "Dining Philosophers", una historia contada por Tony Hoare basada en una pregunta de examen de Edsger Dijkstra, para ilustrar el problema del punto muerto. La historia involucra a filósofos sentados alrededor de una mesa, comiendo fideos con palillos chinos donde cada plato de fideos está situado entre dos palillos, y necesitan dos palillos para comer los fideos. Los filósofos agarran el palillo de la izquierda y la derecha para comer sus fideos. Sin embargo, si todos recogen el palillo izquierdo a su izquierda, terminarán muriendo de hambre.
01:05:00 En esta sección, el orador analiza el tema del interbloqueo en la programación paralela y ofrece una solución que garantiza la no preferencia y evita el interbloqueo: la ordenación lineal de mutexes. Al numerar cada mutex y bloquearlos estratégicamente en función de su orden numérico, los programadores pueden garantizar que no se produzca un ciclo de espera (la condición necesaria para el interbloqueo). Sin embargo, advierte a los programadores que sean conscientes de la encapsulación de bloqueos del sistema de tiempo de ejecución en Silk, ya que la introducción de no determinismo adicional a través de estos bloqueos puede generar problemas. Comparte un ejemplo en el que puede ocurrir un punto muerto con solo un bloqueo, y enfatiza la importancia de una consideración cuidadosa al diseñar programas paralelos.
01:10:00 En esta sección, el ponente profundiza en el tema de la memoria transaccional, una técnica reciente a nivel de investigación que implica tener transacciones de base de datos donde la atomicidad ocurre implícitamente, sin necesidad de especificar bloqueos. El orador da un ejemplo de cómo la memoria transaccional es útil en el cálculo de gráficos concurrentes, a saber, la eliminación gaussiana, donde tener dos nodos eliminados simultáneamente provoca violaciones de atomicidad. La idea detrás de la memoria transaccional es representar la región crítica como una transacción y, al confirmar, todas las actualizaciones de memoria en la región crítica aparecen como si ocurrieran a la vez.
01:15:00 n esta sección, el orador analiza la resolución de conflictos, la resolución de disputas, el avance y el rendimiento en la memoria transaccional. Presentan un algoritmo que utiliza un enfoque basado en bloqueos con una matriz de propiedad finita y un método de ordenación de liberación para evitar interbloqueos e inanición sin necesidad de un bloqueo global. El algoritmo registra lecturas y escrituras para permitir la reversión o la confirmación atómica cuando se cancela una transacción. La matriz de bloqueo se utiliza para bloquear una ubicación a la que se asigna una función hash, lo que permite una adquisición justa de bloqueos. Este algoritmo permite transacciones simultáneas sin sacrificar el rendimiento ni causar interbloqueos.
01:20:00 En esta sección, el orador analiza un algoritmo llamado liberación, ordenación y readquisición. El algoritmo funciona intentando adquirir con avidez un bloqueo de una ubicación de memoria y, si surge un conflicto, la transacción se revierte sin liberar los bloqueos que contiene. Posteriormente, el algoritmo libera todos los bloqueos con índices mayores que el índice de la ubicación a la que intenta acceder. Luego adquiere el bloqueo deseado y finalmente adquiere los bloqueos liberados en orden ordenado. Este proceso se repite hasta que la transacción sea exitosa. El algoritmo está diseñado para evitar que múltiples bloqueos intenten adquirir un bloqueo simultáneamente, lo que puede causar problemas de rendimiento.

OpenCL en el trading Tutoriales de programación Python para el trading

MetaQuotes 2023.04.26 14:33 #297

Lección 17. Sincronización sin bloqueos

Lección 17. Sincronización sin bloqueos

Charles Leiserson explora el concepto de sincronización sin bloqueos en un video de YouTube. Brinda un ejemplo que demuestra la necesidad de un orden lineal global de instrucciones para garantizar la ejecución secuencial y explica cómo se puede lograr la exclusión mutua a través de la coherencia secuencial, evitando las dificultades y los problemas potenciales del uso de bloqueos. Leiserson presenta el algoritmo de Peterson como una solución que usa solo operaciones de carga y almacenamiento para acceder a secciones críticas sin interferencia de procesos concurrentes. El video también cubre los desafíos de la sincronización a través de la memoria debido al reordenamiento del hardware y el concepto de vallas de memoria para mantener el orden relativo con otras instrucciones. Leiserson argumenta que admitir la consistencia secuencial para máquinas paralelas es beneficioso pero difícil de lograr para los diseñadores de hardware.

La segunda parte del video analiza el uso de vallas de memoria e instrucciones de sincronización para prevenir errores en programas paralelos. El orador explora diferentes formas de implementar barreras de memoria, implícita o explícitamente, y la importancia de una ingeniería y coordinación cuidadosas entre diferentes equipos que trabajan en diferentes aspectos de un procesador. Además, el disertante analiza el uso de instrucciones CAS como parte del algoritmo sin bloqueo en el estándar de lenguaje C11 para implementar mutexes de algoritmos de exclusión mutua sin interbloqueo de n subprocesos utilizando solo espacio constante. Charles Leiserson explica el problema de usar bloqueos en un sistema de subprocesos múltiples y la solución de usar CAS en su lugar, ya que un subproceso que mantiene el bloqueo durante mucho tiempo puede potencialmente bloquear otros subprocesos que esperan acceder al mismo recurso. Además, el video destaca el problema potencial del problema ABA con la comparación y el intercambio y alienta a los interesados en el tema a obtener más información sobre los algoritmos sin bloqueo.

00:00:00 y sus instrucciones se intercalan para producir un orden lineal global de todas las instrucciones. Esta es la idea detrás del modelo de memoria de consistencia secuencial, que es el modelo de memoria más importante desde un punto de vista teórico. Es importante comprender los modelos de memoria porque, en ausencia de bloqueos, el comportamiento de los programas paralelos depende del modelo de memoria. Un ejemplo presentado en la lección ilustra este punto preguntando si es posible que dos procesadores tengan el valor de 0 después de ejecutar su código en paralelo, lo que depende del modelo de memoria que se utilice.
00:05:00 En esta sección, Charles Leiserson analiza el concepto de sincronización sin bloqueos donde las cargas y los almacenes deben parecer obedecer algún orden lineal global para que la ejecución sea secuencial. Utiliza el ejemplo de intercalar varios valores para demostrar diferentes rutas de ejecución que pueden ocurrir y cómo el hardware puede hacer lo que quiera. También explica que, aunque puede haber muchas formas diferentes de intercalar valores, debe parecer que las cargas y los almacenamientos siguieron un orden lineal para que la ejecución sea consistente. En última instancia, Leiserson concluye que no hay ejecución que termine con ambos valores siendo cero, y es interesante notar que de las computadoras modernas, ninguna de ellas proporciona consistencia secuencial.
00:10:00 En esta sección, se analiza el concepto de consistencia secuencial, que implica comprender la relación que sucede antes entre las instrucciones y su orden, la relación lineal entre la conexión de la flecha hacia la derecha, el orden del procesador y la secuencia de las instrucciones. Además, la exclusión mutua se puede lograr sin usar instrucciones o bloqueos pesados pensando en la coherencia secuencial e implementando la estructura de datos compartidos mediante el uso de cargas y almacenes. Las notas de clase describen métodos que utilizan operaciones especializadas como probar y establecer o comparar e intercambiar, pero la solución presentada evita la creación de interbloqueos u otras cosas malas que ocurren cuando se usan bloqueos.
00:15:00 En esta sección, Charles Leiserson explica el algoritmo de Peterson para lograr la exclusión mutua en un programa concurrente usando solo operaciones de carga y almacenamiento. El algoritmo permite que dos procesos simultáneos, Alice y Bob, ejecuten código sin interferir entre sí mediante el uso de un conjunto de variables y un mecanismo de turnos. El código garantiza que solo un proceso a la vez pueda ingresar a una sección crítica y modificar un recurso compartido. A diferencia de los bloqueos, el algoritmo de Peterson no se basa en adquirir o liberar un bloqueo y, en su lugar, utiliza cargas y almacenes para lograr la exclusión mutua.
00:20:00 En esta sección, el orador analiza el algoritmo de Peterson para lograr la exclusión mutua en la sección crítica sin usar bloqueos. Explica que solo una persona a la vez puede ingresar a la sección crítica, y el algoritmo garantiza que alguien que quiera ingresar a la sección crítica pueda hacerlo si es el único que quiere ir. Luego, el orador presenta una prueba del algoritmo, que implica asumir que tanto Alice como Bob se encuentran juntos en la sección crítica y derivar una contradicción. La prueba se basa en la relación "sucede antes" y el orden del programa de las instrucciones ejecutadas.
00:25:00 En esta sección, el locutor explica el proceso de sincronización sin bloqueos. Establecen cadenas de instrucciones y se aseguran de que se produzcan en el orden correcto para evitar errores de sincronización. Usan el ejemplo de Bob y Alice queriendo acceder a un recurso compartido como demostración. Explican que al sincronizar, los ingenieros deben tener cuidado y revisar los "sucede antes que las cosas" para asegurarse de que ocurran en el orden correcto.
00:30:00 En esta sección, Charles Leiserson analiza el concepto de verificación de modelos y su uso en el análisis de protocolos de red, seguridad y caché. Luego continúa explicando las propiedades del algoritmo de Peterson, que garantiza la libertad de hambre pero no funciona con más de dos procesos. Leiserson también explora los desafíos de sincronizar a través de la memoria y la falta de consistencia secuencial en los procesadores modernos, lo que lleva a una consistencia de memoria relajada y dificultad para lograr una sincronización correcta.
00:35:00 ¿Es seguro reordenar las instrucciones sin causar problemas con la latencia de carga? La segunda restricción es cuando no hay dependencia de datos entre las instrucciones, lo que significa que las instrucciones no comparten datos ni usan la misma ubicación en la memoria. Reordenar las instrucciones en este caso puede mejorar el rendimiento y cubrir la latencia de sobrecarga, ya que la carga se puede realizar antes y se pueden realizar otros trabajos mientras se espera el resultado. Comprender estos conceptos a nivel de hardware puede ayudar a razonar sobre el software y optimizar el rendimiento.
00:40:00 En esta sección, Charles Leiserson explica el concepto de reordenamiento en sincronización sin bloqueos. Aclara que es seguro realizar el reordenamiento siempre que no haya concurrencia, especialmente cuando el procesador está funcionando o hay burbujas en el flujo de instrucciones. Esto se debe a que, en los procesadores modernos, el hardware almacena datos en un búfer y evita las cargas yendo directamente al sistema de memoria. Sin embargo, esta omisión puede generar problemas de corrección si uno de los almacenes es lo que se está cargando.
00:45:00 En esta sección, Charles Leiserson explica cómo ocurre el reordenamiento del hardware y por qué no satisface la consistencia secuencial, y cómo x86 tiene un modelo de consistencia de memoria llamado orden de almacenamiento total, que es más débil que la consistencia secuencial. Las reglas para el pedido total de la tienda incluyen nunca reordenar cargas con cargas, que los procesadores externos vean las cargas en el mismo orden, nunca reordenar tiendas con tiendas y las cargas solo se reordenan con tiendas anteriores en una ubicación diferente, pero no con cargas anteriores a la misma ubicación. Las instrucciones de bloqueo y el ordenamiento de la memoria respetan un orden total.
00:50:00 En esta sección, el orador analiza cómo el reordenamiento de instrucciones puede violar la consistencia secuencial y dar como resultado valores incorrectos. El reordenamiento puede ocurrir tanto en el hardware como en el compilador, y es importante saber que las instrucciones de bloqueo no se moverán antes que otras instrucciones. El orador también señala que las cargas pueden ir antes de las tiendas si están en una dirección diferente. El peligro de reordenar se demuestra en el algoritmo de Peterson, que podría estropearse por completo si se producen ciertos reordenamientos. Por lo tanto, es importante escribir código determinista para evitar estos problemas al sincronizar a través de la memoria.
00:55:00 En esta sección, Charles Leiserson analiza el tema del reordenamiento al escribir código paralelo y concurrente, donde es importante evitar que ocurra una carga particular antes de una tienda. Para manejar tales escenarios, los ingenieros introducen vallas de memoria, que mantienen un orden relativo con otras instrucciones, pero tienen el costo de una mayor complejidad y posibles errores. Leiserson también argumenta que es beneficioso para las máquinas paralelas admitir la consistencia secuencial, pero es un desafío para los diseñadores de hardware.
01:00:00 En esta sección, el orador analiza la importancia de las barreras de memoria y las instrucciones de sincronización para evitar que los programas paralelos encuentren errores. El orador describe diferentes formas en que se pueden implementar vallas de memoria, como explícitamente como una instrucción o implícitamente a través de otras instrucciones de sincronización, como el bloqueo y el intercambio. Sin embargo, hay casos en los que una valla de memoria puede ralentizar un programa, lo que demuestra la importancia de una ingeniería cuidadosa y la coordinación entre diferentes equipos que trabajan en diferentes aspectos de un procesador. Además, el orador aconseja el uso de variables volátiles y vallas de compilación para evitar que el compilador optimice las variables y cause errores en el código paralelo.
01:05:00 En esta sección, el disertante analiza la sincronización sin bloqueos en el lenguaje estándar C11. El estándar define un modelo de memoria débil, que permite declarar las cosas como atómicas, lo que requiere el uso de operaciones costosas como la valla de memoria o una comparación e intercambio atómico para un algoritmo de exclusión mutua sin puntos muertos. Aquí, la instrucción CAS (Compare-and-Swap) se explora como parte del algoritmo sin bloqueo. La instrucción verifica si el valor en la memoria es el mismo que el valor anterior antes de cambiarlo al nuevo valor, todo hecho atómicamente. El uso de CAS permite implementar mutexes de algoritmos de exclusión mutua sin puntos muertos de n subprocesos utilizando solo un espacio constante. Una instrucción de bloqueo, que gira hasta que obtiene el valor verdadero, se usa para cambiar en verdadero indicando que alguien tiene el bloqueo.
01:10:00 En esta sección, el profesor Charles Leiserson explica cómo utilizar la comparación e intercambio (CAS) para resolver problemas de sincronización. Demuestra cómo usar CAS como un candado y corrige un error en el código presentado por un estudiante. Luego presenta un código incorrecto utilizado para calcular la suma de valores en una matriz, lo que conduce a una condición de carrera. Introduce los bloqueos mutex como una solución típica y explica el problema potencial de que un subproceso se intercambie después de adquirir el bloqueo, lo que lleva a otros subprocesos a esperar el bloqueo, lo que dificulta el progreso.
01:15:00 En esta sección, Charles Leiserson explica el problema de usar bloqueos en un sistema de subprocesos múltiples y la solución de usar CAS en su lugar. Con los bloqueos, un subproceso puede mantener potencialmente el bloqueo durante mucho tiempo, bloqueando otros subprocesos que esperan acceder al mismo recurso. Sin embargo, con CAS, una carga de x es seguida por un almacenamiento de x después de calcular un valor temporal y al mismo tiempo tener las variables antiguo y nuevo para almacenar el resultado anterior y agregar el resultado temporal a ese valor anterior para producir un nuevo valor que puede ser intercambiado si el valor anterior no ha cambiado. Charles también menciona el problema de ABA con comparar e intercambiar y alienta a los interesados en el tema a aprender más sobre los algoritmos sin bloqueo.

OpenCL en el trading Tutoriales de programación Python para el trading

MetaQuotes 2023.04.26 14:34 #298

Lección 18. Idiomas específicos de dominio y autotuning

Lección 18. Idiomas específicos de dominio y autotuning

En este video, el profesor Saman Amarasignhe del departamento EECS del MIT analiza los beneficios del uso de lenguajes específicos de dominio (DSL) y el ajuste automático en la ingeniería de rendimiento. Él enfatiza la importancia de los DSL, que capturan dominios específicos del área que son difíciles de describir en lenguajes de propósito general, lo que permite a los programadores aprovechar el conocimiento de los expertos del dominio para un mejor rendimiento. Singh analiza la optimización de los procesos de gráficos mediante DSL, incluida la partición de gráficos y la importancia de la forma del gráfico en el cálculo. Presenta DSL Halide para el procesamiento de imágenes, que permite una rápida optimización del código y portabilidad entre máquinas. Habla del uso de Halide en varias industrias como Google y Adobe. En última instancia, destaca la importancia de experimentar con diferentes enfoques para optimizar el código mientras se enfoca en el paralelismo, la localidad y el trabajo redundante.

El video también habla sobre los desafíos de la ingeniería de rendimiento y la búsqueda de los parámetros óptimos para que un programa se ejecute de manera eficiente. El orador sugiere que el ajuste automático puede abordar este problema al buscar automáticamente en el gran espacio de parámetros para encontrar los valores óptimos. Señala que la búsqueda exhaustiva puede ser poco práctica y que las soluciones basadas en heurísticas pueden no ser óptimas. El ajuste automático, que define un espacio de valores aceptables e itera en función de los resultados de rendimiento, puede acelerar el proceso de búsqueda de soluciones óptimas. El orador también analiza la aplicación del ajuste automático en la generación de horarios para Try, que pudo producir horarios de manera más eficiente y efectiva que la búsqueda exhaustiva.

00:00:00 En esta sección, el profesor Saman Amarasignhe, profesor del departamento EECS del MIT, habla sobre lenguajes específicos de dominio y autoajuste. Él explica que estos lenguajes tienen beneficios de ingeniería porque capturan dominios específicos de áreas específicas que son difíciles de describir en un lenguaje de propósito general. Los lenguajes específicos de dominio son mucho más fáciles de entender y mantener, y permiten al programador aprovechar el conocimiento de los expertos del dominio para obtener un rendimiento realmente bueno. Además, si se construye correctamente, un lenguaje específico de dominio puede dejar la decisión de nivel inferior al compilador, lo que hace que el proceso de optimización sea mucho más simple.
00:05:00 En esta sección, el orador analiza el uso de lenguajes específicos de dominio (DSL) en ingeniería de rendimiento. Fomentan dejar el rendimiento al compilador siempre que sea posible e introducen tres lenguajes/marcos de programación diferentes para el procesamiento de gráficos: Graffiti, Halide y OpenTuner. Señalan que los gráficos están en todas partes, desde las búsquedas de Google hasta los motores de recomendación, y profundizan en el algoritmo PageRank que utiliza Google para clasificar las páginas web. El algoritmo PageRank analiza los vecinos de una página web y calcula una nueva clasificación en función de su influencia, lo que demuestra la importancia del procesamiento de gráficos en la ingeniería de rendimiento.
00:10:00 En esta sección, el orador analiza los algoritmos gráficos, que pueden implicar el procesamiento de grandes cantidades de datos y la iteración de los cálculos de todo el gráfico. Para optimizar el rendimiento del código, se puede utilizar un DSL. El tipo de algoritmos utilizados para el procesamiento de gráficos incluye algoritmos basados en topología, en los que todo el gráfico participa en el cálculo, y algoritmos basados en datos, en los que el procesamiento se realiza en una pequeña región o parte del gráfico. También hay múltiples formas de hacer inversiones de gráficos, y cada forma tiene un conjunto diferente de resultados.
00:15:00 En esta sección, se trata el tema de la partición de gráficos, donde un gráfico grande se divide en partes más pequeñas. La ventaja de particionar un gráfico es que permite el paralelismo y también proporciona una buena localidad, lo que significa que los nodos en los que se trabaja son lo suficientemente pequeños como para caber en la memoria caché. La partición de gráficos también tiene un impacto en los gráficos de redes sociales, ya que tienen una relación de ley de potencia. Esto significa que ciertos nodos tienen más conexiones o un mayor impacto que otros, y al procesar estos gráficos, ciertas conexiones y nodos deben recibir más atención dada su importancia.
00:20:00 En esta sección, el orador analiza la importancia de la forma de un gráfico en la computación, específicamente cómo el tamaño y la localidad de un gráfico pueden afectar la eficiencia de los algoritmos de paralelismo. Factores como el paralelismo, la localidad y el trabajo adicional necesario se deben equilibrar cuidadosamente para lograr el mejor rendimiento para un algoritmo determinado, y se debe seleccionar el método correcto según el tipo de gráfico, el tipo de algoritmo y el hardware que se utilice. Se desarrolló un lenguaje específico de dominio para separar el algoritmo constante de los métodos de procesamiento para optimizar mejor estos factores.
00:25:00 En esta sección, el orador analiza cómo se pueden usar los lenguajes específicos de dominio (DSL) para escribir código en un nivel superior, haciéndolo más simple y elegante. Dan ejemplos de diferentes algoritmos y cómo los DSL proporcionan una forma sencilla de calcularlos. Además, el ponente explica cómo se puede optimizar la programación de los DSL para obtener la mejor velocidad posible, incluso permitiendo el procesamiento en paralelo. El código se puede variar según los cambios en el gráfico o la máquina, pero el algoritmo sigue siendo el mismo. El orador enfatiza la importancia de que los DSL brinden simplicidad en la programación y sean lo suficientemente potentes como para generar horarios optimizados.
00:30:00 En esta sección, el orador analiza otro lenguaje de dominio específico, Halide, que se enfoca en el procesamiento de imágenes con estructuras regulares densas. Halide ayuda a reducir la cantidad de programación requerida para lograr un rendimiento optimizado y aumenta la portabilidad del programa en diferentes máquinas. El orador proporciona un ejemplo de desenfoque de tres por tres para demostrar cómo funciona Halide. Halide tiene un patrón similar al lenguaje gráfico discutido anteriormente en términos de optimización del rendimiento a través de diferentes combinaciones de varias técnicas.
00:35:00 En esta sección, el orador analiza el uso de lenguajes específicos de dominio (DSL) y el ajuste automático para optimizar el rendimiento del código. Proporciona un ejemplo de un filtro de imagen que se ejecuta más rápido con un DSL llamado Halide, en comparación con un código C válido. Halide permite desacoplar el algoritmo del cronograma, lo que permite una optimización simple de la canalización de funciones puras que se ejecutan. Por último, el orador enfatiza la necesidad de un equilibrio entre localidad, paralelismo y trabajo redundante para lograr el mejor rendimiento de los recursos informáticos disponibles.
00:40:00 En esta sección, el orador analiza la importancia de la localidad en lo que respecta al procesamiento de imágenes. Al procesar una imagen grande, no es eficiente aplicar filtros que operen en toda la imagen a la vez porque no cabe en el caché. En cambio, el orador sugiere dividir la imagen en secciones más pequeñas y aplicar filtros a cada sección, centrándose en la localidad y el paralelismo. Esto se puede lograr mediante el uso de un marco de programación y la optimización del ancho de banda de cómputo y la granularidad del almacenamiento. También puede requerir algo de trabajo redundante para lograr una mejor localidad y paralelismo.
00:45:00 En esta sección, el orador analiza los lenguajes específicos de dominio y el ajuste automático, centrándose en el uso de Halide. Halide puede fusionar las funciones de la biblioteca, lo que es más rápido que llamar a las bibliotecas porque hay más localidad. El orador muestra cómo Halide puede optimizar los procesos computacionales, como el cálculo de filtros bilaterales y los algoritmos de segmentación. En un ejemplo, un algoritmo de segmentación escrito en MATLAB, que había llamado a bibliotecas optimizadas a mano, fue 70 veces más rápido cuando se escribió en Halide. Halide es una parte importante de Google, se integró en teléfonos Android y se usó en Google Glass.
00:50:00 En esta sección, el disertante analiza la efectividad del uso de Halide para el procesamiento inicial y cómo se está utilizando ampliamente en diferentes industrias. Halide cuenta con un aumento de velocidad del 4-5 % en comparación con las versiones anteriores, lo que es significativo para Google teniendo en cuenta la cantidad de videos descargados. Adobe también ha anunciado que todos los filtros de Photoshop están escritos en Halide. El procesador de imagen Snapdragon e Intel también están comenzando a usar Halide. El orador también analiza cómo Halide y Graph comparten similitudes en términos de poder automatizar la optimización, lo que facilita el trabajo del ingeniero de rendimiento. Sin embargo, cuando se trata de optimización algorítmica, es un cambio de nivel superior que requiere un conocimiento contextual específico, lo que dificulta su automatización. No obstante, herramientas como los idiomas programados brindan a los usuarios la opción de probar diferentes enfoques y lograr un mejor rendimiento.
00:55:00 En esta sección, el orador analiza la complejidad de los sistemas informáticos modernos y cómo no existe una forma correcta de optimizar el código. Enfatizan la importancia de probar diferentes enfoques y la importancia de los cachés, la localidad y el paralelismo. También analizan cómo las personas en varios dominios, como la biología y la física, pasan mucho tiempo optimizando el código en lugar de realizar investigaciones porque no pueden escribir programas lo suficientemente rápido debido a la complejidad del código. El orador sugiere que encontrar dominios donde las personas pasen la mayor parte de su tiempo pirateando y generando abstracción puede ser un área interesante para explorar para la investigación. En general, el espacio para operar para optimizar programas incluye paralelismo, localidad y trabajo redundante, y jugar en este espacio es crucial para los ingenieros de rendimiento.

01:00:00 En esta sección, el orador analiza los desafíos de la ingeniería de rendimiento, que implica encontrar los parámetros correctos para que un programa funcione de manera óptima. Explica que existen numerosos parámetros que se pueden ajustar, como la asignación de memoria y el tamaño del bloque, pero que puede ser difícil determinar los valores correctos para cada parámetro para cada programa. Sin embargo, el orador sugiere que el ajuste automático puede abordar este problema, buscando automáticamente en el gran espacio de parámetros para encontrar los valores óptimos. Explica que las soluciones basadas en heurísticas, que involucran reglas de codificación estrictas para ciertas situaciones, pueden funcionar la mayor parte del tiempo, pero no siempre son óptimas. El orador también señala que la construcción de modelos del sistema puede ser problemática ya que el modelo no tiene en cuenta todos los factores importantes, lo que puede conducir a resultados subóptimos.
01:05:00 En esta sección, el orador analiza los desafíos de encontrar soluciones óptimas frente a la tecnología cambiante o los requisitos en evolución. Señala que hay una variedad de "heurísticas" que los programadores usan para guiar sus soluciones, a menudo basadas en pautas o reglas generales que pueden no ser aplicables. Una opción es la búsqueda exhaustiva, pero esto puede no ser práctico dada la gran cantidad de permutaciones posibles. Para abordar esto, el orador recomienda el uso de autotuning como una forma de podar el espacio de búsqueda y encontrar soluciones óptimas más rápido. El ajuste automático implica definir un espacio de valores aceptables, elegir aleatoriamente un valor para probar y luego iterar en función de los resultados de rendimiento. OpenTuner es un ejemplo de un marco que utiliza un conjunto de técnicas, como escaladores de colinas y búsqueda aleatoria, para acelerar este proceso iterativo.
01:10:00 En esta sección, el orador analiza el concepto de ajuste automático y cómo se puede aplicar para generar programaciones para Try. Al comprender los gráficos y el ritmo involucrados, el ajuste automático se puede utilizar para generar un cronograma de manera más eficiente y efectiva que la búsqueda exhaustiva. Este método pudo producir horarios en menos de dos horas y, en algunos casos, incluso mejor que lo que originalmente se pensó que era el mejor horario posible.

OpenCL en el trading Comercio Cuantitativo Estudiamos ONNX para aplicarlo

MetaQuotes 2023.04.26 14:35 #299

Lección 19. Leiserchess Codewalk

Lección 19. Leiserchess Codewalk

En este video de YouTube titulado "19. Leiserchess Codewalk", Helen Xu explica las reglas de Lesierchess, un juego jugado por dos equipos con el objetivo de dispararle al rey del equipo contrario o que le disparen a su rey. El juego tiene dos tipos de movimientos, movimientos básicos y swat, y una regla de Ko que hace que un movimiento sea ilegal si deshace el movimiento más reciente del oponente. Xu se sumerge en varios aspectos del juego, incluido el método de control de tiempo de Fisher, la notación de Forsythe-Edwards, el probador automático de la nube y la organización de proyectos, evaluando y comparando bots usando clasificaciones Elo, generación de movimientos, evaluación estática y algoritmos de búsqueda como alfa-beta, variación de principio, poda de subárboles y tablas de transposición. También analiza la importancia de la infraestructura de prueba para optimizar el programa y el archivo eval.c, que contiene heurísticas que evalúan cada casilla del tablero según el tipo de pieza y su color.

El orador también profundiza en el aspecto de la cobertura láser del juego, explicando el complicado sistema de generar todos los movimientos posibles para una posición basada en el color del jugador usando una declaración de tiempo real. También explican la importancia de la corrección en el código y cómo probarlo, sugiriendo la conversión de la representación para garantizar la corrección antes de la optimización del rendimiento. El orador también analiza la gran flexibilidad que brinda la interfaz UCI de Leiserchess, que permite a los usuarios editar tablas y comandos a su gusto, y asegura a los espectadores que se limpiará el código inactivo y que se debe informar cualquier otro error para corregirlo.

00:00:00 En esta sección, Helen explica las reglas del juego Lesierchess y cómo jugarlo. El juego se juega en dos equipos, naranja y lavanda, y cada equipo tiene siete peones y un rey. El objetivo del juego es disparar al rey del equipo contrario o hacer que tu rey dispare. El juego tiene dos tipos de movimientos, movimientos básicos y swat. Además, el juego tiene una regla de Ko que hace que un movimiento sea ilegal si deshace el movimiento más reciente del oponente simplemente volviendo a donde estaba el equipo contrario. Se produce un empate si ha habido 50 movimientos de cada equipo sin que se haya eliminado un peón, se repite la misma posición o los dos equipos acuerdan el empate.
00:05:00 En esta sección, el orador explica el método de control de tiempo de Fisher utilizado en leiserchess. Cada jugador comienza con un presupuesto de tiempo inicial y un incremento de tiempo. En el ejemplo utilizado, cada jugador comienza con 60 segundos, y cuando finaliza su jugada, obtiene 0,5 segundos adicionales. Pero el límite de tiempo real puede ser cualquier cosa. Luego, el orador demuestra cómo jugar leiserchess al pedirle a la audiencia que sugiera movimientos para que Tangerine golpee al peón en F5 mientras evita los contraataques. Sin embargo, el orador advierte sobre las sutilezas del juego, como matar ingenuamente todas las piezas, ya que podría abrir al oponente.
00:10:00 En esta sección, Helen Xu analiza la notación de Forsythe-Edwards como una herramienta para representar una posición de ajedrez mediante una cadena, que es útil para fines de depuración, lo que permite volver fácilmente a una posición específica. También explica cómo leer registros de partidas de ajedrez, donde desglosa cada jugada y sus anotaciones correspondientes. Además, demuestra cómo usar el servidor de scrimmage para probar bots con otros equipos de la clase, así como también cómo desafiar a otros equipos y ver los partidos jugados.
00:15:00 En esta sección, Helen Xu habla sobre el probador automático de la nube y la organización del proyecto para Lesierchess. Mientras que el servidor de scrimmage solo permite un juego a la vez, Cloud autotester puede ejecutar múltiples juegos y binarios en un control de tiempo que se puede personalizar según las preferencias de cada usuario. La organización del proyecto en el repositorio incluye los directorios doc, auto tester, pgnstates, tests, player y webgui. El probador automático es un probador automático local de Java que se utiliza para probar los cambios localmente, mientras que en el directorio de pruebas, las configuraciones se pueden especificar para las pruebas automáticas. Helen Xu también presenta la interfaz de cofre universal (UCI), un protocolo de comunicación utilizado por Lesierchess para interactuar con el probador automático.
00:20:00 En esta sección, el orador explica cómo se medirán y compararán los bots mediante las clasificaciones Elo, que es un sistema de clasificación basado en el nivel de habilidad relativo en juegos de suma cero. La calificación Elo no se basa únicamente en el tiempo, sino también en los nodos por segundo buscados mediante la UCI. Luego, el orador profundiza en más detalles sobre el juego, como la generación de movimientos, la representación del tablero y la estructura utilizada para almacenar la posición. Además, la jugada se representa mediante 28 bits, que incluyen el tipo de pieza, la orientación, desde el cuadrado, el cuadrado intermedio y los dos cuadrados. La implantación de referencia genera todos los movimientos dependiendo de quién sea el turno iterando a través del tablero y generando todos los movimientos de esa pieza en particular. El orador menciona el uso de la función de depuración perft para garantizar que la generación de movimientos modificados devuelva los mismos movimientos desde cada posición.
00:25:00 En esta sección, el orador analiza cómo determinar si un movimiento es bueno a través de la evaluación estática, que genera una puntuación basada en una posición usando heurística. Las heurísticas incluyen las centradas en el rey, los peones y la distancia, y pueden ayudar a determinar si una posición es buena o no. El orador también habla sobre cómo los programas de juegos usan árboles de búsqueda para jugar y elegir el mejor movimiento en función de la evaluación. Para reducir la cantidad de nodos, el orador entra en detalles sobre la búsqueda de reposo y la búsqueda min-max, que pueden mejorar la cantidad de nodos evaluados y conducir a un mejor rendimiento.
00:30:00 En esta sección, el ponente habla del algoritmo llamado alfa beta, que se utiliza durante una búsqueda desde un nodo con una ventana alfa beta. Si el valor de la búsqueda cae por debajo de alfa, el movimiento no es lo suficientemente bueno y continúa buscando. Beta esencialmente significa que un lado está tratando de maximizar y el otro está tratando de minimizar. Por lo tanto, si el valor cae por encima de beta, generas un corte de beta, porque el oponente no te dejaría hacer ese movimiento, ya que sería demasiado bueno. Luego, el orador explica la búsqueda de variación principal, que supone que el primer movimiento es el mejor, y ejecuta la búsqueda de exploración, que también se llama búsqueda de ventana cero, en los movimientos restantes para verificar que son peores. Esta forma de búsqueda es una variación del algoritmo alfa-beta.
00:35:00 En esta sección, se discute el concepto de poda de subárboles en los algoritmos de búsqueda minimax. La idea detrás de la poda de subárboles es eliminar los subárboles que tienen puntajes más bajos que el mejor puntaje encontrado hasta el momento. Esto reduce el número de nodos evaluados y acelera el proceso de búsqueda. El oponente también busca la mejor jugada y trata de minimizar las puntuaciones del jugador. El equilibrio entre maximizar la puntuación del jugador y minimizar la puntuación del oponente es crucial, y el objetivo es encontrar un movimiento que sea bueno para el jugador y también algo que el oponente permita.
00:40:00 En esta sección, Helen Xu explica el concepto de poda de variaciones principales donde se supone que el subárbol más a la izquierda es el mejor camino y se toman salidas tempranas si la suposición es cierta. Si la suposición es falsa, se debe buscar en todo el subárbol. La búsqueda de exploración se utiliza para aplicar esto recursivamente a los subárboles inferiores, con pases iniciales para verificar las suposiciones. Este método mejora la poda y procesa la mayor parte del árbol del juego con cero búsquedas de ventana.
00:45:00 En esta sección, aprendemos sobre optimizaciones de búsqueda para el programa Leiserchess. Una de las optimizaciones más importantes es el uso de una tabla de transposición para almacenar posiciones encontradas anteriormente, lo que ahorra tiempo al evitar búsquedas innecesarias. Otras optimizaciones incluyen el uso de hashing de Zobrist para generar hashes únicos para cada posición, la tabla de movimientos asesinos para almacenar buenos movimientos para que no tengan que volver a calcularse y la poda de inutilidad para omitir movimientos de exploración que no aumentarían la puntuación alfa. También se recomienda la implementación de un mejor libro de aperturas para almacenar posiciones precalculadas al inicio del juego y ahorrar tiempo en la búsqueda.
00:50:00 En esta sección, el orador analiza algunas herramientas útiles para optimizar un programa de ajedrez, incluidos libros de apertura y bases de datos de juegos finales que pueden calcularse previamente. Es importante probar y tener una buena infraestructura de pruebas para poder innovar y avanzar sin problemas de depuración. El uso de tablas de transposición en la programación paralela hace que sea importante poder desactivarlas con fines de prueba, y se recomienda realizar búsquedas de profundidad fija durante la prueba. En general, tener una buena infraestructura de prueba es crucial para progresar y evitar problemas de depuración significativos.
00:55:00 En esta sección, el orador analiza el archivo eval.c en el proyecto Leiserchess y cómo puede parecer abrumador a primera vista debido a su tamaño y complejidad. Sin embargo, a medida que los usuarios se familiaricen con él, ganarán confianza en el manejo de una pieza de código de tamaño decente. El archivo eval.c contiene heurísticas como p entre, p central, k cara y k agresivo que evalúan cada casilla del tablero en función del tipo de pieza y su color. La heurística p between determina si un peón está entre ambos reyes, mientras que p central otorga una bonificación basada en qué tan cerca está el peón del centro del tablero. Las heurísticas k cara y k agresiva otorgan bonificaciones basadas en la orientación del rey y su distancia del oponente y los bordes del tablero.
01:00:00 En esta sección, el locutor explica la cobertura láser, que es un aspecto complicado del juego. La cobertura láser genera todos los movimientos posibles de una determinada posición en función del color del jugador. Luego proporciona una lista de movimientos, y el orador explica cómo este mapa realiza su función con una declaración de tiempo verdadero. La ruta del láser rebota en algunos peones mientras dibuja la ruta y aumenta la distancia para cada casilla. Después de generar el mapa, el proceso se repite y la distancia se divide por la distancia real desde el láser. Este complicado sistema optimiza las iteraciones requeridas en el método de evaluación para encontrar cada pieza en el tablero, lo que ralentiza el proceso, y el ponente agrega que representar el tablero de manera diferente y afirmar que ambas funciones de conversión dan el mismo resultado es una buena manera de hacer decisiones de optimización.
01:05:00 En esta sección del video, los oradores discuten la importancia de mantener la corrección en el código y cómo probarlo. Explican que la conversión de una representación a otra puede ralentizar el proceso, pero es necesario para garantizar la corrección antes de optimizar el rendimiento. Una forma de probar la corrección es hacer un seguimiento de los recuentos de nodos y asegurarse de que sigan siendo los mismos después de realizar cambios. También demuestran cómo ejecutar el código y muestran la interfaz UCI en Lesierchess.c, que le permite establecer valores para varias cosas sin tener que volver a compilar el binario cada vez. Por último, revisan una tabla de heurística y explican cómo especificar valores para el probador automático.
01:10:00 En esta sección, el ponente comenta la gran flexibilidad que proporciona el juego Leiserchess para editar tablas y comandos a través de la interfaz UCI. Esto permite a los usuarios acceder e implementar cualquier comando que deseen, incluidas nuevas heurísticas, y tener control sobre el análisis y la implementación. Aunque existe algún código inactivo, el profesor asegura a los espectadores que se limpiará y que se debe informar cualquier otro error para corregirlo. Por último, afirma que, si bien el proyecto puede no ser divertido cada minuto, en general brinda mucho placer.

Tutoriales de programación Python para el trading Estudiamos ONNX para aplicarlo

MetaQuotes 2023.04.26 14:36 #300

Lección 20. Paralelismo especulativo y Leiserchess

20. Paralelismo especulativo y Leiserchess

En este video de YouTube titulado "20. Paralelismo especulativo y Leiserchess", el instructor presenta el concepto de paralelismo especulativo, que consiste esencialmente en adivinar de manera preventiva que ciertas tareas se pueden realizar en paralelo y pueden resultar en un código más rápido. Sin embargo, el orador advierte que este código no es determinista y solo debe usarse cuando sea necesario, al tiempo que advierte contra su uso en los casos en que se podría usar un código de serie mejor. Una parte importante del video gira en torno a la discusión de búsquedas alfa-beta paralelas, lo que implica podar el árbol del juego para optimizar el tiempo de búsqueda, y también habla sobre diferentes estructuras de datos y heurísticas utilizadas en el proceso de evaluación de los algoritmos de búsqueda, particularmente para evitar ciclos e inactividad. buscar. El video también aborda los beneficios de la profundización iterativa y cómo conduce a un mejor orden de movimiento para las búsquedas, al tiempo que analiza el hash de Zobrist, una técnica de optimización utilizada en los algoritmos de búsqueda que implica un valor hash único para cada posición en el tablero de ajedrez con las mismas piezas.

Este video también analiza varias técnicas de optimización para motores de ajedrez, como tablas de transposición, reducciones de movimientos tardíos y el uso de bitboards para la generación de movimientos. El orador también habla sobre el tema del "paralelismo especulativo y Leiserchess", donde aconseja a los programadores que evalúen si un movimiento afecta la trayectoria del láser y que busquen la "cobertura del láser". El orador sugiere dejar las representaciones antiguas en el código y usar programas para probar los cambios. También desarrollaron una heurística para medir qué tan cerca está un láser del Rey en Leiserchess. Más sugerencias de optimización incluyen encontrar una mejor manera de evaluar la proximidad del oponente al láser del jugador y optimizar la clasificación de los movimientos. Finalmente, se analiza la importancia de refactorizar y probar correctamente el código.

00:00:00 En esta sección, el instructor presenta el concepto de paralelismo especulativo como una forma de optimizar el código y hacer que se ejecute más rápido. Esto implica adivinar que ciertas tareas se pueden realizar en paralelo, incluso si son inherentemente en serie, lo que puede resultar en un esfuerzo desperdiciado si la suposición resulta ser incorrecta. El instructor brinda un ejemplo de umbralización de una suma y muestra una optimización simple al salir antes si la suma parcial alguna vez supera un umbral, aunque esto introduce una bifurcación predecible que aún podría ralentizar el código.
00:05:00 En esta sección, el orador analiza cómo mitigar el problema de agregar demasiado al bucle interno cuando se opera en paralelo. Explican que la minería a cielo abierto se puede usar para reemplazar el ciclo de n iteraciones con un ciclo de n en cuatro iteraciones con un ciclo interno de cuatro iteraciones, al mismo tiempo que se verifica si se ha excedido el umbral cada cuarta iteración para minimizar el costo de el cheque Para paralelizar un bucle en cortocircuito, el hablante agrega un indicador de cancelación al código y lo usa recursivamente para verificar si la suma es mayor que un límite y no se ha abortado antes de establecer el indicador en verdadero. Al verificar la bandera antes de colocarla, evitan una carrera de determinación y evitan verdaderas carreras compartidas.
00:10:00 En esta sección, el video analiza el paralelismo especulativo, que es cuando un programa predice que necesitará realizar un trabajo paralelo y genera ese trabajo de forma preventiva. Este código no es determinista y solo debe usarse con fines de rendimiento cuando sea necesario. Es esencial restablecer el indicador de aborto y no generar trabajo especulativo a menos que haya pocas otras oportunidades para el paralelismo y una buena probabilidad de que sea necesario. El video advierte contra el uso de paralelismo especulativo en los casos en que se podría usar un mejor código de serie, ya que este enfoque a menudo conduce a más trabajo sin aceleración. Finalmente, se hace referencia a un teorema que establece que para el paralelismo, la probabilidad de que el trabajo sea innecesario debe ser menor que la cantidad de procesadores utilizados.
00:15:00 En esta sección, la discusión se centra en las búsquedas alfa-beta paralelas, lo que implica podar el árbol del juego para optimizar el tiempo de búsqueda. Burkhardt Manin y sus alumnos observaron que en un árbol mejor ordenado, el grado de cada nodo es 1 o máximo. Su idea era especular que el mejor movimiento se seleccionó después de que el primer niño no pudo generar un límite beta. Esto permite que los niños restantes se busquen en paralelo sin desperdiciar trabajo. La heurística en el código ayuda a garantizar que las cosas se hagan en el orden correcto, como usar el algoritmo de ponderación de hermanos jóvenes para seleccionar el mejor movimiento, incluso si es a una profundidad menor. El algoritmo también aborta los subcálculos cuando resultan innecesarios.
00:20:00 En esta sección del video, el orador analiza el mecanismo de trepar al árbol periódicamente para buscar ancestros que fueron abortados en la paralelización y evitar perder trabajo. Sugieren tener un parámetro de contador o vudú para determinar con qué frecuencia verificar porque arrancar el árbol tiene un costo. El ponente también habla de las estructuras de datos utilizadas en la búsqueda como la tabla de transposición que puede causar carreras en la paralelización. Sugieren replicarlo para cada trabajador o bloquearlo para evitar carreras de datos. Por último, el orador recomienda tener una forma de desactivar la especulación y otras partes no deterministas del código para depurar más fácilmente.
00:25:00 En esta sección, el orador habla sobre un programa que casi ganó el Campeonato Mundial de Ajedrez Informático en 1999. Sugirieron un cambio de reglas con el que todos estuvieron de acuerdo, pero luego perdieron ante la famosa computadora IBM Deep Blue. Se estaban ejecutando en una supercomputadora de 1824 nodos en Sandia National Labs, y su única pérdida fue ante Deep Blue. Decidieron dejar que hubiera una carrera en la tabla de transposición en su programa sin incluir bloqueos para acceder a la tabla porque ralentizaría el programa. Calcularon que las probabilidades de que una carrera afectara el valor que elegirían y eventualmente afectara el resultado del torneo eran bajas.
00:30:00 En esta sección del video, el orador analiza tres estructuras de datos que son importantes para la toma de decisiones en la IA del ajedrez. La primera es la heurística "asesina", que realiza un seguimiento de los mejores movimientos en una determinada profundidad de código y tiende a ser de naturaleza repetitiva. La segunda es la tabla de "mejor jugada", que ordena todas las jugadas de menor orden en función de los datos estadísticos. Ambas estructuras de datos se comparten y deben gestionarse correctamente al paralelizar el código. La estructura de datos final es el libro de aperturas, que calcula previamente los mejores movimientos al comienzo del juego. Sin embargo, el orador sugiere que hay frutos más bajos que el libro de aperturas y que, estadísticamente, la mayoría de los juegos no duran lo suficiente como para que un libro de aperturas sea beneficioso.
00:35:00 En esta sección, el orador analiza la estrategia de construir libros de apertura en Leiserchess, un juego en el que los equipos intentan crear los robots más fuertes para jugar al ajedrez. El orador señala que algunos equipos han tenido éxito al crear un fuerte libro de aperturas que les permite ganar a través de un comienzo fantástico. También sugieren que es más efectivo mantener libros de apertura separados para cada lado en lugar de usar uno para ambos. Además, el orador recomienda agregar una ligera aleatoriedad al código para evitar la previsibilidad, pero advierte que no es necesario optimizarlo durante la beta uno. Finalmente, sugieren la estrategia de profundización iterativa que consiste en realizar búsquedas a diferentes profundidades hasta que expire el control de tiempo. El orador señala que esta es una buena estrategia ya que la cantidad de trabajo con cada profundidad crece exponencialmente, pero la información importante se acumula durante las primeras profundidades.
00:40:00 En esta sección, el video profundiza en los beneficios de la profundización iterativa y cómo conduce a una mejor ordenación de movimientos para las búsquedas. Al pasar por una profundización iterativa, la tabla de transposición puede almacenar la mejor información de orden de movimiento para todas las posiciones intermedias, lo que hace que la poda sea más efectiva a mayor profundidad. Además, al realizar una profundización iterativa, también proporciona un buen mecanismo para el control del tiempo. El video también aborda la base de datos del juego y por qué es beneficioso crear una base de datos de finales, al tiempo que analiza cómo evitar el ciclo en una base de datos de finales almacenando la distancia hasta el mate en lugar de un simple valor booleano.
00:45:00 En esta sección, el orador discute diferentes heurísticas utilizadas en el proceso de evaluación de algoritmos de búsqueda, particularmente para evitar ciclos y búsquedas en reposo. El ponente menciona la importancia de mantener la distancia para ganar y evitar andar en bicicleta buscando una distancia para ganar que sea uno menos que la distancia actual. Otra heurística utilizada es la poda de movimiento, donde quedarse quieto no suele ser tan bueno como hacer un movimiento, y la poda sin movimiento, donde se aplica el movimiento nulo para simplificar la búsqueda cuando una posición es tan buena que incluso no hacer nada daría como resultado una victoria. . El orador también analiza Zoogs Wang en Chess y cómo se usan las extensiones de movimiento en la búsqueda de mentiras de Chess cuando solo hay un movimiento forzado.
00:50:00 En esta sección, el orador habla sobre el uso de una tabla de transposición en un algoritmo de búsqueda, que en realidad es un dag (gráfico acíclico dirigido) ya que se puede alcanzar la misma posición a través de movimientos transpuestos. La tabla de transposición almacena puntajes de calidad determinados por la profundidad buscada para establecer el valor de un movimiento para evitar buscar nuevamente la misma posición. Es fundamental no utilizar movimientos de muy baja calidad, ya que no permitirá una búsqueda completa y el valor almacenado puede ser menos preciso. Además, se utiliza un código especial para almacenar las posiciones de mate calculadas restando un número muy grande de la profundidad para llegar al mate. También se analiza el hash de Zobrist, una técnica de optimización utilizada en los algoritmos de búsqueda, que involucra un valor de hash único para cada posición en el tablero con las mismas piezas.
00:55:00 En esta sección, el profesor Leiserson explica el concepto de hashing de Zobrist, que se utiliza para actualizar eficientemente una función hash que representa la posición de diferentes piezas en un tablero de ajedrez. La función hash implica generar una tabla de números aleatorios correspondientes a diferentes combinaciones de tipo de pieza, fila, columna y orientación. La función hash usa operaciones XOR para calcular el hash tomando el XOR de los valores de todas las piezas y sus orientaciones. El hash de Zobrist explota la propiedad XOR para eliminar piezas de la función hash mediante la operación XOR del valor de la pieza que se elimina para obtener el hash de las piezas restantes. Esto permite una actualización económica y eficiente de la función hash con solo dos operaciones XOR para cualquier movimiento realizado.
01:00:00 En esta sección, el orador analiza varias técnicas de optimización para motores de ajedrez. Habla sobre la tabla de transposición, que almacena registros de la clave Zobrist, la puntuación, la calidad y el tipo de límite de un movimiento, y hace que los movimientos anteriores superen la edad. Además, menciona el concepto de reducciones de movimientos tardíos, donde los movimientos menos prometedores se buscan con menos profundidad para ahorrar tiempo. El orador también habla sobre la representación del tablero y cómo el uso de tableros de bits puede acelerar la generación de movimientos y otros conceptos de ajedrez mediante el uso de trucos de bits para realizar de manera eficiente operaciones como cambiar y contar bits.
01:05:00 En esta sección, el orador discute el tema del "paralelismo especulativo y Leiserchess". Él explica que una de las principales optimizaciones que se pueden hacer al tratar con un láser es evaluar si un movimiento afecta la trayectoria del láser o no. Además, el orador sugiere buscar la "cobertura láser", ya que es muy costosa. También aconseja a los programadores que dejen la representación anterior en el código e incluyan afirmaciones que digan que las cosas son equivalentes y que usen programas como Perfectiy para saber si han realizado algún cambio. Finalmente, analiza cómo se supone que funciona el programa en términos de acercar el láser al Rey y la importancia de la posición en el juego.
01:10:00 En esta sección, el orador analiza una nueva heurística que desarrollaron para medir qué tan cerca se está acercando un láser al rey de un oponente en Leiserchess. Evalúan cada movimiento calculando la distancia del láser al rey, contando uno por cada posición en la que se aleja y un valor extra si rebota en un oponente. Toman el número mínimo que pueden llegar a cada casilla y usan un multiplicador para evaluar qué tan bueno es estar cerca del rey. Lo suman todo y lo multiplican por un multiplicador constante mágico para representar el valor como una fracción de un peón. El número resultante oscila hasta alrededor de cuatro en promedio.
01:15:00 En esta sección, el orador analiza varias formas en las que se podría mejorar la eficiencia del motor de ajedrez. Una sugerencia es encontrar una mejor manera de evaluar la proximidad del oponente al láser del jugador, ya que el método actual es computacionalmente costoso. Otra área de optimización es clasificar los movimientos, lo que también puede ser costoso, especialmente si hay muchos movimientos para analizar. El orador sugiere encontrar una manera de optimizar la clasificación para que solo se clasifiquen los movimientos relevantes y se evite la clasificación innecesaria. El orador también menciona que cambiar las representaciones para el tablero puede ser un proceso doloroso, pero existen alternativas a la representación del tablero bit que pueden ser más eficientes.
01:20:00 En esta sección, el video analiza la importancia de refactorizar el código y probarlo adecuadamente para garantizar que los cambios se realicen correctamente sin romper el código. El orador sugiere refactorizar los accesos de la placa a una llamada de función antes de modificarla para que sea más fácil cambiar la representación de la placa sin una refactorización extensa. Las pruebas adecuadas también son esenciales para garantizar que los cambios sean correctos y no rompan el código, y es importante hacer que el código sea determinista para evitar la imprevisibilidad. El orador también menciona una próxima conferencia de John Bentley como una valiosa oportunidad para conocer a una celebridad y aprender más sobre el campo.

Python para el trading Tutoriales de programación Comercio Cuantitativo

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

Nuevo comentario