Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Re­gis­ter­ma­schi­ne

Die Re­gis­ter­ma­schi­ne (engl. ran­dom ac­cess ma­chi­ne) ist ein Rech­ner­mo­dell der theo­re­ti­schen In­for­ma­tik, das einem rea­len Rech­ner (PC) sehr ähn­lich ist. Dabei gibt es ver­schie­de­ne De­fi­ni­tio­nen einer Re­gis­ter­ma­schi­ne, die sich vor allem im Um­fang der zu­läs­si­gen Ope­ra­tio­nen un­ter­schei­den. Die hier vor­ge­stell­te Re­gis­ter­ma­schi­ne stammt aus dem Be­reich der Kom­ple­xi­täts­theo­rie. Man ver­wen­det sie, um die Kom­ple­xi­tät, d.h. den Zeit­be­darf von Al­go­rith­men ab­schät­zen zu kön­nen, ohne sich auf ein spe­zi­el­les Com­pu­ter­mo­dell zu be­zie­hen. Da man be­wei­sen kann, dass die Re­gis­ter­ma­schi­ne und die Tu­ring­ma­schi­ne in Bezug auf die Be­re­chen­bar­keit gleich­wer­tig sind, kann man davon aus­ge­hen, dass alles, was über­haupt be­re­chen­bar ist, sich mit einer Re­gis­ter­ma­schi­ne be­rech­nen lässt. Die Re­gis­ter­ma­schi­ne kann damit alles, was ein rea­ler Com­pu­ter auch kann, ob­wohl sie sehr ein­fach ge­baut ist und nur we­ni­ge Be­feh­le be­herrscht.

Die Re­gis­ter­ma­schi­ne be­steht for­mal aus

  • einem Pro­gramm be­ste­hend aus end­lich vie­len durch­num­me­rier­ten Be­feh­len

  • einem Be­fehls­zäh­ler b

  • einem Ak­ku­mu­la­tor c(0)

  • und einem un­end­lich gro­ßem Spei­cher aus durch­num­me­rier­ten Spei­cher­zel­len (Re­gis­ter) c(1), c(2), c(3), …

Alle Re­gis­ter (incl. b und c(0)) ent­hal­ten be­lie­big große na­tür­li­che Zah­len. Das Pro­gramm be­steht aus Be­feh­len zum Über­tra­gen der Re­gis­ter­wer­te in an­de­re Re­gis­ter, Be­feh­le für die Grund­re­chen­ar­ten und Sprung­be­feh­len, um an eine an­de­re Stel­le im Pro­gramm zu sprin­gen.

Die Re­gis­ter­ma­schi­ne führt die Be­feh­le des Pro­gramms nach­ein­an­der aus. Es wird immer der Be­fehl mit der Num­mer b aus­ge­führt. Fast alle Be­feh­le er­hö­hen dabei den Be­fehls­zäh­ler um 1, so dass der nächs­te Be­fehl aus­ge­führt wird. Nur die Sprung­be­feh­le set­zen b auf einen an­de­ren Wert, um an eine an­de­re Stel­le im Pro­gramm zu sprin­gen. Die Re­gis­ter­ma­schi­ne endet, so­bald sie auf den Be­fehl HALT trifft. Das Er­geb­nis der Be­rech­nung steht dann in (zuvor) de­fi­nier­ten Re­gis­tern.1

Die­ses Mo­dell ent­spricht weit­ge­hend dem Auf­bau eines rea­len Rech­ners:

Den Be­fehls­zäh­ler, den Ak­ku­mu­la­tor und ei­ni­ge der Spei­cher­zel­len fin­det man im Pro­zes­sor. Der Pro­zes­sor be­steht aus einem Re­chen­werk und einem Steu­er­werk. Das Re­chen­werk ent­hält die ALU (arith­me­tic logic unit) und ei­ni­ge Hilfs- und Sta­tus­re­gis­ter. Die ALU ist in der Lage ein­fa­che lo­gi­sche Ver­knüp­fun­gen und die Grund­re­chen­ar­ten durch­zu­füh­ren (vgl. Ka­pi­tel „Ver­knüp­fung bi­nä­rer Da­ten­wor­te“). Der Ak­ku­mu­la­tor (wird mit AX be­zeich­net) ist eines der Hilfs­re­gis­ter im Pro­zes­sor. Dar­über hin­aus ent­hal­ten reale Pro­zes­so­ren wei­te­re Spei­cher­zel­len, die nicht un­be­dingt not­wen­dig sind, aber die Aus­füh­rung der Be­feh­le be­schleu­ni­gen. Die Core i-Pro­zes­soren be­sit­zen bei­spiels­wei­se 16 Re­gis­ter mit 64 Bit Brei­te, Ita­ni­um-Pro­zes­so­ren sogar 128 Re­gis­ter mit 64 und wei­te­re 128 Re­gis­ter mit 82 Bit.

