# Towards optimal reconfigurable constant multipliers

Bastien Barbe, Xiao Peng, Anastasia Volkova, Florent de Dinechin

► To cite this version:

Bastien Barbe, Xiao Peng, Anastasia Volkova, Florent de Dinechin. Towards optimal reconfigurable constant multipliers. 28th Conference on Digital System Design (DSD), Euromicro, Sep 2025, Salerno, Italy. pp.418-425, 10.1109/DSD67783.2025.00064. hal-05094796v2

HAL Id: hal-05094796

https://hal.science/hal-05094796v2

Submitted on 9 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Towards optimal reconfigurable constant multipliers

†Bastien Barbe, ‡Xiao Peng, *Anastasia Volkova, †Florent de Dinechin

†INSA Lyon, Inria, CITI (UR3720)
69621 Villeurbanne, France

{firstname.lastname}@insa-lyon.fr

‡LAAS-CNRS (UPR8001)
31031 Toulouse, France

{firstname.lastname}@laas.fr

*Inria, INSA Lyon, CITI (UR3720)
69621 Villeurbanne, France

{firstname.lastname}@inria.fr

**Abstract**—This paper introduces a novel algorithm for generating run-time reconfigurable single constant multipliers (RSCMs) which are optimal within their model in terms of hardware cost. Optimality is ensured by an exhaustive exploration of the design space mixing constraint programming, depth-first search, and branch-and-prune techniques. The cost model of previous works is also refined. Compared to the state of the art, this approach enables much larger constant sets, and also significantly improves the performance of the resulting architectures. Applications to neural network inference and small floating-point multiplication units are evaluated.

**Index Terms**—Reconfigurable Single Constant Multipliers (RSCM), multiplierless, neural networks, quantization.

## I. INTRODUCTION

In digital circuits, multipliers by constants known at design time can be simplified into specialized operators known as constant multipliers (CM). This is especially relevant in Digital Signal Processing (DSP), with applications such as fast Fourier transforms, digital filters, and video encoding. More recently, CMs have been used to accelerate neural network inference.

A Single Constant Multiplication (SCM) operator is typically a combination of constant shifts and additions that is simpler than a generic multiplier [1, ch. 12]. For example, in Fig. 1a, the multiplication of a binary integer input $X$ by the constant 17 can be expressed with only a shift and an adder: $17X = 16X + X = (X \ll 4) + X$. The shift operation $X \ll 4$ consists of wires and therefore comes for free.

The SCM optimization problem consists in finding, for a given constant $C$, a shift-and-add tree or Direct Acyclic Graph (DAG) multiplying an input $X$ by $C$ at the least possible hardware cost. This is a well-studied problem (8 pages of references in [1, ch. 12]). The minimum number of adders is known for constants up to 32 bits [2]. For larger constants, heuristics like $H_{cub}$ [3] and RPAG [4] exist.

In this article, we address yet another CM variant: the re-configurable single constant multiplier (RSCM), also known as time-multiplexed constant multiplier. As illustrated in Fig. 1b, an RSCM multiplies its input by a constant $T_i$, chosen at runtime from a set of possible constants $T = \{T_i | i \in [0, ... n]\}$ known at design time. Here the index $i$ is another input to the multiplier, used to select the constant to multiply by.

To build an RSCM, $i$ is decomposed into its bits ($i_1$ and $i_0$ in Fig. 1b). Each of these index bits can be used either as the

selection bit of a two-input multiplexer, or as the $\pm$ bit to an adder/subtractor.

RSCM have been used for instance in digital filter design [5], [6]. An emerging application of RSCM is neural networks inference [7]–[9]. It has been shown [7] that replacing generic 8-bit fixed-point multipliers with RSCMs for only 16 well-chosen 8-bit coefficients can achieve up to 50% resource saving, speedups and power savings without significant loss of accuracy on Alexnet [10] and Resnet-18 [11].

The RSCM optimization problem consists, given a set of target constants $T$, in finding the RSCM of least possible cost for this set of constants. Early techniques for minimizing of number of adders in an RSCM were based on common expression elimination (CSE) on the canonical signed digit (CSD) representation of the constants [12]. Another approach is to first find SCMs with the least number of adders, and then merge them into a single graph by inserting multiplexers. This was proposed for ASIC [2] and FPGA [13]. The number of multiplexers can be reduced in post-processing using integer linear programming (ILP) [14] or, more efficiently, during the DAG merging step [15].

This article provides an RSCM optimization algorithm that, instead of minimizing the number of adders, fixes the number of adders to 1, 2 or 3 depending on the target coefficients, and then explores exhaustively their combination using 2-to-1 multiplexers (MUX2). This algorithm, presented in Section II, produces RSCM architectures that are optimal in terms of MUX2, where previous approaches are either heuristic or incomplete [15]. Furthermore, we demonstrate that the number of MUX2 is not an ideal measure of the cost of an RSCM. Section II introduces a more fine-grained cost function (accounting for the bit-level full- and half-adders used in

<figure><img src="image_2.png" /><figcaption>Fig. 1: (a) SCM for 17. (b) RSCM for $T = \{-15, -3, 5, 17\}$.</figcaption></figure>

This work was partially supported by the PEPR IA HOLIGRAIL project of the Agence Nationale de la Recherche, ANR-23-PEIA-0010.

The code is available at https://github.com/GrannyDev/rscmSolverCpp.
the architecture). This cost function is used directly as the minimization objective where previous works [15] estimated it a posteriori.

The evaluation of this approach in Section III shows that it pushes the number of possible target constants beyond what was previously possible, while yielding smaller RSCM architectures than the state of the art.

Section IV demonstrates applications to machine learning acceleration. First, similarly to [10], [11], we demonstrate the relevance of Quantization Aware Training (QAT) of a convolutional neural network targeting a well-chosen RSCM. The cost of this RSCM is compared to generic integer multipliers on FPGA and ASIC targets. Second, we show an RSCM implementation of a multiplier by weights encoded in a 6-bit floating-point format proposed by the Open Compute project.

