Aprendizado de máquina e redes neurais - página 29

Novo comentário
 

Aula 34. Matrizes de Distância, Problema de Procusto



34. Matrizes de Distância, Problema de Procusto

O palestrante discute o problema de Procrustes, que envolve encontrar a melhor transformação ortogonal que leva um conjunto de vetores o mais próximo possível de outro conjunto de vetores. Eles explicam diferentes expressões para calcular a norma de Frobenius de uma matriz de distância e sua conexão com o problema de Procrustes. O palestrante também introduz o conceito de traço de matrizes e encontra o Q correto no problema de Procusto. Além disso, eles abordam a questão de saber se o aprendizado profundo realmente funciona e apresentam a solução para um problema de matriz envolvendo encontrar a melhor matriz ortogonal, que envolve calcular o SVD do produto escalar de duas matrizes e usar as matrizes ortogonais do SVD.

  • 00:00:00 Nesta seção, o palestrante aborda uma questão levantada em uma discussão anterior sobre como encontrar pontos que satisfaçam uma determinada matriz de distância e como resolver a falha da desigualdade triangular. O palestrante explica que a matriz de produtos escalares que vem diretamente da matriz de distância é positiva semidefinida, mas se a desigualdade triangular falhar, a matriz de produtos escalares não sairá definida positiva. Esse problema não pode ser resolvido alterando as dimensões, pois a desigualdade triangular ainda é válida independentemente da dimensionalidade.

  • 00:05:00 Nesta seção, o palestrante fala sobre o Problema de Procusto, que envolve fazer algo se encaixar em outra coisa. O problema recebeu o nome de um mito grego sobre Procrustes que tinha uma cama de certo comprimento e ajustava o comprimento do visitante para caber na cama. O problema envolve encontrar uma maneira de encaixar dois conjuntos de dados, e o palestrante explica que se a desigualdade triangular for satisfeita pelos números da matriz de distância, a matriz que sai da equação é positiva semidefinida. Porém, se a desigualdade triangular for violada, a matriz não é semidefinida positiva e tem autovalores negativos, sendo impossível encontrar o ponto. O palestrante também sugere uma grande questão sobre se o aprendizado profundo realmente funciona, o que ele abordará mais tarde.

  • 00:10:00 Nesta seção, o problema de Procrustes é discutido, o que envolve encontrar a melhor transformação ortogonal que leva um conjunto de vetores o mais próximo possível de outro conjunto de vetores. Se os dois conjuntos de vetores fossem bases ortogonais, seria fácil incluir um no outro com uma matriz ortogonal Q, mas nem sempre é esse o caso. Portanto, o problema é minimizar todas as matrizes ortogonais Q na norma de Frobenius ao quadrado e tratar a matriz como um vetor longo. Uma maneira de fazer isso é olhar para uma transposta a, pegar seu traço e então encontrar a soma de todos os quadrados para obter a norma de Frobenius de uma matriz.

  • 00:15:00 Nesta seção, o palestrante discute diferentes expressões para calcular a norma de Frobenius de uma matriz de distância. Eles mostram que a norma de Frobenius ao quadrado pode ser expressa como a soma dos quadrados de todos os valores singulares, como o traço do produto da matriz e sua transposta, ou o traço do produto da transposta da matriz e a própria matriz . Eles então explicam como essas expressões se conectam umas às outras e mencionam que resolver esse problema requer vários fatos importantes, como o fato de que multiplicar cada coluna de uma matriz por Q não altera a norma de Frobenius e multiplicar a matriz por Q não muda. t afetam os valores singulares.

  • 00:20:00 Nesta seção, o palestrante discute propriedades da norma de Frobenius, incluindo o fato de que ela permanece inalterada quando multiplicada por um fator ortogonal ou quando multiplicada no outro lado pelo mesmo ou por um fator diferente. O palestrante também introduz o conceito de traço de matrizes, destacando o fato de que o traço não muda quando a ordem das matrizes é invertida. O palestrante então explica as etapas para obter o Q correto no problema de Procrustes.

  • 00:25:00 Nesta seção, o palestrante discute se o aprendizado profundo realmente funciona e sugere que é uma questão importante a ser abordada. Eles mencionam que, embora tenha havido muita publicidade e exagero em torno do aprendizado profundo e das redes neurais, não é automático que a estrutura da rede seja bem-sucedida, mesmo com várias camadas. O palestrante então apresenta a solução para um problema de matriz envolvendo encontrar a melhor matriz ortogonal, que envolve calcular o SVD do produto escalar de duas matrizes e usar as matrizes ortogonais do SVD.
 

Aula 35. Encontrando Clusters em Gráficos



35. Encontrando Clusters em Gráficos

Este vídeo discute o agrupamento em gráficos e como encontrar agrupamentos usando diferentes algoritmos, como K-means e agrupamento espectral. A matriz Laplaciana é usada no agrupamento espectral e pode fornecer informações sobre os agrupamentos no grafo por meio de seus autovetores. O autovetor de Fiedler, que é o autovetor para o menor autovalor positivo, é importante para agrupamento. O palestrante também enfatiza a importância dos autovetores serem ortogonais na identificação de diferentes clusters. Além disso, há uma breve prévia da próxima aula, que abordará a propagação reversa usando Julia em álgebra linear. Os alunos são incentivados a enviar seus projetos on-line ou fora do escritório do instrutor.

  • 00:00:00 Nesta seção, o palestrante discute o agrupamento em gráficos, que é o processo de subdividir um grande gráfico em grupos menores e mais gerenciáveis. O problema é encontrar dois clusters razoavelmente iguais em tamanho e, para isso, deve ser utilizado um algoritmo para determinar a posição dos pontos centrais X e Y. O objetivo é minimizar a soma das distâncias entre os pontos centrais e os nós no grafo, garantindo que o número de nós em cada cluster seja razoavelmente próximo. Existem vários algoritmos que podem ser usados para fazer isso, incluindo alguns que usam matrizes associadas ao grafo.

  • 00:05:00 Nesta seção, o palestrante discute o algoritmo de agrupamento K-means para dividir um conjunto de pontos, alguns rotulados como A e outros rotulados como B, em clusters ou grupos. O algoritmo começa identificando os centróides, que são os pontos médios dos grupos A e B, e depois tenta formar os melhores clusters com base nesses centróides. Esse processo é repetido até que o algoritmo convirja nos melhores clusters possíveis para os dados. O palestrante também introduz o conceito de centroide, que é o ponto que minimiza a soma das distâncias entre todos os pontos do grupo e o centroide.

  • 00:10:00 Nesta seção, o instrutor discute dois métodos para resolver o problema de localização de clusters em gráficos. O primeiro método é chamado K-means, que envolve encontrar o centróide do cluster mais próximo para cada ponto, reatribuir pontos aos seus respectivos clusters e repetir o processo até a convergência. O segundo método é chamado agrupamento espectral e envolve o uso de autovalores de uma matriz para agrupar pontos semelhantes. O termo "espectral" refere-se aos autovalores da matriz e ao teorema espectral na álgebra linear. O instrutor enfatiza que o teorema espectral se aplica a matrizes simétricas e afirma que os autovalores são reais e os autovetores são ortogonais.

  • 00:15:00 Nesta seção, o palestrante discute a matriz Laplaciana de grafos, que é a conexão chave entre a álgebra linear e a teoria dos grafos. Eles descrevem essa matriz como uma matriz semidefinida positiva simétrica, e há quatro matrizes associadas a qualquer gráfico: a matriz de incidência, a matriz de grau, a matriz de adjacência e a matriz Laplaciana. O palestrante executa um exemplo usando um gráfico simples para explicar cada uma dessas matrizes. A matriz Laplaciana é usada em agrupamento espectral e pode ter autovetores ortogonais que acompanham uma multiplicidade de autovalores, o que é conhecido como teorema espectral.

  • 00:20:00 Nesta seção, o palestrante explica o conceito de clustering de grafos encontrando clusters em um determinado grafo usando a matriz Laplaciana. A matriz Laplaciana é obtida subtraindo-se a matriz de incidência da matriz de graus. A matriz resultante é positiva semidefinida e seus autovetores fornecem informações sobre os clusters no grafo. O primeiro autovalor é sempre zero e o próximo autovalor é importante para clustering. O palestrante enfatiza a importância do vetor de Fiedler, o autovetor para o menor autovalor positivo, e explica sua importância no agrupamento de grafos.

  • 00:25:00 Nesta seção, o palestrante explica por que a matriz Laplaciana é nomeada assim ao encontrar clusters em um grafo. A matriz Laplaciana tem diagonal de grau 4 e permite encontrar clusters através de seus autovetores. Especificamente, o autovetor de Fiedler pode determinar os componentes positivos e negativos particionando o grafo em dois clusters. Essa abordagem fornece um método para decidir quais nós pertencem a qual cluster usando o grafo laplaciano.

  • 00:30:00 Nesta seção, o palestrante discute o agrupamento em gráficos e como encontrar agrupamentos usando diferentes algoritmos, como k-means e agrupamento espectral. Ele explica que autovetores de uma matriz simétrica são ortogonais, o que significa que somam zero, o que pode ser usado para identificar diferentes clusters. Ele também menciona que existem outros algoritmos propostos para o mesmo problema e dá uma breve prévia da próxima aula que cobrirá a propagação reversa usando Julia em álgebra linear. O palestrante incentiva os alunos a enviarem seus projetos online ou fora de seu escritório.
 

Aula 36: Alan Edelman e Julia Language



Aula 36: Alan Edelman e Julia Language

Neste vídeo, Alan Edelman discute o poder das linguagens de programação para aprendizado de máquina e sua importância na matemática. Ele destaca o desenvolvimento recente da linguagem Julia, reconhecida pelo Google, por seus méritos técnicos e usabilidade em aprendizado de máquina. Edelman explica como funciona a diferenciação automática em Julia e dá um exemplo de como calcular a raiz quadrada de x sem usar diferenças numéricas finitas por meio do algoritmo babilônico. Ele também discute o uso de tipos em Julia para computação eficiente e simplificação do processo de retropropagação com matrizes de bloco. No geral, Edelman enfatiza a importância da álgebra linear para cálculos matemáticos e seu papel na compreensão de fenômenos complexos.

  • 00:00:00 Nesta seção, Alan Edelman discute uma demonstração do professor Strang sobre classificação de linha igual a classificação de coluna e como esse conceito se aplica à matriz zero. Em seguida, ele fala sobre desenvolvimentos recentes em Julia, uma linguagem de programação que vem ganhando força no aprendizado de máquina, e como o Google reconheceu seu poder nesse campo. O Google publicou recentemente uma postagem no blog afirmando que existem apenas duas linguagens poderosas o suficiente para aprendizado de máquina, e Julia é uma delas. Edelman fornece exemplos para ilustrar esse ponto e incentiva os alunos a conferir a postagem do blog para obter mais informações.

  • 00:05:00 Nesta seção, Alan Edelman discute a importância das linguagens de programação no sentido matemático e sua capacidade de fazer mais do que apenas implementar algoritmos. Ele explica que Julia, Swift, C++ e Rust são as quatro linguagens de programação consideradas apropriadas para aprendizado de máquina com base em seus méritos técnicos e usabilidade. Edelman enfatiza a importância da álgebra linear como base para todos os cursos de engenharia e seu lamentável atraso na história. Ele então investiga a diferenciação automática e como ela se relaciona com o cálculo, seu ceticismo inicial em relação a ela e os detalhes técnicos que ele explorou em seu caderno sobre diferenciação automática de modo direto.

  • 00:10:00 Nesta seção, Alan Edelman discute seus pensamentos iniciais sobre diferenciação automática e como ele pensou que era como cálculo que aprendeu na escola, mas com um computador. No entanto, ele logo percebeu que havia um terceiro método que não era nem diferenças finitas nem a regra da cadeia, que o fascinava. Em seguida, ele compartilha um exemplo de como calculou a raiz quadrada de x usando o algoritmo babilônico em Julia e como conseguiu obter a derivada da raiz quadrada sem digitar explicitamente a fórmula da derivada, graças ao recurso de diferenciação automática de Julia.

  • 00:15:00 Nesta seção, o palestrante descreve o uso do código Julia para calcular a raiz quadrada de um número sem usar cálculos de diferenças finitas. O código cria um tipo de variável chamada "número duplo", que é um par de floats representando uma função numérica e sua derivada. O alto-falante então sobrecarrega as operações de adição e divisão para implementar a regra do quociente, permitindo o cálculo da raiz quadrada usando o algoritmo babilônico. O código funciona sem o uso de diferenças numéricas finitas, e o palestrante observa que Julia permite a reutilização de código existente em novos contextos para realizar "mágica".

  • 00:20:00 Nesta seção, Alan Edelman explica como a linguagem de programação Julia pode calcular eficientemente a derivada usando o algoritmo babilônico em um número dual no código assembler. Ele demonstra como o mesmo código executado no pacote de computação simbólica do Python fornece computação simbólica com grandes coeficientes, o que é muito ineficiente. Ele então revela o SVD, outro algoritmo que o convenceu de como funciona o algoritmo babilônico. Tomando a derivada de cada linha do código, o algoritmo pode convergir para a raiz quadrada e a derivada das raízes quadradas. A derivada resultante não é simbólica ou numérica, mas usa a regra do quociente e a regra da adição em cada etapa para obter a resposta.

  • 00:25:00 Nesta seção, Alan Edelman, o criador da linguagem Julia, discute como funciona a diferenciação automática na linguagem. Em vez de derivar manualmente cada linha, Edelman sugere que o software pode fazer isso automaticamente, deixando o compilador JIT lidar com isso. Isso elimina a necessidade de escrever um tradutor ou caligrafia, tornando a codificação muito mais simplificada. Edelman observa que o aprendizado de máquina depende muito de problemas de otimização, que tratam de derivações, tornando a diferenciação automática um componente essencial do processo. Por fim, ele explica como o uso de tipos pode simplificar a criação de matrizes estruturadas para armazenar dados.

  • 00:30:00 Nesta seção, Alan Edelman discute o uso de tipos em Julia para armazenar com eficiência apenas o que é necessário ao realizar cálculos, o que o diferencia de linguagens como Python e MATLAB que têm mais sobrecarga. Ele então aborda brevemente a ideia de diferenciação de modo imerso em redes neurais, começando com um exemplo escalar e generalizando para matrizes e vetores. Ele escreve a álgebra linear envolvida nesse processo, mas fica sem tempo antes de poder explicá-la completamente.

  • 00:35:00 Nesta seção, Edelman explica como usar matrizes de bloco em Julia para executar retropropagação sem ter que calcular manualmente as derivadas. Ele mostra como o uso de uma matriz diagonal e de uma matriz triangular inferior pode simplificar o processo de retropropagação e fazer uso das funções internas de Julia. Usando álgebra linear, ele demonstra como uma barra invertida pode resolver a matriz triangular inferior, tornando a tarefa de calcular derivadas muito mais fácil. Edelman enfatiza que a álgebra linear é essencial para muitos cálculos matemáticos e é o segredo para entender muitos fenômenos complexos.
 

MIT 6.172 Engenharia de desempenho de sistemas de software, outono de 2018 - 1. Introdução e multiplicação de matrizes



1. Introdução e Multiplicação de Matrizes

Neste vídeo do YouTube intitulado "1. Introdução e multiplicação de matrizes", o palestrante discute a importância da engenharia de desempenho e como ela evoluiu ao longo do tempo. Usando o exemplo da multiplicação de matrizes, o palestrante mostra como as técnicas de codificação e as especificações da máquina podem ter um grande impacto no desempenho. A discussão abrange tópicos como ordem de loop, uso de cache e programação paralela. O palestrante também explora maneiras de otimizar o código para diferentes processadores e cálculos aritméticos. No geral, o vídeo fornece informações valiosas sobre o mundo da engenharia de desempenho e suas aplicações práticas nos sistemas de computação modernos.

  • 00:00:00 Nesta seção, o palestrante discute a importância da engenharia de desempenho e por que ela é estudada. O desempenho nem sempre é a principal prioridade quando se trata de desenvolvimento de software. No entanto, é a moeda da computação e é usada para comprar outras propriedades desejadas, como facilidade de programação, segurança e correção. A degradação do desempenho pode causar software inutilizável, e a principal reclamação das pessoas sobre os sistemas de computação é que eles são muito lentos. Portanto, embora o desempenho possa não ter valor intrínseco, ele contribui para as coisas com as quais os desenvolvedores se importam.

  • 00:05:00 Nesta seção, o palestrante discute a história da engenharia de desempenho na computação e a mudança desde os primeiros dias de intensa engenharia de desempenho devido aos recursos limitados da máquina, até a era da Lei de Moore, onde as densidades dos chips dobravam a cada dois anos e aguardavam para o hardware recuperar o atraso foi mais benéfico do que otimizar o software. No entanto, o palestrante observa que o dimensionamento de Dennard, que permitiu que as velocidades de clock aumentassem ao reduzir a potência, chegou ao fim em 2004 e, portanto, a necessidade de engenharia de desempenho é mais importante do que nunca. O palestrante inclui citações dos cientistas da computação Donald Knuth, Bill Wolfe e Michael Jackson sobre a importância do código legível e alertando contra a otimização prematura.

  • 00:10:00 Nesta seção, o palestrante discute os limites das velocidades de clock que foram atingidos no início dos anos 2000 devido à densidade de energia, resultando no desenvolvimento de processadores multi-core para dimensionar o desempenho. No entanto, isso significava que o desempenho não era mais gratuito e exigia programação paralela, o que não era algo que a indústria havia feito antes. A partir daí, o software teve que se adaptar às novas configurações de hardware para ser eficaz e, como resultado, houve um foco maior no desempenho nos trabalhos de desenvolvimento de software.

  • 00:15:00 Nesta seção, o palestrante começa explicando a importância prática e teórica de aprender a escrever software que usa hardware moderno de forma eficiente. Eles então fornecem um exemplo de engenharia de desempenho usando o problema bem estudado da multiplicação de matrizes, discutindo a máquina que eles usarão, incluindo suas especificações e recursos, como processamento paralelo, tamanho do cache e capacidade de memória, e concluindo com uma explicação de o código básico para Python para multiplicação de matrizes. O palestrante enfatiza o poder da máquina e o potencial para projetos divertidos que utilizam seus recursos.

  • 00:20:00 Nesta seção, o palestrante discute o desempenho de Python, Java e C++ no contexto da multiplicação de matrizes. A palestra demonstra que Python é muito lento para grandes multiplicações de matrizes, com um tempo de execução de aproximadamente 21.000 segundos, Java é mais rápido e produz quase nove vezes mais velocidade do que Python, e C++ é o mais rápido com um tempo de execução de aproximadamente 1.100 segundos , que é duas vezes mais rápido que Java e 18 vezes mais rápido que Python.

  • 00:25:00 Nesta seção, o palestrante discute as diferenças de desempenho entre linguagens interpretadas como Python, linguagens compiladas como C e linguagens como Java que são compiladas para bytecode e depois interpretadas. Interpretadores como Python são versáteis, mas lentos, enquanto compiladores como C aproveitam as vantagens do hardware e das instruções de máquina para otimizar o desempenho. Os compiladores JIT, como os usados em Java, recuperam parte do desempenho compilando apenas os trechos de código executados com mais frequência. O palestrante observa que o modelo de desempenho do Python é difícil de entender, e é por isso que eles usarão C para comparações de desempenho no curso. No entanto, haverá uma palestra convidada onde eles discutirão engenharia de desempenho em linguagens gerenciadas como Python.

  • 00:30:00 Nesta seção, é discutida a importância da ordem dos loops para o desempenho na multiplicação de matrizes. A ordem dos loops afeta a localidade do cache, que afeta o tempo de execução. As matrizes são dispostas na memória em ordem de linha principal em C e em ordem de coluna principal em Fortran. O padrão de acesso para a ordem ijk tem boa localidade espacial para C, mas localidade espacial ruim para B. A ferramenta "cachegrind" é útil para determinar as taxas de falta de código, e mudanças simples, como ajustar sinalizadores de compilador, também podem melhorar o desempenho.

  • 00:35:00 Nesta seção, o palestrante discute como otimizar o código para obter melhor desempenho de uma máquina. É importante escolher um bom sinalizador de otimização, como -O2 ou -O3, mas às vezes um sinalizador de otimização inferior pode realmente otimizar melhor, dependendo do código. Além disso, os processadores multi-core podem ser utilizados com loops paralelos usando a infraestrutura de seda, resultando em um aumento de velocidade de quase 18x em 18 núcleos. O palestrante enfatiza que a paralelização de loops externos é mais eficaz do que a paralelização de loops internos, o que pode realmente tornar o programa mais lento. No entanto, ainda existem fontes de oportunidade para otimização, como erros de cache e não uso eficaz de instruções vetorizadas.

  • 00:40:00 Nesta seção, o palestrante discute como gerenciar erros de cache melhor reestruturando a computação para reutilizar os dados no cache o máximo possível. Usando um esquema de ladrilhos, as matrizes são quebradas em submatrizes menores e multiplicadas em blocos para reduzir o número de acessos à memória necessários. O palestrante explica que um parâmetro de ajuste é necessário para determinar o tamanho das submatrizes e sugere que a experimentação é a melhor maneira de encontrar o valor ideal. Por meio dessa abordagem, o palestrante demonstra que é possível reduzir significativamente o número de acessos à memória necessários para computar o mesmo tamanho de espaço ocupado, tornando a computação mais eficiente.

  • 00:45:00 Nesta seção, o palestrante discute os benefícios do uso de bloqueio ou ladrilhos ao realizar a multiplicação de matrizes, como uso aprimorado de cache e tempo de execução mais rápido. Eles explicam os diferentes níveis de caches que os chips possuem e como os programadores podem usar parâmetros de ajuste para otimizar seu código para cada nível de cache. No entanto, o processo de ajuste se torna mais complexo a cada nível de cache e o código pode se tornar difícil de ler e entender. O palestrante sugere uma abordagem de dividir e conquistar que usa programação paralela para resolver recursivamente subproblemas menores. Embora esse método melhore o uso do cache, a sobrecarga das chamadas de função retarda a computação, destacando a necessidade de uma engenharia de desempenho inteligente.

  • 00:50:00 Nesta seção, o palestrante discute como otimizar a multiplicação de matrizes usando a técnica de dividir e conquistar e ajustar o limite para usar o algoritmo. Um caso base é definido para quando o limite está abaixo de um determinado número e o algoritmo usa multiplicação de matriz comum. O melhor valor para o caso base foi 32, resultando em um tempo de execução de 1,3 segundos e 12% de desempenho máximo. Além disso, o palestrante apresenta o conceito de vetorização usando o hardware vetorial, que processa dados em uma única instrução, formato de dados múltiplos. O palestrante descreve diferentes maneiras de otimizar a vetorização, incluindo o uso de relatórios de vetorização, sinalizadores para arquiteturas específicas e o sinalizador matemático rápido, que permite ao compilador reordenar associações. O uso de matemática rápida e nativa da arquitetura resulta no dobro do desempenho ao usar qualquer vetorizador de compilador.

  • 00:55:00 Nesta seção do vídeo, o palestrante discute os vários tamanhos de bits usados para cálculos aritméticos, sendo 64 bits o mais comum para cálculos de álgebra linear. Eles também mencionam que a aritmética de menor precisão pode ser usada para aplicativos de IA para melhorar o desempenho. O palestrante continua falando sobre o uso de instruções vetoriais e os intrínsecos AVX, que fornecem até 41% de desempenho máximo e um aumento de velocidade de cerca de 50.000. Eles advertem que melhorias de desempenho semelhantes às alcançadas na multiplicação de matrizes podem não ser vistas em outras áreas, mas este curso ensinará aos alunos como obter melhorias substanciais de desempenho por conta própria. Além disso, o curso se concentrará na computação multi-core em vez de GPUs ou outras áreas.
 

Aula 2. Regras da Bentley para otimizar o trabalho



2. Regras da Bentley para otimizar o trabalho

Este vídeo do YouTube discute várias técnicas de otimização para programas de computador. As regras da Bentley para otimizar o trabalho são apresentadas e as otimizações são agrupadas em estruturas de dados, loops, lógica e funções. Diferentes técnicas como valores de codificação, aumento da estrutura de dados, pré-computação, cache e utilização de matrizes esparsas são discutidas. O palestrante também aborda os benefícios de usar uma representação de matriz esparsa para gráficos, otimização lógica e otimização de detecção de colisão em programas gráficos. A implementação dessas técnicas de otimização auxilia na redução do tempo de execução dos programas, tornando-os mais eficientes.

