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

Novo comentário
 

Aula 8. Análise de Algoritmos Multithreaded



Aula 8. Análise de Algoritmos Multithreaded

Este vídeo discute o método principal para analisar recorrências de divisão e conquista e o aplica a algoritmos multithread comparando log base B de n com log base B de A com F de N para determinar seu crescimento em n e o trabalho necessário. O vídeo apresenta uma folha de dicas com soluções para algoritmos multithread básicos e aborda tópicos como análise de trabalho e extensão, eficiência do trabalho e superação de custos indiretos por meio da otimização do tamanho do grão. A importância da empatia ao comunicar tópicos técnicos é enfatizada, e o conceito de um DAG é apresentado como um meio de equilibrar trabalho e abrangência para aumentar o paralelismo e diminuir o tempo de execução.

O vídeo também discute a análise de algoritmos multithread, com foco no trabalho e no span, e como maximizar o paralelismo enquanto minimiza o span para atingir uma aceleração linear quase perfeita. O palestrante sugere uma abordagem de divisão e conquista para algoritmos multiencadeados, em que o número de tarefas atribuídas aos encadeamentos é suficientemente grande e adverte contra o surgimento de várias tarefas pequenas devido a sobrecargas de agendamento. O código de exemplo apresentado inclui um eficiente e um péssimo. O palestrante também discute como representar submatrizes em codificação e indexação bidimensionais e enfatiza o uso de 'restringir' no código de multiplicação de matrizes de divisão e conquista para melhorar o desempenho.

  • 00:00:00 Nesta seção, o instrutor começa lembrando aos alunos sobre as recorrências de divisão e conquista e o método geral para resolvê-las chamado de método principal. O método lida com recorrências e sua forma T(n) = a*T(n/B) + F(n), onde a é uma constante, B é o fator de divisão e F(n) é a quantidade total de trabalho para dividir o problema em subproblemas de tamanho n/B. Os alunos são lembrados da árvore de recursão e como cada nível se divide em subproblemas de tamanho n/B, eles adicionam o tempo de execução nas linhas, calculam a altura da árvore e a multiplicam pelo número de subproblemas em cada nível (um ^k). Finalmente, os alunos calculam que n^log base B de A é o tempo total de execução do algoritmo.

  • 00:05:00 Nesta seção, o palestrante explica como determinar o crescimento em n e o trabalho necessário ao avaliar algoritmos multithread. A chave é comparar log base B de n com log base B de A com F de N. O palestrante cobre três casos possíveis, sendo o primeiro quando log base B n é muito maior que F de n. Nesse caso, a fração constante do peso está nas folhas, fazendo com que a resposta seja n elevado a log base B de A. O segundo caso é quando log base B n é aproximadamente igual a F de n. Para isso, você adiciona uma tora extra, e a resposta é n elevado à base B de uma tora elevada a k mais 1 de n. Por último, o terceiro caso é quando um to log base B é muito menor que F de N, o que significa que F tem que satisfazer uma condição de regularidade, que é satisfeita por todas as funções que eles estarão olhando como polinômios e logaritmos.

  • 00:10:00 Nesta seção, o palestrante apresenta uma folha de dicas com soluções básicas de algoritmos multithread que são comumente usados em ciência da computação. O primeiro algoritmo, T(n) = T(n/2) + n, tem uma solução de Θ(n^2) pois se enquadra no caso um. O segundo algoritmo, T(n) = T(n/2) + n^2logn, tem uma solução de Θ(n^2logn), pois se enquadra no caso dois com k = 0. Para o terceiro algoritmo, T(n) = T(n/2) + n^2, a solução é Θ(n^2) pois se enquadra no caso um. O quarto algoritmo, T(n) = 2T(n/2) - n, é complicado, pois não se enquadra em nenhum caso do método mestre e tem uma solução de Θ(n^2loglogn).

  • 00:15:00 Nesta seção, o palestrante discute o método Aqua Bazi e como ele é mais complicado do que o método mestre, que é suficiente para analisar a maioria dos programas. Eles então fornecem um exemplo de um loop paralelo com código de transposição de matriz no local, onde o loop externo é paralelizado. O palestrante enfatiza a importância de definir corretamente o espaço de iteração e o balanceamento de carga para um processamento paralelo eficiente. Eles também explicam como os loops são implementados pelo compilador open silk e pelo sistema de tempo de execução.

  • 00:20:00 Nesta seção, o palestrante descreve um programa recursivo para um loop que utiliza dividir e conquistar para dividir o loop em duas partes e se chamar recursivamente em cada lado até atingir uma iteração de um elemento. O trabalho desta computação é analisado em termos de trabalho e extensão, com o trabalho da folha sendo da ordem n ao quadrado e a parte superior sendo theta n porque cada nível das folhas até a raiz tem apenas n nós. O sistema open silk runtime não tem um primitivo de loop, portanto, os loops são efetivamente traduzidos nessa abordagem de dividir e conquistar em paralelo.

  • 00:25:00 Nesta seção, o palestrante discute o trabalho e a análise de span de um algoritmo multithread. Ele explica que o trabalho total é Θ(n²) porque o trabalho constante é feito para cada uma das n folhas da árvore binária completa. A extensão do controle do loop é log(n), o que significa que um número infinito de processadores pode concluir a tarefa em tempo logarítmico. No entanto, como há um componente linear no cálculo (n), o vão total é Θ(n). Portanto, o paralelismo é Θ(n), que é uma boa quantidade para a maioria dos sistemas práticos. O palestrante então explora o cenário no qual o loop interno também é paralelizado e discute a quantidade de trabalho resultante.

  • 00:30:00 Nesta seção do vídeo, o professor discute o conceito de eficiência do trabalho em algoritmos paralelos. Os algoritmos de paralelização não alteram o trabalho, mas devem reduzir a extensão do cálculo para alcançar um grande paralelismo. No entanto, às vezes, a paralelização pode resultar na adição de mais trabalho, o que pode ser problemático porque torna o programa mais lento em comparação com o algoritmo original. Algoritmos paralelos com eficiência de trabalho são o que o professor está interessado em ensinar, pois são capazes de reduzir o intervalo para obter grande paralelismo sem adicionar mais trabalho. O professor enfatiza a importância de fazer perguntas e errar no processo de aprendizagem, pois pode ajudar outras pessoas que podem ter as mesmas dúvidas, mas têm medo de perguntar. Ele incentiva os alunos a participar e se envolver no processo de aprendizagem, mesmo que não estejam entre os 10% melhores.

  • 00:35:00 Nesta seção, é enfatizada a importância da empatia na comunicação quando se trata de assuntos técnicos. O professor incentiva os alunos a serem pacientes com outras pessoas da classe que podem não estar familiarizadas com o material que está sendo abordado. Passando para a análise de algoritmos multithreaded, um algoritmo de divisão e conquista para adição de vetores é apresentado, e o paralelismo encontrado é n sobre log n. A relação entre paralelismo e o número de processadores é discutida, com o professor enfatizando que, embora mais paralelismo possa parecer melhor, ele só é benéfico até certo limite.

  • 00:40:00 Nesta seção, o palestrante discute a otimização de parte da sobrecarga em um algoritmo multithread, especificamente a sobrecarga de chamada de sub-rotina. Eles introduzem o conceito de "tamanho do grão", que sugere ao compilador que haja até G elementos por bloco nas folhas do processo de divisão e conquista. Isso permite que a sobrecarga da sub-rotina seja amortizada em G iterações em vez de apenas uma, resultando em melhor desempenho. Se o tamanho do grão não for especificado, o sistema fará sua melhor estimativa para minimizar a sobrecarga. O palestrante divide as variáveis I, G e s para analisar o trabalho neste contexto e o compara com o trabalho no código original sem o material de controle paralelo.

  • 00:45:00 Nesta seção, o palestrante fala sobre a análise de algoritmos multithread e como o controle de loop é barato em um processador moderno fora de ordem. Eles analisam o span, que é o tempo necessário para executar o algoritmo com um número infinito de processadores, e discutem o custo indireto versus o custo das iterações. O orador divide o vão em termos do número de folhas e das operações coloridas, referidas como 's', que precisam ser realizadas em cada uma delas. Eles também respondem a perguntas sobre o número de nós internos em uma árvore binária completa e os caminhos percorridos para calcular o intervalo.

  • 00:50:00 Nesta seção, o palestrante discute a análise de algoritmos multithreaded, particularmente o conceito de um DAG (gráfico acíclico direcionado) e como isso afeta o caminho do algoritmo. Eles enfatizam a necessidade de independência entre diferentes subárvores do DAG para permitir o processamento paralelo. O objetivo é equilibrar o trabalho e o alcance do algoritmo, pois esses dois fatores funcionam em direções opostas. A chave é fazer com que G (a quantidade de paralelismo) seja muito maior que s sobre I (a parte sequencial do algoritmo), o que permite uma sobrecarga menor e um processamento mais rápido. O palestrante também menciona uma implementação desse conceito, mas observa que será discutido posteriormente na série de palestras.

  • 00:55:00 Nesta seção, o palestrante apresenta uma implementação de algoritmos multithread usando um loop for para adicionar dois vetores. O loop usa um operador chamado V add para executar a adição serial de vetores, e o loop gera adições em grupos de G usando um vetor de tamanho G. Assumindo que G é igual a um, o trabalho dos loops é de ordem n e o span também é ordem n. O paralelismo é medido tomando a razão do trabalho para o span, que é n dividido por n, que simplifica para 1. O palestrante enfatiza que o objetivo da análise de algoritmos multithreading é aumentar o paralelismo e diminuir o span para minimizar o tempo de execução e destaca a técnica chamado mineração de tira, onde um loop de comprimento N é substituído por um loop duplo aninhado para paralelizar computações, como uma forma de melhorar os algoritmos multithreaded.

  • 01:00:00 Nesta seção, o palestrante analisa o desempenho de algoritmos multithread em termos de trabalho e extensão. Eles discutem como minimizar o span para maximizar o paralelismo, já que o span está no denominador. A chave é gerar dez vezes mais paralelismo do que os processadores, se quisermos uma aceleração linear quase perfeita. O palestrante também sugere negociar algum paralelismo para reduzir a sobrecarga de trabalho, se necessário. Eles incentivam mexer no tamanho do grão para fazer isso, desde que o paralelismo suficiente seja mantido.

  • 01:05:00 Nesta seção, o palestrante discute o uso de estratégias de divisão e conquista em algoritmos multiencadeados, desaconselhando a geração de várias pequenas tarefas uma após a outra, a menos que sejam agrupadas em algumas tarefas, caso em que a sobrecarga está bem. Geralmente, deve haver uma abordagem de dividir e conquistar, onde o número de tarefas atribuídas aos threads é suficientemente grande. O palestrante adverte para cuidado com os overheads de agendamento e sugere paralelizar o loop externo em vez dos loops internos, que possuem mais overheads. Os códigos de exemplo apresentados aqui mostram um eficiente, onde o agendamento ocorre apenas uma vez, e um ruim, onde a sobrecarga ocorre n vezes. A multiplicação de matrizes é usada como um exemplo de um algoritmo multiencadeado usando uma estratégia de dividir e conquistar para multiplicar n por n matrizes fazendo 8 multiplicações de n sobre 2 por n sobre 2 matrizes e, em seguida, adicionando duas matrizes n por n.

  • 01:10:00 Nesta seção, o palestrante discute como representar submatrizes em codificação e indexação bidimensionais, particularmente em ordem de linha principal e ordem de coluna principal para linguagens como C e Fortran. A ideia é que toda matriz bidimensional pode ser indexada como uma matriz unidimensional e, ao lidar com submatrizes, é preciso somar o número de linhas e o comprimento da matriz longa para saber onde está o elemento IJ. Além disso, ao implementar dividir e conquistar, é crucial conhecer os vértices iniciais de cada uma das quatro submatrizes. Por fim, o palestrante enfatiza o uso de 'restringir' no código de multiplicação da matriz de divisão e conquista para informar ao compilador quais elementos podem ou não ser aliasados.

  • 01:15:00 Nesta seção, o palestrante discute um algoritmo multithread para multiplicação de matrizes. O algoritmo é baseado na subdivisão recursiva das matrizes em submatrizes menores, sendo cada submatriz multiplicada recursivamente para obtenção do resultado final. O palestrante destaca um pequeno truque para determinar rapidamente se n é uma potência de dois e usa uma macro para simplificar a indexação das matrizes. O algoritmo exibe alto paralelismo, que pode ser reduzido para melhorar o desempenho. Outros algoritmos semelhantes também são mencionados.
 

Aula 9. O que os compiladores podem e não podem fazer



Aula 9. O que os compiladores podem e não podem fazer

Este vídeo discute como os compiladores podem otimizar o código, usando vários exemplos. Ele explica como os compiladores podem eliminar armazenamento desnecessário e referências de memória e como eles podem otimizar loops para melhorar o desempenho.

