Instruction set and Addressing mode

Addressing Modes

Addressing mode are aspect of instruction set architecture. Defines how the instructions identifies the operand.

Immediate Addressing

• operand is present in the instruction
• typically number will be stored in 2's compliment form
• no memory reference other that instruction fetch is needed to get operand
• Limits the size of number with size of address field
• ADD R4, #5
• reg[R4] <--- reg[R4] + 5

Direct Addressing

• Address field contains effective address of the operand
• EA = A
• Single memory reference to get operand and no special calculations involved
• Limited address space
• ADD R4, 3000
• reg[R4] <------ reg[R4] + mem[3000]

Indirect Addressing

• with direct lenght of address field is usually less than word limiting the address range
• address field refers to address of word in the memory which in turn contains the full length address of operand
• two memory reference
• ADD R4, 3000
• reg[R4] <------ reg[R4] + mem[mem[3000]]
• number of words that can be addressed has increased but number of different effective address that may be referenced is still limited

Register Addressing

• address field refers to register rather than main memory
• only a small address field is needed as there are few registers
• no memory reference
• Limited address space
• ADD R4,R3,R2
• reg[R4] <--- reg[R3]+reg[R2]

Register indirect addressing

• accessed using computed address
• ADD R4,(R1)
• reg[R4] <--- reg[R4] + mem[reg[R1]

Displacement Addressing
direct addressing + register indirect addressing
Effective address = A + content of register R

1)relative addressing
the implicitly referenced register is PC that is A is added to PC to get EA
effective address is displacement relative to address of the instruction
exploits concept of locality
A + PC

2)base register addressing
the referenced register contains a memory address and address field contains a displacement(usually unsigned)
A + mem[mem[R]]
exploits locality of reference

3)Indexing
A= main memory address
R=displacement from that address

EA = A + content(R)
A lenght comparibly large than base register addressing

Auto indexing
index register, that is R displacement register, are used in iterative task so need to increment and decrement to address arrays or memory
automatically done part of same instruction cycle

EA = A + content(R)
R = R + 1

Post indexing
indirect addressing +  indexing
EA = content of A + content of R

preindexing EA = contents of (A + content (R))


Problem address stored in PC=X1 Instruction in X1 has addre ss part X2.The operands needed to execute the instruction is stored in memory word with address X2 An indext register contains the value X4 what is relationship between this when addressing mode is
1)direct
X3=X2

2)indirect
X2 should contain address of X3
that is content(X2) =X3
3)PC relative
X3= PC + displacement +1
X3=X1+X2+1
4)indexing
X3=X2 + index
X3=X2+X4

Problem If current instruction is 256028 in decimal and each instruction is 3 byte. offset is -31 find EA PC relative addressing
Solution
EA for pc address = next instruction address + offset(signed number)
next instruction address =  256028+3
EA = 256031 - 31 = 256000

EA for pc address = next instruction address + offset(signed number)

Problem A pC relative mode branch instruction is stored in memory at address 620 The branch is made to location 530 The address field in instruction is 10bit long
What is binary value in instruction
Solution Assuming offset is stored in 2's compliment because it should be signed number it can be negative for branch before and positive for branch after

EA for pc address = next instruction address + offset(signed number)

next instruction address (assuming one instruction per address) = 621
EA we have been given as 530 that is it branches to this address
so 530 - 621 = offset
offset = -91
two's compliment of -91 = 1110100101

Problem how many memory reference when it fetches and executes indirect address mode instruction is
a)computation with single operand
1 for instruction fetch+ 2 memory  reference for indirect address = 3
b)branch instruction
does not need to fetch the operand here only operand reference needed
1 for instruction fetch + 1 operand reference fetch = 2


Problem Instruction length is 16 bit.Operand specifics are 6 bits in length.
number of two operand instruction = K
number of zero operand instruction = L
number of 1 operand instruction = ?
Solution
Total number of bits is 16
total number of possible combinations is 2^16 of which we have to divide them as two operand instruction, one operand instruction and zero
For two operand instruction 12 bits are required for operand

K*2^12 + X*2^6 + L = 2^16Problem A 32bit ISA needs 100 opcodes 3 source operand 2 destination operand. source and destination operands are registers.maximum size of register file?
Solution 100 opcode needs 7 bits
5 operands(source+destination) have available 32-7  =25bits
each register can be addressed with 25/5 bits

 

Problem code to implement A = (B – C)*D in
1) three address instruction
SUB A B C
MPY A A D
2)two address instruction
MOV T1 B
SUB T1 C
MPY T1 D
MOV A T1
3)1 address instruction
LOAD B
SUB C
MPY D
STORE A
4)zero address
PUSH B
PUSH C
SUB
PUSH D
MPY
POP A

all instructions,data values  will be in memory and must be fetched from memory
fetching instruction like SUB A B C
requires 1 byte for opcode 2 byte for each address A B C. 7byte instruction of instruction to fetch

fetching data
each data value 2byte and during execution B and C datavalues will be fetched from the memory and A 2bytes will be written to memeory so total of 7+6 byte of memory traffic

 Unconditional branch
b label ;
assigns value of label to PC

Conditional branch
If condition is true PC is reset to label
If false branch instruction executes no-op
Zero test
beqz x,label   if x==0 then goto label
bnez x       if x!=0 then goto label
bltz less than zero blez if x less than or equal to zero 

Interrupt
Interrupt: depart from normal program sequence, also
called “exception”
Triggered not by instruction in the program itself
Types of interrupts:

– External interrupts: for example, from timing devices, I/O devices
– Internal interrupts: traps (invalid or erroneous use of an
instruction or data), eg. overflow, divide by zero, protection
violation
– Software interrupt: Generate an interrupt explicitly with an
instruction
An interrupt causes the normal program execution to halt and for the interrupt
service routine (ISR) to be executed.

Semiconductor memory
basic element memory cell
cell represent two stable state 1 and 0
capable of being written into, set state
three signals to each cell select(select particular cell) control(specify wether read or write) and read/write

