Category: Subjects

Mid Point Line Drawing Algorithm

Computer Graphics

Line Drawing Algorithms-

 

In computer graphics, popular algorithms used to generate lines are-

 

 

  1. Digital Differential Analyzer (DDA) Line Drawing Algorithm
  2. Bresenham Line Drawing Algorithm
  3. Mid Point Line Drawing Algorithm

 

In this article, we will discuss about Mid Point Line Drawing Algorithm.

 

Mid Point Line Drawing Algorithm-

 

Given the starting and ending coordinates of a line,

Mid Point Line Drawing Algorithm attempts to generate the points between the starting and ending coordinates.

 

Also Read- DDA Line Drawing Algorithm

 

Procedure-

 

Given-

  • Starting coordinates = (X0, Y0)
  • Ending coordinates = (Xn, Yn)

 

The points generation using Mid Point Line Drawing Algorithm involves the following steps-

 

Step-01:

 

Calculate ΔX and ΔY from the given input.

These parameters are calculated as-

  • ΔX = Xn – X0
  • ΔY =Yn – Y0

 

Step-02:

 

Calculate the value of initial decision parameter and ΔD.

These parameters are calculated as-

  • Dinitial = 2ΔY – ΔX
  • ΔD = 2(ΔY – ΔX)

 

Step-03:

 

The decision whether to increment X or Y coordinate depends upon the flowing values of Dinitial.

Follow the below two cases-

 

 

Step-04:

 

Keep repeating Step-03 until the end point is reached.

For each Dnew value, follow the above cases to find the next coordinates.

 

PRACTICE PROBLEMS BASED ON MID POINT LINE DRAWING ALGORITHM-

 

Problem-01:

 

Calculate the points between the starting coordinates (20, 10) and ending coordinates (30, 18).

 

Solution-

 

Given-

  • Starting coordinates = (X0, Y0) = (20, 10)
  • Ending coordinates = (Xn, Yn) = (30, 18)

 

Step-01:

 

Calculate ΔX and ΔY from the given input.

  • ΔX = Xn – X0 = 30 – 20 = 10
  • ΔY =Yn – Y0 = 18 – 10 = 8

 

Step-02:

 

Calculate Dinitial and ΔD as-

  • Dinitial = 2ΔY – ΔX = 2 x 8 – 10 = 6
  • ΔD = 2(ΔY – ΔX) = 2 x (8 – 10) = -4

 

Step-03:

 

As Dinitial >= 0, so case-02 is satisfied.

 

Thus,

  • Xk+1 = Xk + 1 = 20 + 1 = 21
  • Yk+1 = Yk + 1 = 10 + 1 = 11
  • Dnew = Dinitial + ΔD = 6 + (-4) = 2

 

Similarly, Step-03 is executed until the end point is reached.

 

Dinitial Dnew Xk+1 Yk+1
20 10
6 2 21 11
2 -2 22 12
-2 14 23 12
14 10 24 13
10 6 25 14
6 2 26 15
2 -2 27 16
-2 14 28 16
14 10 29 17
10 30 18

 

 

Problem-02:

 

Calculate the points between the starting coordinates (5, 9) and ending coordinates (12, 16).

 

Solution-

 

Given-

  • Starting coordinates = (X0, Y0) = (5, 9)
  • Ending coordinates = (Xn, Yn) = (12, 16)

 

Step-01:

 

Calculate ΔX and ΔY from the given input.

  • ΔX = Xn – X0 = 12 – 5 = 7
  • ΔY =Yn – Y0 = 16 – 9 = 7

 

Step-02:

 

Calculate Dinitial and ΔD as-

  • Dinitial = 2ΔY – ΔX = 2 x 7 – 7 = 7
  • ΔD = 2(ΔY – ΔX) = 2 x (7 – 7) = 0

 

Step-03:

 

As Dinitial >= 0, so case-02 is satisfied.

 

Thus,

  • Xk+1 = Xk + 1 = 5 + 1 = 6
  • Yk+1 = Yk + 1 = 9 + 1 = 10
  • Dnew = Dinitial + ΔD = 7 + 0 = 7

 

Similarly, Step-03 is executed until the end point is reached.

 

Dinitial Dnew Xk+1 Yk+1
5 9
7 7 6 10
7 7 7 11
7 7 8 12
7 7 9 13
7 7 10 14
7 7 11 15
7 12 16

 

 

