UNIVERSIDAD DE CUENCA

FACULTAD DE INGENIERÍA

Programación I

Estructuras de Selección

2do Ciclo – Computación Grupo 1

Elian Chacha

4 de abril de 2023

Ing. René Estrella

Exercise 1.1

Find the word or phrase from the list below that best matches the description in the
following questions. Use the numbers to the left of words in the answer. Each
answer should be used only once.

1. virtual worlds 14. operating system

2. desktop computers 15. compiler
3. servers 16. bit
4. low-end 17. instruction
5. supercomputers 18. assembly language
6. terabyte 19. machine language
7. petabyte 20. C
8. datacenters 21. assembler
9. embedded computers 22. high-level language
10. multicore processors 23. system software
11. VHDL 24. application software
12. RAM 25. Cobol
13. CPU 26. Fortran

1.1.1 [2] Computer used to run large problems and usually accessed via a network. servers (3)
1.1.2 [2] 1015 or 250 bytes. petabyte (7)
1.1.3 [2] Computer composed of hundred to thousand processors and terabytes of memory.
supercomputers (5)
1.1.4 [2] Today’s science fiction application that probably will be available in the near future.
virtual worlds (1)
1.1.5 [2] A kind of memory called random access memory. RAM (12)
1.1.6 [2] Part of a computer called central processor unit. CPU (13)
1.1.7 [2] Thousands of processors forming a large cluster. data centers (8)
1.1.8 [2] Microprocessors containing several processors in the same chip. multicore processors
(10)
1.1.9 [2] Desktop computer without a screen or keyboard usually accessed via a network. low-
end servers (4)
1.1.10 [2] A computer used to run one predetermined application or collection of software.
embedded computers (9)
1.1.11 [2] Special language used to describe hardware components. VHLD (11)
1.1.12 [2] Personal computer delivering good performance to single users at low cost. desktop
computers (2)
1.1.13 [2] Program that translates statements in high-level language to assembly language.
compiler (15)
1.1.14 [2] Program that translates symbolic instructions to binary instructions. assembler (21)
1.1.15 [2] High-level language for business data processing. Cobol (25)
1.1.16 [2] Binary language that the processor can understand. machine language (19)
1.1.17 [2] Commands that the processors understand. instruction (17)
1.1.18 [2] High-level language for scientific computation. Fortran (26)
1.1.19 [2] Symbolic representation of machine instructions. assembly language (28)
1.1.20 [2] Interface between user’s program and hardware providing a variety of services and
supervision functions. operating system (14)
1.1.21 [2] Software/programs developed by the users. application software (24)
1.1.22 [2] Binary digit (value 0 or 1). bit (16)
1.1.23 [2] Software layer between the application software and the hardware that includes the
operating system and the compilers. system software (20)
1.1.24 [2] High-level language used to write application and system software. C (20)
1.1.25 [2] Portable language composed of words and algebraic expressions that must be
translated into assembly language before run in a computer. high-level (22)
1.1.26 [2] 1012 or 240 bytes. terabyte (6)

Exercise 1.3
Consider three different processors P1, P2, and P3 executing the same instruction set with
the clock rates and CPIs given in the following table.
 Processor Clock Rate CPI
a. P1 3 GHz 1.5
P2 2.5 GHz 1.0
P3 4 GHz 2.2
b. P1 2 GHz 1.2
P2 3 GHz 0.8
P3 4 GHz 2.0

1.3.1 [5] <1.4> Which processor has the highest performance expressed in instructions per
second? P2
1.3.2 [10] <1.4> If the processors each execute a program in 10 seconds, find the
number of cycles and the number of instructions.

a. Cycles
P1 = 10 × 3 × 10^9 = 30 × 10^9
P2 = 10 × 2.5 × 10^9 = 25 × 10^9
P3 = 10 × 4 × 10^9 = 40 × 10^9
a. No. instructions
P1 = 30 × 10^9/1.5 = 20 × 10^9
P2 = 25 × 10^9/1 = 25 × 10^9
P3 = 40 × 10^9/2.2 = 18.18 × 10^9
b. Cycles
P1 = 10 × 2 × 10^9 = 20 × 10^9
P2 = 10 × 3 × 10^9 = 30 × 10^9
P3 = 10 × 4 × 10^9 = 40 × 10^9
b. No. instructions
P1 = 20 × 10^9/1.2 = 16.66 × 10^9
P2 = 30 × 10^9/0.8 = 37.5 × 10^9
P3 = 40 × 10^9/2 = 20 × 10^9
1.3.3 [10] <1.4> We are trying to reduce the time by 30% but this leads to an increase of 20% in
the CPI. What clock rate should we have to get this time reduction?

a. Clock rate
P1 = 20 × 10^9 × 1.8 / 7 = 5.14
P2 = 25 × 10^9 × 1.2 / 7 = 4.28
P3 = 18.18 × 10^9 × 2.6 / 7 = 6.7
b. Clock rate
P1 = 16.66 × 10^9 × 1.44/7 = 3.42
P2 = 37.5 × 10^9 × 0.96/7 = 5.14
P3 = 20 × 10^9 × 2.4/7 = 6.85

