Approximate Computing

Università degli Studi di Napoli Federico II

Ph.D. Program in

Information Technology and Electrical Engineering

XXXVI Cycle

Thesis for the Degree of Doctor of Philosophy

Approximating Hardware

Arithmetic Circuits

by

Gerardo Saggese

Advisor: Prof. Antonio Giuseppe Maria Strollo

Abstract

Brain-Machine Interface (BMI) systems have gained attention for direct com-

munication between brain and outside environment. The spike detection algo-

rithm is crucial for extracting neural information from recorded signals. Integrat-

ing spike detection algorithms with proximity calculations improves the efficiency

of BMI systems and enables real-time processing for responsive device control.

This reduction in computational intensity and power consumption promotes low-

power, energy-efficient BMI hardware.

The main objective of my research activity is to overcome the challenges faced

by conventional spike detection algorithms, especially in terms of computational

intensity and power consumption, when applied to implantable BMI systems with

a large number of channels. To this end, spike detection algorithms tailored to

BMI applications have been researched and developed, and their performance

evaluated using metrics such as accuracy, computational effort and resource re-

quirements.

Another research topic that builds on this foundation is the approximate

computation paradigm. Multipliers are essential building blocks in many signal

processing tasks, including spike detection algorithms. Therefore, I have been

working on developing approximate multipliers to reduce the complexity and

computational cost of multiplication operations while maintaining an acceptable

level of accuracy, resulting in improved computational efficiency and reduced

power consumption. The use of approximate multipliers in spike detection algo-

rithms can improve the overall efficiency and performance of the spike detector

and thus the BMI system.

Overall, my research aims to advance the field of BMI by addressing the

computational challenges associated with spike detection algorithms and explor-

ing the benefits of approximate computational techniques. The results of my

research have the potential to provide valuable insights into optimising compu-

tational resources, power efficiency and real-time processing capabilities, paving

the way for more efficient and practical BMI systems.

brain-machine interface, spike detector, approximate com-

Keywords:

puting, low-power, approximate multipliers.

Sintesi in lingua italiana

I sistemi di interfacciamento uomo-macchina BMI hanno attirato l’attenzione

per la possibilità di una comunicazione diretta tra il cervello e il mondo esterno.

Un elemento fondamentale è l’algoritmo di rilevazione degli impulsi elettrici, che

permette di estrarre le informazioni neurali dai segnali registrati. L’integrazione

di questi algoritmi con tecniche di calcolo approssimato migliora l’efficienza dei

sistemi BMI, aprendo la strada ad implementazioni hardware a basso consumo

energetico per l’elaborazione in tempo reale dei segnali neuronali, finalizzata al

controllo di dispositivi esterni.

Il principale obiettivo della mia attività di ricerca è superare le sfide che i

tradizionali algoritmi di rilevazione degli spike incontrano nell’ambito dei sistemi

BMI impiantabili a multi canale, soprattutto in termini di complessità e consumo

energetico. A tal fine, ho studiato e sviluppato algoritmi di rilevazione degli

spike, valutandone le prestazioni in termini di accuratezza, complessità e risorse

utilizzate.

Un altro tema di ricerca correlato a queste fondamenta è il paradigma del cal-

colo approssimato. I moltiplicatori sono elementi essenziali in molte operazioni

di elaborazione del segnale, inclusi gli algoritmi di rilevazione degli spike. Per-

tanto, mi sono dedicato allo sviluppo di moltiplicatori approssimati per ridurre

la complessità e il costo computazionale delle operazioni di moltiplicazione, pur

mantenendo un livello accettabile di accuratezza. Ciò comporta un miglioramento

dell’efficienza computazionale e una riduzione del consumo energetico. L’utilizzo

di moltiplicatori approssimati negli algoritmi di rilevazione degli spike può miglio-

rare l’efficienza complessiva del rilevatore di spike e, di conseguenza, del sistema

BMI.

Complessivamente, la mia ricerca mira a far progredire il campo della BMI

affrontando le sfide computazionali legate agli algoritmi di rilevazione degli spike e

ad esplorare i vantaggi delle tecniche di calcolo approssimate. I risultati ottenuti

possono fornire indicazioni preziose per ottimizzare le risorse computazionali,

