MIPS: Addressing and Decisions( Endereçamento e decisões)

Decisions in MIPS (decisões)


Instruction for decisions in MIPS( instruções de decisão) :

*  beq registo1, registo2, L1
*  beq means "branch if equal"

Same as (C): 
  if ( registo1== registo2) goto L1

Instruction supplementary decision in MIPS(Instrução de decisão complementar):

* bne registo1, registo2, L1
* bne means “branch if not equal”

Same as (C): 
  if ( registo1 != registo2) goto L1

"Goto" statement in MIPS(instrução "goto"):

It is the jump instruction ("jump") jumps directly to "label" indicated 

without checking any condition.

For example:

In C:

if (i == j) f=g+h; 

else f=g-h; 

 pseudo instruction                MIPS

if(condicion) goto TRUE;    beq $S3,$S4,TRUE
Code FALSE;                     sub $S0,$S1,$S2
goto NEXT;                         j NEXT
TRUE code TRUE;          TRUE
                                           add $S0,$S1,$S2
NEXT:                               NEXT


Another example:

In C:

do { 
g = g + A[i]; 
i = i + j;

} while (i != h); 

where g,h,i,j,base of A, $s1, $s2, $s3, $s4, $s5

pseudo instruction:

LOOP:  g=g+A[i]
             i=i+j;
             if(i!=h) goto LOOP;


MIPS:

LOOP : sll $St1,$S3,2 # St1=4*I
             //Construction of the vector
             add $t1,$t1,$S5  #St1=addr A[i] (address position for A[i])
              lw $t1,0($t1) # $t1=A[i]
             add $S1,$S1,$t1 # g= g+A[i]
             add $S3,$S3,$S4 # i=i+j
             bne $S3,$S2,LOOP # goto LOOP
                                               # if(i!=h)

Análise de complexidade algoritmica

Razões para análise algorítmica:
→prever o seu desempenho (performance)
→comparar algoritmos
→estabelecer garantias para o algoritmo (T(N)<=Tmax)
T(N)=tempo de execução dum algoritmo com input size=N
→perceber a base teórica subjacente
→evitar bugs de performance

Técnicas algorítmicas:
→dividir e conquistar
→programação dinâmica

Exemplo:
Procurar um valor num determinado vector
Int procuraValor (Int *v,Int n, Int val)
{Int i;
    For(i=0;i<n;i++)
       If(v[i]==val)
            Return i;
Return -1;
}

Num algoritmo com tamanho de n dados ,temos 3 situações:

→melhor caso(best case ): situação mais favorável em termos de configuração dos dados na entrada T(N)=B(N)
→pior caso (worst case): situação mais desfavorável T(N)=W(N)
→caso médio (average case): e determinado estatisticamente o número médio de operações básicas T(N)=A(N)

Int s=0; // está instrução e executada 1 vez
For(i=0;i<n;i++)
S=+v[i] Única Instrução que acede ao vector(modelo de custo usado nesta análise poderia por exemplo: considerar apenas as instruções se acesso ao vector(ler ou escrever))

estas instruções são executadas n vezes