Trabalho Implementação Microprocessador+Otimizações de Compilador

Nesta página estão detalhados os procedimentos que devem ser seguidos para o desenvolvimento do Trabalho 1 da disciplina de Tópicos Avançados em Sistemas de Computação. Este trabalho será desenvolvido ao longo do 2o. Bimestre deste semestre letivo e constituirá parte da nota final da disciplina. É fortemente recomendado que os estudantes acessem com freqüencia esta página para: esclarecer possíveis dúvidas, estar ciente do cronograma, estar a par de possíveis atualizações/alterações no trabalho.

Objetivos: Implementar, utilizando a linguagem ArchC, um simulador para o processador ARM (Advanced RISC Machines) versão 7 (ARM7). Definir e implementar otimizações de compilador compatíveis com as características do processador ARM (mais informações sobre a arquitetura ARM7 veja aqui). Uma descrição sobre o pipeline ARM7 pode ser encontrada aqui.

Definição de Algoritmos/Técnicas de Geração de Código (Novo!!!)

Cada estudante deve escolher um dos trabalhos a seguir e verificar a adequabilidade da implementação dessa técnica sobre a arquitetura ARM7. O intuito não é implementar a técnica. No entanto, deve-se estudá-la detalhadamente a fim de: 1) explicá-la durante a apresentação do trabalho; 2) Indicar se é factível (ou não) na arquitetura ARM7 e, principalmente, justificar porque é (ou não é) factível. As técnicas são baseadas nos seguintes artigos:

1. Pinter, S. S., Register Allocation with Instruction Scheduling: a New Approach. Proceedings of the ACM Sigplan Conferece on Programming Languages Design and Implementation. p. 248-257, 1993

2. Norrys, C. Pollock, L. L., Register Allocation Sensitive Region Scheduling. Proceedings of the Conferece on Parallel Architectures and Compilation Techniques. Limassol-Cyprus. p. 1-100, 1995.

3. Ferrante, J., Ottenstein, K. J., Warren, J. D., The Program Dependence Graph and its Use in Optimization. ACM Transactions on Programming Languages and Systems, V. 9, n. 3, 319-349, July 1987.

4. Aiken, A. Nicolau, A., Optimal Loop Parallelization. Proceedings of the SIGPLAN'88 Conference on Programming Language Design and Implementation. p. 308-317. Atlanta-Georgia. 1988.

5. Gibbons, P. B., Muchnick, S. S. Efficient Instruction Scheduling for a Pipelined Architecture. Proceedings of the 1986 SIGPLAN Symposium on Compiler Construction, p. 11-16, 1986.

6. Kerns, D. R., Eggers, S. J. Balanced Scheduling: Instruction Scheduling When Memory Latency is Uncertain. Proceedings of the ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation. Albuquerque-New Mexico, p. 278-289. 1993.

O que deve ser feito?

1. Implementar a especificação (mais próxima possível do modelo completo) do processador em ArchC.

2. Implementar, pelo menos, cinco programas (1 instruções aritméticas, 1 instruções de memória, 1 instruções de desvio condicional (sem loop), 1 loop, 1 instruções para chamadas a procedimentos) exemplo que testam diferentes características do processador.

3. Fornecer montador/linker para o processador.

4. Definição de um algoritmo para geração de código e/ou otimização para o código a ser executado sobre o processador.

5. Escrever relatório (máximo de 8 páginas) relatando o que foi realizado no trabalho.

Sugestão de metodologia para desenvolvimento do trabalho

• Trabalho individual mas com forte viés colaborativo.

• Entendimento da arquitetura ARM.

• Determinação e implementação dos recursos da arquitetura e do conjunto de instruções (o conjunto de instruções ARM está aqui e o conjunto Thumb está aqui). Uma descrição bem específica do conjunto de instruções ARM pode ser obtida aqui

• Implementação comportamental das instruções.

• Testes de correção/desempenho da arquitetura

• Definição/Configuração de um montador+linker para o processador

• Definição de algoritmos para geração de código/otimizações de código e/ou implementação desses algoritmos

Qual o Cronograma ?

• 19/09: Início do trabalho

• 04/10: 1o. Checkpoint: O horário da aula será dedicado para entrevistas/esclarecimentos de dúvidas com cada estudante sobre o andamento do trabalho. É esperado que cada estudante apresente a versão inicial da implementação da arquitetura, definições dos formatos das instruções e início da implementação do comportamento das instruções

• 18/10: 2o. Checkpoint: É esperado que cada estudante tenha finalizado a implementação do comportamento das instruções e apresente programas que utilizam os recursos (instruções) já implementados. Também será averiguado as definições já realizadas sobre a parte de geração de código

• 14/11: 3o. Checkpoint: Cada estudante deve apresentar a situação atual do trabalho: situação do simulador e ferramenta para geração/otimização de código

• 22/11: Entrega de relatório com, não mais que 8 páginas, contendo as seguintes seções :

1. O que foi implementado.

