INFORMATICA 3/85
LOGIČNI MODELI RACUNALNIŠKIH STRUKTUR
MAKSIMILJANGERKEŠ
UDK: 681.3.517.11/.12 TEHNIŠKA FAKULTETA, MARIBOR
VTO ELEKTROTEHNIKA, RAČUNALNIŠTVO IN INFORMATIKA
Koncept stanja in operacije, kot je znan iz snovanja programske opreme, je izhodiščni koncept z nekoliko širšo interpre-
tacijo. Nabor sestavljenih operacij tvorijo selektorska; sekvenčna in paralelna operacija. Definiranaje zančna operaci-
ja, ki ima poljubno mnogo ponovitev in nima izhoda. Transforrnacije, definirane nad sestavljerumi operacijami omogoča-
jonjihovo preoblikovanje, tako da jih lahko modeliramo z izbranimi mikroelektronskimi komponentami male, srednje,
velike, pa tudi zelo velike stopnje integracije, vključno z logičnimi mrežami. Na tej osnovi so zgrajeni modeli nekaterih'
značilnejših logičnih in računalniških striiktur. •
LOGICAL MODEli FOR COMPUTEH STRUCTURES: The concept of state and operation, as it is knovm from software design
is basic concept with extended interpretation. Collection of compound operations consists of select, sequential and para-
llel operation. An infinite loop operation with no exit terminal is defined. Compound operations can be changed with a •
set of defined transformations into a different forms which can be simply modeled with SSI, MSI, LSI, or even VLSI struc-
tures, including gate arrays. Models for some characteristic logic and computer structures are proposed on that base.
UVOD: .
Snovanje račuhalniških struktur postaja z ravojem mikro-
elektronske tehnologije vedno bolj kompleksno opravilo.
Ob predpostavki, da omogočajo metode programskega
snovanja učinkovito reševanje nalog na področju program-
ske opreme, se zdi vprašanje, ali je možno te metode
enako učinkovito uporabljati tudi za snovanje strojne
opreme povsern utemeljeno. Ekspliciteti odgovor na tako
zastavljeno vprašanje bi bil zaenkrat precej spekulativen.
Lažje je odgovoriti tako, da je možno s smiselno prire-
ditvijo teh postopkov, dbseči z njimi dobre rezultate tudi
na področju snovanja strojne opreme.
Začetni zapis računalniške strukture, ki jo želimo reali-
zirati običajno pojmujemo kot nekakšno amorfno struktu-
ro, saj zaradi semantične razdalje v splošnem ni možen
neposreden prehod na logično izvedbo te strukture. lz-
kušnje učijo, da ni smotrno vtiaprej predposUivljati orga-
nizacijo takšne strukture na logičnem nivoju, ampak da
jo je potrebno izpeljati iz lastnosti specifikacije, iz kate-
re izhajamo, z upoštevanjem zunanjUi parametrov-hitrost,
cena, zanesljivost, ...
Ob takšnem izhodišču nas postopki snovanja strojne opre-
me s pomočjo modelov brez večjih neprijetnih presene-
čenj vodijo do želene realizacije: Koraki, ki jih pri tem
izvajamo, so podobni snovanju programske opreme, le
da so osnovne struJuure drugačne. Upoštevati pa mora-
mo tudi zunanje parametre, kamor sodijo tudi realne
lastnosti mikroelektronskih koraponent, ki jih lahko ide-
aliziramo samo na višjih abstraktnih nivojih snovanja.
Neupoštevanje zunanjih parametrov lahko povzroči, da
moramo sicer korektno žasnovano in logično pravilno re-
šitev opustiti in poiskati novo, ki bo dovolj upoštevala te
zahteve.
Koncept stanja in operacije, kot ga poznamo iz snovanja
programske opreme, je izhodiščni koncept, le da ga in-
terpretiramo nekoliko širše. Nabor sestavljenih opera-
cij je drugačen in sestojiv osnovi iz selektorske, se-
kvenčne in paralelne operacije. Za izgradnjo modelov
sekvenčnih krmilnih enot pa je definirana zančna opera-
cija s poljubno mnogo ponovitvami.
i •
Preoblikovanje sestavljenih operacij omogoča nabor trans-
formacij, s katerimi lahko le-te preoblikujemo tako, da
najdemo zanje - ali jih sami definiramo - primerne mi-
kroelektronske gradnike, ki so lahko male, srednje, ve-
like, pa tudi zelo velike stopnje integracije, vključno z
logičnimi mrežami.
1. STANJA IN OPERACUE
Koncept stanja in operacije smiselno prilagodimo za po-
trebe snovanja strojne opreme. S tem bo prehod iz for-
malizirane specifikacije računalniške strukture na njen
logični model razmeroma tekoč. Kot iztočnico uporabimo
koncept stanja in operacije, tako kot je specificiran v
/1/. Formalnega dela definicije ne bomo spreminjali in

