CLASSIFICASSÃO DE FLYNN

Taxonomia de Flynn

Introdução ao Processamento Paralelo e de Alto Desempenho

CLASSIFICAÇÃO DE  FLYNN

PARA ARQUITETURAS PARALELAS DE COMPUTADORES

01.  SISD

Na classe SISD (Single Instruction,  Single Data), um único fluxo de instruções atua  sobre um único fluxo de dados.

Corresponde ao tradicional modelo Von Neumann. Um

processador executa seqüencialmente um conjunto de instruções sobre um conjunto de dados.

Exemplo:

-  Computadores com um processador (PC’s e Mainframes).

02.            SIMD

 Na classe SIMD (Single Instruction, MultipleData), uma única instrução é  executada ao mesmo tempo sobre múltiplos dados.

   Envolve múltiplos processadores (escravos) sob o co

ntrole de uma única unidade de controle (mestre) executando simultaneamente a mesma instrução em diversos conjuntos de

dados. Arquiteturas SIMD são utilizadas para manipulação de matrizes e processamento de imagens.

Uma única unidade de controle busca a instrução que

comanda varias unidades aritméticas que executam em paralelo, cada uma delas com seus próprios dados;

Exemplo:

- Arrayde processadores (vetoriais e matriciais) e alguns

supercomputadores;

 03.  MISD

      

Na classe MISD (MultipleInstruction, SingleData), múltiplos

fluxos de instruções atuam sobre um único fluxo de  dados.

Envolve múltiplos processadores executando diferent

es instruções em um único conjunto de dados. Geralmente, nenhuma arquitetura é classificada como MISD, isto é, não existem representantes desta categoria. Alguns autores cons

ideram arquiteturas pipeline como exemplo deste tipo de organização.

04.       MIMD

    Em uma máquina MIMD (Multiple Instruction, Multiple Data),

cada unidade de controle C recebe um fluxo de instruções  próprio  e repassa-o para sua unidade processadora P.

Envolve múltiplos processadores executando diferentes instruções em diferentes conjuntos de dados, de maneira independente. Esta classe engloba a maioria doscomputadores paralelos.

Os sistemas distribuídos estão nesta categoria, ou um conjunto de computadores  independentes, cada um com seu contador de programa, conjunto de instruções e dados.

Esta categoria dividi-se em duas categorias por tipo de memória:

- Memória Compartilhada: Espaço de endereçamento compartilhado;

- Memória Local ou Individual: espaço de endereçame

nto próprio.

RESUMINDO  PODEMOS TER O SEGUINTE RELATO:

MIMD versus SIMD

Ambos os tipos de organizações computacionais apresentam vantagens e desvantagens. Arquiteturas SIMD, por apresentarem fluxo único de instruções, oferecem facilidades para a programação e depuração de programas paralelos. Além disso, seus elementos de processamento são simples, pois são destinados à computação de pequena granulação. Por outro lado, arquiteturas MIMD apresentam grande flexibili

dade para a execução de algoritmos paralelos (arquiteturas SIMD geralmente se destinam a processamento de propósito específico), e apresentam bom desempenho em virtude de seus elementos de processamento serem

assíncronos.

A classificação de Flynn apresenta alguns problemas. Ela não é abrangente o suficiente para incluir alguns computadores modernos (por exemplo, processadores vetoriais e máquinas de fluxo de dados), falhando também, no que concerne a

extensibilidade da classificação. Outro inconveniente desta classificação é a falta de hierarquia. A classificação MIMD, por exemplo, engloba quase todas as arquiteturas paralelas sem a

presentar subníveis. No entanto, apesar de antiga (proposta em 1972), a classificação de Flynn é bastante concisa e a mais utilizada.

A fim de acrescentar novas arquiteturas paralelas

surgidas, sem descartar a classificação de Flynn (visto que esta é muito difundida), Duncan propôs uma classificação mais completa, e que permite apresentar uma visão geral dos estilos

de organização para computadores paralelos

da atualidade.

ARQUITETURA CISC E RISC

Processadores RISC X Processadores CISC

Introdução

Sempre houve uma grande polêmica em torno de qual dessas plataformas é melhor. Na verdade, você já deve ter ouvido muito boatos como "Os Macs são mais rápidos por que tem chips RISC" ou algo do gênero. O objetivo deste artigo é falar um pouco sobre as duas plataformas e como elas coexistem atualmente.