DRAM
individual words of memory are directly accessed through wired -in address logic
RAM volatile(needs continous power, data donot persist on power cut) random access
DRAM stores data as charge on capacitor
capacitors have tendency to discharge so DRAM requires periodic charge refreshing
analogous device
SRAM
digital device uses flipflop logic gate config
DC applied
no refresh needed

comparision Dram and SRAM
both volatile and needs continous power.
DRAM simple small, more dense ,less expensive
DRAM requires refresh opeartion which is costly, favoured for large memory
SRAM generally faster, used as cache

Types of ROM
nonvolatile
can be read only

Problem write assembly code for
for (i=0; i<=100;i++)
 A[i] = B[i] + C;

R1= A[i]
R2=B[i]
R3=C
R4 = i*4

References
http://pages.cs.wisc.edu/~cs354-1/cs354/solutions/adv.hw.sol.html           // floating point and IEEE math
https://www.cis.upenn.edu/~cis501/

Number representations - IEEE floating point, 2's compliment,biased ..

 2's compliment

Fig 2's compliment representation

Positive number in 2s compliment
sign bit an-1 is zero
n-1 bits are allowed for the magnitude of number so total distinct positive numbers will be 2^(n-1)
numbers range from all zero to all ones(2^0+2^1+2^2 ...2^(n-2)) i.e from 0 to 2^(n-1) - 1

Negative Number in 2s compliment
sign bit an-1 is 1
for magnitude of number all bits are used in calculation including the most significant an-1 bit
Calculation of magnitude considers most significant bit as negative and rest as positive so
magnitude is calculated as  -2^(n-1)+ sum(0 to n-2)ai*2^i
smallest number in negative that can be represented is when all the n-1 bits are zero and only the msb contributes that is -2^(n-1)
Maximum number in negative 2s compliment is when all n-1 bits are 1 and they reduce the effect of msb, it is -2^(n-1) + (2^n-2 + 2^(n-3) ....2^1+2^0) = -1

Observations
single representation of zero, when all n bits are zero
we can represent -2^(n-1)  but not +2^(n-1) in 2s compliment
when bits of positive number n are complimented(1s compliment)  it becomes -(n+1) in decimal example
+3 is 0011, its compliment 1100 is -4
+7 is 0111 its compliment 1000 is -(8)
To obtain the negation of the number that is +n to -n we need to first take 1s compliment which will give us -(n+1) then we can add single digit to get the required number -n
negation of zero  will give zero only if we ignore the carry, exception case is for negation of -2^n-1 also where all bits will become zero , we get same number -2^n-1

Arithmetic Operations in 2s compliment

Addition
discard the extra bit when adding , two 4bit numbers discard the 5 msb if any of result. It is different from overflow which gives incorrect result.
when result is large than can be handled in word size we call it overflow. ALU must signal not to use the result.
example of overflow
add   1001  //-7
         1010  //-6
       10011  //   +3
Overflow can occur whether or not there is carry
overflow occurs when sign of result for two positive numbers or two negative numbers is opposite

Multiplication
//booth algorithm

Division

Overflow
when adding unsigned binary numbers, overflow occurs when the final carry-out is a 1
In 2's complement, the final carry-out is always ignored, and overflow occurs when there is a sign change

One's Complement
used to represent negative numbers
positive numbers same as in sign magnitude system (with first bit zero )
negative number is obtained by inverting the bits of positive number
zero has two representation +0 and -0
range of number sis -(2^n-1 - 1) to (2^n-1 -1)

Floating Point Representation

for numbers too large or too small
number is represented approx to fixed number of significant digits and scaled using exponent
way to represent scientific numbers
A floating point number consist of
1) significand mantissa or coefficient signed digit string.
significand length determines to which precision number can be represented, prportional to accuracy
2)a signed integer exponent scale factor proportional to range, more bits to the exponent means more range

|---|--------------|---------------------|
|---|--------------|---------------------|
sign(1bit)   E(8bit)       Significand(23bit)

Fig. 32 bit floating point Format

 S*B^e
B is bias, implicit, same for all numbers. bias value is typically 2^e-1 - 1
radix point is assumed to be after MSB bit of signigicand

advantage of biased representation is that non negative floating point numbers can be treated as integers for comparison purpose

sign: 0 positive, 1 negative

exponent: stored in biased form, that is, bias is subtracted from the field to get true exponent
exponent is 8 bits means number from 0 to 255 with bias it becomes -127 to +128


Significand: stored in normalized form, msb should be one and radix point should be after msb
msb one is taken as implicit and need not be stored, so 23 bit of significand can represnt 24 bits
In normalized value of significand lies in [1,2)

IBM/360 floating point format
total length 32 bits
exponent 7 bits
fraction 24 bits
bias 2^7-1  = 64 unlike IEEE, 2^n-1 -1 bias

base is 16 unlike IEEE  base-2
there are no hidden 1 significand
so normalization is to 0.bbbb only
If number is represented in IBM/360 floating point like
1/0 eeeeeee fffffff..

fraction has no hidden 1.
we get the decimal for the binary representation exponent and raise it to the base 16
(sign) 0.ffff  * 16 ^exponent

IEEE 754 floating point standard

 single precision: 1 bit sign, 8 bit exponent, 23 bit fraction (24 bit significand = 1+ fraction) (“1” is implied)
double precision: 1 bit sign, 11 bit exponent, 52 bit fraction (53 bit significand)



Fractional portion of the significand represents a fraction between 0 and 1 (each bit from left to right has weight 2-1, 2-2, …)
Since 0 has no leading 1, it is given the reserved exponent value 0 so that hardware won’t attach a leading 1 to it
Exponent is “biased” (biased notation) to make sorting easier
all 0s is smallest exponent (most negative) all 1s is largest (most positive)
bias of 127 for single precision and 1023 for double precision

(–1)^sign × (1 + fraction) × 2^{exponent – bias}

Exponent and mantissa of all zeros and ones are special values

Range of exponents 
exponent of all zero(0) and all ones(255) defines special values
For single precision
it can range from 1 to 254 and in bias we would say -126 to +127
for double precision
-1022 to +1023

