Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Organizacja i Architektura
Komputerów
Elementy i bloki cyfrowe
1
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Bloki kombinacyjne
Przykłady: elementy 32-bitowego procesora
Select
CarryIn
A
A
32
32
Y
Suma
32
32
B
B Carry
32
32
OP
sumator multiplekser
A
32
Wynik
32
B
32
ALU
2
MUX
Sum.
ALU
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Bramki logiczne
Dowolny blok kombinacyjny można zbudować z bramek
Symbol prostokÄ…tny
Symbol tradycyjny
ANSI/IEEE
IEC
&
" iloczyn logiczny AND
" zanegowany iloczyn logiczny NAND
" suma logiczna OR
" zanegowana suma logiczna NOR
" negator (inwerter) NOT
" suma modulo 2 (exclusive OR) XOR
3
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Dekoder binarny
n wejść, 2n wyjść
tylko jedno wyjście jest w stanie  1 dla danej kombinacji
stanów na wejściu (funkcja  1 z n )
n
dekoder
2n wyjść
wejść
binarny
4
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Dekoder binarny  implementacja
Prosty dekoder 2-bitowy:
Y0
&
X1
&
Y1
X0
&
Y2
&
Y3
Enable (zezwolenie)
5
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
2 + 2 = 3 ?
Y0
X0
Y1
dekoder
2-bitowy
Y2
X1
Y3
NOT
X2
Y4
Y5
dekoder
2-bitowy
Y6
Y7
Dwa dekodery 2-bitowe tworzÄ… dekoder 3-bitowy
6
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Koder kodu  1 z n na kod NKB
X0 NC
X1
e"
Y0
X2
e"
X3
Y1
X4
e"
...
Y2
X7
suma logiczna
e"
7
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Multiplekser
Działa jak przełącznik; nazywany
multiplekserem lub w skrócie MUX
s1 s2
Tablica prawdy
a
b
multiplekser
y
s2 s1 y
(MUX)
_______
c
0 0 a
d
0 1 b
1 0 c
s
1 1 d
symbol
a
alternatywny
y
b
(dla dwubitowego MUX)
8
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Multiplekser  implementacja
s1 s2
dekoder
e"
&
a
&
b
y
&
c
&
d
9
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Multiplekser grupowy
S
s0
s1
A
B
MUX
Y
a0
C
b0
MUX
y0
c0
D
d0
S
2
4
A
4
B
a3
4
MUX
4 Y
b3
MUX
y3
C
c3
4
d3
D
10
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Język VHDL  przykład
entity MUX32X2 is
" VHDL  Very (High
generic (output_delay : TIME := 4 ns);
Speed Integrated
port(A,B: in vlbit_1d(31 downto 0);
Circuit) Hardware
DOUT: out vlbit_1d(31 downto 0);
SEL: in vlbit); Description Language
end MUX32X2;
" Opracowany w latach
architecture behavior of MUX32X2 is
80-tych przez
begin
mux32x2_process: process(A, B, SEL) Departament Obrony
begin
USA
if (vlb2int(SEL) = 0) then
DOUT <= A after output_delay;
" Norma IEEE Standard
else
DOUT <= B after output_delay; 1076 (1987, 1993,
end if;
2001)
end process;
end behavior;
11
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Półsumator  HA (half adder)
Sum = (a " b) + (a " b ) = (a + b ) " (a + b)
Carry = a " b
a b Sum Carry
a Sum
HA
b cout
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
a
cout
&
b
&
Sum
e"
12
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Sumator: HA + HA = A (adder)
a b cin Sum cout
a
Sum
b
0 0 0 0 0
sumator
cin
0 0 1 1 0
cout
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
a
pół-
sumator
b
cout
e"
pół-
Sum
sumator
cin
13
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Sumator wielobitowy, szeregowy
a7 b7 a7 b6 a1 b1 a0 b0
. . . .
cout c7 c2 c1 c0
c6
" " " "
. . . .
sum7 sum6 sum1 sum0
" Szeregowa propagacja przeniesień (ripple-carry)
" Wada: długi czas ustalania wyniku; sygnał przeniesienia
propaguje przez wszystkie stopnie sumatora
14
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Sumator równoległy (4-bitowy)
Określamy funkcję gi generującą przeniesienie i funkcję pi
określającą propagację przeniesienia
gi = aibi
pi = ai •" bi
Kolejne przeniesienia można teraz zapisać w postaci:
ci+1 = gi + pici
ci+2 = gi+1 + pi+1ci+1
ci+3 = gi+2 + pi+2ci+2
ci+4 = gi+3 + pi+3ci+3
15
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Sumator równoległy cd.
a następnie, po dokonaniu podstawień, w postaci:
ci+1 = gi + pici
ci+2 = gi+1 + pi+1gi + pi+1 pici
ci+3 = gi+2 + pi+2 gi+1 + pi+2 pi+1gi + pi+2 pi+1 pici
ci+4 = gi+3 + pi+3gi+2 + pi+3 pi+2 gi+1 + pi+3 pi+2 pi+1gi + pi+3 pi+2 pi+1 pici
wprowadzajÄ…c oznaczenia:
g(i,i+3) = gi+3 + pi+3gi+2 + pi+3 pi+2 gi+1 + pi+3 pi+2 pi+1gi
p(i,i+3) = pi+3 pi+2 pi+1 pi
otrzymujemy ostatecznie:
ci+4 = g(i,i+3) + p(i,i+3)ci
16
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Sumator równoległy cd.
Równanie z poprzedniego slajdu określają metodę
nazywaną CLA  carry-look-ahead, w której przeniesienia
sÄ… generowane przez blok CLA:
gi+3 pi+3 gi+2 pi+2 gi+1 pi+1 gi pi
ci+4
ci
CLA
11 bramek AND + 5 bramek OR
g(i,i+3) p(i,i+3) ci+3 ci+2 ci+1
17
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Sumator równoległy cd.
Budujemy z bramek zmodyfikowany sumator 1-bitowy:
ai bi
ai
bi
& =1
ci
"
=
ci
=1
sumi
pi
gi
pi sumi
gi
=1 bramka XOR
18
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Sumator równoległy cd.
4-bitowy sumator z równoległą generacją przeniesień
ai+2 bi+2 ai+1 bi+1
ai+3 bi+3 ai bi
ci+2 ci+1
ci+3 ci
" "
" "
sumi+2
sumi+1
sumi+3 sumi
gi+2 pi+2 gi+1 pi+1
gi+3 pi+3 gi pi
ci+4
CLA
p(i,i+3)
g(i,i+3)
19
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Sumator równoległy dokończenie
Ustalanie wyniku oraz propagacja przeniesień w metodzie CLA są
znacznie szybsze niż w metodzie ripple-carry:
propagacja ripple CLA
c1 do ci+1 4.8 4.8 czas propagacji w ns
c1 do ci+2 9.6 5.6
c1 do ci+3 14.4 6.4
c1 do ci+4 19.2 4.8
Używając 4-bitowego sumatora CLA z poprzedniego slajdu można
budować sumatory 8-, 12-, 16-, bądz
ogólnie 4 x n bitowe
Sumatory CLA można łączyć tak, by przeniesienia między nimi
propagowały szeregowo (ripple), lub wprowadzić układ CLA
drugiego poziomu, zbudowany na takiej samej zasadzie jak układ
CLA pierwszego poziomu
20
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Budujemy ALU
Założenia projektowe
 4-bitowe argumenty A i B