Este vídeo também explica o conceito de passes de otimização do compilador e como eles podem ser usados para melhorar o desempenho do código. Também discute as limitações dos compiladores, especificamente no que diz respeito à vetorização. Os compiladores só podem vetorizar o código se puderem determinar que os ponteiros no código não serão alias. Se os ponteiros fizerem alias, o compilador não conseguirá vetorizar o código. Como programador, você pode ajudar o compilador anotando seus ponteiros para fornecer mais informações sobre seu uso.

  • 00:00:00 Nesta palestra, Tao Schardl discute o que os compiladores podem ou não fazer. Ele explica que estudar as otimizações do compilador pode ajudar os desenvolvedores a entender como escrever código que tira proveito das otimizações e como evitar a otimização manual do código que o compilador já pode otimizar.

  • 00:05:00 O compilador é um grande pedaço de software e pode ajudar na depuração quando o próprio compilador tem bugs. Isso ajuda a entender onde o compilador pode ter cometido um erro ou onde o compilador simplesmente não fez o que você pensou que deveria ser capaz de fazer.

  • 00:10:00 O compilador pode fazer muitas otimizações, mas há algumas coisas que ele não pode fazer. Por exemplo, nem sempre pode criar um caminho rápido ou otimizar loops.

  • 00:15:00 O compilador pode fazer muito para otimizar o código, mas há algumas coisas que ele não pode fazer bem. Um exemplo são as estruturas de dados - o compilador não é inteligente sobre elas da mesma forma que sobre as funções. Outro são os loops - o compilador pode fazer algumas otimizações neles, mas há restrições.

  • 00:20:00 Este vídeo do YouTube explica como os compiladores podem usar operações simples para substituir as mais complexas. Por exemplo, para substituir uma operação de divisão, um compilador pode multiplicar por um número mágico e depois alterar o resultado. Este vídeo também explica como funciona a calculadora de endereço.

  • 00:25:00 O vídeo discute como os compiladores podem otimizar o código, usando uma função simples "vex scale" como exemplo. O código é mostrado primeiro sem otimizações e, em seguida, com várias otimizações aplicadas. As otimizações mostradas incluem a redução do número de instruções, o uso de instruções vetoriais e o uso de números mágicos.

  • 00:30:00 Este vídeo discute como os compiladores podem otimizar o código eliminando operações de memória desnecessárias. Em particular, mostra como um compilador pode otimizar uma função que multiplica dois valores escalares eliminando a necessidade de armazenar os valores na memória. Por fim, mostra como um compilador pode otimizar uma função que opera sobre uma estrutura eliminando a necessidade de armazenar a estrutura na memória.

  • 00:35:00 Neste vídeo do YouTube, o palestrante explica como os compiladores podem otimizar o código eliminando armazenamento desnecessário e referências de memória. Ele usa o exemplo de uma estrutura com vários campos e demonstra como o compilador pode otimizar o código analisando cuidadosamente a matemática envolvida nos cálculos de endereço. Ao entender o que cada instrução faz, o compilador pode otimizar o código e remover operações desnecessárias.

  • 00:40:00 O compilador trabalha duro para transformar estruturas de dados e valores escalares para armazenar o máximo que puder puramente dentro de registros e evitar o uso de qualquer armazenamento local, se possível. Para chamadas de função, o compilador vê a instrução de chamada e o código da função que está sendo chamada. Em seguida, ele tenta tornar a função no código acima ainda mais rápida.

  • 00:45:00 O compilador pode codificar em linha para evitar sobrecarga de chamada de função e também pode otimizar o código removendo operações desnecessárias.

  • 00:50:00 Neste vídeo do YouTube, o palestrante explica que há três razões principais pelas quais um compilador não pode incorporar uma função: se a função for recursiva, se a função estiver em uma unidade de compilação diferente ou se a função puder aumentar tamanho do código e prejudicar o desempenho. O palestrante também dá algumas dicas para controlar a função inlining em seus próprios programas.

  • 00:55:00 Este vídeo mostra como os compiladores podem otimizar loops para tornar os programas mais rápidos. A elevação de código, ou movimento de código invariável em loop, é uma otimização que pode ser usada para melhorar o desempenho.

  • 01:00:00 O compilador pode otimizar o código executando uma sequência de passagens de transformação. Esses passes são projetados para encontrar propriedades como cálculos de endereços idênticos e substituí-los por um código mais eficiente.

  • 01:05:00 O compilador é capaz de vetorizar este loop, apesar de não saber se os endereços de 'x' e 'y' se sobrepõem. Isso ocorre porque a estrutura do código compilado é mais complicada do que a função de duas linhas fornecida como entrada.

  • 01:10:00 Este vídeo do YouTube explica o que os compiladores podem ou não fazer. Os compiladores podem vetorizar o código se o código não contiver nenhum loop. No entanto, se o código contiver loops, o compilador só poderá vetorizar o código se o loop estiver cheio de operações vetoriais. Se o loop não estiver cheio de operações vetoriais, o compilador não poderá vetorizar o código.

  • 01:15:00 A questão se um compilador pode ou não vetorizar código é difícil, pois depende de vários fatores. Em particular, o compilador precisa ser capaz de determinar se dois ponteiros serão ou não alias, o que pode ser uma tarefa difícil. Como programador, você pode ajudar o compilador anotando seus ponteiros para fornecer mais informações sobre seu uso.
 

Aula 10. Medição e Cronometragem



Aula 10. Medição e Cronometragem

Neste vídeo, os palestrantes discutem vários aspectos de medição e temporização na computação, incluindo fatores externos que podem afetar a precisão. Eles enfatizam a necessidade de modelos e compreensão clara dos dados, reduzindo a variação para compensar erros e usando chamadas de tempo adequadas para garantir a confiabilidade. Eles também discutem os desafios de medir o desempenho do software com precisão, como a lei de potência e fatores não determinísticos, enquanto destacam ferramentas como modelagem de desempenho, chamadas de tempo, contadores de hardware e simuladores. Por fim, eles alertam contra a dependência de uma única ferramenta, recomendando a triangulação e a adaptação como técnicas para garantir resultados precisos.

O palestrante explica a importância da medição de desempenho confiável na engenharia de software de desempenho. Ele recomenda o uso de estatísticas para medir o desempenho com precisão e discute vários tipos de estatísticas resumidas, como a média, que podem fornecer medidas úteis de desempenho em diferentes contextos. Ele aponta que tomar a média aritmética das razões não é uma abordagem válida e sugere o uso da média geométrica. O palestrante enfatiza a importância de escolher a maneira correta de agregar dados ao comparar programas e sugere usar a estatística de ordem inferior, como o mínimo ou 10%, de várias execuções para comparar o desempenho com mais precisão. O palestrante também discute diferentes metodologias para medir e comparar desempenho, incluindo comparação frente a frente e ajuste de um modelo para derivar estatísticas, mas adverte sobre a questão do ajuste excessivo na modelagem. No geral, o vídeo enfatiza a importância da medição de desempenho confiável para melhorar o desempenho do programa.

  • 00:00:00 Nesta seção, o palestrante discute um estudo sobre código de ordenação feito por um de seus ex-alunos. O código usa o arquivo de cabeçalho time.h para obter acesso à rotina de obtenção de hora do relógio para medições de tempo. Uma rotina de classificação é cronometrada e o tempo decorrido é calculado e impresso. O gráfico dos tempos de execução medidos mostra que a rotina de classificação segue principalmente um crescimento N log N, mas os tempos medidos são lentos mesmo para as matrizes maiores.

  • 00:05:00 Nesta seção, um professor discute a importância de ter um modelo para os dados que estão sendo observados. Ele apresenta um exemplo em que os dados medidos divergem significativamente do que era esperado e pede aos alunos que sugiram possíveis hipóteses para esse desvio. Embora alguns pensem que pode ser um problema com o cache ou a precisão do tempo, o professor aponta que pode haver processos não relacionados em execução na máquina que estão causando o desvio. Nesse caso, o problema é de multilocação, onde a máquina está sendo usada por mais de um processo simultaneamente. O professor enfatiza a necessidade de medições de qualidade e ter uma compreensão clara do que os dados significam.

  • 00:10:00 Nesta seção, os palestrantes discutem medição e tempo na computação e como fatores externos podem afetar a precisão das medições. Eles se concentram especificamente em como as mudanças na frequência do relógio podem ocorrer devido à temperatura do sistema e às técnicas de economia de energia, que podem afetar significativamente os resultados da medição. Os alto-falantes introduzem o conceito de escala dinâmica de frequência e tensão, que é uma técnica para reduzir a potência ajustando a frequência do clock e a tensão dos transistores. Eles enfatizam que é crucial considerar fatores externos ao fazer medições para evitar resultados imprecisos.

  • 00:15:00 Nesta seção, o palestrante discute os desafios de medir o desempenho do software devido à lei de potência que os engenheiros elétricos usam. A lei de potência afirma que a potência é igual a CV ao quadrado F, onde C é a capacitância dinâmica, V é a tensão de alimentação e F é a frequência do clock. Para reduzir a potência e o calor, pode-se reduzir a frequência e a tensão, resultando em uma redução cúbica da potência. Isso representa um desafio para medir o desempenho do software de forma confiável, e o palestrante sugere desativar os sistemas eliminando parte do ruído para fazer medições precisas. Eles também discutem ferramentas para medir o desempenho do software, como modelagem de desempenho.

  • 00:20:00 Nesta seção, o palestrante discute a importância de reduzir a variação quando se trata de medição e tempo, especialmente no contexto da engenharia de desempenho. Ao reduzir a variabilidade, é possível compensar erros de medição sistemáticos e aleatórios e exigir menos tentativas para comparar programas. O palestrante também aponta várias fontes de variabilidade em sistemas de computador, incluindo trabalhos em segundo plano, interrupções e posicionamento de threads, entre outros. Por fim, ele enfatiza a importância de se concentrar primeiro na redução da variação antes de tentar fazer alterações no sistema, pois a medição durante alta variação pode levar a resultados não confiáveis.

  • 00:25:00 Nesta seção, o palestrante fala sobre o conceito de hyper-threading em processadores e como isso pode levar a medições imprecisas em sistemas em nuvem. O hyper-threading executa dois fluxos de instruções por meio de uma unidade funcional, parecendo dois processadores, mas na verdade fornece apenas uma aceleração de 20% em vez de dois processadores separados. O palestrante também discute outras técnicas, como turbo boost e desativação de um sistema, que podem afetar significativamente os resultados da medição. Ao desativar o hyper-threading e o turbo boost e silenciar todos os demônios, o palestrante e seu grupo conseguiram obter medições notavelmente confiáveis, menos de 1% mais lentas do que o tempo de execução mínimo.

  • 00:30:00 Nesta seção, o palestrante fala sobre vários fatores que podem afetar o determinismo de um programa executado em hardware moderno. Embora existam certas medidas que podem ser tomadas para tornar o programa mais determinístico, é impossível eliminar completamente os fatores não determinísticos. A maioria dos fatores não determinísticos que podem surgir durante a execução do programa, como cache, interrupções, encadeamento e previsão de ramificação, são processos determinísticos. No entanto, a aleatoriedade no hardware está fora do controle do usuário e pode resultar em um erro de memória. O palestrante sugere que o alinhamento do código pode fazer diferença no determinismo do programa, e qualquer alteração feita no código pode causar uma mudança no alinhamento do cache, afetando o determinismo do programa.

  • 00:35:00 Nesta seção, o palestrante discute como pequenas mudanças podem ter um grande impacto no desempenho de um programa. Por exemplo, inserir um byte pode fazer com que tudo depois dele seja impactado linearmente, e alterar a ordem na qual os arquivos dot o aparecem na linha de comando do vinculador pode ter um efeito maior do que alternar entre -OH- e -O3. Para resolver esses problemas, os compiladores estão reconhecendo o problema e fazendo mais alinhamento. O LLVM possui switches que podem alinhar todas as funções e blocos em uma função, mas o alinhamento pode tornar o programa mais lento. Além disso, o nome do programa pode afetar sua velocidade, pois o nome do executável acaba em uma variável de ambiente que acaba na pilha de chamadas.

  • 00:40:00 Nesta seção, o palestrante discute várias ferramentas e métodos para medir o desempenho do software, incluindo medir o programa externamente com o comando time, colocar chamadas de tempo no programa usando clock get time ou outros métodos, interromper o programa com gdb para identificar qual rotina está levando mais tempo, explorando o suporte de hardware e sistema operacional, como os usados no conjunto de ferramentas perf ou simulando o programa para obter uma compreensão mais profunda, mas em uma velocidade mais lenta. O palestrante explica a diferença entre o tempo decorrido, o tempo do usuário e o tempo do sistema ao usar o comando time e como eles podem não somar ao tempo total devido à alocação do processador.

  • 00:45:00 Nesta seção, o palestrante discute os diferentes tipos de temporização e medição, incluindo tempo de relógio de parede, tempo do processador gasto no modo de usuário e tempo gasto no kernel. A chamada de tempo recomendada para uso é clock get time com a opção clock monotonic que garante nunca correr para trás. Embora possa levar uma quantidade de tempo não determinística para ser executado, é mais confiável do que outros cronômetros, como RTIDTSC, que podem fornecer respostas diferentes em diferentes núcleos e podem ser executados ao contrário. O alto-falante adverte contra o uso da hora do dia.

  • 00:50:00 Nesta seção, o palestrante discute várias maneiras de medir e cronometrar eventos na programação, inclusive usando clock_gettime e medindo com o comando time. Eles alertam que, com o tempo, as técnicas podem mudar e os engenheiros podem precisar se adaptar. O palestrante também sugere interromper o código em momentos aleatórios como uma técnica simples de criação de perfil e menciona que grandes empresas como o Facebook usam esse método. Além disso, o palestrante apresenta a ideia de contadores de hardware e a biblioteca livepFM4, que permite o acesso a esses contadores por processo. Eles enfatizam que um engenheiro nem sempre precisa de ferramentas cirurgicamente precisas e que, às vezes, uma ferramenta simples pode ser suficiente para o trabalho.

  • 00:55:00 Nesta seção, o palestrante discute as diferentes formas de coleta de medições, incluindo contadores de hardware e simuladores. Eles advertem que muitos contadores de hardware são mal documentados e que algumas ferramentas compartilham a largura de banda se mais de quatro ou cinco contadores forem usados. Os simuladores são elogiados por sua repetibilidade, mas podem não modelar tudo no cache. O palestrante recomenda a triangulação e o uso de pelo menos duas medições para garantir a precisão. Eles também enfatizam a importância de ter um modelo de desempenho para orientar a interpretação dos dados.

  • 01:00:00 Nesta seção, o palestrante explica o processo de engenharia de software de desempenho, que envolve pegar um programa, fazer alterações nele e medir seu desempenho para produzir um programa mais rápido. No entanto, a medição de desempenho confiável é vital para fazer pequenas alterações que se somam e tirar conclusões com precisão. Portanto, o palestrante recomenda o uso de estatísticas para obter uma imagem precisa do que está acontecendo. Ele também oferece um quebra-cabeça envolvendo a medição do desempenho bruto de um programa determinístico e conclui que usar o mínimo é a melhor maneira de rejeitar o ruído e determinar o desempenho de hardware subjacente do programa.

  • 01:05:00 Nesta seção, vários tipos de estatísticas resumidas são discutidas, incluindo a média, que pode fornecer medidas úteis de desempenho em diferentes contextos. Ao avaliar servidores da Web, a utilização da CPU e o tempo total de conclusão da tarefa podem ser medidos usando a média aritmética, enquanto o tempo de relógio de parede e o comportamento do percentil podem ser mais relevantes para otimizar a satisfação da solicitação. No entanto, ao resumir razões, como comparar o desempenho dos programas A e B, tomar a média aritmética não é uma abordagem válida, embora seja comumente mal utilizada. Isso ocorre porque a média das razões não é a mesma que a própria razão, conforme ilustrado no exemplo dado no vídeo.

  • 01:10:00 Nesta seção, o palestrante discute os problemas de comparação de proporções e médias ao medir o desempenho. Eles demonstram que tirar a média aritmética das razões pode levar a resultados suspeitos, sendo melhor usar a média geométrica. Além disso, eles observam que, ao comparar taxas, a média harmônica costuma ser útil. A importância de escolher a maneira correta de agregar dados ao comparar programas é enfatizada, e o palestrante sugere usar a estatística de ordem inferior, como o mínimo ou 10%, de várias execuções para comparar o desempenho com mais precisão.

  • 01:15:00 Nesta seção, o palestrante discute diferentes metodologias para medir e comparar desempenho. Uma abordagem é comparar as opções 10% mais baratas e fazer redução de ruído para comparar as médias, embora possa não fornecer evidências conclusivas. Como alternativa, uma comparação direta pode ser realizada entre A e B para ver qual deles vence com mais frequência. Com isso, a hipótese nula pode ser testada e o valor-p pode ser calculado para determinar se o desvio é significativo. Este método é comumente usado em ciências sociais e pode ser útil em ambientes ruidosos. Por fim, o palestrante aborda brevemente a ideia de ajustar um modelo para derivar estatísticas e discute o uso da aproximação de mínimos quadrados.

  • 01:20:00 Nesta seção, o palestrante discute a questão do over-fitting na modelagem e como adicionar mais funções de base pode melhorar o ajuste dos dados, mas também levar ao over-fitting. A solução é remover uma função de base e verificar se ela afeta a qualidade do modelo. O palestrante também cita Lord Kelvin, conhecido como o Guru da medição, que afirmou que medir é saber e se não se pode medir, não se pode melhorar. O vídeo termina com o palestrante desejando sorte em um teste na terça-feira.
 