Advantages of Mid Point Line Drawing Algorithm-

 

The advantages of Mid Point Line Drawing Algorithm are-

  • Accuracy of finding points is a key feature of this algorithm.
  • It is simple to implement.
  • It uses basic arithmetic operations.
  • It takes less time for computation.
  • The resulted line is smooth as compared to other line drawing algorithms.

 

Also Read- Bresenham Line Drawing Algorithm

 

Disadvantages of Mid Point Line Drawing Algorithm-

 

The disadvantages of Mid Point Line Drawing Algorithm are-

  • This algorithm may not be an ideal choice for complex graphics and images.
  • In terms of accuracy of finding points, improvement is still needed.
  • There is no any remarkable improvement made by this algorithm.

 

To gain better understanding about Mid Point Line Drawing Algorithm,

Watch this Video Lecture

 

Next Article- Mid Point Circle Drawing Algorithm

 

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Bresenham Line Drawing Algorithm

Computer Graphics

Line Drawing Algorithms-

 

In computer graphics, popular algorithms used to generate lines are-

 

 

  1. Digital Differential Analyzer (DDA) Line Drawing Algorithm
  2. Bresenham Line Drawing Algorithm
  3. Mid Point Line Drawing Algorithm

 

In this article, we will discuss about Bresenham Line Drawing Algorithm.

 

Bresenham Line Drawing Algorithm-

 

Given the starting and ending coordinates of a line,

Bresenham Line Drawing Algorithm attempts to generate the points between the starting and ending coordinates.

 

Also Read- DDA Line Drawing Algorithm

 

Procedure-

 

Given-

  • Starting coordinates = (X0, Y0)
  • Ending coordinates = (Xn, Yn)

 

The points generation using Bresenham Line Drawing Algorithm involves the following steps-

 

Step-01:

 

Calculate ΔX and ΔY from the given input.

These parameters are calculated as-

  • ΔX = Xn – X0
  • ΔY =Yn – Y0

 

Step-02:

 

Calculate the decision parameter Pk.

It is calculated as-

Pk = 2ΔY – ΔX

 

Step-03:

 

Suppose the current point is (Xk, Yk) and the next point is (Xk+1, Yk+1).

Find the next point depending on the value of decision parameter Pk.

Follow the below two cases-

 

 

Step-04:

 

Keep repeating Step-03 until the end point is reached or number of iterations equals to (ΔX-1) times.

 

PRACTICE PROBLEMS BASED ON BRESENHAM LINE DRAWING ALGORITHM-

 

Problem-01:

 

Calculate the points between the starting coordinates (9, 18) and ending coordinates (14, 22).

 

Solution-

 

Given-

  • Starting coordinates = (X0, Y0) = (9, 18)
  • Ending coordinates = (Xn, Yn) = (14, 22)

 

Step-01:

 

Calculate ΔX and ΔY from the given input.

  • ΔX = Xn – X0 = 14 – 9 = 5
  • ΔY =Yn – Y0 = 22 – 18 = 4

 

Step-02:

 

Calculate the decision parameter.

Pk

= 2ΔY – ΔX

= 2 x 4 – 5

= 3

So, decision parameter Pk = 3

 

Step-03:

 

As Pk >= 0, so case-02 is satisfied.

 

Thus,

  • Pk+1 = Pk + 2ΔY – 2ΔX = 3 + (2 x 4) – (2 x 5) = 1
  • Xk+1 = Xk + 1 = 9 + 1 = 10
  • Yk+1 = Yk + 1 = 18 + 1 = 19

 

Similarly, Step-03 is executed until the end point is reached or number of iterations equals to 4 times.

(Number of iterations = ΔX – 1 = 5 – 1 = 4)

 

Pk Pk+1 Xk+1 Yk+1
9 18
3 1 10 19
1 -1 11 20
-1 7 12 20
7 5 13 21
5 3 14 22

 

 

Problem-02:

 

Calculate the points between the starting coordinates (20, 10) and ending coordinates (30, 18).

 

Solution-

 

Given-

  • Starting coordinates = (X0, Y0) = (20, 10)
  • Ending coordinates = (Xn, Yn) = (30, 18)

 

Step-01:

 

Calculate ΔX and ΔY from the given input.

  • ΔX = Xn – X0 = 30 – 20 = 10
  • ΔY =Yn – Y0 = 18 – 10 = 8

 