AB
 4-bitowy wynik operacji
4
4
 Operacje arytmetyczne
dekrementacja A
inkrementacja A
ALU
dodawanie A+B
Wskaz
niki
Sterowanie
4
odejmowanie A B
 Operacje logiczne
f(A,B)
negacja A (uzupełnienie do 1)
iloczyn logiczny A and B
tożsamość A
suma logiczna A or B
 Wskaz
niki: przeniesienie i nadmiar
21
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Krok 1
A
B
Sumator z funkcjÄ… odejmowania
S
S Funkcja Opis "
c4
0 A+B Dodawanie
F
1 A+B +1 Odejmowanie
a3 b3 a2 b2 a1 b1 a0 b0
S
=1 =1 =1 =1
c4
" " " "
f3 f2 f1 f0
22
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Krok 2
Wniosek z kroku 1: sumator z ekstenderem może
realizować więcej funkcji niż samo dodawanie
Ogólna koncepcja ALU:
a3 b3 a2 b2 a1 b1 a0 b0
LE AE LE AE LE AE LE AE
x3 y3 x2 y2 x1 y1 x0 y0
c4 c0
" " " "
f3 f2 f1 f0
LE  logic extender, AE  arithmetic extender
23
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Krok 3  projekt AE
M S1 S0 Funkcja F X Y c0
1 0 0 dekrementacja A 1 A 1...11 0
1 0 1 dodawanie A+B A B 0
1 1 0 odejmowanie A+B +1 A B 1
1 1 1 inkrementacja A+1 A 0...00 1
M S1 S0 bi yi
Tablica prawdy
1 0 0 0 1
1 0 0 1 1
M wybór funkcji: 1  arytmetyczne,
1 0 1 0 0
0  logiczne
1 0 1 1 1
1 1 0 0 1
S1, S0 wybór operacji
1 1 0 1 0
1 1 1 0 0
yi stan na wyjściu i-tego bloku AE
1 1 1 1 0
24
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Krok 4  realizacja AE
bi
S1S0
S0
00 01 11 10
bi
NOT
NOT
0
1
1
S1
NOT
1
1 1
M
yi = M S1bi + M S b &
0 i &
e"
AE
yi
25
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Krok 5  projekt LE
M S1 S0 Funkcja F X Y c0
0 0 0 negacja bitowa A A 0 0
0 0 1 iloczyn logiczny A and B A and B 0 0
0 1 0 tożsamość A A 0 0
0 1 1 suma logiczna A or B A or B 0 0
M S1 S0 xi
Tablica prawdy
0 0 0 a i
M wybór funkcji: 1  arytmetyczne,
0 0 1 aibi
0  logiczne
0 1 0 ai
S1, S0 wybór operacji
0 1 1 ai+bi
xi stan na wyjściu i-tego bloku LE
1 x x ai
26
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
ai
bi
Krok 6  LE
NOT
Ćwiczenie domowe: S0
zbudować mapę Karnaugh a dla
S1 NOT
tablicy prawdy LE z poprzedniego
NOT
slajdu i sprawdzić, że:
M
NOT
xi = M S1 S0 ai + MS1S0bi +
&&&&&
+ S0aibi + S1a1 + Mai
e"
LE
xi
27
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Krok 7  projekt końcowy
a3 b3 a2 b2 a1 b1 a0 b0
S0
S1
M
LE AE LE AE LE AE LE AE
x3 y3 y2 x1 y1 y0
x0
x2
c4
" " " "
c0 &
c3
f3 f2 f1 f0
=1
nadmiar (overflow)
28
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
RozwiÄ…zanie alternatywne ALU
CarryIn Operation
Komórka ALU zbudowana przy użyciu
multipleksera oraz schemat 32-bitowego a0
CarryIn
Result0
ALU0
ALU b0
CarryOut
Operation
CarryIn
a1
CarryIn
Result1
ALU1
b1
a
CarryOut
0
a2
CarryIn
1
Result2
Result
ALU2
b2
CarryOut
2
b
a31
CarryIn
CarryOut
Result31
ALU31
b31
Operacje: +, and, or
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
RozwiÄ…zanie alternatywne cd.
Komórka ALU wzbogacona o funkcję odejmowania
Binvert Operation
CarryIn
a
0
1
Result
b 0
2
1
CarryOut
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Elementy i bloki sekwencyjne
Przerzutnik  podstawowy element sekwencyjnych bloków
funkcjonalnych komputerów
Q
S
R
Q
SRQQ
0110
1001
S
Q
1 1 stan
0 0 niedozwol.
Q
R
31
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Przerzutniki cd.
Przerzutnik D  schemat logiczny i tablica stanów
D Clock Q
D Q
00
Clk Q
11
Przerzutnik D
PR
D Q
z asynchronicznymi
wejściami do ustawiania
Clk Q
(PR  preset) i zerowania
CLR
(CLR  clear)
32
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Przerzutniki cd.
Przerzutnik J-K  schemat logiczny
J K Clock Q
PR
J Q
0 0 bez zmian
>Clk
0 1 0
K Q
1 0 1
CLR
1 1 stan przeciwny
4-bitowy licznik binarny z przeniesieniami szeregowymi
Vcc
X0 X1 X2 X3
J Q J Q
J Q J Q
> >
> >
K K
K K
33
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Rejestry
" Najczęściej zbudowany z
Write Enable
zatrzaskowych przerzutników typu D
(latch)
Data In Data Out
" Jeśli WE = 1, stan Data In zostaje
n n wraz z opadajÄ…cym zboczem zegara
wpisany do rejestru i przeniesiony na
wyjście Data Out
Clk
" W technice komputerowej najczęściej wykorzystuje się rejestry przesu-
wające, które oprócz zapamiętywania n-bitowego słowa mogą je przesuwać
" Najprostsze rejestry przesuwające przesuwają swoją zawartość tylko w
jednym kierunku o 1 pozycjÄ™ (1 bit)
" Bardziej złożone rejestry przesuwają dane w obu kierunkach (SL  shift left,
SR  shift right)
" Na wyjściu ALU znajduje się zwykle szybki rejestr przesuwający (barrel
shifter)
34
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Plik (bank) rejestrów
Przykładowy plik rejestrów pokazany
obok składa się z 32 rejestrów:
 dwie 32-bitowe szyny wyjściowe busA
