08-17-2017, 12:12 AM
Mesh Algorithms in Parallel Processing
Parallel processing is processing a task with several processing units, or many processors
Most powerful computers contain two or more processing units that share among themselves the jobs submitted for processing
Several operations are performed simultaneously, so the time taken by a computation can be reduced.
A problem to be solved is broken into a no.of subproblems. These subproblems are now solved simultaneously, each on different processors. The results are then combined to produce an answer to the original problem.
To achieve speedup of processing
speedup =ws/wp where ws=worst case running time of fastest known sequential algorithm for the problem and wp= worst case running time of the parallel algorithm for the same problem.
Pipelines have been extensively used in processors to increase the performance
The stream of instruction tells the computer what to do at each step and are divided into four types:
Single Instruction stream, single Data stream (SISD)
Multiple Instruction stream, Single Data stream(MISD)
Single Instruction stream, Multiple Data stream(SIMD)
Multiple Instruction stream, Multiple Data stream(MIMD)
A mesh is an a x b grid in which there is a processor at each grid point.
Each processor of the mesh can be labeled with a tuple (i,j),where 1 i a and 1 j b.
Each processor of the mesh has a RAM with some local memory.
Each processor can perform any of the basic operations such as addition, subtraction, multiplication, comparison, and so on, in one unit of time.
Packet Routing
A single step of interprocessor communication in a fixed connection network is called packet routing.
Each processor in the network has a packet of information that has to be sent to some other processor
The bandwidth of any communication channel is limited, it becomes necessary to impose the restriction that at most one packet pass through the channel at a time.
A packet routing algorithm is judged by its run time, that is, the time taken by the last packet to reach its destination and the maximum number of packets any processor has to store during routing.