AULA 06 - MIPS PIPELINE

11998 Morgan Kaufmann Publishers

AULA 06 - MIPS

PIPELINE

RegDst Branch

MemWrite

cRegWrite

olALUControl

IMPLEMENTAÇÃO DO MIPS MONOCICLO

BALUOut

PASSOS relativos ao MIPS Multiciclo

Aritmética reg-reg

Branch Step 3

Passo 1: Busca da instrução (Instruction Fetch)

Passo 2: Decod. da Instrução e Busca de Registradores

Passo 3 (dependente da instrução)

Referência à memória: ALUOut = A + sign-extend(IR[15-0]);Aritmética Reg-Reg: ALUOut = A op B;Aritmética Reg-Imm: ALUOut = A op Imm;Branch: se (A==B) PC = ALUOut;

Passo 4 (Aritmética ou acesso à memória)

Acesso à memória através de loads e stores MDR = Memory[ALUOut]; ou Memory[ALUOut] = B;Fim das instruções R-type: Reg[IR[15-11]] = ALUOut;

Passo 5 (Write-back, para instrução load)

Reg[IR[20-16]]= MDR;

PASSOS (CICLOS)

MULTICICLO x PIPELINE

• Pipeline: vários estágios funcionam juntos para instruções diferentes.

• Multiciclo: a instrução é executada em vários estágios (S) sequenciais.

Estágio ATIVO no ciclo 2

S1 S2 Sk

h Latc

S1 S2 Sk

instrução i instrução i - 1 instrução i – (k -1)

Apenas uma instrução por vez.

k instruções por vez.

Pipeline: é natural!

• Exemplo de Lavanderia

• Tem-se os volumes A, B, C e D de roupas para lavar, secar e passar

• A lavadora leva 30 minutos

• A secadora leva 40 minutos

• “Passadeira” leva 20 minutos

A B C D

Lavanderia Sequencial

• A lavanderia sequencial leva 6 horas para 4 volumes

• Se usarem o “pipeline”, quanto tempo levaria?

30 40 20 30 40 20 30 40 20 30 40 20

6 7 8 9 10 11 Meia noite

Lavanderia em Pipeline

• Lavanderia em Pipeline leva 3.5 horas

6 7 8 9 10 11 Meia noite

30 40 40 40 40 20

Lições sobre o Pipeline

• O Pipeline ajuda melhorar o throughput de um trabalho por completo

• A taxa do Pipeline é limitada pelo estágio mais lento

• Speedup ideal = Número de estágios

• Comprimentos desbalanceados dos estágios do pipeline reduzem o speedup

• O tempo para “preencher” o pipeline e o tempo para “limpar” o pipeline reduzem o speedup

6 7 8 9

30 40 40 40 40 20

Pipelines em Computadores

• Executa bilhões de instruções, tal que o importante seja o throughput

• Fatores desejados:

– todas as instruções tenham o mesmo comprimento,

– os campos de registradores sejam localizados numa mesma posição no formato de instrução,

– referências à memória somente através de instruções loads ou stores

• Speedup: para um programa de n instruções, num computador pipeline de k estágios, relativo a um computador multiciclo de k ciclos, considerando mesmo tempo de ciclo.

Tempo do multiciclo = n . k .tempociclo Tempo do pipeline = (k + n-1).tempociclo

Speedup = tempo do multiciclo/tempo do pipeline = n.k/ (k + n - 1)

Para n grande, speedup ~ k

Pipeline no MIPS

multiciclo

pipeline

Implementação do Pipeline

• O que facilita:

– Todas as instruções com mesmo comprimento

– Somente poucos formatos de instruções

– Os operandos de memória aparecem somente em loads e stores

• O que difículta:

– conflitos estruturais: supor que temos somente uma memória

– conflitos de controle: preocupar com instruções de branch

– conflitos de dados: uma instrução depende de uma instrução prévia

– Manipulação de exceções

– Melhorar o desempenho com execução fora-de-ordem, etc.

Idéia Básica

MEM.INSTR.

SOMADOR

MEM.DADOS

SOMADOR

