Lagret-program datamaskiner (stored-program computers)

Data og program er begge lagret i elektronisk minne. Datamaskinen holder styr på hva som er data og hva som er instruksjoner. Maskinen henter instruksjoner og data blir overført mellom minne og ALU.

Von Neumann- og Harvard-arkitektur

En datamaskin med en von Neumann-arkitektur, lagrer data og instruksjoner i det samme minnet, mens en datamaskin med en Harvard-arkitektur lagrer data og instruksjoner i separate minner. Begge har lagret-program design.

Moores lov

Moores lov er observasjonen at antall transistorer i en tett integrert krets dobles omtrent hvert annet år. Observasjonen er oppkalt etter Gordon Moore, medgründeren av Fairchild Semiconductor og Intel. Hans artikkel fra 1965 beskrev en dobling hvert år i antall komponenter per integrert krets, og anslo at denne veksten ville fortsette i minst et tiår til. I 1975, ved en vurdering av det neste tiåret, reviderte han prognosen til en dobling hvert annet år. Perioden er ofte sitert som 18 måneder på grunn av en spådom fra Intel-leder David House (som er en kombinasjon av effekten av flere transistorer og at transistorene er raskere)

Prosessorer

Oppgaven til en prosessor er å hente instruksjoner enkeltvis fra et minne, dekode dem og utføre dem. Hent-dekod-utfør-syklusen kan alltid beskrives som en algoritme og utføres faktisk noen ganger av et programvaretolkeprogram (interpreter) som kjører på et lavere nivå. For å øke hastigheten har mange datamaskiner nå en eller flere pipeliner eller har et superskalært design med flere funksjonelle enheter som opererer parallelt. En pipeline gjør at en instruksjon kan deles inn i trinn og trinnene for forskjellige instruksjoner utføres samtidig. Flere funksjonelle enheter er en annen måte å oppnå parallellitet uten å påvirke instruksjonssettet eller arkitekturen som er synlig for programmereren eller kompilatoren.

CPU (Central Processing Unit) er "hjernen til datamaskinen". Dens funksjon er å kjøre programmer lagret i hovedminnet ved å hente instruksjonene deres, undersøke dem og deretter utføre dem etter hverandre. Komponentene er koblet sammen med en buss, som er en samling av parallelle ledninger for overføring av adresse, data og kontrollsignaler. Busser kan være eksterne til CPU, koble den til minne og I/O-enheter, men også interne til CPU.

CPU-en er sammensatt av flere forskjellige deler.

Kontrollenheten

Komponent som er ansvarlig for å hente instruksjoner fra hovedminnet og bestemme typen deres.

Den aritmetiske logiske enheten

Komponent som utfører operasjoner som addisjon og boolsk AND. Nødvendig for å utføre instruksjonene.

CPU-en inneholder også et lite høyhastighetsminne som brukes til å lagre midlertidige resultater og kontrollinformasjon. Dette minnet består av et antall registre som hver har en gitt størrelse og funksjon.

Programteller (PC)

Peker på neste instruksjon som skal hentes for utførelse.

Instruksjonsregister (IR)

Holder instruksjonen som utføres for øyeblikket.

Minneadresseregister (MAR)

Inneholder adressen til minneplasseringen som prosessoren for øyeblikket har tilgang til.

Minnebuffer/dataregister (MDR)

Inneholder dataene som overføres til eller fra minneplasseringen som for øyeblikket er gitt tilgang til.

De fleste datamaskiner har også en rekke andre registre, noen av dem for generelle formål så vel som noen for spesifikke formål.

Minne

Minnet er den delen av datamaskinen der programmer og data lagres. Minner kan kategoriseres som primære eller sekundære.

I/O-enheter

I/O-enheter brukes til å overføre informasjon inn og ut av datamaskinen. De er koblet til prosessoren og minnet med en eller flere busser. Eksempler er terminaler, mus, spillkontrollere, skrivere og modemer. De fleste I/O-enheter bruker ASCII-tegnkoden, selv om Unicode også brukes og UTF-8, en av Unicode-standardene, får aksept etter hvert som dataindustrien blir mer nettsentrisk og globalisert.

