Lecture notes, lecture 1 - Niels olof bouvin PDF

Preview

Summary

Niels Olof Bouvin...

Description

Institut for Datalogi Aarhus Universitet

1

Formål med dagens forelæsning

Kurset læringsmål og emner folk og form eksamen

Området maskinarkitektur

2

Computerarkitektur Beskrivelse At give den studerende kendskab til computeres opbygning og virkemåde. Herunder hvorledes en computer kan opfattes som niveauer af abstrakte maskiner realiseret i hardware og software [...]

Læringsmål Deltagerne skal ved afslutningen af kurset kunne: • forklare opbygningen af computere som niveauer af virtuelle maskiner, • beskrive formål, opbygning og begreber på de enkelte niveauer, • anvende begreber og programmere på de enkelte niveauer.

Praktiske færdigheder I kommer til at programmere i (symbolsk) maskinkode på forskellige maskinarkitekturer I kommer til at udvide mikroprogrammer, så en CPU får nye instruktioner

3

Undervisningsmateriale Andrew S. Tanenbaum & Todd Austin Structured Computer Organisation (SCO) 6. udgave, Pearson-Prentice-Hall, 2012 Må, i modsætning til computere, medtages til eksamen

Derudover diverse noter Vejledninger og ugesedler hentes via Blackboard-siderne.

Forelæsninger livecastes og videopodcastes hvis alt går vel (best effort! Ingen garanti) så hurtigt som muligt og senest inden næste forelæsning—typisk samme dag

http://130.226.243.18/videos/livestreams/page1/

4

Øvelseshold og bemanding Fremgår af kursushjemmesiden Instruktorer Mads Buch, Asger Hautop Drewsen, Kasper Sacharias Roos Eenberg, Mikkel Lykke Jørgensen, Kenneth Kaiser Kudsk, Christoffer Øland Skovgaard, Philip Tchernavskij & Jeppe Vinberg

Holdbytte forudsætter, at man finder nogen at bytte med Såfremt I ikke er blevet sat på et hold, så mød op på det, der passer jer bedst I skal selv tilmelde jer til hold og gruppe på Blackboard — vær sikker på at vælge rigtigt! vent til første TØ med at tilmelde jer en gruppe — BB smerten er langt mindre, hvis tilmeldningen foregår koordineret!

5

Ugesedler og opgaver Ugeseddel offentliggøres løbende på hjemmesiden: Læsestof for fredagens forelæsning Opgaver til øvelser i den efterfølgende uge Tavle- og diskussionsopgaver Ugeopgaver

Ugeopgaver bidrager til eksamenskarakteren og skal laves i grupper. Dan grupper af 2-3 personer ved første øvelsesgang. Grupper er faste og kan ikke gå på tværs af øvelseshold.

6

Eksamen

Forudsætning kræver at man har fået mindst 25 point for sine ugeopgaver

Eksamensformen er multiple choice (dvs. skriftlig). eksamen varer 60 minutter

Karakteren beregnes som en vægtet sum af ugeopgaver og eksamen Selvom det er multiple choice er det ikke en test af simpel paratviden

7

Eksempel på eksamensspørgsmål

8

Ugeopgaver: En del af eksamen

Fordi ugeopgaverne indgår i den endelige karakter, tæller afskrivning mv. som eksamenssnyd Hvis vi opdager svindel, er vi forpligtiget til at anmelde det til rektor Da det er gruppeopgaver, er alle medlemmer ansvarlige, og bliver derfor straffet ens

9

Oversigt

Kurset Introduktion til maskinarkitektur og -niveauer Computeren opbygning

10

Hvad er en computer?

En maskine, der udfører beregninger angivet som instruktioner i et program 11

Hvad er en computer?

Maskine opbygget af alt fra mekanik, relæer, radiorør, og (i nutiden) transistorer. Fremtidens maskiner kan være optiske, carbonnanofibre, DNA eller superpositioner af afkølede atomer i kvantecomputere

Instruktioner simple operationer: Læg to tal sammen, sammenlign to værdier, flyt en værdi fra ét sted til et andet, …

Program en sekvens af instruktioner. Skabt direkte af et menneske, eller (typisk) indirekte v.hj.a. en oversætter eller fortolker

12

Computergenerationer 0. generation: Mekaniske computere (1642-1945) 1. generation: Radiorør (1945-55) 2. generation: Transistorer (1955-65) 3. generation: Integrerede kredsløb (IC) (1965-80) 4. generation: Højt integrerede kredsløb (VLSI) (1980-…) 5. generation: Lav energi, pervasive computing, IT i alting (nu og altid)

13

Moore’s lov

CPUer og hukommelse opbygges af transistorer Grundet bedre produktionsformer fordob transistortætheden ca. hver 18. måned

Det giver dobbel kapacite og ca. 40% højere hastigh da transistorerne kommer tættere på hina

14

Computere! 2007: Apple iPhone. Touch GUI success ARM v7: 1994 Intel Pentium: 1993 1997: PalmPilot. Personal Digital Assistant Intel 80386: 1986 1984: Apple Macintosh. Første udbredte GUI. MIPS R2000: 1985 VLSI: 1980 1981: IBM PC. Den mest successrige platform til dato. Intel 8086: 1978 1977: Apple ][: En af de første udbredte personlige computere 1965: IBM S/360: Første, indbyrdes kompatible, familie af computere 1964: CDC 6600: Første supercomputer. 1 MFLOPS Integreret kredsløb: 1958 1960: DEC PDP-1: Første successrige interaktive computer. 4096 words, 200 khz Transistor: 1948 1949: EDSAC. Første “von Neumann” computer. Program gemt i lager. 1946: ENIAC: Første “rigtige” computer. Radiorør. Programmeres med ledninger og kontakter. 5 khz 1941: Konrad Zuse Z3: Første fungerende, programmérbare relæbaseret computer (64 words, 5,3 hz) 1834: Babbage Analytical Engine - mekanisk computer, forventes færdigbygget i 2021. (~675 bytes, 7 hz)

15

Multilevel maskiner Vi ønsker at programmere computere, men ikke på computerens præmisser dvs. den rå hardware bestående af gates og transistorer adresseret v.hj.a. nuller og ettaller (eller kabler og kontakter) det gjorde man i begyndelsen og det er et helvede

Løsning: Skab en virtuel maskine, der er mere letprogrammerbar, og som kan køre på maskinen den skal skrives én gang per maskine

En virtuel maskine definerer instruktioner og datatyper, og er, rent beset, blot endnu en computer, som vi kan skrive virtuelle maskiner til, som var dén en fysisk computer som bliver mere og mere lettilgængelig og, indrømmet, langsommere og langsommere, som vi putter lag på lag på lag på lag af abstraktioner…

16

Virtuelle/Abstrakte maskiner Level n

Virtual machine Mn, with machine language Ln

Level 3

Virtual machine M3, with machine language L3

Level 2

Virtual machine M2, with machine language L2

Level 1

Virtual machine M1, with machine language L1

Level 0

Actual machine M0, with machine language L0

Programs in Ln are either interpreted by an interpreter running on a lower machine, or are translated to the machine language of a lower machine

Programs in L2 are either interpreted by interpreters running on M1 or M0, or are translated to L0. Programs in L1 are either interpreted by interpreters running on M0, or are translated to L0.

Programs in L0 can be executed directly by the electronic circuits

17

Multilevel maskiner

Hardware og software er logisk ækvivalente 18

Moore’s lov og multilevel maskiner Med den øgede hastighed og kapacitet har man igennem computerens historie gradvist kunnet skabe højere og højere lag af abstraktioner I udvikling brug af højniveau programmeringssprog

I anvendelse rige grafiske grænseflade med mange forskellige modaliteter og interaktionsformer

Man har også flyttet funktionalitet fra ét niveau til et andet ofte fra hardware til software og tilbage igen

19

Det digitale niveau Level 5

Problem-oriented language level

Translation (compiler) Level 4

Assembly language level

Translation (assembler) Level 3

Begreber

Operating system machine level

Partial interpretation (operating system)

transistorer, porte (gates), kombinatoriske kredsløb, lagerkredse, høj og lav strøm, bit, digitale værdier, …

Level 2

Instruction set architecture level Interpretation (microprogram) or direct execution

Fordele

Level 1

Micro-architecture level

hurtigt Hardware

Ulemper

Level 0

meget tidskrævende at udvikle

20

Digital logic level

Typisk opbygning af en computer ”von Neumann” maskinarkitektur: First Draft of a Report on the EDVAC, John von Neumann, 1946

Memory

Afvikler programmer gemt i lageret Central Processing Unit (CPU)

Control Unit

Arithmetic Logic Unit (ALU)

Control Unit

Registers

Input/Output devices

Main Memory

Disk

Printer

Bus

21

Arithmetic Logic Unit Accumulator

Input Output

von Neumann maskinen A+B

Begreber

Registers

A

ALU, registre, Program Counter, instruktion sæt, program (i form af maskinkode) og data gemt i hukommelse, ydre enheder tilgået over bus…

Programmer er blot data, der hentes fra lageret og fortolkes af CPUen Der er, basalt set, ikke sket noget med computeres arkitektur siden da

B

A

B

ALU Input registers ALU input bus

ALU

udover at de er blevet lidt hurtigere, en anelse billigere og har opnået en vis udbredelse A+B

22

ALU output register

von Neumann maskinen fortolker maskinkode 1. Fetch the next instruction from memory into the instruction register. 2. Change the program counter to point to the following instruction 3. Determine the type of instruction just fetched. 4. If the instruction uses a word in memory, determine where it is. 5. Fetch the word, if needed, into a CPU register. 6. Execute the instruction. 7. Go to step 1 to begin executing the following instruction. Hver iteration af løkken udfører en maskininstruktion

23

Mikroprogrammering Level 5

Problem-oriented language level

Translation (compiler) Level 4

Assembly language level

Translation (assembler) Level 3

Begreber

Operating system machine level

Partial interpretation (operating system)

busser, registre, dataoverførsel, kontrollager, mikroordrer, clock cykler, fetch-decode-execute,…

Level 2

Instruction set architecture level Interpretation (microprogram) or direct execution

Fordele

Level 1

Micro-architecture level

(meget) nemmere end det digitale niveau Hardware

Ulemper

Level 0

stadig besværligt

24

Digital logic level

Mikroprogrammer 0x64 isub pop two words from stack; push their difference: bipush 20 bipush 12 isub

// 20, ... // 12,20, ... // 8, …

Main1 .... isub1 isub2 isub3

PC=PC+1; fetch; goto (MBR)

(Symbolsk) maskinkode

MAR=SP=SP-1; rd H=TOS MDR=TOS=MDR-H; wr; goto Main1

25

(Symbolsk) mikrokode

Mikroprogrammeringens betydning Mikroprogrammet fortolker et instruktionssæt (ISA) Maskinkodeprogram

Introduktionen af et standardiseret instruktionssæt var en revolution i sin tid udvikl til dette ISA, og så kan dine programmer køre på alle matchende maskiner, uanset hvordan de realiserer udførslen af koden IBM System/360 (1965-1978 i hardware, virtuel lige siden) koden blev portabel, udviklingsinvesteringen beskyttet → IBM solgte masser af mainframes (og har gjort det lige siden)

ISA implementation

En slags hardware

26

ISA implementation

En anden slags hardware

Mikroprogrammeringens udvikling Introduktionen af mikroprogrammer gjorde udviklere langt mere produktive med tiden skabte man flere og flere instruktioner for at lette udviklernes arbejde yderligere dette medførte øget kompleksitet og begrænset ydelse

Alternativet blev Reduced Instruction Set Computer (RISC) CPUer, som eliminerede mikroprogrammering til fordel for simple instruktioner, der udførtes direkte af hardwaren dette øgede hastigheden betragteligt, men med tabet af ISA kompabilitet dvs. maskinkoden skulle skrives om

I dag: Hovedparten af instruktioner udføres direkte i hardware Intels gamle instruktionssæt, der går tilbage til de tidlige 70ere har overlevet men oversættes i realiteten til RISC-agtige instruktion på CPUen (siden Pentium Pro)

27

Typer af CPUer Mikrokontrollere billige, kontrol af ydre enheder

Mobile CPUer lavt strømforbrug

Desktop CPUer høj performance

Med forskellige brugsmønstre og markedsforhold kommer forskellige krav til CPUernes arkitekturer

28

Principper for udvikling af moderne CPUer

Alle instruktioner udføres direkte af hardwaren Maksimér raten hvormed instruktioner påbegyndes Instruktioner skal være lette at afkode Begræns lageradgang til specialiserede load og store instruktioner Masser af registre

29

Pipelining: Påbegynd så mange instruktioner som mulig En instruktion indlæses, fortolkes og udføres i bestemte, diskrete trin (stages) Pipelining: Gå i gang med den næste instruktion, så snart et trin er færdigt samlebåndsarbejde for CPUer kan øge hastigheden dramatisk den enkelte instruktion tager samme tid, men en ny instruktion per clock cycle

Udfordring: forudsætter, at vi løbende kan fodre CPUen med instruktioner hvis vi skal vente på noget, falder farten dramatisk

Pentium 4 31 trin

Core: 16 trin

30

Superscalar: Lav flere ting samtidigt—flere pipelines

Udnyt, at vi har masser af transistorer til at dublere funktionalitet på CPUen kan i princippet være n gange så hurtig

Udfordringer instruktionerne skal være indbyrdes uafhængige sætter nye krav til oversættere og fortolkere for maksimal ydelse

31

Superscalar: Flere funktionelle enheder En del trin er relativt simple, mens andre kan tage længere tid hvis vi skal have en effektiv pipeline, får vi derfor behov for flere af de “dyre” trin

Den typiske model i dag

32

Data-parallelle CPUer: MANGE funktionelle enheder Hvis man har behov for at udføre den samme operation på megen data, kan det betale sig at have massive mængder af funktionelle enheder (cores) Typisk er GPUer bygget på denne måde Voldsom hurtig til specialiserede opgaver, specielt grafik og multimedie I dag ofte sammenbygget med konventionelle CPUer

33

Instruktionssætniveauet Level 5

Problem-oriented language level

Translation (compiler)

Begreber

Level 4

lager, lagerceller, registre, ordrer, ordreformat, …

Assembly language level

Translation (assembler)

Programmer i symbolsk maskinsprog oversættes til absolut maskinkode

Level 3

Operating system machine level

Partial interpretation (operating system) Level 2

Program lagres som en sekvens af bitmønstre (absolut maskinkode)

Instruction set architecture level Interpretation (microprogram) or direct execution

Level 1

Den absolutte maskinkode fortolkes enten af et mikroprogram eller udføres direkte på processorens hardware

34

Micro-architecture level Hardware

Level 0

Digital logic level

Pentium ordreformat Pentium ordreformatet er historisk betinget, kompliceret og variabel i længden (1-17 bytes). Vanskeligt at afkode for processoren.

35

JVM/IJVM ordreformat Den virtuelle maskine, der udfører Javaprogrammer og i reduceret udgave vores fokus i dette kursus

Langt mere regelmæssigt kunne skabes uden at skulle tage hensyn til historien bipush 6 svarer til 00010000 00000110 = 0x10 0x06 … i absolut maskinkode

36

Symbolsk maskinsprog Level 5

Problem-oriented language level

Translation (compiler) Level 4

Begreber

Assembly language level

Translation (assembler) Level 3

lager, lagerceller, registre, ordrer, systemkald, …

Operating system machine level

Partial interpretation (operating system)

Fordele

Level 2

langt lettere at forstå end absolut maskinkode tilbyder (i princippet) den højeste ydelse for udvikleren

Instruction set architecture level Interpretation (microprogram) or direct execution

Level 1

Ulemper

Micro-architecture level Hardware

meget lavt niveau i forhold til almindelige programmeringssprog bundet til den enkelte CPU familie

37

Level 0

Digital logic level

Level 4: Symbolsk maskinsprog Højniveausprog oversættes til assembler—symbolsk maskinsprog gcc -S -m32 -march=pentium towers.c javac towers.java; javap -c towers > towers.code

Begreber Ordrenavne movl $6,%edx Registernavne %edx, %eax, %ebp, %esp Etiketter (labels) .towers, .L3: Operander $-4, 16(%ebp) Direktiver .string “Move ...”

38

towers.c #include

 ./towers Move a disk Move a disk Move a disk Move a disk Move a disk Move a disk Move a disk

void towers(int n, int i, int j) { int k; if (n == 1) printf("Move a disk from %d to %d\n", i, j); else { k = 6 - i - j; towers(n-1, i, k); towers(1, i, j); towers(n-1, k, j); } } int main(int argc, char *argv[]) { towers(3, 1, 3); return 0; }!

39

from from from from from from from

1 1 3 1 2 2 1

to to to to to to to

3 2 2 3 1 3 3

towers.s (Pentium) .file "towers.c" .section .rodata .LC0: .string "Move a disk from %d to %d\n" .text .globl towers .type towers, @function towers: pushl %ebp movl %esp, %ebp subl $24, %esp cmpl $1, 8(%ebp) jne .L2 movl $.LC0, %eax subl $4, %esp pushl 16(%ebp) pushl 12(%ebp) pushl %eax call printf addl $16, %esp jmp .L4 .L2: movl $6, %eax ; start k = 6 - i - j subl 12(%ebp), %eax ; eax = 6 - i subl 16(%ebp), %eax ; eax = 6 - i - j movl %eax, -12(%ebp) ; k = eax movl 8(%ebp), %eax ; start towers(n-1, i, k)

decl %eax subl $4, %esp pushl -12(%ebp) pushl 12(%ebp) pushl %eax call towers addl $16, %esp subl $4, %esp pushl 16(%ebp) pushl 12(%ebp) pushl $1 call towers addl $16, %esp movl 8(%ebp), %eax decl %eax subl $4, %esp pushl 16(%ebp) pushl -12(%ebp) pushl %eax call towers addl $16, %esp

40

; eax = n-1 ; k ; i ; n-1

Pentium registre Værdier kan gemmes i registre (x86 er en register maskine) movl subl subl movl

$6, %eax 12(%ebp), %eax 16(%ebp), %eax %eax, -12(%ebp)

; ; ; ;

start k = 6 - i - j eax = 6 - i eax = 6 - i - j k = eax

Grundet bagudkompabilitet er der ret få synlige registre, og nogle af dem kan anvendes både som 8-, 16- og 32-bit registre samt 64-bit nu om stunder

41

Pentium stakken

Værdier kan også gemmes på stakken movl subl subl movl

$6, %eax 12(%ebp), %eax 16(%ebp), %eax %eax, -12(%ebp)

; ; ; ;

start k = 6 - i - j eax = 6 - i eax = 6 - i - j k = eax

Hvert kald af towers har sit eget stakafsnit (stack frame), der udpeges af ebp registret

42

| k | | | i j |

← ebp-12 ← ebp ← ebp+12 ← ebp+16

Java Virtual Machine

Processoren, som Java bytecode kører på Blev ...