migliorare l’efficienza energetica e le capacità di elaborazione in tempo reale,

aprendo la strada a sistemi BMI più efficienti e pratici.

interfaccia uomo-macchina, impulsi neurali, calcolo

Parole chiave:

approssimato, efficienza energetica, motliplicatori approssimati

Contents

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i

Sintesi in lingua italiana . . . . . . . . . . . . . . . . . . . . . . . ii

Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . vi

List of Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . xi

List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi

List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiv

1 Introduction 1

1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Why Approximation Computing? . . . . . . . . . . . . . . . 5

1.3 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Non-Linear Energy Operator-Based Spike Detection Algo-

rithms 11

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Metrics & Methods . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.1 Evaluation Metrics . . . . . . . . . . . . . . . . . . . 14

2.2.2 Neural Recording . . . . . . . . . . . . . . . . . . . . 15

2.3 Non-linear Energy Operators . . . . . . . . . . . . . . . . . 16

2.4 Noise estimate . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

iii

2.5.1 Software Evaluation . . . . . . . . . . . . . . . . . . 24

2.5.2 VLSI Implementation . . . . . . . . . . . . . . . . . 28

2.5.3 State-of-the-Art . . . . . . . . . . . . . . . . . . . . . 34

2.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 Binary Multiplier 39

3.1 Binary multiplication . . . . . . . . . . . . . . . . . . . . . . 39

3.1.1 Partial Product generation . . . . . . . . . . . . . . 40

3.1.2 Array multiplier . . . . . . . . . . . . . . . . . . . . 44

3.1.3 Tree multipliers . . . . . . . . . . . . . . . . . . . . . 46

3.2 Evaluation Metrics . . . . . . . . . . . . . . . . . . . . . . . 51

3.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4 Static Segmentation Technique 55

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . 56

4.2 Unsigned SSM: Error analysis and Correction . . . . . . . . 57

4.3 Signed SSM: Error analysis and Correction . . . . . . . . . 63

4.4 Sign-Modulus Representation . . . . . . . . . . . . . . . . . 69

4.5 VLSI Implementation Results . . . . . . . . . . . . . . . . . 71

4.5.1 Unsigned Multipliers: . . . . . . . . . . . . . . . . . 71

4.5.2 Signed Multipliers: . . . . . . . . . . . . . . . . . . . 75

4.6 Image processing Results . . . . . . . . . . . . . . . . . . . . 77

4.6.1 Image Filtering . . . . . . . . . . . . . . . . . . . . . 77

4.6.2 Edge Detection using Sobel operator . . . . . . . . . 81

4.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

5 Floating-Point Multiplier 85

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

5.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 86

5.3 IEEE-754 Standard for Floating-Point Arithmetic . . . . . . 88

iv

5.3.1 Numerical Format . . . . . . . . . . . . . . . . . . . 88

5.3.2 Floating-point Multiplication Algorithm . . . . . . . 89

5.4 Static Segmentation on Modified Mantissa Product . . . . . 92

5.4.1 Error Analysis and Correction . . . . . . . . . . . . . 97

5.4.2 Error Metrics Results . . . . . . . . . . . . . . . . . 98

5.4.3 VLSI Implementation Results . . . . . . . . . . . . . 100

5.4.4 HDR Tone Mapping . . . . . . . . . . . . . . . . . . 104

5.5 Configurable Floating-point Multiplier . . . . . . . . . . . . 107

5.5.1 Error Metrics Results . . . . . . . . . . . . . . . . . 110

5.5.2 VLSI Implementation Results . . . . . . . . . . . . . 112

5.5.3 HDR Tone Mapping . . . . . . . . . . . . . . . . . . 115

5.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

6 Spike Detector Efficiency Enhancement through Approxi-

mate Multipliers and Latch-Based Memory 119

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

6.2 Approximate SSM Multipliers Inference . . . . . . . . . . . 120

6.3 Towards the Design of Efficient Memory . . . . . . . . . . . 126

6.3.1 Latch-based RAM . . . . . . . . . . . . . . . . . . . 127

6.4 Approximate Multichannel VLSI Implementation . . . . . . 129

6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

7 Conclusions 133

A Floating Point Fused PPM 137