## II. THE RSCM SOLVER ALGORITHM

Given a set of target constants $T$ and a maximum allowed bitwidth $B$ for representing intermediate constants, the proposed algorithm proceeds in two steps (Fig. 2). First, it models the generation of SCM graphs as a constraint-programming problem in order to enumerate, for each $T_i \in T$, the complete set $S_{SCM}[i]$ of graphs that computes $T_i$ (Section II-A). Second, it performs a depth-first branch-and-prune search (DFS B&P) to merge these SCMs into an RSCM architecture that minimizes the overall cost (Section II-B). Cost metrics are defined at coarse (Section II-C) or bit-level (Section II-D) granularity.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Bird's-eye view of the proposed RSCM solver.</figcaption></figure>

### A. Enumerating all possible SCMs for each target constant

All constants up to 42 can be realized using only 2 adders and up to 682 with 3 adders [16], enabling all 8-bit constants. This step therefore focuses on SCMs with 3 adders at most.

The model of Fig. 3a captures all possible SCMs that can be implemented using either one adder, or one subtractor (according to the value of the variable $\mu$), along with shift values $s^l$, $s^r$ and $s^{out}$ on the left input, right input, and output respectively. The shift values can be chosen from the range $[0, B-1]$. The output $T_i X$ in Fig. 3a is thus defined as

$$T_i X = (X \ll s_0^l + (X \times (-1)^{\mu_0}) \ll s_0^r) \ll s_0^{\text{out}} \quad (1)$$

An SCM layout with more than one adder combines several copies of the adder block of Fig. 3a, each identified by a subscript $i$ on each variable. Adders operating at the same

<figure><img src="image_4.png" /><figcaption>(a) 1 adder model, with example instance below</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 3: Models capturing possible SCMs with up to 3 adders (3-layer 3-adder layout not represented for lack of space).</figcaption></figure>

depth are grouped into layers. When more than one layer is involved (as shown in Figs. 3b and 3c), additional variables $\epsilon_i^l$ and $\epsilon_i^r$ are introduced to describe how the inputs of adder $i$ are connected to the outputs of adders from the previous layers. Furthermore, the adder block $i$ can also directly input $X$, possibly shifted by $s_i^{X,l}$ on the left and $s_i^{X,r}$ on the right. For example, the output of Fig. 3b is:

$$T_i X = ((y_1^l \ll s_1^l) + ((-1)^{\mu_1} y_1^r \ll s_1^r)) \ll s_1^{\text{out}} \quad (2)$$

where

$$y_1^l = \begin{cases} ((X \ll s_0^l) + (-1)^{\mu_0} X \ll s_0^r) \ll s_0^{\text{out}} & \text{if } \epsilon_1^l = 1 \\ X \ll s_1^{X,l} & \text{if } \epsilon_1^l = 0 \end{cases} \quad (3)$$
and

$$
y_1^r = \begin{cases} ((X \ll s_0^l) + (-1)^{\mu_0} X \ll s_0^r) \ll s_0^{\text{out}} & \text{if } \epsilon_1^r = 0 \\ X \ll s_1^{X,r} & \text{if } \epsilon_1^r = 1. \end{cases} \tag{4}
$$

Table I summarizes the model variables and their domains
where $\alpha_i$ denotes the number of adders preceding the layer of
adder block $i$. For instance, in Fig. 3c, $\alpha_0 = 0$ (indicating that
only $X$ is available as input) and $\alpha_1 = 2$.

<table><caption>TABLE I: Model variables and their domains for adder $i$</caption>
  <thead>
    <tr>
      <th>Variable</th>
      <th>Description</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>s<sub>i</sub><sup>l</sup> &isin; &lfloor;0, B &minus; 1&rang;</td>
      <td>shift on the left input</td>
    </tr>
    <tr>
      <td>s<sub>i</sub><sup>r</sup> &isin; &lfloor;0, B &minus; 1&rang;</td>
      <td>shift on the right input</td>
    </tr>
    <tr>
      <td>s<sub>i</sub><sup>out</sup> &isin; &lfloor;0, B &minus; 1&rang;</td>
      <td>shift on the output</td>
    </tr>
    <tr>
      <td>&mu;<sub>i</sub> &isin; {0, 1}</td>
      <td>addition or subtraction</td>
    </tr>
    <tr>
      <td>&epsilon;<sub>i</sub><sup>l</sup> &isin; &lfloor;0, &alpha;<sub>i</sub>&rfloor;</td>
      <td>left input MUX selector</td>
    </tr>
    <tr>
      <td>&epsilon;<sub>i</sub><sup>r</sup> &isin; &lfloor;0, &alpha;<sub>i</sub>&rfloor;</td>
      <td>right input MUX selector</td>
    </tr>
    <tr>
      <td>s<sub>i</sub><sup>X,l</sup> &subset; &lfloor;0, B &minus; 1&rang;</td>
      <td>shift on X if input to the left</td>
    </tr>
    <tr>
      <td>s<sub>i</sub><sup>X,r</sup> &subset; &lfloor;0, B &minus; 1&rang;</td>
      <td>shift on X if input to the right</td>
    </tr>
  </tbody>
</table>

The number of configurations that the model has to explore
for *n* adders is

$$
\#C = \prod_{i=0}^{n-1} 2B^3. \begin{cases} 1 & \text{if } i \text{ in layer } 0 \\ (\alpha_i + B)^2 & \text{else} \end{cases} \tag{5}
$$

Obviously, #C grows exponentially with both the number of
adders and the allowed bitwidth.

The set $S_{\text{SCM}}[i]$ of the possible SCMs for each $T_i$ is built us-
ing constraint programming (CP), well-suited for enumeration
problems over sets.

