Category: Subjects

How Digital Signature Works | Algorithm

Digital Signatures-

 

  • The signature on a document is the proof to the receiver that the document is coming from the correct entity.
  • A digital signature guarantees the authenticity of an electronic document in digital communication.

 

How Digital Signature Works?

 

  • The sender of the document digitally signs the document.
  • The receiver of the document verifies the signature.

 

The steps involved in the digital signature algorithm are-

 

At Sender Side-

 

At sender side,

  • Using a hash function, sender converts the message to be sent into a digested form.
  • There are various hash functions that may be used like SHA-1, MD5 etc.
  • The message in digested form is called as message digest.
  • Sender encrypts the message digest using his private key.
  • The encrypted message digest is called as signed digest or signature of the sender.
  • Sender sends the signed digest along with the original message to the receiver.

 

 

At Receiver Side-

 

At receiver side,

  • Receiver receives the original message and the signed digest.
  • Using a hash function, receiver converts the original message into a message digest.
  • Also, receiver decrypts the received signed digest using the sender’s public key.
  • On decryption, receiver obtains the message digest.
  • Now, receiver compares both the message digests.
  • If they are same, then it is proved that the document is coming from the correct entity.

 

 

Also Read- RSA Algorithm

 

Important Points-

 

Point-01:

 

After digitally signing the document, sender sends the following two things to the receiver-

  • Signed digest or signature
  • Original message

 

Point-02:

 

  • Sender uses his private key to digitally sign the document.
  • Receiver uses the sender’s public key to verify the signature.

 

Point-03:

 

  • Digital signature of a person varies from document to document.
  • This ensures authenticity of the document.

 

Point-04:

 

In digital signature,

  • There is one to one relationship between a message and a signature.
  • Each message has its own signature.

 

Point-05:

 

Digital signature verifies-

  • Authenticity
  • Integrity
  • Non-repudiation

 

Also Read- Diffie Hellman Key Exchange Algorithm

 

PRACTICE PROBLEMS BASED ON DIGITAL SIGNATURES-

 

Problem-01:

 

Anarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim requires-

  1. Anarkali’s public key
  2. Salim’s public key
  3. Salim’s private key
  4. Anarkali’s private key

 

Solution-

 

Clearly, Option (A) is correct.

 

Problem-02:

 

Consider that B wants to send a message m that is digitally signed to A. Let the pair of private and public keys for A and B be denoted by Kx and Kx+ for x = A, B respectively. Let Kx(m) represent the operation of encrypting m with a key Kx and H(m) represent the message digest. Which one of the following indicates the correct way of sending the message m along with the digital signature to A?

  1. {m, KB+(H(m))}
  2. {m, KB(H(m))}
  3. {m, KA(H(m))}
  4. {m, KA+(H(m))}

 

Solution-

 

Clearly, Option (B) is correct.

 

To gain better understanding about Digital Signatures,

Watch this Video Lecture

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Diffie Hellman Key Exchange | Asymmetric Encryption

Asymmetric Encryption-

 

Before you go through this article, make sure that you have gone through the previous article on Asymmetric Key Cryptography.

 

In asymmetric encryption,

  • Sender and receiver use different keys to encrypt and decrypt the message.
  • The famous asymmetric encryption algorithms are-

 

 

In this article, we will discuss about Diffie Hellman Key Exchange Algorithm.

 

Symmetric Key Cryptography-

 

In symmetric key cryptography,

  • Both sender and receiver use a common secret key to encrypt and decrypt the message.
  • The major issue is exchanging the secret key between the sender and the receiver.
  • Attackers might intrude and know the secret key while exchanging it.

 

Read More- Symmetric Key Cryptography

 

Diffie Hellman Key Exchange-

 

As the name suggests,

  • This algorithm is used to exchange the secret key between the sender and the receiver.
  • This algorithm facilitates the exchange of secret key without actually transmitting it.

 

Diffie Hellman Key Exchange Algorithm-

 

Let-

  • Private key of the sender = Xs
  • Public key of the sender = Ys
  • Private key of the receiver = Xr
  • Public key of the receiver = Yr

 

Using Diffie Hellman Algorithm, the key is exchanged in the following steps-

 

