Brochures">
Introd. A Arq. Comp. Raul Weber
Introd. A Arq. Comp. Raul Weber
Introd. A Arq. Comp. Raul Weber
de Computadores
Representao de Dados
Arquitetura e Organizao
Noes de Software Bsico
Notas de aula
Raul Fernando Weber
ii
PREFCIO
SOBRE O AUTOR
Colaboradores
Taisy Silva Weber
Carlos Arthur Lang Lisboa
Ingrid E.S. Jansch-Porto
iv
SUMRIO
1 Bases Numricas
1.1 Introduo........................................................................................1-1
1.2 Representao de nmeros.....................................................................1-2
1.3 Transformao entre bases.....................................................................1-2
1.3.1 Mtodo polinomial............................................................................1-3
1.3.2 Mtodo de subtraes ........................................................................1-3
1.3.3 Mtodo das divises..........................................................................1-4
1.3.4 Mtodo da substituio direta................................................................1-5
1.4 Exerccios propostos............................................................................1-5
2 Sistemas de numerao em computao
2.1 Introduo........................................................................................2-1
2.2 Soma de nmeros binrios.....................................................................2-2
2.3 Representao de nmeros.....................................................................2-2
2.3.1 Nmeros inteiros positivos..................................................................2-3
2.3.2 Nmeros com sinal: representao em sinal-magnitude..................................2-3
2.3.3 Nmeros com sinal: representao em complemento de (B1)..........................2-4
2.3.4 Nmeros com sinal: representao em complemento de B...............................2-9
2.4 Comparao entre os mtodos...............................................................2-12
2.5 Subtrao.......................................................................................2-13
2.6 Estouro de representao.....................................................................2-13
2.7 Exerccios propostos..........................................................................2-14
3 Componentes do computador e modelo de von Neumann
3.1 Breve histrico...................................................................................3-1
3.2 Princpios bsicos...............................................................................3-3
3.3 Elementos funcionais bsicos..................................................................3-4
3.3.1 Memria........................................................................................3-5
3.3.2 Unidade operacional..........................................................................3-6
3.3.3 Unidade de controle ..........................................................................3-7
3.3.4 Registradores especiais.......................................................................3-8
3.3.5 Conjunto de instrues e modos de endereamento ......................................3-9
3.3.6 Ciclo de busca-decodificao-execuo de instrues....................................3-9
3.3.7 Programao de um processador..........................................................3-10
3.4 Um computador de primeira gerao: o EDVAC..........................................3-10
3.5 Modelo de von Neumann: o computador IAS .............................................3-15
3.5.1 Organizao da UCP .......................................................................3-15
3.5.2 Conjunto de instrues.....................................................................3-15
3.6 Arquiteturas de 4, 3, 2, 1 e 0 endereos....................................................3-17
3.6.1 Arquitetura de 4 endereos.................................................................3-17
3.6.2 Arquitetura de 3 endereos.................................................................3-18
3.6.3 Arquitetura de 2 endereos.................................................................3-18
3.6.4 Arquitetura de um endereo................................................................3-19
3.6.5 Arquitetura de zero endereos.............................................................3-20
4 Computador hipottico NEANDER
4.1 Caractersticas....................................................................................4-1
4.2 Modos de endereamento.......................................................................4-1
4.3 Conjunto de instrues .........................................................................4-2
4.4 Cdigos de condio............................................................................4-2
v
vii
Apndice
UM
Utilizao dos simuladores e depuradores
A-2
A . 4 . 1 Hexadecimal x decimal
Todos os valores numricos (endereos, cdigos de instrues, dados) podem ser
representados tanto em hexadecimal como em decimal. O simulador comea sempre a operar
em hexadecimal. Voc pode escolher a forma que melhor lhe convm, atravs dos seguintes
comandos:
Comando Decimal ou Icone 0..9
todos os valores numricos aceitos e mostrados pelo simulador so decimais.
Comando Hexadecimal ou Icone 0..F
todos os valores numricos aceitos e mostrados pelo simulador so hexadecimais.
A . 4 . 2 Visualizao Simblica
A Janela de Programa possui uma coluna que permite visualizar as instrues em modo
simblico, ou seja, em uma interpretao a nvel de linguagem assembler. Note-se que o
cdigo da instruo desmontado, sendo apresentado na forma de mnemnico, mas
endereos e operandos so somente visualizados na forma numrica, em decimal ou
hexadecimal (dependendo da base escolhida).
A visualizao inicia no endereo inicial da janela, independente do fato deste endereo ser
realmente o incio de uma instruo ou no. Por exemplo, considerem-se as duas janelas
abaixo (mostradas somente com 10 posies, em decimal):
Endereo
0
1
2
3
4
5
6
7
8
9
10
Dado
32
128
48
129
48
130
16
128
240
0
0
Simblico
LDA 128
ADD 129
ADD 130
STA 128
HLT
NOP
NOP
Endereo
1
2
3
4
5
6
7
8
9
10
11
Dado
128
48
129
48
130
16
128
240
0
0
0
Simblico
JMP 48
JMP 48
JMP 16
JMP 240
NOP
NOP
NOP
Na janela da esquerda, o endereo inicial zero, e tem-se um programa que soma trs
posies. Ao deslocar-se esta janela de uma posio (com a seta para baixo), tem-se a janela
da direita, cujo contedo o mesmo, mas foi interpretado de forma diferente. Esta
caracterstica no se constitui propriamente um erro, mas tpica da arquitetura de von
Neuman, que permite uma completa liberdade no posicionamento de dados de instrues, e
inclusive no incio das instrues. Um computador deste tipo executa automaticamente as
instrues a partir do endereo apontado pelo PC. Cabe ao programador (ou ao sistema
operacional) garantir que o programa inicie em um endereo coerente.
Caso entretanto se deseje iniciar a interpretao simblica sempre no incio do programa
(endereo zero) e no no incio da janela de programa, pode-se utilizar para isto o comando
Mnemnicos relativos, ou a tecla F2.
A . 4 . 3 Editando um programa na memria
Para alterar o contedo da memria, use os comandos de edio, vlidos tanto para a janela
de dados como para a janela de programa. Ambas apresentam um campo de edio, que
permite alterar um byte de cada vez.
A-3
A escolha de uma das duas janelas para edio feita com o mouse , e a movimentao
dentro da janela tambm. Uma vez ativada uma janela, algumas teclas tambm podem ser
usadas para movimentao:
Tecla
seta para baixo ou enter
seta para cima
page up
page down
Significado
posio posterior de memria
posio anterior de memria
volta 16 posies
avana 16 posies
Alterar AC
permite fornecer um valor inicial para o acumulador (AC). Aps o comando, o
simulador solicita um endereo para inicializar o AC.
Alterar PC
permite fornecer um valor inicial para o apontador de instrues (PC). Aps o
comando, o simulador solicita um endereo para inicializar o PC.
Passo (F8)
cada vez que o comando ativado (via menu, tecla F8, ou iconed e passo a passo), o
simulador executa a instruo apontada pelo PC, parando logo aps.
BP
Break point
permite especificar um endereo de parada. No campo BP da janela de programa
pode ser fornecido o endereo para o break point.
Rodar (F9)
aps o comando Rodar (via menu, tecla F9 ou icone) o simulador executa
continuamente um programa, a partir da posio indicada pelo PC, at encontrar uma
instruo de halt (HLT), o ponto de parada ou o comando ser ativado novamente
(freio de emergncia).
A . 4 . 9 Salvando e carregando arquivos
Para os comandos que seguem, deve ser fornecido um nome de arquivo. Os simuladores
adicionam, automaticamente, o sufixo .mem. Arquivos de simuladores diferentes podem
ou no ser compatveis entre si, dependendo da compatibilidade entre as respectivas
arquiteturas.
Carregar
carrega um arquivo para a memria do computador sendo simulado. O arquivo deve
conter uma memria compatvel com o computador sendo simulado, caso contrrio o
simulador indica erro e o comando anulado.
Salvar
grava o contedo da memria do computador sendo simulado.
A-5
Captulo
UM
Bases Numricas
1 . 1 Introduo
Quando o homem aprendeu a contar, ele foi obrigado a desenvolver smbolos que
representassem as quantidades e grandezas que ele queria utilizar. Estes smbolos, os
algarismos, constituem a base dos sistemas de numerao.
Nos tempos pr-histricos o homem utilizou uma correspondncia um-para-um entre os
objetos a serem contados e os seus dedos, ou ento para pedrinhas ou mesmo para riscos.
Um sistema deste tipo seria um sistema unrio (com um nico smbolo):
V=5
X=10
L=50
C=100
D=500
M=1000
Alm disto, utilizam-se uma srie de regras (como por exemplo a posio relativa dos
smbolos aos seus vizinhos), que permitiam interpretar estes smbolos e determinar qual o
nmero que estava sendo representado:
VI=5+1=6 CXVI=100+10+5+1=116
IV=5-1=4 MCMLIX=1000+(1000-100)+50+(10-1)=1959
A realizao de clculos com este sistema, especialmente para operaes como multiplicao
e diviso, era entretanto extremamente complexa e de aplicao praticamente impossvel.
Posteriormente, os rabes utilizaram-se de um sistema originrio da ndia, que possua 10
smbolos (0 a 9), com os seguintes smbolos (da esquerda para direita, 1234567890):
Este sistema comeou a ser utilizado na Europa no sculo 12, e conhecido atualmente como
sistema de numerao arbica (mas com outros algarismos), e se destaca pelas seguintes
caractersticas:
existe um smbolo para o valor nulo.
cada algarismo utilizado uma unidade maior que o seu predecessor.
1-1
(xi.B i)
a=
i=m
O algarismo xi tem peso Bi, determinado pela sua posio. Para i com valores positivos,
tem-se pesos maiores que a unidade; para i=0 tem-se exatamente o peso unitrio (B0=1).
Para valores negativos de i, tem-se pesos menores que a unidade (fracionrios). Para o caso
especfico de nmeros inteiros, utilizando-se n dgitos (ou casas), indexados de 0 at n1,
a frmula fica:
n-1
(xi.B i)
a=
i=0
169-0.28=169-0.256=169
41-0.26=41-0.64=41
9-0.24=9-0.16=9
1-0.22=1-0.4=1
1-1.20=1-1=0
1-3
Se o resultado de uma subtrao produzir resultado zero, isto significa que todos os dgitos
restantes so zero, como ilustrado no exemplo a seguir.
680-1.29=680-512=168
168-1.27=168-128=40
40-1.25=40-32=8
8-1.23=8-8=0
168-0.28=168-0.256=168
40-0.26=40-0.64=40
8-0.24=8-0.16=8
2,125-1.21=2,125-2=0,125
0,125-0.2-1=0,125-0.0,5=0,125
0,125-1.2-3=0,125-0,125=0
0,8125-6.8-1=0,8125-0,7500=0,0625
Ou seja, 6,8125 10=6,648. Note-se que sempre se utiliza a aritmtica da base de origem.
1 . 3 . 3 Mtodo das divises
O nmero a ser convertido dividido pela nova base (na aritmtica da base de origem). O
resto desta diviso forma o algarismo mais a direita (menos significativo) do nmero
convertido. O quociente novamente dividido, e assim sucessivamente, at o quociente final
ser zero. A sequncia de todos os restos forma o novo nmero.
Note-se que ao dividir o nmero a pela base B obtm-se:
ou seja
A diviso seguinte por B produz como resto x1, e assim sucessivamente at xn-1.
532=26, resta 1
132=6, resta 1
32=1, resta 1
262=13, resta 0
62=3, resta 0
12=0, resta 1
1-4
Exemplo:
0,828125 . 2 = 1,65625
0,65625 . 2 = 1,3125
0,3125 . 2 = 0,625
0,625 . 2 = 1,25
0,25 . 2 = 0,5
0,5 . 2 = 1,0
Parte inteira = 1
Parte inteira = 1
Parte inteira = 0
Parte inteira = 1
Parte inteira = 0
Parte inteira = 1
Frao = 0,1
Frao = 0,11
Frao = 0,110
Frao = 0,1101
Frao = 0,11010
Frao = 0,110101
1-6
Captulo
DOIS
Sistemas de numerao em computao
2 . 1 Introduo
Em todas as frmulas usadas a seguir, B representa a base do sistema de numerao, n
representa a quantidade de dgitos disponveis para representar os nmeros, e a, b e c
representam nmeros. A frmula utilizada para representar um nmero inteiro:
n-1
(xi.B i)
a=
i=0
ser representada por a= n-1xiBi, ficando a variao de i desde 0 at o limite (n-1) implcita.
Para uma determinada base B, empregando-se n dgitos, pode-se representar Bn combinaes distintas, ou seja, Bn nmeros distintos. Assim, para base decimal com trs dgitos
pode-se representar 1000 nmeros distintos (com zero includo!). Entretanto, com os
mesmos trs dgitos e base dois, representa-se somente 8 nmeros distintos. Assim,
nmeros binrios vo exigir um grande nmero de dgitos, e normalmente trabalha-se com
grandes cadeias de zeros e uns. Isto pode levar a erros visuais, e por isso empregam-se
comumente as notaes em base 8 e base 16 para representar nmeros binrios.
A tabela abaixo lista os primeiros 16 nmeros em binrio, decimal, octal e hexadecimal.
Binrio
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Decimal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Octal
00
01
02
03
04
05
06
07
10
11
12
13
14
15
16
17
Hexadecimal
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
entres as bases 2, 8 e 16 pode ser feita facilmente pelo mtodo da substituio direta. Embora
a base hexadecimal seja de representao mais complexa (utiliza letras e dgitos), ela
preferida sobre a base octal por ser mais compacta, ou seja, requerer menos espao para
representar os resultados.
Os nmeros do sistema binrio so formados como qualquer outro nmero do sistema de
numerao arbico (inclusive em octal ou hexadecimal): cada novo nmero obtido por
enumerao, somando-se um ao seu antecessor (e observando-se a regra do vai-um).
Cada dgito do sistema binrio (0 e 1) denominado de bit, a contrao de binary digit. A
determinados conjuntos de bits so empregados nomes especficos. Assim, um quarteto (4
bits) frequentemente denominado de nibble, e um octeto (8 bits) recebe a denominao de
byte (ou o termo aportuguesado baite). Os mltiplos deste conjuntos utilizam os mesmos
denominadores que no sistema decimal (K para kilo, M para Mega, G para giga, T para
3
10
Tera, P para Peta), mas o fator multiplicativo no 1000 (10 ) mas sim 1024 (2 ). Assim,
um kilobit (abreviado 1Kb) so 1024 bits, e um kilobyte (abreviado 1KB) so 1024 bytes.
Um megabyte (1MB) so 1024 KB; um gigabyte (1GB) so 1024 MB, um terabyte (1TB)
so 1024 GB e assim por diante.
2 . 2 Soma de nmeros binrios
A soma de dois nmeros binrios utiliza as mesmas regras da soma no sistema decimal.
Como existem entretanto somente dois smbolos, a tabela de soma extremamente simples:
a
0
0
1
1
c
0
1
0
1
d=a+c
0
1
1
0 e vai-um
c
0
0
1
1
0
0
1
1
vem-um
0
1
0
1
0
1
0
1
d=a+c
0
1
1
0
1
0
0
1
vai-um
0
0
0
1
0
1
1
1
2 . 3 Representao de nmeros
A representao de nmeros inteiros positivos direta e imediata. Entretanto, necessrio
expandir (ou modificar) esta representao para incluir tambm nmeros negativos. Diversas
representaes foram desenvolvidas com este propsito. Quatro destas representaes, as
mais comuns atualmente, so analisadas a seguir: inteiros positivos, sinal/magnitude,
complemento de B-1 e complemento de B.
2-2
2-3
S(c)
+
S(d)
+
se M(a)M(c), +
se M(a)<M(c),
se M(a)>M(c),
se M(a)M(c), +
M(d)
M(a)+M(c)
M(a)+M(c)
M(a)M(c)
M(c)M(a)
M(a)M(c)
M(c)M(a)
Exemplo
5 + 7 = 12
-5 + -7 = -12
7 + -5 = 2
5 + -7 = -2
-7 + 5 = -2
-5 + 7 = 2
2-4
Algarismo
0
1
2
3
4
5
6
7
8
9
B=2
1
0
-
B=3
2
1
0
-
B=4
3
2
1
0
-
B=8
7
6
5
4
3
2
1
0
-
B=9
8
7
6
5
4
3
2
1
0
-
B=10
9
8
7
6
5
4
3
2
1
0
A tabela a seguir ilustra as faixas para diversas bases. Note-se que a gama de representao
dividida em dois subconjuntos, um para nmeros negativos e outro para positivos. A faixa
dos nmeros positivos reduzida da metade (em relao aos inteiros positivos). Continua
existindo a dupla representao do zero, assim como em sinal magnitude, mas no existe
mais a perda de capacidade de representao devido a existncia do dgito de sinal.
Base Num.dig.
Faixa
Faixa em decimal
2
4
1000,1001,..,1111,0000,0001,..,0111
7,6,..,0,+0,1,..7
3
3
112,120,121,..,222,000,001,..,111 12,11,10,..,0,+0,1,..,13
4
3
200,201,..,333,000,001,..,132,133
31,30,..,0,+0,1,..31
8
3
400,401,..,777,000,001,..,376,377
255,254,..,0,+0,..,255
9
2
45,46,..,88,00,01,..,43,44
39,38,..,0,+0,1,..,39,40
10
2
50,51,..,98,99,00,01,..,48,49
49,48,..,1,0,+0,..,48,49
Tabela 2.6 - Exemplos de faixas de representao em complemento de B-1
Por exemplo, para base decimal com dois dgitos, se consideramos somente nmeros positivos tem-se a faixa de 0 at 99; com a representao em complemento de 9 obtm-se a faixa
de 50 a 99 e 0 a 49. A primeira metade (de 50 a 99) representa nmeros negativos (de 49 a
0); a segunda metade (de 0 a 49) representa nmeros positivos. Note-se que um nmero
iniciando por 9, 8, 7, 6 ou 5 negativo; iniciando por 0, 1, 2, 3 ou 4 positivo. Em binrio,
para 4 dgitos, tem-se a faixa 1000 a 1111 (7 a 0) e 0000 a 0111 (0 a 7). Nmeros
iniciando por 1 so negativos, e iniciando por 0 so positivos.
Para bases mpares, existe um nmero positivo a mais, e para a determinao do sinal no
basta a verificao do dgito mais significativo (veja-se a seguir). Por exemplo, na tabela 2.6,
os nmeros em base 3 iniciando por zero so positivos, e os nmeros iniciando por 2 so
negativos, mas dos nmeros iniciando por 1 metade so positivos (100, 101, 102, 110 e
111) e metade so negativos (112, 120, 121 e 122).
2-5
Num.dig.
4
4
4
4
3
3
3
2
2
3
3
3
3
Nmero
1110
1001
1010
0101
102
111
121
98
99
45
54
76
50
Sinal
+
+
+
Magnitude
1
6
5
5
11
13
10
1
0
45
45
23
49
Num.decim.
1
6
5
+5
+11
+13
10
1
0
+45
45
-23
-49
2-6
Troca de sinal
Para trocar o sinal de um nmero a em complemento de (B1), basta complementar, tambm
em B1, cada um de seus dgitos. Assim, no caso de c=(a), tem-se, pelo raciocnio acima,
c=Bn1a. Note-se que ((a)) = (Bn1a) = Bn1(Bn1a) = a.
No caso de bases mpares, o maior positivo, ao ser trocado de sinal, resulta novamente em si
prprio. Nestes casos, diz-se que houve estouro de representao (veja seo 2.6). Para
bases pares, isto nunca ocorre (para complemento de B-1). A tabela abaixo ilustra diversos
casos de troca de sinal.
Base
2
2
2
2
3
3
3
10
10
10
10
16
16
16
Num.dig.
4
4
4
4
3
3
3
2
2
2
2
2
2
2
Nmero
1110
1001
1010
0101
102
111
121
98
99
45
54
01
FF
98
Nm.negado
0001
0110
0101
1010
120
111 (estouro)
101
01
00
54
45
FE
00
67
Magnitude
1
6
5
5
11
13
10
1
0
45
45
1
0
103
2-7
S(a)
S(c)
S(d)
M(d)
M(a)+M(c)
M(a)+M(c)
se M(a)M(c), + M(a)M(c)
se M(a)<M(c), M(c)M(a)
se M(a)>M(c), M(a)M(c)
se M(a)M(c), + M(c)M(a)
Num.dig.
4
4
4
4
4
4
4
4
2
2
2
2
2
2
a
1110
1111
1001
0110
0101
0011
1111
0001
98
99
99
45
45
76
c
0001
0001
0111
1111
1000
0011
1111
1110
37
00
01
55
45
45
d=a+c
1111
10000
10000
10101
1101
0110
11110
1111
135
99
100
100
90
121
2-8
d corrigido
1111
0001
0001
0110
1101
0110
1111
1111
36
99
01
01
90
22
2-9
Num.dig.
4
4
4
4
4
4
3
3
3
3
2
2
3
3
3
Nmero
1110
1001
1010
1000
0101
0111
102
111
112
121
98
99
45
54
50
Sinal
+
+
+
+
Magnitude
2
7
6
8
5
7
11
13
13
11
2
1
45
46
50
Num.decim.
2
7
6
8
+5
+7
+11
+13
13
11
2
1
+45
46
50
Troca de sinal
Para trocar o sinal de um nmero a em complemento de B, basta calcular Bn-a. Ou, pelo
raciocnio acima, calcula-se o complemento de (B1), complementando cada algarismo, e
depois soma-se um. A tabela a seguir ilustra diversos casos de troca de sinal. Note-se que,
para bases pares, a troca de sinal do menor nmero negativo (de maior magnitude) provoca
estouro de representao, pois este nmero no tem equivalente positivo. Em bases mpares
isto no ocorre.
Base
2
2
2
2
2
3
3
3
10
10
10
10
10
Num.dig.
4
4
4
4
4
3
3
3
2
2
3
3
3
Nmero
1110
1001
1010
0101
1000
102
111
121
98
99
45
54
50
Nm.negado Magnitude
0010
2
0111
7
0110
6
1011
5
1000 (estouro)
8 (8)
121
11
112
13
102
10
02
2
01
1
55
45
46
46
50 (estouro)
50 (50)
S(c)
+
S(d)
+
M(d)
M(a)+M(c)
M(a)+M(c)
se M(a)M(c), + M(a)M(c)
se M(a)<M(c), M(c)M(a)
se M(a)>M(c), M(a)M(c)
se M(a)M(c), + M(c)M(a)
d (Soma de a + c)
a+c
Bn-M(a) + Bn-M(c)
Bn+Bn - (M(a)+M(c))
Bn + Bn - M(d)
Bn + d (*)
M(a) + Bn-M(c)
Bn + M(a)-M(c)
Bn + d (*)
M(a) + Bn-M(c)
Bn - (M(c)-M(a))
Bn - M(d)
d
Bn - M(a) + M(c)
Bn - (M(a)-M(c))
Bn - M(d)
d
Bn - M(a) + M(c)
Bn + (M(c)-M(a))
Bn + d (*)
2-11
Base
2
2
2
2
2
2
2
2
10
10
10
10
10
10
Num.dig.
4
4
4
4
4
4
4
4
2
2
2
2
2
2
a
1110
1001
1111
0110
0101
0011
1111
0001
98
99
99
45
45
76
c
0001
0111
0001
1111
1000
0011
1111
1110
37
00
01
55
45
45
d=a+c
1111
10000
10000
10101
1101
0110
11110
1111
135
99
100
100
90
121
d corrigido
1111
0000
0000
0101
1101
0110
1110
1111
35
99
00
00
90
21
Int.positivo
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sinal mag.
+0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
compl. de 1
0
1
2
3
4
5
6
7
7
6
5
4
3
2
1
0
compl. de 2
0
1
2
3
4
5
6
7
8
7
6
5
4
3
2
1
2-12
2 . 5 Subtrao
A operao de subtrao, seja qual for o mtodo de representao utilizado, pode ser
facilmente realizada transformando-a em uma soma:
d = a c = a + (c)
Assim, para realizar subtraes, pode-se simplesmente trocar o sinal do subtraendo e somlo ao minuendo. A troca de sinal e a soma seriam ento realizadas de acordo com o sistema
de representao utilizado.
A subtrao pode, tambm ser realizada atravs de tabelas prprias. Neste caso, no lugar de
vem-um (carry in), tem-se o emprestou-um(borrow in); e no lugar de vai um (carry
out) tem-se o pede-um (borrow out).
a
0
0
1
1
c
0
1
0
1
d=a-c
0
1 e pede-um
1
0
a
0
0
0
0
1
1
1
1
c
0
0
1
1
0
0
1
1
emprestou um
0
1
0
1
0
1
0
1
d=ac
0
1
1
0
1
0
0
1
pede um
0
1
1
1
0
0
0
1
8 + 1 = 7
8 + 1 = 7
7 + 1 = 6
7 + 3 = 6
(correto)
(incorreto; deveria ser 9)
(correto)
(incorreto; deveria ser 10)
Note-se que o estouro no est diretamente relacionado com o vai-um. Os exemplos acima
ilustram isto. No primeiro caso, no ocorreu nem estouro nem vai-um; no segundo caso
2-13
ocorreram tanto estouro como vai-um; no terceiro caso ocorreu vai-um, mas no estouro;
e no quarto caso no ocorreu vai-um, mas ocorreu estouro.
Existe uma regra simples para determinao de estouro em complemento de 2: ocorre estouro
quando o vai-um do dgito mais significativo diferente do vem-um para este mesmo
dgito. Note-se que o dgito mais significativo o utilizado para indicar o sinal do nmero.
Esta a maneira como os computadores internamente calculam se o resultado estourou ou
no.
Uma outra maneira, que no necessita da anlise dos vai-um e vem-um, utiliza somente
os dgitos mais significativos dos dois operandos e do resultado, ou seja, analisam-se os
sinais dos operandos e do resultado. Esta anlise est resumida na tabela a seguir (seja
d=a+c).
Sinal de a Sinal de c
+
+
+
+
+
+/
/+
Sinal real de d
+
+
+/
/+
Estouro
No
Sim
No
Sim
Nunca ocorre
Nunca ocorre
(d) 129,5625
(d) 010110011
4. Quantos nmeros diferentes podem ser representados em uma palavra binria de 6 bits?
5. Quantos nmeros diferentes podem ser representados em um conjunto de 4 chaves, cada
uma com trs posies diferentes?
6. Escrever os 12 primeiros nmeros no sistema de numerao de base 5.
2-14
(d) 3364
2-16
Captulo
TRS
Componentes do computador e modelo de von Neumann
3 . 1 Breve histrico
Uma das mais importantes investidas na rea computacional, e que merece registro histrico,
foi a do ingls Charles Babbage. Ele projetou dois computadores: Difference Engine
(denominado a seguir Dispositivo Diferencial), iniciado em 1823, e o Analytical Engine
(Dispositivo Analtico), concebido em 1834, tendo ambos representado grandes avanos
cientficos em sua poca, embora nenhuma deles tenha sido concludo. O objetivo do
Dispositivo Diferencial era o cmputo automtico de tabelas matemticas. Sua nica operao
era a adio, mas a mquina podia resolver grande nmero de funes teis pela tcnica de
diferenas finitas. Esta mquina foi projetada para polinmios de grau 6 e nmeros binrios
de 20 dgitos, mas no foi concluda devido a problemas de inadequao da tecnologia
mecnica disponvel. Outra tentativa de Babbage, foi a construo do Dispositivo Analtico,
que deveria realizar qualquer operao matemtica automaticamente. Esta mquina j tinha
mdulos de armazenamento (memria) e uma unidade operadora (realizando 4 operaes
aritmticas). A entrada e sada de dados era feita atravs de cartes perfurados. Esta mquina
permitia a alterao da seqncia dos comandos executados, dependendo do resultado de
testes realizados. Novamente por problemas tcnicos, a construo desta mquina no
chegou ao final. Na tabela a seguir esto reunidas algumas das principais tentativas de valor
histrico no mbito computacional.
Data
1642
Inventor:mquina
Pascal
1671
Leibnitz
1827
Babbage:
Difference Engine
Babbage:
Analytical Engine
Zuse: Z3
1834
1941
1944
Aiken:
Harward Mark I
Capacidade
adio, subtrao
Inovaes tcnicas
transferncia automtica de vai-um;
representao em complemento
adio, subtrao,
mecanismo para multiplicao
multipl., diviso
e diviso
avaliao polinomial
operao automtica
por diferenas finitas
com diversos passos
computador de
mecanismo automtico de controle
propsitos gerais
de sequncia (programa)
computador de
primeiros computadores de
propsitos gerais
propsitos gerais operacionais
computador de
primeiros computadores de
propsitos gerais
propsitos gerais operacionais
vlvulas. Para se ter uma idia do tempo de execuo nesta mquina, eram necessrios cerca
de 3 ms para realizao de uma multiplicao de 10 dgitos (decimais), o que se constituiu em
grande avano para a poca. Ele trabalhava preponderantemente com valores decimais e no
binrios. Na Figura 3.1 mostrada a estrutura bsica do ENIAC.
Com o avano da pesquisa e o conseqente desenvolvimento tecnolgico, houve grandes
modificaes nos computadores. Basicamente, ao longo do tempo, a tecnologia e os estilos
usados na construo de computadores apresentam pontos comuns, que nos permitem
classific-los em geraes. Na tabela a seguir, so apresentadas as geraes de computadores
de acordo com sua classificao histrica.
Gerao
Tecnologias
Vlvulas,
1a
memria
de tubos
(1946 catdicos
54)
Transistores, ncleos
2a
de ferrite, discos
(1955 magnticos
64)
a
Circuitos
integrados
3
(SSI
e
MSI)
(1965 74)
4a
(1975 ?)
Caracterstica de
hardware
aritmtica de
ponto fixo
ponto flutuante
registrador ndice
processadores E/S
microprogramao
pipeline
memria cache
Caracterstica de
software
linguagem de
mquina, linguagem
assembler
ling. alto-nvel
bibliot. de subrotinas
monitores batch
multiprogramao
multiprocessamento
sistema operacional
memria virtual
Circuitos LSI
memrias
semicondutoras
Exemplo
IAS,
UNIVAC
IBM7094
CDC1604
IBM
S/360;
DEC
PDP-8
Amdahl
470;
Intel 8748
divisor
multiplicador
e raiz
quadrada
impressora e
perf. de cartes
tabelas de
funes
unidade mestre de
programao
Figura 3.1 - Estrutura bsica do ENIAC
3-2
a
c
u
m
u
l.
3 . 2 Princpios bsicos
Cada computador tem um conjunto de operaes e convenes nico para determinar as
posies dos dados com os quais a operao ser realizada. Os vrios computadores diferem
nas operaes especficas que fornecem e nos mtodos que eles usam para referenciar dados
que sero manipulados por uma operao. Em geral, uma operao tem a forma
OPERAO
OPERANDOS
memria
controle
unidade
operacional
entrada/
sada
entrada e sada. Um barramento s pode receber dados de uma fonte de cada vez. Do ponto
de vista de arquitetura, um barramento se caracteriza pela sua largura em bits. A largura em
bits do barramento deve corresponder ao comprimento dos elementos (dados, endereo,
controle) que so por ele transportados.
Cada um dos blocos bsicos do computador comentado, em detalhes, a seguir.
3 . 3 . 1 Memria
A memria formada por elementos armazenadores de informao. Uma memria est
dividida em palavras. Cada palavra ocupa uma posio de memria e identificada
univocamente por um endereo. O contedo armazenado nas palavras da memria tanto
pode representar dados como instrues. Um esquema da estrutura convencional para a
memria de um computador mostrado na Figura 3.3.
RDM in
R
E
M
read
memria
write
RDM out
RDM i n :
RDM out :
3 . 3 . 2 Unidade operacional
A unidade operacional, tambm chamada de bloco operacional, executa as transformaes
sobre dados especificadas pelas instrues de um computador. Compe-se basicamente de
uma unidade lgica e aritmtica, de registradores de uso geral e especfico e dos barramentos
que interligam todos esses elementos.
O nmero, tamanho e uso dos registradores e a quantidade e tipo de operaes que a unidade
lgica e aritmtica realiza so alguns dos fatores que determinam o porte de um processador.
Unidade lgica e aritmtica ( ULA )
A ULA realiza operaes aritmticas e operaes lgicas sobre um ou mais operandos.
Exemplos de operaes realizadas pela ULA: soma de dois operandos; negao de um
operando; inverso de um operando; AND (E lgico) de dois operandos; OR (OU lgico)
de dois operandos; deslocamento de um operando para a esquerda ou direita ; rotao de um
operando para a esquerda ou direita
As operaes da ULA so, geralmente, muito simples. Funes mais complexas, exigidas
pelas instrues da mquina, so realizadas pela ativao seqencial das vrias operaes
bsicas disponveis. Um exemplo a execuo de instrues de multiplicao em alguns
computadores, que compreende a ativao de operaes sucessivas de soma e deslocamento
na ULA.
A ULA fornece o resultado da operao e tambm algumas indicaes sobre a operao
realizada. Tais indicaes so chamadas cdigos de condio. Exemplos de alguns
cdigos de condio comumente gerados na ULA so:
Overflow:
Sinal:
Carry:
Zero:
controle
U L A
cdigos de
condio
resultado
Figura 3.4 - Modelo estrutural da ULA
3-6
Os sinais de controle que devem ser fornecidos para a ULA servem para selecionar a
operao desejada entre as operaes bsicas disponveis. Convm salientar que a ULA no
armazena nem o resultado, nem os operandos, nem os cdigos de condio gerados.
Uma ULA se caracteriza por:
comprimento em bits dos operandos
nmero e tipo de operaes
cdigos de condio gerados
Acumulador
O acumulador um registrador e tem por funo armazenar um operando e/ou um
resultado fornecido pela ULA. Nos computadores mais simples encontrado apenas um
acumulador. Em algumas arquiteturas mais complexas vrios registradores podem
desempenhar as funes de um acumulador.
Como todos os registradores, o acumulador ativado por um sinal de controle de carga. A
cada sinal de carga, o dado na entrada do registrador copiado para o seu interior
(obviamente o antigo contedo do acumulador perdido).
Um acumulador, sendo um registrador, se caracteriza ao nvel de arquitetura apenas pelo seu
comprimento em bits.
3 . 3 . 3 Unidade de controle
Para gerenciar o fluxo interno de dados e o instante preciso em que ocorrem as transferncias
entre uma unidade e outra so necessrios sinais de controle. Esses sinais so fornecidos
por um elemento conhecido por unidade de controle.
Cada sinal de controle comanda uma microoperao. Uma microoperao pode ser
responsvel pela realizao de uma carga em um registrador, uma seleo de um dado para
entrada em um determinado componente, uma ativao da memria, a seleo de uma
operao da ULA ou a habilitao de um circuito lgico, para citar alguns exemplos.
Unidades de controle so mquinas de estado finitas (FSM) realizadas por lgica seqencial.
Lgica seqencial e lgica combinacional so caracterizadas, informalmente, como segue:
Lgica seqencial: os sinais de sada so funo dos sinais de entrada e do estado
anterior do sistema.
Lgica combinacional: os sinais de sada so funo exclusiva dos sinais de
entrada.
Existem vrias formas de implementar lgica seqencial. Tais formas de implementao
caracterizam a organizao da unidade de controle. As duas organizaes usuais so:
Organizao convencional: a unidade de controle composta por componentes
digitais como flip-flops, contadores e decodificadores, que geram, seqencialmente
e nos instantes de tempo adequados, todos os sinais de controle necessrios
ativao da unidade operacional, do sistema de entrada e sada e da memria.
Organizao microprogramada: em uma unidade de controle microprogramada,
os sinais de controle esto armazenados numa memria especial chamada memria
de controle. Vrios sinais de controle so buscados a cada acesso memria de
controle. Esses sinais esto agrupados em longas palavras chamadas
microinstrues. Um conjunto de microinstrues forma um microprograma.
3-7
RI
RST
unidade
de
controle
sinais de
controle
3 . 3 . 4 Registradores especiais
Existem, no computador, alguns registradores com funes especiais, conforme ser
explicado a seguir. Dependendo da arquitetura e da organizao de cada mquina, alguns
registradores podem estar posicionados na unidade de controle ou na unidade operacional.
Esta localizao, entretanto, no momento no relevante; aqui ser assumida a posio
adotada por cada mquina estudada.
Apontador de instrues
O apontador de instrues um registrador e tem por funo manter atualizado o
endereo de memria da prxima instruo que deve ser executada. Tambm chamado de
contador do programa (ou PC, do ingls Program Counter). O nome contador do
programa se deve ao fato de, no modelo bsico de um computador, instrues consecutivas
de um programa serem armazenadas em palavras da memria que possuem endereos
tambm consecutivos. Assim, para acessar a prxima instruo, basta contar mais um.
Do ponto de vista de arquitetura, um apontador de instrues se caracteriza pelo seu
comprimento em bits. Como o PC contm um endereo de memria, o comprimento do PC
funo do tamanho da memria onde esto armazenados os programas em execuo.
Registrador de instrues ( RI )
O registrador de instrues armazena a instruo que est sendo executada. Em funo
do contedo desse registrador, a unidade de controle determina quais os sinais de controle
devem ser gerados para executar as operaes determinadas pela instruo. Do ponto de vista
de arquitetura, um registrador de instrues se caracteriza pelo seu comprimento em bits. O
comprimento do RI depende do tamanho e codificao das instrues do computador.
Registrador de estado ( RST )
O registrador de estado armazena cdigos de condio gerados pela unidade lgica e
aritmtica (e, eventualmente, por outros elementos, como os sinais de interrupo gerados
por dispositivos de entrada e sada). Em funo do contedo desse registrador, a unidade de
controle toma decises sobre a gerao ou no de certos sinais de controle. Do ponto de vista
3-8
3-9
3-10
unidades de
memria
secundrias
unidade
central de
processamento
memria
principal
unidade
lgicoaritmtica
teletipo
unidade de
controle de
programa
leitora de
cartes
impressora e
perfuradora
de cartes
equipamentos de E/S
A2
A3
A4
OP
que significava o seguinte: realize a operao OP com o contedo das posies de memria
principal, cujos endereos so A1 e A 2 e coloque o resultado na posio A3. O quarto
endereo, A4, especifica a posio da prxima instruo a ser executada.
Uma instruo condicional tinha o seguinte formato:
A1
A2
A3
A4
m,n
A3
A4
significando:
1. Se m = 1, transfira para o condutor n a seqncia de palavras armazenadas na memria
principal nas posies A1, A1+1, A 1+2, ....., A 3.
2. Se m = 2, transfira do condutor n a seqncia de palavras para as posies A1, A 1+1,
A1+2, ....., A 3 na memria principal.
Novamente A4 era o endereo da prxima instruo a ser realizada.
Observe na estrutura do EDVAC, mostrada na Figura 3.6, que h dois conjuntos de linhas
originados na unidade central de processamento que conduzem informaes entre esta
unidade e os equipamentos de entrada e sada. O conjunto de linhas que parte do bloco
3-11
palavra inteira em uma nica operao. Cada instruo continha somente um endereo de
memria e tinha o seguinte formato:
OP
equipamento
de
entrada e
sada
DR
instrues
e dados
IBR
PC
memria
principal
IR
AR
circuitos de
controle
: sinais de
:
controle
endereos
Comentrios
Transfere contedo da memria, end. 100, para acumulador
Soma contedo da posio 101 ao contedo do acumulador e
coloca o resultado no acumulador
Armazena o contedo do acumulador no endereo 102
Figura 3.8 - Exemplo de programa no IAS
Na Figura 3.7 mostrada a estrutura do computador IAS, cuja arquitetura bsica ficou
conhecida como modelo de von Neumann. A terminologia no corresponde exatamente a
utilizada originalmente; os termos esto atualizados para o seu equivalente prximo na
nomenclatura atual.
Organizao da memria
A memria do IAS tinha 212 = 4096 palavras, sendo as palavras compostas por 40 bits.
Estes 40 bits, eram a quantidade de informaes que podiam ser transferidas, em cada
momento, da UCP para a memria (em um passo). Estas palavras armazenadas na memria
podiam corresponder a instrues ou a dados.
Formato dos dados
Os dados eram nmeros binrios representados em ponto fixo e codificados em
complemento de dois. Sendo assim, o bit mais a esquerda do nmero correspondia ao sinal
do mesmo e as operaes de soma e subtrao eram ambas executadas por um somador. O
ponto do nmero estava supostamente entre os bits 0 e 1, permitindo assim a representao
direta apenas de nmeros situados no intervalo entre 0 e 1; os demais nmeros deveriam ser
previamente ajustados antes da realizao de clculos. O formato de um dado representado
a seguir.
0 1
39
Bit de sinal
Figura 3.9 - Formato dos dados do IAS
Formato das instrues: cada instruo podia ser representada com 20 bits; portanto,
uma palavra de memria podia acomodar 2 instrues. Oito bits, os mais da esquerda ou
mais significativos eram usados para o cdigo da operao a ser realizada, e os outros doze
bits eram usados para especificar o endereo de uma posio de memria, conforme
mostrado abaixo.
Instruo posicionada esquerda
0
8
cd.operao
endereo
39
endereo
AC M(X)
Descrio
Transfere contedo do reg. MQ para o
acumulador AC
Transfere contedo da posio X de
memria para MQ
Transfere contedo de AC para a posio
de memria X
Transfere M(X) para AC
AC M(X)
AC |M(X)|
M(X) AC
Desvio
incondicional
Desvio
condicional
Aritmtica
AC |M(X)|
go to M(X, 0:19)
Modificao
endereo
E1
E2
E3
E4
Instruo
ADD B C A e2
MUL A D A e3
ADD A E A e4
SUB A F A e5
DIV A G A e6
DIV A H A e7
HALT
Comentrio
Soma B com C, resultado em A; vai para e2
Multiplica A por D, resultado em A; vai para e3
Soma A com E, resultado em A; vai para e4
Subtrai F de A, resultado em A; vai para e5
Divide A por G, resultado em A; vai para e6
Divide A por H, resultado final em A; vai para e7
Fim do programa
3-17
E1
E2
E3
Instruo
ADD B C A
MUL A D A
ADD A E A
SUB A F A
DIV A G A
DIV A H A
HALT
Comentrio
Soma B com C, resultado em A; incrementa PC
Multiplica A por D, resultado em A; incrementa PC
Soma A com E, resultado em A; incrementa PC
Subtrai F de A, resultado em A; incrementa PC
Divide A por G, resultado em A; incrementa PC
Divide A por H, resultado final em A; incrementa PC
Fim do programa
E1
E2
distintos. Isto permite uma maior reduo nos bits necessrios para especificar os endereos
dos operandos, mas introduz uma restrio sria: o resultado da operao ser armazenado
no endereo de um dos dois operandos fonte, ou seja, um destes dois operandos ser
necessariamente alterado. Esta restrio foi contornada com a criao de uma classe extra de
instrues, as instrues de movimentao de dados, que permitem copiar operandos de uma
posio para outra, conforme pode ser visto no programa a seguir:
Endereo
e1
e1+1
e1+2
e1+3
e1+4
e1+5
e1+6
e1+7
Instruo
MOV A B
ADD A C
MUL A D
ADD A E
SUB A F
DIV A G
DIV A H
HALT
Comentrio
Move B para A
Soma A com C, resultado em A
Multiplica A por D, resultado em A
Soma A com E, resultado em A
Subtrai F de A, resultado em A
Divide A por G, resultado em A
Divide A por H, resultado final em A
Fim do programa
E1
Instruo
LDA B
ADD C
MUL D
ADD E
SUB F
DIV G
DIV H
STA A
HALT
Comentrio
Move B para Acumulador
Soma Acum. com C, resultado no Acumulador
Multiplica Acum. por D, resultado no Acumulador
Soma Acum. com E, resultado no Acumulador
Subtrai F do Acum., resultado no Acumulador
Divide Acum. por G, resultado no Acumulador
Divide Acum. por H, resultado no Acumulador
Armazena Acum. no endereo de A
Fim do programa
Comparando-se este programa com o da arquitetura de trs endereos, nota-se que existem
duas instrues adicionais de transferncia de dados, uma no incio do programa (LDA B) e
outra no fim (STA A). A grande vantagem deste tipo de arquitetura est na economia dos
acessos memria: praticamente cada operando foi lido ou escrito uma nica vez, o que no
ocorre nas arquiteturas anteriores. Este justamente o papel dos registradores locais (ou
acumuladores): permitir que resultados intermedirios ou dados muito utilizados no
precisem ser lidos ou escritos da memria a cada vez que forem utilizados.
3 . 6 . 5 Arquitetura de zero endereos
Em uma arquitetura tpica de zero endereos, as instrues apresentam o formato
OP
ou seja, no existe nenhuma referncia explcita a endereos de memria onde estejam
localizados os operandos. Uma possvel soluo para determinar a posio dos operandos
coloc-los em uma regio especfica de memria, com determinado mecanismo de acesso.
Uma estrutura muito utilizada para estes fins uma pilha: os operandos so sempre retirados
do topo da pilha, e o resultado da operao sempre colocado no topo da pilha. Para facilitar
a operao desta estrutura de pilha, as equaes so escritas utilizando-se notao polonesa
reversa, onde o smbolo da operao escrito aps os dois operandos. Assim, por exemplo,
A+B seria escrito AB+. Com isto, a equao exemplo fica:
HGFEDCB+*+//
E o programa que a implementa seria:
Endereo
e1
e1+1
e1+2
e1+3
e1+4
e1+5
e1+6
e1+7
e1+8
e1+9
e1+10
e1+11
e1+12
e1+13
e1+14
Instruo
PUSH H
PUSH G
PUSH F
PUSH E
PUSH D
PUSH C
PUSH B
ADD
MUL
ADD
SUB
DIV
DIV
POP A
HALT
Comentrio
Coloca H no topo (atual) da pilha
Coloca G no topo da pilha
Coloca F no topo da pilha
Coloca E no topo da pilha
Coloca D no topo da pilha
Coloca C no topo da pilha
Coloca B no topo da pilha
Topo da pilha recebe B+C
(B e C so retirados da pilha)
Topo recebe (B+C)*D
Topo recebe (B+C)*D + E
Topo recebe (B+C)*D + E - F
Topo recebe ((B+C)*D + E - F)/G
Topo recebe ((B+C)*D + E - F)/G*H
Topo da pilha armazenado em A
Fim do programa
3-20
Captulo
QUATRO
Computador hipottico Neander
operando
Esta pseudo-mquina foi criada pelos Profs. Raul Weber e Taisy Weber para a antiga disciplina CPD148 Arquitetura de Computadores I. Possui simulador e depurador associados, que podem ser vistos no apndice A.
4-1
4 . 3 Conjunto de instrues
O conjunto de instrues de NEANDER compreende 11 instrues, codificadas atravs dos
quatro bits mais significativos da palavra que contm o cdigo da instruo (Tabela 4.1):
Cdigo
0000
0001
0010
0011
0100
0101
0110
1000
1001
1010
1111
Instruo
NOP
STA
LDA
ADD
OR
AND
NOT
JMP
JN
JZ
HLT
end
end
end
end
end
end
end
end
Comentrio
nenhuma operao
armazena acumulador - (store)
carrega acumulador - (load)
soma
ou lgico
e lgico
inverte (complementa) acumulador
desvio incondicional - (jump)
desvio condicional - (jump on negative)
desvio condicional - (jump on zero)
trmino de execuo - (halt)
end
end
end
end
end
Comentrio
nenhuma operao
MEM(end) AC
AC MEM(end)
AC MEM(end) + AC
AC MEM(end) OR AC
AC MEM(end) AND AC
end
end
end
AC NOT AC
PC end
IF N =1 THEN PC end
IF Z =1 THEN PC end
sinal do resultado
1 - resultado negativo
0 - resultado positivo
4-2
As instrues lgicas e aritmticas (ADD, NOT, AND, OR) e a instruo de transferncia LDA
afetam os cdigos de condio N e Z. As demais instrues (STA, JMP, JN, JZ, NOP e HLT)
no alteram os cdigos de condio.
4 . 5 Formato das instrues
As instrues de NEANDER so formadas por um ou dois bytes, ou seja, ocupam uma ou
duas posies na memria (Figura 4.2).
cdigo
don't care
endereo direto
posio 0 (0H)
rea de dados
primeira parcela
segunda parcela
terceira parcela
resultado
posio 128
posio 129
posio 130
posio 131
(80H)
(81H)
(82H)
(83H)
O programa seria:
Simblico
Comentrios
LDA 128
ADD 129
ADD 130
STA 31
HLT
4-3
Esse programa pode ser editado em linguagem de mquina (tanto em hexa como em
decimal), depurado e executado usando o simulador/depurador NEANDER, cujos comandos
foram apresentados no captulo respectivo. A codificao em linguagem de mquina
correspondente a cada uma das instrues mostradas acima seria:
Simblico
Hexa
Decimal
LDA 128
ADD 129
ADD 130
STA 131
HLT
20
30
30
10
F0
32
48
48
16
240
80
81
82
83
128
129
130
131
4 . 7 Concluso
NEANDER um computador muito simples, desenvolvido apenas para fins didticos.
Processadores modernos so muito mais complexos que NEANDER. Entretanto, mesmo
processadores utilizados nas mais sofisticadas estaes de trabalho so baseados nos
conceitos elementares que voc aprendeu com NEANDER.
4 . 8 Exerccios de programao usando o NEANDER
Os exerccios apresentados aqui so apenas uma amostra do que pode ser programado com
NEANDER. Na definio de novos problemas, o nico cuidado que deve ser tomado com
a memria disponvel para programa e dados, que compreende apenas 256 posies. Exceto
onde explicitado, todos os nmeros e endereos so representados na base decimal.
Para todos os programas sugeridos, vale a seguinte conveno:
incio do programa
- posio 0 (0H)
incio da rea de dados - posio 128 (80H)
Essa conveno adotada apenas para facilitar a correo dos programas.
1. Limpar o acumulador: faa 4 programas diferentes que zerem o acumulador.
2. Somar duas variveis de 8 bits: faa um programa para somar duas variveis
representadas em complemento de dois. As variveis e o resultado esto dispostos
segundo o mapa de memria abaixo:
posio 128: primeira varivel
posio 129: segunda varivel
posio 130: resultado
3. Subtrair duas variveis: faa um programa para subtrair duas variveis de 8 bits
representadas em complemento de dois. O resultado deve aparecer na posio de memria
consecutiva s ocupadas pelas variveis.
posio 128: minuendo
posio 129: subtraendo
posio 130: resultado
4. Comparao: determine qual a maior de 3 variveis positivas de 8 bits armazenadas em
posies consecutivas de memria. O resultado (ou seja, a maior varivel), deve aparecer
na primeira posio livre de memria na rea reservada aos dados.
5. Determinao de overflow na soma: faa um programa que determine a ocorrncia de
overflow na soma de duas variveis. As variveis so de 8 bits em complemento de dois e
esto armazenadas em posies consecutivas de memria. O resultado da soma, tambm
4-4
em 8 bits, deve aparecer na primeira posio livre e overflow deve ser indicado da
seguinte forma:
posio 130: contedo = 0H
contedo = FFH
6. Limpeza de uma rea de memria: faa um programa para zerar 32 posies consecutivas
na memria.
4-5
Captulo
CINCO
Computador hipottico Ahmes
instruo
memria
endereo
operando
Este computador simulado foi batizado em homenagem ao escriba Ahmes, do antigo Egito (1650 A.C.),
autor de uma srie de papiros contendo regras que possibilitavem clculos aritmticos complexos, como o
clculo de rea de polgonos e manipulao de fraes.
5-1
5 . 3 Conjunto de instrues
O conjunto de instrues de AHMES compreende 24 instrues, codificadas atravs de um
byte de cdigo (Tabela 5.1). Note-se que, na maioria das vezes, os quatro bits mais
significativos so suficientes para definir completamente a instruo.
Cdigo binrio
(relevante)
0000 xxxx
0001 xxxx
0010 xxxx
0011 xxxx
0100 xxxx
0101 xxxx
0110 xxxx
0111 xxxx
1000 xxxx
1001 00xx
1001 01xx
1001 10xx
1001 11xx
1010 00xx
1010 01xx
1011 00xx
1011 01xx
1011 10xx
1011 11xx
1110 xx00
1110 xx01
1110 xx10
1110 xx11
1111 xxxx
Cdigo binrio
(com zeros)
0000 0000
0001 0000
0010 0000
0011 0000
0100 0000
0101 0000
0110 0000
0111 0000
1000 0000
1001 0000
1001 0100
1001 1000
1001 1100
1010 0000
1010 0100
1011 0000
1011 0100
1011 1000
1011 1100
1110 0000
1110 0001
1110 0010
1110 0011
1111 0000
Cdigo
hexadecimal
00
10
20
30
40
50
60
70
80
90
94
98
9C
A0
A4
B0
B4
B8
BC
E0
E1
E2
E3
F0
Cdigo
decimal
0
16
32
48
64
80
96
112
128
144
148
152
156
160
164
176
180
184
188
224
225
226
227
240
Instruo
(mnemnico)
NOP
STA
LDA
ADD
OR
AND
NOT
SUB
JMP
JN
JP
JV
JNV
JZ
JNZ
JC
JNC
JB
JNB
SHR
SHL
ROR
ROL
HLT
end
end
end
end
end
end
end
end
end
end
end
end
end
end
end
end
end
lgicas, uma vez que usam operaes da lgebra booleana (mas manipulando oito bits de
cada vez, e no um s bit). As instrues JMP , JN, JP, JV, JNV, JZ, JNZ, JC, JNC, JB e JNB so
as instrues de desvio, e nelas end corresponde ao endereo de desvio, ou seja, qual o
endereo da prxima instruo a ser executada. As instrues SHR , SHL, ROR e ROL so as
instrues de deslocamento.
Instruo Execuo
nenhuma operao
end MEM(end) AC
end AC MEM(end)
end AC AC + MEM(end)
end AC AC or MEM (end)
end AC AC and MEM(end)
NOP
STA
LDA
ADD
OR
AND
NOT
SUB
JMP
JN
JP
JV
JNV
JZ
JNZ
JC
JNC
JB
JNB
SHR
SHL
ROR
ROL
HLT
end
end
end
end
end
end
end
end
end
end
end
end
AC NOT AC
AC AC MEM(end)
PC end
IF N =1 THEN PC end
IF N =0 THEN PC end
IF V =1 THEN PC end
IF V =0 THEN PC end
IF Z =1 THEN PC end
IF Z =0 THEN PC end
IF C =1 THEN PC end
IF C =0 THEN PC end
IF B=1 THEN PC end
IF B=0 THEN PC end
CAC(0); AC(i-1)AC(i); AC(7) 0
CAC(7); AC(i)AC(i-1); AC(0)0
CAC(0); AC(i-1)AC(i); AC(7)C
CAC(7); AC(i)AC(i-1); AC(0)C
Interrompe o processamento
Comentrio
nenhuma operao
armazena acumulador na memria (store)
carrega acumulador da memria (load)
soma
ou lgico
e lgico
inverte (complementa) acumulador
subtrao
desvio incondicional (jump)
desvio condicional (jump if negative)
desvio condicional (jump if positive)
desvio condicional (jump if overflow)
desvio condicional (jump if not overflow)
desvio condicional (jump if zero)
desvio condicional (jump if non-zero)
desvio condicional (jump if carry)
desvio condicional (jump if not carry)
desvio condicional (jump if borrow)
desvio condicional (jump if not borrow)
deslocamento para direita (shift right)
deslocamento para esquerda (shift left)
rotao para direita (rotate right)
rotao para esquerda (rotate left)
trmino de execuo - (halt)
5 . 4 Cdigos de condio
A unidade lgica e aritmtica de AHMES fornece os seguintes cdigos de condio, que so
usados pelas instrues de desvio condicional (conforme Tabela 5.2):
N - (negativo) : sinal do resultado, interpretado como complemento de dois
1 - resultado negativo
0 - resultado positivo
Z - (zero) : indica resultado igual a zero, interpretado como complemento de dois
1 - resultado igual a zero
0 - resultado diferente de zero
V - (overflow) :
C - (carry) :
indica a existncia de um vai-um aps uma operao de soma
1 - ocorreu vai-um
5-3
0 - no ocorreu vai-um
B - (borrow) :
indica a existncia de um empresta-um aps uma operao de subtrao
1 - ocorreu empresta-um
0 - no ocorreu empresta-um
As instrues do AHMES afetam os cdigos de condio conforme indicado na Tabela 5.3.
Note-se que somente as instrues aritmticas, lgicas e de deslocamento (alm da instruo
LDA) afetam os cdigos de condio. As instrues de desvio (e a instruo STA), apesar de
testarem este cdigos, no os alteram.
Instruo
NOP
STA
LDA
ADD
OR
AND
NOT
SUB
JMP
Jxxx
SHR
SHL
ROR
ROL
HLT
end
end
end
end
end
end
end
end
Cdigos alterados
nenhum
nenhum
N, Z
N, Z, V, C
N, Z
N, Z
N, Z
N, Z, V, B
desvio incondicional - nenhum
desvios condicionais - nenhum
N, Z, C
N, Z, C
N, Z, C
N, Z, C
nenhum
5-4
Experimente agora com diversos pares de operandos nos endereos 128 e 129:
1.1: 7 e 5, 15 e 12, 100 e 26, 110 e 17. Em todos estes casos, a soma no produz nem
carry nem overflow.
1.2: 7 e 251 (-5 em complemento de dois), 15 e 244 (-12 em complemento), 100 e 230
(-26), 110 e 239 (-17). Nestes casos, a soma produz carry (C=1), mas no overflow
(V=0). Isto indica que o resultado est correto. O mesmo ocorre para 249 e 251 (-7 e 5 em complemento de dois), 241 e 244 (-15 e -12 em complemento de dois), 156 e
230 (-100 e -26), 146 e 239 (-110 e -17).
1.3: 127 e 5, 116 e 12, 100 e 28, 110 e 120. Nestes casos, no produzido carry
(C=0), mas ocorre overflow (V=1). Em todos os casos exemplificados, os operandos
so positivos, mas o resultado negativo, o que indica estouro de representao.
1.4: 128 e 251 (-128 e -5 em complemento de dois), 241 e 136 (-15 e -120 em
complemento de dois), 156 e 226 (-100 e -30), 146 e 238 (-110 e -18). Nestes casos,
ocorre tanto carry (C=1) como overflow (V=1). Em todos os casos exemplificados, os
operandos so negativos, mas o resultado positivo, o que indica estouro de
representao.
2. O sinal de carry, em mltiplas somas, cumulativo. Isto significa que, quando se
somam trs ou mais parcelas, o nmero de vai-uns deve ser contado, para determinar
qual a quantidade final (ou seja, se ocorreu um vai-dois, vai-trs, etc)
3. O sinal de overflow, em mltiplas somas, deve ser analisado cuidadosamente. Se o
overflow ocorrer um nmero mpar de vezes, ento garantido que ocorreu overflow
no resultado final. Se entretanto ocorrer overflow um nmero par de vezes, isto no
significa necessariamente que ocorreu estouro da representao do resultado final.
Seja, por exemplo, 127 + 1 + -1. Em complemento de dois, tem-se 01111111 +
00000001 + 11111111. A soma das duas primeiras parcelas resulta em 10000000,
com indicao de overflow. A soma seguinte, 1000000 + 11111111, resulta em
011111111, tambm com indicao de overflow. Neste caso, o resultado final est
correto (127 em decimal), e os dois sinais de overflow anulam-se mutuamente. No
caso de 127 + 127 + 127 + 127, entretanto, tambm ocorre overflow duas vezes, mas
o resultado final (252 em decimal, ou seja, -4) est incorreto, ou seja, realmente
ocorreu overflow.
4. O sinal de borrow o inverso do carry. Isto pode ser verificado comparando-se uma
operao de subtrao com uma adio com o complemento do subtraendo, ou seja, no
5-5
lugar de a b realiza-se a + not (b) + 1. Como pode ser visto na tabela abaixo, o carry
resultante sempre o inverso do borrow:
a+
0
0
1
1
not(b) +
1
0
1
0
1
1
1
1
1
r
0
1
1
0
carry
1
0
1
1
a
0
0
1
1
b
0
1
0
1
r
0
1
1
0
borrow
0
1
0
0
Assim, se o carry for um, significa que o borrow zero, e vice-versa. Isto pode ser
observado comparando-se o borrow (B) da operao 5 7 atravs de uma instruo
de SUB com o carry (C) gerado pela operao 5 + (-7) atravs de uma instruo de
ADD. Note-se que o AHMES gera carry e borrow em instrues distintas - o borrow
o da ltima operao de SUB, e o carry e o da ltima operao de ADD ou de
deslocamento. Assim, no AHMES, os indicadores de carry e borrow (C e B) no
possuem nenhuma relao entre si.
5 . 5 . 2 Aritmtica de inteiros positivos
Apesar de projetado para trabalhar com nmeros em complemento de dois, AHMES (e
tambm todos os processadores que utilizam complemento de dois) tambm pode manipular
nmeros inteiros positivos. As operaes de adio e subtrao (instrues ADD e SUB)
podem ser utilizadas sem restries ou modificaes, mas os cdigos de condio devem ser
analisados de forma diversa, conforme indicado a seguir:
1. O cdigo de sinal (N) no tem mais significado.
2. O cdigo de overflow (V) tambm perde o significado e no deve ser utilizado.
3. Os cdigos de carry (C) e borrow (B) mantm o seu significado original, e passam
adicionalmente a indicar tambm estouro de representao. Isto significa que a
indicao de carry aps uma soma (C=1 aps ADD) e borrow aps uma subtrao
(B=1 aps SUB) so sinnimos de estouro de representao.
4. O cdigo de zero (Z) mantm seu significado.
5 . 5 . 3 Aritmtica em complemento de um
A aritmtica em complemento de um em si bem semelhante de complemento de dois; a
diferena bsica est na representao de nmero negativos, que possuem a quantidade 1 a
mais. Isto permite que um computador projetado com aritmtica em complemento de dois
tambm possa manipular, com relativa facilidade, nmeros em complemento de um.
Conforme visto na seo 2.3.3, a soma de dois nmeros em complemento de um requer uma
eventual correo do resultado, atravs da soma do carry:
0
2
4
6
LDA 128
ADD 129
JNC 8
ADD 130
8HLT
5-6
LDA 128
SUB 129
4
correto
6
JNB 8
SUB 130
8HLT
5-7
Captulo
SEIS
Multiplicao e Diviso
(63 x 3 x 1)
(63 x 2 x 10)
(63 x 1 x 100)
6-1
0
1 1
+ 1 1 0
1 0 1 0
0
0
0
1
1
1
x 1
1
1 1
0 0
0 0
1 1
1 0
1 0
1
1
1
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
1 0
1 1
1 0
0
0 0 0 1 0
1
1
1
0
0
0
0
0
1
1
0
1
1
1 0
1 1
1 0
0
0 0 0 1 0
Para um computador, somar diversas parcelas bem mais complexo do que somar duas
parcelas. Assim, as parcelas intermedirias so somadas a medida em que so formadas:
+
1
+ 1
1 0
1
0
1
1
1
0
0
0
+
1
0
0
1
1
1
x 1
1
1 1
0 1
1 1
0 0
1 0
1 0
1
1
1
0
0
0
0
0
0
0
1
0
1
0
1
1
0
1
1
1
0
1
0
1
0
0
0 0 1 0
0 0 0 1 0
6-2
Incio: i 0, resultado 0
Se o bit de ordem i do multiplicador for zero, ir para 4.
Somar o multiplicando ao resultado (resultado resultado + multiplicando)
Deslocar o multiplicando para a esquerda (multiplicando multiplicando x 2)
Incrementar i de uma unidade (i i + 1)
Se i for menor que o nmero de bits do multiplicador, ir para 2.
Seno, terminar.
5.
Incio: i 0, R 0, r 0
Se o bit de ordem i de m for zero (mi=0), fazer c 0 e ir para 4.
Somar M a R (R R + M), c vai-um
Deslocar os 2n bits do resultado para direita, usando o vai-um da soma
anterior como novo bit mais significativo do resultado (se no houve soma, usase 0):
( R r ) desl.direita( c R r )
Incrementar i de uma unidade (i i + 1)
Se i for menor que n, ir para 2. Seno, terminar.
2. m(5) = 1, continuar em 3
3. R 100000 + 110110 = 010110, c = 1
4. (R r) desl.direita(1 010110 000100) = (101011 000010)
5. i 6; fim. Resultado = 101011000010
O mtodo pode ser melhorado ainda mais. Basta observar-se os seguintes pontos:
1. A rigor, r no necessita ser inicializado com zeros. (No exemplo anterior, basta
substituir o 000000 inicial de r por xxxxxx)
2. Uma vez analisado, um bit do multiplicador no ser mais utilizado (no influencia
mais no resultado) e pode ser descartado.
3. Considerando-se o item (2), para facilitar a anlise dos bits do multiplicador, este
tambm pode ser deslocado para a direita no passo 4. Assim, a anlise ser sempre no
bit menos significativo do multiplicador.
4. Desta maneira, a varivel i somente tem a funo de controlar que o lao seja
executado n vezes. Assim, ao invs de contar para cima de zero at n, pode-se
tambm contar para baixo de n at zero (Observe-se que um teste de zero bem
simples de ser realizado em um computador).
O algoritmo modificado em funo destas observaes pode ser visto a seguir. Sejam m,
M, R, r, n e c definidos como anteriormente.
1.
2.
3.
4.
5.
Incio: i n, R 0
Deslocar m para a direita, juntamente com o carry. Note-se que o bit menos
significativo de m levado para o carry:
( m c ) desl.direita( m )
Se c = 0, ir para 4.
Somar M a R (R R + M), c vai-um
Deslocar os 2n bits do resultado para direita, usando o vai-um da soma
anterior como novo bit mais significativo do resultado (se no houve soma, usase 0 devido ao passo 2):
( R r ) desl.direita( c R r )
Decrementar i de uma unidade (i i 1)
Se i no for zero, ir para 2. Seno, terminar. Resultado em (R r)
6-4
1.
2.
3.
4.
5.
Incio: i n, R 0
Deslocar m para direita (o bit menos significativo vai para o carry). Se o carry
for zero (c=0), ir para 4.
Somar M a R (R R + M), c vai-um
Deslocar os 2n bits do resultado para direita, usando o c como novo bit mais
significativo do resultado: ( R m ) desl.direita( c R m )
4.1. Deslocar R para direita (carry recebe o bit menos significativo).
4.2. Deslocar r para direita (carry torna-se o novo bit mais significativo).
Decrementar i de uma unidade (i i 1)
Se i no for zero, ir para 2. Seno, terminar. Resultado em (R m).
Instruo
LDA 136
STA 132
LDA 134
STA 130
LDA 129
STA 133
LDA 133
SHR
STA 133
JNC 25
LDA 130
ADD 128
STA 130
LDA 130
ROR
STA 130
LDA 131
ROR
STA 131
LDA 132
SUB 135
STA 132
JNZ 12
HLT
endereo 128
endereo 129
endereo 130
endereo 131
endereo 132
endereo 133
constante 0:
constante 1:
constante 8:
endereo 134
endereo 135
endereo 136
Comentrios
Inicializa contador com n (oito no caso)
Inicializa R com zero
Inicializa multiplicador com m
Incio do lao: Carrega multiplicador em AC
Desloca m; carry recebe o bit menos significativo
Salva o multiplicador
Se no houve carry, vai para o deslocamento
Carrega R em AC
Soma R + M; resultado parcial no acumulador
Salva o resultado parcial
Carrega resultado parcial (bits mais significativos) em AC
Desloca para direita com carry
Salva o resultado deslocado
Carrega resultado parcial (bits menos significativos) em AC
Desloca para direita com carry
Salva o resultado deslocado
Carrega o contador em AC
Decrementa de um
Salva o contador
Se no for zero, executa mais uma vez o lao
Fim; resultado em R e m
Endereo
0
2
4
6
8
10
12
14
15
17
19
21
23
24
26
28
29
31
33
35
37
39
Instruo
LDA 136
STA 132
LDA 134
STA 130
LDA 129
STA 133
LDA 133
SHR
STA 133
LDA 130
JNC 23
ADD 128
ROR
STA 130
LDA 131
ROR
STA 131
LDA 132
SUB 135
STA 132
JNZ 12
HLT
Comentrios
Inicializa contador com n (oito no caso)
Inicializa R com zero
Inicializa multiplicador com m
Incio do lao: Carrega multiplicador em AC
Desloca m; carry recebe o bit menos significativo
Salva o multiplicador
Carrega resultado parcial (bits mais significativos) em AC
Se no houve carry (no SHR), vai para o deslocamento
Soma R + M; resultado parcial no acumulador
Desloca R para direita com carry
Salva o resultado deslocado
Carrega resultado parcial (bits menos significativos) em AC
Desloca para direita com carry
Salva o resultado deslocado
Carrega o contador em AC
Decrementa de um
Salva o contador
Se no for zero, executa mais uma vez o lao
Fim; resultado em R e r
6-6
Incio: i n, R 0
Deslocar m para direita (o bit menos significativo vai para o carry). Se o carry
for zero (c=0), ir para 4.
Somar M a R (R R + M), c vai-um
Deslocar os 2n bits do resultado para direita, usando o c como novo bit mais
significativo do resultado: ( R m ) desl.direita( c R m )
4.1. Deslocar R para direita (carry recebe o bit menos significativo).
4.2. Testar o carry (que contem o bit menos significativo de R). Se for zero, no
h nada para fazer (o bit mais significativo de m j zero, devido ao passo 2). Se
for um, ligar o bit mais significativo de m.
5.
Instruo
LDA 136
STA 132
LDA 134
STA 130
LDA 129
STA 131
LDA 131
SHR
STA 131
LDA 130
JNC 23
ADD 128
ROR
STA 130
JNC 34
LDA 131
OR 137
STA 131
LDA 132
SUB 135
STA 132
JNZ 12
HLT
constante 0:
endereo 134
constante 1:
endereo 135
constante 8:
endereo 136
constante 128: endereo 137
Comentrios
Inicializa contador com n (oito no caso)
Inicializa R com zero
Inicializa multiplicador com m
Incio do lao: Carrega multiplicador em AC
Desloca m; carry recebe o bit menos significativo
Salva o multiplicador
Carrega resultado parcial (bits mais significativos) em AC
Se no houve carry (no SHR), vai para o deslocamento
Soma R + M; resultado parcial no acumulador
Desloca R para direita; carry recebe bit menos significativo
Salva o resultado deslocado
Se carry zero, bits menos significativos (m) esto OK
Carrega resultado parcial (bits menos significativos) em AC
Liga o bit mais significativo do resultado (m)
Salva o resultado deslocado
Carrega o contador em AC
Decrementa de um
Salva o contador
Se no for zero, executa mais uma vez o lao
Fim; resultado em R e m
6-8
63
123
(7749 6300 = 1449)
(1449 1260 = 189)
(189 189 = 0)
1 0
1
1
1
1
0
1
0
0
0
0
1
1
1
1
0
0
0
0
0
1
0
1
1
1
0
0
0
1
1
1
0
0
1
1
1
1
1
0
1
1
0
0
0 0 0 1 0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
1 1 0 0 1 1
1 1 0 1 1 0
1
1
0
0 0
Note-se que, como no sistema decimal, depois de cada subtrao (ou tentativa mal sucedida
de subtrao, se o dgito calculado para o quociente for zero) um novo dgito do dividendo
incorporado anlise, isto , um novo dgito do dividendo baixado para o resultado da
subtrao. E, tambm como no sistema decimal, o nmero de bits do dividendo que
participam da primeira anlise escolhido de tal forma que formem um nmero maior que o
divisor, isto , que a primeira subtrao seja possvel.
Com um dividendo de m bits e um divisor de n bits obtm-se um quociente de mn bits
e um resto de n bits. A diviso em um computador, sendo a operao inversa da
multiplicao, opera com um dividendo de 2n bits, um divisor de n bits e fornece
quociente e resto em n bits. Ao contrrio da multiplicao, entretanto, onde o resultado
sempre representvel sem estouro, na diviso o quociente pode no ser representvel em
n bits. Nestes casos sinaliza-se estouro de representao. Nos casos em que o dividendo
tem somente n bits, ele deve ser inicialmente expandido para 2n bits, incluindo-se n
zeros esquerda do dividendo.
Para diviso de dois nmeros representados como inteiros positivos usa-se o mtodo abaixo,
onde o dividendo D tem 2n bits e o divisor v tem n bits. Note-se que, nesta
representao no existem nmeros negativos. Assim, um teste comparativo deve ser feito
para verificar se a subtrao possvel, ou seja, se o resultado ser um nmero positivo.
Observe-se tambm que sua aplicao restringe-se aos nmeros naturais sem o zero. A
incluso do zero, obrigaria ao teste do valor do divisor, abortando a operao se esta for
uma tentativa de diviso por zero.
1. Incio: formar r com os n+1 bits mais significativos do dividendo D, i n.
2. Se r v, ento subtrair r rv e colocar 1 no bit menos significativo de q
(quociente). Seno, somente colocar 0 no bit menos significativo de q. Obs: neste
passo, usar somente n bits para representar r.
3. Decrementar i (i i1). Se i=0, encerrar. O resto est em r e o quociente em q.
4. Deslocar r para esquerda, mantendo o bit mais significativo (ou seja, representar
r com n+1 bits). Como novo bit menos significativo, utilizar o bit seguinte do
dividendo original (baixar um bit). Deslocar q tambm para a esquerda. Ir para
o passo 2.
Exemplo: sejam D = 101011000010 e v = 110011. Ento tem-se:
6-9
1. r 1010110, i 6
2. r v (1010110 110011). Ento r 1010110 110011 = 100011 e q 1
3. i 5
4. r 1000110, q 1x
2. r v (1000110 110011). Ento r 1000110 110011 = 010011 e q 11
3. i 4
4. r 0100110, q 11x
2. r < v (0100110 < 110011). Ento r 100110 e q 110
3. i 3
4. r 1001100, q 110x
2. r v (1001100 110011). Ento r 1001100 110011 = 011001 e q 1101
3. i 2
4. r 0110011, q 1101x
2. r v (0110011 110011). Ento r 0110011 110011 = 000000 e q 11011
3. i 1
4. r 0000000, q 11011x
2. r < v (0000000 < 110011). Ento r 000000 e q 110110
3. i 0, encerrar. Quociente = 110110 e resto = 0
Para alguns operandos, pode ocorrer que quando for executado o passo 2, na primeira vez, o
resultado da operao r rv seja maior do que v (ou at mesmo igual a v). Nestes
casos, o algoritmo no adequado para realizao da operao (portanto, a diviso no
poder ser realizada por este mtodo: ser necessrio escolher algum outro). Para o uso
adequado deste algoritmo, interessante incluir uma observao no passo 2 de verificao do
resultado da operao r rv. Se aps esta operao obter-se r v, ento deve-se abortar a
operao, pois o quociente exigiria mais de n bits para ser representado.
A situao explicada acima exemplificada com a diviso de 11010100 por 1011. Para este
exemplo, D = 11010100 e v = 1011. Ento tem-se:
1. r 11010, i 4
2. r v (11010 1011). Ento r 11010 1011 = 1111 e q 1
Neste passo, se obtm um valor de r que maior do que o divisor (o que no faz sentido).
O prosseguimento da operao pelo algoritmo faria com que se obtenha uma resposta
incorreta.
Como poderia ser corrigido o algoritmo sem modific-lo demasiadamente? Se, para iniciar a
operao, utilizar-se apenas n bits do dividendo (D), o problema se resolve a nvel do passo
2. Mas agora ser necessria uma interao a mais ( preciso baixar mais um bit de D),
ento i deve ser aumentado em uma unidade. Entretanto esta uma soluo para este caso e
no universal. Experimente mudar o divisor para 0101 e observe o que ocorre. O tipo de
anlise e a viso humana sobre as variveis no so facilmente transportveis para o
computador, o que vai exigir a alterao do algoritmo para implementao na mquina.
Com isto, o algoritmo fica:
1. Incio: Se v for zero, terminar indicando erro de diviso por zero. Seno, calcular D
v. Se carry=1 (borrow=0), ento D v e terminar indicando estouro. Se no,
ento a diviso pode ser realizada.
6-10
Instruo
LDA 130
JZ 77
LDA 128
SUB 130
JNB 81
LDA 128
STA 139
LDA 129
STA 140
LDA 138
Comentrios
Carrega o divisor
Se for zero, termina
Carrega D em A
Calcula D v
Se borrow=0, ento D v, e ir ocorrer estouro
Tudo bem. Diviso pode ser realizada
Salva D em endereo temporrio
Carrega d
Salva d em endereo temporrio
Obtm a constante 8
6-11
20
22
24
26
28
29
31
33
34
36
38
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
STA 134
LDA 135
STA 131
LDA 131
SHL
STA 131
LDA 140
SHL
STA 140
LDA 139
ROL
STA 139
JC 49
LDA 139
SUB 130
JB 61
LDA 139
SUB 130
STA 139
LDA 131
OR 136
STA 131
LDA 134
SUB 136
STA 134
JNZ 26
LDA 139
STA 132
LDA 136
JMP 83
LDA 135
JMP 83
LDA 137
STA 133
HLT
Instruo
LDA 130
JZ 64
LDA 128
SUB 130
JNB 68
LDA 128
STA 132
LDA 129
STA 131
LDA 138
STA 134
LDA 131
SHL
STA 131
LDA 132
ROL
STA 132
JC 40
LDA 132
SUB 130
JB 52
LDA 132
SUB 130
STA 132
LDA 131
OR 136
STA 131
LDA 134
SUB 136
STA 134
JNZ 22
LDA 136
JMP 70
LDA 135
JMP 70
LDA 137
STA 133
HLT
Comentrios
Carrega o divisor
Se for zero, termina
Carrega D em A
Calcula D v
Se borrow=0, ento D v, e ir ocorrer estouro
Tudo bem. Diviso pode ser realizada
Salva D como o resto temporrio (r)
Carrega d
Salva d como quociente temporrio (q)
Obtm a constante 8
Inicializa contador com n (8 no caso)
Carrega d (q)
Desloca para esquerda (carry recebe bit mais significativo)
Salva d (q)
Carrega D (r)
Desloca para esquerda (com carry)
Salva D (r)
Testa o carry (antigo bit mais significativo de D(r))
Carry de r = 0, carrega r
Testa se r v
Testa o borrow; se 1, ento r < v, nada a fazer
Borrow=0, ento r > v
Calcula rv
Atualiza r
Carrega d (q)
Coloca bit do quociente em 1
Salva d (q)
Carrega contador
Decrementa contador de lao
Salva contador
Se no for zero, termina
Sinaliza fim normal
Sinaliza diviso por zero
Sinaliza estouro na diviso
Armazena indicador de estado
Fim
6-13
normal). Para contador ser utilizada a posio 134. Para as constantes, so utilizadas as
seguintes posies: 135 para zero, 136 para um, 137 para menos um (255) e 138 para oito.
Note-se que para d e q e para r e D so utilizadas as mesmas palavras de memria (131 e
132, respectivamente), o que pode ser visto nas instrues dos endereos 7 e 12.
Endereo
0
2
4
6
7
9
11
12
14
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
47
49
51
52
54
56
58
60
62
64
66
68
Instruo
LDA 130
JZ 60
LDA 129
SHL
STA 131
LDA 128
ROL
STA 132
SUB 130
JP 64
LDA 138
STA 134
LDA 132
SUB 130
JN 36
STA 132
LDA 131
OR 136
STA 131
LDA 134
SUB 136
STA 134
JZ 56
LDA 131
SHL
STA 131
LDA 132
ROL
STA 132
JMP 22
LDA 136
JMP 66
LDA 135
JMP 66
LDA 137
STA 133
HLT
Comentrios
Carrega o divisor
Se for zero, termina
Carrega d em A
Desloca para esquerda, bit mais significativo vai para carry
Salva d como q (quociente temporrio)
Carrega D em A
Desloca para esquerda
Salva D como r (resto temporrio)
Calcula D v
Se D v, ir ocorrer estouro
Tudo bem ( D < v ). Diviso pode ser realizada
Inicializa contador com n (8 no caso)
Incio do lao. Obtm r
Calcula r v
Se negativo, nada a fazer (no salva r)
Se positivo, atualiza r
Carrega q
Coloca bit do quociente em 1
Salva q
Carrega contador
Decrementa contador de lao
Salva contador
Se for zero, termina normalmente
Carrega q
Desloca para esquerda, bit mais significativo vai para carry
Salva q
Carrega r
Desloca para esquerda
Salva r
Volta para incio do lao
Sinaliza fim normal
Sinaliza diviso por zero
Sinaliza estouro na diviso
Armazena indicador de estado
Fim
6-15
Instruo
LDA 130
JZ 92
LDA 129
SHL
STA 131
LDA 128
ROL
STA 132
SUB 130
Comentrios
Carrega o divisor
Se for zero, termina
Carrega d em A
Desloca para esquerda, bit mais significativo vai para carry
Salva d como q (quociente temporrio)
Carrega D em A
Desloca para esquerda
Salva D como r (resto temporrio)
Calcula D v
16
18
20
22
24
26
28
30
32
34
36
38
40
42
44
46
48
50
52
54
56
58
60
62
64
66
68
70
71
73
75
76
78
80
82
84
86
88
90
92
94
96
98
100
JP 96
LDA 138
STA 134
LDA 136
STA 139
LDA 139
JZ 38
LDA 132
SUB 130
STA 132
JMP 44
LDA 132
ADD 130
STA 132
JN 56
LDA 131
OR 136
STA 131
LDA 136
JMP 58
LDA 135
STA 139
LDA 134
SUB 136
STA 134
JZ 80
LDA 131
SHL
STA 131
LDA 132
ROL
STA 132
JMP 26
LDA 132
JP 88
ADD 130
STA 132
LDA 136
JMP 98
LDA 135
JMP 98
LDA 137
STA 133
HLT
Se D v, ir ocorrer estouro
Tudo bem ( D < v ). Diviso pode ser realizada
Inicializa contador com n (8 no caso)
Inicializa aux com 1
Incio do lao. Testa aux
Aux = 1
Calcula r v
Atualiza r
Aux = 0
Calcula r + v
Atualiza r
Testa o resultado da operao
Carrega q
Coloca bit do quociente em 1
Salva q
Faz aux=1 (prxima operao uma subtrao)
Faz aux=0 (prxima operao uma soma)
Atualiza varivel aux
Carrega contador
Decrementa contador de lao
Salva contador
Se for zero, termina normalmente
Carrega q
Desloca para esquerda, bit mais significativo vai para carry
Salva q
Carrega r
Desloca para esquerda
Salva r
Volta para incio da lao
Fim do lao. Testa valor do resto
Se for positivo, est correto
Se negativo, soma divisor ao resto
Salva resto corrigido
Sinaliza fim normal
Sinaliza diviso por zero
Sinaliza estouro na diviso
Armazena indicador de estado
Fim
6-17
6-18
6-21
Captulo
SETE
Nmeros em Ponto Fixo e Ponto Flutuante
Decimal = 51,5
0 1 1 0 0 1,1 1
Decimal = 25,75
0 1 1 0 0,1 1 1
Decimal = 12,875
0 1 1,0 0 1 1 1
Decimal = 3,21875
0,1 1 0 0 1 1 1
,01 1 0 0 1 1 1
7-1
t
8
7
6
5
4
3
2
1
0
f
0
1
2
3
4
5
6
7
8
Frao (A)
1011
1011
0100
1011
1011
0100
Frao
1010
0100
1110
1000
1010
1000
7-4
total de bits da mantissa e do expoente) pode ser representada. Os nmeros esto ento
dispersos dentro desta faixa.
Os nmeros em ponto flutuante so inerentemente redundantes, no sentido que um mesmo
nmero pode ser representado de mais de uma maneira. Por exemplo, um quintilho pode
ser representado por 1,0.1018, ou 0,1.10 19, ou mesmo 100.1016. Assim, desejvel que
exista uma forma normalizada de representar um nmero. Para tanto, utiliza-se somente
mantissas normalizadas. Uma mantissa est normalizada quando constituda somente de
uma parte fracionria (no existe parte inteira) e quando o primeiro dgito a direita da vrgula
diferente de zero. Assim, a forma normalizada de representar um quintilho dada por
0,1.1019.
Na base binria, a normalizao da mantissa exige que os seus dois bits mais significativos
sejam diferentes. Assim, para nmeros positivos a mantissa inicia sempre por 0,12. Para
nmeros em complemento de dois, isto implica em que o dgito mais significativo da
mantissa e o bit de sinal sejam diferentes - para nmeros positivos a mantissa inicia ento por
0,1 2 e para nmeros negativos a mantissa inicia por 1,02. Assim, a normalizao restringe a
magnitude |M| de uma mantissa ao intervalo
1/2 |M| < 1
Um nmero no normalizado normalizado facilmente, atravs de deslocamentos da
mantissa para a direita ou esquerda e incrementos ou decrementos do expoente,
respectivamente. Note-se que um eventual estouro de representao na mantissa facilmente
resolvido: basta deslocar a mantissa para a direita, corrigir o bit mais significativo, e somar
um ao expoente. Um estouro de representao no expoente, entretanto, indica um estouro na
capacidade de representao dos nmeros em ponto flutuante. Se o expoente ultrapassou o
maior expoente positivo, fala-se em overflow; se o expoente ultrapassou o menor
negativo, fala-se ento em underflow, e o resultado fornecido normalmente zero.
A representao do nmero zero apresenta algumas caractersticas peculiares, que
influenciam fortemente no formato utilizado para representar nmeros em ponto flutuante em
binrio. A mantissa deve ser naturalmente, igual a zero, mas o expoente pode apresentar
qualquer valor, uma vez que 0.be igual a 0 para todos os valores de b e e. Com isto
tem-se:
1. A mantissa do nmero zero deve apresentar todos os seus bits em zero, para facilitar o
teste por zero. Note-se que isto vai contra a definio formal de uma mantissa
normalizada.
2. O nmero zero na realidade a menor quantidade absoluta possvel de representao.
Durante a realizao de diversos clculos, entretanto, arredondamentos e truncagens
podem levar a resultados que sejam nmeros bem pequenos, mas no exatamente
iguais a zero. Para indicar o fato do zero estar bem prximo em magnitude destes
nmeros, o expoente escolhido para o zero deve ser o maior nmero negativo representvel. Assim, por exemplo, se o expoente possuir k bits e for representado em
complemento de dois, o expoente utilizado para o zero dever ser 2k-1.
3. Pelas consideraes anteriores, tem-se que o zero representado por 0.b 2k-1 .
Entretanto, para facilitar o teste de um nmero para verificar se ele igual a zero,
desejvel que o nmero zero seja uma sequncia de bits em zero, sem nenhum bit em
um. Isto est em contradio com a representao acima. Para resolver este problema,
codifica-se o expoente em excesso de 2 k-1, ou seja, um expoente em zero significa
na realidade a maior magnitude negativa representvel. A codificao em excesso
indica que existe uma quantidade a mais somada ao expoente (no caso, 2 k-1); para
obter-se o valor real do expoente deve-se subtrair esta quantidade do valor armazenado
no campo de expoente. Ou seja, e real = e 2 k-1. Para um expoente de 8 bits em
complemento de dois, por exemplo, tem-se ento uma codificao em excesso de
128: o expoente 128 representado por 0; o expoente 0 representado por 128; e o
expoente 127 (o maior possvel) dado por 255.
7-5
Duplo
Qudruplo
Campos:
S = sinal
E = expoente
L = primeiro bit
F = frao
1 bit
8 bits
(no representado)
23 bits
1 bit
11 bits
(no representado)
52 bits
1 bit
15 bits
1 bit
111 bits
Expoente
Excesso-de
Maior valor
Menor valor
127
255
0
1023
2047
0
16383
32767
0
7-6
entretanto facilmente reduzida para o nmero normal de bits, atravs da eliminao dos
seus bits menos significativos (por truncagem ou arredondamento).
X x Y = (Xm x Ym) . 2(Xe+Ye)
Aps a multiplicao o resultado tambm deve ser normalizado; durante este processo pode
ocorrer estouro de representao (se ocorrer estouro na representao do expoente).
7 . 9 Diviso de nmeros em ponto flutuante
Nmeros em ponto flutuante so divididos facilmente. Basta dividir as mantissas e subtrair
os expoentes. A mantissa do dividendo inicialmente expandida para o dobro do seu nmero
de bits (pela incluso de zeros a direita) e depois as duas mantissas so divididas pelo mesmo
algoritmo utilizado para nmeros inteiros. Note-se que agora o resto normalmente
desprezado, e as etapas que na diviso inteira corrigiam quociente e resto podem ser
eliminadas.
X Y = (X m Ym) . 2(XeYe)
Aps a diviso o resultado tambm deve ser normalizado; durante este processo pode ocorrer
estouro de representao (se ocorrer estouro na representao do expoente).
7-8
Captulo
OITO
Codificaes BCD, Numrica e Alfanumrica
Cd.Aiken
(2421)
0000
0001
0010
0011
0100
1011
1100
1101
1110
1111
Cd.Stibitz
(8421 3)
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
Cd.7421
(7421)
0000
0001
0010
0011
0100
0101
0110
0111
1001
1010
Cd. 642-1
(642-1)
0000
0011
0010
0101
0100
0111
1000
1011
1010
1101
2. Dgito ilegal sem vai-um. Neste caso o resultado est entre 10 e 15 (em binrio); para
obter-se o dgito correto deve-se subtrair 10 do dgito (ou somar seis, o que
equivalente), e gerar-se um vai-um para o dgito decimal seguinte.
3. Dgito legal com vai-um. Este caso ocorre quando o resultado cai entre 16 e 19; da
mesma maneira que o caso 2, para obter-se o dgito correto deve-se subtrair 10 do
dgito (ou somar seis). O vai-um gerado est correto.
Por exemplo, seja A=0832 e B=0983. Ento tem-se:
A=
B=
0000
0000
0001
caso 1
1000
1001
0001
caso 3
0011
1000
1011
caso 2
0010
0011
0101
caso 1
Para corrigir o resultado, deve-se somar seis nos dgitos dos casos 2 e 3. No caso 2, ainda
necessrio propagar um vai-um (isto no necessrio no caso 3, pois o vai-um j foi
gerado).
1
0001
0001
1011
0101
0110
0110
0001
1000
0001
0101
Com isto tem-se 1815, que o resultado correto. Uma desvantagem da correo do resultado
dessa maneira que as correes do tratamento do vai-um no caso 2 podem criar novas
correes, como por exemplo no caso de A=0372 e B=0633:
A=
B=
0000
0000
0001
0011
0110
1001
0000
1
1001
0000
1010
caso 2
0111
0011
1010
caso 2
0010
0011
0101
1010
0110
0000
0101
0101
E a nova correo deste novo caso 2 fornece o resultado correto (1005). Para evitar este
tratamento especial, foi criado o algoritmo de Hellerman, que soma 6 em todos os dgitos de
um dos operandos antes da soma das duas parcelas. Assim, s existem dois casos a serem
tratados, distinguidos pelo vai-um:
1. O resultado no deu vai-um e ento caiu entre 6 e 15. Deve-se subtrair 6 para obter o
dgito correto.
2. O resultado produziu um vai-um. Ento este vai-um j foi propagado e o dgito
est correto entre 0 e 9.
Por exemplo, seja A=0372 e B=0633. Ento tem-se:
A=
soma de 6
0000
0110
0110
0011
0110
1001
0111
0110
1101
0010
0110
1000
Se a primeira etapa produzir um vai-um entre dgitos decimais, isto significa que o dgito
original do operando ter sido ilegal; este nmero est mal representado. A segunda etapa
realiza a soma de (A+6) com o segundo operando (B):
8-2
A+6=
B=
1
0110
0000
0111
caso 1
1
1001
0110
0000
caso 2
1101
0011
0000
caso 2
1000
0011
1011
caso 1
operaes aritmticas estes cdigos esto em desuso, mas como uma maneira de armazenar
nmeros decimais eles ainda so utilizados.
Como j foi visto, existem 2,9x10 10 diferentes possibilidades para implementar-se uma
codificao BCD. Algumas delas foram analisadas no captulo anterior. Dois dos cdigos
BCD ainda so bastante utilizados hoje em dia: o BCD natural e o cdigo em excesso-de-trs
(Stibitz). Ambos esto reproduzidos abaixo:
Dgito decimal
0
1
2
3
4
5
6
7
8
9
NBCD
(8421)
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
Excesso-de-3
(8421 3)
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
A soma dos dois dgitos nove ou menos. Neste caso, a soma em excesso resultar
em um dgito que 15 ou menos, e nenhum carry ser gerado. Nestes casos, basta
subtrair 3 do resultado para obter o dgito corretamente codificado em excesso de 3.
A soma dos dois dgitos 10 ou mais. Neste caso, a representao em excesso ser
16 ou mais. Como X e X+16 tem o mesmo cdigo, a diferena est na gerao de
um vai-um. Para corrigir o resultado, ou seja, representar X em excesso de 3,
basta somar 3.
Assim, a regra para a soma em excesso de trs simples: soma-se os dgitos usando
aritmtica binria; se um vai-um gerado, somar 3 (0011) ao dgito decimal; seno,
subtrair 3 (0011) ao dgito decimal (ou somar 1101 e desprezar o vai-um).
Diversos outros cdigos tambm podem ser desenvolvidos atribuindo-se pesos distintos s
diversas posies; o nome destes cdigos normalmente formado pelos pesos. Abaixo so
exemplificados alguns deles (4221, 2421 (Aiken), 5421, 7421, e 642(-1), com peso
negativo). Note-se que a escolha dos pesos no determina de forma inequvoca a
codificao, mas apenas facilita sua compreenso. Assim, por exemplo, no cdigo 4221 o
dgito decimal 2 pode ser codificado tanto por 0010 (como na tabela) como por 0100; o
dgito 6 poderia ser codificado como 1010 ou por 1100 (esta ltima utilizada na tabela).
8-4
Dgito decimal
0
1
2
3
4
5
6
7
8
9
4221
0000
0001
0010
0011
1000
0111
1100
1101
1110
1111
2421
0000
0001
0010
0011
0100
1011
1100
1101
1110
1111
5421
0000
0001
0010
0011
0100
1000
1001
1010
1011
1100
7421
0000
0001
0010
0011
0100
0101
0110
0111
1001
1010
642(-1)
0000
0011
0010
0101
0100
0111
1000
1011
1010
1101
Cd. 74210
11000
00011
00101
00110
01001
01010
01100
10001
10010
10100
Dgito decimal
0
1
2
3
4
5
6
7
8
9
50
01
01
01
01
01
10
10
10
10
10
43210
00001
00010
00100
01000
10000
00001
00010
00100
01000
10000
Cd. Gray
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
8-6
0 1 1 0 1
1 1 1 0 1 1
001
001110
00111001
001110010
Ou seja, obtm-se 001110010, que corresponde em decimal a 114. Note-se que a regra geral
alterna entre cpia dos bits e a inverso dos bits; cada bit em 1 indica que deve ser realizada
uma troca (deste 1 inclusive).
Este cdigo Gray em particular um cdigo binrio refletido. Um cdigo dito refletido
quando ele simtrico (com exceo do bit de mais alta ordem) em relao ao ponto mdio
da lista codificada em ordem crescente de valor. Os cdigos Gray que no so refletidos so
complexos de serem codificados.
Existem diversos cdigos Gray com diferentes tamanhos de ciclo (nmeros de cdigos
distintos utilizados). Normalmente eles so referenciados pelo tamanho do seu ciclo e por
uma lista de nmeros. Por exemplo, o cdigo Gray visto acima referenciado como sendo
de ciclo 16 (1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,4). Os nmeros da lista indicam a posio (a
partir da direita) do bit que invertido no cdigo atual para formar o prximo cdigo. A
codificao pode iniciar em qualquer nmero binrio (no caso do exemplo, um nmero de 4
bits). Por exemplo, um cdigo Gray de comprimento 6 (1,2,1,3,2,3) ser diferente se
iniciado em nmeros binrios diferentes, conforme pode ser visto na tabela a seguir.
8-7
Dgito
decimal
0
1
2
3
4
5
6
000
000
001
011
010
110
100
000
001
001
000
010
011
111
101
001
010
010
011
001
000
100
110
010
101
101
100
110
111
011
001
101
110
110
111
101
100
000
010
110
111
111
110
100
101
001
011
111
Cdigo
00000
00001
00011
00111
01111
11111
11110
11100
11000
10000
Trs tcnicas principais sero analisadas nas sees seguintes: cdigos m-de-n, cdigos com
paridade e cdigos de Hamming. Todos estes cdigos utilizam o mesmo comprimento em
bits para sua codificao. Existem cdigos de comprimento varivel, em que os smbolos
mais freqentes utilizam menos bits que os smbolos menos freqentes. Assim, por
exemplo, a codificao da letra e utilizaria muito menos bits que a letra q. Estes cdigos,
como por exemplo cdigo Morse, cdigo de Shannon-Fano, cdigo de Huffman, no sero
analisados aqui.
8 . 8 Cdigos m-de-n
Os cdigos m-de-n so compostos de tal forma que os n bits de uma palavra binria so
formados por m uns e n-m zeros. Com esta limitao, de 2n combinaes binrias
possveis somente (n/m) combinaes, ou seja, n!/m!(n-m)!. Este nmero de combinaes
maximizado quando m=n/2 (ou m=n/2 1/2, se n for mpar).
No cdigo 2-de-5, onde palavras de 5 bits apresentam sempre 2 bits em 1, tem-se ento
exatamente 5!/2!(5-2)! = 5!/2!3! = 5.4/1.2 = 10 combinaes vlidas. Este cdigo j foi
analisado na seo 7.3 (cdigos de cinco bits ponderados, com pesos 74210). Outra
codificao possvel a 2-de-7, o cdigo biquinrio. Este cdigo j foi analisado na seo
8.5 (cdigos de sete bits ponderados, com pesos 5043210).
8 . 9 Cdigos de paridade
Nestes cdigos adicionado um bit palavra codificada, de tal forma que o nmero de uns
seja par (paridade par) ou mpar (paridade mpar). A tabela a seguir ilustra o uso de bits de
paridade par e mpar para um cdigo de trs bits.
Cdigo
000
001
010
011
100
101
110
111
Paridade par
0
1
1
0
1
0
0
1
Soma dos 1
0
2
2
2
2
2
2
4
8-9
Por exemplo, se estes dois cdigos so 0001 e 0100, sua distncia de 2; entre os cdigos
0000 e 1111 a distncia de 4. Se a distncia de Hamming for de 1, como por exemplo em
000, 100, 101, 001, 011, 111, 110 e 010, no possvel nem a deteco nem a correo de
erros; cada erro transforma um cdigo vlido em outro tambm vlido. Se a distncia for de
2, como por exemplo em 000, 011, 110 e 101, ento possvel detectar-se um erro, mas que
no pode ser corrigido (por exemplo, 001 poderia ter sido originado tanto de 000 como de
101 ou 011). Se a distncia for de 3, como por exemplo em 011 e 100, ento um erro
simples pode ser detectado e corrigido (por exemplo, 000 s poderia ter sido originado de
100), e um erro duplo pode ser detectado.
O cdigo de Hamming corrige um erro alterando a palavra errada para o cdigo vlido mais
prximo (de menor distncia), desde que esta menor distncia seja inequvoca, isto , no
existam duas ou mais palavras corretas igual distncia da palavra errada.
Para possibilitar a correo de um erro simples, o cdigo de Hamming mostrado na tabela a
seguir utiliza trs bits adicionais de paridade (A, B e C) para os quatro bits de cdigo
(ponderados por 8, 4, 2 e 1).
Posio
Cdigo
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1
A
0
1
0
1
1
0
1
0
1
0
1
0
0
1
0
1
2
B
0
1
1
0
0
1
1
0
1
0
0
1
1
0
0
1
3
8
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
4
C
0
1
1
0
1
0
0
1
0
1
1
0
1
0
0
1
5
4
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
6
2
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
7
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Assim, cba = 101, ou seja, a posio 5 est errada e seu bit deve ser invertido para ser
corrigido. Se o nmero tivesse sido recebido correto, a combinao dos bits de paridade
seria zero (000).
Esta codificao pode ser estendida para qualquer nmero n de bits de informao, desde
que k bits de paridade sejam adicionados de acordo com a frmula 2k n + k + 1. A tabela
a seguir ilustra alguns casos.
8-10
Bits de informao
4
5
11
12
26
27
57
Bits de paridade
3
4
4
5
5
6
6
000
null
soh
stx
etx
eot
enq
ack
bell
bsp
ht
lf
vt
ff
cr
so
si
001
dle
dc1
dc2
dc3
dc4
nak
syn
etb
can
em
sub
esc
fs
gs
rs
us
=
M
]
.
>
N
^
/
?
O
_
110
`
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
111
p
q
r
s
t
u
v
w
x
y
z
{
|
}
~
del
O cdigo ASCII foi posteriormente estendido para oito bits, com a incorporao de mais 128
combinaes tabela acima. Com isto pode-se representar caracteres acentuados (, , , ,
, , , , etc) e diversos smbolos especficos de diversas lnguas. No existe, entretanto,
uma definio nica para esta tabela ASCII de 8 bits; cada fabricante desenvolveu a sua
prpria.
Atualmente oito bits j se tornaram insuficientes para representar todos os smbolos
utilizados. No h espao disponvel, por exemplo, para codificao do alfabeto grego, rabe
ou cirlico (para no mencionar os alfabetos hindus, japoneses e chineses). Para solucionar o
problema, estuda-se atualmente um cdigo de 16 bits, que possibilitaria representar 65536
smbolos distintos (Unicode).
8-12
Captulo
NOVE
Elementos bsicos de organizao
9 . 1 Introduo
Um computador pode ser projetado e/ou descrito em diversos nveis de abstrao. Assim,
pode-se descrever inteiramente um computador atravs de equaes booleanas ou o seu
equivalente em portas lgicas E, OU e NOT. Devido complexidade dos computadores
atuais, entretanto, tal nvel de abstrao no prtico, por envolver milhares de equaes.
Uma das solues empregadas para diminuir o nmero de elementos a serem manipulados
envolve o uso de nveis de abstrao mais elevados, tal como o nvel de transferncia entre
registradores (em ingls Register Transfer, ou RT). Este captulo aborda os principais
elementos utilizados neste nvel.
9 . 2 Portas lgicas e equaes booleanas
A lgebra booleana definida sobre um conjunto de dois elementos, denominados de
verdadeiro e falso, ou 0 e 1. Em sistemas digitais, estes dois valores so dois nveis de
tenso pr-fixados aos quais so associados os nomes 0 e 1.
O complemento de uma varivel booleana definido pela tabela-verdade indicada na Tabela
9.1. Basicamente tem-se uma alternncia entre os dois valores.
Entrada a
0
1
Sada s
1
0
9-1
Entrada a
0
0
1
1
Entrada b
0
1
0
1
Sada s
0
0
0
1
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
s
0
0
1
0
1
1
1
1
b.c
a
Figura 9.4 - Portas lgicas para a funo a+bc
b
0
1
0
1
a
b
a+b
b(a+b)
1
1
1
0
1
0
1
1
0
1
1
0
0
0
0
0
Tabela 9.5 - Tabela verdade da funo a+b(a+b)
a
a+b
a+b(a+b)
0
1
1
1
a+b(a+b)
b
b(a+b)
Figura 9.5 - Portas lgicas para a funo a+b(a+b)
Tanto por observao da tabela-verdade da Tabela 9.5 como por simplificao da equao
booleana chega-se na equao a+b, que pode ser implementada atravs de uma nica porta
OR e representa uma grande economia de portas em relao implementao. Existem
inmeras tcnicas de simplificao de equaes booleanas, o que, entretanto, no ser tratado
neste livro. A minimizao de uma equao booleana importante em sistemas digitais por
diversos motivos. Entre os principais destacam-se:
9-3
reduo do nmero de entradas de uma porta lgica portas com menor nmero de
entradas so mais econmicas; assim, por exemplo, uma porta AND de trs entradas
melhor que uma porta AND de quatro entradas (e uma de duas entradas melhor ainda!).
reduo da potncia consumida pelo circuito.
reduo da rea fsica necessria para o circuito.
diminuio do tempo necessrio para que uma mudana em um ou mais entradas se
manifeste na sada do circuito (tempo de propagao).
Alm das portas tradicionais (AND, OR, NOT), ainda so utilizadas diversas outras. De
especial interesse so as portas NAND (no-e), NOR (no-ou), XOR (ou exclusivo) e
XNOR (no-ou exclusivo). As tabelas-verdade para estas portas esto mostradas nas Tabelas
9.6 a 9.9, respectivamente.
Entrada a
0
0
1
1
Entrada b
0
1
0
1
Sada s
1
1
1
0
Entrada b
0
1
0
1
Sada s
1
0
0
0
Entrada b
0
1
0
1
Sada s
1
0
0
1
s=(a.b)
a
b
a.b
s=(a.b)
Figura 9.6 - Porta lgica NAND de duas entradas e seu equivalente em termos de AND e
NOT
9-4
s=(a+b)
a
b
a+b
s=(a+b)
Figura 9.7 - Porta lgica NOR de duas entradas e seu equivalente em termos de OR e NOT
A operao de ou-exclusivo (Figura 9.8) derivada do ou, mas com sada em zero no caso
das duas entradas terem valor um. Esta pequena diferena torna o ou-exclusivo uma porta
com caractersticas nicas. Sua funo pode ser interpretada como soma em mdulo 2 (onde
o carry-out desprezado), ou como gerado de paridade par, ou simplesmente como o
operador diferena.
a
a
s=(ab)
ab
b
b
Figura 9.8 - Porta lgica XOR de duas entradas e porta lgica XNOR de duas entradas
Expresso equivalente
(a . b)
a nand b
(a+ b)
a nor b
a.b + a.b
(a.a), a nand a
(a+a), a nor a
a xor 1
a.b + a.b
b
0
0
1
1
0
0
1
1
c
0
1
0
1
0
1
0
1
s
1
0
1
0
1
0
1
0
termos-produto
a.b.c
a.b.c
a.b.c
a.b.c
a.b.c
a.b.c
a.b.c
a.b.c
termos-soma
a+b+c
a+b+c
a+b+c
a+b+c
a+b+c
a+b+c
a+b+c
a+b+c
9-6
Observe-se que a forma soma de produtos pode ser implementada utilizando-se somente
portas NAND no lugar das portas AND e OR, como pode ser visto na Figura 9.9. Da mesma
forma, o produto de somas pode ser implementado com portas NOR no lugar das portas
AND e OR.
a
b
s
d
Figura 9.9 - Soma de produtos atravs de portas NAND
9 . 4 Circuitos combinacionais
Circuitos combinacionais so aqueles que no possuem memria ou quaisquer outros
elementos de armazenamento. Suas sadas so funo nica e exclusivamente das entradas.
So construdos por portas lgicas sem realimentao, isto , o valor das sadas no
utilizado em qualquer outra parte do circuito.
Dois circuitos combinacionais bem simples, bastante utilizados em sistemas digitais, so os
multiplexadores e os decodificadores. Uma unidade lgica e aritmtica (ULA ou UAL), por
outro lado, bem mais complexa, e ser vista em sees posteriores.
Um multiplexador (ou seletor) um circuito combinacional que possui m entradas e uma
sada. A cada instante de tempo, o valor da sada igual ao valor de uma das entradas,
conforme determinado por um conjunto de linhas de controle (ou linhas de seleo). A
Tabela 9.12 ilustra alguns casos de multiplexadores.
Multiplexador
2-para-1
4-para-1
8-para-1
16-para-1
Nmero de entradas
2
4
8
16
b
Figura 9.10 - Portas lgicas de um multiplexador de 2-para-1
interessante notar que uma tabela-verdade pode ser simplificada se for utilizado um novo
valor o dont care, ou no interessa, representado por um X. Uma linha da tabela onde
uma varivel apresenta o valor X indica que, para o caso desta linha, o valor da varivel no
interessa para a sada, ou seja, a varivel no influencia o valor da sada neste caso.
A Tabela 9.14 mostra a tabela-verdade de um multiplexador 2-para-1 utilizando-se este novo
valor.
Entrada0 (a) Entrada1 (b) Seleo (sel)
Sada (s)
0
X
0
0
1
X
0
1
X
0
1
0
X
1
1
1
Tabela 9.14 - Tabela-verdade de um multiplexador de 2-para-1
9-8
s
b
sel
sel
8 s
sel 2
sel 2
9-9
sada 0
entrada 1
sada 1
entrada 0
sada 2
sada 3
A Tabela 9.16 mostra a variao dos valores dos sinais de sada (Q e Q) de acordo com os
sinais de entrada (R e S) ao longo de nove intervalos de tempo. A Figura 9.15 reproduz a
mesma informao em um diagrama de tempos.
t
1
2
3
4
5
6
7
8
9
R
0
0
0
1
0
1
0
0
0
S
0
1
0
0
0
0
0
1
0
Q
0
1
1
0
0
0
0
1
1
Q
1
0
0
1
1
1
1
0
0
2
3
4
5
6
7
Figura 9.15 - Diagrama de tempos em um flip-flop RS
Observe-se que, quando as entradas no esto ativas, um flip-flop RS mantm seu estado
anterior, ou seja, memoriza o ltimo valor lgico que foi armazenado nele, seja via um
comando S (set) ou R (reset). Note-se tambm que a ativao de ambas as entradas
simultaneamente leva a resultados imprevisveis. Assim, o funcionamento de um flip-flop
RS pode ser resumido de acordo com a Tabela 9.17, onde Qt indica o estado atual e Qt+1
indica o prximo estado.
R
0
0
1
1
S
0
1
0
1
Qt+1
Qt
1
0
Indeterminado
Resultado
Estado fica inalterado
Estado passa para 1
Estado passa para 0
Condio de erro
9-11
S
Q
R
Figura 9.16 - Flip-flop RS com controle
Q
Figura 9.17 - Flip-flop D sensvel ao nvel
Com o flip-flop D tem-se o elemento bsico de armazenamento, que copia o valor da entrada
(D) quando o sinal de controle ou carga (C) ativado. No caso do flip-flop da Figura 9.17,
enquanto o valor da entrada de controle C for igual a 1, o valor da entrada D copiado (ou
armazenado) para o flip-flop. Se a entrada D variar enquanto C=1, o valor armazenado
tambm varia. Quando C=0, o flip-flop mantm seu valor, independente de variaes em D.
Com isto tem-se um flip-flop sensvel ao nvel, ou um latch.
Considerando o instante de ativao do sinal de controle, podem ser definidos quatro tipos
distintos:
Sensvel ao nvel 1 - o sinal de controle ativo enquanto apresentar nvel 1, e por
todo o tempo que permanecer neste nvel.
Sensvel ao nvel 0 - o sinal de controle ativo enquanto apresentar nvel 0, e por
todo o tempo que permanecer neste nvel.
Sensvel borda de subida - o sinal de controle ativo quando realizar uma
transio do nvel 0 para o nvel 1, e somente neste instante de tempo.
Sensvel borda de descida - o sinal de controle ativo quando realizar uma
transio do nvel 1 para o nvel 0, e somente neste instante de tempo.
9-12
Flip-flops sensveis borda so mais complexos que os sensveis ao nvel. A Figura 9.18
ilustra o caso de um flip-flop D sensvel borda de subida.
D
C
inativo
ativo
Tipo T
Qt+1
Qt
D
C
inativo
ativo
Tipo JK
Qt+1
Qt
Qt
J
X
0
0
1
1
K
X
0
1
0
1
C
inativo
ativo
ativo
ativo
ativo
Qt+1
Qt
Qt
1
0
Qt
9-13
Dn-2
Dn-1
Flip-flop
D
Flip-flop
D
D1
.......
Qn-1
.......
Qn-2
D0
Flip-flop
D
.......
Flip-flop
D
Q1
Q0
Flip-flop
D
.......
Flip-flop
D
Flip-flop
D
9-14
Para contadores til o uso de flip-flop sensveis borda, para que a contagem se realize em
um instante de tempo bem preciso. A Figura 9.21 ilustra um contador binrio de n bits
utilizando flip-flops tipo T. A contagem binria obtida conectando-se a sada de um bit na
entrada do flip-flop seguinte. Observe-se que, para facilitar o desenho, o bit menos
significativo est a esquerda e o mais significativo a direita.
Flip-flop
T
Flip-flop
T
Q0
.......
Q1
Flip-flop
T
.......
Flip-flop
T
Qn-2
Qn-1
B
0
1
0
1
S
0
1
1
0
C
0
0
0
1
9-15
A
S = ab
A
Meio
Somador
C = a.b
S = ABCi
Ci
Co = AB+Ci(AB)
A
B
Ci
Meio
Somador
Co
S
C
Meio
Somador
Um somador completo realiza a soma de um bit. Para somar n bits, necessrio agrupar n
somadores completos, onde o carry-out de cada um transportado para o carry-in do
somador imediatamente esquerda, conforme pode ser visto na Figura 9.25.
An-1
Bn-1
An-2
Bn-2
.......
A1
B1
A0
B0
Ci=0
Somador
completo
Somador
completo
Sn-1
Sn-2
.......
Somador
completo
Somador
completo
S1
S0
.......
Somador
Ci=0
not(A)
A+B
A and B
A or B
Sel
S
Figura 9.26 - ULA com 4 operaes
9-17
Se uma ULA realiza diversas funes, uma forma simples de realizar sua implementao
projetar individualmente cada uma destas funes, e depois simplesmente reuni-las atravs
de um multiplexador, que seleciona qual o valor a ser apresentado na sada. Por exemplo,
suponha-se que uma ULA deva realizar as operaes de ADD, AND, OR e NOT. A
implementao desta ULA com um multiplexador de 4-para-1 pode ser vista na Figura 9.26.
Todas as linhas, com exceo de Ci e Sel, so de n bits.
Assim como qualquer outro circuito, tambm para a ULA vale o compromisso entre
desempenho e custo. Embora a ULA da Figura 9.26 tenha baixo custo, pois s utiliza
elementos padres, no tem alto desempenho, pois no foi otimizada para isto.
9 . 7 Memria
Assim como um registrador de n bits pode ser visto como um array de n flip-flops, uma
memria de m posies pode ser vista como um array de m registradores. Logicamente, o
funcionamento de uma memria pode ser visto na figura 1.27. Observe-se, entretanto, que
este um modelo lgico, e no um modelo da estrutura fsica da memria. Na operao de
escrita as linhas de endereo selecionam, atravs de um circuito decodificador, em qual
registrador o dado deve ser escrito. A sada de decodificador, juntamente com o sinal de
Write, formam o sinal de carga nos registradores. Na operao de leitura as mesmas linhas
de endereo selecionam, atravs de um multiplexador, qual o registrador que ter o seu
contedo levado at a sada. A habilitao do dado na sada realizada pelo sinal Read.
A implementao dos circuitos de memria atuais diferente do modelo apresentado na
Figura 9.27. Este modelo muito simplificado, e visa somente explicar o funcionamento
geral da memria. Observe-se inclusive que os tempos necessrios para a realizao de uma
operao de escrita ou leitura no esto modelados na figura.
Endereo
Write
Dado de Entrada
8
carga
Leitura
Posio 0
8
8
carga
Posio 1
Dado de
Sada
2
8
carga
8
Posio 2
8
8
carga
Posio 3
8
Captulo
DEZ
Organizao do Neander
1 0 . 1 Elementos necessrios
Para definir uma organizao para o computador NEANDER, necessrio inicialmente
definir quais os elementos necessrios. Estes dados podem ser retirados das prprias
caractersticas do NEANDER:
Largura de dados e endereos de 8 bits
Dados representados em complemento de dois
1 acumulador de 8 bits (AC)
1 apontador de programa de 8 bits (PC)
1 registrador de estado com 2 cdigos de condio: negativo (N) e zero (Z)
Assim, os seguintes elementos so necessrios:
Um registrador de 8 bits para o acumulador
Um registrador de 8 bits para o PC (e possivelmente um registrador contador)
Dois flip-flops: um para o cdigo de condio N e outro para Z
Uma memria de 256 posies de 8 bits cada
1 0 . 2 Fluxo de dados
O conjunto de instrues do NEANDER fornece mais detalhes sobre o uso e as
interconexes necessrias entre estes elementos:
Cdigo
0000
0001
0010
0011
0100
0101
0110
1000
1001
1010
1111
Instruo
NOP
STA end
LDA end
ADD end
OR
end
AND end
NOT
JMP end
JN
end
JZ
end
HLT
Execuo
nenhuma operao
MEM(end) AC
AC MEM(end)
AC MEM(end) + AC
AC MEM(end) OR AC
AC MEM(end) AND AC
AC NOT AC
PC end
IF N=1 THEN PC end
IF Z=1 THEN PC end
trmino de execuo - (halt)
10-1
Instruo LDA
Busca:
Execuo:
Instruo ADD
Busca:
Execuo:
RI MEM(PC)
PC PC +1
Nenhuma operao necessria
RI MEM(PC)
PC PC +1
end MEM(PC)
PC PC +1
MEM(end) AC
RI MEM(PC)
PC PC +1
end MEM(PC)
PC PC +1
AC MEM(end); atualiza N e Z
RI MEM(PC)
PC PC +1
end MEM(PC)
PC PC +1
AC AC + MEM(end); atualiza N e Z
Instruo OR
Busca:
Execuo:
Instruo AND
Busca:
Execuo:
Instruo NOT
Busca:
Execuo:
Instruo JMP
Busca:
Execuo:
10-2
RI MEM(PC)
PC PC +1
end MEM(PC)
PC PC +1
AC AC or MEM(end); atualiza N e Z
RI MEM(PC)
PC PC +1
end MEM(PC)
PC PC +1
AC AC and MEM(end); atualiza N e Z
RI MEM(PC)
PC PC +1
AC NOT(AC); atualiza N e Z
RI MEM(PC)
PC PC +1
end MEM(PC)
PC end
RI MEM(PC)
PC PC +1
Parar o processamento
Uma transferncia do tipo x MEM(y) descreve uma leitura de memria. Esta operao
pode ser decomposta em trs fases:
1. REM y Transferncia do endereo y para o Reg. de Endereos da Memria
2. Read
Ativao de uma operao de Leitura da Memria
3. x RDM
Transferncia do Reg. de Dados da Memria para x
Por outro lado, uma transferncia do tipo MEM(y) x descreve uma escrita de memria.
Esta operao tambm pode ser decomposta em trs fases:
1. REM y Transferncia do endereo y para o Reg. de Endereos da Memria
2. RDM x
Transferncia do dado x para o Reg. de Dados da Memria
3. Write
Ativao da operao de Escrita na Memria
Alm disto, as seguintes observaes podem ser feitas:
1. Aps uma leitura de memria na posio do PC, o contedo deste registrador deve
ser incrementado, para apontar para a posio seguinte. Esta operao pode ser feita
a qualquer instante de tempo aps a transferncia do PC para o REM. E o
incremento pode ser feito em paralelo com outras operaes. Nas seqncias
descritas a seguir, este incremento feito sempre ao mesmo tempo que a operao
na memria (Read ou Write).
2. Um desvio condicional que no se realize no necessita ler o valor do endereo de
desvio. Assim, basta incrementar mais uma vez o valor do PC, para que este pule
sobre a posio de memria que contm este endereo e passe a apontar para a
instruo seguinte.
Com isto, obtm-se as seguintes seqncias:
Instruo NOP:
Busca:
REM PC
Read; PC PC + 1
RI RDM
10-3
Execuo:
Instruo STA
Busca:
Execuo:
Instruo LDA
Busca:
Execuo:
Instruo ADD
Busca:
Execuo:
Nenhuma operao
REM PC
Read; PC PC + 1
RI RDM
REM PC
Read; PC PC +1
REM RDM
RDM AC
Write
REM PC
Read; PC PC + 1
RI RDM
REM PC
Read; PC PC +1
REM RDM
Read
AC RDM; Atualiza N e Z
REM PC
Read; PC PC + 1
RI RDM
REM PC
Read; PC PC +1
REM RDM
Read
AC AC + RDM; Atualiza N e Z
Instruo OR
Busca:
Execuo:
Instruo AND
Busca:
Execuo:
Instruo NOT
Busca:
Execuo:
10-4
REM PC
Read; PC PC + 1
RI RDM
REM PC
Read; PC PC +1
REM RDM
Read
AC AC or RDM; Atualiza N e Z
REM PC
Read; PC PC + 1
RI RDM
REM PC
Read; PC PC +1
REM RDM
Read
AC AC and RDM; Atualiza N e Z
REM PC
Read; PC PC + 1
RI RDM
AC not(AC); Atualiza N e Z
Instruo JMP
Busca:
Execuo:
REM PC
Read; PC PC + 1
RI RDM
REM PC
Read
PC RDM
REM PC
Read; PC PC + 1
RI RDM
REM PC
Read
PC RDM
REM PC
Read; PC PC + 1
RI RDM
PC PC + 1
REM PC
Read; PC PC + 1
RI RDM
REM PC
Read
PC RDM
REM PC
Read; PC PC + 1
RI RDM
PC PC + 1
REM PC
Read; PC PC + 1
RI RDM
Parar o processamento
10-5
X+Y
X and Y
X or Y
not X
Y
Operaes da UAL
carga RDM
RDM
write
MEM
read
AC
carga AC
seleo UAL
UAL
carga NZ
N Z
DECOD.
Cd. Op.
P
C
Unidade de Controle
don't care
M
P
X
RI
carga RI
R
E
M
carga REM
s1
carga PC
Incrementa PC
5. O nico registrador que recebe dados de duas fontes possveis o REM. Para
solucionar este conflito utiliza-se um multiplexador que seleciona entre o PC (sel=0)
e o RDM (sel=1).
1 0 . 3 Sinais de controle
Todos os sinais de controle da Figura 10.1 so gerados nos instantes de tempo adequados
pela Unidade de Controle. A Tabela 10.2 mostra a equivalncia entre as transferncias
realizadas e os sinais de controle a serem ativados.
Transferncia
REM PC
PC PC + 1
RI RDM
REM RDM
RDM AC
AC RDM; Atualiza N e Z
AC AC + RDM; Atualiza N e Z
AC AC or RDM; Atualiza N e Z
AC AC and RDM; Atualiza N e Z
AC not(AC); Atualiza N e Z
PC RDM
Sinais de controle
sel=0, carga REM
incrementa PC
carga RI
sel =1, carga REM
carga RDM
UAL(Y), carga AC, carga NZ
UAL(ADD), carga AC, carga NZ
UAL(OR), carga AC, carga NZ
UAL(AND), carga AC, carga NZ
UAL(NOT), carga AC, carga NZ
carga PC
LDA
sel=0,
carga REM
Read,
incrementa
PC
carga RI
sel=0,
carga REM
ADD
sel=0,
carga REM
Read,
incrementa
PC
carga RI
sel=0,
carga REM
OR
sel=0,
carga REM
Read,
incrementa
PC
carga RI
sel=0,
carga REM
AND
sel=0,
carga REM
Read,
incrementa
PC
carga RI
sel=0,
carga REM
t4
Read,
incrementa
PC
sel=1,
carga REM
Read
UAL(Y),
carga AC,
carga NZ,
goto t0
Read,
incrementa
PC
sel=1,
carga REM
Read
UAL(ADD),
carga AC,
carga NZ,
goto t0
Read,
incrementa
PC
sel=1,
carga REM
Read
UAL(OR),
carga AC,
carga NZ,
goto t0
Read,
incrementa
PC
sel=1,
carga REM
Read
UAL(AND,
carga AC,
carga NZ,
goto t0
t5
t6
t7
Read,
incrementa
PC
sel=1,
carga REM
carga RDM
Write,
goto t0
NOT
sel=0,
carga REM
Read,
incrementa
PC
carga RI
UAL(NOT),
carga AC,
carga NZ,
goto t0
Tabela 10.3- Sinais de controle para STA, LDA, ADD, OR, AND e NOT
10-7
tempo JMP
t0
sel=0,
carga REM
t1
Read,
incrementa
PC
t2
carga RI
t3
sel=0,
carga REM
JN, N=1
sel=0,
carga REM
Read,
incrementa
PC
carga RI
sel=0,
carga REM
JN, N=0
sel=0,
carga REM
Read,
incrementa
PC
carga RI
incrementa
PC,
goto t0
JZ, Z=1
sel=0,
carga REM
Read,
incrementa
PC
carga RI
sel=0,
carga REM
t4
Read
Read
Read
t5
carga PC,
goto t0
carga PC,
goto t0
carga PC,
goto t0
JZ, Z=0
sel=0,
carga REM
Read,
incrementa
PC
carga RI
incrementa
PC,
goto t0
NOP
sel=0,
carga REM
Read,
incrementa
PC
carga RI
goto t0
HLT
sel=0,
carga REM
Read,
incrementa
PC
carga RI
Halt
t6
t7
Tabela 10.4- Sinais de controle para JMP, JN, JZ, NOP e HLT
Para o sequenciamento de todas as instrues so necessrios 8 tempos distintos, numerados
de t0 a t7. Os trs primeiros, t0, t1 e t2, servem para a fase de busca das instrues. Os
demais (t3 a t7) so necessrios para a fase de execuo. Observe-se que, quando termina a
execuo de uma instruo, existe um sinal de controle explcito para voltar ao tempo t0
(goto t0). Das Tabelas 10.3 e 10.4 podem ser derivadas as equaes booleanas para cada um
dos sinais de controle. Estas equaes so indicadas a seguir, em forma no necessariamente
otimizada:
carga REM = t0 + t3.(STA+LDA+ADD+OR+AND+JMP+JN.N+JZ.Z +
t5.(STA+LDA+ADD+OR+AND)
incrementa PC = t1 + t4.(STA+LDA+ADD+OR+AND) + t3.(JN.N + JZ.Z)
carga RI = t2
sel = t5.(STA+LDA+ADD+OR+AND)
carga RDM = t6.STA
Read = t1 + t4.(STA+LDA+ADD+OR+AND+JMP+JN.N+JZ.Z) +
t6.(LDA+ADD+OR+AND)
Write = t7.STA
UAL(Y) = t7.LDA
UAL(ADD) = t7.ADD
UAL(OR) = t7.OR
UAL(AND) = t7.AND
UAL(NOT) = t3.NOT
carga AC = t7.(LDA+ADD+OR+AND) + t3.NOT
carga NZ = t7.(LDA+ADD+OR+AND) + t3.NOT = carga AC
carga PC = t5.(JMP+JN.N+JZ.Z)
goto t0 = t7.(STA+LDA+ADD+OR+AND) + t3.(NOP+NOT+JN.N+JZ.Z) +
t5.(JMP+JN.N+JZ.Z)
10-8
Captulo
ONZE
Noes de Entrada e Sada
1 1 . 1 Introduo
Englobam-se sob a denominao de Entrada e Sada (E/S) todas as atividades de troca de
informaes do computador com o meio externo. Basicamente, o computador pode utilizar
atividades de entrada/sada com as seguintes finalidades:
troca de informaes com os usurios humanos do sistema, utilizando-se, para a
entrada de informaes ou para a exibio, dos chamados dispositivos perifricos.
Estes dispositivos podem ser teclados, vdeos, mouses, impressoras, leitoras de
cartes, etc.
permitir ao computador acessar dispositivos de armazenamento para grandes conjuntos
de dados, e que normalmente no podem ser mantidos todo o tempo em memria
primria. Estes dispositivos so englobados sob a denominao de memria
secundria e incluem, em geral discos e disquetes magnticos, CD-Rom, discos
magneto-ticos e fitas magnticas.
permitir ao computador comunicar-se com outros equipamentos, tais como outros
computadores e outros equipamentos cientficos e industriais, atravs de linhas
telefnicas e equipamentos especficos requeridos por este tipo de comunicao
(modens).
A arquitetura de E/S os elementos que um programa utiliza para transportar dados entre o
processador e os diversos dispositivos de E/S. Ela precisa especificar:
um mtodo para identificao do dispositivo a ser utilizado em uma operao de E/S;
o endereo do dado, ou seja, a fonte do dado a ser transportado para uma operao de
sada ou o destino do dado em uma operao de entrada;
a quantidade de dados a serem transportados;
os mtodos para determinar quando as operaes de E/S tiverem terminado ou
encontrarem dificuldades que impeam o seu trmino.
Estes parmetros no precisam ser necessariamente especificados a cada transferncia; alguns
deles podem ser convencionados de tal forma que estaro implcitos quando ocorrer o incio
da operao.
Uma caracterstica importante e fundamental da maioria dos dispositivos de E/S, sejam eles
orientados ao intercmbio de informaes diretamente com o usurio ou atuando no
armazenamento intermedirio de informaes, que eles operam em velocidades
consideravelmente mais lentas do que em processadores ou memrias (do tipo primrias).
Assim, referncias a dados ou interaes com seres humanos consomem enormes
quantidades de tempo em comparao a funes computacionais dentro de um par
processador-memria. Por esta razo, o projeto de E/S crucial para minimizar atrasos e o
projeto de funes de E/S normalmente sentido diretamente na arquitetura.
11-1
1 1 . 2 Dispositivos perifricos
A classe de dispositivos que so utilizados atualmente para realizao de operaes de
entrada e sada (isto , que atuam na troca de informaes tendo de um lado um computador
e do outro usurios humanos do sistema) bastante ampla e diversa, apresentando um leque
bastante variado de caractersticas e operao. Entre elas esto:
impressoras: para criar cpia em papel ou similar, de textos e figuras. As impressoras
variam em atributos, tendo com forma mais primitiva dispositivos que se
assemelham a mquinas de escrever. Atualmente, as mais modernas utilizam como
tecnologia a impresso a laser e podem imprimir at milhares de linha por minuto;
monitores (ou telas): que mostram textos e figuras, ambos podendo ser formatados de
diversas maneiras e utilizar vrias cores. O tipo mais comum, utiliza um tubo no
muito diferente de um tubo de televiso (tubo de raios catdicos). Atualmente,
utiliza-se tambm visores de cristal lquido, que consomem menor quantidade de
energia;
dispositivos grficos (ou plotters): que criam cpias impressas de grficos e curvas de
papel. Com o avano tecnolgico, as impressoras atualmente tem capacidade de
produzir material grfico de tima qualidade, tendo sua maior limitao no campo
(tamanho) de impresso. Os traadores, dependendo das suas caractersticas podem
produzir desenhos com mais de um metro de largura e comprimento limitado pela
bobina de papel;
dispositivos de explorao tica: que podem ler diretamente documentos. Dentre os
mais primitivos, pode-se citar as leitoras ticas de cartes ou folhas de marcas
(como as usadas no vestibular para registro das respostas). Atualmente, existem
dispositivos bem mais complexos como os scanners, que podem transferir para o
computador imagens obtidas em figuras, textos e fotografias;
dispositivos de apontamento: que podem indicar informaes ao computador atravs do
posicionamento de um cursor sobre a tela, como o caso do mouse e da caneta
luminosa (ou lightpen).
O mbito de dispositivos utilizados por computadores para comunicar-se com os usurios
encontra-se em expanso e melhorando em qualidade de interao. De forma a complementar
os dispositivos recm-mencionados, h grandes avanos no campo do reconhecimento de
voz e sada de voz. J h alguma disponibilidade nesta ltima opo.
1 1 . 3 Memria secundria
O grande volume de dados armazenados no computador inviabiliza a manuteno permanente
destas informaes integralmente na memria principal. Isto faz com que grande parte das
informaes, utilizadas menos freqentemente, seja guardada em dispositivos de uma classe
diferente dos empregados para a construo da memria principal (antes, memrias de
ncleos magnticos, atualmente circuitos semicondutores). Os dispositivos mais usados
anteriormente eram discos, tambores rotativos e fitas, todos magnticos; atualmente so os
discos e disquetes magnticos, fitas magnticas e os CD's.
Estes dispositivos so endereados utilizando-se conceitos de arquitetura e organizao de
E/S, embora no se enquadrem na primeira classe apresentada de dispositivos de E/S que
pressupem interao entre o computador e o usurio ou ser humano. Eles podem ser
considerados como arquivos eletrnicos que esto aptos a responder a uma solicitao de
dados.
1 1 . 4 Comunicao com outras mquinas
A troca de informaes com outras mquinas tambm consiste em uma atividade de entrada e
sada. Inicialmente, eram utilizadas para troca de informaes entre computadores ou entre
computador e algum perifrico especial localizados dentro de um prdio, em salas prximas.
11-2
11-3
uma instruo (INPUT) para transferir uma palavra de um dispositivo de E/S para a
UCP;
uma instruo (STORE) para transferir uma palavra da UCP para a memria principal.
Endereamento
Em sistemas com E/S programada, os dispositivos de E/S, a memria principal e a UCP se
comunicam atravs de um barramento de uso comum, partilhado entre eles. As linhas de
endereamento deste barramento, usadas para para selecionar posies de memria, tambm
podem ser utilizadas para selecionar dispositivos de E/S. Cada ligao entre o barramento
principal e o dispositivo de E/S chamada de porta de E/S, sendo atribuda a ela um
endereo exclusivo. A porta de E/S pode incluir um registrador de dados.
Em algumas mquinas, parte do espao de endereamento da memria principal usado para
portas de E/S (E/S mapeada em memria). Neste caso, no h necessidade de dispor-se de
instrues especiais de entrada e sada, mas estes aspectos sero tratados mais tarde, em
outras disciplinas.
Instrues de E/S
O esquema de E/S programada pode ser implementado com poucas instrues. O
microprocessador Intel 8080, por exemplo, que usa o sistema de endereamento explicado
no pargrafo anterior, emprega apenas duas instrues de E/S:
IN x, que transfere uma palavra da porta de E/S x para o acumulador do 8080;
OUT x, que transfere uma palavra do acumulador do 8080 para a porta de E/S x.
A UCP no atribui qualquer interpretao s palavras transferidas: o programador deve fazlo. Algumas palavras podem indicar o estado do dispositivo de E/S e outras podem ser
instrues especiais para este dispositivo.
O simples envio de dados, sem que o dispositivo esteja pronto para receb-los, pode resultar
na perda de informaes. Por outro lado, a espera de informaes sem que haja tempos prdeterminados, pode resultar em tempos de execuo excessivamente longos. Assim, o ideal
que se tenha possibilidade de testar as condies de recebimento / envio de informaes pelo
dispositivo de E/S, ou seja, avaliar o estado do dispositivo. Normalmente este estado pode
ser especificado por um bit de informao que o dispositivo mantm disponvel de forma
contnua (independente das linhas de dados). Assim, sero necessrios os seguintes passos:
Passo 1: l a informao de estado;
Passo 2: testa o estado para determinar se o dispositivo est pronto para iniciar a
transferncia de dados;
Passo 3: se no est pronto, retorna ao passo 1; se est pronto, efetua a transferncia
do dado.
A seguir, tem-se como exemplo um programa escrito para o INTEL 8080, que executa a
transferncia de uma palavra de dados de um dispositivo de E/S para o acumulador na UCP.
Por hiptese, o dispositivo est ligado s portas 1 e 2. O estado do dispositivo est
disponvel continuamente na porta 1, enquanto que os dados solicitados esto disponveis na
porta 2 quando a palavra de estado tem o valor READY.
Instruo
Comentrio
WAIT:
IN 1
L estado do dispositivo de E/s para o acumulador
CMP READY Compara a palavra READY (de forma imediata, com o
acumulador; de for igual, liga Z=1, seno, Z=0
JNZ WAIT
Se Z1 (disp. de E/S no est pronto), volta para WAIT
IN 2
L palavra de dados para o acumulador
Figura 11.1 - Trecho de programa de E/S
11-4
11-5
Captulo
DOZE
Software Bsico
1 2 . 1 Introduo
Emprega-se comumente a palavra software para designar o conjunto de programas que so
utilizados com um sistema de hardware para facilitar seu uso por programadores e
operadores do sistema. Entretanto, esta utilizao do termo exclui programas de aplicaes,
incluindo apenas programas que fornecem funes gerais independentes dos detalhes de uma
aplicao (software do sistema ou software bsico). Na prtica, o que o usurio enxerga
facilmente deste grupo (embora ele seja mais extenso) so as linguagens que ele encontra
disponveis para programao, como Basic, Fortran, Cobol, Pascal, Logo, C, Delphi,
Visual C, C++, Java, etc, e programas escritos para resolver problemas especficos ou que
realizam funes especiais como planilhas de clculo, editores de texto, jogos eletrnicos,
entre outros, que fazem parte do software de aplicao.
Os programas que so escritos em linguagens de programao de alto nvel (emprega-se esta
denominao como distino a linguagens mais prximas da mquina) precisam ser
convertidos em programas de mquina. O processo desta converso executado por um
elemento de software denominado de processador de linguagem. Os programas escritos
em alto nvel tendem a ser independentes da estrutura da mquina na qual sero executados,
mas os programas de baixo nvel no. Por isso, esta converso dependente da mquina
sobre a qual vai ser executado o programa.
Os processadores de linguagem so programas longos, que ocupam espao significativo na
memria do computador. Por isso, freqentemente ficam armazenados (residem) em um
dispositivo de entrada/sada, como um disco, por exemplo. Este programa ser chamado e
copiado para a memria quando o programador quiser fazer uso dele. O uso de um
processador de linguagem significa que o programador vai execut-lo, tendo como entrada
de dados o programa escrito em linguagem de alto nvel. Como sada, ser obtida uma
representao do programa em forma diretamente executvel pela mquina ou uma forma
mais prxima desta do que a representao anterior (em alto nvel).
A escrita de um programa consiste na especificao, direta ou indireta, de uma seqncia de
instrues de mquina para o computador. As instrues de mquina formam um padro
binrio com o qual difcil de trabalhar do ponto de vista humano e complexo para entender.
mais fcil de escrever programas empregando smbolos mais familiares, orientados ao
usurio, tais como os caracteres alfa-numricos e suas combinaes. Como conseqncia
desta facilidade, torna-se necessrio traduzir esta representao simblica de programas em
elementos binrios que possam ser reconhecidos pelo hardware.
1 2 . 2 Linguagens de programao
Um programa uma lista de instrues ou comandos que determina ao computador a
execuo de uma tarefa de processamento de dados. H diversas linguagens de
programao, atravs das quais pode-se escrever programas para o computador; mas o
computador s pode execut-los quando eles esto representados internamente na forma
binria, organizado e codificado de forma a resultar na gerao de sinais de controle da UCP.
12-1
Portanto, os programas que no esto escritos na forma binria necessitam ser traduzidos
antes da sua execuo. Os programas podem se incluir em uma das seguintes categorias:
cdigo binrio: sequncia de instrues e operandos em binrio; lista a
representao exata das instrues como elas aparecem na memria;
cdigo octal ou hexadecimal: representao, equivalente ao cdigo binrio, em
representao octal ou hexadecimal;
cdigo simblico: o usurio emprega smbolos tais como letras, nmeros e
caracteres especiais, para representar o cdigo das instrues, composto por parte de
operao, endereo e outras. Cada instruo simblica pode ser traduzida em uma
instruo binria equivalente, o que feito por um programa montador (assembler).
Por esta razo, este programa simblico referido como programa em linguagem
de montagem ou assembler.
linguagens de programao em alto nvel: so linguagens especiais
desenvolvidas para facilitar a especificao de procedimentos usados na soluo de
problemas, no havendo preocupao com o comportamento do hardware que suporta
estas operaes. Portanto, elas empregam smbolos e formatos orientados a
problemas, de acordo com o raciocnio comumente empregado na soluo destes.
Assim, cada comando precisa ser traduzido em uma seqncia de instrues binrias,
antes que o programa possa ser executado em um computador. O programa que traduz
um programa escrito em linguagem de alto-nvel para binrio chamado de
compilador.
O termo linguagens de programao refere-se em geral ao estudo da estrutura das diversas
linguagens de programao de alto nvel, sendo realizado de forma independente dos
dispositivos computacionais de do seu hardware. Este no o enfoque para o pessoal de
arquitetura, que o utiliza com outra conotao incluindo linguagens a nvel de mquina.
A seguir ser exemplificada esta relao existente entre as diversas linguagens de
programao. Esta relao no estabelecida diretamente a nvel de comandos, mas tenta
deixar claro o nvel crescente de dificuldades de programao e depurao de cdigo,
medida que de vai do alto para o baixo nvel de programao.
1 2 . 3 Exemplo com NEANDER
Problema: Realizar a multiplicao de dois nmeros inteiros positivos, a e b (a0, b0),
utilizando o mtodo das somas sucessivas, ou seja, somar a consigo mesmo b vezes.
Descrio em portugus estruturado:
Sejam a,b,r trs nmeros inteiros positivos.
Ento fazer:
1. Zerar r
2. Enquanto b for maior que zero, somar a em r e decrementar b de uma unidade
3. Fim. O resultado est em r
Descrio em pseudo-linguagem de alto nvel
Begin Program
Variable a,b,r: type positive-integer
r:=0
while b>0
do r:=r+a
b:=b-1
12-2
end while
End Program
Descrio em pseudo-linguagem, sem uso de while
Begin Program
Variable a,b,r: type positive-integer
Label lao
r:=0
lao:
if b>0
then r:=r+a
b:=b-1
goto lao
end if
End Program
Descrio em pseudo-linguagem, somente com uso de if-goto
Begin Program
Variable a,b,r: type positive-integer
Label lao, fim
r:=0
lao:
if b=0 goto fim
r:=r+a
b:=b-1
goto lao
fim:
End Program
Descrio em pseudo-assembler
fim:
ORG 0
LDA Zero
STA r
LDA b
JZ fim
LDA r
ADD a
STA r
LDA b
ADD m1
STA b
JMP lao
HLT
a
b
r
zero
m1
DEF BYTE
DEF BYTE
DEF BYTE
DEF BYTE=0
DEF BYTE=-1
lao:
Instruo
LDA 26
STA 25
LDA 24
% r:=0
% if b=0 goto fim
12-3
6
8
10
12
14
16
18
20
22
23
24
25
26
27
JN 22
LDA 25
ADD 23
STA 25
LDA 24
ADD 27
STA 24
JMP 4
HLT
0
0
0
0
255
% r:=r+a
% b:=b-1
% goto lao
% define varivel a
% define varivel b
% define varivel r
% define varivel zero e inicializa com 0
% define varivel m1 e inicializa com menos um
Instruo
32 26
16 25
32 24
160 22
32 25
48 23
16 25
32 24
48 27
16 24
128 4
240
0
0
0
0
255
% r:=0
% if b=0 goto fim
% r:=r+a
% b:=b-1
% goto lao
% define varivel a
% define varivel b
% define varivel r
% define varivel zero e inicializa com 0
% define varivel m1 e inicializa com menos um
12-4
Assemblers
Nos primrdios da computao, o programador de computadores tinha a sua disposio uma
mquina que, atravs do hardware, executava certas funes bsicas. A programao do
computador consistia em escrever uma srie de uns e zeros (linguagem de mquina),
colocar esta srie na memria, pressionar um boto. Com isto o computador iniciava a
execuo destas instrues.
extremamente difcil, entretanto, escrever e ler programas em linguagem de mquina. Na
procura por um mtodo mais conveniente, desenvolveram-se os processadores de
linguagem, ou seja, programas que traduzem um programa fonte escrito pelo usurio
em um programa objeto que pode ser entendido pelo computador. Um montador ou
assembler um programa do sistema que traduz um programa escrito em linguagem
assembler para um programa equivalente descrito em linguagem binria (da mquina).
Tipicamente, em uma linguagem assembler utilizam-se mnemnicos (smbolos) para cada
instruo de mquina, e a principal funo do montador traduzir cada um destes smbolos
no cdigo binrio equivalente.
Compiladores
Com o aumento da complexidade dos programas, mesmo o uso de linguagem assembler no
fornece o grau de abstrao necessrio para uma boa compreenso do programa. Assim,
desenvolveram-se as linguagens de alto nvel, onde um nico comando substitui dezenas de
instrues assembler. Um compilador um programa do sistema que traduz um programa
em linguagem de alto-nvel para a linguagem de mquina. Uma linguagem de alto nvel
suficientemente abstrata para ser independente do hardware (ou quase independente diversas caractersticas da arquitetura, como por exemplo a representao dos nmeros, so
refletidos nas linguagens). Para poder utilizar uma linguagem de alto nvel, o programador
deve conhecer sua sintaxe (forma) e sua semntica (significado).
As linguagens de alto nvel esto em constante evoluo, refletindo as mudanas que
ocorrem nas metodologias de programao. Dentre as primeiras linguagens destacam-se
FORTRAN, COBOL, ALGOL e PL/I. Entre as linguagens mais utilizadas atualmente podem
ser citadas C e PASCAL. Dois outros processadores de linguagens largamente usados so os
montadores de macros (ou macro-assemblers) e os interpretadores.
Macros
Uma macro uma pseudo-instruo que define um grupo de instrues de mquina. Uma
pseudo-instruo uma instruo que existe para definir condies especiais para o
montador; no resulta em cdigo propriamente dito, mas provoca transformaes no cdigo
original. Um montador de macros traduz programas escritos em linguagem assembler
com facilidades de macros, o que significa usar nomes simblicos para representar
seqncias de instrues. Cada vez que o programa encontra esta macro, substitui-a pela
seqncias de instrues.
Assim, por exemplo, poderia ser definida uma macro para o NEANDER que realizasse
subtraes. Tal macro (convenientemente denominada SUB), conteria as instrues
necessrias para realizar uma subtrao (inverso do subtraendo, soma de uma unidade e
soma com o minuendo), como ilustrado na definio da macro a seguir:
MACRO SUB end
STA aux
LDA end
NOT
ADD um
ADD aux
END MACRO
12-5
Todas as ocorrncias posteriores do smbolo SUB seriam substitudas pela sequncia acima,
uma vez para cada smbolo. As macros no devem ser confundidas com as subrotinas.
Subrotinas so conjuntos de instrues que podem ser utilizadas diversas vezes por um
programa; assim, aes repetitivas no precisam ser escritas repetidamente e nem geram
trechos repetidos de cdigo em um programa. Cada vez que uma rotina utilizada,
executado um desvio do programa principal ( o que chama a subrotina) para o endereo
inicial onde ela se encontra carregada; aps sua execuo, executado um novo desvio que
causa o retorno para o programa principal. Uma subrotina para subtrao seria por exemplo
o seguinte trecho de programa, armazenado a partir do endereo xx :
xx
STA aux
LDA end
NOT
ADD um
ADD aux
RET
A chamada desta funo seria feita atravs de uma instruo de chamada para subrotina
(CALL xx) ou de desvio para subrotina (JSR xx). Note-se que na chamada deve ser
fornecido o endereo de memria onde a subrotina foi armazenada. Tanto a instruo de
chamada (CALL ou JSR) como a instruo de retorno (RET) devem existir na arquitetura do
computador. O NEANDER, por exemplo, no possui estas facilidades.
Interpretadores
Um interpretador tambm um processador de linguagem que traduz cada comando de
um programa escrito em linguagem de alto nvel, executando-o imediatamente. Assim, o
interpretador trabalha alternando aes de traduo e execuo. O compilador atua
exclusivamente na traduo do programa fonte e no na execuo, o que os diferencia.
Assim o interpretador responde mais rapidamente a modificaes no programa fonte, o que
bastante til em um ambiente de desenvolvimento. Na execuo rotineira de programas ele se
torna mais lento, uma vez que refaz a traduo de cada comando a cada nova execuo. O
exemplo mais conhecido de interpretador o utilizado na linguagem BASIC.
Bibliotecas
Bibliotecas de programas existem para simplificar tarefas repetitivas de programao.
Assim, rotinas muito utilizadas so padronizadas, catalogadas e tornadas acessveis aos
usurios. Isto implica no estabelecimento de convenes. Nas aplicaes cientficas,
encontra-se neste campo a programao de funes matemticas tais como raiz quadrada,
funes exponenciais, inverso de matrizes, etc Para processamento de dados comercial,
encontram-se funes de organizao de arquivos como ordenao e busca ou procura.
Muitas outras esto disponveis ou podem ser programadas de acordo com o interesse dos
usurios.
Carregadores
Carregadores so programas do sistema que inserem ou posicionam outros programas na
memria e preparam-nos para a execuo. Podem ser do tipo absoluto, que carregam o
programa a partir de um endereo especificado pelo usurio, ou do tipo relocvel, que no
permitem a interveno do usurio, posicionando o programa de forma eficiente, de acordo
com as disponibilidades de espao na memria.
Em um esquema simples, o montador assembler armazena sua sada em uma memria
secundria (disco, por exemplo). A funo do carregador seria simplesmente transferir o
cdigo desta memria secundria para a memria principal e transferir o controle para ele
(colocar no PC para o endereo da primeira instruo do programa).
12-6
12-8
100
9100
/*
//STEP2
/*
//STEP3
/*
JOB
DONOVAN,
FORTRAN, NOPUNCH
READ 9100,N
DO 100 I = 1,N
I2 = I * I
I3 = I * I * I
PRINT 9100, I, I2, I3
FORMAT (3I10)
END
T168,1,100,0
EXEC LOAD
EXEC OBJECT
10
O primeiro carto define um processo que o usurio de nome Donovan deseja realizar; o
segundo carto indica que os cartes seguintes devem ser processados pelo compilador
FORTRAN (at o carto de fim de arquivo, marcado com /*). O passo seguinte a chamada
do carregador, sem nenhum outro carto especial. O ltimo passo comanda a execuo do
programa objeto recm gerado, e fornece os dados a serem lidos (no caso o nmero 10).
Todos os cartes so interpretados pelo sistema operacional, que inclui todos os programas
do sistema mencionados anteriormente, alm de outros que supervisionam e controlam as
operaes de todos os programas no computador.
O sistema operacional realiza as seguintes funes:
aloca espao de memria e carrega programas para a execuo;
12-9
12-10
Ento o processador designado para o job de mais alta prioridade. Nos dois primeiros
casos, o job deve ser removido da memria. Nos dois ltimos, o job suspenso
temporariamente.
O sistema operacional contribui para o usos mais eficiente dos recursos de hardware pelo
gerenciamento dos recursos de memria. Por exemplo, se um programa no pode ser
acomodado inteiramente na memria devido ao seu tamanho, o sistema operacional pode
dividi-lo em partes denominadas de pginas ou segmentos, transferindo-os gradualmente
da memria secundria para a principal.
O efeito do sistema operacional na gerenciamento do sistema computacional visa melhorar
sua eficincia, a qual avaliada pelo throughput. Throughput a quantidade de
processamento que o sistema realiza com sucesso durante um intervalo de tempo
especificado. Pode servir como medida de avaliao tanto para hardware como para o
software. A contribuio do sistema operacional neste sentido resultante da eficincia das
facilidades existentes no seu cdigo.
1 2 . 7 Funes bsicas dos sistemas operacionais
Um sistema operacional um conjunto de programas que permite ao computador controlar
os recursos, executar programas e gerenciar dados. Inclui todos os programas do sistema
mencionados anteriormente, alm de outros que supervisionam e controlam as operaes de
todos os programas no computador. Do ponto de vista do usurio, a funo do sistema
operacional auxili-lo na mecnica de resoluo de problemas.
O sistema operacional tem trs encargos principais: gerenciar a execuo de programas e
aes realizadas na memria, gerenciar o armazenamento de arquivos e gerenciar as
atividades de E/S. Para tanto, ele detm trs funes bsicas, que so:
controlar os recursos do sistema de computao;
executar os programas do computador;
gerenciar dados.
Estas funes so executadas sem que o programador precise estar instruindo o sistema
operacional a faz-lo, a cada momento. Na verdade, o sistema operacional j existe como
uma srie de programas que fazem parte da mquina e que permitem uma operao
razoavelmente confortvel para o programador de aplicaes. Os programas de controle
minimizam a interveno do operador de tal forma que as operaes do computador fluem de
forma suave e contnua. O programa mais importante no sistema o supervisor, cuja maior
parte reside na memria (est sempre l). Ele controla o sistema operacional inteiro e chama
outros programas do sistema operacional (do disco), quando necessrio, para que eles
permaneam na memria enquanto forem executados. Aps, eles retornam para o disco, para
que se tenha uso eficiente do espao de memria.
O sistema operacional aumenta a eficincia de duas maneiras:
ele atua como promotor da cooperao entre os usurios do sistema, ajudando-os a
fazerem o melhor uso possvel dos recursos computacionais de forma que todos tirem
proveito.
ele chama tradutores e outros programas para que se encarreguem de tarefas comuns
(usuais). Isto libera os programadores de aplicaes de tarefas rotineiras e repetitivas.
A fim de cumprir as funes acima listadas, o sistema operacional executa atividades tais
como:
operaes de seqenciamento e escalonamento de jobs (alocao de espao de
memria e carga de programas para a execuo), e controle de trfego: o sistema recebe
12-11
12-12
processos, tais como: primeiro a chegar, primeiro a ser servido, ou processos com mnimo
tempo de execuo.
Com preempo, um processo pode ser interrompido em execuo para transferir controle de
um recurso para outro processo ou atender s necessidades do sistema. Este tipo de
escalonamento muito empregado em sistemas de multiprogramao onde existe
compartilhamento de espao e tempo por todos os processos. Em sistemas de
multiprogramao, os modelos para determinar a poltica de escalonamento podem ser
bastante complexos. A interrupo, bastante usada em sistemas multiprogramveis, tem a
funo de preempo de um processo momentaneamente em posse de um recurso de um
recurso, tal como UCP, dispositivos, etc.
1 2 . 9 Carga do sistema (inicializao da mquina)
Denomina-se de carga do sistema, operao que tem por objetivo colocar o computador em
condies de funcionamento. Consiste, fundamentalmente, em carreg-lo com rotinas
essenciais ao atendimento dos diversos programas de aplicao que lhe sero posteriormente
submetidos. Esta operao comumente denominada de bootstrap, referindo-se
informalmente ao procedimento como dar o boot na mquina.
Esta operao envolve: a colocao das primeiras instrues na memria a partir de um
comando especfico: nas mquinas modernas, este comando j vem embutido na inicializao
da mquina; nas antigas, era disparado por uma tecla ou boto especial, ou estas instrues
eram carregadas manualmente na memria da mquina. Este programa dispara a leitura (de
um disquete, do disco, de uma memria de armazenamento permanente, por exemplo) de um
programa carregador que ento posicionado na memria; a partir deste, novos programas
ou rotinas so sucessivamente carregados ou posicionados na memria, para executar as
aes subseqentes. Esta carga completa denominada de boot inicial do sistema. O
computador no tem a capacidade de reter a informao que est na memria principal
quando cortada a energia eltrica: assim, esta operao repetida a cada nova ligao da
mquina.
1 2. 10 Multiprogramao
Assim, como visto na unidade anterior, a multiprogramao se refere existncia de mais
do que um programa em diferentes partes da memria principal ao mesmo tempo. Seu
principal objetivo a eficincia computacional. Uma tcnica relacionada a multi-tarefas, ou
a existncia de diversas tarefas que so parte do mesmo job e podem ser executadas
simultaneamente.
Em sistemas multiprogramados, dois ou mais programas so carregados em diferentes
reas da memria, na expectativa de que eles vo gerar uma quantidade significativa de
trabalho para o computador. Se este trabalho gerado exceder a capacidade do computador, o
resultado que a mquina (em princpio) no dever ficar parada, esperando novas tarefas.
Assim, o programa supervisor executa o trabalho de alocao das diferentes unidades pela
manuteno de listas de passos que esto prontos para execuo em cada uma das unidades.
Quando uma unidade completa um passo, o supervisor pode consultar a sua lista para um
novo trabalho. No caso das unidades de entrada/sada, a concluso de uma passo indicado
por uma interrupo, que sinaliza UCP para parar temporariamente o programa atual e para
alocar mais trabalho unidade de E/S, se houver. No caso da CPU, a concluso indicada
quando o programa na UCP ou chega ao final do job ou requisita buffers de E/S que ainda
no esto disponveis isto se uma entrada foi requisitada, e o sistema ainda no
preencheu o buffer, ou se uma sada foi requisitada, o sistema ainda no esvaziou os buffers
anteriores de tal forma que haja lugar para os novos.
Neste gerenciamento de execuo de jobs, h problemas envolvidos tais como:
12-13
Processo selecionado
Pronto
Executando
Processo interrompido
(fim da fatia de tempo)
Bloqueado
12-14
12-16
Do ponto de vista do sistema operacional, tem-se um recurso a mais a ser gerenciado: a rede.
Servios que no esto disponveis no computador local podem estar acessveis via rede e,
para utiliz-los de forma adequada, o sistema operacional deve ter conhecimento deles. Temse assim os sistemas operacionais distribudos, onde os recursos a serem gerenciados
no esto concentrados em um nico computador, mas sim espalhados ao longo da rede.
O processador deixa de ser uma entidade nica no sistema. Alm do tradicional aspecto do
escalonamento de processos (qual processo ser executado pelo processador), surge a
questo do escalonamento de processadores (qual dos processadores disponveis ir executar
determinado processo).Uma outra consequncia da multiplicidade de processadores a
possibilidade de continuidade do processamento aps a ocorrncia de falhas em um
determinado processador. Como provavelmente ainda haver rplicas desse recurso na rede,
os processos afetados pela falha podem continuar aps migrarem para um processador no
falho.
Tais vantagens, entretanto, so pouco exploradas atualmente. Esse fato decorre da pouca
utilizao de sistemas operacionais distribudos nesse tipo de ambiente. mais frequente o
emprego de sistemas operacionais centralizados tradicionais, que no foram projetados
especificamente para ambientes distribudos, com extenses para suportar algumas operaes
remotas bsicas (como transferncia de arquivos e execuo remota de processos, por
exemplo).
Por um sistema distribudo se entende atualmente um sistema que consiste de mltiplos
processadores que no compartilham memria primria e se comunicam por mensagens
atravs de uma rede de comunicao. Programas distribudos podem contar com quatro tipos
de processos: clientes, servidores, filtros e pares. Clientes e servidores interagem usualmente
de forma sncrona: um cliente envia uma mensagem de requisio de servio a um servidor
local ou remoto; o servio executado pelo servidor, que retorna os resultados ao cliente
(que espera bloqueado). Um servidor pode ser projetado para atender mltiplas requisies
concorrentemente. Processos filtro recebem, processam e enviam adiante os dados obtidos.
Processos pares interagem com mensagens para cooperar no atendimento a requisies.
Nos dias de hoje os ambientes computacionais da maioria das organizaes apresentam um
realidade heterognea. Esta heterogeneidade, que pode ser definida com a diversidade
existente em sistemas de computao, manifesta-se especialmente sob os seguintes aspectos:
arquitetura da mquina: processadores, memria e dispositivos de E/S. As arquiteturas
atuais diferem em uma srie de aspectos, dos quais o principal a famlia do elemento
processador utilizado no equipamento. Por famlia entenda-se um conjunto de
elementos processadores com certo grau de compatibilidade entre si. Exemplos so os
microprocessadores Intel 80x86 e os Motorola 680x0. Uma parcela das estaes de
trabalho existentes atualmente utiliza processadores RISC (Reduced Instruction Set
Computer), embora as linhas de processadores de cada fabricante sejam incompatveis
entre si. H ainda outros tipos de processadores, tal como os Transputers, utilizados
em mquinas paralelas.
sistemas operacionais: chamadas do sistema, interface com o usurio (interpretador de
comandos e ambientes de janelas) e mecanismos de comunicao entre processos;
redes de comunicao: protocolos de comunicao e interfaces de rede;
linguagens de programao e compiladores: diferenas entre implementaes de uma
mesma linguagem e uso de diferentes linguagens.
Um sistema operacional de rede pode ser definido como a soma das camadas de software
escritas em cada mquina (host, ou hospedeiro) para propiciar comunicao e
compartilhamento de recursos entre a mquina local e diferentes mquinas remotas. Tanto o
computador local como os equipamentos remotos que compe a rede so entidades
autnomas.
12-17
Bibliografia
Hayes, John
Tokyo,1978.
Hamacher, V.C.; Vranesic, Z.G.; Zaky, S.G. Computer Organization. MacGrawHill, Tokyo, 1978.
Flores, Ivan. Computer Logic: the functional design of digital computers. PrenticeHall, New Jersey, 1960. Captulos 6 (Machine arithmetic), 7 (Number systems and
counting) e 8 (Machine Languages).
P.
Computer
architecture
and
and
programming.
McGraw-Hill
organization.MacGraw-Hill,
Maley, Gerald A.; Earle, John. The logic design of transistor digital computers.
Prentice-Hall, New Jersey, 1963. Captulos 2 (Number systems and codes) e 7
(Arithmetic operations).
Coonen, Jerome T. An implementation guide to a proposed standard for floatingpoint arithmetic. Computer, vol.13, n1, january 1980, pp.68-79.
Weber, Raul Fernando. Processador Pipeline com arquitetura bit-slice. PsGraduao em Cincia da Computao, UFRGS, janeiro 1980. Dissertao de
mestrado. (Algoritmos de aritmtica binria).