Mantissa number of bits
A normalized number would add a hidden 1 making the mantissa of 2
24 bit for single precision
53 bit for double precision


Denomalized or subnormal number
demormal numbers have hidden bit of significand as 0
have exponent of all zeros 

0.0         0 or 1   00000000   00000000000000000000000
                                (hidden bit is a 0)

subnormal   0 or 1   00000000   not all zeros
                                (hidden bit is a 0)

normalized  0 or 1    > 0        any bit pattern
                                (hidden bit is a 1)

Representation of Zero
Two representation of zero +0 and -0

exponent and mantissa all 0

in hex 0x0000 0000 and  0x8000 0000

Representation of infinity and NaN
• +∞ an -∞ are denoted with an exponent of all 1's

s  e        f
  +∞     0 11111111 00000... (0x7f80 0000)
  -∞     1 11111111 00000... (0xff80 0000)
  NaN    ? 11111111 (not all zero) 
 

(S is either 0 or 1, E=0xff, and F is anything but all zeros)

significand fraction lies betwee 1/B <= s <=1
where B is base
for base 16 fraction lies betwee 1/16 and 1 inclusive
for base 2 its .5 to 1 inclusive

Error in representing recurring fractions

xT – true value
xA – approximate value

True Error in xA (exact value of the error) = E(x) = xT - x A
True Relative Error in xA = xT-xA / xT
True Percentage Relative Error in xA = xT-xA / xT * 100


Problem Consider 16 bit floating point format  with 1 bit for sign 5 for exponent and 10 for fraction exponent is in excess 15 representation
a) decimal for number in this format
0 01001 0101000000
Solution
sign bit is positive
exponent is in excess 15 so e+15 = 9
e=-6
so the value is 1.0101₂ * 2^-6 which is (1 + 1/4 + 1/16)/64 = 2.05078 * 10^-2

b)convert decimal number -50.75 in above representation
50₁₀ = 110010₂  and .75₁₀ = .11₂ 
so -50.75 = -1.1001011 * 2⁵
 biased exponent value will be 15 + 5 = 20₁₀ = 10100₂
leaving the first bit in significand
Number is 1 10100 1001011000


Problem 6 bit wide number represented in 2's compliment what is maximum and minimum number
Solution Minimum when first bit is 1 i.e -2^n-1 = -32
Max number when first bit is zero and sum of all n-1 bits i.e 2^n-1 -1  = 31




Problem Consider bit pattern 1010 1100 1011 0101 0011 0000 0011 1000 what value does it represent in
1)2's compliment
since number is negative(msb is 1) we find the value by
1)subtracting  1
2)fliping bits

2)single precision floating point
sign = negative
exponent 8 bits after sign 010 11001, its biased so we have to subtract 127 from it
i.e 89-127 = -38
significand is remaining bits with an implicit 1 so
1.011 0101 0011 0000 0011 1000
number is - 1.011 0101 0011 0000 0011 1000 * 2^-38

Problem Convert - 1101001.10011 to IEEE format

Solution
a) Normalize : -1.10100110011 * 2 ^6
b)exponent = 6+127= 133 = 10000101
significand 10100110011  and remaining bits goes zero


Problem Consider IBM base-16 single precision format
represent decimal number 2.25 in this format

Solution

1)get sign bit, 0
2)express number in binary
(2.25)d = (10.01)b

Base 16 format means number is represented

Offset Binary Numbers (Excess-K)

all zeros corresponds to minimal negative value 00000000..
all ones correspond to maximal positive value 111111...


excess 2^n-1
take an example where 4 bit number is stored in  excess 8
4 bit number 1111
in unsigned notation its 15 in decimal
in offset biased notation the number is  15 - 8 =7
so decimal range for number is from -8, all zero's 0 - 8
and max would be 7, when all 1's  15-8
zero would be represented by 1000 because 8- 8(excess-8)

comparison to 2's compliment 
If we look at the minimum and maximum number above we can see that if we invert the first bit we get the same number in 2's compliment
like minimum -8 is 0000 in excess 8
invert first bit 1000 and interpret as 2's compliment its same
for 8 we have 0111 in excess-8
invert first bit 1111 and in 2's compliment it is 8

Example
excess 2^n-1 is used in IBM mainframe 360/370  to store the exponent
excess (2^n-1 - 1) is used in IEEE 754 to store the exponent



converting  IEEE  to decimal number
IEEE single precision  1 bit sign 8 bit exponent rest signigicand
number in significand lies between  1/2 <=s <= 1

For single precision
total length = 32 bits
exponent =  8 bits
bias =  2^8-1 -1 =127
fraction is 32 - (8+1) = 23 bits

for double precision
total lenght = 64 bits
exponent= 11bits
bias is 2^11-1 -1 =1023
fraction is 64 - (11+1) = 52
 steps
1)get the sign bit from
2)get the next 8 bits for the exponent from the representation
this is in excess 2^8-1 -1 i.e excess-127 for single precision
3)subtract 127 from the exponent value
e = extracted exponent - 127
4) get the 24 bit fraction f the representation
and one to the fraction 1.f
now number is
(sign) (1.f) * 2^e

Convert from binary to IEEE format

convert from decimal to IEEE
1)convert decimal number into binary
2)normalize it form 1.bbb * 2^e
3) find the exponent by adding bias
4)add bbbb... to significand and store exponent
when bbb... lenght is less than number of bits to store store remaining zeros
(sign) (exponent)  bbbbbbbbbb

Example


1)10.6
10 =   1010 ,  .6=10011001...
For single precision
1) so number in binary is  1010.10011001 with repeating pattern 1001
2) normalize it, 1.01010011001... * 2^3
3) exponent is 3+127 = 130, in binary 10000010
4) sign is 0
fraction becomes repeating pattern  for total length of 23
0 10000010 01010011001..

Converting decimal to IBM/360 floating point format

