Webinar-1

Performance Assessment
Error Correction
BITS Pilani
Pilani Campus
CPU-OS Simulator Q&A
 Performance Assessment
(R1: 1.4, T1: 2.3)
- MIPS Rate, Amdahl’s Law
BITS Pilani
Pilani Campus
Performance Assessment-Summary

• If you were running a program on two different

processors, we would say that the faster is the one that
gets the job done first.
• Execution time: The total time required for the computer
to complete a task, including disk accesses, memory
accesses, I/O activities, operating system overhead, CPU
execution

BITS Pilani, Pilani Campus

Performance Assessment-Summary
• All computers are governed by a clock that determines when
events take place in the hardware.
• These discrete time intervals are called clock cycles.
• The rate of clock pulses is known as the clock rate, or clock
speed (Hertz) which is the inverse of the clock period. For
example, 1 GHz processor receives 1 billion pulse / sec
CPU Performance and Its Factor

BITS Pilani, Pilani Campus

Performance Assessment-Summary

Instruction Performance

• The term clock cycles per instruction, which is the average

number of cycles each instruction takes to execute, is often
abbreviated as CPI.

BITS Pilani, Pilani Campus

Performance Assessment –
Millions of Instructions per Second
(MIPS) Rate

Million Instructions Per Second (MIPS) is the common

measure of performance for a processor is the rate at
which instructions are executed, expressed as
MIPS or referred to as MIPS rate

BITS Pilani, Pilani Campus

Problem -1

A benchmark program runs on a system having clock rate of

40MHz. The program consists of 100000 executable
instructions with following instruction mix and clock cycle
count for each instruction type.
Instruction Type Instruction Count Cycles Per
(IC) Instruction (CPI)
Integer Arithmetic 45000 1
Data Transfer 32000 2
Floating Point 15000 2
Control Transfer 8000 2
Determine the effective CPI, MIPS and execution time for
the program

BITS Pilani, Pilani Campus

Solution -1

Given Data :
• Clock speed of the processor = 40MHz
• No. of Instructions the executed program consists of =
100000

• CPI = = = 1.55

BITS Pilani, Pilani Campus

Solution -1

• To calculate MIPS

• MIPS = (40 x 106 ) / (1.55 x 106)

• = 25.8

BITS Pilani, Pilani Campus

Solution -1

• To calculate Execution Time

• Execution Time = Instruction Count x CPI x Cycle Time
= Ic x CPI x (1/f)
= (100000 x 1.55) /(40x106)
= 0.003875
= 3.875 ms

BITS Pilani, Pilani Campus

Problem - 2
A Netcom systems developed two computer systems C1 and C2.,where C1 has
machine instructions for floating point (FP) operations as part of its processor ISA
and C2 does NOT have floating point instructions as part of its processor ISA.
Since C2 does not have floating point instructions, all floating-point instructions
will be implemented in Software level with non-FP instructions. You can assume that
both systems are operating at a clock speed of 300 Mhz. We are trying to run the
SAME program in both the systems which has the following proportion of
commands:

BITS Pilani, Pilani Campus

Solution-2
a) Find the MIPS for both C1 and C2.
Clock speed = 300 MHz
For C1:
• CPI =
0.16*6 + 0.1*8 + 0.08*10 + 0.66*3 = 4.54
• MIPS =
300 * 10^6 / (4.54 * 10^6) = 66.08
For C2:
• CPI =
0.16*20 + 0.1 * 32 + 0.08 * 66 + 0.66 * 3 = 13.66
• MIPS =
300 * 10^6 / (13.66 * 10^6) = 21.96
BITS Pilani, Pilani Campus
Solution-2 Contd…
b) Assume that there are 9000 instructions in the program
that is getting executed on C1 and C2. What will be the CPU
program execution time on each system C1 and C2 ?
• CPU time for C1 of the program execution
= No of instructions * CPI / Clock rate
= 9000 * 4.54 / (300*10^6)
= 0.136 ms

• CPU time for C2 of the program execution

= No of instructions * CPI / Clock rate
= 9000 * 13.66/ (300 * 10^6)
= 0.41 ms

BITS Pilani, Pilani Campus

Solution-2 Contd…
c) For the two systems to have the fastest speed and at the
same time have equal speed, what would be the possible
combination of the instructions that would be required in the
program? WHY?

• For both C1 and C2 should be equally fast,

• Have a program that does NOT have any floating point instructions
as CPI for non-floating point instructions is same between C1 and C2.

BITS Pilani, Pilani Campus

Problem -3 (Home work)

• Consider two different machines, with two different

instruction sets, both of which have a clock rate of 200
MHz. The following measurements are recorded on the two
machines running a given set of benchmark programs:

• Determine the effective CPI, MIPS rate, and execution

time for each machine.

BITS Pilani, Pilani Campus

Amdhal’s Law

• Deals with the potential speedup of a program using

multiple processors (parallel) compared to a single
processor.
• It states that if P is the proportion of a program that can
be made parallel and (1-P) is the proportion that cannot be
parallelized (remains sequential), then the maximum speed
up that can be achieved by using N processors is:

• As N tends to infinity, the maximum speedup tends to

1/(1-P)

BITS Pilani, Pilani Campus

Amdhal’s Law

Speedup = Time to execute program on a single processor

_____________________________________
Time to execute program on N parallel processors

T(1-P) + TP
= ________

T(1-P) + TP/N

•As N tends to infinity, the maximum

speedup tends to 1/(1-P)

BITS Pilani, Pilani Campus

Problem -4 (Amdhal’s Law)

• A programmer is given the job to write a program on a

computer with processor having speedup factor 3.8 on 4
processors. He makes it 95% parallel and goes home
dreaming of a big pay raise. Using Amdahl’s law, and
assuming the problem size is the same as the serial version,
and ignoring communication costs, what is the speedup
factor that the programmer will get?
• Solution:
• Given Data: No. of Processors (N) = 4
• Proportion of parallelism = 95%
• Speed up = 1/[(1-P)+P/N]
= 1/[(1-0.95)+0.95/4]
= 3.47
BITS Pilani, Pilani Campus
Problem – 5 (Home Work)

• A programmer has parallelized 99% of a program, but there

is no value in increasing the problem size, i.e., the program
will always be run with the same problem size regardless of
the number of processors or cores used. What is the
expected speedup on 20 processors?

BITS Pilani, Pilani Campus

 Hamming Code
BITS Pilani
Pilani Campus
Error Correcting Code Function
• The comparison logic receives as
input two K-bit values. A bit-by-
bit comparison is done by taking
the exclusive-OR of the two
inputs. The result is called the
syndrome word.
• The comparison yields one of
three results
– No errors are detected.
– An error is detected and it is
possible to correct the error
– An error is detected but it is
not possible to correct it.
BITS Pilani, Pilani Campus
Hamming Code…..
What should be the length of the code K

• Length of Data is “M” bits

• length of the syndrome word is K bits,
• Length of K should satisfy
2k-1 >= M+K
and K has a range between 0 and 2k-1

BITS Pilani, Pilani Campus

Problem 1

Let us assume data transmitted is 1011, data corruption

in Semiconductor memory has resulted in altering the
content of a single memory cell. How do we detect
and correct the error using Hamming Code?

Step 1 : Check the length of Check bits required to

form Tx word
Data = 1011 (M=4)
2k-1 >= M+K
Here M = 4. at least K value should be 3
Hence there are in total 7 bits for transmission

BITS Pilani, Pilani Campus

Problem 1

Step 2: How to calculate Check bits and their position

Now we know there are total 7 bits for transmission

Data bits – D1, D2, D3, D4
Check bits – C1, C2 and C3

__ __ __ __ __ __ __

BITS Pilani, Pilani Campus

Problem 1

Step 2: How to calculate Check bits and their position

C3 C2 C1 Position Bits

Positi
7 6 5 4 3 2 1
on
• C1 = 1 1 1 = 1
Bits • C2 = 1 1 = 0
Data • C3 = 1 1 = 0
bits
BITS Pilani, Pilani Campus
Problem 1

Step 2: How to calculate Check bits and their position

(Given Data = 1011)

• C1 = 11 1 = 1
• C2 = 1 1 = 0
• C3 = 11 = 0

        2^2   2^1 2^0