A segunda parte do vídeo cobre várias categorias de técnicas de otimização, incluindo loop hoisting, uso de sentinelas em loops, desenrolamento e fusão de loop e função inlining. O palestrante desaconselha a otimização prematura e enfatiza a importância de manter a correção e usar testes de regressão. O vídeo também descreve as Regras da Bentley para otimizar o trabalho, um guia de seis etapas para aumentar a produtividade e atingir metas de maneira eficiente. Essas regras incluem estabelecer metas claras, dividir tarefas, planejar e organizar, priorizar tarefas, minimizar distrações e revisar e ajustar regularmente a abordagem de cada um.

  • 00:00:00 Nesta seção, o palestrante apresenta o conceito de otimização de trabalho em programas de computador e explica como reduzir o trabalho de um programa pode melhorar seu desempenho. Ele também fala sobre as regras da Bentley para otimizar o trabalho, em homenagem a John Lewis Bentley, que escreveu um livro sobre a criação de programas eficientes. As otimizações são agrupadas em quatro categorias: estruturas de dados, loops, lógica e funções, e o palestrante planeja abordar todas as 22 regras em uma série de miniaulas ao longo do curso. Embora a redução do trabalho de um programa seja uma boa heurística para melhorar seu tempo de execução, a natureza complexa do hardware do computador significa que nem sempre se traduz em uma redução no tempo de execução; portanto, o palestrante também abordará otimizações específicas da arquitetura posteriormente no curso.

  • 00:05:00 Nesta seção do vídeo, o palestrante discute o conceito de empacotar e codificar estruturas de dados para armazenar mais de um valor de dados em uma palavra de máquina e converter valores de dados em uma representação que requer menos bits. Ao reduzir o número de coisas a serem movimentadas na memória, torna-se uma boa heurística para diminuir o tempo de execução de um programa. O alto-falante fornece um exemplo de codificação de datas para armazená-las usando menos bits para facilitar a busca do mês, ano ou dia de uma data específica. O palestrante sugere o uso de facilidades de campos de bits em C para armazenar os dados estruturados, tornando-os mais acessíveis. Essa representação requer um pouco mais de bits, mas é muito mais eficiente para acessar valores de dados específicos dentro da estrutura.

  • 00:10:00 Nesta seção, o vídeo discute três técnicas de otimização. A primeira técnica é decidir se os valores devem ser codificados como inteiros sequenciais ou desempacotados para um acesso mais rápido. A segunda técnica é o aumento da estrutura de dados, onde adicionar informações a uma estrutura de dados pode otimizar operações comuns. Um exemplo é adicionar um ponteiro de cauda a uma lista vinculada individualmente para tornar a anexação de duas listas mais eficiente. A terceira técnica é a pré-computação, que consiste em realizar cálculos com antecedência para evitar fazer os cálculos em momentos de missão crítica. Um exemplo é usar o triângulo de Pascal para pré-calcular coeficientes binomiais para acelerar o programa que os utiliza.

  • 00:15:00 Nesta seção, o palestrante discute como pré-calcular o triângulo de Pascal usando uma fórmula recursiva e código C. Eles explicam que a fórmula recursiva envolve chamar a função select e como pré-calcular a tabela em tempo de execução usando um loop. Além disso, eles discutem como inicializar a tabela em tempo de compilação colocando os valores da tabela no código-fonte, o que economiza tempo durante a execução do programa. Finalmente, fornecem uma tabela de exemplo de coeficientes binomiais até 10 que podem ser acessados durante a execução do programa.

  • 00:20:00 Nesta seção, o palestrante apresenta o conceito de metaprogramação como uma forma de evitar a digitação manual de grandes tabelas de valores constantes em um programa. Ao escrever um programa que gera o código necessário, a tediosa tarefa pode ser realizada automaticamente. O palestrante fornece um trecho de código Python como exemplo. O tópico de cache também é introduzido, como uma técnica para evitar a repetição de cálculos dispendiosos, armazenando os resultados acessados recentemente em um cache. O exemplo dado é o cálculo da hipotenusa de um triângulo retângulo usando o operador de raiz quadrada, onde o cache pré-armazena as hipotenusas anteriores, juntamente com os valores de a e b. A função de hipotenusa primeiro verifica se os valores de entrada correspondem aos do cache e, em caso afirmativo, retorna o valor armazenado em cache sem precisar recalcular a raiz quadrada.

  • 00:25:00 Nesta seção, o palestrante discute o conceito de cache para otimizar o trabalho em um programa. Ao armazenar valores comumente calculados em um cache, os programas podem economizar tempo por não terem que calcular repetidamente os mesmos valores. Embora o hardware também faça cache, o software também pode fazer isso, com um cache de tamanho 1.000 armazenando os 1.000 valores calculados mais recentemente sendo um exemplo. A otimização pode acelerar um programa em cerca de 30% se os mesmos valores forem calculados repetidamente. O palestrante então apresenta a ideia de explorar a dispersão em uma entrada para evitar a computação em elementos zero dessa entrada, economizando tempo de computação. Eles demonstram isso com um exemplo de multiplicação de vetores de matrizes e introduzem a estrutura de dados Compact Sparse Row (CSR) que pode acelerar a multiplicação de matrizes.

  • 00:30:00 Nesta seção, o palestrante discute como otimizar o armazenamento e a eficiência computacional de matrizes esparsas usando o formato Compressed Sparse Row (CSR). O formato CSR armazena os elementos diferentes de zero de uma matriz em três matrizes: a matriz de valores, a matriz de colunas e a matriz de linhas. O palestrante explica como calcular o comprimento de uma linha e como realizar a multiplicação matriz-vetor usando o formato CSR. O formato CSR pode ser mais eficiente em termos de espaço do que a representação de matriz densa se o número de elementos diferentes de zero for significativamente menor que N^2. No entanto, para matrizes relativamente densas, a representação da matriz densa pode ocupar menos espaço. O palestrante fornece um exemplo de código para realizar a multiplicação matriz-vetor usando o formato CSR.

  • 00:35:00 Nesta seção, o instrutor discute os benefícios de usar uma matriz esparsa para representar um gráfico e como ela pode ser utilizada para executar algoritmos de gráficos clássicos, como pesquisa em largura e PageRank com mais eficiência. A representação gráfica esparsa consiste em duas matrizes: deslocamentos e arestas, onde os graus de cada vértice podem ser obtidos tomando a diferença entre deslocamentos consecutivos. O peso das arestas também pode ser armazenado em uma matriz separada ou intercalado com as arestas para melhorar a localização do cache. A seção termina com uma breve introdução às otimizações lógicas, especificamente desdobramento e propagação constantes, que avaliam expressões constantes durante a compilação para reduzir o tempo de execução.

  • 00:40:00 Nesta seção do vídeo, o palestrante discute diferentes técnicas de otimização para código, incluindo desdobramento e propagação constantes, eliminação de subexpressões comuns e exploração de identidades algébricas. Ao definir constantes em tempo de compilação, o compilador pode avaliá-las e economizar tempo durante a execução. A eliminação de subexpressão comum permite evitar o cálculo da mesma expressão várias vezes, armazenando o resultado para uso futuro. Explorar identidades algébricas envolve substituir expressões mais caras por alternativas mais baratas. O palestrante enfatiza que, embora o compilador geralmente seja bom em implementar essas otimizações, ainda é importante conhecê-las para situações em que o compilador não o faz automaticamente.

  • 00:45:00 Nesta seção do vídeo, o palestrante discute duas técnicas de otimização. A primeira é reduzir o uso do operador de raiz quadrada, que é computacionalmente caro, usando identidades algébricas para evitar raízes quadradas. A segunda técnica de otimização é o curto-circuito, que envolve a interrupção de uma série de testes assim que o resultado é conhecido, no caso em que um array contém inteiros não negativos e a soma dos valores no array precisa ser verificada em relação a um limite. A otimização pode eliminar a necessidade de olhar para todos os elementos na matriz e pode acelerar a execução do programa, mas deve ser usada criteriosamente com base na frequência de quando o teste pode ser curto-circuitado.

  • 00:50:00 Nesta seção, o vídeo discute o conceito de operadores lógicos de curto-circuito e sua utilidade na otimização do código. O e comercial duplo e a barra vertical dupla são operadores lógicos de curto-circuito que podem economizar tempo e recursos avaliando apenas um lado do argumento. Além disso, o vídeo sugere a solicitação de testes com base na frequência de sucesso e no custo de execução. Essa abordagem pode aproveitar o curto-circuito para pular testes caros se os menos caros já falharem. Por fim, o vídeo apresenta a ideia de criar um caminho rápido usando verificações para sair de um programa antecipadamente se um resultado já for conhecido. Um exemplo disso é verificar se as caixas delimitadoras de duas bolas se cruzam antes de verificar outras condições de colisão.

  • 00:55:00 Nesta seção, a Bentley discute maneiras de otimizar testes para detecção de colisão em programas gráficos. Ele sugere um teste de caminho rápido para determinar se as caixas delimitadoras se cruzam antes de realizar o teste mais caro para colisão. Este teste consiste em verificar o valor absoluto da diferença em cada coordenada e verificar se é maior que a soma dos dois raios. A Bentley também observa que a combinação de testes por meio de uma única instrução switch ou mesmo pesquisas de tabela pode melhorar muito o desempenho. No geral, essas otimizações podem ser benéficas para muitos aplicativos e programas gráficos.

  • 01:00:00 Nesta seção, o vídeo aborda a terceira categoria de otimizações, que está relacionada a loops. A primeira otimização de loop discutida é o hoisting, que envolve evitar a recomputação do código invariante do loop a cada vez através do corpo de um loop. Calcular uma expressão uma vez e armazená-la em uma variável, em vez de recalculá-la a cada iteração, pode economizar tempo de execução. A segunda otimização de loop é o uso de sentinelas, valores fictícios especiais colocados em estruturas de dados para simplificar a manipulação de condições de contorno e a lógica de manipulação de testes de saída de loop. Modificando o programa para usar duas entradas adicionais na matriz, um sentinela pode ser usado para realizar apenas uma verificação em cada iteração do loop.

  • 01:05:00 Nesta seção, o palestrante discute duas técnicas para otimizar o código: condições de contorno e desenrolamento de loop. Para condições de contorno, ele mostra como modificar um loop para lidar eficientemente com o caso especial quando todos os elementos da matriz de entrada são zero. Ao adicionar um elemento fictício ao final da matriz e verificar se há estouro, o código pode detectar quando deve parar. Para o desenrolamento do loop, ele explica dois tipos: completo e parcial. Enquanto o desenrolamento de loop completo é raro devido a tamanhos de loop maiores, o desenrolamento de loop parcial reduz o número de iterações de um loop combinando vários em um, o que pode melhorar o desempenho reduzindo o número de instruções de fluxo de controle executadas.

  • 01:10:00 Nesta seção, o instrutor discute as otimizações de desenrolamento e fusão de loop. O desenrolar do loop envolve a combinação de várias iterações de um loop em uma única iteração, reduzindo assim a sobrecarga do controle do loop e permitindo mais otimizações do compilador. No entanto, desenrolar demais pode afetar negativamente o desempenho ao poluir o cache de instruções. A fusão de loop, por outro lado, combina vários loops no mesmo intervalo de índice em um único loop, reduzindo a sobrecarga de controle de loop e melhorando a localização do cache. O instrutor também discute a eliminação de iterações desperdiçadas modificando os limites do loop para evitar a execução de iterações de loop em corpos de loop vazios.

  • 01:15:00 Nesta seção, Bentley discute otimizações de função, especificamente o conceito de inlining para evitar a sobrecarga de uma chamada de função. Ao declarar uma função como estática em linha, o compilador tentará substituir uma chamada para a função pelo corpo da própria função, o que elimina a necessidade de uma chamada de função separada. Embora as macros também possam fazer isso, as funções inline são mais estruturadas e avaliam todos os seus argumentos, evitando o risco de uma macro colar uma expressão cara várias vezes no código. A Bentley desaconselha a otimização prematura e incentiva os desenvolvedores a primeiro garantir que seu programa esteja correto e usar testes de regressão para manter a correção. Por fim, ele aponta que muitos níveis de otimização podem ser automatizados pelo compilador, e a verificação do código assembly pode revelar essas otimizações.

  • 01:20:00 Nesta seção, as regras da Bentley para otimizar o trabalho são descritas em uma série de seis etapas. Essas regras consistem em estabelecer metas claras, dividir as tarefas em partes menores, reservar um tempo para planejar e organizar, priorizar tarefas, minimizar distrações e revisar e ajustar regularmente sua abordagem. Seguindo essas diretrizes, você pode aumentar sua produtividade e atingir suas metas de maneira mais eficiente. Além disso, incorporar essas estratégias em sua rotina diária pode ajudá-lo a manter uma forte ética de trabalho e manter o foco em seus objetivos.
 

