, ADDI R3,0,P@l ADDIS R3,R3,P@h ADDI R4,0,Q@l ADDIS R4,R4,Q@h LWZ R6,0(R3) LWZ R5,0(R4) STW R5,0(R3) STW R6,0(R4) .ENDC .MEND De pseudo-instructie .IF bepaalt onder welke voorwaarde de volgende instructies moeten worden vertaald. De voorwaarde DIF gevolgd door twee parameters omsloten door haakjes betekent dat de instructies tussen de .IF en de .ENDC alleen dan moeten worden vertaald als de twee karakterstrings verschillend zijn. Andere mogelijke testen zijn: IDN (Identiek), en voor getalwaarden: EQ (gelijk), NE (niet gelijk), LT (kleiner dan), GT (groter dan), LE (kleiner of gelijk) en GE (groter of gelijk). De macro aanroep EXCHNG X,Y wordt ge¨expandeerd in 2 stappen. Eerst wordt de macro zelf ge¨expandeerd, waarbij P en Q vervangen worden door X en Y. Dit geeft: .IF DIF,<X>,
29
2.3. MACRO’S ADDIS ADDI ADDIS LWZ LWZ STW STW
R3,R3,X@h R4,0,Y@l R4,R4,Y@h R6,0(R3) R5,0(R4) R5,0(R3) R6,0(R4)
.ENDC Daarna wordt de .IF uitgewerkt. Omdat <X> en
R3,0,X@l R3,R3,X@h R4,0,Y@l R4,R4,Y@h R6,0(R3) R5,0(R4) R5,0(R3) R6,0(R4)
De macro-aanroep EXCHNG X,X wordt echter niet ge¨expandeerd, maar uit het programma gehaald zonder er iets voor in de plaats te zetten. Alle typen instructies mogen tussen .IF en .ENDC voorkomen, een andere .IF-.ENDC inbegrepen. Als conditionele expansies genest voorkomen begint de expansie met uitwerking van de buitenste .IF en werkt vandaar uit naar binnen. Als aan de .IF conditie niet voldaan is wordt het gedeelte tot de bijbehorende .ENDC overgeslagen.
2.3.4
Geneste Macro-aanroepen
Omdat een macro-aanroep op dezelfde manier gebruikt wordt als een gewone instructie, valt het te verwachten dat een macro-aanroep mag voorkomen in een andere macro-definitie. De meeste macro-assemblers laten dit dan ook toe. Er zijn ook mogelijkheden voor recursieve macro-aanroepen. We gaan hier niet verder op in.
2.3.5
De Implementatie van een Macro-faciliteit
Om macro’s te kunnen gebruiken moet de assembler zijn uitgebreid met een aantal pseudo-instructies, die correct herkend en verwerkt moeten worden. Dit betekent dat ten eerste de bodies van macro’s moeten worden opgeslagen, en ten tweede dat aanroepen door die bodies moeten worden vervangen, na eventuele parameter-substitutie. Voor het eerste doel kan de assembler een tabel bijhouden met per macro ten minste de naam van de macro en een pointer naar de macro-tekst. Daarnaast moet uiteraard de macro-tekst opgeslagen worden. Eventuele overige velden in de tabel zijn mogelijk, zoals het aantal parameters, de namen van de formele parameters, etc.
30
2.3.6
HOOFDSTUK 2. ASSEMBLER TALEN
Geneste Macro-definities
Een macronaam is slechts een afkorting voor een stuk tekst. Hieruit volgt dat een macrobody elke instructie mag bevatten die buiten de macro legaal is, dus ook de definitie van een nieuwe macro. Geneste macrodefinities vormen echter een probleem voor de assembler. Op het moment dat een macro definitie wordt ontdekt, wordt de body (een stuk tekst) naar een tabel geschreven. Maar komt er binnen deze tekst een nieuwe macrodefinitie voor dan is het niet duidelijk welke .ENDM bij de in behandeling zijnde tekst hoort. Daarom eisen de meeste assemblers dat de .ENDM vergezeld gaat van de naam van de bijbehorende macro. Een macrodefinitie binnen een andere macrodefinitie wordt door de assembler pas ontdekt en verwerkt bij aanroep van de buitenste macro.
Hoofdstuk 3 Linking and Loading 3.1
Introductie
Het draaien van een computerprogramma (geschreven in assemblertaal of in een hogere programmeertaal die wordt gecompileerd) bestaat uit de volgende drie stadia1 : 1. Eerst moet het bronprogramma, geschreven in assemblercode of een hogere taal, door een assembler of compiler vertaald worden in een objectmodule, d.w.z. een (deel van een) programma in machinecode. 2. Daarna moeten objectmodulen samengevoegd worden tot een objectprogramma. 3. Tenslotte moet het objectprogramma in het hoofdgeheugen geladen en vervolgens uitgevoerd worden. Voorlopig gaan we er daarbij van uit dat we te maken hebben met een enkele fysieke adresruimte. Later zullen we zien dat het probleem van relocatie van programmatuur elegant kan worden opgelost door een zogeheten virtueel geheugen (zie 5.7). Als een objectprogramma bij het assembleren of compileren op het achtergrondgeheugen, b.v. een schijf, is gezet, is er een speciaal programma nodig om het in het hoofdgeheugen te laden. Zo’n programma wordt een lader (Engels: loader) genoemd. De volgende typen loaders worden behandeld: 1. De absolute loader; 2. De relocating loader; 3. De linking loader. waarbij de geboden mogelijkheden, en daardoor de complexiteit van de loader, steeds verder toenemen. 1
Zie ook paragraaf 2.6.2 van [Hamacher02]
31
32
HOOFDSTUK 3. LINKING AND LOADING
Een bronprogramma bestaat vaak uit een aantal onafhankelijk van elkaar geschreven gedeelten. Zo’n gedeelte wordt een bronmodule genoemd en kan het hoofdprogramma, e´ e´ n of meer subroutines, en/of declaraties van constanten en variabelen bevatten. Verschillende bronmodulen kunnen in verschillende programmeertalen geschreven zijn. De bronmodulen worden onafhankelijk van elkaar geassembleerd of gecompileerd. Hierbij wordt een bronmodule omgezet in een objectmodule, die op het achtergrondgeheugen wordt bewaard. Als een bepaalde module gewijzigd moet worden, hoeft alleen de betreffende bronmodule opnieuw geassembleerd of gecompileerd te worden. Voordat een programma kan worden geladen en uitgevoerd, moeten de samenstellende objectmodulen worden samengevoegd tot een objectprogramma. Dit wordt gedaan door een programma dat een linker wordt genoemd. Naast de linking loader, waarin de functies van een linker en een loader zijn samengevoegd, worden nog de volgende typen linkers behandeld: 1. De linkage editor; 2. De dynamische linker.
3.2
Compile, Load and Go
De eenvoudigste manier om het objectprogramma in het hoofdgeheugen te laden is om de assembler of compiler de machinecode rechtstreeks in een door het operating system toegewezen gebied van dit geheugen te laten zetten. Zodra het hele bronprogramma naar machinecode is omgezet, wordt er naar de eerste instructie van het objectprogramma gesprongen als ware het een subroutine. Dit wordt aangeduid met assemble, load and go of compile, load and go. Deze vorm van laden van objectprogramma’s werd in de begintijd van de computer erg veel gebruikt. Tegenwoordig wordt het nog gebruikt bij programma-ontwikkeling of bij kleine programma’s die slechts eenmaal geassembleerd of gecompileerd en daarna gedraaid worden. De belangrijkste nadelen van deze vorm van laden zijn: • Programma’s die meerdere keren gebruikt worden moeten elke keer opnieuw geassembleerd of gecompileerd worden, hetgeen veel extra computertijd kost; • Het is erg moeilijk verschillende objectmodulen samen te voegen, i.h.b. wanneer de bronmodulen in verschillende talen zijn geschreven. Het eerste nadeel kan worden ondervangen door het objectprogramma ook op een achtergrondgeheugen te zetten, waar het meerdere keren vanaf gehaald kan worden om te worden uitgevoerd. Hiervoor is een loader nodig, die het objectprogramma in het hoofdgeheugen laadt.
3.3
De Absolute Loader
Bij een absolute loader (zie Figuur 3.1) is de vorm van een objectprogramma dat op het achtergrondgeheugen staat exact de vorm waarin het in het hoofdgeheugen wordt geladen. Het laden van
33
3.3. DE ABSOLUTE LOADER
een objectprogramma bestaat slechts uit het van het achtergrondgeheugen naar het hoofdgeheugen brengen, waarbij meestal een aantal controles wordt uitgevoerd om de integriteit van het ingelezene te controleren. Absolute loaders worden nog toegepast bij het ontwikkelen van programmatuur ten behoeve van het verrichten van vaste functies in in apparatuur ingebouwde microprocessoren, waarbij de programmatuur in een dood geheugen (ROM), en daardoor dus op een vaste plaats, geladen wordt. Hoofdgeheugen
object-
module 1
bronmodule 1
-
bronmodule 2
-
object-
module 1
vertaler
?
absolute loader @ 6
vertaler @
@ R @
@ R @
objectmodule 2
objectmodule 2
Figuur 3.1: De absolute loader. De belangrijkste nadelen van deze vorm van laden zijn: • Alle in een objectprogramma voorkomende adressen van operanden en adressen in spronginstructies moeten al bij het assembleren of compileren bekend zijn, en het objectprogramma moet altijd in het dan vastgelegde gebied van het hoofdgeheugen worden geladen, omdat de loader geen faciliteiten heeft om adressen aan te passen aan de plaats waar het objectprogramma in het hoofdgeheugen geladen wordt (de adressen in het objectprogramma zijn echte machineadressen of absolute adressen). Dit is een belangrijk nadeel in een computersysteem waarin verschillende objectprogramma’s tegelijkertijd in het hoofdgeheugen worden geladen, zoals in een computersysteem met meer gebruikers achter terminals, waarbij de plaats waar het objectprogramma geladen kan worden niet van te voren vastligt; • Als een programma uit meerdere modulen bestaat, moet bij het assembleren of compileren van een bepaalde module voor een adres uit een andere module eveneens het absolute
34
HOOFDSTUK 3. LINKING AND LOADING adres worden genomen (als b.v. een bepaalde module een subroutine uit een andere module aanroept, moet bij het assembleren of compileren in de subroutine-aanroepinstructie het absolute adres van deze subroutine worden gezet). Er moet dan ook voor gezorgd worden dat elke objectmodule van het programma een afzonderlijk gebied in het hoofdgeheugen krijgt toegewezen.
3.4
De Relocating Loader
Omdat het ongewenst is dat al bij het assembleren of compileren het adres wordt vastgelegd van de plaats in het hoofdgeheugen waar een objectprogramma geladen moet worden, is het beter een objectprogramma onafhankelijk van deze plaats te maken. Een relocating loader maakt dit mogelijk (zie Figuur 3.2). Hoofdgeheugen
bronmodule
- vertaler
- reloceerbare
obj. code
- relocating
loader
- coreimage
code
Figuur 3.2: De relocating loader. Een objectprogramma wordt reloceerbaar genoemd wanneer het op een willekeurige plaats in het hoofdgeheugen kan worden geladen om te worden uitgevoerd. Zo’n objectprogramma verschilt in twee opzichten van een objectprogramma in absolute vorm: • Adressen zijn relatief t.o.v. het begin van het objectprogramma, i.p.v. absoluut; • Aan het objectprogramma is relocatie-informatie toegevoegd, die aangeeft welke adresvelden in instructies veranderd moeten worden als het programma geladen wordt. De relocatie-informatie wordt gewoonlijk op e´ e´ n van de volgende manieren door de assembler of compiler aan het objectprogramma toegevoegd: • Aan elke machine-instructie wordt een relocatie-bit toegevoegd, dat aangeeft of het/de adresveld(en) in de instructie wel of niet veranderd moet(en) worden bij het laden;
3.5. LINKEN, LIBRARIES EN DE LINKING LOADER
35
• Alle relocatie-informatie wordt in een relocatie-tabel gezet, die een verwijzing bevat naar elke machine-instructie waarin het/de adresveld(en) veranderd moet(en) worden bij het laden. Een relocating loader zet m.b.v. de relocatie-informatie bij het laden van een reloceerbaar objectprogramma in het hoofdgeheugen alle relatieve adressen in het objectprogramma om in absolute adressen. Dit omzetten houdt in dat bij alle relatieve adressen het adres waar het begin van het objectprogramma wordt geladen wordt opgeteld. Het programma moet, nadat het geladen is, gedurende de gehele uitvoering ervan wel op dezelfde plaats in het hoofdgeheugen blijven staan. Nu er een onderscheid is gemaakt tussen de code die door de assembler of compiler wordt geproduceerd en de code die door de relocating loader in het hoofdgeheugen wordt geladen, gebruiken we hiervoor verschillende termen. De eerste blijven we objectcode noemen, de tweede noemen we core-image-code, hetgeen aangeeft dat het code is zoals die staat in het hoofdgeheugen, dat vroeger uit magnetische kernen (Engels: core) bestond. De assembler of compiler produceert een objectprogramma in de vorm van een file, waarin relocatie-informatie is opgenomen, en de relocating loader gebruikt de relocatie-informatie om een uitvoerbaar core-image-programma in het hoofdgeheugen te laden. De problemen bij het samenvoegen van verschillende objectmodulen tot een objectprogramma zijn nog niet opgelost bij een relocating loader. Dit leidde tot de ontwikkeling van linking loaders.
3.5
Linken, Libraries en de Linking Loader
Het samenvoegen van een aantal objectmodulen tot een enkel objectprogramma wordt linking genoemd. Een objectmodule is het resultaat van het assembleren of compileren van een bronmodule. Iedere grootheid in een objectmodule is van e´ e´ n van de volgende soorten: • Absolute grootheden, d.w.z. vaste waarden, die onafhankelijk zijn van de plaats in het hoofdgeheugen waar de objectmodule wordt geladen en daarom geen problemen veroorzaken; • Relatieve grootheden, d.w.z. adressen waarvan de waarden relatief t.o.v. het begin van de objectmodule bekend zijn en die, voordat het programma uitgevoerd kan worden, een absolute waarde gegeven moet worden, hetgeen gedaan kan worden zodra het adres van het begin van de module bekend is; • Externe referenties, d.w.z. verwijzingen naar objecten die in andere modulen staan (b.v. de aanroep van een subroutine uit een andere module) en waarvan de waarde pas bepaald kan worden zodra alle objectmodulen bekend zijn. Een objectmodule bestaat dan ook uit de volgende onderdelen (zie Figuur 3.3): • De lengten van de onderdelen, de naam, en het main entry point (de locatie waar executie moet beginnen) van de objectmodule;
36
HOOFDSTUK 3. LINKING AND LOADING • Een blok code en data; • De relocatie-tabel met relocatie-informatie; • Een tabel met voor alle externe referenties de symbolische naam van de referentie, b.v. de naam van de aangeroepen subroutine, en de relatieve adressen van plaatsen in het objectmodule waar de referentie voorkomt, b.v. de plaatsen waar een aanroep van de betreffende subroutine staat; • Een tabel met voor alle entry points, d.w.z. de objecten die in een module staan en in andere modulen gebruikt mogen worden, de naam en het relatieve adres binnen de objectmodule. Als een module b.v. een subroutine bevat die in andere modulen gebruikt mag worden, bevat de tabel de naam van de subroutine en het relatieve adres binnen de objectmodule waar de subroutine begint.
Naam en lengte Code en Data Relocatie-Tabel Externe-referentie Tabel Entry-point Tabel Figuur 3.3: Een objectmodule. Het linken van een aantal objectmodulen wordt gewoonlijk in twee fasen gedaan; in beide worden alle objectmodulen gelezen. De fasen behelzen de volgende activiteiten (vgl. two-pass assemblers): • In de eerste fase worden alle objectmodulen gelezen om een tabel met de namen en lengten van de objectmodulen en een naamtabel met alle externe referenties en entry points te maken. Vervolgens wordt gecontroleerd of voor alle externe referenties het ermee overeenkomende entry point is gedeclareerd, wordt aan elke objectmodule een adres relatief t.o.v. het eerste objectmodule toegekend, en worden de adressen van de entry points hierbij aangepast. • In de tweede fase worden alle objectmodulen opnieuw gelezen, wordt bij alle adressen in een objectmodule het relatieve adres van de objectmodule t.o.v. de eerste objectmodule opgeteld, en worden alle externe referenties ingevuld m.b.v. de informatie over de entry points in de naamtabel.
37
3.5. LINKEN, LIBRARIES EN DE LINKING LOADER
In Figuur 3.4 wordt een voorbeeld gegeven van het koppelen van twee objectmodulen tot een objectmodule. De twee objectmodulen hebben de structuur zoals weergegeven in Figuur 3.3. Alle adressen zijn oktaal. Het tweede module zal na linken op adress 1000 starten, en de aanroep van de sinus-routine op adres 20 van het eerste module wordt een aanroep naar adres 1300 na linken. Angle Naam Lengte 1000 0 20 aanroep van sin 200 70 776 200 sin 20
1300
0 20
70
200
1200
1100
start van sin
1300 1376
@ @ R @
Linken Naam Sinus-module Lengte 400 0 100 200 300 start van sin 376 100
-
sin 300
Figuur 3.4: Het koppelen van twee objectmodulen (alle adressen zijn oktaal). Een groot gedeelte van de te linken objectmodulen komt meestal uit e´ e´ n of meer objectbibliotheken (Engels: object libraries). Een bibliotheek is een verzameling modulen die beschikbaar is gesteld om het programmeren te vereenvoudigen. Voorbeelden van bibliotheken zijn: • Invoer- en uitvoerbibliotheken, met subroutines voor invoer en uitvoer van gegevens; • Systeembibliotheken, met allerlei subroutines om het gebruik van het operating system te vereenvoudigen;
38
HOOFDSTUK 3. LINKING AND LOADING • Numerieke bibliotheken, met allerlei subroutines voor numerieke functies, zoals sinus en logaritme.
Bibliotheken worden vaak verzorgd door de leverancier van de computer of de locale systeemprogrammeurs, maar programmeurs kunnen ook hun eigen bibliotheken hebben. Bepaalde modulen uit bibliotheken worden vaak automatisch aan een programma gelinkt, zonder dat de programmeur dit expliciet hoeft te specificeren. Een linking loader verzorgt zowel het linken van een aantal objectmodulen als het laden in het hoofdgeheugen van het daarbij geproduceerde objectprogramma. Bij het laden worden, m.b.v. de relocatie informatie, de adressen aangepast aan de plaats in het hoofdgeheugen.
3.6
De Linkage Editor
De in 3.5 beschreven linking loader heeft als nadeel dat de linking van een aantal objectmodulen tot een objectprogramma elke keer herhaald moet worden wanneer het programma wordt uitgevoerd, hetgeen onnodig veel computertijd vergt. Dit kan voorkomen worden door de linkfase en de laadfase te scheiden. Een programma dat alleen linking verzorgt wordt een linkage editor genoemd. Een linkage editor produceert een objectprogramma dat op het achtergrondgeheugen wordt gezet. Een loader haalt dit objectprogramma van het achtergrondgeheugen en laadt het in het hoofdgeheugen. Daarbij doen zich twee mogelijkheden voor: • Het objectprogramma bevat geen relocatie-informatie meer, zodat van een absolute loader gebruik kan worden gemaakt; • Het objectprogramma bevat nog wel relocatie-informatie, zodat voor het laden een relocating loader moet worden gebruikt, waarbij m.b.v. de relocatie-informatie de adresreferenties worden aangepast aan de plaats in het hoofdgeheugen.
3.7
Relocatie via Virtuele Adressering
De tot nu toe behandelde methode om relocatie te plegen, namelijk door voorafgaande aan of tijdens het laadproces de adresreferenties aan te passen aan de plaats waar het programma geladen gaat worden, heeft twee nadelen: 1. De relocatie kost het relocerende proces veel werk; 2. Na het reloceren tijdens of voorafgaande aan het laden kan het programma in het hoofdgeheugen niet meer verschoven worden, hetgeen met name lastig is in een multi-user omgeving. Zoals in Hoofdstuk 5 behandeld zal worden, is het mogelijk een computer te voorzien van de mogelijkheid de relocatie niet voorafgaande aan de programma-executie te doen plaatsvinden, maar in plaats daarvan tijdens programma-executie, waarbij gebruik gemaakt wordt van extra
3.8. HET TIJDSTIP VAN BINDING
39
hardware-voorzieningen in de vorm van adresvertalingsmechanismen. De simpelste oplossing is om te werken met een zogeheten relocatie- en een lengteregister. Dit zijn speciale registers die niet worden beheerd door het gebruikersprogramma zelf, maar door (een onderdeel van) het operating system dat, zoals we in Hoofdstuk 4 zullen zien, opgevat kan worden als een programmatisch uitgevoerde versie van de operator of de beheerder van het computersysteem. Met betrekking tot het reloceren en laden is voor ons daarbij interessant dat de linker in dit geval een objectprogramma kan afleveren dat gereloceerd kan worden door het invullen in het relocatieregister in de CPU van het beginadres waar het programma geladen wordt, zonder dat echter de adresreferenties in het programma zelf behoeven te worden aangepast. Hoewel het relocatieregister toelaat het programma zonder veel moeite in het geheugen te verplaatsen geldt als nadeel dat steeds het gehele programma in het geheugen aanwezig moet zijn, zodat de in de voorgaande paragraaf genoemde problemen nog niet zijn opgelost. Dit bezwaar kan men ondervangen door gebruik te maken van paginering, waarbij delen van het programma (pagina’s) op in het hoofdgeheugen beschikbare plaatsen (page frames) geladen kunnen worden en het operating system bijhoudt (in z.g. page tables) op welke fysieke plaats in het hoofdgeheugen de pagina zich bevindt. De gebruiker hoeft zich niet meer om relocatie te bekommeren, maar kan denkbeeldig gebruik maken van een adresruimte die altijd vanaf adres 0 beschikbaar is (een virtuele adresruimte, dit is ook al het geval bij gebruik van een relocatie-register), en die bovendien groter kan zijn dan het hoofdgeheugen. Virtueel geheugen wordt verder behandeld in [H], 5.7.
3.8
Het Tijdstip van Binding
Het proces van het relateren van symbolische namen in een programma in assemblertaal of in een hogere programmeertaal aan de uiteindelijke re¨ele machine-adressen gedurende de executie van het in machine-code omgezette programma heet binding. Binding is feitelijk een tweetraps procedure: eerst worden symbolische namen gebonden aan virtuele adressen, en vervolgens worden die virtuele adressen gebonden aan adressen in het hoofdgeheugen. Het tijdstip waarop die binding plaatsvindt kan verschillend zijn: • Tijdens het schrijven van het programma, bijvoorbeeld als absolute adressering gebruikt wordt om een randapparaat-register te bereiken; • Bij het vertalen van het programma, als een symbolisch adres wordt gekoppeld aan een absolute (niet-reloceerbare) waarde doordat de assembler absolute code genereert; • Tijdens de linkage van het programma door een linker die een niet-reloceerbaar objectprogramma aflevert, waarbij door het samenvoegen van de modulen absolute adressen worden gegenereerd voor de in verschillende modules gedefinieerde symbolische namen; • Bij het laden van het programma, bijvoorbeeld als van een relocating loader gebruik wordt gemaakt;
40
HOOFDSTUK 3. LINKING AND LOADING • Wanneer tijdens de programma-executie het fysieke adres wordt bepaald als de som van het virtuele adres en de inhoud van een relocatieregister (ofwel, bij paginering, de som van het door de adresvertalingshardware geleverde fysieke pagina-frame-adres en het adresdeel binnen die pagina, zie 5.7).
3.9
De Dynamische Linker
Bij de tot nu toe beschreven vorm van linken worden alle objectmodulen die eventueel gebruikt worden samengevoegd tot een objectprogramma, voordat de uitvoering van het programma begint. Veel programma’s bevatten echter subroutines die alleen in uitzonderlijke gevallen worden aangeroepen, b.v. subroutines voor het afhandelen van zelden voorkomende fouten. Een flexibeler vorm is dan ook om een subroutine pas te linken op het moment dat deze voor het eerst wordt aangeroepen. Een linker die dit mogelijk maakt wordt een dynamische linker genoemd. De volgende beschrijving schetst een manier om dynamisch linken te implementeren. Met elk objectprogramma dat gedeeltelijk of helemaal in het hoofdgeheugen is geladen, is een linkage tabel geassocieerd. Deze tabel bevat voor elke eventueel aan te roepen subroutine een plaats voor het adres van de subroutine en de naam van de subroutine. Alle aanroepen van een subroutine moeten indirect via de linkage tabel plaatsvinden, m.a.w. het adres van een subroutine moet uit de linkage tabel gehaald worden. Voordat een programma gaat draaien, wordt op alle plaatsen in de linkage tabel voor subroutine-adressen het adres van de linker gezet. De eerste keer dat een subroutine wordt aangeroepen wordt dan automatisch de linker geactiveerd en niet de subroutine. De linker zoekt vervolgens uit waar de subroutine zich op het achtergrondgeheugen bevindt, bepaalt de plaats in het hoofdgeheugen waar de subroutine geladen wordt, verzorgt het laden en vult het adres van de subroutine in de linkage tabel in, waarna de subroutine wordt uitgevoerd. Bij eventuele volgende aanroepen van de subroutine, die weer indirect via de linkage tabel moeten plaatsvinden, wordt meteen de subroutine zelf uitgevoerd. De linker wordt dus alleen bij de eerste aanroep van een subroutine geactiveerd.
Hoofdstuk 4 Taalniveaus 4.1
Programmatransformaties
Onder de term programmatransformaties1 worden allerlei omzettingen van de vorm van een programma begrepen die zich binnen een computersysteem afspelen. In eerste instantie wordt gedacht aan transformaties die door een compiler of een assembler worden uitgevoerd en die direct door de gebruiker worden ge¨ınitieerd met een commando. Daarnaast vinden er transformaties plaats waar de gebruiker (soms) geen weet van heeft, zoals de omzetting door een compiler van een programma in een hogere programmeertaal naar een programma in een tussencode. Programmatransformaties zijn noodzakelijk om het mogelijk te maken dat programma’s geschreven in een voor mensen hanteerbare programmeertaal uitgevoerd worden door een computer met een architectuur die gericht is op het uitvoeren van programma’s in machinecode. Essentieel hierbij is dat de functie van het programma dezelfde blijft. Er zijn twee basis-methoden om programma’s om te zetten. Een programmavertaler vertaalt een programma in een gegeven taal eerst in zijn geheel naar een programma in een andere taal, waarbij de functie van het programma gehandhaafd blijft. Vervolgens kan het resulterende programma worden uitgevoerd, als deze andere taal bijvoorbeeld de machinetaal van een computer is. Een programma-interpretator analyseert en executeert een programma opdracht voor opdracht. In dit hoofdstuk wordt eerst ingegaan op deze twee soorten van programmatransformatie. Vervolgens wordt aandacht besteed aan het verschil tussen en de voor- en nadelen van vertalen en interpreteren. Daarna beschouwen we computers als opgebouwd uit verschillende niveaus. Tenslotte wordt de structuur van compilers behandeld.
4.1.1
Soorten Vertalers
Het doel van een vertaling is meestal het verkrijgen van een programma dat van een syntactisch en semantisch lager niveau is, waardoor executie van het verkregen programma al dan niet direct door de hardware mogelijk is. Mogelijke vertalingen zijn: 1
Additionele stof: Wordt niet behandeld in [Hamacher02]
41
42
HOOFDSTUK 4. TAALNIVEAUS • Vertaling van een hoger-niveau taal als Pascal of Modula-2 naar de machinetaal van een computer (compilatie); • Vertaling van een hoger-niveau taal naar de assemblertaal van een computer (compilatie). Het nut hiervan is o.a. dat bij het opsporen van fouten bij executie er een leesbare versie is van het te executeren programma; • Assemblage: het vertalen van een assemblerprogramma naar machine-taal (een transformatie die bij het vorige punt natuurlijk nog moet worden gebruikt); • Vertaling van een hoger-niveau taal naar een tussentaal. Hierbij wordt b.v. vertaald naar een ’universele’ machinetaal, d.w.z. de machinetaal van een ge¨ıdealiseerde CPU die veel lijkt op bestaande machinetalen. Het nut hiervan is om een zo groot mogelijk deel van een compiler voor een taal machine-onafhankelijk te laten zijn; • Vertaling van tussencode naar machinecode. Hierboven dient er voor iedere specifieke computer nog een back-end te zijn die de vertaling naar machine-code verzorgt.
4.1.2
Soorten Interpretatoren
We onderscheiden de volgende soorten interpretatoren (zie Figuur 4.1): 1. Hardware-interpretator. Indien de doelcode van een vertaler overeenkomt met de machinecode van bestaande hardware, dan kan deze code direct door de computer, die een hardware-interpretator is, worden uitgevoerd. Hierbij verwijst de programmateller (PC) naar de volgende uit te voeren machine-instructie. 2. Software-interpretator. Indien voor een taal geen vertaler bestaat of de doelcode van een vertaler niet overeenkomt met de machinecode moeten we een software-interpretator gebruiken: een op de computer uitvoerbaar programma dat de geproduceerde doelcode verwerkt en de werking van de bijbehorende computer nabootst. Soms wordt een software-interpretator ook gebruikt in gevallen waarin we deze nabootsing in ieder geval willen kunnen benutten, bijvoorbeeld om de voortgang van het programma volledig te kunnen beheersen, zelfs indien de hardware het programma direct zou kunnen executeren. De gesimuleerde programmateller (IPC) verwijst naar de uit te voeren instructie in het uit te voeren (= te interpreteren) programma. Dit uitvoeren gebeurt door een interpreteerprogramma dat meestal ook in het interne geheugen staat (soms ook in een read-only memory (ROM)). De ’werkelijke’ (hardware- )programmateller (PC) verwijst naar instructies in dat interpreteerprogramma. De hoofdinterpretatie-cyclus van een software-interpretator is (vgl. de fetch-decode-execute cyclus in een CPU): (a) Haal de instructie op waarnaar de gesimuleerde programmateller verwijst; (b) Verhoog de programmateller;
43
4.1. PROGRAMMATRANSFORMATIES (c) Decodeer de instructie; (d) Bepaal de adres(sen) van de operand(en); (e) Voer de operatie uit.
Een ge¨eigende structuur voor zo’n interpretator is een hoofdprogramma met deze hoofdinterpretatiecyclus, en daarnaast voor elk type instructie een subroutine. Deze subroutines kunnen elkaar weer aanroepen.
Voorbeeld 1 Machine-code wordt in veel processoren door micro-code ge¨ınterpreteerd. Soms wordt micro-code firmware genoemd, maar zeker als het control store beschreven kan worden, is hier in feite sprake van software-interpretatie.
Voorbeeld 2 Er zijn hogere programmeertalen die door software worden ge¨ınterpreteerd. Een voorbeeld is Java.
(I)PC
IPC -
programma
-
-
programma
PC
PC
PC -
programma
interpretator
- run time
system/ operating system
Figuur 4.1: Hardware, Software, en Hardware/Software Interpretatie.
3. Hardware/software-interpretator. In dit geval is van een combinatie van hardware- en software-interpretatie sprake (en van een hybride interpretator). Sommige instructies kunnen direct door de hardware worden uitgevoerd, terwijl voor andere (vaak complexe) instructies, die niet direct door de hardware kunnen worden uitgevoerd, de hulp van software moet worden ingeroepen. Er is hier op verschillende momenten sprake van e´ e´ n of twee programmatellers:
44
HOOFDSTUK 4. TAALNIVEAUS (a) Zolang instructies in het uit te voeren programma direct door de hardware kunnen uitgevoerd, wijst de programmateller PC naar die instructies; (b) Wanneer er in het uit te voeren programma een instructie voorkomt die door een softwareroutine moet worden uitgevoerd, is er een IPC in het programma, wijzend naar die instructie, en een programmateller PC in de routine die die instructie interpreteert. De IPC ’staat stil’ (d.w.z. verandert niet van waarde) zolang die routine wordt uitgevoerd. Voorbeeld 1 In veel typen CPUs worden floating-point bewerkingen niet direct door de hardware uitgevoerd. In oudere computers bestonden er wel vaak machine-instructies voor dergelijke operaties, maar bij het uitvoeren trad er een trap op, werd herkend om welke operatie het ging, en werd een machine-code routine uitgevoerd die het effect had alsof de instructie wel direct door de hardware was uitgevoerd. De verzameling van dergelijke routines die de executie van (gecompileerde) programma’s in hoger-niveau talen ondersteunen en met zo’n programma worden meegeladen, wordt wel het run-time system genoemd. Voorbeeld 2 Programma’s in machine-code bestaan voornamelijk uit instructies die direct door de hardware kunnen worden uitgevoerd. Voor o.a. I/O-instructies wordt de hulp van het operating system ingeroepen (d.m.v. system calls). Deze instructies, die wel operating-system instructies worden genoemd (zie 4.2), worden door software ge¨ınterpreteerd, en wel door operatingsystem routines, die op hun beurt uiteraard weer uit machine-instructies bestaan die direct door de hardware worden uitgevoerd (of door het microprogramma worden ge¨ınterpreteerd).
4.1.3
Vergelijking van Interpreteren en Compileren
Bij verwerking van programma’s in hogere programmeertalen heeft interpretatie als voordelen t.o.v. compilatie: • Er is minder ruimte nodig voor programma-opslag. Veelal is de broncode van ge¨ınterpreteerde talen veel compacter dan die bij gecompileerde talen. Daarnaast moet bij compilatie ook het objectmodule opgeslagen worden; • Interpreteren biedt een werkwijze waarbij de gebruiker het idee krijgt met een computer te maken te hebben die zijn programma direct uitvoert. Er is geen aparte vertaalslag noodzakelijk. Er kan op eenvoudige wijze van de executie-fase naar de correctie-fase worden overgestapt. Bovendien is het mogelijk om symbolisch te debuggen (’ontluizen’, d.w.z. fouten te zoeken) door op brontaal-niveau waarden van variabelen te inspecteren, op te vragen, te veranderen, etc.
4.1. PROGRAMMATRANSFORMATIES
45
Als voordelen van een compiler gelden: • De executie van een programma verloopt sneller. De o¨ verhead”van een interpretator (o.a. het steeds opnieuw analyseren van een statement, ook al wordt deze vele malen achtereen uitgevoerd) wordt immers vermeden; • Een aantal controles op de goede werking van het programma kan reeds tijdens het compileren worden uitgevoerd, zodat tijdens het draaien slechts de hoogst noodzakelijke controles behoeven te worden uitgevoerd. Bij de analyse van statements in een interpretator moeten deze controles aldoor opnieuw worden uitgevoerd; • De doelcode is op de machine toegesneden en door optimalisaties vaak nog effici¨enter te maken, ten koste van een ingewikkelder compilatieproces. Zoals reeds aangegeven, geeft het gebruik van interpretatieve verwerking de mogelijkheid om op taalniveau te debuggen, waarmee fouten in het algemeen gemakkelijk op te sporen en te herstellen zijn. Bij gecompileerde talen moet het debuggen meestal op assemblercode- of zelfs machinecode-niveau gebeuren, waardoor de programmeur met twee taalniveaus te maken krijgt. Dit kan slechts tot succes leiden als het verband tussen de twee niveaus duidelijk is en de programmeur beide niveaus begrijpt. Is dit niet het geval, dan moeten maatregelen zoals invoegen van print-statements op taalniveau uitgevoerd worden om meer inzicht te verkrijgen in de waarden van verschillende variabelen. In de testfase van een programma is snel compileren belangrijker dan snel executeren. Later, als het programma uitgetest is en er geen fouten meer gevonden worden, is het aan te bevelen het programma te vertalen met de compiler die de snelste code aflevert, waarbij dan de eenmalig langere compileertijd geen rol speelt. De executie van ge¨ınterpreteerde code is ruwweg een factor honderd langzamer dan de executie van een gecompileerd programma. Hoe dichter het niveau van de ge¨ınterpreteerde code het machinecode niveau benadert, hoe kleiner die factor zal zijn. Vaak zal echter het werken met software-interpretatie niet mogelijk zijn, b.v. voor real-time toepassingen, waarbij bepaalde acties gegarandeerd binnen bepaalde tijdsgrenzen voltooid moeten zijn (b.v. bij procesbesturing). Het gebruik van software-interpretatoren in een debugging situatie is verstandig; het gebruik ervan in een productie-omgeving is af te raden.
4.1.4
Just-in-time compilers
Een nieuwe hybriede vorm is de Just-in-time compiler (JIT). Deze zijn door het gebruik van de taal Java sterk in opkomst. Oorspronkelijk werd Java uitsluitend ge¨ınterpreteerd. Vanwege de wens naar een hogere executiesnelheid, worden delen van het Java programma vlak voor de executie gecompileerd. Het betreft hier delen waarvan de executietijden lang zijn en waarbij compilatie een snelheidsvoordeel oplevert. Just-in-time compilatie kan ook op run-time plaatsvinden. Als de interpretator er achter komt dat een bepaalde method-call veel executietijd neemt, dan kan alsnog een gecompileerde versie worden aangemaakt.
46
HOOFDSTUK 4. TAALNIVEAUS
4.1.5
Simuleren en Emuleren
Op deze plaats is het zinvol om twee andere begrippen te introduceren. Onder een simulator (emulator) verstaan we programmatuur (apparatuur) die een bepaalde functie nabootst. De functie kan oorspronkelijk zowel in hardware als in software zijn gerealiseerd. De simulatie (emulatie) kan op twee niveaus worden uitgevoerd: 1. Op het niveau van de architectuur. Op dit niveau wordt het effect van de functie nagebootst, zonder er op te letten hoe dat effect wordt bereikt. Het gaat er hierbij om dat wat de functie doet te imiteren; 2. Op het niveau van de implementatie. Nu wordt ook rekening gehouden met de manier waarop de functie is ge¨ımplementeerd. Hierbij wordt geprobeerd zo zorgvuldig mogelijk na te bootsen hoe de bijbehorende architectuur is ge¨ımplementeerd. De realisatie van de nabootsing kan op twee manieren plaatsvinden: 1. Op programmatuurniveau, dan spreken we van simulatie. 2. Op hardware of firmware (microprogrammerings-)niveau, dan spreken we van emulatie. Voorbeelden. 1. Een computer X kan op een computer Y worden gesimuleerd, d.w.z. op computer Y is in een geschikte taal een simulatieprogramma geschreven dat de werking van computer X nabootst. Als het voldoende is dat het effect van elke instructie van X wordt nagebootst, spreken we van een simulatie van de architectuur. Soms is het echter nodig dat elk intern register zoals dat in de hardware van X aanwezig is, z’n analogon krijgt in het simulatieprogramma. Dan spreken we van een simulatie op implementatieniveau. Een voorbeeld hiervan is de PowerPC simulator geschreven in C die bij het practicum gebruikt wordt. 2. Als een door software te interpreteren brontaal wordt beschouwd als de ”machinetaal”voor een hoog-niveau computer, dan is de software-interpretator een simulator van die computer. 3. Als Y een microprogrammeerbare computer is, dan kan X worden ge¨emuleerd op Y door een speciaal microprogramma te construeren dat de werking van X nabootst. 4. Tenslotte kunnen we ook hardware maken om een functie na te bootsen.
4.1.6
Compatibiliteit
Er zijn verschillende verschijningsvormen van de definitie van een taal, die gedeeltelijk samenhangen met het niveau. Een machinetaal wordt veelal vastgelegd in een reference manual dat precies beschrijft wat het effect is van de executie van iedere instructie (in een stijl als in App. B van [H]). Bij hogere programmeertalen zijn er veelal verschillende verschijningsvormen:
4.2. TAALNIVEAUS
47
1. De formele taaldefinitie, die meestal in een of ander defini¨erend rapport is vastgelegd; 2. De standaard taaldefinitie zoals die is vastgelegd door een internationale commissie voor standaardisatie (b.v. door ISO = International Standards Organization), en waaraan de compilers voor de betreffende taal moeten voldoen; 3. De taalimplementatie zoals die op een bepaald merk computer voor een bepaald operating system is gedefinieerd. Een goede implementatie houdt zich aan de standaard of geeft tenminste de restricties en/of uitbreidingen t.o.v. de standaard aan. Door deze verschillende vormen en implementaties zijn er veelal afwijkingen. Bij talen verstaat men onder compatibiliteit (oftewel overeenstemming) de mate waarin taalimplementaties met elkaar of met een standaard overeenkomen, d.w.z. in hoeverre een programma bij verwerking m.b.v. de ene implementatie dezelfde resultaten bij uitvoering oplevert als bij verwerking m.b.v. de andere implementatie. Hierbij moet men vooral denken aan: 1. Het machine-niveau. Dit betreft compatibiliteit van machine-talen en computersystemen, veelal van computers in een serie van een fabrikant. Het ene model heet dan compatibel met het andere als programmatuur in machine-code van de e´ e´ n zonder aanpassingen ook draait op de ander. We spreken wel van upwards compatible (naar boven overeenkomstig) indien een nieuwe implementatie minstens alle faciliteiten bevat van de oudere implementatie. Programma’s geschreven voor de vorige implementatie zijn dan nog steeds te verwerken. 2. Het niveau van hogere programmeertalen. Compatibiliteit is hier met name belangrijk indien we ons niet beperken tot een enkel computersysteem. Indien we een programma willen construeren dat op verschillende systemen moet kunnen draaien, dan speelt de compatibiliteit van de taalimplementaties voor de overdraagbaarheid (portabiliteit) van dat programma een grote rol. Volledige compatibiliteit is veelal een illusie. Er zijn altijd details van het computersysteem die op het niveau van de hogere programmeertaal niet te verdoezelen zijn, al was het maar het waardenbereik van gehele getallen, dat uiteraard samenhangt met de woordlengte. 3. Het niveau van het operating system (zie ook 4.2). Men spreekt van compatibele operating systems indien de system calls (zoals aangeroepen vanuit een hogere programmeertaal) een identiek effect hebben. Vanwege het hier en onder 2. genoemde dient er bij het overdragen van een programma naar een andere compiler, taal, of systeem een zekere mate van aanpassing of conversie plaats te vinden.
4.2
Taalniveaus
In zekere zin wordt een computer gedefinieerd door zijn machinetaal. De machinetaal, d.w.z. de precieze structuur en werking van de machine-instructies, bepaalt de uitwendige verschijningsvorm van de processor. Indien de machinetaal direct uitgevoerd wordt door de hardware, dan
48
HOOFDSTUK 4. TAALNIVEAUS
definieert de machine-taal een re¨ele machine. Indien het een gemicroprogrammeerde computer betreft is dit niet het geval. Dan worden de micro-instructies door de hardware uitgevoerd en bepaalt de microprogrammerings-taal de werkelijke machine, en is de door de machine-taal gedefinieerde machine (die voor de gebruiker in beide gevallen even ’echt’ bestaat) niet werkelijk, ofwel virtueel. In feite definieert iedere programmeertaal (inclusief hogere programmeertalen, assemblertalen, machine-talen, microprogrammeringstalen) een machine, nl. de machine die instructies (statements) in die taal begrijpt en kan uitvoeren. In de meeste gevallen is die machine virtueel. Om een programma in zo’n taal te doen uitvoeren moet er een (wederom mogelijkerwijze virtuele) machine bestaan waarop dat programma ge¨ınterpreteerd kan worden of waarop dat programma vertaald kan worden en daarna ge¨executeerd. Dit betekent dat een virtuele machine Mi+1 met machine-taal
Virtuele Machine Mn met . . . . Virtuele Machine M3 met
Machine-taal Ln
Virtuele Machine M2 met
Machine-taal L2
Machine-taal L3
Re¨ele Machine M1 met Machine-taal L1 Figuur 4.2: Een computer bestaande uit een aantal niveaus. Li+1 ge¨ımplementeerd kan worden op machine Mi met machine-taal Li als er ofwel een interpretator in Li geschreven bestaat voor Li+1 , ofwel een vertaler, in Li geschreven, die een programma in Li+1 vertaalt naar een programma in Li (zie Figuur 4.2). Uiteraard is het ook mogelijk dat er op een lager niveau een interpretator of compiler bestaat voor Li+1 . In Figuur 4.3 zien we de niveaus die gewoonlijk in conventionele systemen aanwezig zijn, samen met het vertaalmechanisme. In sommige machines is het microprogrammeringsniveau niet aanwezig; indien het er is, is het een extra software niveau dat e´ e´ n voor e´ e´ n de uit te voeren machine-instructies interpreteert. Het operating-system niveau behoeft nog enige uitleg. In de meeste computers bestaan speciale instructies om service van het operating system te vragen. Bij het aantreffen van zo’n operating-system instructie in de instructiestroom treedt een trap op, waarna de instructie ge¨ınterpreteerd wordt door een routine in machine-code. Dit soort instructies te zamen met alle machine-instructies defini¨eren het operating-system niveau. Deze niveaus zijn
49
4.2. TAALNIVEAUS
dus voor een zeer groot deel identiek. Voor zover dat niet het geval is, is er sprake van interpretatie. Hier zien we dus dat de implementatie van de virtuele machine die door de verzameling instructies op het operating-system niveau wordt gedefinieerd, gedeeltelijk via hardware-executie verloopt (als we even afzien van het microprogramma), en gedeeltelijk via interpretatie van software (nl. operating-system routines). Het hoogste niveau kan b.v. het niveau van een hogere programmeertaal zijn, maar er zijn andere mogelijkheden. Indien er b.v. een tekst-verwerker draait op een computer, kan men met recht zeggen dat het een tekst-verwerkingsmachine is, die commando’s van de tekstverwerker begrijpt en uitvoert. De totale verzameling van opdrachten die men in zo’n situatie aan een computer kan geven defini¨eren weer een virtuele machine. Hetzelfde geldt b.v. als er een database op een computer is ge¨ınstalleerd. Een ander mooi voorbeeld van een virtuele machine is die gedefinieerd door het commando-interface van een operating system (niet te verwarren met het operating-system niveau). Het aantal niveaus hoeft niet beperkt te zijn tot dat in Figuur 4.3.
Het Probleem-geori¨enteerde Niveau Interpretatie of Vertaling Het Assembleertaal Niveau Vertaling Het Operating-system Niveau Identiek/Interpretatie Het Conventionele-machine Niveau Interpretatie Het Microprogrammeringsniveau Interpretatie Het Digitale Niveau Figuur 4.3: Niveaus in conventionele computers. Van de niveaus die we hierboven noemen worden sommige door software ondersteunt (b.v. hogere programmeertalen) en andere door hardware (b.v. de microprogrammeringstaal of de machine-taal). Logisch gezien maakt het niet uit of het een of het ander het geval is (voor de snelheid maakt het wel degelijk uit). Een bepaalde functie kan net zo goed in hardware als in software zijn ge¨ımplementeerd. Men zegt hierom wel dat hardware en software (en firmware) equivalent zijn. Een goed voorbeeld hiervan vormen de eerder aangehaalde floating-point operaties (voorbeeld 1 in 4.1.2).
50
4.3
HOOFDSTUK 4. TAALNIVEAUS
De Structuur van Compilers
Een compiler vertaalt een programma geschreven in een hogere programmeertaal naar een equivalent programma in machinecode. Dit vertaalproces is qua logische opbouw en qua implementatie zo ingewikkeld, dat het niet in e´ e´ n stap uit te voeren is. Het is daarom gebruikelijk het vertaalproces in een aantal deelprocessen, die we fasen zullen noemen, te verdelen. Een fase is een logisch samenhangende operatie die als invoer een representatie van het oorspronkelijke bronprogramma heeft en als uitvoer een andere representatie van hetzelfde programma produceert. Bij de beschrijving van de fasen gaan we uit van het schema in Figuur 4.4.
Bronprogramma
Lexicografische Analyse
Syntactische Analyse
Generatie van Tussencode Code-optimalisatie
Code-generatie
Doelprogramma Figuur 4.4: De Fasen in een Compiler. Delen van een of meer fasen kunnen in een implementatie worden gecombineerd tot een module, die naar analogie met assemblers wederom meestal pass wordt genoemd. Zo spreken we bijvoorbeeld van one- en two-pass compilers. Een pass leest zijn invoer, voert de in de fasen gespecificeerde transformaties uit en schrijft z’n uitvoer naar een tijdelijk bestand dat door een volgende pass weer wordt ingelezen. Het aantal passes en de verdeling van de fasen over de passes worden opgelegd door de verschillende eigenschappen van de betreffende taal en computer. De structuur van de taal heeft veel invloed op het aantal passes. Sommige talen vereisen tenminste een two-pass
4.3. DE STRUCTUUR VAN COMPILERS
51
compiler, omdat ze toestaan dat de declaratie van een naam optreedt na het gebruik van die naam. Code voor het evalueren van een expressie die zo’n naam bevat kan pas adequaat worden gegenereerd nadat de declaratie is verwerkt. Ook de omgeving waarin een compiler wordt gebruikt, kan invloed hebben op het aantal passes. Zo zal een multi-pass compiler minder geheugen nodig hebben dan een one-pass compiler. De eerstgenoemde zal natuurlijk langzamer zijn, omdat elke pass moet lezen van en schrijven naar een tijdelijk bestand. Compilers op computers met een klein hoofdgeheugen en voldoende achtergrondgeheugen zullen in het algemeen multi-pass zijn, terwijl compilers op een computer met voldoende intern geheugen meestal minder passes nodig zullen hebben. De structuur van compilers lijkt op die van assemblers (zie 2.2). Er zijn de volgende essenti¨ele verschillen: 1. De syntactische analyse is veel ingewikkelder bij compilers dan bij assemblers vanwege de veel rijkere structuur van opdrachten in hogere programmeertalen (if ... then ... else, while-loops, en nesting van dergelijke opdrachten); 2. De code-generatie is niet eenduidig. Bij assemblers ligt de code die gegenereerd moet worden vast; die is nl. door de programmeur precies gespecificeerd. Voor de te genereren object-code hebben compilers echter de nodige vrijheid. Het effect van een bepaalde opdracht in een hogere programmeertaal kan op verschillende manieren worden bereikt (b.v. het plaatsen van operanden in registers of niet).
4.3.1
Lexicografische Analyse
De lexicografische analysator (Engels: scanner) vormt het interface tussen het bronprogramma en de compiler. Een voor een worden de karakters van het programma ingelezen en gegroepeerd tot rijen van atomaire eenheden, tokens genaamd. Aan de hand van een voorbeeld zal dit proces worden toegelicht. Stel we hebben het volgende initialiserings statement in C of Java: int
sum=3;
In eerste instantie zal deze statement als een serie van characters worden opgeslagen in het geheugen, i n t ♦ s u m = 3 ; waarbij ♦ het spatie teken representeerd. Vanuit een logisch punt bekeken bestaat het statement echter uit de volgende elementen: int
sum
=
3
;
Ieder van deze elementen wordt een token genoemd. Elk token kan behandeld worden als een logische eenheid. Voorbeelden van tokens zijn: namen (identifiers), keywords, constanten, operatoren, leestekens zoals komma’s en haakjes. Tokens kunnen worden ingedeeld in de volgende klassen:
52
HOOFDSTUK 4. TAALNIVEAUS • keywords: gereserveerde woorden in een taal (bv. if, for,..) • identifiers: namen van variabelen, functies, procedures, etc. • constanten: vaste waarden in een progamma • delimiters: ordenen en groeperen van verzamelingen van tokens • operators: tokens die bewerkingen op operands aangeven
Wat precies een token is, hangt enerzijds van de taal af en anderzijds tot op zekere hoogte van de compilerbouwer, die het interface moet defini¨eren tussen scanner en parser (zie 4.3.2). Er zijn twee type tokens: keywords, leessymbolen, etc., die in de taal gedefinieerd zijn, en namen (van variabelen, constanten, procedures, etc.) die door de programmeur gedefinieerd worden. Voor de registratie van namen bouwt de scanner een naamlijst (Engels: symbol table) op, waarvan we hier aannemen dat deze ge¨ımplementeerd wordt als een array van records, voor iedere naam e´ e´ n. Zo’n record heeft als velden de naam zelf (of een pointer daarnaar), en een aantal attributen. Mogelijke attributen zijn de soort van de naam (b.v. variabale, procedure), het type (voor een variabele b.v. integer of real), de waarde (mits bekend, bij constanten is dit zo). Bijvoorbeeld, neem de volgende Java-statements: int sum; float tot; final static int A=5; final static float B=0.51; sum=A; tot=B; De naamlijst na scanning van de bovenstaande Java-statements kan er b.v. zo uit zien: index .. 100 .. 150 .. 200 .. 300
naam .. sum .. tot .. A .. B
soort type .. .. variable integer .. .. variable real .. .. constant integer .. .. constant real
waarde .. .. .. .. .. 5 .. 0.51
In de representatie van de token-rij kan de scanner namen vervangen door de index in de naamlijst. Ook voor de overige tokens moet een bepaalde representatie gekozen worden. De tokenrij behorende bij het bovenstaande programmafragment ziet er b.v. als volgt uit:
53
4.3. DE STRUCTUUR VAN COMPILERS st[100], as, st[200], st[150], as, st[300].
Tokens met een entry in de symbol tabel worden gerepresenteerd door st[index]. De parser kan informatie omtrent het betreffende token in de symbol table vinden. Het zal duidelijk zijn dat bij hogere programmeertalen waarin dezelfde naam meer dan eens mag worden gebruikt (b.v. een variabele met dezelfde naam in twee verschillende procedures), er meer informatie beschikbaar moet zijn (b.v. het deel van het programma waar welke naam geldig is).
4.3.2
Syntactische Analyse
De syntactische analysator (ontleder, Engels: parser) groepeert de tokens tot syntactische structuren overeenkomstig de grammatica (syntax) van de taal. De syntactische structuren worden meestal in de vorm van een boomstructuur, een z.g. parse tree, gerepresenteerd. De parse tree geeft de hi¨erarchische structuur weer die in de tokenrij aanwezig is. Parse trees zijn het eenvoudigst uit te leggen aan de hand van een arithmetische expressie en een assignment. Stel we hebben de volgende assignment statement: sum = 3 + (2*5);
Assignment statements hebben in het algemeen twee kanten. De linkerkant voor het toekennings token (=) correspondeerd met een variable. De rechterkant na het toekennings token evalueert tot een waarde. Wat de parser doet is de tokens van de bovenstaande assigment organiseren als een groep T met als kenmerk dat het een assignment is. De parser verdeelt de groep vervolgens in een Tlinks en een Trechts . Het is niet moeilijk te zien dat Trechts verder onderverdeeld kan worden in een optelling en een vermenigvuldiging. We kunnen het statement vervolgens grafisch representeren als in Fig. 4.5. Ook voor de andere typen opdrachten (zoals de besturings-opdrachten) kunnen in principe bomen worden gebruikt. = @ @ @
sum
* @ @ @
3
* @ @ @
2
5
Figuur 4.5: Parse tree voor sum=5+(2*3).
54
HOOFDSTUK 4. TAALNIVEAUS
Vaak worden de lexicografische en de syntactische analyse gecombineerd in een enkele pass. De parser roept hierin de scanner aan als subroutine wanneer hij een token nodig heeft. De scanner geeft dan b.v. de index van het token in de naamlijst door aan de parser.
4.3.3
Tussencode-generatie
De uitvoer van de parser, een representatie van de parse tree, wordt door de tussencode-generator omgezet in een tussencode-representatie. De daarvoor gebruikte tussentalen staan dichter bij het machine-niveau dan de hogere programmeertaal. Deze tussentalen hebben veelal de volgende eigenschappen: 1. In een expressie kan slechts e´ e´ n operator optreden. Expressies in een hogere programmeertaal die meerdere operatoren bevatten moeten dus worden opgebouwd m.b.v. deelexpressies; 2. Er kan op slechts e´ e´ n conditie tegelijk worden getest. Samengestelde condities moeten worden opgesplitst in de onderscheiden delen; 3. De besturings-structuren zoals while-loops komen er niet in voor en moeten worden vervangen door tests en sprong-instructies. Voorbeeld 1 De expressie a*b+c moet in tussencode aldus worden opgesplitst: h1 = a * b; h2 = h1 + c; waarin h1 en h2 hulpvariabelen zijn. Voorbeeld 2 Het code-fragment while (a > b) && (a <= c + d) { a = a * b; } wordt in tussencode: L1: if (a > b) goto L2 goto L3 L2: h1 := c + d if (a <= h1) goto L4 goto L3
4.3. DE STRUCTUUR VAN COMPILERS
55
L4: a := a * b goto L1 L3: De tussencode kan worden opgevat als een serie macro-aanroepen die later ge¨expandeerd worden tot machinecode. Het voornaamste verschil tussen assemblercode en tussencode is dat in de tussencode de registers niet expliciet worden benoemd. De meeste compilers genereren de parse tree niet expliciet, maar produceren direct een tussencode.
4.3.4
Code-optimalisatie
Optimalisatie van code is een facultatieve fase die slechts dient om de doelcode sneller en/of korter te maken. Dit is vooral van belang voor programma’s die vaak worden gedraaid. Eigenlijk is het fout om te spreken van optimaliseren. Het is theoretisch onmogelijk voor een compiler om het beste doelprogramma te produceren voor elk willekeurig bronprogramma, ongeacht de kostenfunctie die gekozen wordt. Deze fase probeert slechts een doelprogramma te maken dat beter is dan het programma dat zonder optimaliseren zou zijn verkregen. Een betere naam voor deze fase zou dan ook ’code-verbetering’ zijn. Een goede optimaliserende compiler kan het doelprogramma beduidend versnellen. Onder code-optimalisatie wordt hier verstaan verbeteringen aan de code die onafhankelijk zijn van de doel-machine. Zaken als register-allocatie blijven hier dus buiten beschouwing. Een andere belangrijke optimalisatie vindt plaats gedurende de code-generatie, waarin gestreefd wordt naar een zo effici¨ent mogelijk gebruik van de registers en de instructie set van de computer. Vervolgens is er grote winst te halen uit het effici¨enter maken van inwendige loops. De z.g. 90-10-regel zegt immers dat 90% van de draaitijd wordt doorgebracht in 10% van de code. Dus de meest bezochte delen van een programma, de binnenste loops (lussen), komen als eerste in aanmerking voor optimalisatie. Typische loop-optimalisaties zijn het verwijderen van loop-invariante berekeningen en het elimineren van z.g. inductie-variabelen, d.w.z. variabelen waarvan de waarde direct samenhangt met de waarde van een andere variabele (b.v. als i=1,2,...,10 en j=3*i, dan kan i worden ge¨elimineerd als deze variabele niet zelf nodig is). Verdere optimalisaties zijn te vinden in het vervangen van run-time berekeningen door compile-time berekeningen (b.v. arrayindices die alleen van constanten afhangen). De allerbelangrijkste verbetering van een programma ligt buiten het bereik van een compiler, nl. de verbetering van het algoritme zelf. In plaats van een sorteeralgoritme van de orde O(n2 ) kan beter een sorteeralgoritme van de orde O(n log(n)) genomen worden. We zullen een tweetal soorten optimalisaties nader bekijken. 1. Locale optimalisatie. In voorbeeld 2 in 4.3.3 komen sprongen over sprongen voor. Dit zou vermeden kunnen worden door de test om te draaien.
Voorbeeld. Het fragment if (a > b) goto L2
56
HOOFDSTUK 4. TAALNIVEAUS goto L3 L2: kan worden veranderd in: if (a <= b) goto L3 Een andere locale optimalisatie is het elimineren van gemeenschappelijke deelexpressies. Voorbeeld. Het Java fragment a = b * c + d; e = b * c + f; kan worden ge¨evalueerd als: h1 = b * c; a = h1 + d; e = h1 + f; 2. Loop-optimalisatie. Zoals al vermeld kunnen loops worden versneld door de berekeningen die bij elke loopdoorgang hetzelfde resultaat opleveren buiten de loop te brengen.
Voorbeeld. In het programma fragment i = 0; a = 0; while (i < 200) { a = a + 3.0 * g * h[i]; i= i+1; } kan de deelexpressie 3.0*g buiten de loop gebracht worden, waardoor 199 vermenigvuldigingen worden bespaard: i = 0; a = 0; t = 3.0 * g; while (i < 200) { a = a + t * h[i]; i = i + 1; }
57
4.3. DE STRUCTUUR VAN COMPILERS
4.3.5
Code-generatie
De laatste stap is het omzetten van de tussencode naar machinecode. In deze fase worden geheugenlocaties toegewezen aan de data, wordt code gegenereerd om toegang te verkrijgen tot de data, worden registers toegewezen om berekeningen uit te voeren, etc. Het recht-toe recht-aan expanderen van een tussencode-instructie in een aantal machinecode-instructies zal in het algemeen een doelprogramma opleveren waarin nogal wat overbodige ’laad register’- en ’berg register op’-opdrachten voorkomen. Dit is te vermijden door de code generator te laten bijhouden welke grootheden zich op elk moment in de registers bevinden. Een goede code-generator probeert de registers, waarmee berekeningen sneller kunnen worden uitgevoerd, zo effici¨ent mogelijk te gebruiken. Een optimale registerallocatie is erg moeilijk te realiseren. De code-generator van een compiler is in feite het enige machine-afhankelijke deel. We zullen e.e.a. illustreren aan de hand van de omzetting van het code fragment sum=5+(2*3); naar code voor de PowerPC. In het voorbeeld wordt aangenomen dat er een 32k programma ruimte is, dat R1 de stackpointer is en dat er 32 bit aritmetiek wordt gebruikt. Initieel zal de codegenerator elke assignment statement willen omzetten naar de volgende twee instructies: LWZ STW
R2,
# [R2] <-
De volgende stap is beide kanten van de assignment te evalueren. Beide subgroepen Tlinks en Trechts kunnen onafhankelijk van elkaar worden verwerkt. Voor Tlinks is het simpel en hoeft er slechts een referentie naar de variable sum worden gesubstitueerd. De rechterkant is meer gecompliceerd. De eerste na¨ıve aanpak is de volgende code voor de optelling te genereren: ADDI ADD
R2,0,3 R2,<2*3>,R2
# [R2] <- 3 # [R2] <- [R2] + <2*3>
De vermenigvuldiging resulteert vervolgens in ADDI R2,0,2 ADDI R3,0,5 MULLW R2,R3,R2
# [R2] <- 2 # [R3] <- 5 # [R2] <- [R3]*[R2]
Nu moeten deze code fragmenten worden gecombineerd. Dat betekent dat de tussenresultaten aan elkaar moeten worden doorgegeven. De meest generieke methode is om de tussenresultaten door te geven middels de stack. ADDI ADDI MULLW STW
R2,0,2 R3,0,5 R2,R3,R2 R2,0(R1)
# # # #
[R2] <- 2 [R3] <- 5 [R2] <- [R3]*[R2] zet resultaat op de stack
LWZ
R3,0(R1)
# [R3] <- stack
58
HOOFDSTUK 4. TAALNIVEAUS ADDI ADD STW LWZ STW
R2,0,3 R2,<2*3>,R2 R2,0(R1) R2,0(R1) R2,sum(0)
# [R2] <- 3 # [R2] <- [R2] + <2*3> # zet resultaat op de stack # [R2] <- stack # doe toekenning
Deze compositie van code fragmenten is generiek, maar niet efficient. Vooral het schrijven naar en terughalen van de stack is een dure operatie. Het is veel efficienter om de tussenresultaten in de registers van de CPU te laten staan. We moeten dan echter uitkijken dat we het tussenresultaat niet in een register zetten dat de volgende routine voor andere doeleinden gebruikt. Dat is duidelijk te zien in de overgang van het eerste fragment naar het tweede fragment. Als we het tussenresultaat van het eerste fragment in R2 laten staan, dan komen we in de problemen omdat in het tweede fragment R2 gebruikt wordt om het getal 3 in te zetten. Hiermee wordt het tussenresultaat overschreven. Dit kan opgelost worden door een ander register te kiezen. Hiervoor moeten we echter alle code fragmenten analyseren om te zorgen dat er geen conflicten onstaan. Dit probleem wordt het register allocatie probleem genoemd. Als we deze optimalistie toepassen onstaat het volgende code fragment: ADDI R2,0,2 ADDI R3,0,5 MULLW R2,R3,R2
# [R2] <- 2 # [R3] <- 5 # [R2] <- [R3]*[R2]
ADDI ADD
# [R2] <- 3 # [R2] <- [R2] + <2*3>
STW
4.3.6
R3,0,3 R2,<2*3>,R2 R2,sum(0)
# doe toekenning
Het Beheer van Tabellen en Foutafhandeling
De functie van dit onderdeel van de compiler is het opslaan van alle essenti¨ele informatie over namen en data-objecten zoals die in een programma voorkomen. Zo moet een compiler weten of een variabele een integer of een real waarde representeert, wat de omvang, de dimensies en het basistype van een array zijn, hoeveel argumenten een functie verwacht, etc. Deze informatie staat expliciet in de declaraties of is impliciet aanwezig door de context waarin een bepaald object wordt gebruikt. Een centrale rol bij het vastleggen van de informatie wordt vervuld door de naamlijst. Tijdens de syntactische analyse kan hier informatie aan worden toegevoegd, zoals het type van een variabele. De verzamelde informatie wordt onder andere gebruikt om te bepalen of er, na een eventuele voorafgaande conversie, een real dan wel een integer optelling in een expressie moet worden uitgevoerd of om te bepalen of er een foutmelding gegeven moet worden als de optelling van een integer en een real niet is toegestaan in de taal. In feite wordt er een semantische analyse uitgevoerd om te controleren of het type van (tussen)resultaten nog wel correct is en of er een operatie wordt toegepast op operanden van het juiste type. De semantische analyse kan zowel
4.3. DE STRUCTUUR VAN COMPILERS
59
plaats vinden tijdens de fase van de syntactische analyse, de generatie van tussencode als de codegeneratie.
Vragen 1. Beschrijf het verschil tussen vertaling en interpretatie. 2. Verklaar waarom er bij software-interpretatie twee programmatellers worden bijgehouden, en waarvoor zij dienen. 3. Wanneer is er sprake van simulatie en wanneer van emulatie ? 4. Welke niveaus zijn er gewoonlijk in een conventionele computer aanwezig ? Welke worden door vertaling verwerkt, welke door interpretatie, en welke door een combinatie van beide ? 5. Noem de verschillende fasen van een compiler en hun functie.
60
HOOFDSTUK 4. TAALNIVEAUS 6. Vertaal het onderstaande programma-fragment in tussencode met de restricties zoals in 4.3.3: if (a > b) || while (a > a = a + b = b } }
(c = d) { c) && (b = d) { c + d; c - d;
Hoofdstuk 5 Large Computer Systems 5.1
Interconnection Networks
Bij de beoordeling van de structuur van multicomputers1 spelen de volgende drie grootheden een rol (hierbij is de afstand tussen twee processoren de lengte van het (een) kortste pad tussen de processoren): 1. De diameter, het maximum van de afstanden tussen ieder tweetal processoren. De diameter is uiteraard van belang i.v.m. de maximale vertraging van berichten tussen processoren; 2. De gemiddelde afstand tussen twee processoren, die ook van belang is i.v.m. vertragingen van berichten; 3. De graad, het maximum van het aantal verbindingen per processoren. Dit is met name van belang i.v.m. de realisatie in hardware. Een zeer groot aantal verbindingen per processor is moeilijk te realiseren. We gaan hier niet in op de programmering van multicomputers. Ze worden met name gebruikt voor snelle executie van specifieke, rekenintensieve programma’s. Het is hierbij van het grootste belang (maar ook zeer moeilijk) om van de totale aanwezige processorcapaciteit en de geboden interconnectie-structuur effici¨ent gebruik te maken. Er bestaan vele interconnectiestructuren voor multicomputers, waarvan we er hier een aantal behandelen. We beschouwen een interconnectie-structuur als een graaf, d.w.z. als een verzameling V van knopen (Engels: vertices) die de processoren modelleren, en een verzameling E van randen (Engels: edges), die staan voor de verbindingen tussen processoren. Iedere rand verbindt een tweetal knopen, en dus is E ⊆ V × V . We noteren de verzameling {0, 1, . . . , k − 1} als hki. Voor een niet-negatief geheel getal w defini¨eren we wi als het gehele getal verkregen door het (i + 1)-ste minst-significante bit in de binaire representatie van w te inverteren (bij voorbeeld, als w = 5, dan is w0 = 4, w1 = 7 en w2 = 1). Hieronder staat p aldoor voor het aantal processoren; we veronderstellen deze genummerd van 0 tot en met p − 1. 1
Zie ook H12 van [Hamacher02]
61
62
HOOFDSTUK 5. LARGE COMPUTER SYSTEMS
Complete Netwerken In zekere zin de eenvoudigste interconnectie-structuur is een compleet netwerk, waarbij alle processoren met elkaar verbonden zijn: V = hpi E = {(i, j)|i, j ∈ V } Het totale aantal verbindingen is p(p−1)/2, en de graad is p−1, hetgeen voor een fysieke realisatie veel te groot is als p groot is. Een voordeel is natuurlijk dat de diameter 1 is.
5.1.3
Multistage Networks
Omega-netwerken De 2 × 2 switches (schakelaars) behandeld in [H] worden wel omega switches genoemd, en een netwerk als in [H], Figuur 10.6, een omega-netwerk. We zullen nu bepalen hoeveel omega switches er nodig zijn in een netwerk dat N = 2n CPUs met N geheugenmodulen verbindt. In een omega-netwerk doorloopt een bericht een aantal stadia (Engels: stages). In het eerste stadium wordt naar het eerste bit van de n-bits identificatie van het geheugenmodule gekeken, in het tweede stadium naar het tweede, etc. Dit betekent dat er n stadia van schakelaars nodig zijn. Omdat iedere schakelaar 2 inputs en 2 outputs heeft, zijn er per stadium N/2 schakelaars nodig. Het totale aantal schakelaars is dus n · N/2 = N · 2 log N/2.
5.1.4
Hypercube Networks
De hyperkubus van dimensie n, kortweg de n-kubus, heeft de volgende verzamelingen knopen en randen: V = h2n i E = {(w, wi )|w ∈ V, i ∈ hni} De verbindingen (w, wi ) worden de verbindingen van dimensie i + 1 genoemd. Een hyperkubus is te zien als een speciaal geval van een rooster, nl. e´ e´ n met slechts twee processoren per dimensie. Zie ook [H]. Butterfly Networks Butterfly netwerken zijn iets ingewikkelder dan hyperkubussen. Formeel: V = h2n i × hn + 1i E = {([w, t], [w, t + 1]), ([w, t], [wt , t + 1])|w ∈ h2n i, t ∈ hni} Deze definitie betekent dat we een butterfly netwerk kunnen opvatten als n + 1 boven elkaar liggende rijen, genummerd van 0 tot en met n, van 2n processoren, genummerd van 0 tot en met
5.1. INTERCONNECTION NETWORKS
63
2n − 1, met de volgende verbindingen. Alle verticale verbindingen bestaan (de verbindingen ([w, t], [w, t+1])), en daarnaast zijn er de ”scheve”verbindingen ([w, t], [wt , t+1]), die voor grotere waarden van t over steeds grotere afstanden lopen. Cube-connected Cycles Een cube-connected-cycles netwerk van dimensie n is een hyperkubus van dimensie n waarin de processoren vervangen zijn door ringen met n processoren. Ieder van de processoren van zo’n ring zorgt voor de verbinding in e´ e´ n dimensie. Shuffle-Exchange Netwerken Shuffle-exchange netwerken vormen grafen van graad 3, en zijn als volgt gedefinieerd: V = h2n i E = {[w, w + 1]|w ∈ V, w even} ∪ {[w, 2w mod (2n − 1)]|w ∈ h2n − 1i} ∪ {[2n − 1, 2n − 1]} Er zijn twee soorten randen. Exchange randen verbinden knoop w met knoop w0 , de knoop met het minst-significante bit ge¨ınverteerd. Shuffle randen verbinden knoop w met de knopen w0 die verkregen worden door de binaire representatie van w cyclisch e´ e´ n positie naar rechts of links te schuiven. De naam shuffle is ontleend aan de volgende manier van schudden van een pak van 2n speelkaarten, genummerd van 0 tot en met 2n − 1. Verdeel de kaarten in twee stapels, de eerste bestaande uit de kaarten 0 tot en met 2n−1 − 1, de tweede uit de kaarten 2n−1 tot en met 2n − 1. Neem nu om en om een kaart van de eerste en van de tweede stapel. De shuffle rand uitgaande van een bepaalde knoop (speelkaart) heeft als eindpunt de knoop met het nummer waar deze kaart terecht komt bij deze manier van schudden. In Tabel 5.1 wordt van deze structuren enige relevante waarden gegeven (zie de opgaven voor de berekening van een aantal van deze waarden).
5.1.5
Mesh Networks
In een tweedimensionaal rooster (Engels: grid of mesh) zijn de processoren gearrangeerd in een rechthoek, waarbij behalve aan de randen iedere processor met vier buren is verbonden (boven, onder, links, rechts). Voor twee positieve gehele getallen k, l is een rooster gedefinieerd door V = hki × hli E = {([i, j], [i + 1, j])|i ∈ hk − 1i, j ∈ hli} ∪ {([i, j], [i, j + 1])|i ∈ hki, j ∈ hl − 1i} Een tweedimensionaal rooster is op te vatten als het product van twee lineaire arrays. Er zijn in totaal k · (l − 1) + l · (k − 1) ≈ 2kl verbindingen, de diameter is k + l − 2, de gemiddelde afstand is ongeveer (k + l)/3 (zie opgave 3), en de graad is 4.
64
HOOFDSTUK 5. LARGE COMPUTER SYSTEMS
structuur
aantal processoren Compleet netwerk p Lineair array p Ring p Rooster (n bij n) p = n2 Hyperkubus (dim. n) p = 2n Butterfly (dim. n) p = (n + 1)2n Cube-connected cycles (dim. n) p = n2n Shuffle-exchange netwerk p = 2n
totale aantal verbindingen p(p − 1)/2 p−1 p 2n(n − 1) n · 2n−1 2n · 2n n · 2n−1 + n · 2n 3 · 2n−1
diameter
gemiddelde afstand 1 1 p−1 ≈ p/3 ≈ p/2 ≈ p/6 2(n − 1) ≈ 2n/3 n n/2
graad p−1 2 2 4 n 4 3 3
Tabel 5.1: De relevante waarden van een aantal interconnectie-structuren van multicomputers. De Transputer, een RISC-achtige processor met geheugen van de Engelse firma INMOS, is speciaal ontworpen voor deze interconnectie-structuur. Deze processor heeft 8 bit-seri¨ele, unidirectionele links, twee voor verbindingen met ieder van de vier buurprocessoren. Een ander voorbeeld van een computer met een tweedimensionaal rooster is de Intel Paragon XP/S. Er zijn twee uitbreidingen te geven van tweedimensionale roosters. Ten eerste kan de dimensie hoger zijn: neem simpelweg het product van n lineaire arrays om een n-dimensionaal rooster te verkrijgen. De andere uitbreiding is om de randen a¨ an elkaar te knopen”, waardoor een zgn. mesh met wraparound verbindingen wordt verkregen. Dit betekent in het tweedimensionale geval dat processor (0, j) verbonden wordt met processor (k − 1, j), voor j = 0, . . . , l − 1, en dat processor (i, 0) verbonden wordt met processor (i, l−1), voor i = 0, . . . , k −1. Ditzelfde kan worden gedaan in hogere dimensies. Een mesh met wraparound verbindingen van dimensie n is het product van n ringen.
5.1.7
Ring Networks
Een lineair array van processoren is gedefinieerd door V = hpi E = {(i, i + 1)|i ∈ V \ {p − 1}} De gemiddelde afstand in een array is ongeveer p/3 (zie opgave 3). Een ring is een lineair array waarin processoren 0 en p − 1 ook met elkaar verbonden zijn.
Vragen 1. Teken een omega-netwerk dat 16 processoren met 16 geheugenmodulen verbindt. Teken ook voor een aantal paren (processor, geheugenmodule) de verbinding.
5.1. INTERCONNECTION NETWORKS
65
2. Indien in een omega-netwerk dat 16 processoren met 16 geheugenmodulen verbindt een schakelaar in het eerste stadium uitvalt, voor hoeveel paren (processor, geheugenmodule) is dan de verbinding verbroken? Hoeveel verbindingen zijn dit voor een schakelaar in het tweede, derde resp. het vierde stadium? 3. Laat zien dat de gemiddelde afstand tussen twee processoren (de afstand van een processor tot zich zelf meegerekend) in een lineair array met p processoren gelijk is aan (p − 1/p)/3 P (Aanwijzing: voer een directe berekening uit, en gebruik pi=1 i2 = p3 /3+p2 /2+p/6). Leidt hieruit af dat de gemiddelde afstand in een array en een ring met p processoren ongeveer gelijk is aan p/3 resp. p/6. Leidt hier tevens uit af dat de gemiddelde afstand in een k × lrooster voor grote waarden van k en l ongeveer gelijk aan (k + l)/3 is. 4. Laat zien dat het totale aantal verbindingen in een hyperkubus van dimensie n gelijk is aan n · 2n−1 . 5. Laat zien dat de gemiddelde afstand tussen twee processoren (de afstand van een processor tot zich zelf meegerekend) in een hyperkubus van dimensie n gelijk is aan n/2 (Aanwijzing: laat zien dat voor iedere l = 0, 1, . . . , n er net zoveel processoren op afstand l als op afstand n − l zijn vanaf een vaste processor). 6. Wat is in de hyperkubus van dimensie 6 de afstand tussen de processoren met identificatie 101010 en 111111? Hoeveel paden van die lengte zijn er tussen deze twee processoren? 7. Bepaal het totale aantal processoren en verbindingen, de diameter, de gemiddelde afstand, en de graad in een hyperkubus van dimensie 4 resp. een 4 × 4-rooster. 8. Teken een butterfly netwerk met 12 en 32 processoren. 9. Laat zien dat in een butterfly netwerk van dimensie n het aantal verbindingen gelijk is aan 2n · 2n , en dat de graad 4 is. 10. Teken een cube-connected-cycles netwerk van dimensie 2 en 3. 11. Laat zien dat het totale aantal verbindingen in een cube-connected-cycles netwerk van dimensie n gelijk is aan 3n · 2n−1 . 12. Teken een shuffle-exchange netwerk met 8 en 16 processoren. 13. Welke processoren hebben in een shuffle-exchange netwerk een verbinding met zichzelf? Laat zien dat het totale aantal verbindingen in een shuffle-exchange netwerk met 2n processoren gelijk is aan 3 · 2n−1 . Zie ook de vragen bij Hoofdstuk 10 in [H], i.h.b. 10.2 t/m 10.5, 10.7, 10.9, en 10.16.
66
HOOFDSTUK 5. LARGE COMPUTER SYSTEMS
Bijlage A Overzicht Tentamenstof De tentamenstof van Computersystemen (vakcode in1705) bestaat uit: • Van het collegedictaat Computersystemen, H1 t/m H5. • [Hamacher02] V.C. Hamacher, Z.G. Vranesic, en S.G. Zaky, Computer Organization, vijfde editie, 2002, McGraw-Hill, Opmerkingen: 1. Bij het tentamen is gebruik van het boek en collegedictaat verboden. 2. Bij het tentamen zijn rekenmachines niet toegestaan. Uit het collegedictaat de volgende delen:
Hoofdstuk 1 2 3 4 5
Tentamenstof Geheel Geheel Geheel Geheel Geheel
67
68
BIJLAGE A. OVERZICHT TENTAMENSTOF
Uit het boek [Hamacher02] de volgende delen:
Hoofdstuk 1 2 3 4 5 6 7 8 9 10 11 12 Appendix A Appendix B Appendix C Appendix D Appendix E
Tentamenstof Geheel Geheel Geheel niet Geheel, behalve 4.3, 4.6 en 4.7 Geheel tot 5.2.2, 5.5 tot 5.5.4, 5.6 tm 5.10 Geheel, behalve 6.2, 6.4, 6.5, 6.6, 6.7.4 Geheel (geen details van de voorbeelden) Geheel, behalve 8.7 Geheel niet Geheel, behalve 10.3 Geheel niet Geheel Geheel, behalve A5.1, A5.3, A6.2, A6.5, A6.6 Geheel niet Geheel niet Geheel niet E.2