Arquitectura de Computadores Lic. Matemática & Ciências da Computação, 1º ano 2005/2006 Docente responsável: A.J.Proença

Projecto Integrado
Programação Imperativa & Arquitectura de Computadores

Objectivos | Regulamento | Enunciado: Fase1, Fase2, Fase3 | Submissão

Ultima Modificação: 14 Mar 2006

departamento de informática

Notas

1. Pesos da avaliação de AC e prazos referentes à Fase 3 modificados (ver directamente no Regulamento). (13-Mai-06)
2. Avaliação prática da Fase 2 em AC: os exemplos necessários e referidos no enunciado estão compactados aqui. (02-Mai-06)
3. Novas alterações ao calendário de submissões e avaliação da Fase 2 introduzidas no texto do Regulamento (31-Mar-06)

4. Alterações desde o dia 10-Mar-06: endereço do local de submissões, modelo do relatório LaTeX (e respectiva versão PDF), tarefa 3 da fase 1 (13-Mar-06)

Objectivos de formação e resultados de aprendizagem

Este projecto tem como objectivos principais a formação genérica e específica de estudantes num ou mais temas em fundamentos de computação, em áreas de informática afins e interligadas: a programação imperativa e a arquitectura de computadores.

Os objectivos de formação genérica incluem: (i) a pesquisa, análise e selecção de informação, (ii) o treino de trabalho de grupo na resolução de problemas, (iii) o desenvolvimento da capacidade de análise e compreensão de textos em língua inglesa, e (iv) o desenvolvimento da capacidade de comunicação escrita e oral.

A avaliação dos resultados esperados de aprendizagem irão verificar se as/os estudantes conseguem demonstrar ter adquirido o seguinte conjunto de competências genéricas e específicas:

• competências genéricas
  • a capacidade de trabalho em grupo e respectiva comunicação efectiva e eficiente entre os elementos do grupo
  • a capacidade de comunicação escrita e oral na apresentação e discussão dos processos usados e resultados obtidos
  • a capacidade de utilização de ferramentas genéricas de informática em ambiente Linux e de elaboração de documentos anotados
• competências específicas de Programação Imperativa
  • a capacidade de desenvolver algoritmos para resolver problemas, de forma criativa, criteriosa e crítica, e inserida/o num grupo de trabalho
  • o conhecimento e a capacidade de codificar algoritmos e estruturas de dados segundo os princípios da programação estruturada (imperativa)
  • a capacidade e aptidões práticas para gerar, executar e testar programas codificados em C, usando um conjunto adequado de utilitários (GNU)
  • o conhecimento e a capacidade de analisar a execução de programas numa dada arquitectura, e as aptidões de desenvolver e aplicar testes de conformidade em situações de fronteira
  • capacidade e aptidões na produção de documentação adequada à manutenção por terceiros dos programas desenvolvidos
• competências específicas de Arquitectura de Computadores
  • a capacidade de pesquisar, seleccionar, analisar, interpretar e sintetizar a informação necessária para realizar as tarefas especificadas na fase inicial do projecto (a partir de textos em língua inglesa, e relacionada com um tema indicado no enunciado)
  • o conhecimento e a capacidade de identificar e caracterizar as técnicas de codificação de estruturas típicas de controlo e dos métodos de acesso e manipulação de dados estruturados, no processo de compilação de uma linguagem imperativa, usando o gcc
  • a aptidão para analisar código em assembly e utilizar ferramentas de baixo nível de depuração (gdb) de programas
  • o conhecimento, a capacidade e a aptidão para aplicar técnicas de engenharia inversa a código binário
  • aptidões na aplicação de técnicas e métricas na análise de desempenho baseadas no profiling de aplicações
  • capacidades e aptidões para descrever, aplicar e avaliar técnicas de optimização de desempenho independentes e dependentes da máquina

Regulamento

Caracterização do Projecto