bomo stanje pojmovali samo kot nabor imenovanih vred-
nosti.
Pojem operacije poiiazorimo kot prireditev, ki začetnemu
stanju priredi končno stanje.
Formulo, ki določa pogoje za izvajanje operacije povza-
memo po / 1/:
(Vs«S)(Pi(s) —Po (s, ex (Op, s))) . (1.1)
Za vsako stanje s iz prostora statij a, ki izpolniuje za-
četno trditev določerio s predikatom l'i, se z izvajanjem
operacije Op določi (izračuna) izhodno stanj e ex(Op,s),
ki je z začetnim stanjem povezano s končno trditvijo, ki
jo specificira predikat Po.
S taitšno opredelitvijo stanja in opernrije se ne /elimo
omejiti na krmiljenje operacij, po principu ... izvedi
operacijo i, izvedi opredijo i+1 ... .
Če ponovno preberemo (l.l) laliko specificiramo krmil-
ni pogoj za izvajanje operacije tudi takole ,.če je zadano
stanje s trditev določena s predikatom l'i iz|X)lnjena, te-
daj seoperacija Op lahko izvede .... Zadnjo izjavo raz-
širimo takole: ... izvedejo se lahko vse tisle operacije
izmed Op , Op , ..., Op za katere velja da so pri-
12 n
padajoče trditve Pi , Pi^,..., l'i izpolnjene nad stanji
S1'S2 Sn"' •
Za to izjavo riajdemo v praksi pocjosto naslednji približek:
... izvedejo se lahko vse tiste instrukcije, /.a katerp
velja, da imajo veljavne Izvorne operatide ....
Če povzamemo, lahko rečemo, da je niozno o[X3raiijo v
obeh skrajnostih izvajali s krmilnim oz. podatkovnim
pretokom. Formula (l.l) predpisuje samo pocjoj, kdaj
se operacija lahko izvede, ne predpisuje pa, kdo je tisti,
ki ugotavlja izpolnjenost pogoja - clovek oz. stroj.
1.1. MODEL PODATKA
Za logični model računalnLške strukture prilagojen zapis
stanj oz. njihovih komponent, iz<jradimo model s pomoč-
jo izjav, s katerimi opisujemo elemente izbranili mtiozic,
katerih člani so vredno.sti komj>onent st'mj, imona kom-
ponent stanj, imena operacij, ....
Vzemimo množico elementov IJ in vsakemu elementu, ki
je član te množice, priredimo izjavo, ki le-tega enolično
opisuje. Če ima množica I) m olomentov , je izjnv, ki tn
elemente opisujejo |^"uv tako in. Izjave označimo z
Dm-,'Dm-2 °0-
Sedaj pa izberimo še n izjav ob pogoju m^2 , ki jili oz-
načimo z A , A , ..., AQ in zaenkrat ignorirajmo
vsebino teh izjav. Če tvorimo vse možne konjunkcije teh
izjav, s tem da pravilnostne vrednosti izjavam sami
|iredpišemo dobimo:
VlAln-2A-AXlAA0
V,AV2A-AA.AAo
An-lAAn-2A-"AA,AA0
V,AAn-2A-"AA.AA0 •
iedaj pa tvorimo m ekvivalenc, tako da vsaki izjavi iz-
med U , D , ... D predpišemo kot ekvivalentrio
0 1 m-1
izjavo poljubno konjunkcijo izmed (1.1.1), vendar tako,
da bo prireditev enolična.
Za zgled pred|»st.'wirr>o , da je m»2 in tvorimo eno iz-
rned možnih prireditev.
An-lAAn-2A-"AAlAA0"D3
Izjavam A , A ,...,A,, A priredimo pravilnostne
n-1 n-2 1 0
vrednosti glede (1.1.2) indobimo:
An-1
0
0
0
0
1
1
An-2"-
0 ...
0 ...
0
0 ...
1 ...
1 ...
Al
0
0
1
1
1
1
Ao
0
1
0
1
0
1
Do
Dl
D3
Dm-2
Dm-1
(1.1.3)
Če si zapomnimo prireditev (1.1.3) lahko z nizi pravil-
nosUiLh vreclnosti izjav A , A ..... A , A ponazo-
n-1 n-2 1 0
rimo elemente množice D.
Na opisan način lahko praktično elemente poljubnih mno-