2. O que faltou implementar.

3. A sintaxe para execução da ferramenta.

4. Bugs/Falhas detectados e não corrigidos.

5. Dificuldades encontradas durante o desenvolvimento do trabalho.

6. Conclusões.

• Enviar o código fonte da ferramenta, o respectivo arquivo executável e programas de exemplo para execução.

• 28/11: Apresentação: cada estudante terá 15 minutos para apresentar seu trabalho.

• Até 29/11: Envio (por e-mail com título: “Avaliações: Tópicos Avançados” ) das avaliações para o professor.

Como será a avaliação?

• Os relatórios entregues serão avaliados pelo professor e pelos demais colegas que também devem ler o relatório e assistir a apresentação.

• Além disso, a avaliação também constará das avaliações parciais dos checkpoints (cada checkpoint terá peso 1).

• Será feita uma média entre as notas dadas pelos demais colegas e, a essa média será atribuido peso 1.5.

• A nota do professor para o relatório e apresentação também terá peso 1.5.

• A avaliação final de todo o trabalho de acordo com a abrangência e versão alcançada (peso 4);

• Bônus (peso 1.5): versão alcançada pelo simulador, organização e documentação do código, arquivo README, scripts para configuração e execução, clareza na explicação do relatório;

Dicas/Sugestões

• Procure estudar a implementação dos modelos implementados e disponíveis na página da linguagem ArchC.

• Inicie o trabalho o quanto antes. O tempo voa!

• Documente o código. Isso ajudará a relembrar o que estava sendo feito no dia anterior e, principalmente, depurar o código em caso de bugs.

• Retire as dúvidas quanto ao entendimento da sintaxe antes de implementá-la. Isso permitirá que a etapa de implementação não seja interrompida.

Perguntas frequentes:

P: Se faltar no dia do checkpoint, fica com 0?

R: Há duas possibilidades: 1) Se souber, previamente, que irá faltar em dia de checkpoint, a dupla deve avisar ao professor que irá agendar um horário anterior ao dia do checkpoint. 2) caso a falta seja devido a um imprevisto, a dupla deve procurar o professor e deve justificar a ausência e, após isso, o professor marcará um horário para a entrevista. Faltas sem justificativa, aí sim, terão 0 como nota do checkpoint.

P: Há possibilidade de adiar a entrega do trabalho por alguns dias?

R: Infelizmente, não. As datas de entrega estão no limite do aceitável. Trabalhos entregues fora do prazo correm o sério risco de não serem avaliados e, no melhor dos casos, serão avaliados mas os atrasos serão descontados no valor da nota.

P: O que devo privilegiar: implementar todo o conteúdo de uma etapa ou implementar todas as etapas?

R: Se não houver tempo hábil, é melhor implementar o mínimo necessário em uma etapa e partir para a próxima. A contribuição deste trabalho para vocês é justamente a experiência prática com relação a uma implementação de mais baixo nível dos processadores e de algoritmos para geração de código.

P: O que fazer em caso de dúvidas no entendimento do trabalho (recursos não disponíveis na linguagem ArchC, ausência de detalhes na atribuição das tarefas, etc.)?

R: Procure o professor o quanto antes: pessoalmente ou enviando mensagem eletrônica com subject: "Dúvidas: Trabalho1 – Tópicos Avançados". Nesse último caso, procure discorrer sucintamente a sua dúvida. Além disso, aproveite bem os encontros de checkpoint para retirar suas dúvidas, sugerir alterações na atribuição do trabalho, justificar suas escolhas. Isso contará na sua participação e dedicação do trabalho.

P: Como deve ser a saída do simulador?

R: O simulador que será entregue para avaliação não deverá ``fugir'' do formato de saída padrão do ArchC. É importante seguir a risca essa recomendação para que a avaliação de todos os trabalhos seja a mais coerente possível.

P: Há algum formato específico para as avaliações que farei dos trabalhos e apresentações de meus colegas?

R: Não. Como sugestão de organização sugiro que dedique uma página para cada trabalho avaliado. Nessa página, indique: nome do aluno, trabalho: pontos positivos, trabalho: pontos negativos, apresentação: comentários, nota final.

P: Serei avaliado pelas minhas avaliações?

R: Uma vez observado todos os prazos que temos, os resultados das suas avaliações não farão parte do cômputo da sua nota. Na verdade, a pontualidade, a participação e o detalhamento das avaliações entrarão como bônus.

P: O que apresentarei no dia 28/11 se todos farão um simulador para um mesmo processador?

R: O foco da apresentação será a implementação que você fez e o algoritmo para geração/otimização de código. Não perca tempo da apresentação mostrando o que a arquitetura faz pois isso todos os presentes já deverão saber.

P: Como saber que versão atribuir à minha implementação do simulador?

R:

P: Se obter nota máxima em todos os itens da avaliação ficarei com 11.5?

R: Não. A nota máxima é 10! Além disso, esses pontos não são cumulativos.