Samenvatting Geavanceerde Computerarchitectuur

Samenvatting Geavanceerde Computerarchitectuur Dumon Willem 2009-2010

12

P ROCESSOR S TRUCTURE & F UNCTION

12.1

Registers

• User-visible registers: toegankelijk vr programmeur – general purpose-reg: versch functies OF toch vr bep functies (vb enkel floating point) – data registers: enkel data, nt bruikbaar in berekeningen v adressen – adres registers: algemeen OF bep specifieke adresmode (segment, index of stack pointers) → berekenen v adressen – condition codes = flags: gezet als resultaat v operaties (k gelezen w, nt geschreven) general ↔ specifiek: design-beslissingen (flexibel-simpel ↔ snel) • controle & statusregisters: program counter PC, instruction register IR, memory adress register MAR, mem buffer reg MBR, program status word PSW (sign, zero, carry, equal, ...) • supervisor mode = kernel mode: gepriviligeerde instr’s uitvoeren dr OS • andere registers: wijzen nr Process Control Blocks, interrupt vectors,...

12.2

Instruction Cycle

Figuur 1: Normale instruction cycle & uitbreiding met indirecte cycle • Indirect cycle als indirecte adressen gebruikt (meer mem-access) → extra cycle/stage nodig • Data flow: 1

Samenvatting Geavanceerde Computerarchitectuur

– Fetch cycle: volgende instr in PC, adres → MAR → adresbus, Ctrl Unit CU vraagt memread → result op databus → MBR → IR, PC++ – Indirect cycle: IR bekijken, als indirect → N meest rechtse bits v MBR → MAR, CU vraagt mem-read, result (adres v operand) nr MBR – Execute cycle: afh v instr (mem-read/write, I/O, register transfers, ALU-ops) – Interrupt Cycle: PC opslaan (vr hervatten) in MBR (vb op stack), adres (SP) → MAR, MBR → mem, PC geladen met adres v interrupt handler → 1e instr v interrupt handler fetchen

12.3

Instruction Pipelining

• cf assembleerlijn/lopende band → alles na elkaar in versch ‘stages’ • 2-stage pipeline → fetchen = mem-access ↔ execute mstal nt ⇒ apart doen: volgende instr bufferen tijdens executie vorige (prefetch, fetch overlap) executie duurt langer & dr branching volgend adres nt direct gekend → wachten • 6-stage pipeline: Fetch Instruction, Decode Instruction, Calculate Operands, Fetch Operands, Execute Instruction & Write Operand ⇒ ≈ zelfde tijdsduur • problemen: – niet alle instries alle stages – sommige stages k nt samen (mem-conflict) ↔ waarden in cache steken & sommige stages niet nodig bij sommige instries dus compenseert – tijdsduur verschillend – (conditional) branching: fetch ed vr niets gedaan, idem vr interrupts – dependencies → wachten op vorige – # stages↑ op bep punt nt mr nuttig (overhead, vl ctrl logic nodig) ⇒ optimum zoeken! • pipeline hazards: deel v pijplijn gestopt omdat omstandigheden gn continue uitvoering toelaten ≈ pipeline bubble (cf luchtbel) 1. resource hazard: versch instries h zelfde resource nodig (single port mem & gn cache) 2. data hazard: true data- (RAW), anti- (WAR) & output dependency (WAW) 3. control = branch hazard: verkeerde branch-beslissing → pipeline clearen – multiple streams: meerdere pijplijnen maken per ‘tak’ → extra delays want meer instries & in versch streams ng branch = weer extra streams – prefetch branch target: bij conditional branch volgende instr + doel v branch fetchen (⇒ beide mogelijkheden fetchen) – loop buffer: heel snel geh (cf cache) met laatste fetches (in volgorde) → deze buffer checken vr mem-fetch ⇒ in volgorde dus geen mem-accesstijd, als if-then-else zit alles in buffer, ideaal vr kleine loops/jumps – branch prediction: ∗ predict never taken ↔ predict always taken 2009-2010

p2


∗ predict by opcode: afh v instr maken ∗ taken/not taken switch: afh v vorige, bits opslaan in temp high-speed-storage, # bits bepaalt lengte gesch ∗ branch history table = klein cache-geh, elke entry = adres v branch instr + geschbits + adres v branch-doel/branch-instr zelf (afh v implementatie) verbetering: nt enkel gesch v huidige branch, maar ook v N laatste branches gebruiken – delayed branch: progr herschikken dat branches later voorkomen • Intel 80486 pipelining: Fetch + Decode stage 1 (opcode & adresmode in 1e 3 bytes) + Decode stage 2 (rest v instr) + Execute + Write Back

13

R EDUCED I NSTRUCTION S ET C OMPUTERS RISC • >> general purpose-registers (reg-gebruik optimaliseren) + kleine simpele instructie set IS + nadruk op instr-pipeline-optimalisatie • High-level-progr talen (HLL) ⇒ semantic gap: architecturen k nt mee → complexere arch’en CISC ↔ RISC: simpeler ipv complex • dynamische studies → executie v progr meten adhv – operaties: simpele verplaatsing v data & sequentiectrle bel, call-return = tijdrovend – operands: meestal locale scalaire variabelen → dit optimaliseren – procedure-aanroepen: tijdrovend, afh v # parameters/locale variabelen & v nestinglevel • RISC ⇒ vl registers of compiler-based registergebruik optimalisatie (operand-referenties) + pipelines goed ontwerpen (branching/calls) + simpele kleinere instructieset

13.1

Grotere registers

lokale scalaire variabelen in registers → mem-access↓ ⇒ HW: ‘register windows’ • → meer registers, per procedure CPU naar vast # registers (window) laten kijken ipv registers op te slaan & andere op te halen in mem bij call & return • registerwindow

