Perguntas P2 PCP PDF

Processadores Memória Elementos de Conexão 1. Conceitos Básicos de Conectividade: a) Defina "grau", "diâmetro" e "largura de bissecção" em uma rede de interconexão. b) Qual a importância desses parâmetros na avaliação do desempenho de uma rede? c) Desenhe um exemplo de uma pequena rede estática e...

Processadores Memória Elementos de Conexão 1. Conceitos Básicos de Conectividade: a) Defina "grau", "diâmetro" e "largura de bissecção" em uma rede de interconexão. b) Qual a importância desses parâmetros na avaliação do desempenho de uma rede? c) Desenhe um exemplo de uma pequena rede estática e calcule seu grau, diâmetro e largura de bissecção. 2. Redes Estáticas vs. Dinâmicas: a) Compare e contraste redes estáticas e dinâmicas, destacando suas vantagens e desvantagens. b) Dê exemplos de topologias de redes estáticas e dinâmicas. c) Em que situações cada tipo de rede é mais adequado? 3. Função de Roteamento: a) O que é uma função de roteamento? b) Qual o seu papel em uma rede de interconexão? c) Dê um exemplo de uma função de roteamento simples. 4. Redes de Alta Velocidade e Latência: a) Quais são os dois principais aspectos a serem considerados para se obter alta velocidade em uma rede de interconexão? b) Explique o que é latência e como ela afeta o desempenho de aplicações paralelas. c) Descreva como o RDMA (Remote Direct Memory Access) ajuda a reduzir a latência. 5. RDMA e Protocolos: a) Quais são as principais vantagens do RDMA? b) Explique as diferenças entre RoCE, iWARP e InfiniBand em relação ao RDMA. 6. Tecnologias de Interconexão: Compare e contraste as seguintes tecnologias de interconexão, considerando desempenho, custo e aplicabilidade: Ethernet Infiniband Omni-Path Myrinet 7. Topologia Clos (Spine-Leaf): a) Descreva a topologia Clos (spine-leaf) e explique como ela contribui para a redução do diâmetro da rede. b) Quais as vantagens desta topologia em relação a outras topologias de redes? 8. Tendências em Redes de Alta Velocidade: a) Quais são as principais tendências e desafios no desenvolvimento de redes de interconexão de alta velocidade para HPC? b) Discuta o papel das tecnologias emergentes, como redes ópticas e chips de interconexão, no futuro da computação de alto desempenho. RESPOSTAS Vamos às respostas das perguntas sobre Elementos de Conexão: 1. Conceitos Básicos de Conectividade: a) * Grau: Número de conexões diretas que um nó possui. Diâmetro: Maior distância mínima (em número de saltos) entre quaisquer dois nós da rede. Largura de Bissecção: Número mínimo de conexões que precisam ser cortadas para dividir a rede em duas metades iguais (ou o mais próximo possível disso). b) Esses parâmetros afetam diretamente o desempenho da rede. Um grau maior permite maior concorrência na comunicação. Um diâmetro menor reduz a latência. Uma largura de bissecção maior permite maior vazão de dados entre diferentes partes da rede. c) Exemplo (rede em anel com 4 nós): Unset Nó 1 -- Nó 2 | | Nó 4 -- Nó 3 Grau: 2 (cada nó tem duas conexões) Diâmetro: 2 (a maior distância mínima é entre Nó 1 e Nó 3, ou Nó 2 e Nó 4) Largura de Bissecção: 2 (cortando as conexões Nó 1-Nó 2 e Nó 3-Nó 4) 2. Redes Estáticas vs. Dinâmicas: a) Estáticas: Conexões físicas fixas entre os nós. Vantagens: menor latência, mais simples de implementar. Desvantagens: menor flexibilidade, escalabilidade limitada. Dinâmicas: Conexões estabelecidas por switches ou roteadores, podendo variar com o tempo. Vantagens: maior flexibilidade, melhor escalabilidade. Desvantagens: maior latência devido aos switches/roteadores, mais complexas de gerenciar. b) Estáticas: Anel, malha, árvore, hipercubo. Dinâmicas: Redes crossbar, redes multiestágios (como a rede ômega), redes em barramento. c) Estáticas: Adequadas para sistemas menores com padrões de comunicação previsíveis. Dinâmicas: Adequadas para sistemas maiores com padrões de comunicação variáveis. 3. Função de Roteamento: a) Determina o caminho que uma mensagem deve seguir na rede para ir do nó de origem ao nó de destino. b) Garante que as mensagens cheguem ao destino correto, mesmo em redes complexas com múltiplos caminhos possíveis. c) Exemplo (roteamento XY em uma malha 2D): Uma mensagem do nó (x1, y1) para o nó (x2, y2) primeiro percorre a dimensão X até x2 e depois a dimensão Y até y2. 4. Redes de Alta Velocidade e Latência: a) Baixa latência e alta vazão (bandwidth). b) Latência é o tempo que uma mensagem leva para ir da origem ao destino. Latência alta prejudica o desempenho, especialmente em aplicações com muita comunicação entre os nós. c) RDMA permite que um processo acesse diretamente a memória de outro processo em um nó remoto, sem envolvimento do sistema operacional ou da CPU do nó remoto. Isso reduz a latência e o overhead de processamento associado à comunicação. 5. RDMA e Protocolos: a) Vantagens do RDMA: Baixa latência, alta vazão, baixo uso de CPU. b) * RoCE (RDMA over Converged Ethernet): Permite o uso de RDMA sobre redes Ethernet, aproveitando a infraestrutura existente. iWARP (Internet Wide Area RDMA Protocol): Protocolo para RDMA sobre redes IP, permitindo comunicação de longa distância. Infiniband: Protocolo de alta performance projetado desde o início para RDMA, com baixa latência e alta vazão. 6. Tecnologias de Interconexão: Ethernet: Baixo custo, amplamente disponível, mas latência relativamente alta em comparação com as outras. Infiniband: Alta performance, baixa latência, alto custo. Comum em clusters de HPC. Omni-Path: Desenvolvida pela Intel, alta performance, similar ao Infiniband, mas com menor adoção no mercado. Myrinet: Alta performance, baixa latência, mas com menor presença no mercado atualmente. 7. Topologia Clos (Spine-Leaf): a) Topologia hierárquica em que os nós "leaf" se conectam aos nós "spine", e os nós "spine" se conectam entre si. O diâmetro da rede é baixo e constante, independentemente do número de nós. b) Vantagens: Baixo diâmetro, alta largura de bissecção, fácil escalabilidade. 8. Tendências em Redes de Alta Velocidade: a) Maior largura de banda, menor latência, maior eficiência energética, suporte para novas tecnologias como computação quântica. Desafios incluem o gerenciamento da complexidade, o custo e a dissipação de calor. b) Redes ópticas oferecem maior largura de banda e menor latência, enquanto chips de interconexão permitem maior integração e densidade. Essas tecnologias são cruciais para atender às demandas crescentes de desempenho da computação de alto desempenho. Condições de Paralelismo 1. Classificação de Dependências: Identifique o tipo de dependência de dados (fluxo, antidependência ou saída) presente em cada um dos seguintes trechos de código: a) Unset x = a + b; y = x * c; b) Unset a = b * 2; b = c + 1; c) Unset x = a + b; x = c * d; 2. Aplicando as Condições de Bernstein: Considere os seguintes processos e seus conjuntos de entrada e saída: P1: I1 = {a, b}, O1 = {c} P2: I2 = {c, d}, O2 = {e} P3: I3 = {b, e}, O3 = {f} Determine quais processos podem ser executados em paralelo de acordo com as Condições de Bernstein. Justifique sua resposta. 3. Identificando Dependências em Laços: Analise o seguinte trecho de código e identifique se existe alguma dependência de dados que impede a paralelização do laço: Unset for (int i = 1; i < N; ++i) { a[i] = a[i-1] + b[i]; } Explique o tipo de dependência, se houver. 4. Dependência de Controle: Explique porque dependências de controle podem dificultar a paralelização de um programa. Dê um exemplo de código com dependência de controle e explique como ela afeta o paralelismo. 5. Granulação e Comunicação: a) Defina os três níveis de granulação de paralelismo (fino, médio e grosso) e dê exemplos de cada um. b) Explique como a velocidade de comunicação entre os processadores/threads influencia a escolha do tamanho do grão. 6. Balanceamento de Paralelismo: Considere um programa com um paralelismo de software de 8 instruções e um paralelismo de hardware de 4 unidades de processamento. Explique como o balanceamento entre software e hardware pode ser alcançado. Quais são as estratégias que podem ser utilizadas? 7. Situações Indeterminadas: Explique o que são "situações indeterminadas" no contexto da análise de dependência. Dê um exemplo de código onde a paralelização é dificultada por uma situação indeterminada. 8. Cenário Real: Imagine que você precisa paralelizar um programa de processamento de imagens. Quais fatores você considera ao escolher o nível de granulação do paralelismo? Justifique sua resposta. RESPOSTAS Vamos às respostas das questões sobre Condições de Paralelismo: 1. Classificação de Dependências: a) Fluxo: O valor de x calculado na primeira linha é usado na segunda. b) Antidependência: O valor de b é lido na primeira linha antes de ser sobrescrito na segunda. c) Saída: Ambas as linhas atribuem um valor à mesma variável x. 2. Aplicando as Condições de Bernstein: P1 // P2: Sim, pois I1 ∩ O2 = ∅, I2 ∩ O1 = ∅, e O1 ∩ O2 = ∅. P1 // P3: Sim, pois I1 ∩ O3 = ∅, I3 ∩ O1 = ∅, e O1 ∩ O3 = ∅. P2 // P3: Não, pois I3 ∩ O2 = {e} ≠ ∅ (dependência de fluxo). Portanto, P1 pode ser executado em paralelo com P2 e P3, mas P2 e P3 não podem ser executados em paralelo entre si. 3. Identificando Dependências em Laços: Existe uma dependência de fluxo dentro do laço. O valor de a[i] em cada iteração depende do valor de a[i-1] calculado na iteração anterior. Isso impede a paralelização direta do laço. Técnicas como redução ou reescrita do laço podem ser necessárias para paralelizá-lo. 4. Dependência de Controle: Dependências de controle surgem quando o fluxo de execução do programa depende de decisões tomadas em tempo de execução, como em um if. Isso dificulta o paralelismo, pois não se sabe de antemão quais instruções serão executadas. Exemplo: Unset if (condição) { // Bloco de código 1 } else { // Bloco de código 2 } Se condição só for avaliada em tempo de execução, não é possível executar os blocos 1 e 2 em paralelo, pois apenas um deles será executado. 5. Granulação e Comunicação: a) Fino: Pequenos blocos de código, como instruções individuais ou laços curtos. Ex: operações vetoriais. Médio: Funções, procedimentos ou tarefas. Ex: processamento de uma parte de uma imagem. Grosso: Programas inteiros ou grandes partes de um programa. Ex: execução de diferentes estágios de um pipeline em paralelo. b) A velocidade de comunicação é crucial. Se a comunicação for rápida, grãos finos são viáveis, pois o overhead da comunicação é baixo. Se a comunicação for lenta, grãos maiores são preferíveis para minimizar a comunicação entre processadores/threads. 6. Balanceamento de Paralelismo: O balanceamento pode ser obtido replicando as 4 unidades de processamento para igualar o paralelismo do software (8). Outra opção seria dividir as 8 instruções paralelas em grupos menores que possam ser executados pelas 4 unidades, embora isso possa introduzir overhead. A melhor estratégia depende do custo de replicação de hardware versus o overhead de gerenciamento de software. 7. Situações Indeterminadas: São situações em que as dependências de dados não podem ser determinadas em tempo de compilação. Isso ocorre frequentemente em laços com indexação complexa. Exemplo: Unset for (int i = 0; i < N; ++i) { a[b[i]] = c[i]; } Se os valores em b não forem conhecidos em tempo de compilação, não é possível determinar se haverá dependências de dados entre as iterações do laço, dificultando a paralelização. 8. Cenário Real (Processamento de Imagens): Para processamento de imagens, a granulação média (processar blocos ou regiões da imagem) costuma ser uma boa escolha. Grãos finos (pixel a pixel) podem gerar muito overhead de comunicação, enquanto grãos grossos (imagem inteira) podem limitar o paralelismo. A granulação ideal dependerá do tamanho da imagem, da complexidade das operações e da arquitetura do sistema. Paralelizar Programas 1. Atuação do Compilador e do Programador: a) Descreva as principais diferenças entre a paralelização realizada pelo compilador e a realizada pelo programador. b) Em que tipo de arquitetura (memória compartilhada ou distribuída) cada tipo de paralelização é mais comum? c) Dê um exemplo de diretiva de compilador que auxilia na paralelização. 2. Exemplo de Paralelização pelo Compilador: Analise o seguinte laço e determine se ele pode ser paralelizado pelo compilador. Justifique sua resposta. Se for paralelizável, mostre como ficaria o código com a diretiva apropriada. Unset DO I = 1, N A(I) = B(I) + C(I-1) ENDDO 3. Comunicação, Tamanho do Grão e Grau de Paralelismo: Explique como a comunicação entre processadores afeta o tamanho ideal do grão e o grau de paralelismo em um programa paralelo. 4. Particionamento de Matrizes: Descreva como o particionamento em blocos pode ser usado para otimizar a multiplicação de matrizes em um ambiente paralelo. Por que essa abordagem é vantajosa em relação à multiplicação linha-coluna tradicional? 5. Modelos de Particionamento: a) Quais são os três paradigmas básicos de interação entre processos paralelos? b) Descreva as principais características de cada paradigma e dê um exemplo de aplicação onde cada um seria mais adequado. 6. "Embarrassingly Parallel": O que significa um sistema ser "embarrassingly parallel"? Dê um exemplo de problema que se encaixa nessa categoria. 7. Hadoop MapReduce: a) Explique a ideia central por trás do paradigma MapReduce. b) Descreva as duas fases principais do MapReduce e como elas contribuem para o paralelismo. c) Qual a estrutura básica de dados utilizada no MapReduce? 8. Transactional Memory: a) Explique o conceito de Transactional Memory. b) Quais são as vantagens e desvantagens dessa abordagem? c) Diferencie as implementações de Transactional Memory em software (STM) e em hardware (HTM). 9. Estratégias de Programação Paralela: a) Diferencie paralelismo por dados e paralelismo por tarefas. b) Dê exemplos de situações em que cada estratégia seria mais adequada. 10. Sistemas com Dominação de E/S: Explique por que sistemas com dominação de E/S são difíceis de paralelizar.  RESPOSTAS Vamos às respostas das perguntas sobre Paralelização de Aplicações: 1. Atuação do Compilador e do Programador: a) Compilador: Atua em nível de instrução (ILP), identificando trechos de código independentes e gerando instruções paralelas. É mais automático, mas limitado pela complexidade do código. Programador: Atua em nível de tarefas ou blocos de código maiores, decompondo o problema em partes paralelas. Requer mais esforço do programador, mas permite maior flexibilidade e controle sobre o paralelismo. b) Compilador: Mais comum em arquiteturas de memória compartilhada, onde a comunicação entre threads é mais rápida. Programador: Mais comum em arquiteturas de memória distribuída, onde a comunicação é mais custosa e precisa ser explicitamente gerenciada. c) Exemplo de diretiva: #pragma omp parallel for (OpenMP), que indica ao compilador que um laço pode ser paralelizado. 2. Exemplo de Paralelização pelo Compilador: O laço não pode ser paralelizado diretamente devido à dependência de fluxo: A(I) depende de C(I-1). Para paralelizar, seria necessário reescrever o código ou usar técnicas como redução. 3. Comunicação, Tamanho do Grão e Grau de Paralelismo: A comunicação introduz overhead. Grãos muito pequenos com muita comunicação entre eles podem ter desempenho pior do que a execução sequencial. Grãos maiores reduzem a comunicação, mas podem limitar o paralelismo. O grau ideal de paralelismo depende do equilíbrio entre a quantidade de trabalho paralelo disponível e o overhead de comunicação. 4. Particionamento de Matrizes: O particionamento em blocos divide as matrizes em submatrizes menores, que são multiplicadas independentemente. Isso reduz o acesso à memória principal e melhora o uso do cache, resultando em melhor desempenho em ambientes paralelos. A multiplicação linha-coluna tradicional pode gerar muitos acessos não sequenciais à memória, prejudicando o desempenho do cache. 5. Modelos de Particionamento: a) Os três paradigmas são: Bag of Tasks, Heartbeat e Pipeline. b) * Bag of Tasks: Tarefas independentes são distribuídas por um coordenador para trabalhadores. Adequado para processamento em lote e tarefas independentes. Ex: renderização de frames de um filme. Heartbeat: Processos trabalham em ciclos de expansão, contração e processamento, trocando dados a cada iteração. Adequado para problemas iterativos com dependências entre iterações. Ex: simulação de fluidos. Pipeline: Dados fluem por uma sequência de estágios de processamento, como uma linha de produção. Adequado para processamento de fluxos de dados. Ex: processamento de vídeo em tempo real. 6. "Embarrassingly Parallel": Um sistema é "embarrassingly parallel" quando o problema pode ser facilmente decomposto em tarefas completamente independentes, sem necessidade de comunicação ou sincronização entre elas. Ex: renderização de imagens independentes em um filme. 7. Hadoop MapReduce: a) MapReduce é um paradigma para processamento paralelo de grandes conjuntos de dados distribuídos. b) * Map: Mapeia os dados de entrada em pares chave-valor intermediários. Reduce: Agrega os valores intermediários com a mesma chave, produzindo o resultado final. A paralelização ocorre principalmente na fase Map, que processa os dados de entrada de forma independente. c) A estrutura básica de dados é o par chave-valor. 8. Transactional Memory: a) Permite que blocos de código sejam executados como transações atômicas, como em bancos de dados. As mudanças são aplicadas apenas se a transação for bem-sucedida, evitando problemas de concorrência. b) Vantagens: Simplifica a programação paralela, reduzindo a necessidade de locks explícitos. Desvantagens: Overhead na criação e gerenciamento das transações, e pode ser ineficiente se houver muitos conflitos entre transações. c) STM: Implementada em software, tipicamente usando bibliotecas. HTM: Implementada em hardware, com suporte direto do processador, geralmente mais eficiente que STM. 9. Estratégias de Programação Paralela: a) Dados: Mesmo código em diferentes processadores, atuando sobre diferentes partes dos dados. Tarefas: Diferentes códigos em diferentes processadores, executando tarefas distintas. b) Dados: Ideal para processamento de grandes volumes de dados, como em aplicações científicas. Tarefas: Ideal para problemas com diferentes etapas ou subproblemas, como em pipelines de processamento. 10. Sistemas com Dominação de E/S: São difíceis de paralelizar porque o gargalo está na E/S, não no processamento. Adicionar mais processadores não acelera a E/S, e o tempo gasto esperando pelos dados limita o ganho de desempenho com o paralelismo. Espero que estas respostas ajudem na sua preparação para a prova! Continue revisando e praticando para dominar os conceitos. Avaliação de Desempenho - Análise 1. Definição de Desempenho:  Por que a definição de "desempenho" é subjetiva e depende do objetivo da análise? Dê exemplos de métricas de desempenho, além do tempo de execução, que podem ser relevantes em diferentes contextos. 2. Desempenho e Paralelismo: Liste e explique os fatores que podem degradar o desempenho de um sistema paralelo. Como o overhead de comunicação e sincronização afeta o speedup? Qual a importância de identificar trechos não paralelizáveis em um programa? 3. Escalabilidade: Defina escalabilidade no contexto de sistemas paralelos. Quais fatores afetam a escalabilidade de um sistema? Explique o conceito de slowdown e como ele se relaciona com a escalabilidade. 4. Speedup: Defina speedup e explique sua importância na avaliação de sistemas paralelos. Quais são os diferentes tipos de speedup e como eles são calculados? Compare e contraste a Lei de Amdahl e a Lei de Gustafson. Quais as limitações de cada uma? Por que o speedup medido é considerado mais útil que o speedup teórico? Explique os diferentes tipos de speedup medido e os desafios na escolha do programa sequencial de referência. 5. Lei de Amdahl e Gustafson - Aplicação: Considere um programa em que 90% do tempo de execução pode ser paralelizado. Calcule o speedup máximo possível de acordo com a Lei de Amdahl para 4, 8 e 16 processadores. Calcule o speedup para os mesmos números de processadores usando a Lei de Gustafson. Explique a diferença nos resultados e discuta as implicações para a escalabilidade do programa. 6. Benchmarks e Predição de Desempenho: O que são benchmarks e qual o seu papel na avaliação de desempenho? Quais são as diferentes abordagens para a realização de benchmarks? Quando a predição de desempenho é necessária e quais técnicas podem ser utilizadas? Essas perguntas abordam os pontos-chave sobre avaliação de desempenho, incluindo conceitos teóricos e práticos. Respondê-las e estudar os exemplos do material ajudarão na sua compreensão do tema. RESPOSTAS Vamos às respostas das perguntas sobre Métodos para Avaliação de Desempenho: 1. Definição de Desempenho: A definição de desempenho é subjetiva pois depende do que o usuário ou administrador considera importante. Um usuário pode se preocupar com o tempo de resposta de uma aplicação, enquanto um administrador pode se preocupar com a utilização da CPU ou a vazão do sistema.  Outras métricas: Vazão (throughput), latência, uso de memória, consumo de energia, custo por operação. 2. Desempenho e Paralelismo: Fatores de degradação: Overhead de comunicação e sincronização, trechos não paralelizáveis, contenção por recursos, ociosidade de processadores, balanceamento de carga inadequado. O overhead reduz o speedup pois adiciona tempo à execução paralela, diminuindo a eficiência do paralelismo. Trechos não paralelizáveis limitam o speedup máximo alcançável, conforme a Lei de Amdahl. Identificá-los é crucial para focar os esforços de otimização nas partes do código que realmente se beneficiarão do paralelismo. 3. Escalabilidade: Escalabilidade é a capacidade de um sistema manter ou aumentar o desempenho à medida que mais recursos (processadores, memória) são adicionados. Fatores que afetam a escalabilidade: Algoritmo, arquitetura do sistema, overhead de comunicação, características do problema. Slowdown ocorre quando o desempenho diminui com o aumento do número de processadores. Indica que o overhead de comunicação e outros fatores estão superando os ganhos do paralelismo. É um sintoma de falta de escalabilidade. 4. Speedup: Speedup mede o ganho de desempenho obtido com a paralelização. É a razão entre o tempo de execução sequencial e o tempo de execução paralela. Tipos de speedup: Teórico (Amdahl, Gustafson), medido (com base no melhor programa sequencial ou no programa paralelo monoprocessado).  Amdahl: Considera um tamanho fixo do problema e estima o speedup limitado pela fração sequencial do código. Gustafson: Considera um tempo fixo de execução e estima o speedup considerando que o tamanho do problema pode aumentar com o número de processadores. Amdahl é pessimista, Gustafson é otimista. Ambas são teóricas e não levam em conta todos os overheads da execução paralela. Speedup medido reflete o desempenho real do sistema, incluindo todos os overheads. Speedup medido: Comparação com o melhor programa sequencial (mais realista) ou com o programa paralelo executado em um único processador (menos realista, pois o programa paralelo geralmente tem overhead mesmo em um processador). O desafio é definir o "melhor" programa sequencial, que nem sempre é trivial. 5. Lei de Amdahl e Gustafson - Aplicação: Amdahl: ○ 4 processadores: 1 / (0.1 + 0.9/4) = 3.6 ○ 8 processadores: 1 / (0.1 + 0.9/8) = 6.4 ○ 16 processadores: 1 / (0.1 + 0.9/16) = 10.29 Gustafson: ○ 4 processadores: 4 - 0.1 * (4-1) = 3.7 ○ 8 processadores: 8 - 0.1 * (8-1) = 7.3 ○ 16 processadores: 16 - 0.1 * (16-1) = 14.5 A diferença nos resultados ocorre porque Gustafson assume que o tamanho do problema cresce com o número de processadores, mantendo a parte serial constante. Amdahl, por outro lado, assume um tamanho fixo do problema, o que limita o speedup. Isso mostra que, para problemas escaláveis (onde o tamanho pode crescer com o número de processadores), o speedup pode ser muito maior do que o previsto pela Lei de Amdahl. 6. Benchmarks e Predição de Desempenho: Benchmarks são programas ou conjuntos de programas usados para medir o desempenho de um sistema. Permitem comparar diferentes sistemas ou configurações, e avaliar o impacto de otimizações. Abordagens: Microbenchmarks (medem operações específicas), application benchmarks (usam aplicações reais), synthetic benchmarks (combinam características de várias aplicações). Predição é necessária quando a medição direta é inviável (sistema ainda não existe) ou muito custosa. Técnicas: Modelagem analítica (fórmulas e equações), simulação (modelos computacionais). 1. Problemas com Medição: Explique a importância de definir "por que medir" antes de "o que medir" e "como medir". Dê exemplos de diferentes objetivos de medição e como eles influenciam as métricas escolhidas. 2. Técnicas de Medição:  Compare e contraste as técnicas de monitoração e modificação de código para medição de desempenho. Quais são as vantagens e desvantagens de cada técnica? Descreva como a monitoração por hardware e software funciona. Explique o que é profiling e como ele pode ser usado para analisar o desempenho de um programa. 3. Ferramentas de Profiling: Quais são os problemas comuns associados às ferramentas de profiling? Como o gprof funciona? Explique os passos para utilizá-lo. Descreva as informações fornecidas pelo gprof, como flat profile e call graph. 4. Modificação de Código Fonte: Explique como a modificação de código fonte pode ser usada para medir o desempenho. Dê um exemplo de código C/C++ que utiliza a função clock_gettime() para medir o tempo de execução de uma função. 5. Precisão das Medições: Por que as medições de desempenho podem ser imprecisas, mesmo com funções de alta resolução como clock_gettime()? Quais fatores contribuem para a imprecisão das medições? 6. Problemas com Benchmarks: Discuta os desafios na definição da carga de trabalho e dos padrões de medida em benchmarks. Por que é importante normalizar os resultados de benchmarks pelo volume de uso de cada programa? 7. Benchmarks por Organizações vs. Locais:  Compare e contraste benchmarks desenvolvidos por organizações e benchmarks locais. Dê exemplos de benchmarks de cada tipo. Quais as vantagens e desvantagens de cada abordagem? 8. Prevendo o Desempenho: Quando é apropriado usar modelos analíticos ou de simulação para prever o desempenho? Quais são as diferenças entre essas abordagens? Dê exemplos de ferramentas ou técnicas usadas para modelagem analítica e simulação de desempenho. 9. Critérios de Escolha de Métodos: Quais critérios devem ser considerados ao escolher entre benchmarking, modelagem analítica e simulação para avaliação de desempenho? Em que estágios do desenvolvimento de um sistema cada método é mais adequado? 10. Ferramentas de Análise de Desempenho: Descreva as funcionalidades e os recursos das ferramentas Intel vTune, Advisor e TAU. Quais as principais diferenças entre elas? RESPOSTAS 1. Problemas com a Medição: Definir "por que medir" estabelece o objetivo da análise, guiando a escolha das métricas relevantes e das técnicas de medição apropriadas. Sem um objetivo claro, as medições podem ser inúteis ou levar a conclusões equivocadas.  Exemplos: ○ Objetivo: Comparar o desempenho de dois algoritmos de ordenação. Métricas: Tempo de execução, número de comparações, número de trocas. ○ Objetivo: Avaliar o impacto de uma otimização em um programa paralelo. Métricas: Speedup, eficiência, overhead de comunicação. 2. Técnicas de Medição: Monitoração: Observa o sistema em execução sem interferir diretamente no código. Modificação de Código: Insere código de medição no programa. Monitoração: Vantagens: Sem impacto no desempenho do programa (idealmente). Desvantagens: Pode ser complexa de configurar, requer acesso a ferramentas específicas. Modificação: Vantagens: Mais fácil de implementar, permite medir trechos específicos do código. Desvantagens: Pode afetar o desempenho do programa, requer acesso ao código fonte. Monitoração por Hardware: Utiliza dispositivos de hardware, como analisadores lógicos, para coletar dados sobre o sistema. Mais precisa, mas mais complexa e cara. Monitoração por Software: Utiliza recursos do sistema operacional, como interrupções, para coletar dados. Menos precisa, mas mais simples de implementar. Profiling: Coleta informações sobre o tempo de execução de diferentes partes de um programa, identificando gargalos de desempenho. 3. Ferramentas de Profiling: Problemas comuns: Overhead na execução do programa, imprecisão na amostragem, dificuldade em lidar com paralelismo. :  ○ Compilar o programa com a opção -pg. ○ Executar o programa normalmente. Isso gera um arquivo gmon.out. ○ Executar o comando gprof nome_do_programa > arquivo_de_saida. - Informações: ○ Flat profile: Tempo gasto em cada função individualmente. ○ Call graph: Mostra a hierarquia de chamadas de funções e o tempo gasto em cada uma. 4. Modificação de Código Fonte: Inserindo chamadas a funções de medição, como clock_gettime(), no código fonte. Exemplo: Unset #include #include double etimes() { struct timespec tp; clock_gettime(CLOCK_REALTIME, &tp); return tp.tv_sec + tp.tv_nsec / 1000000000.0; } int main() { double inicio = etimes(); // Código a ser medido double fim = etimes(); printf("Tempo de execução: %f segundos\n", fim - inicio); return 0; } 5. Precisão das Medições: Imprecisões podem ocorrer devido ao overhead das chamadas de medição, à resolução limitada do relógio, à variabilidade do sistema e a interferências externas. Fatores: Resolução do relógio, overhead das chamadas de função, variações no tempo de execução do código, interferências externas. 6. Problemas com Benchmarks: Carga de Trabalho: Representatividade da carga real, variabilidade da carga. Padrões de Medida: Métricas relevantes, condições de teste, configuração do sistema. A normalização é importante para comparar sistemas com diferentes capacidades de processamento, garantindo que a comparação seja justa e reflita o desempenho relativo em relação à carga de trabalho. 7. Benchmarks por Organizações vs. Locais: Organizações: Padronizados, amplamente utilizados, permitem comparação entre diferentes sistemas. Locais: Específicos para uma aplicação ou sistema, mais relevantes para o contexto local. Organizações: SPEC, Linpack, NAS. Locais: Programas representativos da carga de trabalho do sistema. Organizações: Vantagens: Comparação justa entre sistemas. Desvantagens: Podem não representar a carga de trabalho real. Locais: Vantagens: Mais relevantes para o contexto local. Desvantagens: Difícil comparar com outros sistemas. 8. Prevendo o Desempenho: Apropriado quando a medição é impossível (sistema em projeto) ou muito custosa (testes extensos).  Analíticos: Usam fórmulas e equações para estimar o desempenho. Mais simples, mas menos precisos. Simulação: Criam um modelo computacional do sistema e simulam sua execução. Mais complexos, mas potencialmente mais precisos. Analíticos: Teoria das filas, Lei de Amdahl. Simulação: Simuladores de redes, CloudSim. 9. Critérios de Escolha de Métodos: Custo, tempo disponível, precisão necessária, disponibilidade do sistema, estágio do desenvolvimento. Analíticos: Início do projeto. Simulação: Projeto, prototipagem. Benchmarking: Sistema em funcionamento. 10. Ferramentas de Análise de Desempenho: vTune: Análise detalhada do desempenho da aplicação, incluindo hotspots, uso de CPU e GPU, threading. Advisor: Identifica oportunidades de otimização, como vetorização e paralelização. Roofline analysis. TAU: Profiling e tracing para aplicações paralelas, análise do desempenho em diferentes níveis de granularidade Avaliação de Desempenho - Otimização 1. Otimização de Código: a) Qual o objetivo da otimização de código? b) Quem pode realizar a otimização de código? 2. Otimização pelo Compilador: a) O que é código "visível" para o compilador, no contexto de otimização? b) Cite exemplos de técnicas de otimização realizadas por compiladores. 3. Otimização pelo Programador: a) Que tipo de informação o programador precisa para otimizar o código efetivamente? b) Além das técnicas de compiladores, que outras técnicas o programador pode utilizar para otimizar o código? 4. Gargalos de Desempenho: a) Defina "gargalo de desempenho". b) Quais são os três tipos de gargalos de software? Dê exemplos de cada. 5. Gargalos de Linguagem: a) Que características de uma linguagem de programação devem ser consideradas para favorecer o desempenho? b) Por que o uso de ponteiros e estruturas dinâmicas pode ser prejudicial ao desempenho? c) Em que contexto Fortran 77 ou HPF podem ser vantajosos em termos de desempenho? 6. Gargalos em Funções: a) Explique por que o excesso de modularização e o uso de funções curtas podem prejudicar o desempenho. b) O que é function inlining e como ele pode melhorar o desempenho? Dê um exemplo. 7. Gargalos em Blocos de Repetição: a) Cite as principais técnicas para otimizar laços (blocos de repetição). b) Explique o que é desdobramento de código (loop unrolling) e como ele pode ser usado para melhorar o paralelismo. Dê um exemplo. c) Como lidar com o desdobramento de laços quando o número de iterações não é múltiplo do fator de desdobramento? d) Explique e exemplifique as técnicas de remoção de testes desnecessários, inversão de aninhamentos e fissão/fusão de laços. 8. Multiplicação de Matrizes Otimizada: Analise o código otimizado para multiplicação de matrizes apresentado no material. Explique como a mudança na ordem dos laços e o uso da variável SCALE melhoram o desempenho. 9. Otimizações pelo Compilador (Avançadas): a) Descreva as seguintes otimizações de compilador: propagação de código, renomeação de variáveis, desdobramento de constantes e redução de força. b) Dê exemplos de cada uma dessas otimizações. 10. Considerações Finais: a) Por que a otimização de desempenho depende fortemente do trabalho do programador? b) Qual o impacto das escolhas de estruturas de dados e algoritmos no desempenho de um programa? RESPOSTAS 1. Otimização de Código: a) O objetivo é melhorar o desempenho do programa, reduzindo o tempo de execução, o consumo de memória ou outros recursos. b) O programador e o compilador. 2. Otimização pelo Compilador: a) Código "visível" é o código que o compilador pode analisar e modificar para melhorar o desempenho, sem alterar a semântica do programa. Isso exclui, por exemplo, chamadas a funções externas cujo código o compilador não possui. b) Técnicas: Loop unrolling, dead code elimination, constant folding, inlining, common subexpression elimination. 3. Otimização pelo Programador: a) Informações sobre o tempo de execução de diferentes partes do código (profiling), gargalos de desempenho, e características da arquitetura do sistema. b) Escolha de algoritmos e estruturas de dados eficientes, paralelização, otimização de acesso à memória. 4. Gargalos de Desempenho: a) Um gargalo é uma parte do código que limita o desempenho geral do programa. Melhorar o desempenho do gargalo melhora o desempenho geral. b) Linguagem, funções e blocos de repetição. Exemplos: * Linguagem: Uso excessivo de alocação dinâmica em C++. * Funções: Chamadas frequentes a funções pequenas. * Laços: Muitos cálculos redundantes dentro de um laço. 5. Gargalos de Linguagem: a) Simplicidade, tipagem estática, e suporte a vetorização. b) Alocação e desalocação frequentes de memória podem ser custosas. Ponteiros podem dificultar a análise de dependências pelo compilador. c) Quando a performance é crítica e o código se beneficia da vetorização e paralelização automática, que são mais eficazes em linguagens como Fortran. 6. Gargalos em Funções: a) O overhead das chamadas de função pode ser significativo, especialmente para funções pequenas. Muitas funções pequenas também dificultam a otimização do compilador. b) Inlining substitui a chamada de função pelo código da própria função, eliminando o overhead da chamada. Exemplo: Unset // Sem inlining inline int soma(int a, int b) {  return a + b; } int main() { int x = soma(1, 2); } // Com inlining (o compilador pode fazer isso) int main() { int x = 1 + 2; } 7. Gargalos em Blocos de Repetição: a) Desdobramento, remoção de testes, inversão de aninhamentos, fissão/fusão. b) Loop unrolling replica o corpo do laço múltiplas vezes, reduzindo o número de iterações e o overhead do controle do laço. Exemplo: Unset // Sem unrolling for (int i = 0; i < 4; ++i) { a[i] = b[i] * c; } // Com unrolling (fator 2) for (int i = 0; i < 4; i += 2) { a[i] = b[i] * c; a[i+1] = b[i+1] * c; } c) Adicionar um laço separado para as iterações restantes, que não são múltiplas do fator de desdobramento. d) * Remoção de Testes: Evitar testes redundantes dentro do laço, movendo-os para fora ou eliminando-os completamente quando possível. Inversão de Aninhamentos: Mudar a ordem dos laços aninhados para melhorar o acesso à memória, levando em conta a organização da memória (linha-maior ou coluna-maior). Fissão/Fusão: Dividir um laço em laços menores (fissão) ou combinar laços consecutivos (fusão) para melhorar o uso do cache ou reduzir o overhead do controle do laço. 8. Multiplicação de Matrizes Otimizada: A mudança na ordem dos laços garante que os acessos à matriz B sejam sequenciais na memória, melhorando o desempenho do cache. A variável SCALE evita o recálculo repetido de A[j][k] dentro do laço mais interno. 9. Otimizações pelo Compilador (Avançadas): a) * Propagação de Código: Substitui o uso de uma variável pelo seu valor conhecido. Renomeação de Variáveis: Renomeia variáveis para evitar dependências artificiais e permitir maior paralelismo. Desdobramento de Constantes: Calcula expressões constantes em tempo de compilação. Redução de Força: Substitui operações caras por operações mais baratas equivalentes. =-=-=-=-=-=-==-=-=-=-=-------=----------------------------------------------------------------=-=-=-=-=-=-= Bloco 1: Processadores Questão 1: Hardware para Computação de Alto Desempenho (Comparação e Justificativa) Compare as arquiteturas de um cluster de computadores e uma máquina com múltiplos GPUs para a execução de uma aplicação de aprendizado de máquina. Considere os seguintes aspectos: Escalabilidade: Qual arquitetura oferece melhor escalabilidade para o treinamento de modelos maiores? Justifique.  Custo: Qual arquitetura tende a ser mais custosa, considerando hardware e software? Justifique. Complexidade de Programação: Qual arquitetura apresenta maior complexidade de programação para paralelizar a aplicação? Justifique. Consumo de Energia: Qual arquitetura tende a ter maior consumo de energia? Justifique. Questão 2: Bibliotecas para Programação Paralela em Memória Compartilhada (Implementação de Trecho de Código) Implemente um trecho de código em C/C++ utilizando OpenMP para calcular a soma dos elementos de um vetor de inteiros de tamanho N. Paralelize o laço de iteração sobre o vetor utilizando a diretiva #pragma omp parallel for. Garanta a exclusão mútua no acesso à variável que acumula a soma. Questão 3: Condições de Paralelismo (Identificação e Classificação) Analise o seguinte trecho de código e identifique as partes que podem ser paralelizadas. Classifique o tipo de paralelismo presente (dados, tarefas, etc.) e justifique sua resposta. Unset for (int i = 0; i < N; ++i) { resultado[i] = funcao_a(i); outro_resultado[i] = funcao_b(i); } resultado_final = funcao_c(resultado, outro_resultado); Questão 4: Métricas e Avaliação de Desempenfpho (Análise e Interpretação) Você executou uma aplicação paralela em um cluster com diferentes números de nós. Os resultados de speedup obtidos foram os seguintes: 2 nós: Speedup = 1.8 4 nós: Speedup = 3.2 8 nós: Speedup = 5.5 Analise os resultados e responda: A aplicação apresenta um speedup linear? Justifique. Quais fatores podem estar limitando o speedup? Que métricas adicionais, além do speedup, seriam relevantes para avaliar o desempenho da aplicação? Questão 5: Otimização de Desempenho (Proposta de Melhorias) Considere o seguinte código OpenMP: Unset #pragma omp parallel for for (int i = 0; i < N; ++i) { // Operações complexas com vetor[i] } Sugira duas otimizações que poderiam melhorar o desempenho desse código. Justifique suas escolhas e explique o impacto esperado. Considere aspectos como false sharing, balanceamento de carga e overhead. Questão 6: Modelos de Paralelismo (Comparação) Compare os modelos de paralelismo Fork-Join e Master-Worker. Destaque as principais diferenças entre eles e cite exemplos de situações em que cada modelo seria mais adequado. Questão 7: Bibliotecas para Programação Paralela em Memória Distribuída (MPI) Escreva um programa MPI que calcula a soma dos elementos de um vetor distribuído entre os processos. Cada processo deve ser responsável por calcular a soma parcial dos elementos que possui e, em seguida, um processo designado (por exemplo, o processo 0) deve coletar as somas parciais e calcular a soma total. Questão 8: Bibliotecas para Programação Paralela em GPUs (CUDA) Explique o conceito de kernel em CUDA. Descreva como os dados são transferidos entre a CPU e a GPU e como os threads são organizados em blocks e grids. Questão 1: Hardware para Computação de Alto Desempenho Escalabilidade: Clusters oferecem maior escalabilidade. Adicionar mais nós a um cluster é mais simples e barato do que aumentar o número de GPUs em uma única máquina. Em aprendizado de máquina, modelos  maiores frequentemente exigem mais memória e poder de processamento, e clusters podem ser expandidos para atender a essas demandas. Custo: Inicialmente, um cluster pode ser mais caro devido à necessidade de interconexão de rede e múltiplas CPUs, placas-mãe, etc. No entanto, a longo prazo, a escalabilidade do cluster pode torná-lo mais econômico para modelos muito grandes, comparado a máquinas com múltiplas GPUs de última geração, que têm custo inicial mais alto e upgrades limitados. Complexidade de Programação: Clusters, utilizando MPI, geralmente apresentam maior complexidade de programação para paralelizar aplicações. Gerenciar a comunicação e sincronização entre nós exige mais código e cuidado do que programar para GPUs com CUDA ou OpenCL, que oferecem um modelo mais simplificado para programação paralela. Consumo de Energia: Clusters tendem a ter maior consumo de energia, pois envolvem múltiplas máquinas, cada uma com sua própria CPU, memória e fontes de alimentação. GPUs, apesar de consumirem bastante energia, são mais concentradas em uma única máquina, o que pode resultar em menor consumo total em alguns casos, especialmente ao considerar a escalabilidade. Questão 2: Bibliotecas para Programação Paralela em Memória Compartilhada Unset #include #include #include int main() { std::vector vetor(1000); // Inicializa o vetor (omitido para brevidade) int soma = 0;  #pragma omp parallel for reduction(+:soma) for (int i = 0; i < vetor.size(); ++i) { soma += vetor[i]; } std::cout