Step-02:

 

Calculate the decision parameter.

Pk

= 2ΔY – ΔX

= 2 x 8 – 10

= 6

So, decision parameter Pk = 6

 

Step-03:

 

As Pk >= 0, so case-02 is satisfied.

 

Thus,

  • Pk+1 = Pk + 2ΔY – 2ΔX = 6 + (2 x 8) – (2 x 10) = 2
  • Xk+1 = Xk + 1 = 20 + 1 = 21
  • Yk+1 = Yk + 1 = 10 + 1 = 11

 

Similarly, Step-03 is executed until the end point is reached or number of iterations equals to 9 times.

(Number of iterations = ΔX – 1 = 10 – 1 = 9)

 

Pk Pk+1 Xk+1 Yk+1
20 10
6 2 21 11
2 -2 22 12
-2 14 23 12
14 10 24 13
10 6 25 14
6 2 26 15
2 -2 27 16
-2 14 28 16
14 10 29 17
10 6 30 18

 

 

Advantages of Bresenham Line Drawing Algorithm-

 

The advantages of Bresenham Line Drawing Algorithm are-

  • It is easy to implement.
  • It is fast and incremental.
  • It executes fast but less faster than DDA Algorithm.
  • The points generated by this algorithm are more accurate than DDA Algorithm.
  • It uses fixed points only.

 

Disadvantages of Bresenham Line Drawing Algorithm-

 

The disadvantages of Bresenham Line Drawing Algorithm are-

  • Though it improves the accuracy of generated points but still the resulted line is not smooth.
  • This algorithm is for the basic line drawing.
  • It can not handle diminishing jaggies.

 

To gain better understanding about Bresenham Line Drawing Algorithm,

Watch this Video Lecture

 

Next Article- Mid Point Line Drawing Algorithm

 

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.

DDA Algorithm | Line Drawing Algorithms

Computer Graphics

Line Drawing Algorithms-

 

In computer graphics, popular algorithms used to generate lines are-

 

 

  1. Digital Differential Analyzer (DDA) Line Drawing Algorithm
  2. Bresenham Line Drawing Algorithm
  3. Mid Point Line Drawing Algorithm

 

In this article, we will discuss about DDA Algorithm.

 

DDA Algorithm-

 

DDA Algorithm is the simplest line drawing algorithm.

 

Given the starting and ending coordinates of a line,

DDA Algorithm attempts to generate the points between the starting and ending coordinates.

 

Procedure-

 

Given-

  • Starting coordinates = (X0, Y0)
  • Ending coordinates = (Xn, Yn)

 

The points generation using DDA Algorithm involves the following steps-

 

Step-01:

 

Calculate ΔX, ΔY and M from the given input.

These parameters are calculated as-

  • ΔX = Xn – X0
  • ΔY =Yn – Y0
  • M = ΔY / ΔX

 

Step-02:

 

Find the number of steps or points in between the starting and ending coordinates.

 

if (absolute (ΔX) > absolute (ΔY))

Steps = absolute (ΔX);

else

Steps = absolute (ΔY);

 

Step-03:

 

Suppose the current point is (Xp, Yp) and the next point is (Xp+1, Yp+1).

Find the next point by following the below three cases-

 

 

Step-04:

 

Keep repeating Step-03 until the end point is reached or the number of generated new points (including the starting and ending points) equals to the steps count.

 

PRACTICE PROBLEMS BASED ON DDA ALGORITHM-

 

Problem-01:

 

Calculate the points between the starting point (5, 6) and ending point (8, 12).

 

Solution-

 

Given-

  • Starting coordinates = (X0, Y0) = (5, 6)
  • Ending coordinates = (Xn, Yn) = (8, 12)

 

Step-01:

 

Calculate ΔX, ΔY and M from the given input.

  • ΔX = Xn – X0 = 8 – 5 = 3
  • ΔY =Yn – Y0 = 12 – 6 = 6
  • M = ΔY / ΔX = 6 / 3 = 2

 

Step-02:

 

Calculate the number of steps.

As |ΔX| < |ΔY| = 3 < 6, so number of steps = ΔY = 6

 

Step-03:

 

As M > 1, so case-03 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

 

Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1)
5 6 5.5 7 (6, 7)
6 8 (6, 8)
6.5 9 (7, 9)
7 10 (7, 10)
7.5 11 (8, 11)
8 12 (8, 12)

 

 

