The compaction of acyclic terms
Ga tan Hains · 2005
The compaction of acyclic terms is proposed as a dynamic memory management operation for distributed symbolic computation. Compaction is defined here as the minimisation of term graphs, to give maximal structure-sharing. A simple transformation is described to show this problem equivalent to the minimisation of finite automata. When processing an object distributed among separate processes, substructures may be copied to reduce communication overheads. However, if accesses to the same object later become local (and sequential) it is more efficient to merge repeated structures. The need for a fast compaction algorithm therefore arises from the dynamic interplay of local vs global access, to recover structure-sharing after copying. No sequential algorithm is known for compacting terms in linear time. Superlineartime algorithms exist but suffer fi'om significant overheads, which make them unsuitable for repeated dynamic use. As a practical solution a systolic algorithm for compaction is described, on an array of size equal to the number of input graph vertices.