Introduction to parallel computing

Serial Computing
Traditionally, software was designed for serial computation, which means:
• Problems are broken down into a series of individual instructions.
• These instructions are carried out one after another, in sequence.
• The execution happens on a single processor.
• At any given time, only one instruction is executed.
Examples: A typical example of a device designed for serial computing is an early Personal Computer (PC), such as:
 IBM PC (1981): A single-processor system designed for sequential execution of tasks.
 Apple II: One of the first popular home computers.
These systems primarily operated on single-core processors, like the Intel 8088 in the IBM PC, which executed one instruction at a time.
Parallel Computing
Parallel Computing refers to a computing approach where multiple tasks are executed simultaneously by dividing the workload among multiple processors or cores. This
method improves efficiency and reduces the time required for complex computations.
In the simplest sense, parallel computing means using multiple computers or processors at the same time to solve a problem. Here's how it works:
• The problem is divided into smaller parts that can be solved simultaneously.
• Each smaller part is broken into detailed instructions.
• These instructions are processed at the same time by different processors.
• A coordination system ensures everything works together properly.
Map-reduce model
• Big Data is a term used for very large sets of data that are too big to be handled by normal computer systems.
• Big Data is now a field of study that involves learning tools, techniques, and methods to manage and analyze large amounts of information. One important tool
for this is MapReduce, a framework designed to handle big data by using many computers together.
• Why use MapReduce? Traditional computer systems store and process data in a central server. But when the data becomes too large, these systems can’t
handle it well, causing delays and inefficiencies.
To solve this, Google developed MapReduce. It breaks down a big task into smaller parts and distributes them to different computers. Each computer works on
its part, and then the results are combined into one final output.
How does MapReduce work?
• MapReduce is a way to process very large amounts of data by splitting the work across multiple computers. It works well for Big Data when combined with
HDFS (Hadoop Distributed File System).
• HDFS is the main system for storing data in Hadoop. It uses two parts:
• NameNode: Keeps track of where files are stored.
• DataNode: Actually stores the [Link] allows fast and reliable storage across many computers working together.
• Hadoop is free, open-source software that helps process and store huge amounts of data across multiple computers.
• How does MapReduce work? and components:
• It uses key-value pairs to process the data. All data must be converted into key-value pairs before processing.
• MapReduce has two main steps
• Map: Breaks the data into smaller tasks.
• Reduce: Combines the results into a final [Link] process always follows the order: Map → Shuffle → Reduce.

 Map Stage: The Map stage is a key part of the MapReduce process. The Mapper organizes unstructured data into a meaningful structure.
For example, to count the number of songs in your playlist by genre, the mapper would process the unstructured data.
The Mapper creates key-value pairs from the data.
Example: Key = Genre, Value = Music file.
The Mapper processes one key-value pair at a time, breaking the data into smaller parts for easier handling.
 Reduce Stage: The Reduce stage includes the Shuffle and Reduce steps.
The Reducer takes the Mapper's output and processes it further to produce the final result.
The Reducer checks all the key-value pairs, groups them by their keys, and combines the values for each key.
Finally, the results are saved in HDFS, providing meaningful outputs like totals or counts for each key.
Application of MapReduce
• Search Engines: Indexing web pages by counting keywords.
• Data Analytics: Processing large datasets, e.g., user behavior analysis.
• Machine Learning: Feature extraction from large datasets.
• Scientific Research: Analyzing massive datasets, like genome sequencing.
• Image Processing: Filtering and analyzing image datasets.
Parallel efficiency of Map-Reduce
The efficiency of MapReduce depends on:
• Data Distribution: Balanced allocation of data across nodes reduces bottlenecks.
• Task Parallelism: Independent tasks ensure minimal waiting time.
• Communication Overhead: Efficient shuffle and sort reduce delays.
Metrics:
1. Speedup: How much faster the task is completed compared to sequential processing.
2. Scalability: Ability to handle increasing data volume by adding more nodes.
MapReduce Infrastructure:
The infrastructure supporting MapReduce is built on distributed systems. Key components include:
• Distributed File System (DFS): Stores large datasets across multiple nodes (e.g., Hadoop HDFS).
• Job Tracker: Manages the execution of Map and Reduce tasks.
• Worker Nodes: Execute Map and Reduce functions.
• Shuffle and Sort Mechanism: Organizes intermediate data for efficient Reduce phase.
Diagram Representation:
Input Data → Map Tasks → Shuffle & Sort → Reduce Tasks → Output Data
1. What happens during the Reduce phase in the MapReduce model?
In the Reduce phase, the data output from the Map phase is aggregated, summarized, or processed to produce the final [Link] Reduce function takes key-value pairs
from the Map phase, groups all values by key, and then applies a computation (like sum, average, count, or custom processing) to each [Link], the Reduce
phase combines the intermediate results from the Map phase into meaningful final output. Example: In word count, the Map phase emits (word, 1) for each word, and the
Reduce phase sums the counts for each word to get (word, total count).

2. List and explain three real-world applications of MapReduce.

1. Word Count and Text Analysis

 Use: Counting word occurrences in large text files, analyzing logs, or processing social media data.
 How it works:
o Map phase: Breaks text into words and emits (word, 1).
o Reduce phase: Sums all counts for each word to get total occurrences.
 Example: Counting hashtags on Twitter.
2. Log Analysis
 Use: Analyzing server or website logs to detect patterns, errors, or user activity.
 How it works:
o Map phase: Extracts relevant fields like user IDs, timestamps, or status codes.
o Reduce phase: Aggregates data by user, URL, or error type to find trends.
 Example: Detecting the most visited pages on a website.
3. Recommendation Systems
 Use: Generating product or content recommendations in e-commerce and streaming platforms.
 How it works:
o Map phase: Maps user-item interactions into key-value pairs (user, item) or (item, user).
o Reduce phase: Aggregates interactions to calculate similarities or rankings.
 Example: Amazon product recommendations or Netflix movie suggestions.
3. How does parallel efficiency in MapReduce depend on data distribution and task allocation?
1. Data Distribution:
 Parallel efficiency improves when the input data is evenly distributed across all nodes.
 If some nodes get more data than others, they become bottlenecks, causing other nodes to wait.
 Example: If Node A has 10 GB and Node B has 1 GB, Node B finishes early and sits idle → inefficient.
2. Task Allocation:
 Efficiency depends on how tasks (Map and Reduce) are assigned to nodes.
 Balanced task allocation ensures all nodes work simultaneously and complete at roughly the same time.
 Poor allocation (e.g., assigning many heavy tasks to a single node) reduces parallel efficiency.
3. Combined Effect:
 Even data distribution + balanced task allocation → high parallel efficiency.
 Skewed data or uneven tasks → low efficiency, longer job completion time, wasted resources.

4. What role does a distributed file system play in the MapReduce infrastructure?

Storage of Large Data:

 MapReduce processes very large datasets that cannot fit on a single machine.
 The Distributed File System (DFS), like HDFS (Hadoop Distributed File System), stores data across multiple nodes.
Data Localization:
 DFS stores data in blocks across nodes and MapReduce tries to run tasks on nodes where the data is located.
 This reduces network traffic and improves processing speed.
Fault Tolerance:
 DFS replicates data blocks across multiple nodes.
 If a node fails, tasks can access the replica on another node, ensuring reliable computation.
Support for Parallel Processing:
 DFS allows simultaneous access to different blocks by multiple Map tasks.
 This enables highly parallel computation in the MapReduce framework.
5. Compare the speedup and scalability of MapReduce with sequential computation.
Feature Sequential Computation MapReduce Computation
Achieves high speedup by running tasks in parallel
Speedup Limited by a single machine’s CPU.
across multiple nodes.
Poor scalability; performance degrades as Highly scalable; can handle petabytes of data by adding
Scalability
data size increases. more nodes.
Data
Processes data one at a time. Processes large datasets simultaneously across nodes.
Processing
Fault If a task fails, entire computation may Built-in fault tolerance; failed tasks rerun on other
Tolerance restart. nodes.
Best Use Big Data applications: log analysis, text processing,
Small datasets, simple computation.
Case recommendation systems.