Steps
1)get the sign bit of the number
2)express decimal number in binary notation
3)normalize it, its base-16 so we move 4 bits at a time instead of 1
since we are moving radix point in binary  *2^4(16) will move radix right 4 places
and if we moved n times exponent is n
like for binary 10.01 we represent it in normal base 16 as
.001001 *  16^1
for binary .00001
.1*16^-1
4)fraction is to the right of radix point in normalized form
5)exponent is 64+power of base-16, express it in binary

Example
2.25
1)sign = +
2)binary for 2.25 decimal = 10.01
3)normalized value = .001001 * 16^1
4)fraction value is 001001 and rest zeros for 24 bits total
5)exponent is 64 + 1 = 65, in binary 1000001
6) number is 0 1000001 001001000000000000000000


Floating Point Arithmetic
1)Align radix point, exponent values should be same for both opernads
2)perform operation
3)

Overflow and Underflow 


Overflow
overflow is check by checking exponent value before and during normalization
positive exponent exceeds the maximum possible exponent value
represented by setting to infinity 
Underflow
occurs when number is too small(near zero) and getting a 1 before radix point in normalized form causes exponent field to be zero 
underflow may result in demormalized values where hidden bit will be zero and exponent wil be all zeros
precision would be reduced 



largest negative number(magnitude)
exponent all 1's = 255-127 = 128
fraction all 1's  = (.111...) = (1/2)^1 +(1/2)^2 .....(1/2)^23 = ((1/2)^24 - (1/2))/(-1/2) = -2^-23+1
significand would be 2-2^-23
sign -1
number is  -(2-2^-23) *2^128
Negative overflow
numbers less than -(2-2^-23) *2^128 are negative underflow
smallest magnitude negative number 
exponent all 0's = -127
fraction all 0's =0
significand =1+0 =1
number - 2^-127
Negative underflow
numbers greater than - 2^-127 are negative underflow
smallest positive number expressible
exponent all zeros
fraction all zeros
significand 1
number 2^-127
Positive underflow
numbers less than 2^-127 are positive underflow
largest positive number
all exponent bits 1
all fraction bits 1 = 1-2^-23
significand = 2-2^-23
number  (2-2^-23)*2^128


Rouding
when number cannot represented in limited precision bits, we round the results
there are number of ways of rounding 
IEEE standard requires
ALU register also has three extra bits  other than significand 1.bbbbb
extra bits in order from lsb
1)guard bit
2)round bit
3)sticky bit

when mantissa has to be shifter to align the radix point, bits that fall off the lsb goes into extra bits.These bits can also be set in division and multiplication
guard and round bits are for precision 
if sticky bit is set to 1 it remains at 1 to indicate what was beyond  lsb

1. round toward 0. truncates any bits that the representation does not hold. result is approximate value represented err on the side of being closer to 0.
2. round toward positive infinity. chooses representations that err on the side of being to "the right" as viewed on a number line.
3. round toward negative infinity. chooses representations that err (for representing approximate values) on the side of being to "the left" as viewed on a number line.
4. round to nearest. This method attempts to distinguish which approximate value that may be represented is closer to the desired value. 

Number Conversions

All Operations on 7bit number
Decimal Number to 1's compliment form
1)find the representation for positive number that is 127
2)negate the bits  
Represent -127 in 1's compliment
solution
representation of 127 is 0111111 so 1's compliment is negation of this that is1000000
Represent 0 in 1's compliment
1's compliment has two representation for zero +0(all zero's) and -0(will all 1's)

Decimal Number to signed representation 
1)include sign bit (msb)  =1 when number is negative else 0
2)represent the number with remaining n-1 bits in normal form

Represent -23 in signed representation
1)msb =1
2)binary of 23 is 16+4+2+1 = 010111
so signed number is 1010111

Decimal Number to 2's compliment
for negative number
1)find binary for +N
2) -N = (1's compliment[n] +1)

Note remember to convert number to required number of bits

example if we convert 23 to 10111 in 5 bits instead of 6 and perform operation like
23 = 10111
2's compliment = (01000 +1) = 01001 it gives positive number which is incorrect

represent -23
1)23=010111

2)1's compliment of 23=  1101000
2's compliment  is 1101001


2's compliment to decimal number
For negative
if number has more 1's then zero then
1)B = (1's compliment B + 1)
example represent 2's compliment 10111 in decimal
B = -(01000 +1) = -(01001) = -9

http://pages.cs.wisc.edu/~cs354-1/cs354/karen.notes/flpt.apprec.html
www.cs.sunysb.edu/~cse220/Homework/HW1-sol.pdf      //IEEE and floating point

Instruction Pipeline and CPU Performance

• Pipeline is implementation technique where multiple instructions are overlapped in execution.
• Pipeline does not reduces the completion task for single task but increases the throughput of entire workload
• preformance increase from pipeline is directly proportional to number of pipe stages

 Key Terms
Instruction Latency : time from initiation of instruction until its result available.
Throughput is number of operations per unit time
Pipeline overhead is (pipeline register delay + clock skew)
Lenght of all stages is same in pipeline, equal to length of longest stage + overhead
Speed up = (average instruction time non pipeline)/ (avg instruction time in pipeline architecture)
Average instruction time in pipeline architecture is equal to instruction latency because after first instruction each instruction completes in one stage time.
Speedup for n instructions  is ratio of time needed to process n instruction of non pipeline to that on pipeline architecture

that is
Sn = n * T / (n+k-1) * Tk
T time to process one instruction on non pipeline
Tk clock cycle time


Example
Consider 6 execution stages of lengths 40 ns, 50 ns, 60 ns, 50 ns, 60 ns, and 40 ns.

Find the instruction latency and time execute 100 instructions on both pipelined and non pipeline machine assume overhead of 5ns in pipline machine.

Solution
non pipeline machine
instruction latency is time from initiation of instruction to its completion
each instruction consist of 6 stages of enght mentioned above so
 instruction latency = 40+50+60+50+60+40 = 300
time to execute 100 instruction is 100*instruction latency = 30000ns

Pipeline machine
Since all stages have same length in pipeline each would be equal to (largest stage + overhead)
i.e 60+5ns
After first instruction is complete we get result for other instruction at interval of clock cycle
So Time to execute 100 instruction is  65*6 + 99*65=6825ns

Problem An instruction requires 4 stages of 30ns 9ns,20ns,10ns.
i)What is minimum asynchronous time for instruction to complete
Solution 30+9+20+10 = 69ns
ii)what should be the clock rate if we use pipeline for this stages
clock rate should be able to accommodate the largest stage 30sec because each instruction in pipeline can be initiated in 30ns and would give latency of 30*4 = 120ns
we can choose finer  clock by looking at the shortest stage that is 9ns and find clock rate that is integrally divisible in other stages if we choose 10ns it would take 3 clock for first stage 1 for second 2 for third and 1 for last and would give latency of 70ns
ii)what is speed up
speed up = 30+9+20+10/30 =2.3