1. O projecto consiste na realização de um trabalho prático em grupo, integrando conteúdos de 2 disciplinas, e com entrega faseada de resultados.
2. O projecto é único para cada ano lectivo, e a não aprovação no projecto conduz à classificação de "Não Admitido" na pauta final de exame. 
3. O projecto conterá questões e tarefas específicas para cada uma das disciplinas, devidamente especificadas no enunciado do projecto na página de cada uma das disciplinas.
4. O projecto deverá ser submetido através de um sistema de submissões de trabalhos com uma designação consoante a fase (1, 2 ou 3) e o nº de grupo (com a indicação de "Fasen" seguido da identificação do grupo; por ex., "Fase2-3.1"); a documentação a submeter deverá constar de: (i) relatório redigido em LaTeX, segundo a estrutura e modelo definidos para os relatórios (modelo Tex com anexo), (ii) relatório compilado para PDF (aspecto do relatório), (iii) eventuais ficheiros com o código e/ou conjunto de testes, e (iv) eventual informação adicional.
5. Material de apoio à produção de documentos em LaTeX, elaborado por Alberto Simões: Mini-curso de LaTeX e  Manual de LaTeX.
6. Os resultados do projecto serão avaliados em 3 fases distintas ao longo do semestre: nas semanas 5, 7 e 12/13 (datas indicadas adiante).
7. As questões e tarefas a efectuar pelos grupos que se encontram inscritos a apenas uma das disciplinas serão devida e atempadamente acauteladas, e por contacto directo com o docente responsável da respectiva disciplina.

O Projecto como trabalho de grupo

1. O projecto deverá ser realizado por grupos de 3 elementos, devendo estes estarem inscritos às mesmas disciplinas (ou às 2, ou todos apenas a uma delas). Em casos excepcionais, devidamente justificados e aceites pelo docente responsáveis de cada uma das disciplinas, será possível a realização do projecto com menos elementos.
2. A organização, planeamento e coordenação das actividades do trabalho de grupo é da inteira responsabilidade dos seus elementos. Os slides apresentados na sessão de introdução ao trabalho de grupo estão aqui disponíveis (também estão incluídos nos slides de apresentação de AC).
3. O Dep. Informática assegura diverso apoio extra-lectivo à preparação do projecto, nomeadamente:
   1. Postos de trabalho em laboratórios Unix (com MacOS ou Linux), quando disponíveis.
   2. Uma sala no CP-II (2.203) para trabalho em grupo, nas quartas, das 14h00 - 18h00.
   3. Uma sala no DI (0.02) para trabalho em grupo, com supervisão e algum apoio docente, nas quartas, das 14h00 - 18h00.
   4. Um laboratório de Informática no DI (0.12) com 12 postos de trabalho em Linux, para trabalho em grupo, com supervisão e apoio de um docente, nas quartas, das 14h00 - 18h00.

Metodologia de avaliação do Projecto

1. A avaliação do projecto consiste na verificação da aquisição individual dos conhecimentos, capacidades e aptidões especificadas no enunciado do trabalho, e decorrerá num laboratório do DI.
2. Os elementos que serão utilizados na avaliação incluem:
   1. O relatório: (i) a versão electrónica deverá ser submetida no prazo especificado, e (ii) a versão impressa deverá acompanhar o grupo durante a defesa do trabalho; o relatório de cada uma das fases do projecto deverá conter o relatório da fase anterior, com eventuais correcções e melhorias.
   2. Eventual apresentação formal oral (tarefa a definir explicitamente no enunciado).
   3. O programa desenvolvido de acordo com as especificações, em condições de ser apresentado (não são admitidos erros de compilação), e respectiva bateria de testes.
   4. A defesa do trabalho (obrigatória) junto a um computador, na presença de todos os elementos do grupo, durante um tempo estimado de 20 min; em situações de ausência de um elemento, devidamente justificadas, poderá haver uma posterior defesa individual do trabalho.
   5. Uma defesa individual do trabalho realizado, em casos a especificar.