Aula 11. Alocação de Armazenamento



Aula 11. Alocação de armazenamento

O palestrante discute a alocação de armazenamento neste vídeo, abrangendo alocação e liberação de memória. Diferentes tipos de armazenamento são abordados, incluindo a pilha e o heap, bem como esquemas de alocação de tamanho fixo e variável. A fragmentação externa causada por blocos de memória espalhados também é discutida, com soluções como listas livres ou bitmaps por página de disco. O conceito de coleta de lixo também é introduzido, incluindo a contagem de referências e as limitações desse algoritmo. Os procedimentos de coleta de lixo "marcar e varrer" e "parar e copiar" também são explicados, com foco em como o último aborda a fragmentação e o possível problema de correção criado por atualizações de ponteiro. O vídeo termina com notas sobre a complexidade de tempo e espaço do algoritmo stop and copy e sua eliminação da fragmentação externa.

Este vídeo aborda vários tópicos relacionados à alocação dinâmica de armazenamento, incluindo o sistema Buddy, procedimentos de marcação e varredura, otimizações, coleta de lixo geracional e em tempo real, alocação de armazenamento multiencadeada e coleta de lixo paralela. O palestrante explica que a coleta de lixo geracional é baseada na ideia de que os objetos mais jovens são verificados com mais frequência, enquanto a coleta de lixo em tempo real é executada em segundo plano durante a execução do programa, mas pode levar a problemas de correção se o objeto e o gráfico do ponteiro continuarem mudando. Por fim, a palestra resume diferentes tipos de alocação de armazenamento, incluindo pilha e heap, e diferentes métodos de coleta de lixo, como contagem de referência, marcação e varredura e parada e cópia. O professor menciona que os alunos poderão experimentar alguns desses métodos em sua próxima tarefa de casa.

  • 00:00:00 Nesta seção, o palestrante discute a alocação de armazenamento, que inclui alocação e liberação de memória. A forma mais simples de armazenamento é uma pilha, onde a memória é alocada incrementando o ponteiro da pilha e liberada diminuindo o ponteiro da pilha. No entanto, a pilha tem aplicabilidade limitada porque só pode liberar a última coisa que foi alocada e não pode liberar nada no meio da região usada. O palestrante também observa que, por motivos de eficiência, o estouro de pilha geralmente não é verificado pelos compiladores.

  • 00:05:00 Nesta seção, o palestrante fala sobre dois tipos de armazenamento: a pilha e o heap. A pilha é um armazenamento de tamanho fixo que é eficiente, mas não pode ser usado para tudo, enquanto a pilha é mais geral, mas difícil de organizar e usar com eficiência. Para alocação de heap, funções malloc e free C podem ser usadas, mas como C e C++ não fornecem um coletor de lixo, os programadores precisam gerenciar a memória por conta própria, o que pode levar a vazamentos de memória, ponteiros pendentes e liberação dupla. O palestrante sugere o uso de verificadores de memória como o sanitizador de endereços e o Valgrind para reduzir o número de bugs de memória no programa.

  • 00:10:00 Nesta seção, o palestrante discute diferentes formas de alocação de armazenamento, começando com a alocação de tamanho fixo, em que cada parte do armazenamento tem o mesmo tamanho e alguns blocos são usados enquanto outros não são utilizados. Os blocos não utilizados são mantidos em uma lista chamada lista livre, e cada bloco da lista livre tem um ponteiro para o próximo bloco da lista. Para alocar um objeto da lista livre, o programa define o ponteiro como livre e, em seguida, define o ponteiro livre para apontar para a próxima coisa na lista livre, retornando o ponteiro para o primeiro objeto na lista livre. Para desalocar, basta definir o próximo ponteiro do objeto como livre e definir como livre igual ao objeto a ser liberado. Com a lista livre, alocar e liberar leva tempo constante e também se obtém uma boa localidade temporal.

  • 00:15:00 Nesta seção, é introduzido o conceito de fragmentação externa, que ocorre quando os blocos de memória usados estão espalhados pelo espaço de toda a memória. Isso pode levar a uma tabela de páginas maior, o que pode causar sobrecarga no disco e tornar menos eficiente a pesquisa de traduções. Para atenuar a fragmentação externa, uma lista livre ou bitmap por página de disco pode ser usada, e alocação da página mais cheia, liberando blocos de histórias e paginando páginas vazias podem ser feitas. A alocação de heap de tamanho fixo também pode ser útil para reduzir a fragmentação externa. Por fim, a alocação de heap de tamanho variável pode ser usada com listas de compartimentos livres, que aproveitam a eficiência das listas livres para diferentes tamanhos de memória alocada.

  • 00:20:00 Nesta seção, é apresentado um esquema para armazenar blocos de memória de tamanhos variados em um sistema de alocação de memória. O esquema envolve dividir os blocos em caixas com base em seu tamanho, com cada caixa contendo blocos de um tamanho especificado que são potências de dois. Ao alocar memória, o compartimento apropriado é selecionado com base no tamanho solicitado e, se estiver vazio, um compartimento maior não vazio é dividido em blocos menores para obter o tamanho desejado. No entanto, esse esquema pode resultar em fragmentação interna da memória, o que é um desperdício, portanto, o número de compartimentos usados é limitado e pequenos blocos são agrupados em páginas para reduzir a sobrecarga. O sistema operacional pode ser usado para fornecer mais memória, se necessário, e há chamadas de sistema disponíveis para essa finalidade.

  • 00:25:00 Nesta seção, o vídeo discute como funciona a alocação de memória e observa que as implementações padrão de 'malloc' dependem de comandos como 'break' para obter memória do sistema operacional. O sistema operacional fornece uma grande parte da memória e cabe ao sistema de alocação de armazenamento dividi-la em blocos menores. Esta seção também abrange variantes do alocador de memória, incluindo diferentes esquemas para armazenar tamanhos de bloco e como o espaço de endereço da memória virtual é disposto em um programa. Ele observa que a pilha e a pilha crescem uma em direção à outra, mas nunca se cruzam. Por fim, menciona-se que pré-computar grandes tabelas de constantes em um programa pode aumentar o tempo de carregamento, pois requer a leitura do segmento de dados.

  • 00:30:00 Nesta seção, a questão da fragmentação com memória virtual é discutida, o que pode levar à fragmentação externa, degradação do desempenho da tabela de páginas, debulha de disco e baixas taxas de ocorrência de TLB se a memória estiver espalhada. O objetivo da alocação de armazenamento é usar o mínimo possível de memória virtual, mantendo compactas as partes usadas da memória. O esquema de alocação de lista livre de compartimentos é analisado, com um teorema afirmando que a quantidade de memória virtual consumida pelo armazenamento de heap é limitada por M log M. A união de blocos menores em blocos maiores pode melhorar o esquema de lista livre de compartimentos, mas a sobrecarga de esse método pode ser alto em comparação com o algoritmo de lista livre de compartimentos padrão, que é apenas um fator constante pior do que o alocador ideal, de acordo com um artigo de Charles Leiserson.

  • 00:35:00 Nesta seção, o palestrante explica o conceito de alocação de armazenamento e como isso pode reduzir a fragmentação ao lidar com armazenamento de heap. Ele também discute a ideia de coleta de lixo, que libera o programador de ter que liberar objetos manualmente. O palestrante explica os três tipos de objetos de memória - raízes, objetos vivos e objetos mortos - e como a coleta de lixo pode reciclar estes últimos. Por fim, ele descreve a contagem de referência, uma forma simples de coleta de lixo que conta o número de ponteiros que fazem referência a um objeto para determinar se ele pode ser liberado.

  • 00:40:00 Nesta seção, o palestrante apresenta o conceito de contagem de referência como um esquema de coleta de lixo e explica como funciona o algoritmo de contagem de referência. No entanto, aponta-se uma limitação do algoritmo, onde os ciclos no grafo de referência não podem ser coletados. O palestrante então discute o uso de ponteiros fortes e fracos em algumas linguagens de programação para evitar essa limitação. Por fim, o palestrante visualiza dois outros esquemas de coleta de lixo, "marcar e varrer" e "parar e copiar", que evitam a limitação da contagem de referência ao lidar com ciclos no gráfico de referência.

  • 00:45:00 Nesta seção, o palestrante discute o uso de um algoritmo de busca em largura para encontrar todos os objetos ativos na memória. Um array com dois ponteiros é usado para representar uma fila FIFO para a busca, e o algoritmo marca cada objeto vivo que é alcançável a partir das raízes. Depois que a pesquisa for concluída, os objetos não marcados estarão disponíveis para serem coletados como lixo. O procedimento de marcação e varredura envolve dois estágios: o estágio marcado, que envolve o algoritmo de busca em largura, e o estágio de varredura, que envolve a varredura da memória para liberar objetos não marcados. No entanto, há limitações nesse esquema, como a necessidade de varrer toda a memória e a sobrecarga associada à observação de objetos não referenciados.

  • 00:50:00 Nesta seção, o vídeo apresenta o procedimento de coleta de lixo "parar e copiar" que lida com a fragmentação. Esse procedimento é semelhante ao algoritmo de marcação e varredura, mas adota uma abordagem diferente para garantir que os objetos ativos sejam contíguos na memória. O procedimento usa dois espaços de memória separados - o espaço de origem e o espaço de destino - e aloca e libera objetos do espaço de origem até que fique cheio. Em seguida, o algoritmo de coleta de lixo é executado e o espaço dois é usado como a fila para a busca em largura para identificar objetos ativos, que serão colocados contiguamente na memória no espaço dois. No entanto, usar esse algoritmo pode levar a um possível problema de correção, onde os ponteiros que apontam para objetos no espaço podem não estar mais corretos. Para resolver isso, o procedimento armazena um ponteiro de encaminhamento no objeto correspondente no espaço de origem e atualiza todos os ponteiros seguindo esses ponteiros de encaminhamento ao remover um objeto da fila na pesquisa em largura.

  • 00:55:00 Nesta seção, o palestrante discute o algoritmo de coleta de lixo stop and copy, sua complexidade de tempo e como ele lida com a fragmentação externa. O algoritmo stop and copy envolve copiar objetos do espaço from para o espaço to e, em seguida, atualizar os ponteiros desses objetos no espaço to. Esse algoritmo é linear no tempo e no espaço, o que o torna uma forma mais eficiente e eficaz de coleta de lixo. Quando o espaço de origem fica cheio, o usuário pode solicitar um novo espaço de heap e dobrar o tamanho do espaço de origem. O espaço de memória virtual requerido por este esquema é constante vezes ótimo, e este algoritmo elimina a fragmentação externa.

  • 01:00:00 Nesta seção, o palestrante aborda mais tópicos relacionados à alocação dinâmica de armazenamento, como o sistema Buddy para fazer coalescência, variantes do procedimento de marcação e varredura, otimizações para melhorar o desempenho, coleta de lixo geracional, coleta de lixo em tempo real , alocação de armazenamento multiencadeada e coleta de lixo paralela. A coleta de lixo geracional é baseada na ideia de que muitos objetos têm vida curta, portanto, apenas os objetos mais jovens são verificados na maior parte do tempo. A coleta de lixo em tempo real funciona em segundo plano enquanto o programa está sendo executado, mas pode levar a problemas de correção se o gráfico de objetos e ponteiros estiver mudando. A alocação de armazenamento multiencadeada e a coleta de lixo paralela têm vários encadeamentos em execução, o que torna os algoritmos mais difíceis de lidar com corridas e outros problemas de correção. O palestrante também resume os diferentes tipos de alocação de armazenamento, incluindo pilha e heap, e diferentes maneiras de fazer coleta de lixo, como contagem de referência, marcação e varredura e parada e cópia.

  • 01:05:00 Nesta seção, o instrutor mencionou que se aprofundará nos esquemas de alocação de armazenamento e que os alunos terão a oportunidade de experimentar alguns deles em sua próxima tarefa de casa. O instrutor então encerrou a palestra e abriu espaço para mais perguntas.
 

Aula 12. Alocação de Armazenamento Paralelo



Aula 12. Alocação de Armazenamento Paralelo

O vídeo discute várias estratégias de alocação de memória e suas compensações. O uso de malloc e alocação alinhada, bem como a importância da desalocação de memória adequada com free, é explicado. O uso do Mmap para alocação de memória virtual também é abordado, juntamente com os problemas de fragmentação externa e desempenho lento. O conceito de pilhas na programação C e C++ é explorado, com ênfase em uma abordagem de pilha cactus baseada em heap para alocar quadros de pilha, o que pode levar a melhores provas de limite de espaço e limites superiores. O uso de um conjunto de pilhas lineares também é discutido, junto com a importância de otimizar para pequenos blocos para minimizar a fragmentação. O vídeo termina com uma discussão sobre as abordagens de heap global e local e seus possíveis problemas, juntamente com abordagens como listas de lixo livre e rebalanceamento periódico de memória para resolver esses problemas.

