Forem: Mohammadhu Faalil

Will Von Neumann Architecture be diminished in the future?

Mohammadhu Faalil — Wed, 02 Jun 2021 14:13:30 +0000

Introduction
Computer architecture has undergone incredible changes in the past 20 years. One element that has remained constant throughout the years, is the von Neumann concept of computer design. It has been used in computers since it was published.

Von Neumann Architecture.
Von Neumann architecture was first published by John Von Neumann in 1945. His computer architecture design consists of a Control Unit, Arithmetic and Logical Unit (ALU), Memory unit, Registers and Inputs/Outputs. The basic structure of the Von Neumann Architecture is shown in the Figure below.

According to Von Neumann Architecture, CPU consists of two units, Control Unit and Arithmetic Logic Unit. The underlying principle of Von Neumann Architecture is that data and instructions are treated in the same manner which means that both data and instructions are addressable. It operates using for simple steps:- Fetch, Decode, Execute, Store, called the Machine Cycle as shown in the diagram.

Instructions are fetched from the memory by the CPU. The CPU then decodes and executes the instructions and once it is completed it is stored back in the memory.

Von Neumann Bottleneck.
Under this architecture, memory for instructions and data are unified and shared with one data bus and one address bus between processor and memory. Instructions and data have to be fetched in sequential order, known as the Von Neumann Bottleneck which limits the bandwidth of memory access. The processor is idle for a certain amount of time while memory is accessed. Though numerous solutions have been proposed and implemented in modern day including cache memory and branch predictor algorithms, these solutions have not been able to solve the root of the problem rather it had made the architecture more complex.

Has the world started to move away from the Von Neumann Architecture?
In the modern world, Harvard Architecture has become a challenge for the Von Neumann Architecture. Harvard architecture is a type of computer architecture that separates its memory into two parts so that data and instructions are stored separately. This architecture also has separate buses to transfer data and fetch data. This allows the CPU to fetch data and instructions simultaneously.
Further, IBM researches introduced a new non Von Neumann Architecture called the True North Architecture inspired by the functions of the human brain. Here, it uses a memory controller like a neuron, with no CPU, to work on synaptic-like data sets in memory with no shuffling around whatsoever by virtue of harnessing the crystallization dynamic of phase-change memories .
In addition to these, many other alternative architectures have come up in the world of today.

Conclusion
It is obvious working with Von Neumann Architecture is not suitable to work in the future and it will be diminished in the near future. Some companies have already started to work with the alternative architectures, and the rest of the world would most probably switch to the alternative architectures as the traditional Von Neumann Architecture will be unable to cater the needs of the future computers.

Automation in agricultural equipment and technology.

Mohammadhu Faalil — Wed, 05 May 2021 13:42:53 +0000

The agriculture industry in the modern era is developing by leaps and bounds. The rise in the global population has caused an increase in food demands which in turn incurs farming produce price increase, reconsidering trade policies, shifting supply chains, and reshaping traditional food delivery routes. Despite these challenges, the amount of agricultural workers is steadily declining. Therefore the farmers are facing a critical juncture between wanting to produce more, higher-quality crops and finding the workers to plant, maintain, and harvest those crops. The necessity arose to focus on using technology to produce more food in order to meet the demand and the concept “Smart Farming” came into place which makes farm more efficient and automates the crop production cycle.

In the modern world there are numerous technologies that are commonly being utilized in agriculture. The advent of Agricultural robots simply called as agribots was a turning point in the field of agriculture that has resulted in producing more and higher quality foods with less manpower.

Traditional tractors have been replaced by automated tractors which can be controlled remotely or even pre-programmed to give full autonomy to a producer. Bear Flag Robotics specializes in building driverless tractors which provides significant savings in labour and input costs. They have the ability to control several tractors remotely, plan the machine’s route, get real-time reports and alerts – the work can be done without direct human intervention in the field.

Moreover, robots developed for seeding and weeding are focused on the field’s specific area, and they work with great precision. This type of farming robot uses artificial intelligence and computer vision, which allows for a reduction of pesticides in the field and, subsequently, the production of high-quality food.

Historically, the harvesting of crops by automated means is something unimaginable due to the delicate nature of fresh fruits and vegetables. But in the modern days it has changed. The commercial company Abundant has developed an apple picking robot which uses a vacuum instead of graspers or similar devices.

In addition to robots, drones too play a major role in the automation of agriculture. Drone devices can identify damaged crops via imagery and infrared analysis. Farmers receive this information immediately and can quickly react to the changing conditions. Also they can be used to water plants in the fields. The company DroneSeed have developed drones to plant from air in the aim of reforesting lands after wildfires. These types of drones carries a module that “shoots” seeds at the set place and specific distance from each other. To make it possible, developers use compressed air – this way, seeds will not scatter around the field.

The benefits of automating traditional agriculture processes are monumental. Increase of productivity through automation has increased the yield as well as the rate of production which in turn has reduced the costs for customers. The routines tasks being automated using robots has reduced the labour cost as well as addressed the issue of labour shortage in the field of agriculture. Besides these, automation has decreased the usage of pesticide and fertilizer while also reducing greenhouse gas emissions.

There are still certain factors that stop automation of agriculture from gaining momentum. The higher prices of the automated agricultural equipment and lack of technological knowledge stands as a great barrier for this adaptation. Besides, lack of infrastructure and internet connection in certain remote rural areas should not be forgotten. Steps has to be taken by the relevant authorities of the country to provide a helping hand to the farmers in order to fully utilize farm automation.

Automation in agricultural equipment using the technological advancements has paved the way towards sustainable and more efficient agriculture.

Bubble Sort

Mohammadhu Faalil — Sun, 31 Jan 2021 13:30:27 +0000

Bubble sort is the simplest sorting algorithm that sorts the array by repeatedly swapping the consecutive pair of adjacent elements if they are not sorted.

The Algorithm for Bubble Sort is as follows :

Bubble Sort (A,N)
1.Repeat Step 2 for I=0 to N-1
2.  Repeat for J=0 to N-I
3.    If A[J] > A[J+1]
4.    SWAP A[J] and A[J+1]
5.  [END OF INNER LOOP]
6.[END OF OUTER LOOP]

Let's have a pictorial representation of how bubble sort will sort a given array.

So we see once the first iteration has ended, the largest element has taken its correct place and after second iteration the second largest element will take up its sorted place and it will continue.

It's time to write the code.

   void bubbleSort(int arr[],int n)
    {
     int i, j,temp;

        for(i = 0; i < n-1; i++)
        {
            for (j = 0; j < n-i-1; j++)
            {
                if (arr[j] > arr[j+1])
                 temp=arr[j];
                 arr[j]=arr[j+1];
                 arr[j+1]=temp;
            }
        }           
    }

Consider an array of 6 elements is sorted using the bubble sort algorithm. Even if the array is sorted after second or third iteration, the loop will continue until the 6th iteration. This is merely a waste of time. So, the computer scientists have found out a way to optimize this algorithm by using another variable swapped which will check whether a swapping takes place in the inner for loop. If there are no swapping inside the inner loops, it means array is already sorted and we can jump out of the for loop instead of executing all the iterations.

The optimized implementation of bubble sort algorithm is as follows :

void bubbleSort(int arr[],int n)
        {
         int i, j,temp;
         int swapped=0;

            for(i = 0; i < n-1; i++)
            {
                for (j = 0; j < n-i-1; j++)
                {
                    if (arr[j] > arr[j+1])
                    {
                     temp=arr[j];
                     arr[j]=arr[j+1];
                     arr[j+1]=temp;
                     // if swapping occurs update swapped to 1
                     swapped =1
                     }
                }
                //If the value of swapped is 0 after all the iterations of the inner loop
                //then break out
                if(swapped==0)
                {
                    break;
                }

            }           
        }

Complexity Analysis of Bubble Sort
In bubble sort we have seen there are N-1 comparisons in first pass, N-2 in second pass and so on. Therefore, to compute the complexity of bubble sort, we need to calculate the number of comparisons. It can be shown as follows.

f(n) = (n – 1) + (n – 2) + (n – 3) + ..... + 3 + 2 + 1
f(n) = n (n – 1)/2
f(n) = n^2/2 + O(n) = O(n^2)

The time complexity of the bubble sort algorithm can be summarized as,

Worst Case Time Complexity [ Big-O ]: O(n^2)
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n^2)

The main advantage of the Bubble sort algorithm is the simplicity of the algorithm.

By going through the above blog post, I am pretty sure that you have gained a sound knowledge on Bubble Sort Algorithm. If you have any queries or need more clarifications, feel free to drop in comments.
Thank You.

Insertion Sort

Mohammadhu Faalil — Wed, 30 Dec 2020 13:30:17 +0000

Insertion Sort is an in place comparison based sorting algorithm, which is commonly used in Computer Science. This algorithm is just similar to the way we sort a deck of cards while playing bridge. The main idea behind insertion list is that it inserts each item into its proper place in the final sorted array.

How does Insertion Sort Work ?

The array of values to be sorted is divided into two parts. One stores the sorted values while the other consists of the unsorted values.
This algorithm continues until the unsorted part is empty.
Assume there are n elements in the array. Initially the first element is in the sorted part while the rest in the unsorted part.
During each iteration, the first element in the unsorted part is picked and inserted into the correct position in the sorted array.