3. Calendário para a entrega dos relatórios em formato electrónico:
   1. Fase 1, segunda 20-Mar-06, 12h00.
   2. Fase 2: segunda 10-Abr-06, 12h00 (com variantes; consultar o enunciado da Fase 2).
   3. Fase 3: sexta 26-Mai-06; adiado para segunda 29-Mai-06, 12h00.
4. Calendário para a realização das defesas dos trabalhos:
   1. Fase 1: não há avaliação oral; os resultados da avaliação serão apresentados e discutidos pelos docentes das 2 disciplinas nas suas aulas.
   2. Fase 2: em data/horário especial para PI (19-Abr-06, consultar a pág. de PI) e para AC (03-Mai-06, consultar pág. de avisos de AC).
   3. Fase 3: no horário das sessões laboratoriais, na semana de 29-Mai-06; em horário a indicar na semana de 22-Mai-06.
5. A ordem de defesa dos trabalhos é coincidente com a ordem de inscrição dos grupos, e será atempadamente divulgada.
6. A classificação final do projecto será, em princípio, por patamares:
   • Não Aprovado - não apresentação de projecto ou resultados com um nível elevado de insatisfação de requisitos.
   • Fraco (<10) - com diversas falhas, mas que não inviabiliza a ida a exame teórico (lacunas sérias em conhecimentos ou na utilização de ferramentas, deficiências graves no programa apresentado, ... )
   • Aprovado (10) - cumpre, no limite, os requisitos mínimos especificados nos resultados de aprendizagem (embora com questões relevantes que não estejam correctas)
   • Razoável (entre 11 e 14) - cumpre razoavelmente os requisitos especificados nos resultados de aprendizagem
   • Bom (entre 15 e 18) - cumpre bem os requisitos especificados nos resultados de aprendizagem
   • Excelente (19 ou 20) - excede os requisitos especificados nos resultados de aprendizagem
7. Os pesos relativos da avaliação de cada uma das fases são os seguintes:
   1. Fase 1: 10% em PI, 20% em AC.
   2. Fase 2: 40% em PI, 50 65% em AC.
   3. Fase 3: 50% em PI, 30 15% em AC (opcional para quem já tiver garantido o exame a AC).
8. Para cada uma das fases de avaliação do projecto os grupos serão atempadamente informados do seu desempenho, com feedback adequado para melhorarem os seus resultados, de acordo com um modelo de classificação similar.
9. A classificação individual final será um valor de compromisso entre a classificação obtida pelo grupo no projecto e a impressão individual que cada elemento produziu nas equipas de examinadores e a opinião manifestada por todos os elementos do grupo de trabalho.
10. Caso sejam detectadas situações fraudulentas (desde plágio de outro grupo ou de um outro qualquer local, a comportamento fraudulento de um dos elementos do grupo), as partes envolvidas ficarão sujeitas a acções ou procedimentos disciplinares seguindo a hierarquia institucional e de acordo com a gravidade demonstrada. Recomenda-se a leitura do documento de reflexão produzido na sequência das irregularidades ocorridas em 2004/05, em que vários de estudantes comprometeram a sua carreira de estudante com a reprovação a estas 2 disciplinas (para além dos procedimentos disciplinares).
11. Dúvidas que surjam na sequência de ambiguidades ou lacunas no enunciado do projecto e/ou deste regulamento, deverão ser apresentadas a um dos docentes responsáveis de PI ou AC, preferencialmente por email. Quando necessário, o esclarecimento dessas situações far-se-á por inclusão de um aviso na página Web da disciplina.

Topo...

Enunciado

Fase 1

Esta primeira fase do projecto tem como principais objectivos avaliar (i) a capacidade de pesquisa e selecção de informação (avaliação feita em AC), (ii) a capacidade de sintetizar a informação relevante e de a comunicar por escrito de uma maneira clara e estruturada (avaliação feita em AC), (iii) as aptidões na utilização de ferramentas Unix na produção de documentos (em LaTeX e PDF) (avaliação feita em PI) e (iv) a capacidade de analisar um problema e de propor uma solução viável e funcional usando uma linguagem de programação imperativa (avaliação feita em PI).

