Lic. Matemática e Ciências da Computação, 2ºano
2001/02
Avisos | Equipa docente | Objectivos | Programa | Bibliografia | Sumários | Avaliação
Pauta: aqui (19-Set-02, 09h00)
Material de estudo para exame: o material de estudo encontra-se organizado de forma diferente aqui (09-Jan-02, 18h00)
Material de consulta para exame: cada aluno poderá levar 1 (e 1 só) folha A4, manuscrita (original, não serão aceites fotocópias) com qualquer informação que considere necessária para consulta durante o exame. (08-Jan-02, 12h30)
Estrutura do exame: terá uma estrutura semelhante à dos 8 temas leccionados, conforme apresentados na página com o material de estudo; prever em média um peso de 10% para cada um dos temas, com excepção dos temas 4 e 5 que, no conjunto, deverão pesar cerca de 40% do total; tipo de perguntas: algumas semelhantes às do exame de Fev-99 (com correcção comentada na Web), outras semelhantes aos Home_Works, (também resolvidos na Web). (09-Jan-02, 18h00)
ATENÇÃO: O programa das sessões práticas de 2001/02 difere consideravelmente do programa de anos anteriores: o estudo do assembly é feito com base no instruction set da família processadores da Intel de 32-bits (IA-32), usando ferramentas standard da GNU em Linux, enquanto em anos anteriores se baseava na família de processadores da MIPS, num ambiente simulado (SPIM).
Alberto José Proença
email: aproenca@di.uminho.pt
Horário de atendimento: Terça 14:00 - 18:00 ; Quarta 09:00 - 11:00
António Manuel Pina
email: pina@di.uminho.pt
Horário de atendimento: Segunda 17:00 - 19:00
Pretende-se com esta disciplina - relacionada com a engenharia dos computadores - que os alunos adquiram os conceitos fundamentais relativos ao funcionamento dum computador, nomeadamente:
Para atingir estes últimos objectivos a disciplina segue uma estrutura e orientação que tira partido da formação de base dos estudantes em linguagens de programação: a partir de programas em C são introduzidas as características da linguagem máquina indispensáveis à sua realização física, com sessões teórico-práticas em metodologia de análise e desenvolvimento de programas em linguagem máquina, baseadas no instruction set de um processador real (Intel IA-32).
Introdução à organização e estrutura de um computador
Representação da informação num computador: de caracteres, de valores numéricos (com destaque para inteiros e reais), de instruções em linguagem máquina. Introdução à organização interna de um computador: o processador principal, a memória (e respectiva hierarquia de organização), os barramentos e os periféricos (e respectivos controladores). A estrutura interna dum processador e o seu funcionamento básico na execução de instruções. Operações e operandos num processador; formatos de instruções; a tomada de decisões.
Mecanismos e modelos na execução de programas
Níveis de abstracção num computador: do HLL à linguagem máquina. Mecanismos na execução de programas: a edição do programa, a conversão entre níveis (pré-processdor, compilador/interpretador, assembler), a junção de módulos e sua preparação para execução (linker e loader).
Modelo de um processador e metodologia de construção de programas em assembly
O modelo de programação em linguagem máquina: os registos
visíveis ao programador, os modos de acesso aos operandos, os tipos de instruções.;
comparação destas características entre o modelo RISC (exemplificado pelo
MIPS) e o modelo CISC (exemplificado pelo Intel IA-32).
Análise do instruction set tipo dum processador:
instruções para transferência de informação,
operações aritméticas/lógicas, instruções para a tomada
de decisões e para suporte à invocação de procedimentos; comparação entre
a estrutura de instruções numa arquitectura RISC (MIPS) e numa arquitectura
CISC (IA-32).
Metodologia de construção de programas em
assembly, com
análise detalhada de exemplos com utilitários GNU para IA-32 e em ambiente
Linux; comparação desta metodologia com a seguida nas arquitecturas
RISC.
Computação aritmética
Especificação e construção de uma ALU para adição/subtracção de inteiros, a partir dos operadores AND, OR e INV. Análise detalhada da realização de operações aritméticas e lógicas num processador (MIPS): adição/subtracção de inteiros, operações de manipulação de bits, e algoritmos de multiplicação e divisão com inteiros. Introdução a algoritmos nas operações em vírgula flutuante.
Medição do desempenho de computadores
Identificação das características a medir num computador (latência e throughput), e suas influências nos tempos de execução dum programa. Métricas na medição do desempenho; factores na arquitectura que influenciam o desempenho. Selecção de programas para o cálculo do desempenho (benchmarks), com análise do SPEC.
Organização hierárquica da memória
Introdução aos princípios da localidade (espacial e temporal) e propriedades numa hierarquia de memória (inclusão e consistência). Alternativas de implementação (cache, memória virtual, disco). Conceitos associados a cada nível da hierarquia: bloco (linha/página), hit, miss, colocação e modo de acesso aos blocos, estratégias de substituição de blocos e estratégias de escrita.
O paralelismo na melhoria de desempenho
O paralelismo ao nível da instrução máquina: introdução ao pipeline e à superescalaridade. Análise quantitativa. Paralelismo na execução de aplicações: introdução aos modelos de partilha de memória e de comunicação entre processos.
Organização e estrutura de um computador
Representação da informação no computador:
texto e respectivos alfabetos e códigos, números, informação multimédia e
comandos codificados para o processador.
Sistemas de numeração e conversão de bases; representação binária de
valores positivos e negativos (sinal + magnitude, complemento para 1,
complemento para 2, e representação por excesso).
Representação binária de valores fraccionários e introdução à
representação de valores reais em vírgula flutuante (noção e vantagens duma
normalização).
A norma IEEE 754 na representação de valores em vírgula flutuante
Introdução aos níveis de abstracção presentes num computador: o nível HLL, o nível da linguagem assembly e o da linguagem máquina.
Análise da estrutura interna dum computador (o
processador, a memória, módulos de I/O e o sistema de interligação), com
destaque para o processador (a unidade de controlo, o conjunto de registos e as
unidades funcionais) e para a organização da memória (noção de endereço e
de célula).
Funcionamento básico dum computador: modelo de execução de instruções;
introdução aos conceitos de registo de instrução, registo apontador para a
próxima instrução, e mecanismo de busca de instruções à memória -
utilizando os barramentos de endereços, controlo e de dados; descodificação
das instruções e execução das operações especificadas na instrução;
interface genérico entre o CPU e os módulos de I/O.
Mecanismos e modelos na execução de programas
Mecanismos para execução de programas: edição de texto (de programas source), tradução de programas source para níveis de abstracção mais baixos - pré-compilador, compilador e assembler - e ligação de ficheiros objecto num executável (linker); análise do formato dum ficheiro objecto; o papel do loader na execução de programas. Introdução ao ambiente laboratorial em Linux/IA32 (gcc, hexdump, as, gdb)
Modelo de um processador e e respectiva arquitectura do instruction set
Análise do funcionamento dum processador e
respectivo instruction set:
- introdução às operações num processador: análise do n.º de operandos em
cada instrução, operações aritméticas básicas, e localização de
operandos (escalares em registos, e estruturados em memória);
- introdução às operações de transferência de informação, com análise
de formatos de instruções (comprimento, campos numa instrução, variação de
formatos e pseudo-instruções); modo e número de operandos a especificar em
operações aritméticas e lógicas (0-, 1-, 2- e 3-operandos).
Modelo de programação dum processador: registos visíveis ao programador em arquitecturas RISC (para inteiros e para fp, e em detalhe no MIPS) e noutras arquitecturas; convenção na utilização dos registos no MIPS; modos de acesso aos operandos, instruções de input/output, e ordenação de bytes numa palavra (little-endian, big-endian); apresentação de um instruction set típico.
Metodologia de construção de programas em assembly: análise detalhada da implementação de instruções (para transferência de informação e operações aritméticas/lógicas) num processador genérico, e num em particular (MIPS), com exemplos de utilização; análise do formato dessas instruções em binário (no MIPS); análise detalhada da implementação de instruções para controlo do fluxo de execução (inc. invocação e retorno de rotinas/funções) num processador genérico, e num em particular (MIPS), com exemplos de utilização; análise do formato dessas instruções em binário (no MIPS).
Análise do nível ISA dum caso concreto: Intel
IA-32 em Linux; introdução da arquitectura da família x86 da Intel,
nomeadamente a estrutura de registos visíveis ao programador/compilador, os
formatos de instruções e os tipos e localização de operandos.
Análise do nível ISA do IA-32 em Linux: análise das instruções mais comuns
para transferência de informação, e para execução de operações aritméticas/lógicas;
revisão de técnicas na execução de operações aritméticas/lógicas e no
controlo do fluxo de execução de instruções (códigos de condição e
codificação de jumps); técnicas de codificação de estruturas de
controlo presentes em C, incluindo o controlo de ciclos; introdução ao modelo
de funcionamento das funções/procedimentos em HLL (C em particular) e sua
implementação ao nível da linguagem máquina do IA-32.
Resolução de exercícios diversos de interpretação e de programação em assembly.
Metodologia
de construção de programas em assembly: análise detalhada da estrutura
de instruções para invocação/retorno de rotinas e suporte à invocação de
procedimentos/funções; análise comparativa do modelo de implementação numa
arquitectura RISC versus IA-32, com estudo de exemplos de funções com
IA-32.
Medição do desempenho de computadores
Identificação das características a medir num
computador - latência e throughput - e no tempo de execução de
programas em computador (inc. CPUtime).
Noção de processo e de comutação de processos, e sua influência na
medição do desempenho.
Métricas na medição do desempenho do par
processador-memória, com dedução e análise da equação para cálculo do CPUtime
para um dado programa; factores da arquitectura que influenciam o seu desempenho.
Breve introdução ao funcionamento dum processador em pipeline e
respectivas limitações.
Medição de tempos de execução de programas:
aplicação de conceitos à análise prática de desempenho de sistemas baseados
em IA-32 em ambiente Linux; referência à medição de tempos com contadores
intervalares (do Unix) e com contadores de ciclos de clock (no IA-32).
Organização hierárquica da memória
Introdução aos princípios da localidade -
espacial e temporal - com uso de metáfora, às alternativas de implementação
(cache, memória virtual e disco), e propriedades - inclusão e consistência.
Conceitos associados a cada nível da hierarquia: bloco (linha/página), hit,
hit rate, miss, page fault, miss rate, miss penalty.
Caracterização quantitativa de níveis da hierarquia e sua influência no
desempenho. Análise de implementação de memória cache: colocação e modo de
acesso às linhas, estratégias de substituição de linhas e estratégias de
escrita. Impacto da hierarquia de memória no desempenho dum computador.
Bibliografia base: a disciplina Arquitectura de Computadores leccionada a MCC em 2001/02 vai seguir essencialmente 2 livros:
Destacam-se neste livro as questões de análise quantitativa do funcionamento dum computador (que serão analisados na última parte da disciplina) e os conceitos de funcionamento dum processador enquanto componente orientado ao instruction set, sendo de referir os capítulos 1.Computer Abstractions and Technology, 2.The Role of Performance, 3.Instructions: Language of the Machine, 4.Arithmetic for Computers e 7.Large and Fast: Exploiting Memory Hierarchy, bem como o apêndice A (Assemblers, Linkers and the SPIM Simulator). A empresa editora do livro tem disponível uma página Web com mais informação sobre o livro e com diversas extensões interessantes em http://www.mkp.com/books_catalog/catalog.asp?ISBN=1-55860-428-6 .
Este site contém links para as figuras do livro e para os acetatos de um dos autores, também disponibilizados em formato .zip no site desta disciplina (em figuras (826KB) e acetatos (2.6MB)). O autor do texto do apêndice A disponibiliza essa informação no seu site, havendo um exemplar desse apêndice no site desta disciplina (em Annex).As aulas teóricas baseadas neste livro serão leccionadas com acetatos elaborados em anos anteriores (e fortemente inspirados neste livro), os quais contêm essencialmente os tópicos de cada assunto a ser analisado. Cópias desses acetatos, eventualmente com notas adicionais, serão igualmente disponibilizados sob a forma de Notas de estudo.
Existe igualmente disponível uma tradução brasileira deste livro: "Organização e Projeto de Computadores: a interface hardware/software", 2ª ed., Livros Técnicos e Científicos Ed. S.A. De notar que, nos SDUM, em Gualtar-Braga, existem vários exemplares de cada uma destas 2 versões (inglesa e portuguesa), estando um volume de cada colocado no estado de "não-requesitável", i.e., apenas para consulta local.
Destacam-se neste livro os capítulos relacionados com a estrutura de um computador e o seu modo de funcionamento, sendo de referir as Partes I e II, bem como as referências sistemáticas aos processadores Pentium e PowerPC. A empresa editora do livro tem disponível uma página Web em http://www.prenhall.com/books/esm_0130812943.html; contudo, existe informação complementar mais rica em http://cwx.prenhall.com/bookbind/pubbooks/stallings9/chapter0/deluxe.html, ou ainda em http://www.williamstallings.com/COA5e.html, incluindo as figuras e os acetatos usados na disciplina leccionada pelo autor.
No site desta disciplina também poderá encontrar links para as figuras do livro e para os acetatos do autor, em formato .zip (em figuras (750KB) e acetatos (3.8MB)). Existem alguns exemplares deste livro nos SDUM, estando um deles no estado "não-requesitável".
Sob a forma de notas de estudo complementares é ainda disponibilizado um resumo do livro (baseado nos tópicos mais relevantes para a disciplina), com o prefácio e as figuras do livro (72 páginas, compactado (2.2MB); partes deste resumo serão ainda disponibilizadas para consulta em linha, conforme indicação explícita nos sumários).
Bibliografia complementar recomendada para leitura adicional:
Este livro é um excelente documento para a cultura geral de qualquer pessoa interessada em perceber o funcionamento dum computador pessoal na data em que o livro foi escrito, com um mínimo de bases científicas; não pode, nem deve, no entanto, ser considerado um livro universitário. Mais informação em http://www.amazon.com/exec/obidos/ASIN/0789721120/qid=939907930/sr=1-1/002-0850831-2413013).
Existem "variantes" deste livro noutras editoras, inclusive sob a forma de revista, sendo de destacar a disponibilizada no site da SmartComputing; uma cópia do conjunto das páginas relevantes encontra-se igualmente no site desta disciplina, em formato .zip, em HCW (7.9MB; a página inicial é indice.htm).
Alguns sites com interesse na Internet, para quem se mostra curioso com o tema da Arquitectura de Computadores:Mais um bom livro para leitura adicional, que se destaca pelos exemplos retirados de processadores com impacto comercial, e pela utilização do JVM como exemplo ilustrativo da microarquitectura. A editora disponibiliza mais informação em http://cw.prenhall.com/bookbind/pubbooks/tanenbaum2/, e o autor disponibiliza ainda na sua página pessoal da universidade holandesa onde lecciona (em http://www.cs.vu.nl/~ast/books/book_software.html). As figuras do seu livro estão também disponíveis no site da disciplina em formato JPEG (14.4MB) e PDF (827KB).
A disciplina de Arquitectura de Computadores está organizada em aulas teóricas (2*1h/sem) e em sessões teórico-práticas (2h/sem). A frequência às aulas teóricas não é obrigatória, mas é recomendada; a participação nas sessões teórico-práticas é obrigatória, existindo controlo de presenças; com mais de 1/3 de faltas o aluno poderá não ser admitido a exame.
As aulas teóricas são utilizadas para se transmitirem os conceitos necessários à compreensão da matéria. O material leccionado nestas aulas é encadeada, pelo que se torna indispensável o seu regular acompanhamento. A avaliação da capacidade de compreensão dos conhecimentos obtidos com o material leccionado nas aulas teóricas é realizada através de exames, e tem 50% do peso da disciplina.
As sessões teórico-práticas têm por objectivo aprofundar e/ou aplicar conceitos adquiridos nas aulas teóricas, incluindo o desenvolvimento de técnicas de programação em linguagem assembly. A prática na utilização destas técnicas de programação adquire-se com a resolução de exercícios e/ou construção de pequenos programas. A avaliação do trabalho desenvolvido ao longo destas sessões tem também 50% do peso da disciplina, repartido por duas componentes:
Os inscritos com estatuto de trabalhador-estudante - ou outros impossibilitados de frequentar as sessões teórico-práticas, devidamente justificados - poderão substituir a componente de avaliação relativa à participação nas sessões (com 10% do peso) por outra alternativa equivalente, desde que dêem conhecimento da sua situação no início do semestre.
Resumo dos pesos relativos das diversas componentes de avaliação:
Nota: Está disponível enunciado(s) de exame (Fev-99, ...) e respectiva sugestão (comentada) de resposta, para que os estudantes possam ter uma ideia do tipo de enunciado e respectiva resposta, bem como do seu grau de dificuldade.