Aula 3. Bit Hacks



3. Hacks de bits

Este vídeo do YouTube cobre uma variedade de tópicos de manipulação de bits, incluindo representação binária, complemento de dois, operadores bit a bit, troca de variáveis sem uma variável temporária e otimização de código. O vídeo demonstra vários truques de bits, como encontrar o mínimo de dois inteiros sem usar instruções if-else e como trocar dois inteiros sem usar uma variável temporária. O palestrante discute ramificações imprevisíveis e apresenta um truque de bit mínimo sem ramificação para quando ramificações previsíveis não estão disponíveis e mostra como os hacks de bits podem otimizar o código substituindo operações caras, como divisão, por operações bit a bit simples. O vídeo também discute a sequência de De Bruijn e sua aplicação na solução de problemas como o problema de N Queens.

A segunda parte discute a solução do problema N Queens usando vetores de bits e contando eficientemente o número de bits 1 em uma palavra binária. Backtracking é usado para implementar o problema N Queens, e vetores de bits são usados para representar a placa de forma eficiente. Três verificações são descritas para colocar com segurança uma rainha no problema de N Rainhas, e um método para contar o número de bits 1 em uma palavra, eliminando recursivamente o bit 1 menos significativo, é apresentado. Além disso, é discutido o uso de pesquisa de tabela e manipulação de registro para contar o número de bits 1. O vídeo termina com uma demonstração de uma abordagem de divisão e conquista para contar 1 bits que tem um desempenho proporcional ao log base dois do comprimento da palavra. Recursos para aprendizagem adicional também são fornecidos.

  • 00:00:00 Nesta seção, aprenderemos sobre representação binária para palavras e como calcular valores inteiros a partir delas. Também aprendemos sobre a representação de complemento de dois para inteiros com sinal e os casos especiais da palavra todos os zeros e todos os uns. Além disso, vemos uma identidade importante para o complemento de um de X e sua relação com o negativo de X na representação do complemento de dois.

  • 00:05:00 Nesta seção, o apresentador explica o Complemento de Um e como obter o negativo de um número adicionando 1 ao Complemento de Um. Ele também examina o uso de números hexadecimais para representar grandes constantes binárias e fornece uma tabela para converter entre hexadecimais e binários. Em seguida, o vídeo aborda os operadores bit a bit em C++ e mostra exemplos de como usá-los para operações lógicas e, lógicas ou, exclusivas ou e de deslocamento à esquerda e à direita.

  • 00:10:00 Nesta seção, o vídeo discute vários idiomas comuns que podem ser implementados usando operadores bit a bit em C. Um exemplo é definir ou limpar o bit de caso em uma palavra X usando um deslocamento seguido por um OU ou NÃO e um E, respectivamente. Outro exemplo é extrair um campo de bit de uma palavra X gerando uma máscara com uns nas posições dos bits desejados e zeros em outro lugar, depois fazendo AND da máscara com X e deslocando à direita os bits extraídos. O vídeo também menciona que o uso desses truques pode ser particularmente útil ao trabalhar com dados compactados ou codificados.

  • 00:15:00 Nesta seção, o vídeo discute como trocar dois números inteiros sem usar uma variável temporária usando alguns truques de bits. O código envolve definir X igual a X XOR Y, depois Y igual a X XOR Y e, finalmente, X igual a X XOR Y. Isso funciona porque XOR é seu próprio inverso e a primeira linha gera uma máscara com aqueles em que os bits em X e Y diferem, que é então usado para inverter os bits em Y que são diferentes de X. Isso permite a troca sem o uso de uma variável temporária. O vídeo também enfatiza a importância do mascaramento para garantir a segurança ao trabalhar com esses truques.

  • 00:20:00 Nesta seção, o palestrante discute hacks de dois bits. O primeiro hack é um método para trocar duas variáveis sem usar uma variável temporária. O hack envolve o uso de XOR e uma máscara para inverter os bits que diferem entre as duas variáveis. Embora esse hack seja legal, não é a maneira mais eficiente de trocar variáveis devido ao baixo paralelismo do nível de instrução. O segundo hack é uma maneira de encontrar o mínimo de dois inteiros sem usar instruções if-else, o que pode causar problemas de desempenho devido a erros de previsão de ramificação. Em vez disso, o palestrante mostra como usar operações bit a bit para comparar os números inteiros e calcular o mínimo sem ramificação.

  • 00:25:00 Nesta seção, o palestrante discute a otimização de código e o uso da palavra-chave "restrict" em uma sub-rotina que mescla dois arrays classificados. O processo é explicado por meio de um exemplo em que dois arrays verdes são mesclados em um array azul. A previsibilidade de cada ramificação no código também é discutida, sendo a primeira ramificação previsível enquanto a segunda é imprevisível.

  • 00:30:00 Nesta seção, o vídeo discute desvios previsíveis e imprevisíveis na programação e apresenta um truque de bit mínimo sem desvio como uma solução para o problema de desvio imprevisível. O truque envolve usar uma variável chamada "comp" para armazenar o resultado da comparação entre o primeiro elemento de a e b e obter o mínimo de a e b usando um truque de bit. Em seguida, o valor mínimo é colocado em C, e o valor de A ou B é incrementado ou decrementado com base no valor de "comp". O vídeo observa que, embora o truque possa não funcionar em alguns casos, é útil entender o que o compilador está fazendo e que muitos hacks de bits para palavras podem se estender a hacks de bits e palavras para vetores, tornando útil conhecer esses truques.

  • 00:35:00 Nesta seção, o vídeo discute hacks de bits e sua utilidade na programação. O exemplo dado é um pequeno truque para adição modular que permite operações mais rápidas sem o uso de divisão. Ao definir Z como a soma de X e Y e, em seguida, verificar se é menor ou maior que N, o programa pode retornar Z se estiver dentro do intervalo ou o resultado de Z menos N para trazê-lo de volta ao intervalo. O programa usa lógica semelhante ao mínimo e tem uma ramificação imprevisível que pode resultar em uma previsão incorreta da ramificação. Outro exemplo fornecido é uma maneira de arredondar um valor para a potência de dois mais próxima usando a manipulação de bits decrementando N, executando bit a bit ou operações com N deslocado à direita por valores diferentes e, em seguida, incrementando no final.

  • 00:40:00 Nesta seção do vídeo, o palestrante discute problemas de manipulação de dois bits. O primeiro problema envolve encontrar a menor potência de dois que seja maior que um determinado valor n. O palestrante explica como conseguir isso usando manipulação de bits e decrementando n se já for uma potência de dois para garantir que o logaritmo de n menos um bit seja definido. O segundo problema envolve calcular a máscara do menos significativo em uma palavra X, e o palestrante explica como conseguir isso definindo o resultado como X e usando bit a bit e operação com X negativo. O palestrante também apresenta o código para encontrar o índice do bit multiplicando X por uma constante e procurando o resultado em uma tabela. A seção termina com o orador executando um truque de mágica matemática envolvendo manipulação de bits.

  • 00:45:00 Nesta seção, um vídeo do YouTube mostra um grupo realizando um truque de mágica com cartas e um sino. A performer afirma ler a mente do público e pede que cortem o baralho antes de distribuí-lo. O artista prevê o naipe e o número da carta de cada pessoa e aparentemente tem sucesso. Eles atribuem suas habilidades a usar um "macaco incrível" e um chapéu mágico, além de limpar o ar com um sino.

  • 00:50:00 Nesta seção, aprendemos sobre a sequência de Bruyne e sua correlação com o cálculo do log base 2 de uma potência de 2. A sequência de Bruyne é uma sequência de bits cíclica em que cada cadeia de bits possível de comprimento K ocorre exatamente uma vez como uma substring na sequência. Usando uma tabela de conversão, podemos multiplicar a constante de sequência de Bruyne por uma potência de 2 e extrair a substring que aparece no início da sequência para calcular o log base 2 da potência de 2. Deslocando a sequência para a esquerda e procurando subindo a posição inicial da substring na tabela de conversão, podemos determinar o log base 2 do inteiro com o qual começamos, o que resolve o truque do cartão demonstrado anteriormente.

  • 00:55:00 Nesta seção, o palestrante discute a sequência de Bruijn, que é uma sequência cíclica de um alfabeto binário que contém cada sequência de n bits possível exatamente uma vez. A sequência pode ser usada para resolver problemas como o problema das N Rainhas e pode ser gerada usando um truque de mágica. O palestrante também explica como o truque do bit funciona para determinar a posição de uma substring de uma sequência de De Bruijn após um deslocamento à esquerda. O desempenho desse truque de bit é limitado pelo desempenho da multiplicação e da consulta à tabela, mas agora existe uma instrução de hardware para calculá-lo.

  • 01:00:00 Nesta seção, o palestrante discute o problema das N Rainhas, que envolve colocar N rainhas de xadrez em um tabuleiro de xadrez NxN de modo que duas rainhas não ameacem uma à outra. O problema geralmente é implementado usando retrocesso, onde as rainhas são colocadas linha por linha e o programa retrocede quando nenhuma posição válida pode ser encontrada. Diferentes representações da placa também são discutidas, sendo a mais compacta um conjunto de vetores de três bits. O vetor descendente armazena a presença de rainhas em cada coluna, o vetor diagonal esquerdo armazena a presença de rainhas em cada diagonal esquerda e o vetor diagonal direita armazena a presença de rainhas em cada diagonal direita. O uso de vetores de bits permite uma implementação mais eficiente do algoritmo.

  • 01:05:00 Nesta seção, é descrito o processo de verificar se uma posição é segura para colocar uma rainha em um problema de n-rainhas usando vetores de bits. As três verificações envolvem verificar se já existe uma rainha na mesma linha, na mesma coluna e na mesma diagonal da posição. Este método é eficiente e garante que uma rainha possa ser posicionada com segurança se passar em todas as três verificações. Outro problema discutido é a contagem da população, que envolve contar o número de 1 bits em uma palavra X. O método apresentado elimina repetidamente o 1 bit menos significativo em X até que ele se torne zero, e o número de iterações necessárias é proporcional ao número de 1 bits em X.

  • 01:10:00 Nesta seção, o palestrante discute o uso da pesquisa de tabela para contar com eficiência o número de bits 1 em uma palavra binária. O método de pesquisa de tabela envolve a criação de uma tabela de tamanho 256 que armazena o número de uns em cada palavra de 8 bits e, em seguida, procura a contagem de cada substring de 8 bits na palavra binária. O palestrante observa que o desempenho desse método é prejudicado pelas operações de memória necessárias para acessar a tabela. O palestrante apresenta uma terceira forma de contar o número de bits 1 usando registradores, onde eles criam máscaras e executam instruções específicas que permitem contar o número de uns em uma palavra binária sem acessar a memória. O apresentador passa por um exemplo para explicar como esse método funciona.

  • 01:15:00 Nesta seção, o palestrante demonstra como contar o número de 1s em uma palavra de entrada usando um método paralelo de divisão e conquista, onde o desempenho é proporcional ao logaritmo da base dois do comprimento da palavra, W. É apontou que a maioria das máquinas modernas tem uma instrução de contagem pop intrínseca que é mais rápida do que qualquer coisa que possa ser codificada, acessível por meio de intrínsecos do compilador. No entanto, isso pode tornar o código menos portátil em diferentes máquinas. O palestrante fornece alguns recursos para aprender mais sobre truques de bits, incluindo um site, um livro didático, um site de programação de xadrez e um livro chamado Hacker's Delight.
 

Aula 4. Linguagem Assembly e Arquitetura de Computador



