In some applications, such as many cryptography algorithms, multiplication by a known integer constant is a common operation. It’s well known that integer multiplication with a constant can be computed with a sequence of shifts and adds. Most modern processors already have fast integer multiplication units, so in software it is usually faster to use the multiply instruction instead of a sequence of shifts and adds. However, a hardware multiplier is a relatively large piece of hardware. Therefore, when designing a special-purpose hardware accelerator for a particular application, it may be significantly more efficient to generate a special-purpose multiplier unit for a given constant, rather than generating a general-purpose multiplier.
The minimum constant multiplier problem is the problem of trying to find the minimum number of addition (and subtraction) operations that can multiply by a constant. For example, it is possible to compute a number A multiplied by 12345 with the following sequence: t1 = 8A – A //t1 = 7A; t2 = 32A – t1 // t2 = 25A; t3 = 64 t1 + t1 // t3 = 455 t1; t4 = 512 t2 – t3; // t4 = 12345 A. In general, the problem of finding a minimum sequence of shifts and adds is NP complete. But for many constants that arise in practice, it is possible to find in a reasonable amount of time either an optimal sequence or a sequence that is good enough.
One successful approach to finding efficient sequences of shifts and adds/subtracts models the problem as an integer linear programming (ILP) problem. ILP allows you to describe combinatorial optimisation problems as a set of constraints. Typically, you write a program that generates the ILP constraints, and pass the problem to an existing ILP solver. ILP solvers use a large number of techniques to try to solve ILP problems quickly.
An existing paper describes how the minimum constant multiplier problem can be solved using ILP (https://ieeexplore.ieee.org/document/8332505). Another paper describes a solution that models the problem as a Boolean satisfiability (SAT) problem, and uses a SAT solver (https://modref.github.io/papers/ModRef2020_Deriving%20Optimal%20Multiplication-by-Constant%20Circuits%20With%20A%20SAT-based%20Constraint%20Engine.pdf).
One goal of the project is for the ILP formulation to be sufficiently flexible to model some additional constraints. For example, on FPGAs multiplication by certain small constants may be less expensive to evaluate than for others. It would be helpful if the formulation is flexible enough to add some of these additional opportunities to reduce the cost.