O vídeo também discute soluções para alocação de armazenamento paralelo e apresenta o alocador Hoard como uma solução. O alocador Hoard usa uma combinação de heaps locais e globais e grandes super blocos que podem ser movidos entre heaps para reduzir o compartilhamento falso, melhorar a escalabilidade e reduzir a fragmentação externa. O armazenamento máximo alocado no heap global é no máximo o armazenamento máximo alocado nos heaps locais, e o volume é limitado pelo tamanho do usuário mais o armazenamento alocado, mas não utilizado, nos heaps locais. O vídeo também discute brevemente outros alocadores, como Je malloc e Super malloc, com resultados de benchmark indicando que Super malloc teve um desempenho melhor do que Je malloc e Hoard. A discussão termina com uma referência aos slides online para detalhes da coleta de lixo.

  • 00:00:00 Nesta seção, o palestrante revisa as primitivas de alocação de memória, incluindo malloc e alocação alinhada. A alocação alinhada pode ser usada para alinhar a memória às linhas de cache de modo que o acesso a um objeto dentro de uma linha de cache exija apenas um acesso de cache, reduzindo o número de faltas de cache. O palestrante também discute a importância de desalocar adequadamente a memória com a função free e evitar vazamentos de memória e liberações duplas. Por fim, o palestrante apresenta a chamada de sistema Mmap, que pode ser usada para alocar memória virtual sem um arquivo de apoio.

  • 00:05:00 Nesta seção, o palestrante explica o processo de alocação de memória usando M map, que é uma chamada de sistema que encontra uma região contígua não utilizada no espaço de endereço do aplicativo grande o suficiente para conter o tamanho de memória solicitado e atualiza o tabela de páginas para conter uma entrada para as páginas alocadas. Ao contrário de malloc, que é uma chamada de biblioteca e parte do código de gerenciamento de heap da biblioteca C, o mapa M não aloca imediatamente memória física para a memória solicitada, mas preenche a tabela de páginas com entradas apontando para uma página zero especial que é modificada e traduzido para a memória física somente quando o usuário escreve nela pela primeira vez. Além disso, M map é responsável por obter memória do sistema operacional, enquanto malloc é responsável por reutilizar a memória alocada anteriormente para reduzir a fragmentação e melhorar a localidade temporal.

  • 00:10:00 Nesta seção, o vídeo discute as diferenças entre usar MMAP e MALLOC para alocação de armazenamento, enfatizando que o MMAP é relativamente pesado e aloca páginas inteiras mesmo para pequenas alocações, levando à fragmentação externa e baixo desempenho. O vídeo também analisa o processo de conversão de endereços, onde o endereço virtual é usado para acessar a memória e o hardware procura o endereço físico apropriado na tabela de páginas. O vídeo explica como os TLBs funcionam armazenando pesquisas recentes na tabela de páginas e observa que os programas com localidade espacial ou temporal terão muitos acessos recentes armazenados no TLB, levando a um desempenho mais rápido.

  • 00:15:00 Nesta seção, o palestrante discute como a tradução de endereços funciona em máquinas modernas e também se aprofunda no conceito de pilhas na programação C e C++. As pilhas são usadas para acompanhar chamadas de função e variáveis locais e seguir uma ordem linear. O palestrante enfatiza uma regra de ponteiros em pilhas lineares tradicionais: um pai pode passar ponteiros para suas variáveis de pilha para seus filhos, mas não o contrário, para evitar sobrescrever variáveis. O locutor também sugere opções, como alocar memória no heap ou na pilha do pai, para passar a memória de uma função filha de volta para o pai.

  • 00:20:00 a alocação de heap paralelo está correta, o possível problema com o uso de uma pilha cactus baseada em heap é a fragmentação da memória, onde pode não haver memória contígua suficiente para alocações futuras, levando ao desperdício de espaço e, possivelmente, esgotamento de memória ou travar o programa. Embora os primeiros sistemas de programação paralela usassem essa estratégia, é importante otimizar o código para minimizar o impacto no desempenho e considerar as consequências da fragmentação da memória.

  • 00:25:00 Nesta seção, o vídeo discute o uso de uma abordagem cactus stack baseada em pilha para alocar quadros de pilha sem colocar um limite superior na profundidade máxima. No entanto, a interoperabilidade é um problema ao tentar usar o código de pilha linear tradicional com essa pilha cactus baseada em heap. Isso pode ser corrigido usando uma abordagem chamada mapeamento de memória thread-local, mas essa abordagem requer alterações no sistema operacional. Apesar disso, a abordagem cactus stack baseada em heap ainda é boa na prática e pode ser usada para provar um limite de espaço de um programa Silk que a utiliza. Este limite de espaço mostra que o espaço de pilha de uma execução P worker usando uma pilha cactus baseada em heap é superior a P vezes s1, onde s1 é o espaço de pilha necessário para uma execução serial do programa Silk. Esse é um bom recurso da abordagem de pilha de cactos baseada em heap.

  • 00:30:00 Nesta seção, o código de multiplicação da matriz de divisão e conquista é analisado para entender como ele pode ser aplicado ao Teorema de Troca de Espaço-Tempo. O código faz oito chamadas recursivas, cada uma de tamanho N/2, e antes de cada chamada, ele faz um malloc para obter espaço temporário de ordem de tamanho N ao quadrado, que é liberado logo antes do retorno da função. Como as alocações seguem uma disciplina de pilha, mesmo ao alocar fora da pilha, o espaço vinculado do slide anterior pode ser usado para limitar o espaço P do trabalhador. O trabalho é N ao cubo e a extensão é da ordem log ao quadrado N. A recorrência para o espaço é s de N/2 + theta de N ao quadrado, que resulta em N ao quadrado. Portanto, a propriedade das folhas ocupadas e o teorema para o limite de espaço mostram que em P processadores, o espaço é limitado por P vezes N ao quadrado.

  • 00:35:00 Nesta seção, o palestrante mostra ao público como provar um limite de espaço mais forte para o algoritmo discutido na seção anterior. Ao analisar a estrutura do algoritmo e focar na ramificação o máximo possível perto do topo da árvore de recursão, o locutor é capaz de demonstrar um limite espacial de P elevado a um terço vezes N ao quadrado, o que é melhor do que os limites superiores anteriores . O palestrante observa que a análise da estrutura de um algoritmo pode levar a provas mais fortes no espaço do que simplesmente aplicar um teorema geral. A seção conclui discutindo como as funções paralelas falham em interoperar com binários seriais herdados e de terceiros.

  • 00:40:00 Nesta seção, o palestrante discute o uso de um pool de pilhas lineares na alocação de armazenamento, que pode ser usado para manter um pool de pilhas para código legado. O número de pilhas no pool deve ser constante vezes o número de processadores para que o limite de espaço seja preservado. No entanto, essa estratégia pode afetar o limite de tempo do algoritmo de roubo de trabalho porque o trabalhador pode não conseguir roubar se não houver mais pilhas disponíveis. O palestrante então fala sobre as propriedades básicas dos alocadores de armazenamento de heap, incluindo a velocidade do alocador e a pegada do usuário, enfatizando a importância de otimizar para pequenos blocos devido ao potencial de fragmentação e sobrecarga na alocação. A fragmentação é definida como a pegada do alocador dividida pela pegada do usuário.

  • 00:45:00 Nesta seção do vídeo, o palestrante discute como manter a pegada alocada o mais próximo possível da pegada do usuário para minimizar a proporção dos dois. Uma solução é usar algo chamado M warning, que informa ao sistema operacional que uma determinada página de memória não é mais necessária, mas deve ser mantida na memória virtual. O palestrante também menciona o teorema da aula anterior de que a fragmentação para listas livres de bins é o log de ordem base dois de U, onde U é a quantidade total de memória alocada, e explica as diferenças entre sobrecarga de espaço, fragmentação interna e fragmentação externa. Finalmente, o palestrante observa que os processadores modernos de 64 bits fornecem cerca de 2 a 48 bytes de espaço de endereço virtual, o que é suficiente para a maioria dos programas, mas ainda mais do que a memória física em uma máquina típica.

  • 00:50:00 Nesta seção, o vídeo explora uma estratégia de alocação de heap paralelo usando um heap global com proteção mutex, que é como funciona o alocador C++ padrão. A ampliação dessa estratégia é única, pois não requer espaço adicional em comparação com um alocador serial. No entanto, o problema potencial com essa abordagem é o impacto no desempenho, pois a aquisição do bloqueio para cada alocação e desalocação é lenta e piora com o aumento de processadores. A contenção de bloqueio é o principal motivo para escalabilidade ruim, que é mais problemática para pequenas alocações devido a taxas de solicitação mais altas, e alocações de blocos grandes exigem mais trabalho.

  • 00:55:00 Nesta seção, o vídeo discute o possível problema com o uso de uma abordagem de heap local, que pode levar a desvios de memória e explosão ilimitada. Essencialmente, se você alocar toda a sua memória em um thread, mas liberá-la em outro, pode haver memória não utilizada no sistema que o alocador não é inteligente o suficiente para reutilizar. Como resultado, seu programa rodando em vários processadores pode eventualmente ficar sem memória, mas isso não acontecerá se for executado apenas em um único núcleo. O vídeo sugere o uso de uma abordagem de lista livre de lixo para resolver esse problema, que envolve a configuração de ponteiros na estrutura de dados da lista livre de lixo para que o bloco liberado possa aparecer em uma das listas vinculadas. Outra estratégia é reequilibrar periodicamente a memória, mas uma abordagem mais simples também é discutida.

  • 01:00:00 Nesta seção, o vídeo discute como alterar o alocador de memória para obter o comportamento desejado de ter cada thread acessando seu próprio heap sem a necessidade de um heap global. Uma abordagem é rotular cada objeto com um proprietário e retorná-lo ao heap do proprietário quando for liberado. Dessa forma, objetos locais obtêm alocação e liberação rápidas, enquanto objetos remotos requerem alguma sincronização, mas não tanto quanto com um heap global. A quantidade máxima de memória que pode ser alocada é limitada por X, a quantidade usada pelo programa sequencial, e a taxa de expansão é limitada por P, o número de heaps. Essa abordagem também tem resiliência ao falso compartilhamento, que ocorre quando vários processadores acessam diferentes locais de memória, mas na mesma linha de cache.

  • 01:05:00 Nesta seção, o palestrante discute como a alocação de pilha paralela pode levar a um falso compartilhamento e apresenta o alocador de tesouro como uma solução. O alocador de tesouro usa uma combinação de heaps locais e globais, organizando a memória em grandes superblocos que podem ser movidos entre os heaps. Essa abordagem é rápida, escalável e resistente a falsos compartilhamentos. Quando uma alocação é feita, o alocador verifica se há um objeto livre no heap local e o obtém, se houver. Caso contrário, ele vai para o heap global para obter mais memória.

  • 01:10:00 Nesta seção, o palestrante explica como o alocador Horde reduz a fragmentação externa alocando um objeto livre do super bloco não cheio mais cheio para densificar o movimento dos super blocos. Se o objeto não for encontrado no heap local, ele verifica o heap global e, se o heap global estiver vazio, ele chama um novo super bloco do sistema operacional. O alocador Horde mantém uma invariante em que o heap está no máximo meio utilizado e, se detectar que o heap está subutilizado, move um superbloco meio vazio para o heap global. O falante então apresenta um lema afirmando que o armazenamento máximo alocado no heap global é no máximo o armazenamento máximo alocado nos heaps locais. Finalmente, o palestrante prova o teorema de que a pegada do alocador Horde é limitada pela ordem u mais SP, onde u é a pegada do usuário para o programa e SP é o armazenamento alocado, mas não utilizado, nos heaps locais. A explosão é então calculada como sendo um mais SP de ordem dividido por u.

  • 01:15:00 Nesta seção, o palestrante discute diferentes alocadores, incluindo Je malloc e Super malloc. Je malloc tem bloqueios globais separados para diferentes tamanhos de alocação e libera páginas vazias usando conselhos em que o torna robusto para diferentes rastreamentos de alocação. Por outro lado, o Super malloc tem poucas linhas de código e está se desenvolvendo muito rápido. O alto-falante compartilha resultados de referência em que Super malloc teve um desempenho melhor que J malloc, que teve um desempenho melhor que Horde, enquanto o alocador padrão teve desempenho ruim. A discussão também se estende à coleta de lixo, porém, o palestrante deixa os detalhes disso para os slides online.
 

Aula 13. O Cilk Runtime System



Aula 13. O Cilk Runtime System

O sistema de tempo de execução Cilk é responsável por computações de agendamento e balanceamento de carga em processadores paralelos, usando um agendador de roubo de trabalho aleatório para mapear computações em processadores em tempo de execução. O sistema é projetado para otimizar a execução serial do programa, mesmo à custa de custos adicionais para roubos. O trabalhador mantém uma estrutura de dados de deck separada que contém ponteiros para os quadros de pilha e usa ponteiros iniciais e finais. Os quadros que estão disponíveis para serem roubados possuem uma estrutura local adicional que contém as informações necessárias para que o roubo ocorra enquanto o deck estiver externo à pilha de chamadas. A seção explica como o sistema permite que os processadores comecem a executar a partir do meio de uma função em execução e como a sincronização entre os processadores se torna complicada ao atingir uma instrução de sincronização que não pode ser executada além do ponto porque os processadores específicos ainda estão aguardando a conclusão dos cálculos. Além disso, o palestrante aborda o desempenho do sistema, considerações de design e estruturas de dados e como o sistema otimiza a execução usando o protocolo THC, envolvendo dois conjuntos de protocolos, um para o trabalhador que executa o trabalho e outro para o ladrão.