žic priredimo za logični nivo pri izgradnji modelov ra-
čunalniških struktur. ...
Doslej nas notranja zgradba izjav ni posebej zanimala.
Včasih pa lahko z upoštevanjem notranje zgradbe izjnv,
izgradimo modele, ki imajo podobne lastnosti kotoricji-
nalni podatki. Takšen pristop ham včasih olajša •izgrad-
njo modelov operacij nad tako modeliranimi.podatki.
Kot zgled uporabimo množico dvojiških štev.il, ki jo opi-
šemo z izrazom:
(2.1.1)
Pn=R1(e1(š1.),s.)AR2(e2(s.),s.)A...ARn(en(s.),s.) .
V izrazih (2.1.1) soR ,R,...,R predikati, s. je za-
četno stanje, e, j = 1, 2, ..., n pa so lunkcije.
LcKjična pravila, s katerimi opišemo selektorsko opera-
c ijo, so:
Pi (s.)A
kjer je a.e {o, l} in i = 0, 1,..., n- I.
Sedaj specificirajmo n izjav takole:
Koeficient a. ima vrednost 1, . ,
1 2
a. »0, 1, ... , n-1 . • • '
( 1. 1 .">)
Izjava je pravilna, če je trditev resnična, drugače je
napačna. Pri takšnem mbdelu lahko na primer sešteval-
nik po mod nad dvojiskimi števili |onazorimo z opera-
cijo logične ekvivalence nad izjavami (1.1.5).
2. SESTAVLJENE OHERAC-IJK'
2.1. SELEKTORSKA OPKRACIJA
Selektorsko operarijo portazorimo z t)/.riiičenim nsmerje-
nim grafom tia sliki 2.1.1."
Po.
Slika 2.1.1: Graf selektorske operacije
Selektorska operacija je sestavljena. op.erac:iju, kjer SP
naenkrat lahko izvede samo ena izmed operacij Op , ,
Op ,.'.., Op . Katera operacija se bo izvedla, je od-
Z n
visno od pravilnosti ene izmed izjnv P , l'o, ... P , ki
jih definiramo takole:
P1=R1(e1(s.),s.)AH.)(e9(s.),s.)A...ARr|(er|(s.),s.)
P2=R1(ei(s.),s.)AK2(e2(s.),,s.)A,..ARn(e (s.),s.)
I'i(s.)A P -^ Pi (s.)
i . n n l
PitspAPjAPo^s.', sQ) — Po(s.', sQ)
Pi(s.')AP2APo2(s.', sQ) l— Po(s.',s0)
(2.1.2)
Nadspodnjo polovico izrazov (2.1.2) uporabimo formu-
lo 0V ...V 0VAV0 V. ..V0>A in dobimo :
1 • . ' ' • (2.1.3)
Vl'i(s.')A P A Po (sf.sj) Po(s.',sn) .
l n n 1 0 l 0
Ce upoštevamo se: (AAB)V ••• V( A A C )=A A (13 V. • VC )
dobimo naslodnji izraz:
i 1 1 i' 0 2 2 i1 0 (2.1.4)
V 'izrazih (2. 1.2) do (2.1.4) je s.' spremenjeno sUuije s.,
ki (ja povzroči operacija Op ali Op^ ali ....
Zapis (2.1.4) sicer s stališča snovanja programske opre-
me ni posebno zanimiv, vendar je njegova zrjVadba" zna-
cilna v loliko, da-nas navede na definicijo poenostavljene
selektorske operacije, ki.jo specificirajmo takole:
sel (!>.):
P —- Op
1 1
P2 — Op,
(2.1.5)
V —- Op
.n n ' .
Pj, P^, ..., P^ so izjave, Op^, Op^,..., Op^ pa izjave
nli podatki modelirani v sinislu rn/.delka (l.l). Za iz-
jave P , P ,..., P |X>novno velja ixx)oj, da je lahko na-
enkrat pravilna samo ena izmed njih.
Z izrazom AA(A —• 13) zožimo pravilnpstni prostor
implikacije, tako da je enak prosloru pravilnosti konjunk-

cije AAB. Napravimo to za implikacije v (2.1.5).
-B-
(2.1.6)
P A(P — Op ) = P AOp
n n n n n
Upoštevamo OV ... V OVAV OV ... V 0 = A in zapišemo:
P1AOpiVP2A°P2V">VPnAUPn * (2.1.7)
Izraz (2.1.7) sicer strogo gledano ni ekvivalenten zapi-
su (2.1.5), vendar se dogovorimo, da bomo (2.1.5) bra
li takole ... če je Pi pravilna, tedaj je pravilna tudi
Op.
Na sliki 2.1.2 so podani zgledi modelov nekaterih tipič-
nih gradnikov s pomočjo poenostavljene selektorske ope-
racije.
V(SQAŠ,AŠn)A(B - A - 1 +C. )V
Š . OR . B)V
+ B + c.)V
c) model ALU operacijske enote
Slika 2.1.2: Zgledi uporabe poenostavljene
selektorske operacije za Izgradnjo
loglčnih modelov
Pri tem smo ponovno predpostavili, da so skrajno desni
konjunktivni členi ponazorjeni v smislu razdelka 1.1.
Zaradi lažje orientacije je na sliki 2.1.3 podan še eden
izmed možnih strukturnih modelov za c) s slike 2.1.2.
h h h h
1111
a) model multipleksirnika
An-1 V Ao U
1
V(S,Afo)A'lV
b) model bralnega pomnilnika
A B
0 A.XOR.B
1
A-B-1-C1n 1
...
A
B
MUX
Slika 2.1.3: Blokovna shema možnega strukturnega
modela za c) 2.1.2
2.2. SEKVENČNA OPERACIJA
Cri specifikaciji sekvenčne operacije izhajamo iz grafa
na sliki 2.2.1.
Logirna pravila za sekvenčno operacijo zapišemo takole:
l'i(Sj) -^
(2.2.1)
— Pi (s )
n n
-Po (Sj, sQ).
V (2.2.1) smo upoštevali, da lahko Op spremeni kom-

