Livet uden XOR

Data Generals NOVA CPU var i praksis den første rigtige RISC CPU.

Det betød blandt andet at den ikke havde nogen "OR" instruktion, men som alle der har haft boolsk algebra ved, kan man lave "OR" ud af "AND" og nogle invertere.

Men man kan gøre sådan her:

14. Perform the inclusive OR of the operands in AC0 and
    AC1.  The result is placed in AC1.  The carry bit is
    unchanged.
 
     COM     0,0     // AC0 = ~AC0
     AND     0,1     // AC1 &= AC0
     ADC     0,1     // AC1 += ~AC0

Men det bliver bedre endnu, for der var heller ikke nogen "XOR" instruktion, men derimod:

15. Perform the exclusive OR of the operands in AC0 and
    AC1.  The result is placed in AC1.  The contents of
    AC2 and the carry bit are destroyed.
 
     MOV     1,2     // AC2 = AC1
     ANDZL   0,2     // AC2 = (AC2 & AC0) << 1
     ADD     0,1     // AC1 += AC0
     SUB     2,1     // AC1 -= AC2

Eksemplerne er fra Regnecentralens manual for "RC3803" videreudviklingen af Nova CPU'en og kan findes omkring side 120 i RCSL-42-I-1008 manualen.

Weekendens datahistoriske hjernevrider er at forklare hvordan de to stykker kode virker og hvorfor XOR ødelægger carry bit, mens OR kan lade den være uændret.

phk

Kommentarer (11)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Thue Kristensen

XOR synes jeg faktisk er den simpleste. Du adderer de to, hvilket på en given plads giver 1 præcis hvis de to bits på en plads er forskellige. Der er bare problemet med hvis de begge to er 1, så bliver der fejlagtigt adderet 1 til cifferet over. Så du finder de pladser hvor begge er 1, flytter dem en til venstre, og trækker dem fra. Hvis AC0 og AC1 er vilkårlige værdier, så er det klart at "AC1 += AC0" kan overflowe, og derved sætte carry-bitten.

Ved OR kan man betragte hver bit isoleret. Man udregner først C = A & NOT B. Når man derefter udregner C+B, så ved man at C og B ikke begge er 1, da C indeholde NOT B så ingen mulighed for carry. Hvis B er 1, så er det klart at resultatet er 1. Hvis det oprindelige A er 1, så er C 1 præcis hvis B ikke er 1, dvs at resultatet C+B er korrekt 1 hvis A OR B.

  • 1
  • 0
Jacob Christian Munch-Andersen

For at forklare carry bitten skal det lige med at instruktionerne ikke bare sætter den når de overflower. Først specificerer instruktionen om bitten skal være 0, 1, flippes, eller lades være. Derefter flippes bitten hvis instruktionen overflower. Det vil sige at man også kan bevare carry bitten hvis man ved at instruktionen overflower, eller hvis blot man ved at en serie af instruktioner altid overflower enten et lige eller et ulige antal gange.

Det kan man dog ikke vide med denne XOR kode, dertil bruger shift modifikationen carry bitten til at fylde den tomme plads, så koden bliver nødt til at sætte carry bitten til 0 for at få det ønskede resultat.

  • 0
  • 0
Torben Mogensen Blogger

Nova havde ganske vist et meget forenklet instruktionssæt, men den havde en feature, der går imod de normale kriterier for RISC: Et indirection bit.

Hvis man laver et indirekte hop, og den hentede adresse har den højeste bit sat, henter man en ny hopadresse på denne adresse (minus det højeste bit), og så fremdeles i en ubegrænset kæde af indirections.

Det betyder, at en instruktion kan tilgå et ubegrænset antal adresser. En af de almindelige RISC kriterier er, at en instruktion kun tilgår et sammenhængende område i lageret, og at dette har en begrænset størrelse.

Den første "rigtige" computer, jeg programmerede, var en RC7000, en Nova som Regnecentralen videresolgte under eget navn. Jeg programmerede den dog aldrig i maskinsprog, men kun i COMAL.

  • 1
  • 0
Chris Bagge

For god ordens skyld så kan PDP-8 kun AND "0xxx"og ADD "1xxx". Der kan laves complement af akkumulatoren "7040" og så er det muligt at lave OR med MQ registeret "7501". Derudover "udmærker" PDP-8 sig ved ikke at have en stak. Ved et subrutine kald bliver returadressen lagt i den første celle af subrutinen. At kalde dette en CISC er måske at overdrive.

  • 0
  • 1
Poul-Henning Kamp Blogger

Nova havde ganske vist et meget forenklet instruktionssæt, men den havde en feature, der går imod de normale kriterier for RISC: Et indirection bit.

Taget i betragtning at "kriteriet" kommer væsentligt senere end DG Nova, kunne man lidt skeptisk overveje om ikke de der, efter at have opstillet kriteriet havde planlagt en stor markedsføring deraf også havde sikret sig at det var formuleret så ingen kom og pegede på "prior art" :-)

Indirekte bit'en taler i min optik ikke imod RISC princippet, tværtimod nærmest.

Men de 2 gange 8 magiske "auto-increment" og "auto-decrement" memory locations gør derimod. De bliver dog stort set aldrig brugt så vidt jeg ved...

Men når det lange og det korte er gjort op, så designede DG Nova'ens instruktionssæt efter den præcis samme ide som de efterfølgende RISC designs: Hardwarenært og med mål om en instruktion per clockcycle.

Læs f.eks The Woz' begejstrede erindringer om hvor simpelt det var.

Sjovt nok er implementeringen faktisk ikke lavet så simpelt som den kunne være fra DG's side, fordi man ved at krølle ting lidt sammen kunne bruge TTL 4-bits ALU.

En af implementeringerne har sågar kun én sådan ALU chip og køre fire gange igennem med hver 4 bit for hver instrution.

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