程序代写代做代考 computer architecture flex cache PowerPoint Presentation

PowerPoint Presentation

REVISION

Bernhard Kainz

b.kainz@imperial.ac.uk

mailto:b.kainz@imperial.ac.uk

Boolean Algebra – Truth Tables

• All possible outcomes of the operators can be written as

truth tables

Boolean Algebra – Rules

• Note: A and B can be any Boolean Expression

Negation:

(A’)’ = A

A • A’ = 0

A + A’ = 1

Associative:

(A • B) • C = A • (B • C)

(A + B) + C = A + (B + C)

Commutative:

A • B = B • A

A + B = B + A

Distributive:

A • (B + C) = A • B + A • C

A + (B • C) = (A + B) • (A + C)

Note the precedence

Boolean Algebra – Rules

Single variables (Idempotent law):

A • A = A

A + A = A

Simplification rules with 1 and 0:

A • 0 = 0

A • 1 = A

A + 0 = A

A + 1 = 1

Boolean Algebra – de Morgan’s Rule

(A + B)’ = A’ • B’

(A • B)’ = A’ + B’

as before, A and B can be any Boolean expression

Can generalise to n Boolean variables:

(A + B + C + D + …)’ = A’ • B’ • C’ • D’ • …

(A • B • C • D • … • X)’ = A ‘ + B’ + C’ + D’ + … + X’

Half Adder

• Recall

• Truth Table

0 0 1 1

+ 0 1 0 1

00 01 01 10

A B A + B Sum Carry

0 0 0 0 0

0 1 1 1 0

1 0 1 1 0

1 1 2 0 1

Full Adder

S = A⊕ B⊕ Cin
Cout = (A • B) + Cin • (A ⊕ B))

Full Adder

• Conceptually

1-Bit Full

Adder

A B

Cout Cin

S

Latches

• SR-Latch: Truth table

S R Q Q’

0 0 Latch

0 1 0 1

1 0 1 0

1 1 Undefined

Memory

• Useful variation on the SR latch circuit is the Data latch,

or D latch

• Constructed by using the inverted S input as the R input

signal

• Allows for a single input  No race condition as input is inverted

Memory

• Memories hold binary values

• Data (e.g. Integers, Reals, Characters)

• CPU Instructions (i.e. Computer Programs)

• Memory Addresses (“Pointers” to data or instructions)

• Contents remain unchanged unless overwritten with a

new binary value

• Some of them lose the content when power is turned off (volatile

memory)

Computer Architecture

Input/Output Controllers

RAM RAM

Main Memory

Arithmetic & Logic Unit (ALU)

Registers
Control

Unit

CPU

Hard Disk

DVD Drive

Memory Stick

Mouse,

Keyboard

Monitor, Printer,

Scanner

Ethernet

Modem

Wifi

Bluetooth

GSM/GPRS

Speakers,

Microphone,

Camera, Game

Devices

Summary

Registers

RAM

Hard Disk

expensive cheapCOST

small largeCAPACITY

high lowVOLATILITY

slower

SPEED

faster

difficult

FLEXIBILITY

USABILITY

easier

Cache

Byte Addressing (Big Endian)
Main Memory

1

3

5

7

9

11

13

15

Byte Address

0

2

4

6

8

10

12

14

Byte Address

0110 1101 1010 1101

0000 0000 0000 0011

0000 0000 0000 0000

1111 1111 1111 1111

0000 0000 0000 0000

1001 1010 1010 0010

0000 0000 0000 0000

1111 1111 1111 1110

Byte Addressing (Little Endian)
Main Memory

0

2

4

6

8

10

12

14

Byte Address

1

3

5

7

9

11

13

15

Byte Address

0110 1101 1010 1101

0000 0000 0000 0011

0000 0000 0000 0000

1111 1111 1111 1111

0000 0000 0000 0000

1001 1010 1010 0010

0000 0000 0000 0000

1111 1111 1111 1110

1GB (256M x 32-bit) Memory

256M

rows

32 bits

1GB (256M x 32-bit) Memory
• Four 256MB memory modules

• Each module has four 64M x 8-bit RAM Chips

8

Module 0

256MB

Module 1

256MB

Module 2

256MB

Module 3

256MB

64M

8 8 8

64M

64M

64M

Memory Interleaving

• Example:

• Memory = 4M words, each word = 32-bits

• Built with 4 x 1M x 32-bit memory modules

• For 4M words we need 22 bits for an address

• 22 bits = 2 bits (to select Modules) + 20 bits (to select row within

Module)

Row within Module

220

Low-Order Interleave

High-Order Interleave

Module

Row within Module

2 20

Module

MSI Chips – Multiplexer

• A multiple-input, single-output switch

• Also called MUX for short ☺

• sel selects which of I0 or I1 is mapped to the output

• For example, sel = 0 selects I0 and sel = 1 selects I1

• Example is called a 2-to-1 MUX

• With n selects/control lines, we can have 2n input lines

MSI Chips – Decoder

• Only one output is 1 – the

one selected by the n-bit

binary input number – the

rest are zero

• Useful in transmitting line

selection with fewer wires

(e.g. selecting a memory

chip)

MSI Chips – Decoder

• Truth Table

A B C D7 D6 D5 D4 D3 D2 D1 D0

0 0 0 0 0 0 0 0 0 0 1

0 0 1 0 0 0 0 0 0 1 0

0 1 0 0 0 0 0 0 1 0 0

0 1 1 0 0 0 0 1 0 0 0

1 0 0 0 0 0 1 0 0 0 0

1 0 1 0 0 1 0 0 0 0 0

1 1 0 0 1 0 0 0 0 0 0

1 1 1 1 0 0 0 0 0 0 0

MSI Chips – Calculations – Comparator

• The comparator returns 1

if the two n-bit inputs A and

B are equal, 0 otherwise

MSI Chips – Calculations – Bit-shifter

• Faster calculations for powers of 2

• Shift left and right (multiply and divide)

• c = 0  shift left

• c = 1  shift right

The Arithmetic Logic Unit (ALU)

• The ALU is able to perform

multiple functions

• Depending on the input to

the decoder (F0,F1) one of

four functions is selected –

A and B, A or B, not B,

arithmetic A+B

Data representation

Bit Pattern 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Unsigned 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Sign &

Magnitude
+0 +1 +2 +3 +4 +5 +6 +7 −0 −1 −2 −3 −4 −5 −6 −7

1s

Complement
+0 +1 +2 +3 +4 +5 +6 +7 -7 -6 -5 -4 -3 -2 -1 -0

2s

Complement
+0 +1 +2 +3 +4 +5 +6 +7 -8 -7 -6 -5 -4 -3 -2 -1

Excess-8 -8 -7 -6 -5 -4 -3 -2 1 0 1 2 3 4 5 6 7

BCD 0 1 2 3 4 5 6 7 8 9 – – – – – –

ASCII Character Set

Bit positions 654
Bit positions
3210

000 001 010 011 100 101 110 111

NUL DLE SP 0 @ P ‘ p 0000

SOH DC1 ! 1 A Q a q 0001

STX DC2 “ 2 B R b r 0010

ETX DC3 # 3 C S c s 0011

EOT DC4 $ 4 D T d t 0100

ENQ NAK % 5 E U e u 0101

ACK SYN & 6 F V f v 0110

BEL ETB ‘ 7 G W g w 0111

BS CAN ( 8 H X h x 1000

HT EM ) 9 I Y i y 1001

LF SUB * : J Z j z 1010

VT ESC + ; K [ k { 1011

FF FS , < L \ l | 1100 CR GS - = M ] m } 1101 SO RS . > N ^ n ~ 1110

SI US / ? O _ o DEL 1111

Strings are represented as sequence of characters. E.g. Fred is encoded as follows:

English F r e d

ASCII (Binary) 0100 0110 0111 0010 0110 0101 0110 0100

ASCII (Hex) 46 72 65 64

Two’s Complement – BNA Summary

• Addition
• Add the values, discarding any carry-out bit

• Subtraction
• Negate the subtrahend and add, discarding any carry-out bit

• Overflow
• Adding two positive numbers produces a negative result

• Adding two negative numbers produces a positive result

• Adding operands of unlike signs never produces an overflow

• Note – discarding the carry out of the most significant bit during
Two’s Complement addition is a normal occurrence, and does not
by itself indicate overflow

Floating point zones of expressibility

• Example: assume numbers are formed with a signed 3-

digit coefficient and a signed 2-digit exponent

• Zones of expressibility:

Normalised forms (base 10)

Number Normalised form

23.2 × 104 2.32 × 105

−4.01 × 10−3 −4.01 × 10−3

343 000 × 100 3.43 × 105

0.000 000 098 9 × 100 9.89 × 10−8

Binary fraction to decimal fraction

• What is the binary value 0.01101 in decimal?


1

4
+

1

8
+

1

32
=

13

32
= 0.40625


8+4+1

25
=

13

32

• What about 0.000 110 011?

• Answer:
32+16+2+1

29
=

51

512
= 0.099 609 375

𝟐−𝟏 𝟐−𝟐 𝟐−𝟑 𝟐−𝟒 𝟐−𝟓

. 0 1 1 0 1

𝟑𝟐 𝟏𝟔 𝟖 𝟒 𝟐 𝟏

. 0 1 1 0 1

Floating point multiplication

𝑁1 × 𝑁2 = 𝑀1 × 10
𝐸1 × 𝑀2 × 10

𝐸2

= 𝑀1 ×𝑀2 × 10
𝐸1 × 10𝐸2

= 𝑀1 ×𝑀2 × 10
𝐸1+𝐸2

• That is, we multiply the coefficients and add the

exponents

• Example:

2.6 × 106 × 5.4 × 10−3 = 2.6 × 5.4 × 103

= 14.04 × 103

• We must also normalise the result, so final answer is

1.404 × 104

Floating point addition

• A floating point addition such as 4.5 × 103 + 6.7 × 102 is not a
simple coefficient addition, unless the exponents are the same.
Otherwise, we need to align them first

𝑁1 +𝑁2 = 𝑀1 × 10
𝐸1 + 𝑀2 × 10

𝐸2

= 𝑀1 +𝑀2 × 10
𝐸2−𝐸1 × 10𝐸1

• To align, choose the number with the smaller exponent and
shift its coefficient the corresponding number of digits to the
right

4.5 × 103 + 6.7 × 102 = 4.5 × 103 + 0.67 × 103

= 5.17 × 103 = 5.2 × 103

(rounded)

IEEE Single precision format (32-bit)

• Coefficient is called the significand in the IEEE standard

• Value represented is ±𝟏. 𝑭 × 𝟐𝑬−𝟏𝟐𝟕

• The normal bit (the 1.) is omitted from the significand
field  a hidden bit

• Single precision yields 24 bits (approx. 7 decimal digits
of precision)

• Normalised ranges in decimal are approximately:

−𝟏𝟎𝟑𝟖 to −𝟏𝟎−𝟑𝟖, 0, 𝟏𝟎𝟑𝟖 to 𝟏𝟎−𝟑𝟖

Sign

S

1 bit

Exponent

E

8 bits

Significand

F

23 bits

Special values

• IEEE formats can encode five kinds of values: zero,

normalised numbers, denormalised numbers, infinity

and not-a-number (NaNs)

• Single precision representations:

IEEE value Sign

field

Exponent Significand True

exponent

Value

±0 0 or 1 0 0 (all zeros) ±0.0 x 20

± denormalised no. 0 or 1 0 Any non-zero bit
pattern

−126 ±0. F x 2
_126

±normalised no. 0 or 1 1…254 Any bit pattern −126…127 ±1. F x 2E
_127

±∞ 0 or 1 255 0 (all zeros) ±1.0 x 2128

Not-a-number 0 or 1 255 Any non-zero bit
pattern

±1. F x 2128