O Cilk Runtime System usa um protocolo set jump e long jump para lidar com o roubo de cálculos dos decks de execução dos processos vítimas. A abstração Cactus Stack permite que o processo ladrão tenha sua própria pilha de chamadas para evitar a corrupção das pilhas da vítima. O protocolo de sincronização do sistema usa uma árvore de cálculos e um Cactus Stack para garantir que a sincronização ocorra apenas entre cálculos aninhados dentro de uma função. A Full Frame Tree mantém relacionamentos pai-filho entre cálculos com sub-computações pendentes para simplificar o processo de sincronização. Além disso, o sistema de tempo de execução otimiza o caso comum em que a função atual não possui cálculos filho pendentes e todos os trabalhadores estão ocupados. Outros recursos suportados incluem exceções C++, hiperobjetos redutores e pedigrees.

  • 00:00:00 Nesta seção, Tibi explica o sistema de tempo de execução Cilk, que é responsável por agendamento e cálculos de balanceamento de carga em processadores paralelos. O sistema de tempo de execução usa um agendador de roubo de trabalho aleatório para mapear computações em processadores em tempo de execução, garantindo uma execução eficiente. Tibi observa que o sistema de tempo de execução Cilk é um software complexo, mas sua mágica subjacente é implementada por meio da colaboração do compilador Cilk e da biblioteca de tempo de execução. Além disso, ele mostra o pseudocódigo para um programa Cilk simples após a compilação, que destaca o processo complexo subjacente ao sistema de tempo de execução do Cilk.

  • 00:05:00 Nesta seção, o palestrante explica a funcionalidade necessária para o sistema de tempo de execução Cilk, bem como as considerações de desempenho. Ele usa um exemplo de rotina de Fibonacci paralelizada para ilustrar como o programa Cilk executa um dag de computação, que se desdobra dinamicamente conforme o programa é executado em um processador. No entanto, quando a instrução silk spawn é encontrada, um novo frame é criado para fib de 3, e outra vertente fica disponível para execução em paralelo. O processador então começa a executar fib de 3 como se fosse uma chamada de função comum. O processo se repete quando o ponteiro de instrução retorna ao início da rotina fib.

  • 00:10:00 Nesta seção, vemos como vários processadores executam uma rotina fib em paralelo com a ajuda do sistema de tempo de execução Cilk. Cada processador salta para o meio de uma função em execução e começa a executá-la, apesar de ter registradores independentes, o que levanta a questão de como o sistema Silk permite que os processadores comecem a executar a partir do meio de uma função em execução. Além disso, a sincronização entre os processadores torna-se complicada ao atingir uma instrução de sincronização que não pode ser executada além do ponto porque os processadores específicos ainda estão aguardando a conclusão dos cálculos, o que requer uma sincronização refinada dentro do padrão aninhado.

  • 00:15:00 Nesta seção, o palestrante discute as considerações de implementação para o sistema de tempo de execução Cilk. Eles mencionam três considerações principais: um único trabalhador sendo capaz de executar o programa, a capacidade de pular no meio da execução de funções e continuar de onde outros processadores pararam e a sincronização. Além disso, o Silk tem uma noção de cactus stack, que precisa ser implementada corretamente para tornar todas as visualizações da pilha disponíveis e consistentes. Finalmente, o sistema precisa permitir o roubo de trabalho, permitindo que os processadores roubem quadros uns dos outros.

  • 00:20:00 Nesta seção, o palestrante discute a funcionalidade necessária para o Cilk Runtime System, que inclui execução serial, ladrões pulando no meio de funções em execução, sincronizações para sincronizar de forma aninhada, uma pilha de cactos para que todos os trabalhadores vejam e lidando com misturas de quadros de geração e quadros chamados que podem estar disponíveis quando eles roubam a computação. A seção então passa a abordar o desempenho do sistema, onde precisamos de amplo paralelismo, T1 sobre T infinito deve ser muito maior que P e queremos aceleração linear ao aumentar o número de processadores para executar o programa. A seção também aborda o tempo de execução esperado do TCP em processadores P, que é proporcional ao trabalho da computação dividido pelo número de processadores mais algo na ordem do intervalo da computação.

  • 00:25:00 Nesta seção, aprendemos sobre o Cilk Runtime System e seu objetivo de manter alta eficiência de trabalho em programas com paralelismo suficiente. O Silk Runtime System segue o princípio do primeiro trabalho, otimizando a execução serial do programa, mesmo à custa de algum custo adicional para os aços. A biblioteca do sistema de tempo de execução lida com problemas de execução paralela e com caminhos de execução mais lentos quando ocorrem aços. O trabalhador mantém uma estrutura de dados de deck separada que contém ponteiros para os quadros de pilha e usa ponteiros iniciais e finais. Os quadros que estão disponíveis para serem roubados possuem uma estrutura local adicional que contém as informações necessárias para que o roubo ocorra enquanto o deck estiver externo à pilha de chamadas.

  • 00:30:00 Nesta seção, aprendemos sobre o design do Cilk Runtime System e suas estruturas básicas de dados. O sistema gera uma função auxiliar de geração para cada computação, que mantém uma estrutura de trabalho e uma estrutura de quadro de pilha do Silk para cada instanciação de uma função de geração e um auxiliar de geração, respectivamente. O quadro de pilha do Silk RTS contém campos como um buffer e um número inteiro de sinalizadores para resumir o estado do quadro de pilha do Silk e um ponteiro para um quadro de pilha do Silk pai na pilha de chamadas. A estrutura de trabalho mantém um deck e um ponteiro para o atual quadro de pilha do Silk RTS. Essas estruturas de dados são os fundamentos do Cilk Runtime System que o sistema Intel so+ runtime elabora.

  • 00:35:00 Nesta seção, o vídeo explora o código para a função de spawn "foo" e a função auxiliar de spawn. O código para "foo" inclui uma chamada para inicializar o quadro de pilha, configurado para um spawn com a rotina set jump, uma chamada para a função auxiliar de spawn "barra de spawn", um bloco de código condicional para um coletor no Silk RTS, e chamadas para pop e leaf frames para limpeza. O código para o auxiliar de spawn inclui uma chamada para inicializar o quadro de pilha e uma chamada para desanexar o Silk RTS com funções de limpeza adicionais para a estrutura de pilha. A rotina de configuração é descrita como uma função que permite que ladrões roubem a continuação da função, tomando como argumento um buffer para armazenar as informações necessárias para retomar o local da função.

  • 00:40:00 Nesta seção, o palestrante discute como restringir o conjunto de registradores e salvá-los em um conjunto predeterminado para uma chamada de função. A responsabilidade de salvar os registradores recai sobre a função, mas o ponteiro de instrução e os ponteiros de pilha são salvos no buffer. A seção continua a discutir uma função auxiliar de geração e como ela atualiza as estruturas de trabalho e os quadros de pilha atuais. Por fim, a seção explica como a rotina rápida de inserção de quadro estabelece um ponteiro pai na pilha de chamadas e atualiza o quadro de pilha atual do trabalhador para apontar para a parte inferior.

  • 00:45:00 Nesta seção, a transcrição do vídeo do YouTube intitulado "The Cilk Runtime System" explica como a função Silk RTS detach permite que a computação seja roubada, onde uma vez que a execução artística do silk é concluída, um ladrão pode vir e roubar a continuação da desova da seda. O quadro pop é responsável por limpar a estrutura do quadro de pilha e atualizar o quadro de pilha atual para apontar para o pai. Essa chamada de função pode ou não retornar, e qual desses dois casos é mais importante para o sistema de tempo de execução otimizar é o caso de sucesso, com base nos dois que funcionam primeiro princípio.

  • 00:50:00 Nesta seção, o palestrante discute a otimização do sistema de tempo de execução Cilk na execução do trabalhador no caso um, em que os trabalhadores devem fazer a execução serial regular. Eles também explicam como funciona o roubo de trabalhadores, com o ladrão mirando no topo do baralho da vítima, removendo o item da fila e atualizando o topo do baralho e o ponteiro do quadro de pilha atual. O resultado da função gerada é retornado ao quadro de pilha pai no código SIL original.

  • 00:55:00 Nesta seção, o palestrante explica a abordagem do Cilk Runtime System no tratamento de acessos simultâneos envolvendo vários processadores usando um protocolo chamado protocolo THC. O protocolo envolve dois conjuntos de protocolos, um para o trabalhador que executa o trabalho e outro para o ladrão. O protocolo do trabalhador é otimizado tentando estourar algo do fundo do convés, e somente em caso de falha ele consegue travar o convés, enquanto o ladrão sempre agarra um cadeado antes de realizar qualquer operação no convés. O ladrão então retoma magicamente uma continuação roubada chamando a função de salto longo, passando o buffer de quadro de pilha recuperado da função de salto definido e definindo seu estado de registro como o da continuação roubada.

  • 01:00:00 Nesta seção, o palestrante discute a interação entre as chamadas set jump e long jump no sistema de tempo de execução Cilk. Eles explicam como, quando uma rotina de salto longo é chamada, ela efetivamente retorna do salto definido uma segunda vez, desta vez com um valor diferente especificado no segundo argumento. Usando o buffer apropriado e o segundo argumento, o ladrão pode executar um salto longo para pular uma certa computação no código da vítima. O palestrante observa que é possível calcular estaticamente a distância necessária para pular uma chamada e usar uma abordagem diferente, mas o salto definido e o protocolo de salto em distância servem como um método mais flexível para o sistema de tempo de execução Cilk. No geral, o palestrante destaca as diversas técnicas disponíveis para o ladrão roubar computações do baralho da vítima usando o Cilk.

  • 01:05:00 Nesta seção, é discutida a necessidade de uma abstração cactus stack para o sistema de tempo de execução Cilk. É explicado que usar a pilha da vítima pode corromper a pilha da vítima e causar problemas na manutenção da consistência em todos os trabalhadores. Portanto, é necessária uma pilha de chamadas separada para o ladrão. A implementação da pilha cactus envolve o ladrão roubando a continuação e definindo seu ponteiro de pilha para sua própria pilha enquanto ainda consegue acessar o estado da função na pilha da vítima por meio de compensações de RB p.

  • 01:10:00 Nesta seção, o palestrante explica como o sistema de tempo de execução SIL lida com a sincronização de computação em diferentes processadores. O sistema usa a pilha cactus e uma árvore de cálculos para garantir que a sincronização ocorra apenas entre subcomputações aninhadas em uma função, não no programa em geral. Quando um trabalhador atinge uma instrução de sincronização de seda antes que todos os subcomputações retornem, ele se torna um ladrão e continua trabalhando no quadro de pilha de uma computação roubada. Isso permite que o sistema evite o desperdício de trabalhadores e garanta que os cálculos aninhados sejam sincronizados adequadamente. O sistema instrui especificamente o compilador a não usar uma otimização que possa entrar em conflito com essa abordagem.

  • 01:15:00 Nesta seção, o Cilk Runtime System é descrito como mantendo uma árvore de estados chamada full frames, que mantém o controle de quais computações estão esperando por quais outras computações para terminar. Esse sistema usa uma árvore de quadro completo para acompanhar cargas de informações para execução paralela, incluindo ponteiros para quadros pai, potencialmente para quadros filho e como subcomputações pendentes se relacionam entre si. Quando um trabalhador encontra uma sincronização, se tiver um cálculo filho pendente, ele não pode sincronizar e deve suspender seu quadro completo até que possa se tornar um ladrão para roubar mais trabalho. Este sistema permite que um programa tenha amplo paralelismo e simplifica os protocolos de sincronização.

  • 01:20:00 Nesta seção, o palestrante discute como o Cilk Runtime System otimiza o caso comum em que a função em execução não possui filhos pendentes e todos os funcionários do sistema estão ocupados com suas próprias tarefas. O sistema de tempo de execução usa bits de um campo de sinalizador do quadro de pilha associado para avaliar se a sincronização é necessária para uma sincronização de seda. O palestrante também menciona vários outros recursos suportados pelo sistema de tempo de execução, incluindo exceções C++, hiperobjetos redutores e pedigrees.
 

Aula 14. Caching e Algoritmos Eficientes em Cache



Aula 14. Caching e Algoritmos Eficientes em Cache

No vídeo sobre cache e algoritmos com eficiência de cache, o instrutor explica a hierarquia de cache de máquinas modernas, as diferenças entre caches totalmente associativos e mapeados diretamente e as vantagens e desvantagens de caches associativos definidos. O vídeo também apresenta o modelo de cache ideal e o conceito de algoritmos com eficiência de cache. O palestrante discute o lema de falta de cache, a suposição de cache alto e o lema de cache de submatriz. Eles também analisam faltas de cache incorridas durante a leitura de uma submatriz e durante a multiplicação de matrizes. O vídeo conclui apresentando o conceito de multiplicação de matrizes lado a lado e como ela pode melhorar significativamente o desempenho, mas também observa que não é portátil e pode ser caro para otimizar vários níveis de cache.