parameterreg = parameters v methode die deze methode opgeroepen heeft = temp-reg v callprocedure (fysisch dezelfde!) • # registerwindows vr recente procedure-activaties, oudere naar mem ⇒ cirkelvormige buffer door overlappingen, SWP & CWP, als buffer vol oudste naar mem 2009-2010

p3


• reg-set vr globale variabelen behouden! anders te vl mem-access

Figuur 2: Grotere registers vs cache

13.2

Compiler-based register optimalisatie

• beperkt # reg’s (HW) → reg’s toekennen obv meest gebruikte variabelen: complexe progranalyse! • ∞ # symbolische reg’s mappen op # echte reg’s → symbolische die nt overlappen k zelfde gebruiken, als niet genoeg reg’s → geh gebruiken • Graph Colouring! als gn kleuren genoeg → in geheugen

13.3

RISC architectuur

• wrom CISC?

2009-2010

p4


– simpelere compiler? nt zkr: complexe machine-instries moeilijker optimaal te gebruiken, optim moeilijker (passen quasi nooit perfect met HLL) – kleinere progr’s? minder geh nodig MAAR geh-kost↓, kortere symbolische vorm ↔ evenveel bits (meer instries = langere opcode), reg’s-referenties = minder bits – snellere progr’s? CU complexer & µprogr control store vl uitgebreider → exec-time↑ • RISC karakteristieken – 1 instr/machine-cycle: 2 operands fetchen uit geh + ALU + result wegschrijven → hardwired maken ipv microcode – zovl mog reg-naar-reg-operaties: enkel load en store nodig → IS & CU simpeler + optim v reg-gebruik nodig – 1 of enkele simpele adresseringsmodes → IS & CU simpeler – 1 of enkele simpele instructieformaten: vaste lengte (words) & veldlocaties (vral opcode) → opcode decoderen & reg-operand ophalen tegelijkertijd ⇒ meer berekenen @ compile-time (opsplitsen in simpelere instr’s) =⇒ ontwerpers gebruiken delen v CISC & RISC

13.4

RISC Pipelining

• met nrmle instr’s: meestal reg-naar-reg-operaties (instr fetch I + execute E (ALU met reg IO)) als load&store operaties: I + E (mem-adres berekenen) + D (reg-naar-geh of geh-naar-reg operatie)

fig b) & c) NOOP omdat branch de sequentiële voortgang onderbreekt fig c) NOOP owv true data dependency! fig d) = c) maar E gesplitst (duurt langst → E1 = reg-read, E2 = ALU-op + reg-write) → even lange stages • optimalisatie:

2009-2010

p5


– delayed branch: NOOP nodig na branch → nuttige instr daar zetten! gemakkelijk bij unconditional branches & call/returns ↔ conditional: conditie k aangetast w dr voorgaande instructie daar te zetten ⇒ andere zoeken of NOOP – delayed load: instr’s reorganiseren dat nuttig werk k w verricht tijdens load (duurt lang) – loop unrolling: ‘body’ v lus in lus u maal herhalen & lus in stappen v u overlopen → lus-overhead↓, parallellisme↑ & betere reg/datacache gebruik

14

I NSTRUCTION - LEVEL PARALLELISM & S UPERSCALAR P ROCES SORS • superscalair = nrmle instr’s (ALU, floating points, integers, load/store, condit.branches) k gelijktijdig gestart & onafh uitgevoerd w → meerdere onafh pipelines ⇒ std methode om highperformance µCPU’s te implementeren • superpipelined: vl stages doen tasks die < halve clockcycle duren → interne freq x2 ⇒ 2 tasks in 1 externe clockcycle • instr-level parallellisme: graad waarin (gem) instr’s parallel k w uitgevoerd ⇒ beperkingen: – True data dependency = flow dep = Read After Write RAW – Procedural dep: instr’s na branch (genomen of niet) k nt parallel met instr’s vr branch w uitgevoerd (zelfde in gwne scalaire pijplijn mr erger) als instr-lengte nt vast m ganse instr w gedecodeerd om # fetches te weten – Resource conflict: 2+ instr’s die tegelijkertijd zelfde bron willen → bron 2x (vb ALU)

14.1

Ontwerpkwesties

• Instr-lvl parallellisme: afh v true data & procedural dependencies • machine-lvl parallellisme: vermogen v CPU om gebruik te maken v instr-lvl parall., afh v # instr’s die k w gefetchd & uitgevoerd tegelijkertijd = # pipelines Als nt genoeg instr’lvl parall → nt volledig gebruik maken machine-lvl parall & beperkte machine-lvl parall beperkt performantie onafh v programma-aard

2009-2010

p6


• Instr issue policy = protocol hoe instr’s v decode stage nr 1e execute stage gn → CPU kijkt vooruit nr welke instr’s i/d pipeline k w gebracht 3 volgordes belangrijk: fetch-volgorde, execute-volgorde & volgorde wrin instr’s reg’s & geh aanpassen ⇒ pipeline optimaliseren = volgorde aanpassen (mr resultaat moet kloppen!): 1. in-order issue met in-order completion: nt efficiënt, instr’s m soms w8en, kan wel >1 instr fetchen 2. in-order issue met out-of-order compl: perform↑ v instr die meerdere cycles nodig h 3. out-of-order issue met out-of-order completion → output dep (WAW) ⇒ complexe logica nodig + moeilijk interrupts afhandelen → anti-dependency (WAR): instr k nt afronden vrdat andere zijn operands heeft opgehaald

in-order issue = CPU decodeert instr’s tt dep & stopt tt dep opgelost ↔ out-of-order: decodestage & exec-stage ontkoppelen → buffer = instr window: fetch+decode tt buffer vol & als functionele 1heid vrij instr uit window halen ⇒ CPU k vooruit kijken MAAR dep’s/conflicten k instr’s blokkeren in instr window • Register renaming: opl vr anti- & output-dep’s (wrbij waarden in reg’s nt mr kloppen met gang v progr)