Um processador CISC (Complex Instruction Set Computer, ou "computador com um conjunto complexo de instruções"), é capaz de executar várias centenas de instruções complexas diferentes, sendo extremamente versátil. Exemplos de processadores CISC são o 386 e o 486.

   Na década de 80, a tendência era construir chips com conjuntos de instruções cada vez mais complexos. Alguns fabricantes porém, resolveram seguir o caminho oposto, criando o padrão RISC (Reduced Instruction Set Computer, ou "computador com um conjunto reduzido de instruções"). Ao contrário dos complexos CISC, os processadores RISC são capazes de executar apenas algumas poucas instruções simples. Justamente por isso, os chips baseados nesta arquitetura são mais simples e muito mais baratos. Outra vantagem dos processadores RISC, é que, por terem um menor número de circuitos internos, podem trabalhar a freqüências mais altas. 

RISC e CISC

  A vantagem de uma arquitetura CISC é que já temos muitas das instruções guardadas no próprio processador, o que facilita o trabalho dos programadores, que já dispõe de praticamente todas as instruções que serão usadas em seus programas. No caso de um chip estritamente RISC, o programador já teria um pouco mais de trabalho, pois como disporia apenas de instruções simples, teria sempre que combinar várias instruções sempre que precisasse executar alguma tarefa mais complexa. Seria mais ou menos como se você tivesse duas pessoas, uma utilizando uma calculadora comum, e outra utilizando uma calculadora cientifica. Enquanto estivessem sendo resolvidos apenas cálculos simples, de soma, subtração, etc. quem estivesse com a calculadora simples poderia até se sair melhor, mas ao executar cálculos mais complicados, a pessoa com a calculadora científica disporia de mais recursos.

RISC x CISC        

    Máquinas CISC (Complex Instruction Set Computer) têm um conjunto de instruções grande, de tamanhos variáveis, com formatos complexos. Muitas dessas instruções são bastante complicadas, executando múltiplas operações quando uma única instrução é dada (por exemplo, é possível realizar um loop complexo usando apenas uma operação assembly). O problema básico com máquinas CISC é que um conjunto pequeno de instruções complexas torna o sistema consideravelmente mais lento. Os projetistas decidiram retornar a uma arquitetura mais simples, delegando ao compilador a responsabilidade de produzir código eficiente com esse novo conjunto de instruções. Máquinas que utilizam esta filosofia são chamadas de máquinas RISC.
     A arquitetura RISC (Reduced Instruction Set Computer), como o próprio nome já diz, tem como principal objetivo simplificar as instruções de modo que elas possam ser executadas mais rapidamente. Cada instrução executa apenas uma operação, que são todas do mesmo tamanho, tem poucos formatos, e todas as operações aritméticas devem ser executadas entre registradores (dados da memória não podem ser utilizados como operandos). Praticamente todos os conjuntos de instruções (para qualquer arquitetura) lançados desde 1982 têm sido RISC, ou alguma combinação entre RISC e CISC.
    Membros da família x86 de arquitetura Intel são conhecidos como máquinas CISC, enquanto que a família Pentium e processadores MIPS são conhecidos como máquinas RISC.
Vamos montar uma tabela com as principais diferenças entre as arquiteturas. Isto deveria ser suficiente para responder a maioria das questões de concurso sobre o assunto.

RISC	CISC
Múltiplos conjuntos de registradores, muitas vezes superando 256	Único conjunto de registradores, tipicamente entre 6 e 16 registradores
Três operandos de registradores permitidos por instrução (por ex., add R1, R2, R3)	Um ou dois operandos de registradores permitidos por instrução (por ex., add R1, R2)
Passagem eficiente de parâmetros por registradores no chip (processador)	Passagem de parâmetros ineficiente através da memória
Instruções de um único ciclo (ex. load e store)	Instruções de múltiplos ciclos
Controle hardwired (embutido no hardware)	Controle microprogramado
Altamente paralelizado (pipelined)	Fracamente paralelizado
Instruções simples e em número reduzido	Muitas instruções complexas
Instruções de tamanho fixo	Instruções de tamanho variável
Complexidade no compilador	Complexidade no código
Apenas instruções load e store podem acessar a memória	Muitas instruções podem acessar a memória
Poucos modos de endereçamento	Muitos modos de endereçamento

FORMAS DE EXECUÇÃO DE PROGRAMAS

O que é : Tradução, Compilação  e  Interpretação.

Execução de programas 

Um programa de computador não é escrito em uma linguagem que a máquina entende, por isso é necessário haver uma tradução do programa para a linguagem binária. 

1) Montagem (Assembler = Montador)

Tradução de um programa em linguagem de montagem (código fonte) para linguagem binária (código objeto).

O programa que faz a tradução é o montador (ou Assembler)

Funções básicas: 

• Examinar a correção de cada instrução
• Substituir códigos de operações simbólicos por valores numéricos
• Substituir nomes simbólicos de endereços por valores numéricos
• Converter valores de constantes para binários
• Reservar espaço de memória para armazenamento de instruções e dados

2 ) Compilação

Traduz o programa-fonte escrito em linguagem de alto nível (linguagem fonte) para o programa-objeto escrito, por exemplo, em linguagem de máquina (binária). Pode-se gerar um programa intermediário no meio do processo escrito em Assemply, por exemplo.

O tempo para realizar esta tarefa é chamado tempo de compilação. Em seguida executa o programa-objeto. O tempo para realizar esta tarefa é chamado tempo de execução.

O programa que faz a tradução é o compilador.

Compilador executa duas funções básicas: análise e síntese

Análise:

• Análise léxica: decompõe o programa fonte em seus elementos individuais distintos e verifica se estão de acordo com as regras da linguagem
  (ex: associa strings de caracteres a comandos, operadores, variáveis,....)
  Resultado: conjunto de tokens
  
  
• Análise sintática: cria as estruturas para os comandos e verifica a correção das estruturas (ex: tem int antes de main, tem abre e fecha parênteses)
  Resultado: árvore sintática representando a estrutura do programa

• Análise semântica: verifica as regras semânticas estáticas da linguagem (ex: estar atribuindo valores do tipo correto para uma variável: Parcela1=1.5, poderia dar erro pois variável Parcela1é do tipo int)

Síntese: gera o programa-objeto 

• Geração de código: gera o programa-objeto

• Otimização de código: tenta tornar o programa-objeto mais eficiente

Exemplo de linguagem compilada: C, Pascal

Montagem x Compilação:

Diferença está na complexidade. Na montagem existe uma relação 1:1 entre o código na linguagem de montagem e o código na linguagem de máquina. Já na compilação a relação é múltipla, cada instrução do código fonte gera múltiplas instruções no código de máquina.

3) Ligação ou link-edição

Algumas rotinas já existem codificadas no sistema, por exemplo, rotinas para entrada e saída de dados, de modo que o programador não precisa codificá-las.

 
Exemplo: printf(), readln(), rotinas matemáticas como seno e coseno.

 
Estas rotinas são armazenadas em bibliotecas que são incluídas no código objeto gerado pelo compilador.

 
Para que o código da subrotina externa seja anexado ao código objeto utiliza-se o processo de ligação. Este processo examina todo o código objeto e procura por referências externas não resolvidas assinaladas pelo compilador.

 
Ele procura pela rotina no sistema e se a encontra, inclui seu código no código objeto, caso contrário, gera uma mensagem de erro.

4) Interpretação

A partir do código fonte realiza as três fases (compilação, ligação e execução) comando a comando. Lê uma instrução, compila, liga e executa. Depois lê a próxima instrução e faz os mesmos 3 passos.

O programa executa estas três fazes é o interpretador.

Exemplo de linguagem interpretada: Java

Compilação X Interpretação

Tempo de execução:

É maior no na interpretação pois cada vez que o programa é executado, o interpretador executa as três fases. Já o compilador é só executar o programa-objeto já gerado na primeira vez.

Consumo de memória:

O interpretador precisa permanecer na memória durante todo o tempo de execução. Já o compilador fica na memória somente durante o tempo de compilação. Quando o programa é executado, somente o programa-objeto fica na memória.

Repetição da interpretação:

Sempre que um programa for utilizado, terá que ser interpretado novamente. Isso é um problema para os programas que são muito utilizados.

No caso de loops, cada instrução do loop é interpretada em todos os passos do loop. No caso da compilação, a tradução para código-objeto ocorre só uma vez pois o loop não e executado enquanto a tradução é feita.

Por tanto, o método de interpretação torna-se mais lento que o de compilação.

Detecção de erros:

No método de compilação, a identificação de erros durante a fase de execução fica sempre difícil, pois não há mais relação entre comandos do código fonte e instruções do executável.

 
No método de interpretação, cada comando é interpretado e executado individualmente, a relação entre código fonte e executável é mais direta e o efeito da execução (certa ou errada) é direta e imediatamente sentido.

Por tanto, erros são detectados de forma mais fáci

EQUAÇÃO DO 3º GRAU : DICAS PARA SOLUÇÃO

Como Resolver Equações do

Terceiro Grau através da Fatoração

 

Equações do terceiro grau possuem a forma de

                 "f(x) = Ax³ + Bx² + Cx + D"

onde A é diferente de zero. Encontrar variáveis através da fatoração é um dos modos mais eficientes de simplificar seu problema. Além disso, determinar variáveis do terceiro grau é algo difícil de se fazer. Entretanto, com esta abordagem para resolver problemas de fatoração do terceiro grau, você não terá dificuldade em resolver outros no futuro.

 

Instruções

1.       Analise o polinômio cúbico claramente. Por exemplo, a equação é:

                "f(y) = 12y³- 30y - 5 + 2y²".

2.      Rearranje os termos do expoente mais alto até o mais baixo. A equação ficará:

                "f(y) = 12y³+ 2y² - 30y - 5".

3.      Divida a equação em dois grupos. No exemplo,

       "12y³ + 2y² - 30y - 5" = "(12y³+ 2y²) - (30y + 5)".

4.      Simplifique encontrando o fator em comum. Nesta equação, não existe um fator comum absoluto, embora o primeiro parênteses tenha o fator comum de "(2y^2)", e o segundo parênteses tenha o fator comum de "5". Isto resulta em uma equação da forma:

                   "2y²(6y + 1) - 5(6y + 1)".

5.       Deixe em evidência os termos em comum, que são    "(6y + 1)".

   A nova equação é

                      "(6y + 1)(2y² - 5)".

Estes termos são as raízes cúbicas da função

                 "f(y) = 12y³ + 2y²- 30y - 5".

 

 

TABELA DOS GRAUS E QUADRANTES

DERIVADAS E INTEGRAIS

   PRINCIPAIS FÓRMULAS DE DERIVAÇÃO E INTEGRAÇÃO

MEMÓRIA PRINCIPAL

Cálculos -  Capacidade da Memória Principal ( MP )

01.  Definições Importantes

a.   A memória principal é organizada em um conjunto de N

      células, cada uma podendo armazenar um quantidade M

      de bits;

b.   N = a capacidade da memória, dada pela quantidade  de

       células ou de endereços que a memória possui;

c.   M quantidade de bits que podem ser armazenados  em uma

      célula.

      Obs.:   Esses bits representam a informação em si, seja uma

           Instrução ( ou parte dela ) ou um dado ( ou parte dele );

d.   E = quantidade de bits ( ou tamanho ) de cada endereço;

e.   T = total de bits que podem ser armazenados na memória.

                                                                                               M

f.    Pode-se armazenar em cada célula um valor entre 0 e 2    - 1.

                M

      São  2       combinações possíveis;

                                            8

g.   Se  M = 8 bits, tem-se 2    = 256. Logo é possível armazenar

      valores de:

   00000000 ( 0     ou  0  )  até   11111111 (  255     ou  FF    ).

                         10        16                                   10           16

h.   A capacidade da memória principal é dada  por:

                                     E

                           N = 2           .

i.    O total de bits que podem ser armazenados na MP é dado por:

                                        T = N x M    ,

onde  por  ( I )  pode-se escrever:

                           E

                  T = 2     x   M

Exercícios :

1.   Uma memória principal possui espaço de 512 células, com  8 bits de tamanho.  Quantos bits essa memória é capaz de armazenar.  Em  seguida, verifique quantos bits são necessários para representar cada um dos endereços da memória.

      Solução:

 N  = total de células = 512

 M  =  tamanho da célula = 8 bits

 T   =  total de bits da memória = ?

 E   =  quantidade de bits para representar um endereço = ?

    Temos  que :

 T   =   N  x  M ,    logo vem:

  T = 512 x 8  = 4096 bits =  4 x 1024 bits =  4 K bits.

    Sabemso que :

                 E                                   9

        N = 2       e       N = 512 =  2      ,    logo :

                 9        E

               2   =   2   ,

     Onde podemos concluir que :  E =  9 bits.

OPERAÇÕES QUE OCORREM NUM PC