Problem-02:

 

Calculate the points between the starting point (5, 6) and ending point (13, 10).

 

Solution-

 

Given-

  • Starting coordinates = (X0, Y0) = (5, 6)
  • Ending coordinates = (Xn, Yn) = (13, 10)

 

Step-01:

 

Calculate ΔX, ΔY and M from the given input.

  • ΔX = Xn – X0 = 13 – 5 = 8
  • ΔY =Yn – Y0 = 10 – 6 = 4
  • M = ΔY / ΔX = 4 / 8 = 0.50

 

Step-02:

 

Calculate the number of steps.

As |ΔX| > |ΔY| = 8 > 4, so number of steps = ΔX = 8

 

Step-03:

 

As M < 1, so case-01 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

 

Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1)
5 6 6 6.5 (6, 7)
7 7 (7, 7)
8 7.5 (8, 8)
9 8 (9, 8)
10 8.5 (10, 9)
11 9 (11, 9)
12 9.5 (12, 10)
13 10 (13, 10)

 

 

Problem-03:

 

Calculate the points between the starting point (1, 7) and ending point (11, 17).

 

Solution-

 

Given-

  • Starting coordinates = (X0, Y0) = (1, 7)
  • Ending coordinates = (Xn, Yn) = (11, 17)

 

Step-01:

 

Calculate ΔX, ΔY and M from the given input.

  • ΔX = Xn – X0 = 11 – 1 = 10
  • ΔY =Yn – Y0 = 17 – 7 = 10
  • M = ΔY / ΔX = 10 / 10 = 1

 

Step-02:

 

Calculate the number of steps.

As |ΔX| = |ΔY| = 10 = 10, so number of steps = ΔX = ΔY = 10

 

Step-03:

 

As M = 1, so case-02 is satisfied.

Now, Step-03 is executed until Step-04 is satisfied.

 

Xp Yp Xp+1 Yp+1 Round off (Xp+1, Yp+1)
1 7 2 8 (2, 8)
3 9 (3, 9)
4 10 (4, 10)
5 11 (5, 11)
6 12 (6, 12)
7 13 (7, 13)
8 14 (8, 14)
9 15 (9, 15)
10 16 (10, 16)
11 17 (11, 17)

 

 

Advantages of DDA Algorithm-

 

The advantages of DDA Algorithm are-

  • It is a simple algorithm.
  • It is easy to implement.
  • It avoids using the multiplication operation which is costly in terms of time complexity.

 

Disadvantages of DDA Algorithm-

 

The disadvantages of DDA Algorithm are-

  • There is an extra overhead of using round off( ) function.
  • Using round off( ) function increases time complexity of the algorithm.
  • Resulted lines are not smooth because of round off( ) function.
  • The points generated by this algorithm are not accurate.

 

To gain better understanding about DDA Algorithm,

Watch this Video Lecture

 

Next Article- Bresenham Line Drawing Algorithm

 

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.

TCP Congestion Control | Practice Problems

Computer Networks

TCP Congestion Control-

 

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

 

TCP congestion control policy consists of following three phases-

 

 

  1. Slow Start
  2. Congestion Avoidance
  3. Congestion Detection

 

In this article, we will discuss practice problems on TCP Congestion Control.

 

PRACTICE PROBLEMS BASED ON TCP CONGESTION CONTROL-

 

Problem-01:

 

The growth of congestion window takes place-

  1. Infinitely
  2. Up to Threshold
  3. Up to the size of receiver’s window
  4. Up to timeout

 

Solution-

 

Option (C) is correct.

 

Problem-02:

 

Consider the effect of using slow start on a line with a 10 msec RTT and no congestion. The receiver window is 24 KB and the maximum segment size is 2 KB. How long does it take before the first full window can be sent?

 

Solution-

 

Given-

  • Receiver window size = 24 KB
  • Maximum Segment Size = 2 KB
  • RTT = 10 msec

 

Receiver Window Size-

 

Receiver window size in terms of MSS

= Receiver window size / Size of 1 MSS

= 24 KB / 2 KB

= 12 MSS

 

Slow Start Threshold-

 

Slow start Threshold

= Receiver window size / 2

= 12 MSS / 2

= 6 MSS

 