RW RA RB
i busB
WE
5 5 5
 jedna 32-bitowa szyna wejściowa:
busA
busW
busW
32
32 32-bit
 sygnał zegara ma znaczenie tylko
32
Registers
busB
przy zapisie; przy odczycie układ
Clk
działa jak układ kombinacyjny
32
Rejestry sÄ… wybierane przez:
Przykład pliku
 RA  numer rejestru
rejestrów o organizacji
wyprowadzanego na szynÄ™ busA
32 x 32 bity
 RB  numer rejestru
wyprowadzanego na szynÄ™ busB
 RW  numer rejestru zapisywanego z
szyny busW jeśli WE=1
35
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Pamięć
Szyny
WE
Adres
 jedna szyna wejściowa: Data In
 jedna szyna wyjściowa: Data
DataIn DataOut
Out
n
n
SÅ‚owo n-bitowe zapisane w
Clk
pamięci jest wybierane przez:
 adres o długości zależnej od
pojemności pamięci
Schemat logiczny bloku
 sygnał WE = 1
pamięci n-bitowej
(wyidealizowany)
Sygnał zegara Clock (CLK)
 sygnał CLK ma znaczenie tylko
przy zapisie
 przy odczycie układ zachowuje
siÄ™ jak kombinacyjny
36
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Elementy trzystanowe
W systemach komputerowych często zachodzi potrzeba łączenia
wyjść różnych układów cyfrowych na wspólnej szynie. Wygodnym
rozwiązaniem są wyjścia trzystanowe. W trzecim stanie (wysokiej
impedancji) wyjście stanowi wysoką impedancję umożliwiającą
traktowanie połączenia jako rozwarcie.
enablein
Szyna
Układ
enableout
Inwertery i bufory z wyjściem trzystanowym są często używane do
połączenia układów z szynami (bus drivers)
 dwa drivery umożliwiają realizację połączenia dwukierunkowego
 dodatkowym zadaniem driverów jest wzmocnienie sygnału, dzięki
