Abstract :
A parallel copying garbage collection algorithm for symbolic languages executing on shared-memory multiprocessors is proposed. The algorithm is an extension of Baker´s sequential algorithm with a novel method of heap allocation to prevent fragmentation and facilitate load distribution during garbage collection. An implementation of the algorithm within a concurrent logic programming system, VPIM, has been evaluated and the results, for a wide selection of benchmarks, are analyzed. The authors show (1) how much the algorithm reduces the contention for critical sections during garbage collection, (2) how well the load-balancing strategy works and its expected overheads, and (3) the expected speedup achieved by the algorithm
Keywords :
logic programming; parallel algorithms; shared memory systems; storage management; VPIM; benchmarks; committed-choice logic programs; heap allocation; load-balancing; parallel copying garbage collection algorithm; sequential algorithm; shared-memory multiprocessor garbage collector; symbolic languages; Algorithm design and analysis; Automatic logic units; Bismuth; Impedance matching; Integrated circuit testing; Logic programming; Magnetic heads; System performance;