Aula 4. Linguagem Assembly e Arquitetura de Computador

Este vídeo fornece uma visão geral abrangente da linguagem assembly e da arquitetura do computador. A linguagem assembly é uma interface importante para otimizar o desempenho do código, e entender a arquitetura do computador é essencial para dominar a linguagem assembly. O palestrante explica a história da arquitetura x86 64 e seu desenvolvimento, seus principais registradores, tipos de dados, modos de endereçamento de memória e arquitetura do conjunto de instruções, incluindo pilhas, lógica inteira e binária, lógica booleana e sub-rotinas. Eles também discutem extensões como zero e extensão de sinal e vários modos de endereçamento em linguagem assembly. Além disso, o vídeo discute tipos de ponto flutuante, vetores e unidades vetoriais, instruções tradicionais e SSE e recursos de design de arquitetura de computador, como processamento superescalar, execução fora de ordem e previsão de ramificação.

O vídeo também aborda vários tópicos relacionados à linguagem assembly e arquitetura de computadores. Um dos temas centrais é o paralelismo de nível de instrução (ILP) e as paradas de pipeline, que são causadas por perigos como dependências de dados. O palestrante discute as dependências de dados verdadeiras, anti e de saída e como os processadores superescalares podem explorar mais paralelismo no hardware para executar várias instruções ao mesmo tempo. No entanto, para evitar riscos, os arquitetos implementaram estratégias como renomear e reordenar, bem como a execução especulativa para adivinhar o resultado de uma ramificação e executá-la antecipadamente. O palestrante incentiva o público a entender esses métodos para compreender melhor as otimizações de software.

  • 00:00:00 Nesta seção, o instrutor fala sobre linguagem assembly e arquitetura de computador, que muitas vezes não são abordadas em cursos de software modernos. Compreender esses conceitos é necessário para otimizar o desempenho do código, e a linguagem assembly é a melhor interface para fazer isso. O processo de compilação de código envolve vários estágios, incluindo pré-processamento, compilação, montagem e vinculação. A linguagem assembly é uma estrutura mnemônica do código de máquina que o torna mais legível por humanos, e o executável final é produzido por meio de um estágio de vinculação usando o comando LD.

  • 00:05:00 Nesta seção, o palestrante explica que o assembly e o código de máquina são muito semelhantes em estrutura, com códigos OP em assembly correspondendo a padrões de bits específicos no código de máquina. O palestrante apresenta o programa ABS, que pode produzir uma desmontagem de código de máquina, revelando o código de montagem mnemônico e legível por humanos. O palestrante então discute vários motivos pelos quais alguém pode querer examinar o código assembly, incluindo revelar o que o compilador fez e o que não fez, depurar erros do compilador e fazer engenharia reversa de um programa sem acesso à sua fonte.

  • 00:10:00 Nesta seção, o palestrante explica as expectativas para a classe, que incluem entender como um compilador implementa construções linguísticas com instruções x86, ser capaz de ler a linguagem assembly x86 e entender as implicações de desempenho de padrões comuns de montagem. Os alunos também devem ser capazes de escrever código do zero, se necessário, e obter domínio a um nível em que isso seja viável. O alto-falante então mergulha na arquitetura do conjunto de instruções x86 64, incluindo registros, instruções, tipos de dados e modos de endereçamento de memória. Registradores de chave incluem registradores de uso geral e registradores de sinalizadores, que rastreiam operações aritméticas e carregam. O ponteiro de instrução orienta o hardware através da sequência de instruções em um programa em linguagem assembly.

  • 00:15:00 Nesta seção, o palestrante discute a história da arquitetura x86 64 e seu desenvolvimento de máquinas de palavras de 16 bits com memória limitada para palavras mais amplas para indexação à medida que mais memória se torna disponível. O palestrante também explica a adição de registradores vetoriais, como os registradores xmm e AVX para vetorização, e como eles são usados. Eles também abordam o tópico de registradores de uso geral e como seus propósitos funcionais mudaram significativamente ao longo do tempo, mas seus nomes permaneceram devido a razões históricas. Além disso, o palestrante explica como certos registros são alias para a mesma coisa para as metades inferior e superior da palavra curta, palavras de 32 bits ou 64 bits.

  • 00:20:00 Nesta seção, o palestrante explica os fundamentos da linguagem assembly x86 64 e como ela funciona. Os registradores têm nomes diferentes, dependendo de qual parte do registrador está sendo acessada, e alguns têm propósitos específicos, como RSP sendo usado como o ponteiro da pilha. O formato de um código de instrução x86 64 é ter um opcode e uma lista de operandos, geralmente com 0-3 operandos que podem ser fontes ou destinos. O palestrante explica a diferença entre a sintaxe da AT&T e a sintaxe da Intel para se referir a operações e fornece uma lista de códigos operacionais comuns, como "mover" e "mover condicional". Além disso, o palestrante explica a importância de estender o sinal ao passar de um registro de valor de 32 bits para um registro de 64 bits.

  • 00:25:00 Nesta seção, o palestrante discute os vários tipos de instruções em linguagem assembly, incluindo instruções para pilhas, aritmética inteira, lógica binária, lógica booleana, saltos e sub-rotinas. Os opcodes podem ser aumentados com um sufixo que descreve o tipo de dados da operação ou um código de condição. Por exemplo, um movimento com uma "sugestão" indica que os dados que estão sendo movidos são uma palavra quádrupla, que consiste em 8 bytes ou 64 bits. Os tipos de dados x86 64 e seus sufixos de montagem também são discutidos, e exemplos são fornecidos para ilustrar como a extensão de sinal funciona. A presença ou ausência de certos opcodes e mnemônicos na linguagem assembly pode ser confusa, mas o compilador precisa entender essas instruções para executar o programa corretamente.

  • 00:30:00 Nesta seção, o palestrante discute as extensões como extensão de zero e extensão de sinal que ocorrem ao mover operações de 32 bits para operações de 64 bits. Eles também mencionam como o conjunto de instruções da Intel pode se tornar mais complicado com a adição de novas instruções. O palestrante continua explicando os diferentes códigos de condição usados em saltos condicionais e movimentos condicionais e os sinalizadores que são usados com eles, como o sinalizador zero e o sinalizador de estouro. A razão para certos códigos de condição verificarem o sinalizador zero também é discutida.

  • 00:35:00 Nesta seção, o palestrante discute os diferentes modos de endereçamento direto e indireto na linguagem assembly. Os modos de endereçamento direto incluem memória imediata e direta e usando um registrador. Os modos de endereçamento indireto de registro e indexado de registro permitem acessar a memória fornecendo o endereço em um registro ou compensando o endereço. O palestrante observa que o acesso à memória pode ser lento e caro, por isso é importante armazenar valores em registradores sempre que possível para agilizar o processo. Eles também mencionam a importância do cache na otimização do acesso à memória.

  • 00:40:00 Nesta seção, o vídeo discute o uso da indexação relativa de ponteiro, em que o ponteiro de instrução é usado para indexar dados em vez de um registrador de uso geral. O método de endereçamento de deslocamento de escala de índice de base também é introduzido, que é uma instrução complicada que oferece suporte à indexação suave de um ponteiro de base. O vídeo fornece uma visão geral de alguns idiomas da linguagem assembly, incluindo o opcode XOR, que é usado para zerar registradores, e o opcode de teste, que calcula bit a bit e de dois valores e preserva os sinalizadores de registradores. Por fim, o vídeo aborda instruções de salto e rótulos, que permitem o fluxo de controle no código.

  • 00:45:00 Nesta seção, o vídeo discute a linguagem assembly e a arquitetura do computador, incluindo vários conjuntos de instruções e a história do ponto flutuante. Os conjuntos de instruções x86, incluindo x87 e SSE, suportam aritmética de ponto flutuante escalar de precisão simples e dupla e instruções vetoriais. As instruções SSE são geralmente preferidas pelos compiladores sobre x87 devido à sua simplicidade na compilação e otimização. O propósito de usar instruções sem operação (nop) na montagem, como otimização de alinhamento, também é explicado.

  • 00:50:00 Nesta seção, o palestrante discute tipos de ponto flutuante, vetores e unidades vetoriais que são utilizados na arquitetura de computadores. O palestrante explica que a forma como as unidades vetoriais funcionam é que o processador emite instruções para todas as unidades vetoriais, cada uma das quais é chamada de pista. As pistas contêm aritmética inteira ou de ponto flutuante e todas operam em sincronia, o que significa que todas fazem a mesma coisa. Eles podem realizar várias operações ao mesmo tempo e tudo isso pode ser feito com uma única instrução. O palestrante explica que algumas arquiteturas exigem que os operandos vetoriais sejam alinhados, enquanto outras podem deslocar vetores na memória, o que resulta em uma diferença de desempenho entre as duas. Além disso, existem arquiteturas que suportam operações cross-lane, como permutação, embaralhamento e dispersão.

  • 00:55:00 Nesta seção, o palestrante discute as diferenças entre instruções tradicionais e SSE e como elas podem ser usadas. Eles também mencionam o truque de aliasing em que os registros ymm alias os registros xmm e os estendem para 512 bits com avx-512. Eles então passam para uma discussão sobre arquitetura de computador, especificamente a diferença entre um pipeline de cinco estágios e um processador moderno com 14 a 19 estágios de pipeline. Os recursos de design que eles discutem incluem vetor ou Hardware I, processamento superescalar, execução fora de ordem e previsão de ramificação, mas eles mencionam que não se aprofundarão na execução fora de ordem devido a restrições de tempo.

  • 01:00:00 Nesta seção do vídeo, o instrutor discute o paralelismo de nível de instrução (ILP) e as paradas de pipeline. O ILP envolve encontrar oportunidades para executar várias instruções simultaneamente para melhorar o rendimento. No entanto, as interrupções do pipeline podem ocorrer quando uma instrução não pode ser executada devido a um perigo, como um perigo estrutural, perigo de dados ou perigo de controle, sendo os perigos de dados os mais comuns. Uma dependência verdadeira ocorre quando uma instrução lê após uma dependência de gravação, enquanto uma antidependência ocorre quando uma instrução deseja gravar em um local, mas precisa esperar até que a instrução anterior tenha lido o valor. O compilador tenta reduzir as interrupções do pipeline otimizando o código para evitar perigos.

  • 01:05:00 Nesta seção, o conceito de dependências de dados em linguagem assembly é discutido. Existem três tipos de dependências de dados: true, anti e output. As operações aritméticas, especialmente as complexas como a aritmética de ponto flutuante, têm uma latência mais longa e requerem unidades funcionais separadas no processador, às vezes com registradores separados. Para aumentar o paralelismo do nível de instrução, os arquitetos implementaram técnicas como emitir várias instruções por ciclo para explorar mais paralelismo no hardware.

  • 01:10:00 Nesta seção, o vídeo explica como os processadores superescalares podem executar várias instruções ao mesmo tempo, usando o exemplo de Haswell quebrando as instruções em operações mais simples chamadas micro ops e emitindo até quatro micro ops por ciclo. O vídeo detalha estratégias para liberar os processadores de executar instruções em ordem, incluindo ignorar e renomear registradores, o que permite que instruções não dependentes sejam executadas fora de ordem, resultando em tempos de processamento mais rápidos. Essas estratégias exigem o acompanhamento das dependências e a execução do código de forma a evitar perigos, como dependências de dados.

  • 01:15:00 Nesta seção, o palestrante discute renomear e reordenar, que são dois métodos importantes usados em processadores modernos para evitar riscos de dados. O palestrante também fala sobre a execução especulativa, que é usada na previsão de ramificação para adivinhar o resultado de uma ramificação e executá-la antecipadamente, para evitar a paralisação. No entanto, se o palpite estiver errado, custará cerca de 15 a 20 ciclos para desfazer o cálculo. O palestrante menciona brevemente como os preditores de ramificação funcionam, mas aponta que é complicado e requer um estudo mais aprofundado. Apesar do final apressado, o palestrante incentiva o público a entender os vários métodos, o que ajudará a entender por que certas otimizações de software funcionam e não funcionam.
 

Aula 5. C para assembléia



Aula 5. C para assembléia