Fluxo de dados com latch’s entre os estágios

IF/ID ID/EX EX/MEM MEM/WB

Mem.Instr.

Regist.

Mem.dados

somador

Pipelines representados graficamente

IM Reg DM Reg

CC 1 CC 2 CC 3 CC 4 CC 5 CC 6

Time (in clock cycles)

lw $10, 20($1)

Programexecutionorder(in instructions)

sub $11, $2, $3

MemRead

MemWrite

ALUSrc

RegWrite

RegDst

MemtoReg

Mem.Inst.

Mem.dados

CONTROLE DO PIPELINE

• O que necessita ser controlado em cada estágio?

– Busca de Instrução e Incremento do PC– Decodificação da Instrução / Busca de Registradores– Execução– Estágio de Memória– Write Back

• Cada estágio deve funcionar para uma determinada instrução,

simultaneamente a outros estágios.

Controle do Pipeline

Execution/Address Calculation stage control lines

Memory access stage control lines

Write-back stage control

InstructionReg Dst

ALU Op1

ALU Op0

ALU Src Branch

Mem Read

Mem Write

Reg write

Mem to Reg

R-format 1 1 0 0 0 0 0 1 0lw 0 0 0 1 0 1 0 1 1sw X 0 0 1 0 0 1 0 Xbeq X 0 1 0 1 0 0 0 X

IF/ID ID/EX EX/MEM MEM/WB

Os sinais são repassados pelos estágios como os dados

RegDst

MemWrite

Fluxo de dados e controle

• Pode ocorrer iniciando uma instrução antes de terminar a anterior

• dependências que “vão retroceder no tempo” são conflitos de dados

Dependências de dados

IM Reg

sub $2, $1, $3

and $12, $2, $5

IM Reg DM Reg

IM DM Reg

CC 7 CC 8 CC 9

10 10 10 10 10/– 20 – 20 – 20 – 20 – 20

or $13, $6, $2

add $14, $2, $2

sw $15, 100($2)

Value of register $2:

DM Reg

- Atuar no caminho do banco de registr. p/ substituir o valor de leit/escrita de registrador

- Antecipação da ALU

Solução por Antecipação – usar os resultados temporários, sem esperar que eles sejam escritos

what if this $2 was $13?

IM Reg

sub $2, $1, $3

Programexecution order(in instructions)

and $12, $2, $5

IM Reg DM Reg

IM DM Reg

CC 7 CC 8 CC 9

10 10 10 10 10/– 20 – 20 – 20 – 20 – 20

or $13, $6, $2

add $14, $2, $2

sw $15, 100($2)

Value of register $2 :

DM Reg

X X X – 20 X X X X XValue of EX/MEM :X X X X – 20 X X X XValue of MEM/WB :

Solução por Antecipação

Unidade de antecipação

sub $2,$1,$3and $12,$2,$5

Antecipação do estágio EX/MEM

Seleciona MUXdo lado A

da ALU paraantecipação

Seleciona MUXdo lado B

sub $2,$1,$3

or $13,$6,$2

Antecipação do estágio MEM/WB

Seleciona MUXdo lado A

Seleciona MUXdo lado B

CIRCUITO DE ANTECIPAÇÃO (FORWARDING UNIT)

MUX ASA1

MUX BSB0

MUX ASA0

MUX BSB1

SELEÇÃO DOMUX A

SELEÇÃO DOMUX B

- Se uma instrução tenta ler um registrador seguindo uma instrução de load word que escreve no mesmo registrador.

• Portanto, necessitamos que a unidade de detecção de conflitos paralize, em um ciclo, as instruções seguintes ao load word

Nem sempre é possível solucionar por antecipação (Fazer o Load de uma palavra pode causar um conflito)

lw $2, 20($1)

and $4, $2, $5

IM Reg DM Reg

IM DM Reg

CC 7 CC 8 CC 9

or $8, $2, $6

add $9, $4, $2

slt $1, $6, $7

DM Reg

Parada (Stall) manter instruções nos mesmos estágios

IM Reg DM Reg

DM Reg