Step-01:

 

  • One of the parties choose two numbers ‘a’ and ‘n’ and exchange with the other party.
  • ‘a’ is the primitive root of prime number ‘n’.
  • After this exchange, both the parties know the value of ‘a’ and ‘n’.

 

Step-02:

 

  • Both the parties already know their own private key.
  • Both the parties calculate the value of their public key and exchange with each other.

 

Sender calculate its public key as-

Ys = aXs mod n

Receiver calculate its public key as-

Yr = aXr mod n

 

Step-03:

 

  • Both the parties receive public key of each other.
  • Now, both the parties calculate the value of secret key.

 

Sender calculates secret key as-

Secret key = (Yr)Xs mod n

Receiver calculates secret key as-

Secret key = (Ys)Xr mod n

 

Finally, both the parties obtain the same value of secret key.

 

PRACTICE PROBLEMS BASED ON DIFFIE HELLMAN KEY EXCHANGE-

 

Problem-01:

 

Suppose that two parties A and B wish to set up a common secret key (D-H key) between themselves using the Diffie Hellman key exchange technique. They agree on 7 as the modulus and 3 as the primitive root. Party A chooses 2 and party B chooses 5 as their respective secrets. Their D-H key is-

  1. 3
  2. 4
  3. 5
  4. 6

 

Solution-

 

Given-

  • n = 7
  • a = 3
  • Private key of A = 2
  • Private key of B = 5

 

Step-01:

 

Both the parties calculate the value of their public key and exchange with each other.

 

Public key of A

= 3private key of A mod 7

= 32 mod 7

= 2

 

Public key of B

= 3private key of B mod 7

= 35 mod 7

= 5

 

Step-02:

 

Both the parties calculate the value of secret key at their respective side.

 

Secret key obtained by A

= 5private key of A mod 7

= 52 mod 7

= 4

 

Secret key obtained by B

= 2private key of B mod 7

= 25 mod 7

= 4

 

Finally, both the parties obtain the same value of secret key.

The value of common secret key = 4.

Thus, Option (B) is correct.

 

Problem-02:

 

In a Diffie-Hellman Key Exchange, Alice and Bob have chosen prime value q = 17 and primitive root = 5. If Alice’s secret key is 4 and Bob’s secret key is 6, what is the secret key they exchanged?

  1. 16
  2. 17
  3. 18
  4. 19

 

Solution-

 

Given-

  • n = 17
  • a = 5
  • Private key of Alice = 4
  • Private key of Bob = 6

 

Step-01:

 

Both Alice and Bob calculate the value of their public key and exchange with each other.

 

Public key of Alice

= 5private key of Alice mod 17

= 54 mod 17

= 13

 

Public key of Bob

= 5private key of Bob mod 17

= 56 mod 17

= 2

 

Step-02:

 

Both the parties calculate the value of secret key at their respective side.

 

Secret key obtained by Alice

= 2private key of Alice mod 7

= 24 mod 17

= 16

 

Secret key obtained by Bob

= 13private key of Bob mod 7

= 136 mod 17

= 16

 

Finally, both the parties obtain the same value of secret key.

The value of common secret key = 16.

Thus, Option (A) is correct.

 

To gain better understanding about Diffie Hellman Key Exchange Algorithm,

Watch this Video Lecture

 

Next Article- Digital Signatures

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Public Key Cryptography | RSA Algorithm Example

Cryptography in Network Security-

 

Before you go through this article, make sure that you have gone through the previous article on Cryptography.

 

We have discussed-

  • Cryptography is a method of storing and transmitting data in a particular form.
  • Cryptography techniques are-

 

 

In this article, we will discuss about Asymmetric Key Cryptography.

 

Asymmetric Key Cryptography-

 

In this technique,

  • Sender and receiver use different keys to encrypt and decrypt the message.
  • It is called so because sender and receiver use different keys.
  • It is also called as public key cryptography.

 

Working-

 

The message exchange using public key cryptography involves the following steps-

 

 

Step-01:

 

At sender side,

  • Sender encrypts the message using receiver’s public key.
  • The public key of receiver is publicly available and known to everyone.
  • Encryption converts the message into a cipher text.
  • This cipher text can be decrypted only using the receiver’s private key.

 

Step-02:

 

  • The cipher text is sent to the receiver over the communication channel.

 

Step-03:

 

At receiver side,

  • Receiver decrypts the cipher text using his private key.
  • The private key of the receiver is known only to the receiver.
  • Using the public key, it is not possible for anyone to determine the receiver’s private key.
  • After decryption, cipher text converts back into a readable format.

 

Advantages-

 

The advantages of public key cryptography are-

  • It is more robust.
  • It is less susceptible to third-party security breach attempts.

 

Disadvantages-

 

The disadvantages of public key cryptography are-

  • It involves high computational requirements.
  • It is slower than symmetric key cryptography.

 

Number of Keys Required-

 

To use public key cryptography,

  • Each individual requires two keys- one public key and one private key.
  • For n individuals to communicate, number of keys required = 2 x n = 2n keys.

 

Asymmetric Encryption Algorithms-

 

The famous asymmetric encryption algorithms are-

 

 

  1. RSA Algorithm
  2. Diffie-Hellman Key Exchange

 

In this article, we will discuss about RSA Algorithm.

 

RSA Algorithm-

 

Let-

  • Public key of the receiver = (e , n)
  • Private key of the receiver = (d , n)

 

Then, RSA Algorithm works in the following steps-

 

Step-01:

 

At sender side,

  • Sender represents the message to be sent as an integer between 0 and n-1.
  • Sender encrypts the message using the public key of receiver.
  • It raises the plain text message ‘P’ to the eth power modulo n.
  • This converts the message into cipher text ‘C’.

 

C = Pe mod n

 

Step-02:

 

  • The cipher text ‘C’ is sent to the receiver over the communication channel.

 

Step-03:

 

At receiver side,

  • Receiver decrypts the cipher text using his private key.
  • It raises the cipher text ‘C’ to the dth power modulo n.
  • This converts the cipher text back into the plain text ‘P’.

 

P = Cd mod n

 

NOTE-

 

‘e’ and ‘d’ must be multiplicative inverses modulo Ø(n)

 

After decryption, receiver must have-

P = Cd mod n

P = (Pe mod n)d mod n

P = Ped mod n

For this equation to be true, by Euler’s Theorem, we must have-

ed = 1 mod Ø(n)

OR

ed = kØ(n) + 1

Thus, e and d must be multiplicative inverses modulo Ø(n).

 

Steps to Generate Public Key And Private Key-

 

An individual can generate his public key and private key using the following steps-

 

Step-01:

 

Choose any two prime numbers p and q such that-

  • They are different.
  • They are very large.

 

Step-02:

 

Calculate ‘n’ and toilent function Ø(n) where-

  • n = p x q
  • Ø(n) = (p-1) x (q-1)

 

Step-03:

 

Choose any value of ‘e’ such that-

  • 1 < e < Ø(n)
  • gcd (e, Ø(n)) = 1

 

Step-04:

 

Determine ‘d’ such that-

 

 

  • You already know the value of ‘e’ and Ø(n).
  • Choose the least positive integer value of ‘k’ which gives the integer value of ‘d’ as a result.
  • Use trial and error method.
  • Start substituting different values of ‘k’ from 0.

 

PRACTICE PROBLEMS BASED ON RSA ALGORITHM-

 

Problem-01:

 

In a RSA cryptosystem, a participant A uses two prime numbers p = 13 and q = 17 to generate her public and private keys. If the public key of A is 35, then the private key of A is _______.

 

Solution-

 

Given-

  • Prime numbers p = 13 and q = 17
  • Public key = 35

 

Step-01:

 

Calculate ‘n’ and toilent function Ø(n).

 

Value of n,

n = p x q

n = 13 x 17

∴ n = 221

 

Toilent function,

Ø(n) = (p-1) x (q-1)

Ø(n) = (13-1) x (17-1)

∴ Ø(n) = 192

 

Step-02:

 

  • We are already given the value of e = 35.
  • Thus, public key = (e , n) = (35 , 221)

 

Step-03:

 

Determine ‘d’ such that-

 

 

Here,

  • The least value of ‘k’ which gives the integer value of ‘d’ is k = 2.
  • On substituting k = 2, we get d = 11.

 

Thus, private key of participant A = (d , n) = (11, 221).

 

Problem-02:

 