Harzard
Consider a 5 stage pipeline, to run pipeline at full performance 4 next instruction will start their execution before first complete but what if these next instructions are dependent on the result of the first instruction

I1
I2 //depends on the output of I1
I3//depends on output of I1

these kind of situations which prevent next instruction to continue are called hazards.such situations can occur because programmer may assume that in sequential program first instruction will complete and then only next instruction will execute

Data Hazard
the pipeline is delayed because the data to be operated on are delayed for some reason
when the result of instruction i is the source of instruction j (j>i)
decode stage cannot continue for instruction 2 and need to be resumed after instruction 1 has written the result
Instruction attempts to read the data before data is available in register file

Classification of Data Hazard
1)RAW read after write
2)WAW
3)WAR

Data Hazards are avoided in one of the two ways
Operand Forwarding
We allow ID to fetch the wrong content from register file but by using the bypass multiplexer we compare the content read in the decode stage with content of execute stage
 Before instruction j writes data to register it is availabe at output of ALU after execute stage.
Instruction Decode fetches contents from register file

Pipeline Interlock

load addr --> r0
add r1 <--- r1 +  r0
For such instructions it is not possible to foreward the result because the content of register r0 is not availble until the end of memory access for load while the add instruction needs the r0 at mem access of load
We need to insert stall in such case

Control Hazards
caused by conditional and unconditional branching

1)Stall Pipeline

2)Predict not taken

• high performance than previous but more complex
• predict ------------not taken branch ------------continue with instructions after branch
• two scenarios occur when its actuallu taken and when not taken
• not taken branch
• no change
• taken branch
• Assume after ID stage we know if branch is taken or not and new instruction address then we need to restart IF for branch instruction and discard the fetched instruction causing a delay of one clock cycle

          1     2    3    4     5    6     7
----------------------------------------
B       F     D   E   M    W
i+1            F   -    -       -
Bk                  F    D     E  ..

3) Predict branch as taken
If target address can be known before branch instruction then it can be of use

4) Delayed Branch

B
i+1
i+2   /// branch delay slot
i+3
...
Bk

Instructions in branch delay slot are executed whether or not branch is taken

For taken branch it will look like

          1     2    3    4     5    6     7
----------------------------------------
B       F     D   E   M    W
i+1            F   D    E     M  W
Bk                  F    D     E  ..

If branch is untaken,
    execution continues with the instruction after the branch delay instruction.
If the branch is taken,
    execution continues at the branch target.

The job of the compiler is to make the instruction that fills this slot useful and valid.

Branch scheduling schemes
1) from before the branch

• we move the instruction before the branch in the delay slot  but branch should not depend on moved instruction
• this strategy is best, always results in performance enhancement

2)from target

• In case before branch instruction decides the branch we can move the taget instruction in the branch delay slot It should not harm to execute the rescheduled instruction in case branch is not taken, when branch is taken can increase the code as two copies will be executed
• improves performance when branch is taken

3)from fall through

• improves performance when branch is not taken

 Cancelling branch

Solving problems
1)If no forwarding is used then result is available after MEM
2)If forwarding is used result is available in ID
3)If LW instruction is used then result is not available until MEM even if forwarding is used
4)If branch not taken strategy is used and if loop runs n times then n-1 times branch will be predicted wrong and 1 time it is predicted correct
5)find number of times loop runs and then count number of steps by counting until last instruction's IF stage
multiply to get total number of steps
6)MUX is used for bypassing
7)seperate adder needs to be used when branch is to be calculated in ID stage
-------------------------------------------------------

CPU Performance
1) If x is n% faster than y
execution_time (y) = (1+nf) * execution_time (x)

2)CPU time = number of clock cycles * clock cycle time  or
                   = nnumber of clock cycles / clock rate

number of clock cycle = instruction count(IC) * Clock cycles per instruction (CPI)

so CPU time = IC * CPI * (clock cycle time)
                     = (instructions/program) * (cycles/instruction) * cycle time

Problem compare the cpu time for two cases
i)condition code is set by the compare instruction and followed by branch that test condition code
ii)compare is included in branch instruction itself
Assume conditional branch instruction takes 2 clock cycles and all other instruction take 1 cycle.For case 1 number of branch instruction is 20%. clock cycle time for case 1 is 25% faster also because it has single instruction
Solution
cpu time = IC(i) * CPI * (clock cycle time)
CPI = CPI of branch + CPI for other instructions(including compare)
CPI branch  = (frequency of branch instruction) * (cycles for branch instruction )
 frequency of branch instruction(i) = .20*IC(i) / IC(i) = .20
CPI(i)    = .20*2 + .80*1 = 1.2
for case ii
we donot have compare instructions we have only load instructions which constitutes 20% of all instructions
total number of instructions in terms of case i is
IC(ii) = IC(i) - .2* IC(i) = .8*IC(i)
CPI branch = (frequency of branch instruction) * (cycles for branch instruction )
 since 20% of total instructions in case(i) were branch instructions but in case(ii) total number of instructions has changed which is 80% of case i
frequency of branch instruction(ii) = .20*IC(i) / .80*IC(i) =  .25
CPI(ii) = .25*2 + .75*1 = 1.25
clock cycle time(ii) =  1.25 * clock cycle time (i)