Reg DM Reg

IM Reg DM Reg

IM Reg

lw $2,20($1)

and $4,$2,$5

or $8, $2, $8

add $9, $4, $2

slt $1, $6, $7 IM Reg DM Reg

Parada com inserção de nop a partir do estágio EX

Unidade de detecção de conflitos• A parada faz com que uma instrução que não faz nada (nop) prossiga

Exemplo de inserção de parada

sinais 0

• Quando é decidido pelo branch, outras instruções estão em pipeline!

• O pipeline equivale a previsão de “não ocorrer branch”– Solução: hardware para desprezar as instruções posteriores caso haja branch

Conflitos de Desvio (Branch)

40 beq $1, $3, 7

IM Reg

DM Reg

Reg Reg

44 and $12, $2, $5

48 or $13, $6, $2

52 add $14, $2, $2

72 lw $4, 50($7)

CC 2 CC 3 CC 4 CC 5 CC 6 CC 7 CC 8 CC 9

Controle para limpar as instruções posteriores

IFFlush

além de antecipar o cálculo da condição

beq $1,$3,7and $12,$2,$5

Exemplo de beq e atualização do PC

Resulta em NOP

endereço 72 lw $4, 50($7)

RESULTADO DO CONTROLE DE DESVIO

Necessidade de limpar apenas uma instrução

Melhorando o desempenho

• Tentar evitar paradas! P.ex., reordenar essas instruções:

lw $t0, 0($t1)lw $t2, 4($t1)sw $t2, 0($t1)sw $t0, 4($t1)

• Adicionar um “branch delay slot”

– permitindo que a próxima instrução seguida do branch seja sempre executada

– Confiar no compilador para preencher o slot com algo útil

• Processador Superescalar: iniciar mais que uma instrução no mesmo ciclo

MIPS superescalar

Tipo de instrução

Estágios do pipeline

R ou desvio IF ID EX MEM WB

Load/store IF ID EX MEM WB

EXEMPLO

loop: lw $t0, 0 ($s1) # t0 = elemento de array add $t0, $t0,$s2 # soma o elemento do array a um valor escalar em $s2 sw $t0, 0($s1) # armazena o resultado addi $s1, $s1, -4 # decrementa o ponteiro bne $s1, $zero, loop # desvia para loop se $s1 diferente de 0

R ou desvio Load/store Ciclo de clock

loop: lw $t0, 0($s1) 1

addi $s1, $s1,-4 2

add $t0 , $t0, $s2 3

bne $s1, $zero, loop sw $t0, 4($s1) 4

O código:

pode ser escalonado para o MIPS superescalar da seguinte forma:

5 instruções em 4 ciclos

Desdobramento de laço (loop unrolling)

R ou desvio Load/store Ciclo

de clock

Observações

loop: addi $s1, $s1, -16 lw $t0, 0 ($s1) 1 $s1 inicial

lw $t1, 12($s1) 2 $s1 = $s1 - 16

add $t0, $t0, $s2 lw $t2, 8($s1) 3

add $t1, $t1, $s2 lw $t3, 4($s1) 4

add $t2, $t2, $s2 sw $t0, 16($s1) 5 16($s1) =

$s1 inicial

add $t3, $t3, $s2 sw $t1, 12($s1) 6

sw $t2, 8($s1) 7

bne $s1, $zero, loop sw $t3, 4($s1) 8

14 instruções em 8 ciclos

Escalação Dinâmica

• O hardware realiza a “escalação”

– O hardware tenta encontrar instruções para executar

– É possível execução fora de ordem

– Execução especulativa e previsão dinâmica de desvio (branch)

– DEC Alpha 21264: tem 9 estágios pipeline, 6 instruções simultâneas

– PowerPC e Pentium: tabela de história de desvio

– É importante a tecnologia do compilador

Escalação Dinâmica

Despacho em ordem

Execuçãofora de ordem

Unidade de Comprometimento:escrita final do resultado em ordem

Unidadesfuncionais

A microarquitetura do Pentium 4

Multiprocessadores• criar computadores potentes conectando muitos computadores pequenos