A.1 Segmentation Analysis Fused PPM . . . . . . . . . . . . . . 137

A.2 Error analysis for Fused PPM . . . . . . . . . . . . . . . . . 140

Bibliography 143

Author’s Publications 155

v

Acknowledgements

The author’s work has been carried out in the framework of the PRIN

2017 (Progetti di Rilevante Interesse Nazionale) project “Autonomous In-

vivo Brain-Machine-Interface in 28nm-CMOS technology with Ultrasound-

based Power-Harvester and Communication-Link (Brain28nm)”

(Prot. 20177MEZ7T). vi

List of Acronyms and Symbols

The following acronyms and symbols are used throughout the thesis.

3-Point Median Mean Distance

3MMD Absolute Average

AA Approximating Computing

AC Analogue-Digital Converter

ADC Absolute Differential Operator

ADO Actual Potential

AP Application-Specific Integrated Circuit

ASIC Amplitude Slope Operator

ASO Brain-Computer Interface

BCI Brain-Machine Interface

BMI Ceil operator

⌈⌉ Run-time Configurable Floating Point Multiplier

CFPM Clock Gate Latch

CGL Complementary Metal-Oxide Semiconductor

CMOS Convolutional Neural Network

CNN vii

Carry-Propagate Adder

CPA Central Processing Unit

CPU Corrected Static Segmented Floating Point Multiplier

cSSFPM Corrected Static Segment Method

CSSM Corrected Static Segmented Multiply-and-Add

cSSMAA Double Precision

DP Digital Signal Processor

DSP Electrocorticography

ECoG Error Distance

ED Electroencephalography.

EEG Mean Square Error

E M S Entire-Spike Activity

ESA Full-Adder

FA False Alarm Rate

FAR Flip-Flop

FF Floor operator

⌊⌋ False Negatives

FN False Positives

FP Field Programmable Gate Array

FPGA Floating Point Multiplier

FPM Floating Point Unit

FPU Graphics Processing Unit

GPU Half-Adder

HA Hardware Description Language

HDL viii

High Dynamic Range

HDR Haff Precision

HP Infinite Impulse Response

IIR Local Field Potential

LFP Leading One Detector

LOD Least Significant Bit

LSB Long-Short Term Memory

LSTM Multiply-and-Add

MAA Multiply-and-Accumulate

MAC Median Absolute Deviation

MAD Maximum Absolute Error

MAV Microcontroller Unit

MCU Modified Full-Adder

MFA Modified Half-Adder

MHA Mean Relative Error Distance

MRED Most Significant Bit

MSB Mean Squared Error

MSE Multi-Unit

MUA Mean Error

µ E Non-linear Energy Operator

NEO Normalized Mean

NM Normalized Max Error Distance

NmaxED Normalized Mean Error Distance

NMED Negating-Modified Full-Adder

NMFA ix

Neural Network

NN Number of Effective Bits

NoEB Power-Area Product

PAP Principal Component Analysis

PCA Partial Product Matrix

PPM Partial Product Reduction Tree

PPRT Peak Signal-to-Noise-Ratio

PSNR Read Address Decoder

RAD Random-Access Memory

RAM Relative Error Distance

RED Root-mean-square error

RMSE Recurrent Neural Network

RNN Read-Only Memory

ROM Smoothed ASO

SASO Stochastic Computing

SC Standard Cell Memory

SCM Standard Delay Format

SDF Specialized Half-Adder

SHA SRAM Macrocell

SMM Smoothed NEO

SNEO Signal-to-Noise Ratio

SNR Single Precision

SP Static Segmented Floating Point Multiplier

SSFPM Structural Similarity Index Measure

SSIM x

Mean Structural Similarity Index

SSIM Static Segment Method

SSM Static Segmented Multiply-and-Add

SSMAA Standard Deviation

STD Single-Unit

SUA Support Vector Machines

SVM Toggle Count Format

TCF Three Dimensional Minimization

TDM True Positives

TP True Positive Rate

TPR Very High-speed integrated circuit Hardware Description

VHDL Language

Very-Large-Scale Integration

VLSI Voltage Over-Scaling

VOS Winsorization

WA Write Address Decoder

WAD xi Draft

List of Figures

1.1 BMI systems standard workflow. Modules shown: different