As equipas docentes destas disciplinas reforçam deste modo a opinião expressa por António Adrego da Rocha no seu recente livro Introdução à Programação usando C (ver bibliografia de PI):

"Para que, no futuro, qualquer programador possa compreender todos os aspectos implementados, podendo alterar e estender facilmente a funcionalidade da aplicação, é necessário assegurar que a aplicação está suficientemente documentada. Assim, em aplicações informáticas profissionais, existe ainda a questão da documentação, que assenta na produção de tipicamente dois manuais. Um manual de produção, para auxiliar futuros programadores na manutenção da aplicação, por isso as etapas de especificação e de análise algorítmica devem estar bem documentadas, de maneira a ser possível alterá-las facilmente. Também é necessário que a codificação esteja bem documentada, de forma a ser fácil fazer alterações futuras, reaproveitando ao máximo código existente, ou seja, é preciso privilegiar todos os aspectos ligados à elegância da decomposição e à clareza da documentação - por isso é que na fase da geração de código da aplicação se dá muita ênfase à questão da legibilidade do código. (...)"

Face a esta exposição, pretende-se que as/os estudantes executem as seguintes tarefas na fase 1:

1. Analisar o modelo de relatório proposto e testar a compilação do LaTeX e a geração de ficheiros em PDF.
2. Caracterizar detalhadamente o ambiente de trabalho a ser utilizado na implementação da solução informática deste problema (ou doutro semelhante), com o objectivo de assegurar uma integral reprodutibilidade das condições de teste; i.e., se alguém pretender repetir o trabalho a partir da mesma proposta de solução codificada (em C), quais deverão ser as condições de trabalho em termos de arquitectura do sistema informático (características relevantes do CPU, memória primária e secundária, sistema operativo) e do ambiente de desenvolvimento usado (lista integral das aplicações e respectivas versões) (avaliação exclusiva de AC).
3. Complementar essa caracterização da arquitectura com 3 parágrafos adicionais (máx. 200 palavras por parágrafo, e 1 parágrafo por cada elemento do grupo), onde, por palavras vossas, apresentem de uma maneira integrada com o resto do relatório, uma definição clara e sucinta de 3 conceitos/termos de entre os seguintes (ignore os nºs entre parêntesis): BIOS (0), frequência do clock do CPU (1), on-die L2 cache (2), chipset com PCI-Express (3), resolução de monitor WXGA, WSXGA e WSXGA+ (4), hard disk IDE SATA de 5400rpm (5), interface USB2 (6), flash memory (7), processador dual-core com FSB 800MHz (8), DDR-II 400/533/667MHz (9).  Para cada um dos temas deverá ser sugerido um local na Web para aprofundar conhecimentos sobre o assunto (nota: a inclusão de traduções de textos para português também é considerado plágio).
   A distribuição dos temas pelos grupos será feita posteriormente, em aviso a colocar na página de AC (avaliação exclusiva de AC).
4. Analisar um dos problemas propostos como Trabalho Prático I (em PI), desenvolver um algoritmo para resolução desse problema e apresentá-lo / explicá-lo nas secções apropriadas do relatório (avaliação exclusiva de PI).
5. Codificar os algoritmos propostos, documentando-os adequadamente (avaliação exclusiva de PI).
6. Preparar um conjunto de ficheiros de entrada para teste, que permita validar, além de outras, as de condições limite (avaliação exclusiva de PI).
7. Criar programas executáveis, usando o ambiente de desenvolvimento da GNU, e seleccionando o nível de optimização -O2, e testar o produto final da Fase 1 (avaliação exclusiva de PI).
8. Apresentar os resultados destas tarefas num relatório redigido redigido conforme as regras definidas no regulamento; a sua estrutura deverá conter, para além do título e lista de autores, um resumo (máx. 600 caracteres), uma introdução com caracterização sumária do problema a resolver, uma caracterização do ambiente de trabalho usado para resolver o problema, uma breve exposição/relato dos aspectos relevantes de cada uma das fases/tarefas necessárias para a análise, especificação, concepção, codificação e teste de uma solução informática, as conclusões (resumo dos resultados com opinião pessoal sobre o que poderia ter sido feito melhor ou...), uma lista da bibliografia pertinente para a resolução do trabalho, e, em anexo, uma listagem do código (avaliação da qualidade do relatório influencia essencialmente a classificação de AC).

