Dynamic load balancing for concurrent Lisp execution on a multicomputer system
Raymond Maihin Chowkwanyun · University of Southern California Digital Library · 2015
A major problem in programming multicomputers is the allocation of processes to processors. A multicomputer is a distributed-memory multiprocessor. Partitioning and allocating programs on an ad hoc basis is expensive and inefficient. Dynamic load balancing provides a systematic solution to the allocation problem. The basic mechanism is run time migration of processes from busy to idle processors. The goal is to prevent processor idling and increase system throughput. The load balancer effectively provides a set of operating system functions which isolates the programmer from the details of the underlying hardware. As a result, programmability is enhanced because applications written to the load balancer are portable and scalable. Dynamic rather than static load balancing is used. Dynamic load balancing is required when the run time characteristics of the applications program cannot be predicted at compile time. Artificial intelligence programs written in Lisp are targeted as an important class of applications having just such characteristics. A model of load balancing is presented which identifies sufficient conditions for a distributed system to achieve a balanced load. New concepts of strongly and weakly balanced load are introduced to characterize load balancing methods. The model is applied to the proposed hybrid load balancing method and two other methods to show that a balanced load can be achieved. I discuss the implementation of the hybrid load balancing method which adapts to changing system load by switching individual processors between two operating modes; sender-initiated and receiver-initiated. Sender-initiated mode promotes rapid process propagation and is used when system load is light. Receiver-initiated mode is conservative about process migration and is used when system load is heavy. The adaptability of the hybrid system makes it superior to load balancers based exclusively on sender-initiation or receiver-initiation. Benchmarking results based on the Gabriel benchmarks Tak, Boyer, Browse, and Traverse support the superiority of the hybrid system. Other issues discussed include parallelization of serial programs, the macro dataflow execution model, and the architecture of the hybrid system. (Copies available exclusively from Micrographics Department, Doheny Library, USC, Los Angeles, CA 90089-0182.)