Lab 7 - Replicated Workers Model
In parallel programming, the Replicated Workers model (or Thread Pool) is a design pattern used to achieve concurrency in program execution. In this model, there are two main components: a task pool to be executed, typically represented as a queue, and a group of workers (usually threads). Each worker in the replicated workers model exhibits the following behavior:
while (1)
take a task from the pool
execute the task
add zero or more resulting tasks to the pool
As can be observed in the pseudocode above, a worker takes a task from the pool and executes it. As a result of executing a task, additional tasks may be generated, which the worker adds to the pool, and then the previous steps are repeated.
The Replicated Workers model is useful when:
- The size of the problem is not known in advance, meaning the number of steps to be executed is not predetermined.
- There are many small-sized tasks that need to be executed, and it is more efficient to reuse the same threads rather than creating new ones for each step.
- There is a possibility of thread imbalance (e.g., some cores are busier than others or different from each other), and an equal distribution of computational tasks would lead to delays in the program.
A graphical representation of the replicated workers model can be seen in the figure below.
📄️ ExecutorService Interface
ExecutorService is an interface in Java that allows the execution of asynchronous tasks in the background concurrently, based on the Replicated Workers model. For example, there might be a need to send a number of requests, but it would be inefficient to send them one by one, sequentially, waiting for each one to complete. The solution is to work asynchronously, meaning to send a request, not wait for it (send it in the background), and use threads to divide the number of requests and send multiple at once (concurrently). This would be the case when we don't know in advance the size of the problem we are solving, and either we need all the solutions to the problem (because we have to send all the requests) or we don't want to find all the solutions but at least one.
📄️ ForkJoinPool Class
Another method to implement the Replicated Workers model in Java is the Fork/Join framework, which uses a "divide et impera" approach, meaning it first involves the recursive splitting (Fork) of the initial task into smaller, independent subtasks until they are small enough to be executed asynchronously. After that, the recursive collection (Join) of results follows to produce a single result (in the case of a task that doesn't return a specific result, it simply waits for all subtasks to finish execution).
📄️ Exercises
In this lab, you will work with this skeleton, which you will use to parallelize three problems based on the Replicated Workers model, using ExecutorService and ForkJoinPool: