Somadores e ULA
Vídeo da aula estará disponível em breve
O Somador de 1 Bit
Toda aritmética computacional começa com a operação mais básica: somar dois bits. Existem dois circuitos fundamentais.
O half adder soma dois bits (A e B), produzindo um bit de soma (S) e um bit de carry (C):
Half Adder — Tabela Verdade
Entradas Saídas
A B │ S (Soma) C (Carry)
─────────┼──────────────────────
0 0 │ 0 0
0 1 │ 1 0
1 0 │ 1 0
1 1 │ 0 1
Equações lógicas:
S = A XOR B
C = A AND B
Circuito:
A ──┬──[XOR]── S
│
B ──┼──[AND]── C
│
└──────────┘
Limitação: não aceita carry de entrada.
Só serve para o bit menos significativo (bit 0).O full adder resolve essa limitação: aceita um carry de entrada (Cin) vindo do bit anterior.
Full Adder — Tabela Verdade
Entradas Saídas
A B Cin │ S (Soma) Cout (Carry out)
──────────────┼───────────────────────────────
0 0 0 │ 0 0
0 0 1 │ 1 0
0 1 0 │ 1 0
0 1 1 │ 0 1
1 0 0 │ 1 0
1 0 1 │ 0 1
1 1 0 │ 0 1
1 1 1 │ 1 1
Equações lógicas:
S = A XOR B XOR Cin
Cout = (A AND B) OR (Cin AND (A XOR B))
Implementação com 2 half adders:
Half Adder 1: A, B → S1, C1
Half Adder 2: S1, Cin → S, C2
Cout = C1 OR C2
Custo: 2 XOR + 2 AND + 1 OR = 5 portas lógicasRipple-Carry Adder
Para somar números de N bits, encadeamos N full adders. O carry de saída de cada bit alimenta o carry de entrada do próximo. Este é o ripple-carry adder:
Ripple-Carry Adder — 4 bits
A3 B3 A2 B2 A1 B1 A0 B0
│ │ │ │ │ │ │ │
▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
│ FA │←C3─│ FA │←C2─│ FA │←C1─│ FA │← C0=0
│ │ │ │ │ │ │ │
└──┬───┘ └──┬───┘ └──┬───┘ └──┬───┘
C4 │ S3 │ S2 │ S1 │ S0
▼ ▼ ▼ ▼
C4 = carry final (overflow indicator para unsigned)
Exemplo: 0101 (5) + 0011 (3)
Bit 0: A=1, B=1, Cin=0 → S=0, Cout=1
Bit 1: A=0, B=1, Cin=1 → S=0, Cout=1
Bit 2: A=1, B=0, Cin=1 → S=0, Cout=1
Bit 3: A=0, B=0, Cin=1 → S=1, Cout=0
Resultado: 1000 (8) ✓
Problema: VELOCIDADE
O carry "propaga" bit a bit, da direita para a esquerda.
Para 32 bits: o resultado final só está pronto depois
que o carry passou por TODOS os 32 full adders.
Atraso total = 32 × (atraso de 1 full adder)
Se cada full adder leva 2 gate delays:
32 bits → 64 gate delays — LENTO para processadores modernos!Carry-Lookahead Adder (CLA)
O carry-lookahead adder resolve o problema de velocidade calculando os carries em paralelo, sem esperar a propagação sequencial.
Carry-Lookahead — Conceito
Ideia: para cada bit i, definir dois sinais:
G_i = A_i AND B_i (Generate: este bit GERA carry independente)
P_i = A_i XOR B_i (Propagate: este bit PROPAGA carry de entrada)
Carry pode ser calculado diretamente:
C1 = G0 OR (P0 AND C0)
C2 = G1 OR (P1 AND G0) OR (P1 AND P0 AND C0)
C3 = G2 OR (P2 AND G1) OR (P2 AND P1 AND G0) OR (P2 AND P1 AND P0 AND C0)
C4 = G3 OR (P3 AND G2) OR ... (continua expandindo)
Todas essas expressões dependem APENAS de A, B e C0!
Podem ser calculadas EM PARALELO, em apenas 2 níveis de portas.
Comparação de atraso:
Ripple-Carry (32 bits): 64 gate delays
CLA (32 bits): ~4 gate delays (com agrupamento hierárquico)
Trade-off:
+ Muito mais rápido (O(log N) vs O(N))
- Muito mais hardware (portas AND/OR com muitas entradas)
- Custo cresce rapidamente com N
Solução prática: CLA hierárquico
Usa CLA de 4 bits como bloco básico.
Agrupa 4 blocos de 4 bits para fazer 16 bits.
Agrupa 4 blocos de 16 bits para fazer 64 bits.
Atraso: proporcional a log₄(N).
Na prática
Processadores modernos usam variantes do CLA combinadas com outras otimizações (carry-select, carry-skip). O somador é tão crítico que engenheiros gastam semanas otimizando seus 32 ou 64 bits de circuito.
A ULA: Unidade Lógica e Aritmética
A ULA (ou ALU, Arithmetic Logic Unit) é o componente do processador que executa todas as operações aritméticas e lógicas. Ela recebe dois operandos e um sinal de controle que indica qual operação executar.
ULA MIPS — Operações e Controle
┌─────────────────┐
A (32b) ──▶│ │
│ ULA │──▶ Resultado (32b)
B (32b) ──▶│ │──▶ Zero (1 bit)
│ │──▶ Overflow (1 bit)
ALUOp (4b) ────▶│ │
└─────────────────┘
ALUOp Operação Instrução MIPS
────── ────────────── ──────────────────
0000 AND and, andi
0001 OR or, ori
0010 add add, addi, lw, sw
0110 subtract sub, beq, bne
0111 set on less than slt, slti
1100 NOR nor
1101 XOR xor, xori
Sinais de saída:
Resultado: 32 bits com o resultado da operação
Zero: 1 se Resultado == 0 (usado por beq/bne)
Overflow: 1 se houve overflow (usado por add/sub)
Implementação interna (1 bit da ULA):
ALUOp
│
A ─┬─[AND]─────┐ ┌───┴───┐
│ ├─────│ MUX │──▶ Resultado
B ─┼─[OR]──────┤ │ 4:1 │
│ │ └───────┘
├─[Adder]───┤
│ │
└─[SLT]─────┘
A ULA de 32 bits = 32 cópias desse circuito de 1 bit,
com carry encadeado entre os somadores (CLA para velocidade).Como a ULA Implementa Subtração e SLT
A subtração e a comparação slt reutilizam o somador, aproveitando a propriedade do complemento a 2:
Subtração e SLT na ULA
# Subtração: A - B = A + NOT(B) + 1
# Implementação:
# 1. Inverter B (usando portas NOT)
# 2. Somar A + NOT(B) com Cin = 1
# O mesmo somador faz add E sub! Basta um sinal "Bnegate".
Sinal de controle:
Bnegate = 0 → operação normal (add, AND, OR)
Bnegate = 1 → inverte B e Cin=1 (sub, slt)
# SLT (Set on Less Than): A < B ?
# A - B resulta negativo se A < B.
# O bit de sinal (bit 31) do resultado indica isso.
# slt pega o bit 31 da subtração e coloca no bit 0 do resultado.
Circuito para slt:
1. Calcula A - B (usando o somador com Bnegate=1)
2. Resultado[31] (bit de sinal) → Resultado[0]
3. Resultado[31:1] = 0
4. Mas se houver overflow, o bit de sinal está invertido!
Solução: Resultado[0] = Bit31 XOR Overflow
# Sinal Zero (para beq/bne):
# NOR de todos os 32 bits do resultado.
# Se todos são 0, o resultado é zero.
# beq: desvia se Zero=1 (A == B → A-B == 0)
# bne: desvia se Zero=0 (A != B → A-B != 0)
Reutilização de hardware
Perceba a elegância: add, sub, beq, bne e slt usam todos o mesmo somador. A diferença está nos sinais de controle (Bnegate, ALUOp) e em como o resultado é interpretado. Isso é o princípio RISC levado ao extremo — hardware mínimo, máxima funcionalidade.
Diagrama Completo da ULA de 32 Bits
Diagrama — ULA MIPS 32 bits
Bnegate
│
A[0] ─┐ B[0]─┼─[NOT]─┐
│ │ │
│ ┌────┴────┐ │
│ │ MUX 2:1│───┘ Cin=Bnegate
│ └────┬────┘ │
│ │ │
▼ ▼ ▼
┌─────────────────────────────┐
│ ALU bit 0 │
│ AND / OR / ADD / SLT │──▶ Res[0]
│ │──▶ Cout → Cin do bit 1
└─────────────────────────────┘
...
┌─────────────────────────────┐
│ ALU bit 31 │
│ AND / OR / ADD / SLT │──▶ Res[31]
│ │──▶ Cout (carry final)
│ │──▶ Set (bit sinal → SLT do bit 0)
│ │──▶ Overflow = Cin XOR Cout
└─────────────────────────────┘
Res[31:0] ──▶ [NOR de 32 entradas] ──▶ Zero
Sinais de controle vindos da Unidade de Controle:
ALUOp (4 bits): seleciona operação no MUX interno
Bnegate (1 bit): 0=normal, 1=inverte B e Cin=1
Total de portas para ULA de 32 bits:
~1000 portas lógicas (AND, OR, XOR, NOT, MUX)
+ somador CLA: ~500 portas adicionais
Modesto pelo padrão moderno (processadores têm bilhões de transistores)No harness.os
A ULA é o executor — recebe uma operação e operandos, produz resultado. No harness.os, cada tool call segue o mesmo padrão: operação + parâmetros = resultado.
Mapeamento: ULA → harness.os
Componente da ULA Equivalente no harness.os
────────────────────────────── ────────────────────────────────────
ALUOp (sinal de controle) Nome da tool: "log_decision",
"get_knowledge", "end_session"
— seleciona qual operação executar
Operandos A e B Parâmetros da tool call:
title, rationale, project_slug
Resultado Retorno da tool: dados, status,
confirmação
Sinal Zero Validação: resultado vazio?
Se sim, a condição falhou
(como beq verificando igualdade)
Sinal Overflow Erro: tool call que excede limites
(context window cheia, timeout,
parâmetro inválido)
Reutilização do somador Reutilização de tools: a mesma
(add, sub, slt, beq usam o ferramenta run_sql serve para
mesmo hardware) INSERT, SELECT, UPDATE, DELETE
— a "operação" está no parâmetroHomework
- Construa a tabela verdade completa de um full adder. Verifique as equações: S = A XOR B XOR Cin e Cout = (A AND B) OR (Cin AND (A XOR B)).
- Calcule a soma de 0110 (6) + 0101 (5) usando um ripple-carry adder de 4 bits. Mostre o carry em cada estágio. Houve overflow?
- Para um CLA de 4 bits, escreva a equação de C3 em termos de G, P e C0. Quantas portas AND e OR são necessárias?
- Explique como a ULA MIPS implementa
beq $s1, $s2, Label: qual operação ela executa, e qual sinal de saída é usado pelo processador para decidir se desvia ou não?
Resumo
- Half adder soma 2 bits; full adder soma 2 bits + carry de entrada
- Ripple-carry adder: simples mas lento (O(N) gate delays para N bits)
- Carry-lookahead adder: calcula carries em paralelo usando Generate e Propagate (O(log N))
- A ULA executa AND, OR, add, sub, slt, nor, xor — controlada por ALUOp (4 bits)
- Subtração reutiliza o somador: A - B = A + NOT(B) + 1
- SLT usa o bit de sinal da subtração; Zero flag é NOR de todos os bits do resultado
Verifique seu entendimento
Como a ULA MIPS implementa a instrução sub (subtração) reutilizando o somador?