→ R3c vermijd anti-dep in I2 en output-dep in I1 ⇒ I3 k direct gelanceerd w 2009-2010

p7


• Machine parallelisme: 1. base = gn functionele units gedupliceerd, wel out-of-order issuing mogelijk 2. +ld/st = base + extra load/store unit 3. +alu = base + extra ALU 4. +both = base + extra load/store + ALU ⇒ dupliceren units nt nuttig zonder reg’s renaming & groot genoeg instr window nodig (>8) • Branch Prediction: vb 80486 fetched volgende instr + doelinstr v branch → als branch genomen 2 cycles kwijt want 2 stages tss prefetch & exec delayed branch bij RISC? nt nuttig vr superscalair → meerdere instr’s uitvoeren in delay-slot & instr dep problemen • Superscalaire exec:

• Superscalaire impl: – gelijktijdig versch instr’s fetchen: versch fetch & decode stages + branch prediction logica – logica die true-data-dep bepaalt ivm reg-waarden + mechanismen die deze waarden doorgeven waar nodig – mechanismen om versch instr’s parallel te lanceren (= issuing) – bronnen om versch instr’s parallel uit te k voeren – mechanismen om processtatus in juiste volgorde te comitten na out-of-order completion

14.2

Pentium 4

• operaties: 1. instr’s fetchen in statische volgorde v geh 2. instr vertalen in vaste-lengte-RISC-instr = micro-operaties = µops 3. µops uitvoeren in superscalaire pipeline: out-of-order execution kan 4. resulten v µops comitten nr reg-set in originele progr-volgorde • P4 = extern CISC met interne RISC-kern (20-stages-pijplijn) 2009-2010

p8


15

C ONTROL U NIT O PERATION

15.1

Micro-operaties

• stages v pipeline bestaan uit µops = atomische acties v CPU • FETCH CYCLE 1. PC = adres v volgende instr → MAR → adresbus 2. CU lanceert READ-commando → resultaat op databus → MBR & parallel PC+=instr.length 3. data (instr) v MBR → IR ⇒ MBR vrij vr volgende data fetch ⇒ 3 tijdstappen/4 µops

µops groeperen kan (vb PC=+I kan ook in t3) → juiste volgorde behouden & conflicten vermijden (vb nt schrijven & lezen in zelfde reg: onvrspelbr) • INDIRECT CYCLE 1. adresveld v instr → MAR 2. MAR gebruikt om adres v operand op te halen 3. adresveld v IR upgedate v MBR → direct adres in IR

• INTERRUPT CYCLE (afh v machine) 1. inhoud PC → MBR: opslaan om terug te keren v interrupt 2. adres waar PC op te slaan → MAR & parallel adres v interrupt-routine in PC 3. MBR (oude waarde PC) → geheugen

2009-2010

p9


⇒ minimum # µops: adressen ophalen k meerdere µops vereisen

