Embedded software

Inleiding

Toon Goedemé

Zie uw eigen notities of het eerste artikel in het boek van Walls^[1].

Hardware

CPU-keuze

Maarten Reekmans

Algemene Architectuur

Essentieel gezien is een CPU enkel de processor. Maar tegenwoordig zit er dikwijls nog een Memory Management Unit, cache-geheugen en een Floating Point Unit bij in de core. We spreken van een System On Chip wanneer de volgende componenten aanwezig zijn in de chip verpakking:

De processor, en eventueel een DSP
Geheugen: RAM, ROM, EEPROM en Flash
Oscillators en PLL's
Counters, Timers, Power on reset
Externe Interfaces: USB, Ethernet, USART, SPI
Analog interfaces: ADC's en DAC's
Voltage regulators en power management circuits.

Historisch gezien zijn bij de ontwikkeling van CPU's 2 grote stromingen bekend. Langs de ene kant hebben we de CISC-architectuur (Complex Instruction Set Computing). Deze architectuur legt de nadruk op hardware. Een complexe instructie wordt uitgevoerd door 1 lijn assembly. Langs de andere kan hebben we de RISC-architectuur (Reduced Instruction Set Computing), die de nadruk eerder legt in de software. Een complexe instructie wordt door meerdere lijnen assembly uitgevoerd.

Als voorbeeld nemen we een vermenigvuldiging

CISC:

  MULT 2:3, 2:2

RISC:

  LOAD A, 2:3 
  LOAD B, 5:2
  PROD A, B
  STORE 2:3, A

Een CPU-chip met CISC architectuur is in normaal gezien groter dan de RISC variant. In embedded systemen worden daarom bijna exclusief RISC-architecturen gebruikt. Alhoewel de enige nog steeds in gebruik zijnde CISC architectuur, x86, de laatste tijd zodanige die shrinks heeft ondergaan dat ze stilaan in het embedded domein beginnen op te duiken.

We kunnen CPU's opdelen in 3 types volgens de breedte van de data registers. We onderscheiden 8, 16 en 32 bit CPU's. Hoe breder de dataregisters hoe meer informatie 1 register kan opslaan. Naarmate een ontwerp complexer wordt kiest men meestal voor een grotere breedte van data register. De laatste tijd beginnen ook CPU's met een data register breedte van 64bits op te duiken.

De adresbus van een CPU gaat bepalen hoeveel geheugen een CPU direct kan adresseren:

16-bit adresbus: 64K adres ruimte
24-bit adresbus: 16M adres ruimte
32-bit adresbus: 4G adres ruimte

De Memory management unit (of kortweg MMU) is een hardware-component in de CPU die gebruikt wordt voor de runtime-mapping van virtuele naar fysieke geheugenadressen. Daarnaast zorgt het bij sommige architecturen voor meer geavanceerde taken zoals geheugenbescherming. Wanneer een ontwerp gebruik gaat maken van een besturingssysteem is het aangewezen om een CPU te kiezen die een MMU aan boord heeft.

Hoe kiezen?

Performantie/Complexiteit

De meest logische keuze hoe men een CPU/SoC kiest is natuurlijk de vereisten van de applicatie. Het spreekt voor zich dat als men een alarmklok wil maken geen 32-bit SoC met MMU nodig heeft. Toch is de keuze van de juiste CPU/SoC niet altijd evident. De kloksnelheid van een CPU is niet altijd een goede referentie om de rekenkracht te kennen. De gehele performantie zal ook afhangen van o.a. hoe groot de pipeline is, hoeveel cache een CPU heeft en welke optimalisaties aanwezig zijn. Men moet natuurlijk ook zien dat de gewenste controllers en I/O aanwezig zijn.

Kost

Bij een design moet altijd een kostenplaatje gemaakt worden. Vooral in grote oplages kan enkele centen per chip een enorme kost betekenen. Er zijn de directe kosten zoals de prijs van aankoop, maar men moet ook rekening houden met de prijs die de compilers, debuggers en IDE's met zich meebrengen. Bovendien kan de kost voor een chip met veel pinnen oplopen omdat men een meerlagige PCB moet ontwerpen. De levensduur van een chip is ook belangrijk. Als een chip van een ontwerp niet meer leverbaar wordt, en er geen compatibele vervangingen zijn moet het hele design hermaakt worden en dit brengt ook kosten mee. Tenslotte kan men nog rekening houden met de tijd tot aflevering van het product. Als een bepaalde chip makkelijker werkt, of de ontwerper al ervaring heeft met de chip, kan er sneller een prototype gemaakt worden en zullen de totale kost dalen.

Verbruik

Voor embedded toepassingen kan het verbruik van de chip een belangrijk gegeven zijn. Wanneer een embedded toepassing enkel door een batterij gevoed wordt, of zelfs enkel door RF-signalen is het essentieel dat de vermogen dissipatie minimaal is. De CPU is meestal de grootste verbruiker van het systeem en is daarom uitermate belangrijk in het hele verbruiksverhaal. Door een CPU te kiezen die bepaalde slaap modi heeft kan zo rekenkracht behouden worden en toch efficient met het stroomverbruik omgegaan worden door de niet gebruikte delen tijdelijk uit te schakelen.

Software

Om een ontwerp te maken is het belangrijk om de juist software voorhanden te hebben. Zonder een goede compiler en linker kan geen applicatie gebouwd worden. Bovendien is een debugger een enorme hulp bij het design. Een JTAG poort of een Debug UART kan, mits de software ondersteuning bestaat, een efficiente manier zijn om ontwerpfouten op te lossen en zo het hele ontwerp proces versnellen. Als men gebruik gaat maken van een besturingssyteem is het een enorme hulp als er ondersteuning is voor de CPU architectuur. Het overzetten van een besturingssysteem op een nieuwe architectuur is een specialistenwerk en is een project op zich.

Ondersteuning

De ondersteuning die geboden wordt door de fabrikant kan ook de keuze van de CPU beinvloeden. Als de fabrikant een volledige omgeving ter beschikking stelt met compilers, debuggers, besturingssysteem, filesystem en een IDE zal ervoor zorgen dat op korte tijd een ontwerp gemaakt kan worden. De beschikbaarheid van alle informatie over de CPU/SoC is ook een vereiste om het ontwerp tot een goed einde te brengen.

Ervaring Ontwerper

Wanneer de ontwerper al voorgaande ervaring heeft met een bepaalde CPU/SoC of met het gebruikte besturingssysteem zal het korter duren alvorens een afgewerkt product kan afgeleverd worden. In de praktijk wordt voorgaande ervaring, al dan niet terecht, vaak als keuzecriterium gebruikt.

Hergebruik Ontwerp

Een afgewerkt ontwerp kan altijd uitgebreid worden met nieuwe functionaliteit. Daarom is het aangewezen om niet het minimum van specs te nemen maar altijd nog ruimte te laten voor uitbreidingen. Er kan ook een nieuw project gestart worden met dezelfde hardware. Op die manier is de hardware direct voorhanden en heeft de ontwerper al de nodige ervaring en ontwikkelomgeving.

Overzicht architecturen

8051

De 8051 microcontroller is een acht bit microcontroller ontwikkeld door Intel in 1980. Hij is zo populair dat er wel twintig (en meer) verschillende types op de markt zijn, die allemaal opgebouwd worden rond dezelfde kern (core). Voor simpele toepassingen die meestal bestaan uit 1 state machine met interrupts kan men best kiezen voor een 8051 of een andere 8-bit microcontroller.

ARM

De naam ARM is afkomstig van Advanced RISC Machine en is een 32-bit RISC architectuur. Het bedrijf ARM limited verkoopt zelf geen CPU's/SoC's maar verkoopt wel de licensies voor de ARM-processor architectuur. Door de vergevorderde power savings van de ARM-architectuur is ARM uitgegroeid tot de grootste speler op de embedded markt, met een aandeel van ongeveer 75%. ARM begon in 1983 met de ARM1, en ondertussen zijn ARM11 en Cortex de laatste nieuwe high performance ontwerpen.

Enkele specialiteiten die de ARM kenmerken:

Thumb mode: Sinds de ARM7 kan de processor in thumb mode gaan. Dit houdt in dat er de 32-bit processor 16-bit instructies gaat uitvoeren. Op die manier kan in sommige situaties een betere code dichtheid bekomen worden en zal de performantie hoger zijn dan in de gewone modus.
DSP uitbreidingen: Er bestaan in de latere generaties ARM bijkomende instructies die DSP en multimedia toepassingen sneller doen verlopen.
Jazelle: Door Jazelle Direct Byte Code Execution kunnen meer recente ARM modellen sommige Java bytecode rechtstreeks in hardware uitvoeren waardoor de uitvoering veel sneller kan gebeuren.

PowerPC

PowerPC is een RISC-processorarchitectuur gemaakt door de Apple-IBM-Motorola alliantie van 1991, beter bekend als de AIM. De processoren waren oorspronkelijk bedoeld voor workstations, maar zijn later populair geworden in embedded systemen. Motorola stapte uit de AIM alliantie en richte Freescale op om verder te gaan in embedded systemen. IBM verkocht zijn deel van de PowerPC aan AMCC. De PowerPC bestaat zowel in een 32-bit, als in een 64-bit variant.

MIPS

De MIPS architectuur is 20 jaar geleden uitgevonden aan de Stanford Universiteit en is na ARM de grootste speler op de markt. Er bestaat een hele grote varieteit van MIPS CPU's/SoC's.

MIPS Heeft volgende optimalisaties:

MIPS-3D: floating point SIMD instructies voor 3D taken.
MDMX: 64-bit floating point berekeningen
MIPS16e: compressie om programma's kleiner te maken (vergelijkbaar met Thumb van ARM)
MIPS-MT: recentelijk ontwikkelt om multithreading mogelijk te maken (vergelijkbaar met Hyperthreading)

AVR

De AVR is een reeks van 8-bit controllers die door Atmel in 1996 is uitgebracht. De AVR was de eerste microcontroller familie die on-chip flash gebruikte. In 2006 heeft Atmel de AVR32 reeks uitgebracht die een volledige 32-bit RISC architectuur omvatte. De AVR32 heeft verschillende optimalisaties zoals SIMD (single instruction multiple data), DSP instructies en verschillende audio en video processing mogelijkheden. De AVR32 is gemaakt als concurrentie van de ARM.

x86

De x86 architectuur is klassiek gezien een architectuur die enkel op de Desktop/Server/Laptop markt wordt ingezet. Maar dankzij continue vooruitgang in de productie van chips kunnen de x86 processoren zodanig verkleind worden zodat ze stilaan in de embedded wereld kunnen ingezet worden bij toepassingen waar het verbruik niet kritiek is. Het voordeel van de x86 is dat er een enorme hoeveelheid software beschikbaar is en er vergevorderde optimalisaties mogelijk zijn.

De belangrijkste fabrikanten met hun chips:

Intel Atom
AMD Geode/Athlon
Via Nano/C7/Eden

Conclusie

Er is meer en meer een enorme keuze aan embedded CPU's/SoC's. De keuze van een goede CPU/SoC is niet meer triviaal. De juiste selectie kan in de ontwerpfase tijd, geld en moeite uitsparen. Daarom kan er best wat research gedaan worden in plaats van meteen een keuze te maken.

Geheugen architectuur en gebruik in embedded systemen

Kevin Deckx

Typen geheugens

Flat single space memory
Segmented memory
Bank switched memory
Multiple space memory

Flat single space memory

Deze geheugen architectuur is de meenste voorde hand liggende wijze waarop geheugens worden aangesproken.
Elk adres correspondeert met welgeteld 1 fysische locatie op het geheugen. Dit heeft één groot voordeel en nadeel.

De compiler heeft geen speciale statements nodig om met dit type geheugen om te gaan, het is een simpel geheugen architectuur.
Omdat elk adres correspondeert met slechts één fysisch adres heeft dit als gevolg dat er slechts een beperkt aantal fysische adressen zijn.
Een 16bit processor zal dus slechts 65536 adressen kunnen aanspreken.
Gecombineerd met een 4k breedte van een geheugen cel is er slechts 256Mb main geheugen beschikbaar.
Dit is ook de reden waarom men voor flat memory kiest bij kleine embedded projecten.

Segmented memory

Om de adresseerbare geheugen ruimte van flat memory te vergroten kan men segmented memory gebruiken.
Men verdeelt het adres in 2 distinctie delen, een memory segment nummer en een offset.
Men plaats dus een geheugen groter dan de 256MB van het vorig voorbeeld.
Men verdeeld dit in een aantal delen (=segments), die men kan aanspreken door middel van status registers in de processor.
Met de segment code en de offset in deze segment kan men een fysiek adress bepalen.

Bank switched memory

Het idee van segmented memory word nu niet meer toegepast op één geheugen lat.
Maar men gebruikt dezelfde status registers om een andere geheugen lat aan te spreken. Men switched dus van de ene memorybank naar een andere memorybank om zo het geheugen te vergroten.

Multiple space memory

In deze oplossing om het geheugen ruimte te vergroten gebruikt men de mogelijkheid om onderscheid te maken tussen 4 niveaus
Men geeft deze 4 niveaus elk hun eigen adress space om zo meer geheugen ruimte te creeëren

Data : user-niveau
Code : user-niveau
Data : supervisor-niveau
Code : supervisor-niveau

Testing

Bart Kerckx

Inleiding

Er gaan hoofdzakelijk 2 hoofdonderdelen gezien worden, namelijk actief testen en self-testing. Met actief testen word er bedoelt dat men zelf het initiatief moet nemen, door bv middel van externe debuggers. Het 2e deel gaat over self-testing, en hierin wordt besproken over hoe men het systeem zichzelf kan laten testen. Het moeilijkst van het debuggen bij vele embedded systemen, is het ontbreken van een display of dergelijke. Dit maakt het moeilijker om fouten te tonen.

Actief Testen/Debuggen

In-Circuit Emulators (ICE)

Dit was 1 van de eerste methodes die werd geprefereerd om een system te debuggen. Het systeem kan hiermee op volle snelheid gedebugged worden. Het gebruiken van een ICE is waarschijnlijk 1 van de beste methodes om een systeem te debuggen, MAAR tijdens de jaren zijn processors sneller en complexer geworden. Hierbij is vooral de snelheid nadelig voor ICE, omdat deze de prijzen van ICEs die deze snelheid aankunnen de hoogte in drijven. Tegenwoordig zijn daarom ICEs meestal alleen maar beschikbaar voor low-end systemen.

Monitor Debuggers