Unpipeline system
Average instruction execution time = clock cyle * Average CPI

Pipeline system without  hazards
Average instruction executiion time = (clock cycle + overhead) * Average CPI
Average CPI for pipeline system is considered as 1 so
Average instruction executiion time = (clock cycle + overhead)

Pipeline system with hazards
A stall causes pipeline performance to degrade from the ideal
speedup = (Avg execution time on non pipeline system) / (Avg execution time on pipeline system)
CPI = Ideal CPI + pipeline stall clock cycles per instruction (because of hazards)
ideal CPI of pipeline system is 1
so CPI = 1+ pipeline stall clock cycles per instruction
 
Instruction pipeline performance in case of branch penalty

Avg time for instruction = Ideal CPI + (penalty) * P(branch)* P(taken)

1 + (penalty) * P(branch)* P(taken)

Problem
In an instruction pipeline of 10ns clock memeory instruction takes 2 stall cycles branch instruction takes 3 stall cycles and frequency of memory and branch instruction is 20% and 30% resp.calculate average instruction time
Solution
Average instruction time = (Ideal CPI + pipeline stall clock cycle per instruction ) * clock cycle time
                                     = (1+ (.20*2+.30*3)) * 10ns
                                    =  23ns

If we consider out of 20% branch only 10% of time its taken then
Average instruction time = (Ideal CPI + pipeline stall clock cycle per instruction ) * clock cycle time

                                      = (1+ (.20*.10*2+.30*3)) * 10ns  = 19.4ns

Without Forwarding  dependent instruction Decode cannot occur until WB of the previous instruction
that is
I1 I2 where I2 is dependent on I1
 
        1     2     3      4          5      6
----------------------------------------
I1    if     id     ex   mem      wb  
I2           if       -       -         id      ex   ...
 

With  Forwarding
Results can be forwarded from EX, MEM and WB so immediately next as well as other instruction after that can get the result

        1     2     3      4          5      6
----------------------------------------
I1    if     id     ex   mem      wb  
I2           if      id     ex         ...
 
here ex of I2 is forwarded result from ex of I1

Problem Consider standard RISC pipeline with 5 stages each instruction takes single cycle for each stage
loop: I1  //load instruction
        I2  // add instruction using data loaded in register in I1
        I3
        I4
        I5
       bnz (condition) loop

 bnz is branch instruction and assume that loop runs for n times Draw the pipeline timing  diagram
i) when no forwarding
ii) with forwarding
Solution

i) no forwarding

Result of the branch is not known until mem stage of branch instruction so the bnz instruction restarts after mem stage of I5
17 clock cycle it takes for single iteration,18th cycle we will be counting in the next iteration so for all iteration except last we have 17 clock cycles and for the last iteration we have 18 clock cycle
total clock cycle for n iterations = (n-1)*17+1*18

ii) with forwarding and branch prediction as not taken

In cycle 4 we have stall for instruction I2 because it is case of Pipeline interlock where data from I1(load instruction) is not available until after memory instruction to I2(add instruction)

m in the last instruction I1 is because of incorrect branch prediction of not taken
Total cycles for complete n iterations = 10*n-1+11*1

Note n-1 time its predicted wrong but the last time the branch is predicted correct so we need to take that case into account

http://www.cc.gatech.edu/classes/cs4760_96_fall/hw/hw2-sol.html
http://pages.cs.wisc.edu/~markhill/cs752/Fall1999/hw3-sol.html

Cache memory - Direct mapped, Set Associative, Associative ,Performance

 Direct mapped Cache

Mapping function 

Each main memory block can be mapped to only single cache line like ,
 each 0, m,2m ... block can be assigned to cache block 0
 each m+1, 2m+1, 3m+1 ... block can be assigned to cache block 1

cache line number  = (main memory block number) mod number of cache lines
                            = (main memory address / Block size) mod number of cache lines
                            = (M_d/B) mod m

Problem 1

A two dimensional byte array A[50][50] is stored in main memory starting address 0x1100 in row major order. Direct mapped cache is used with 32 line.
If array is accessed in following order

for (int i=0;i< M; i++)
 for (int j= 0;j
    A[i][j] = 0

1)Find number of cache miss assuming cache is empty initially.
2)consider same code to run again, one more time after first scenario then find total cache miss.
3) If the size of array element is t Bytes  then find total cache miss for single array access.
4) What difference would it make if we had fully associative cache.

Solution 1.1

Array is accessed in order


A[0][0], A[0][1] ....  A[0][N-1] .... A[M-1][0],A[M-1][1] ...A[M-1][N-1]

First element A[0][0] is stored at address (0x1100)_H = (1048576)_d in decimal

Cache line to which element A[0][0] will be mapped
  = (main memory block number) mod number of cache lines
  = (main memory address / Block size) mod number of cache lines
  = (1048576 / 64) mod 32 = 0



so first element is mapped to first cache line and complete block of 64 bytes are moved
i.e elements A[0][0] to A[0][49] and A[1][0] to A[1][13](64th element of two dimensional array) will be moved in cache line zero

Next reference to A[0][1] will be a hit and so till A[1][13](64rd element of array)

Fig. shows organization of main and cache memory

Each Bth(block size) element will be miss because first element in every new memory block will not be present in cache.


i.e number of miss will be ceil(MN/B) for array A[M][N] for this case

= ceil(50x50 / 64) = 40

Fig shows state of cache memory

number of blocks that will be overwritten on first array access is ceil(MN/B) - m

= 40-32
= 8

Solution 1.2

On first run of function we had 40 cache miss  and first 8 blocks were overwritten.


Now array elements are accessed again from A[0][0]

Assuming it as first run then there would be ceil(MN/B) = 40 cache miss
But since we already have data from previous run in the cache memory of which we had overwritten first 8 blocks so
remaining 32 - 8 = 24 are still present in cache memory and we will have hit for that may elements
So number of cache miss will be 40-24 = 16

