Searching a Sorted Sequence:
EREW, CREW, and CRCW Searching
Understanding Parallel Search Models
Presented by: [Your Name]
Date: [Your Date]
Introduction to Searching in Parallel
Computing
What is Searching?
• Searching involves finding a specific element in a dataset.
• When the dataset is sorted, searching is faster and more
efficient (e.g., Binary Search).
Why Use Parallel Searching?
• Large datasets require fast search methods.
• Parallel computing speeds up searching by using
multiple processors.
• Different parallel computing models define how
processors access memory.
Searching a Sorted Sequence
Why is sorting important in searching?
• Sorted sequences allow efficient searching like binary
search (O(log n) time).
• Parallel search methods distribute workload across
multiple processors.
How does Parallel Searching Work?
• Instead of one processor sequentially searching,
multiple processors work simultaneously.
• Different PRAM (Parallel Random Access Machine)
models define memory access rules.
PRAM Model Overview
• - PRAM (Parallel Random Access Machine)
allows multiple processors to share memory.
• - Different models control memory access:
• • EREW: Exclusive Read, Exclusive Write
• • CREW: Concurrent Read, Exclusive Write
• • CRCW: Concurrent Read, Concurrent Write
EREW Searching (Exclusive Read, Exclusive
Write)
Concept:
• Most restrictive model:
• Only one processor can read a memory location at a time.
• Only one processor can write at a time.
Algorithm Steps:
1. Divide the search space among multiple processors.
2. Each processor independently performs a Binary Search on its
assigned section.
3. If the target value is found, the processor stores the index in a
shared variable.
Time Complexity:
• O(log n) time using O(n/log n) processors.
CREW Searching (Concurrent Read,
Exclusive Write)
Concept:
• Allows multiple processors to read the same memory location.
• Only one processor can write at a time (others must wait).
• More efficient than EREW since multiple processors can read
simultaneously.
Algorithm Steps:
1. Processors read different parts of the sorted sequence simultaneously.
2. If a processor finds the key, it writes the result (ensuring only one
writes).
3. Processors stop when the result is found.
Time Complexity:
• O(log n) time using O(n/log n) processors.
CRCW Searching (Concurrent Read,
Concurrent Write)
Concept:
• Most relaxed model:
• Multiple processors can read and write at the same time.
• Write Conflict Resolution Strategies:
• Common: Only one processor writes.
• Arbitrary: Any one processor’s write is accepted.
• Priority: The processor with the highest priority writes.
Algorithm Steps:
1. Processors scan the search space simultaneously.
2. When multiple processors find the target, one writes the result based on
conflict resolution.
3. The result is retrieved in O(1) time if a resolution strategy is efficient.
Time Complexity:
• O(log log n) time using O(n/log log n) processors
Comparison of EREW, CREW, and CRCW
Searching
Conclusion & Applications
• - Parallel searching enhances efficiency for large
datasets.
• - EREW is restrictive, CREW is balanced, CRCW is
fastest.
• - Real-world applications:
• • Big Data Processing
• • Database Indexing
• • AI & Machine Learning
• • Distributed Computing Systems