For problems below, use the information in the following table.

Processor Clock Rate No. Instructions Time

a. P1 3 GHz 20.00E+09 7s
P2 2.5 GHz 30.00E+09 10s
P3 4 GHz 90.00E+09 9s
b. P1 2 GHz 20.00E+09 5s
P2 3 GHz 30.00E+09 8s
P3 4 GHz 25.00E+09 7s

1.3.4 [10] <1.4> Find the IPC (instructions per cycle) for each processor.

a. IPC
P1 = 0.95
P2 = 1.2
P3 = 2.5
b. IPC
P1 = 2
P2 = 1.25
 P3 = 0.89

1.3.5 [5] <1.4> Find the clock rate for P2 that reduces its execution time to that of P1.

a. Clock rate
P2 = 3.57
b. Clock rate
P2 = 4.8

1.3.6 [5] <1.4> Find the number of instructions for P2 that reduces its execution time to that of
P3.

a. No. Instructions
P3 = 27 × 10^9
b. No. Instructions
P3 = 26.25 × 10^9

Exercise 1.4
Consider two different implementations of the same instruction set architecture. There are
four classes of instructions, A, B, C, and D. The clock rate and CPI of each implementation
are given in the following table.

Clock Rate CPI Class A CPI Class B CPI Class C CPI Class D
a. P1 2.5 GHz 1 2 3 3
P2 3 GHz 2 2 2 2
b. P1 2.5 GHz 2 1.5 2 1
P2 3 GHz 1 2 1 1

1.4.1 [10] <1.4> Given a program with 106 instructions divided into classes as follows: 10%
class A, 20% class B, 50% class C, and 20% class D, which implementation is faster?
 a. Time
P1 = (10^5 + 2 * 10^5 * 2 + 5 * 10^5 * 3 + 10^5 * 3) / (2.5 * 10^9) = 10.4 * 10^-4
P2 = (10^5 * 2 + 2 * 10^5 * 2 + 5 * 10^5 * 2 + 2 + 10^5 * 2) / (3 * 10^9) = 6.66 * 10^-4
b. Time
P1 = (10^5 + 2 * 10^5 * 2 + 5 * 10^5 * 2 + 10^5 * 3) / (2.5 * 10^9) = 6.8 * 10^-4
P2 = (10^5 + 2 * 10^5 * 2 + 5 * 10^5 + 2 + 10^5) / (3 * 10^9) = 4 * 10^-4

1.4.2 [5] <1.4> What is the global CPI for each implementation?

a. CPI
P1 = 10.4 * 10^-4 * 2.5 * 10^9 / 10^6 = 2.6
P2 = 6.66 * 10^-4 * 3 * 10^9 / 10^6 = 2.0
b. CPI
P1 = 6.8 * 10^-4 * 2.5 * 10^9 / 10^6 = 1.7
P2 = 4 * 10^-4 * 3 * 10^9 / 10^6 = 1.2

1.4.3 [5] <1.4> Find the clock cycles required in both cases.

a. Clock cycles
P1 = 10^5 * 1 + 2 * 10^5 * 2 + 5 * 10^5 * 3 + 2 * 10^5 * 3 = 26 * 10^5
P2 = 10^5 * 2 + 2 * 10^5 * 2 + 5 * 10^5 * 2 + 2 * 10^5 * 2 = 20 * 10^5
b. Clock cycles
P1 = 17 * 10^5
P2 = 12 * 10^5

The following table shows the number of instructions for a program.

Arith Store Load Branch Total

a. 650 100 600 50 1400
b. 750 250 500 500 2000
1.4.4 [5] <1.4> Assuming that Arith instructions take 1 cycle, load and store 5 cycles, and
branches 2 cycles, what is the execution time of the program in a 2 GHz processor?

a. Execution time
(650 * 1 + 100 * 5 + 600 * 5 + 50 * 2) * 0.5 * 10^-9 = 2125
b. Execution time
(750 * 1 + 250 * 5 + 500 * 5 + 500 * 2) * 0.5 * 10^-9 = 2750

1.4.5 [5] <1.4> Find the CPI for the program.

a. CPI
2125 * 10^-9 * 2 * 10^9 / 1400 = 3.03
b. CPI
1750 * 10^-9 * 2 * 10^9 / 2000 = 2.75

1.4.6 [10] <1.4> If the number of load instructions can be reduced by one half, what is the
speedup and the CPI?

a. Speedup
2125 / 1375 = 1.54
a. CPI
1375 * 10^-9 * 2 * 10^9 / 1100 = 2.5
b. Speedup
2750 / 2125 = 1.29
b. CPI
2125 * 10^-9 * 2 * 10^9 / 1750 = 2.43

Exercise 1.5
Consider two different implementations, P1 and P2, of the same instruction set. There are
five classes of instructions (A, B, C, D, and E) in the instruction set. The clock rate and CPI
of each class is given 2below.
 Clock Rate CPI Class A CPI Class B CPI Class C CPI Class D CPI Class E
