Embed Size (px)
Citation preview
1
Sistemas Microprocessados – ENGC50
Prof. Augusto Loureiro da CostaDepartamento de Engenharia Elétrica
Escola PoltécnicaUniversidade Federal da Bahia
2
Programa do Curso
IntroduçãoDesempenho de Sistemas de Computação: aspectos Arquitetura de Conjunto de InstruçõesEstrutura do processador: fluxo de dados e controleSistemas de Entrada/Saída e comunicaçãoSistemas de Memória.
3
Slides - referênciasftp://ftp.nuperc.unifacs.br/professor/celso/publico/html/Modulo1/University College of London, J. Crowcroft, S. Wilbur,www.cs.ucl.ac.uk/teaching/1B10 ©UCLUniversity of California, Berkeley, David Patterson’s lectureslides ©UCB, DAP’ 97 www.cs.berkeley.edu/~pattrsn/152F97/index_lectures.html
Morgan Kaufmann Publishers, Tod Amon www.mkp.com/books_catalog/cod2/ph2_res.htm#slidesCopyright 1998 Morgan Kaufmann Publishers
Central Queensland University, A Silberschatz, P. Galvin, www.infocom.cqu.edu.au/Units/win99/85349/Resources/Lectures ©CQU
4
INTRODUÇÃO
5
O que é a Arquitetura de um Computador?
Arquitetura de Computadores =
Conjunto de Instruções(ISA - Instruction Set Architecture)
+Organização da Máquina
6
Conjunto de Instruções da Arquitetura (ISA)
... os atributos de um sistema [de computação] vistos pelo programador, i.e. a estrutura conceptual e o comportamento funcional, são distintos da organização dos fluxos de dados e dos controles da lógica e da implementação física. [Amdahl, Blaaw andBrooks, 1964]
-- Organização da Memória
-- Tipos de dados e estruturas de dados:Codificações e representações
-- Conjunto de Instruções
-- Formato das Instruções
-- Modos de Endereçamento e Acesso de Dados e Instruções
-- Condições de Exceção
7
Conjunto de Instruções: Uma Interface Crítica
Conjunto de instruções
software
hardware
8
Conjunto de Instruções
O conjunto de instruções especifica o mais baixo nível das funcionalidades de uma máquina.
O conjunto de instruções é como o “vocabulário”do computador; as instruções seriam suas “palavras”.
É possível se fazer um mapeamento quase de 1-para-1 entre as instruções de máquina (binárias) e representações simbólicas (mnemônicos) em linguagens de montagem (ou assembly)
9
Exemplos de Conjuntode Instruções da Arquitetura
Digital Alpha (v1, v3) 1992-97HP PA-RISC (v1.1, v2.0) 1986-96Sun Sparc (v8, v9) 1987-95SGI MIPS (MIPS I, II, III, IV, V) 1986-96Intel (8086,80286,80386, 1978-00
80486,Pentium, MMX, ...)
10
MIPS R3000 Instruction Set Architecture
Tipo de InstruçãoLoad/StoreComputationalJump and BranchFloating Point (coprocessor)Memory ManagementSpecial
R0 - R31
PCHILO
OP
OP
OP
rs rt rd sa funct
rs rt immediate
jump target
3 Formatos de Instrução: TODOS com 32 bits de comprimento
Registradores
Q: Quem já ouviu falar desta arquitetura?
11
Organização da Máquina
Capacidades & Características de Desempenho das Principais Unidades Funcionais (Fus)
(ex., Registradores, ULA, Shifters, Unidades Lógicas, ...)
Forma de interconexão dos componentesFluxo de informação entre componentesLógica e forma pela qual o fluxo de informações écontroladoImplementação do ISA sobre as Unidades FuncionaisDescrição do Nível de Transferência dos Registros
12
Exemplo de Organização
TI SuperSPARCtm TMS390Z50 da Sun SPARCstation20
Floating-point Unit
Integer Unit
InstCache
RefMMU
DataCache
StoreBuffer
Bus Interface
SuperSPARC
L2$
CC
MBus Module
MBus
L64852 MBus controlM-S Adapter
SBus
DRAM Controller
SBusDMA
SCSIEthernet
STDIOserialkbdmouseaudioRTCBoot PROMFloppy
SBusCards
13
O que é Arquitetura de Computadores?
Coordenação de níveis de abstração
I/O systemInstr. Set Proc.
CompilerOperating
System
Application
Digital DesignCircuit Design
ISA - Instruction SetArchitecture
Sujeita a um conjunto de influências em constante e rápidas alterações.
14
Desempenho crescente. . .
Computadores têm se tornado incrivelmente mais poderosos desde que foram inventados nas décadas de 30-40.
• Um palm-top hoje é tipicamente mais potente que ...
• ... uma máquina IBM que ocupava uma sala na geração anterior.
15
Influências nas Arquiteturas...
Arquitetura deComputadores
Tecnologia Linguagens deProgramação
SistemasOperacionais
História
Aplicações
(A = F / M)
Levando em conta que... O ENIAC tem 18000 válvulas e pesa 30 toneladas, no futuro os computadores deverão ter 1000 válvulas e pesar 1,5 toneladas
Revista Popular Mechanics, março de 1949.
16
Tecnologia: memória
DRAMYear Size1980 64 Kb1983 256 Kb1986 1 Mb1989 4 Mb1992 16 Mb1996 64 Mb1999 256 Mb2002 1 Gb2009 ? Gb
capacidade do chip DRAMEm ~1985 o processador “single-chip” (32-bit) e o computador “single-board” apareceram⇒ workstations, personal
computers, multiprocessorssurgiram nessa era
Em 2002 + δt, este caminho nos leva a crer que teremos mainframescomparados a computadores “single-chip” (talvez 2 ou + chips)
17
Tecnologia: densidade
i80286
i80486
Pentium
i80386
i8086
i4004
R10000
R4400
R3010
SU MIPS
1000
10000
100000
1000000
10000000
100000000
1970 1975 1980 1985 1990 1995 2000 2005
Núm
ero
de T
rans
isto
rs
i80x86M68KMIPSAlpha
Densidade de Lógica dos Microprocessadores
18
Projeções de DesempenhoLo
gdo
des
empe
nho
0.1
1
10
100
1000
1965 1970 1975 1980 1985 1990 1995 2000
Microprocessors
Minicomputers
Mainframes
Supercomputers
19
Desempenho: CPU e Redes (Patterson)
Ano
DesempenhoRelativo
1000
100
10
11980 1985 1990 1995 2000
100 Mb FDDI10 Mb
1 Gb ATM
MIPSM/120
DECAlpha
CPU(spec)
LAN
20
Tecnologia: mudanças drásticas
Processadorcapacidade lógica: ~ 30% por anotaxa de clock: ~ 20% por ano
MemóriaCapacidade DRAM: ~ 60% por ano (4x em 3 anos)Velocidade: ~ 10% por anoCusto por bit: ganho de 25% por ano
DiscosCapacidade: ~ 60% por ano
21
Desempenho dos Processadores
0
50
100
150
200
250
300
35019
82
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
Ano
Des
empe
nho
RISC
Intel x86
35%/yr
Introdução doRISC
Quais as possibilidades do RISC em relação às outras?
Desempenho aumenta ~ 50% por ano (2x a cada 1.5 ano)
22
Linguagens e Aplicações
CAD, CAM, CAE, . . .MAC, Unix, DOS, . . . Multimídia, . . .World Wide Web, . . .JAVA, . . .???
Tecnologia criando necessidades versus necessidades demandando novas tecnologias
23
Assim ...
Arquitetura é um processo iterativo-- Busca de espaço para possíveis projetos-- Observar todos os níveis de sistemas de
computação
Design
Análise
Boas IdBoas IdééiasiasIdéias Medíocres
Idéias Ruins
Custo/Análise deDesempenho
Criatividade
24
Visão geral de Arquitetura de Computadores
Arquitetura de Computadores e Engenharia
Conjunto de Instruções Organização do Computador
Interfaces Componentes de Hardware
Visão Compilador/Sistema Visão do Projeto Lógico
“Arquitetura da Construção” “Engenharia de Construção”
25
Arquitetura Básica dos Computadores Atuais
CPU: ALU (datapath)+ control
Cache
I/OController
I/OController
I/OController
Main Memory
Graphicsdisplay
Keyboard
main bus
interrupts
26
Como se fazer entender pelo computador?
“Linguagem” do computador : 100011000001 (bits)Números binários: base da teoria computacional
1. Primórdios: uso da linguagem nativa em binário!!!2. Linguagem de Montagem (Assembly)
Montador: traduz uma versão simbólica das instruções para sua representação binária na arquiteturaadd A, B → montador → 100011000001
3. Linguagem de Programação de alto-nívelCompilador: traduz instruções de alto-nível para instruções binárias diretamente ou via um montadorA + B → compilador → add A, B → montador →100011000001 ouA + B → compilador → 100011000001
27
Mas é só isso?
Existe ainda um programa que gerencia os recursos da máquina durante a execução dos programas: o SISTEMA OPERACIONAL (SO)Operações de Entrada/Saída (E/S), “carga” do programa na memória, exceções, etc.O SO funciona como um gerente dos recursos, escondendo o acesso direto ao hardware dos usuáriosMais ainda: multiprocessamento, gerência de arquivos, processamento distribuído, ...Assim, existem diversas camadas e serviços disponíveis para auxiliar nossa comunicação com a máquina.
28
Uma questão?
O que é isto?00000000001000100100000000100000
• Pode ser lido como:25 + 214 + 217 + 221
= 32 + 16384 + 131072 + 2097152= 2244640
214
15o. bit 6o. bit
25 ... 20
29
Diálogo com o computador...
Melhor assim?00000000 00000001 00000010 00001000 0000000
0010000000000000 00000011 00000100 00001001 0000000
0010000000000000 00001000 00001001 00000101 0000000
00100010
• O que é isto?0000000000000001000000100000100000000000010000000000000000000110000010000001001000000000100000000000000000100000001001000001010000000 00100010
30
Traduzindo...
E assim?0 1 2 8 0 320 3 4 9 0 320 8 9 5 0 34
• Melhorando...add $8, $1, $2add $9, $3, $4sub $5, $8, $9
31
Traduzindo mais um pouco...
Melhorando ainda mais...$8 = $1 + $2$9 = $3 + $4$5 = $8 - $9
• Claro agora?u = a + bv = c + d;x = u - v
• Sim, é claro: x = (a+b) - (c+d)
32
Níveis de Representação
Programa em Linguagem de Alto-Nível
Programa em Linguagem de Montagem
Programa em Linguagem de Máquina
Especificação do controle de sinais
Compilador
Montador ou Assembler
Interpretação da Máquina
x = (a+b)x = x – (c+d)
lw $15, 0($2)lw $16, 4($2)sw $16, 0($2)sw $15, 4($2)
0000 1001 1100 0110 1010 1111 0101 10001010 1111 0101 1000 0000 1001 1100 0110 1100 0110 1010 1111 0101 1000 0000 1001 0101 1000 0000 1001 1100 0110 1010 1111
°°
ALUOP[0:3] <= InstReg[9:11] & MASK
Compilador
33
Níveis de Organização
SPARCstation 20
Processador
Computador
Controle
Datapath
Memória Dispositivos
Entrada
Saída
Objetivo do Projeto:25% do custo - Processador25% do custo - Memória(configuração mínima)Resto – dispositivos I/O,energia, gabinete, etc.
34
Executando um Programa:Ciclo de Execução
Obtém uma instrução do programa armazenado
Determine as ações e o tamanho da instruções
Localiza e obtém os dados (operandos)
Calcula um valor do resultado ou status
Armazena resultados na memória para uso futuro
Determina a próxima instrução
InstructionFetch
InstructionDecode
OperandFetch
Execute
ResultStore
NextInstruction
35
Instruções Básicas de Programas
Conjunto de instruções = linguagem de máquinaInstrução: opcode [operandos]Tipos de instrução:
Instruções aritméticas e lógicas (add, sub, AND, OR)Referência à memória ou Load&storeDesvios Condicionais: if + goto / if-then-elseDesvios incondicionais ou saltos (jumps)
Formas de endereçamento: complexidade da arquite-tura → em RISC poucas formas de endereçamento direto a operandos; instruções de mesmo tamanho
36
Registradores
Registradores armazenam palavras simples na CPU, em locais próximos à ULA.
A ULA tem acesso extremamente rápido aos registradores
Em arquiteturas RISC modernasTodas as instruções são executadas sobre dados armazenados em registradoresInstruções do tipo carregar/armazenar (load/store)↔ registradores
MIPS:32 registradores indicados: $0...$31
37
Avaliando o desempenho de arquiteturas
Métricas de projeto:
- Pode ser implementado em quanto tempo e com qual custo?
- Pode ser programado? Fácil para compilar?Métricas estáticas:- Quantos bytes o programa ocupa na memória?Métricas dinâmicas:- Quantas instruções são executadas?- Quantos bytes o processador deve buscar para
executar o programa?- Quantos clocks são requeridos por instrução (CPI)?- Qual valor de clock ideal?
Melhor métrica: Tempo para executar o programa!
NOTA: isto depende do conjunto de instruções, da organização do processador e das técnicas de compilação
CPI
Inst. Count Cycle Time
38
Aspectos do Desempenho da CPU
CPU time = Seconds = Instructions x Cycles x SecondsProgram Program Instruction Cycle
CPU time = Seconds = Instructions x Cycles x SecondsProgram Program Instruction Cycle
instr count CPI clock rate
Programa X
Compilador X X
Conj. Instr. X X
Organização X X
Tecnologia X
39
Lei de Amdahl
Ganho de velocidade (speed-up) devido ao ganho E:
speedup(E) = TExec sem E = Desempenho com E
TExec com E Desempenho sem E
Suponha que a melhoria E acelere a parte S e o restante do programa não é afetada pela melhoria:
TExec(com E) = ((1-F) + F/S) × TExec(sem E)
speedup(com E) = 1 1(1-F) + F/S
40
Desempenho x Tecnologia
Poder da Tecnologia: 1.2 x 1.2 x 1.2 = 1.7 x / anoTamanho: miniaturização ganha 10%/ ano →velocidade de chaveamento ganha 1.2 / ano.Densidade: aumenta 1.2x / ano.Área da pastilha (die): 1.2x / ano.
A lição da abordagem RISC é deixar o conjunto de instruções (ISA) o mais simples possível:
Ciclo de projeto curto → explora de maneira otimizada a tecnologia (~3 anos)Técnicas de pipeline e previsão de desvios (branches)Caches on-chip maiores e mais sofisticados
41
PROCESSADOR E
MEMÓRIA
42
Onde estamos agora?
Cinco componentes do computador
Projetando uma CPU monociclo
Conjunto de Instruções(parte 2)
tecnologia (parte 1 e 2)
Projeto da máquina
Aritmética
Processor
Computer
Control
Datapath
Memory Devices
Input
Output
43
Filosofia RISC [Tanembaum]...
1. Regra de base: Simplificar a via de dados – registradores, ULA e barramentos de interconexão;
2. Minimizar tempo de ciclo da via de dados:• Faça o comum executar mais rápido• A simplicidade favorece a regularidade
3. “A perfeição é atingida, não quando não existe nada mais a acrescentar, mas quando não existe nada mais a jogar fora!”[St. Exupéry]
44
Implementação do conjunto de instruções
Para executar qualquer instrução:1. Enviar o valor do PC para a memória que contém o
código (opcode) e trazer para a via de dados a instrução armazenada nessa memória
2. Ler registradores (1 ou mais), usando os campos da instrução para selecioná-los (operandos)
As ações do hardware para completar a execução da instrução variam, mas em geral, usam a ULA (simpli-cidade e regularidade)
INSTRUÇÂO opcode operando 1 operando 2
45
Visão geral da implementação MIPS
DataOut
Clk
5
Rw Ra Rb32 32-bitRegisters
Rd
AL
U
Clk
Data In
DataAddress Ideal
DataMemory
Instruction
InstructionAddress
IdealInstruction
Memory
Clk
PC
5Rs
5Rt
32
323232
A
B
Nex
tAdd
ress
Control
Datapath
Control Signals Conditions
46
Controle e Via de Dados
Controle: define os sinais para acionar o hardware (unidades funcionais) para cada instrução decodificadaVia de dados: movimentação de dados mem-reg, reg-reg, reg-ULA (barramentos + unidades)CPU “monociclo”: instrução quebrada em passos correspondentes às unidades funcionais envolvidas
PCInstrução
Endereço deleitura
Memória de instruções
4 som
ador
Ex: Busca dapróxima instrução
47
Implementação “multiciclo”
Cada passo de execução da instrução = 1 ciclo de clockCompartilhamento das unidades funcionais dentro do espaço de tempo correspondente a uma instruçãoAssume-se que o ciclo de clock possa acomodar operações de acesso à memória, uma operação da ULA e acesso (leitura-escrita) aos registradoresA via de dados possui registradores “adicionais” para armazenar valores usados nas próximas instruções (registrador de instrução e registrador de dados da memória, saída da ULA, operandos lidos dos reg’s, ...)Ex: Busca da instrução X (PC) → PC = PC +4 → ...
PC pode ser incrementado antes do fim da instrução X
48
Controle numa CPU multiciclo (1)
Complexidade aumenta:Monociclo: tabelas-verdade (combinacional)Multiciclo: próximo estado depende do atual e dos sinais de entrada (seqüencial)
Duas soluções:1. Máquina de estados – seqüência de estados e regras
de transição2. Multiprogramação – representação para o controle
semelhante a um programaQuanto mais simples o conjunto de instruções, mais simples e ágil o controle: INTEL 80x86 precisa de milhares de estados (modos de endereçamento, mais
opcodes); MIPS 100 instruções
49
Controles baseados em Máquinas de Estado
Lógica de ControleCombinacional
Entradas
Saíd
as
Saídas de controle docaminho de dados
Entradas vindas do opcodedo registrador de instruções
Registradorde estado
Próximoestado
50
Controle por Microprogramação
Máquinas de estados não são adequadas para controle de conjunto de instruções complexos! A única saída é a microprogramaçãoMicroprograma: conjunto de microinstruções que definem o conjunto de sinais de controle da via de dados a serem ativados em determinado estado
Representação simbólica do controle, que deve ser traduzida em termos de sinais para o hardwareEm geral, o microprograma está numa ROM ou PLA
Ainda fazem parte do controle da CPU: tratamento de interrupções e de exceções que determinam mudança no fluxo normal de execução (overflow, operação de E/S)
51
CPU’s de arquiteturas conhecidas
Kernel: via de dados e controleOutras técnicas para aumentar o desempenho: pipeline
1985: MIPS R2000 com pipelineAté 80386 sem pipeline80486, Pentium, Pentium PRO têm pipeline, mas o controle continua extremamente complexo para suporte das instruções da linha 80x86
Pentium e Pentium PRO usam pipeline superescalar: mais de uma instrução por clock replicando os recursos da via de dados
Pentium suporta até 2 instruções e o POR, até 4Pentium PRO usa conceitos RISC
52
Aumentando o desempenho: Pipeline
Técnica de implementação de processadores que permite a superposição temporal de diversas fases de execução de instruçõesCada passo de execução da instrução deve ser executada em 1 ciclo de clock:
Tecnologia limita o tempo de clock e o tempo de cada passo do pipeline
A idéia de base é aumento a “vazão” e não redução do tempo de execução por instrução:
Analogia: Produção de uma linha de montagem de automóveis = 1 automóvel por minuto!
53
Implementação um pipeline
1 2 3 4 51 2 3 4 5
1 2 3 4 51 2 3 4 5
1 2 3 4 51 2 3 4 5
1 clock
BuscaInstrução
Decodificainstrução
ExecutaOperação
AcessaMemória
Escreveresultado tempo
Ordem de execução
54
Vantagens do RISC
Instruções têm o mesmo tamanho: busca e decodificação simples e com tempo reduzidoInstruções simétricas e com uso dos registradores facilita a seqüência das operações do pipelineO uso de apenas instruções load & store para referên- cias à memória permite o uso do estágio de execução para cálculo de memória, para depois, no seguinte, acessar a memória
55
Problemas a vista: conflitos do pipeline
Conflitos estruturais: com uma memória única para dados e instruções, existe um conflito entre o ciclo de busca de instrução e escrita em memória; a solução éusar duas memórias independentes (design) Conflitos de controle: obrigam a parada do pipeline
Instruções de desvioParadas geram bolhas no pipeline
busca di ULA mem w regbusca di ULA mem w reg
busca di ULA mem w reg
tempo
Ordem de execução
add $4,$5,$6beq $1,$2,40
lw $3,300($0)
bolha bolha bolha bolha bolha
56
Outros conflitos
Conflitos por dados: a próxima instrução utiliza um operando da instrução anterior que ainda não estápronto:
add $s0, $t0, $t1sub $t2, $s0, $t1
busca di ULA mem w regbusca di
tempo
Ordem de execução
add$s0,$t0,$t1sub $t2,$s0,$t3
ULA mem w regdi
57
Soluções clássicas para conflitos
Reordenação do código (compilador): mudar a ordem de execução sem que o resultado da execução global seja alterado pode evitar as bolhasIncluir instruções do tipo NOPAdiantamento de instruçõesPré-suposição da realização do desvio condicional (if)Predição dinâmica em loops e desvios baseado em dados armazenados (história)
E em pipelines superescalares? Mais complexidade...
58
Próximo passo...
Hierarquia de Memória: reduzindo o tempo de acesso aos dados
59
Os componentes clássicos de um computador
O processador deve buscar cada dado e instrução na memória durante a execução de um programa: o
tempo de acesso é fundamental para o desempenho!
Processor
Computer
Control
Datapath
Memory Devices
Input
Output
60
Desafios para a memória...
Desempenho da CPU aumenta 25-50% p.a.Desempenho das memórias, cerca de 7% p.a.
Capacidade Velocidade
Lógica: 2x em 3 anos 2x em 3 anos
DRAM: 4x em 3 anos 1.4x em 10 anos
Disco: 2x em 3 anos 1.4x em 10 anosDRAM
ano Tam Tempo de Ciclo1980 64 Kb 250 ns1983 256 Kb 220 ns1986 1 Mb 190 ns1989 4 Mb 165 ns1992 16 Mb 145 ns1995 64 Mb 120 ns
61
Reflexões Sobre Arquiteturas de Memórias
A velocidade de memória aumenta muito menosrapidamente que a dos processadores (Lei de Moore)Para máquinas + rápidas, é necessário projetar um sistema de memória de forma a não desperdiçar osganhos adquiridos com o processadorSolução: hierarquia de memória e cachesÉ desejável que o usuário “acredite” que ele tem um espaço de memória enorme, mesmo se a quantidade de memória é sabidamente limitadaO SO precisa suprir o mesmo espaço de memória paravários usuários sem que haja conflitoSolução: Memória Virtual
62
Melhorando o desempenho: Princípio da localidade
Localidade TemporalUma palavra de memória que acaba de ser referenciada, tende a ser novamente referenciada
Localidade EspacialItens cujos endereços estão próximos daqueles queacabam de ser referenciados tendem a ser referenciados também brevemente
Conclusão: usar mecanismos que permitam armazenartemporariamente o material com que se trabalhaObservar a estrutura dos programas:
Programas acessam somente uma pequena porçãode memória num curto espaço de tempo
variáveis – temporal, laços - temporal e espacial, percurso de arrays - espacial
63
Idéia de hierarquia para a memóriaDividir o espaço de memória em níveis com tamanhos, velocidades e custos diferentes por nível
O princípio da localidade pode ser aplicado diretamente àhierarquia de memória: quanto mais rápida a memória, mais próxima ao processador
Velocidade Tam Custd: $/bit Exemplo
+ rápida menor + alto 64k SRAM
64M DRAM
+ lenta maior + baixo 6.4 G Mag. Disk
MemóriaNível 1
MemóriaNível 2
Processador
MemóriaNível 3
capacidade
64
Hierarquia de Memória atualmente
Memória
Registradores CPU~100 Bytes~10 ns
CacheK Bytes10-100 ns
Memória PrincipalM Bytes100ns-1us
DiscoG Bytesms-3 -4
CapacidadeTempo de Acesso
Tapeinfinitosec-min
Cache
Registradores
Tape
Disco
Operandos Inst.
Blocos
Páginas
Arquivos
EstágioUnidade
prog./compil.1-8 bytes
contr. cache8-128 bytes
SO512-4K bytes
user/operadorMbytes
Nível + Alto
Nível + baixoMaior
Fonte: Slides Patterson
+ rápido
65
Funcionamento a hierarquia (1)
Pode conter diversos níveis, mas a gerência é feita entre níveis adjacentesUnidades de mapeamento entre níveis: blocosSe a informação solicitada pelo processador estiver presente no nível superior da hierarquia, ocorre um “acerto” (hit)Se a informação não puder ser encontrada nesse nível, ocorre uma “falha” (miss) e um nível mais baixo éacessado para que o bloco desejado seja recuperadoA medida de desempenho da hierarquia é relacionada àtaxa de acertos dos acessos: fração dos acessos à me-mória encontrados no nível superiorOutra medida: taxa de falhas = 1 – taxa de acertos
66
Funcionamento a hierarquia (2)
Desempenho = tempo de acesso à memória1. Tempo de acerto (ta): tempo para acessar o nível
superior da hierarquia (RAM) + tempo necessário para se determinar se o acesso é ou não um acerto
2. Penalidade por falta (tf): tempo para substituir um dos blocos do nível superior pelo bloco do nível inferior com a informação desejada + tempo para enviar o dado ao processador
ta << tf: tempo de acesso ao nível inferior é muito maiorHierarquia de memória tem influência direta na gerên-cia de memória feita pelo SO, no código gerado pelo compilador e até mesmo no tipo de aplicação a ser executada na máquina.
67
Conceitos básicos sobre Memória Cache
Cache: esconderijo! ☺De maneira abrangente: qualquer memóriagerenciada que tira proveito das propriedadesde localidadeComo fazer para guardar os dados e instruçõesrecentemente usados numa cache:
Como saber se um item de dado está ounão na cache?Se estiver, como achá-lo?
68
Conceitos básicos sobre Memória Cache
Caches com mapeamento direto mapeiam cadaendereço de memória numa locação específicada cache
Várias locações de memória têm a mesmalocação na cacheUsa um mecanismo modulo N (N é potênciade 2)Precisa de uma tag indicando o endereçoatualmente armazenadoPrecisa de um bit de validade indicando se o dado está na cache
69
Cache com mapeamento direto simples
131415161718
0123456789101112
Memória
0123
Cache diretamente mapeadoTamanho = 4
•Cache de 4 (22) palavras•Endereços de memória “mod 4”
mapeiam locações de cache•Muitos endereços de memória são
mapeados p/ uma mesma locação•Usa log2N bits de endereços para
a indexaçao da cache19
70
Acesso à cache: Rótulo (tag) e Índice (index)Considerando endereços de memória de 32-bits :
Uma cache com mapeamento direto de 2N bytes:− Índice (index): Os N bits mais baixos dos endereços de memória− Rótulo (tag): Os (32-N) bits mais altos dos endereços de memória
Cache Index
0123
2 - 1N
:
2 N BytesCache com Mapeamento Direto
Byte 0Byte 1Byte 2Byte 3
Byte 2N -1
0N31
:
Cache Tag Ex: 0x50 Ex: 0x03
0x50
Armazenados comoparte do cache “state”Bit validade
:
Endereços de Memória
71
Alguns comentários…
Cache com mapeamento direto precisa ser grandesuficiente , por ex, para que as últimas instruções num laço de execução não se sobreponham sobre as anteriores (a cache com 4 blocos é apenas exemplo)Podem existir 2 caches o numa arquitetura: uma parainstruções e outra para dados
Em geral, não é mais eficiente que apenas umacache para um tamanho fixo de cacheMas, o dobro de vazão pode ser compensar
No start-up, a cache está vazia (ou inválida) e tem-se uma taxa de falhas elevada inicialmenteA abordagem trata assim da localidade temporal masnão da localidade espacial
72
Cache com 64KB (DECStation 3100)
31 30 29 28 ... ... 19 18 17 16 15 14 13 12 ... ... 7 6 5 4 3 2 1 0Endereços de Memória
V Tag Data-32bits
16kentradas
Data
Index
EQ
AND
Tag
ValidHIT
14
16
16 32
Deslocamento
73
Localidade temporal
A cache mostrada anteriormente apenas explora a localidade espacialPara tratar com a localidade temporal um bloco de maisde uma palavra é transferido para a cache no caso de uma falha (miss)No exemplo seguinte, a cache tem o mesmo tamanho(64KB), mas 4K entradas para blocos de 16 bytes cada:
Os próximos devem gerar acertos ao invés de faltasIsso pode provocar um aumento significativo na taxade acertos, mesmo com pequenos tamanhos de blocos
74
Cache com 64KB (DECStation 3100)
31 30 29 28 ... ... 19 18 17 16 15 14 13 12 ... ... 7 6 5 4 3 2 1 0Endereços de Memória
V Tag Data-0 Data-4 Data-8 Data-12
4kentries
Select
Block offset
Data
Index
EQ
AND
Tag
ValidHIT
75
Resultados de desempenho das duascaches
Fonte: Livro P&H p. 329
Programa Tam. Bloco TaxaI-miss Taxa D-miss Taxa Comb. miss
gcc 1 6.1% 2.1% 5.4%4 2.0% 1.7% 1.9%
spice 1 1.2% 1.3% 1.2%4 0.3% 0.6% 0.4%
Tamanho da cache: 128KB (64KB + 64KB)
76
Tamanho do Bloco de Cache
Em geral, um tamanho maior leva a vantagem dalocalidade espacial dos dados, MAS:
Maior tamanho de bloco significa maior penalidade de falhas (miss penalties) – mais tempo para encher um blocoSe o tamanho do bloco é muito grande em relação aotamanho da cache, a taxa de falhas irá aumentar
TMédio de Acesso = tacerto x (1 – taxa_acerto) + penalidade_falha x tfalhas
77
Tamanho do Bloco de Cache
Taxa deFalhas
Tam. Bloco
Taxa deAcerto Explora a Localidade
Espacial
Poucos blocos: compromete alocalidade temporal
Tempo Médio de Acesso
Aumenta Miss Penalty& Miss Rate
Tam. Bloco Tam. Bloco
Fonte: Patterson slides
78
Acessos em escrita
Não é tão simples em se tratando de cache
Deve-se assegurar que o dado foi escritona memória
Do contrário, memória e cache podem se tornar inconsistentes
79
Acessos em escrita
Solução mais simples: write-throughMemória e cache escritas ao mesmo tempoMas se for necessário uma espera para isso, osvalores da cache serão perdidos!
Usar um buffer (FIFO) no caminho de escritapara a memóriaBuffers permitem “equalizar” o serviço quandoa taxa de chegada de requisições é variável(algo como cadeiras num banco para osclientes esperarem…)
80
Outras soluções para escrita…
Escrita somente no retorno: write-backAtualização quando o bloco for susbstituído e se houver ocorrido alteração
Escrita somente uma vez : write-onceIdeal para sistemas multiprocessadores, quecompartilham um mesmo barramento (maisadiante)O controlador da cache escreve a atualização namemória principal sempre que o bloco for atualizado pela primeira vez na cache – ou seja, faz um write-through e ainda alerta os demaiscomponentes ligados ao barramento que houve a alteração
81
Comparando as três soluções
write-through : pode acontecer uma grandequantidade de escritas desnecessárias na memória…
write-back : minimiza o problema, mas a memóriapode ficar temporariamente desatualizada, obrigandoque outros dispositivos acessem os valores via cache…
write-once : conveniente, mas apenas em sistemascom múltiplas CPUs; utilização excessiva do barramento pode ser um fator de queda de desempenho…
82
Elementos de Projeto de uma Cache
Definição do tamanhoFunção de mapeamento de dados Memória/cacheAlgoritmos de substituição de dados nacachePolítica de escrita na cache
83
Próximo passo...
Hierarquia de Memória: MemóriaVirtual, Paginação, Aumento de Desempenho
84
Hierarquia Completa de Memória
Memória
Registradores CPU~100 Bytes1~10 ns
CacheK Bytes10-100 ns
Memória PrincipalM Bytes100ns-1us
DiscoG Bytesms-3 -4
CapacidadeTempo de Acesso
Tapeinfinitosec-min
Cache
Registradores
Tape
Disco
Operandos Inst.
Blocos
Páginas
Arquivos
EstágioUnidade
prog./compil.1-8 bytes
contr. cache8-128 bytes
SO512-4K bytes
user/operadorMbytes
Nível + Alto
Nível + baixoMaior
Fonte: Slides Patterson
+ rápido
85
Requisitos de um Sistema de Memória
Dar a ilusão de um vasto espaço de memóriatotal memória para todos os jobs simultâneos > memória realum job pode usar um espaço de endereços > memória atual
Acesso rápido à memóriaTransparência:
Livrar os programadores da tarefa de otimizar dautilização da memória → cache:memória:disco
Espaço de endereçamento uniforme:Não se pode saber onde os programas serãocarregados nem quais partes dos programas serãomudadas e recarregadas durante a execuçãoIdeal: os endereços situados entre 0 e 2N-1
86
Endereço virtual x endereço físico
O programador usa um espaço de endereçamentovirtual “imenso”, por ex. 231 bytes
Ele pode escrever programas como se todas essasposições de memória existissem realmente!O SO e a arquitetura de memória gerenciam o mapeamento endereço virtual – físicoSe o programa é realmente muito grande, deveexistir uma forma de armazená-lo na memória damáquina – seja em memória ou em disco (“memória de massa”)
A memória real é normalmente menor que o espaçovirtual de endereçamento
o tanto quanto puder ser suportado…endereços físicos ou reais
87
Memória Virtual (2)
Mapeamento endereços virtuais – memória real éfeita em blocos – tipicamente de 1 a 8KBBlocos de memória virtual são chamados páginasPáginas de memória virtual que estão no disco sãochamadas de paginadas-fora (paged-out)Uma referência feita a uma página que não está namemória principal é chamada de falha de página(page fault)A transformação entre endereços virtuais emendereços físicos (memory mapping) é feito atravésde uma tabela de paginação (page table)
88
Mapeamento de endereços virtuais
0x00000x10000x20000x30000x40000x50000x60000x7000
0xD0000xE0000xF000
:::
Prog A VirtualAddresses
:::
Prog B VirtualAddresses
Physical MemoryAddresses
Disk AddressesVirtualAddressSpace
No memory
UnusedMemoryaddressspace
Unused Unused
89
Mapeamento de Memória
O mapeamento Endereço Virtual x Endereço Físicoé também chamado de translação de endereçoNo INTEL 80386: espaço de end. lógico de 4GB ou 230 bytes – páginas de 4KB – endereços de 12 bits. Uma tabela de página poderia ocuparde memória (entradas de 4 bytes) Endereços virtuais são divididos em Número daPágina Virtual (NPV) e offset da página (12 bits nesse caso)Mapeamento de memória feito observando-se o NPV na tabela de páginas e concatenando com o offset da páginaNas arquiteturas atuais, o tamanho das tabelas de página varia (esquema de diretório de tabelas)
90
Processo de Mapeamento
Considere um espaço de endereçamento virtual de 4 GB e um espaço físico em memória de 1 GB
31 30 29 28 .. .. 15 14 13 12 11 10 9 .. .. 3 2 1 0
Número da Página Virtual Deslocamento
Translação
29 28 .. .. 15 14 13 12 11 10 9 .. .. 3 2 1 0
Número da Página Física Deslocamento
4GB
1GB
91
Falhas com Memória Virtual
Custo de uma falha é muito alto: em torno de mspara acessar um bloco de discoAs páginas devem ser grandes o suficiente paraamortizar o alto custo de acesso (4 KB, 8 KB, e mesmo MB …)
Mas não tão grandes para evitar a fragmentação…Tamanho fixado pelo hardware (MMU)
92
Falhas com Memória Virtual
Re-estruturação de programas reduz taxa de falhasProcessar as falhas de página por SW e não por HW
Algoritmos sofisticados podem ser empregadosPequenos aumentos na miss rate podem ser recompensadas pela redução de custos do algoritmo
Evitar a política write-through: Escritas em níveis mais baixos são muitodemoradas
93
Tabelas de Páginas (1)
As páginas deveriam poder ser localizadas emqualquer lugar conveniente na memória
Qualquer página virtual pode ser mapeada emqualquer página física disponívelChamado mapeamento totalmente associativoTabela de páginas faz o mapeamento e reside namemóriaCada programa tem sua própria tabela de páginaO hardware tem um registrador de tabela queaponta para a tabela de página
Os diagramas anteriores se tornam então:
94
Tabelas de Páginas (2)
29 28 .. .. 15 14 13 12 11 10 9 .. .. 3 2 1 0
Número da página física Deslocamento
Endereço Físico
Registrador da tabela de página
12
18Se Zero :Falha depágina
31 30 29 28 .. .. 15 14 13 12 11 10 9 .. .. 3 2 1 0
Número da Página Virtual Deslocamento
Endereço Virtual
Validade Número da página física
Pagetable
20
4GB
1GB
95
Falhas de Página (Page Faults) (1)
Quando o valid bit é zero ele indica que a página nãoestá na memória principalO controle deve ser passado ao SO para buscar a página(ou criar a página, para páginas de dados…)
Tipicamente o SO cria uma imagem do programa no disco quando o programa começaBusca as partes relevantes quando é precisoOnde olhar? – um mapeamento é necessário paramostrar onde estão as imagens no discoPode ser parte da tabela de páginas ou ser feita emseparado
96
Falhas de Página (Page Faults) (2)
Se todas as páginas na memória física estão em uso e o S.O. precisa substituir uma – Qual será escolhida?Política de substituição de páginas
Localidade Temporal é um critério normalMenos recentemente usada (MRU ou LRU)
i.e., sendo os acessos recentes às páginas: 10, 12, 9, 7, 11, 10.MRU numa falha de página trocaria a página 12; napróxima falha, substituiria a página 9, etc.
Tabelas de páginas tem um bit de uso ou referência“Levado a 1” quando a página é acessadaPode ser periodicamente “levado a 0” pelo S.O.Possibilita que o S.O. tenha uma visão aproximada das páginas recentemente utilizadas
97
Falhas de Página (Page Faults) (3)
Para um endereço virtual de 32-bits, páginas de 4KB (12-bits) com 4 bytes por entrada na tabela de página
220 pag x 4 bytes = 4MBIsto para cada programa ativo → muito memória“presa” em tabelas de páginas não usadas
Poderiam ser adicionados registradores de limites e somente mapear as páginas para endereços virtuaisbaixos para limitar o registrador
mas, num modelo normal, o segmento de dados cresce para cima e a pilha para baixonão consistente com a abordagem de limitesUsa 2 tabelas de páginas com 2 registradores de limite – um para a pilha e outro para o resto…
98
Operações de escrita
Write-through para o nível mais baixo da hierarquia (o disco nesse caso) é impraticável nesse caso devido ao alto custo para a escrita no discoA idéia é “salvar as escritas” para depois executá-lasWrite-back quando a página é substituída!Entretanto...
Custoso e desnecessário fazer write-back para páginaspara as quais não forem feitas escritas (por ex., páginas de programa)Assim, as tabelas de páginas têm um bit de sujeira(dirty bit) por entrada que é setado quando dados sãoescritos na páginaSe esse dirty bit é setado quando a página precisa ser substituída, ele é escrito em write-back para a imagemdo programa no disco
99
Fazendo isso rápido…
Tabela de páginas em máquinas modernas está namemória principal:
2 registradores: um de base da tabela namemória e outro indicando o no. de entradas
Portanto ...Cada acesso à memória lógica de um programanecessita de dois outros acessos à memória fíciapara achar a tabela de páginas
Como agilizar isso?Localidade de referências novamente
Inserir numa cache as tabelas de página maisrecentementes utilizadas:
Translation-lookaside buffer = cache inseridadentro da MMU (memory management unit)
100
Translation-Lookaside Buffer (TLB)
Número dapágina virtual
MemóriaFísica
Disco
Validade Página Física ou End. Disco
Validade End. Página FísicaRótulo
TLB
Tabela de Página
101
Translation-Lookaside Buffer
TLB é uma cache Se não existir a entrada na TLB, é preciso buscá-la natabela de páginas que está na memória principalA tabela de páginas tem uma entrada para cada páginaO TLB e a página usam o dirty bit e o reference bitUsar a abordagem write-back para esses bits da TLB para a página de tabelas numa falha é muito eficienteCaracterísticas típicas:
Block size 1-2 page table entries (4-8 bytes each)Hit time 1/2 to 1 clock cycleMiss penalty 10 to 30 clock cyclesMiss rate 0.01% - 1%TLB size 32 to 1024 entriesFonte: Livro P&H p. 492
102
Sistemas Modernos de Memória
Characteristic Intel Pentium Pro PowerPC 604Virtual address 32 bits 52 bitsPhysical address 32 bits 32 bitsPage size 4 KB, 4 MB 4 KB, selectable, and 256 MBTLB organization A TLB for instructions and a TLB for data A TLB for instructions and a TLB for data
Both four-way set associative Both two-way set associativePseudo-LRU replacement LRU replacementInstruction TLB: 32 entries Instruction TLB: 128 entriesData TLB: 64 entries Data TLB: 128 entriesTLB misses handled in hardware TLB misses handled in hardware
Characteristic Intel Pentium Pro PowerPC 604Cache organization Split instruction and data caches Split intruction and data cachesCache size 8 KB each for instructions/data 16 KB each for instructions/dataCache associativity Four-way set associative Four-way set associativeReplacement Approximated LRU replacement LRU replacementBlock size 32 bytes 32 bytesWrite policy Write-back Write-back or write-through
103
Próximo passo...
Interface: dispositivos de entrada e saída (E/S) e barramentos
104
INTERFACE PROCESSADOR – DISPOSITIVOS
105
Os componentes clássicos de um computador
Características extremamente dependentes da tecnologia, assim como os processadores“Um pouco neglicenciados” nos últimos anos...
Processor
Computer
Control
Datapath
Memory Devices
Input
Output
106
Arquitetura Típica
Processadorvia de dados
+ controle
Cache
ControladorE/S
ControladorE/S
ControladorE/S
MemóriaPrincipal
Display(monitor)
Teclado
interrupções
Barramento de Memória – E/S
Rede
ControladorE/S
107
Desempenho em Sistemas de Entrada e Saída
Seja um programa com tempo de execução de 100s, com 90% do tempo em CPU e 10% E/S
Se a CPU aumenta a velocidade 50% por ano, ao fim de 5 anos, o programa passa a ser executado em:90/(1.5)5 + 10 = 22 → 45% do tempo em
E/S !!!Métricas de desempenho complexas:
Supercomputadores: leitura de arquivos imensos e escrita de vários arquivos pequenos → vazãoProcessamento de Informações: tempo de resposta e desempenho em termos de vazãoSistemas de Arquivo: acessos a arquivos pequenos, dados seqüenciais, mais leitura e menos escrita →utilização do espaço e tempo de resposta
108
Arquitetura de Entrada/SaídaCaracterísticas dos dispositivos de E/S (I/O)
Cada dispositivo tem um endereço de portaLimite de dispositivos ~ número de bits da portaAcesso da CPU via bus + interface do dispositivo
Esquemas para a transferência de dadosDispositivos lentos
Programada com espera ocupada (polling ou busy-waiting)Acionada por interrupção
Dispositivos rápidosAcesso direto à memória – DMA (Direct Memory Access)Utilizando canais de dados – Controle de barramentos
109
Tipos de Dispositivos e E/SDispositivo Tipo Parceiro Taxa Ordem
(KB/sec)Teclado entrada humano 0.01 0Mouse entrada humano 0.02 0Alto-falante saída humano 0.60 1Line printer saída humano 1 2Floppy disc armazenagem máquina 50 3Laser printer saída humano 100 4Scanner entrada humano 200 4Optical disc armazenagem máquina 500 4LAN entrada/saída máquina 10K-1G 5Hard disc armazenagem máquina >10K 5Display saída humano 60K 6
A arquitetura de E/S deve acomodar uma variedadeenorme de dispositivos periféricos, com diferençassignificantes de desempenho.
110
Dispositivos de E/S simples
Lentos, geralmente orientados a caracteres (8bits) : teclados, displays, impressoras, etc. Muito mais lentos que o processador... ... Necessidade de protocolo de controle de fluxo de dados, hand-shaking protocolRequerem, pelo menos:
um registrador de dadosum registrador de controle com um bit done (colocado em 1 quando pronto para receber ou enviar o próximo dado, ou 0 em caso contrário).
111
MouseProcessador lê os contadores para determinar a posição e atualizar a telaBotões pressionados geram eventosTudo controlado por softwareInterface E/S por polling (mais adiante...)
+ 20 em Y+ 20 em Y– 20 em X
– 20 em Y– 20 em X
+ 20 em Y+ 20 em X
– 20 em X + 20 em X
– 20 em Y+ 20 em X
– 20 em Y
Posiçãoinicial
112
Discos Magnéticos (hard disks)
Superfície rotativa magnética
1 ou mais pratosRotação a ~ 103 RPM
Divididos em (~1000 a 5000) trilhas concêntricasCada trilha tem tipicamente 64 a 200 setores (entre 512-4096 bits)
Setores
Trilhas
Superfícies
113
Discos MagnéticosO setor, às vezes chamado bloco, é a unidade fundamental de transferência (não se pode transferir menos que ela)Discos mais recentes utilizados em PC’s só tem 1 prato devido aos ganhos tecnológicos na confecção dos discosEm geral, fabricantes informam tempo de busca máximo, mínimo e médio de acesso aos dadosDiscos flexíveis utilizam tecnologia da década de 80: menor velocidade, confiabilidade e capacidadeDiscos ópticos tornam-se parte integrante nos anos 90...
114
Desempenho de discos
Os braços movem-se entre os pratos rotativos, lendo ou escrevendo informaçõesTempo de busca (seek time)
Tempo para o braço localizar a trilha corretaLatência rotacional
Tempo para encontrar o setor corretoTempo de transferência
Tempo para transferir o bloco de informaçõesCabeças
Muitos discos têm uma cabeça por superfície – alta densidade de dadosAlguns discos mais antigos têm múltiplas cabeças por superfície – baixa latência de acesso e alto desempenho.
115
E/S com Disco
Registradores de dispositivo:Endereço no discoNúmero de bytes a ser transferido, que pode ser <, = ou > um setor. Endereço de memória para a transferênciaRegistrador de comando:
tipo de comando: read - disco para memória; write; write&verify (ler depois de escrever), etc.habilita interrupção go - quando ligado promove a transferência para o início, utilizando os valores correntes nos registradores de endereço e de comprimento.
Registrador de statusIndicadores de erros - unreadable/unwritablesector, etc.Livre/ocupado (idle/busy)
116
Conexão dos Dispositivos de E/S ao Processador e àMemória
Conexão via barramento: Nada mais é que um conjunto de ligações (fios) que forma um canal de comunicação compartilhado entre os vários subsistemas (processador, memória, entrada/saída)Limitação: gargalo para a comunicaçãoDesempenho limitado fisicamente pelo número de dispositivos conectados, comprimentoInclui uma via de controle (solicitações) e uma via de dados (informações):
A via de controle inclui envolve linhas para requisição do barramento e para garantir o seu controleA via de dados tipicamente tem de 8 a 64 bits de largura, i.e. 8 a 64 ligações separadas
117
Interconexão de componentes (1)
Diretamente com o processadorNenhuma máquina moderna aplicam esta solução, em geralNem flexível, nem extensívelBarramento plano (backplane)Barramento “curto” e de propósito geral – conecta memória, periféricos e o processadorDeve seguir um padrão – ex. VME, PCI, etc.
Barramento E/Slongo, interligando diferentes tipos de dispositivosDeve seguir um padrão comercial: SCSI, IPI, etc.
Barramento processador-memóriaBarramento “curto” de altíssima velocidade, especializado para otimizar as comunicações memória-processadorGeralmente proprietário – específico para a máquina ou vendedor na busca de melhoria de desempenho
118
Interconexão de componentes (2)
Local Area Network (LAN)Pode ser usada para compartilhar periféricos, como impressoras, sistemas de arquivos, etc.Distâncias muito maioresGeralmente taxas de dados “moderadas/altas” entre 100Kbits/sec e 155 Mbits/sec
Projetos de alto desempenho envolvem múltiplos barramentos para produzir caminhos ótimos para os dados.Geração futura deve usar “switches” especializados –derivados da tecnologia LAN
119
Barramentos Síncronos e Assíncronos
Síncrono: inclui um clock em suas linhas de controleRequer que cada dispositivo do barramento “rode”a uma mesma velocidade.Barramentos Processador-memória : sincronização na leitura e escrita; poucos dispositivos, próximos e muito rápidos
Assíncrono: não “segue” um clockPode ligar vários dispositivos de características diferentes, sem preocupação com o sincronismoTipicamente para entrada/saídaControlado por um mecanismo de handshaking(vários passos, mas o receptor e transmissor sóseguem em frente se ambas as partes envolvidas estão de acordo)
120
Arbitragem do barramento (1)
Como isso se comporta na prática?O que acontece quando vários dispositivos querem ter acesso ao barramento?
8-64
Controladorde
Barramentoou
Árbitro 16-?
4-8
Comando
Dados
Endereço
Processador Memória HardDisk
FloppyDisk
Bus requestBus grant
Daisy chain
121
Arbitragem do barramento (2)Quando um dispositivo (incluindo a CPU) necessita do barramento, ele envia (ou “seta”) uma requisição na requestline
Existe uma linha única de requisições funcionando em “wired-OR “Só distingue se existe ou não requisição
O árbitro atende uma requisição quando o barramento torna-se disponível “setando” a linha grant lineO primeiro dispositivo que “vai para nível 0” pode usar o barramento
Árbitro do
Barramento
Dispositivo 1
Dispositivo 2
Dispositivo 3
Dispositivo 4
Bus Request
Bus Grant
A permissão pode ou não se propagar
pela cadeia
122
Arbitragem do barramento (3)
Dispositivo que “ganha” o barramento:Torna-se o mestre do barramentoEle não propaga o sinal de “grant” para os outros dispositivos desligados (em nível baixo)Portanto, um mecanismo de prioridade é construído – os dispositivos mais próximos do árbitro têm maior prioridadeGarantir que outros dispositivos tenham acesso ao barramentoAssim limitar “a janela de tempo” para assegurar que restrições temporais críticas não sejam ultrapassadas nos dispositivosO mestre colocar comandos, endereços e dados no barramento para serem tratados pela memória ou por um outro dispositivoSe a transferência não recebe um acknowledgment, uma exceção de erro de endereço de barramento é gerada
123
Arbitragem do barramento (4)
Árbitro do
Barramento
Dispositivo 1
Dispositivo 2
Dispositivo 3
Dispositivo 4
Grant nível 1Grant nível 2
Req. nível 1Req. nível 2
Esquema com nível de prioridades no barramento:nível 2 > nível 1Conflito: 3 > 4 > 1 > 2
124
Padrões para barramentos (1)Barramento E/S permite a expansão da máquina: padronização é fundamental!
SCSI (Small Computer Systems Interface) e Ethernet são exemplos de padrões criados por reunião de fabricantesPCI criado pela INTEL e depois adotado por outras
PCI : barramento para backplane de propósito geralSCSI: barramento de entrada e saída
Faz a interface entre o barramento do backplane e o barramento processador-memória
125
Padrões para Barramentos (2)
Característica PCI SCSItipo backplane E/Slargura de dados 32 a 64 bits 8 a 32 bitsmestre do bus múltiplos múltiplosArbitragem centralizada, com distribuída, com
requisição em paralelo acesso por seleçãoclock Síncrono 33 a 66Mhz Ambos (5 a 10Mhz)Banda passante 80 MB/s 5 or 40 MB/sNo.max dispositivos 1024 7 a 31comprimento max 0.5m 25mNome padrão PCI ANSI
Source: P&H p. 395
Em evolução constante... Dados tabelados em 1997!
126
Interface dos Dispositivos E/S com a Memória, Processador e SO
Um protocolo de barramento define exatamente o que deve ser feito em uma transmissão de dados entre subsistemasO SO é responsável pela gerência de toda a E/S:
Proteção de acesso aos dispositivosDefine abstrações para acesso aos dispositivosTrata as interrupções geradas pelo processador e dipositivosGarante o acesso compartilhado aos dispositivos
O SO efetua 3 tipos de comunicação:1. Envio de comandos aos dispositivos2. Comunicação do dispositivo indicando fim da tarefa3. Transferência dos dados entre memória e dispositivos
127
Envio de Comandos aos dispositivos
Dois métodos de endereçamento: Mapeamento de E/S em memóriaComandos especiais de E/S
Mapeamento em memória:Parte do espaço de endereçamento é reservada aos dispositivos (e protegido dos programas usuário)Leituras/escritas a esses endereços são interpretadas pelo SO como operações de E/SVantagem: simplicidade e transparência
Comandos especiais de E/S:Instruções incluídas no processadorVerifica o estado do dispositivo para saber se o comando foi completado ou não (só em modo kernel)
128
Exemplo: Teclado e monitoresTeclados produzem caracteres à medida em que são digitados, em geral à taxa média de 10 cpsMonitores são capazes de exibir textos alfanuméricos àtaxa aproximada de 1200 cps
7 6 45 3 2 1 07 6 45 3 2 1 0
Ready/Done
Keyboard RegistersControle Data
7 6 45 3 2 1 07 6 45 3 2 1 0
Ready/Done
Display RegistersControl Data
Read-only
Write-onlyUnused (for now)
129
Exemplo - Estrutura de um programa “echo”
Assuma que os registradores de E/S são mapeados em memória a partir das posições 0xffff 0000:
+0 Keyboard control+4 Keyboard data+8 Display control+12 Display data
No modo full-duplex os caracteres inseridos através do teclado não são exibidos a menos que haja um programa que instrua a arquitetura para tal, por ex:1. aguarde o sinal ready do teclado ser ligado2. leia o caractere - automaticamente zera (desliga) ready3. envie o caractere ao display4. aguarde a exibição ( Não necessariamente verdade, já
que o display geralmente é muito mais rápido que a digitação )
5. volte ao começo
130
Exemplo - o código...
Programa simples em assemblyusando E/S polled
.textmain: li $8, 0xffff0000
mloop: lw $7, 0($8) # get control registerandi $7, $7, 1 # mask out done bitblez $7, mloop # loop waiting for data
lw $6, 4($8) # get data/clear kbd done
lp2: lw $7, 8($8) # wait for display readyandi $7, $7, 1 # mask out done bitblez $7, lp2 # loop waiting
sw $6, 12($8) # display character
b mloop # next char
131
Analisando o desempenho do Polling
A espera “ocupada” do bit done é chamada pollingDesperdício de tempo de processamento, já que os dispositivos são (em geral) muito mais lentos do que o processadorPor outro lado, no caso de disco magnético o processador pode não dar conta de atender a alta taxa de transferência de dados.Necessidade de outras técnicas é clara: mecanismo de entrada/saída dirigida por interrupção
132
Mecanismo de Interrupção
Mecanismo que desvia o processador de suas atividades normais quando algum dispositivo precisa ser atendido: 1. A CPU emite uma instrução de E/S e não espera resposta
imediata, desviando-se para realizar outra atividade, suspendendo a execução do programa de E/S
2. O processador verifica, no início ou fim do ciclo de execução de cada instrução, se ocorreu alguma interrupção.
3. Em caso positivo (i.e., a interface está para transferir o dado), o controle é transferido para uma rotina de tratamento de interrupção - Interrupt Service Routine ou Interruption Handler
4. O dado é então transferido5. A CPU retoma ao programa original no ponto em que
aconteceu a interrupção.
133
Interrupções
Internas: Devido a eventos gerados durante a execução de um programa pelas instruções (overflow por divisão por zero, underflow) ou por programação (alarmes)
Externas:Devido a sinais externos à CPU: interface de dispositivos de E/S que “avisam” à CPU que existem dados a serem transferidos
Algumas podem ser desabilitadas:No nível do dispositivo - afeta apenas um dispositivoNo nível do sistema - afeta todos os dispositivos
Para lidar com a imensa gama de dispositivos de E/S, os mecanismos de interrupção têm níveis de prioridade definidos
134
Como sincronizar as interrupções?
Através de fila ou bufferEstrutura tipo first-in, first-outUma fila para entrada, outra para saída. Se a fila estiver vazia → nenhum trabalho a ser feito. Se a fila de entrada estiver vazia e o programa do usuário necessita uma entrada, então o Sistema Operacional (SO) suspende o programa assume algum outro que possa dar prosseguimento. De maneira similar, se a fila de saída estiver cheia, o SO precisa re-escalonar os processos até que a rotina de interrupção tenha gerado algum dado.
135
Filas de I/O
entrada Q
out: add to Qif full OS suspends
saída Q
in: get from Qif empty OS suspends
Programa do usuário
main: do workcall indo workcall out
Kbd data
Display data
Rotina de interrupção
Código de Inicializaçãopara habilitar interrupções
Kbd: get dataput in Qif full beepresume
Disp: get data from Qif none disableinterruptsend to displayresume
136
Múltiplos Dispositivos
Quando ocorre uma interrupção pode-se sair varrendo um a um para determinar quem interrompeu: test chain
Processo lento, utilizado em máquinas antigas. Certos dispositivos têm tempos críticos de resposta: se o dado não for tratado a tempo ele será perdido ou outro prejuízo na aplicação pode acontecer. Diversas soluções:
Interrupção vetorizada - cada dispositivo tem associado um endereço exclusivo na memória onde um ponteiro para sua ISR pode estar armazenado. Interrupção com vetorização parcial - dispositivos são divididos em classes com faixa de tempo crítico similares, vetorizados todos para o mesmo endereço. O test chain érealizado para o refinamento da identificação. Interrupção não-vetorizada - test chain e outros truques...
137
Vetores de Interrupção
.ktext 0x80000000
.word Lkbd # vector for kbd
.word Ldisp # vector for display
.ktext 0x80000020
.word Lhd # hard disk vector
.ktext 0x80000040
.word Lscan # scanner vector
.ktextLkbd: ... # ISR for kbd
resumeLdisp: ... # ISR for display
resumeLhd: ... # ISR for disk
resumeLscan: ... # ISR for scanner
resume
138
Vetorização Parcial.ktext 0x80000000.word slow # vector for slow devices.ktext 0x80000020.word med # vector for med speed devices.ktext 0x80000040.word fast # vector for fast devices.ktext
slow: test kbd # ISR for slow devstest disptest clocktest mouseresume
kbd: ... # ISR for kbdresume
disp: # etc.# - - - - - - - -med: ... # ISR for med speed devs
resume# - - - - - - - -fast: ... # ISR for fast devs
resume
Not MIPS code!
139
Do ponto de vista da CPU
A CPU é interrompida: Qual tipo de interrupção? Qual o dispositivo sinalizou? Reagir imediatamente, mais tarde, ignorar? O que fazer com o programa interrompido? Quando retornar à sua execução?
Rotina de Tratamento da InterrupçãoAntes de ir para a rotina a CPU “salva o contexto” do processo em execuçãoA CPU recebe o endereço inicial da rotina de tratamento da interrupção e inicia sua execução
Embora melhore o desempenho, a CPU ainda “perde tempo”com a execução da rotina de interrupção e controle da transferência: imagine a transferência de 100KB do disco para a memória
140
Transferência entre Dispositivo e Memória
Polling e Interrupções funcionam bem para transfe-rências entre dispositivos de banda passante baixaAs interrupções retiram do processador ô “ônus” de ter que esperar cada evento de E/S, mas ainda assim, a transferência do disco para memória não necessitam do controle direto da CPUA solução encontrado foi criar um mecanismo de transferência denominado DMA (directmemory access) ou acesso direto à memória
141
Acesso Direto a Memória (DMA)
Dados são transferidos entre a memória e o disco diretamente, sem o envolvimento do processador.
Interrupção ainda utilizada para dizer à CPU quando a transferência é iniciada e terminada.
Transferências DMA:CPU informa ao controlador de disco a operação a ser realizada e os endereços envolvidos. O controlador do dispositivo realiza então a operação, através de DMA, deixando livre a CPUControlador de barramento faz a arbitragem do barramento.O controlador do dispositivo informa à CPU o término da transferência usando uma interrupção ou no caso de erro
142
Análise do DMA (1)
Um barramento é um caminho compartilhado de alta velocidade. Considere a execução normal de um programa que requisita acessos à memória ao processador:
Inst R Data R Data WInst RInst R Inst RInst R
Atividade no Bus (P/M)
Tempo
Processador trabalhando
Processador
Memória Disco
Tela Teclado
Bus
143
Análise do DMA (2)
Agora, com o disco envolvido na transferência DMA
Inst R Data R Data WInst R Inst R
Atividade no Bus (P/M/D)
Tempo
Inst R Inst RInst R Inst R
Disk R/W Disk R/W
Disk R/W Data W Disk R/W
Processador
Memória Disco
Tela Teclado
Bus
144
Análise do DMA (3)
Bus é compartilhado por transferências processador-memória e disco-memóriaAssim, o desempenho do processador pode sofrer uma redução. Arquiteturas multi-barramentos são usadas para reduzir este efeitoÉ preciso que algo seja usado para organizar o compartilhamento do barramento: árbitro ou controlador de barramentoA conexão ao barramento e a tomada de decisões gasta tempo. Em alguns protocolos de barramentos SO, somente rajadas (burst) limitadas de dados podem ser transmitidas: burst-mode
145
Próximo passo...
Arquiteturas Avançadas: multicomputadorese multiprocessadores
146
Sistemas Multiprocessadores (I)
Mais que uma CPU
Em geral confinadas a um mesmo espaço físico (gabinete, rack, ...)
Fortemente acoplados
Comunicação via memória compartilhada
147
Sistemas Multiprocessadores (II)
CPU
Mem
Bus
CPU
cache
148
Sistemas Multiprocessadores (III)
Switch
(Ômega)
CPU
Mem
149
Sistemas Multiprocessadores (IV)
Crossbar
CPU
Mem
150
Sistemas Multicomputadores (I)
Mais que uma CPU
Máquinas podem estar geograficamente distantes
Sistemas fracamente acoplados
Cada processador possui sua memória local própria e a comunicação é feita por passagem de mensagens
151
Sistemas Multicomputadores (II)
CPU
Mem local
Rede
152
Sistemas Multicomputadores (III)
MALHA TRIDIMENSIONAL (k=3, n=3)
CPU
Mem local
153
Desafios
Balanceamento de carga entre processadoresAdequação aplicação x arquiteturaCoerência de memória (cache)Linguagem de programação e compiladoresLimitações físicas: temperatura, comprimento das ligações, custo
![Artur loureiro[1]](https://img.document.onl/doc/110x75/5497831bb4795903288b45ff/artur-loureiro1.jpg)