Nesta parte do vídeo, é discutida a importância de entender C para linguagem assembly, juntamente com como o código C é implementado em linguagem assembly usando um compilador. O foco está especificamente em como o LLVM IR é convertido em assembly na convenção de chamada x86 64 do Linux. O apresentador explica os componentes básicos do LLVM IR e como as construções na linguagem de programação C são traduzidas para o LLVM IR. O vídeo também aborda o layout da memória virtual, a questão da coordenação de chamadas de função entre várias funções e o uso da convenção de chamada do Linux x86 64 de dois ponteiros - o BP e o SP - para gerenciar todos os quadros de pilha.

O vídeo também explica as estratégias para manter os estados de registro em programação C para Assembly, como salvar registros como caller-save ou callee-save, e como a convenção de chamada x86 evita o desperdício de trabalho. Ele aborda como as chamadas de função funcionam em C e assembly, discutindo o processo de salvar argumentos e variáveis locais na pilha, bem como a otimização comum de usar o ponteiro da pilha em vez do ponteiro base. O vídeo também mostra o processo de compilação do LV miR em código assembly, discutindo o prólogo da função, salvando registradores, manipulando condições e convertendo código C em código assembly usando um gráfico de fluxo de controle. Finalmente, fala sobre a função epílogo usada para restaurar registros antes de retornar resultados.

  • 00:00:00 Nesta seção do vídeo, TB Shuttle discute a importância de entender C para a linguagem assembly. Ele observa que a linguagem assembly fornece maior precisão do que o código C e pode revelar detalhes sobre um programa que não são óbvios no código C. Observar o assembly também pode permitir que os desenvolvedores determinem o que o compilador fez ou não ao otimizar um programa. Além disso, podem surgir bugs que apenas criariam um comportamento inesperado ao otimizar o código em determinados níveis, dificultando a identificação desses bugs. Por fim, entender o assembly pode permitir que os desenvolvedores modifiquem o código do assembly manualmente ou façam engenharia reversa do código.

  • 00:05:00 Nesta seção, o vídeo discute como o código C é implementado em linguagem assembly por meio do uso de um compilador que precisa tomar decisões complexas sobre quais instruções assembly usar, como implementar condicionais e loops C e como chamadas de função coordenada. Para entender o processo de tradução, o vídeo apresenta o LVM IR, que é um assembly simplificado que o compilador usa para raciocinar sobre o programa. O vídeo explica como as construções na linguagem de programação C, como funções, condicionais e loops, são traduzidas para o LVM IR. A seção termina com uma breve menção aos atributos LVM IR.

  • 00:10:00 Nesta seção, o foco está no processo de como o LLVM ir é traduzido em assembly, especificamente na convenção de chamada x86 64 do Linux. O apresentador fornece uma breve cartilha sobre LLVM ir, explicando seus componentes básicos de funções, instruções e registros, que se assemelham a uma versão mais simples de montagem. Os registradores ir do LLVM são semelhantes às variáveis c e são diferenciados por seus nomes, e cada função tem seus próprios nomes de registradores locais. O apresentador destaca os registros em um trecho de código de exemplo e observa que a sintaxe dos registros é sequestrada ao se referir a diferentes blocos básicos no LLVM. A palestra termina com um estudo de caso sobre como esse processo funciona para um código simples para calcular números de Fibonacci.

  • 00:15:00 Nesta seção, o palestrante explica a sintaxe das instruções LV Mir, que envolve um nome de registrador, um símbolo de igual, um opcode e uma lista de operandos. Enquanto algumas instruções retornam um valor que é armazenado em um registrador local, outras não. O conjunto de instruções LV Mir é menor que o do x86, pois contém apenas algumas instruções para movimentos de dados, operações aritméticas e lógicas e fluxo de controle. No LV Mir, tudo é exposto como tipos, que incluem números inteiros (com um número definido de bits), tipos de ponto flutuante, tipos de ponteiro, tipos de vetor e tipos de rótulo para blocos básicos. O palestrante também menciona que as operações vetoriais LV Mir não se parecem com SSE ou AVX, mas sim com operações comuns que funcionam em um tipo vetorial.

  • 00:20:00 Nesta seção, o vídeo discute como as sequências de operações no código C são traduzidas em LLVM IR e as regras básicas para interpretar o código em IR. O trecho também explica como o LLVM IR lida com tipos primitivos e agregados, como arrays e structs, e mostra exemplos de como acessar elementos em um array envolve computar endereços na memória. Além disso, o vídeo explica como as funções C são traduzidas em LLVM IR, com as declarações de retorno correspondentes em ambos os idiomas.

  • 00:25:00 Nesta seção, o vídeo explica como funções e parâmetros em C se traduzem em LV Mir. As funções em LV Mir são semelhantes às funções em C, mas os parâmetros C tornam-se listas de parâmetros em LV Mir. No entanto, a leitura do LV Mir pode ser desafiadora, pois os registros não são bem nomeados, dificultando a decifração. O vídeo também discute blocos básicos no LV Mir, que são blocos de código particionados com base em instruções de fluxo de controle. As conexões entre blocos básicos são baseadas em arestas induzidas por instruções de desvio. Por fim, o vídeo aborda condicionais em LV Mir, onde declarações if-then-else tornam-se instruções de ramificação condicional que induzem blocos básicos e controlam bordas de fluxo.

  • 00:30:00 Nesta seção, o vídeo explica como as operações condicionais e as ramificações funcionam no LLVM IR. O processo começa com uma comparação entre um valor literal e um valor armazenado em um registrador, que cria um resultado inteiro ou booleano de um bit. Esse resultado é então passado para uma ação de ramificação condicional junto com dois rótulos de blocos básicos indicando para onde ir se o predicado for verdadeiro ou falso. Se houver um desvio incondicional com um operando, o resultado é um salto direto para um bloco básico específico. O vídeo também mostra como criar uma forma de diamante no gráfico de fluxo de controle sempre que houver uma instrução condicional e fornece um exemplo de loop escrito em código C.

  • 00:35:00 Nesta seção, o vídeo discute os componentes de um loop C, que incluem o corpo do loop e o controle do loop. O corpo do loop é executado em cada iteração, enquanto o controle do loop gerencia todas as iterações do loop. O loop AC produz um padrão de loop no gráfico de fluxo de controle, que por sua vez cria uma estrutura de loop no LLVM ir. O vídeo então analisa o código LLVM ir para o controle do loop, onde há uma estranha instrução fie que surge comumente ao lidar com loops. A instrução fie tenta resolver um problema com a representação LLVM do código, onde I é representado por um monte de registradores diferentes, deixando claro para onde eu realmente fui.

  • 00:40:00 Nesta seção, o vídeo discute o mapeamento da variável de indução em um loop para vários locais no LLVM, o que ocorre devido à alteração dos valores da variável nas iterações do loop. Isso leva à invariante de "atribuição única estática" no LLVM em que cada instrução define apenas o valor de um registro uma vez, o que representa um problema para variáveis de indução. A instrução "phi" resolve esse problema definindo um valor de registro que depende de como o fluxo de controle se funde no ponto de entrada de um loop. O vídeo também discute atributos em LLVM e como eles podem fornecer informações extras para construções LLVM, como o atributo NSW anexado à instrução "add".

  • 00:45:00 Nesta seção do vídeo, o foco está no LLVM IR, que é semelhante à montagem, mas mais simples em muitos aspectos, pois todos os valores calculados são armazenados em registradores que são como variáveis C comuns. O LLVM IR usa o paradigma de atribuição única estática em que cada variável é escrita por no máximo uma instrução. O vídeo descreve como traduzir código C em LLVM IR e depois em assembly, com algumas complexidades adicionais no processo. O compilador seleciona as instruções de montagem necessárias para as operações LLVM IR, decide quais registradores de uso geral são usados e coordena chamadas de função entre diferentes arquivos de origem e bibliotecas binárias. A discussão então se volta para a convenção de chamada Linux x86 64.

  • 00:50:00 Nesta seção, o layout da memória virtual para um programa é discutido. A memória virtual é dividida em segmentos, como os segmentos de pilha e heap, que são organizados com o uso de diretivas assembler no código assembly. Além disso, são discutidos diferentes tipos de diretivas de armazenamento, como a diretiva de espaço e o segmento longo, que alocam memória e armazenam valores. A atenção é então voltada para o segmento da pilha onde os dados são armazenados para gerenciar chamadas e retornos de função, o que inclui o armazenamento de variáveis locais, argumentos de função, endereço de retorno e possivelmente resultados intermediários.

  • 00:55:00 Nesta seção do vídeo, o apresentador discute a questão da coordenação de chamadas de função em várias funções, algumas das quais podem se originar de diferentes arquivos ou bibliotecas. Para garantir que todas as funções funcionem bem juntas, foi estabelecida uma convenção de chamada que todas as funções devem obedecer. A convenção de chamada do Linux x86 64 usa dois ponteiros - o BP e o SP - para gerenciar todos os quadros de pilha para cada instanciação de função. Quando uma instrução de chamada é executada, o valor atual do IP é colocado na pilha como o endereço de retorno e a instrução de chamada salta para o endereço de alguma função na memória do programa. A instrução return desfaz as operações da instrução call e retira o endereço de retorno da pilha para retornar à execução do chamador. Para lidar com o problema de várias funções que desejam usar os mesmos registradores, a convenção de chamada detalha as regras para quais registradores cada função pode usar e como elas devem preservar esses registradores por meio de chamadas de função.
  • 01:00:00 Nesta seção, o vídeo discute as estratégias para manter os estados dos registradores ao operar com diferentes funções em programação C para Assembly. Ele menciona os dois métodos que podem ser usados, um onde o chamador salva o estado do registrador antes de invocar uma chamada, e o outro onde o chamado salva todo o estado do registrador. A convenção de chamada x86 envolve ambos, especificando alguns registros como callee-save e outros como caller-save para evitar desperdício de trabalho. O vídeo também explora como a memória da pilha é organizada e a pilha cresce. Por fim, discute a coordenação de como as funções usarão as partes sobrepostas da memória da pilha.

  • 01:05:00 Nesta seção, o vídeo discute como funciona uma chamada de função em C e assembly. Antes de chamar a função C, a função B coloca argumentos sem registro para a função C em um bloco de ligação reservado em sua própria memória de pilha abaixo de suas variáveis locais. Ele acessará esses argumentos com compensações negativas. Quando a função C inicia, ela executa um prólogo de função que salva o ponteiro base para o quadro de pilha de B e define BP igual a SP porque está entrando em um novo quadro. Em seguida, ele aloca espaço na pilha para suas próprias variáveis locais, bem como o espaço que B usará para quaisquer blocos de ligação que crie para seus chamadores ou para as coisas que chama. O vídeo também menciona uma otimização comum em que o compilador pode se livrar do BP e fazer toda a indexação com base no ponteiro da pilha RSP para obter mais um registro de uso geral.

  • 01:10:00 Nesta seção, o instrutor leva o público através do processo de compilação do LV miR até o código assembly. A primeira etapa envolve definir a função 'fib' como uma função globalmente acessível usando algumas diretivas do montador, como diretiva fib global e alinhamento. Em seguida, o prólogo da função é salvo com uma fila push de var BP e uma fila mob de RSP rbp. O código assembly também coloca alguns registradores na pilha, que são registradores Kali-save, antes de mover o argumento para a função, RTI, e o guarda no registrador RBX. Por fim, uma instrução de comparação é avaliada para verificar se o valor de N é menor que dois e, se for, retorna o valor de entrada. Caso contrário, ele passa por algum código de linha reta para calcular fib de n menos um e fib de n menos dois, adicioná-los e retornar esse resultado.

  • 01:15:00 Nesta seção, o vídeo discute os saltos condicionais e os vários comportamentos que ocorrem a seguir no código, dependendo dos resultados da comparação. A instrução JGE salta para o rótulo do lado falso da operação de ramificação LLVM quando n é maior ou igual a 2, enquanto as operações correspondem ao lado verdadeiro da operação quando n é menor que 2. A instrução LEA é usada para cálculo de endereço, enquanto a operação de movimentação salva o resultado da chamada de função em R14. O próximo conjunto de instruções calcula o valor de n-2, armazena-o em RDI e, em seguida, chama fib em n-2, retornando o resultado para nosso AX. Finalmente, a operação adiciona R14 ao nosso AX.

  • 01:20:00 Nesta seção, o vídeo discute a conversão do código C para o código assembly. O palestrante explica que o processo utiliza um gráfico de fluxo de controle, composto por blocos básicos conectados por arestas de fluxo de controle, para representar o código. Eles também mencionam a complexidade de lidar com as convenções de chamada no código assembly. A função epílogo é usada para restaurar registradores antes de qualquer coisa no stack frame, antes de retornar o resultado. O vídeo conclui resumindo os principais tópicos abordados em toda a seção.
 