Een andere goede oplossing is het gebruik van een monitor debugger. Om dit te kunnen gebruiken moet wel de ROM tijdelijk vervangen worden door RAM alsook een extra I/O device moet voorzien worden (bv een seriële poort) tijdens het debuggen. Hierdoor kan de code op volle snelheid gedebugged worden op de hardware van het target. Het gebruik van een Monitor Debugger heeft niet alle functionaliteiten van een ICE, maar meestal is dit wel voldoende.

On-Chip Debug (OCD)

Meeste moderne microprocessors hebben On-Chip support voorzien voor software debugging. Een vaak gebruikte interface is de JTAG, een andere is BDM( Background Debug Mode). OCD is meestal geïmplementeerd in demicrocode van de chip. Ook moet een connector voorzien worden op het bord. Hierop wordt dan de adapter verbonden. Maar de kost en de ruimte die hiervoor moet voorzien worden is miniem.

Self-Testing

CPU en Register test

De CPU wordt meestal als 1 van de eerste getest tijdens het booten. De bedoeling is hier dat de interne werking van de CPU in orde is. De test zal uitgevoerd worden door processor instructies laten uit te voeren en dan de output van deze instructie te controleren. Ook de registers worden gecontroleerd in deze test. Bijvoorbeeld data in een register kan geshift worden met 1 bit en het resultaat van deze shift operatie zal dan vergeleken worden met een op voorhand berekende waarde.

Interrupt en Exception test

Hier worden de interrupt en exception afhandelen gecontroleerd. Een goede methode is om een conditie te maken waarbij een interrupt of exception gegenereerd word en dit blijven doen totdat de verwachte interrupt herkent word. Bv: Een timer interrupt kan geenabled worden en de test kijkt dan of een bepaalde vlag geset is, die zou gezet moeten worden door de interrupt handler. Een voorbeeld van een exception test is het expres creëren van een exception conditie zoals het delen door nul, en dan controleren dat dit correct afgehandeld word.

Memory Test

Geheugen is 1 van de meest belangrijke onderdelen van het systeem, en de integriteit is kritiek voor het systeem. Daarom is het testen van het geheugen zeker te overwegen.

RAM testen tijdens opstarten v/h systeem

Door het feit dat RAM nog geen bruikbare data heeft tijdens het opstarten is dit een goed moment om het eens goed te testen. Een vaak gebruikte vorm van test is de “bewegende enen” of “bewegende nullen”, of ook wel RAM March Test genoemd. Deze test focust zich op het vinden van 3 type fouten van het geheugen:

- Adreslijn fouten: Adreslijnen op het bord of binnen de geheugenchip kan een kortsluiting bevatten met elkaar, of ze kunnen blijven hangen op een 1 of een 0. In beide gevallen zal wanneer er op geheugen geschreven zal worden, kan dit foutief op meerdere plaatsen, of op verkeerde plaatsen gebeuren. Het lezen kan corrupte data geven wanneer 2 verschillende plaatsen in het geheugen, hun data op de bus plaatsen.

- Datalijn fouten: Ook de datalijnen kunnen kortgesloten zijn met elkander, of vast blijven zitten op 1 of 0. Dit veroorzaakt dat er verkeerde data geschreven of gelezen wordt uit het geheugen.

- Verlies van data: Wanneer data geschreven wordt op een bepaalde geheugenplaats, kan dit helemaal in orde zijn wanneer het meteen gelezen wordt na het schrijven. Maar deze data kan een tijdje later verloren zijn. Hier zijn de adres- en datalijnen perfect in orde, maar de geheugencellen werken niet meer naar behoren.

De test van de “bewegende enen” werkt als volgt: Stap 1: Initializeren, schrijf nullen naar alle geheugenlocaties. De volgende stappen moeten gedaan worden voor alle adressen. Stap 2: kijk na of de inhoud van het geheugenplaats nog steeds nul is. Stap 3: Schijf een 1 op de bit 0 plaats. Stap 4: lees het geheugenplaats uit, en kijk na of de 1 succesvol geschreven is, en de andere locaties nog steeds 0 zijn. Stap 5: Zet de bit terug op 0. Stap 6: herhaal dit voor alle bits van de geheugenlocatie.

RAM testen tijdens werking v/h systeem

Wanneer het systeem in werking is, en de applicatie(s) aan het draaien zijn, kunnen we geen RAM tests doen, aangezien deze de data corrupt zouden maken. Het enige soort van test dat er gedaan kan worden is data eerst in een register schrijven voor het in het geheugen gaat. Deze 2 kunnen dan vergeleken worden. Deze test kan nu en dan gedaan worden, of in gang gezet worden.

PROM Checksum

PROM kan het best getest worden door een checksum te berekenen Een voorbeeld is bv dat wanneer een PROM geprogrammeerd word, de 2 laatste bytes speciaal op nul geïnitialiseerd worden. Dan berekent dat PROM programmer de checksum, deze checksum wordt dan in deze 2 laatste bytes gefused. Deze test zal dan een 16-bit XOR doen, buiten de 2 laatste bytes. Deze berekende checksum wordt dan vergeleken met diegene die in de PROM gefused is. De test is geslaagd wanneer beide checksums gelijk zijn.

I/O apparaten

Aangezien dit nogal algemeen is, en er veel te veel apparaten zijn om ze allemaal te bespreken is het nogal moeilijk om hierover algemeenheden te zeggen. Toch zijn er enkele dingen die vaak voorkomen. Veel verkopers van onderdelen voorzien speciale maatregelen om hun toestel te testen door een test mode te voorzien. Wanneer een toestel zo een test mode niet heeft, kan men vaak best extra functionaliteit voorzien op het bord om het toestel te testen. Vaak kan men ook een toestel testen door de zender met de ontvanger te verbinden van dit toestel. En deze in Loop Back te zetten. Nu kan men dan data versturen versturen, en wachten totdat de ontvanger de data ontvangt na de Loop Back. Het enige nadeel hiervan is dat een toestel vaak niet de fysieke paden gebruikt maar de Loop Back in de chip zelf gebeurd.En dus externe fouten niet gecheckt worden.

Watchdog Timer

Een vaak gebruikte methode om het vastlopen van hardware of software modules in het oog te houden, is het gebruik van een Watchdog Timer. Het systeem wordt voorzien van een hardware timer dewelke nooit een timeout mag krijgen. Onder normale omstandigheden word deze timer perdiodiek terug herstart. Wanneer bv een hardware module blijft vasthangen, zal deze timer niet meer herstart worden, en de Watchdog Timer zal aflopen. Dan kan een gepaste actie ondernomen worden. Meestal zal dit een hardware reset als gevolg geven.

eenmalige fouten

Wanneer een systeem in werking is, moeten ook eenmalige fouten in het oog gehouden worden. Hierbij worden fouten bedoelt die gewoon eens eenmalig voorvallen door bv een spike of interferentie. En deze fout zal dus (normaal gezien) niet meteen meer voorvallen wanneer de operatie opnieuw gedaan wordt. Deze fouten moeten in oog gehouden worden, en de gepaste actie moet worden gedaan door het systeem.

Error gevonden, wat nu?

We hebben nu een hele hoop methodes gezien waarop het systeem zichzelf test. Maar wat moet er nu gebeuren als er een fout ontdekt is? Vaak word het hele systeem gereset. Wanneer data corrupt geraakt is door bv een spike en dergelijke zal deze methode helpen. Het beste is ook dat er wordt getoond of gerapporteerd wordt dat er een fout was, en zelfs wat voor fout het was. Wanneer het niet kan getoond worden, zou het tenminste toch ergens moeten opgeslagen worden, zodat met een debugger de fout geïdentificeerd worden.

Software

Assembler

Raf Verbiest

Wat?

Elke CPU wordt ontworpen met een specifieke instructieset. Deze instructieset (een verzameling van zogenaamde opcodes) is in feite het machinecode-niveau waarmee de CPU wordt aangesproken. Toen microprocessors een opgang maakten in de jaren '70 werden ze manueel geprogrammeerd door de opcodes één voor één op een hexadecimaal keypad in te voeren. Instructies zowel als geheugenadressen werden aangeroepen met een hex code.

Voorbeeld van een microprocessorbord uit de jaren 70, met hex keypad als programmatiemethode

Omdat deze vorm van programmeren hopeloos onpraktisch wordt als de code meer dan een paar tientallen regels lang is, werd er een iets overzichtelijkere programmeermethode bedacht. Assembler is een programmeertaal waarin de machinecode iets verder van de programmeur wordt geschoven om het ontwikkelproces vlotter te laten verlopen:

De specifieke hex codes voor elke instructie wordt vervangen door een naam, bv. 'MOV' voor een kopieeractie, 'ADD' voor een optelactie, 'DIV' om een deling uit te voeren. Deze mnemonics zijn niets meer dan aliassen voor de opcodes.
Het wordt mogelijk aan deze instructies vaste waarden mee te geven zonder jezelf te bekommeren over waar die vaste waarde precies vandaan komen uit het geheugen, vb ADD A 0x50h : 'Tel bij het register A 0x50 op'. Deze 0x50 wordt ergens in een geheugenadres opgeslagen tijdens de uitvoering; assembler zal deze 0x50 mee in het uitvoerbaar formaat steken en het argument aan de instuctie ADD vervangen door het geheugenadres waar 0x50 staat. (dit is niet nodig bij alle CPU's)
De assembler produceert ofwel standalone programma's ofwel Operating-System-Specific binaries (ELF)

De term Assembler wordt zowel gebruikt voor de taal als voor de compiler en linker die van de assemblercode uitvoerbare binaire bestanden maken. Uiteraard blijft zowel de taal als de compiler volledig CPU-specifiek.

Waarom?

Vroeger: Assembler is de logische stap omhoog vanaf bytecode. Een dergelijke programmeeromgeving is noodzakelijk om een project van noemenswaardige omvang tot een goed einde te kunnen brengen.

Nu: Assembler raakt alsmeer in onbruik, maar er zijn nog omstandigheden waarin het nuttig en zelfs noodzakelijk kan zijn om assembler te gebruiken.

C-code wordt beschouwd als zeer snel uitvoerbare code, maar dezelfde code manueel geimplementeerd in assembler kan in sommige gevallen een grootorde sneller zijn. Dat komt omdat de C compiler zelf maar een computerprogramma is, dat in veel gevallen onnodige stappen zal ondernemen om simpele bewerkingen uit te voeren.
Het implementeren van CPU-specifieke drivers voor operating systemen vereist vaak dat de C code moet worden verlaten om de CPU in assembler aan te spreken.
Het optimaliseren van een project: veronderstel een programma waarbij uitvoeringssnelheid zeer belangrijk is. Heel vaak is de CPU gedurende 99% van de tijd bezig met het uitvoeren van 1% van de code. Indien precies dat stukje code geherprogrammeerd wordt in assembler, kan de uitvoeringssnelheid enorm verhoogd worden. Bekend voorbeeld is het computerspel Quake, dat de allereerste commerciele 3D-engine bevatte, maar ten tijde van de release te zwaar was om vlot te werken op een toenmalige PC. Dankzij assembler-optimalisatie kon de snelheid worden opgedreven tot een bruikbaar niveau.
Real-time toepassingen: omdat elke specifieke instructie gedefinieerd wordt door de programmeur en elke instructie een bekend aantal klokpulsen nodig heeft, kan er makkelijk bepaald worden hoeveel tijd er precies voorbij zal gaan tijdens het uitvoeren van een functie. Daarom is Assembler onmisbaar tijdens het creëren van een realtime systeem
CPU's hebben vaak specifieke instructies die bepaalde bewerkingen extreem kunnen versnellen (MMX, SSE, SSE2, 3DNOW!, enz.). Tenzij je beschikt over een zeer intelligente C compiler, worden die instructies niet altijd automatisch gebruikt door C code. In Assembler kies je zelf.

Eigenschappen?

Specifiek voor elke CPU
- Eenvoudiger voor RISC
- Complexer voor CISC
Abstractieniveau's:
- Assembler: Er wordt geen snelheidsverlies geboekt tegenover manueel opcodes invoeren, maar wel aan praktischheid gewonnen
- C: De snelheid loopt niet drastisch terug, maar programmeren wordt praktisch genoeg om zeer grote projecten te realiseren.
- Hogere Talen: Wordt door mijn collega's uitvoerig besproken, maar het volstaat om te zeggen dat hogere talen het werk van de programmeur enorm vergemakkelijken, ook al ligt de executiesnelheid vaak tientallen of honderden keer lager. (eg. Python, UML)
Voorbeeld: assemblertaal voor een Intel 8051 microcontroller

start           equ             4000h
stack           equ             07fh
cstack          equ             030h	                   ;lengte van de custom stack                                            
cstackp         equ             036h	                   ;de custom stack pointer                                               

                org             start
                mov             sp,#stack
                mov             tl0,#00101001b          ;41                                                                    
                mov             th0,#00000000b          ;reload waarde van timer                                               
                mov             tmod,#00000110b         ;timer0->8bit auto reload                                              
                mov             tcon,#00010000b         ;timer 0 opzetten                                                      
                mov             cstackp,#000h           ;cstackpointer op 0 zetten                                             
                lcall           initlcd
input:          jnb             p3.7,input              ;wachten op input                                                      
                inc             cstackp
                mov             a,cstackp
                lcall           outbytelcd
                mov             r0,#cstack              ;cstackpointer adres berekenen                                         
                mov             a,#cstackp
                add             a,r0                    ;het adres van de cstackpointer zit in de accu                         
                mov             r0,a                    ;het adres in de r0 zetten voor indirecte adressering                  
                mov             a,tl0                   ;de waarde van de laagste 8 bits van de timer in accu zetten           
                mov             @r0,a                   ;de waarde in de cstack zetten op plaats cstackp                       
                mov             r7,cstackp
                mov             r6,a
controle:       dec             r7
                cjne            r7,#000h,afdrukken
controle2:      mov             a,#cstack
                add             a,r7
                mov             r1,a
                mov             a,@r1
                cjne            a,006h,controle

Voor/nadelen?

Voor:

Snelheid: In theorie gebeurt er nooit een instructie te veel
Totale controle: De programmeur beslist zelf op welke plaats in het geheugen er iets wordt bijgehouden en welke machineinstructies hij gebruikt

Na:

Onhandigheid, wat na een tijd vermoeiend werkt voor de programmeur
- Zelfs simpele bewerkingen zoals het optellen van 2 getallen nemen vaak meerdere instructies in
- Geen mogelijkheid om elegante 'lussen' te schrijven, lussen gebeuren door goto-achtige instructies als DJNZ of CJNZ
Quasi-onmogelijk te beheren bij grote projecten: een hedendaags operating system kan nooit volledig in Assembler geschreven worden, niet zozeer door een tekortkoming in de taal, maar eerder door een tekortkoming van het menselijke verstand. Men kan namelijk niet op elk moment aan alles tegelijk denken.

Optimalisatie voor RISC-architectuur m.b.v. c

Johan Boeckx

Overzicht van RISC-architectuur

Vroeger werden de meeste programma's in assembler geschreven. Maar doordat de hardware geavanceerder werd gebruikten ontwerpers ook complexere instructies om het systeem ten volle te benutten. Vandaag worden de meeste programma's in hogere-orde talen geschreven, hierdoor is de complexe instructieset niet meer zichtbaar voor de programmeur. Als men de code gaat bekijken, gegenereerd door de compilers, dan ziet men dat er bijna geen gebruik wordt gemaakt van complexe instructies. De idee achter RISC-architectuur is dat de voorziening voor complexe instructies, die op zich maar een klein deel uitmaken van alle instructies, alle instructies gaat vertragen. De bedoeling is om te werken met kortere instructies die sneller kunnen uitgevoerd worden, liefst binnen één klokperiode.

Een eerste mogelijkheid om meerdere operaties per tijdseenheid te kunnen uitvoeren is om de individuele instructies sneller uit te voeren. Een andere mogelijkheid is om meerdere operaties parallel uit te voeren. Maar er zijn enkele beperkingen:

Sommige instructies vergen van nature uit meer dan één klokperiode zoals de vermenigvuldiging, deling, ... Een oplossing hiervoor is pipelining: de instructie wordt opgedeeld in meerdere instructies. Het resultaat zal beschikbaar zijn na een aantal klokperiodes.
Geheugen is traag. Om dit te compenseren hebben RISC-processoren hoge snelheid registers en een load/store architectuur. M.a.w. instructies zelf werken alleen met deze registers, enkel load/store-instructies werken met het geheugen. Tijdens zo'n instructie kunnen andere instructies uitgevoerd worden. Het is aan de compiler om het geheugen zo weinig mogelijk te gebruiken en indien het onvermijdbaar is om parallellisme te gebruiken.
Sprongen onderbreken de instructie "stroom"

Optimalisatiedoelstellingen

Optimaliseren voor RISC-architectuur is tot op zekere hoogte hetzelfde als optimaliseren voor om het even welke architectuur. Alhoewel dat er speciale aandacht moet besteed worden aan de "één instructie per klokpuls" doelstelling van RISC. De doelstellingen zijn:

elimineren van redundante berekeningen
de snelle registers optimaal gebruiken
loads/stores vermijden (zeker in lussen)
alle verwerkingseenheden optimaal gebruiken en de pipelines vol houden

Instruction-Scheduling Optimalisatie

De instructies zodanig herschikken zodat de hardware optimaal gebruikt wordt door:

langere operaties vroeger te starten, indien mogelijk. (Het laden van informatie uit geheugen, een vermenigvuldiging) Immers als de volgende instructie direct gebruik maakt van het resultaat van de vorige instructie, dan zal deze daarop wachten. Door de instructie naar voor te schuiven kunnen er parallel andere instructies uitgevoerd worden.
gebruik te maken van compaction om zo geen CPU tijd te verspillen. Compaction is het process om nuttige instructies al uit te voeren op het ogenblik dat de CPU idle zou zijn. (Bijvoorbeeld tijdens het laden van informatie uit het geheugen)
het vermijden van branch delays. Het zijn vooral voorwaardelijke sprongen die het principe van "één instructie per klokpuls" tegenwerken door het nagaan of er al dan niet voldaan is aan de voorwaarde.(Ze moeten dus wachten totdat de condition code gezet is.) Als de condition code tijdig gezet is, dan is er geen vertraging.
gebruik te maken van een branch prediction bit. Het wijzigen van de program counter en het herladen van het cache kan een vertraging met zich meebrengen. Dit kan opgelost worden door een branch prediction bit, er is dan alleen een vertraging als er fout gegokt wordt.
parallel programmeren: Sommige architecturen hebben meerdere verwerkingseenheden: de i80960CA heeft 1 REG side (execution unit) en 1 MEM side (address-generation unit). Opdat deze architectuur optimaal gebruikt zou worden moet de compiler de instructies afwisselen, daar waar mogelijk. (REG instructie gevolgd door een MEM instructie)
Register cycling: Normaal wordt er gebruik gemaakt van "Register coloring": een minimaal aantal registers gebruiken en registers hergebruiken als ze terug vrijkomen. De strategie van langere operaties vroeger te starten heeft meerdere mogelijkheden voor parallellisme als de registers niet direct terug gebruikt worden. Bij "Register cycling" gaat men het hergebruik van registers zo lang mogelijk uitstellen.

Lus-optimalisatie

Induction expression elimination: In de eerste lus moet het programma telkens het adres berekenen m.b.v. een vermenigvuldiging (een multi-cycle instructie). In de tweede lus, door gebruik te maken van een pointer, moet het programma alleen maar een som maken.

int a[GRENS][GRENS];
int i,j;
for (i=0; i<BOUND; i++)
    for (j=0; j<BOUND; j++)
        a[i][j] = 0;

/* De berekening van het adres moet bij elke iteratie van de lus gebeuren m.b.v. : adres(a) + GRENS * i + j */
/* Een vermenigvuldiging is een "multi-cycle"-instructie, daardoor wordt de lus trager. */

/* Door gebruik te maken van pointers kan men de code efficiënter maken (zie volgend voorbeeld) */

int a[GRENS][GRENS];
int i,j;
register int *p1;
for (i=0, p1=a; i<GRENS; i++, p1 += GRENS)
{
    register int *p2;
    for (j=0, p2=p1; j<GRENS; j++, p2++)
        *p2 = 0;
}

Register caching: Load en store operaties vergen veel tijd bij een RISC-processor. Door gebruik te maken van een snel register kan men n-1 loads en stores vermijden van de variabele som. Afhankelijk van de processor kan dit een groot verschil geven in performantie (zie screenshot & broncode).

som = 0;
for (i=0; i<n; i++)
    som += a[i];

register int temp;
temp = 0;
for (i=0; i<n; i++)
    temp += a[i];
som = temp;

Software pipelining: De herschikking van sommige instructies in een lus en het uitvoeren van enkele instructies voor de lus kunnen de performantie ervan verbeteren. In het volgende voorbeeld moet de store wachten op de multiply die op zijn beurt moet wachten op de 2 loads. Door een kleine herschikking kan de wachttijd van de multiply, met uitzondering van de eerste iteratie, drastisch verlaagd worden.

for (i=0; i<GRENS; i++)
    z[i] = x[i] * y[i];

/* In pseudo-assembler geeft dit */
i := 0 
loop:
  load  x[i]
  load  y[i]
  multiply
  store z[i]
  if (++i<GRENS) goto loop

/* na herschikking geeft dit */
i := 0 
  load  x[0]
  load  y[0]
loop:
  multiply
  load  x[i+1]
  load  y[i+1]
  store z[i]
  if (++i<GRENS) goto loop

Code efficiëntie optimaliseren

Inline functions: De compiler gaat alle verwijzingen naar deze functie vervangen door de code van de functie zelf. Door dit toe te passen moeten er geen sprongen gemaakt worden naar deze functie. Een nadeel is wel dat de code gedupliceerd wordt, dit is dus enkel nuttig bij korte functies.
Table lookups: Een switch-statement is een veelgebruikte techniek maar moet met zorg toegepast worden. Elke test en/of sprong kan kostbare verwerkingstijd in beslag nemen. Voor betere performantie is het best om de meest voorkomende gevallen eerst te plaatsen. Maar dit zal nog altijd geen verbetering betekenen voor de "worst-case time". Men kan het switch-statement vervangen door functie-pointers.

enum NodeType {NODE_A, NODE_B, NODE_C};
     
switch (getNodeType(  ))
{
    case NODE_A:
        .
        .
    case NODE_B:
        .
        .
    case NODE_C:
        .
        .
}

/* Dezelfde functionaliteit zonder switch */

int processNodeA(void);
int processNodeB(void);
int processNodeC(void);
     
/* Establishment of a table of pointers to functions. */
int (* nodeFunctions[])(  ) = {processNodeA, processNodeB, processNodeC};
     
.
.

/* The entire switch statement is replaced by the next line. */
status = nodeFunctions[getNodeType()](  );

Hand-coded assembly: De meeste c compilers genereren betere machinecode dan de gemiddelde programmeur. Maar een ervaren assembler programmeur kan voor bepaalde functies misschien beter werk leveren dan een compiler.
Register variables: Zoals reeds aangehaald bij Lus-optimalisatie kan het gebruik van het woord "register" de performantie van uw code verbeteren. Alhoewel dat sommige compilers het woord gewoon negeren. (vb.: register int)
Global variables: Het kan soms beter zijn om een globale variabele te gebruiken dan telkens de variabele door te geven via de functie. Zo kan men telkens een push/pop van de variabele op de stack vermijden. Anderzijds wordt het gebruik van globale variabelen wel afgeraden. Vooral voor de modulariteit van de functie en om de functie reentrant te maken.
Fixed-point arithmetic: Tenzij dat het platform een floating-point processor heeft, zal men een grote "straftijd" krijgen voor het manipuleren van float-data. Als het programma maar enkelen berekeningen moet maken kan het beter zijn om voor fixed-point berekeningen te kiezen.
Loop unrolling: In sommige gevallen kan het beter zijn om een lus te "ontrollen". Daardoor gaat men geen overhead meer hebben aan het begin en het einde van de lus.

for (idx = 0; idx < 5; idx++){
    value[idx] = incomingData[idx];
}	

/* na het "ontrollen" */

value[0] = incomingData[0];
value[1] = incomingData[1];
value[2] = incomingData[2];
value[3] = incomingData[3];
value[4] = incomingData[4];

Verminderen van code

Vermijden van standaard bibliotheken te gebruiken: Standaard bibliotheken zijn groot omdat ze alle mogelijke gevallen proberen te behandelen.
goto-statements gebruiken: Het gebruik van goto-statements wordt meestal afgeraden, maar ze kunnen vermijden dat er een ingewikkelde structuur moet opgezet worden om gedeelde code te gebruiken.

int functieDoeIets(void){
    /* Doe iets */
    ...

    /* Als er een probleem is opgetreden, stop */
    goto RUIMOP;

    /* Doe iets */
    ...

    /* Als er een probleem is opgetreden, stop */
    goto RUIMOP;

    ...

    /* In alle andere gevallen, alles is gelukt */
    return GESLAAGD;

RUIMOP:
    /* Opruim-code */
    return NIETGESLAAGD;
}

Conclusie

RISC-architecturen hebben een gesofistikeerde compiler nodig om de hardware optimaal te benutten.

In een zekere zin wordt de complexiteit verschoven van de hardware naar de software.

De technieken die gebruikt worden voor de optimalisatie kunnen ook voor andere architecturen gebruikt worden.

Hogere orde programmeertalen kunnen gemakkelijker zijn voor de programmeur, maar soms is het toch nog nodig om stukken code in assembler aan te passen om optimaal gebruik te kunnen maken van de hardware.

Object georiënteerd software ontwerp met c++ en Java

Floris De Smedt

C++

Inleiding

C++ is in de jaren 80 onstaan als een uitbereiding van C. De belangrijkste toevoeging is de mogelijkheid om object georiënteerd te programmeren. Net als C is het een sequentiële taal die kan gebruikt worden om embedded devices te programmeren. Men hoort wel is de bewering dat de toevoeging van de object oriëntatie de nodige overhead en programmagrootte met zich mee brengt. Ik ga hier dieper op ingaan en enkele voordelen/nadelen aanhalen die c++ heeft boven C.

Software matig

Wat C kan, kan ook in c++

C++ is een uitbereiding op C, wat betekend dat alles dat in C mogelijk is ook in c++ mogelijk is. Het is zelfs zo dat de vroegere embedded c++-compilers de c++ code eerst omzette naar het C equivalent, om hierna door een C-compiler verwerkt te worden als reguliere C code. Omdat beide talen zo weinig verschillen is het mogelijk om beide talen te combineren in 1 product, wat op korte termijn de risico’s die een taalverandering met zich mee brengt te vermijden. Op langere termijn is het gebruik van gemengde code echter niet aan te raden, omdat het zo moeilijk is om nog aan een object georiënteerd design te voldoen. Om aan te geven dat de performantie van een c++ programma zeer weinig verschilt van die van een C programma, ga ik in de volgende paragrafen enkele c++ voorbeelden aanhalen en hun equivalent in C.

function overloading

In c++ is het mogelijk om meerdere functies met dezelfde naam te gebruiken. Aan de hand van het type en het aantal argumenten kan de compiler bepalen welke functie er dient uitgevoerd te worden. Om een onderscheid te kunnen maken tussen de functies met dezelfde naam gebruikt de compiler een methode die gekend is als ’name-mangling’. Deze methode bestaat eruit om aan de hand van het type en aantal argumenten een verschillende naam te verzinnen voor de functie (iets dat in C door de programmeur zelf moet gebeuren). Door bij het oproep van een functie naar het aantal en type van de argumenten te kijken kan met dezelfde methode bepaald worden welke functie moet worden uitgevoerd.

File:Overloading2.jpg

In de figuur zie je een voorbeeld in c++ van function overloading (de functie “foo” is 2 keer gedefinieerd maar met een verschillend argument). De compiler zal voor beide functies een verschillende naam voorzien, zoals ’?foo@@YAHH@Z’ en ’?foo@@YAXPAU s@@@Z’. Bij het oproepen van de de functie foo kan er nu door te kijken naar het opgegeven argument beslist worden welke functie uitgevoerd zal worden.

klassen en member functions

Object oriëntatie is de mogelijkheid om de code op te delen in verschillende klassen en objecten. Dit is dus 1 van de belangrijkste elementen om te vergelijken met het C-equivalent. Eigenlijk kan een klasse gezien worden als een structure uit C die uitbereid is met functies (member functions). In object oriëntatie is het ook mogelijk om member functions af te schermen van anderen met keywords als ’private’, ’protected’ en ’public’ zodat de programmeur er zeker van kan zijn dat de klassen en objecten op de voorziene manier benaderd worden. Deze keywords zijn enkel een indicatie voor de compiler en zodoende zal een integer met het keyword ’public’ hetzelfde voorgesteld worden in machinecode als een integer met het keyword ’protected’ bijvoorbeeld.

In de figuur staat een programma met een klasse en een member function ’foo’ die de interne variabele gebruikt. Exact dezelfde machine code kan bereikt worden met het C-programma aan de rechter zijde. Hier is opzettelijk gebruik gemaakt van de variabele ‘this‘ omdat deze in c++ de verwijzing bevat naar het eigen object. Bij de omzetting van een klasse naar machine code zal elke member function voorzien worden van een argument die een verwijzing bevat naar het object waarop deze functie zijn taak moet uitvoeren. De interne variabelen van een klasse komen, zoals eerder vermeld, exact overeen met wat C in een struct bewaart.

constructor en destructor

De constructor en destructor zijn respectievelijk verantwoordelijk voor het initialiseren en verwijderen van een object. Bij het aanmaken van een object zal dus altijd de constructor opgeroepen worden. Het is dus belangrijk dat de constructor/destructor niet te complex is zodat bij het intensief aanmaken/verwijderen van objecten niet te veel tijd verloren gaat. Een constructor en destructor kunnen in C gezien worden als een functie die de variabelen voor gebruik juist zet of deze na gebruik weer vrij geeft. Door het gebruik van constructoren/destructoren voorkomt men initialisatie-bugs en geheugen lekken.

inline functions

Inline functions zullen door de compiler niet als een afzonderlijke functie gezien worden, maar terplaatse als machine code vertaald. Dit heeft als voordeel dat er een function call uitgespaard wordt in de uiteindelijk code. Als nadeel dient de code wel op elke plaats waar deze gebruikt wordt opnieuw naar machine code te worden in plaats van een gemeenschappelijke versie te gebruiken, elke keer deze code nodig is. Het gebruik van inline functions is dus enkel nuttig in gevallen waar de functie minder instructies inneemt dan het gebruik van een function call. Het kan gezien worden als een veiligere en uitgebreidere tegenhanger van macro’s in C.

Operator overloading

Naast het herdefinieren van functies is het ook mogelijk om operatoren een nieuwe betekenis te geven. Dit kan van pas komen als we bijvoorbeeld met klassen willen rekenen alsof het eenvoudige variabelen zijn (denk aan complexe getallen en dergelijke). Operator overloading kan in C gezien worden als een function call van een functie die een operatie uitvoerd met de argumenten. De betekenis van de geherdefinieerde operator moet niet overeenstemmen met de oorspronkelijke betekenis, zo doet de stream-klasse een herdefenitie van de ’<<’-operator om een string op de bouwen.

new en delete

new en delete komen respectievelijk overeen met malloc en free in C, al is er een essentieel verschil. Bij het uitvoeren van new zal altijd de constructor worden aangeroepen van de klasse waarvan een object aangemaakt wordt, en bij het gebruik van delete wordt altijd de destructor van de te verwijderen klasse uitgevoerd. Het is dus een veiligere implementatie omdat zo initialisatie bugs en geheugen lekken kunnen vermeden worden.

virtual functions

Een functie die virtual gemaakt is moet in een child klasse opnieuw geherdefinieerd worden. Dit heeft als voordeel dat deze functie vanuit de basis klasse kan worden opgeroepen zonder de interne structuur te kennen van de child klasse. In de figuur wordt een basis klasse A met een virtual function f() gedefinieerd. De klasse B erft van A en herdefinieerd de functie f() zodat deze een andere waarde terug geeft. In de main functie maken we een object van de klasse B aan, maken een pointer die naar een A-object wijst aan, maar laten deze verwijzen naar het object B. Als we nu de functie f() oproepen met behulp van deze pointer zal niet de functie f() uit de klasse A opgeroepen worden, maar die uit klasse B.

Om dit principe te laten werken wordt er gebruik gemaakt van een vtable. Dit is een array die een pointer naar elke geherdefinieerde functie bevat en die bewaard wordt voor elke klasse die virtual functions bevat. Bij het maken van objecten wordt er dan via een pointer verwezen naar de vtable van die klasse om zo de juiste functie op te kunnen roepen.

De aanwezigheid van virtual functions heeft enkele gevolgen op de grootte van de uiteindelijke code omdat er gebruik moet worden gemaakt van de vtable:

Het object wordt groter omdat er een extra pointer nodig is naar de vtable. Voor een groot object zal die extra 4 bytes waarschijnlijk niet het verschil maken, maar er bestaan ook objecten van 1 byte groot, bij het toevoegen van een pointer wordt dan de grootte van het object al 5 bytes groot, wat dus wel een heel verschil maakt.
Bij het oproepen van een functie uit de vtable moeten er 2 geheugen lezingen gebeuren in plaats van 1. Eerst moet het adres van de functie worden gehaald uit de vtable, en daarna pas kan de function call naar de eigenlijke functie plaats vinden. Maar deze extra geheugen lezing vraagt niet meer recources als een extra parameter aan een functie toe te voegen, dus ook dit nadeel is vrij hard te verwaarlozen.
Als laatste nadeel is er nog de klasse grootte. Omdat elke klasse met virtual functions voorzien wordt van een vtable die pointers naar de functies bevat, is het essensieel voor de linker dat deze pointers ook een geldig doel hebben. Daarom zal elke virtuele functie worden opgenomen in de resulterende machine code, ook als deze niet gebruikt wordt in de toepassing.

Hardware matig

Heap gebruik

Door de encapsulatie die in c++ aanwezig is, wordt er meer gebruik gemaakt van de heap. In C is het mogelijk om een programma te ontwikkelen waar geen enkele aanroep van malloc of free gebruikt wordt. Doordat c++ met klassen en objecten werkt is het gebruik van new en delete onvermijdelijk gezien het veelvoudig gebruik van constructoren.

Het gebruik van ROM geheugen

In C kan door de compiler eenvoudig statische data worden vastgelegd die in goedkoop ROM geheugen kan bewaard worden. Dit is echter moeilijker bij c++ omdat de meeste klassen voorzien zijn van een constructor die de waarde van de interne variabelen wijzigt. Door gebruik te maken van opstartcode die een constructor met op voorhand vastgelegde data oproept is het echter mogelijk objecten toch in ROM geheugen te bewaren. Deze opstartcode neemt wel meer plaats in dan de static initializer die in C gebruikt kan worden zou innemen. Om een object in ROM te kunnen bewaren moet voldaan worden aan volgende verreisten:

Er mag geen basis klasse zijn
Er mag geen constructor zijn
Er mogen geen virtuele functies zijn
Er mag geen gebruik worden gemaakt van private of protected members
Elke interne klasse moet over dezelfde voorwaarden beschikken

Met deze voorwaarden wordt het echter moeilijk om aan goede encapsulatie te voldoen, en bestaat de mogelijkheid tot fout gebruik van de klasse. Zo kan er een object van de klasse aangemaakt worden dat niet constant is of niet is geinitialiseerd. Als oplossing voor dit probleem gaat men meestal de klasse die men in ROM geheugen wil bewaren in het private gedeelte van een andere klasse zetten. Als we dan ook nog de te gebruiken instanties van die klasse in het private gedeelte opnemen, kunnen we toch een gecontroleerde interface voorzien naar deze instanties. De uitwendige klasse moet immers niet voldoen aan de stricte voorwaarden van een klasse/object dat in ROM geheugen moet geplaatst worden.

Java

Van Java naar embedded java

Java wordt vooral veel gebruikt voor zijn overdraagbaarheid naar andere platformen. Dit is grotendeels te danken aan het gebruik van een virtual machine die als een laag functionneerd tussen de java-code en de ISA-code (Instruction Set Architecture). Omdat het gebruik van een virtual machine de nodige recources met zich mee brengt wordt hier geen gebruik van gemaakt voor embedded software. We gaan dus net als bij C of C++ rechtstreeks naar een instructieset omzetten die verstaanbaar is voor de hardware.

Java wordt meestal gebruikt voor het ontwikkelen van java-applets, en de mogelijkheid tot het gebruikt van geluid, afbeeldingen, ... moet dus voorzien worden. Dit is echter niet nodig voor het gebruik van embedded software. Omdat de onderliggende hardware goed gekend is kan er een perfecte selectie gemaakt worden uit de libraries. Zo kunnen al de overbodige functies wegblijven uit de gegenereerde machine code. Maar op dit vlak is er geen verschil met C of c++.

Waarom embedded java gebruiken

Het grote voordeel dat java heeft ten opzichte van andere talen is dat er een standaard voor multithreading en data synchronisatie is ingebouwd. In C is het ook mogelijk gebruik te maken van multithreading door functies uit een onderliggend besturingssysteem aan te spreken. Deze besturingssystemen zijn echter verkoper specifiek en er is geen globale standaard voor deze functies gedefinieerd. Dit maakt de overdraagbaarheid naar andere systemen van de code zeer moeilijk. In java is dit opgelost door de standaard te implementeren op broncode-niveau. Er is echter nog altijd een onderliggend besturingssysteem nodig om hier gebruik van te maken.

Een embedded applicatie werkt meestal op basis van binnenkomende data/interupts die onmiddelijk dienen verwerkt te worden. Het systeem is dus opgebouwd uit een samenwerking van verschillende threads die elk hun eigen taak te vervullen hebben. Hier heeft java dus een zeer groot voordeel omdat het gebruik hiervan al is ingebouwd in de taal zelf.

Momenteel beginnen er meer en meer besturingssystemen die zowel C als java code ondersteunen op de markt te komen. Dit stelt, net als bij c++, de mogelijkheid om beide talen te mengen tijdens een overgangs fase. Ook hier is het echter niet aan te raden dit op lange termijn te doen doordat de ingebouwde beveiliging van java dan niet meer kan gegarandeerd worden. Zo denk ik aan de pointer die in C bestaat en die naar eender welk type gegeven kan wijzen. Deze is speciaal uit java weggehouden om fouten te vermijden. Door beide talen door elkaar te gebruiken kan java niet meer garanderen dat dergelijke fouten vermeden worden. Een ander voordeel van de besturingssystemen is dat deze transparant zijn voor het aantal CPU’s in het systeem. Zo kan dezelfde code gebruikt worden op een systeem dat over meerdere CPU’s beschikt doordat het aantal ingevoerde gegevens is verhoogd ten opzichte van een eerdere versie.

Conclusie

C++ heeft veel voordelen door de implementatie van onder andere object oriëntatie die tot een beter begrijpbare code kunnen leiden. Dit voordeel weegt veel harder door dan het nadeel dat de grootte van de executable groter kan worden door het gebruik van virtual functions. Java heeft dan weer zeer grote voordelen door de ingebouwde standaard voor multithreading in de taal. Er is echter een onderliggend besturingssysteem nodig om van deze functionaliteit gebruik te maken, java code zal dus eerder zijn nut bewijzen in complexere embedded systemen.

Model-Based Design en UML

Hans Van Beneden

Wat?

Bij model based design maken we gebruik van software tools om een virtueel model te creëren. Door de resultaten van simulaties te vergelijken met de requirements kunnen we reeds in een zeer vroeg stadium fouten in het design ontdekken. Vervolgens kunnen we door middel van automatische codegeneratie code genereren voor processoren, PLC’s, FPGA’s…

Waarom?

De taak van een ontwikkelaar van embedded systemen wordt steeds moeilijker; embedded systemen moeten niet alleen performanter zijn als vroeger maar ze mogen ook steeds minder verbruiken. Meer functionaliteit moet op een kleinere ruimte komen en dit moet steeds sneller en goedkoper gebeuren. Een embedded systeem ontwikkelen bevat twee verschillende zeer complexe zaken; software design en hardware design. Een juiste verhouding tussen deze twee kiezen is cruciaal, zeker wanneer we weten dat een foute keuze achteraf een hele boel problemen met zich meebrengt.

Traditioneel ontwerp

Bij traditioneel ontwerp is er een duidelijke scheiding tussen de hardware en de software, deze scheiding wordt voorgesteld door een hardware/software interface. Deze interface is een document met de specificaties van het embedded systeem, er staat in welke functionaliteiten de hardware en de software moeten bieden. Samen met dit document wordt ook het evenwicht tussen hardware en software vastgelegd. Als de hardware/software interface vastgelegd is gaan hardware en software ingenieurs afzonderlijk werken aan hun deel van de implementatie. Na lang werk kunnen de twee delen samengevoegd worden en bekomt men een prototype. De kans is echter zeer groot dat dit prototype niet naar behoren werkt vermits de hardware/software interface vaak een moeilijk te begrijpen document is dat vrij geïnterpreteerd kan worden. Hierdoor is een herontwerp van het prototype nodig, wat een zeer kostbare operatie is.

Model-Based Ontwerp

Model-based design biedt een ontwikkelomgeving aan waarin ontwikkelaars één enkel model geburiken voor het hele ontwikkelproces. De ontwikkelomgiving kan gebruikt worden voor data-analyse, model visualization, testing & validation tot zelfs de product deployment met of zonder automatische code generatie. Aan de hand van de specificaties wordt een model gemaakt, dit model is een volledig testbaar geheel dat opgedeeld is in verschillende blokken. In Simulink wordt dit model de "executable specification" of "the golden reference" genoemd, voordelen van dit model zijn:

Er moeten geen specificaties meer op papier gezet worden, het hardware/software interface document gebruikt bij het traditionele ontwerp is vrij interpreteerbaar en zorgt voor veel fouten.
Simulatie is mogelijk vanaf het begin, dus fouten kunnen rap opgespoord worden

Oorspronkelijk houdt dit model geen rekening met beperkingen die opgelegd worden door de hardware, deze worden later toegevoegd. Elke keer als een extra beperking toegevoegd wordt, wordt het model opnieuw getest en nagekeken of de resultaten nog steeds aanvaardbaar zijn. Wanneer de executable specification geoptimaliseerd is voor een bepaald embedded device kunnen Hardware ontwikkelaars beginnen aan de ontwikkeling van de HDL. Dit kan gebeuren door alles zelf te codeern of door middel van automatische code generatie. In bijde gevallen zullen de ontwikkelaars hun resultaten vergelijken met de resultaten van het oorspronkelijke model.

Eigenschappen

Het hele systeem wordt voorgesteld door middel van blok-diagramma's en toestands-diagramma's.
Door middel van simulaties kunnen ontwerpkeuzes geëvalueerd worden en de performantie getest worden.
Software (c-code) en hardware (VHDL) kunnen automatisch gegenereerd worden.
Deployment en Real-time testen worden geondersteund.

Voor/nadelen

Voordelen

De globale tijd om een toepassing te ontwerpen wordt aanzienlijk ingekort
Men kan fouten in het oorspronkelijk design veel vroeger opsporen
Simulatie van het design is veel sneller mogelijk dan bij HDL simulaties .
Een fundamentele wijziging kan véél sneller uitgevoerd worden.
Hardware keuze kan zo lang mogelijk uitgesteld worden.
Menselijke fouten bij de vertaling van het model naar C-code worden vermeden.
Er blijft een koppeling tussen de uiteindelijke productiecode en de high-level specificatie van het algoritme, de oorspronkelijke requirements en de testprocedures.
Het model kan rechtstreeks gebruikt worden als testbench, er moeten dus geen testbanken meer geschreven worden in een HDL.
Mogelijkheden voor software reuse zodat ontwerpen snel, effectief en betrouwbaar geüpgrade kunnen worden

nadelen

De verandering van het traditionele ontwerp naar een nieuwe manier van ontwerpen kan ontwerpers afschrikken.
Bedrijven moeten investeringen doen om nieuwe de software tools aan te kopen en hun ontwerpers bij te scholen
Automatische code generatie zorgt vaak voor overhead

Besluit

Model-Based design geeft ontwikkelaars de kans om het design-proces te verkorten doordat ze fouten eerder kunnen opsporen. Je kan reeds zeer vroeg simulaties uitvoeren en de keuze van het type hardware kan uitgesteld worden tot het laatste moment.Ontwikkelaars die alle voordelen van model-based design gebruiken moeten, door de code-generatie, zelfs niet eens meer kunnen programmeren

Real-Time

Wat is Real-Time?

Michael Van den Broeck

Inleiding:

Real-Time of tijdsgarantie! We spreken over Real-Time als een inputsignaal op een gegarandeerde(=vooropgestelde) tijd reageert! Dit betekent dat er van tevoren bepaald kan worden in wat voor tijd bepaalde taken/functies/acties uitgevoerd (kunnen) worden.

Concreet

De juiste acties uitvoeren in de juiste tijd. Men zegt soms: Realtime vereist een snelle computer! Dit is een FABEL! Nergens in de RealTime definitie staat dat zaken snel moeten gebeuren. Bijvoorbeeld: een boot die met een snelheid van 25 knopen de oceaan over vaart heeft genoeg aan een positie bepaling van 1 berekening per seconde.

Voor realtime toepassingen is eerder een nauwkeurig systeem nodig! Dit maakt het voorspelbaar en vaak ook betrouwbaar.

Wanneer spreken we van Real-Time?

"Een goed antwoord te laat is net zo fout als een fout antwoord op tijd" vertelt LINUX, die goed op weg is in embedded en Real-Time systemen. Aan de hand van het volgende voorbeeld wordt dit duidelijk:

Een remcommando bij een onbemand voertuig. Als de voorganger te dicht in de buurt komt, moeten we snel remmen. Als het remcommando te laat komt zitten we in de kreukelzone van onze voorganger. De actie “remmen” was juist, maar te laat, met schade als gevolg. Niet alleen snel remmen is van levensbelang, maar ook de garantie dat er altijd snel genoeg geremd wordt.

Wanneer een systeem tijdsgaranties kan geven, noemen we het systeem Real-Time.

Aan de volgende criteria moet voldaan worden:

Gegarandeerde tijdsinterval waarop de applicatie processortijd krijgt
Een gegarandeerde minimale hoeveelheid rekentijd
Er mogen in bovenstaande geen onderbrekingen (Interrupts) plaatsvinden

Hieruit besluiten we:

De applicatie moet een vast aantal malen per seconde rekentijd krijgen, en deze rekentijd moet een minimale tijdsduur hebben.

Voor welke toepassingen is dit nodig?

Proces-controle:

Door controle van een klep, een gelijke stroming in een pijpleiding realiseren

Productomgeving:

Mechanische tuigen, automatisering, volledige productieproces, ...

Communicatie, bevel en controle:

Automatische bediening van medische toestellen, luchtverkeer controle, bankoperaties per terminal

Industrieel ingebed computersystemen

Directe interface met de fysische wereld
Sensoren die op regelmatige tijdstippen data produceren
Een lijst van informatie, ingrijpbaar en bijgehouden op een gegevensbank

Een voorbeeld in Embedded systemen

Communicatiesysteem in een auto

Zeer complex
Goedkoop
Zware Real-Time vereisten
Laag vermogen verbruik
Moet zeer flexibel zijn, open staan voor nieuwe toepassingen

We kunnen besluiten dat Embedded systemen tegenwoordig ook niet allemaal meer "echt" realtime zijn, maar dit proberen op een andere manier te bereiken (bv. time-slicing, wat zoveel wil zeggen als tijd opdelen en toekennen aan een taak/functie/actie).

Verschillende soorten Real-Time?

Men onderscheidt 3 soorten van Real-Time die in deze figuur afgebeeld zijn. De tijdsgarantie is een punt op de t-as. Langs de y-as staat QoS (=Quality of Service). Merk op dat in de figuur bij soft realtime de QoS weliswaar niet aangetast wordt bij overschrijding van de deadline, maar dit moet wel gecompenseerd worden door bijvoorbeeld ook een aantal keren vóór de deadline iets af te handelen, waardoor gemiddeld de deadline gehaald wordt. In de figuur is dit aangegeven met een grijs gebied.

Hard Real-Time:

de tijdsgarantie(deadline) absoluut gehaald worden

Firm Real-Time:

de tijdsgarantie moet gehaald worden.
Indien niet? Functioneert het systeem ondermaats

Soft Real-Time:

de tijdsgarantie mag nu en dan overschreden worden zonder dit als fataal of slecht functioneren wordt aangemerkt

Wat gebeurt er indien de deadline wordt gemist:

Het systeem faalt: Hard Real-time
De waarde van het resultaat vermindert: Soft Real-Time
Het resultaat heeft geen waarde meer: Firm Real-Time

Toepassing Hard, Firm en Soft Real-Time:

Hard Real-Time:

een peacemaker die op het juiste moment een puls moet afgeven

Firm Real-Time:

Controlesysteem

Soft Real-Time:

Mp3-speler

Conclusie

Op de juiste manier omgaan met tijd:

Respontie tijd is van groot belang

Deadlines moeten in alle omstandigheden gehaald worden

Worst-case moet gekend zijn
Voorspelbaarheid

Taal en systeem moeten toelaten om tijd en deadlines te specifiëren

Interrupt-gebaseerd RT-systeem

Wannes Geysen

Introductie

Events zijn zeer belangrijk in embedded systemen. Zonder exceptions zou het ontwerpen van systemen een zeer complexe taak zijn. Met deze exceptions kunnen we bugs in het systeem, fouten in geheugentoegang opsporen. En we kunnen het programma debuggen door bepaalde breakpoints in het programma te plaatsen.

Wat is een event?

Een event is iets dat de aandacht nodig heeft van een embedded systeem. Wanneer een event gebeurt in de echte wereld moet een embedded systeem dit herkennen en gepast op reageren binnen een bepaalde tijdsspanne.

Door het feit dat systemen steeds complexer worden, hebben we systemen met meerdere bronnen van interrupts. Daarom is een afhandelingsschema van interrupts nodig om de verschillende manieren van afhandelen te bepalen. Er kunnen ook prioriteiten toegekend worden aan verschillende interrupts. In sommige gevallen kunnen we geneste afhandeling van events nodig hebben.

Is een signaal hetzelfde als een event? De termen event, signaal, interrupt en exception verwijzen allemaal naar hetzelfde: er is iets gebeurt en daar moet op gereageerd worden door het systeem.

Wat doet de microprocessor als bij een exception?

De microprocessor stopt de programma-thread die momenteel aan het draaien was. En schrijft de huidige registers (current program status register en program counter) weg naar de stack. Daarna start het de volgend programma thread die de exception afhandelt.

Enkele interrupt afhandelingsschema’s:

Ongeneste interruptafhandeling

Dit is de gemakkelijkste interrupt handeler. Alle andere interrupts worden uitgeschakeld totdat de main thread terug actief wordt. Dus slechts 1 interrupt kan worden behandeld per keer. Dit is ook waarom dit schema niet gebruikt kan worden voor complexere systemen die waarschijnlijk meer dan een interrupt bron hebben. Voordelen: - gemakkelijk te implementeren

Nadelen: - niet geschikt voor complexe systemen

Prioritized simple interrupt handling

Bij deze manier van interruptafhandeling kunnen meer dan een interrupt tegelijk worden afgehandeld. Hiebij kan de code die een exception afhandelt onderbroken worden door een andere exception met hogere prioriteit. Dit verhoogt de complexiteit van het systeem. Het schema moet zorgvuldig ontworpen worden omdat telkens weer de context opgeslagen en opgeroepen moet worden. En het opslaan van de registers of het ophalen van de registers mag niet onderbroken worden door enige exception. Hierdoor zou er data verloren kunnen gaan en kan de context niet meer hersteld worden. Het nadeel van dit systeem is dat er meer initialisatie code vereist is bij het opstarten omdat de prioriteit level tabel opgesteld moet worden voordat het systeem aangeschakeld kan worden.

asynchroon vs synchroon

synchrone exceptions gebeuren door dingen die het systeem zelf doet. Asynchrone exceptions worden opgeroepen als gevolg van iets dat iemand anders deed.

Synchrone exception treden meestal op bij fouten. De twee meest voorkomende exceptions zijn ‘divide by zero’ en ‘bus error exception’ In beide gevallen stopt de microprocessor de huidige thread en wordt de thread opgeroepen die de exception zal afhandelen.

Een asynchrone exception gebeurt wanneer een thread onderbroken wordt door een externe gebeurtenis. Deze exception wordt meestal een event genoemd. Een bekend voorbeeld hiervan is de I/O interrupt. De huidige thread heeft geen idee wanneer de data zal aankomen of verzonden worden van een van de I/O poorten. Dus de running thread loopt gewoon door en doet zijn ding totdat het event plaatsvindt.

hoe worden interrupts gegenereerd De meeste microprocessoren hebben een speciale input pin of pinnen die gebruikt wordt door externe hardware Exception proriteiten Omdat verschillende exceptions simultaan kunnen optreden moet de processor voor elke exception een prioriteit hebben. Zo kan het beslissen welke van de opgetreden exceptions de belangrijkste is en dus eerst afgehandeld moet worden.

Link register offset

Het link register wordt gebruikt om de program counter terug te zetten naar de plaats in het geheugen waar de main thread mee bezig was toen het onderbroken werd. Het link register wordt aangepast op basis van de huidige program counter waarde en op basis van het type van de exception. In sommige gevallen moet er bij de program counter 1 bij geteld worden zodat het naar de volgende instructie wijst. (Dit is in het geval bij een algemene Interrupt) In andere gevallen moet de program counter juist verlaagd worden zodat enkele vorige instructies herhaald worden. (zoals bijvoorbeeld bij een exception waarbij de nodige data niet aanwezig is. Dan moet de thread even wachten en daarna opnieuw kijken of de data nu wel aanwezig is)

Programming for interrrupts

De meeste embedded systemen moeten in Real Time werken. Ze moeten op externe events reageren binnen een vaste tijd. Er zijn verschillende mannieren hoe dit geïmplementeerd kan worden.

De code kan geschreven worden in een grote lus. Die gaat continue inputs en outputs controleren. Voor een simpel systeem is dit een goede oplossing. Voor complexere systemen is het minder gepast. De code wordt minder leesbaar en helemaal niet onderhoudbaar. Bij complexere systemen kan deze lus zeer groot worden en kan het lang duren voor de lus rond is. Hierdoor worden de tijd voordat een input behandeld wordt groot.

Een tweede manier kan geïmplementeerd worden als twee lussen waarbij de controle over het systeem steeds uitgewisseld wordt tussen de twee (co-routines). Dit zorgt voor een meer leesbare code die sneller reageert. Deze methode is een eerste stap richting de implementatie van een Multi-tasking schema.

Een Multi-tasking systeem laat toe dat de code is opgedeeld in een aandtal discrete programma’s die schijnbaar tesamen lopen. Dit model wordt gebruikt bij complexere systemen waar de functionaliteit opgedeeld is in verschillende processen. Hierbij kan elke programmeur apart werken aan zijn gedeelte van het totale systeem.

Een systeem dat niet zo stipt moet verlopen kan gebruik maken van een lus waarbij de input/output geregeld wordt door interrupts.

Interrupts opzetten

Bij het schrijven van interrupts in software zijn er drie aspecten: - interrupt service routine - interrupt vector - initialisatie en activeren van interrupts

interrupt service routine

dit is de code die uitgevoerd wordt als gevolg van een event. Deze code is gelijkaardig met een functieoproep in C behalve voor twee voorwaarden: 1. ISR moet de context opslaan van de code die aan het lopen was en deze terug plaatsen wanneer de ISR is afgelopen 2. Op het einde van de ISR moet een “return from interrupt” opgeroepen worden.

Voorbeeld: Interrupt void alpha() { indate = device_data; device_control = 0x80; ei(); }

deze ISR is een void functie zonder argumenten.

Interrupt vector

De meeste microprocessoren ondersteunen meerdere interrupts. Meestal worden de verschillende ISR voor de interrupts opgeslagen in een vector. In C is dit een araay van pointers naar functies.

Initialisatie

Het is meestal nodig om de I/O devices te initialiseren. Dit houdt meestal niet meer in dan enkele registers bepaalde waardes te geven.

De meeste microprocessoren moeten interrupts geactiveerd worden door het uitvoeren van een “enable interrupt” commando. In C kan dit gedaan worden door een functie op te roepen uit een bibliotheek. Of door een wat inline assembler code in te voegen.

RTOS

Scheduling van Taken

Ive Billiauws

Inleiding

In een real-time systeem moeten we de garantie hebben dat bepaalde resultaten binnen een vooraf opgelegde tijd afgeleverd worden. De tijd die een applicatie hiervoor nodig heeft, hangt van vele factoren af en een belangrijke factor hierbij is de toegewezen CPU-tijd. Het is belangrijk dat de ontwerper “de ideale volgorde” vindt voor het uitvoeren van de verschillende activiteiten van de applicatie, zodat elk van deze activiteiten afgewerkt zijn binnen hun deadlines. De ontwerper kan dus een set van regels opstellen die we een scheduling algoritme noemen.

Vroeger ging met op een meer heuristische manier zulke algoritmes ontwerpen en hen daarna uitgebreid testen. Voor bedrijven die vaak gebruik maakten van real-time systemen (bv. Department of Defense) volstond deze kunstelige manier van algoritmeontwerp niet. Daarom is de laatste 25 jaar veel geld gepompt in het onderzoek en ontwerp van scheduling algortimes om ze toch een meer wetenschappelijke basis te kunnen geven.

RTOS Scheduling

Algemeen kan men twee grote soorten van scheduling onderscheiden: time based en priority based.

Time Based Scheduling

Bij time-based scheduling wordt aan elke taak een time slice gegeven. Als de taak zijn toegewezen tijd heeft opgebruikt, moet ze wachten tot er een nieuwe time slice voorzien wordt. Nadeel hierbij is dat er altijd rekening moet gehouden worden met de worst-case scenario's. Men kan dus geen nuttig gebruik maken van de less-than-worst-case scenario's.

Priority Based Scheduling

De meeste RTOS gebruiken echter een priority based, preemptive scheduler. Het worst-case scenario bij dit type komt voor als een bepaalde taak van hoge prioriteit de CPU enorm lang opeist. Hierdoor zullen taken van lagere prioriteit eindeloos lang moeten wachten op wat CPU-tijd. Dat wordt starvation genoemd. Dit valt echter op twee manieren op te lossen:

De taken worden op dezelfde prioriteit gebracht als de tijd-consumerende en de scheduler onderbreekt de tijd-consumerende taak op geregelde intervallen om zo andere taken CPU-tijd te gunnen.
Een beter alternatief is het voorzien van een sleep-commando. Hiermee zal de tijd-consumerende taak zelf op niet-kritieke momenten zijn CPU-tijd kunnen afgeven.

Men kan priority based scheduling nu op twee manieren gaan indelen:

Statisch/Dynamisch: Bij statische-prioriteitalgoritmes liggen de prioriteiten van de verschillende taken vast. Dit geeft een zeer beperkte flexibiliteit, maar de complexiteit van de scheduler blijft hierdoor ook gering. Hierbij kunnen de prioriteiten vastgelegd worden bij het compileren (off-line) of tijdens run-time (on-line). Nadelen van dit type is hun laag processorgebruik en hun slechte afhandeling van aperiodische taken. Bij de dynamische algoritmes gebeurt de prioriteitbepaling uitsluitend on-line. Tijdens run-time kunnen de verschillende priotiteiten aangepast worden afhankelijk van deadlines, starvation, ... Hierdoor zijn we veel flexibeler. Zij kunnen dus ook beter overweg met aperiodische taken.
Preemptive/Non-preemptive: Een preemptive scheduler biedt de mogelijkheid om de uitvoering van een taak te laten onderbreken door een taak van hogere prioriteit om deze achteraf weer voort te zetten alsof er niets gebeurd is. Bij een non-preemptive scheduler is deze mogelijkheid niet aanwezig.

Problemen bij scheduling

Naast het tijdsgedrag van applicaties moeten we voor het selecteren van het juiste algoritme ook rekening houden met het onderliggende OS. Want het kan voorkomen dat door de applicatie een system-call wordt opgeroepen die bv. memory gaat alloceren/dealloceren en die dus een vastgelegde tijdsduur heeft. Hierdoor zal het enorm moeilijk worden om op een betrouwbare manier te schedulen. Een tweede probleem komt voor als het OS een te beperkte system-call set heeft. Hierdoor zal regelmatig een groep system-calls gecombineerd worden, waardoor de tijdsduur wederom moeilijk te voorspellen valt.

Als een applicatie slecht ontworpen is, kan die ook problemen veroorzaken die schedulingalgoritmes verstoren. Een goed voorbeeld hiervan is priority inversion:

Een taak van lage prioriteit alloceert geheugen en krijgt de semafoor van deze gedeelde datastructuur.
De taak wordt geinterrupt en een taak van hoge prioriteit. De nieuwe taak probeert het geheugen aan te spreken, maar het is nog altijd gelocked. De taak wordt gesuspend en de vorige taak begint terug.
Een taak van middelmatige prioriteit neemt de CPU over omdat de eerste taak van lage prioriteit is en de tweede taak gesuspend is. De taak van hoge prioriteit staat dus eigenlijk op gelijke prioriteit met de lage. Dit is priority inversion.

Voorbeelden van Scheduling algoritmes

Er zijn reeds een aantal algoritmes ontworpen die toelaten een juiste schatting te geven van de benodigde rekentijd van een real-time applicatie. Twee van de bekendste zijn Rate Monotonic en Earliest Deadline First:

Rate Monotonic Scheduling

Als een applicatie bestaat uit een set van periodische taken met een vaste uitvoeringstijd, dan kan RMS een goede scheduling garanderen. Het RMS-algoritme zegt dat hoe frequenter een taak voorkomt, hoe hoger zijn prioriteit is. Alle instanties van een taak hebben dus dezelfde prioriteit. Dit is een voorbeeld van statische scheduling.

Earliest Deadline First

Als we te maken hebben met zowel periodische als aperiodische taken of met taken met variable uitvoeringstijd, kan beter het EDF-algortime gebruikt worden. Hierbij hebben de taken met dichtstbijliggende deadline de hoogste prioriteit. Dit is een voorbeeld van een dynamisch schedulingalgoritme. Want als er tijdens het uitvoeren van een taak, een nieuwe taak bijkomt die een korterbijliggende deadline heeft, dan zullende de prioriteiten van alle taken veranderen omdat deze laatste eerst moet uitgevoerd worden. Best wordt hierbij ook nog pre-emption toegepast, zodat de taak in uitvoering onderbroken kan worden en de nieuwe taak kan voordringen.

Mutuele exclusie

Joris Willems

Inleiding

Mutuele exclusie, beter gekend als Mutual Exclusion, Mutex afgekort gaat gebruikt worden bij processen. Als er meer dan 1 proces dezelfde variabele of geheugen wilt gebruiken dan zullen we er moeten op toezien dat de processen niet gelijktijdig gebruiken maken hiervan. We moeten dus bij het gebruik van globale variabele gaan bepalen welk proces deze mag schrijven en lezen. Een probleem dat kan ontstaan is het bekomen van DEADLOCK. Neem een kijkje naar het voorbeeld en aan de hand hiervan gaan we uitleggen waarom we Mutual Exclusion nodig hebben.

void echo() {

IEEE802.11n   chin =  getchar():
   chout = chin;
   putchar(chout);

}

In het voorbeeld programma gaan we dus met 2 processen werken, elk proces gaat willen inlezen van het toetsenbord. We beginnen met proces 1, deze gaat een x inlezen in de chin variabele. Dan gaan we deze naar de uitgang zetten, op het moment dat in de chout de waarde zit, gaat proces 2 aan de beurt komen. Deze zullen we de nieuwe waarde Y inlezen. En vervolgens dit uitvoeren. Dus we printen de Y af op de terminal. Dan gaan we terug naar proces 1, en gaan we NOG eens de Y afdrukken. Dit moeten we dus voorkomen, en gaan we doen met behulp van de Mutex.

Veschillende manieren + werkingsprincipe

Er zijn verschillende manieren van werken, we hebben de keuze uit Hardware of Software oplossing. Hieronder gaan we dieper ingaan op de verschillende manieren die er zijn.

Hardware

Disabele van interrupts

Bij het disabele van de interrupts, gaan we als we het belangrijkste stuk van de code uitgevoerd wordt, de interrupts uitschakelen om te voorkomen dat tijdens het kritische stuk van de code, er een onderbreking zal zijn. Dit heeft als voordeel dat het enorm eenvoudig is in gebruik, maar heeft wel als nadeel dat als je dan een interrupt krijgt tijdens dat deze uitgeschakeld is dat die niet kan verwerkt worden. Dus daarom moeten we ervoor zorgen dat de tijd dat we de interrupts uitschakelen niet te lang duurt. Want dit zal ons systeem negatief beinvloeden.

Spinlock

Bij de Spinlock gaan we gebruik maken van een Flag. Deze flag gaan we dan gebruiken om te bepalen welke van de processen dat in de kritieke sectie terecht komt. Het voordeel van dit is dat we wel een grote controle hebben over het geheel. Als de Flag gecleared wordt dan zullen de andere processen weten dat ze gebruik kunnen maken van de kritieke sectie. Dit heeft als voordeel dat het makkelijk te implementeren is, en dat de interrupts niet moeten worden uitgeschakeld.

Software

Deckers Algoritme

Het Deckers algoritme is ontworpen door de heer Theodorus Jozef Dekker in 1964. Dit algoritme was opgebouwd in verschillende pogingen. Uiteindelijk was de 4de poging de juiste poging. In dit algoritme willen we dat de processen de staat van elkaar kennen. Dit doen we door middel van het gebruik te maken van een Flag variabele. Deze flag kan je bekijken als een array. De nummer van de flag word gezegt door de nummer van het proces. vb : Als proces 1 bezig is, deze gaat dan flag[1] op true zetten als het proces in zijn kritieke sectie zit. Als we daar niet in zitten, zal deze flag op false staan. Als proces 2 bezig is, gaat deze dan flag[2] op true zetten. Vervolgens gaan we moeten bepalen welk proces de mogelijkheid krijgt om in zijn kritieke sectie te gaan. Deze wordt dan bepaald door een variabele met de naam turns. Als de variabele turns gelijk is aan de nummer van het proces, mag het proces zijn kritieke sectie ingaan, enkel als de andere processen niet in de kritische sectie zitten. Dus als de turn gelijk is aan de nummer van het proces, zal deze constant pollen naar de status van de andere processen. Als we dan zien dat deze hun waarde allemaal false is, krijgt dit proces de kans om in kritische toestand te gaan.

Petersons algoritme

Omdat het Deckers algoritme nogal een complex algoritme is, ennogal lastig te bewijzen is er het Petsons algoritme gekomen. Als bij het Deckers algoritme is er een FLAG variable die we gaan gebruiken en heeft als voordeel dat het makkelijker uitbereidbaar is dan het Deckers algoritme.

Semaforen

Dit een veel gebruikt systeem bij besturingsystemen en programmeertalen. Als grondbeginsel nemen we, twee of meer processen die samen kunnen werken door middel van heel eenvoudige signalen. Door middel van deze signalen kan een proces gedwongen worden om te stoppen, tot dat het een specifiek gevraagde signaal terug binnen krijgt. Voor het signaleren worden specifieke variabelen gebruikt, semaforen genoemd. We kunnen deze beschouwen als een variabele waarop 3 bewerkingen mogelijk zijn. - Initialiseren op een niet-negatieve waarde - Wait : verlaagt de waarde van de semafoor met 1. Indien de waarde negatief wordt, dan zal het proces geblokeerd worden. - Signal : verhoogt de waarde van de semafoor met 1. Indien de waarde gelijk is aan iets negatief nog steeds, dan gaat een proces dat geblokeerd is gedeblokeerd worden.

Bij semaforen word er gebruik gemaakt van een wachtrij (queue) die dat alle processen bevat die de semafoor willen gebruiken. In deze wachtrij is het een FIFO toepassing. Er zijn 2 verschillende soorten semaforen, nl Sterke en Zwakke semaforen. Bij de sterke semaforen, gaat de queue lijst een FIFO toepassing hebben. Degene die dat eerst binnenkomt zal ook als eerste aan de beurt zijn. Bij zwakke semaforen gaat er niet vastgelegd zijn op welke manier dat de processen uit de wachtrij worden verwijderd.

De meeste besturingsystemen maken gebruik van de sterke semaforen.

Monitors

Dit is een iets makkelijkere manier van werken dan met semaforen. Bij de semaforen is het moeilijk om een correct programma te maken. Een monitor is een constructie in een programmeer taal die een functionaliteit bied zoals een semafoor. Monitoren bied de mogelijkheid om grendels te plaatsen op elk object. De belangrijkste kenmerken voor de monitor zijn : - De gegevensvariabelen zijn enkel toegankelijk voor de procedures van de monitor, en niet voor externe procedures - Een proces benaderd de monitor door een van de procedures op te roepen - Slechts 1 proces kan worden uitgevoerd door die procedure.

De gegevensvariabele zijn dus enkel toegankelijk door één proces tegelijk. Indien we andere procesen hebben die ook gebruik willen maken van de deze monitor, dan gaan we een deze in een wachtrij plaatsen. Eens dat de monitor vrij komt kunnen de processen die aan het wachten zijn terug aan de beurt komen. De processen die in de monitor zitten kunnen ook onderbroken worden door het cwait() signaal. Als dit gebeurt dan gaan we het proces dat uitgevoerd wordt in de wachtrij toegevoegd worden als dan de conditie veranderd, dan gaan we dit proces terug als de monitor vrij komt aan de monitor geven.

Message passing

Bij de interactie tussen de processen moet aan 2 eisen voldoen, synchronisatie en communicatie. De processen moeten gesynchroniseerd worden voor de mutuele exclusie. We gaan dit nu bekomen met behulp van het uitwisselen van berichten. Er bestaan tal van manieren voor het uitwisselen van berichten. Als we berichten gaan uitwisselen tussen verschillende processen, vraagt dit in zekere manier toch om een synchronisatie. De ontvanger kan pas een bericht ontvangen als het verzonden wordt door het andere proces. Dit gebeurt na het uitvoeren van een send/receive. Er zijn 2 manieren van receive mogelijk : - Is reeds iets verzonden, we wachten tot we de receive krijgen om verder te gaan. - er is geen wachtend bericht, dan proces blokkeren tot het bericht aankomt, of het proces wordt voortgezet en staakt zijn poging om een iets te ontvangen. Zowel de zender als ontvanger kunne geblokkeerd raken. Meestal willen we bekomen dat we een niet geblokkeerde zender en ontvanger hebt. Dan hoeft geen van beide processen te wachten. Het is wel nodig om bij het zenden te weten naar waar we gaan sturen, dus dat we een adres mee geven. Dit kan door middel van directe adressering, of indirecte adressering. Directe adressering is bij de send de indentificatie code mee sturen. Bij indirecte adressering word het bericht niet rechtstreeks verzonden van de zender naar de ontvanger, maar naar een gedeelde gegevens venster. Deze structuur bestaat uit een wachtrij waarin de tijdelijke berichten opgeslagen worden. Het gebruik van de indirecte adressering is veel flexibeler dan de directe adressering.

Besluit

Er zijn verschillende manieren om Mutex toe te passen. We gaan altijd zelf bepalen welke manier dat we gaan gebruiken. Het is zeker nodig bij het gebruik van een operating systeem.

Communicatie tussen taken

Joris Eeman

Inleiding

Taken communiceren met elkaar om 2 redenen:

Synchronisatie van informatie
uitwisseling van gegevens

Synchronisatie van informatie

Er bestaan 2 types van synchronisatie informatie:

de negatieve commando’s: het recht tot toegang naar een bepaalde bron voor zich reserveren. Dit kan gebeuren op basis van semaforen, mutex zoals in het vorige hoofdstuk uitgelegd.
de positieve commando’s: wanneer een taak de hulp nodig heeft van een andere taak voor het verwerken van een bepaalde handeling. Het gebruikte mechanisme hiervoor hangt van het gebruikte RTOS af. De volgende mechanismen die hiervoor gebruikt kunnen worden zijn event-flags, signals en message passing.

Data uitwisseling

Gegevens uitwisselen tussen taken kan gebeuren op de volgende twee wijzen:

Shared memory: Hierbij is het belangrijk dat de 2 taken niet tegelijk toegang hebben tot het geheugen; anders kunnen er corrupte data ontstaan. Dit kan opgelost worden door het gebruik maken van mutex zoals in het vorige hoofdstuk uitgelegd. Het nadeel van dit systeem is dat wanneer er 1 taak sneller werkt dan de andere, zal de snellere taak moeten wachten tot wanneer de tragere taak de toegang tot het geheugen vrijgeeft.
Message passing

Message passing

Bij message passing zal de communicatie tussen taken gebeuren aan de hand van berichten die verzonden worden tussen de taken. Er bestaat indirecte en directe message passing

Indirect message passing

Afbeelding wordt later toegevoegd

Bij indirect message passing zal het bericht niet rechtstreeks van taak naar taak gekopieerd worden, maar zal er gebruikt gemaakt worden van een buffer(Message Queue)., waaruit later de ontvanger het bericht kan lezen. De message queue is een “verborgen” plaats in het ram geheugen. Dit is nodig zodat andere taken het bericht niet kunnen aanpassen en zo collisions voorkomen.

Voordat de message queue gebruikt kan worden moet deze eerst worden aangemaakt. Dit kan door eender welke taak gebeuren. Alleen de zender en de ontvanger moeten op de hoogte gebracht worden van het indificatie nummer van de message queue. Wanneer er bi-directionele data uitwisseling plaats vindt, zullen er 2 message queue’s aangemaakt worden, 1 voor iedere richting waarin data uitwisseling plaats vindt.

De meeste operating systems kopiëren het bericht 2 keer; 1 keer van de zender naar de message queue en 1 keer van de message queue naar de ontvanger. Het probleem hierbij is dat het niet deterministisch is omdat hoe groter het bericht is hoe meer tijd dit in beslag zal nemen. De oplossing hiervoor is ipv het hele bericht te kopiëren, pointers te kopiëren die naar het bericht verwijzen. Dit zal voor ieder bericht evenveel tijd in beslag nemen. Hierbij is het belangrijk dat in de taak van de zender de pointer naar het bericht verwijderd wordt om zo collisions te voorkomen.

Direct message passing

Het bericht wordt rechtstreeks van taak naar taak verzonden.

Afbeelding wordt later toegevoegd

Voor zowel directe als indirecte message passing kunnen we nog deze 2 types onderscheiden:

Synchroon message passing: De zender moet wachten totdat de ontvanger het bericht heeft ontvangen voordat hij zijn taak verder mag uitvoeren. Dit kan er voor zorgen dat de taak van de zender een vertraging oploopt.
Asynchronous messag passing: Shoot and forget principe: de zender moet niet wachten totdat de ontvanger het bericht heeft ontvangen om zijn code verder uit te voeren. Bij gebruik van dit type is het niet gegarandeerd dat de ontvanger het bericht ontvangt. Wanneer de ontvanger niet klaar is om het bericht te ontvangen, zal de RTOS automatisch een message queue aanmaken om het bericht later te leveren aan de ontvanger bij direct message passing.

Besluit

Message passing is een populaire en betrouwbare manier om communicatie tussen taken te verwezenlijken.

Keuze van het RTOS

Yves Vervoort

Overzicht van het spectrum van beschikbare RTOS'sen. Commercieel of zelfgeschreven RTOS gebruiken? OSEK Standaard?

Inleiding

In de wereld van de ingebedde software is er veel discussie over het al dan niet aankopen van een RTOS. Hoewel een commerciële verkoper van RTOS’en het niet zou aanraden, is er de optie dat men zijn eigen RTOS schrijft. Dit wordt door vele ontwikkelaars gedaan, ook al is er een grote variëteit van RTOS’en beschikbaar op de markt. In dit gedeelte zal er vooral besproken worden wat de voornaamste voor –en nadelen zijn van beide manieren van ontwerpen.

Heb ik een RTOS nodig?

De eerste vraag die men zichzelf moet stellen betreft het feit of men al dan niet een RTOS nodig heeft. Zijn alle ingebedde softwaresystemen het best af met een RTOS? Het antwoord op deze vraag is simpel: veel applicaties zijn niet groot of complex genoeg en hebben die extra overhead dus ook niet nodig. Deze applicaties vereisen enkel gelimiteerde OS services. In deze gevallen zijn simpele structuren zoals round-robin scheduling of state-machine gebaseerde functies voldoende om het systeem te doen werken. Men verwacht toch geen RTOS in een broodrooster?

Waarom een commercieel RTOS?

Een commercieel RTOS moet goed gevormd en betrouwbaar zijn om nuttig te zijn voor de klant. Veel hangt hier dus af van de kwaliteit van de producent. Wanneer het om een gekende producent gaat zal het product ook betrouwbaar zijn. De koper en de producent gaan een lange termijn overeenkomst aan. De koper verwacht van het product dat het goed werkt en dat het een goede investering is. De verkoper verzekerd de support voor het product wanneer er nieuwe technologieën geïntroduceerd worden. Langs de zijde van de producent is het ook belangrijk dat het product goed gedocumenteerd wordt, wat het voor de koper aantrekkelijker maakt wanneer hij met een probleem te kampen heeft. Een commercieel product bestaat niet enkel uit een kernel. Alle omringende technologieën zoals: networking protocols, file systems, graphics, Java en dergelijke zijn zonder problemen beschikbaar als de koper hierom vraagt. Een moeilijk punt in het ontwikkelen van ingebedde software is vaak de low level interface met de hardware, namelijk de drivers. Een commercieel RTOS zal voorzien zijn van een aantal drivers voor standaard -en geïntegreerde apparaten.

Nadelen van een commercieel RTOS

Eén van de grootste nadelen van een commercieel RTOS zijn meestal de kosten. Jaarlijkse licentiekosten zijn vaak de oorzaak om af te stappen van een commercieel RTOS. Een ander argument van kopers tegen een commercieel RTOS is het feit dat het vaak overdreven functionaliteit bevat. Ook al bevat een RTOS veel mogelijkheden die niet nodig zijn in het uiteindelijke design, toch is elk modern RTOS schaalbaar. Alleen de nodige functionaliteit is voorzien in het uiteindelijke geheugen. Uiteraard is de schaalbaarheid verschillend van product tot product. Een ander argument van kopers is het feit dat er een prijs betaald wordt voor deze extra functionaliteit, maar dit is eigenlijk irrelevant daar de kosten verspreidt zijn over een groot aantal designs voor verschillende kopers.

Waarom een eigen RTOS?

De belangrijkste reden waarom men een eigen intern RTOS zou willen schrijven is vooral om de controle te behouden over het systeem. Als het intern ontwikkeld is, dan is uiteraard alle code in het bezit van de ontwikkelaar en is ook alle interne kennis van het systeem volledig gekend. Daarbuiten moeten we wel rekening houden met het feit dat dit enkel het geval is wanneer er een goed team achter het ontwikkelen staat dat voldoende kennis heeft om het RTOS te onderhouden. Zoals eerder gezegd zijn hier geen licentiekosten die het systeem duurder maken, wat een eigen intern RTOS aantrekkelijker maakt. Vele ingenieurs vinden dat een intern RTOS exact overeenkomt met hun behoeften, maar dit argument is moeilijk sterk te houden als we kijken naar een goed schaalbaar commercieel RTOS wat ook perfect aan de behoeften van de koper voldoet. Verder is de functionaliteit van een eigen intern RTOS dikwijls gelimiteerd door wat er bereikt kan worden met een bepaald budget of tijdsschema.

Nadelen van een eigen RTOS

Er zijn veel factoren die het ontwikkelen van een intern RTOS in vraag stellen. Zoals gewoonlijk starten we de analyse met geld. Een RTOS brengt altijd een ontwikkelkost met zich mee. Het gevaar hierbij is dat de kost van het intern RTOS verloren kan gaan in het totale budget van het gehele project. De kosten gaan echter verder dan dit. Als men rekening houdt met de lange termijn support van het RTOS kunnen de kosten al hoog oplopen. Een ander belangrijk iets waar rekening met moet worden gehouden: debuggen. Debuggen neemt veel tijd in beslag en de kost om een debugger te ontwikkelen kan tot 10 keer de prijs van het ontwikkelen van het RTOS bedragen. Er is natuurlijk altijd de optie om een commerciële debugger aan te passen voor je eigen intern RTOS, dit kan men dan ook best doen. Verder is het ook altijd de vraag waar het ontwikkelen van een eigen intern RTOS stopt. Ofwel wordt er gekozen om enkel de kernel te schrijven, maar er zijn meestal extra lagen nodig zoals protocols, grafische mogelijkheden ed. Er moet gekozen worden om ofwel:

Deze extra mogelijkheden zelf te schrijven, wat veel werk met zich meebrengt;
Een commerciële verkoper overtuigen om jou RTOS te porten, wat niet evident is en waarschijnlijk veel kosten met zich meebrengt;
Een Open Source product porten naar jou RTOS, wat ook veel werk met zich mee kan brengen.

Een ander nadeel van een eigen intern RTOS heeft te maken met overdraagbaarheid naar andere systemen. Omdat het waarschijnlijk veel Assembly code zal bevatten gaat het niet echt portable zijn daar het afhankelijk gaat zijn van de interrupt structuur van de CPU. Een laatste opmerking is dat een eigen intern RTOS niet zo bekwaam gaat zijn als een commercieel RTOS, om het feit dat er bedrijven zijn die gespecialiseerd zijn in één bepaald onderdeel: bijv. networking hardware. Zo’n bedrijf probeert om alles uit zijn hardware te halen. Dit is onmogelijk voor een eigen intern RTOS.

Lijst van goed gevormde RTOS’en van welgekende en betrouwbare verkopers:

AMX (KADAK)
C Executive (JMI Software)
RTX (CMX Systems)
eCos (Red Hat)
INTEGRITY (Green Hills Software)
LynxOS (LynuxWorks)
µC/OS-II (Micrium)
Neutrino (QNX Software Systems)
Nucleus (Mentor Graphics)
RTOS-32 (OnTime Software)
OS-9 (Microware)
OSE (OSE Systems)
pSOSystem (Wind River)
QNX (QNX Software Systems)
Quadros (RTXC)
RTEMS (OAR)
ThreadX (Express Logic)
Linux/RT (TimeSys)
VRTX (Mentor Graphics)
VxWorks (Wind River)

OSEK – Een RTOS Standaard

OSEK staat voor “Offene Systeme und deren Schnittstellen fur die Elektronik im Kraftfahrzeug” (Open systems and the corresponding interfaces for automotive electronics). Het is een industriestandaard^[2] voor ingebedde systemen in voertuigen die door enkele grote spelers in de auto-industrie tot stand is gekomen. Het biedt een standaard architectuur voor de verschillende elektronische controle eenheden (ECU’s) in een auto. De OSEK-standaard bestaat uit 3 modules:

Operating System (OS)
Communication Stack (COM)
Network Management Protocol(NM)

De specificaties voor het OSEK OS bevatten zeer strikte real-time regels:

Memory gebruik moet zo klein mogelijk zijn;
Het OS moet schaalbaar, betrouwbaar en low-cost zijn;
De software moet portable zijn en moet als basis dienen voor software integratie van verschillende ontwikkelaars.
De configuratie moet statisch zijn.

Het belangrijkste aan heel het OSEK project is de portability en de hergebruikbaarheid van de applicatiesoftware. De specificaties van de user interface moeten verder onafhankelijk zijn van de hardware. Sommige delen van OSEK zijn gestandaardiseerd in ISO 17356.

FPGA's

FPGA-gebruik in embedded systemen

Thomas Buts

Wat is een FPGA?

Wanneer we even terugduiken in de tijd, kunnen we het ontstaan van de FPGA goed schetsen. Board Based Design is een concept dat al redelijk oud is, maar nog steeds gebruikt wordt. Men neemt verschillende componenten, zet ze op een PCB en verbindt deze met elkaar. Indien aanwezig programmeert men de microprocessor of controller. Voor eenvoudige systemen gaat dat allemaal, maar wanneer men een systeem op maat wil maken met specifieke hardwarevereisten zouden er een veelvoud van componenten moeten toegevoegd worden. Vandaar ook het ontstaan van de SoC. Het probleem was dat de processor in de SoC moeilijk te debuggen is en fouten in het ontwerp van de chip niet te herstellen zijn na de productie. Men zocht andere, efficiëntere methodes om de logica in de chip te krijgen en kwam uit bij de PLD. Het idee was eenvoudig. Men gebruikt een matrix van logische elementen die men op een bepaalde manier verbindt om zo tot het gevraagde systeem te komen. Deze interconnects werden gerealiseerd door fuse en antifuse, met als gevolg dat de PLD maar éénmalig programmeerbaar was. Desondanks bleef het gebruik enorm stijgen, met een grote toename van het aantal logische cellen in de chip tot gevolg. Een nieuwe programmatiemethode diende zich aan onder de vorm van SRAM. De configuratie wordt meestal bewaard in flash en uitgelezen bij het opstarten van het systeem. Een FPGA begint tegenwoordig echter meer en meer op zichzelf te staan, vandaar ook de benaming Programmable SoC,

Waarom kiezen voor een FPGA?

De FPGA zelf bestond al terwijl men nog volop ASIC's aan het maken was. Hoe komt het dan dat deze niet onmiddellijk zijn opmars heeft gemaakt? Gezien de relatief nieuwe technologie was de FPGA zeker niet sneller dan een ASIC en verbruikte hij bovendien meer vermogen. Maar het grote probleem was dat een FPGA meer kostte. Hij werd daarom ook eerst gebruikt om de time-to-market kleiner te maken. Een FPGA is vrij snel geprogrammeerd, terwijl een ASIC heel wat meer werk vraagt. Zo wordt het design vrij snel in een FPGA gemapped en geroute terwijl bij een ASIC de routing manueel verder nagekeken moet worden. De FPGA kon tijdelijk als een prototype voor de ASIC gebruikt worden, zodat de productontwikkelaars verder konden werken. Zodra de FPGA's goedkoper en sneller werden en minder stroom verbruikten, kwamen ze echter ook terecht in uiteindelijke producten. Op die manier moet er geen geld meer uitgegeven worden aan het ontwerp van ASIC masks en patronen. Daarnaast heeft de FPGA ook enkele voordelen tegenover ASIC's. Zo gaat de in-system verification een stuk eenvoudiger aangezien het mogelijk is om bepaalde signalen op een pin naar buiten te routen. Zo heeft men tegenwoordig de mogelijkheid om in software paketten snel een volledig system-design te maken. En een van de belangrijkste zaken. Het is achteraf mogelijk om de hardware aan te passen!

De FPGA architectuur

In het algemeen kunnen we een FPGA opdelen in 3 stukken. De Configurable Logic Blocks (CLB), de Input-Output Blocks (IOB) en de programmable interconnects. Een FPGA zonder configuratie is dan ook niet veel meer dan een blokkendoos. De CLB bevatten de logica die gebruikt wordt om de schakeling op te bouwen. Er zijn verschillende lookup tables (LUT) aanwezig om logische functies te bouwen. Flip-flops voor geheugenwerking en multiplexers om in- en uitgangen met elkaar te koppelen. De IOB worden gebruikt om in- en uitgangssignalen in de chip te krijgen. Elke pin is verbonden met een input en output buffer zodat ze voor tweerichtingsverkeer gebruikt kan worden. Om te voorkomen dat er kortsluiting zou optreden wordt een tri-state buffer voorzien bij de output buffer. Deze zal hoogimpedant zijn wanneer de pin als input gebruikt wordt. De programmable interconnects zijn in feite de draden die men gaat gebruiken om de verschillende logische blokken met elkaar te verbinden. Enerzijds hebben we de local interconnects. Deze gaan CLB's die fysiek dicht bij elkaar liggen met elkaar verbinden. Het in-/uitschakelen van deze lijnen gebeurt door transistors. Naast de lokale interconnects hebben we ook de lijnen die CLB's op grotere afstand van elkaar kunnen verbinden. Deze zijn verbonden met een switch-matrix die de juiste lijnen met elkaar verbindt (wederom een reeks transistors). Deze lange lijnen kunnen ook gebruikt worden als bus door de CLB's via een tri-state buffer met de lijn te verbinden. Naast deze verbindingen hebben we ook de speciale kloklijnen. Deze zijn zo gelegd dat er een zo laag mogelijke impedantie en zo goed als geen vertraging op zit.

De FPGA in een embedded systeem

Een FPGA zonder configuratie is zoals een motor zonder benzine. Of met andere woorden, niet werkzaam... Deze configuratie wordt gemaakt door een beschrijving in VHDL, Verilog,.... Maar er bestaan ook andere middelen die enorm veel gebruikt worden bij embedded design. Programmeurs zijn van nature lui en zoeken middeltjes om het hun zo makkelijk mogelijk te maken. Daaruit vloeiden de begrippen softcore en IP uit voort. IP of Intellectual Property zijn blokken VHDL die geschreven zijn en geïmplementeerd kunnen worden in de eigen VHDL code. Zo kunnen een ethernet, bluetooth, e.a modules snel in het design opgenomen worden. Passen we dit toe op een embedded systeem dan komen we uit bij softcore processoren. Dit zijn geen stukjes VHDL, maar een volledige processor die geschreven is in VHDL code. Deze kunnen we in een fpga steken, samen met een stukje voor geheugenwerking, wat IO en we hebben een embedded systeem. Tegenover deze volledige software implementatie staan de termen hardcore en specialized logic. Een FPGA is door de jaren heen veranderd van een programmeerbare chip tot een programmeerbare system on chip. Men ging dus niet enkel logica in de chip steken, maar ook effectieve processors. Vandaar ook de benaming hardcore processors. De aanwezigheid van de extra logica naast de processor laat toe om op een snelle manier een embedded systeem op te bouwen. Aangezien de processor zelf volledig in hardware is gebouwd, zal deze een betere performantie hebben dan een softcore processor. Het voordeel van de softcore processor is dan weer dat je de processor zelf kan gaan aanpassen. Meer registers toevoegen, .... Specialized logic staat dan weer tegenover IP. In plaats van in VHDL een ethernet, bluetooth,... module te beschrijven, wordt deze al in hardware in de FPGA toegevoegd. Het enige wat overblijft, is het beschrijven van de andere hardware en verbinden met de ingebouwde componenten.

Eens we zo'n systeem op poten hebben gekregen, kunnen we er software voor schrijven. We kunnen er voor kiezen om een programma in Assembler of C te schrijven en zo de hardware aan te spreken, maar meestal gebruiken we een RTOS waar we een C-programma voor maken.

Performantie van een FPGA systeem

Het voordeel van de configureerbare hardware is de mogelijkheid om te schuiven tussen software en hardware. Bepaalde algoritmes zullen eenvoudiger in hardware te implementeren zijn én bovendien sneller werken dan in software. Zo kunnen we een optimaal systeem bekomen. Erg handig zou het zijn wanneer een C-programma rechtstreeks geïmporteerd zou worden en bepaalde delen van die code automatisch in hardware worden omgezet. Op die manier moeten de programmeurs niets meer afweten van de onderliggende hardware om te programmeren op het embedded systeem. Gezien de moeilijkheid van zo'n omzetting is dit tot op heden nog niet mogelijk, maar er is al wel een tegemoetkoming voor de software ontwikkelaars. Met System-C is er een taal ontwikkeld die sterk op C lijkt, maar uiteindelijk hetzelfde doet als VHDL,Verilog,... Momenteel worden echter volgende technieken gehanteerd: Instruction Set Extending: Gezien de mogelijkheid van de softcore processoren bij FPGA's kunnen we ook de instructieset van de softcore bewerken. Zo kunnen we bepaalde blokken toevoegen aan de ALU van de processor die voorgedefinieerde operaties kan uitvoeren op data.

Adding On-Chip Coprocessors: (hardware accelators) Hier gaan we geen aanpassingen doen aan de processor zelf, maar voegen we een stukje logica toe dat zelfs off-chip kan zijn. Het essentiële element hier is de Direct Memory Access (DMA). De logica gebruikt DMA voor het inlezen en het wegschrijven van de data. Daarnaast zit er nog een controleblok dat de coprocessor kan instellen, starten, stoppen en pollen. Men gaat dit systeem vooral gebruiken bij het verwerken van grote hoeveelheden data bij atomic operaties.

Multiprocessor systemen: Afhankelijk van het aantal CLB's kunnen we verschillende softcore processoren toevoegen aan het design. Dit zijn geen coprocessors, maar processoren die onafhankelijk van elkaar specifieke taken uitvoeren.

Multichannel applications: Er worden verschillende processoren op dezelfde chip gebruikt. Deze gaan elk een deel van de applicatie op zich nemen. In sommige gevallen wordt er ook nog een master processor toegevoegd die zorgt voor een goede aansturing van de slave processoren.

Serially Linked Processors: De verschillende processoren wordt in een ketting achter elkaar gezet en gaan de resultaten van een operatie doorgeven aan de volgende processor, die dan weer hetzelfde doet.

De werking met verschillende cpu's geeft een mooie toename van processorkracht, maar het geheugengebruik moet wel in goede banen geleid worden. Zoniet zal het systeem niet voldoende kunnen profiteren van die extra kracht.

Besluit

Het gebruik van FPGA opent verschillende nieuwe mogelijkheden tot het bouwen van embedded systemen met steeds toenemende performantie. De grootste troeven liggen natuurlijk in de variabele configuratie van de hardware. Zo is het zelfs mogelijk om achteraf niet alleen de software, maar ook de hardware van een systeem aan te passen!

Soft-core processoren

Peter Bontekoe

Wat is een soft-core processor

De CPU, cache geheugens en randperiferie kunnen worden opgebouwd uit on-chip LUT's en block RAM memory. Een soft-core processor is meestal ontwikkeld voor een specifieke bouwsteen (FPGA/CPLD).Het wordt onder andere gebruikt in netwerk materiaal,telecom applicaties, de stuurtechniek en de consumenten markt. De meeste FPGA fabrikanten bieden hun eigen soft-core processor aan. Dit omdat de interne silicium structuur van fpga's zich niet lenen voor arm, pentium of mips cpu's.^[3] Het grote voordeel is de flexibiliteit van randperiferie voor deze core die mee kan geïmplementeerd worden in de FPGA of CPLD. Ook is de core makkelijk aanpasbaar gedurende de design flow. Hierdoor is de time-to- market een stuk korter. Wanneer het product zich al op de markt bevindt, zijn aanpassingen ook nog steeds mogelijk.

Families

Er zijn 3 grote families op de soft-core markt:

Xilinix
Altera
Lattice

Xilinx Microblaze SPC

De Microblaze kan geïmplementeerd worden in de Virtex of Spartan-3 FPGA's van Xilinx. Het betreft een 32-bit RISC Harvard-stijl architectuur. Het blokschema is hieronder weergegeven. Xilinx laat toe de processor te strippen om zo een kleinere voetafdruk te bekomen. Performantie en de benodigde devices dienen tegen mekaar afgewogen te worden. De Memomory Management unit bijvoorbeeld vertaalt de fysieke in de logische adressen. Deze is essentieel voor bepaalde OS'en maar kan in bepaalde gevallen overbodig zijn. In onderstaande figuur is het blokschema van de Microblaze afgebeeld. Aan de verschillende bussen kan randperiferie worden gehangen die mee op de fpga worden ingeplant. Eenerzijds bestaat er vrije periferie zoals o.a. UART,interrupt controller en timers , anderzijds bestaan er ook commerciële IP's (intellectual property) cores zoals o.a. een Ethernet controller,PCI en HDLC. Ook is de microblaze configureerbaar in een 3 of 5 delige parallelle pijplijn. File:Microblaze.jpg

De Fast Simplex Link (mfsl en sfsl op figuur) laat toe om bepaalde processor taken te gaan uitbesteden aan FPGA-logica. Het is een unidirectionele punt-tot-punt communicatie, dat steunt op het FIFO(First in First out)-prinipe. Er is een FSL master en een FSL slave tijdens de communicatie. De FSL kan gebruik maken van zowel controle als data communicatie. De bus is ideaal voor Microblaze-naar-Microblaze of streaming I/O communicatie. Ze laat ook toe om eigen gedefiniëerde processor logica te implementeren. In de figuur is hiervan een voorbeeld te zien men laat eerst via de controlecommunicatie de juiste functie in. Vervolgens stuurt men de registers waar de bewerking op moet worden uitgevoert. Om ten slotte het resultaat te ontvangen. File:FSL.jpeg

De Microblaze SPC wordt geleverd bij het Xilinx Platform Studio EDK tool suite van Xilinx, een ontwerpomgeving voor het gebruik van Xilinx processoren.

andere Xilinx processoren voor FPGA's

Xilinx beschikt ook over de Picoblaze, dit is het 8-bit broertje van de Microblaze. De Picoblaze kan op eventueel op een CPLD geïmplementeerd worden. Deze soft-core heeft een kleinere footprint en leent zich dan ook meer voor de eenvoudigere, kost-efficiëntere applicaties.

Xilinx beschikt in zijn virtex series ook over PowerPC processoren. Samen met een minimum aan FPGA-logica kan men hiermee een UltraController-II implementeren in een virtex FPGA. Dit is vooral nuttig bij het coderen van VHDL of Verilog voor de FPGA. De UltraController-II microprocessor kan dan gebruikt worden voor controle,monitoring,configuratie en simpele data manipulatie van een applicatie.

Altera NIOS II

De Altera NIOS II soft-core processor is eveneens een 32-bit RISC architectuur. Hij is gebouwd voor de Stratix en Cyclone FPGA's van Altera. Maar kan eveneens geïmplementeerd worden in een Hardcopy asic van Altera. De NIOS II is beschikbaar in 3 versies:

de fast core
de standard core
de economy core

De fast core is de performanste en de economy core heeft de kleinste voetafdruk van de 3. Enkel de fast core heeft een MMU. Ook wordt de pijplijn verkleint telkens men een versie zakt. De economy core heeft geen pijplijn. De fast core heeft een data en een instructie cache, de standard core enkel een instructie cache en de economy core heeft geen cache ter beschikking. De keuze is weederom een afweging van performantie,grootte van de logische bouwsteen en kostprijs. Een blokschema van de NIOS II soft-core is hieronder weergegeven: File:Nios.jpg

Ze beschikken alle drie over de mogelijkheid om een custom processor instrunctie te integereren in hun design. Een voorbeeld hiervan is weergegeven in onderstaande figuur. A en B stellen processor registers voor, nu kan er zelf een alu-functie worden gedefinieerd in VHDL of Verilog. Deze kan dan door de CPU worden gebruikt. Op deze manier kan men ingewikkelde ALU-functies in FPGA-logica gaan implementeren. Er kunnen maximaal 256 van zulke functies worden geïmplementeerd.

De ontwikkeltools voor de NIOS II software is NIOS IDE welke bestaat uit een C compiler(GNU) en eclipse (java gebaseerde ontwikkelomgeving). Voor de hardware implementatie is er de Quartus-II met SOPC builder tool.

andere processoren voor Altera FPGA's

Altera biedt een aantal van de gekende discrete processor architecturen aan in soft-core vorm:

32-bit
- arm Cortex m1 van de ARM architectuur
16-bit:
- C68000 van de Motorola 68000 architectuur
8-bit:
- R8051XC van de 8051-architectuur

Open soft-core:Lattice

Lattice heeft als enige de open IP soft-core processor. De open source aanpak zorgt voor een verhoogde:

Zichtbaarheid: open source zorgt voor het beter begrijpen van de architectuur en de werking ervan.
Flexibeliteit: open source maakt dat de gebruikersgemeenschap kan aangeven welke vlakken verbetert dienen te worden ,dat de leden kunnen meehelpen aan hogere kwaliteitsoplosingen en het maken van modificaties.
Overdraagbaarheid: het is architectuur onafhankelijk waardoor het design beter kan geïmplementeerd worden op andere platformen zoals ASICs of andere programmeerbare devices.

Lattice bescikt over een 32-bit versie en een 8-bit soft-core processor, respectievelijk de LatticeMico32 en de LatticeMico8 microprocessor.

Besluit

De keuze van de juiste soft-core zal het vinden van een goed evenwicht zijn tussen kostprijs en performantie. De flexibiliteit is één van de grote voordelen t.o.v. andere processoren. De nieuwe generatie FPGA's en CPLD's bieden een ruime keuze aan mogelijkheden.

Referenties

↑ Colin Walls, What Makes an Embedded Application Tick?, in Embedded Software: The Works, Newnes, 2006.
↑ Embedded.com
↑ Embedded.com

[1] Colin Walls, What Makes an Embedded Application Tick?, in Embedded Software: The Works, Newnes, 2006.

[2] Embedded.com

[3] Embedded.com

[1]

[2]

[3]