Gates

Computers are constructed from integrated circuit chips containing tiny switching elements called gates. The most common gates are AND, OR, NAND, NOR, and NOT. Simple circuits can be built up by directly combining individual gates, although everything can be built using NOR or NAND gates.

Adders

Computer arithmetic is done by adders. A single-bit full adder can be constructed from two half adders. An adder for a multibit word can be built by connecting multiple full adders in such a way as to allow the carry out of each one feed into its left-hand neighbour.

A logical schematic for a full adder.

Memory

The components of (static) memories are latches and flip-flops, each of which can store on bit of information. These can be combined linearly into latches and flip-flops for memories with any word size desired. Memories are available as RAM, ROM, PROM, EPROM, EEPROM, and flash. Static RAMs need not be refreshed; they keep their stored values as long as the power remains on. Dynamic RAMs, on the other hand , must be refreshed periodically to compensate for leakage from the capacitors on the chip.

Bus

The components of a computer system are connected by buses. Many, but not all, of the pins on a typical CPU chip directly drive on bus line. The bus lines can be divided into address, data, and control lines. Synchronous buses are driven by a master clock. Asynchronous buses use full handshaking to synchronize the slave to the master.

Buses enables data and control signals to move around the CPU and memory. There are a number of different buses.

A bus is a communication channel through which data can be moved.

There are many buses in a computer; one example is the universal serial bus (USB), which can transfer data between the computer and external devices.

Control bus: Carries control signals around the CPU and memory indicating whether the operation is a read or a write and ensuring that the operation happens at the right time.

Address bus: Carries memory addresses for memory locations to be read from or written to.

Data bus: Carries data between the CPU and memory. For a write operation the CPU will put the data on the data bus to be sent to memory. For a read operation, the data will be taken from a memory block and sent to the CPU.

Example CPU Chips

The core i7 is an example of a modern CPU. Modern systems using it have a memory bus, a PCIe bus, and a USB bus. The PCIe interconnect is the dominant way to connect the internal parts of a computer at high speeds. The ARM is also a modern high end CPU but is intended for embedded systems and mobile devices where low power consumption is important. The Atmel ATmega168 is an example of a low-priced chip good for small, inexpensive appliances and many other price-sensitive applications.

Interfacing

Switches, lights, printers, and many other I/O devices can be interfaced to computers using parallel I/O interfaces. These chips can be configured to be part of the I/O space or the memory space, as needed. They can be fully decoded or partially decoded depending on the application.

Synchronized bus-transfer:

The signal is syncronized with a clock

Asynchronized bus-transfer:

The signal is syncronized with a handshake

Components in CPU

The Data Path

The heart of every computer is the data path. It contains some registers, one, two or three buses, and one or more functional units such as ALUs and shifters. The main execution loop consists of fetching some operands from the registers and sending them over the buses to the ALU and other functional unit for execution. The results are then stored back in the registers.

The data path can be controlled by a sequencer that fetches microinstructions form a control store. Each microinstruction contains bits that control the data path for one cycle. The bits specify which operands to select, which operation to perform, and what to do with the results. In addition, eahc microinstruction specifies its successor, typically explicitly by containing its address. Some microinstructions modify this base address by ORing bits into the address before it is used.

The IJVM Machine

The IJVM machine is a stack machine with 1-byte opcodes that push words onto the stack, pop words from the stack, and combine (e.g., add) words on the stack. A microprogrammed implementation was given for the Mic-1 microarchitecture. By adding an instruction fetch unit to preload the bytes in the instruction stream, many references to the program counter could be eliminated and the machine greatly sped up.

Microarchitecture Level Designs.

