Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Arquitetura e Organização de Computadores
Professor: Mário Luiz Rodrigues Oliveira/Otávio de Souza
Martins Gomes
Atividade: 3ª Lista de Exercícios
Formiga, MG, 2 de abril de 2014
INSTRUÇÕES:
1. Esta lista de exercícios poderá ser resolvida em grupo com no máximo 3 integrantes.
2. Caso você ache que falta algum detalhe nas especificações, você deverá fazer as suposições que
julgar necessárias e escrevê-las com as suas respostas. Pode acontecer também de algum
enunciado conter dados e/ou especificações supérfluas para a solução de alguma pergunta
específica. Utilize sua capacidade de julgamento para separar o supérfluo do necessário.
3. Entregue apenas uma resolução por grupo.
4. A data final para entrega desta lista de exercícios é o dia 09/04/2014, no início da aula.
5. Listas plagiadas serão desconsideradas, sendo atribuída nota 0 (zero) a todos os envolvidos.
EXERCÍCIOS
1) Sobre pipeline responda:
a) Qual o principal problema encontrado na implementação da técnica de pipeline em processadores? Cite e
explique 4 estratégias usadas para solucioná-lo.
b) Certa manhã, a abelha rainha de uma colmeia reuniu as abelhas operárias e informou-lhes que o trabalho
seria coletar o néctar de margaridas. Encerrada a reunião, as abelhas operárias voaram em várias direções em
busca de margaridas. Esse sistema de trabalho das abelhas é análogo à técnica de pipeline? Justifique sua
resposta.
2) [STA-Adaptado] Considere um sistema hipotético de memória virtual no qual os endereços lógicos têm
36 bits e são mapeados numa memória física de 2Gbytes. Considere, também, que o tamanho de cada página
virtual é 16 Kbytes. Pergunta-se:
a) Quantas entradas têm a tabela de páginas? Justifique sua resposta.
b) Qual o tamanho, em Mbytes, ocupado pela tabela de páginas? Considere que cada entrada da tabela de
página armazena 8 bytes. Justifique sua resposta.
c) Quantas molduras de página existem nesse sistema de memória virtual?
d) Qual seria o efeito sobre a tabela de páginas, se o espaço físico de memória fosse reduzido pela metade?
Considere que os demais parâmetros não se alteram. Justifique sua resposta.
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Arquitetura e Organização de Computadores
Professor: Mário Luiz Rodrigues Oliveira/Otávio de Souza
Martins Gomes
Atividade: 3ª Lista de Exercícios
Formiga, MG, 2 de abril de 2014
e) Qual seria o efeito sobre a tabela de páginas, se o tamanho de cada página virtual fosse alterada para 4
Kbytes? Considere que os demais parâmetros não se alteram. Justifique sua resposta.
f) Qual seria o efeito sobre a tabela de páginas, se o tamanho dos endereços lógicos fossem 32 bits?
Considere que os demais parâmetros não se alteram. Justifique sua resposta.
3) Considere um sistema de memória paginado e responda:
a) Em um sistema de memória virtual paginado, por quê é geralmente mais desejável substituir uma página
que não foi alterada do que uma que foi alterada desde que ela foi trazida para a memória pela última vez
(página suja)?
b) Cite uma situação na qual seria mais desejável substituir uma página que foi modificada?
c) Explique e discuta as três faixas de comportamento observadas na situação descrita abaixo:
Um programa é executado sozinho, várias vezes, em uma máquina com
memória paginada muito maior que o número de páginas do programa. A
cada
execução,
controla-se
o
número
de
molduras
de
página
da
memória que o programa pode usar. Ele é executado pela primeira vez
com apenas duas molduras, depois com três, etc., até o tamanho da
memória. A cada vez, o tempo de execução é medido. Observa-se que
até quatro quadros, o tempo de execução diminui drasticamente a
cada vez; de quatro a seis quadros, o tempo de execução ainda
diminui, mas menos acentuadamente; com sete ou mais quadros esse
tempo permanece essencialmente constante.
4) [STA] Considere o seguinte código:
for (i=0; i<20; i++)
for (j=0; j<10: j++)
a[i]=a[i] * j;
a) Dê um exemplo de localidade espacial no código. Justifique sua resposta.
b) Dê um exemplo de localidade temporal no código. Justifique sua resposta.
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Arquitetura e Organização de Computadores
Professor: Mário Luiz Rodrigues Oliveira/Otávio de Souza
Martins Gomes
Atividade: 3ª Lista de Exercícios
Formiga, MG, 2 de abril de 2014
5) [STA-Adaptado] Um processador tem um espaço de endereçamento virtual com 32 páginas de 16Kybtes
cada e uma memória física com apenas 4 molduras de página. De início, a memória principal está totalmente
vazia. Um programa referencia páginas virtuais na seguinte ordem: 0,2,4,5,2,4,3,11,2,10 e 4.
a) Quais dessas referências causam falta de página se considerarmos o algoritmo LRU para substituição de
páginas? Justifique sua resposta.
b) Quais dessas referências causam falta de página se considerarmos o algoritmo FIFO para substituição de
páginas? Justifique sua resposta.
c) Por que o tamanho de página num sistema de memória virtual não deve ser muito pequeno nem muito
grande?
6) Suponha uma implementação de um processador sem hardware para ponto flutuante, ou seja, todas as
operações de ponto flutuante devem ser emuladas (simuladas com instruções envolvendo apenas números
inteiros) em software. Suponha também que a frequência deste processador é 4Ghz e considere a
necessidade de emular um programa que contém única e exclusivamente 40 milhões de instruções com
precisão de ponto flutuante. O processo de emulação produz um novo programa com o seguinte mix de
instruções envolvendo apenas números inteiros.
Tipo de Instrução
BRANCHES/JUMPS
ALU
STORE
LOAD
CPI
2
3
4
5
Frequência
15%
50%
10%
25%
Se o tempo para executar o novo programa (contendo apenas instruções envolvendo números inteiros) é de
1.38 segundos; quantas instruções envolvendo números inteiros são necessárias, na média, para emular uma
instrução em ponto flutuante? Justifique sua resposta.
7) [STA-Adaptado] Um computador possui uma memória cache, uma memória principal e um disco usado
para memória virtual. Se uma palavra referenciada está na memória cache, o tempo de acesso é 1ns
(nanossegundo). Se está na memória principal, mas não na cache, o tempo de acesso é 40ns
(nanossegundos). Se não está na memória principal, o tempo de acesso é 8ms (milissegundos). A taxa de
acerto na cache é de 90% e na memória principal é de 60%. Qual o tempo médio de acesso, em
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Arquitetura e Organização de Computadores
Professor: Mário Luiz Rodrigues Oliveira/Otávio de Souza
Martins Gomes
Atividade: 3ª Lista de Exercícios
Formiga, MG, 2 de abril de 2014
nanossegundos, necessários para acessar uma palavra referenciada nesse sistema? Justifique sua resposta,
mostrando os cálculos e o raciocínio utilizado para encontrar o tempo médio de acesso.
8) Um disco magnético possui 16 pratos com 2 faces cada, 1 cabeça de leitura/escrita por face e 8192 trilhas
em cada face. Cada trilha tem 1024 setores e cada setor possui 512 bytes. O disco possui uma velocidade de
rotação de 15.000 RPM (rotações por minuto) e leva 1ms (milissegundo) para mover-se entre trilhas
adjacentes. O tempo de seek informado pelo fabricante é 10ms (milissegundos). Despreze o overhead da
controladora e do sistema operacional.
a) Qual o tamanho do disco em Gbytes?
b) Quantos bits são necessários para endereçar diretamente cada setor desse disco?
c) Qual a taxa de transferência do disco ao longo de uma trilha?
d) Qual é o maior tempo, em milissegundos, gasto para ler um setor arbitrário nesse disco?
e) Qual o tempo médio, em milissegundos, gasto para ler um setor arbitrário nesse disco? Considere o tempo
de seek médio igual a 40% do tempo informado pelo fabricante e a latência rotacional média igual a 50% do
tempo de rotação.
9) Considere um sistema hipotético de memória virtual no qual os endereços lógicos têm 40 bits e os
endereços físicos têm 36 bits. Considere, também, que o tamanho de cada página virtual é 4 Kbytes.
Pergunta-se:
a) Quantas entradas têm a tabela de páginas? Justifique sua resposta.
b) Qual o tamanho, em Kbytes, ocupado pela tabela de páginas? Suponha que cada entrada da tabela de
páginas possua 5 campos, a saber: 1bit para indicar se a página é somente para leitura ou para leitura/escrita,
1bit indicando se a página está na memória ou em disco (bit de presença), um bit para indicar se a página foi
alterada (está suja), um bit para indicar se a página foi acessada (bit de uso) e o número da moldura de
página onde encontra-se a página. Justifique sua resposta.
c) Quantos bits existem no campo deslocamento do endereço lógico? Justifique sua resposta.
10) Qual é o speedup que pode ser esperado se o conjunto de instruções de uma máquina for modificado
para que a instrução de desvio (branch) gaste um ciclo de clock e não três? Suponha que instruções de
desvio representam 20% do total de instruções e que o CPI médio das demais instruções é igual a 3.
Considere que não houve alterações nos demais parâmetros necessários para a análise do speedup.
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Arquitetura e Organização de Computadores
Professor: Mário Luiz Rodrigues Oliveira/Otávio de Souza
Martins Gomes
Atividade: 3ª Lista de Exercícios
Formiga, MG, 2 de abril de 2014
11) [PAR-Adaptado] Num processador o pipeline é implementado com 20 estágios e quatro bolhas (stalls)
devem ser inseridas para instruções de desvio (branch), as quais representam 20% do total de instruções
executadas. Cerca de 5% de todas as instruções geram falhas quando tentam acessar a memória cache,
fazendo o pipeline parar por 80 ciclos. Qual o CPI efetivo para esse pipeline?
12) [PAR-Adaptado] Para um sistema de memória cache, um colega sugere que a substituição da linha mais
recentemente utilizada (MRU) pode ser uma alternativa viável. Você tenta convencê-lo que essa é a pior
ideia possível e faz ponderações sobre o princípio da localidade exibido por programas típicos. Seu amigo
insiste na ideia afirmando que em alguns casos o MRU pode ter desempenho superior ao algoritmo que
substitui a linha menos recentemente utilizada (LRU). A afirmação de seu colega possui algum mérito?
13) Segundo Stallings [STA], o uso de uma memória cache unificada (única memória para armazenar
referências a dados e instruções) apresenta vantagens, tais como: apenas uma memória cache precisa ser
projetada e geralmente a taxa de acerto da memória cache unificada é melhor que a taxa de acerto de um
projeto com memórias caches separadas (uma cache de dados e outra cache para instruções). Essa
arquitetura com memórias cache separadas é referenciada na literatura como arquitetura de Harvard.
Considere tais informações e os seus conhecimentos sobre o projeto de memória cache e responda:
a) Cite e discuta uma razão para as memórias cache unificadas apresentarem, geralmente, uma taxa de acerto
melhor que a configuração da arquitetura de Harvard.
b) Apesar das vantagens citadas, a tendência atual é utilizar memórias caches separadas para instruções e
dados (arquitetura de Harvard). Justifique a preferência atual pela arquitetura de Harvard.
c) Como o projeto de memória cache tira proveito da localidade espacial? E da temporal?
14) Segundo Tanenbaum [TAN], o acesso à memória é um enorme gargalo em todos os computadores
modernos porque o tempo de ciclo da CPU é muito superior ao tempo de acesso à memória. A Figura1
mostra a performance da memória e da CPU no período 1980-2010. Dessa forma, uma das maneiras de
melhorar o desempenho de computadores atuais é evitar acessar à memória principal. O tempo de acesso à
memória principal é alto e degrada o desempenho do sistema computacional. A estratégia de usar memória
cache tenta suprir essa lacuna existente no desempenho relativo CPU/Memória e assim o uso de memória
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Arquitetura e Organização de Computadores
Professor: Mário Luiz Rodrigues Oliveira/Otávio de Souza
Martins Gomes
Atividade: 3ª Lista de Exercícios
Formiga, MG, 2 de abril de 2014
cache tornou-se um dos principais temas a ser analisado no projeto de um sistema computacional.
Considerando tais informações e seus conhecimentos a respeito do projeto de memória cache, responda:
a) apresente uma discussão mostrando os trade-offs envolvidos nos seguintes aspectos relacionados ao
projeto de memória cache: tamanho da cache, tamanho da linha e associatividade. Sugestão: faça uma tabela
mostrando como esses aspectos impactam no tempo de acesso, na penalidade por falta e na taxa de acerto.
Escreva um parágrafo explicando a tabela.
b) As CPU's modernas apresentam pelo menos dois níveis de cache. Numa CPU com dois níveis de cache
há a cache L1 (nível 1) e a cache L2 (nível 2). O tamanho da cache L2 é maior que o tamanho da cache L1.
Apresente duas justificativa para a cache L2 ser maior que a cache L1.
Figura 1 - Desempenho CPU x Memória - Fonte [HEN]
15) [PAT-Adaptado] Uma das estratégias para resolver conflitos de dados num pipeline é o adiantamento
(forwarding). Analise os códigos 1 e 2 abaixo, suponha uma implementação de pipeline semelhante ao
implementado na arquitetura MIPS e responda:
a) O conflito de dados do código1 pode ser resolvido usando forwarding? Justifique sua resposta.
b) Explique como a situação de conflito de dados do código2 difere da situação apresentada no código1 e dê
uma alternativa de solução para o conflito de dados exibido no código2.
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Arquitetura e Organização de Computadores
Professor: Mário Luiz Rodrigues Oliveira/Otávio de Souza
Martins Gomes
Atividade: 3ª Lista de Exercícios
Formiga, MG, 2 de abril de 2014
Código1
ADD R2, R5, R4
ADD R4. R2, R5
Código2
LOAD R5, 1000(R3)
STORE R8, 1000(R3)
16) Historicamente, quando os tempos de ciclo das memórias eram muito longos e os preços de memória
muito altos, sistemas computacionais com arquitetura CISC tinham uma vantagem sobre sistemas com
arquiteturas RISC. Contudo, quando a memória tornou-se barata o suficiente e hierarquias de memória
tornaram-se rápidas e grandes o suficiente, essa vantagem passou a ser questionada. Você concorda que essa
afirmativa? Justifique sua resposta.
17) Num processador o ciclo de execução de instruções é dividido em 5 etapas, a saber: busca de instruções,
decodificação, execução, acesso à memória e escrita nos registradores. Cada uma dessas etapas gasta 2ns
(nanossegundos). Existem duas implementações desse processador: uma sem pipeline e outra usando a
técnica de pipeline. O pipeline implementado possui 5 estágios. Indaga-se:
a) Qual o tempo para executar cada instrução no processador com pipeline? Considere ausência total de
conflitos.
b) Qual o tempo para executar cada instrução no processador sem pipeline?
c) Qual a CPI média no processador sem pipeline?
d) Qual a CPI média no processador com pipeline? Considere ausência total de conflitos.
DICA: Ao resolver essa lista de exercícios você aperfeiçoará seus conhecimentos sobre os mais importantes
temas do projeto moderno de computadores: memória cache e pipeline. Adicionalmente, a resolução de
exercícios é uma boa prática de estudo e de preparo para as avaliações.
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Arquitetura e Organização de Computadores
Professor: Mário Luiz Rodrigues Oliveira/Otávio de Souza
Martins Gomes
Atividade: 3ª Lista de Exercícios
Formiga, MG, 2 de abril de 2014
MATÉRIA DA 3ª AVALIAÇÃO:
Análise de desempenho, memória cache, memória virtual, memória de massa e hierarquias de
memória: estudar capítulos 4, 6 e 7 do livro PATTERSON, David A. e HENNESSY, John L.
Organização e Projeto de Computadores: a interface hardware/software. 3ª edição. São Paulo:
Campus, 2008.
Linguagem Assembly: estudar transparências disponibilizadas pelo prof. Otávio
INFORMAÇÕES QUE PODEM SER ÚTEIS
Etapas do pipeline na arquitetura MIPS:
Ciclo IF (instruction fetch)
Busca na memória a instrução contida em PC e atribui a IR;
Atribui a PC o valor de PC + 4 (pois cada instrução ocupa 4 bytes e o endereçamento é byte a byte);
Ciclo ID (instruction decoder / register fetch)
Decodifica a instrução em IR;
Lê banco de registradores;
Ciclo EX (execution / effective address)
Neste ciclo o MIPS executa uma das funções dependendo do tipo de instrução:
Referencia à memória: calcula o endereço efetivo do acesso à memória;
Instrução ALU registrador-registrador: realiza a operação especificada;
Branch: determina o endereço da próxima instrução a ser executada;
Ciclo MEM (memory access)
Neste ciclo são realizados os acessos à memória.
Ciclo WB (write-back)
Escrita no banco de registradores.
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Arquitetura e Organização de Computadores
Professor: Mário Luiz Rodrigues Oliveira/Otávio de Souza
Martins Gomes
Atividade: 3ª Lista de Exercícios
Formiga, MG, 2 de abril de 2014
Fórmulas:
Tempo de CPU:
CPU time = IC * CPI * TempodeCiclo
Tempo de CPU pipelined:
CPU time pipelined = IC * (CPI ideal + CPI stalls) * TempodeCiclo
Tempo de CPU com falhas no acesso a cache:
CPU time cache = IC * (CPI sem falhas + CPI stalls memoria) * TempodeCiclo
CPI stalls memoria = (QteAcessosMemoria * TaxaFalta *PenalidadeporFalta) / IC
Speedup:
speedup = CPU time / CPU time pipelined
Tempo médio de acesso à memória:
Tempo = h * T1 + (1 – h) * (T1 + T2), aplicando uma pequena manipulação algébrica chega-se à seguinte
fórmula equivalente:
Tempo = T1 + (1 – h) * T2, onde T1 representa o tempo de acesso ao nível 1 da hierarquia de memória, T2
representa o tempo de acesso ao nível 2 da hierarquia de memória e h representa a taxa de acerto (hit) ao
acesso o nível 1 da hierarquia de memória.
Essa fórmula pode ser replicada para n níveis. Por exemplo, para 3 níveis de memória, tem-se: Tempo = h1
* T1 + (1 – h1) * (T1 + T2) + (1 – h1) * (1 – h2) * ( T1 + T2 + T3), onde T1 representa o tempo de acesso
ao nível 1 da hierarquia de memória, T2 representa o tempo de acesso ao nível 2 da hierarquia de memória,
T3 representa o tempo de acesso ao nível 3 da hierarquia de memória, h1 representa a taxa de acerto (hit) ao
acesso o nível 1 da hierarquia de memória e h2 representa a taxa de acerto (hit) ao acesso o nível 2 da
hierarquia de memória.
Tempo de acesso e transferência do disco:
Tempo disco = Tempo de seek + Latencia Rotacional + Tempo de transferência + overhead da controladora
+ overhead do sistema operacional
Instituto Federal de Educação, Ciência e Tecnologia
Curso: Bacharelado em Ciência da Computação
Disciplina: Arquitetura e Organização de Computadores
Professor: Mário Luiz Rodrigues Oliveira/Otávio de Souza
Martins Gomes
Atividade: 3ª Lista de Exercícios
Formiga, MG, 2 de abril de 2014
Referências:
[PAT] PATTERSON, David A. e HENNESSY, John L. Organização e Projeto de Computadores: a interface
hardware/software. 3ª edição. São Paulo: Campus, 2008.
[HEN] HENNESSY, John L. e PATTERSON, David A. Arquitetura de Computadores: uma abordagem
quantitativa. 5ª edição. São Paulo: Campus, 2014.
[PAR] PARHAMI, Behrooz. Arquitetura de Computadores: de microprocessadores a supercomputadores. 1ª
edição. McGraw-Hill, 2008.
[STA] STALLINGS, William. Arquitetura e Organização de Computadores. 8ª edição. São Paulo: Pearson
Prentice Hall, 2010.
[TAN] TANENBAUM, Andrew S. Organização Estruturada de Computadores. 5ª edição. São Paulo:
Pearson Prentice Hall, 2007.