Fase 2

Correcção (apenas para estudantes que frequentam AC): o prazo de entrega do relatório para ambas as disciplinas (AC e PI) foi adiado para depois da defesa do trabalho em PI (entrega a 24-Abr-06, 12h00).
Este relatório será fruto de avaliação em AC e PI, e deverá conter, nas conclusões, uma reflexão sobre a defesa oral do trabalho em PI; em PI exige-se a entrega prévia do algoritmo e programa, com eventuais ficheiros de teste (na data indicada na página de PI).

A 2ª fase dá uma ênfase maior à avaliação dos conhecimentos e capacidades específicas entretanto adquiridas: (i) na concepção, codificação e teste de algoritmos e estruturas de dados mais elaborados, (ii) na análise laboratorial de código assembly gerado pelo compilador e de variáveis de estado na execução de código (conteúdo de registos e de células de memória), e (iii) no processo de reverse engineering de código, i.e, na recuperação de código objecto executável para a provável codificação em HLL.

Nesta perspectiva, pretende-se que as/os estudantes executem as seguintes tarefas:

1. Corrigir e/ou completar as tarefas solicitadas na 1ª fase relativas à elaboração do relatório, e que não foram realizadas, ou foram-no de modo menos correcto ou adequado; recordar que o relatório deverá ter entre 4 e 8 páginas (mais os anexos); para os estudantes que também frequentam PI, as componentes relativas à apresentação do problema de programação a resolver deverão ser substituídas pelas que se encontram no enunciado da fase 2. Esta tarefa de reescrita do relatório é obrigatória para todos. (o seu não cumprimento em AC conduz à não-Aprovação na componente prática).
2. Analisar o problema proposto como Trabalho Prático II (em PI), desenvolver um algoritmo para resolução desse problema e apresentá-lo / explicá-lo nas secções apropriadas do relatório (avaliação exclusiva de PI).
3. Codificar os algoritmos propostos, comentando-os e documentando-os adequadamente; existem rotinas de suporte e exemplos disponibilizados aqui (avaliação exclusiva de PI).
4. Criar programas executáveis, usando o ambiente de desenvolvimento da GNU, e seleccionando o nível de optimização -O2.
5. Preparar um conjunto de ficheiros de entrada para teste dos algoritmos/código das funções solicitadas, que permita validar, além de outras, as condições limite (avaliação exclusiva de PI).
6. Analisar o código assembly produzido pelo gcc no processo de compilação (apenas) do código C da função LoadMFT (leitura de um desenho previamente gravado) do ficheiro myio.c (programas disponibilizados aqui); dedique uma secção do relatório a esta análise, com a seguinte informação: (i) apresentação do código em assembly, claramente identificando o corpo da função e as componentes de arranque e término da função, e incluindo comentários no corpo da função semelhantes a código C; (ii) identificação dos registos e/ou células de memória onde foram alocadas as variáveis locais da função; (iii) apresentação da estrutura e conteúdo da stack frame no início da execução do corpo da função; (iv) identificação clara do código das estruturas de controlo do corpo do ciclo while "Enq não se tiverem lido as linhas todas"; algumas destas tarefas deverão também ser executadas durante a defesa do trabalho (avaliação exclusiva de AC).
7. Efectuar o reverse engineering da função xfunc (assinatura no ficheiro ofuscado.h): a partir do objecto ofuscado.o, obter uma possível versão do código dessa função em C, estruturada de uma forma correcta e elegante (avaliação exclusiva de AC).
8. Preparar-se para uma demonstração individual da utilização dos diversos utilitários de análise de código de baixo nível (assembly e binário) e de valores na memória e em registos, durante a execução de um programa (avaliação exclusiva de AC, na defesa oral do trabalho).