czemu szyny mogą być dłuższe
37
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Multiplikator
38
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
1101 (13)
Przykład mnożenia
Stan
x1011 (11)
poczÄ…tkowy
Counter
3 1 1 0 1
1 1 0 1
0
C
Reg A
1
0 0 0 0 0 1 0 1 1
39
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Qo =1: dodaj mnożną
3 1 1 0 1
1 1 0 1
0
C
Reg A
1
0 1 1 0 1 1 0 1 1
40
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Przesuń wynik cząstkowy
dekrementuj
licznik
2 1 1 0 1
0
C
Reg A
1
0 0 1 1 0 1 1 0 1
wynik czÄ…stkowy
41
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Qo =1: dodaj mnożną
2 1 1 0 1
0
C
Reg A
1
1 0 0 1 1 1 1 0 1
wynik czÄ…stkowy
42
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Przesuń wynik cząstkowy
1 1 1 0 1
Qo =0
0
C
Reg A
0
0 1 0 0 1 1 1 1 0
wynik czÄ…stkowy
43
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Qo=0: przesuń (nie dodawaj)
po przesunięciu:
0 1 1 0 1
0
C
Reg A
1
0 0 1 0 0 0 1 1 1
wynik czÄ…stkowy
44
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Qo=1: dodaj mnożną
0 1 1 0 1
1
C
Reg A
1
1 0 0 0 1 1 1 1 1
wynik czÄ…stkowy
45
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Przesuń (koniec, Z=1)
0 1 1 0 1
1
C
Reg A
0 1 0 0 0 1 1 1 1
wynik końcowy
46
Wyższa Szkoła Informatyki Stosowanej i Zarządzania
Podsumowanie
Elementy i bloki kombinacyjne
 bramki, bufory (w tym trzystanowe)
 kodery i dekodery
 multipleksery
Synteza półsumatora i sumatora (look-ahead)
Synteza ALU
Elementy i bloki sekwencyjne
 przerzutniki
 liczniki
 rejestry
 pliki rejestrów
 pamięci
Metody opisu bloków cyfrowych (język VHDL)
Synteza układu mnożenia
47