Slow Start Phase-

 

  • Window size at the start of 1st transmission = 1 MSS
  • Window size at the start of 2nd transmission = 2 MSS
  • Window size at the start of 3rd transmission = 4 MSS
  • Window size at the start of 4th transmission = 6 MSS

 

Since the threshold is reached, so it marks the end of slow start phase.

Now, congestion avoidance phase begins.

 

Congestion Avoidance Phase-

 

  • Window size at the start of 5th transmission = 7 MSS
  • Window size at the start of 6th transmission = 8 MSS
  • Window size at the start of 7th transmission = 9 MSS
  • Window size at the start of 8th transmission = 10 MSS
  • Window size at the start of 9th transmission = 11 MSS
  • Window size at the start of 10th transmission = 12 MSS

 

From here,

  • Window size at the end of 9th transmission or at the start of 10th transmission is 12 MSS.
  • Thus, 9 RTT’s will be taken before the first full window can be sent.

 

So,

Time taken before the first full window is sent

= 9 RTT’s

= 9 x 10 msec

= 90 msec

 

Problem-03:

 

Consider an instance of TCP’s Additive Increase Multiplicative Decrease (AIMD) algorithm where the window size at the start of slow start phase is 2 MSS and the threshold at the start of first transmission is 8 MSS. Assume that a time out occurs during the fifth transmission. Find the congestion window size at the end of tenth transmission.

  1. 8 MSS
  2. 14 MSS
  3. 7 MSS
  4. 12 MSS

 

Solution-

 

Given-

  • Window size at the start of slow start phase = 2 MSS
  • Threshold at the start of first transmission = 8 MSS
  • Time out occurs during 5th transmission

 

Slow Start Phase-

 

  • Window size at the start of 1st transmission = 2 MSS
  • Window size at the start of 2nd transmission = 4 MSS
  • Window size at the start of 3rd transmission = 8 MSS

 

Since the threshold is reached, so it marks the end of slow start phase.

Now, congestion avoidance phase begins.

 

Congestion Avoidance Phase-

 

  • Window size at the start of 4th transmission = 9 MSS
  • Window size at the start of 5th transmission = 10 MSS

 

It is given that time out occurs during 5th transmission.

 

TCP reacts by-

  • Setting the slow start threshold to half of the current congestion window size.
  • Decreasing the congestion window size to 2 MSS (Given value is used).
  • Resuming the slow start phase.

 

So now,

  • Slow start threshold = 10 MSS / 2 = 5 MSS
  • Congestion window size = 2 MSS

 

Slow Start Phase-

 

  • Window size at the start of 6th transmission = 2 MSS
  • Window size at the start of 7th transmission = 4 MSS
  • Window size at the start of 8th transmission = 5 MSS

 

Since the threshold is reached, so it marks the end of slow start phase.

Now, congestion avoidance phase begins.

 

Congestion Avoidance Phase-

 

  • Window size at the start of 9th transmission = 6 MSS
  • Window size at the start of 10th transmission = 7 MSS
  • Window size at the start of 11th transmission = 8 MSS

 

From here,

Window size at the end of 10th transmission

= Window size at the start of 11th transmission

= 8 MSS

 

Thus, Option (A) is correct.

 

Problem-04:

 

Suppose that the TCP congestion window is set to 18 KB and a time out occurs. How big will the window be if the next four transmission bursts are all successful? Assume that the MSS is 1 KB.

 

Solution-

 

Congestion Window Size-

 

Congestion window size in terms of MSS

= 18 KB / Size of 1 MSS

= 18 KB / 1 KB

= 18 MSS

 

Reaction Of TCP On Time Out-

 

TCP reacts by-

  • Setting the slow start threshold to half of the current congestion window size.
  • Decreasing the congestion window size to 1 MSS.
  • Resuming the slow start phase.

 

So now,

  • Slow start threshold = 18 MSS / 2 = 9 MSS
  • Congestion window size = 1 MSS

 

Slow Start Phase-

 

  • Window size at the start of 1st transmission = 1 MSS
  • Window size at the start of 2nd transmission = 2 MSS
  • Window size at the start of 3rd transmission = 4 MSS
  • Window size at the start of 4th transmission = 8 MSS
  • Window size at the start of 5th transmission = 9 MSS

 

Thus, after 4 successful transmissions, window size will be 9 MSS or 9 KB.

 

Problem-05:

 

On a TCP connection, current congestion window size is 4 KB. The window advertised by the receiver is 6 KB. The last byte sent by the sender is 10240 and the last byte acknowledged by the receiver is 8192.

 

Part-01:

 

The current window size at the sender is ____.

  1. 2048 B
  2. 4096 B
  3. 6144 B
  4. 8192 B

 

Part-02:

 

The amount of free space in the sender window is ____.

  1. 2048 B
  2. 4096 B
  3. 6144 B
  4. 8192 B

 

Solution-

 

Part-01:

 

Sender window size

= min (Congestion window size, Receiver window size)

= min(4KB , 6KB)

= 4 KB

= 4096 B

Thus, Option (B) is correct.

 

Part-02:

 

Given-

  • Last byte acknowledged by the receiver = 8192
  • Last byte sent by the sender = 10240

 

From here,

  • It means bytes from 8193 to 10240 are still present in the sender’s window.
  • These bytes are waiting for their acknowledgement.
  • Total bytes present in sender’s window = 10240 – 8193 + 1 = 2048 bytes.

 

From here,

Amount of free space in sender’s window currently

= 4096 bytes – 2048 bytes

= 2048 bytes

 

This indicates that half of the sender’s window is currently empty.

Thus, Option (A) is correct.

 

Next Article- TCP Timers

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Memory Organization in Computer Architecture

Computer Organization and Architecture

Memory Organization in Computer Architecture-

 

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

 

In a computer,

  • Memory is organized at different levels.
  • CPU may try to access different levels of memory in different ways.
  • On this basis, the memory organization is broadly divided into two types-

 

 

  1. Simultaneous Access Memory Organization
  2. Hierarchical Access Memory Organization

 

1. Simultaneous Access Memory Organization-

 

In this memory organization,

  • All the levels of memory are directly connected to the CPU.
  • Whenever CPU requires any word, it starts searching for it in all the levels simultaneously.

 

Example-01:

 

Consider the following simultaneous access memory organization-

 

 

Here, two levels of memory are directly connected to the CPU.

 

Let-

  • T1 = Access time of level L1
  • S1 = Size of level L1
  • C1 = Cost per byte of level L1
  • H1 = Hit rate of level L1

Similar are the notations for level L2.

 

Average Memory Access Time-

 

Average time required to access memory per operation

= H1 x T1 + (1 – H1) x H2 x T2

= H1 x T1 + (1 – H1) x 1 x T2

= H1 x T1 + (1 – H1) x T2

 

Important Note

In any memory organization,

  • The data item being searched will definitely be present in the last level.
  • Thus, hit rate for the last level is always 1.

 

Average Cost Per Byte-

 

Average cost per byte of the memory

= { C1 x S1 + C2 x S2 } / { S1 + S2 }

 

Example-02:

 

Consider the following simultaneous access memory organization-

 

 

Here, three levels of memory are directly connected to the CPU.

 

Let-

  • T1 = Access time of level L1
  • S1 = Size of level L1
  • C1 = Cost per byte of level L1
  • H1 = Hit rate of level L1

Similar are the notations for other two levels.

 

Average Memory Access Time-

 

Average time required to access memory per operation

= H1 x T1 + (1 – H1) x H2 x T2 + (1 – H1) x (1 – H2) x H3 x T3

= H1 x T1 + (1 – H1) x H2 x T2 + (1 – H1) x (1 – H2) x 1 x T3

= H1 x T1 + (1 – H1) x H2 x T2 + (1 – H1) x (1 – H2) x T3

 

Average Cost Per Byte-

 

Average cost per byte of the memory

= { C1 x S1 + C2 x S2 + C3 x S3 } / { S1 + S2 + S3 }

 

2. Hierarchical Access Memory Organization-

 

In this memory organization, memory levels are organized as-

  • Level-1 is directly connected to the CPU.
  • Level-2 is directly connected to level-1.
  • Level-3 is directly connected to level-2 and so on.

 

Whenever CPU requires any word,

  • It first searches for the word in level-1.
  • If the required word is not found in level-1, it searches for the word in level-2.
  • If the required word is not found in level-2, it searches for the word in level-3 and so on.

 

Example-01:

 

Consider the following hierarchical access memory organization-

 

 

Here, two levels of memory are connected to the CPU in a hierarchical fashion.

 

Let-

  • T1 = Access time of level L1
  • S1 = Size of level L1
  • C1 = Cost per byte of level L1
  • H1 = Hit rate of level L1

