Torben Mogensen header

Underlige CPU'er

Computeres regneenheder (CPU'erne) har efterhånden konvergeret mod en model, der kun varieres lidt: Man har 2^n bit per register, typisk 8, 16, 32 eller 64. Man har 2^n registre, hvoraf nogle få kan have specialfunktioner (såsom PC, stakpegepind eller konstant lig med 0). Heltal bruger tokomplement repræsentation og kommatal bruger IEEE-standarden. Men der har gennem tiderne været lavet mange underlige ting, der måske gav mening i sin tid, men som på darwinistisk vis er uddøde i kampen om overlevelse. Her er et par eksempler:

Skæve ordlængder

Tidlige computere havde ikke nødvendigvis ordlængder, der var toerpotenser. Vores hjemlige DASK havde for eksempel 40-bits ord, og GIER 42-bit ord, hvor de to sidste bit dog kun blev brugt til instruktionsindkodning (tal var altid 40 bit). Univac 1100, som var den computer, der blev brugt på DIKU, da jeg startede med at studere, havde 36-bit maskinord. Det havde den fordel, at man kunne dele et register op i to halve, tre tredjedele, fire fjerdedele eller seks sjettedele, som f.eks. blev brugt til at indkode seks Fieldata tegn i et register. Digitale signalprocessorer (DSP'er) har ofte skæve ordlængder, f.eks. 24 bit, så man havde lidt større præcision end 16 bit uden at betale hele prisen for 32 bit. Ofte var der et par ekstra bit i akkumulatoren, så man kunne have mellemresultater, der var lidt større end registrene ellers tillod. http://en.wikipedia.org/wiki/Word_%28computer_architecture%29 har en tabel over ældre maskiners ordlængder, hvoraf man blandt andet kan se, at Saturn V raketternes computer havde 26-bit ord. Hvor moderne computere er byte-addresserede (dvs. at adresser tæller 1 op for hver byte i lageret), ver det almindeligt i de tidlige computere, at der var et helt maskinord per adresse. Men det modsatte har også været forsøgt: Intels første forsøg på erstatning af x86, iAPX432, havde 32-bit maskinord, men havde en adresse for hvert bit i lageret, så man kunne f.eks. hente 32 bit startende fra bit 113 i lageret.

Alternative talindkodninger

Stort set alle moderne computere bruger tokomplement binær repræsentation til heltal. Men det har ikke altid være tilfældet. Den før omtalte UNIVAC 1100 brugte foreksempel etkomplementrepræsentation, hvor et tal negeres ved at vende alle bit. Hvis tallet 3 er indkodet i 8 bit som 00000011, er -3 indkodet som 11111100. Det gør nogle ting enklere, men der er underlige konsekvenser, f.eks. har 0 to forskellige indkodninger: 00000000 og 11111111, hvoraf den sidste ofte blev kaldt -0. Det gjorde også kredsløbende til addition lidt mere besværlige (subtraktion er nem nok, når man har addition: Man vender blot alle bit i den ene operand). Andre maskiner brugte fortegn + magnitude, hvilket stadig ses i kommatalsrepræsentationer, men der var flere muligheder. Det var ikke ualmindeligt, at computere brugte decimaltal: Hvert ciffer blev internt repræsenteret med fire bits (Binary-Coded Decimal), og aritmetik sørgede for at menteoverførsler fungerede som i decimal. Det gjorde man til dels for at understøtte COBOL, hvor taltyper var specificeret som et antal decimale cifre (både før og efter decimalpunktummet). x86 understøtter stadig BCD i hardware, men de fleste andre processorer overlader det til software. Men det kunne være endnu mere underligt: Den russiske Saturn computer brugte ternære tal: Cifre kunne være 0, +1 eller -1. Denne balancerede ternære repræsentation har nogle gode matematiske egenskaber: Negative tal er ikke specialtilfælde, negation er en tritvis (et ternært ciffer kaldet en "trit") og det er den mest effektive talindkodning af alle, hvis man regner på følgende måde: Vi antager, at et ciffer "fylder" lineært i antallet af forskellige cifre. Da kræver det det log(n)/log(base) cifre, der hver koster base plads at indkode et tal n. Man skal altså minimere base/log(base). For base 2 (binær) er dette tal 2,885, for base 3 (ternær) er det 2,731, for base 4 er det 2,885 (ligesom for base 2), og derefter stiger værdien. Så base 3 er marginalt mindre pladskrævende end base 2. Desværre er elektronikken væsentligt mere kompliceret. I Saturn repræsenterede man f.eks. en trit som to bit, hvor en kombination ikke blev brugt, så i praksis var der ikke vundet noget. Der forskes dog stadig teoretisk med ternær logik for kredsløb, blandt andet i forbindelse med kvantecomputere. Hvem ved: Hvis et element i en fremtidig computer har tre naturlige tilstande i stedet for to, kan ternære tal komme på mode igen.

Stakcomputere

Moderne CPU'er bruger stort set altid registre til mellemresultater og lokale variabler, selv om mange virtuelle maskiner (JVM, CLI, osv) bruger stakke. Men tidligere var det ikke ualmindeligt at lave CPU'er, der eksplicit brugte en stak til mellemresultater. En af de mere kendte er Burroughs B5000 serien, som var bygget til Algol 60 (man brugte en variant af Algol kaldet ESPOL som assemblersprog). Et andet eksempel er den britiske Transputer, der var lavet til at understøtte sproget Occam, der var rettet mod parallelle og samtidige beregninger. Der er også hybride maskiner, f.eks. SPARC, der har en registerstak: 16 af de 32 heltalsregistre er et vindue ind i en større registerstak, der flyttes op eller ned ved funktionskald. Ideen var at mindske prisen for funktionskald ved at undgå, at der skal gemmes og hentes et større antal registre ved hvert kald. Intels mindre succesfulde Itanium brugte en lignede ide. En næsten modsat ide blev brugt i Texas Instruments' TMS9900 16-bit processor (som blev brugt i hjemmecomputeren TI-99/4): Et WP (workspace pointer) register pegede på 16 16-bit ord i lageret, som blev brugt som registre. Udover WP var kun PC og statusregisteret egentlige on-chip registre, så alle beregninger skete via lageret, o det var almindeligt at organisere en stak i lageret og lade WP rykke op og ned ved funktionskald og retur.

Forbedringer in oversætterteknik har gjort stakmaskinernes fordel i forhold til enkel kodegenerering fra højniveausprog stort set irrelevant, og overhead til at gemme og hente registre ved funktionskald er minimeret dels gennem registerallokering og dels gennem hurtig primærcache. Så stort set ingen moderne CPU'er er egentlige stakmaskiner.

Andre underligheder

En tidlig mikroprocessor, RCA 1802 fra 1974, var ret usædvanlig: Den havde et akkumulatorregister D (16 bit) samt 16 16-bit registre, der kunne bruges som operander sammen med D til aritmetik og lagertilgang. Der var ikke nogen egentlig stakpegepind, ingen subrutinekaldinstruktion og ingen betingede hop, men enhver af de 16 registre kunne sættes til at være PC, så man kunne simulere disse ting med lidt snedighed. Alle instruktioner var 8 bit bestående af 4 bit opcode og 4 bit operandregister. På mange måder kan RCA 1802 siges at være en forløber for RISC-ideen.

Data General's Nova computer (som Regnecentralen lavede en version af undre navnet RC7000) havde 16-bit registre og adresser. Men det ene bit i adressen havde en speciel funktion: Hvis det var sat, var lagertilgang eller hop indirekte, så man hentede ordet på adressen og brugte det som adresse. Hvis dette ord også havde indirektionsbittet sat (og det var en hopinstruktion), var denne adresse også indirekte, og så fremdeles, så man kunne have vilkårligt lange kæder af indirekte adresser. I de første versioner af computeren, kunne man ikke afbryde denne sekvens, så hvis man forsøgte at tilgå en cyklisk kæde af adresser, kom computeren i en uendelig løkke, som kun kunne afbrydes ved at slukke computeren. Senere modeller tilføjede en tæller, der afbrød kædefølgeriet efter et stykke tid.

Der har været adskillige processorer, der har været specialiseret til et bestemt højniveausprog. Jeg nævnte Burroughs B5000 serien og Algol samt Transputeren og Occam før, men der har også været lavet processorer specielt til sprog som LISP, Java, Forth m.m. De er for det meste blevet overflødige, fordi oversætterteknik har gjort implementering af disse sprog på traditionelle CPU'er lige så effektiv som på de specialiserede processorer.

Der er korte beskrivelser af flere bemærkelsesværdige processorer på Great Microprocessors of the Past and Present. Nogle af dem er underlige på forskellige måder, mens andre "blot" er klassikere.

Alle de ovenstående eksempler har været i kommerciel produktion, men der er utallige mærkelige CPU'er, der aldrig har forladt laboratorierne. Et eksempel på dette er Pendulum processoren, der implementer et reversibelt instruktionssæt: Et bit i processoren bestemmer, om programmet kører forlæns eller baglæns, og dette bit kan vendes i forbindelse med hop.

Kommentarer (27)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Svenne Krap

Der er faktisk en ny arkitektur på vej ... http://millcomputing.com

De kalder det en bælte-arkitektur og den er helt registerløs (bæltet fungerer lidt som en stak, blot at den er fixed size fifo - hvor ting ryger ud over kanten og på gulvet).

Spændende arkitektur, som jeg håber bliver til noget :)

  • 3
  • 0
Bjørn Reese

Idag har vi (næsten) kun big-endian (ABCD) og little-endian (DCBA), men i fordums tid havde man også forskellige typer af middle-endian. Eksempelvis benyttede PDP-11 sig af word-swapped little-endian (BACD), og Honeywell 316 af word-swapped big-endian (CDAB).

  • 2
  • 0
Thomas Dynesen

Univac 1100's efterkommere eksisterer skam stadig den dag i dag. Nu hedder de 2200 eller Clearpath Dorado serien. Den første Univac 1107 blev leveret i 1962 og programmer kompileret til den vil køre uden problemer på en nuværende Dorado 890 (top-end modellen) som i dag kan have op til 32 CPU'er og kan konfigureres i clustre med 4 (snart 6) sådanne systemer. Og ordlængden er stadig 36 bit og der er op til 32G af dem, svarende til 128GB, i memory. Instruktionssættet er dog udviddet til 291 instruktioner mod 1107'erens 117. Og der findes skam også indirekte addressering på alle instruktioner. Hvis man laver en uendelig kæde får man en "instruction timeout contingency". Der er stadig 1-komplement logik dvs. både 0 og -0. Disse systemer driver nogle af verdens største luftfartsselskaber og banker. Fx. er ALLE fly checkin i HELE Kina håndteret af ét 4 X 32 CPU cluster. Det har kørt adskillige år uden stop og er vel at mærke fuldt opgraderet til nyeste system software (CP14.0 released feb. 2013). Hvis det stopper starter der ingen fly i Kina før det kommer op igen! 7500 transaktioner i sekundet. Der er desværre ikke flere tilbage i Danmark. SAS slukkede som de sidste deres i maj sidste år. Opgaven blev outsourcet til Amadeus, men kører stadig på en 2200.
Burroughs B5500 efterkommere findes også. Nu hedder de A-serien eller Clearpath Libra.
http://www.unisys.com/unisys/theme/index.jsp?id=1120000970018010225

  • 5
  • 0
Morten Andersen

Men her et hurtigt spørgsmål - præcis hvordan fungerede idéen du nævner:

>>>Der er også hybride maskiner, f.eks. SPARC, der har en registerstak: 16 af de 32 heltalsregistre er et vindue ind i en større registerstak, der flyttes op eller ned ved funktionskald. Ideen var at mindske prisen for funktionskald ved at undgå, at der skal gemmes og hentes et større antal registre ved hvert kald. <<<

Som jeg læser det havde CPU'en en del flere registre end der var synlige for programmet og man flyttede så vinduet ved funktionskald m.m. Men hvor mange "ekstra" registre var der tale om? For der må jo være en eller anden grænse, så hvad skete der i givet fald når man havde brugt dem op? Jeg kan godt se fidusen indtil man når dette punkt, men når man først har brugt registrene op er eneste løsning jeg kan se at CPU'en må lægge toppen af registerstakken ud til memory, som så kan hentes tilbage ved returning. Men er der i givet fald noget vundet når man først når til den tilstand? For alle funktionskald/returkald herefter vil jo medføre at der skal spilles noget eller hentes noget ind fra memory så det virker som om tilgangen til memory bliver den samme som hvis man blot havde brugt stakken til funktionskald. Eller der var måske så mange registre i CPU'en at man i praksis aldrig havde en kalddybde der kom ud i den situation?

  • 0
  • 0
Poul-Henning Kamp Blogger

1802 er den absolut mest bizarre CPU jeg nogensinde har prøvet at skrive en disassembler til, tricket med at skifte CPU kræver i realiteten en "value-tracking" disassembler hvis den ikke skal strande meget hurtigt.

Hvis der er nogen der trænger til en frisk lille hjernevrideropgave:

Læs i RCA1802 databladet hvorledes man starter CPU'en med interrupts disabled.

Disassembler så den angivne løsning :-)

