Upload
marcelo
View
10
Download
0
Embed Size (px)
DESCRIPTION
Como se organizam múltiplos processadores.
Citation preview
05/07/2015
1
Paralelismo e Desempenho
Prof. Evans Ghisio
Agenda Multithreading
Pipeline de Instrues
Desempenho de hardware
05/07/2015
2
Multithreading
O conceito de thread usado na discusso sobre processadores multithread pode ou no ser o mesmo conceito de threads de software em sistemas operacionais multiprogramados.
Vejamos alguns termos para elucidar esta diferena:
Multithreading
Processo: uma instncia de um programa executado em um computador. Um processo engloba duas caractersticas principais: posse do recurso e escalonamento/execuo.
Posse do recurso: um processo inclui um espao de endereo virtual para guardar a imagem do processo. A imagem do processo a coleo de programa, dados, pilhas e atributos que definem o processo. De tempos em tempos, a um processador pode ser dado o controle de recursos, como memria principal, canais de E/S, dispositivos de E/S e arquivos.
05/07/2015
3
Multithreading
Escalonamento/execuo: a execuo de um processo segue um caminho de execuo (rastro) por um ou mais programas.
Esta execuo pode ser intercalada com a de outros processos. Assim, um processo possui um estado de execuo, e uma prioridade de despacho, e a entidade que escalonada e despachada pelo sistema operacional.
Multithreading
Troca de processos: uma operao que troca em um processador de um processo para o outro, salvando todos os dados de controle do processador, registradores e outras informaes do primeiro e substituindo com informaes de processo do segundo.
05/07/2015
4
Multithreading
Thread: uma unidade de trabalho dentro de um processo que pode ser despachada. Ela inclui um contexto de processador e sua prpria rea de dados para uma pilha.
Uma thread executa sequencialmente e pode ser interrompida para que o processador possa se dedicar a outra thread.
Multithreading
Troca de Thread: o ato de trocar o controle do processador de uma thread para outra dentro do mesmo processo.
Normalmente, esse tipo de trocar muito menos custoso computacionalmente do que uma troca de processo.
05/07/2015
5
Multithreading
Desta forma, uma thread se preocupa com o escalonamento e execuo, enquanto um processo se preocupa com escalonamento/execuo e posse de recursos.
Varias threads em um mesmo processo compartilham os mesmos recursos, sendo assim, uma troca de thread consome menos tempo que uma troca de processos.
Multithreading
Pode-se concluir que, nesse caso, ocorre um aproveitamento de recursos.
Os sistemas operacionais mais antigos, como verses anteriores do Unix, no suportavam threads.
A maioria dos sistemas operacionais modernos como verses do Linux e Windows suportam threads.
05/07/2015
6
Multithreading
Uma distino feita entre threads em nvel de usurio, as quais so visveis para o programa da aplicao, e threads em nvel de kernel, as quais so visveis apenas para o sistema operacional.
Ambas podem ser definidas como threads explcitas e definidas em software.
Multithreading
Todos os processadores comerciais e a maioria dos processadores experimentais at hoje tem utilizado multithreading explcito.
Esse tipo de sistema executa instrues de diferentes threads em pipelines compartilhados ou com execuo paralela em pipelines paralelos.
05/07/2015
7
Multithreading
Multithreading implcito refere-se execuo concorrente de mltiplas threads extradas de um nico programa sequencial.
. Estas threads implcitas podem ser definidas estaticamente pelo compilador ou dinamicamente pelo hardware.
Multithreading
A partir de agora nosso estudo estar focado em multithreading explcito.
Um processador multithread deve prover no mnimo um contador de programa separado para cada thread de execuo para que seja executada concorrentemente.
05/07/2015
8
Multithreading
Os projetos diferem em quantidade e tipo adicional de hardware adicional para suportar a execuo de threads concorrentes.
Existem quatro tipos abordagens principais para multithreading:
Multithreading
Multithreading intercalado: tambm conhecido como multithreading de granularidade fina.
O processador lida com dois ou mais contextos de thread ao mesmo tempo, trocando de uma thread para outra a cada ciclo de clock.
Se uma thread bloqueada por causa das dependncias de dados ou latncias da memria, ela pulada e uma thread pronta.
05/07/2015
9
Multithreading
Multithreading bloqueado: tambm conhecido como multithreading de granularidade grossa.
As instrues de uma thread so executadas sucessivamente at que ocorra um evento que possa causar atraso, como uma falha na cache.
Esse evento induz uma troca de uma thread para outra.
Multithreading
Granularidade GrossaGranularidade Fina
05/07/2015
10
Multithreading
Multithreading (SMT): instrues so enviadas simultaneamente a partir de mltiplas threads para unidades de execuo de um processador superescalar.
Isto combina a capacidade de envio de instrues superescalares com o uso de mltiplos contextos de threads.
Multithreading Multithreading (SMT):
05/07/2015
11
Multithreading
Chip multiprocessadores: neste caso, o processador inteiro replicado em um nico chip e cada processador lida com threads separadas.
A vantagem desta abordagem que a rea de lgica disponvel em um chip usada eficientemente sem depender da sempre crescente complexidade no projeto de pipeline isto conhecido como multicore.
Multithreading
05/07/2015
12
Multithreading
Multithreading
05/07/2015
13
Multithreading
Pipeline de Instrues
Uma pipeline de instrues semelhante a uma linha de montagem de uma indstria.
Uma linha de montagem tira proveito do fato de que um produto passa por vrios estgios de produo.
Produtos em vrios estgios do processo de produo podem ser trabalhados simultaneamente.
05/07/2015
14
Pipeline de Instrues
Pipeline de Instrues
05/07/2015
15
Pipeline de Instrues
Em uma pipeline de instrues, assim como em uma linha de montagem, novas entradas so aceitas em uma extremidade, antes que entradas aceitas previamente apaream como sadas na outra extremidade.
Para aplicar esse conceito para a execuo de instrues, precisamos reconhecer que, de fato, uma instruo possui vrios estgios.
Pipeline de Instrues
De maneira clara, existe oportunidade para trabalhar simultaneamente vrias instrues, cada uma em um diferente estgio de execuo.
Como uma abordagem mais simples, suponha que o processamento de uma instruo subdividido em dois estgios: busca da instruo e execuo da instruo.
05/07/2015
16
Pipeline de Instrues
Existem momentos durante a execuo de uma instruo em que a memria principal no est sendo usada.
Esse instante pode ser usado para buscar a prxima instruo, em paralelo com a execuo da instruo corrente.
O estgio busca uma instruo e a armazena em uma rea de armazenamento temporrio.
Pipeline de Instrues
Quando o segundo estgio est livre, o primeiro passa para ele a instruo armazenada.
Enquanto o segundo est executando essa instruo, o primeiro tira proveito de ciclos de memria que no so usados para buscar e armazenar a prxima instruo.
Isso chamado de busca antecipada de instruo (instruction prefetch) ou superposio de busca (jetch overlap).
05/07/2015
17
Pipeline de Instrues
Esse processo acelera a execuo de instrues.
Se os estgios de busca e de execuo tiverem a mesma durao, o nmero de instrues executadas por unidade de tempo ser dobrado.
Entretanto, se examinarmos bem essa pipeline veremos que essa duplicao da taxa de execuo de instrues ser pouco provvel, por duas razes:
Pipeline de Instrues
Primeira razo: O tempo de execuo geralmente maior que o tempo de busca, pois a execuo de uma instruo geralmente envolve leitura e armazenamento de operandos e execuo de algumas operaes.
Portanto, o estgio de busca pode ter de esperar algum tempo antes que possa esvaziar sua rea de armazenamento temporrio.
05/07/2015
18
Pipeline de Instrues
Segunda razo: A ocorrncia de instrues de desvio condicional faz com que o endereo da prxima instruo a ser buscada seja desconhecido.
Nesse caso, o estgio de busca teria de esperar at receber o endereo da prxima instruo do estgio de execuo.
O estgio de execuo poderia, ento, ter de esperar enquanto a prxima instruo buscada.
Pipeline de Instrues
Em razo da ocorrncia de instrues de desvio, o tempo perdido pode ser reduzido pelo uso de uma estratgia de adivinhao.
Uma regra simples: quando uma instruo de desvio condicional passada do estgio de busca para o de execuo, o estgio de busca obtm na memria a instruo imediatamente seguinte instruo de desvio.
05/07/2015
19
Pipeline de Instrues
Ento, se no ocorrer o desvio, nenhum tempo ser perdido.
Se ocorrer o desvio, a instruo buscada deve ser descartada, sendo buscada uma nova instruo.
Embora esses fatores reduzam a potencial efetividade da pipeline de dois estgios, algum ganho de desempenho obtido.
Pipeline de Instrues
Para conseguir maior desempenho, a pipeline deve ter maior nmero de estgios. Considere a seguinte decomposio do processamento de uma instruo:
Busca de Instruo (BI): l a prxima instruo esperada e a armazena em uma rea de armazenamento temporrio.
05/07/2015
20
Pipeline de Instrues
Decodificao da instruo (DI): determina o cdigo de operao da instruo e as referncias a operandos.
Clculo de operandos (CO): determina o endereo efetivo de cada operando fonte. Isso pode envolver endereamento por deslocamento, endereamento indireto via registrador, endereamento indireto, assim como outras formas de clculo de endereo.
Pipeline de Instrues
Busca de operandos (BD): busca cada operando localizado na memria. Os operandos localizados em registradores no precisam ser buscados.
Execuo da instruo (EI): efetua a operao indicada e armazena o resultado, se houver, na localizao do operando de destino especificado.
05/07/2015
21
Pipeline de Instrues
Escrita de operando (ED): armazena o resultado na memria.
Pipeline de Instrues
05/07/2015
22
Sem pipeline
Com pipeline
Desempenho de hardware
Um computador multicore, conhecido tambm como chip multiprocessador, combina dois ou mais processadores (chamados ncleos core) em uma nica pea de silcio (chamada pastilhas die).
Normalmente, cada ncleo consiste de todos os componentes de um processador independente, como registradores, ULA, hardware de pipeline e unidade de controle, mais caches L1 de dados e de instrues.
05/07/2015
23
Desempenho de hardware
Alm de vrios ncleos, os chips multicoreatuais incluem tambm cache L2 e, em alguns casos, cache L3.
Desempenho de hardware
Os sistemas dos microprocessadores experimentaram um aumento slido e exponencial do desempenho de execuo durante dcadas, o que pode ser evidenciado pela Lei de Moore.
As mudanas organizacionais no projeto dos processadores se concentraram, em primeiro lugar, no aumento do paralelismo em nvel de instrues, para que mais trabalho pudesse ser feito em cada ciclo de clock.
05/07/2015
24
Desempenho de hardware Dentre estas mudanas podem ser destacadas:
Pipeline: instrues individuais so executadas por um pipeline de estgios de tal forma que, durante a execuo de uma instruo em um estgio do pipeline, outra instruo executada em outro estgio do pipeline.
Superescalar: vrios pipelines so construdos pela replicao de recursos da execuo. Isto possibilita execuo paralela de instrues em pipelines paralelos, assim que os hazards so evitados.
Desempenho de hardware
Multithreading simultneo (SMT): bancos de registradores so replicados para que vrias threads possam compartilhar o uso dos recursos do pipeline.
05/07/2015
25
Organizaes alternativas do chip
Desempenho de hardware
Para cada uma destas inovaes, os projetistas tentaram, ao longo dos anos, aumentar o desempenho do sistema acrescentado complexidade.
No caso do uso de pipeline, pipelines simples de trs estgios foram substitudos pelos pipelines com cinco estgios e depois com muito mais estgios, com algumas implementaes tendo mais de doze estgios.
05/07/2015
26
Desempenho de hardware
H um limite prtico para at onde essa tendncia pode ser levada porque, com mais estgios, h necessidade por mais lgica, mais interconexes e mais sinais de controle.
Com a organizao superescalar, aumentos de desempenho podem ser alcanados ao se aumentar o nmero de pipelines paralelos.
Novamente, o retorno diminui medida que o nmero de pipelines aumenta.
Desempenho de hardware
Mais lgica necessria para gerenciar os hazards e para recursos do estgio de instrues.
Eventualmente, uma nica thread de execuo alcana o ponto onde os hazards e dependncias de recursos impedem o uso total de vrios pipelines disponveis.
05/07/2015
27
Desempenho de hardware
Este mesmo ponto da diminuio de retornos acontece com o SMT, medida que a complexidade de gerenciar vrias threads por meio de um conjunto de pipelines limita o nmero de threads e o nmero de pipelines que podem ser usados efetivamente.
Desempenho de hardware
H um conjunto de problemas relatado que trata de questes relacionadas ao projeto e fabricao de chips de computadores.
O aumento na complexidade para lidar com todas as questes de lgica relacionadas com pipelines muitos longos, vrios pipelines superescalares e vrios bancos de registradores SMT significa que uma grande rea do chip ocupada com lgica de coordenao e transferncia de sinais.
05/07/2015
28
Desempenho de hardware
Isso aumenta a dificuldade de projeto, fabricao e depurao de chips.
O difcil e crescente desafio de engenharia relacionado lgica de memria mais simples.
Desempenho de hardware
Para manter a tendncia de desempenho mais alta medida que o nmero de transistores por chip aumenta, os projetistas recorreram aos projetos de processadores mais elaborados (pipeline, superescalar, SMT) e s altas frequncias de clock.
Infelizmente, requisitos de energia cresceram exponencialmente medida que aumentaram a densidade e a frequncia de clock do chip.
05/07/2015
29
Desempenho de hardware
Uma maneira de controlar densidade da energia usar mais rea do chip para memria cache.
Os transistores so menores e tm uma densidade de energia em ordem de magnitude menor do que a da lgica.
Com o passar do tempo, a percentagem da rea do chip dedicada memria cresceu para mais de 50% medida que a densidade de transistores do chip aumentou.
Desempenho de hardware
At 2017, podemos esperar ver chips de microprocessadores com cerca de 150 bilhes de transistores em um molde de 300 mm ou at menores.
Supondo que 50 a 60% da rea do chip seja dedicado memria, ele suportar memria cache em torno de 100 MB e deixar em torno de 1 bilho de transistores disponveis para lgica.
05/07/2015
30
Desempenho de hardware
Como usar todos esses transistores um ponto chave do projeto.
Conforme discutido anteriormente nesta seo, existe limite para uso efetivo de tais tcnicas como superescalar e SMT.
Em termos gerais, a experincia das dcadas recentes foi definida por uma regra conhecida como regra de Pollack, que diz que o aumento de desempenho diretamente proporcional raiz quadrada do aumento de complexidade.
Desempenho de hardware
Em outras palavras, se voc dobrar a lgica em um ncleo do processador, ento ele apresenta apenas 40% a mais de desempenho.
A princpio, o uso de vrios ncleos tem o potencial para fornecer um aumento de desempenho quase linear com aumento em nmero de ncleos.
05/07/2015
31
Desempenho de hardware
Consideraes sobe energia fornecem outro motivo para ir em direo a uma organizao multicore.
Como o chip tem tanta quantidade de memria cache, torna-se improvvel que uma nica thread de execuo possa efetivamente usar toda essa memria.
Desempenho de hardware
Mesmo com SMT, se est fazendo multithreading de forma relativamente limitada e no pode, portanto, explorar totalmente uma cache gigante, enquanto que um nmero de threads ou processos relativamente independentes tem uma oportunidade maior de obter a total vantagem da memria cache.
05/07/2015
32
Agradecimentos
Muito obrigado e preparem-se para a prova.
Prova dia: 13/07
Recuperao de todo o contedo dia: 20/07
As Notas estaro disponveis no site at o dia: 17/07