Aula 6. Programação Multicore



Aula 6. Programação Multicore

Esta videoaula discute a programação multi-core e o surgimento de processadores multi-core devido à Lei de Moore e ao fim do escalonamento das frequências de clock. O palestrante explica o problema de densidade de energia enfrentado pelos processadores e como isso levou à adição de vários núcleos aos chips para acompanhar a Lei de Moore. A palestra também aborda os fundamentos dos protocolos de coerência de cache em hardware de memória compartilhada e plataformas de simultaneidade como Pthreads, TBB, OpenMP e Silk, que fornecem abstrações para programação paralela. Os prós e contras de cada plataforma são discutidos e demonstrados com exemplos de implementação de programas Fibonacci. O vídeo fornece uma visão abrangente da programação multi-core e os desafios e soluções enfrentados pelos programadores.

O vídeo também cobre vários aspectos do Silk, uma ferramenta de abstração para manipulação de processamento paralelo. O palestrante discute tópicos como silk for loops aninhados, geração de código assembly, redução usando redutores, agendador e otimização de desempenho. Eles também fornecem uma visão geral do ecossistema Silk e das ferramentas relacionadas, como o higienizador de seda e a escala de seda para depuração e análise de escalabilidade, respectivamente. A principal conclusão é que escrever programas paralelos para processadores multicore pode ser um desafio, mas o Silk simplifica o processo lidando com tarefas complexas com eficiência, dando aos programadores mais controle sobre a execução de seu código.

  • 00:00:00 Nesta seção, o instrutor discute a programação multi-core e as razões para o surgimento de processadores multi-core. Com o advento da lei de Moore, que afirma que o número de transistores que podem caber em um chip dobra a cada dois anos, e o fim do escalonamento das frequências de clock por volta de 2004 a 2005, os fornecedores de semicondutores começaram a produzir chips com vários núcleos de processador. Isso se deve ao fato de que não era mais possível aumentar a frequência de núcleos únicos em um chip, tornando necessário mudar para um modelo de design que permitisse o processamento paralelo. O instrutor também esclarece a relação entre o número de transistores em um chip e a frequência máxima do processador.

  • 00:05:00 Nesta seção, o palestrante discute o problema de densidade de energia enfrentado pelos processadores, onde o aumento da frequência do clock faz com que a densidade de energia aumente exponencialmente. Isso levou à adição de vários núcleos aos chips para acompanhar a Lei de Moore e não exceder os limites de densidade de energia. Em seguida, o palestrante apresenta a arquitetura abstrata multi-core, conhecida como multiprocessador de chip, e descreve as palestras sobre desafios de hardware e soluções de software para programar programas paralelos em máquinas multi-core usando diferentes plataformas de simultaneidade, como threads P, threads winAPI, threading Intel blocos de construção, openmp e mais.

  • 00:10:00 Nesta seção, o palestrante explica como os caches funcionam na programação multicore. Quando um processador carrega um valor em seu cache da memória principal, ele manterá esse valor no cache caso precise acessá-lo novamente no futuro. Se outro processador quiser carregar o mesmo valor, ele também pode obtê-lo através do cache do primeiro processador, em vez de ir até a memória principal. No entanto, surge um problema quando um processador atualiza o valor em seu próprio cache, tornando obsoleto o valor no cache de outro processador. O protocolo MSI é uma solução básica para esse problema, que rotula as linhas de cache com três estados possíveis (M, S e I) para garantir a coerência entre os caches.

  • 00:15:00 Nesta seção, a palestra discute os fundamentos dos protocolos de coerência de cache em hardware de memória compartilhada, particularmente como as modificações em uma linha de cache no cache de um processador podem invalidar as cópias de outros caches da mesma linha. A palestra apresenta um protocolo simples e explica como outros protocolos mais complexos existem na prática. O hardware é responsável por gerenciar conflitos quando vários processadores modificam a mesma linha de cache, mas isso pode resultar em uma "tempestade de invalidação" e diminuir o desempenho. A palestra também observa que as plataformas de simultaneidade podem abstrair essas complexidades e ajudar na sincronização e comunicação na programação paralela.

  • 00:20:00 Nesta seção, o palestrante discute diferentes plataformas de simultaneidade usando o exemplo dos números de Fibonacci. O programa Fibonacci é implementado usando um algoritmo recursivo que calcula os números de Fibonacci várias vezes, tornando-o um algoritmo ruim. As duas chamadas recursivas podem ser paralelizadas, pois são cálculos completamente independentes. Pthreads, uma API padrão para threading, pode ser usada para implementar essa paralelização.

  • 00:25:00 Nesta seção, o palestrante discute o Pthreads, uma biblioteca de funções que permite a simultaneidade na programação. O Pthreads fornece uma plataforma de simultaneidade do tipo faça você mesmo, pois permite que você especifique a simultaneidade em seu código usando uma biblioteca de funções com semântica especial. Cada thread em Pthreads implementa uma abstração de um processador e é multiplexada nos recursos reais da máquina. O Pthreads também fornece máscaras que simplificam os protocolos envolvidos na coordenação interna do thread. A biblioteca Pthreads tem funções-chave como pthread_create, que armazena e identifica o novo thread que pthread cria, e pthread_join, que espera até que o thread termine antes de continuar no código. O palestrante demonstra como implementar uma série de Fibonacci usando Pthreads.

  • 00:30:00 Nesta seção, o apresentador discute a implementação do código Pthreads para executar a sequência de Fibonacci em paralelo. Eles explicam que se o tamanho da entrada for pequeno o suficiente, é melhor executar o programa sequencialmente devido ao custo de criar threads em paralelo. O código empacota o argumento de entrada para o thread e o armazena na estrutura de argumentos. O apresentador discute Pthread create, Pthread join e algumas de suas desvantagens, como tornar-se muito mais complicado se o código precisar criar threads recursivamente. Eles também mencionam que esse código cria apenas um thread, portanto, a aceleração máxima possível é de dois, se executado em quatro processadores.

  • 00:35:00 Nesta seção do vídeo, são discutidos os problemas com Pthreads e o código para a sequência de Fibonacci. A alta sobrecarga para criar um thread resulta em simultaneidade grosseira, e o problema de escalabilidade é que os dois núcleos não estão fazendo a mesma quantidade de trabalho. O código também carece de modularidade, pois a lógica de Fibonacci não é encapsulada de maneira adequada em uma função, dificultando sua manutenção e alteração. O código também se torna complicado devido ao empacotamento de argumentos, que é semelhante a escrever código em assembly. O vídeo apresenta o Threading Building Blocks (TBB), uma biblioteca desenvolvida pela Intel para fornecer uma solução para esses problemas.

  • 00:40:00 Nesta seção, o vídeo discute o uso da biblioteca Intel Thread Building Blocks (TBB), uma biblioteca C++ projetada para permitir que os programadores usem threads nativos e um algoritmo de roubo de trabalho sem ter que lidar diretamente com threads. Ao especificar as tarefas, o TBB faz o balanceamento de carga entre as threads, tornando o código mais simples de escrever e com melhor desempenho do que usando threads POSIX. O vídeo mostra um exemplo de implementação de um programa Fibonacci usando TBB, demonstrando como ele cria recursivamente tarefas filhas, permitindo mais paralelismo e escalabilidade em vários processadores. O TBB também fornece modelos para paralelismo de loop, agregação de dados e pipelining de software, bem como classes de contêiner simultâneas para acesso simultâneo seguro a dados compartilhados.

  • 00:45:00 Nesta seção, o palestrante apresenta duas soluções linguísticas para o problema de concorrência: OpenMP e Silk. OpenMP é uma especificação que fornece extensões linguísticas para C e C++, bem como Fortran, usando pragmas de compilador para especificar quais partes do código devem ser executadas em paralelo. Ele suporta paralelismo de loop, paralelismo de tarefa e paralelismo de pipeline e possui muitas diretivas de agendamento e compartilhamento de dados, bem como construções de sincronização. O palestrante fornece um exemplo de implementação de Fibonacci no OpenMP, que é mais simples e tem melhor desempenho do que usar Pthreads ou TBB. O OpenMP é uma solução popular para escrever programas paralelos, pois fornece muitos recursos e simplifica o código.

  • 00:50:00 Nesta seção, o palestrante discute a plataforma de programação silk, que suporta paralelismo de vetores e conjuntos e inclui um agendador de roubo de trabalho comprovadamente eficiente. O programa também possui uma biblioteca de hiperobjetos para paralelizar o código com variáveis globais e vem com ferramentas de programação como um detector de corrida de tela de seda e um analisador de escalabilidade chamado silk view. O palestrante também observa que, embora não usem o silk plus na aula, eles usarão um compilador melhor conhecido como taper LLVM, que produz um código melhor em relação ao seu compilador base do que todas as outras implementações do silk existentes.

  • 00:55:00 Nesta seção, o uso de instruções silk spawn e silk sync para habilitar a execução paralela é discutido por meio de exemplos. O primeiro exemplo é o salt coat para Fibonacci, que inclui instruções de silk spawn e silk sync para sugerir que fib de n-1 pode ser executado em paralelo com a função que o chama enquanto fib de n-2 está sendo executado. No entanto, o sistema de tempo de execução decide se deve ou não executar essas tarefas em paralelo. Outro exemplo discutido é o paralelismo de loop, onde a instrução silk for é usada para executar um loop for em paralelo com o compilador dividindo recursivamente o espaço de iteração ao meio e usando as instruções silk spawn e silk sync até que o intervalo se torne muito pequeno para executar em paralelo. É importante garantir que as iterações sejam independentes para obter resultados corretos e usar silk para adicionar algumas despesas adicionais.

  • 01:00:00 Nesta seção, o vídeo discute o uso de loops for silk aninhados e os detalhes da geração de código assembly usando um sinalizador no compilador clang. O código de exemplo para uma soma de valores usando um loop silk for levanta a questão da corrida de determinação quando vários processadores gravam no mesmo local de memória. O Silk resolve esse problema por meio do uso de redutores, que são hiperobjetos que manipulam a função de adição para uma determinada variável, enquanto registram e cancelam o registro das macros redutoras. Esta é uma forma de lidar com o problema de redução, que pode surgir na programação multicore, com muitos outros operadores de redução também disponíveis para uso.

  • 01:05:00 Nesta seção, o palestrante discute redutores em Silk - estruturas algébricas que possuem uma operação binária associativa e um elemento identidade. O Silk tem vários redutores predefinidos, incluindo adição, multiplicação, min, max e XOR, e você pode definir seu próprio redutor. Um dos benefícios do Silk é que sempre há uma interpretação serial válida do programa, facilitando a depuração, e possui um agendador de tempo de execução que monitora e mapeia o programa nos núcleos do processador disponíveis, usando um algoritmo de agendamento de roubo de trabalho para equilibrar as tarefas uniformemente. Ao contrário de outras plataformas de simultaneidade, o agendador do Silk é teoricamente eficiente.

  • 01:10:00 Nesta seção, o palestrante fornece uma visão geral de alto nível do ecossistema Silk para programação multicore, incluindo como compilar o código-fonte Silk, comparar o desempenho paralelo e serial e depurar problemas usando ferramentas como o silk higiener e o silk escala. Eles também enfatizam a importância de otimizar o desempenho do programa serial e como o agendador do Silk pode lidar com diferentes tarefas durante a execução do programa. Além disso, o palestrante explica como a escala de seda pode determinar o número máximo de processadores que um código pode aproveitar, tornando-se uma ferramenta útil para analisar a escalabilidade.

  • 01:15:00 Nesta seção, o palestrante resume as principais conclusões da palestra sobre programação multicore. Eles explicam que a maioria dos processadores modernos possui vários núcleos, tornando necessário escrever programas paralelos para alto desempenho. No entanto, escrever esses programas pode ser difícil, e é aí que entra o Silk. Essa ferramenta abstrai os núcleos do processador do programador e lida com sincronização, protocolos de comunicação e balanceamento de carga. O palestrante também menciona um projeto futuro em que os alunos implementarão seu próprio protetor de tela paralelo usando o Silk.
 