Im Sta­tus­re­gis­ter wer­den In­for­ma­tio­nen (Flags) über das Er­geb­nis der letz­ten Be­rech­nung ab­ge­legt: War das letz­te Er­geb­nis 0 (Zero-Flag)? War das Er­geb­nis ne­ga­tiv (Sign-Flag)? Diese In­for­ma­tio­nen wer­den für den wei­te­ren Pro­gramm­ab­lauf be­nutzt, um be­ding­te Sprün­ge zu an­de­ren Pro­gramm­stel­len aus­zu­füh­ren.

Die rest­li­chen Spei­cher­zel­len der Re­gis­ter­ma­schi­ne stel­len den Ar­beits­spei­cher (RAM) des Com­pu­ters dar. In einem rea­len Com­pu­ter sind alle Spei­cher­zel­len na­tür­lich nicht be­lie­big groß, son­dern kön­nen nur Zah­len bis zu einem ge­wis­sen Ma­xi­mal­wert auf­neh­men. Im Ge­gen­satz zur for­ma­len De­fi­ni­ti­on, bei der Daten und Pro­gramm ge­trennt sind, liegt auch das Pro­gramm für die Re­gis­ter­ma­schi­ne im Ar­beits­spei­cher.

Das Steu­er­werk ver­wal­tet den Be­fehls­zäh­ler und sorgt dafür, dass die zur Ver­fü­gung ste­hen­den Be­feh­le in die rich­ti­gen Schalt­im­pul­se für die ALU um­ge­setzt wer­den. Der Be­fehls­satz eines rea­len Rech­ners um­fasst alle Be­feh­le, die für die Re­gis­ter­ma­schi­ne de­fi­niert sind. In der Regel be­herrscht er aber ei­ni­ge mehr.

Von-Neu­mann-Ar­chi­tek­tur

Diese Ar­chi­tek­tur wurde schon 1945 von John von Neu­mann vor­ge­schla­gen. Seine ent­schei­den­de Idee aber war es, nicht nur die Daten, son­dern auch das Pro­gramm der Re­gis­ter­ma­schi­ne im Ar­beits­spei­cher ab­zu­le­gen. Nur da­durch wird der reale Com­pu­ter zu einer uni­ver­sel­len Ma­schi­ne. Dies ist für das ma­the­ma­ti­sche Mo­dell der Re­gis­ter­ma­schi­ne un­er­heb­lich, da es hier nur um Lauf­zeit­ab­schät­zun­gen und keine kon­kre­te Um­set­zung geht, und fin­det daher keine Be­rück­sich­ti­gung in der De­fi­ni­ti­on.

Von Neumann Architektur (eigenes Werk)

Von Neu­mann Ar­chi­tek­tur

In einem rea­len Pro­zes­sor sorgt ein Bus­sys­tem für die Über­tra­gung der Daten zwi­schen dem Ar­beits­spei­cher (und wei­te­ren Rech­ner­kom­po­nen­ten) und dem Pro­zes­sor. Die Kom­mu­ni­ka­ti­on des sehr schnel­len Pro­zes­sors mit hohen Takt­ra­ten mit dem ver­gleichs­wei­se lang­sa­men Ar­beits­spei­cher ist nicht un­pro­ble­ma­tisch und kann den Pro­zes­sor aus­brem­sen. Das Bus­sys­tem wird daher auch als Von-Neu­mann-Fla­schen­hals be­zeich­net. In den An­fangs­jah­ren der Com­pu­ter war der Pro­zes­sor das lang­sams­te Bau­ele­ment, so dass die Nut­zung eines ein­zi­gen Bus­ses für die Da­ten­über­tra­gung von Daten und Pro­gramm­be­feh­len kein Pro­blem war. In­zwi­schen sind die Pro­zes­so­ren aber um ein Viel­fa­ches schnel­ler als das Bus­sys­tem. Daher wer­den zahl­rei­che Maß­nah­men er­grif­fen (L2-Cache-Spei­cher = schnel­ler Spei­cher im Pro­zes­sor; Vor­her­sa­ge von Spei­cher­zu­grif­fen, um die Daten schon vor­her zu laden; usw.), um die Aus­wir­kun­gen zu be­gren­zen. Im Fol­gen­den wird nur das Pipe­lining an­ge­spro­chen.