Jeg synes egentlig også at HP's "Saturn" CPU fortjene at blive nævnt, det er den 4-bit CPU der sidder i alle HP's high-end lommeregnere (HP28, HP48 osv.)

  • 3
  • 0
Poul-Henning Kamp Blogger

En af de absolut mest bizarre konstruktioner i en computer var også i en af de første.

"LEO", "Lyons Electronic Office", havde en "multi-radix-adder", således at de effektivt kunne regne på det pre-decimale engelske møntsystem: Et pund var 20 shilling, en shilling var 12 pence.

  • 5
  • 0
Jesper Poulsen

Jeg synes egentlig også at HP's "Saturn" CPU fortjene at blive nævnt, det er den 4-bit CPU der sidder i alle HP's high-end lommeregnere (HP28, HP48 osv.)


Jeg tænkte også på den. Men er den 4-bit eller 64-bit?
Databussen er 4-bit. Adressebussen er 20-bit og registrene er 64-bit.
Jeg ved godt at den er nibble-baseret (min gamle HP32S kan have halve KiB fri, ligesom mange programinstruktioner ikke forbruger hele KiB).

Den er alt andet end RISC. Instruktionssættet er enormt.

  • 0
  • 0
Torben Mogensen Blogger

Men hvor mange "ekstra" registre var der tale om? For der må jo være en eller anden grænse, så hvad skete der i givet fald når man havde brugt dem op?