Processor

Single bus

Memory I/ONetwork

Processor

Memory Memory Memory

Multiprocessador de memóriacompartilhada centralizada

Multiprocessador de memóriadistribuída

CPU de um único thread

• Thread é uma seqüência de instruções de um programa

RAM - Diferentes cores = quatro diferentes programas em execução na memória

7 Pipelines, sendo apenas o programa de cor vermelhaem execução

Nota-se os espaços em branco dos estágios pipeline ociosos

Front end – busca até 4 instruções

Single Threaded SMP (Symmetric Multiprocessor)

Os diferentes programas são executados em CPUs distintos para não deixar muitos programas em espera.

Programa vermelho numa CPU

amarelo em outra

Superthreading ou multithreading

• CPU com capacidade para executar mais de um thread simultaneamente,

porém, cada estágio do pipeline deve conter instruções de apenas um thread

• Não se pode emitir instruções de threads distintos num mesmo instante

Hyper-threading (HT)Simultaneous multithreading (SMT)

• Não existe restrição de

emissão de instruções

para threads diferentes

em cada clock.

• Compara-se ao single-threaded SMP

Single-threaded SMP

Superscalar SimultaneousMultithreading

Multithreading

Issue slots

s Empty

Thread 1

Thread 2

Thread 3

Thread 4

Formas de Execução dos Threads

Superescalar SMT

Chips de um único CORE

Processadores Multi-Core

• Um único chip com múltiplos cores (CPUs), cada um executando threads distintos como em single-threaded SMP

• Compatível em softare a uma arquitetura SMT porém tecnologicamente mais interessante,

pois usando tecnologia que consome menos energia pode ser usado, e o desempenho aumenta com o número de CORES.

REFERÊNCIAS SOBRE SMT E MULTICORE

• http://arstechnica.com/articles/paedia/cpu/hyperthreading.ars

• http://www.intel.com/cd/ids/developer/asmo-na/eng/211198.htm?page=1

AULA 06 - MIPS PIPELINE

Documents

Sesam Pipeline 2016

Unter Mitarbeit von Thomas Merten MIPS berechnen · PDF filegangsmaterialien beim Design von Artefakten unter Berücksichtigung ihrer ... MIPS steht für Material-Input Pro Serviceeinheit,

Aula Trafo

Pipeline ROU

Aula Organogramasfluxogramas (1)

Pipeline Tendido de Tubería - Lincoln Electric

Michael Wahl Rainer Brück Seite 1 Befehlssatz des MIPS R2000 Prozessors

Augel Pipeline

Aula dezessetepre2015

Aula 02 - Excel

BEDIENUNGSANLEITUNG - pipeline-store.compipeline-store.com/manual/PROEIGHTY/PIPELINE-PRO-EIGHTY-DE.pdf · Der PIPELINE PRO EIGHTY ist ein in Deutschland hergestellter High-End-Akkuträger

MIPs REVOLUTION SYSTEM

Overview Status CMIP6-Endorsed MIPs...Overview Status CMIP6-Endorsed MIPs SLIDES kindly provided by the Co-Chairs of each MIPs – THANKS! Veronika Eyring Deutsches Zentrum für Luft-

03 MIPS-Assembler - userpages.uni-koblenz.deunikorn/lehre/gdra/ss18/03 MIPS... · MIPS unterstützt mit einem separaten FPU‐Coprozessor Gleitkommaarithmetik auf Zahlen im IEEE 754‐Single‐Precision

Deployment pipeline mit maven, chef und jenkins

Die vom Prozessor ausführbaren Befehle · PDF fileDie Maschinenprogrammebene eines Rechners Jörg Roth 273 5.CDie MIPS-Befehle Die MIPS-Befehle orientieren sich an folgenden vier

Aula Profibus

MIPS Poseidon

Aula v youtube

UNIVERSITÄT LEIPZIGjedi.informatik.uni-leipzig.de/de/Vorles/Integration/soa/...Eine Pipeline kann als Service Requester Pipeline oder als Service Provider Pipeline konfiguriert werden,