recording probes, pre-processing, feature extraction, classi-

fication/prediction techniques, and an use cases for inten-

tion/movement decoding control. . . . . . . . . . . . . . . . 2

1.2 An example of wireless online systems pre-process the record-

ing on-implant for bandwidth reduction, where classifica-

tion and proper tuning are performed externally and offline.

*Assuming a firing rate of 20 Hz with binary data stream

and 128 channels. . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Approximate computing methodology applied in the Sobel

edge detection method. The pre-processed images, still pre-

servers the meaningful information about the edges. . . . . 7

xiii

2.1 The workflow outlines the proposed method’s subsequent

processing stages, whilst the dataflow depicts the effect of

each block on the input signal from the recording matrix up

to detection. The workflow begins with a filtering step de-

signed to reduce out-of-band noise. Following this, a spike

enhancement module is employed to enhance the differenti-

ation between spikes and background noise. The workflow

concludes with the application of a threshold, typically esti-

mated based on the background noise, for the identification

and extraction of spikes. . . . . . . . . . . . . . . . . . . . . 12

2.2 Example of simulated data used by The

(a)

Wave_clus.

three template spike shapes used to generate the signal. (b)

The previous spikes embedded in the background noise. (c)

The same data with a magnified timescale. Note the vari-

ability of spikes from the same class due to the background

noise. The black dot line represents the estimate noise stan-

dard deviation. . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3 A 5-second frame of real extracellular recording. The spikes

identified and belonged to the same neuron (i.e., cluster)

are highlighted with the same color. . . . . . . . . . . . . . 18

xiv

2.4 Synthetic extracellular spike (grey) after applying the en-

ergy operators. NEO (blue), ASO (red) and ADO (yel-

(a)

low). The tuning parameter is 4. It can be seen that the

spike at 0.7 ms is more enhanced by the ASO operator.

However, with all the operators the energy signal provides

for the same spike two peaks that might cause a double de-

tection. Another reason to employ a smoothing window is

to limit the detection of the same spike many times. (b)

Effect on the same spike with cascade of energy operators

ADO and ASO with tuning parameter 4 and 2, respectively.

Here the double peaks effect is reduced. . . . . . . . . . . . 19

2.5 Estimation of the noise level using different noise esti-

(a)

mations at various firing rates by constructing a segment of

10 seconds of background noise with unit standard devia-

tion and introducing a unique spike class with varied firing

rates in succeeding runs. Mean relative error bar when

(b)

determining the noise level (zero firing rate) over different

window length M. . . . . . . . . . . . . . . . . . . . . . . . . 23

2.6 Scale factor effect on average accuracy and specificity

(a)

of the energy series operator where the threshold is the

real noise level. As the scale factor increase, the number

of false positives (FAR) decreases, but this might lead to

a loss of true spikes too. Average accuracy and FAR

(b)

curves when the real noise value is replace with the noise

estimate: Median Absolute Deviation (MAD) and 3-Point

Median Mean Distance (3MMD). . . . . . . . . . . . . . . . 25

2.7 Accuracy results of energy operators on four synthetic datasets

over four different noise levels: SNEO, SASO, and our pro-

posal. The smoothed versions are considered with a tuning

parameter of 4 and a Hamming window of length 17. . . . . 26

xv

2.8 Detection performance on the real dataset discussed in 2.2.2.

Sensitivity and Specificity of the detector under

(a) (b)

investigation. The scale factor might be lowered to increase

the number of the true spikes to further process them offline. 28

2.9 Hardware block scheme of the proposed spike detector. (a)

IIR 2 filter based on the direct form I with 10-bit width co-

nd

efficients. The numerator coefficients were scaled to prevent

overflow. The fixed-point filter maintains its stability. (b)

Series of energy operator ADO and ASO with tuning pa-

rameter 4 and 2, respectively. detection block, together

(c)

with the multiplication of the noise estimate with the scale

factor The bit-width of has chosen to be the same for

C. C

all the investigated algorithms. The grey block referred as

"MEM" represents the memory block unit. . . . . . . . . . 29

2.10 3MMD noise estimate block and cumulative his-

(a) (b)

togram of the median operator where the bin structure is

illustrated in the bottom corner. Being even, two indices

M

are used to estimate th