In the RSA public key cryptosystem, the private and public keys are (e, n) and (d, n) respectively, where n = p x q and p and q are large primes. Besides, n is public and p and q are private. Let M be an integer such that 0 < M < n and f(n) = (p-1)(q-1).

 

Now consider the following equations-

I. M’ = Me mod n and M = (M’)d mod n

II. ed ≡ 1 mod n

III. ed = 1 mod f(n)

IV. M’ = Me mod f(n) and M = (M’)d mod f(n)

 

Which of the above equations correctly represent RSA cryptosystem?

  1. I and II
  2. I and III
  3. II and IV
  4. III and IV

 

Solution-

 

Clearly, Option (B) is correct.

 

To gain better understanding about RSA Algorithm,

Watch this Video Lecture

 

Next Article- Diffie Hellman Key Exchange Algorithm

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Symmetric Key Cryptography | Cryptography Techniques

Cryptography in Network Security-

 

In network security,

  • Cryptography is a method of storing and transmitting data in a particular form.
  • It ensures that only the person for whom the message is intended can read the message.

 

The message exchange using cryptography involves the following steps-

 

 

Step-01:

 

At sender side,

  • Using an encryption algorithm, the message is converted into an unreadable form.
  • The message in unreadable form is called as cipher text.

 

Step-02:

 

  • The cipher text is sent to the receiver over the communication channel.
  • Since the message is encrypted, the attackers can not read the message.

 

Step-03:

 

At receiver side,

  • Using a decryption algorithm, the message is again converted into the readable form.
  • Then, receiver can read the message.

 

Cryptography Techniques-

 

Cryptography techniques may be classified as-

 

 

  1. Symmetric Key Cryptography
  2. Asymmetric Key Cryptography

 

In this article, we will discuss about symmetric key cryptography.

 

Symmetric Key Cryptography-

 

In this technique,

  • Both sender and receiver uses a common key to encrypt and decrypt the message.
  • This secret key is known only to the sender and to the receiver.
  • It is also called as secret key cryptography.

 

Working-

 

The message exchange using symmetric key cryptography involves the following steps-

 

 

 

  • Before starting the communication, sender and receiver shares the secret key.
  • This secret key is shared through some external means.
  • At sender side, sender encrypts the message using his copy of the key.
  • The cipher text is then sent to the receiver over the communication channel.
  • At receiver side, receiver decrypts the cipher text using his copy of the key.
  • After decryption, the message converts back into readable format.

 

Symmetric Encryption Algorithms-

 

Some of the encryption algorithms that use symmetric key are-

  • Advanced Encryption Standard (AES)
  • Data Encryption Standard (DES)

 

Advantages-

 

The advantages of symmetric key algorithms are-

  • They are efficient.
  • They take less time to encrypt and decrypt the message.

 

Disadvantages-

 

Point-01:

 

The number of keys required is very large.

 

In symmetric key cryptography,

  • Each pair of users require a unique secret key.
  • If N people in the world wants to use this technique, then there needs to be N(N-1) / 2 secret keys.
  • For 1 million people to communicate, a half billion secret keys would be needed.

 

How N(N-1)/2 Keys Will Be Required?

 

  • Consider a complete graph with N nodes.
  • Consider each node represents one person.
  • Then, each person will require (N-1) keys to communicate with other (N-1) people.
  • Thus, each edge must have a unique key for communication.
  • Thus, Number of keys required = Number of edges = nC2 = n(n-1)/2.

 

Point-02:

 

  • Sharing the secret key between the sender and receiver is an important issue.
  • While sharing the key, attackers might intrude.

 

To overcome this disadvantage,

Diffie Hellman Key Exchange Algorithm is used for exchanging the secret key.

 

Important Points-

 

Point-01:

 

In symmetric key cryptography,

  • Both sender and receiver uses the same key.
  • Sender encrypts the message using his copy of the key.
  • Receiver decrypts the message using his copy of the key.
  • The key must not be known to anyone else other than sender and receiver.
  • If the secret key is known to any intruder, he could decrypt the message.

 

Point-02:

 

  • This cryptography technique is called as symmetric key cryptography.
  • It is because both sender and receiver use the same key on their sides.

 

Point-03:

 

  • This cryptography technique is called as secret key cryptography.
  • It is because the key has to be kept secret between the sender and receiver.

 

To gain better understanding about Symmetric Key Cryptography,

