degreeStuff
Aula 17/12/2021
CODV2 EX.6.7:
Consider the following portions of two different programs running at the same time on four processors in a symmetric multicore processor (SMP). Assume that before this code is run, both x and y are 0.
1. What are all the possible resulting values of w, x, y, and z? For each possible outcome, explain how we might arrive at those values. You will need to examine all possible interleavings of instructions.
R:
| x | y | w | z | ordem | | | x | y | ordem |
|---|---|---|---|---|---|---|---|---|
| 2 | 2 | 5 | 4 | core 1, core 2, core 3, core 4 | | | 2 | 5 | 1-2 |c1 c21 c22 |
| 2 | 2 | 1 | 0 | core 4, core 3, core 2, core 1 | | | 2 | 1 | 2-1 | c21 c22 c1 |
| 2 | 2 | 5 | 4 | core 1, core 2, core 4, core 3 | | | 2 | 3 | codico* |
| 2 | 2 | 1 | 4 | core 3, core 1, core 2, core 4 | | | c21 cc1 c22 | ||
| 2 | 2 | 3 | 2 | core 1, core 4, core 3, core 1 | | | |||
| 2 | 2 | 5 | 0 | core 2, core 2, core 1, core 3 | | | |||
| 2 | 2 | 1 | 2 | core 3, core 1, core 4, core 2 | | | |||
| 2 | 2 | 3 | 4 | core 2, core 3, core 1, core 4 | | | |||
| 2 | 2 | 3 | 0 | core 4, core 2, core 3, core 1 | | | |||
| 2 | 2 | 5 | 2 | core 1, core 4, core 2, core 3 | | |
Info:
C1-> x=2;
C21-> y=x+1;
C22-> y=y+x;
lw t0,x
addit0,t0,1
lw t1,x
add t0,t0,1
sw t0,y
--2:
addi t0,t0,1
sw t0, x
2. How could you make the execution more deterministic so that only one set of values is possible?
25. Pretende-se implementar um mecanismo para a sincronização de processos num sistema multiprocessador RISC-V de memória partilhada, que permita garantir que nenhuma thread do programa continua a execução, para lá de um ponto de sincronização, até todas as threads terem alcançado esse ponto. A base desse mecanismo é uma função espera que todas as threads devem invocar no ponto de sincronização.
As versões C e RISC-V da implementação proposta para a função são apresentadas abaixo. O valor inicial da variável (global partilhada) faltam é o número de threads que devem sincronizar naquele ponto.
void espera()
{
faltam = faltam - 1;
while (faltam > 0)
;
}
espera: lw t0, faltam
addi t0, t0, -1
sw t0, faltam
testa: beq t0, zero, fim
lw t0, faltam
jal zero, testa
fim: jalr zero, 0(ra)
a. Explique a razão por que a implementação proposta pode não funcionar como se pretende. Exemplifique usando duas threads e 2 como valor inicial de faltam.
R:
| t | CPU A | t0 | CPU B | t0 | faltam |
|---|---|---|---|---|---|
| 0 | - | ? | - | ? | 2 |
| 1 | lw t0,faltam | 2 | - | ? | 2 |
| 2 | addi t0,t0,1 | 1 | - | ? | 2 |
| 3 | sw t0,faltam | 1 | - | ? | 1 |
| 4 | beq t0,zero,fim | 1 | lw t0,faltam | 1 | 1 |
| 5 | lw t0,faltam | 1 | addi t0,t0,-1 | 0 | 1 |
| 6 | jal zero,0(ra) | 1 | sw t0,faltam | 0 | 0 |
Solução:
| t | CPU A | t0 | CPU B | t0 | faltam |
|---|---|---|---|---|---|
| 0 | - | ? | - | ? | 2 |
| 1 | lw t0,faltam | 2 | ? | 2 | |
| 2 | addi t0,t0,-1 | 1 | lw t0,faltam | 2 | 2 |
| 3 | sw t0,faltam | 1 | addi t0,t0,-1 | 1 | 1 |
| 4 | beq t0,zero,fim | 1 | sw t0,faltam | 1 | 1 |
| 5 | lw t0,faltam | 1 | beq t0,zero,fim | 1 | 1 |
| 6 | jal zero,testa | 1 | lw t0,faltam | 1 | 1 |
| 7 | beq t0,zero,fim | 1 | jal zero, testa | 1 | 1 |
| 8 | lw t0,faltam | 1 | beq t0,zero,fim | 1 | 1 |
b. Apresente uma versão RISC-V que tenha o efeito pretendido.
R:
espera: lrw t0, faltam
addi t0, t0, -1
srw t0, faltam
testa: beq t0, zero, fim
lrw t0, faltam
jal zero, testa
fim: jalr zero, 0(ra)
RP:
espera: lrw t0, faltam
addi t0, t0, -1
srw t1, t0, faltam
beq t1, zero, espera
testa: beq t0, zero, fim
lw t0, faltam
jal zero, testa
fim: jalr zero, 0(ra)
c. Supondo que a execução decorre, enquanto possível, como na alínea a, mostre o que acontece durante a execução do novo código.
| t | CPU A | t0 | t1 | CPU B | t0 | t1 | faltam | marca |
|---|---|---|---|---|---|---|---|---|
| 0 | - | ? | - | ? | 2 | |||
| 1 | lrw t0,faltam | 2 | - | ? | 2 | |||
| 2 | addi t0,t0,-1 | 1 | lw t0,faltam | 2 | 2 | |||
| 3 | sw t0,faltam | 1 | addi t0,t0,-1 | 1 | 1 | |||
| 4 | beq t0,zero,fim | 1 | sw t0,faltam | 1 | 1 | |||
| 5 | lw t0,faltam | 1 | beq t0,zero,fim | 1 | 1 | |||
| 6 | jal zero,testa | 1 | lw t0,faltam | 1 | 1 | |||
| 7 | beq t0,zero,fim | 1 | jal zero, testa | 1 | 1 | |||
| 8 | lw t0,faltam | 1 | beq t0,zero,fim | 1 | 1 |