Imagine checking a long list of passwords: each candidate can be tested without waiting for any other candidate. An embarrassingly parallel problem divides such independent work among processing resources, with no communication or synchronization required between tasks. section 2.10 section 2.8
A practical solution follows a simple pattern:
- Decompose the large problem into separate tasks. section 2.10
- Create ranges or chunks of work for each processing resource. section 2.10
- Distribute the chunks and execute them in parallel, avoiding synchronization points. section 2.10 section 2.8
Password checking
A sequential password search checks combinations one after another and reports a processing time of about 64.6 seconds. A parallel design divides the combinations into ranges, assigns those ranges to available cores, and checks them independently. Finding prime numbers by allocating subsets to processing resources follows the same pattern. section 2.10 section 2.8
ChunkRange = T.Tuple[int, int]
def get_chunks(num_ranges: int,
length: int) -> T.Iterator[ChunkRange]: #1
max_number = int(math.pow(10, length) - 1) #1
chunk_starts = [int(max_number / num_ranges * i) #1
for i in range(num_ranges)] #1
chunk_ends = [start_point – 1 #1
for start_point in #1
chunk_starts[1:]] + [max_number] #1
return zip(chunk_starts, chunk_ends) #1
def crack_password_parallel(crypto_hash: str, length: int) -> None:
num_cores = cpu_count() #2
chunks = get_chunks(num_cores, length)
# DO IN PARALLEL #3
# for chunk_start, chunk_end in chunks: #3
# crack_chunk(crypto_hash, length, chunk_start, chunk_end)} #3
Inspect the chunk-range pseudocode that calculates work intervals and assigns one range to each available core. section 2.10