Therefore Total number of cache miss after two run of function would be 40 + 16 = 56

Solution 1.3

When transferring block to cache from main memory  we moved 64 elements earlier which lead to miss on every 65 element
Now in a block we can accommodate (B/t) elements Hence transfer would be for next B/t -1 elements along this one.  Hence every (B/t) will give result in a cache miss here


So we will have (MN/(B/t)) cache miss.

Associative Mapping

main memory block can be loaded in to any cache line
address is interpreted as just tag and word instead of line because which ever line is empty we put block into that
number of lines in cache is not determined by address format unlike as in Direct mapped

Set Associative Cache

cache is divided into v sets each consisting of k lines
k-way set associative mapping that is there are k possible lines in which the same mapped blocks can go.

cache line number  = (main memory block number) mod number of sets v
                            = (main memory address / Block size) mod (number of cache line/k)
                            = (M_d/B) mod m/k
memory address is interpreted as tag set and word
tag+set specify a block in main memory

when memory address is presented from CPU it indexes with set bits in cache to find set where would could be It then compares tag bits with every tag field of line in set and if there is match then it addresses the word in that line
number of cache lines
here tag comparison is only to k possible


Problem  A 64KB cache has 16 byte blocks. If addresses are 32 bits, how many
bits are used the tag, index, and offset in this cache?
a)if cache is direct mapped
Solution
number of bits for addressing word= 4bit
number of cache lines = size of cache / size of block = 64KB/16B = 4K = 12bits
remaining 16 bits for tag so  division of 32 bits is like
16bit  12bit  4bit


b)if cache is 4-way set associative
number of bits for addressing word are same 
number of lines/blocks in each cache set is 4 
so each cache set is 4*16B = 64B
number of cache sets = size of cache/size of cache set = 64KB/64B = 1K 
so 10 bits for cache set/index
so division of 32 bits is like 
18bit tag  10bit index  4bit word


c)for fully asscociative cache
number of index bits = 0 because any block can be stored in any line


Problem Consider following
cache size 8 byte, 
2-way set associative
2 byte block size with
LRU replacement
request for addresses
0110, 0000, 0010, 0001, 0011, 0100, 1001, 0000, 1010, 1111, 0111
determine address in cache and miss/hit
Solution 
number of lines/blocks in each set = 2
size of cache set = 2*2 B = 4B
number of cache set = 8B/4B = 2 
division of 4bits address
2bit tag  1bit index 1bit word


2 bytes(block) are moved for each address so next address would be also brought in cache 
here index maps directly into 0 or 1 cache set
if index is 1 its set 1 and if bit is 0 its set 0

1) for address 0110
index is 1 so it goes in  set 1
set 0  --------
         ---------
set 1 01------(address 0110 and 0111) 
       ----------
its compulsory miss because first reference of 0110
2)0000
index 0
set 0  00------(address 0000 0001)
         ---------
set 1 01------(address 0110 and 0111)
       ----------
its compulsory miss because first reference of 0000
3) similarly for 0010 its compulsory miss and placed in set 1 line 2 with next byte 0011
4), 0001 its hit because its in set0 line1
5)0011 hit
6)0100 compulsory miss mapped to set 0 line 2 with next byte 0101
7)1001 is first reference hence compulsory miss it will replace content of set 0 line based on LRU


set 0  (0000 0001)
         (0100 0101)
set 1  (0110 0111) 
         (0010 0011)
0000 is reference least recently so its replaced in line1
and line 1 would be now (1001 1010)
8)0000
it 0000 second reference and its miss so its conflict miss 
replaces with LRU its 0100 second line so now set 0 line 2 is 0000 0001
9)1010 compulsory miss mapped to set 1 line 1 because 0110 should be replaced 
now content of set1 line 1 is 1010 1011
10)1111 compulsory miss mapped to set 1 line 2
set 1 line 2 1111 0011
11)0111
we brought this block into cache but was replaced without use so
its capacity miss




Types of cache miss
Compulsory miss: when block is accessed for first time its called first reference miss, cold start miss or compulsory miss
Capacity miss: when blocks are discarded because cache cannot contain all blocks needed for program execution. when block is discarded before its use
Conflict miss: when several blocks are mapped to same cache set/block. Occurs in case of direct mapped and set associative cache




Cache performace
number of memory stall = number of miss  * miss penalty(cost per miss)
number of miss = IC * misses/instruction
miss/instruction =number of memory access/ instruction * miss rate






Problem Consider CPI = 1, only data access are load and store which makes 50% instructions 
miss penalty =25clock cycles, miss rate 2%
Solution 
number of memory access per instruction is 1 for instruction and .5 for data 
Memory stall cycle = IC * (1+.5)* .02*25 = .75*IC
cpu execution time = (cpu clock cycle + memory stall cycle) * clock cycle
with cpu with all cache hits its =  (IC*CPI ) * clock cycle
for cache its .2 miss rate ts  (IC*CPI +IC*.75) * clock cycle =1.75*IC * clock cycle
the computer with no cache miss is 1.75 times faster


Problem Consider CPI for ALU=1, Load/Store=1.5,  Branch=1.5, Jump=1. instruction mix of 40% ALU and  logical operations, 30% load and store, 20% branch and 10% jump instructions.
4-way set associative cache with separate data and instruction cache 
 miss rate of 0.20 for data and miss rate of  0.10 for instructions
miss penalty of 50 cycles for both . What is the effective CPU time (or effective CPI with memory stalls) and the average memory access time for this application with this Cache organization?
Solution
CPI ideal =(0.4*1)+(0.3*1.5)+(0.2*1.5)+(0.1*1) = 1.25.
memory stalls = number of memory access/ instruction * miss rate *miss penalty
.3 load/store data operations
1 instruction 
memory stall = .3*.2*50 + 1*.1*50 =8
Average memory access time = percentage of data accesses (hit time + data miss rate* miss penalty) +
percentage of inst. Accesses (hit time + inst.miss rate*miss penalty).
Therefore AMAT = (0.3/1.3)(1 + 0.2*50) + (1/1.3)(1+ 0.1*50).


