Otimizacao de Uso de Registradores em Algoritmos - Analise e Mapeamento

1 40 pontos Considere o algoritmo que aparece descrito pelo seu diagrama ASM na Figura Q1a fornecida anteriormente Nesta mesa figura mostrase a Tabela de Uso de Variáveis correspondente a 05 ponto Pedese que seja feito o preenchimento da última linha da Tabela de Uso de Variáveis que corresponde aos valores do número mínimo de registradores necessários em cada Estado Para facilidade Figura Q11 reproduziuse a primeira linha Estados e a última linha da Tabela que é onde deve ser escrito o número mínimo de registradores Figura Q11 Tabela de Número Mínimo de Registradores Estado s0 s1 s2 s3 s4 s5 O número mínimo de registradores é 3 Número Mínimo de Registradores 0 2 2 3 2 1 Para uso do professor 1a 0 1 2 3 4 5 1 b 10 ponto Use a Figura Q12 para preencher a quarta coluna da Tabela de Aplicação do LEA que é onde são feitas as alocações de variáveis a registradores para execução do algoritmo Aproveite para preencher também o mapeamento de variáveis a registradores obtido pela aplicação do LEA mais à direita naquela mesma Figura Caso não haja alocação de variáveis a algum dos registradores fornecidos utilize a notação φ Figura Q12 Tabela de Aplicação do LEA Mapeamento de variáveis a registradores LEA Variável Tempo de vida Conflitos Registrador t7 2 t3t5t6 R1 R1 xt1t7t8 x 1 y R1 R2 yt2t3t6 y 1 x R2 R3 t5 t1 1 t2 R1 R4 φ t2 1 t1 R2 R5 φ t3 1 t5t7 R2 R6 φ t5 1 t3t7 R3 t6 1 t7 R2 t8 1 R1 Para uso do professor 1b 0 1 2 3 4 5 6 7 8 9 10 Somente para apreciação dos professores Não divulgue 1 c 10 ponto Pedese que na Figura Q13 analisando a Tabela do Grafo de Compatibilidade Q13b sejam preenchidos os mapeamentos de variáveis a registradores Q13a e os SuperNós do Grafo de Compatibilidade Q13c Mapeamento de variáveis a registradores pelo GPA R1xt1t3t6t8 Q13a R2yt5 R3t2t7 Tabela do Grafo de Compatibilidade Figura Q13 Q13b Q13c Grafo de Compatibilidade x t1 t3 t6 t8 t2 t7 x y t1 t2 t3 t5 t6 10 10 t7 10 10 t8 01 y t5 Para uso do professor 1c 0 1 2 3 4 5 6 7 8 9 10 1 d 15 pontos A tarefa agora é a de preencher o ASMD RTL a partir do ASM mnemônico fornecido Devese preencher o ASMD RTL da esquerda com a alocação de registradores obtida pela aplicação do LEA e o da direita pela obtida pelo GPA Solicitase que replique para sua facilidade as devidas alocações que foram derivadas nas partes anteriores nos espaços reservados para tal Diagrama ASMD RTL LEA Figura Q14 Diagrama ASMD RTL GPA Mapeamento LEA R1 xt1t7t8 R2 yt2t3t6 R3 t5 R4 φ R5 φ R6 φ Mapeamento GPA R1xt1t3t6t8 R2yt5 R3t2t7 R1 In1 R2 In2 R1 R1 R2 R2 R1 In1 R3 R2 não Start sim S0 S1 R1 R1 R2 R2 não Start sim S0 S1 R2 máx R1 R2 R3 máx R1 R2 4 R1 mín R1 R2 1 R1 máx R1 R3 R2 R2 R3 S2 S2 R1 R1 R2 S3 S3 R1 máx R2 R1 S4 S4 Out R1 Ready 1 Out R1 Ready 1 S5 S5 Para uso do professor 1d 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Somente para apreciação dos professores Não divulgue 2 30 pontos A figura abaixo mostra um código em linguagem Assembly do PoliLEG e o conteúdo da memória de dados 07 08 0F 10 17 20 1F 22 27 00 06 00 0E 00 16 00 1E 00 26 00 05 00 0D 00 15 00 1D 00 25 00 04 00 0C 00 14 00 1C 00 24 00 03 00 0B 00 13 00 1B 00 23 00 02 00 0A 00 12 00 1A 00 22 00 01 00 09 00 11 00 19 00 21 00 00 00 08 00 10 00 18 00 20 00 1 ADD X0 XZR XZR 2 ADD X1 XZR X0 3 LDUR X2 XZR 0 4 repete ADD X0 X0 X2 5 LDUR X3 X0 0 6 CBZ X3 resultado 7 ADD X1 X1 X3 8 B repete 9 resultado STUR X1 X0 0 10 fim B fim Considere que os números de 64 bits armazenados na memória estão dispostos com o byte mais significativo no endereço menor Lembrese que o registrador XZR ou X31 contém sempre a constante zero Analisando o código acima responda as próximas perguntas a 05 ponto Qual é o resultado da execução do programa armazenado no registrador X1 Para uso do professor 2a 0 1 2 3 4 5 52h a soma de três words na memória a partir do endereço 08h b 05 ponto Em qual endereço da memória o resultado será salvo No endereço 20h a primeira posição de memória contendo o word zero Para uso do professor 2b 0 1 2 3 4 5 Somente para apreciação dos professores Não divulgue 3 30 pontos Considere o projeto do processador PoliLEG cujo diagrama lógico completo é apresentado na terceira página desta prova O circuito do PoliLEG realiza a implementação de 8 instruções do ARMv8 ADD SUB AND ORR LDUR STUR CBZ B Esta figura apresenta os componentes do Fluxo de Dados e sua interligação além dos sinais de controle gerados pela Unidade de Controle 3 a 10 ponto Apresente e depois detalhe cinco características ou funcionalidades do Banco de Registradores do PoliLEG Cinco características ou funcionalidades do Banco de Registradores do PoliLEG 1 Capacidade 32 registradores de 64 bits 2 Dual port possui 2 saídas de leitura e 1 entrada para escrita 3 Registrador XZR o registrador X31 deve sempre ser igual a zero e é invariante nas escritas 4 Sinal de controle possui apenas 1 sinal de controle RegWrite 5 Clock é um componente síncrono sensível a borda do sinal de clock Para uso do professor 3a 0 1 2 3 4 5 6 7 8 9 10 3 b 10 ponto Seja a instrução assembly CBZ A instrução usa o formato de instrução CB mostrado na página 3 que contém código de operação opcode deslocamento condbraddress e registrador de condição Rt Explique como a próxima instrução a ser executada depois de uma instrução CBZ é determinada E quais são os sinais do fluxo de dados e de controle responsáveis pelo cálculo do endereço da próxima instrução Para uso do professor 3b 0 1 2 3 4 5 6 7 8 9 10 Considere o formato da instrução CB mostrado na página 3 que contém código de operação opcode deslocamento condbraddress e registrador de condição Rt A instrução CBZ determina a próxima instrução a ser executada verificando o valor de um registrador de condição Se o valor armazenado pelo registrador for diferente de zero a próxima instrução é a próxima instrução do programa PC4 No caso do registrador armazenar o valor zero o endereço da próxima instrução é calculado usando o campo de deslocamento e o valor atual de PC PCdeslocamento4 O cálculo do endereço da próxima instrução envolve o valor atual do PC e o campo de deslocamento da instrução CBZ O único sinal de fluxo de dados usado é a saída Zero da ULA O sinal de controle gerado da Unidade de Controle envolvido neste cálculo é Branch que junto com Zero é usado para gerar o sinal PCSrc para selecionar qual será o próximo valor de PC PCPC4 se PCSrc0 e PCPC4deslocamento se PCSrc1 3 c 10 ponto Durante o processo de fabricação dos circuitos integrados de um sistema digital um defeito de fabricação que pode ocorrer é conhecido como Stuckat0 fault Este defeito faz com que o fio de um sinal do circuito fique sempre em nível lógico 0 Considere as oito instruções do PoliLEG ADD SUB AND ORR LDUR STUR CBZ B e responda Quais instruções não operam corretamente se o sinal de controle MemWrite apresenta a falha Stuckat0 Justifique sua resposta Para uso do professor 3c 0 1 2 3 4 5 6 7 8 9 10 Apenas a instrução STUR Com uma falha Stuckat0 do sinal MemWrite o valor a ser armazenado pela instrução STUR não será escrito na memória de dados c 05 ponto O que faz a instrução que aparece na linha 1 Mostre uma outra forma de se obter o mesmo resultado Para uso do professor 2c 0 1 2 3 4 5 Zera o conteúdo do registrador X0 Outra forma SUB X0 X0 X0 ou AND X0 X0 XZR d 05 ponto O que faz a instrução que aparece na linha 2 Mostre uma outra forma de se obter o mesmo resultado Para uso do professor 2d 0 1 2 3 4 5 Copia o valor do registrador X0 para o registrador X1 Outra forma ORR X1 X0 XZR e 05 ponto Qual a finalidade da instrução na linha 6 Para uso do professor 2e 0 1 2 3 4 5 Encerrar o loop se X3 for igual a zero f 05 ponto Se a instrução ADDI estivesse disponível como esse programa poderia ser melhorado Para uso do professor 2f 0 1 2 3 4 5 Não seria necessário armazenar a constante 08h na memória A instrução na linha 4 poderia ser ADDI X0 X0 8