Parallel Algorithm : Concepts & Types

/ कंप्यूटर फंडामेंटल्स / 7 minutes of reading

Parallel Algorithms

Parallel Algorithm वह Algorithm होता है, जिसमें किसी बड़ी problem को कई छोटे-छोटे sub-problems में divide किया जाता है और उन सभी sub-problems को एक साथ (simultaneously) multiple processors / multiple cores की Help से execute किया जाता है।

Parallel Algorithm का main goal होता है

  • execution time कम करना और
  • system performance बढ़ाना।

सरल शब्दों में :

जब एक ही समय पर कई tasks computer द्वारा किए जाते हैं, तो उसे Parallel Algorithm कहा जाता है।

Key Points (मुख्य बिंदु)

  • Parallel Algorithm में multiple processors / cores एक साथ काम करते हैं।
  • Problem को divide करके अलग-अलग हिस्सों में बाँटा जाता है।
  • Execution simultaneous होती है, sequential नहीं।
  • Time complexity कम होती है और speed बढ़ती है।
  • Multi-core CPU और GPU का सही उपयोग होता है।
  • Big data और large-scale problems के लिए ज्यादा useful होता है।
  • AI, Machine Learning, Weather Forecasting, Banking systems में widely used होता है।
  • Parallel Algorithm design करना complex हो सकता है।
  • Synchronization और communication की आवश्यकता पड़ती है।

Why Do We Need Parallel Algorithms?
(Parallel Algorithms की आवश्यकता क्यों है?)

मुख्य कारण (Key Reasons)

1. High Speed Execution

  • Parallel Algorithm में कई tasks एक साथ execute होते हैं।
  • इससे total execution time कम हो जाता है।

2. Large Data Processing

  • Big Data, Artificial Intelligence (AI) और Machine Learning (ML) में huge amount of data होता है।
  • Sequential Algorithm इतना data efficiently handle नहीं कर पाता।

3. Better Utilization of Multi-Core Processors

  • Modern computers में multi-core CPU और GPU होते हैं।
  • Parallel Algorithms इन cores का maximum utilization करते हैं।

4. Time-Critical Applications

  • कुछ applications में delay acceptable नहीं होता।
  •  Example :
    • Online banking & UPI transactions
    • Stock market trading systems
    • Air traffic control systems

5. Scalability

  • Users या data बढ़ने पर system easily scale हो जाता है।
  • Performance पर ज्यादा असर नहीं पड़ता।

6. Solving Complex Scientific Problems

  • कुछ scientific problems बहुत complex और computation-heavy होते हैं, जैसे :
    • Weather forecasting
    • Space research (ISRO missions)
    • Climate modeling
  • इन problems को solve करने के लिए Parallel Computing mandatory है।

7. Foundation of Modern Technologies

  • आज की modern technologies की backbone Parallel Algorithms हैं, जैसे :
    • Artificial Intelligence (AI)
    • Machine Learning (ML)
    • Cloud Computing
    • Supercomputers

Basic Concepts of Parallel Algorithms (सिद्धांत)

1. Parallelism

  •  Parallelism का अर्थ है, एक से ज़्यादा operations को एक ही समय पर execute करना।
    • Multiple tasks simultaneously run होते हैं
    • Speed और performance increase होती है

2. Concurrency 

  • Concurrency का अर्थ है, कि Multiple tasks एक ही समय के period में progress कर रहे हों, आवश्यक नहीं कि exactly same moment पर।
    • Parallelism = physically together
    • Concurrency = logically together

3. Processor / Core

  • Processor computer का brain होता है
  • Modern CPU में multiple cores (Dual-core, Quad-core) होते हैं |

4. Task Decomposition

  • Problem को छोटे-छोटे sub-tasks में divide करना।
  • Example :
    • Online shopping
    • Payment
    • Order confirmation
    • Delivery update
  • सब tasks parallel execute होते हैं।

5. Data Decomposition 

  • Same task को अलग-अलग data parts पर perform करना।
  • Example : Array के elements को different processors पर process करना

6. Communication 

  • Processors को आपस में data exchange करना पड़ता है।
  • Shared Memory
  • Message Passing

7. Synchronization 

  • Processors को proper order में coordinate करना।
  • Example : Railway signal system, One process waits for another

Types of Parallel Algorithms (प्रकार)

1. Data Parallel Algorithms 

इस प्रकार में same operation को different data sets पर simultaneously perform किया जाता है।

Key Points :

  • Operation एक ही रहता है
  • Data अलग-अलग processors पर divide होता है

Example :

  • Array के सभी elements का square निकालना
  • Image processing (हर pixel पर same operation)

2. Task Parallel Algorithms 

इसमें different tasks को parallel execute किया जाता है।

Key Points :

  • Tasks अलग-अलग होते हैं
  • Data same या different हो सकता है
  • Control-based parallelism

Example :

  • एक processor sorting कर रहा है
  • दूसरा searching

3. Pipeline Parallel Algorithms 

Pipeline Parallelism में tasks को stages में divide किया जाता है, और stages conveyor-belt style parallel में execute होती हैं।

Key Points :

  • Sequential stages
  • Execution overlapping
  • Throughput increase होता है

Example :

  • CPU instruction pipeline
  • Assembly line in factory

4. Divide and Conquer Parallel Algorithms

Problem को छोटे sub-problems में divide करके उन्हें parallel solve किया जाता है।

Key Points :

  • Recursive approach
  • Independent sub-problems
  • Result combine किया जाता है

Example :

  • Merge Sort
  • Quick Sort

5. SIMD Parallel Algorithms (Single Instruction Multiple Data)

एक ही instruction को multiple data items पर apply किया जाता है।

Key Points :

  • Hardware level parallelism
  • Vector processing

Example :

  • Graphics rendering
  • Matrix multiplication

6. MIMD Parallel Algorithms (Multiple Instruction Multiple Data)

अलग-अलग instructions और अलग-अलग data streams parallel execute होते हैं।

Key Points :

  • Most flexible
  • Used in distributed systems

Example :

  • Cloud computing
  • Supercomputers

Models of Parallel Computation (मॉडल)

1. PRAM Model (Parallel Random Access Machine)

PRAM (Parallel Random Access Machine) एक ऐसा computational model है, जिसमें multiple processors एक साथ काम करते हैं, और सभी processors को एक shared global memory तक equal access time मिलता है।

Types of PRAM Model

  1. EREW PRAM (Exclusive Read Exclusive Write) : एक memory location को एक समय में सिर्फ एक processor read और write कर सकता है।
    •  Used For :
      • Sorting algorithms
      • Basic parallel problems
  2. CREW PRAM (Concurrent Read Exclusive Write) : Multiple processors एक ही memory location को एक साथ read कर सकते हैं, लेकिन write operation exclusive होता है।
    • Used For :
      • Searching algorithms
      • Graph problems
  3. CRCW PRAM (Concurrent Read Concurrent Write) : Multiple processors एक memory location को simultaneously read और write कर सकते हैं। 
    • Used For :
      • Matrix multiplication
      • Advanced parallel algorithms

2. Shared Memory Model

Shared Memory Model वह parallel computation model है, जिसमें सभी processors एक common shared memory को access करते हैं, और communication memory read/write के माध्यम से होता है।

 Example :

  • Multi-core CPU
  • Thread-based programming (Java Threads, OpenMP)

3. Distributed Memory Model 

Distributed Memory Model वह model है जिसमें हर processor की अपनी private local memory होती है और processors आपस में message passing के माध्यम communicate करते हैं।

 Example:

  • Cluster computing
  • Supercomputers
  • Cloud computing

4. Hybrid Model 

Hybrid Model shared memory और distributed memory model का combination होता है।

Example :

  • Multi-core clusters
  • Cloud data centers

5. BSP Model (Bulk Synchronous Parallel Model)

BSP Model एक parallel computation model है, जिसमें computation को supersteps (phases) में divide किया जाता है।

Example :

  • Graph algorithms
  • Big data processing

Design Techniques for Parallel Algorithms (विधियाँ)

1. Divide and Conquer Technique

Problem को छोटे-छोटे independent sub-problems में divide किया जाता है, उन्हें parallel solve किया जाता है और अंत में result combine किया जाता है।

Examples : Merge Sort, Quick Sort

2. Data Decomposition 

Same operation को different data sets पर parallel perform किया जाता है।

Example :

  • Array elements को different processors में divide करना
  • Matrix multiplication

3. Task Decomposition 

Problem को अलग-अलग tasks में divide किया जाता है और हर task parallel execute होता है।

Example :

  • One processor → Sorting
  • Another processor → Searching

4. Pipeline Technique 

Computation को stages में divide किया जाता है और stages overlap होकर execute होती हैं।

Example

  • CPU instruction pipeline
  • Assembly line

Advantages of Parallel Algorithms (लाभ)

1. High Speed Execution

  • Parallel Algorithm में multiple tasks एक साथ execute होते हैं।
  • इससे total execution time काफी कम हो जाता है।

2. Better Utilization of Resources

  • Modern systems में multi-core CPU और GPU होते हैं।
  • Parallel Algorithm इन resources का maximum utilization करता है, जिससे idle time कम हो जाता है।

3. Large Problem Handling

  • यह big data और complex problems को efficiently handle करता है।

4. Scalability 

  • जैसे processors की संख्या बढ़ती है, वैसे system performance भी improve होती है।

5. Essential for Modern Technologies

  • Parallel Algorithm आज की modern technologies की basic requirement है:
    • Artificial Intelligence (AI)
    • Machine Learning (ML)
    • Big Data Analytics
    • Cloud Computing

6. Energy and Time Efficient (Large Scale Tasks)

  • Large-scale problems के लिए time कम लगता है
  • energy consumption भी कम होता है

Limitations of Parallel Algorithms (सीमाएँ)

 1. Complex Design

  • Parallel algorithm को design करना difficult होता है।
  • इसके अलावा debugging और testing भी आसान नहीं होती।

2. High Hardware Cost

  • Parallel computing के लिए multiple processors, GPU, high-speed network की आवश्यकता होती है, जिससे cost बढ़ जाती है।

3. Synchronization Overhead

  • Tasks को synchronize करने के लिए locks, barriers, signals का use होता है। इससे extra delay आता है और performance reduce हो सकती है।

4. Communication Cost

  • Processors के बीच data transfer में time लगता है।
  • अगर communication ज्यादा हो, तो speed advantage कम हो जाता है।

5. Load Imbalance Problem

  • कभी-कभी कुछ processors busy रहते हैं
  • और कुछ idle, जिससे resources का proper use नहीं हो पाता।

6. Not Suitable for Small Problems

  • Small problems में parallel overhead ज्यादा हो जाता है।
  • ऐसे cases में Sequential Algorithm ज्यादा efficient रहता है।

7. Limited Speedup (Amdahl’s Law)

  • Algorithm का हर part parallel नहीं बनाया जा सकता। इसलिए maximum speedup limited होता है |

Related Posts

Start typing and press enter to search

error: Content is protected !!

DCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर

PGDCA के सभी नोट्स,
पुराने पेपर और महत्वपूर्ण प्रश्न उत्तर