Watch this Video Lecture

 

Next Article- Asymmetric Key Cryptography | RSA Algorithm

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Pipelining | Practice Problems

Pipelining in Computer Architecture-

 

Before you go through this article, make sure that you have gone through the previous article on Instruction Pipelining.

 

In instruction pipelining,

  • A form of parallelism called as instruction level parallelism is implemented.
  • Multiple instructions execute simultaneously.
  • Speed up, Efficiency and Throughput serve as performance measures of pipelined execution.

 

Also Read- Performance Criteria Of Pipelining

 

In this article, we will discuss practice problems based on pipelining.

 

PRACTICE PROBLEMS BASED ON PIPELINING IN COMPUTER ARCHITECTURE-

 

Problem-01:

 

Consider a pipeline having 4 phases with duration 60, 50, 90 and 80 ns. Given latch delay is 10 ns. Calculate-

  1. Pipeline cycle time
  2. Non-pipeline execution time
  3. Speed up ratio
  4. Pipeline time for 1000 tasks
  5. Sequential time for 1000 tasks
  6. Throughput

 

Solution-

 

Given-

  • Four stage pipeline is used
  • Delay of stages = 60, 50, 90 and 80 ns
  • Latch delay or delay due to each register = 10 ns

 

Part-01: Pipeline Cycle Time-

 

Cycle time

= Maximum delay due to any stage + Delay due to its register

= Max { 60, 50, 90, 80 } + 10 ns

= 90 ns + 10 ns

= 100 ns

 

Part-02: Non-Pipeline Execution Time-

 

Non-pipeline execution time for one instruction

= 60 ns + 50 ns + 90 ns + 80 ns

= 280 ns

 

Part-03: Speed Up Ratio-

 

Speed up

= Non-pipeline execution time / Pipeline execution time

= 280 ns / Cycle time

= 280 ns / 100 ns

= 2.8

 

Part-04: Pipeline Time For 1000 Tasks-

 

Pipeline time for 1000 tasks

= Time taken for 1st task + Time taken for remaining 999 tasks

= 1 x 4 clock cycles + 999 x 1 clock cycle

= 4 x cycle time + 999 x cycle time

= 4 x 100 ns + 999 x 100 ns

= 400 ns + 99900 ns

= 100300 ns

 

Part-05: Sequential Time For 1000 Tasks-

 

Non-pipeline time for 1000 tasks

= 1000 x Time taken for one task

= 1000 x 280 ns

= 280000 ns

 

Part-06: Throughput-

 

Throughput for pipelined execution

= Number of instructions executed per unit time

= 1000 tasks / 100300 ns

 

Problem-02:

 

A four stage pipeline has the stage delays as 150, 120, 160 and 140 ns respectively. Registers are used between the stages and have a delay of 5 ns each. Assuming constant clocking rate, the total time taken to process 1000 data items on the pipeline will be-

  1. 120.4 microseconds
  2. 160.5 microseconds
  3. 165.5 microseconds
  4. 590.0 microseconds

 

Solution-

 

Given-

  • Four stage pipeline is used
  • Delay of stages = 150, 120, 160 and 140 ns
  • Delay due to each register = 5 ns
  • 1000 data items or instructions are processed

 

Cycle Time-

 

Cycle time

= Maximum delay due to any stage + Delay due to its register

= Max { 150, 120, 160, 140 } + 5 ns

= 160 ns + 5 ns

= 165 ns

 

Pipeline Time To Process 1000 Data Items-

 

Pipeline time to process 1000 data items

= Time taken for 1st data item + Time taken for remaining 999 data items

= 1 x 4 clock cycles + 999 x 1 clock cycle

= 4 x cycle time + 999 x cycle time

= 4 x 165 ns + 999 x 165 ns

= 660 ns + 164835 ns

= 165495 ns

= 165.5 μs

Thus, Option (C) is correct.

 

Problem-03:

 

Consider a non-pipelined processor with a clock rate of 2.5 gigahertz and average cycles per instruction of 4. The same processor is upgraded to a pipelined processor with five stages but due to the internal pipeline delay, the clock speed is reduced to 2 gigahertz. Assume there are no stalls in the pipeline. The speed up achieved in this pipelined processor is-

  1. 3.2
  2. 3.0
  3. 2.2
  4. 2.0

 