There are many ways to design the microarchitecture level. Many trade-offs exist, including two-bus versus three-bus designs, encoded versus decodeed microinstruction fields, presence or absence of prefetching, shallow or deep pipelines and much more. The Mic-1 is a simple, software-controlled machine with sequential execution and no parallelism. In contrast, the Mic-4 is a highly parallel microarchitecture with a seven-stage pipeline.

Improving performance

Performance can be improved in a variety of ways. Cache memory is a major one. Direct-mapped cashes and set-associative caches are commonly used to speed up memory refreshes. Branch prediction, both static and dynamic, is important, as are out-of-order execution, and speculative execution.

Examples of the microarchitecture level

Our three example machines, the Core i7, OMAP4430, and ATmega168, all have microarchitectures not visible to the ISA assemble-language programmers. The Core i7 has a complex scheme for converting the ISA instructions into micro-operations, caching them, and feeding them into a superscalar RISC core for out-of-order execution, register renaming, and ever other trick in the book to get the last possible drop of speed out of the hardware. The OMAP4430 has a deep pipeline, but is further relatively simple, with in-order issure, in-order execution, and in-order retirement. The ATmega168 is very simple, with a straightforward single main bus to which a handful of registers and one ALU are attached.

The purpose of instructions sets

When writing a computer program, you don't want to write it using logic (boolean algebra) because it would be very inconvenient.

How a program executes

Programs are written by people (programmers) usually in a high level language such as java, c, python and so on. The code written in high level language needs to be compiled into assemble code which is language at a lower level. The assembly code will be put into an OS loader which loads the program into memory.

The instruction set architecture level is what most people think of as "machine language" although on CISC machines it is generally built on a lower layer of microcode. At this level the machine has a byte- or word-oriented memory consisting of some number of megabytes or gigabyes, and instructions such as MOVE, ADD, and BEQ.

Most modern computers have memory that is organized as a sequence of bytes, with 4 or 8 bytes grouped together into words. There are normally also between 8 and 32 registers present, each one containing one word. On some machines (e.g., Core i7), refrences to words in memory do not have to be aligned on natural boundaries in memory, while on others (e.g. OMAP4430, ARM), they must be. But even if words do not have to be aligned, performance is better if they are.

Instructions generally have one, two, or three operands, which are addressed using immediate, direct, register, indexed, or other addressing modes. Some machines have a large number of complex addressing modes. In many cases, compilers are unable to use them in an effective way, so they are unused. Instructions are generally available for moving data, dyadic and monadic operations, including arithmetic and Boolean operations, branches, procedure calls, and loops, and sometimes for I/O. Typical instructions move a word form memory to a register (or vice versa), add, subtract, multiply, or divide two registers or a register and a memory words, or compare two items in registers or memory. It is not unusual for a computer to have well over 200 instructions in its repertoire. CISC machines often have many more.

Control flow at level 2 is achieved using a variety of primitives, including branching, procedure calls, coroutine calls, traps, and interrupts. Branches are used to terminate one instruction sequence and begin a new one at a (possibly distant) location in memory. Procedures are used as an abstration mechanism, to allow a part of the program to be isolated as a unit and called from multiple places. Abstraction using procedures or the equivalent, it would be impossible to write any modern software. Coroutines allow two threads of control to work simultaneously. Traps are used to signal exceptional situations, such as arithmetic overflow. Interrupts allow I/O to take place in parallel with the main computation, with the CPU getting a signal as soon as the I/O has been completed.

The Towers of Hanoi is a fun little porblem with a nice recursive solution that we examined. Iterative solutions to it have been found, but they are far more complicated and elegant than the recursive one we studied.

Last, the IA-64 architecture uses the EPIC model of computing to make it easy for programs to exploit parallelism. It uses instruction groups, predication, and speculative LOADs to gain speed. All in all, it may represent a significant advance over the Core i7, but it puts much of the burden of parallelization on the compiler. Still, doing work at compile time is always better than doing it at run time

Common instructions

LOAD

Move data from RAM to registers.

STORE

Move data from registers to RAM.

MOVE

Copy data among registers.

ADD