B. Merging SCMs to construct optimal RSCMs

A recursive depth-first search function (detailed in Alg. 1) then exhaustively explores all the possible merges between the SCMs. The merging process consists in inserting multiplexers between SCMs wherever their variable assignments differ. In the example of Fig. 4, merging SCMs that compute 49X and 71X into an RSCM requires an adder/subtractor in the first layer as well as the insertion of a multiplexer on the right-hand branch. These two elements are controled by a configuration bit $i_0$, allowing selection between the two outputs at runtime.

As all the SCMs share the same layout, it is possible to
associate a bit to each possible value of each variable of the
layout, so that the (R)SCMs in Fig. 4 are stored as bit-sets.
The merging process is a set union that can be implemented
as a bitwise OR, a constant time operation. A multiplexer is
needed as soon as more than one bit is set for a variable.

The number of DAGs to explore is the product between
the number of possible SCMs for each target constant $T_i$ and
thus grows exponentially with the number of constants $\#T$.
Therefore, to keep the corresponding combinatorial explosion
under control, the space exploration is a B&P which updates
the current cost and prunes any branch as soon as its current
cost exceeds the best cost found so far.

<figure><img src="image_6.png" /><figcaption>Fig. 4: Merging two SCMs (a) and (b) to obtain an RSCM (c) for $T = \{49, 71\}$ with one configuration bit $i_0$.</figcaption></figure>

**Algorithm 1 Optimal RSCM search**
1: **function** OPTIMALRSCMBUILDER(T)
2:     S<sub>SCM</sub> ← ENUMERATESCM(T)
3:     bestRSCM ← ∅, bestCost ← ∞ ▷ global variables
4:     RECURSIVEMERGE(0, ∅)
5:     **return** bestCost, bestRSCM
6: **function** RECURSIVEMERGE(i, RSCM)
7:         **if** i ≥ #T **then** ▷ all constants done
8:             bestRSCM ← RSCM
9:             bestCost ← cost(bestRSCM)
10:         **return**
11:      **for** k ∈ [0, #S<sub>SCM</sub>[i]] **do** ▷ try all SCMs for T<sub>i</sub>
12:          nextRSCM ← RSCM ∪ S<sub>SCM</sub>[i][k]
13:          **if** cost(nextRSCM) < bestCost **then**
14:              RECURSIVEMERGE(i + 1, nextRSCM)

C. A coarse-grained cost function: counting multiplexers

The number of MUX2 has been proposed as a cost metric
for assessing the resource requirements of a RSCM, under the
assumption that the number of adders is optimal, as discussed
in [14], [15]. An *n*-to-1 multiplexer (i.e., a multiplexer with
*n* inputs and a single output) can be functionally decomposed
into *n* − 1 MUX2. In previous works, the extra cost of an
adder/subtractor compared to a simple adder is not consid-
ered. Our cost model, however, assigns an additional cost of
one MUX2 to an adder/subtractor, reflecting the extra logic
required for conditional addition or subtraction.

D. A fine grained cost function: estimating area

The number of MUX2 is a high-level metric of the actual
area of the implemented RSCM. Indeed, for a given target
coefficient set, many architectures implementing it with the
optimal MUX2 cost may exist. For example, there are 1213
possible 2-adder 5-MUX2 solutions that implement the target
set of Fig.9. The estimated area of these solutions using a
bit-level model [15], [17] for adders and multiplexers demon-
strates significant room for improvement, as it ranges from
2871 to 3198 area units, see Fig.5. This motivates the use of a more fine-grained metric as a primary optimization objective in our algorithm, instead of minimizing the number of MUX2.

<figure><img src="image_7.png" /><figcaption>Fig. 5: Area cost distribution for RSCM architectures implementing Fig. 9 constants within optimal MUX2 count.</figcaption></figure>

The cost model below extends that of [15] by distinguishing between half-adders and full-adders.

For each MUX $i$, let $k_M(i)$ be the bitwidth of its output. Let $m(i)$ be the number of inputs of a $m$-to-1 MUX. The cost of one bit of MUX is defined as $c_M$.

For each adder ($A$), subtractor ($S$), or adder/subtractor (AS) $i$, let $k_a^{FA}(i)$ be its number of full-adders and $k_a^{HA}(i)$ be its number of half-adders. The associated cost for one bit is noted $c_a^b$ for $a \in \{A, S, AS\}$ and $b \in \{FA, HA\}$.

With these notations, the total area cost is

$$C_{\text{area}} = \sum_{i=0}^{N_M-1} c_M \cdot k_M(i) \cdot m(i) + \sum_{a \in \{A,S,AS\}} \sum_{i=1}^{N_a} \left( k_a^{\text{FA}}(i) c_a^{\text{FA}} + k_a^{\text{HA}}(i) c_a^{\text{HA}} \right). \quad (6)$$

As the costs $c_M$ and $c_a^b$ are technology-dependent, they are provided as parameters by the user. This flexibility allows the proposed algorithm to generate RSCM architectures optimized for a specific technology node. This work uses the $c_M$ and $c_a^b$ from the prior works [12], [15], [17] based on a commercial 180 nm standard cell library: $c_M = 14$, $c_A^{FA} = 67$, $c_S^{FA} = 75$, and $c_{AS}^{FA} = 93$. The corresponding half-adder costs are counted as 5/9 of their respective full-adder values, which is the ratio of the number of NAND/NOR gates in standard CMOS implementations [18, ch. 3].

1) **Counting full- and half-adders:** Consider a two-input adder with nonzero left and right signed operands, $l$ and $r$ respectively, shifted by $s_l$ and $s_r$. The positions of their most-significant bit are denoted as $msb_l$ and $msb_r$.

* For an adder block ($A$), there is only one case (see Fig. 6):