Solution-

 

Cycle Time in Non-Pipelined Processor-

 

Frequency of the clock = 2.5 gigahertz

Cycle time

= 1 / frequency

= 1 / (2.5 gigahertz)

= 1 / (2.5 x 109 hertz)

= 0.4 ns

 

Non-Pipeline Execution Time-

 

Non-pipeline execution time to process 1 instruction

= Number of clock cycles taken to execute one instruction

= 4 clock cycles

= 4 x 0.4 ns

= 1.6 ns

 

Cycle Time in Pipelined Processor-

 

Frequency of the clock = 2 gigahertz

Cycle time

= 1 / frequency

= 1 / (2 gigahertz)

= 1 / (2 x 109 hertz)

= 0.5 ns

 

Pipeline Execution Time-

 

Since there are no stalls in the pipeline, so ideally one instruction is executed per clock cycle. So,

Pipeline execution time

= 1 clock cycle

= 0.5 ns

 

Speed Up-

 

Speed up

= Non-pipeline execution time / Pipeline execution time

= 1.6 ns / 0.5 ns

= 3.2

Thus, Option (A) is correct.

 

Problem-04:

 

The stage delays in a 4 stage pipeline are 800, 500, 400 and 300 picoseconds. The first stage is replaced with a functionally equivalent design involving two stages with respective delays 600 and 350 picoseconds.

The throughput increase of the pipeline is _____%.

 

Solution-

 

Execution Time in 4 Stage Pipeline-

 

Cycle time

= Maximum delay due to any stage + Delay due to its register

= Max { 800, 500, 400, 300 } + 0

= 800 picoseconds

Thus, Execution time in 4 stage pipeline = 1 clock cycle = 800 picoseconds.

 

Throughput in 4 Stage Pipeline-

 

Throughput

= Number of instructions executed per unit time

= 1 instruction / 800 picoseconds

 

Execution Time in 2 Stage Pipeline-

 

Cycle time

= Maximum delay due to any stage + Delay due to its register

= Max { 600, 350 } + 0

= 600 picoseconds

Thus, Execution time in 2 stage pipeline = 1 clock cycle = 600 picoseconds.

 

Throughput in 2 Stage Pipeline-

 

Throughput

= Number of instructions executed per unit time

= 1 instruction / 600 picoseconds

 

Throughput Increase-

 

Throughput increase

= { (Final throughput – Initial throughput) / Initial throughput } x 100

= { (1 / 600 – 1 / 800) / (1 / 800) } x 100

= { (800 / 600) – 1 } x 100

= (1.33 – 1) x 100

= 0.3333 x 100

= 33.33 %

 

Problem-05:

 

A non-pipelined single cycle processor operating at 100 MHz is converted into a synchronous pipelined processor with five stages requiring 2.5 ns, 1.5 ns, 2 ns, 1.5 ns and 2.5 ns respectively. The delay of the latches is 0.5 sec.

The speed up of the pipeline processor for a large number of instructions is-

  1. 4.5
  2. 4.0
  3. 3.33
  4. 3.0

 

Solution-

 

Cycle Time in Non-Pipelined Processor-

 

Frequency of the clock = 100 MHz

Cycle time

= 1 / frequency

= 1 / (100 MHz)

= 1 / (100 x 106 hertz)

= 0.01 μs

 

Non-Pipeline Execution Time-

 

Non-pipeline execution time to process 1 instruction

= Number of clock cycles taken to execute one instruction

= 1 clock cycle

= 0.01 μs

= 10 ns

 

Cycle Time in Pipelined Processor-

 

Cycle time

= Maximum delay due to any stage + Delay due to its register

= Max { 2.5, 1.5, 2, 1.5, 2.5 } + 0.5 ns

= 2.5 ns + 0.5 ns

= 3 ns

 

Pipeline Execution Time-

 

Pipeline execution time

= 1 clock cycle

= 3 ns

 

Speed Up-

 

Speed up

= Non-pipeline execution time / Pipeline execution time

= 10 ns / 3 ns

= 3.33

Thus, Option (C) is correct.

 

Problem-06:

 

We have 2 designs D1 and D2 for a synchronous pipeline processor. D1 has 5 stage pipeline with execution time of 3 ns, 2 ns, 4 ns, 2 ns and 3 ns. While the design D2 has 8 pipeline stages each with 2 ns execution time. How much time can be saved using design D2 over design D1 for executing 100 instructions?

  1. 214 ns
  2. 202 ns
  3. 86 ns
  4. 200 ns

 

Solution-

 

Cycle Time in Design D1-

 

Cycle time

= Maximum delay due to any stage + Delay due to its register

= Max { 3, 2, 4, 2, 3 } + 0

= 4 ns

 

Execution Time For 100 Instructions in Design D1-

 

Execution time for 100 instructions

= Time taken for 1st instruction + Time taken for remaining 99 instructions

= 1 x 5 clock cycles + 99 x 1 clock cycle

= 5 x cycle time + 99 x cycle time

= 5 x 4 ns + 99 x 4 ns

= 20 ns + 396 ns

= 416 ns

 

Cycle Time in Design D2-

 

Cycle time

= Delay due to a stage + Delay due to its register

= 2 ns + 0

= 2 ns

 

Execution Time For 100 Instructions in Design D2-

 

Execution time for 100 instructions

= Time taken for 1st instruction + Time taken for remaining 99 instructions

= 1 x 8 clock cycles + 99 x 1 clock cycle

= 8 x cycle time + 99 x cycle time

= 8 x 2 ns + 99 x 2 ns

= 16 ns + 198 ns

= 214 ns

 

Time Saved-

 

Time saved

= Execution time in design D1 – Execution time in design D2

= 416 ns – 214 ns

= 202 ns

Thus, Option (B) is correct.

 

Problem-07:

 

Consider an instruction pipeline with four stages (S1, S2, S3 and S4) each with combinational circuit only. The pipeline registers are required between each stage and at the end of the last stage. Delays for the stages and for the pipeline registers are as given in the figure-

 

 

What is the approximate speed up of the pipeline in steady state under ideal conditions when compared to the corresponding non-pipeline implementation?

  1. 4.0
  2. 2.5
  3. 1.1
  4. 3.0

 

Solution-

 

Non-Pipeline Execution Time-

 

Non-pipeline execution time for 1 instruction

= 5 ns + 6 ns + 11 ns + 8 ns

= 30 ns

 

Cycle Time in Pipelined Processor-

 

Cycle time

= Maximum delay due to any stage + Delay due to its register

= Max { 5, 6, 11, 8 } + 1 ns

= 11 ns + 1 ns

= 12 ns

 

Pipeline Execution Time-

 

Pipeline execution time

= 1 clock cycle

= 12 ns

 

Speed Up-

 

Speed up

= Non-pipeline execution time / Pipeline execution time

= 30 ns / 12 ns

= 2.5

Thus, Option (B) is correct.

 

Problem-08:

 

Consider a 4 stage pipeline processor. The number of cycles needed by the four instructions I1, I2, I3 and I4 in stages S1, S2, S3 and S4 is shown below-

 

S1 S2 S3 S4
I1 2 1 1 1
I2 1 3 2 2
I3 2 1 1 3
I4 1 2 2 2

 

 

What is the number of cycles needed to execute the following loop?

for(i=1 to 2) { I1; I2; I3; I4; }

  1. 16
  2. 23
  3. 28
  4. 30

 

Solution-

 

The phase-time diagram is-

 

 

From here, number of clock cycles required to execute the loop = 23 clock cycles.

Thus, Option (B) is correct.

 

Problem-09:

 

Consider a pipelined processor with the following four stages-

IF : Instruction Fetch

ID : Instruction Decode and Operand Fetch

EX : Execute

WB : Write Back

 

The IF, ID and WB stages take one clock cycle each to complete the operation. The number of clock cycles for the EX stage depends on the instruction. The ADD and SUB instructions need 1 clock cycle and the MUL instruction need 3 clock cycles in the EX stage. Operand forwarding is used in the pipelined processor. What is the number of clock cycles taken to complete the following sequence of instructions?

 

ADD R2, R1, R0      R2 ← R0 + R1

MUL R4, R3, R2      R4 ← R3 + R2

SUB R6, R5, R4      R6 ← R5 + R4

 

  1. 7
  2. 8
  3. 10
  4. 14

 

Solution-

 

The phase-time diagram is-

 

 

