A parallel algorithm is an algorithm that can execute several instructions simultaneously on different processing devices and then combine all the individual outputs to produce the final result.
while designing a parallel algorithm, proper CPU utilization should be considered to get an efficient algorithm.
Depending on the instruction stream and data stream, computers can be classified into four categories:
- Single Instruction stream, Single Data stream (SISD) computers
- Single Instruction stream, Multiple Data stream (SIMD) computers
- Multiple Instruction stream, Single Data stream (MISD) computers
- Multiple Instruction stream, Multiple Data stream (MIMD) computers
Analysis of an algorithm helps us determine whether the algorithm is useful or not. Generally, an algorithm is analyzed based on its execution time (Time Complexity) and the amount of space (Space Complexity) it requires.
-
Data parallel model
-
Task graph model
-
Work pool model
-
Master slave model
-
Producer consumer or pipeline model
-
Hybrid model
-
Parallel Random Access Machines (PRAM)
-
memory access unit (MAU)
-
SolarisTM threads for Solaris
-
POSIX threadsin Linux
-
Win32 threads Windows NT and Windows 2000
-
JavaTM threads as part of the standard JavaTM Development Kit (JDK).
-
Message Passing Libraries
-
Message Passing Interface (MPI)
-
Parallel Virtual Machine (PVM)
-
Linked List
- Singly Linked List
- Doubly Linked List
- Circular Linked List
-
Arrays
-
Hypercube Network