Aula 7. Raças e Paralelismo



Aula 7. Raças e Paralelismo

O vídeo cobre uma variedade de tópicos relacionados a raças, paralelismo e dags de computação na programação Silk. Alguns dos principais conceitos abordados incluem as instruções de geração e sincronização para execução simultânea, a importância de evitar condições de corrida e o uso do detector de corrida do Silk para identificá-las. O vídeo também aborda a lei de Amdahl, a lei do trabalho e a lei do span como formas de quantificar a quantidade de paralelismo em um programa, junto com maneiras de analisar o trabalho e o alcance dos cálculos. O potencial de aceleração e paralelismo dos algoritmos de ordenação paralela e o conceito de teoria do escalonamento também são discutidos, com foco no teorema do escalonador guloso. No geral, o vídeo fornece informações valiosas para entender e otimizar o desempenho do programa na programação Silk.

O vídeo explica os corolários do limite do escalonador ganancioso, que essencialmente afirma que qualquer escalonador ganancioso atinge uma aceleração linear quase perfeita, desde que T1/Tinfinity seja maior ou igual a P^2. O agendador de seda, que usa um agendador de roubo de trabalho, pode atingir uma aceleração linear quase perfeita, desde que o número de processadores seja muito menor que T1/Tinfinity. O sistema silk runtime funciona mantendo uma plataforma de trabalho de fios prontos e manipula a parte inferior da plataforma como uma pilha. O vídeo também discute o Cactus Stack, que permite múltiplas visualizações de pilhas em paralelo e possibilita chamadas de funções paralelas. O limite superior do espaço de pilha exigido pela execução do processador P é geralmente muito mais flexível do que a quantidade real necessária, pois cada processador pode não precisar percorrer todo o caminho do gráfico de computação toda vez que rouba trabalho.

  • 00:00:00 Nesta seção, o instrutor apresenta o tópico de corridas e paralelismo no Silk, que será importante para o próximo projeto e tarefa de casa. Os fundamentos das instruções de spawn e sincronização do Silk são revistos, o que permite a execução simultânea de funções pai e filho. O instrutor também enfatiza a importância de se reunir com os membros da política do MIT e evitar condições de corrida no código, o que pode levar a consequências desastrosas, como visto em exemplos anteriores. Os bugs de corrida mais difíceis de encontrar são aqueles que causaram eventos catastróficos, e os testes convencionais geralmente não são eficazes. O Silk oferece uma ferramenta para ajudar a identificar possíveis erros de corrida no código.

  • 00:05:00 Nesta seção, o vídeo explica como as corridas são um dos bugs mais desafiadores para os desenvolvedores encontrarem porque podem ocorrer apenas em eventos raros quando códigos logicamente paralelos acessam o mesmo local de memória e pelo menos um registra uma gravação para isso. Como exemplo, o vídeo demonstra um código simples que utiliza um gráfico de dependência para mostrar como o bug de corrida compartilhado entre dois caminhos paralelos nem sempre ocorre. A corrida acontece quando ambos os armazenamentos gravam no mesmo local de memória, o que pode resultar em saídas diferentes, dependendo de qual caminho de execução é executado inteiramente primeiro.

  • 00:10:00 Nesta seção, o palestrante explica o conceito de corridas de determinação, que ocorrem quando duas instruções acessam o mesmo local de memória e pelo menos uma das instruções é uma operação de escrita, resultando em um comportamento não determinístico no programa. O palestrante dá dicas sobre como evitar corridas, como garantir que as iterações de um Silk for-loop sejam independentes e garantir que o código entre uma instrução de spawn do Silk e a instrução de sincronização do Silk correspondente também seja independente. O palestrante também observa que o tamanho da palavra da máquina é importante e deve-se tomar cuidado ao ler e gravar em estruturas de dados compactados que usam tipos não padronizados.

  • 00:15:00 Nesta seção, o vídeo discute o "detector de corrida" da plataforma Silk, que pode ajudar a identificar possíveis condições de corrida em um programa. Ao usar o sinalizador '-f higienizado igual ao silk' para gerar um programa instrumentado, o Silk pode relatar e localizar raças ofensivas, o que ajuda a depurar o código. O vídeo também explica o conceito de paralelismo e como o modelo de execução Silk usa gráficos de computação para ilustrar o desdobramento da computação durante a execução. É importante entender esses conceitos ao tentar otimizar e melhorar o desempenho do programa.

  • 00:20:00 tipos de vértices no dag de computação: o fio inicial, os fios de continuação, os fios de chamada de função e os fios finais. A vertente inicial contém a primeira instrução a ser executada, e a vertente final contém a última instrução executada no programa. As vertentes de continuação representam a continuação de uma operação de spawn, enquanto as vertentes de chamada de função representam a execução de uma chamada de função. É importante observar que o dag de computação se desdobra dinamicamente durante a execução e é alheio ao processador, o que significa que o sistema de tempo de execução descobre como mapear tarefas para processadores em tempo de execução. Em resumo, o dag de computação é uma ferramenta poderosa para entender o paralelismo e a simultaneidade de um programa.

  • 00:25:00 Nesta seção, aprendemos sobre computação dags e como eles podem ser usados para analisar o paralelismo em um programa. O dag de computação representa as dependências entre diferentes partes do programa e tem diferentes tipos de arestas, incluindo arestas de spawn, arestas de chamada, arestas de retorno e arestas de continuação. É possível usar dags de computação para analisar quanto paralelismo existe em um programa, e usamos a lei de Amdahl para quantificar a quantidade de paralelismo. No exemplo fornecido, há menos de sete nós que precisam ser executados sequencialmente, indicando que existe algum grau de paralelismo na computação.

  • 00:30:00 Nesta seção, o conceito da Lei de Amdahl é introduzido como uma forma de determinar a máxima aceleração possível no processamento paralelo. É determinado que a fração serial do programa é 3/18, resultando em uma aceleração máxima de 6. Embora a Lei de Amdahl forneça um limite superior para o paralelismo, muitas vezes ela é muito flexível em casos práticos. A lei do trabalho e a lei do span são introduzidas como definições alternativas de paralelismo, com a lei do trabalho afirmando que o tempo de execução nos processadores P é maior ou igual ao trabalho do programa dividido por P, e a lei do span afirmando que o tempo de execução em processadores P é pelo menos o tempo de execução em um número infinito de processadores. Essas leis fornecem melhores limites superiores na aceleração máxima do que a Lei de Amdahl em muitos casos.

  • 00:35:00 Nesta seção, o palestrante discute como compor o trabalho e abranger quantidades de diferentes cálculos. Eles explicam que ao executar duas computações paralelas, o trabalho ainda é a soma do trabalho das computações individuais, e o span é o máximo do span das computações individuais. O palestrante também define o aumento de velocidade nos processadores P e discute o aumento de velocidade sublinear, linear e superlinear. Eles observam que a máxima aceleração possível é igual ao paralelismo da computação, que é igual à quantidade média de trabalho por etapa ao longo da computação. No geral, esta seção fornece informações sobre a composição de cálculos e como medir seu paralelismo.

  • 00:40:00 Nesta seção, o palestrante discute como analisar o trabalho e o alcance das computações para calcular o paralelismo máximo, usando exemplos como um DAG de computação e um algoritmo Quicksort paralelo. O palestrante apresenta o analisador de escalabilidade Silk Scale, que usa instrumentação de compilador para analisar a execução serial de um programa e derivar limites superiores na aceleração paralela do programa. O palestrante também menciona que analisar manualmente o paralelismo de grandes cálculos pode ser tedioso, mas o Silk Scale pode ajudar nisso.

  • 00:45:00 Nesta seção, o vídeo discute os resultados da execução de um cálculo paralelo e da geração de um gráfico que mostra a aceleração observada, bem como os limites do vão e as leis de trabalho. O gráfico mostra que a aceleração máxima é de cerca de 5, indicando que o paralelismo no programa é baixo. A análise revela que o gargalo para o paralelismo é executar a função de partição sequencialmente, e o trabalho esperado e o span da versão paralela do quicksort é da ordem de n log n. O paralelismo máximo que pode ser alcançado é da ordem de log log n, que não é muito alto. Para aumentar o paralelismo, a função de partição deve ser paralelizada.

  • 00:50:00 Nesta seção, o palestrante discute a importância de implementar o paralelismo em algoritmos de classificação de partição e mesclagem para obter uma aceleração significativa. Versões paralelas desses algoritmos têm um span geral limitado com log ao quadrado n e um alto paralelismo de n sobre log n. Além disso, existem muitos outros algoritmos paralelos práticos por aí que possuem alto paralelismo e um limite de trabalho assintoticamente igual ao do algoritmo sequencial correspondente. O palestrante também apresenta o conceito de teoria do escalonamento, explicando que um escalonador centralizado pode mapear DAGs de computação em processadores disponíveis em tempo de execução, enquanto um escalonador distribuído é usado na programação Silk. Um escalonador guloso, que faz o máximo possível em cada etapa da computação, é usado como exemplo.

  • 00:55:00 Nesta seção, é apresentado o conceito de escalonador guloso, que realiza o máximo de trabalho possível no intervalo de tempo atual sem pensar no futuro. Uma etapa completa, onde pelo menos P vertentes estão prontas, e uma etapa incompleta, onde menos de P vertentes estão prontas, são definidas. O famoso teorema, mostrado pela primeira vez por Ron Graham em 1968, afirma que o limite de tempo alcançado por um escalonador ganancioso é menor ou igual a T1/P + T infinito, com T1 sendo o trabalho e T infinito sendo o span. A prova para este teorema é fornecida e é mostrado que qualquer escalonador ganancioso atinge dentro de um fator de dois o tempo de execução ideal.

  • 01:00:00 Nesta seção, o vídeo explica os corolários do limite do escalonador guloso, que atinge um fator de dois do escalonador ideal. O corolário afirma que qualquer escalonador ganancioso alcança velocidade linear quase perfeita quando T1/Tinfinity é maior ou igual a P^2, onde T1/P vezes T infinito mede a quantidade de paralelismo na computação em comparação com o número de processadores disponível. O escalonador silk usa um escalonador de roubo de trabalho, que tem um tempo de execução esperado de TP igual a T1/P mais ordem T infinito, com um Big O na frente do T infinito para contabilizar as despesas gerais de escalonamento e pode atingir quase aceleração linear perfeita desde que o número de processadores seja muito menor que T1/Tinfinity. O sistema silk runtime funciona mantendo uma plataforma de trabalho de fios prontos e manipula a parte inferior da plataforma como uma pilha. A instrumentação no Silk Scale permite medir termos de trabalho e vão para determinar o paralelismo no programa.

  • 01:05:00 Nesta seção, o palestrante discute o conceito de geração e paralelismo em processadores. Eles explicam que quando um processador chama uma função, ele coloca o quadro dessa função no final de sua pilha e pode gerar quadros no final da pilha. Vários processos podem ocorrer em paralelo e os retornos podem ser feitos a partir de spawns e chamadas. Quando os trabalhadores ficam sem trabalho para fazer, eles roubam do topo do convés de outro processador. O famoso teorema afirma que os trabalhadores roubam muito raramente, dando uma aceleração quase linear. O palestrante também observa que o Silk suporta as regras de C para ponteiros, onde um ponteiro para um espaço de pilha pode ser passado de um pai para um filho, mas não de um filho para um pai.

  • 01:10:00 Nesta seção do vídeo, o palestrante discute o Cactus Stack, que é a pilha que pode ser vista por uma tarefa no gráfico de computação ancestral de um programa Silk. Essa pilha permite várias exibições de pilhas em paralelo, o que possibilita chamadas de funções paralelas. O palestrante explica que o espaço de pilha necessário para um programa Silk pode ser encontrado tomando o espaço de pilha necessário para uma execução serial do programa (S sub 1) e multiplicando-o pelo número de processadores (P) que serão usados (S sub P ≤ P x S sub 1). O palestrante fornece uma prova de alto nível desse conceito e observa que o limite superior no espaço de pilha exigido pela execução do processador P é geralmente muito mais flexível do que a quantidade real necessária, pois cada processador pode não precisar percorrer todo o gráfico de computação a cada tempo que rouba trabalho.
1...222324252627282930313233343536...74
Novo comentário
Razão: