LU1

Admita um processador em pipeline semelhante ao MIPS, mas com 4
andares de execução, como se indica na figura a seguir.
Carlos Sêrro – Maio de 2007

Enunciado
IF
4-nov-15
ID
BR
EX1
EX2
ME1
EX3
ME2
Arquitectura de Computadores 2004/05
EX4
WB
Exercício LU1 - 1
LU1

Carlos Sêrro – Maio de 2007



Enunciado (cont.)
Admita ainda que existe forwarding total para as instruções que não
necessitam de 4 ciclos de execução, e que as instruções que nos vão
interessar neste problema exigem os seguinte número de ciclos de
execução:
• Multiplicação em vírgula flutuante – 4 ciclos
• Adição em vírgula flutuante – 2 ciclos
• Operação com inteiros – 1 ciclo
Admita ainda que existe um “branch delay slot”, que não existe
latência entre as operações com inteiros e as operações de branch que
delas dependem, e que a latência para os pares de instruções (LoadUtilizador do Load) é de 2 ciclos --- por outras palavras, o número de
delay slots para os Loads é igual a 2.
Pretende-se fazer correr o seguinte código neste pipeline, que calcula
o produto interno de dois arrays de números em vírgula flutuante com
32 bits.
4-nov-15
Arquitectura de Computadores 2004/05
Exercício MI1 - 2
LU1
Enunciado (cont.)

Carlos Sêrro – Maio de 2007
Prod:


L.D
L.D
MUL.S
ADD.S
ADDI
ADDI
ADDI
BNE
NOP
F5,0(R1)
F6,0(R2)
F7,F5,F6
F4,F4,F7
R1,R1,4
R2,R2,4
R3,R3,-1
R3,R0,Prod
;
;
;
;
;
;
carrega elem. do primeiro array
carrega elem. do segundo array
multiplica os elementos
acumula resultado em F4
incrementa ponteiro
incrementa ponteiro
; fecha o ciclo
; branch delay slot
Admita que R1 e R2 contêm os endereços iniciais dos arrays, e que F4
foi inicializado a 0.
1. Quantos ciclos dura a execução de uma iteração, se não alterar o
código?
4-nov-15
Arquitectura de Computadores 2004/05
Exercício LU1 - 3
LU1

Carlos Sêrro – Maio de 2007



Enunciado (cont.)
2. Modifique o código, por forma a obter o menor número possível de
ciclos de execução. Não desdobre os ciclos (isto é, não faça “loop
unrolling”). Mostre o código que resulta desse escalonamento. Quantos
ciclos dura agora a execução de uma iteração?
3. Faça agora um único desdobramento do ciclo. Faça o escalonamento
por forma a eliminar completamente os stalls. Escreva o código
resultante. Quantos ciclos dura agora a execução de uma iteração?
4. Se desdobrar o ciclo 8 vezes, quantos ciclos por iteração se
conseguem? Nota: não precisa de escrever o código que resulta do
desdobramento, nas precisa de justificar a sua resposta.
4-nov-15
Arquitectura de Computadores 2004/05
Exercício MI1 - 4
MI1 [adaptado de AQA3e – 3.16, pág. 294]
Resolução
•
1. 14 ciclos: 9 das instruções, mais 2 stalls antes dos MUL.S, e
ainda 3 stalls antes do ADD.S
Prod:
Carlos Sêrro – Maio de 2007

4-nov-15
L.D
L.D
NOP
NOP
MUL.S
NOP
NOP
NOP
ADD.S
ADDI
ADDI
ADDI
BNE
NOP
F5,0(R1)
F6,0(R2)
; carrega elem. do primeiro array
; carrega elem. do segundo array
RAW - 2 ciclos L.D-Utilizador
F7,F5,F6
; multiplica os elementos
RAW - 4 ciclos de execução do MUL.S
WB no 4º ciclo
leitura de F7 no mesmo ciclo pelo ADD.S
F4,F4,F7
R1,R1,4
R2,R2,4
R3,R3,-1
R3,R0,Prod
; acumula resultado em F4
; incrementa ponteiro
; incrementa ponteiro
; fecha o ciclo
; branch delay slot
Arquitectura de Computadores 2004/05
Exercício MI1 - 5
LU1
Resolução (cont.)
•
2. 9 ciclos/iteração: 8 das instruções, mais 1 stall antes do BNE.
ADD.S no branch delay slot
Prod:
Carlos Sêrro – Maio de 2007

4-nov-15
L.D
L.D
ADDI
ADDI
MUL.S
ADDI
NOP
BNE
ADD.S
F5,0(R1)
F6,0(R2)
R1,R1,4
R2,R2,4
F7,F5,F6
R3,R3,-1
R3,R0,Prod
F4,F4,F7
;
;
;
;
carrega elem. do primeiro array
carrega elem. do segundo array
incrementa ponteiro
incrementa ponteiro
2 ciclos L.D-Utilizador
4 ciclos de execução do MUL.S
; no branch delay slot
Prod: L.D
L:D
NOP
NOP
MUL.S
NOP
NOP
NOP
ADD.S
ADDI
ADDI
ADDI
BNE
NOP
Arquitectura de Computadores 2004/05
F5,0(R1)
F6,0(R2)
F7,F5,F6
F4,F4,F7
R1,R1,4
R2,R2,4
R3,R3,-1
R3,R0,Prod
Exercício LU1 - 6
LU1

Resolução (cont.)
•
3. 12 instruções, sem stalls em 2 iterações  6 ciclos/iteração
Carlos Sêrro – Maio de 2007
Prod:
4-nov-15
L.D
L.D
L.D
L.D
MUL.S
ADDI
MUL.S
ADDI
ADD.S
ADDI
BNE
F5,0(R1)
F6,0(R2)
F8,4(R1)
F9,4(R2)
F7,F5,F6
R1,R1,8
F10,F8,F9
R2,R2,8
F4,F4,F7
R3,R3,-2
R3,R0,Prod
;
;
;
;
carrega
carrega
carrega
carrega
elem.
elem.
outro
outro
do primeiro array
do segundo array
elem. do prim. array
elem. do segundo array
; fecha o ciclo
ADD.S
F4,F4,F10
; acumula resultado em F4
; incrementa ponteiro
; incrementa ponteiro
; acumula resultado em F4
Arquitectura de Computadores 2004/05
Exercício
Exercício LU1
MI1 - 7
LU1
Carlos Sêrro – Maio de 2007

Resolução
•
4. Uma iteração possui 4 instruções efectivas (não contando com o
overhead do ciclo): duas L.D, uma MUL.S e uma ADD.S. O
overhead é constituído por 4 instruções (três ADDI e um BNE),
que se podem distribuir pelas 8 iterações. Temos, portanto, 4*8+4
= 36 ciclos/8 iterações ou 4,5 ciclos/iteração.
4-nov-15
Arquitectura de Computadores 2004/05
Exercício LU1 - 8