Positi
7 6 5 4 3 2 1
on
Bits D4 D3 D2 C3 D1 C2 C1
Data
1 0 1 0 1 0 1
bits
BITS Pilani, Pilani Campus
Problem 1 – Data bit corrupted

Step 3: Let us assume the corrupted data received is

1111. Calculate Check bits for the received word
        2^2   2^1 2^0
Positi
7 6 5 4 3 2 1
on
Bits D4 D3 D2 C3 D1 C2 C1 • Calculated Check bit
Data • C1 = 1 1 1 = 1
1 1 1 1 1 1 1 • C2 = 1 1 1 = 1
bits
• C3 = 11 1 = 1

Step 4: Compare Check bits to generate Syndrome

Calculated check bits : 111

Syndrome : 110
Toggle the (110)2 or 6th position bit to get the correct data.
Here Corrected data is 1010111. Extracting Data it yields 1011
BITS Pilani, Pilani Campus
Problem 1 – Check bit is corrupted

Step 3: Let us assume the data received is same 1011.

Calculate Check bits for the received word
        2^2   2^1 2^0
Positi
7 6 5 4 3 2 1
on
Bits D4 D3 D2 C3 D1 C2 C1 • C1 = 1 1 1 = 1 (0)
Data • C2 = 1 1 = 0
1 0 1 0 1 0 0
bits • C3 = 1 1 = 0

Step 4: Compare Check bits to generate Syndrome

Received check bits : 000

Syndrome : 001
Change in Single bit indicates error in one of the check bits. Only error signal is
generated.

BITS Pilani, Pilani Campus

Problem 1. Conclusion…

• If the syndrome contains all 0s, no error has been

detected.
• If the syndrome contains one and only one bit set to
1, then an error has occurred in one of the 3 check
bits. No correction is needed.
• If the syndrome contains more than one bit set to 1,
then the numerical value of the syndrome indicates
the position of the data bit in error. This data bit is
inverted for correction.

BITS Pilani, Pilani Campus

Problem 2 - Homework

Consider a 12 bit (Data + Check bit) Code 111101011101

Find out if there is an error. If so which bit is having
error?

BITS Pilani, Pilani Campus

Layout of Data and Check bits

•  

⊕ : Bitwise XOR operation

BITS Pilani, Pilani Campus
 Q&A

BITS Pilani
CPU-OS Simulator
Pilani Campus
CPU OS Simulator
• Components of CPU Simulator
• Execute a program
• Cache updates
• Assignment

BITS Pilani, Pilani Campus

CPU-OS Simulator Interface

BITS Pilani, Pilani Campus

How to Simulate and Run the
program
Simulator Teaching Language (STL)
program SelectionSort
VAR a array(10) INTEGER
a(1)=15
a(2)=20
a(3)=8
a(4)=100
a(5)=30
for n = 1 to 5
writeln("num",a(n))
next
for i = 1 to 5
for j = i+1 to 5
p = a(i)
q = a(j)
if p > q then
x=p
a(i) = q
a(j) = x
end if
next
next
writeln("Sorted Array in ascending order")
for n = 1 to 5
writeln("num",a(n))
next
end

BITS Pilani, Pilani Campus

How to Simulate and Run the
program
Simulator Teaching Language (STL)
a) Execute the above program by setting block size to 2, 4, 8,
16 and 32 for cache size = 8, 16 and 32. Record the
observation in the following table.

b) Plot a single graph of Cache hit ratio Vs Block size with

respect to cache size = 8, 16 and 32. Comment on the graph
that is obtained.
BITS Pilani, Pilani Campus
Web link for CPU-OS Simulator
Resources
• Link to download CPU-OS Simulator
• https://drive.google.com/drive/folders/12YUK52RQ-JhP0d
dj6CD_oifW4sTMbsBl?usp=sharing

• Introduction to CPU Simulator

• https://www.youtube.com/watch?v=izcvk0x7kKM&list=PLGz
_KyS7cuuWGqFbBITk7Nr4PoVmAWkE0

• Installation on Mac OS
• https://www.youtube.com/watch?v=2vBjXUbvCKs

BITS Pilani, Pilani Campus