A Resource-Aware Dynamic Load-Balancing Parallelization Algorithm in a Farmer-Worker Environment

The Farmer-Worker Algorithm And Its Dependable Extension

The dependable multiresource dynamic algorithm is based on an elaboration of the traditional farmer-worker algorithm. In the most commonly known basic farmer-worker model, a farmer processing entity grabs the input data or tasks, divides the tasks into subtasks, and feeds the subtasks in parallel to processing entities called workers. The farmer collects the results and glues them together to one resulting processed output.

The farmer needs to go through quite some sequential processing between two runs. The input data needs to be grabbed, divided, and dispatched to the workers, and afterward the worker’s processing output needs to be collected, merged, and finalized to one result. In video processing, where video is received from a camera and images extracted and divided for further processing, real-time behavior is important. Furthermore the failure of one worker endangers the processing of the complete task.

Therefore a dependable extension of the farmer-worker model has been proposed (De Florio, Deconinck, & Lauwereins, 1997) and, later, a corresponding framework library, RAFT-net (Leeman, Leeman, De Florio, & Deconinck, 2003). This extension describes a dispatcher and a collector. The workers subscribe themselves for processing with the dispatcher. The farmer grabs the input data and sends the list of subtasks to the dispatcher, which assigns them to idle workers. While these workers are processing subtasks and the dispatcher is assigning them, the farmer can grab the input data for the next run.

Once a worker has processed a subtask, it notifies the dispatcher of its idle state so that a new subtask can be assigned to it. The output is sent to the collector. This entity collects the output from each worker and notifies the dispatcher that this subtask has been processed. From the moment a subtask is finished, the dispatcher also notifies the farmer, which sends as a response the corresponding subtask from the next run to the dispatcher.