Add two numbers together.

COMPARE

Compare one number with another.

JUMP IF CONDITION

Jump if condition to another address in RAM

JUMP

Jump to another address in RAM.

OUT

Output to a device.

IN

Input from a device such as a keyboard.

Instruction Formats

An instuction consists of an opcode, usually alongwith additional information such as where operands come from and where results go to. The general subject of specifying where the operands are (i.e, their addresses) is called addressing. There can be several possible formats for level 2 instructions. An instruction always has an opcode to tell what the instruction does. There can be zero, one, two, or three addresses present. On some machines, all instructions have the same length; on others there may be many different lengths. Instructions may be shorter than, the same length as, or longer than the word length. Having all the instructions be the same length is simmpler and makes decoding erasier but often wastes space, since all instructions then have to be as long as the longest one. Other trade-offs are also possible.

Addressing

Most instructions have operands, so some way is needed to specify where they are. This is called addressing.

Immediate addressing

The address part of an instruction actually contains the operand itself rather than an address or other information describing where the operand is.

Immediate addressing has the virtue of not requiring an extra memory reference ot fetch the operand. It has the disadvantage that only a constant can be supplied this way. Also, the numberof values is limited by the size of the field. Still, many architectures use this technique for specifying small integer constants.

Direct addressing

The address part of an instruction contains the operands full address in memory.

Like immediate addressing, direct addressing is restricted in its use: the instruction will always access exactly the same memory location. So while the value can change, the location cannot. Thus direct addressing can only be used to access global variables whose address is known at compile time. Nevertheless, many programs have global variables, so this form of addressing is widely used.

Register addressing

The address part of an instruction specifies a register rather than a memory location.

Register indirect addressing

The address

Virtual memory

Virtual memory is an architectural feature whose purpose is to allow programs to use more address space than the machine has physical memory, or to provide a consistent and flexible mechanism for memory protection and sharing. It can be implemented as pure paging, pure segmentation, or a combination of the two. In pure paging, the address space is broken up into equal-sized virtual pages. Some of these are mapped onto physical page frames. Others are not mapped. A reference to a mapped page is translated by the MMU into the correct physical address. A reference to an unmapped page causes a page fault. Both the Core i7 and the OMAP4430 ARM CPU have MMUs that support virtual memory and paging.

CPU

En Central Processing Unit (CPU) er "hjernen" til moderne datamaskiner. Hovedfunksjonen til en CPU er å utføre instruksjoner som er gitt av et dataprogram. Disse dataprogrammene er lagret i hovedlageret til CPUen. Dette gjøres ved at instruksjoner hentes inn til hovedprosessoren hvor den inspiserer og så sekvensielt kjører hver instruks. Hver av disse "instruksjonsettene" ligger i en buss.

Array processor

Mange identiske prosessorer som synkront gjør de samme operasjonene på datasett med lik struktur, men ulikt innhold. Dette lar maskinen utføre store mengder arbeid parallellt, nyttig f.eks. for å analysere vitenskapelig data.

Vector processor

Lignende idé som array processor. Dataene som skal jobbes med puttes i en vektor og sendes samlet gjennom en prosessor spesialdesignet for å håndtere slike vektorer.

Ord | Word

En benevnelse som benyttes om den naturlige datastørrelsen i en gitt datamaskin. Et ord er ganske enkelt en samling av bit som håndteres samtidig av maskinen. Antallet bit i et ord, kalt ordstørrelsen, er et viktig kjennetegn ved enhver datamaskinarkitektur. Vanlige ordstørrelser i dagens PC-er er 32 og 64 bit. De fleste registrene i en datamaskin har størrelsen til et ord.

Locality of reference | Lokalitetsprinsippet

Når man ber om ett ord fra hovedminnet, antar man at man kommer til å trenge det ordet flere ganger, og at man også kommer til å trenge noen av naboene. Derfor blir ordet sammen med noen av naboene kopiert til hurtigbufferet.

Gjennomsnittlig minneaksesstid | mean memory access time