a. P1 2.0 GHz 1 2 3 4 3
P2 4.0 GHz 2 2 2 4 4
b. P1 2.0 GHz 1 1 2 3 2
P2 3.0 GHz 1 2 3 4 3

1.5.1 [5] <1.4> Assume that peak performance is defined as the fastest rate that a computer can
execute any instruction sequence. What are the peak performances of P1 and P2 expressed in
instructions per second?

a. Peak performances
P1 = 2 x 10^9
P2 = 2 x 10^9
b. Peak performances
P1 = 2 x 10^9
P2 = 3 x 10^9

1.5.2 [10] <1.4> If the number of instructions executed in a certain program is divided equally
among the classes of instructions except for class A, which occurs twice as often as each of the
others, which computer is faster? How much faster is it?

a. Performance
P2 / P1 = 4 / 7 | P2 is 1.75 times faster
b. Performance
P2 / P1= 4.66 / 5 | P2 is 1.07 times faster

1.5.3 [10] <1.4> If the number of instructions executed in a certain program is divided equally
among the classes of instructions except for class E, which occurs twice as often as each of the
others, which computer is faster? How much faster is it?

a. Performance
 P2 / P1 = 4.5 / 8 | P2 is 1.77 times faster
b. Performance
P2 / P1 = 5.33 / 5.5 | P2 is 1.03 times faster

The table below shows instruction-type breakdown for different programs. Using this data, you
will be exploring the performance trade-offs different changes made to an MIPS processor.

No. Instructions
Compute Load Store Branch Total
a. Program 1 600 600 200 50 1450
b. Program 2 900 500 100 200 1700

1.5.4 [5] <1.4> Assuming that computes take 1 cycle, loads and store instructions take 10 cycles,
and branches take 3 cycles, find the execution time on a 3 GHz MIPS processor.

a. Execution time
2.91
b. Execution time
2.5

1.5.5 [5] <1.4> Assuming that computes take 1 cycle, loads and store instructions take 2 cycles,
and branches take 3 cycles, find the execution time on a 3 GHz MIPS processor.

a. Execution time
0.78
b. Execution time
0.9

1.5.6 [5] <1.4> Assuming that computes take 1 cycle, loads and store instructions take 2 cycles,
and branches take 3 cycles, what is the speedup if the number of compute instruction can be
reduced by one-half?
 b. Speedup
0.68 | 1.14 times faster
c. Speedup
0.75 | 1.2 times faster

Exercise 1.6
Compilers can have a profound impact on the performance of an application on given a
processor. This problem will explore the impact compilers have on execution time.

Compiler A Compiler B
No. Instructions Execution Time No. Instructions Execution Time
a. 1.00E+09 1.8 s 1.20E+09 1.8 s
b. 1.00E+09 1.1 s 1.20E+09 1.5 s

1.6.1 [5] <1.4> For the same program, two different compilers are used. The table above shows
the execution time of the two different compiled programs. Find the average CPI for each
program given that the processor has a clock cycle time of 1 ns.

a. CPI
Compiler A = 1.8
Compiler B = 1.5
b. CPI
Compiler A = 1.1
Compiler B = 1.25

1.6.2 [5] <1.4> Assume the average CPIs found in 1.6.1, but that the compiled programs run on
two different processors. If the execution times on the two processors are the same, how much
faster is the clock of the processor running compiler A’s code versus the clock of the processor
running compiler B’s code?

a. A / B = 1
 b. A / B = 0.73

1.6.3 [5] <1.4> A new compiler is developed that uses only 600 million instructions and has an
average CPI of 1.1. What is the speedup of using this new compiler versus using Compiler A or
B on the original processor of 1.6.1?

a. Speedup
Compiler A = 0.36
Compiler B = 0.36
b. Speedup
Compiler A = 0.6
Compiler B = 0.44

Consider two different implementations, P1 and P2, of the same instruction set. There are five
classes of instructions (A, B, C, D, and E) in the instruction set. P1 has a clock rate of 4 GHz,
and P2 has a clock rate of 6 GHz. The average number of cycles for each instruction class for P1
and P2 are listed in the following table.

CPI Class A CPI Class B CPI Class C CPI Class D CPI Class E
a. P1 1 2 3 4 5
P2 3 3 3 5 5
b. P1 1 2 3 4 5
P2 2 2 2 2 6

1.6.4 [5] <1.4> Assume that peak performance is defined as the fastest rate that a computer can
execute any instruction sequence. What are the peak performances of P1 and P2 expressed in
instructions per second?

a. Peak Performance
P1 = 4 * 10^9
P2 = 2 * 10^9
 b. Peak Performance
P1 = 4 * 10^9
P2 = 3 * 10^9

1.6.5 [5] <1.4> If the number of instructions executed in a certain program is divided equally
among the five classes of instructions except for class A, which occurs twice as often as each of
the others, how much faster is P2 than P1?

a. P1 / P2 = 1.9
b. P1 / P2 = 1.5

1.6.6 [5] <1.4> At what frequency does P1 have the same performance of P2 for the instruction
mix given in 1.6.5?

a. P1 = 4.37
b. P1 = 6