The efficient processing of tree based multiple task jobs arriving in batches to parallel and distributed systems is presented. This type of processing can be found in such application fields as, for example, automatic diagnostics and document recognition. A key management issue in such systems is task allocation. Load balancing is often proposed as the task allocation approach. The load balancing algorithms are employed to improve the throughput of the system by distribution of the incoming workload evenly among the processors in the system. The problem-specific static algorithms as well as general dynamic load balancing algorithms have been developed for supporting batch processing of tree based multiple task jobs. The proposed algorithms have been studied through simulation. Prescheduling load balancing algorithms have been evaluated as superior to other algorithms investigated.
Index Terms:
parallel processing; trees (mathematics); batch processing (computers); resource allocation; distributed processing; parallel processing; tree-based multiple-task jobs; tree based multiple task jobs; batch processing; task allocation; incoming workload; problem-specific static algorithms; prescheduling load balancing algorithms; dynamic load balancing algorithms
Citation:
L. Borzemski, "Load balancing in parallel and distributed processing of tree-based multiple-task jobs," pdp, pp.98, 3rd Euromicro Workshop on Parallel and Distributed Processing, 1995