Wenn die Pro­gram­me sich ge­nau­so wie die Daten im Ar­beits­spei­cher be­fin­den, müs­sen die ein­zel­nen Be­feh­le vor der Aus­füh­rung in den Pro­zes­sor über­tra­gen wer­den und dort in die Schalt­im­pul­se für die ALU über­setzt wer­den. Der Von-Neu­mann Zy­klus be­schreibt die­sen Vor­gang:

FETCH

Von Neumann-Zyklus

Von Neu­mann-Zy­klus

In das Be­fehls-Re­gis­ter (OP = Ope­ra­ti­on Poin­ter) wird aus dem Ar­beits­spei­cher der Ma­schi­nen­code des nächs­ten zu be­ar­bei­ten­den Be­fehls ge­la­den.

Bei mo­der­nen Pro­zes­so­ren kön­nen meh­re­re Be­feh­le (etwa 10-20 Be­feh­le) aus dem Spei­cher in einen Zwi­schen­spei­cher (Pre­fetch-Re­gis­ter­block) ge­la­den wer­den, wäh­rend der ak­tu­el­le Be­fehl noch de­co­diert wird (Op­Code Pre­fet­ching). Dies wird als Pipe­lining be­zeich­net.

  • Vor­teil: Deut­li­che Stei­ge­rung der Ver­ar­bei­tungs­ge­schwin­dig­keit.

  • Nach­teil: Bei Pro­gramm­ver­zwei­gun­gen müs­sen Be­feh­le evtl. wie­der ent­fernt wer­den.

DE­CO­DE

Der Be­fehl aus dem OP-Re­gis­ter wird durch das Steu­er­werk in Schal­tin­struk­tio­nen für das Re­chen­werk auf­ge­löst. Dabei muss ein ein­zel­ner Be­fehl in ganze Se­quenz von Steu­er­si­gna­len über­setzt wer­den. Eine ein­fa­che und be­währ­te Mög­lich­keit ist die Spei­che­rung der Ab­läu­fe in einem ROM-Bau­stein (Read-Only-Me­mo­ry). Wel­che Spei­cher­stel­le des ROM aus­ge­le­sen wird, wird durch das OP-Re­gis­ter, den Zu­stand des Sta­tus­re­gis­ters (Flags) und durch Ein­stel­lun­gen im ROM-Bau­stein selbst fest­ge­legt. Jede Aus­ga­be von Steu­er­si­gna­len führt zu einem Wech­sel auf eine neue Adres­se, so dass sich eine Se­quenz von Steu­er­si­gna­len er­gibt. Durch eine ge­eig­ne­te Aus­wahl der Fol­ge­adres­se sind auch Wie­der­ho­lun­gen und Ver­zwei­gun­gen mög­lich. Man spricht daher von Mi­kro­pro­gram­mie­rung und be­zeich­net den Spei­cher­bau­stein als Mi­kro­pro­gramm­spei­cher (Mi­kro­code-ROM)2.

FETCH OPE­RAN­DS

Aus dem Ar­beits­spei­cher wer­den nun die Ope­ran­den ge­holt, d.h. Werte, die als Pa­ra­me­ter ver­wen­det wer­den.

Mo­der­ne Pro­zes­so­ren (z.B. Intel Core) ken­nen das „spe­ku­la­ti­ve Laden“: Das Steu­er­werk star­tet das (mög­li­cher­wei­se) lang­wie­ri­ge Laden von Ope­ran­den, so­bald in der Pipe­line ein La­de­be­fehl auf­taucht. Wird nun vor­her ein Schreib­be­fehl aus­ge­führt, der diese Daten ver­än­dert, müs­sen die zu früh ge­la­de­nen Daten ver­wor­fen und er­neut ge­la­den wer­den. Im Durch­schnitt wird die Ver­ar­bei­tung da­durch aber be­schleu­nigt3.

EXE­CU­TE

Die Se­quenz von Schalt­im­pul­sen wird vom Re­chen­werk aus­ge­führt. Eine ein­zel­ne Steu­er­an­wei­sung kann dabei meh­re­re Takt­zy­klen be­nö­ti­gen. Ein gan­zer Ma­schi­nen­be­fehl, also die ganze Se­quenz von Steu­er­si­gna­len, be­nö­tigt in der Regel also viele Takte.

UP­DATE PRO­GRAM COUN­TER

Der Be­fehls­zäh­ler (IP = In­struc­tion Poin­ter) muss er­höht wer­den, damit er auf den nächs­ten Be­fehl im Ar­beits­spei­cher zeigt.