A palestra aborda cache e algoritmos eficientes em cache, usando a multiplicação recursiva de matrizes como exemplo. O palestrante enfatiza a importância de analisar erros de trabalho e de cache separadamente e observa que os algoritmos com reconhecimento de cache podem não ser ideais para todas as máquinas devido aos diferentes tamanhos de cache. O palestrante também discute algoritmos de esquecimento de cache que se ajustam automaticamente para qualquer tamanho de cache e menciona desenvolvimentos em código paralelo de esquecimento de cache. Por fim, o objetivo é projetar algoritmos com reconhecimento ou esquecimento de cache, e a discussão sobre o projeto de algoritmos com esquecimento de cache continuará na aula seguinte.

  • 00:00:00 Nesta seção sobre cache e algoritmos eficientes de cache, o instrutor discute a hierarquia de cache de máquinas modernas, que inclui dados L1 privados e caches de instrução para cada processador, um cache L2 privado e um cache de último nível que é compartilhado entre todos os processadores. Os tamanhos desses caches aumentam à medida que se sobe na hierarquia de memória, sendo a DRAM a mais lenta e a maior. A associatividade do cache e a latência também aumentam à medida que se sobe na hierarquia da memória, sendo o cache L1 o mais rápido e o mais associativo. O instrutor também menciona a importância dos protocolos de coerência de cache para garantir a consistência nos acessos aos endereços de memória para processamento paralelo. Entender como aproveitar a localidade em programas pode ajudar a fazer uso eficiente dos caches de memória mais rápidos.

  • 00:05:00 Nesta seção, as diferenças entre caches totalmente associativos e mapeados diretamente são discutidas. Um cache totalmente associativo requer a pesquisa de todo o cache para encontrar um bloco que pode ser lento e ineficiente, pois encontrar um bloco pode exigir o acesso a várias linhas. O cache mapeado direto, por outro lado, possui apenas uma localização possível para cada bloco, o que torna o acesso aos blocos muito mais rápido, com menos conflitos. Os três componentes do espaço de endereço, o deslocamento, o conjunto e a marca, também são explicados ao dividir o endereço da memória virtual para determinar a localização do bloco de cache. A tag identifica a qual bloco de memória o bloco de cache corresponde, e o conjunto determina em qual posição no cache o bloco vai, com um espaço de endereço total de W bits.

  • 00:10:00 Nesta seção, o vídeo discute as vantagens e desvantagens de caches mapeados diretamente, que são rápidos porque apenas um local no cache precisa ser pesquisado, mas são propensos a erros de conflito onde os blocos de cache continuam despejando uns aos outros, reduzindo o desempenho. Em seguida, o vídeo apresenta os caches associativos de conjunto, uma solução híbrida em que cada conjunto contém várias linhas, permitindo mais de uma localização possível no cache para cada bloco de cache. O vídeo também menciona uma taxonomia de diferentes tipos de cache misses, incluindo cold misses que ocorrem na primeira vez que um bloco de cache é acessado e não podem ser evitados.

  • 00:15:00 Nesta seção, o vídeo discute diferentes tipos de faltas de cache, incluindo faltas de capacidade, faltas de conflito e faltas de compartilhamento. Faltas de capacidade ocorrem quando o cache está cheio e não cabe em todos os blocos de cache que precisam ser acessados, enquanto faltas de conflito acontecem em caches associativos definidos quando muitos blocos do mesmo conjunto mapeiam para o cache. Por fim, as falhas de compartilhamento ocorrem em um contexto paralelo quando vários processadores estão acessando a mesma linha de cache e pelo menos um deles está escrevendo nela. O vídeo também fornece um exemplo de um caso ruim para falhas de conflito ao acessar uma submatriz dentro de uma matriz maior armazenada na ordem principal da linha.

  • 00:20:00 Nesta seção, o palestrante discute cache e algoritmos eficientes de cache. Eles usam um exemplo de acesso a uma submatriz dentro de uma matriz maior e como erros de conflito podem ocorrer quando o cache é apenas associativo de 4 vias. O palestrante sugere adicionar uma quantidade constante de espaço ao final de cada linha na matriz, para que cada linha tenha mais de 2 ^ 15 bytes, o que pode ajudar a reduzir as perdas de conflito.

  • 00:25:00 Nesta seção, o palestrante discute o modelo de cache ideal, que é um modelo usado para analisar o desempenho do cache de algoritmos. Este modelo assume uma hierarquia de cache de dois níveis, um cache totalmente associativo e uma política de substituição Nishant ideal. O palestrante explica que as duas medidas de desempenho que importam são a ordem de N e o número de faltas de cache, onde o cenário ideal é ter um número baixo de faltas de cache sem aumentar o trabalho do algoritmo padrão tradicional. O lema LRU, que foi provado em 1985, também é mencionado, que afirma que um algoritmo que incorre em Q cache misses em um cache ideal de tamanho M incorrerá em 2Q cache misses em um cache totalmente associativo de tamanho 2M que usa a política LRU.

  • 00:30:00 Nesta seção, o palestrante apresenta o conceito de algoritmos com eficiência de cache e como eles podem melhorar o desempenho do programa minimizando o número de faltas de cache. Ele explica a política de substituição menos usada recentemente (LRU), que afirma que um cache totalmente associativo com o dobro do tamanho do cache ideal usando LRU incorrerá em não mais que o dobro do número de faltas de cache. Isso permite uma análise mais fácil de faltas de cache ao realizar análises assintóticas. O palestrante também apresenta um lema de falta de cache, afirmando que se um programa lê um conjunto de segmentos de dados cujo tamanho é menor que um terço do tamanho do cache e cujo tamanho médio é pelo menos o tamanho de uma linha de cache, então o número de cache misses para ler todos eles é no máximo três vezes o tamanho total dos segmentos dividido pelo tamanho de uma linha de cache.

  • 00:35:00 Nesta seção, o vídeo discute duas suposições relacionadas ao armazenamento em cache - o cache miss lemma e a suposição de cache alto. O lema de falta de cache afirma que, se o comprimento médio dos segmentos de dados for maior que o tamanho de um bloco de cache, ele aumentará o número de faltas de cache apenas por um fator constante. A suposição de cache alto assume que o cache é mais alto do que largo e geralmente é satisfeito na prática. O vídeo também explica o lema de cache de submatriz, que discute o problema com caches curtos no ajuste de submatrizes em linhas de cache e por que a suposição de cache alto é útil para resolver esse problema.

  • 00:40:00 Nesta seção, o palestrante discute cache e algoritmos eficientes de cache. Eles analisam o número de erros de cache incorridos ao ler uma submatriz quadrada no cache e usam o lema de erros de cache para mostrar que o número de erros de cache necessários para ler todos os elementos da matriz no cache é no máximo 3n^2/B . Eles então analisam o número de faltas de cache incorridas no algoritmo de multiplicação de matriz de trabalho cúbico padrão, assumindo que a matriz está na ordem principal da linha e satisfazem a suposição de cache alto. Eles consideram três casos e assumem LRU para o segundo e terceiro casos, mostrando a importância da otimização de cache no projeto de algoritmos.

  • 00:45:00 Nesta seção, o palestrante discute cache e algoritmos eficientes de cache. Eles analisam dois casos de multiplicação de matrizes, onde n é maior que M sobre B e quando n é menor que C vezes M sobre B. Eles usam uma política de substituição LRU e calculam o número de faltas de cache incorridas ao acessar a matriz B. No primeiro Nesse caso, eles descobrem que precisam de theta de n faltas de cache cúbicas, resultando em nenhum ganho por ter localidade no algoritmo. No segundo caso, eles podem explorar a localidade espacial e reduzir o número de cache misses por um fator de B, resultando em teta de n ao cubo sobre B cache misses, o que é mais eficiente.

  • 00:50:00 Nesta seção do vídeo, o palestrante discute o cache e algoritmos eficientes de cache. Eles primeiro analisam o caso em que toda a matriz se encaixa no cache, resultando em um número total de erros de cache de theta de n ao quadrado sobre B. Eles então discutem uma otimização trocando a ordem dos dois loops internos para se beneficiar da localidade espacial e reduzir o número total de faltas de cache para theta de n ao cubo sobre B. No entanto, eles observam que é possível fazer melhor usando uma otimização chamada ladrilho, onde seis loops for são usados para fazer um loop sobre ladrilhos e o cálculo é feito para cada sub -matrix antes de passar para a próxima. O trabalho para uma submatriz de tamanho s por s é então s ao cubo.

  • 00:55:00 Nesta seção, o conceito de multiplicação de matrizes lado a lado é apresentado e discutido em detalhes. O objetivo desse algoritmo é ajustar as submatrizes no cache para que todos os cálculos possam ser feitos no cache sem mais perdas de cache. O número de faltas de cache é analisado e descobre-se que o número de faltas de cache é n/s^3 vezes s^2 /B, para um total de faltas de cache n^3/B * sqrt(M). Este número é muito significativo para melhorar o desempenho do código de multiplicação de matrizes. No entanto, surge um problema com o algoritmo: ele não é portátil, pois depende muito do tamanho do cache da máquina em que é executado. Além disso, a otimização de ajuste multidimensional torna-se muito mais cara e o código torna-se mais confuso ao otimizar para vários níveis de cache.

  • 01:00:00 Nesta seção, a palestra explora o cache e algoritmos eficientes de cache. O palestrante discute os desafios de ajustar os parâmetros para um algoritmo eficiente de cache e otimizá-lo para uma máquina específica. Eles introduzem um algoritmo recursivo de multiplicação de matrizes onde as matrizes de entrada são divididas em quatro submatrizes ou quadrantes. Para cada quadrante da matriz de saída, uma soma de duas multiplicações de matriz ocorre recursivamente. Por fim, o palestrante analisa o funcionamento desse algoritmo e conclui que é um projeto mais simples que ainda mantém um bom desempenho do cache.

  • 01:05:00 Nesta seção, o palestrante discute cache e algoritmos eficientes de cache e usa o exemplo de multiplicação de matrizes para explicar a diferença entre analisar trabalho e faltas de cache. O falante desenha uma árvore de recursão para visualizar o problema de tamanho e subproblemas de ramificação e observa que o número de níveis até as folhas é log base 2 de n. O número de folhas é calculado como oito elevado à base logarítmica 2 de n, que é o mesmo que n ao cubo. A quantidade de trabalho é simplesmente theta n ao cubo, e os erros de cache são analisados com um caso base diferente, onde a submatriz se encaixa no cache, e o theta de N quadrado sobre erros de cache é usado. O palestrante destaca que o número de níveis não é apenas log base 2 de n, mas também depende do tamanho do cache, resultando em um número diferente de folhas, teta de n ao cubo sobre m às três metades.

  • 01:10:00 Nesta seção, o palestrante explica como analisar o número de faltas de cache em um algoritmo eficiente de cache usando o exemplo de um código de multiplicação de matriz recursiva. O código ignora o cache, o que significa que ele não tem nenhum conhecimento explícito dos caches e se autoajusta passivamente para o tamanho do cache específico da máquina em que está sendo executado. O palestrante também menciona que os melhores códigos de esquecimento de cache hoje trabalham em matrizes retangulares arbitrárias e realizam divisão binária em vez de divisão de oito vias. O palestrante discute o contexto paralelo e explica como analisar o número de faltas de cache em uma computação de célula determinística que é executada em vários processadores com caches privados.

  • 01:15:00 Nesta seção, o palestrante discute cache e algoritmos eficientes de cache. Ao minimizar as faltas de cache na ilusão serial, podemos essencialmente minimizá-las na execução paralela para algoritmos de baixo alcance. O alto-falante fornece um limite de falta de cache para um algoritmo de multiplicação de matriz recursiva paralela, que é o mesmo que a execução serial. O objetivo é projetar algoritmos que tenham conhecimento explícito do cache ou que olvidem o cache. O palestrante fornece exemplos de ambos e menciona que haverá uma discussão mais aprofundada sobre o design do algoritmo de esquecimento de cache na próxima palestra.
 

Aula 15. Algoritmos Cache-Oblivious



Aula 15. Algoritmos Cache-Oblivious

O vídeo discute algoritmos de esquecimento de cache, que podem ajustar automaticamente o tamanho do cache em uma máquina, obter boa eficiência de cache e não exigem conhecimento dos parâmetros de cache da máquina. O vídeo mostra como escrever código para simular a difusão de calor por meio de equações diferenciais usando o método de estêncil em uma matriz 2D. O código tem versões em loop e trapezoidais, sendo a última mais eficiente em cache, mas não significativamente mais rápida em uma simulação 2D devido à previsibilidade do padrão de acesso do código em loop. O vídeo também discute a interação entre cache e paralelismo e o diagnóstico de possíveis gargalos de aceleração paralela. Por fim, o palestrante explica os cálculos do estêncil e como cada ponto em uma matriz é atualizado usando um padrão fixo chamado estêncil, que pode sofrer erros de cache e tem requisitos de armazenamento que podem ser reduzidos usando algoritmos eficientes que exploram a localidade temporal e espacial.

A segunda parte do vídeo discute algoritmos que ignoram o cache para classificação e mesclagem. Especificamente, o vídeo aborda a complexidade do cache do merge sort, apresenta o conceito de mesclagem multidirecional e explica a complexidade do cache do algoritmo de mesclagem multidirecional. O vídeo também discute o algoritmo de classificação por funil, que é um algoritmo de classificação que ignora o cache e pode mesclar K elementos quadrados e K listas classificadas. O algoritmo funnel sort é ótimo e recursivamente construído com raiz quadrada de K funis. O vídeo explica que existem muitos outros algoritmos e estruturas de dados que ignoram o cache, como b-trees, manutenção ordenada de arquivos e filas de prioridade. No geral, o vídeo fornece uma introdução aos algoritmos de esquecimento de cache para os interessados em aprender mais sobre o assunto.

  • 00:00:00 Nesta seção, o vídeo discute os algoritmos de esquecimento de cache, que são um algoritmo que ajusta automaticamente o tamanho do cache em uma máquina e obtém uma boa eficiência de cache, sem que o código precise ter conhecimento dos parâmetros de cache de a máquina. O vídeo usa o exemplo de simulação de difusão de calor por meio de equações diferenciais para mostrar como a computação científica geralmente depende de equações diferenciais para descrever processos físicos e, em seguida, deve escrever um código eficiente para simular o processo. O vídeo demonstra como escrever código com base no método de aproximação de diferenças finitas para simular a equação de calor 1D.

  • 00:05:00 Nesta seção, o palestrante aborda como escrever código para uma equação de simulação que permite a aproximação de diferenças finitas usando o método de estêncil. A equação usa derivadas parciais de U em relação a T e X, e o palestrante mostra como obter essas derivadas parciais usando métodos de aproximação. O espaço 2D é representado por uma matriz com os valores X e T representados horizontal e verticalmente, respectivamente. O palestrante explica os limites da matriz e calcula U usando a equação.

  • 00:10:00 Nesta seção, o apresentador explica cálculos de estêncil, um método amplamente utilizado em computação científica para diversos fins. Nesse método, cada ponto em uma matriz é atualizado usando um padrão fixo chamado estêncil. O cálculo depende de três outros valores, e isso é conhecido como postura de três pontos. Embora os cálculos de estêncil possam ser usados para valores de X grandes, o desempenho pode ser prejudicado em relação ao armazenamento em cache, resultando em erros de cache. Além disso, o armazenamento necessário para armazenar os dados pode ser reduzido armazenando apenas duas linhas, a atual e as anteriores, para atualizar os valores dos pontos.

  • 00:15:00 funciona: em cada intervalo de tempo, estamos apenas atualizando os valores de X para uma linha específica usando os valores da linha anterior. Assim, podemos alternar qual linha estamos atualizando e qual linha estamos usando como a linha anterior, e só precisamos manter uma linha extra de valores. No entanto, esse código não é muito eficiente em cache e podemos torná-lo ainda mais usando algoritmos de ocultação de cache ou lado a lado. O modelo de cache ideal assume um cache totalmente associativo com uma política de substituição ideal ou LRU e captura faltas de capacidade, mas não faltas de conflito em uma execução serial. No entanto, ainda é útil para projetar algoritmos eficientes que exploram a localidade temporal e espacial.

  • 00:20:00 Nesta seção, o palestrante explica como um algoritmo de esquecimento de cache pode ser usado para calcular pontos dentro de um espaço trapezoidal em uma matriz 2D sem olhar para fora dela. O cálculo envolve uma função de kernel que leva um ponteiro para UT mod para X e retorna W de 0 mais alfa vezes W de 1 negativo menos 2 vezes W de 0 mais W de 1. O comportamento do cache é analisado assumindo a política de substituição LRU, e o número de faltas de cache é Theta de NT sobre B para cada linha. No entanto, o palestrante observa que um melhor desempenho pode ser alcançado com o mosaico, mas continua discutindo a versão sem cache. O trapézio tem uma base superior em T1 e uma base inferior em T0. O algoritmo calcula todos os pontos dentro do trapézio usando condições de desigualdade que envolvem T, t0, t1, X, x0, x1, DX0, DX1, onde DX0 e DX1 são -1, 0 ou 1 representando inclinações.

  • 00:25:00 Nesta seção, o palestrante descreve uma abordagem de dividir e conquistar para o algoritmo da regra do trapézio. A abordagem tem um caso base em que a altura do trapézio é 1 e um loop calcula todos os valores com base na ordem de cálculo. O algoritmo possui dois casos recursivos, a saber, o corte de espaço e o corte de tempo, que dependem da largura e da altura do trapézio, respectivamente. Quando o trapézio é muito largo, um corte de espaço é aplicado onde o trapézio é cortado verticalmente com uma linha com inclinação um negativo passando pelo centro do trapézio. Em contraste, um corte de tempo é aplicado quando o trapézio é muito alto e é cortado com uma linha horizontal passando pelo centro. O algoritmo recursivo faz duas chamadas que percorrem os lados esquerdo e direito do trapézio e inferior e superior, respectivamente, em uma ordem específica para evitar a interdependência entre os pontos.

  • 00:30:00 Nesta seção, o palestrante discute a complexidade do cache dos algoritmos de esquecimento de cache. Eles analisam a abordagem da árvore de recursão e descobrem que o algoritmo se divide em dois subproblemas em cada nível até atingir o caso base, que representa o theta de pontos HW onde H é Theta de W. O número de faltas de cache por folha é theta W sobre B, e o número de folhas é Theta de NT sobre HW. Os nós internos não contribuem substancialmente para a complexidade do cache. A complexidade do cache se generaliza para mais de uma dimensão e, se d for um, resultará em NT sobre MB.

  • 00:35:00 Nesta seção, o palestrante explica a diferença entre o código de loop e o código trapezoidal, que tem uma complexidade de cache muito melhor ao salvar um fator de M onde M é o número de linhas de cache. A simulação demonstra que o código trapezoidal incorre em menos erros de cache em comparação com o código em loop, concluindo a computação muito mais rapidamente. No entanto, o palestrante observa que essa simulação foi apenas para uma dimensão e passa a mostrar uma demonstração do que acontece em duas dimensões.

  • 00:40:00 Nesta seção, o apresentador demonstra uma simulação em tempo real da difusão de calor em um espaço 2D, onde as cores na tela correspondem às temperaturas. O apresentador compara o desempenho do código de loop e do código trapezoidal e revela que, embora o código trapezoidal incorra em muito menos perdas de cache, ele é apenas marginalmente mais rápido do que o código de loop. Sugere-se que isso pode ser devido à pré-busca de hardware ajudando o código em loop, pois seu padrão de acesso é regular e fácil de prever.

  • 00:45:00 Nesta seção, o palestrante discute a interação entre cache e paralelismo. Eles explicam um teorema que afirma que minimizar faltas de cache na execução serial pode essencialmente minimizá-las na execução paralela, assumindo um algoritmo de baixo alcance. Eles então demonstram como o algoritmo trapezoidal pode funcionar em paralelo usando um corte em V, onde dois trapézios independentes são executados em paralelo e o trapézio cinza é executado posteriormente. Eles também mencionam o corte em V invertido que é usado para trapézios invertidos.

  • 00:50:00 Nesta seção, o palestrante discute o desempenho do código de loop paralelo e do código trapezoidal paralelo em comparação com suas contrapartes seriais. O código de loop paralelo atinge menos da metade do aumento de velocidade potencial, apesar de ter mais paralelismo potencial do que o código trapezoidal. Isso ocorre porque, no caso paralelo, há um gargalo de largura de banda de memória, o que impede que a pré-busca ajude o código de loop paralelo, em comparação com o caso serial em que há bastante largura de banda de memória. Em contraste, o código trapezoidal atinge um aumento de velocidade quase linear, o que é consistente com o fato de que a eficiência do cache desempenha um papel muito maior em tamanhos de entrada maiores, nos quais o cache é muito pequeno, em comparação com o tamanho da entrada.

  • 00:55:00 Nesta seção, o palestrante discute como diagnosticar um gargalo de aceleração paralela e identifica várias coisas que podem causar isso, como paralelismo insuficiente, sobrecarga de agendamento, falta de largura de banda de memória e contenção. Eles sugerem várias maneiras de diagnosticar esses problemas, incluindo o uso do Silk Scale para medir o paralelismo no código e a execução de contadores de hardware para medir a largura de banda da memória. No entanto, diagnosticar a contenção é particularmente desafiador, e o palestrante aconselha examinar as três primeiras causas potenciais antes de avaliar se a contenção é o problema. Por fim, o palestrante passa a discutir a computação de estêncil.

  • 01:00:00 Nesta seção, o palestrante discute a análise da complexidade do cache da classificação por mesclagem analisando primeiro a complexidade da mesclagem de duas matrizes de entrada classificadas. O tempo para fazer isso é proporcional à soma dos tamanhos dos arrays de entrada. O número de faltas de cache incorridos ao mesclar n elementos é thetan sobre B, onde B é o número de bytes em uma linha de cache. A classificação por mesclagem tem duas chamadas recursivas em entradas com metade do tamanho e mescla as saídas classificadas de suas chamadas recursivas. O trabalho geral do merge sort é theta de n log n, que é analisado usando o método de árvore de recursão. A complexidade do cache do merge sort também é discutida e é mostrado que o número de faltas de cache é proporcional ao número de blocos de cache necessários para armazenar os dados, que é theta n sobre B log M, onde M é o tamanho máximo a sub-bloco pode ter.

  • 01:05:00 Nesta seção, o palestrante explica a recorrência para a complexidade do cache do merge sort. O caso base ocorre quando o tamanho do problema cabe no cache, incorrendo em Θ(n/B) faltas de cache. Caso contrário, o algoritmo tem duas chamadas recursivas de tamanho n/2 e faltas de cache Θ(n/B) para mesclar os resultados. A análise envolve o número de níveis de uma árvore de recursão, que é log base 2 de n/CM, onde CM é uma constante. O número de faltas de cache por folha é Θ(M/B * n/CM), fornecendo um número geral de faltas de cache de Θ(n/B * log (n/CM)), economizando um fator de B no primeiro termo . No entanto, para tamanhos de problemas maiores, economizamos apenas um fator de B em comparação com o trabalho, enquanto economizamos um fator de B log n para tamanhos de problemas pequenos. O palestrante pergunta se existe uma solução melhor, e a resposta é sempre sim.

  • 01:10:00 Nesta seção, o palestrante explica como usar a mesclagem multidirecional para mesclar subarrays classificados e apresenta a ideia de uma árvore de torneio para determinar os elementos mínimos dos subarrays. Eles também explicam o trabalho e as complexidades de cache dessa abordagem, que é usada em algoritmos de cache para classificação. A complexidade de trabalho da mesclagem multidirecional é a mesma que a classificação de mesclagem binária, enquanto a complexidade do cache é determinada pelo número de faltas de cache necessárias para preencher a árvore do torneio e acessar as matrizes de entrada, que podem ser otimizadas se R for menor que C*M/B para uma pequena constante C.

  • 01:15:00 Nesta seção, o palestrante discute a complexidade do cache do algoritmo de classificação por mesclagem multidirecional e o compara com o algoritmo de classificação por mesclagem binário. O algoritmo de classificação por mesclagem multidirecional envolve a divisão do problema em subproblemas de tamanho n/R e o pagamento de faltas de cache n/B para mesclá-los. O número de níveis da árvore de recursão é log base R de n/cm, e o tamanho da folha é cm. O alto-falante define R igual a theta de M/B, tornando-o o maior possível, e analisa a complexidade do cache, que acaba sendo thetan log n dividido por B log M. Comparado com o algoritmo de classificação de mesclagem binária, o multi -way merge sort algoritmo salva um fator de log M em faltas de cache. No entanto, o algoritmo não ignora o cache e o valor de R precisa ser ajustado para uma máquina específica, o que pode ser um problema se outras tarefas estiverem em execução e competirem pelo cache.

  • 01:20:00 Nesta seção, o palestrante discute o algoritmo de classificação por funil, que é um algoritmo de classificação que ignora o cache e pode mesclar K elementos quadrados e K listas classificadas. O custo dessa mesclagem é o mesmo do algoritmo de ordenação de mesclagem multidirecional, mas o algoritmo de ordenação por funil é indiferente ao cache e seu limite é ideal. O palestrante apresenta uma imagem de como é um funil K e explica que o algoritmo é construído recursivamente com raiz quadrada de funis K que alimentam elementos para buffers, que, por sua vez, alimentam elementos para a raiz quadrada de saída final do funil K, produzindo a saída para o funil K. O palestrante também menciona que existem muitos outros algoritmos e estruturas de dados que ignoram o cache, como b-trees, manutenção de arquivos ordenada e filas de prioridade, e convida os espectadores a aprender mais sobre eles online.
 

