Algoritmi di elaborazione e rilevazione di potenziali evocati

U à S N

niversit degli tudi di apoli

F ederico II

Dipartimento di Ingegneria Elettrica e

delle Tecnologie dell’Informazione

Classe di Laurea in Ingegneria dell’Informazione, Classe n. L.8

Corso di Laurea in Ingegneria Elettronica

Elaborato di Laurea

Algoritmi di elaboraizone e rilevazione di potenziali evocati

Anno Accademico

2019/2020

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 the median as the result of the mean of

the two median values and The control logic units

M1 M2.

(CLU ) consist of counters controlling the assertion of the

flags. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.11 caption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.1 Partial product matrix for unsigned multiplier. . . . . 41

×

8 8

3.2 Two’s complement PPM for multiplier. . . . . . . . . 43

×

8 8

3.3 Mixed-operands PPM for multiplier. . . . . . . . . . . 44

×

8 8

3.4 Unsigned array multiplier with critical path at the

×

8 8

bottom right corner. . . . . . . . . . . . . . . . . . . . . . . 45

3.5 Rectangular unsigned array multiplier. . . . . . . . . . 46

×

8 8

3.6 Rectangular signed array multiplier. . . . . . . . . . . 47

×

8 8 xvi

3.7 Wallace tree reduction for Partial Product Matrix

×

8 8

(PPM). Full rectangle: full-adder; dotted rectangle: half-

adder. In each step, is the height of reduced partial prod-

h

uct matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.8 Dadda tree reduction for PPM. Full rectangle: full-

×

8 8

adder; dotted rectangle: half-adder. In each step, is the

h

height of reduced partial product matrix. The number of

FAs and HAs is decreased in comparison to Figure 3.7. . . . 50

4.1 Unsigned multiplier operand segmentation for . 57

n=12, m=8.

4.2 Unsigned multiplier: NMED as a function of for the cases

n,

Solid lines: stan-

m = n/2, m = 2 + n/2, m = 4 + n/2.

dard SSM; dashed lines: SSM with proposed error correc-

tion technique. . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.3 Unsigned Static Segment Method (SSM) partial product

matrix with different cases for and and pro-

α α (a) (b)

A B

posed error correction . . . . . . . . . . . . 63

(n = 8, m = 5).

4.4 Error histogram of Standard design with suggested

(a) (b)

error correction for an unsigned SSM. . . . . . . 64

n=8, m=4

4.5 Hardware architecture of unsigned SSM with error correc-

tion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

4.6 Proposed signed multiplier operand segmentation for

(a) Error histogram for an

n = 12, m = 8; n = 8, m = 4

(b)

signed SSM. . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

xvii

4.7 Trade-off between power savings and accuracy of unsigned

multipliers. Each data point represents a multiplier; the

closer the point is to the upper-left corner, the better the

trade-off. The green line represents the Pareto-optimal fron-

tier, which is determined by multipliers that have the op-

timum power-accuracy trade-off. Power decrease com-

(a)

pared to NMED; Power reduction compared to MRED. 74

(b)

4.8 Trade-off between power saving and accuracy in signed mul-

tipliers. Each point corresponds to a multiplier, the closer

the point to the top-left corner, the better the trade-off.

The green line is the Pareto-optimal frontier, given by mul-

tipliers with the best power-accuracy trade-off. Power

(a)

reduction compared to NMED; Power reduction com-

(b)

pared to MRED. . . . . . . . . . . . . . . . . . . . . . . . . 76

4.9 Kernels for Gaussian smoothing (left) and for motion effect

(right). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

4.10 Image Gaussian filtering of “cameraman” image with un-

signed multipliers. original image; reference re-

(a): (b):

sult, obtained by using an exact multiplier; images:

(c)-(f )

results using approximate multipliers. . . . . . . . . . . . . . 79

4.11 Trade-off between power saving and SSIM for edge detection

application. Each point corresponds to a multiplier, the

closer the point to the top-right corner, the better the trade-

off. The green line is the Pareto-optimal frontier, given by

multipliers with the best power-SSIM trade-off. . . . . . . . 82

5.1 Floating point multiplication flowchart describing: ex-

1.

ponents addition, mantissa multiplication, mantissa

2. 3.

normalization and exception handling, mantissa round-

4.

ing and normalization and sign extraction. . . . . . . . . 90

5.

xviii

5.2 A simplified FP multiplication architecture with optimized

mantissa multiplier. The approximate designs will replace

the multiplier in the red box indicating the MAA unit. . . . 91

5.3 Segmentation of the mantissa in the case bits

n = 8

Ma m

and bits. Approximation error is introduced when

m = 5

the upper portion of the m