Efficient synthesis of register transfer level (RTL) arithmetic operations is critical for the performance of data-processing hardware. Multipliers are crucial among all such operators. Multiplication of a variable with a single integer constant can be implemented using addition, subtraction, and shifts. When a variable is multiplied with a set of constants, the sharing of these add/subtract/shift operations becomes possible, but determining an optimal combination of those operations is nondeterministic polynomial time (NP) complete.

Aksoy and Gunes introduce an approximate graph-based algorithm that improves on earlier published methods for this multiple constant multiplications (MCM) problem.

The paper is well written and provides a short overview of the relevant background material. The notation is from earlier work, using an MCM formulation that is based on minimizing the number of A-operations.

The authors refer to an earlier heuristic, “Hcub,” that is considered to be better than previous methods. It provides an improved graph-based approach, where all the target and intermediate constants are synthesized at the end, rather than synthesizing the target constants one at a time.

Section 3 describes the core contribution of the paper: the algorithm ApproximateSearch. The presentation style is good, but Step 11 of the algorithm seems redundant given the assignment at Step 9.

Section 4 shows convincing evidence of the merits of the proposed method, but still “Hcub” is reportedly better in 173 of the 1,890 total instances considered. Therefore, it appears that there is further room for improvement and research.