Efficient Algorithms for the Ensemble Computation Problem

Ensemble Computation (EC) is an optimization problem to find the least operations sequence to calculate all of the given multiple monomials. EC can be applied to simplify the logic circuits, and to the optimization of the compiler. In this paper, we suggest efficient algorithms for EC. By the computational experiments, we compared an algorithm based on Beam Search (BS) with an algorithm derived from the compression algorithm Re-Pair. Experimental results show that the BS based algorithm produces better solutions although it is slower than the Re-Pair based algorithm.