$$k_A^{FA} = \max(\text{msb}_l, \text{msb}_r) - |s_l - s_r| - 1 \quad (7)$$

$$k_A^{HA} = 1 \quad (8)$$

* For a subtractor ($S$) and adder/subtractor (AS), three cases arise (see Fig. 7a–7c):

- Case (a): $s_l > s_r$, and $s_l < msb_r$:

$$k_{S/AS}^{FA} = \max(\text{msb}_l, \text{msb}_r) - |s_l - s_r| \quad (9)$$

$$k_{S/AS}^{HA} = |s_l - s_r| \quad (10)$$

- Case (b): $s_l \le s_r$:

$$k_{S/AS}^{FA} = \max(\text{msb}_l, \text{msb}_r) - |s_l - s_r| \quad (11)$$

$$k_{S/AS}^{HA} = 0 \quad (12)$$

- Case (c): $s_l > s_r$, and $s_l \ge msb_r$:

$$k_{S/AS}^{FA} = \max(\text{msb}_l, \text{msb}_r) - |s_l - s_r| - 1 \quad (13)$$

$$k_{S/AS}^{HA} = 1 + \text{msb}_r \quad (14)$$

<figure><img src="image_8.png" /><figcaption>Fig. 6: One-bit adders for the adder case, $se$ denotes the sign extension.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 7: One-bit adders for the adder/subtractor and subtractor cases. (a) $s_l > s_r \land s_l < msb_r$. (b) $s_l \le s_r$. (c) $s_l > s_r \land s_l \ge msb_r$. (d) $H^*$ is a half-adder with an extra NOT gate to compute the sign extension, which is used in (c).</figcaption></figure>

2) **Further optimizations based on constant sets:** If both $l$ and $r$ can only multiply by even values, then their LSB can be predicted as 0: the cost function must handle this case. This is captured by considering the minimum shift required across all possible $l$ (resp. $r$) values, which is then selected
as $s_l$ and $s_r$ in the cost function. Furthermore, outputs may be truncated to their maximum two's-complement bitwidth. Similar optimizations can be applied to multiplexers.

### III. EVALUATION

The proposed algorithm is compared against the publicly available DAG Fusion [17] using the number of MUX2 as the cost function. The state-of-the-art TMCCM algorithm [15] is also included, but with results extracted from the original paper, as the code is not available.

The coarse- and fine-grained functions are then discussed, as well as the limitations of the proposed algorithm.

#### A. Comparison with previous works

For each bitwidth $B \in \{5, 6, 8, 10, 12\}$ and for each set size $\#T \in \{4, 8, 16\}$, 100 random sets of positive constants feasible with up to two adders were generated. Note that the proposed algorithm supports signed constants, but it is not the case of DAG Fusion.

The average number of MUX2 is reported in Table II. In the TMCCM algorithm, the cost of an adder/subtractor is the same as an adder. In our cost function, an adder/subtractor costs a MUX2 on top of the adder. To provide an apple-to-apple comparison, Table II shows the MUX2 costs in both cases. The proposed algorithm yields the lowest number of MUX2 for all tested cases, achieving up to 55% savings compared to DAG Fusion.

A significant advantage of the proposed algorithm is that, as Table IV illustrates, it works for $\#T$ up to 256 constants, where previous works seem to be limited at 20. In this table, the algorithm's runtime was capped at 5 minutes on an Intel Gold 6444Y CPU. Even with a large number of constants and limited runtime, the algorithm is capable of finding low-cost RSCMs.

#### B. Runtime considerations and comparison of cost functions

A detailed comparison of the two cost functions on the same benchmarking sets as Table II is presented in Table III. Results indicate that an RSCM optimized for the number of MUX2 is not necessarily optimal under the fine-grained cost model. However, the fine-grained cost function is significantly more computationally expensive, requiring up to 43 times more runtime than the MUX2-based cost.

To mitigate this issue, particularly for larger values of $\#T$, we propose a hybrid cost function. This approach performs a warm restart from the MUX2-optimal solution, fixing the number of MUX2 units and subsequently optimizing for the fine-grained cost.