b)Now consider a 2 level 4-way unified cache with a level l (L1) miss rate of 20% (0.20) and a
level 2 (L2) local miss rate of 30% (0.30). Assume hit time in L1 is 1 cycle, assume miss penalty
is 10 cycles if you miss in L1 and hit in L2 (i.e., hit time in L2 is 10 cycles), and assume miss
penalty is 50 cycles if you miss in L2 (i.e., miss penalty in L2 is 50 cycles). Derive the equation
for the effective CPU time (or effective CPI) and the average memory access time for the same
instruction mix as part (a) for this cache organization.

First note that the miss rate for L2 is given as the local miss rate. Average memory accesses per
instruction = 1.3 as noted earlier (0.3 for data and 1 for inst).


Cache miss penalty reduction
L2 cache second level cache
average memory access time = hit time(L1) + miss rate(L1) * miss penalty(L1)
miss penalty(L1) = hit time(L2) + miss rate(L2) * miss penalty(L2)
Local miss rate is total number of miss in cache divided by total number of access to cache
Global miss rate is total number of misses/ total number of CPU accesss
for L2 global miss rate is  miss rateL1 * miss rate L2
for L1 global and local miss rate is same

Write policy
write through written to both block in cache and to lower memory
write back written only to block in cache .Modified block is written to memory only when it is replaced. write occurs at speed of cache memory, less memory bandwidth required save intermediate writes. Read miss can result in writing the 
cpu wait during write through is called write stall. 
write allocate  a block is allocated on write miss that is a block is written in memory so next time it will be hit
no write allocate until read miss no block is allocated


www.seas.gwu.edu/~bhagiweb/cs211/homeworks/hw4-sol.pdf

References:

http://www.cs.lth.se/EDA115/    -- Cache memories Problem solutions

Magnetic Disk Problem Set

Magnetic Disk
bit near center moves slow comparision to bit near end
increasing the spacing between bits in outer tracks so that head can move with CAV
disadvantage amount data in outer and inner track would be same , limited by amount of data that can be stored in inner track
so density increases moving to inner tracks
multiple zone recording
within a zone number of bits per track is constant
zones father from center contains more bits hence better utilization of space
As head moves from one zone to another along same track length of bits changes, causing change in timing for read and write
seek time
= initial startup time + time to traverse tracks
traversal time is not linear that is if it takes t seconds to reach track 4 then it would take 2t to reach track 8 is not the case that is
It also has startup time and settling time


Problem Consider disk with rotation 5400rpm, seek time 4+.05t msec  where t is number of track
1024 tracks,512sector/track,block size 512 bytes.DMA and disk controller read and write data at 4MB/sec
a) capacity of disk
1024*512*512
b)reading 16KB file where sector contagious on track. max and min throughput
maximum th
rotational latency = 1/5400m/rev = 60/5400 sec/rev
it means it takes 60/5400 sec to read a track or 512sectors
so it takes 60/(5400*512) sec =22micro sec to read a sector
In case of maximum throughput we donot have any rotational latency overhead or seek latency It only takes time to move over that many sectors to read
there 16K/512 = 32 sectors in file
so to read 32 sectors it will take 22*32 microsec =694microsec = .694msec
so it takes 694 microsec to read file from the disk
Now we need DMA transfer will take time 16KB/4MB/s = 3.9 msec

Total time is time to get disk from disk + time to transfer via DMA = .694+3.9


For minimum throughput
It has to go for maximum distance to get data that is it has to seek all 1024 tracks and a complete rotational delay to reach data
seek time + latency = 4+.05*1024 + 60/5400


In average case
if there are t tracks, r rpm then
average seek time = t/2 * (per track seek time)
Average rotational delay = 60/ 2r rpm

Worst case
seek time = t * (per track seek time) 
rotational delay 60/ 2r

To read contagious sectors of file
we work on track 
1) For first track we have avg seek time and avg rotational delay overhead
2)For rest of tracks we have track-track seek time

To read non contagious file
we caclulate data for a sector
1)for each sector overhead of avg seek time, avg rotational delay
2) we add the time for all sector for that much number of blocks in file

Cylinder
Both surface of platter and tracks on them form cylinder
if there are p platters and both surface of each platter is used then
A cylinder has 2*p tracks

I/O and Interrupts

fraction of processor time consumed =k/t when
interrupt is generated every t sec and takes k sec to process interrupt
|------------t-----------|----k-----|

If DMA steals 1 cycle every k msec then
fraction CPU slow down is  1/k

Problem A microprocessor scans output I/O device every 20ms There are two interface ports status and output.Instruction takes 12 clock cycles.If clock is 8Mhz how long does it take to scan and service device.
Solution To check the status one instruction to read the status register, One instruction to verify content of register that is if ready or not and one more instruction if ready to feed data to device
each instruction takes (12*1)/(8*10^-6)=1.5microsec
so total of 3 instruction would take 4.5microsec

Problem If character is input in keyboard character buffer each k msec what should be scan rate
Scan should be done atleast 1 every k msec

Problem Average number of commands entered through keyboard is 60 per 8hr
If keyboard is scanned every 100ms then
1)number of times CPU scanned in 8hr?
2)number of scan if interrupt driven I/o is used
3)fraction
Solution  10 scan every sec so in 8hr its 8*60*60*10 scans
In interrupt driven I/O interrupt would be generated for each command so 60 interrupts
Problem Interrupt I/o is used on system with average 8KB/s transfer rate
1)if interrupt processing takes 100microsec. what fraction of time is consumed by i/o device if it interrupts for each byte
in a second it would interrupt 8000 times per sec or 1/8000 =1 every 125microsec
if each interrupt takes 100microsec
fraction  = 100/125
2) if device has 2 16byte bufer and interrupts the cpu after one buffer is full It takes 8microsec to transfer each byte then
it interrupts 8K/16B times that is 500 times every sec or 1 times every 2000microsec
100microsec for interrupt processing + 16*8microsec for transfer of each chracter