Escreva a seqüência de microoperações que devem ser realizadas pelo ciclo de execução das seguintes instruções:

a) SUB Op. ACC ACC – (Op.)

Resposta:

t1: REM (RI(Endereço))

t2: RDM Memória

t3: ACC (ACC) - (RDM)

b) JMP Op. CI Op

Resposta:

t1: CI (RI(Endereço))

c) INC Op. (Op.) (Op.) + 1

Resposta:

t1: REM (RI(Endereço))

t2: RDM Memória

t3: ACC (RDM) + 1

t4: RDM ACC

t5: Memória RDM

Considere uma máquina que possa endereçar 512 Mbytes de memória física, utilizando endereço referenciando byte, e que tenha a sua memória organizada em blocos de 32 bytes. Ela possui uma memória cache que pode armazenar 8K blocos, sendo um bloco por linha. Mostre o formato da memória cache, indicando os campos necessários (tag, bloco) e o número de bits para cada campo, e o formato de um endereço da memória principal, indicando os bits que referenciam os campos da cache, para os seguintes mapeamentos:

a) Mapeamento direto.

Resposta:

Como há 16 M blocos na memória principal e 8 K blocos na cache, então cada linha deverá acomodar 2K blocos, um de cada vez, é claro.

Formato da memória cache:

A memória cache terá 8K linhas (ou quadros) em cada linha teremos tag de 11 bits e bloco de 32 bytes.

O endereço da memória principal terá o seguinte formato:

Campo de número do bloco: de 11 bits (para endereçar um dos 2 K blocos)

Campo de número da linha: de 13 bits (já que temos 8 K blocos)

Campo de endereço da palavra: 5 bits (já que temos 32 bytes por bloco)

b) Mapeamento totalmente associativo.

Resposta:

Como há 16 M blocos na MP e eles podem ficar em quaisquer dos 8 K blocos da Cache, temos:

Formato da memória cache:

A memória cache terá 8K linhas (ou quadros), em cada linha teremos tag de 24 bits e bloco de 32 bytes.

O endereço da memória principal terá o seguinte formato:

Campo de número do bloco: de 24 bits (para endereçar um dos 16 M blocos)

Campo de endereço da palavra: 5 bits (já que temos 32 bytes por bloco)

c) Mapeamento associativo por conjunto, onde cada conjunto possui quatro linhas, cada uma de um bloco.

Resposta:

A memória cache neste caso terá um número de conjuntos igual a 8K linhas/ 4 = 2 K. Onde, cada um

dos 16M blocos pode ficar em um dos 2K conjuntos, ou seja, cada conjunto poderá alocar 8K blocos.

Assim, o formato da memória cache será: 2k conjuntos de 4 linhas e cada linha com bloco de 32 K.

O tag da memória cache terá 13 bits e bloco de 32 bytes.

O endereço da MP terá os seguintes campos:

Tag: 13 bits (já que cada conjunto poderá alocar 8K blocos)

Número de conjuntos: 11 bits (já que existem 2K conjuntos)

Endereço da palavra: 5 bits (já que temos 32 bytes por blocos)

FÓRMULAS DE INDETERMINAÇÃO

Formas Indeterminadas

                                              

Aqui estão as sete indeterminações matemáticas:

01.   0/0,

            

02.   ∞/∞,

03.   0 x ∞,

          ∞

04.   1         ,

05.   0° ,

06.   ∞        ,

07.   ∞ − ∞ .

OBSERVAÇÃO:

 Temos dois tipos de divisão por zero: 

- a divisão de um número não nulo por zero;

- a divisão de zero por zero. 

Os representantes protótipos desses tipos são: 

- a divisão 1/0;

- a divisão 0/0.

Essas duas divisões tem natureza bastante distinta:

• a divisão 1/0 é indefinida ou impossível entre os número.
• e a divisão 0/0 é indeterminada. 

Resumo e conclusões:

• a divisão 1/0 é indefinida entre os números, mas pode ser definida como 1/0 = infinito. Se adotarmos essa solução, devemos estar bem cientes que a operação com o infinito provocará resultados absurdos a menos que façamos uma drástica modificação nas regras usuais de cálculo.
   
• a divisão é/0 indeterminada entre os números não nulos, e em especial com a escolha 0/0 = 1; o caminho alternativo 0/0 = 0 leva a resultados não naturais e inconvenientes.