Såvidt jeg erindrer var antallet af fysiske maskiner forskelligt på forskellige modeller, men Jespers bud på 128 lyder rigtigt for de tidlige modeller. Når registerstakken var ved at løbe tør, lavede processoren et interrupt til en rutine, der lagde den nederste halvdel af stakken i lageret og rykkede den øverste halvdel ned (det skete såvidt jeg husker ved at vippe et bit i adresseringen). Når stakken var ved at være tom, skete det omvendte.

  • 2
  • 0
Torben Mogensen Blogger

1802 er den absolut mest bizarre CPU jeg nogensinde har prøvet at skrive en disassembler til, tricket med at skifte CPU kræver i realiteten en "value-tracking" disassembler hvis den ikke skal strande meget hurtigt.

Ja, den var ret speciel. Du mener i øvrigt nok "skifte PC".

Jeg stødte på en COSMAC (som brugte 1802) i forbindelse med et studiejob, men fik aldrig selv prøvet at programmere den. En sjov ting ved den var, at man kunne se HELE lageret som bitmap på skærmen, så man kunne følge med i, hvordan programmet kørte. En kollega lavede et RAM-check ved at skrive skiftevis 0 og 1 til hele lageret. Hvis en pixel sad fast på enten 0 eller 1, kunne det ses tydeligt på skærmen.

  • 1
  • 0