Fase 3

Nesta fase final, pretende-se que as/os estudantes executem as seguintes tarefas:

1. Corrigir e/ou completar as tarefas solicitadas nas 1ª e 2ª fases e que não foram realizadas, ou foram-no de modo menos correcto ou adequado.
2. Complementar as tarefas das fases anteriores com novas tarefas, para avaliação exclusiva em PI, conforme descrição efectuada na página dessa disciplina (aqui).
3. Complementar as tarefas da fase anterior com novas tarefas, para avaliação exclusiva em AC, conforme descrição detalhada feita a seguir a esta lista de tarefas, e apenas destinada a quem pretender uma classificação de Bom ou superior.
4. Elaboração de um texto, por cada elemento do grupo de trabalho, com uma dimensão aproximada de 1 página A4, contendo: (i) uma visão pessoal da sua participação no projecto (e o seu papel em cada um dos temas das 2 disciplinas), (ii) uma reflexão crítica sobre o projecto como um todo, e (iii) a uma autoavaliação pessoal do trabalho efectuado pelo grupo e por si, no âmbito do projecto. Este texto deverá ser incluído no relatório, como anexo, com o título de "Análise crítica de <Nome>".
5. Elaboração e entrega do relatório final nas seguintes condições: (i) de acordo com o modelo de referência disponibilizado no início, mas podendo ser estendido para 12 páginas, (ii) submetido conforme estipulado no regulamento, e (iii) contendo uma descrição de todas as fases do projecto, de um modo integrado e coerente.

A tarefa nova prevista para AC tem como objectivo principal avaliar o desempenho de uma aplicação em C e modificar o código de modo a optimizar o desempenho de uma função dessa aplicação, mas sem alterar a sua funcionalidade.
Para uma correcta execução desta tarefa ela deverá ser realizada de acordo com as seguintes sub-tarefas:

• analisar o código no ficheiro "encolhe.c" (disponibilizado aqui), que contém uma função que aplicada a um ficheiro com um desenho vai modificar esse desenho encolhendo-o; o desenho original deverá ser feito de acordo com as especificações do programa em C definido na fase 2, usando apenas caracteres como marcas do desenho; de notar que esta função apenas está preparada para lidar com desenhos contendo um nº ímpar de linhas e colunas;
• especificar de modo informal, todas as operações presentes no ficheiro e a sequência de passos presente no main; (para incluir no relatório)
• compilar e testar a execução deste código com um desenho feito por si (de preferência de grande dimensão, por ex., com 599x799);
• modificar o código disponibilizado de modo a: (i) efectuar o aquecimento da cache, i.e., acrescentar código que aceda a todos os elementos do desenho, (ii) calcular 10 valores do CPE da função que encolhe o desenho, e imprimir o menor deles (pode usar o código para cálculo dos valores do CPE disponibilizado com o Guião 5); (para incluir no relatório, em anexo)
• compilar o código resultante (sem nenhuma optimização activada, e depois com -O1 e -O2), executar essas 3 versões (com o desenho feito por si), registar os valores de CPE obtidos, e tentar interpretar as possíveis diferenças nos valores obtidos; (para incluir no relatório)
• modificar agora o código apenas associado à função que encolhe o desenho de modo a melhorar o  seu desempenho; criar versões diferentes para cada modificação introduzida, e calcular os respectivos valores de CPE, colocando-os todos numa tabela; (para incluir no relatório)
• interpretar/explicar (recorrendo ao código em assembly sempre que necessário) todas as melhorias esperadas e/ou obtidas, fazendo uma análise crítica dos resultados e das medições efectuadas (para posterior avaliação oral individual).

Topo...