Similar are the notations for level L2.

 

Average Memory Access Time-

 

Average time required to access memory per operation

= H1 x T1 + (1 – H1) x H2 x (T1 + T2)

= H1 x T1 + (1 – H1) x 1 x (T1 + T2)

= H1 x T1 + (1 – H1) x (T1 + T2)

 

Average Cost Per Byte-

 

Average cost per byte of the memory

= { C1 x S1 + C2 x S2 } / { S1 + S2 }

 

Example-02:

 

Consider the following hierarchical access memory organization-

 

 

Here, three levels of memory are connected to the CPU in a hierarchical fashion.

 

Let-

  • T1 = Access time of level L1
  • S1 = Size of level L1
  • C1 = Cost per byte of level L1
  • H1 = Hit rate of level L1

Similar are the notations for other two levels.

 

Average Memory Access Time-

 

Average time required to access memory per operation

= H1 x T1 + (1 – H1) x H2 x (T1 + T2) + (1 – H1) x (1 – H2) x H3 x (T1 + T2 + T3)

= H1 x T1 + (1 – H1) x H2 x (T1 + T2) + (1 – H1) x (1 – H2) x 1 x (T1 + T2 + T3)

= H1 x T1 + (1 – H1) x H2 x (T1 + T2) + (1 – H1) x (1 – H2) x (T1 + T2 + T3)

 

Average Cost Per Byte-

 

Average cost per byte of the memory

= { C1 x S1 + C2 x S2 + C3 x S3 } / { S1 + S2 + S3 }

 

PRACTICE PROBLEMS BASED ON MEMORY ORGANIZATION-

 

Problem-01:

 

What is the average memory access time for a machine with a cache hit rate of 80% and cache access time of 5 ns and main memory access time of 100 ns when-

  1. Simultaneous access memory organization is used.
  2. Hierarchical access memory organization is used.

 

Solution-

 

Part-01: Simultaneous Access Memory Organization-

 

The memory organization will be as shown-

 

 

Average memory access time

= H1 x T1 + (1 – H1) x H2 x T2

= 0.8 x 5 ns + (1 – 0.8) x 1 x 100 ns

= 4 ns + 0.2 x 100 ns

= 4 ns + 20 ns

= 24 ns

 

Part-02: Hierarchical Access Memory Organization-

 

The memory organization will be as shown-

 

 

Average memory access time

= H1 x T1 + (1 – H1) x H2 x (T1 + T2)

= 0.8 x 5 ns + (1 – 0.8) x 1 x (5 ns + 100 ns)

= 4 ns + 0.2 x 105 ns

= 4 ns + 21 ns

= 25 ns

 

Problem-02:

 

A computer has a cache, main memory and a disk used for virtual memory. An access to the cache takes 10 ns. An access to main memory takes 100 ns. An access to the disk takes 10,000 ns. Suppose the cache hit ratio is 0.9 and the main memory hit ratio is 0.8. The effective access time required to access a referenced word on the system is _______ when-

  1. Simultaneous access memory organization is used.
  2. Hierarchical access memory organization is used.

 

Solution-

 

Part-01:Simultaneous Access Memory Organization-

 

The memory organization will be as shown-

 

 

Effective memory access time

= H1 x T1 + (1 – H1) x H2 x T2 + (1 – H1) x (1 – H2) x H3 x T3

= 0.9 x 10 ns + (1 – 0.9) x 0.8 x 100 ns + (1 – 0.9) x (1 – 0.8) x 1 x 10000 ns

= 9 ns + 8 ns + 200 ns

= 217 ns

 

Part-02: Hierarchical Access Memory Organization-

 

The memory organization will be as shown-

 

 

Effective memory access time

= H1 x T1 + (1 – H1) x H2 x (T1 + T2) + (1 – H1) x (1 – H2) x H3 x (T1 + T2 + T3)

= 0.9 x 10 ns + (1 – 0.9) x 0.8 x (10 ns + 100 ns) + (1 – 0.9) x (1 – 0.8) x 1 x (10 ns + 100 ns + 10000 ns)

= 9 ns + 8.8 ns + 202.2 ns

= 220 ns

 

Important Note

While solving numerical problems

If the kind of memory organization used is not mentioned, assume hierarchical access memory organization.

 

To gain better understanding about Memory Organization,

Watch this Video Lecture

 

Next Article- Cache Memory

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.