Torben Mogensen Blogger

Se fx http://www.sics.se/~psm/sparcstack.html for en diskussion af register windowing på SPARC.

God diskussion. Den centrale sætning er, efter min mening "Register windows was a bad idea that was caused by simulation studies that considered only programs in isolation, as opposed to multitasking workloads, and by considering compilers with poor optimization".

  • 0
  • 0
Morten Andersen

Nogle af de første CPU'er havde ferritkernelager. Her er læsning destruktiv, d.v.s. at det at læse en bit fra RAM medfører at bitten samtidigt slettes (sættes til 0 eller 1 afhængigt af konvention). Derfor er RAM-enheden (eller lignende) nødt til at genskrive en læst bit straks efter læsning så værdien ikke går tabt. Men da det ikke er i alle situationer det faktisk er nødvendigt for programmet at kunne læse værdien igen (som et simpelt eksempel, hvis programmet udfører "i = i + 1" og dermed alligevel skal skrive i kort efter), så havde nogle af CPU'erne fra den tid instruktioner der kunne læse fra lageret UDEN automatisk at genskrive værdien, som dermed kunne køre hurtigere (men altså også medførte at værdien i lageret gik tabt).

Af andre kuriositeter: Nogle CPU'er udfører instruktionen umiddelbart EFTER et konditional branch, selv når branchen tages. På den måde kan man begrænse de negative effekter af et pipeline flush ved branch mispredictions (inkl. tilfældet med CPU'er der slet ikke har branch prediction eller kun triviel branch prediction, f.eks. at de altid gætter på hoppet ikke tages) idet CPU'en i alle tilfælde har en instruktion den kan udføre mens den venter på at få hentet næste instruktion ind i piplinen.

  • 0
  • 0
Torben Mogensen Blogger

Af andre kuriositeter: Nogle CPU'er udfører instruktionen umiddelbart EFTER et konditional branch, selv når branchen tages. På den måde kan man begrænse de negative effekter af et pipeline flush ved branch mispredictions

Ja, disse branch delay slots findes f.eks. på MIPS. Man er gået bort fra dem sidenhen, for fordelen er begrænset, når implementeringen ikke længere er en simpel pipeline, og så er de faktisk til mere besvær end gavn.

  • 0
  • 0
Henrik Wahlberg

.. som data centret på AUC var udstyret med, var en 60 bit maskine.
Det var omkring 1980.

Den kunne holde 10 stk seks bit tegn i et register/hukommelses "celle".
Min foretrukne Pascal compiler havde specielle instruktioner til at håndtere disse 10x6 bit tegn.
Det gik der mange linjer kode med at styre :-)

/henrik

  • 0
  • 0
Mikkel Lauritsen

Mens vi er godt i gang med at snakke sjove CPU'er må man nok også nævne VAX-familien, det måske mest ekstreme eksempel på et ortogonalt CISC-instruktionssæt. Hver instruktion kan fylde op til 54 bytes (hvis ikke mere, se fx https://groups.google.com/forum/#!topic/comp.arch/OJYBg8o7vcQ ), så det kan ikke undre, at Digital havde svært ved at presse dem op på meget mere end 170 MHz.

  • 0
  • 0
Jesper Louis Andersen

Hvis jeg husker rigtigt, så siger standarden bare at du skal have mindst 32 registre for at være en SPARC, men at familien godt kan have flere. Knuth's MMIX har også register windows, men det er som skrevet nok tvivlsomt om det hjælper så meget i praksis. Vi ved godt hvordan vi skal håndtere registre effektivt i compilers i dag, bare vi har en 16+ stykker tilgængelige. Så det er næppe et problem.

Millcomputings Mill architecture er virkeligt interessant. Den gentænker hele CPU-designet, men i modsætning til Itanium så virker det her faktisk gennemtænkt. Torben, burde du ikke have nævnt Itanium eller Transmeta pga VLIW ?

  • 0
  • 0
Jesper B. Rosenkilde

Jeg synes egentlig også at HP's "Saturn" CPU fortjene at blive nævnt, det er den 4-bit CPU der sidder i alle HP's high-end lommeregnere (HP28, HP48 osv.)

Den sad i alle HP's high-end lommeregnere, i alle de nyere, dvs. alle efter HP48, emuleres den af en ARM processor. Grunden til man har valgt at emulere den er nok at der er gået utroligt mange timer i HP's CAS og at det er skrevet i maskinkode.

  • 2
  • 0
Log ind eller Opret konto for at kommentere