Lokalitetsprinsippet betyr at for å bruke ett ord k ganger trenger man ett tregt kall til hovedminnet og deretter k - 1 raske kall til hurtigbufferet. Ved hjelp av k kan man regne seg fram til et gjennomsnitt på hvor raskt prosessoren kan jobbe.

mean access time = c + (1 - h) * m

• c er cache access time, tiden det tar programmet å hente informasjon fra hurtigbuffer.
• m er memory access time, tiden det tar å hente informasjon fra hovedminnet.
• h = (k - 1)/k er trefforholdstall (hit ratio), andelen av referanser som kan hentes fra hurtigbufferet i stedet for hovedminnet. (1 - h) er dermed miss ratio, andelen som må hentes fra hovedminnet.

Adderere

Når man adderer to bits sammen har man de fire mulighetene som tabellen viser. Kretskomponenten som adderer to bits kaller man en halvadderer (half adder).

For å addere et ord som består av flere bits, må man ha en ripple-carry adder. Det kan man lage ved å lenke sammen flere fulladderere.

Fulladdereren består av en halvadderer som adderer de to bitene, og en annen halvadderer som adderer resultatet fra den første halvaddereren med carry-biten fra addisjonen av de forrige bitene. Summen herfra lagres som resultat-bit, og hvis en eller begge av addisjonene i dette steget produserte en carry-bit sendes en cassy-bit videre til neste fulladderer.

Parallellisme

Parallellisme kommer i to generelle former, nemlig parallellisme på instruksjonsnivå og parallellisme på prosessornivå.

1.1 Introduction

Vi bruker datamaskiner overalt, i blant annet biler, telefoner, og innebgyde systemer (embedded). Personlige datamaskiner (Personal Computers (PC)) er datamsskiner designet for å brukes av en bruker, gjerne med et grafisk grensenitt og enheter som et tastatur og en mus. Servere er datamaskiner som brukes for å kjøre større programmer, gjerne rettet mot flere brukere, gjerne samtidig, og er ofte tilgjengelig via et nettverk. Supercomputers er datamskiner med høyest ytelse og kostnad, og er gjerne laget som servere. Disse har gjerne flere terabytes(TB) med minne(1,000,000,000,000 (10^(12)) bytes. Innebgyde datamaskiner (embedded computer) er en datamaskin innen en annen enhet som er brukt for å kjøre et gitt programm eller aplikasjon. Telefoner og nettbrett er Personal mobile devices (PMDs)(personlige mobile enheter).

Cloud Computing (skytjenester) refererer til store samlinger av servere, gjerne på et datasenter, som man kan knytte seg til via internettet og brukes til bl.a lagring. Software as a Service(Saas) er en tjeneste som leverer software som en tjeneste over internettet, gjerne gjennom en browser på en lokal enhet i stedet for binær kode som må installeres på datamskinen. Eksempler er søkemotorer og sosiale media.

1.2 Eight Great Ideas in Computer Architecture

2.1 Introduction

For å programmere en datamaskin sin hardware, må man "snakke" dens språk. Dette er da i form av instruksjoner. Hver datamaskin har et instruksjonssett, et "vokabular" for å kunne gi "kommandoer" til en datamaskinarkitektur. Vi jobber med instruksjonssettet RISC-V (uttalt "risk five").

En datamaskin bruker stored program concept, som er ideen at instruksjoner og data kan bli lagret i minnne som nummer (en rekke med binære tall som 0 og 1, som kan utrykkes med desimal).

2.2 Operations of the Computer

I en RISC-V instruksjon som add a, b, c, vil datamaskinen ta inn verdien til variablene b og c og legge de i a. Vær obs på denne rekkefølgen.

Eksempel på addisjon av flere variabler (engelsk):

The following sequence of instructions adds the four variables: add a, b, c// The sum of b and c is placed in a add a, a, e// The sum of b, c, d, and e is now in a add a, a, d // The sum of b, c, and d is now in a

Thus, it takes three instructions to sum the four variables.

// Utgjør kommentarer i koden.

2.3 Operands of the Computer Hardware

I motsetning til variabler man er vandt med i annen kontekst, jobber man i datamaskinarkitektur med registre. I RISV-V har man 32 ulike registre. Størrelsen på et register i RISV-V arkitektur er enten 64 bits (doubleword) eller 32 bits (word).

Noen instruksjoner i RISC-V er data transfer instructions, som innebærer å overføre data mellom minne og registre. For å gjøre dette, må man vite adressen til dette dataelementet, som er en verdi som indikerer plasseringen til dataen i en minnestruktur.

I instruksjoner kan man også bruke konstante verdier. Eksempel (på engelsk):

An alternative that avoids the load instruction is to offer versions of the arithmetic instructions in which one operand is a constant. This quick add instruction with one constant operand is called add immediate or addi. To add 4 to register x22, we just write addi x22, x22, 4 // x22 = x22 + 4

RISC-V har et register, x0som er hardkodet til verdien null(0).

2.4 Signed and Unsigned Numbers

Least Significant Bit - LSB (til høyre i ordet) Most Significant Bit - MSB (til venstre i ordet)

Toerskomplement (two's complement) eksempel (på engelsk):

Suppose we're working with 8 bit quantities (for simplicity's sake) and suppose we want to find how -28 would be expressed in two's complement notation. First we write out 28 in binary form.

00011100

Then we invert the digits. 0 becomes 1, 1 becomes 0.

11100011

Then we add 1.

11100100

That is how one would write -28 in 8 bit binary.

Thomas Finley, April 2000

For å sjekke om et tall er positivt eller negativt, trenger en datamaskinarkitektur bare sjekke første bit, om det er 1 (negativt tall) eller 0 (positivt tall). Dette er kalt sign bit (tenk minus/plus sign på engelsk).

2.5 Representing Instructions in the Computer

2.6 Logical Operations

arith = arithmetic AND, OR, XOR og NOT er bit-by-bit

3.2 Addition and Subtraction

Man vet at man får overflyt på et tall på toerskomplement(altså tallet kan ikke korrekt represnteres av gitt antall bit) når resultatet av to positive tall blir et negativt tall, og resultatet av to negative tall blir et positivt tall. Dette skyldes at det ekstra bit-et som blir brukt for å representere overflyten har "glidd" inn i sign-bitet, og man får da feil representasjon av tallet.

Knowing when an overflow cannot occur in addition and subtraction is all well and good, but how do we detect it when it does occur? Clearly, adding or subtracting two 64-bit numbers can yield a result that needs 65 bits to be fully expressed. The lack of a 65th bit means that when an overflow occurs, the sign bit is set with the value of the result instead of the proper sign of the result. Since we need just one extra bit, only the sign bit can be wrong. Hence, overflow occurs when adding two positive numbers and the sum is negative, or vice versa. This spurious sum means a carry out occurred into the sign bit. Overflow occurs in subtraction when we subtract a negative number from a positive number and get a negative result, or when we subtract a positive number from a negative number and get a positive result. Such a ridiculous result means a borrow occurred from the sign bit.

For unsigned tall, kan man se om det har skjedd overflyt om resultatet av en sum er mindre enn de to tallene som adderes og om resultatet av å trekke fra et tall er større enn forskjellen mellom de to tallene.

5.1 Introduction

Det finnes to typer lokalitet ("nærhet); lokalitet i tid og lokalitet i rom. Prinsippet bak disse er at når man henter en intstruksjon, er det stor sannsynlighet for at man trenger en instruksjon som ligger nært i adresserommet(rom). Om man henter en instruksjon, er det også stor sannsynlighet for at man skal bruke denne instruksen igjen snart (tid). Oppstår f.eks. i løkker.

Wikipedia Commons

I en datamaskin er det er hierarki av minne. Dette representeres grafisk som en trekant, for å beskrive forholdet mellom størrelse, pris, fart og lokalitet. I en minnestruktur som dette er det raskeste minnet (i toppen av trekanten) det raskeste minnet, men også det dyreste per størrelsesenhet og det minste i størrelse. Hvordan dette fungerer er at prosessoren vil be om data fra det øverste nivået av minne. Om den ønskede dataen finnes i det gitte minnet, kalles dette en hit, mens om denne dataen ikke finnes i det gitte minnet, kalles dette en miss. I dette tilfellet må man hoppe et steg ned i hierarkiet av minne for å igjen se om den gitte ønskede dataen eksisterer der. Raten av hit versus miss er hit-raten, gitt i en brøkdel mellom 0 og 1. Miss-raten er 1-hit rate.

Minneblokk (block (or line)): den minste enheten informasjon som kan være tilstede (eller ikke tilstede) i en cache.

Om man får en miss, bruker man miss penalty for å beskrive tiden det tar å overføre en blokk fra et lavere nivå av minne til det øverste nivået i minne så det er tilgjengelig for prosessoren. Hit time er tiden det tar for å aksessere et nivå av minne og avgjøre om det var en hit eller miss.

5.2 Memory Technologies

5.3 The Basics of Caches

• direct-mapped cache: a cache structure where each memory location is matched to exactly one location in the cache
• tag: a field in a table used for memory hierarchy that contains the address information required to identify whether the associated block in the hierarchy corresponds to a requested word.
• valid bit: a field in the tables of a memory hierarchy that that the block contains valid data
• caches are used for prediction recently referenced words replace less recently referenced words.
• miss rate goes up if block size is too large relative to cache.
• early restart → processor doesn't wait for all data, just first word (after miss)
• requested word first/critical word first organizes by address slightly faster (after miss)
• cache miss: a request for data from the cache that cannot be filled, not present data. the address of the instruction that generates a cache miss is PC-4. if we have a miss we stall the processor
• write-through: a scheme in which writes always update both cache and the next lower- level of the memory hierary, ensuring consistent data
• write buffer: a queue that holds data while the data is waiting to be written to memory.
• write-back: updates values only to the block in the cache, modifies lower level memory when the cache block is replaced
• split cache: a scheme in which two independent caches operate in parallell, one w/ data and one w/ instructions
• fully associative cache: structure which a block can be placed in any location of the cache
• set-associative cache: fixed number of locations (at least 2) Where each blockcan be placed in cache
• when a miss occurs in a direct-mapped cache, the requested block can only go in one position → replace.
• in an associative cache, we have a choice of which to replace.
• in a fully assosian cache, all caches are candidates for replacement.
• set-associative → select between sets.
• Least Recently Used (LRU): a replacement scheme in Whichthe block replaced isthe one that has been unused the longest time.
• multilevel cache: multiple levels

A.2 Gates, Truth Tables, and Logic Equations

• asserted signal: '1' deasserted signal: 'O'
• combinatorial logic: no memory, output dependent on input
• sequential logic: memory. previous inputs + inputs

A.3 Combinational Logic

• decoder: logic block with n-bit input and 2n output, one output for each input
• PLA (Programmable Logic Array): implement logic functions as a sum of products
• ROMs (read only memory) (programmable ROMs, erasable PROMS) -erasure process ultraviolet light (slow)
• bus: a collection of data lines that are treated together as a single logical signal, or a collection of lines

A.7 Clocks

• clocking metodology: determine valid data relative to clock

A.8 Memory Elements: Flip-Flops, Latches, and Registers

• register file: a data element that consists of a set of registers that can be read and written to by supplying a register number to be accessed
• flip-flop: a memory element for which the output is equal to the value of the stored state inside, changed only on clock edge
• latch: output equal to data stored, state changed when inputs and clock is asseterted ('1')
• D flip-flop: one data input that stores input when the clock edge occurs
• setup time: minimum time input to a memory device must be valid before the clock edge
• hold time: minimum time the output must be valid after the clock edge