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

Análise algoritmica

* Utilizar metodologias  e/ou técnicas de análise de desempenho de algoritmos com o objetivo de:

→prever a sua performance temporal e espacial
→comparar algoritmos entre si
→estabelecer garantias de desempenho
→perceber a base teórica subjacente
→evitar bugs de performance

Abordagem empírica

1)variar o tamanho dos dados da entrada n(regra :aumentar o tamanho n, multiplicando o por 2)
2)medir para cada valor de n, o tempo do algoritmo
3)tentar encontrar a lei (função) matemática que melhor se afasta aos dados. Para isso aplica-se regressão LINEAR aos dados log-log

Multiplicidade

* Os relacionamentos têm uma multiplicidade, que especifica o número de elementos de cada entidade que participam neles

Exemplo anterior:
- Sabe -se que um aluno só se pode inscrever em um só um "curso"
- Sabe-se que num "curso" se podem inscrever nenhum ou N alunos

Modelo E R

Modelo E R

* Representa apenas aspectos estáticos( entidades , os seus relacionamentos e a as propriedades de ambas)
* Destina-se a melhorar o conhecimento do utilizador sobre os dados

Entidade: qualquer objecto indentificavel , por exemplo: aluno,curso, cliente....

Propriedade: é informação/dado sobre uma dada entidade, como por exemplo: idade, nome, morada,...

Relacionamento: entidade que serve para ligar dias ou mais entidades, como por exemplo: frequenta, tem....

* Existe um relacionamento "inscrito" entre as entidade "aluno" e "curso"

* Esse relacionamento é caracterizado pelo atributo "data"

* As entidades "aluno" e "curso" têm os atributos mostrados

Blogs

Venho com uma nova categoria no meu blog.

Em vez de só criar post relacionados com apontamentos sobre o meu curso(Engenharia Informática), decide que também é preciso divulgar novos blogs na minha área de eleição(Informática) e porque não começar com o Blog: "Pegada Digital" http://daft-hferreira.blogspot.pt/ .

O Blog "Pegada Digital" é um blog relacionado com área da informática mas com algumas pequenas curiosidades, também como alguns apontamentos de conteúdos relacionados com a Informática.

O Blog/Site "FU2ion" http://fu2ion.azurewebsites.net/é um site  de entretenimento sobre diversas áreas, com foco na área das Novas Tecnologias.

Por enquanto são estes blogs que eu tenho conhecimento. Mas gostava que vocês deixa-sem em comentário mais blogs/sites para eu fazer a sua divulgação. É desta maneira que todos nós conseguimos manter actualizados.

Gestor de Processos

Um processo pode executar-se no processador ou á espera de ter possibilidade de se executar. O ciclo de vida dos processos vai evoluir desde a sua criação por três estados fundamentais: o primeiro corresponde a deter o processador e portanto, estar em Execução; quando o processo não se pode executar por não ter acesso ao processador está no estado Executável. O terceiro estado, Bloqueado, corresponde a um situação diferente em que o processo mesmo que tivesse o processador não poderia avançar porque uma condição lógica o impedia (já anteriormente nos apareceram funções que esperam pela terminação de outro processo e situações em que um processo se bloqueia á espera de um acontecimento).

·         Em execução- Processo a usar o processador

·         Executável- Processo que pode prosseguir a sua execução e que tal necessita que lhe seja atribuído processador

·         Bloqueado- Processo que espera um acontecimento que enquanto não ocorrer o impede de continuar a executar-se.

As transições entre os três estados correspondem aos seguintes acontecimentos:

·         Executável-> Em execução- O processo foi seleccionado para execução pelo despacho porque é mais prioritário do que o processo corrente ou porque este ultimo deve abandonar o processador (terminou ou bloqueou-se)

·         Em execução-> Executável- Um outro processo na lista dos executáveis tem maior prioridade e o despacho efetua a comutação

·         Em execução-> Bloqueado- O processo tem de interromper a sua execução porque espera um acontecimento sem o qual não pode continuar a executar o respectivo programa.

·         Bloqueado-> Executável- O acontecimento que mantinha o processo bloqueado ocorreu e este passa novamente a poder executar-se. Passa para a lista de executáveis, podendo, se for o mais prioritário, passar de seguida a executar-se ou mais tarde quando for seleccionado pelo despacho.

Quatro objectivos diferentes relacionados com este tipo de gestão:

·         Optimizar a produtividade do sistema, executando o maior numero de programas possível num dado período de tempo (determinado throughput do sistema);

·         Procurar equilibrar a carga do sistema de forma a dar um serviço relativamente uniforme aos diversos clientes;

·         Dotar o sistema de grande reactividade as condições externas;

·         Minimizar o tempo médio para completar a execução de vários programas