Anotações sobre Abstrações e Tecnologia de Computadores - Patterson e Hennessy

CHAPTER 1 COMPUTER ABSTRACTIONS AND TECHNOLOGY PATTERSSONHENNESSY Luiz Paulo de Assis Barbosa 1 12 Abaixo de seu programa Applications software System software Hardware 12 Abaixo de seu programa Dois dos principais software de sistema são sistema operacional SO e compilador SO promove a interface entre os programas de usuário e o hardware e provê uma variedade de serviços e funções de supervisão Entre as funções mais importantes temos Tratar das operações de entrada e saída básicas Alocar armazenamento e memória Prover o compartilhamento da máquina entre múltiplas aplicações simultâneas de forma protegida ou seja sem que uma interfira com a outra de forma indesejada 4 12 Abaixo de seu programa Compiladores realizam uma função vital a tradução de um programa em linguagem de alto nível em instruções que o hardware pode executar 5 12 Abaixo de seu programa Para que haja comunicação entre componentes de hardware é necessário a troca de sinais elétricos entre eles Os sinais mais fáceis de serem compreendidos pelos computadores são ligado e desligado desta forma o alfabeto da máquina possui apenas dois símbolos 0 e 1 Os computadores são escravos que obedecem aos nossos comandos Os comandos são denominados instruções 6 12 Abaixo de seu programa Instruções são apenas um conjunto de bits que o computador entende e obedece podem ser visualizadas como números binários Por exemplo Diz ao computador para adicionar dois números 1000110010100000 7 12 Abaixo de seu programa Os primeiros programadores se comunicavam com os computadores por meio dos números porém logo foi inventada uma notação mais próxima da forma humana de pensar No princípio a tradução dessa notação para binário era feita à mão no entanto podese usar o computador para auxiliar em sua própria programação e desta forma foram escritos programas para automatizar a terefa de tradução add AB 8 12 Abaixo de seu programa O primeiro desses programas foi denominado Assembler montador A linguagem simbólica utilizada foi batizada de linguagem Assembly Enquanto que a linguagem binária é denominada linguagem de máquina add AB 1000110010100000 9 12 Abaixo de seu programa Programa em linguagem de alto nível C para Assembly MIPS swapint v int k int temp temp vk vk vk1 vk1 temp swap multi 2 5 4 add 2 42 lw 15 02 lw 16 42 lw 16 02 lw 15 42 jr 31 10 12 Abaixo de seu programa Programa em Assembly MIPS para linguagem de máquina binária 00000000101000010000000000011000 00000000000110000001100000100001 10001100011000100000000000000000 10001100111100100000000000000100 10101100111100100000000000000000 10101100110001000000000000000100 00000011111000000000000000001000 swap multi 2 5 4 add 2 42 lw 15 02 lw 16 42 lw 16 02 lw 15 42 jr 31 11 14 Performance Quando dizemos que um computador tem melhor performance que outro o que isso significa Fazendo uma analogia com a aviação civil se definirmos performance em termos de velocidade distância ou capacidade qual o melhor avião Avião Capacidade passageiros Distância de cruzeiro milhas Velocidade de cruzeiro mph Vazão de passageiros passageiros x mph Boeing 777 375 4630 610 228750 Boeing 747 470 4150 610 286700 BACSud Concorde 132 4000 1350 178200 Douglas DC850 146 8720 544 79424 12 14 Performance Se queremos levar um passageiro de um ponto a outro no menor tempo possível o melhor é o que tem a maior velocidade de cruzeiro em verde Se o objetivo é levar 450 passageiros de um ponto a outro o outro o que tem maior vazão é o melhor em amarelo Avião Capacidade passageiros Distância de cruzeiro milhas Velocidade de cruzeiro mph Vazão de passageiros passageiros x mph Boeing 777 375 4630 610 228750 Boeing 747 470 4150 610 286700 BACSud Concorde 132 4000 1350 178200 Douglas DC850 146 8720 544 79424 13 14 Performance Um usuário de computador pessoal dirá que o melhor computador é aquele que termina uma tarefa primeiro em outras palavras é aquele que apresenta o menor tempo de resposta ou tempo de execução Já um administrador de datacenter dirá que o melhor computador é aquele que completa mais tarefas durante um período de tempo ou seja está interessado em aumentar a vazão throughput ou largura de banda bandwidth 14 14 Performance Vazão e tempo de resposta As seguintes mudanças em um computador aumentam a vazão reduzem o tempo de resposta ou afeta ambos Trocar o processador por uma versão mais rápida Acrescentar processadores a um sistema que suporta múltiplos processadores para tarefas distintas 15 14 Performance Para o primeiro caso quase sempre diminuir o tempo de resposta melhora a vazão Para o segundo caso nenhuma tarefa individual será realizada em menor tempo portanto apenas a vazão aumenta No entanto se a demanda por processamento no segundo caso era quase igual a vazão do sistema original poderiam existir filas de tarefas Neste caso o tempo de resposta também poderia melhorar devido a redução do tempo de espera na fila 16 14 Performance Focando no parâmetro tempo de resposta temos Para maximizar a performance temos que reduzir o tempo de resposta Logo podemos relacionar performance e tempo de execução em um computador X X X tempo de execução Performance 1 17 14 Performance O que significa que para dois computadores X e Y se a performance de X é maior que a de Y temos Y X Performance Performance Y X tempo de execução de execução tempo 1 1 X Y tempo de execução tempo de execução 18 14 Performance Para relacionar a performance de dois computadores quantitativamente normalmente usamos a expressão X é n vezes mais rápido que Y onde n é dado por n de execução tempo de execução tempo e Performanc e Performanc X Y Y X 19 14 Performance Performance relativa Ex Se o computador A executa um programa em 10s e o computador B executa o mesmo programa e 15s A é quantas vezes mais rápido que B Podemos dizer também que B é 15 mais lento que A ou seja n de execução tempo de execução tempo e Performanc e Performanc A B B A 51 10 15 51 A B Performance Performance 20 14 Performance Um computador C é 4 vezes mais rápido que um computador B o qual executa uma dada aplicação em 28s Quanto tempo o computador C leva para executar a mesma aplicação 4 28 C C B tempo de execução de execução tempo de execução tempo s tempo de execução C 7 4 28 n de execução tempo de execução tempo e Performanc e Performanc X Y Y X 21 14 Performance Medindo Performance Tempo de resposta ou tempo transcorrido elapsed time Referese ao tempo total para executar uma tarefa incluindo acesso a disco acesso à memória operações de entrada e saída overhead do SO enfim tudo Tempo de execução de CPU ou tempo de CPU É o tempo que a CPU gasta computando uma tarefa específica e não inclui os tempos de espera por entrada e saída ou gastos executando outros programas 22 14 Performance O tempo de CPU pode ser dividido em Tempo de de CPU de usuário Tempo gasto pela CPU no programa do usuário Tempo de CPU de sistema Tempo gasto pela CPU realizando serviços do SO em favor do programa do usuário Difícil de destinguir de maneira precisa entre os dois Será usado o termo performance de sistema para designar a performance baseada no tempo trascorrido e o termo performance de CPU para o caso baseado no tempo de CPU 23 14 Performance Entendendo a performance de programa Quase todos os computadores são construídos usando um relógio clock que determina quando ocorrem os eventos no hardware Estes intervalos de tempo discretos são chamados ciclos de clock O período é a quantidade de tempo gasta para realizar um ciclo de clock completo ex 250ps A frequência ou taxa de relógio clock rate ex 4GHz corresponde ao inverso do período 24 14 Performance Performance de CPU e seus fatores Ou alternativamente devido à relação entre período e frequência período programa do de CPU Ciclos um programa de tempo de CPU frequência o programa para de CPU Ciclos um programa para tempo de CPU 25 14 Performance Exemplo melhorando performance Um computador A possui um clock de 2GHz e executa um programa P em 10s O objetivo é construir um computador B que execute P em 6s Foi determinado que é possível aumentar substancialmente a frequência f porém ao custo de que o computador B necessitará de 12 vezes mais ciclos de clock que o computador A para executar P 26 14 Performance Solução Achar o número de ciclos que A usa para executar P A A A frequência Ciclos de CPU tempo de CPU A A A frequência tempo de CPU Ciclos de CPU ciclos s ciclos s Ciclos de CPU A 9 9 20 10 2 10 10 27 14 Performance Continuação da solução Determinar a frequência do clock que B precisa para executar P em 6s usando B B B de CPU tempo Ciclos de CPU frequência GHz s ciclos s ciclos de CPU tempo de CPU Ciclos de CPU tempo Ciclos de CPU frequência B A B B B 4 4 10 6 20 10 21 21 9 9 28 14 Performance Performance de instrução O tempo de execução de um programa depende do número de instruções que compõem o programa Desta forma o número de ciclos de CPU para um dado programa pode ser calculado por por instrução clock médio de ciclos de Número programa do Número de instruções Ciclos de CPU 29 14 Performance 30 Performance de instrução Continuação O número médio de ciclos de clock por instrução pode ser abreviado por CPI Clock cycles Per Instruction A métrica CPI provê uma maneira de comparar diferentes implementações de um mesmo conjunto de instruções já que o número de instruções executadas por um programa será o mesmo 14 Performance Exemplo usando a equação de performance Suponha que temos 2 implementações do mesmo ISA Instruction Set Architecture Um computador A possui um período de ciclo de clock de 250ps e uma CPI de 20 para um programa P E um outro computador B possui um período de ciclo de clock de 500ps e uma CPI de 12 para P Qual computador A ou B é o mais rápido para executar P E quão mais rápido ele é em relação ao outro 31 14 Performance Solução Façamos I corresponder ao número de instruções de P Agora podemos calcular os ciclos de CPU para A e B em função de I usando I CPI I Ciclos de CPU A A 2 I CPI I Ciclos de CPU B B 21 32 14 Performance Os tempos de CPU para A e B podem ser determinados usando De forma análoga Ou seja A é mais rápido que B A A A A A período Ciclos de CPU frequência Ciclos de CPU tempo de CPU I ps ps I tempo de CPU A 500 250 2 I ps ps I tempo de CPU B 600 500 21 33 14 Performance Utilizando a relação para performance relativa Logo A é 12 vezes mais rápido que B n de execução tempo de execução tempo e de CPU Performanc e de CPU Performanc A B B A 21 500 600 ps I ps I e de CPU Performanc e de CPU Performanc B A B A Performance de CPU Performance de CPU 21 34 14 Performance A equação clássica da performance de CPU Ela é particularmente útil pois separa os 3 fatores chaves que afetam a performance frequência CPI I período CPI I tempo de CPU 35 14 Performance Exemplo comparando segmentos de código Um projetista de compiladores está tentando decidir entre 2 sequências de código para um determinado computador Ele sabe que CPI para cada classe de instrução Classe A B C CPI 1 2 3 36 14 Performance Para uma linguagem de alto nível L as sequências de instruções em consideração levam a duas contagens de instruções distintas a saber Qual sequência de código executa mais instruções Qual a mais rápida Qual é a CPI para cada sequência Número de instruções para cada classe de instrução Classe A B C Seq 1 2 1 2 Seq 2 4 1 1 37 14 Performance Solução Qual sequência de código executa mais instruções A sequência 1 executa 212 5 instruções enquanto a sequência 2 executa 411 6 instruções Qual a mais rápida Para determinar isso precisamos descobrir os ciclos de CPU para cada sequência n i i i I CPI de CPU Ciclos 1 38 14 Performance Logo Portanto a sequência 2 é a mais rápida mesmo tendo um numero de instruções maior o que nos diz que a CPI2 CPI1 ciclos Ciclos de CPU 10 6 2 2 3 2 2 1 1 2 1 ciclos Ciclos de CPU 9 3 2 4 3 1 2 1 1 4 2 39 14 Performance Qual é a CPI para cada sequência Sabemos que Assim Analogamente CPI I Ciclos de CPU I Ciclos de CPU CPI 2 5 10 1 1 1 I Ciclos de CPU CPI 51 6 9 2 2 2 I Ciclos de CPU CPI 40 14 Performance 41 Uma dada aplicação A em Java roda em 15s num processador de um desktop Um novo compilador Java é lançado e requer apenas 60 do número de instruções do compilador antigo para A Infelizmente ele aumenta a CPI por um fator de 10 Quão rápido podemos esperar que a aplicação rode usando o novo compilador 14 Performance Alternativas Demonstre a partir da relação das variáveis do problema qual das alternativas é a correta 42 s 28 11 60 15 s 99 11 60 15 27 5 s 60 11 15 a b c 14 Performance Dados Sabemos Compilador antigo 1 Compilador Novo 2 43 s tCPU 15 1 1 2 60 I I 1 2 11 CPI CPI T CPI I f CPI I tCPU f CPI I 1 1 15 f CPI I tCPU 2 2 2 f CPI I tCPU 1 1 2 11 60 f CPI I tCPU 11 60 1 1 2 14 Performance 44 Isolando f e igualando as equações Resolvendo para 15 1 1 CPI I f 2 1 1 11 60 CPU t CPI I f 2 1 1 1 1 11 60 15 CPU t CPI I CPI I 1 1 1 1 2 11 60 15 CPI I CPI I tCPU s tCPU 99 11 60 15 2 tCPU 2 16 Uniprocessadores para Multiprocessadores 45 A relação entre frequência de operação e potência dissipada nos processadores forçou uma mudança dramática no projeto de microprocessadores A mudança de uniprocessadores single core para multiprocessadore multicore Em vez de diminuir o tempo de resposta de um único programa rodando em um único processador os microprocessadores passaram a oferecer mais de um processador core por pastilha Deslocando os benefícios de um novo processador do tempo de resposta para a vazão 16 Uniprocessadores para Multiprocessadores 46 Antes os programadores podiam confiar nas inovações de hardware arquitetura e compiladores que faziam dobrar a performance dos seus programas a cada 18 meses sem a necessidade de reescrever seus programas Atualmente para se obter uma melhora significativa no tempo de resposta é necessário reescrever os programas para tirar vantagens dos múltiplos processadores disponíveis 16 Uniprocessadores para Multiprocessadores 47 Escrever programas que exploram paralelismo explicitamente é programação voltada a performance o que dificulta a atividade de programação pois O programa tem que resolver o problema corretamente e tem que ser rápido A aplicação tem que ser dividida para que cada processador receba aproximadamente a mesma quantidade de trabalho ao mesmo tempo de forma que o overhead de agendamento e coordenação não anule os benefícios do paralelismo 16 Uniprocessadores para Multiprocessadores 48 Classificação de Flynn SISD Single Instruction Single Data SIMD Single Instruction Multiple Data MISD Multiple Instruction Single Data MIMD Multiple Instruction Multiple Data Single Data Multiple Data Single Instruction SISD SIMD Multiple Instruction MISD MIMD 16 Uniprocessadores para Multiprocessadores 49 Classificação de Flynn SISD Single Instruction Single Data Fluxo único de instruções sobre um único conjunto de dados Processadores single core SIMD Single Instruction Multiple Data Fluxo único de instruções em múltiplos conjuntos de dados GPUs processadores vetoriais 16 Uniprocessadores para Multiprocessadores 50 Classificação de Flynn MISD Multiple Instruction Single Data Fluxo múltiplo de instruções em um único conjunto de dados Pipeline MIMD Multiple Instruction Multiple Data Fluxo múltiplo de instruções sobre múltiplos conjuntos de dados Processadores muticore 16 Uniprocessadores para Multiprocessadores 51 Fazendo uma analogia com a escrita de um artigo de jornal no qual 8 repórteres estão trabalhando na mesma estória Para termos ganho em velocidade Todos têm que ter trabalho ao mesmo tempo Se um atrasar degrada a performance Não pode haver muita comunição entre eles para que o artigo seja escrito nem uma parte que dependa das outras para ser escrita por exemplo a conclusão 16 Uniprocessadores para Multiprocessadores 52 Desafios da programacão paralela Agendamento de tarefas Balanceamento de carga Redução da comunicação Redução do overhead de sincronização 18 FALÁCIAS E ARMADILHAS 53 Armadilha Esperar que a melhoria de um aspecto do computador aumente a performance geral por uma quantidade proporcional ao tamanho da melhoria Suponha que um programa roda em 100s num conputador com as operações de multiplicação sendo responsáveis por 80s desse tempo Quanto eu tenho que melhorar a velocidade da operação de multiplicação para que o programa rode 5 vezes mais rápido 18 FALÁCIAS E ARMADILHAS 54 Lei de Amdahl calcula o tempo de execução de um programa após uma melhoria Para o problema em particular não afetado exec afetado pela melhoria exec exec depois da melhoria t de melhoria Quantidade t t n 80 segundos 0 segundos n segundos segundos segundos 20 80 20 5 100 18 FALÁCIAS E ARMADILHAS 55 Conclusão Não existe como atingir uma performance geral 5 vezes melhor apenas melhorando a performance das operações de multiplicação se elas representarem apenas 80 da carga de trabalho Falácia Computadores em baixa utilização gastam menos potência Estudos mostram que mesmo operando em 10 da carga máxima ainda são gastos 666 da potência consumida em carga máxima 18 FALÁCIAS E ARMADILHAS 56 Armadilha Usar um subconjunto da equação de performance como métrica de performance Uma métrica alternativa ao tempo é o MIPS MIPS Million Instructions Per Second não confundir com o MIPS processador 6 10 exec t I MIPS 18 FALÁCIAS E ARMADILHAS 57 Problemas ao usar MIPS para comparar computadores Especifica a taxa de instruções mas não leva em conta as capacidades de cada instrução Computadores com ISAs diferentes não podem ser comparados usando MIPS a contagem de instruções seria diferente A métrica MIPS é dependente do programa e um computador pode apresentar vários MIPS para programas diferentes Se um novo programa executa mais instruções mas cada instrução é mais rápida o MIPS pode variar de forma independente da performance 18 FALÁCIAS E ARMADILHAS 58 Relacionamento entre MIPS frequência clock rate e CPI Exemplo Qual computador possui o maior MIPS E qual é o mais rápido 6 6 6 10 10 10 CPI f f CPI I I t I MIPS exec Métrica Computador A Computador B I 10 bilhões 8 bilhões f 4GHz 4GHz CPI 10 11 18 FALÁCIAS E ARMADILHAS 59 Calculando MIPS Calculando MIPS MIPS A 4 000 4 10 10 1 10 4 3 6 9 MIPS MIPSB 3 640 3 64 10 10 11 10 4 3 6 9 exec t s t exec A 52 10 4 01 10 10 9 9 s t exec B 22 10 4 11 10 8 9 9