Aula 16. Programação Paralela Não Determinística



Aula 16. Programação Paralela Não Determinística

Este vídeo discute vários conceitos relacionados à programação paralela determinística e não determinística. O palestrante enfatiza a importância de evitar o não determinismo, pois pode levar a comportamentos anômalos e depuração difícil. As estratégias para gerenciar o não determinismo incluem o uso de valores fixos, repetição de registros, ferramentas de análise, encapsulamento e teste de unidade. O uso de mutexes é explorado em detalhes, incluindo girando x cedendo, reentrante x não reentrante e justo x injusto. O palestrante também aborda o conceito de troca de contexto e o "problema do aluguel de esquis" no contexto da programação paralela. O segmento conclui discutindo os princípios básicos da engenharia de desempenho em processadores multi-core.

A segunda parte do vídeo aborda o problema de deadlock na programação paralela e oferece soluções para evitá-lo, como ordenação linear de mutexes que garante que não haja ciclo de espera. Além disso, o palestrante apresenta o conceito de memória transacional, que garante atomicidade ao representar uma região crítica como uma transação que confirma todas as atualizações de uma só vez. Em seguida, o vídeo apresenta um algoritmo que usa uma abordagem baseada em bloqueio com uma matriz de propriedade finita e um método de exigência de classificação de liberação para evitar impasses e privação sem a necessidade de um bloqueio global. Por fim, é explicado o algoritmo release sort e readquirir, o que evita que vários bloqueios tentem adquirir um bloqueio simultaneamente, evitando problemas de desempenho.

  • 00:00:00 Nesta seção, o palestrante apresenta o conceito de determinismo na programação e como ele se relaciona com a computação paralela. Um programa é determinístico se cada localização de memória é atualizada com a mesma sequência de valores em cada execução, e o programa sempre se comporta da mesma forma. Os programas determinísticos têm a vantagem de serem repetíveis, tornando-os mais fáceis de depurar. O palestrante enfatiza a importância de nunca escrever programas paralelos não determinísticos, pois eles podem apresentar comportamentos anômalos e difíceis de depurar. No entanto, na prática, pode ser um desafio evitar o não determinismo na computação paralela.

  • 00:05:00 Nesta seção, o palestrante discute a programação paralela não determinística e o fato de que às vezes pode levar a um melhor desempenho, mas ainda deve ser evitada, a menos que seja necessário. O palestrante recomenda desenvolver uma estratégia de teste para gerenciar o não determinismo se você precisar escrever um programa dessa maneira. Exemplos de estratégias incluem desativar o não determinismo, usar a mesma semente para números aleatórios ou fornecer valores fixos para entradas de programa que, de outra forma, poderiam mudar aleatoriamente. O palestrante enfatiza a importância de se ter uma forma de tratar bugs no programa causados por não determinismo.

  • 00:10:00 Nesta seção, o palestrante fala sobre estratégias para lidar com programação não determinística, como repetição de gravação, encapsulamento de não determinismo, substituição por uma alternativa determinística, uso de ferramentas de análise e teste de unidade. O palestrante enfatiza a importância de controlar o não determinismo para melhorar as chances de detecção de bugs no código. O palestrante também fornece um exemplo de uso de exclusão mútua e atomicidade em uma tabela de hash para ilustrar como lidar com programação não determinística.

  • 00:15:00 Nesta seção, o palestrante discute como instruções paralelas acessando o mesmo local podem levar a erros de corrida e destruir a integridade do sistema. A solução padrão é tornar algumas instruções atômicas, o que significa que elas são vistas como totalmente executadas ou não executadas pelo resto do sistema. Para conseguir isso, um bloqueio de exclusão mútua ou bloqueio mutex é usado, que é um objeto com funções de membro de bloqueio e desbloqueio. Cada slot é feito em uma struct com um mutex lock e uma cabeça de ponteiro para o contexto do slot, permitindo que as funções lock e unlock sejam usadas antes de acessar a lista, garantindo assim a correção do sistema.

  • 00:20:00 Nesta seção, o vídeo explora o uso de mutexes para implementar a atomicidade e como ela se relaciona com as corridas de determinação. Os bloqueios mutex podem garantir que as seções críticas sejam atômicas, mas o código resultante é não determinístico devido a uma corrida de determinação que pode ser o desejado em alguns casos. O vídeo enfatiza a importância de entender a diferença entre corridas de dados e corridas de determinação, e observa que simplesmente eliminar corridas de dados não significa necessariamente que não há bugs presentes no código. É importante ter uma maneira de detectar o não determinismo para evitar falsos positivos ou erros de corrida ausentes no código.

  • 00:25:00 Nesta seção, o palestrante explica que não ter corridas de dados não significa necessariamente que o código não tenha bugs. Embora nenhuma corrida de dados seja um aspecto positivo do código, o exemplo de bloqueio para fornecer atomicidade pode levar a uma violação de atomicidade. Além disso, corridas benignas podem ocorrer, como quando dois processos paralelos estão acessando o mesmo valor, o que pode resultar no mesmo resultado, mas também pode levar a valores incorretos em algumas arquiteturas. O palestrante argumenta que, embora algumas pessoas considerem as raças benignas como inofensivas, ainda é essencial identificá-las e evitá-las.

  • 00:30:00 Nesta seção, o palestrante explica os perigos da programação não determinística, principalmente devido a condições de corrida que podem ocorrer quando vários processos tentam definir valores no mesmo local. O palestrante apresenta o conceito de "Silks", que permite corridas intencionais, mas pode ser perigoso se não for usado corretamente. A complexidade das corridas também pode dificultar a depuração e confundir as ferramentas destinadas a ajudar a detectar o código correto. O palestrante também discute como a implementação de mutexes e seus parâmetros podem afetar seu comportamento, como se eles estão cedendo ou girando.

  • 00:35:00 Nesta seção, o vídeo explica três propriedades básicas de mutexes em programação paralela: girando x cedendo, reentrante x não reentrante e justo x injusto. O conceito de girar versus ceder é a ideia de que um encadeamento não ficará ocioso e verificará continuamente o acesso a um bloqueio, mas cederá o controle ao sistema operacional para uma execução mais eficiente. O mutex reentrante permite que um thread que já está segurando um bloqueio o adquira novamente, enquanto os bloqueios não reentrantes entrarão em conflito se o thread tentar readquirir um mutex que já possui. Por fim, o mutex justo garante que o thread que está esperando há mais tempo obtenha o bloqueio primeiro para evitar a possibilidade de um problema de inanição. O vídeo também fornece uma implementação de um mutex giratório simples em linguagem assembly.

  • 00:40:00 Nesta seção, o vídeo discute o uso de mutex na programação paralela e por que a instrução de troca é usada em vez de apenas obter o mutex. Explica-se que a operação de câmbio é semelhante a um direito, e para realizar um direito, a linha de caixa em que se encontra deve ser invalidada nas demais e mantida em estado modificado ou exclusivo. Isso cria tráfego na rede de memória e retarda o processo. Por outro lado, usando a instrução exchange, as linhas de cache são colocadas em estado compartilhado, mantendo assim o processo mais rápido e gerando menos tráfego.

  • 00:45:00 Nesta seção, o palestrante discute a diferença entre um mutex giratório e um mutex maleável. Em um mutex giratório, o programa continua verificando se o mutex está desbloqueado, enquanto em um mutex flexível, o programa cede o controle ao sistema operacional, o que permite agendar outra coisa. O palestrante observa que há também outro tipo de mutex chamado mutex competitivo, que atinge os dois objetivos de um mutex giratório e de um mutex flexível. O palestrante também explora o uso de passagem de mensagens ou interrupções para informar threads em espera, mas observa que a solução mais simples seria usar um mecanismo de exclusão mútua.

  • 00:50:00 Nesta seção, o palestrante explica o conceito de troca de contexto, que é a frequência com que o sistema operacional alterna entre threads nos processadores disponíveis. Normalmente, o sistema faz troca de contexto cerca de 100 vezes por segundo, o que significa que cada troca leva cerca de 10 milissegundos. No entanto, isso é mais do que uma ordem de grandeza maior do que o tempo de execução de uma instrução simples, o que significa que muitas instruções podem ser executadas antes que o thread tenha a chance de voltar e obter um bloqueio. Este problema pode ser resolvido usando uma combinação de fiação e escoamento. O palestrante chama isso de "problema de aluguel de esqui" na literatura teórica.

  • 00:55:00 Nesta seção, o vídeo discute o processo de decisão de comprar ou alugar equipamentos para uma determinada tarefa, usando o exemplo de compra ou aluguel de equipamentos esportivos. O palestrante incentiva os espectadores a considerar os custos de aluguel versus compra e sugere alugar até que o custo seja igual ao da compra e, em seguida, fazer a compra. O vídeo também explora o conceito de tempo de troca de contexto, tempo de acesso ao disco e a questão do impasse ao manter vários bloqueios ao mesmo tempo. No geral, este segmento cobre os princípios básicos de engenharia de desempenho em processadores multi-core.

  • 01:00:00 Nesta seção, o palestrante explica o deadlock, que é quando duas threads retêm recursos que são exigidos pela outra thread, levando à perda de desempenho. Existem três condições básicas para o deadlock: exclusão mútua (controle exclusivo sobre recursos), não preempção (recursos retidos até terminar) e espera circular (um ciclo de threads aguardando recursos retidos pelo próximo). A remoção de qualquer uma dessas restrições pode resolver o problema de impasse. O palestrante usa "Dining Philosophers", uma história contada por Tony Hoare com base em uma questão de exame de Edsger Dijkstra, para ilustrar o problema do impasse. A história envolve filósofos sentados ao redor de uma mesa, comendo macarrão com pauzinhos onde cada prato de macarrão está situado entre dois pauzinhos, e eles precisam de dois pauzinhos para comer o macarrão. Os filósofos pegam o pauzinho à esquerda e à direita para comer o macarrão. No entanto, se todos pegarem o pauzinho esquerdo à sua esquerda, acabarão morrendo de fome.

  • 01:05:00 Nesta seção, o palestrante discute a questão do impasse na programação paralela e oferece uma solução que garante a não preempção e evita o impasse: ordenação linear de mutexes. Ao numerar cada mutex e bloqueá-los estrategicamente com base em sua ordem numérica, os programadores podem garantir que um ciclo de espera (a condição necessária para o impasse) não ocorra. No entanto, ele alerta os programadores para estarem cientes do encapsulamento de bloqueios do sistema de tempo de execução no Silk, pois a introdução de não determinismo adicional por meio desses bloqueios pode causar problemas. Ele compartilha um exemplo em que um impasse pode ocorrer com apenas um bloqueio, enfatizando a importância de uma consideração cuidadosa ao projetar programas paralelos.

  • 01:10:00 Nesta seção, o palestrante aprofunda o tema da memória transacional, uma técnica recente em nível de pesquisa que envolve transações de banco de dados onde a atomicidade acontece implicitamente, sem a necessidade de especificar bloqueios. O palestrante dá um exemplo de como a memória transacional é útil na computação de grafos concorrentes, ou seja, eliminação Gaussiana, onde ter dois nós eliminados simultaneamente causa violações de atomicidade. A ideia por trás da memória transacional é representar a região crítica como uma transação e, ao confirmar, todas as atualizações de memória na região crítica aparecem como se tivessem acontecido de uma só vez.

  • 01:15:00 Nesta seção, o palestrante discute a resolução de conflitos, resolução de disputas, progresso de encaminhamento e taxa de transferência na memória transacional. Eles introduzem um algoritmo que usa uma abordagem baseada em bloqueio com uma matriz de propriedade finita e um método de exigência de classificação de liberação para evitar impasses e privação sem precisar de um bloqueio global. O algoritmo registra leituras e gravações para permitir reversão ou confirmação atômica quando uma transação é interrompida. A matriz de bloqueio é usada para bloquear um local para o qual uma função hash mapeia, permitindo a aquisição justa de bloqueios. Esse algoritmo permite transações simultâneas sem sacrificar o desempenho ou causar impasses.

  • 01:20:00 Nesta seção, o palestrante discute um algoritmo chamado release sort and readquire. O algoritmo funciona tentando avidamente adquirir um bloqueio de um local de memória e, se surgir um conflito, a transação é revertida sem liberar os bloqueios que possui. Em seguida, o algoritmo libera todos os bloqueios com índices maiores que o índice do local que está tentando acessar. Em seguida, ele adquire o bloqueio desejado e, finalmente, adquire os bloqueios liberados em ordem de classificação. Esse processo é repetido até que a transação seja bem-sucedida. O algoritmo é projetado para evitar que vários bloqueios tentem adquirir um bloqueio simultaneamente, o que pode causar problemas de desempenho.
 