From here, number of clock cycles required to execute the instructions = 8 clock cycles.

Thus, Option (B) is correct.

 

Problem-10:

 

Consider the following procedures. Assume that the pipeline registers have zero latency.

P1 : 4 stage pipeline with stage latencies 1 ns, 2 ns, 2 ns, 1 ns

P2 : 4 stage pipeline with stage latencies 1 ns, 1.5 ns, 1.5 ns, 1.5 ns

P3 : 5 stage pipeline with stage latencies 0.5 ns, 1 ns, 1 ns, 0.6 ns, 1 ns

P4 : 5 stage pipeline with stage latencies 0.5 ns, 0.5 ns, 1 ns, 1 ns, 1.1 ns

 

Which procedure has the highest peak clock frequency?

  1. P1
  2. P2
  3. P3
  4. P4

 

Solution-

 

It is given that pipeline registers have zero latency. Thus,

Cycle time

= Maximum delay due to any stage + Delay due to its register

= Maximum delay due to any stage

 

For Processor P1:

 

Cycle time

= Max { 1 ns, 2 ns, 2 ns, 1 ns }

= 2 ns

 

Clock frequency

= 1 / Cycle time

= 1 / 2 ns

= 0.5 gigahertz

 

For Processor P2:

 

Cycle time

= Max { 1 ns, 1.5 ns, 1.5 ns, 1.5 ns }

= 1.5 ns

 

Clock frequency

= 1 / Cycle time

= 1 / 1.5 ns

= 0.67 gigahertz

 

For Processor P3:

 

Cycle time

= Max { 0.5 ns, 1 ns, 1 ns, 0.6 ns, 1 ns }

= 1 ns

 

Clock frequency

= 1 / Cycle time

= 1 / 1 ns

= 1 gigahertz

 

For Processor P4:

 

Cycle time

= Max { 0.5 ns, 0.5 ns, 1 ns, 1 ns, 1.1 ns }

= 1.1 ns

 

Clock frequency

= 1 / Cycle time

= 1 / 1.1 ns

= 0.91 gigahertz

 

Clearly, Process P3 has the highest peak clock frequency.

Thus, Option (C) is correct.

 

Problem-11:

 

Consider a 3 GHz (gigahertz) processor with a three-stage pipeline and stage latencies T1, T2 and T3 such that T1 = 3T2/4 = 2T3. If the longest pipeline stage is split into two pipeline stages of equal latency, the new frequency is ____ GHz, ignoring delays in the pipeline registers.

 

Solution-

 

Let ‘t’ be the common multiple of each ratio, then-

  • T1 = t
  • T2 = 4t / 3
  • T3 = t / 2

 

Pipeline Cycle Time-

 

Pipeline cycle time

= Maximum delay due to any stage + Delay due to its register

= Max { t, 4t/3, t/2 } + 0

= 4t/3

 

Frequency Of Pipeline-

 

Frequency

= 1 / Pipeline cycle time

= 1 / (4t / 3)

= 3 / 4t

 

Given frequency = 3 GHz. So,

3 / 4t = 3 GHz

4t = 1 ns

t = 0.25 ns

 

Stage Latencies Of Pipeline-

 

Stage latency of different stages are-

  • Latency of stage-01 = 0.25 ns
  • Latency of stage-02 = 0.33 ns
  • Latency of stage-03 = 0.125 ns

 

Splitting The Pipeline-

 

The stage with longest latency i.e. stage-02 is split up into 4 stages.

After splitting, the latency of different stages are-

  • Latency of stage-01 = 0.25 ns
  • Latency of stage-02 = 0.165 ns
  • Latency of stage-03 = 0.165 ns
  • Latency of stage-04 = 0.125 ns

 

Splitted Pipeline Cycle Time-

 

Splitted pipeline cycle time

= Maximum delay due to any stage + Delay due to its register

= Max { 0.25, 0.165, 0.165, 0.125 } + 0

= 0.25 ns

 

Frequency Of Splitted Pipeline-

 

Frequency

= 1 / splitted pipeline cycle time

= 1 / 0.25 ns

= 4 GHz

Thus, new frequency = 4 GHz.

 

Get more notes and other study material of Computer Organization and Architecture.

Watch video lectures by visiting our YouTube channel LearnVidFun.