U sel
~~ °P2 (2.2.2)
Po_
Po(ar a0)
• Slika 2.2.1: Graf sekvenčne oper.-icije
ponente v s., ki zalo preide v s .
Do zanimivih zaključkov pridemo, re i/.<irarlim<> sekvenč-
no krmiljen model sekvenčne .operuuije. V ta nanien precl-
postavimo, da je sekvenčna operacija s slike 2.2.1 del
sestavljene operacije in jo ponazorimo po sliki 2.2.2.
Q -~ Op
n ii
Na sliki 2.2.3 je podan nekoliko prilagojen graf selek-
torske operacije, s katerim ponazorimo krmiljenje izva-
janjn sekvenčne operacije s slike 2.2.1.
Slika 2.2.2: Prirejen graf sekveiične openicijo
Vozliščem grafa na sliki 2.2.2 smo pripisali izjave
Q , Q ,..., Q . Izjava Q 1 = 1, 2,..., n je prav ilna
tedaj in le tedaj, ko je cjlede na sekvenčno operacijo s
slike 2.2.1 izpolnjena pripadajočn izjava 1'i^Sj) in se
operacija Op še ni izvedla. Tedaj lahko (jraf s slike
2.2.2 preoblikujemo v selektorsko operacijo in zapišemo:
Slika 2.2.3: Graf modela krmiljenja izvajanja
sekvenčne operacije
K dosedanjim izvajanjem sekvenčnetia krmilnega modela
in sliki 2.2.3 pripbmnimo, da bo sekvenčno krmiljenje
operacij podrobneje obdelano v razdelku 2.5.
2.3. 1'ARALELNA OPERACUA
V dosedanjih izvajanjih sekvenčne operacije smo predpo-
stavljali, da je začema trditev Pi.(s.) operacije Op. pra-
vilna šele, ko se izvedejo vse operacije Op , Op , ...,
Op. . Pri izpeljavi paralelne operacije pa sprostimo -tn
|)CX)OJ.
Izhajajmo iz grafa sekvenčne operacije na sliki 2.3.1.
Logična pravila za takšno sekvenčno operacijo so:
(2.3.1)
Sedaj pa predpostavimo, da velja:

Po
Slika 2.3.1: Graf dveh sekvenčno povezanili operacij
s.) — Pi2(s.) , (2.3.2)
že izvršila ali ne. Za končni pogoj lahko tedaj zapišemo:
da je Pi (s.) pravilen neodvisno od tega, ali se je Op
— Po(S],(s2,s3)). (2.3.3)
Z (s ,s ) smo označili konkatenacijo s0 in s . 2.a pona-
zoritev paralelne operacije vpeljemo 'jraf, ki cja podaja
slika 2.3.2.
Po,
Sllka 2.3.2: Graf paralelnc operarije
Izvedimo še posplošitev paralelne operacije na n piiralel-
no povezanih operacij in zapišimo logična pravila:
Pi(s.) — Pi (s.)
i n l
(2.3.4)
— PO(S1' (S2'S3 »
Pripadajoč graf podaja slika 2.3.3.
Pogoj za paralelno izvajanje operacij je v bistvu ta, da
Slika 2.3.3: Graf n paralelno povezanih operacij
operacija Op. ne spremeni tistih komponent stanja s., ki
so tudi začetne komponente za Op , Op ,..., Op. ,
Op. ,..., Op . Enako velja tudi zavse ostale operacije.
Operacija tedaj lahko spremeni samo tiste vhodne kom-
ponente v stanju s., ki so vliodne komponente samo te
operacije, sicer se mehanizem paralelnega izvajanja
poruši.
Takšno paralelno operacijo lahko tedaj razstavimo na
komponente, med katerimi ni več nobene povezave. Sli-
ka 2.3.4 podaja tako razgrajeno paralelno operacijo.
Pln(3i")
Slika 2.3.4: Grafi operacij, ki se lahko izvajajo
paralelno
2.4. 1'HKUUMKOVANJli SliSTAVLJtMH OPliUACIJ
Kazdelek |x)daja nekatere možnosti preoblikovanja ses-
tavljenili operacij.
a) Preoblikovanje sestavljene selektorske operacije v
selektorsko operacijo.
Selektorsko operacijo s slike 2.4.1 zapišimo v disjurik-
tivni obliki.
• • .AQnlAQn)A Op^
V(Q]AQ2A...AQnlAQn)AOp3v
(2.4.1)

