Você está perdendo oportunidades de negociação:
- Aplicativos de negociação gratuitos
- 8 000+ sinais para cópia
- Notícias econômicas para análise dos mercados financeiros
Registro
Login
Você concorda com a política do site e com os termos de uso
Se você não tem uma conta, por favor registre-se
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.