Multiple Real-Constant Multiplication for Computationally Efficient Implementation of Digital Transforms

Abstract

The need to multiply signals by vectors (or matrices) of constants is fundamental and frequently arises in many areas of electrical and computer engineering.

In their hardware implementations, performance issues such as circuit area, delay, and power consumption heavily influence the design process.

It is well known that multiplication of a signal by a constant can be implemented multiplierless as a network of shifts and additions, and that these computational networks, termed shift-add networks, can lend to higher performing circuit implementations than when using general multipliers.

There is a rich body of work on the optimization of shift-add networks, known as the multiple constant multiplication (MCM) problem.

However, the optimization strategies that have been developed for the MCM traditionally assume that the vector multiplications being optimized always stem from integer constants.

This assumption breaks down for many real-world applications, where the target constants for MCM optimization are real numbers rather than integers.

In these situations there is flexibility in how constants are quantized in digital circuits that can be leveraged.

Thus, it is desirable to have a method of jointly optimizing both the constant quantization error and the shift-add network simultaneously.

This dissertation addresses this need by providing a problem framework and algorithms for joint quantization/MCM optimization and, through a series of experiments, shows that there is a potential for tremendous benefit when the optimization of quantization and shift-add networks is executed in one unified problem framework.

After reviewing the relevant work, this dissertation rigorously develops the aforementioned joint optimization framework, describing the metrics used for quantization error, and culminates in a formal problem statement.

We call this joint optimization problem the multiple real-constant multiplication problem (MRCM) in order to distinguish it from the traditional MCM problem that operates exclusively with integer constants, which we hereafter refer to as the multiple integer-constant multiplication (MICM) problem.

Then, we consider three different cost models used for evaluating shift-add networks and, with each model, we determine the potential advantages of using our MRCM framework over the traditional MICM approach.

First, we consider the traditional adder-count cost model.

We start by formally defining the MRCM problem in the context of this cost model, and then describe a series of theoretical developments centered around finitizing and pruning the search space, leading to an efficient algorithm for solving the problem.

Next, via extensive randomized experiments, we show that our joint framework leads to a reduction on the number of adders by 15%–60% on moderate size problems.

In particular, for vectors of arbitrary constants, we show a possibility for 20%–60% reduction with less than 10% vector approximation error for both frameworks, whereas for vectors of low-pass filter coefficients, a 15%–30% reduction is possible without exceeding 10% error in frequency response.

Second, we consider an adder-bits cost model, whereby instead of simply counting the number of adders, we compute the combined bitwidth of all the adders.

To solve the MRCM problem in this context, we introduce two search algorithms—one greedy and one optimal, each guided by a novel MRCM-aware heuristic.

Next, we discuss a randomized experiment, in which we compare both algorithms to an MICM-targeted heuristic.

We observe that the greedy search finds solutions with an average cost improvement of 13% over the MICM solution with the trials considered, and the optimal search finds an additional improvement of 6%.

Third, we consider a prominent gate-level cost model from the literature that.

This gate-level model consider the bitwidths of an adder's inputs and output along with the relative alignment of the inputs/output due to bit shifting, when computing the adder cost.

To solve the MRCM problem in this context, a novel greedy algorithm is developed that uses a functional programming approach to solving the MRCM problem.

Next, we experimentally show this algorithm to offer an improvement of up to 18%, over a competing MICM algorithm, on small instances having 20 8-bit constants, increasing to up to 59% improvement on larger instances having 80 5-bit constants.

Finally, we conclude the work by offering recommendations for possible future work in the development of efficient MRCM algorithms and novel problem formulations for optimizing MCM circuits.