a-°Pm-l
b - Op ' •
m
Slika 2.4.1: Sestavljena selektorska operacija
Konjunkcije izjav Q., i = 1, 2, ..., nv (2.4.l) poime-
nujmo s P,, P,,..., P , m=2 indobimo:
l c, m
Z izrazom (2.4.2) pa lahko opišemo tudi selektorsko
operacijo, katere graf podaja slika 2.4.2.
b) Prepblikovanje paralelne selekiorske operacije v [vira-
lelno povezane selektorske operacije
Sliko 2.4.3 opišemo s poenostavljeno selektorsko opera-
cijo:
sel(P.):
, - (OPU, oPi2 opj
2^(op21,op22 op2n)
a - Op
m-1
Slika 2.4.2: Graf selektorske operacije za izraz 2.4.2
1 - Op, 4-Op, 7 - Op
11 K21 ' -*-mi
2-Op,o 5-Op00 8-Op
'12 " ~F22 " "Fm2
.'!•- Op, 6 - Opn <) - Op
rln K2n Kmn
Slika 2.4.3: Graf paralelne selektorske operacije
in preoblikujemo v disjunktivno obliko:
piA(Oph' Opi2 oP
Izraz (2.4.4) zapišemo po komponentah.
(2.4.3)
(2.4.5)

10
V izraze (2.4.5) pa lahko preoblikujemo tudi naslednje
selektorske operacije:
sel (P.
l-°P,2
sel
o."
P, -
P2 7
P —
m
Opn
°P21
Opmi
sel
sel (F ):
r
(P.):
pl, -
1'., -
p -
m
°Pln
(2.4.0)
— Op
2n
p _^ Op
m mn
Gral selektorskih operacij (2.4.6) je podan na sliki
2.4.4, kot paralelno povezane selektorske operacije.
Opomba: koda operacij je na sliki 2.4.3.
Slika 2.4.4: Graf paralelno povezanU) selektorskih
operacij
c) Preoblikovanje paralelne selektorske operacije,
kadar se operacije ponavljajo
Primerov za ponavljanje operacij v paralelrii selektorski
operaciji je veliko. Omenimo samo mikroprocjramirano
krmilno enoto, asociativni pomnilnik, razne recjisterske
strukture, ki omogočajo paralelen dostop do podatkov,
procesorje z množico funkcijskih enot, itd.
Ponazoritev takšnih sklopov s paralelno selektorsko ope-
racijo ima svojo težo, saj jih lahko tako fia višjih abstrak-
tnih nivojih snovanja ponazorimo v koncentriranem zapisu,
ki ga postopoma razgrajujemo z napredovanjem pri iz-
rjrarlnji modeln.
Preoblikovanj e paralelne selektorske operacije z lastnost-
jo ponavljanja operacij ponazorimo z zgledom:
sel
— A , 1 , a
— A, 1, b
— A, 1, c
— A, 2, a
— A, 2, b
— A, 2, c
—•• A, 3, a
— A, 3,b
0—- A, 3, c
6"*°' *' a
?—B, 1, b
8— B, l,c
;0— B, 2, a
,,— B, 2, b
!2— B, 2, c
<A-~ D, 3, a
,s— B, 3,b
,6— B, 3, c
(2.4.7)
p.
1
p
0
pl
P2
P
4
P5
"6
P8
P9
pio
P16
P17
P18
P
20
P21
P22
P24
P25
P26
Q
4
04
54
Q
4
%
Q4
%
%
%
Q4
Q4
Q4
Q
4
Q4
Q4
Q4
Q4
Q4
!i 2
Q3 «2
Q3 %
Q Q
3 2
?3 Q2
Q U
3 2
Q Q
s <
Q3 Š
^3 Š
Š Š
53 Š
Q Q
3 2
53 Q2
53 Q2
S \
% %
Q3 Š
1 0
Q Q
Q Q
1 0
Q Q
1 0
Q, %
Q Q
1 0
Qj %
Q, %
Q Q
1 0
Q, Qo
Q Q
1 0
Q Q
1 0
Q Q
1 0
Q, %
Q Q
1 0
Q Q
1 0
Q Q
1 0
Q Q
1 0
(2.4.8)
(2.4.8) je tabela izjav, ki jih priredimo izjavam P..
Paralelno selektorsko operacijo (2.4.7) laliko sedaj na-
domestimo s tremi selektorskimi operacijami.
sel(Q4): sel(Q3,Q2):
Q3AQ2
Q3AQ2
Q3AQ2 — 3
sel (Q},QQ)--
Q,AU0 —
(2.4.9)
(2.4.9) lahko glede na točko b) ponazorimo v grafu kot
tri paralelno povezane selektorske operacije.
2.5. MODEL SEKVENČNEGA STROJA
Izliajamo iz implikacij:
Ap (I, Q) — Q
Ap (I, Q) — Z ,
(2.5.1)
kjer smo z I ponazorili niz izjav (i ,,i „,..., i,,)
m-1 m-2 u
inzQ niz izjav (q , q ,..., q ). Z A(', Q) ozna-
čimo vse možne konjunkcije sestavljenega niza (I, Q),

11
j Ap('i Q) pa izbor poljubnega števila konjunkcij iz
A(I, Q), Z pa naj bo znak za niz (z , z o,...,z ).
(2.5.1) lahkp ponazorimo s paralelno selektorško opera-
sel (P.):
P. — Z. , V.
l+v l+v i+v+1
kjer smo s ... , P., ... označili konjunkcije iz tabele
Ap(I,Q). Pri tem v splošnem ne zahtevamo enoličnosti
prireditev ... Z niti desne strani ... P ... v
i i+1 .
(2.5.2), oz. isti Z. in P. se laliko na desni pojavijo več-
krat, medtem pa mora biti leva stran (L!.:"i.2) enolična.
(2.5.2) ponazorimo z (jr.ifom paralelru; selektorske ope-
racije na sliki 2.5. L.
(2.5.1) in
f : I x Q —- Q .
cj :. IxQ^-~Z ; -.-.•. • • .(2.5'.3)
ter so I - vliodi, Q - stanja, Z - izhodi in f in g.presli-
kavi.
Pravkaropisani model nekoliko dopolnimo, tako da ga
bolj približamo obliki s kakršno imamo opravka v praksi
snovanja strojne opreme. Za ta namen najprej definiraj-
mo rep in glavo niza 1 • (i , i ,..., i., i. ,,...,
m-1 m-2 j j-1
i ) ter poimenujmo glavo niza I s P in rep niza I z B in
ju označimo takole:
•' » (P, v. P_ ,i...-i Pn) (2.5.4)
kjer so r-l = m-1, r-2 = m-2, ... ins-1 <• j-1 i>s-2 = j -2,
Niz P imenujmo zuhanjevhodne izjave, niz B pa notranje
vhodne izjave. . '
Sedaj pa narišimo nekoliko modificiran graf s slike
2.5.1 nasliki 2.5.2. ...
<bs-l V
a - Z.
b - Z
c - Z.
d -
e-Q. „
1+2
f - Q
i+v+1
1 - P.
2 - P.
i+l
3 - V.
Slika 2.5.1: Graf vase zaključene paralelne
selektorske operacije
Tako definiramo selektorsko operacijo lahko imenujemo
model Mealyjevega stroja, če napravimo primerjavo med
Slika 2.5.2: Modificiran graf paralelne .
selektorske operacije s slike 2.5.1
V sliko (2.5.2) smo vgradili operacijsko enoto OP, ki
izvaja operacije določene z Z in kot rezultat daje izjave
B o izvedenih operacijah. Podatkovni del operacijske eno-
te nas zaenkrat ne zanima. (b •• , b •,..., b ) imenu-
jemo vejitvene pogoje, ker omogočajo izvajanje vejitev
v grafih operacij, ki jih modeliramo na takšnem modelu .

12
Sedaj pa vgradimo v naš model še mehanizem, ki omogo-
ča časovno prekrivanje operacij med krmilno in operacij-
sko strukturo modela, kadar so izjave (b , b , ...
.., b ) neaktivne. V ta namen oblikujmo graf našega mo-
dela po sllki 2.5.3.
(Pp-l
"s-1
Slika 2.5.3: Model izvajanja operacij s časovnim
prekrivanjem
Na sliki 2.5.3 imenujmo D zakasnilni element, ki vhod-
ne izjave prenese na izhod s časovno zakasnitvijo, kate-
re dolžina naj bo zaenkrat določena z zunanjimi pogoji.
K grafu, na sliki 2.5.3 narišimo še pripadajočo blokov-
no shemo, kakršne smo pri snovanju bolj vajeni, na sli-
ki 2.5.4.
Preden nadaljujemo z izgradnjo krmilnega modela defini-
rajmo še modela programirane logične ureditve in bral-
nega pomnilnika. V ta namen izhajajmo iz poenostavljene
selektorske operacije:
...VA AD , (2.5.5)
kjer soA., i=0, 1,..., m-1 enolično prirejene vsem
možnim konjunkcijam nad nizem (an_j» an-2**"' a0^
in D. poljubno izbrane - v splošnem ne enolično - iz ta-
bele izjav:
11-1 11-1 11-1
BRALNI POMNILNIK ALI
PROGRAMIRANA LOGIČNA
UREDITEV .
1
...
2(n*l)
D
""' Q
D
Z(n) Q(n)
B = (b^ bo)
Slika 2.5.4: Blokovna shema modela sekvencnega
stroja z operacijsko enoto
dt-r "
at-.'-
...,d1,
1 r
...,d..
do
do
5o
dt-i di'do
(2.5.6)
dt-i di'do •
Ce "preberemo" iz bralnega pomnilnika z "adrese" A
"element" U. lahko to zapišemo takole:
. = 0V0V...VAJADJV0V-..V0 (2.5.7)
i
Model programirane logične ureditve je v bistvu identičen
s to razliko, da (2.5.5) zapišemo po komponentah in v
zapisu izpustimo vse tiste konjunkcije, ki imajo zaradi
d » 0 vrednost 0. V disjunktivne zapise vstavimo tedaj
samo tiste komponente d., ki imajo vrednost 1, glede na
tabelo (2.5.6).
S stališča uporabe lahko tedaj rečemo, da v splošnem ni
potrebno razlikovati med bralnim pomnilnikom in progra-
mirano logično ureditvijo, saj lahko oba gradnika po po-
trebi interpretiramo kot bralni pomnilnik oz. progiramira-
mo loijično ureditev.
Sedaj pa nadaljujmo z izgradnjo modela mlkroprogramira-
nega krmilnika. V ta namen definirajmo selektorsko ope-
racijo, s katero bomo izdelali začetni približek k sekven-
cerju rnikroprogramiranega krmilnika. Iz nizev:
^n-l'^n-2'
B=(bs-l'bs-2 V
(2.5.8)
Q= (q
n-l'Hn-2' '•••

13
z operacijami glava, rep, delni niz, konkatenacija, glava
delnega niza, rep delnega niza, konkatenac ija delnega ni-
za tvorimo nize enakih dolžin in jih poimenujmo z
A • (a ,a ..... aj. Oglejmo si nekaj primerov
n-1 n-«2 u
tako koristruiranih nizev:
' B
Vi' •.— •' Vqo
2.5.9)
Pn-1 Pl'P0
Pri tem bomo.smatrali, da lahko v splošnem vsi elemen-
ti tako definiranih nizev zavzamejo vrednosti q ali q
b ali b in p ali p inalnc« (o, l,...,n-l} ter
e€ (0,1 s-l} ' .
Sedaj pa definirajmo selektorsko operacijo s katero iz-
biramo nize, ki smo jih konstruirali po zgornjem pravi-
lu.
sel(BR.):
BH —- niz 1
BR — niz 2
. (2.5.10)
Za zgled predpostavimo, da ima niz j takšno obliko:
Vi'V2 vVV
Z BR. tedaj izberemo enega izmed nizev
6,'bo
bi'5o
Vr V2 V br bo '
odvisno pač od trenutnih vrednosti, ki jih imajo izjave
Za seleklorsko operacijo (2.5.10) bomo smatrali, da
opravlja nalogo sekveneerja adres v začetnem približku
k modelu mikroprogramiranega krmilnika, (sl. 2.5.5).
S postopno širitvijo.začetnega modela sekvencerja ga lali-
ko opremimo z mehanizmi za strežbo podprogramov, pa-
sti itd., vendar lahko še tako kompleksen sekvencer. ved-
no prevedemo na selektorsko operacijo. Na sliki 2.5.6
je podana blokovna shema krmilnika izdelana na podlagi
graia na sliki 2.5.5.
Omenimo še, čeprav s tem prehajamo zastavljeni okvir
tega članka, da se krmilna struktura z izgradnjo mikro-
programskega krmilnika ne konča, ampak v splošnern
prehaja v operacijsko enoto, ki smo jo doslej opazovali
. Z(m-l) • - T BR(n*l)
Slika 2.5.5: Začetn i približek k mikroprogrami-
ranemu krmilniku
\
P B Q(n)
SEOTENCER L
\
BRALNI
BR(J)
/
A
POMNILNIK
D
,1
Z(n)
BR(n+l)
: D. ."
BR(n)
Q(n*l)
' D
Q(n)
Slika 2.5.6: Blokovna shema začetnega približka
mikroprogramiranega krmilnika
le kot koncentrirani gradnik strukture. Tudi izgradnjo

14
modela operacijske enote lahko v splošnem pričnemo s
selektorsko operacijo, ki jo razgrajujemo toliko časa,
dokler ne pridemo do gradnikov, ki jih s stališča izvaja-
njaoperacij lahko pojmujemo kot kuncontr irane gradnike.
Te gradnike obravnavamo tedaj kot elemetite, ki prično
izvajati izbrano operacijo z nastopom izvornih operandov
oz. v trenutku, ko so izpolnjeni pogoji začetne trditve
Pi(s) v (1.1).
3. ZAKLJUČEK
Podani so postopki snovanja z logičnimi modeli računalniš-
kih struktur, s katerimi je možen postopen prehod na lo-
gično realizacijo izbranih struktur.
Stanja in operacije je možno postopoma razgrajevati v
vedno večje detalje, postopek se konča, ko najdemo z.i
sestavljene operac ije skupek ustrezno povezanih mikro-
elektronskih gradnikov, katerih fimkcije ustrezajo sestav-
ljenim operacijam, s katerimi smo rnodelirali izhbdiščno
strukturo.
Pri predlaganih postopkUi snovanja moramo ra/.en no-
tranjih značilnosti strukture upoštevati tudi zunanje pa-
rametre - hitrost, cena, zanesljivosi, ..., ki v snova-
nje vnašajo komponento renlneja okolja.
Izdelani so modeli sestavljenih operacij, transformaci-
je med njimi in izgrajeni modeli nekaterih realnih logič-
nih in računalniških struktur.
4. LITERATURA
/1/ C. B. JONES: Software Design: A Rigorous
Approach, Prentlce-Hall International 1980.
/2/ M. GliRKEŠ: Metodologija snovanja računalniških
struktur in sistemov z upoštevanjem trendov v
razvoju tehnologije in konceptnih rešitev, diserta-
cija, Univerza Edvarda Kardelja v Ljubljani, Ka-
kulteta za elektrotehniko, Ljubljana 1984.
/3/ J. VliiANT: Preklopne funkcije, strukture in sis-
temi, Univerza Edvarda Kardelja v Ljubljani, Va-
kulteta za elektrotehniko, Ijubljana 1983.
/4/ M. GEUKES, M. PERNEK, M. PAGLAVEC: Aplika-
cija bipolarnega mikroprocesorja, Poročilo o delu
za leto 1984, UHP/RP: Računalniška oprema
03-2570, RSS, PORS 3, Visoka tehniška šola.Mari-
bor, 1984.
informatica85
Posvetovanje in semlnarjl Informatlca '65
Nova Gorica. 24. • 27 scptember 1985
Posvetovanje
18. jugoslovansko mednarodno posvetovanje za
raSunalniško tehnologijo in uporabo
Nova Gorica, 24-27. september 1985
Seminarji
Izbrana poglavja iz rafiunalniške tehnologije in upo-
rabe
Razstava
Razstava računalniške tehnologije. uporabe. litera-
ture in drugih ratunalniških naprav. z mednarodno
udelezbo
Sympošlum and Samlnar* Inlormatica '85
Nova Gorica, Seplembsr 24lh-27th, 1985
Conference
18lh Vugoslav Internalional Conlerence on Compu-
ter Technology and Usage
Seminar«
Selected Topics in Computer Technology and
Usage
Nova Gorica. Septomber 24th-27lh. 1985
Exhlblllon
Exhibilion ol Computer Technology, Usage, Litera-
lure and Other Compuler Equipmenl with Internalio-
nal Participation
Nova Gorica, September 24lh-27th, 1985