Aula 17. Sincronização Sem Bloqueios



Aula 17. Sincronização Sem Bloqueios

Charles Leiserson explora o conceito de sincronização sem bloqueios em um vídeo do YouTube. Ele fornece um exemplo que demonstra a necessidade de uma ordem linear global de instruções para garantir a execução sequencial e discute como a exclusão mútua pode ser alcançada por meio da consistência sequencial, evitando as dificuldades e problemas potenciais do uso de bloqueios. Leiserson apresenta o algoritmo de Peterson como uma solução que usa apenas operações de carregamento e armazenamento para acessar seções críticas sem interferência de processos simultâneos. O vídeo também aborda os desafios da sincronização por meio da memória devido ao reordenamento de hardware e o conceito de cercas de memória para manter a ordenação relativa com outras instruções. Leiserson argumenta que o suporte à consistência sequencial para máquinas paralelas é benéfico, mas difícil de alcançar para os projetistas de hardware.

A segunda parte do vídeo discute o uso de limites de memória e instruções de sincronização na prevenção de erros em programas paralelos. O palestrante explora diferentes formas de implementar cercas de memória, implícita ou explicitamente, e a importância de uma engenharia cuidadosa e coordenação entre diferentes equipes trabalhando em diferentes aspectos de um processador. Além disso, o palestrante discute o uso de instruções CAS como parte do algoritmo livre de travamento no padrão de linguagem C11 para implementar mutexes de algoritmos de exclusão mútua livre de impasse n-thread usando apenas espaço constante. Charles Leiserson explica o problema de usar bloqueios em um sistema multithread e a solução de usar o CAS, pois um thread segurando o bloqueio por um longo tempo pode potencialmente bloquear outros threads esperando para acessar o mesmo recurso. Além disso, o vídeo destaca o problema potencial do problema ABA com comparação e troca e incentiva os interessados no tópico a aprender mais sobre algoritmos sem bloqueio.

  • 00:00:00 e suas instruções são intercaladas para produzir uma ordem linear global de todas as instruções. Essa é a ideia por trás do modelo de memória de consistência sequencial, que é o modelo de memória mais importante do ponto de vista teórico. É importante entender os modelos de memória porque, na ausência de bloqueios, o comportamento dos programas paralelos depende do modelo de memória. Um exemplo apresentado na palestra ilustra esse ponto perguntando se é possível que dois processadores tenham o valor 0 após executarem seu código em paralelo, o que depende do modelo de memória que está sendo usado.

  • 00:05:00 Nesta seção, Charles Leiserson discute o conceito de sincronização sem bloqueios onde as cargas e os armazenamentos devem parecer obedecer a alguma ordem linear global para que a execução seja sequencial. Ele usa o exemplo de intercalar vários valores para demonstrar diferentes caminhos de execução que podem ocorrer e como o hardware pode fazer o que quiser. Ele também explica que, embora possa haver muitas maneiras diferentes de intercalar valores, deve parecer que as cargas e os armazenamentos seguiram uma ordem linear para que a execução seja consistente. Em última análise, Leiserson conclui que não há execução que termine com ambos os valores sendo zero, e é interessante notar que dos computadores modernos, nenhum deles fornece consistência sequencial.

  • 00:10:00 Nesta seção, o conceito de consistência sequencial é discutido, o que envolve entender o que acontece antes da relação entre as instruções e sua ordem, a relação linear entre a conexão da seta para a direita, a ordem do processador e o sequenciamento das instruções. Além disso, a exclusão mútua pode ser realizada sem o uso de instruções ou bloqueios pesados, pensando na consistência sequencial e implementando a estrutura de dados compartilhada por meio do uso de cargas e armazenamentos. As notas de aula descrevem métodos que usam operações especializadas, como testar e definir ou comparar e trocar, mas a solução apresentada evita a criação de impasses ou outras coisas ruins que ocorrem ao usar bloqueios.

  • 00:15:00 Nesta seção, Charles Leiserson explica o algoritmo de Peterson para obter exclusão mútua em um programa concorrente usando apenas operações de carregamento e armazenamento. O algoritmo permite que dois processos simultâneos, Alice e Bob, executem código sem interferir um no outro usando um conjunto de variáveis e um mecanismo de tomada de turno. O código garante que apenas um processo por vez possa entrar em uma seção crítica e modificar um recurso compartilhado. Ao contrário dos bloqueios, o algoritmo de Peterson não depende da aquisição ou liberação de um bloqueio e, em vez disso, usa carregamentos e armazenamentos para obter exclusão mútua.

  • 00:20:00 Nesta seção, o palestrante discute o algoritmo de Peterson para obter exclusão mútua na seção crítica sem usar bloqueios. Ele explica que apenas uma pessoa por vez pode entrar na seção crítica, e o algoritmo garante que alguém que queira entrar na seção crítica possa fazê-lo se for o único que deseja ir. O palestrante então apresenta uma prova do algoritmo, que envolve assumir que Alice e Bob se encontram juntos na seção crítica e derivam uma contradição. A prova depende do relacionamento "acontece antes" e da ordem do programa das instruções executadas.

  • 00:25:00 Nesta seção, o palestrante explica o processo de sincronização sem bloqueios. Eles estabelecem cadeias de instruções e garantem que ocorram na ordem correta para evitar erros de sincronização. Eles usam o exemplo de Bob e Alice querendo acessar um recurso compartilhado como demonstração. Eles explicam que, ao sincronizar, os engenheiros precisam ter cuidado e revisar os "acontecimentos antes das coisas" para garantir que estejam ocorrendo na ordem correta.

  • 00:30:00 Nesta seção, Charles Leiserson discute o conceito de verificação de modelo e seu uso na análise de rede, segurança e protocolos de cache. Ele então passa a explicar as propriedades do algoritmo de Peterson, que garante a liberdade de inanição, mas não funciona com mais de dois processos. Leiserson também explora os desafios da sincronização por meio da memória e a falta de consistência sequencial nos processadores modernos, o que leva a uma consistência de memória relaxada e à dificuldade de obter a sincronização correta.

  • 00:35:00 é seguro reordenar as instruções sem causar problemas de latência de carregamento? A segunda restrição é quando não há dependência de dados entre as instruções, o que significa que as instruções não compartilham dados ou usam o mesmo local na memória. Reordenar as instruções neste caso pode melhorar o desempenho e cobrir a latência de carga, pois a carga pode ser feita mais cedo e outro trabalho pode ser feito enquanto se espera pelo resultado. Compreender esses conceitos de nível de hardware pode ajudar a raciocinar sobre software e otimizar o desempenho.

  • 00:40:00 Nesta seção, Charles Leiserson explica o conceito de reordenar na sincronização sem bloqueios. Ele esclarece que a reordenação é segura desde que não haja concorrência, principalmente quando o processador está operando ou há bolhas no fluxo de instruções. Isso ocorre porque, nos processadores modernos, o hardware armazena os dados em um buffer e desvia as cargas indo diretamente para o sistema de memória. No entanto, esse desvio pode levar a problemas de exatidão se uma das lojas for a coisa que está sendo carregada.

  • 00:45:00 Nesta seção, Charles Leiserson explica como ocorre a reordenação de hardware e por que não satisfaz a consistência sequencial, e como o x86 tem um modelo de consistência de memória chamado ordem total de armazenamento, que é mais fraco que a consistência sequencial. As regras para o pedido total da loja incluem nunca reordenar cargas com cargas, cargas sendo vistas na mesma ordem por processadores externos, lojas nunca sendo reordenadas com lojas e cargas sendo reordenadas apenas com lojas anteriores para um local diferente, mas não com cargas anteriores para o mesmo local. As instruções de bloqueio e ordenação de memória respeitam uma ordem total.

  • 00:50:00 Nesta seção, o palestrante discute como a reordenação de instruções pode violar a consistência sequencial e resultar em valores incorretos. A reordenação pode ocorrer tanto no hardware quanto no compilador, e é importante saber que as instruções de bloqueio não serão movidas antes de outras instruções. O palestrante também destaca que as cargas podem ir antes das lojas se forem para um endereço diferente. O perigo da reordenação é demonstrado no algoritmo de Peterson, que pode ser completamente danificado se certas reordenações ocorrerem. Portanto, é importante escrever um código determinístico para evitar esses problemas ao sincronizar por meio da memória.

  • 00:55:00 Nesta seção, Charles Leiserson discute a questão da reordenação ao escrever código paralelo e simultâneo, onde é importante evitar que uma determinada carga ocorra antes de uma loja. Para lidar com tais cenários, os engenheiros introduzem cercas de memória, que mantêm a ordem relativa com outras instruções, mas vêm com o custo de maior complexidade e possíveis bugs. Leiserson também argumenta que é benéfico para máquinas paralelas oferecer suporte à consistência sequencial, mas é um desafio para os projetistas de hardware realizar.

  • 01:00:00 Nesta seção, o palestrante discute a importância dos limitadores de memória e das instruções de sincronização para evitar que programas paralelos encontrem erros. O falante descreve diferentes maneiras pelas quais as cercas de memória podem ser implementadas, como explicitamente como uma instrução ou implicitamente por meio de outras instruções de sincronização, como bloqueio e troca. No entanto, há casos em que um limitador de memória pode realmente desacelerar um programa, mostrando a importância de uma engenharia cuidadosa e coordenação entre diferentes equipes trabalhando em diferentes aspectos de um processador. Além disso, o palestrante aconselha o uso de variáveis voláteis e cercas do compilador para evitar que o compilador otimize as variáveis e cause erros no código paralelo.

  • 01:05:00 Nesta seção, o palestrante aborda a sincronização sem bloqueios no padrão de linguagem C11. O padrão define um modelo de memória fraca, que permite declarar coisas como atômicas, exigindo o uso de operações caras como cerca de memória ou uma comparação e troca atômica para um algoritmo de exclusão mútua livre de impasse. Aqui, a instrução CAS (Compare-and-Swap) é explorada como parte do algoritmo lock-free. A instrução verifica se o valor na memória é igual ao valor antigo antes de trocá-lo pelo novo valor, tudo feito atomicamente. O uso do CAS permite a implementação de mutexes de algoritmos de exclusão mútua sem impasse n-thread usando apenas espaço constante. Uma instrução de bloqueio, que gira até obter o valor true, é usada para trocar em true informando que alguém detém o bloqueio.

  • 01:10:00 Nesta seção, o professor Charles Leiserson explica como usar comparar e trocar (CAS) para resolver problemas de sincronização. Ele demonstra como usar o CAS como trava e corrige um bug no código apresentado por um aluno. Ele então apresenta um código incorreto usado para calcular a soma dos valores em uma matriz, o que leva a uma condição de corrida. Ele apresenta bloqueios mutex como uma solução típica e explica o problema potencial de um encadeamento sendo trocado após adquirir o bloqueio, levando a outros encadeamentos esperando pelo bloqueio, impedindo assim o progresso.

  • 01:15:00 Nesta seção, Charles Leiserson explica o problema de usar bloqueios em um sistema multi-thread e a solução de usar o CAS. Com bloqueios, um encadeamento pode segurar o bloqueio por um longo tempo, bloqueando outros encadeamentos que aguardam para acessar o mesmo recurso. No entanto, com o CAS, uma carga de x é seguida por um armazenamento de x depois de calcular um temp, além de ter as variáveis old e new para armazenar o resultado antigo e adicionar o resultado temporário a esse valor antigo para produzir um novo valor que pode ser trocado se o valor antigo não foi alterado. Charles também menciona o problema ABA com comparação e troca e incentiva os interessados no tópico a aprender mais sobre algoritmos sem bloqueio.
1...232425262728293031323334353637...74
Novo comentário