Parallel Algorithm Structure - Parallel Algorithm

What is the structure of Parallel Algorithm?

A proper data structure need to be selected for properly applying the algorithm. This is because the time taken for the performance of a particular operation on different data structures is different.

Example – By using an array, the ith element in a set can be accessed consuming a constant time. The time becomes polynomial if a linked list is used for performing the same operation.

Parallel Algorithms use the following types of data structures -

  • Linked List
  • Arrays
  • Hypercube Network

Linked List

A data structure with zero or more nodes connected by pointers is known as a linked list. The memory location is not occupied by the nodes. Node consists of three parts – data part which stores the data and the other two are the link fields, where the address of the previous or next node is stored. An external pointer called head stores the address of the first node. The last node, tail does not contain any address.

Linked lists are of three types -

  • Singly Linked List
  • Doubly Linked List
  • Circular Linked List

Singly Linked List

The data and the address of the next node is present in the singly linked list. The address of the first node is stored in the external pointer called head.

Singly Linked List

Doubly Linked List

The data and address of both the previous and next node is present in doubly linked list. The address of the first node is stored in the external pointer called head and the address of the last node is stored in the external pointer called tail.

Doubly Linked List

Circular Linked List

Similar to that of singly linked list, in circular linked list, the address of the first node is saved in the last node.

Circular Linked List

Arrays

A data structure where similar type of data is stored in known as an array. An array can be one-dimensional or multi-dimensional. Arrays are created either statically or dynamically.

  • In statically declared arrays, at compilation time, the dimension and size of the array are known
  • In dynamically declared arrays, at run time, the dimension and size of the array are known.

Arrays are used as common memory for shared memory programming and they are partitioned into sub-arrays and are used for parallel programming.

Hypercube Network

In parallel algorithms, each task communicates with other task by using hypercube architecture. The topologies such as ring and mesh can easily be embedded by the hypercube topology. Hypercube topology is known as n-cubes, where n stands for number of dimensions.

Hypercube

Hypercube

Parallel Algorithm Related Tutorials

Parallel Algorithm Related Practice Tests


All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Parallel Algorithm Topics