Jetzt kann der Zy­klus wie­der von vorn be­gin­nen.

Re­gis­ter­ma­schi­nen-Si­mu­la­tor

Das ma­the­ma­ti­sche Mo­dell kann – er­gänzt um das Bus­sys­tem – in einem Si­mu­la­ti­ons­pro­gramm um­ge­setzt wer­den. Alle dabei be­nö­tig­ten Kom­po­nen­ten be­ste­hen aus ein­fa­chen elek­tro­ni­schen Schal­tun­gen, die in den vor­an­ge­gan­gen Ka­pi­teln be­spro­chen wur­den.

Die ALU ent­hält die lo­gi­schen Ver­knüp­fungs­ope­ra­tio­nen und ein­fa­che ma­the­ma­ti­sche Funk­tio­nen. Für viele An­wen­dun­gen rei­chen Ad­di­ti­ons- und Sub­trak­ti­ons­schal­tun­gen. Die Re­gis­ter kön­nen durch Flip­Flops rea­li­siert wer­den. Das Bus­sys­tem kann durch eine ein­fa­che Tor­steue­rung si­mu­liert wer­den.

Damit kann aus ein­fa­chen Bau­ele­men­ten ein Si­mu­la­tor auf­ge­baut wer­den, der theo­re­tisch jedes be­re­chen­ba­re Pro­blem lösen kann. Die Be­gren­zung des Ar­beits­spei­chers im Si­mu­la­ti­ons­pro­gramm stellt dabei eine not­wen­di­ge Ein­schrän­kung eines rea­len Pro­gramms dar. Die Re­gis­ter­ma­schi­ne ist damit zwar keine uni­ver­sel­le Ma­schi­ne mehr, kann aber trotz­dem eine Viel­zahl von Pro­ble­men lösen.

Eine wei­te­re Ein­schrän­kung stellt die Be­schrän­kung der Re­gis­ter­brei­te auf eine feste Bit­zahl dar. Durch diese Ein­schrän­kung, die auch für reale Com­pu­ter gilt, kön­nen nicht be­lie­bi­ge große Zah­len ge­spei­chert wer­den, son­dern nur bis zu einem ge­wis­sen Ma­xi­mal­wert. Dies hat Aus­wir­kun­gen bei der Ver­wen­dung von Va­ria­blen beim Pro­gram­mie­ren, die not­wen­di­ger­wei­se immer einen be­schränk­ten Wer­te­be­reich haben (vgl. Lö­sung Mi­kro­sim-Skript Aufg. 1k). Ad­diert man zum Ma­xi­mal­wert 1 hinzu, lan­det man beim kleinst­mög­li­chen Wert (vgl. 2-er Kom­ple­ment­dar­stel­lung). Sol­che Über­läu­fe sind im ma­the­ma­ti­schen Mo­dell der Re­gis­ter­ma­schi­ne nicht vor­ge­se­hen.

Der Be­fehls­satz der Re­gis­ter­ma­schi­nen-Si­mu­la­to­ren um­fasst in der Regel in etwa den Be­fehls­satz, der für das Re­gis­ter­ma­schi­nen­mo­dell in der Kom­ple­xi­täts­theo­rie de­fi­niert wird. Ein Ma­schi­nen­be­fehl be­steht dabei aus einem Ope­ra­ti­ons­teil und einem Ope­ran­den­teil.

  • Der Ope­ra­ti­ons­teil gibt die Ein­sprung­stel­le im Mi­kro­pro­gramm­spei­cher an. Da diese Adres­sen schwer zu mer­ken sind, wer­den ihnen eine Be­fehls­be­zeich­nun­gen, wie add für ad­die­ren oder mov für Da­ten­trans­fer zu­ge­ord­net. Diese Be­fehls­be­zeich­nun­gen bil­den eine As­sem­bler­spra­che.

  • Der Ope­ran­den­teil be­inhal­tet den Ope­rand als di­rek­ten Wert (z.B. 05) oder als RAM-Adres­se (Dar­stel­lung mit ecki­ger Klam­mer z.B. [05]). Dabei be­schränkt man sich auf einen Ope­rand. Die Ar­beit mit (ma­xi­mal) 1-Ope­rand-Be­feh­len hat zur Folge, dass zwei­stel­li­ge Ope­ra­tio­nen ein fest de­fi­nier­tes Re­gis­ter als wei­te­ren Ope­rand ver­wen­den und das Er­geb­nis an der Stel­le des ers­ten Ope­ran­den spei­chern.

    z.B. ADD AX, 05 => Die Zahl 05 zu AX ad­diert und das Er­geb­nis wie­der in AX ge­spei­chert. AX ist hier kein Ope­rand, son­dern Teil der Ope­ra­ti­on. ADD BX, 05 ist also eine an­de­re Ope­ra­ti­on. Da­durch er­reicht man die Be­schrän­kung auf 1-Ope­rand-Be­feh­le.