This strategy substantially reduces computation time, as demonstrated by the ($\#T = 16$, $B = 10$) case in Table III, where the hybrid approach is 5.9 times slower than the coarse-grained cost function, yet 7.2 times faster than the fine-grained cost function, narrowing the estimated area gap to the optimal solution from 11 to 2.9%.

#### C. Limitations of the proposed algorithm

This algorithm is generic, but does not scale in practice beyond 2/3 adders and $B = 12$ bits. Furthermore, its performance is heavily dependent on the specific constants in the target set $T$.

These limitations are a direct consequence of the combinatorial explosion of Eq. (5). We counted how many SCM compute each constant, and results for small constants are illustrated in Fig. 8. For instance there are 632 times more SCMs computing zero with 3 adders than with 2 adders. There are also 1102 times more SCMs computing zero with $B = 16$ than with $B = 4$ bits, because a larger bitwidth permits the use of larger intermediate constants, which in turn allows for more combinations.

<figure><img src="image_10.png" /><figcaption>Fig. 8: Number of different SCMs under various $B$ and number of adders for some small constants.</figcaption></figure>

### IV. APPLICATIONS

#### A. RSCM for machine learning

A motivation of this work was to build efficient multipliers for machine learning applications. With Quantization-Aware Training (QAT), there is no significant degradation of the application-level accuracy when quantizing a floating-point neural network to 8-bit integers for weights and activations. Below 4 bits, the accuracy of the network is degraded.

Fig. 9 shows a RSCM for a set of constants ranging between -20 and 19. If a network is trained by QAT to have all its weights in this set, then these weights may be encoded in 4 bits, but still provide a dynamic range that is almost two bits more.

To support this claim, a ResNet-56 [11] was trained on the CIFAR-100 [19] dataset using QAT. The network weights were quantized either to 4 bits, or to the RSCM constants of Fig. 9.

To accommodate the non-uniform target sets of the RSCMs, the standard Learned Step Size Quantization (LSQ) method [20], originally designed for uniform quantization, was adapted to support non-uniform quantization. This adaptation is illustrated in Fig. 10, where the resulting quantization steps align with the RSCM targeted constants. Note that the LSQ step size $s$ has been set to one in Fig. 10 for the reader convenience.
<table><caption>TABLE II: Average number of MUX2 in 2-adder RSCMs for #T constants of B bits</caption><thead><tr><th rowspan="2">B<br>#T</th><th colspan="3">5</th><th colspan="3">6</th><th colspan="3">8</th><th colspan="3">10</th><th colspan="3">12</th></tr><tr><th>4</th><th>8</th><th>16</th><th>4</th><th>8</th><th>16</th><th>4</th><th>8</th><th>16</th><th>4</th><th>8</th><th>16</th><th>4</th><th>8</th><th>16</th></tr></thead><tbody><tr><td>DAG Fusion (run) [17]</td><td>4.53</td><td>8.48</td><td>13.3</td><td>5.27</td><td>9.34</td><td>13.97</td><td>6.93</td><td>11.51</td><td>16.06</td><td>7.71</td><td>12.74</td><td>18.35</td><td>8.33</td><td>13.89</td><td>19.75</td></tr><tr><td>TMCCM (data from [15])</td><td>3.41</td><td>6.11</td><td>/</td><td>3.74</td><td>6.65</td><td>/</td><td>/</td><td>/</td><td>/</td><td>/</td><td>/</td><td>/</td><td>/</td><td>/</td><td>/</td></tr><tr><td>This work, ± is free</td><td>2.30</td><td>3.24</td><td>4.13</td><td>2.51</td><td>3.92</td><td>5.14</td><td>3.31</td><td>5.21</td><td>6.93</td><td>3.92</td><td>6.03</td><td>8.10</td><td>4.22</td><td>6.75</td><td>9.12</td></tr><tr><td>This work, ± costs a MUX2</td><td>3.33</td><td>4.79</td><td>6.01</td><td>3.55</td><td>5.48</td><td>6.95</td><td>4.53</td><td>6.93</td><td>8.84</td><td>5.13</td><td>7.77</td><td>10.08</td><td>5.44</td><td>8.56</td><td>11.10</td></tr><tr><td>Savings compared to DAG Fusion</td><td>26%</td><td>44%</td><td>55%</td><td>33%</td><td>41%</td><td>50%</td><td>35%</td><td>40%</td><td>45%</td><td>34%</td><td>39%</td><td>45%</td><td>35%</td><td>38%</td><td>44%</td></tr></tbody></table>

<table><caption>TABLE III: #MUX2, area costs and average solving time by constant set for the three cost functions</caption><thead><tr><th rowspan="2">B<br>#T</th><th colspan="3">5</th><th colspan="3">6</th><th colspan="3">8</th><th colspan="3">10</th><th colspan="3">12</th></tr><tr><th>4</th><th>8</th><th>16</th><th>4</th><th>8</th><th>16</th><th>4</th><th>8</th><th>16</th><th>4</th><th>8</th><th>16</th><th>4</th><th>8</th><th>16</th></tr></thead><tbody><tr><td rowspan="3">#MUX2<br>cost</td><td>Coarse-grained</td><td>3.33</td><td>4.79</td><td>6.01</td><td>3.55</td><td>5.48</td><td>6.95</td><td>4.53</td><td>6.93</td><td>8.84</td><td>5.13</td><td>7.77</td><td>10.08</td><td>5.44</td><td>8.56</td><td>11.10</td></tr><tr><td>Fine-grained</td><td>3.44</td><td>5.15</td><td>6.46</td><td>3.80</td><td>6.01</td><td>7.57</td><td>4.96</td><td>7.67</td><td>9.75</td><td>5.70</td><td>8.61</td><td>11.10</td><td>6.02</td><td>9.71</td><td>12.16</td></tr><tr><td>Hybrid</td><td>3.33</td><td>4.79</td><td>6.01</td><td>3.55</td><td>5.48</td><td>6.95</td><td>4.53</td><td>6.93</td><td>8.84</td><td>5.13</td><td>7.77</td><td>10.08</td><td>5.44</td><td>8.56</td><td>11.10</td></tr><tr><td rowspan="3">Area<br>cost</td><td>Coarse-grained</td><td>2303</td><td>2977</td><td>3429</td><td>2601</td><td>3667</td><td>3920</td><td>3272</td><td>4213</td><td>4894</td><td>3772</td><td>4753</td><td>5780</td><td>4137</td><td>5546</td><td>6754</td></tr><tr><td>Fine-grained</td><td>2095</td><td>2652</td><td>3067</td><td>2347</td><td>3041</td><td>3521</td><td>2954</td><td>3785</td><td>4411</td><td>3325</td><td>4282</td><td>5113</td><td>3634</td><td>4842</td><td>5828</td></tr><tr><td>Hybrid</td><td>2102</td><td>2686</td><td>3115</td><td>2381</td><td>3106</td><td>3595</td><td>3007</td><td>3894</td><td>4538</td><td>3439</td><td>4425</td><td>5303</td><td>3732</td><td>5124</td><td>6099</td></tr><tr><td rowspan="3">Runtime<br>(s)</td><td>Coarse-grained</td><td>0.29</td><td>0.48</td><td>1.27</td><td>0.33</td><td>0.86</td><td>2.25</td><td>0.69</td><td>1.78</td><td>3.86</td><td>1.87</td><td>4.00</td><td>11.03</td><td>3.93</td><td>9.71</td><td>27.62</td></tr><tr><td>Fine-grained</td><td>0.31</td><td>0.58</td><td>5.14</td><td>0.36</td><td>1.12</td><td>18.58</td><td>0.72</td><td>2.36</td><td>66.54</td><td>2.03</td><td>8.78</td><td>469.35</td><td>4.40</td><td>20.01</td><td>990.50</td></tr><tr><td>Hybrid</td><td>0.30</td><td>0.54</td><td>6.32</td><td>0.35</td><td>1.04</td><td>13.46</td><td>0.70</td><td>2.11</td><td>65.17</td><td>1.95</td><td>4.84</td><td>65.08</td><td>4.13</td><td>12.33</td><td>123.82</td></tr></tbody></table>

<table><caption>TABLE IV: Average #MUX2 cost for larger #T</caption><thead><tr><th>#T</th><th>B = 8</th><th>B = 10</th><th>B = 12</th></tr></thead><tbody><tr><td>32</td><td>10.53</td><td>12.06</td><td>13.28</td></tr><tr><td>64</td><td>12.66</td><td>15.42</td><td>17.84</td></tr><tr><td>128</td><td>14.14</td><td>18.44</td><td>21.62</td></tr><tr><td>256</td><td>-</td><td>21.08</td><td>26.17</td></tr></tbody></table>

<figure><img src="image_11.png" /></figure>

$$T_i \in \{-20, -13, -8, -6, -5, -3, -2, -1, 0, 1, 2, 4, 5, 7, 12, 19\}$$

<figure><img src="image_12.png" /><figcaption>(a) Representable weights</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(b) LSQ-quantized output $\hat{v}$ as a function of the weight $v$</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(c) LSQ-quantized weight gradients $\hat{v}$ with respect to step size $s$</figcaption></figure>

<caption>Fig. 10: Comparison of INT4 and the RSCM from Fig. 9</caption>

The training procedure is adapted from the LSQ recipe [20], which originally used 90 epochs for ImageNet [21], as CIFAR-100 was not explicitly considered. However, in our case, training was halted after 20 epochs to prevent overfitting. The complete set of training hyperparameters is detailed in Table V. Note that no data augmentation techniques were used to provide a fair comparison between the quantizers.

Furthermore, in both cases, the first and last layers were quantized to INT8 to prevent accuracy loss, as suggested by [22]–[24]. The training was perfomed on a single NVIDIA RTX 4080 GPU with 16GB of GDDR6X memory using PyTorch [25].

As demonstrated by [26], the random seed can have a significant impact on the accuracy of the network. To mitigate this, the training was repeated 10 times with random seeds, and the average best accuracy along with the margin of error at 95% confidence level are reported in Table VI.

This demonstrates that RSCM have potential to be used
<table><caption>TABLE V: Training hyperparameters used for ResNet-56 on CIFAR-100</caption><thead><tr><td>Hyperparameter</td><td>Value</td></tr></thead><tbody><tr><td>Epochs</td><td>20 (early stopping due to overfitting)</td></tr><tr><td>Batch size</td><td>128</td></tr><tr><td>Learning rate</td><td>0.01</td></tr><tr><td>Optimizer</td><td>SGD</td></tr><tr><td>Scheduler</td><td>Cosine annealing [27]</td></tr><tr><td>INT4 Rounding</td><td>Half to even</td></tr><tr><td>RSCM Rounding</td><td>Nearest in T</td></tr><tr><td>Image size</td><td>32×32</td></tr></tbody></table>

<table><caption>TABLE VI: Average accuracy of ResNet-56 on CIFAR-100 with both quantizers</caption><thead><tr><td>Quantizer</td><td>Top-1 Accuracy (%)</td><td>Top-5 Accuracy (%)</td></tr></thead><tbody><tr><td>FP32 baseline [28]</td><td>75.09</td><td>93.05</td></tr><tr><td>INT4</td><td>74.87 ± 0.07</td><td>93.53 ± 0.07</td></tr><tr><td>RSCM from Fig. 9</td><td>75.19 ± 0.03</td><td>93.42 ± 0.04</td></tr></tbody></table>

to quantize weights in a neural network without loss of accuracy compared to FP32, despite their non-uniform and non-symmetrical nature.

## B. Synthesis of an example RSCM

This section compares the RSCM architecture of Fig. 9 to generic 4x8-bit and 6x8-bit multipliers. This choice reflects the RSCM's structure: its constants are selected via a 4-bit control word, yet span a 6-bit signed range.

A naive implementation is also included as a baseline. It performs the same constant multiplications using the decoded constants from the selection signal $i$ by applying a generic multiplier without any multiplierless techniques.

FPGA results (obtained with Vivado 2024.1 for Kintex7, part xc7k70tfbv484-3) are given in Table VII. ASIC results (obtained using Synopsys Design Compiler with a 4nm TSMC technology node) are given in Fig. 11.

In the FPGA case, the RSCM offers the best latency and is marginally more expensive than the 4-bit multiplier while being significantly cheaper than the 6-bit multiplier.

In the ASIC case, the RSCM surpasses the 6-bit multiplier in area beyond a delay threshold of 0.4ns, while achieving comparable power consumption. This suggests a potential operating window where the RSCM offers a favorable trade-off: it may exceed the post-quantization accuracy of a 4-bit multiplier due to its extended 6-bit constant range, while maintaining a smaller area footprint than a full 6-bit multiplier. Additionally, it preserves the use of 4-bit weight encoding, reducing memory requirements.

<table><caption>TABLE VII: Synthesis on FPGA</caption><thead><tr><td></td><td>latency</td><td>area</td></tr></thead><tbody><tr><td>RSCM from Fig. 9</td><td>2.611ns</td><td>31 LUT</td></tr><tr><td>mult 4x8</td><td>3.133ns</td><td>29 LUT</td></tr><tr><td>mult 6x8</td><td>3.182ns</td><td>48 LUT</td></tr><tr><td>naive RSCM</td><td>3.451ns</td><td>54 LUT</td></tr></tbody></table>

<figure><img src="image_15.png" /><figcaption>Fig. 11: ASIC performance metrics.</figcaption></figure>

## C. RSCM for Floating Point (FP) multipliers

<figure><img src="image_16.png" /></figure>

<table><caption>Fig. 12: FP6 multiplier.</caption><thead><tr><td>s<sub>6</sub>...s<sub>0</sub></td><td>T<sub>i</sub></td><td>s<sub>6</sub>...s<sub>0</sub></td><td>T<sub>i</sub></td><td>s<sub>6</sub>...s<sub>0</sub></td><td>T<sub>i</sub></td><td>s<sub>6</sub>...s<sub>0</sub></td><td>T<sub>i</sub></td><td>s<sub>6</sub>...s<sub>0</sub></td><td>T<sub>i</sub></td></tr></thead><tbody><tr><td>1020201</td><td>-60</td><td>1012201</td><td>-20</td><td>0000201</td><td>-5</td><td>0102200</td><td>8</td><td>0111211</td><td>26</td></tr><tr><td>1022210</td><td>-56</td><td>1010011</td><td>-18</td><td>0010210</td><td>-4</td><td>1111000</td><td>9</td><td>0112201</td><td>28</td></tr><tr><td>1022200</td><td>-52</td><td>1002200</td><td>-16</td><td>0000200</td><td>-3</td><td>0112001</td><td>10</td><td>1110011</td><td>30</td></tr><tr><td>1020111</td><td>-48</td><td>1000201</td><td>-15</td><td>0102110</td><td>-2</td><td>0121000</td><td>11</td><td>0112211</td><td>32</td></tr><tr><td>1022201</td><td>-44</td><td>1012010</td><td>-14</td><td>0011001</td><td>-1</td><td>0110210</td><td>12</td><td>0120200</td><td>36</td></tr><tr><td>1022211</td><td>-40</td><td>1011100</td><td>-13</td><td>0020000</td><td>0</td><td>0111101</td><td>13</td><td>1110111</td><td>40</td></tr><tr><td>1020011</td><td>-36</td><td>0020101</td><td>-12</td><td>0101010</td><td>1</td><td>1102101</td><td>14</td><td>1112201</td><td>44</td></tr><tr><td>1012210</td><td>-32</td><td>1002010</td><td>-11</td><td>1102110</td><td>2</td><td>0100201</td><td>15</td><td>0120111</td><td>48</td></tr><tr><td>1010201</td><td>-30</td><td>0012010</td><td>-10</td><td>1101010</td><td>3</td><td>0122001</td><td>16</td><td>0122201</td><td>52</td></tr><tr><td>1012200</td><td>-28</td><td>0021100</td><td>-9</td><td>0101001</td><td>4</td><td>1102111</td><td>18</td><td>0122211</td><td>56</td></tr><tr><td>1011210</td><td>-26</td><td>1001110</td><td>-8</td><td>1002011</td><td>5</td><td>1100111</td><td>20</td><td>1110211</td><td>60</td></tr><tr><td>0022210</td><td>-24</td><td>1002000</td><td>-7</td><td>1112000</td><td>6</td><td>1111111</td><td>22</td><td></td><td></td></tr><tr><td>1021111</td><td>-22</td><td>0021111</td><td>-6</td><td>1101011</td><td>7</td><td>1112101</td><td>24</td><td></td><td></td></tr></tbody></table>

With a significant improvement of the target set size, our RSCMs can be applied to replace integer multipliers in more complex cases than possible before. Motivated by machine learning acceleration, we used our algorithm on a set of constants corresponding to the 63 possible values of the E2M3 FP6 format, one of several microscaling formats described in [29]. The resulting RSCM, is presented in Fig. 12.

However, an issue arises when mapping the 6 bits of the
constant index *i* onto the RSCM selection variables *s*<sub>*k*</sub> as it has more possible configurations than output constants. It was actually also the case on Fig. 9 (if one decomposes the MUX4 into 3 MUX2, making it 5 selection variables with the other MUX2 and the adder/subtractor), but there was a trivial sharing of bit *i*<sub>3</sub> between two MUX2.

In Fig. 12, this mapping is no longer straightforward, as the FP6 RSCM configuration can be encoded using 10 bits (8 MUX2 and the two adder/subtractor control bits), while only 6 bits to index the 63 outputs are needed. The resulting decoding overhead depends on the chosen binary encoding of *T*. In previous works [13], [15], [17] this issue was left to the synthesis tool. Future work must address this, either by minimizing this overhead as a post-processing step, or by integrating the maximization of the sharing of configuration bits directly into the model.

V. CONCLUSION & PERSPECTIVES

In this paper, we presented a novel algorithm that leverages CP and B&P to generate optimized RSCMs for a given set of constants. With an exhaustive, yet reasonably fast, exploration of the design space and new fine-grained optimization metric, the proposed approach demonstrates superior results compared to previous methods. Our approach is currently limited by the number of adders and the maximum target constant bitwidth, which could be improved by restricting the design space exploration at the cost of optimality.

For the machine learning application, which tolerates low
bitwidths, an RSCM architecture was successfully used for
weight quantization without any loss in model accuracy.
Synthesis results confirmed its practical viability for hardware
implementation when compared to generic integer multipliers,
particularly in resource-constrained settings. Moreover, thanks
to its extended dynamic range, the RSCM enables efficient
encoding of weights, hence demonstrating a potential for an
improved resource utilization in machine learning applications.
Future work will explore the development of a dedicated DNN
accelerator based on generated RSCMs.

ACKNOWLEDGMENTS

Many thanks to Orégane Desrentes for the VLSI synthesis.

REFERENCES

[1] F. de Dinechin and M. Kumm, *Application-Specific Arithmetic*. Springer, 2024.

[2] J. Thong and N. Nicolici, "A novel optimal single constant multiplication algorithm," in *Proceedings of the 47th design automation conference*, 2010, pp. 613–616.

[3] Y. Voronenko and M. Püschel, "Multiplierless multiple constant multi-plication," *ACM Transactions on Algorithms (TALG)*, vol. 3, no. 2, pp. 11-es, 2007.

[4] M. Kumm, P. Zipf, M. Faust, and C.-H. Chang, "Pipelined adder graph optimization for high speed multiple constant multiplication," in *2012 IEEE International Symposium on Circuits and Systems (ISCAS)*. IEEE, 2012, pp. 49-52.

[5] S. S. Demirsoy, I. Kale, and A. Dempster, “Reconfigurable multiplier blocks: Structures, algorithm and applications,” *Circuits, Systems & Signal Processing*, vol. 26, pp. 793–827, 2007.

[6] Z. Fu and W. Ye, “A new design of low hardware cost and low power programmable FIR filters,” *IEEE Transactions on Circuits and Systems II: Express Briefs*, 2023.

[7] J. Faraone, M. Kumm, M. Hardieck, P. Zipf, X. Liu, D. Boland, and P. H. Leong, “Addnet: Deep neural networks using FPGA-optimized multipliers,” *IEEE Transactions on Very Large Scale Integration (VLSI) Systems*, vol. 28, no. 1, pp. 115–128, 2019.

[8] K. Kim, H.-J. Lee, and X. T. Nguyen, “Reconfigurable one-adder multiplication for cnn acceleration,” in *International Conference on Electronics, Information, and Communication (ICEIC)*. IEEE, 2024.

[9] N. Bain, R. Guizzetti, E. Taly, A. Oudrhiri, B. Paille, P. Urard, and F. Pérot, “Quantization modes for neural network inference: ASIC implementation trade-offs,” in *International Joint Conference on Neural Networks (IJCNN)*. IEEE, 2023.

[10] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “ImageNet classification with deep convolutional neural networks,” *Advances in neural information processing systems*, vol. 25, 2012.

[11] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in *Proceedings of the IEEE conference on computer vision and pattern recognition*, 2016, pp. 770–778.

[12] J. Chen and C.-H. Chang, “High-level synthesis algorithm for the design of reconfigurable constant multiplier,” *IEEE transactions on computer-aided design of integrated circuits and systems*, vol. 28, no. 12, pp. 1844–1856, 2009.

[13] K. Möller, M. Kumm, M. Kleinlein, and P. Zipf, “Reconfigurable constant multiplication for FPGAs,” *IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems*, vol. 36, no. 6, pp. 927–937, 2016.

[14] K. Möller, M. Kumm, M. Garrido, and P. Zipf, “Optimal shift re-assignment in reconfigurable constant multiplication circuits,” *IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems*, vol. 37, no. 3, pp. 710–714, 2017.

[15] C. Eleftheriadis and G. Karakonstantis, “Optimal adder-multiplexer co-optimization for time-multiplexed multiplierless architectures,” *IEEE Transactions on Circuits and Systems I: Regular Papers*, 2023.

[16] N. Fiege, M. Kumm, and P. Zipf, “Bit-level optimized constant multiplication using boolean satisfiability,” *IEEE Transactions on Circuits and Systems I: Regular Papers*, vol. 71, no. 1, pp. 249–261, 2023.

[17] P. Tummeltshammer, J. C. Hoe, and M. Puschel, “Time-multiplexed multiple-constant multiplication,” *IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems*, vol. 26, no. 9, pp. 1551–1563, 2007.

[18] M. M. Mano, K. Charles R. M. Tom et al., *Logic and computer design fundamentals*. Pearson Education Limited, 2016.

[19] A. Krizhevsky, V. Nair, and G. Hinton, “CIFAR-100 (Canadian Institute for Advanced Research).” [Online]. Available: http://www.cs.toronto.edu/~kriz/cifar.html

[20] S. K. Esser, J. L. McKinstry, D. Bablani, R. Appuswamy, and D. S. Modha, “Learned Step Size Quantization,” *arXiv:1902.08153 preprint*, 2020.

[21] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “ImageNet: A large-scale hierarchical image database,” in *2009 IEEE Conference on Computer Vision and Pattern Recognition*, 2009, pp. 248–255.

[22] J. Choi, Z. Wang, S. Venkataramani, P.-J. Chuang, V. Srinivasan, and K. Gopalakrishnan, “PACT: Parameterized clipping activation for quantized neural networks,” *arXiv:1805.06085 preprint*, 2018.

[23] S. Zhou, Y. Wu, Z. Ni, X. Zhou, H. Wen, and Y. Zou, “Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients,” *arXiv:1606.06160 preprint*, 2016.

[24] I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio, "Quantized neural networks: Training neural networks with low precision weights and activations," *journal of machine learning research*, vol. 18, no. 187, pp. 1–30, 2018.

[25] A. Paszke, “Pytorch: An imperative style, high-performance deep learning library,” *arXiv:1912.01703 preprint*, 2019.

[26] R. Wightman, H. Touvron, and H. Jégou, “Resnet strikes back: An improved training procedure in timm,” *arXiv:2110.00476 preprint*, 2021.

[27] I. Loshchilov and F. Hutter, “SGDR: Stochastic gradient descent with warm restarts,” *arXiv:1608.03983 preprint*, 2016.

[28] O. Sémery, “Pytorchcv: Computer vision models on pytorch,” https://github.com/osmr/pytorchcv, 2024, accessed: 2025-04-14.

[29] B. D. Rouhani, N. Garegrat, T. Savell et al., “OCP Microscaling Formats (MX) Specification,” *Open Compute Project*, 2023. [Online]. Available: https://www.opencompute.org/documents/ocp-microscaling-formats-mx-v1-0-spec-final-pdf