The way in which a given array is arranged using Selection Sort Algorithm is depicted in the following diagram.

Pseudo Code for Selection Sort

INSERTION-SORT(A)
   for i = 1 to n
    key ← A [i]
        j ← i – 1
     while j > = 0 and A[j] > key
        A[j+1] ← A[j]
        j ← j – 1
    End while 
    A[j+1] ← key
  End for

Implementation of Selection Sort in C

void Insertion_Sort ( int A[ ] , int n) 
{
     for( int i = 0 ;i < n ; i++ ) {
    //storing current element whose left side is checked for its correct position //

      int key = A[ i ];    
      int j = i;

       /* check whether the adjacent element in left side is greater or
            less than the current element. */

          while(  j > 0  && key < A[ j -1]) {

           // moving the left side element to one position forward.
                A[ j ] = A[ j-1];   
                j= j - 1;

           }
         // moving current element to its  correct position.
           A[ j ] = key;       
     }  
}

Complexity of Insertion Sort

Time Complexities

Best Case Complexity : O (n)
This occurs when the array is already sorted. The outer loops runs n number of times while the inner loop does not run at all. Therefore, there are only n number of comparisons such that complexity is linear.
Worst Case Complexity : O (n^2)
The worst case occurs when the elements in the array are in the reversed order. Here, the first element of the unsorted part has to be compared with every elements in the sorted part. Therefore it has a quadratic running time.
Average Case Complexity : O(n^2)
It occurs when the elements in the array is in neither ascending nor descending order.

Space Complexity
Space Complexity is O(1) as an extra variable key is used.

Advantages of Insertion Sort

It requires less memory space (only O(1) of additional memory space)
It is easy to implement.
It is efficient to use on small sets of data.

By reading the above blog post, I hope you would have gained a sound knowledge on Insertion Sort.

Selection Sort

Mohammadhu Faalil — Wed, 25 Nov 2020 13:30:05 +0000

Sorting refers to the operation or technique of arranging and rearranging sets of data in some specific order in order to make it easy for us to use those data. There are many sorting algorithms used to put the elements of a list in a certain order, which can be either numerical order or any user defined order. Some of the widely used sorting algorithms are :

Selection Sort
Insertion Sort
Bubble Sort
Merge Sort

Here, I will be discussing about the Selection Sort Algorithm.

Selection Sort is a simple sorting algorithm which can be easily understood even by a beginner. In Selection Sort, an array is divided into two parts as :

The sorted part at the right end.
The unsorted part at the left end.

Firstly, the sorted part is empty while the entire list takes the unsorted part. The minimum element in the unsorted part is found and swapped with leftmost element in unsorted part. And then onwards that element becomes part of the sorted array. With time, the sorted part expands and the unsorted part shrinks. Finally, when the unsorted part becomes empty, we have achieved the sorted array.
The way how an array is sorted in Selection Sort Algorithm is given in the image below.

A Pseudo Code for Selection Sort

1. for i=1 to i=n-1
2. min=i
3. for j=i+1 to j=n
4.  if A[j]<A[min], then
5.    min=j
6. end for
7. if min≠i then , interchange A[i] and A[min]
8. end for

Implementation of Selection Sort in C

//arr is the name of the array to be sorted
// n is the size of the array

void SelectionSort(int arr[], int n) 
{ 
    int i, j, min; 

    for (i = 0; i < n-1; i++) 
    { 
        // Find the minimum element in the unsorted part of the array
        min = i; 
        for (j = i+1; j < n; j++) 
          if (arr[j] < arr[min]) 
            min = j; 

        // Swap the found minimum element with the first element of the unsorted array
            int temp = arr[i];  
            arr[i] = arr[min];  
            arr[min] = temp; 
    } 
}

Complexity of Selection Sort

In first pass, finding the element with the smallest value calls for scanning all n elements; thus, n–1 comparisons are required in the first pass. Then, the smallest value is swapped with the
element in the first position. In Pass 2, finding the second smallest value requires scanning the remaining n – 1 elements and so on. Therefore,

(n – 1) + (n – 2) + ... + 2 + 1
= n(n – 1) / 2 = O(n2)

So, we can see the time complexity of Selection Sort is the same irrespective of the original order of the elements in the given array.
When we see the space complexity, it is 0(1) as an extra variable temp is used.

Advantages of Selection Sort

It is very simple and easy to implement.
It can be used to sort very small data sets.

To sum up, Selection Sort is a simple sorting algorithm that is easy to understand and the knowledge on Selection Sort algorithm will help us to have a strong introduction into learning other sorting algorithms.