Die Re­gis­ter­ma­schi­ne de­fi­niert Be­feh­le zur Über­tra­gung zwi­schen Re­gis­tern und Ar­beits­spei­cher, ein­fa­che Re­chen­ope­ra­tio­nen (In­kre­ment, De­kre­ment, Ad­di­ti­on, Sub­trak­ti­on, Mul­ti­pli­ka­ti­on, Di­vi­si­on) und Sprung­be­feh­le, die den Pro­gramm­ab­lauf be­ein­flus­sen. In voll­stän­di­gen As­sem­bler­spra­chen gibt es da­ne­ben noch Be­feh­le für den Auf­ruf von Un­ter­pro­gram­men, Stack-Be­feh­le (ein Sta­pel er­leich­tert die Aus­wer­tung von Ter­men), Be­feh­le zum Auf­ruf von Be­triebs­sys­tem-Be­feh­len, uvm.

Viele Be­feh­le exis­tie­ren in zwei Ver­sio­nen: z.B. MOV AX, BX und MOV AX,[BX]. Die erste Va­ri­an­te über­trägt den Wert von BX nach AX. Die zwei­te Va­ri­an­te über­trägt den Wert aus dem RAM, der an der Adres­se BX steht. Sie ist hilf­reich, um ein Array zu rea­li­sie­ren. Das BX-Re­gis­ter kann hoch­ge­zählt wer­den und damit auf eine Reihe von auf­ein­an­der­fol­gen­den Spei­cher­adres­sen zu­ge­grif­fen wer­den.

Die Sprung­be­feh­le be­ein­flus­sen weder den Wert der Hilfs­re­gis­ter noch den RAM. Sie sind dazu ge­dacht den Pro­gramm­auf­lauf zu steu­ern. Da der nächs­te aus­zu­füh­ren­de Be­fehl im Be­fehls­re­gis­ter des Steu­er­werks (IP = In­struc­tion Poin­ter) steht, muss dazu le­dig­lich die­ses Re­gis­ter an­ge­passt wer­den. In Ab­hän­gig­keit der Sta­tus­re­gis­ter kön­nen dabei be­ding­te Sprün­ge aus­ge­führt wer­den, d.h. Sprün­ge, die nur dann aus­ge­führt wer­den, wenn ein be­stimm­tes Flag ge­setzt ist, bzw. nicht ge­setzt ist. Die wich­tigs­ten sind

  • JZ = Sprung, wenn das Zero-Flag ge­setzt ist, d.h. das Er­geb­nis der letz­ten Be­rech­nung Null er­ge­ben hat

  • JNZ = Sprung, wenn das Zero-Flag nicht ge­setzt ist.

  • JS = Sprung, wenn das Sign-Flag ge­setzt ist, d.h. das Er­geb­nis der letz­ten Be­rech­nung ne­ga­tiv ist (d.h. das erste Bit ge­setzt ist)

  • JNS = Sprung, wenn das Sign-Flag nicht ge­setzt ist.


1 De­fi­ni­ti­on der Re­gis­ter­ma­schi­ne aus Seite Re­gis­ter­ma­schi­ne. In: Wi­ki­pe­dia, Die freie En­zy­klo­pä­die. Be­ar­bei­tungs­stand: 22. Au­gust 2011. (Ab­ge­ru­fen: 24. Sep­tem­ber 2011)

2 Wüst, Klaus: Mi­kro­pro­zes­sor­tech­nik: Grund­la­gen, Ar­chi­tek­tu­ren und Pro­gram­mie­rung von Mi­kro­pro­zes­so­ren, Mi­kro­con­trol­lern und Si­gnal­pro­zes­so­ren, View­eg+Teub­ner, S.91

3 Wüst, Klaus: Mi­kro­pro­zes­sor­tech­nik: Grund­la­gen, Ar­chi­tek­tu­ren und Pro­gram­mie­rung von Mi­kro­pro­zes­so­ren, Mi­kro­con­trol­lern und Si­gnal­pro­zes­so­ren, View­eg+Teub­ner, S.212

 

 

Hin­ter­grund­in­for­ma­tio­nen: Her­un­ter­la­den [odt][4 MB]

 

Wei­ter zu Pro­gram­mie­rung