Over computers valt heel wat te zeggen, maar dit is geen cursus informatica dus niets hier over de hardware, niets over bedrijfssystemen, enz. Hieronder wordt een eenvoudig computermodel gegeven, en geïllustreerd aan de hand van de PDP8, een computer die populair was omstreeks 1970.
In dit hoofdstuk is een computer een machine met twee delen: een processor (CPU, Central Processing Unit) en een geheugen. Het geheugen is opgedeeld in cellen die elk een adres hebben, en kan precies twee dingen: (i) als een adres aangeboden wordt, de inhoud van de geheugencel met dat adres teruggeven, en (ii) als een adres en een waarde aangeboden worden, die waarde in de geheugencel met dat adres opbergen. De processor heeft zelf een klein beetje geheugen; de geheugen cellen in de processor heten registers. Een processor heeft ten minste één register, PC (Program Counter) genaamd, en voert de volgende oneindige lus uit:
(i) Vraag het geheugen naar de inhoud van de cel waarvan het adres door PC gegeven wordt.
(ii) Interpreteer deze inhoud als een instructie, en voer die instructie uit.
(iii) Hoog PC met 1 op, en ga weer naar (i).
(Hier zien we de "van Neumann bottleneck" optreden: instructies moeten van het geheugen naar de processor, en bij het uitvoeren van die instructies worden ook gegevens uit het geheugen gelezen of naar het geheugen geschreven. Deze flessehals, het draadje dat processor met geheugen verbindt, is een belangrijke beperkende factor voor de snelheid van een computer. Verfijningen zoals cache geheugens ontlasten dit draadje een beetje, en zorgen voor een belangrijke versnelling.)
Teneinde (ii) nauwkeuriger te beschrijven moeten we bij elke mogelijke geheugencelinhoud vertellen welke instructie hij voorstelt.
In de goede oude tijd waren zulke lijsten met instructies vaak tamelijk kort, met enkele tientallen soorten instructies. Later werd het aantal instructies sterk uitgebreid. Men spreekt van CISC (Complex Instruction Set Computing) bij computers zoals de Intel *86 familie, met veel meer dan honderd verschillende soorten instructies. Het bleek evenwel dat veel van deze instructies nooit gebruikt werden in door compilers gegenereerde code, en dat snellere machines gebouwd kunnen worden door voor een klein instructierepertoire (RISC, Reduced Instruction Set Computing) te kiezen (weer met enkele tientallen instructies), en ingewikkelder functies in software uit te schrijven. Bijvoorbeeld is het veel eenvoudiger een superscalar machine (een computer waarin twee of meer instructies gelijktijdig uitgevoerd worden) te bouwen als het aantal verschillende soorten instructies niet te groot is.
De PDP8 is een heel eenvoudige computer. In de hier beschreven versie heeft hij een geheugen met 2^12 = 4096 geheugenplaatsen, elk 12 bits groot. (De computer waarop ik dit schrijf, dertig jaar later, heeft een intern geheugen met 2^26 = 67108864 plaatsen, elk 8 bits groot, ruim tienduizend keer zo veel voor een twintigste van de prijs.) Er zijn 4 registers: twee 12-bit registers: PC (program counter) en AC (accumulator), en twee 1-bit registers oftewel vlaggen: L (link) en IE (interrupt enabled). De klokcyclus duurt 1.5 microseconde, de tijd benodigd voor een geheugenacces. De executietijd van een instructie is 1, 2 of 3 cycli, afhankelijk van het aantal benodigde geheugenaccessen. Elke instructie is een woord van 12 bits. De eerste drie bits bepalen het type instructie, zodat men zou kunnen zeggen dat de PDP8 acht verschillende instructies kent. Deze acht instructies zijn: AND, TAD, ISZ, DCA, JMS, JMP, IOT, OPR. De eerste zes instructies adresseren een geheugenplaats M:
AND: Schrijf de bitsgewijs logische AND van de inhoud van M en die van AC in AC. (Voorbeeld: (octaal) 5073 AND 4447 = 4043, oftewel (binair) 101000111011 AND 100100100111 = 100000100011; er komt een 1 als beide getallen een 1 hebben, en anders een 0.)
TAD (`two's complement add'): Schrijf de som van de inhoud van M en die van AC in AC. Als er een overdracht (`carry') is, complementeer dan L.
ISZ (`increment and skip if zero'): Hoog de inhoud van M met 1 op; als het resultaat nul is, sla dan de volgende instructie over.
DCA (`deposit and clear accumulator'): Schrijf de inhoud van AC in M, en maak AC nul.
JMS (`jump to subroutine'): Schrijf de inhoud van PC (die al opgehoogd is, en dus naar de volgende instructie wijst) in M, en schrijf M+1 in PC.
JMP (`jump'): schrijf M in PC (d.w.z.: ga verder met het programma vanaf adres M).
De geheugenplaats M die een instructie adresseert blijkt uit de laatste 9 bits van de instructie. Als de twaalf bits tttipaaaaaaa zijn, zodat ttt het type aangeeft (000=AND, 001=TAD, 010=ISZ, 011=DCA, 100=JMS, 101=JMP), dan geeft aaaaaaa een 7-bit adres aan. Hiermee kan niet het hele geheugen geadresseerd worden want 2^7 = 128 is minder dan 4096, en daarom is het geheugen ingedeeld in 32 `paginas' ter lengte 128. Met het bit p kun je kiezen uit twee paginas: als dit 0 is dan komt het adres uit pagina 0, en als het 1 is dan komt het adres uit de huidige pagina, die waarin de instructie ligt (dwz die aangegeven wordt door de eerste 5 bits van PC). Tenslotte is i het `indirect' bit: als de overige bits een adres M0 aanwijzen, en i = 0, dan is M = M0, maar als i = 1 dan is M de inhoud van geheugenplaats M0.
Een voorbeeld. De volgende subroutine KEER10 vermenigvuldigt een getal met 10. Hij wordt aangeroepen met `JMS KEER10', en bij het verlaten is AC tien keer zo groot als bij het binnenkomen. Hieronder eerst het adres, dan de geheugeninhoud, dan de symbolische (assembler) versie van de code. Alles is octaal (8-tallig).
0200 7766 MIN10, 7766 /CONSTANTE -10 (OCTAAL)
0201 0000 TELLER, 0 /GEHEUGENPLAATS GERESERVEERD VOOR TELLERTJE
0202 0000 GETAL, 0 /GEHEUGENPLAATS GERESERVEERD VOOR INVOER
0203 0000 KEER10, 0 /GEHEUGENPLAATS GERESERVEERD VOOR AANROEPADRES
0204 3202 DCA GETAL /BEWAAR INVOER
0205 1200 TAD MIN10 /LAAD AC MET -10
0206 3201 DCA TELLER /DEPONEER IN TELLERTJE, AC WEER 0
0207 1202 LUS, TAD GETAL /TEL GETAL BIJ AC
0210 2201 ISZ TELLER /AL VAAK GENOEG GEDAAN?
0211 5207 JMP LUS /NEE, GA VERDER
0212 5603 JMP I KEER10 /JA, KLAAR, KEER TERUG NAAR AANROEPADRES
Opgave
Hoeveel microseconden kost de aanroep JMS KEER10 ?
Hier een plaatje van het instructierepertoire.
Een van de meest voorkomende operaties is het copiëren van gegevens van één plaats in het geheugen naar een andere. Met bovenstaande instructies zou dat als volgt gaan (copieer N=128 woorden van HIER=1000 naar DAAR=2000):
0400 7600 TEL, 7600
0401 1000 HIER, 1000
0402 2000 DAAR, 2000
0403 1601 VERHUIS, TAD I HIER /PAK BEET
0404 3602 DCA I DAAR /SCHRIJF WEG
0405 2201 ISZ HIER /VOLGENDE BRON
0406 2202 ISZ DAAR /VOLGENDE DOEL
0407 2200 ISZ TEL /KLAAR?
0410 5203 JMP VERHUIS /NEE, DOORGAAN
*10
0010 0777 HIER, 1000-1
0011 1777 DAAR, 2000-1
*400
0400 7600 TEL, 7600
0401 1410 VERHUIS, TAD I HIER
0402 3411 DCA I DAAR
0403 2200 ISZ TEL
0404 5201 JMP VERHUIS
Opgave Welke rekenfout wordt hier gemaakt?
Blijven nog de laatste twee typen instructies, die niet het geheugen aanspreken. De instructie IOT (`I/O-transfer', octaal 6xxx) doet invoer of uitvoer. (I/O staat voor Input/Output) De middelste 6 bits vertellen welk apparaat aangesproken wordt, en de laatste drie bits welke opdracht dat apparaat krijgt. De TTY (teletype: toetsenbord en printer met een rol papier) wordt bediend als twee apparaten: 03 voor het toetsenbord en 04 voor de printer. Voorbeeld: `JMS LEESTOETS' wacht tot er een toets wordt aangeslagen, en levert dan de bijbehorende code af. `JMS PRINTSYM' schrijft een symbool op de printer.
0213 0000 LEESTOETS, 0
0214 6031 KSF /AL IETS INGETYPT?
0215 5214 JMP .-1 /NEE, GA TERUG
0216 6036 KRB /JA, LAAD IN AC
0217 5613 JMP I LEESTOETS /EN KEER TERUG
0220 0000 PRINTSYM, 0
0221 6046 TLS /STUUR AC NAAR DE PRINTER, en zet AC=0
0222 6041 TSF /IS DE PRINTER KLAAR?
0223 5222 JMP .-1 /NEE, WACHT
0224 5620 JMP I PRINTSYM /JA. KEER TERUG
Het is natuurlijk heel inefficient om een computer honderdduizend keer te laten vragen: Ben je klaar met deze letter? Mag ik al met de volgende komen? Deze computers werden veel gebruikt bij procesbesturing. Hoogovens had er veel. Dan wil je reageren op invoer van het eerste apparaat dat iets te melden heeft. Om dit probleem te vermijden is de interrupt ingevoerd. Als het IE register op 1 staat, dan wordt gewoon het programma uitgevoerd tot het moment dat voor het eerst een apparaat iets te melden heeft. Op het moment dat een apparaat een verzoek tot interrupt doet wordt IE op 0 gezet, en een `JMS 0' gedaan. Dus de plaats waar het programma bezig was komt in adres 0, en de besturing wordt overgegeven aan de routine die op adres 1 begint. Als die klaar is zet hij de interrupt weer aan en doet `JMP I 0' om terug te keren naar het oude programma. (De instructie ION=6001 die de Interrupt Enable vlag aanzet doet dit met een vertraging van 1 instructie, zodat adres 0 niet bedorven kan worden door de volgende interrupt voor de `JMP I 0' is uitgevoerd.) Een typische interruptroutine ziet er zo uit:
*1
0001 3020 DCA AC /BEWAAR AC
0002 7004 RAL /ROTEER AC,L NAAR LINKS
0003 3021 DCA L /BEWAAR L
0004 6031 KSF /IS DIT EEN KEYBOARD INTERRUPT?
0005 7410 SKP /NEE, SLA VOLGENDE INSTRUCTIE OVER
0006 5422 JMP I KBD /JA, BEHANDEL TOETSENBORD
0007 5024 JMP VERVOLG /SLA DE AUTOINDEX LOCATIES OVER
*20
0020 0000 AC, 0 /PLAATS OM AC TE BEWAREN
0021 0000 L, 0 /PLAATS OM L TE BEWAREN
0022 0600 KBD, DOEKBD /ADRES VAN TOETSENBORDINTERRUPTROUTINE
0023 0700 PRN, DOEPRN /ADRES VAN PRINTERINTERRUPTROUTINE
0024 6041 VERVOLG, TSF /IS DIT EEN PRINTER INTERRUPT?
0025 7410 SKP /NEE
0026 5423 JMP I PRN /JA, BEHANDEL PRINTER
0027 7402 HLT /CATASTROFE! IK WEET NIET WIE HET WAS!
0030 1021 TERUG, TAD L /GRIJP OUDE INHOUD VAN L
0031 7110 CLL RAR /HERSTEL L, AC WORDT 0
0032 1020 TAD AC /HERSTEL AC
0033 6001 ION /IE=1
0034 5400 JMP I 0 /TERUG NAAR HET PROGRAMMA DAT ONDERBROKEN WERD
*600
0600 6036 DOEKBD, KRB /LEES TOETSAANSLAG (EN HAAL INTERRUPTVERZOEK WEG)
0601 3... DCA ERGENS /BERG OP
.... .... ... /DOE DE BIJBEHORENDE ADMINISTRATIE
0637 5030 JMP TERUG /HERSTART ONDERBROKEN PROGRAMMA
*700
.... .... DOEPRN, ...
Tenslotte hebben we nog de laatste groep instructies, met waarde 7xxx octaal. Deze vallen uiteen in twee groepen (met eerste 4 bits 1110 en 1111, respectievelijk) waarbij binnen elke groep microprogrammering optreedt, dwz dat de 8 bits die volgen elk met een actie overeenkomen, en als meerdere van die bits aan staan de bijbehorende acties gecombineerd worden. In de eerste groep zijn er CLA=7200 (zet AC op 0), CLL=7100 (zet L op 0), CMA=7040 (complementeer alle bits van AC), CML=7020 (complementeer L), IAC=7001 (hoog AC met 1 op, complementeer L bij overdracht), RAR=7010 (roteer L,AC cyclisch naar rechts), RAL=7004 (roteer L,AC cyclisch naar links) en 7002 (roteer over twee plaatsen; RTR=7012, RTL=7006) uitgevoerd in deze volgorde. Bijvoorbeeld laadt 7332=CLA CLL CML RTL het getal 2 in AC. De combinatie 7041=CMA IAC heeft de afkorting CIA gekregen; hij vervangt een getal in AC door zijn tegengestelde.
In de tweede groep zijn er testinstructies: sla de volgende instructie over als aan een bepaalde voorwaarde is voldaan. De instructies zijn SMA=7500 (skip on minus [i.e., negative] AC), SZA=7440 (skip on zero AC), SNL=7420 (skip on nonzero link), SKP=7410 (skip), CLA=7600, OSR=7404 (maak AC de bitsgewijs logische OR van AC en de 12 bits die in de schakelaars aan de voorkant staan ingesteld), HLT=7402. Combinaties: LAS=7604 (laad AC met switch register), SNA=7450 (skip on nonzero AC), SPA=7510 (skip on positive AC), SZL=7430 (skip on zero link), kortom, bit 0010 complementeert de test; SMA SZA=7540 (skip on negative or zero AC), kortom SMA, SZA, SNL worden met `of' gecombineerd. Er volgt dat SPA SNA=7550 (skip when AC is positive and nonzero). In deze gevallen heet een getal positief (negatief) als het voorste bit 0 (1) is.
Opgave Waarom bestaat de instructie SZA SZL niet?
Het bovenstaande beschrijft alle PDP8 instructies, behalve de IOT's en de instructies met binair patroon 1111.......1; deze laatste zijn instructies voor een Extended Arithmetic Element dat je er los bij kon kopen; een apparaat dat kon vermenigvuldigen. (Net zoals je bij een Intel 386 een afzonderlijke floating point processor 387 kon kopen.) Heb je dat EAE niet dan doen deze instructies niets.
De oude PDP8 programma's zijn nog goed bruikbaar. De machines bestaan niet meer (misschien nog een enkele in een museum) maar de huidige machines zijn meer dan honderd keer zo snel. Nu je bij het simuleren van een machine op een andere machine een factor honderd verspeelt betekent dit dat een moderne computer met PDP8 simulator de oude programma's ongeveer met de natuurlijke snelheid kan uitvoeren. In het ftp directory is een simulator beschikbaar. Voor een gebruiksaanwijzing zie het voorbeeldfile `simul_use' en de auteursdocumentatie `sim.doc'.
Probleem: Schrijf een programma van minder dan 4096
instructies dat het gehele geheugen op HLT (7402) zet. Randapparaten
mogen niet worden gebruikt.
(Waarom is dit een probleem en geen opgave? Met een eenvoudig loopje
kun je bijna het gehele geheugen moeiteloos op HLT zetten.
Het probleem komt als het programma zichzelf gaat overschrijven...
Meer dan 22 instructies zijn niet nodig.)
Tom Verhoeff verschafte nog twee URLs: (i) Wat meer details over de PDP8 kun je in de FAQ vinden. (ii) Er is ook een java machientje dat PDP8 speelt. (Helaas geen `Load Address' en `Deposit' knoppen. Misschien heeft de auteur nooit zelf een PDP8 gehad.)