• EXECUTE CYCLE: afh v instr (N versch opcodes = N versch µop-sequenties • INSTRUCTION CYCLE = alle vrgaande aan elkaar hangen (ICC = Instr Cycle Code)

15.2

Processorcontrole

1. basiselementen v CPU definiëren: ALU, reg’s, interne data-paden, externe- & controle unit 2. types µops: transfer tss reg’s, v reg nr extern, extern nr reg & arithmetische of logische ops 3. CU-fties : sequencing (CPU dr µops laten gn in volgorde v progr) & zorgen vr executie v elke µop → adhv ctrlesignalen interactie CU ↔ andere elementen v processor: • inputs: clock, IR (= opcode huidige instr), flags (status CPU & resultaat vorige µop) & ctrlsignn v controlebus (interrupts & ACK’s) • outputs: – in CPU: zorgen voor databeweging & specifieke fties activeren – via controlebus: naar geheugen & I/O-modules 3 types controlesignalen: activeer ALU-ftie , activeer datapad & signalen op externe systeembus of iface (cf figuur)

2009-2010

p 10


interne CPU-organisatie → meestal 1 interne bus als datapad ⇒ controlesignn vr verplaatsen data v&nr bus v elk reg + temp reg’s nodig vr goeie werking ALU (Z-Y)

15.3

Hardwired implementatie

• CU = combinatorisch circuit: inputs w gecomb tt set output-signn = controlesignn • 4 inputsignalen: 1. flags & controlbus: elke bit betekent iets 2. IR: adhv opcode versch controlesignalen vr versch instr → unieke logica/opcode geëncodeerde input → DECODER → 1 output (n binaire inputs & 2n outputs) 3. clock: meten tijdsduur µops, periode lang genoeg om signaal te k laten voortplanten dr interne logica CU zendt versch controlesignalen op versch tijdstippen in 1 instr-cycle (versch µops per instr-cycle) → versch periodes ⇒ counter nodig • CU Logic → vr elk signaal booleanse expressie afleiden adhv inputs ⇒ vb in boek: P/Q cf ICC

2009-2010

p 11


15.4

Nadelen

complex: vl booleanse logica/expressies, complexe sequenties, moeilijk ontwerp/testen, nt flexibel (moeilijk aanpas/uitbreidbr) MAAR sneller dan microprogrammering & circuits/tools veel beter

16

M ICROPROGRAMMED C ONTROL

16.1

Basisconcepten

• mircroprogr = firmware = sequentie v micro-instr’s, die elk bestaan uit µops → tss HW & SW • CU maakt vr elke µop set v ctrl-signn (aan of uit) → alle ctrl-signn binair voorstellen o/e rij = ctrl word met elke bit = ctrl-sign/ctrl-lijn ⇒ elke µop = versch patroon in ctrl-word • sequentie v ctrl-words per machinecode instr + adres nr volgende µinstr (afh v conditiebits) = horizontale µintsr (1 µinstr = versch bits op 1 ⇒ meerder µops)

• interpretatie: 1. µinstr uitvoeren = alle ctrl-lijnen wrv bit = 1 aanzetten, andere uitlaten → juiste µops uitgevoerd 2. als vw dr conditiebits = false → volgende µinstr in volgorde uitvoeren 3. als vw dr conditiebits = true → volgende µinstr aangegeven in adresveld • Control Memory CM = verzameling alle µinstr’s, sequentieel, behalve laatste v cycle h branch • organisatie CM → volgorde v cycles (execute = vast adres wrin adres nr juiste routine staat, afh v nodige opcode) • architectuur CU: 2009-2010

p 12


– CM: set µinstr’s – ctrl adresreg: adres v volgende instr – ctrl bufferreg: als µinstr gelezen uit CM = ook uitgevoerd want linkerdeel v buffer = verbonden met ctrl-lijnen – sequencing logic: laad ctrl-adresreg & lanceert read-commando

(a) Control memory organisatie

(b) Control Unit architectuur

• functionering (alles in 1 clock-puls!) 1. sequencing logic lanceerd read-commando naar ctrl-mem 2. woord wrnaar adres in ctrl-adresreg verwijst is ingelezen in ctrl-bufferreg = controlebits 3. inhoud v ctrl-bufferreg genereert ctrl-signn & volgend adres vr sequencing logic unit 4. sequencing logic unit laadt nieuw adres adhv volgend adres v ctrl-bufreg & ALU-flags: – volgende instr = 1 optellen bij ctrl-adresreg – nr nieuwe routine springen obv jump-µinstr = adresveld v ctrl-bufreg in ctrl-adresreg – nr machine instr-routine springen: = ctrl-adresreg laden adhv opcode in IR → bovenste decoder vertaalt opcode in ctrl-mem-adres 5. onderste decoder: gebr vr verticale µinstr’s: code gebruikt vr elke actie ipv bits (µop) die w vertaald in juiste bits ⇒ ctrl-store (= CM) kleiner MAAR terug decoden nt elke combo v bits toelaten want lezen/schrijven zelfde reg nt mog → optimaliseren • Wilkes control: systeem = matrix gevuld met diodes → tijdens machinecycle 1 lijn v matrix geactiveerd → signn op ptn wr diodes staan (1e deel = ctrl-signn & 2e = adres-signn ) ⇒ elke rij = 1 µinstr met conditie-signaal jumps sturen

2009-2010

p 13


16.2

Micro-instructie sequencing

• microprogrammed CU: 1. µinstr-sequencing: volgende instr uit CM halen 2. µinstr-executie: ctrl-signn genereren om de instr uit te voeren ⇒ tijdens ontwerp samen beschouwen → alle2 invloed op instr-formaat & timing CU • volgorde-technieken: 1. 2-adresvelden: mogelijk adres = volgende (nrml), jump-adres of IR-code 2. 1-adresveld: mogelijk adres = volgende (= vorige +1 dus gn apart veld nodig), adresveld of IR-code → ADD+1 nodig dus trager ↔ ctrl-store<< 3. variabel formaat: 2 versch formaten gebruiken, beslissen welke nodig (ofwel ctrl-bits (adres = in volgorde of IR ofwel jump-logica+adres) → extra cycle om te beslissen • adresgeneratie 1. mapping: opcode vertalen (mbv bovenste decoder) in ctrl-storeadres (1x per cycle) 2. optellen: 2 porties optellen/combineren om adres te vormen 3. residual control: eerder opgeslagen adres (temp-storage) gebrn : subroutines return-adres

16.3

Control Unit Organisatie

• Cycle = basis = Fetch (adhv adres) + Execute (ctrl-signn maken → interne/externe ctrl-bus)

17

PARALLEL P ROCESSING • Single instr, single datastream SISD: 1 CPU die 1 instr uitvoert op data die in single mem zit • Single instr, multiple - SIMD: simultane uitvoering v enkele processing-elemn , elk met hun data-mem • Multiple instr, single - MISD: meerdere CPU’s die meerdere instr’s uitvoeren • Multiple instr, multiple - MIMD: set v CPU’s voeren simultaan versch instr-sequenties uit op versch datasets – tightly coupled: shared mem, communicatie dr dat geh (SMP of NUMA) – loosely coupled: verzameling onafh uni-CPU’s of SMP’s geconnecteerd om cluster te vormen, communicatie via fixed path of netw-connectie

2009-2010

p 14


17.1

Symmetrische Multiprocessors SMP

• EIGENSCHAPPEN : – 2(+) gelijkaardige CPU’s die zelfde geh & I/O delen, geconnecteerd dr e bus → memaccesstijd vr elke CPU ≈ – toegang tt I/O-appn dr zelfde of gescheiden kanalen – iedere CPU k zelfde taken uitvoeren → symmetrisch – dergelijk systeem gecontroleerd dr OS: interactie tss processors (op job, taak, bestand & data-level) • VOORDELEN : – performantie: parallellisme – beschikbaarh: alle CPU’s zelfde fties → 1 CPU die faalt 6= probl – uitbreiding: toevoegen CPU mogelijk – schaalbaarh: producten verkopen met prijs/perform afh v # CPU’s • ORGANISATIE : – time-shared bus (mstal): adressering (versch elemn op bus), arbitrage & time-sharing – voordelen: simpel, flexibel & betrouwbaar (1 apparaat dat uitvalt 6= crash) – nadelen: perf gelimiteerd dr bus cycle-time, elke CPU moet lokale cache h (# bus-toegangen↓) → cache-coherentie? • OS ontwerpkwesties: moet overkomen als systeem met 1 CPU – gelijktijdige parallelle processen: zelfde stukken code tegelijkertijd gebruiken → mgmt fties nodig (deadlock, invalid ops vermijden) – scheduling dr elke processor → conflicten vermijden – synch: gedeelde adresruimte & IO → mutual exclusion – geh-mgmt → multiport-geh, paging coördineren (consistentie bij pag’s delen) – betrouwbaarh & fouttolerantie: als 1 CPU uitvalt ‘vloeiend’ opvangen: herstructureren

17.2

Multithreading & Chip Multiprocessors

• perf meten adhv snelheid wrmee instr’s w uitgevoerd: MIPS = f × IPC (gem # instr’s/cycle) • perf↑ dr f↑ & dr IPC↑ → pipelining, superscalair, gebruik pipeline optimaliseren (out-of-order issuing) ↔ limieten dr complexiteit & stroomverbruik • oplossing: multithreading MT – proces = broneigendom (adresruimte & evt controle over IO/files) & scheduling/executie (interleaved met andere, prio, exec-state) – proces-switch = operatie die CPU v/h ene nr andere proces omschakelt: adresruimte opslaan & vervangen 2009-2010

p 15


– thread = uitvoerbare 1heid v proces: CPU-context (PC, SP) & eigen dataruimte – thread-switch: schakelen v ene thread nr andere binnen proces (minder kostelijk dan proces-switch) – implicit MT: parallel uitvoeren threads van 1 proces – explicit MT: parallel instr’s v versch threads v versch processen uitvoeren, instr’s v versch threads interleaven op 1 pipeline & parallel uitvoeren op versch pipelines 1. interleaved MT = fine-grained MT: CPU switched tss 2(+) threads ∼ clock-cycle 2. blocked MT = course-grained MT: 1 thread uitvoeren tt event die delay veroorzkt (vb cache miss) → andere thread 3. Simultaneous MT = SMT: instr’s gelijktijdig gelanceerd v versch threads nr execunits v superscalaire CPU 4. Chip multiprocessing: CPU gekopieerd op chip, elke CPU handelt aparte threads af → alle logica beschikbaar per CPU ⇒ multicore • scalaire processors: – Single-threaded: simpele pipeline (RISC), gn MT – Interleaved MT: cf supra, pipeline stages ≈ voll vol, HW nodig vr thread-switches – Blocked MT: delay-event zou pipeline stoppen → threadswitch • superscalaire processors: – gwn superscalair: gn MT – interleaved MT: per cycle zovl mog instr’s v 1 thread (# afh v dependencies) – blocked MT: instr’s v 1 thread – Very Long Instr Word VLIW: meerdere parallelle instr’s/woord (dr compiler), evt deel NOOPs – interleaved MT VLIW: zelfde vrdelen als zonder VLIW – blocked MT VLIW: idem

(c) Scalair

(d) Superscalair

• parallelle gelijktijdige uitvoering v versch threads: – SMT: versch instr’s gelijktijdig lanceren, 1 thread mag alle horiz slots vullen, als genoeg threads → max # instr’s/cycle

2009-2010

p 16


– chip multiprocessor: meerdere 2-issue superscalaire CPU’s, elke CPU krijgt thread → tt 2 instr’s/cycle/thread

17.3

Voorbeelden

• Pentium 4: hyperthreading = SMT met support vr 2 threads → 2 CPU’s • IBM Power5: chip multiprocessing + SMT → elke chip 2 versch CPU’s die elk 2 threads parallel k uitvoeren adhv SMT

18

M ULTICORE C OMPUTERS

18.1

Performantiekwesties

1. Hardware: • performantie↑ dr betere organisatie & hogere freq • parallelisme↑ pipelining, superscalair, SMT • resultaten↓ want complexere logica nodig, transistors<< → mr o/e chip ⇒ moeilijker ontwerpen, debuggen, testen + verbruikprobln √ Regel v Pollack: performantie ≈ sti jging complexiteit ⇒ nt lineaire toename ↔ multicore = bijna-lineaire toename (kern k nooit alle cache effectief gebruiken) 2. Software: perf-voordelen afh v effectief gebr v parallellisme → klein deel seriële code = grote terugval in perf! wet v Amdahl: speedup =

executietijd v progr op enkele CPU 1 = executietijd v progr op N parallelle CPU’s (1 − f ) + ( f /N)

- f = fractie die parallelliseerbr is - gn overhead (communicatie, jobs verdelen/scheduling & cache coherentie) in rek gebr8 vb-progr die profiteren v multicore: db’s, java-, multiproces- & multi-instance applicaties

18.2

Multicore organisatie

• variabelen: # kernen per chip, # levels cache per chip, # gedeelde cache • individuele kernen = superscalair of SMT • voordelen gedeelde L2-cache: 2009-2010

p 17


– constructieve interferentie vermindert algemene ‘miss rate’: ene core roept geh-blok met nodige data op in cache, andere heeft andere data in zelfde geh-blok nodig – gedeelde data w nt gedupliceerd – deftige frame-vervangingsalgoritmes → shared cache per kern = dynamisch ⇒ afh v uitvoerende threads – inter-CPU-communicatie gemakkelijk te integreren dr gedeelde geh-locaties – cache-coherentieprobln beperkt tt L1-cache → perf↑ nadelen: dedicated = rapper L2-toegang vr kernen gedeelde L3 k ook perf↑

18.3

Intel x86 multikernorganisatie

1. Intel Core Duo: • 2 x86 superscalaire kernen, dedicated L1, temp-controle per kern • Advanced Programmable Interrupt Control (APIC): inter-process interrupts tss kernen, stuurt interrupts nr juiste kern, incl timer zodat OS kern k onderbreken • Power Mgmt Logic: monitort temp & CPU-activiteit, past spanning/stroom aan & k subsystemen switchen • gedeelde L2 cache (2mb): dynamische toekenning, MESI-support (cache-coh protocol) vr L1, uitgebreide ondersteuning om meerdere Core Duo’s in SMP te ondersteunen (lokaal gedeeld ↔ algemeen gedeeld) • Bus interface → FSB 2. Intel Core i7 • 4 x86 SMT-kernen die elk 4 threads aankunnen, dedicated L2, shared L3 • speculatieve fetch vr caches • DDR3-geh controller op chip → gn FSB • QuickPath interconnectie: cache-coherente punt-tt-punt link = hogesnelh link tss CPUchips

21

T HE IA-64 A RCHITECTURE • motivatie – P4 = laatste x86, overstap op nieuwe architectuur: 64-bit → veel circuits, snelheid, parallellisme, weg v superscalair – instr-lvl parallellisme: impliciet in machine-instr, nt bep dr CPU runtime – LIW of VLIW – branch predication ipv branch prediction – speculative loading

2009-2010

p 18


⇒ Explicit Parallel Instruction Computing EPIC, IA-64 = IS-architectuur vr op EPIC, Itanium = vb v organisatie v deze arch

• wrm nieuwe arch? nt HW compatibel met x86: alle HW-mogelijkhn al ge¨ımpl • expliciet parallellisme: instr-parallellisme gepland @ compile time → CPU gebruikt deze info → minder complexe circuits nodig, compiler mr tijd dan @ runtime & ziet voll progr ipv stukje • std organisatie

– vl registers → hoge graad v parallellisme ondersteunen & expliciet zichtbr (gn reg-renaming dr CPU) – versch exec-units (8+ vs nrml 4 bij superscal), afh v # beschikbre transistors → 8 parallelle instr’s k w gesplitst in 2x4 als mr 4 EU’s 1. I-unit: integer bewerking, shift/add, logisch, compare, ... → adresberekening 2. M-unit: geheugen → load/store tss geh®’s + ALU-ops 3. B-unit: branch-instr’s 4. F-unit: floating-point instr’s 5. X-unit: extended → als nrmle units nt lang genoeg om instr erin te coderen – instr formaat

2009-2010

p 19


∗ meerdere bundels fetchen in 1x, per bundel 3 instr’s ( = syllables) + template ∗ template = type instr, welke k parallel w uitgevoerd (nt enkel diegene in desbetreffende bundel!) ∗ opcode = 4 bits → 16 instr’s mogelijk ↔ opcode + template + other modifying bits (vwn ) vb templ+opcode = jump, OMF = if zero ∗ compiler hft instr’s gebundeld → nt in orig volgorde – mapping v instr’s op exec-units, tem zwarte strepen = parallel uitvoerbr, er8r dependencies ed

– assembly language format: [qp] instr [.comp] dest = srcs // ;; stopt reeks parallelle instr’s = instr-groep

21.1

Predication = ‘toekenning’

compiler verwijdert branches dr conditionele uitvoering: (vb met if-then-else) 1. bij if voegt compiler compare toe die 2 predicates creërt: P1 & P2, als compare = true P1 = 1, anders P2 = 1 2. elke instr in then-pad hft referentie nr P1, elke instr in else-pad nr P2 3. CPU voert beide uit, als uitkomst compare gekend → ene weg, andere comitten

21.2

Control Speculation = speculative loading

• data uit geh laden vr CPU het nodig hft → geh-delays vrkomen • als exception → uitstellen tt juiste tijdstip (wr load nodig) • als load vóo´ r branch verplaatst → probln ⇒ Not-a-Thing bit (v te laden reg) setten, w gecheckt in check → als NaT = 1 branch nr recovery progr w genomen (OS)

21.3

Data Speculation = advanced loading

1. ld8.a doet load & schrijft bronadres (= wat geladen) in Advanced Load Address Table 2009-2010

p 20


2. st8 controleert ALAT vr entries die overlappen met hetgeen hij schrijft, zoja → match uit ALAT verwijderen 3. ld8.c controleert ALAT ook, als gn match → opnieuw loaden, anders gn probl

21.4

Software pipelining

• ≈ loop’n’rolling → loop in stappen v 2 verder zetten en 2 acties per loop doen → overhead↓ • loops uitsplitsen in hun versch instr’s, kijken welke parallel k met andere instr’s • veronderstelt multi-port geheugen (load & store samen)

21.5

Register set

Register stack: procedure krijgt frame (tt 96 reg’s) op stack bij call/return, als stack vol oudste nr geh

A

G EHEUGENCHIPS

A.1

Klein & goedkoop - DRAM

• DRAM = dynamische RAM: op tijd dynamisch verversen anders info weg (condensatoren opnieuw laden) • opbouw & werking: – geh-cellenveld: 2dim-matrix → elke bit opgeslagen in individueel adresseerbare geh-cel (kolom/rijnr) – adresbuffer: ontvangt opslagadres (dr externe geh-sturing bep adhv dr CPU ingevoerde adres) → opsplitsen in regel- & kolomadres die apart w ingelezen (minder pinnen nodig) = multiplexing ∗ Row Adress Strobe-pin → regeladres inlezen & nr regeldecoder ∗ Column Address Strobe-pin → kolomadres inlezen & nr kolomdecoder RAS-CAS-delay = tijd tss rij- & kolomadres inlezing – geadresseerde cel geeft inhoud vrij → leesversterker → I/O-gate → data-uitvoerbuffer → Dout -pin schrijven: Write Enabled → Din -pin → data-invoerbuffer → I/O-gate + leesversterker → geadresseerde cel – geheugencel = condensator die bit opslaat (lading) & keuzetransistor die condensator kiest (schakelaar) – gate v transistor verbonden met woordleiding (1 per regel), bitleidingparen verbonden met sources v transistors (1 paar per kolom), drain verbonden met condensator

2009-2010

p 21


• lezen: – voorlaadschakeling: voorlader laadt alle bitleidingparen op tt Vcc/2 + alle bitleidingparen kortgesloten → zelfde potentiaal ⇒ RAS-voorlaadtijd – hierna voorlader uitschakelen & geh-cellen benaderen via woordleiding ∗ regeladressignaal activeert juiste woordleiding → alle verbonden keuzetransistors doorgeschakeld & ladingen vloeien naar bitleidingen ∗ probleem: opslagcondensator hft capaciteit <<< bitleiding → V op bitleiding verandert hl weinig (100mV, t2 in figuur) ∗ als opslagcondensator leeg was (= 0) → V↓ klein beetje ⇒ leesversterker legt bitleiding die aan opslagcondensator hangt aan massa, andere versterkt nr Vcc (t3) als opslagcondensator vol omgekeerde = differentiaalversterking ∗ op figuur: VRD = afh v opgeslagen waarde, deze wordt versterkt – versterkte opslagsign v elke leesversterker → I/O-gates (= 2 gatetransistors, gestuurd dr kolomdecoder, die 1 I/O-gate activeert) → I/O-leidingpaar → data-uitvoerbuffer → versterkt signaal ng eens → Dout -pin – tegelijkertijd komen V v bitleidingparen over1 met gegevens in over1komstige geh-cellen v/d woordleiding → gegevens ververst! – decoders & leesversterkers uitschakelen, gates in I/O sperren → voorlader terug activeren (t4): V v bitleidingen w trg Vcc/2 (t5) → nieuwe leescyclus

2009-2010

p 22


• schrijven: – geh-sturing geeft RAS-sign + WE-sign – te schrijven gegevens via Din → invoerbuffer (versterkt) → I/O-leidingpaar – regeldecoder ontcijfert regeladres → activeert juiste woordleiding (dus alle keuzetransistors doorgeschakeld → lading aan bitleidingpaar) – CAS-sign + kolomadres via adresbuffer → kolomdecoder, ontcijfert → transfergate doorgeven → nr juiste leesversterker (versterkt) – afh v databit (0 of 1) V v bitleiding versterken/verzwakken – signaal v data-invoerbuffer >> lading in geadresseerde opslagcel → gegevens opslaan – alle leesversterkers versterken lading in opslagcellen → alle gepaarde bitleidingen trug op V ∼ waarden v te schrijven gegevens • ingewikkeldere RAM: – Dual-Port RAM: simultaan lezen/schrijven – VRAM: naast parallelle schrijftoegangspoort zr snelle seriële uitgangspoort → meerdere bits snel nr buiten sturen • DRAM verversen: condensators ontladen → vb alle 128 rijen binnen de 2ms verversen – RAS-only refresh: blinde leescyclus → RAS-sign activeren, regeladres = refreshadres maar geen CAS-sign: nts doorgegeven aan I/O-leidingen & data-uitvoerbuffer externe schakeling (of CPU zelf) nodig om alle adressen te overlopen & door te geven – CAS-before-RAS refresh: DRAM-chip hft eigen refresh-schakeling met adresteller, geactiveerd dr CAS bep tijd laag te houden vr RAS te activeren – Pin 1-refresh: met specifieke refresh-pin – Hidden RAS-only refresh: refresh- verstopt achter leescyclus → CAS-sign laag houden, RAS schakelen tijdens leescyclus gelezen gegs blijven geldig tijdens refreshcyclus – Hidden Pin 1-refresh: refresh- verstopt achter leescyclus, maar nt trg RAS maar refresh-pin activeren tijdens CAS laag blijft 2009-2010

p 23


– Self-refresh: tijdens tre f m alle processen w gestopt ⇒ onmogelijk vr pc’s! (stand-by mode)

(e) RAS-only refresh

(f) CAS-before-RAS refresh

(g) Pin 1-refresh

(h) Hidden RAS-only refresh

(i) Hidden Pin 1-refresh

(j) Self-refresh

• DRAM-indelingen: bit- geörienteerd (cf supra), nibble(4 bits)-, byte- & word(2 bytes)-geörienteerd (wide-RAMS): meer datapinnen = breedte datawoord dat k w verstuurd bij lees/schrijfbenadering • DRAM-werkmodi: 1. traditionele modus: iedere keer regel & kolomadres ingeven → data lezen/schrijven 2. paginamodus: 1x regeladres, kolomadres aanpassen → RAS-sign 1x, iedere keer verversen mbv CAS-sign ⇒ pagina = regel i/h geh-cellenveld RAS-vrladen & regeladres decoderen overbodig → 50% winst in toegangstijd, cyclustijd 70% korter (als data v 1 pag nodig!) 200-tal bewerkingen met 1 actief RAS-sign (schrijf & lees!) 3. hyperpaginamodus = EDO-modus: tijd tss 2 op1volgende CAS-activeringen korter 4. static column modus: cf hyperpaginamodus maar CAS-sign blijft gelijk → interne DRAMsturing herkent wijziging automatisch 5. nibble modus: eenvoudige seriële modus: CAS 4x 8reenvolgens omschakelen → 4 bits uit geadresseerde rij ophalen & in intern 4bits-tss-geh → per CAS-sign bit uitvoeren 6. serial modus: uitgebreide nibble modus → nt tt 4 beperkt, afh v interne indeling v/d chip (handig vr beeldschermgegevens, vullen cachelijn) 7. interleaving = geh in meerdere banken opdelen vb 2-wegsinterleaving: even en oneven dubbelwoordadressen splitsen → bij seriële benadering: beide banken afwisselend aanspreken, ene bank voorladen terwijl andere w benaderd interleaving + paginamodus combineren: op1volgende pages in versch banken zetten

2009-2010

p 24


A.2

Geheugenmodulen

• ipv losse geh-cellen modulen gebruiken: SIMM & SIP (breedte v 9bits, verouderd), PS/2 (breedte 36, 32 of 40bits) of DIMM • SIMM & SIP’s: vb max in 4 banken verdeeld → 4-wegsinterleaving mogelijk • Double Inline Memory-Modules DIMM’s: 64bits breed, meestal met SDRAM-chips op • Synchronous DRAM SDRAM (6= SRAM = static RAM): werken in burstmodus (figuur = leesburstmodus) & met synchroon kloksignaal ipv met CAS- & RAS-timing (wel ng aanwezig mr vr read/write/burststop) met of zonder EEPROM: bevat gegs ivm soort module, org v gebruikte DRAMS & timingparams → vr automatische optimale instelling (zonder EEPROM instellen via BIOS)

• Double Data Rate RAM = SDRAM met datatranspn op opgaande & neergaande klokflank • Synchronous Graphic RAM SGRAM: geh op graka’s = SDRAM geoptimaliseerd vr hoogst mogelijke overdr8snelh (ipv SDRAM = vr hoogst mog geh-hoeveelh) • RAMBus = Rambus Inline Memory Modules RIMM’s: op beide flanken v klok gewerkt, controller + RDRAM’s + afsluiting → bussysteem met DRAM

A.3

SRAM - snel & duur

• opslagcel bestaat (mstal) uit flip-flop, wrv toestand = waarde ⇒ refresh nt nodig! (↔ DRAM) • flip-flop omschakelen: hoge spanning op Q → spanning over Tr2 = doorschakelen → minder spanning op Q = lichtjes sperren v Tr1 → terugkoppeling ⇒ enz tt omschakeling • stabiliteit bep dr verhouding belanstingsweerstn tov doorlaatweerst v transistors: hoe groter hoe stabieler • duur, minder opslagcapaciteit → cache • ook 2dim-matrix: regel- & kolomdecoder, gates v keuzetransistor verbonden met woordleiding, Q/Q met bitleidingpaar • kolom en regeladres nt multiplexen, opdeling w intern gedaan ↔ meer pinnen nodig • bij schrijven geeft leesversterker veel sterker signaal dan flip-flip (die ook al sterk is) → overschreven 2009-2010

p 25


• 1 modus: std ↔ andere (cf DRAM) gn effect ⇒ eenvoudige sturing (wel complexere interne struct) • vluchtigheid v SRAM: stroomuitval detectie = watchdog

bovenste deel figuur = spanningstabilisatie (mbv gelijkrichter + condens + spanningstabil) onderste deel = powerfaildetectie: 2 diodes vormen wisselspanning om tt enkel positieve loben → als stroomuitval wordt transistor gesperd ⇒ V = 0 → invertor → hoge spanning die hertriggerbare multivibrator activeert → nog korte tijd stroomvoorziening • vb - Non Volatile RAM NOVRAM (nt vluchtig): SRAM uitgebreid met EEPROM wrin alles bij stroomuitval w gebackupped • vb - Phase-change RAM PRAM: CMOSRAM + lithiumknopcel + VLSI-controllerchip – schakelt batterij of voedingsspanning aan, afh v welke grootst – Power Fail detectie: als V<4.25V → Chip Enabled blokkeren – als CE al actief bij powerfailure, Write Protect ftie vertraagd tt geh-cyclus compleet (duur typisch 10ns)

A.4

Permanent Geheugen

1. ROM: gn lading/schakeltoestanden → vaste verbingen tss componenten ⇒ compact/inflexibel 2. PROM = Programmable ROM: flexibeler → info inbranden dr gebruiker = Mask-ROM 3. EPROM = Erasable Programmable ROM: mbv sterke elektrische puls bep verbindingen doorbranden ipv masker: (a) testen of EPROM leeg (inhoud = 0ffH) (b) programmeren VPP = 26V, adres & data aanbrengen, progr-puls v 50ms (c) verifiëren als inhoud klopt fast = interactieve mode → progr-puls v 10-20ms wissen mbv UV-licht (TL-lamp of zon ook na lange tijd) 2009-2010

p 26


4. OTPROM = One Time PROM: EPROM zonder lichtvenster 5. Flash memory = EEPROM’s die even flexibel w geprogr dan DRAM/SRAM (zelfde opbouw: geh-matrix), permanente data zonder batterij 6. EAROM = Electrically Alterable ROM 7. EEPROM = Electrically EPROM: UV = duur PIA = Peripheral Interface Adapter: 2x8 bidir poorten + 4 ctrl-lijnen → verbind ⇒ juiste signalen genereren → decoderen → actie op EEPROM 8. SEEPROM = Serial EEPROM: EEPROM met seriële connectie nr circuitbord (minder pins → minder plaats nodig & stroomverbruik↓

A.5

Koppeling v geh-schakelingen aan CPU

• adres- & selectie-info: geh-schakeling selecteren tss alle andere & juiste cel kiezen – directe adressering: n adrespennen (afh v # cellen) & chipselectieklem die w actief gemaakt als juiste adres op adresklemmen – multiplex adressering: adres/data-mux = op ene tijdstip adres op pinnen, latere tijdstip data OF adres-mux (regel & kolom cf supra) • gegevensinfo (databus): nuttige info die in/uitgevoerd w • controlinfo Adresdecoders: • vast: adrespinnen mbv logica-elementen verbinden → juiste cel selecteren • instelbaar: – adrespinnen met IC verbinden → mapping – adresbereik met schakelaars instellen (comparator-IC of EXNOR-poorten) • vast-programmeerbaar: vb mbv PROM

2009-2010

p 27

Samenvatting Geavanceerde Computerarchitectuur

Recommend Documents