CSC-418 · Parallel & Distributed Computing

Parallel Algorithm
Models
A Comprehensive Study Guide
Task Graph · Work Pool · Master-Slave · Pipeline · Hybrid

Instructor: Dr. Saeed Azfar

Dept. of Computer Science, CCSIS, IoBM

Parallel & Distributed Computing | Study Reference

Parallel Algorithm Models | CSC-418 Page 2

Table of Contents

1
Introduction to Parallel Algorithm Models 3
.

2
Task Graph Model 4
.

3
Work Pool Model 5
.

4
Master-Slave Model 6
.

5
Producer-Consumer / Pipeline Model 7
.

6
Hybrid Model 8
.

7
Comparison of Models 9
.

8 1
Conclusion
. 0

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM

Parallel Algorithm Models | CSC-418 Page 3

1. Introduction to Parallel Algorithm Models

Parallel computing involves executing multiple computations simultaneously to solve large problems
faster. A parallel algorithm model provides a structured framework that guides how a problem is
decomposed into tasks, how those tasks are assigned to processors, and how data and results are
exchanged between them. Choosing the right model for a given problem is critical to achieving
efficiency and scalability.

The model is developed by considering two main concerns:

● Data decomposition strategy: How the problem's data is divided across processors.
● Interaction minimization: How communication overhead between tasks is reduced to maximize
efficiency.

Core Parallel Algorithm Models at a Glance

Model Primary Strategy Best For

Task Graph Task dependency graph Data-heavy, divide-and-conquer problems

Work Pool Dynamic task assignment Tasks with small data, unpredictable load

Master-Slave Centralized task dispatch Homogeneous tasks, balanced workloads

Pipeline Data stream through stages Stream processing, signal/image processing

Hybrid Combined strategies Complex, multi-phase problems

Key Insight: No single model fits all problems. Experienced parallel programmers analyze the data volume,
computation-to-communication ratio, and workload predictability before choosing a model.

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM

Parallel Algorithm Models | CSC-418 Page 4

2. Task Graph Model

The Task Graph Model represents the parallel algorithm as a directed acyclic graph (DAG) in which
each node represents an independent unit of computation (a task) and each directed edge represents
a data dependency — the output of one task becomes the input of another. This structure naturally
captures both the parallelism available in a problem and the ordering constraints imposed by data
dependencies.

How It Works
● The problem is decomposed into atomic tasks; each task is an independent computation unit.
● Tasks are modeled as a directed graph where edges denote data flow from producer to consumer
task.
● An antecedent task must complete before any dependent task can begin execution.
● Once a task finishes, its output is passed to all downstream (dependent) tasks automatically.
● The program terminates when the last dependent task in the graph completes.
● The model promotes locality — tasks that share data can be scheduled on nearby processors to
reduce data movement cost.

When to Use
The task graph model is most effective when the amount of data associated with tasks is large
compared to the number of computations. In such cases, thoughtful task assignment reduces
expensive data movement between processors. Problems solved via the divide-and-conquer
paradigm map naturally to this model.

Classic Examples
● Parallel Quicksort: The partitioning step creates independent sub-arrays (sub-tasks) whose sorting
is independent — a natural DAG structure.
● Sparse Matrix Factorization: Non-zero elements form natural dependency chains expressible as a
task graph.
● Divide-and-Conquer Algorithms: Merge sort, FFT, and tree computations all map directly to the
task graph model.
● Compiler DAGs: Instruction scheduling in compilers uses task graphs to exploit instruction-level
parallelism.

Real-World Connection: Modern frameworks like Apache Spark and TensorFlow internally represent
computations as DAGs (Directed Acyclic Graphs), making the Task Graph Model the foundation of big data and
deep learning pipelines.

Advantages & Limitations

Advantages Limitations

Explicit data dependency tracking Graph construction overhead

Maximizes data locality Complex scheduling required

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM

Parallel Algorithm Models | CSC-418 Page 5

Fine-grained parallelism control Not suitable for dynamic, unpredictable tasks

Natural fit for divide-and-conquer Load imbalance if graph is irregular

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM

Parallel Algorithm Models | CSC-418 Page 6

3. Work Pool Model

The Work Pool Model (also called the task pool or replicated worker model) uses a shared or
distributed repository of tasks from which any idle process can pick work. Unlike the Task Graph Model,
there is no predefined static assignment of tasks to processes — assignment happens dynamically at
runtime, achieving automatic load balancing.

How It Works
● Tasks are stored in a shared pool — implemented as a list, priority queue, hash table, or tree.
● Any idle process can fetch a task from the pool and execute it — no process is locked to specific
tasks.
● Task assignment can be centralized (single coordinator manages the pool) or decentralized
(distributed across processes).
● New tasks may be generated dynamically during execution (e.g., when exploring a search space).
● When decentralized and dynamic, a termination detection algorithm is required so all processes
know when all work is done.
● Processes that finish early immediately request new tasks, ensuring no processor is idle
unnecessarily.

When to Use
This model excels when task sizes vary unpredictably, or when tasks are generated dynamically. It
works best when the data per task is small relative to the computation, because communication
overhead of fetching a task should be dwarfed by the work performed.

Classic Examples
● Branch-and-Bound Search: Each branch in a search tree is a task; new tasks (sub-branches) are
generated dynamically.
● Discrete Event Simulation: Events are tasks; new events are generated as simulation progresses.
● Ray Tracing: Individual pixel computations are independent tasks drawn from a shared pool.
● Web Server Thread Pools: Incoming HTTP requests are queued in a pool; worker threads pick
them up dynamically.

Real-World Connection: Thread pool executors in Java (ExecutorService), Python's [Link], and
OpenMP's task directive all implement the Work Pool model. It is the backbone of concurrent server
architectures.

Advantages Limitations

Automatic dynamic load balancing Pool access can become a bottleneck

Simple to implement for irregular tasks Termination detection adds complexity

Works with unpredictable task sizes High communication if tasks are tiny

No pre-planning of task distribution needed Decentralized pool requires synchronization

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM

Parallel Algorithm Models | CSC-418 Page 7

4. Master-Slave Model

The Master-Slave Model (also called the manager-worker model) designates one or more processes
as masters whose sole responsibility is to generate tasks and distribute them to a pool of slave
(worker) processes. Workers perform the actual computation and report results back to the master. The
model is naturally suited for both shared-memory and message-passing paradigms due to its
inherently two-way communication structure.

How It Works
● The master process maintains a task queue and dispatches tasks to idle slave processes.
● Slaves execute assigned tasks and return results to the master upon completion.
● The master can pre-assign tasks if it can estimate task sizes, or assign them lazily on demand.
● When tasks span multiple phases, the master waits for all phase-N tasks to complete before
generating phase N+1 tasks.
● A hierarchical (multi-level) variant uses intermediate masters: top-level master → sub-masters →
workers, reducing bottleneck at the top.
● Task granularity must be chosen carefully — tasks should be large enough that computation
dominates communication cost.

Precautions and Design Considerations

● Avoid master congestion: If tasks are too small or slaves are very fast, the master becomes a
bottleneck limiting scalability.
● Task size matters: The cost of performing a task must dominate the communication +
synchronization overhead.
● Asynchronous communication: Overlap task generation with slave execution using non-blocking
sends to hide latency.
● Fault tolerance: If a slave fails, the master can reassign its pending tasks to another worker.

Classic Examples
● Parallel Rendering: Master distributes image tiles; workers render tiles independently.
● Parameter Sweep Simulations: Master generates parameter combinations; workers simulate
each.
● Map-Reduce (simplified): The driver (master) schedules map tasks to workers and collects results.
● Parallel Search Engines: A coordinator process distributes document chunks to indexing workers.

Real-World Connection: The Master-Slave model is the foundation of distributed computing frameworks like
Hadoop MapReduce (JobTracker as master, TaskTrackers as slaves) and Apache Spark (Driver as master,
Executors as slaves).

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM

Parallel Algorithm Models | CSC-418 Page 8

5. Producer-Consumer / Pipeline Model

The Pipeline Model (a generalization of the producer-consumer pattern) structures the parallel
algorithm as a chain — or directed graph — of processing stages. Data flows through the stages in
sequence: each stage consumes the output of the previous stage, processes it, and passes the result to
the next. Multiple data items can be in-flight simultaneously at different stages, achieving temporal
parallelism analogous to an assembly line.

Key Concepts
● Stage: A process (or group of processes) that performs one specific transformation on the data
stream.
● Producer: The first stage generates or ingests data and passes it downstream.
● Consumer: The last stage produces the final output; intermediate stages are both consumer and
producer.
● Throughput: Determined by the slowest stage (the bottleneck) — all stages must be balanced for
maximum efficiency.
● Latency: Time for one item to traverse the entire pipeline; throughput and latency are distinct
metrics.
● The pipeline topology need not be linear — it can be a tree, DAG, or graph with cycles for more
complex data flows.
● Key optimization: Overlapping communication with computation — while stage N processes item
K, stage N+1 processes item K-1.

Producer-Consumer Relationship
Each pair of adjacent stages has a producer-consumer relationship: the upstream stage produces data
that the downstream stage consumes. Buffers or channels between stages decouple their execution
speeds, allowing the faster stage to continue working without waiting for the slower one (bounded buffer
/ back-pressure mechanisms manage overflow).

Classic Examples
● Signal Processing: Filter → FFT → Feature Extraction → Classifier stages run concurrently on
successive signal frames.
● Image Processing Pipelines: Decode → Resize → Color-correct → Encode — each frame flows
through all stages.
● Compiler Stages: Lexer → Parser → Semantic Analyzer → Code Generator — each phase is a
pipeline stage.
● Network Packet Processing: Ingress → Classification → Policy → Egress stages in routers and
firewalls.
● Instruction Pipelines in CPUs: Fetch → Decode → Execute → Write-back is the archetypal
hardware pipeline.

Real-World Connection: Streaming frameworks like Apache Kafka, Apache Flink, and Unix shell pipes (cmd1 |
cmd2 | cmd3) are direct implementations of the Pipeline Model. Video encoding software uses multi-stage
pipelines for real-time performance.

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM

Parallel Algorithm Models | CSC-418 Page 9

Advantages Limitations

High throughput via temporal parallelism Throughput capped by slowest stage

Simple, modular structure Latency increases with more stages

Naturally handles streaming data Startup and drain overhead

Easy to scale individual stages Stage imbalance causes idle time

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM

Parallel Algorithm Models | CSC-418 Page 10

6. Hybrid Model

Real-world parallel problems are rarely uniform enough to be solved optimally by a single model. The
Hybrid Model combines two or more of the above models — either sequentially across phases of the
algorithm or hierarchically (one model at the outer level, another at the inner level). The designer
selects the best-fitting model for each phase or granularity level of the problem.

Common Hybrid Combinations

● Master-Slave + Pipeline: Master distributes data streams to worker pipelines; each worker runs a
local multi-stage pipeline.
● Task Graph + Work Pool: A task graph structures coarse-grained phases; within each phase, a
work pool manages fine-grained tasks.
● Pipeline + Master-Slave: Each pipeline stage is itself managed by a master-slave team, scaling
individual stages independently.
● MPI + OpenMP (common in HPC): MPI (message passing) implements Master-Slave between
nodes; OpenMP implements Work Pool within each node's threads.

When to Use
Use the hybrid model when a problem has multiple distinct computational phases with different
characteristics, or when the available hardware has a hierarchical structure (e.g., multi-node clusters
where each node has multiple CPU cores and GPU accelerators). A single model applied uniformly to
hierarchical hardware typically underperforms.

Examples
● Scientific Simulations (e.g., climate models): Task graph for domain decomposition across
nodes + pipeline for time-stepping within each domain.
● Deep Learning Training: Pipeline model parallelism across layers + data parallelism (work pool)
within each layer.
● Genome Sequencing: Master-slave for distributing genome segments + task graph within each
segment for alignment.

Key Design Principle: Profile first, then model. Identify the bottleneck phase of your algorithm and apply the
model that best addresses it. Premature hybridization adds complexity without guaranteed performance gains.

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM

Parallel Algorithm Models | CSC-418 Page 11

7. Comparison of Parallel Algorithm Models

Model Task Assignment Load Balancing Communication Pattern Best Scenario

Task Graph Static (DAG-based) Moderate Point-to-point (dependencies)

Data-heavy, structured dependencies

Work Pool Dynamic Excellent Any process ↔ pool Irregular tasks, unpredictable sizes

Master-Slave Centralized (master) Good Master ↔ slaves (two-way)Homogeneous, estimable tasks

Pipeline Static (stage-based) Moderate Linear/graph data flow Streaming, phased transformations

Hybrid Mixed Varies Mixed Multi-phase, hierarchical HW

Model Selection Decision Guide

Question If YES → Consider

Is data volume >> computation? Task dependencies dominate Task Graph Model

Are task sizes unpredictable? Load varies at runtime Work Pool Model

Can one process generate all tasks? Centralized control feasible Master-Slave Model

Does data flow through fixed stages? Sequential transformation Pipeline Model

Are there multiple distinct phases? No single model fits Hybrid Model

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM

Parallel Algorithm Models | CSC-418 Page 12

8. Conclusion

Parallel algorithm models provide the conceptual scaffolding for designing efficient parallel software.
Rather than working directly with low-level thread or message primitives, these models let programmers
reason at a higher level of abstraction, focusing on what runs in parallel and how data moves.

Key Takeaways
● Each model solves a distinct class of parallel problems — there is no universally best model.
● The Task Graph Model excels when data movement dominates and dependencies are structured.
● The Work Pool Model provides automatic load balancing for irregular, unpredictable workloads.
● The Master-Slave Model offers simple centralized control suitable for homogeneous tasks.
● The Pipeline Model maximizes throughput for streaming data through sequential transformations.
● The Hybrid Model combines strengths of multiple models for complex, multi-phase problems.
● All models share the common goal: maximize computation, minimize communication and
synchronization overhead.
● Real-world frameworks (Spark, Flink, OpenMP, MPI) directly implement these conceptual models.

Design Principle

"The parallel algorithm model solves large problems by dividing them into smaller parts, then
solving each independent sub-task simultaneously. Each model uses its own data partitioning
and processing strategy to improve speed and efficiency."

— CSC-418, Parallel & Distributed Computing

Dr. Saeed Azfar · Dept. of Computer Science, CCSIS, IoBM