# Special Session: Reliability Analysis for ML/AI Hardware

Shamik Kundu1, Kanad Basu1, Mehdi Sadi2, Twisha Titirsha3, Shihao Song3, Anup
Das3, Ujjwal Guin2
1Department of Electrical & Computer Engineering, University of Texas at
Dallas<EMAIL_ADDRESS>
2Department of Electrical & Computer Engineering, Auburn University
({mehdi.sadi<EMAIL_ADDRESS>
3Department of Electrical & Computer Engineering, Drexel University
<EMAIL_ADDRESS>
###### Abstract

Artificial intelligence (AI) and Machine Learning (ML) are becoming pervasive
in today’s applications, such as autonomous vehicles, healthcare, aerospace,
cybersecurity, and many critical applications. Ensuring the reliability and
robustness of the underlying AI/ML hardware becomes our paramount importance.
In this paper, we explore and evaluate the reliability of different AI/ML
hardware. The first section outlines the reliability issues in a commercial
systolic array-based ML accelerator in the presence of faults engendering from
device-level non-idealities in the DRAM. Next, we quantified the impact of
circuit-level faults in the MSB and LSB logic cones of the Multiply and
Accumulate (MAC) block of the AI accelerator on the AI/ML accuracy. Finally,
we present two key reliability issues – circuit aging and endurance in
emerging neuromorphic hardware platforms and present our system-level approach
to mitigate them.

###### Index Terms:

Machine learning, deep learning accelerator, neuromorphic computing,
reliability

##  I Impact on DRAM Faults on DNN Accelerators

Deep Neural Networks (DNNs), with their ever increasing computing power are
gaining momentum over classical machine learning and computer vision
algorithms. As a result, DNNs are being extensively deployed across real-time
data driven applications on resource constrained Internet-of-Things (IoT) edge
devices. Conventional CPU architectures tend to lose out on implementing the
computational complexity of state-of-the-art DNNs, which propelled the
development of cost and energy efficient application-specific neural network
accelerators. Both industry and academia responded to this emerging community
of DNN accelerators by developing several purpose-built inference hardware [1,
2, 3]. Google’s Tensor Processing Unit (TPU) is one such accelerator that
achieves 15–30$\times$ higher performance and 30–80$\times$ higher
performance-per-watt over traditional CPUs and GPUs [1]. These custom built
DNN accelerators find their application in the domains of computer vision,
multimedia processing, graph analytics, and search. With this widespread
proliferation of DNNs, researchers have focused on performance optimization
and energy-efficiency of such hardware architectures. Even though DNNs are
presumed to be resilient against errors by virtue of their inherent fault
tolerant capabilities, the threshold of such resiliency can be easily
inflicted with bit-level hardware faults, leading to graceless degradation in
classification accuracy of the DNN [4].

To execute an inference network at the edge, considerable amount of on-chip
memory is required to store millions of trained network parameters, input
activations and intermediate feature maps. For this purpose, energy restricted
DNN accelerators utilize Dynamic Random Access Memory (DRAM) as their primary
memory subsystem, owing to its low access latency and high density
architecture. However, due to various non-idealities associated with the
access transistor, the charge stored in the DRAM cells leak away over time,
engendering bit-level faults throughout the memory. In order to alleviate
this, a DRAM is periodically replenished using an implicit background refresh
operation, which contributes to a significant amount of DRAM energy overhead
as well as performance bottleneck in the DNN accelerator. Existing research to
alleviate this high refresh rate of DRAMs have focused on utilizing sub-
optimal refresh rates; at the expense of bit-flip faults that are highly
dependent on temperature and variable retention times of each cell in the
structure. Such faults manifested in the structure adversely impact the
classification of the network, as demonstrated in Figure 1. Since DNN
accelerators are often deployed in high-assurance environments, e.g., self
driving vehicles for enhancing the autonomous driving dynamics, smart sensors
in aerial surveillance vehicles like drones, analyzing the impact of these
DRAM faults is highly imperative to avoid catastrophic circumstances.

Figure 1: Fault manifestation in DRAM leading to misclassification in a
mission-critical DNN accelerator.

###  I-A DRAM Basics

DRAM is the primary choice for main memory in most computing platforms ranging
from large scale data centers to miniature edge devices, due to its high
density, longevity, and low cost. The basic element of the 2D-DRAM array is a
DRAM bitcell, which consists of a single capacitor and an access transistor.
Depending on the charge in the DRAM cell capacitor, a binary data value is
identified as 1 when the capacitor is fully charged, or 0 when it is in a
discharged state. However, DRAM capacitor loses charge over time due to
various factors predominantly related to the non-ideality of the access
transistor like sub-threshold leakage and gate-induced drain leakage. As a
result of this, faults in the form of bit flips start to manifest in the data
bits after a certain time interval (known as retention time). Therefore, the
charge needs to be refreshed periodically to preserve the integrity of the
data. The leakiest cell in the entire DRAM array determines the worst-case
retention time, which is usually 64ms in case of commercial DRAM modules. Even
though high refresh rates are imperative to maintain correctness, they also
adversely impact on the overall energy efficiency and performance. Energy
efficiency declines due to the periodic activation of individual rows as well
as the increase in energy consumption due to a longer execution time.

Existing research to alleviate the high refresh rate of DRAMs have focused on
utilizing sub-optimal refresh rates, approximating the device performance. One
of the earliest work in this domain, Flikker, partitions the application data
into critical and non-critical parts, injecting errors in the non-critical
portion at higher refresh intervals [5]. Sparkk, a DRAM approximation
framework refreshes the most significant bits at a higher refresh rate than
the least significant ones [6]. Other DRAM approximation schemes have also
been proposed, that reduces DRAM energy consumption at lower refresh rates [7,
8, 9]. A quality configurable approximate DRAM has been proposed, that
utilizes the concept of critical and non-critical data partitioning to
allocate data in multiple quality bins, considering the property of variable
retention times exhibited by DRAM cells [10]. However, the impact of the
errors on high assurance DNN accelerators has not been well explored at high
DRAM refresh intervals, which drives us to analyze the reliability of such
high assurance architectures.

###  I-B DNN Accelerator and Its Reliability

In recent years, DNNs have acquired a meteoric rise in various spheres of life
due to their use of sophisticated mathematical modeling to process data with
high complexity parameters. To meet the extreme compute requirements of these
compute-heavy DNN algorithms, a number of DNN accelerators have emerged over
the past decade. Most DNN accelerators in practice utilizes DRAM as the main
memory subsystem. For example, well known DNN accelerators such as Google TPU
[1], Eyeriss [2], NVIDIA Jetson Dev Board [11], Google Coral Edge TPU [12],
and Intel MyriadX VPU [13] consists of 8 GB, 1 GB, 4 GB, 1 GB, and 2 GB of
DRAM, respectively. Recently, a new class of sparse DNN accelerators has
emerged, such as Eyeriss v2 [14], NVIDIA Ampere [15], Intel Keem Bay VPU [16],
_etc._ , that accelerates the performance of sparse matrix convolution in the
inference. These accelerators leverage the sparsity in a tensor graph and
therefore, skip certain computations during the inference, based on the bitmap
encoding of the tensors. In these sparse accelerators, DRAM reliability is
extremely critical, which can lead to subverting the accuracy of the DNN
accelerator.

With the extensive deployment of DNN accelerators in a wide gamut of
applications, researchers have analyzed the impact of faults in various
inference hardware. To explore the correlation between bit error rate and
model accuracy, permanent faults are injected in the memory elements of a
customized DNN accelerator [17]. The impact of single bit soft errors in the
memory on the network performance is explored in [18], which further proposed
a bit-flip resilience optimization method for DNN accelerators. Memory faults
are induced in the Autonomous Driving System (ADS) of a vehicle and the
corresponding resilience of different modules are examined [19]. The
susceptibility of the architecture under single event upsets on the datapath
of an accelerator is analyzed on multiple Convolutional Neural Network (CNN)
models [20]. The safety critical bits in a machine learning system were
identified by inducing soft errors in the network datapath and evaluating them
on eight DNN models across six datasets [21]. A formal analysis on the impact
of faults in the datapath of an accelerator has been illustrated using
Discrete-Time Markov Chain (DTMC) formalism [22]. The intense performance
penalty in a systolic array-based DNN accelerator has been demonstrated by
inducing manufacturing defects in the datapath of the accelerator [4, 23, 24].
However, fault characterization of DNN accelerators due to device-level non-
idealities in the DRAM cells has not been well explored.

###  I-C Fault Characterization to Estimate Network Performance

In order to analyze the impact of DRAM faults on the performance of the DNN
accelerator, we implement Multilayer Perceptron (MLP) on two different
datasets —MNIST and Fashion-MNIST. The detailed network configuration of the
MLP is provided in Table I. We consider Google’s Tensor Processing Unit as the
baseline DNN accelerator, having 8GB of dual-channel DDR3 DRAM as the main
memory subsystem. The trained weights from each network are extracted and
quantized to 8 bits to be stored in the DRAM, similar to [4]. Subsequently,
the trained weights from the DRAM are mapped on to the inference hardware.
MNIST furnishes a baseline classification accuracy of 97.28%, whereas Fashion-
MNIST manifest an accuracy of 88.17% on MLP. Errors in the form of bit-flips
are induced throughout the DRAM structure, following which the application-
level fault characterization of the accelerator is analyzed in this section.

Table I: Overview of the MLP Architecture. Dataset | Model Configuration
---|---
MLP on MNIST | $784-256-256-256-10$
MLP on Fashion-MNIST | $784-256-256-256-10$

####  I-C1 Impact of Faults for Varying Bit Positions

In this experiment, the vulnerability of the network is analyzed for varying
bit positions of the induced fault in the 8-bit weight stored in the DRAM.
Bit-flips are introduced at random positions and the average classification
accuracy of the model is observed for 10 runs. Bit flip faults are induced in
the three most significant bit positions, starting from the sign bit.

The corresponding accuracy drop for MLPs on MNIST and Fashion-MNIST are
represented in Figures 2(a) and 2(b) respectively. As seen from the figures,
with the increase in number of faults, the classification accuracy of the
network reduces for every bit position. As the significance of the bit
position diminishes, the sensitivity of the induced fault reduces; thereby
increasing the number of faults to accomplish identical reduction in
classification accuracy. Since bit-flips induced in the sign bit reverses the
signed integer representations, it causes maximum impact on the classification
accuracy of the network. Hence, MLPs on MNIST and Fashion-MNIST manifest an
1-2% reduction in accuracy with only 250 and 40 faults injected in each layer,
respectively, at the sign bit of the weights. Thus, minimal faults in the sign
bit have the most intense impact on the reliability of the DNN accelerator.

(a)

(b)

Figure 2: Impact of Faulty Bit Position on Classification Accuracy of MLP on
(a) MNIST and (b) Fashion-MNIST.

####  I-C2 Impact of Faults on the Most Vulnerable Weights

Random errors throughout the fault space furnish adequate degradation in
classification accuracy. However, the number of random faults required to
bring about such degradation is usually quite large. Hence, in this
experiment, we focus on estimating the most vulnerable weights in a MLP. The
weights corresponding to a particular layer in the MLP are arranged in the
form of rows and columns in the 2D DRAM structure, where a particular column
of weights corresponds to a specific neuron in the layer [4]. Hence, inducing
faults along a distinct column is likely to produce a deeper impact on the
network performance. As described in Section I-C1, since flipping the sign bit
has the most impact on the model performance, we introduce bit-flip errors in
the sign bit across only 20 random locations along a particular column of the
weight matrix. This erroneous column location is varied, and the corresponding
degradation in accuracy, averaged over 10 random runs, is depicted in Figure 3
for both the datasets. We observe that faults in all the columns till column
‘9’ render almost a consistent reduction in accuracy for all the datasets.
However, as the column number exceeds ‘9’, the accuracy drop plummets close to
zero, signifying almost negligible impact of the faults on the accuracy of the
network. Since the output layer of the network consists of 10 neurons
corresponding to 10 distinct classes in all the datasets, the last layer
weights are mapped onto the first 10 columns of the matrix. When faults are
induced in one among those 10 columns, the computation for that column
corresponding to a specific neuron, and thereby to a particular application
class is disrupted. With datasets having higher number of classes, such faults
can impact differently, affecting the computation in other columns of the
systolic array.

Figure 3: Variation of Accuracy Drop for 20 Faults across Varying Columns of
the Weight Matrix.

Therefore, by injecting bit-wise faults engendering from device-level non-
idealities in the primary memory subsystem, we analyzed the reliability of
resource-constrained DNN accelerators. We perform an extensive fault
characterization of a neural network architecture on multivariate exhaustive
datasets. An application-level analysis on the quantized pre-trained inference
networks demonstrate degradation of classification accuracy, even at
infinitesimal error rates. Hence, it is highly imperative to develop
mitigation strategies that protect the most vulnerable network parameters in
the memory, in order to improve the performance of the DNN accelerator at sub-
optimal DRAM refresh rates.

##  II AI/Deep Learning Accelerator Faults and Performance Impact

AI and Deep Learning tasks are compute-intensive and require millions of
Multiply and Accumulate (MAC) operations for training and inference. In Table
II, the number of MACs required for classifying a single image from ImageNet
benchmark [25] during inference is shown. To increase the execution
throughput, the AI accelerators are designed with thousands of densely packed
Processing Elements(PEs)/MAC circuits [1]. As a result of this dense
integration at advanced technology nodes which are susceptible to defect and
yield issues, the AI chips are especially vulnerable to circuit faults (Fig.
4).

Figure 4: Hardware hazards and faults impacting AI accelerator chips. Table II: Multiplication and additions in CNNs to classify one image [26] | CNN
---
Architecture
| Conv2d
---
Layers
| Linear
---
Layers
| Number of
---
Multiplications
| Number of
---
Additions
LeNet-5 | 3 | 2 | 416,520 | 416,520
AlexNet | 5 | 3 | 714,188,480 | 714,188,480
VGG-16 | 13 | 3 | 15,470,264,320 | 15,470,264,320
ResNet-50 | 53 | 1 | 3,729,522,688 | 1,761,820,672

###  II-A Circuit and Hardware Hazards on Deep Learning/AI Accelerator
Fidelity

The major types of circuit and transistor level hazards that can impact the
performance of AI/Deep Learning accelerator are, (i) process variation induced
circuit parameter variations, (ii) runtime power supply voltage noise and
droop, (iii) circuit aging with time, and (iv) radiation induced soft errors.
For safety-critical applications, chips with permanent stuck-at faults are
generally discarded according to defective parts per million/billion
(DPPM/DPPB) guidelines of FuSa standards[27]. However, aging induced in-field
stuck-at faults can be a concern for automotives.

####  II-A1 Process Variations:

Process parameter variations are caused by semiconductor manufacturing
imperfections, which is a major concern for current advanced technologies
(e.g., 10nm and newer), and impact circuit performance at both the memory and
MAC units in accelerator hardware. As a result, different samples of the same
accelerator chip might exhibit different frequencies (i.e., speed binning
[28]) post-fabrication. For safety-critical AV application, it is important to
analyze how process variations can impact the Deep Learning accuracy and
fidelity. Unlike other areas, a one-size-fits-all training method may not be
suitable for Deep Learning used in safety-critical domains.

####  II-A2 Power Supply Noise:

Voltage noise is caused by simultaneous switching events inside the chip.
Since the accelerator chips will perform millions of operations to infer
decisions from analysis of the images, the extensive switching inside the MAC
and memory units from this can cause voltage noise [29]. The corresponding
transient voltage droop can cause timing violations or bit-flips inside the
accelerator.

####  II-A3 Circuit Aging:

Circuit aging is a critical reliability problem in modern VLSI chips [30].
Since aging is use-case dependent and cannot be accurately estimated at time
0, it is a major concern for safety-critical applications. Aging can impact
the weight storage SRAM modules by altering their read/write stability with
time, and thus cause bit-flip errors. The Deep Learning accelerator’s
performance (i.e., operating frequency $F_{MAX}$) might shift with time
depending on the amount of usage.

####  II-A4 Soft Errors:

Although most of the AI accelerators are used at sea-level altitude, it may
seem they are immune to soft errors caused by high-energy neutrons from cosmic
radiation. However, as shown in detail in [31], because of weight reuse in
Deep Learning, soft-errors can indeed impact the accuracy of accelerators.
Hence, it is essential to embed resiliency and robustness against random bit-
flips in addition to radiation hardening of the critical MSB bits.

The key modules of accelerators that are susceptible to defects are the weight
storage SRAM/Register Files (RF) and the PE/MACs. For SRAM/RF, the faults are
generally repaired with ECC and spare cells. The timing-faults in MAC can be
solved by appropriate timing guard-band and run-time frequency adjustment. The
stuck-at faults in the MAC are permanent and can adversely impact accuracy. In
this section accuracy impact of stuck-at faults in MAC are analyzed.

Figure 5: Faults are classified as critical or non-critical based on their
location in the logic cone of the bits. Figure 6: Deactivating some non-
critically faulty PEs to keep fault rate within $FR_{max\\_non-crit}$ to
ensure accuracy does not degrade beyond acceptable limit. Figure 7: Impact of
faults in logic cones of LSB positions on inference accuracy for AlexNet with
ImageNet data set. (a), (b) int8 data format and MAC type.; (c), (d) bfloat16
data format and MAC type. Figure 8: Inference accuracy changes with fault
(non-critical) rates for CNNs running imagenet dataset. (a), (b) Top-1 and
Top-5 accuracy changes ; (c), (d) Top-1 and Top-5 accuracy changes with model
pruning; (e) to (h) normalized accuracy changes in Top-1 and Top-5 (with and
without pruning) for fault rates.

###  II-B Fault Location and Accuracy Impact:

Systematic defects and yield losses are caused by layout-sensitive
lithographic hotspots and other process imperfections, variations, and are
generally independent of the layout area. On the other hand, random defect
generated yield losses are caused by defect particles and are dependent on the
standard-cell or the layout area as well as the defect particle size [32].
These defects (e.g., short/open defect, poor contact/via, etc.) and
corresponding circuit faults can occur at different sites inside the MAC
circuit block. The precision loss - due to the presence of circuit faults - at
the output of multiply and accumulate operation will depend on the location of
the fault inside the MAC circuit and the logic cone impacted by the fault as
shown in Fig. 5. For example, if a multiplier circuit that performs the
multiplication of two 8-bit numbers, has faults impacting up to $K$ LSB bits,
then it will sustain a worst-case error of $\pm\sum_{i=0}^{K+1}2^{i}$ (the
last $2^{K+1}$ term comes from the worst-case carry-in path of partial product
addition, as explained in the next subsection). As $K$ increases, the faults
impact the more significant digits causing the worst-case error of the
multiplier to increase. Errors will also occur in the adder circuit of the MAC
if it is corrupted by faults. Since the multiplier is the more area-dominant
block in a MAC, it will be more prone to faults and computation errors. A
similar analysis can be also done for bfloat16 [33] MAC to identify faults in
LSB positions (i.e., logic cone of corresponding bits) and their impact on
accuracy. If any PE has a fault in the critical logic cone then it needs to be
deactivated to prevent accuracy loss because critical faults can cause large
magnitude error in MAC output. For faults in the non-critical logic cone, up
to a certain fault rate (i.e., $FR_{max\\_non-crit}$) may be acceptable.

The IDs of faulty PEs and their fault type (e.g., critical or non-critical)
can be identified with ATPG test patterns and recorded in a Fault Status
Register (FSR) [26]. During inference, the mobile/edge accelerator’s FSR and
control unit reads the $FR_{max\\_non-crit}$ and if it is lower than the
current fault rate $FR_{non-crit}$, then the control unit sends deactivation
signals to disable some of the PEs. The deactivation protocol and the complete
map of faulty PE locations are programmed in firmware/software by the
manufacturer. With the user-given input of acceptable fault rate and the
stored PE fault map, the protocol will automatically disable a few faulty PEs
to ensure that the overall faulty PE rate of the accelerator does not exceed a
threshold (i.e., $FR_{max\\_non-crit}$). When deactivating some faulty PEs,
the firmware/software will ensure that the remaining faulty PEs are not
clustered. As shown in Fig. 6, control signals are transmitted from the FSR to
all the PEs to selectively disable the faulty PEs when needed. By adopting
this scheme, the manufacturer can avoid discarding the full accelerator
chip/die only because of the presence of few PEs with faulty MACs, and thereby
increase yield. The overhead in this yield loss reduction are the extra on-
chip register (FSR) to store the IDs and the control signal routes to disable
faulty PEs [26].

Figure 9: Improvement in accuracy with fault-aware training on LeNet-5.

###  II-C Accelerator Architecture and Faulty PE Deactivation

AI accelerators can be designed either in SIMD or Systolic architectures. In
SIMD architecture the loosely coupled independent Processing Elements (PEs)
are connected with NoC or mesh and can be individually switched off and
bypassed with wires [2, 1, 26]. The tightly-coupled 2D systolic-arrays in TPU
introduce challenges in deactivating and bypassing individual PEs. A common
technique is to use spare PE blocks to substitute for faulty PEs. However,
this approach requires complex wiring between spare and faulty PEs [34]. An
innovative software-level technique to deactivate and bypass faulty PEs in
systolic array without any hardware-level modifications was proposed in [26].

###  II-D Results and Analysis

To identify the impact of the number of LSBs having faults in their logic
cones, the number of LSBs were varied from 2 to 4 for int8 and 3 to 5 for
bfloat16 [33] data formats for the CNN model AlexNet with the ImageNet test
set. These experiments were done with PyTorch. The results are shown in Fig.
7, where X-axis is fault-rate in non-critical logic cones (the LSBs). From
this analysis, we conservatively selected 2 LSBs for int8 and 4 mantissa LSBs
for the bfloat16 hardware models as non-critical (i.e., circuit faults
occurring in their logic cones are non-critical), and rest of all the bits are
considered critical. Any PE with one or more critical faults are considered
defective and must be deactivated to ensure fidelity in accuracy. In the
experiments the accelerator hardware comprised of 128 by 128 array of PE/MACs.
The faulty PEs are modeled as uniformly distributed across the accelerator
columns with fault probability of $FR\%$, the fault rate. This implies that
for $FR\%$ fault rate, each column of the accelerator has $0.01*FR*N_{Row}$
faulty PEs randomly distributed across that column.

The accuracy changes - in the standard Top-1 and Top-5 format - with MAC
faults are shown in Fig. 8 for 50,000 test images from ImageNet [25]. We
observe from Fig. 8 that up to a certain fault (non-critical) rate might be
acceptable depending on the desired accuracy of the AI/Deep Learning task.

####  II-D1 Fault-aware training to enhance Robustness

Using a fault-aware training flow some of the accuracy loss due to faults in
MAC units can be recovered by incorporating the fault effects in the
backpropagation-based weight update segment and allowing the DNN to adapt
accordingly [26]. To experimentally demonstrate this technique, we used the
LeNet-5 CNN architecture. Results from this fault-aware training are shown in
Fig. 9. For 7.5% fault rate (non-critical faults) the normalized accuracy loss
improved from 0.5% to 0.22% due to fault-aware training.

##  III Dependability Issues in Neuromorphic Computing

Neuromorphic Computing is a term coined by Carver Mead in the late 1980s
describing Very Large-Scale Integration (VLSI) systems, which mimic the neuro-
biological architecture of the central nervous system [35]. Neuromorphic
systems are energy efficient in executing Spiking Neural Networks (SNNs),
which are considered as the third generation of neural networks. SNNs use
spike-based computations and bio-inspired learning algorithms in solving
pattern recognition problems [36]. In an SNN, pre-synaptic neurons communicate
information encoded in spike trains to post-synaptic neurons, via synapses.
Performance, e.g., accuracy of an SNN model can be assessed in terms of the
inter-spike interval (ISI), which is defined as inverse of the mean firing
rate of neurons. This is illustrated in Figure 10.

Figure 10: Integration of spike trains at the post-synaptic neuron from four
pre-synaptic neurons in a Spiking Neural Network (SNN). Each spike is a
voltage waveform of small time duration to the order of ms.

Recently, neuromorphic platforms such as DYNAPs [37], TrueNorth [38], and
Loihi [39] are introduced to the systems community. These systems are designed
as tile-based architectures with a shared interconnect for communication [40,
41, 42]. A tile may consist of a crossbar for mapping neurons and synapses of
an application. Recently, Non-Volatile Memory (NVM) technologies such as
Phase-Change Memory (PCM) and Oxide-based Resistive RAM (OxRRAM) are used to
implement synaptic storage in each crossbar [43, 44].111Beside neuromorphic
computing, some of these NVM technologies are also used to implement main
memory in conventional computers to improve performance and energy efficiency
[45, 46, 47, 48, 49]. NVMs bring certain advantages such as high integration
density, multi-bit synapses, CMOS compatibility, and above all, non-
volatility, which can further lower the energy consumption of neuromorphic
hardware. However, NVMs also introduce reliability issues such as endurance,
aging, and read disturbances (see Table III for a summary of these issues). In
this paper, we will discuss some of these issues and our approach to mitigate
them.

Table III: Reliability issues in NVMs. Reliability Issues | NVMs
---|---
High-voltage related circuit aging | PCM, Flash
High-current related circuit aging | OxRAM, STT-MRAM
Read disturbance | All
Limited endurance | All

###  III-A Introduction to Non-Volatile Memory

Emerging NVM technologies such as phase-change memory (PCM), oxide-based
memory (OxRAM), spin-based magnetic memory (STT-MRAM), and Flash have recently
been used to implement synaptic storage in neuromorphic hardware. NVMs are
non-volatile, have high CMOS compatibility, and can achieve high integration
density. Each NVM device can implement both a single-bit and multi-bit
synapse. Because of these properties, an NVM-based neuromorphic hardware
typically consumes energy that is in the order of magnitudes lower than using
SRAMs [43].

Without loss of generality, we discuss the dependability issues for PCM-based
neuromorphic computing. PCM is one of the mature NVM technologies and is
successfully demonstrated in recent neuromorphic prototypes [44].

Figure 11 ❶ illustrates how a chalcogenide semiconductor alloy is used to
build a PCM cell. The amorphous phase (RESET) in this alloy has higher
resistance than the crystalline phase (SET). Ge2Sb2Te5 (GST) is the most
commonly used alloy for PCM. To compute $(x_{i}\cdot w_{i})$, a current is
injected into the resistor-chalcogenide junction via the heater element. The
current is controlled to ensure that the phase of the PCM cell is not
disturbed. This is the fundamental operation of forward propagation of neuron
excitation during inference. For online learning (e.g., using STDP), the
injected current induces (Joule) heating in the chalcogenide alloy, changing
its conductivity, thereby achieving synaptic weight updates. Figure 11 ❷
illustrates the current profiles necessary for inference (using the read
pulse) and online learning (using SET and RESET pulses) in PCM. These current
profiles are generated using an on-chip charge pump (CP). Figure 11 ❸
illustrates the PCM cell’s operation when idle, i.e., when a neuron is not
activated. We illustrate a 1D-1R structure, where a single PCM cell is
connected to a row and column using a diode as an access device. Diode-based
PCM cells allow very high integration density in scaled technology nodes
compared to transistor-based PCM. The CP is operated at 1.8V to maintain the
required biasing. Finally, Figure 11 ❹ illustrates the PCM operation during
inference. The CP is operated at 3V to generate the read current profile of
Figure 11 ❷ using the sense amplifier (SA). The write driver (WD) is used for
generating the currents for online learning.

Figure 11: Operation of PCM in neuromorphic computing.

These high-voltage operations of the charge pump (and the peripheral circuit
of a crossbar) accelerate circuit aging, lowering the dependability of
neuromorphic computing.

Apart from diode, transistors are also used as access devices. When using
transistor-based PCM cells, the CP is operated at lower voltages: 1.2V during
idle and 1.8V during spike propagation. Though aging issues are less severe in
such designs, they are still a dependability concern for neuromorphic
computing.

Peripheral aging are not the only dependability issues in neuromorphic
hardware. Unfortunately, NVMs have limited endurance, ranging from $10^{5}$
(for Flash) to $10^{10}$ (for OxRRAM), with PCM somewhere in between ($\approx
10^{7}$).

In the following we describe our recent efforts in mitigating aging and
endurance in neuromorphic computing.

###  III-B Mitigating Peripheral Aging in Neuromorphic Hardware

In our prior work [50, 51, 52], we have analyzed different aging issues in the
peripheral circuit of a neuromorphic hardware. We briefly elaborate on these
issues.

We consider the CMOS aging due to Time-Dependent Dielectric Breakdown (TDDB),
Bias Temperature Instability (BTI), and Hot-Carrier Injection (HCI) failure
mechanisms. These are the dominant ones in scaled technology nodes (45nm and
below). In older nodes, Electromigration (EM) also plays a key role [53, 54,
55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70].

CMOS aging is accelerated when the device is _stressed_ , i.e., exposed to
high overdrive voltages222Overdrive voltage is defined as the voltage between
transistor gate and source ($V_{GS}$) in excess of the threshold voltage
($V_{\text{th}}$), where $V_{\text{th}}$ is the minimum voltage required
between gate and source to turn the transistor on.. With this understanding,
we provide a brief background of these failure mechanisms.

  * •

TDDB: This is a failure mechanism in a CMOS device, when the gate oxide breaks
down as a result of long-time application of relatively low electric field (as
opposed to immediate breakdown, which is caused by strong electric field)
[71]. The lifetime of a CMOS device is measured in terms of its mean time to
failure (MTTF) as

$\vspace{-6pt}\footnotesize\text{MTTF}_{\text{TDDB}}=A.e^{-\gamma\sqrt{V}},$
(1)

where $A$ and $\gamma$ are material-related constants, and $V$ is the
overdrive gate voltage of the CMOS device.

  * •

_BTI:_ This is a failure mechanism in a CMOS device in which positive charges
are trapped at the oxide-semiconductor boundary underneath the gate [72]. BTI
manifests as 1) decrease in drain current and transconductance, and 2)
increase in off current and threshold voltage. The BTI lifetime of a CMOS
device is

$\vspace{-6pt}\footnotesize\text{MTTF}_{\text{BTI}}=\frac{A}{V^{\gamma}}e^{\frac{E_{a}}{KT}},$
(2)

where $A$ and $\gamma$ are material-related constants, $E_{a}$ is the
activation energy, $K$ is the Boltzmann constant, $T$ is the temperature, and
$V$ is the overdrive gate voltage.

  * •

_HCI:_ This is a failure mechanism in a CMOS device, when a carrier (electron
or hole) gains sufficient kinetic energy to overcome the potential barrier of
the conducting channel and gets trapped in the gate dielectric, permanently
changing the CMOS’s switching properties [73].

Unlike the TDDB and BTI failure mechanisms, for which silicon-characterized
reliability models are available from foundries, characterized models for HCI
failure mechanism are still in development for scaled nodes.

Current methods for qualifying reliability are overly conservative, since they
estimate circuit aging considering worst-case operating conditions and
unnecessarily constrain performance. Recent system-level works on mapping SNN-
based applications to neuromorphic hardware, such as [74, 75, 76, 77, 78, 79,
80, 81, 82, 83], target performance improvement only. They do not consider
reliability issues of neuromorphic computing.

To address these limitations, we have designed RENEU [51], a reliability-
oriented approach to map machine learning applications to neuromorphic
hardware, with the aim of improving system-wide reliability, without
compromising key performance metrics such as execution time of these
applications on the hardware. Fundamental to RENEU is a novel formulation of
the aging of CMOS-based circuits in a neuromorphic hardware considering
different failure mechanisms. Using this formulation, RENEU develops a system-
wide reliability model which can be used inside a design-space exploration
framework involving the mapping of neurons and synapses to the hardware. To
this end, RENEU uses an instance of Binary Particle Swarm Optimization (PSO)
[84] to generate mappings that are Pareto-optimal in terms of performance and
reliability. We evaluate RENEU using SNN-based streaming and non-streaming
applications [85, 86, 87, 88, 89]. We evaluate these applications on a state-
of-the-art neuromorphic hardware with PCM synapses.

Figure 12 reports the circuit aging caused by RENEU normalized to PyCARL, a
state-of-the-art SNN mapping approach. We plot results for each of our machine
learning applications. We observe that the aging of RENEU is lower than PyCARL
by an average of 38%. This improvement is because RENEU formulates the
detailed circuit aging of a neuromorphic hardware and allocates the neurons
and synapses of a machine learning application to minimize it.

Figure 12: Circuit aging in the neuromorphic hardware normalized to PyCARL
(lower is better) [51].

###  III-C Mitigating Thermal and Endurance Issues in Neuromorphic Hardware

In our prior work [90, 91, 92], we have formulated the thermal issues in
neuromorphic hardware and established its impact on endurance.

We analyze the internal architecture of a PCM crossbar (see Fig. 13) and
observe that parasitic components on horizontal and vertical wires of a
crossbar are a major source of parasitic voltage drops in the crossbar. Using
detailed circuit simulations at different process (P), voltage (V), and
temperature (T) corners, we show that these voltage drops create current
variations in the crossbar. For the same spike voltage, current on the
shortest path is significantly higher than the current on the longest path in
the crossbar, where the length of a current path is measured in terms of its
number of parasitic components. These current variations create asymmetry in
the self-heating temperature of PCM cells during their weight updates, e.g.,
during model training and continuous online learning [93], which directly
influences their endurance.

Figure 13: Bitline and wordline parasitics in a PCM crossbar.

Figure 14 plots the temperature and endurance maps of a 128x128 crossbar at
65nm process node with $T_{amb}=298K$. The PCM cells at the bottom-left corner
have higher self-heating temperature than at the top-right corner. This
asymmetry in the self-heating temperature creates a wide distribution of
endurance, ranging from $10^{6}$ cycles for PCM cells at the bottom-left
corner to $10^{10}$ cycles at the top-right corner. These endurance values are
consistent with the values reported for recent PCM chips from IBM [94].

Figure 14: Temperature and endurance map of a 128x128 PCM crossbar at $65$nm
process node with $T_{amb}=298K$.

Using such technology modeling, we propose eSpine, a novel technique to
improve endurance-related lifetime of PCM by incorporating the endurance
variation within each crossbar in mapping machine learning workloads, ensuring
that synapses with higher activation are always implemented on PCM cells with
higher endurance, and vice versa. eSpine works in two steps. First, it uses
the Kernighan-Lin Graph Partitioning algorithm to partition a workload into
clusters of neurons and synapses, where each cluster can fit in a crossbar.
Second, it uses an instance of PSO to map clusters to tiles, where the
placement of synapses of a cluster to the PCM cells of a crossbar is performed
by analyzing their activation within a workload. We evaluate eSpine for a
state-of-the-art neuromorphic hardware model with PCM synapses. Using 10 SNN
workloads, we demonstrate a significant improvement in the effective lifetime.

##  IV Conclusion

To conclude, as process technology continues to scale aggressively,
reliability issues in neuromorphic hardware are becoming a primary concern for
system developer. First, we analyzed the reliability of DNN accelerators in
the presence of DRAM faults. By injecting bit-wise faults engendering from
device-level non-idealities in the memory subsystem of the accelerator, we
perform an extensive fault characterization of multiple DNN architectures on
multivariate exhaustive datasets. An application-level analysis on the
quantized pre-trained inference networks demonstrate degradation of
classification accuracy, even at infinitesimal error rates. Next, we analyzed
the MAC circuits, as they occupy a significant portion of the DNN hardware.
Circuit faults in MSB logic cones of the MAC can adversely impact accuracy.
For MACs with faults in LSB logic cones, the fraction of such faulty MACs must
be within an application-dependent range to ensure accuracy degradation does
not exceed acceptable limits. System-level approaches, such as the ones we
highlighted in this paper, mitigate these reliability issues via intelligent
neuron and synapses placement on the hardware. These approaches, however, can
be further improved by incorporating technology perspective within a holistic
design-technology co-optimization framework.

## References

  * [1] Jouppi _et al._ , “In-datacenter performance analysis of a tensor processing unit,” in _ISCA_ , 2017, pp. 1–12.
  * [2] Chen _et al._ , “Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks,” _IEEE Journal of Solid-State Circuits_ , vol. 52, pp. 127–138, 2016.
  * [3] Park _et al._ , “4.6 a1. 93tops/w scalable deep learning/inference processor with tetra-parallel mimd architecture for big-data applications,” in _IEEE ISSCC_ , 2015, pp. 1–3.
  * [4] Zhang _et al._ , “Analyzing and mitigating the impact of permanent faults on a systolic array based neural network accelerator,” in _2018 IEEE 36th VLSI Test Symposium (VTS)_. IEEE, 2018, pp. 1–6.
  * [5] Liu _et al._ , “Flikker: saving dram refresh-power through critical data partitioning,” in _Proceedings of the 16th ASPLOS_ , 2011, pp. 213–224.
  * [6] Lucas _et al._ , “Sparkk: Quality-scalable approximate storage in dram,” in _The memory forum_ , 2014, pp. 1–9.
  * [7] Sampson _et al._ , “Enerj: Approximate data types for safe and general low-power computation,” _ACM SIGPLAN Notices_ , vol. 46, pp. 164–174, 2011\.
  * [8] Rahmati _et al._ , “Refreshing thoughts on dram: Power saving vs. data integrity,” in _Workshop on Approximate Computing Across the System Stack_ , 2014.
  * [9] Raha _et al._ , “Synergistic approximation of computation and memory subsystems for error-resilient applications,” _IEEE Embedded Systems Letters_ , vol. 9, pp. 21–24, 2017.
  * [10] Raha _et al._ , “Quality configurable approximate dram,” _IEEE TC_ , vol. 66, pp. 1172–1187, 2016.
  * [11] S. Cass, “Nvidia makes it easy to embed ai: The jetson nano packs a lot of machine-learning power into diy projects-[hands on],” _IEEE Spectrum_ , vol. 57, pp. 14–16, 2020.
  * [12] S. Cass, “Taking ai to the edge: Google’s tpu now comes in a maker-friendly package,” _IEEE Spectrum_ , vol. 56, pp. 16–17, 2019.
  * [13] “Intel movidius™ myriad™ x vision processing unit (vpu),” https://www.intel.com/content/www/us/en/products/details/processors/ movidius-vpu/movidius-myriad-x.html, (Accessed on 03/17/2021).
  * [14] Chen _et al._ , “Eyeriss v2: A flexible accelerator for emerging deep neural networks on mobile devices,” _IEEE JETCAS_ , vol. 9, pp. 292–308, 2019.
  * [15] “Nvidia ampere architecture — nvidia,” https://www.nvidia.com/en-us/data-center/nvidia-ampere-gpu-architecture/, (Accessed on 08/01/2020).
  * [16] “Intel keem bay vpu,” https://d1io3yog0oux5.cloudfront.net/ _a000324c17af610f0c3d7c52e5620775/intel/db/861/7791/pdf/intel-ai-summit-keynote-slides.pdf, (Accessed on 10/02/2020).
  * [17] Reagen _et al._ , “Ares: A framework for quantifying the resilience of deep neural networks,” in _ACM Design Automation Conference (DAC)_ , 2018, pp. 1–6.
  * [18] Schorn _et al._ , “An efficient bit-flip resilience optimization method for deep neural networks,” in _Design, Automation & Test in Europe Conference & Exhibition_, 2019, pp. 1507–1512.
  * [19] Jha _et al._ , “Ml-based fault injection for autonomous vehicles: a case for bayesian fault injection,” in _2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)_. IEEE, 2019, pp. 112–124.
  * [20] Li _et al._ , “Understanding error propagation in deep learning neural network (dnn) accelerators and applications,” in _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ , 2017, pp. 1–12.
  * [21] Chen _et al._ , “Binfi: an efficient fault injector for safety-critical machine learning systems,” in _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ , 2019, pp. 1–23.
  * [22] Kundu _et al._ , “High-level modeling of manufacturing faults in deep neural network accelerators,” in _2020 IEEE 26th International Symposium on On-Line Testing and Robust System Design (IOLTS)_. IEEE, 2020, pp. 1–4.
  * [23] Zhang _et al._ , “Fault-tolerant systolic array based accelerators for deep neural network execution,” _IEEE Design & Test_, vol. 36, pp. 44–53, 2019.
  * [24] Kundu _et al._ , “Toward functional safety of systolic array-based deep learning hardware accelerators,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 29, pp. 485–498, 2021.
  * [25] J. D. et al., “Imagenet: A large-scale hierarchical image database,” in _CVPR_ , 2009.
  * [26] M. Sadi and U. Guin, “Test and yield loss reduction of ai and deep learning accelerators,” in _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 2021.
  * [27] ISO 26262, “Road vehicles-Functional safety,” 2018, Accessed: 11-Mar-2021.
  * [28] M. Sadi et al., “SoC Speed Binning Using Machine Learning and On-Chip Slack Sensors,” in _IEEE Transactions on Computer-Aided Design_ , 2017.
  * [29] M. Sadi and M. Tehranipoor, “Design of a Network of Digital Sensor Macros for Extracting Power Supply Noise Profile in SoCs,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , 2016.
  * [30] M. Sadi, G. K. Contreras, J. Chen, L. Winemberg, and M. Tehranipoor, “Design of Reliable SoCs With BIST Hardware and Machine Learning,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , 2017\.
  * [31] G. Li et al., “Understanding Error Propagation in Deep Learning Neural Network (DNN) Accelerators and Applications,” in _International Conference for High Performance Computing, Storage and Analysis_ , 2017.
  * [32] A. J. Strojwas et al., “Yield and Reliability Challenges at 7nm and Below,” in _Electron Devices Technology and Manufacturing Conference_ , 2019.
  * [33] S. Wang and P. Kanwar, “BFloat16: The secret to high performance on Cloud TPUs,” in _Google Cloud Blog_ , 2019.
  * [34] J. J. Zhang, K. Basu, and S. Garg, “Fault-Tolerant Systolic Array Based Accelerators for Deep Neural Network Execution,” in _IEEE Design & Test_, 2019.
  * [35] C. Mead, “Neuromorphic electronic systems,” _Proceedings of the IEEE_ , 1990\.
  * [36] W. Maass, “Networks of spiking neurons: the third generation of neural network models,” _Neural Networks_ , 1997.
  * [37] S. Moradi, N. Qiao, F. Stefanini _et al._ , “A scalable multicore architecture with heterogeneous memory structures for dynamic neuromorphic asynchronous processors (DYNAPs),” _TBCAS_ , 2017.
  * [38] M. V. Debole, B. Taba, A. Amir _et al._ , “TrueNorth: Accelerating from zero to 64 million neurons in 10 years,” _Computer_ , 2019.
  * [39] M. Davies, N. Srinivasa, T. H. Lin _et al._ , “Loihi: A neuromorphic manycore processor with on-chip learning,” _IEEE Micro_ , 2018.
  * [40] A. Balaji, Y. Wu, A. Das, F. Catthoor, and S. Schaafsma, “Exploration of segmented bus as scalable global interconnect for neuromorphic computing,” in _GLSVLSI_ , 2019.
  * [41] A. Balaji, S. Ullah _et al._ , “Design methodology for embedded approximate artificial neural networks,” in _GLSVLSI_ , 2019.
  * [42] F. Catthoor, S. Mitra, A. Das, and S. Schaafsma, “Very large-scale neuromorphic systems for biological signal processing,” in _CMOS Circuits for Biological Sensing and Processing_. Springer, 2018.
  * [43] A. Mallik, D. Garbin, A. Fantini, D. Rodopoulos, R. Degraeve _et al._ , “Design-technology co-optimization for OxRRAM-based synaptic processing unit,” in _VLSIT_ , 2017.
  * [44] G. W. Burr, R. M. Shelby _et al._ , “Neuromorphic computing using non-volatile memory,” _Advances in Physics: X_ , 2017.
  * [45] S. Song, A. Das, O. Mutlu, and N. Kandasamy, “Enabling and exploiting partition-level parallelism (PALP) in phase change memories,” _TECS_ , 2019\.
  * [46] S. Song, A. Das, and N. Kandasamy, “Exploiting inter-and intra-memory asymmetries for data mapping in hybrid tiered-memories,” in _ISMM_ , 2020\.
  * [47] S. Song, A. Das, O. Mutlu _et al._ , “Improving phase change memory performance with data content aware access,” in _ISMM_ , 2020.
  * [48] S. Song, A. Das, O. Mutlu _et al._ , “Aging aware request scheduling for non-volatile main memory,” in _ASP-DAC_ , 2021.
  * [49] S. Song and A. Das, “Design methodologies for reliable and energy-efficient PCM systems,” in _IGSC Workshops_ , 2020.
  * [50] A. Balaji, S. Song, A. Das, N. Dutt, J. Krichmar _et al._ , “A framework to explore workload-specific performance and lifetime trade-offs in neuromorphic computing,” _CAL_ , 2019.
  * [51] S. Song, A. Das _et al._ , “Improving dependability of neuromorphic computing with non-volatile memory,” in _EDCC_ , 2020.
  * [52] S. Song and A. Das, “A case for lifetime reliability-aware neuromorphic computing,” in _MWSCAS_ , 2020.
  * [53] A. Das, A. Kumar, and B. Veeravalli, “Reliability and energy-aware mapping and scheduling of multimedia applications on multiprocessor systems,” _TPDS_ , 2015.
  * [54] A. Das, A. Kumar, and B. Veeravalli, “Aging-aware hardware-software task partitioning for reliable reconfigurable multiprocessor systems,” in _CASES_ , 2013.
  * [55] A. Das, A. Kumar, B. Veeravalli, C. Bolchini, and A. Miele, “Combined dvfs and mapping exploration for lifetime and soft-error susceptibility improvement in mpsocs,” in _DATE_ , 2014.
  * [56] A. Das, A. Kumar, and B. Veeravalli, “Reliability-driven task mapping for lifetime extension of networks-on-chip based multiprocessor systems,” in _DATE_ , 2013.
  * [57] A. K. Das, A. Kumar, B. Veeravalli, and F. Catthoor, _Reliable and Energy Efficient Streaming Multiprocessor Systems_. Springer, 2018.
  * [58] A. Das, A. Kumar, and B. Veeravalli, “Fault-tolerant network interface for spatial division multiplexing based network-on-chip,” in _ReCoSoC_ , 2012\.
  * [59] A. Das, G. V. Merrett, and B. M. Al-Hashimi, “The slowdown or race-to-idle question: Workload-aware energy optimization of smt multicore platforms under process variation,” in _DATE_ , 2016.
  * [60] A. Das, A. K. Singh, and A. Kumar, “Energy-aware dynamic reconfiguration of communication-centric applications for reliable mpsocs,” in _ReCoSoC_ , 2013\.
  * [61] A. Das, G. V. Merrett, M. Tribastone, and B. M. Al-Hashimi, “Workload change point detection for runtime thermal management of embedded systems,” _TCAD_ , 2015.
  * [62] A. Das, R. A. Shafik, G. V. Merrett, B. M. Al-Hashimi, A. Kumar _et al._ , “Reinforcement learning-based inter-and intra-application thermal optimization for lifetime improvement of multicore systems,” in _DAC_ , 2014\.
  * [63] A. Das, S. Venkataraman, and A. Kumar, “Improving autonomous soft-error tolerance of FPGA through LUT configuration bit manipulation,” in _FPL_ , 2013.
  * [64] R. Santos, S. Venkataraman, A. Das, and A. Kumar, “Criticality-aware scrubbing mechanism for sram-based fpgas,” in _FPL_ , 2014.
  * [65] A. Das, A. Kumar, and B. Veeravalli, “Communication and migration energy aware task mapping for reliable multiprocessor systems,” _FGCS_ , 2014.
  * [66] A. Das, A. Kumar, and B. Veeravalli, “Energy-aware task mapping and scheduling for reliable embedded computing systems,” _TECS_ , 2014.
  * [67] A. Das, A. Kumar, and B. Veeravalli, “Energy-aware communication and remapping of tasks for reliable multimedia multiprocessor systems,” in _ICPADS_ , 2012\.
  * [68] A. Das, A. Kumar, and B. Veeravalli, “Temperature aware energy-reliability trade-offs for mapping of throughput-constrained applications on multimedia MPSoCs,” in _DATE_ , 2014.
  * [69] A. Das, B. M. Al-Hashimi, and G. V. Merrett, “Adaptive and hierarchical runtime manager for energy-aware thermal management of embedded systems,” _TECS_ , 2016.
  * [70] C. Bolchini, M. Carminati, A. Miele, A. Das, A. Kumar _et al._ , “Run-time mapping for reliable many-cores based on energy/performance trade-offs,” in _DFTS_ , 2013.
  * [71] P. J. Roussel _et al._ , “New methodology for modelling MOL TDDB coping with variability,” in _IRPS_ , 2018.
  * [72] R. Gao _et al._ , “NBTI-generated defects in nanoscaled devices: fast characterization methodology and modeling,” _TED_ , 2017.
  * [73] X. Wan _et al._ , “HCI improvement on 14nm FinFET io device by optimization of 3D junction profile,” in _IRPS_ , 2019.
  * [74] A. Balaji _et al._ , “PyCARL: A PyNN interface for hardware-software co-simulation of spiking neural network,” in _IJCNN_ , 2020.
  * [75] S. Song, A. Balaji, A. Das, N. Kandasamy _et al._ , “Compiling spiking neural networks to neuromorphic hardware,” in _LCTES_ , 2020.
  * [76] A. Balaji, S. Song, A. Das, J. Krichmar, N. Dutt _et al._ , “Enabling resource-aware mapping of spiking neural networks via spatial decomposition,” _ESL_ , 2020.
  * [77] A. Balaji, A. Das, Y. Wu, K. Huynh _et al._ , “Mapping spiking neural networks to neuromorphic hardware,” _TVLSI_ , 2020.
  * [78] A. Balaji and A. Das, “A framework for the analysis of throughput-constraints of SNNs on neuromorphic hardware,” in _ISVLSI_ , 2019.
  * [79] A. Das and A. Kumar, “Dataflow-based mapping of spiking neural networks on neuromorphic hardware,” in _GLSVLSI_ , 2018.
  * [80] A. Balaji, T. Marty, A. Das, and F. Catthoor, “Run-time mapping of spiking neural networks to neuromorphic hardware,” _JSPS_ , 2020.
  * [81] T. Titirsha, S. Song, A. Balaji, and A. Das, “On the role of system software in energy management of neuromorphic computing,” in _Computing Frontiers_ , 2021.
  * [82] A. Balaji and A. Das, “Compiling spiking neural networks to mitigate neuromorphic hardware constraints,” in _IGSC Workshops_ , 2020.
  * [83] A. Das, Y. Wu, K. Huynh _et al._ , “Mapping of local and global synapses on spiking neuromorphic hardware,” in _DATE_ , 2018.
  * [84] M. A. Khanesar, M. Teshnehlab, and M. A. Shoorehdeli, “A novel binary particle swarm optimization,” in _Mediterranean Conference on Control & Automation_, 2007.
  * [85] A. Das, P. Pradhapan, W. Groenendaal, P. Adiraju, R. Rajan _et al._ , “Unsupervised heart-rate estimation in wearables with Liquid states and a probabilistic readout,” _Neural Networks_ , 2018.
  * [86] A. Das, F. Catthoor, and S. Schaafsma, “Heartbeat classification in wearables using multi-layer perceptron and time-frequency joint distribution of ECG,” in _CHASE_ , 2018.
  * [87] A. Balaji, F. Corradi _et al._ , “Power-accuracy trade-offs for heartbeat classification on neural networks hardware,” _JOLPE_ , 2018.
  * [88] E. J. Moyer and A. Das, “Motif identification using cnn-based pairwise subsequence alignment score prediction,” _arXiv preprint arXiv:2101.08385_ , 2021.
  * [89] E. J. Moyer, A. Das _et al._ , “Machine learning applications to dna subsequence and restriction site analysis,” _arXiv preprint arXiv:2011.03544_ , 2020.
  * [90] T. Titirsha and A. Das, “Reliability-performance trade-offs in neuromorphic computing,” in _IGSC Workshops_ , 2020.
  * [91] T. Titirsha and A. Das, “Thermal-aware compilation of spiking neural networks to neuromorphic hardware,” in _LCPC_ , 2020.
  * [92] T. Titirsha, S. Song, A. Das, J. Krichmar, N. Dutt _et al._ , “Endurance-aware mapping of spiking neural networks to neuromorphic hardware,” _TPDS_ , 2021.
  * [93] D. L. Silver, Q. Yang, and L. Li, “Lifelong machine learning systems: Beyond learning algorithms,” in _AAAI_ , 2013.
  * [94] G. W. Burr, M. J. Brightsky, A. Sebastian _et al._ , “Recent progress in phase-change memory technology,” _JETCAS_ , 2016.


# The equivalence between doubly nonnegative relaxation and semidefinite
relaxation for binary quadratic programming problems111This work is supported
by National Natural Science Foundation of China (Grant No. 11071158)

Chuan-Hao Guo<EMAIL_ADDRESS>Yan-Qin Bai<EMAIL_ADDRESS>Li-Ping Tang
<EMAIL_ADDRESS>Department of Mathematics, Shanghai University, Shanghai
200444, China

###### Abstract

It has recently been shown (Burer, Math. Program Ser. A 120:479-495, 2009)
that a large class of NP-hard nonconvex quadratic programming problems can be
modeled as so called completely positive programming problems, which are
convex but still NP-hard in general. A basic tractable relaxation is gotten by
doubly nonnegative relaxation, resulting in a doubly nonnegative programming.
In this paper, we prove that doubly nonnegative relaxation for binary
quadratic programming (BQP) problem is equivalent to a tighter semidifinite
relaxation for it. When problem (BQP) reduces to max-cut (MC) problem, doubly
nonnegative relaxation for it is equivalent to the standard semidifinite
relaxation. Furthermore, some compared numerical results are reported.

###### keywords:

binary quadratic programming, semidefinite relaxation, completely positive
programming, doubly nonnegative relaxation, max-cut problem

###### MSC:

90C10, 90C26, 49M20

##  1 Introduction

In this paper, we consider the following binary quadratic programming problem

$\rm{(BQP)}\ \ \ \ \ \begin{array}[]{lll}&\min&x^{T}Qx+2c^{T}x\\\ &{\rm
s.t.}&a_{i}^{T}x=b_{i},\ i=1,2,\ldots,m,\\\ &&x\in\\{-1,1\\}^{n},\\\
\end{array}$

where $x\in R^{n}$ is the variable, $Q\in R^{n\times n}$, $c\in R^{n}$,
$a_{i}\in R^{n}$ and $b_{i}\in R$ for all $i\in I:=\\{1,2,\dots,m\\}$ are the
data. Without loss of generality, $Q$ is symmetric, and we assume $Q$ is not
positive semidefinite, which implies generally that problem (BQP) is nonconvex
and NP-hard [1].

Problem (BQP) arises in many applications, such as financial analysis [2],
molecular conformation problem [3] and cellular radio channel assignment [4].
Many combinatorial optimization problems are special cases of problem (BQP),
such as max-cut problem [5]. For solving this type of problem, a systematic
survey of the solution methods can be found in Chapter 10 in [6] and the
references therein.

It is well-known that semidefinite relaxation (SDR) is a powerful,
computationally efficient approximation technique for a host of very difficult
optimization problems, for instance, max-cut problem [5], Boolean quadratic
program [7]. It also has been at the center of some of the very exciting
developments in the area of signal processing and communications [8, 9]. The
standard SDR for problem (BQP) is as follows:

$\rm{(SDR)}\ \ \ \ \ \begin{array}[]{lll}&\min&X\bullet Q+2c^{T}x\\\ &{\rm
s.t.}&a_{i}^{T}x=b_{i},\ \forall i\in I,\\\ &&a_{i}^{T}Xa_{i}=b_{i}^{2},\
\forall i\in I,\\\ &&X_{ii}=1,\ \forall i=1,2,\ldots,n,\\\ &&X\succeq
0,\end{array}$

where symbol $\bullet$ denotes the trace for any two conformal matrices. It is
obviously that problem (SDR) is convex and gives a lower bound for problem
(BQP) if the feasible set of problem (BQP) is nonempty. Moreover, if the
optimal solution $(x^{*},\ X^{*})$ for problem (SDR) satisfy
$X^{*}=x^{*}(x^{*})^{T}$, then we can conclude that $x^{*}$ is an optimal
solution for problem (BQP).

Recently, Burer [10] proves that a large class of NP-hard nonconvex quadratic
programs with a mix of binary and continuous variables can be modeled as so
called completely positive programs, which are convex but still NP-hard in
general. In order to solve such convex programs efficiently, a computable
relaxed problem is obtained by approximation the completely positive matrices
with doubly nonnegative matrices, resulting in a doubly nonnegative
programming [11], which can be efficiently solved by some popular packages.
For more details and developments of this technique, one may refer to [10, 11,
12, 13] and the references therein.

In this paper, a tighter SDR problem and a doubly nonnegative relaxation
(DNNR) problem for problem (BQP) are established, respectively, according to
the features of the constraints in problem (BQP) and the techniques of DNNP.
And, we prove that doubly nonnegative relaxation for problem (BQP) is
equivalent to the tighter semidefinite relaxation for it. Applying this result
to max-cut (MC) problem, it is shown that doubly nonnegative relaxation for
problem (MC) is equivalent to the standard semidefinite relaxation for it.
Moreover, some compared numerical results are reported to illustrate the
features of doubly nonnegative relaxation and semidefinite relaxation,
respectively.

The paper is organized as follows. In Section 2, a new tighter semidefinite
relaxation for problem (BQP) is proposed in Section 2.1. Problem (BQP) is
relaxed to a doubly nonnegative programming problem in Section 2.2. Section 3
and Section 4 are devoted to show the equivalence of two relaxation problems
for problem (BQP) and problem (MC), respectively. Some conclusions are given
in Section 5.

##  2 New relaxation for problem (BQP)

###  2.1 New tighter SDR for problem (BQP)

First, note that problem (BQP) also can be relaxed to the following problem by
SDR

$\widetilde{\rm{(SDR)}}\begin{array}[]{lll}&\min&X\bullet Q+2c^{T}x\\\ &{\rm
s.t.}&a_{i}^{T}x=b_{i},\ \forall i\in I,\\\ &&a_{i}^{T}Xa_{i}=b_{i}^{2},\
\forall i\in I,\\\ &&X_{ii}=1,\ \forall i=1,2,\ldots,n,\\\ &&X-xx^{T}\succeq
0.\end{array}$

If the optimal solution $(x^{*},\ X^{*})$ for problem $\widetilde{\rm{(SDR)}}$
satisfy $X^{*}=x^{*}(x^{*})^{T}$, it holds that $x^{*}$ also is an optimal
solution for problem (BQP). On one hand, it is worth noting that

$X-xx^{T}\succeq 0\Longrightarrow X\succeq 0$ (1)

holds always, which further implies that any feasible solution of problem
$\widetilde{\rm{(SDR)}}$ is also feasible for problem (SDR). It follows that
$\rm{Opt(SDR)}\leq\rm{Opt(\widetilde{\rm{SDR)}}}$ since the two problems have
the same objective functions, where $\rm{Opt(\ast)}$ denotes the optimal value
for problem $(\ast)$. Therefore, we can conclude that problem
$\widetilde{\rm{(SDR)}}$ is a tighter SDR problem for problem (BQP) than
problem (SDR).

On the other hand, we can easily verify that the constraint $X-xx^{T}\succeq
0$ is nonconvex, since the quadratic term $-xx^{T}$ is nonconvex. Thus,
problem $\widetilde{\rm{(SDR)}}$ is nonconvex and not solved by some popular
packages for solving convex programs. In order to establish the convex
representation for problem $\widetilde{\rm{(SDR)}}$, a crucial theorem is
given below and the details of its proof can be seen in Appendix A.5.5 Schur
complement in [14].

######  Theorem 2.1.

Let matrix $M\in S^{n}$ is partitioned as

$M=\left[\begin{array}[]{ll}A&B\\\ B^{T}&C\end{array}\right].$

If $\rm{det}A\neq 0$, the matrix $H=C-B^{T}A^{-1}B$ is called the Schur
complement of $A$ in $M$. Then, we have the following relations:
(i) $M\succ 0$ if and only if $A\succ 0$ and $H\succ 0$.
(ii) If $A\succ 0$, then $M\succeq 0$ if and only if $H\succeq 0$.

According to Theorem 2.1(ii) and (1), it holds immediately that

$\left[\begin{array}[]{ll}1&x^{T}\\\ x&X\end{array}\right]\succeq
0\Longleftrightarrow X-xx^{T}\succeq 0\Longrightarrow X\succeq 0,$ (2)

i.e., the constraint $X-xx^{T}\succeq 0$ can be equivalently reformulated as
$\left[\begin{array}[]{ll}1&x^{T}\\\ x&X\end{array}\right]\succeq 0$, which is
not only convex, but also computable. So, problem $\widetilde{\rm{(SDR)}}$ is
equivalently reformulated as follows:

${\rm{(SDR1)}}\begin{array}[]{lll}&\min&X\bullet Q+2c^{T}x\\\ &{\rm
s.t.}&a_{i}^{T}x=b_{i},\ \forall i\in I,\\\ &&a_{i}^{T}Xa_{i}=b_{i}^{2},\
\forall i\in I,\\\ &&X_{ii}=1,\ \forall i=1,2,\ldots,n,\\\
&&\left[\begin{array}[]{ll}1&x^{T}\\\ x&X\end{array}\right]\succeq
0,\end{array}$

which is not only convex in form, also can be efficiently solved by some
popular packages for solving convex programs.

Here, some examples are given to show that problem (SDR1) is a tighter
relaxation problem compared to problem (SDR), and the corresponding numerical
results further show that problem (SDR1) is more efficient than problem (SDR).
These examples are solved by CVX, a package for specifying and solving convex
programs [15].

######  Example 2.1.

This is a two dimensional nonconvex problem with one linear equality
constraint, the corresponding coefficients are selected as follows:

$Q=\left[\begin{array}[]{cc}0&-3\\\ -3&-20\end{array}\right],\
c=\left[\begin{array}[]{cc}-8\\\ 9\end{array}\right],\ \ A=[10,\ -10],\ \
b=0,$

where $A=[a_{1},a_{2},\ldots,a_{m}]^{T}$, $b=[b_{1},b_{2},\ldots,b_{m}]^{T}$.

On one hand, we use CVX to solve problem (SDR), then we obtain
$\rm{Opt(SDR)}=-\infty$, since problem (SDR) is unbounded below. On the other
hand, when problem (SDR1) is solved, it follows that $\rm{Opt(SDR1)}=-28$ with
$X=\left[\begin{array}[]{cc}1&1\\\ 1&1\end{array}\right]$ and $x=[-1,\
-1]^{T}$. Note that the relationship $X=xx^{T}$ holds, thus we can conclude
that $x=[-1,\ -1]^{T}$ also is an optimal solution for problem (BQP). The
results show that problem (SDR1) is more tighter and efficient than problem
(SDR) for this problem.

######  Example 2.2.

This problem is five dimensions with three linear equality constraints, the
corresponding coefficients are chosen as follows:

$Q=\left[\begin{array}[]{cccccc}-52&31&49&-7&4\\\ 31&-16&-50&-13&-49\\\
49&-50&8&44&-30\\\ -7&-13&44&36&12\\\ 4&-49&-30&12&56\end{array}\right],\ \ \
\ \ c=\left[\begin{array}[]{cc}-20\\\ 37\\\ 43\\\ 25\\\ -6\end{array}\right],$
$A=\left[\begin{array}[]{ccccc}4&10&29&14&-36\\\ 38&9&1&-17&23\\\
48&39&5&-17&-13\end{array}\right],\ \ \ \ \ \
b=\left[\begin{array}[]{ccc}11\\\ -50\\\ -36\end{array}\right].$

If this problem is solved by CVX with problem (SDR), then it returns
$\rm{Opt(SDR)}=-\infty$ since problem (SDR) is unbounded below. When we use
problem (SDR1) to solve this problem, we have $\rm{Opt(SDR1)}=-307.548$,
however, the relationship $X=xx^{T}$ is not holds for this problem. Therefore,
we obtain a tighter lower bound $-307.548$ for original problem. These results
also show that problem (SDR1) is more effective than problem (SDR).

In fact, the constraint $x\in\\{-1,+1\\}^{n}$ in problem (BQP) further imply
that the following relationship

$(1-x_{i})(1-x_{j})\geq 0\Rightarrow 1-x_{i}-x_{j}+X_{ij}\geq 0,\ \forall
1\leq i\leq j\leq n$ (3)

always hold. Combing with (3) in problem (SDR1), we get the following new
semidefinite relaxation problem

$\rm{(SDR2)}\begin{array}[]{lll}&\min&X\bullet Q+2c^{T}x\\\ &{\rm
s.t.}&a_{i}^{T}x=b_{i},\ \forall i\in I,\\\ &&a_{i}^{T}Xa_{i}=b_{i}^{2},\
\forall i\in I,\\\ &&X_{ii}=1,\ \forall i=1,2,\ldots,n,\\\
&&1-x_{i}-x_{j}+X_{ij}\geq 0,\ \forall 1\leq i\leq j\leq n,\\\
&&\left[\begin{array}[]{ll}1&x^{T}\\\ x&X\end{array}\right]\succeq
0.\end{array}$

The above semidefinite relaxation problem $\rm{(SDR2)}$ is more tighter than
problem $\rm{(SDR1)}$ in form, since $\frac{n(n+1)}{2}$ inequality constraints
are added into corresponding problem $\rm{(SDR2)}$. Furthermore, we will prove
that problem (SDR2) is equivalent to another convex relaxation problem for
problem (BQP) in Section 3.

Now, we test some problems to show that problem (SDR2) is tighter than problem
(SDR1) from the computational point of view. These problems are of one of two
types:

Table 1: Statistics of the test problems Type |  | Instances |  | $n$ |  | $m$ |  | Function
---|---|---|---|---|---|---|---|---
RdnBQP |  | $50$ |  | $50$ |  | $20$ |  | randn($\cdot$)
RdiBQP |  | $50$ |  | $50$ |  | $20$ |  | randi($[-10,10],\cdot$)

$\bullet$ RdnBQP. We generate $50$ instances of problem (BQP) by MATLAB
function randn($\cdot$). The symmetric matrix $Q$ is generated by
tril(randn($\cdot$),
-1)+triu(randn($\cdot$)’,0), and all instances are nonconvex.

$\bullet$ RdiBQP. $50$ instances of problem (BQP) are generated by MATLAB
function randi([-10, 10], $\cdot$). The symmetric matrix $Q$ is generated by
randn($\cdot$)+randn($\cdot$)’. Each element in the data coefficients is a
random integer number in the range $[-10,10]$. All instances are nonconvex
binary quadratic programming problems.

To compare the performance of two relaxation problems for problem (BQP), by
using problem (SDR1) and problem (SDR2), respectively, we use performance
profiles as described in Dolan and Moré’s paper [16]. Our profiles are based
on optimal values for problems (SDR1) and (SDR2). These problems are solved by
CVX, and the results of performance are shown in Figure 1. From Figure 1, it
is obviously that the lower bound which got from problem (SDR2) is much
greater than that one of from problem (SDR1), for test problems RdnBQP and
RdiBQP, respectively. Moreover, we find that optimal value of problem (SDR2)
is strictly greater than that of problem (SDR1) for test problems in the
experiment. Thus, the performance of problem (SDR2) is much better than
problem (SDR1) for solving problem (BQP) in some sense.

Figure 1: Left figure is based on optimal values of problems RdnBQP, right
figure is based on optimal values of problems RdiBQP.

###  2.2 Doubly nonnegative relaxation for problem (BQP)

Recently, Burer [10] has shown that a large class of NP-hard nonconvex
quadratic problems with binary constraints can be modeled as so-called
completely positive programs (CPP), i.e., the minimization of a linear
function over the convex cone of completely positive matrices subject to
linear constraints. Motivated by the ideas, we first establish the CPP
representation for problem (BQP), and then give its doubly nonnegative
relaxation (DNNR) formulation. Subsequently, some compared numerical results
are presented in this section.

Let $z=\frac{1}{2}(e-x)$ in problem (BQP), it follows that
$z\in\\{0,1\\}^{n}$, and then problem (BQP) can be equivalently reformulated
as follows:

$\widehat{\rm{(BQP)}}\begin{array}[]{lll}&\min&4z^{T}Qz-4z^{T}(Qe+c)+e^{T}Qe+2c^{T}e\\\
&{\rm s.t.}&2a_{i}^{T}z=a_{i}^{T}e-b_{i},\ \forall i\in I,\\\ &&z\in\\{0,\
1\\}^{n},\end{array}$

where $e$ denote the vector of ones with appropriate dimension. According to
Theorem 2.6 in [10] and similar to the analysis in it, problem
$\widehat{\rm{(BQP)}}$ can be further equivalently transformed into the
following CPP problem

${\rm{(CPP)}}\begin{array}[]{lll}&\min&4Q\bullet
Z-4z^{T}(Qe+c)+e^{T}Qe+2c^{T}e\\\ &{\rm s.t.}&2a_{i}^{T}z=a_{i}^{T}e-b_{i},\
\forall i\in I,\\\ &&4a_{i}^{T}Za_{i}=(a_{i}^{T}e-b_{i})^{2},\ \forall i\in
I,\\\ &&Z_{ii}=z_{i},\ \forall i=1,2,\ldots,n,\\\
&&\left[\begin{array}[]{ll}1&z^{T}\\\ z&Z\end{array}\right]\in
C_{1+n},\end{array}$

where $C_{1+n}$ is defined as follows:

$C_{1+n}:=\left\\{X\in S^{1+n}:\ X=\sum\limits_{k\in
K}z^{k}(z^{k})^{T}\right\\}\cup\\{0\\},$

and for some finite $\\{z^{k}\\}_{k\in K}\subset
R^{1+n}_{+}\backslash\\{0\\}$.

In view of the definition of convex cone in [14], $C_{1+n}$ is a closed convex
cone, and is called the completely positive matrices cone. Thus, problem (CPP)
is a convex problem. However, problem (CPP) is NP-hard, since checking whether
or not a given matrix belongs to $C_{1+n}$ is NP-hard, which has been shown by
Dickinson and Gijen in [17]. Thus, it has to be replaced by some computable
cones, which can efficiently approximate cone $C_{1+n}$. Note that the convex
cone $(S_{n})^{+}$ is self-dual, and so is the convex cone $S_{n}^{+}$, where
$(S^{n})^{+}$ and $S^{n}_{+}$ denotes the cone of $n\times n$ nonnegative
symmetric matrices and the cone of $n\times n$ positive semidefinite matrices,
respectively. Hence, Diananda’s decomposition theorem [18] can be reformulated
as follows.

######  Theorem 2.2.

$C_{n}\subseteq S_{n}^{+}\cap(S_{n})^{+}$ holds for all $n$. If $n\leq 4$,
then $C_{n}=S_{n}^{+}\cap(S_{n})^{+}$.

By the way, the matrices in $S_{n}^{+}\cap(S_{n})^{+}$ sometimes are called
“doubly nonnegative”. Of course, in dimension $n\geq 5$ there are matrices
which are doubly nonnegative but not completely positive, the counterexample
can be seen in [19].

According to Theorem 2.2, problem (CPP) can be relaxed to the following DNNP
problem

${\rm{(DNNP)}}\begin{array}[]{lll}&\min&4Q\bullet
Z-4z^{T}(Qe+c)+e^{T}Qe+2c^{T}e\\\ &{\rm s.t.}&2a_{i}^{T}z=a_{i}^{T}e-b_{i},\
\forall i\in I,\\\ &&4a_{i}^{T}Za_{i}=(a_{i}^{T}e-b_{i})^{2},\ \forall i\in
I,\\\ &&Z_{ii}=z_{i},\ \forall i=1,2,\ldots,n,\\\
&&\left[\begin{array}[]{ll}1&z^{T}\\\ z&Z\end{array}\right]\in
S_{1+n}^{+}\cap(S_{1+n})^{+}.\end{array}$

Up to now, the other convex relaxation problem for problem (BQP) is
established, i.e., problem (DNNP), which is computable by some popular
packages for solving convex programs, such as CVX, etc.

Note that problem (DNNP) has $n+\frac{n(n+1)}{2}$ equality constraints more
than standard semidefinite relaxation problem (SDR1), and $n$ equality
constraints more than problem (SDR2), respectively. Thus, the lower bound
which get from problem (DNNP) is much greater than that one of by problem
(SDR1) and problem (SDR2), respectively.

In the following, two types of problems are tested to show the performance of
problem (SDR1), problem (SDR2) and problem (DNNP), respectively. The
statistics of the test problems are chosen as follows:

Table 2: Statistics of the test problems Type |  | Instances |  | $n$ |  | $m$ |  | Function
---|---|---|---|---|---|---|---|---
RdBQP |  | $50$ |  | $50$ |  | $25$ |  | rand($\cdot$)
RdsBQP |  | $50$ |  | $50$ |  | $25$ |  | rands($\cdot$)

$\bullet$ RdBQP. For this type of problems, we generate $50$ instances of
problem (BQP) by using MATLAB function rand($\cdot$). The symmetric matrix $Q$
is generated by rand($\cdot$)+rand($\cdot$)’, and all problems are nonconvex.

$\bullet$ RdsBQP. The coefficients of $50$ instances of problem (BQP) are
generated by using MATLAB function rands($\cdot$), and the symmetric matrix
$Q$ is generated by rands($\cdot$)+rands($\cdot$)’. All instances are
nonconvex.

We use performance profiles [16] to compare the performance of problem (SDR1),
problem (SDR2) and problem (DNNP), for problem (BQP), respectively. The
corresponding results of performance are shown in Figure 2. The profiles for
Figure 2 are based on optimal values of problem (SDR1), problem (SDR2) and
problem (DNNP), respectively, and these problems are solved by CVX. From
Figure 2, it is obviously that the performances of problem (SDR2) and problem
(DNNP) are almost the same, which are better than that one of problem (SDR1),
for problems RdBQP and RdsBQP, respectively. Thus, we can conclude that it is
more efficient to use problem (SDR2) and problem (DNNP) than problem (SDR1) to
solve problem (BQP), from the point of view of optimal values.

Furthermore, we will show the equivalence of the problems (DNNP) and (SDR2) in
Section 3.

Figure 2: Left figure is based on optimal values of problems RdBQP, right
figure is based on optimal values of problems RdsBQP.

##  3 Relationship between relaxation problems

In this section, we will investigate the relationship between two relaxation
problems (SDR2) and (DNNP). First of all, the definition of the equivalence of
two optimization problems is defined as follows.

######  Definition 3.1.

We call two problems are equivalent if they satisfy the following two
conditions:

(i) If from a solution of one problem, a solution of the other problem is
readily found, and vice versa.

(ii) The two problems have the same optimal value.

Now, based on the above Definition 3.1, the main theorem is given below.

######  Theorem 3.1.

Suppose that the feasible sets $\rm{Feas(SDR2)}$ and $\rm{Feas(DNNP)}$ are all
nonempty. Then, two problems (SDR2) and (DNNP) are equivalent.

###### Proof.

The proof can be divided into two parts. First of all, we will prove that
$\rm{Opt(SDR2)\geq Opt(DNNP)}$.

Suppose that $(x^{*},X^{*})$ is an optimal solution of problem $\rm(SDR2)$,
let $Z_{ij}=\frac{1}{4}(1-x_{i}^{*}-x_{j}^{*}+X_{ij}^{*})$ and
$z_{i}=\frac{1}{2}(1-x_{i}^{*}),\ \forall 1\leq i\leq j\leq n$, i.e.,

$Z=\frac{1}{4}(ee^{T}-e(x^{*})^{T}-x^{*}e^{T}+X^{*}),\
z=\frac{1}{2}(e-x^{*}).$ (4)

By $a_{i}^{T}x^{*}=b_{i}$ for all $i\in I$ and (4), we have

$a_{i}^{T}x^{*}=a_{i}^{T}(e-2z)=b_{i}\Rightarrow
2a_{i}^{T}z=a_{i}^{T}e-b_{i},\ \forall i\in I.$ (5)

From (4) and $a_{i}^{T}X^{*}a_{i}=b_{i}^{2}$ for all $i\in I$, it follows that

$\begin{array}[]{ll}a_{i}^{T}X^{*}a_{i}&=a_{i}^{T}(4Z-ee^{T}+e(x^{*})^{T}+x^{*}e^{T})a_{i}=b_{i}^{2}\\\
&\Rightarrow 4a_{i}^{T}Za_{i}=(a_{i}^{T}e-b_{i})^{2},\ \forall i\in
I.\end{array}$ (6)

Again from (4), which imply that

$Z_{ii}=\frac{1}{4}(1-2x_{i}^{*}+X_{ii}^{*})=\frac{1}{2}(1-x_{i}^{*})=z_{i},\
\forall i\in I,$ (7)

since $X_{ii}^{*}=1$.

From $1-x_{i}^{*}-x_{j}^{*}+X_{ij}^{*}\geq 0,\forall 1\leq i\leq j\leq n$, it
holds that

$Z_{ij}\geq 0,\forall 1\leq i\leq j\leq n,$ (8)

which combining with (7), further imply that

$z_{i}\geq 0,\forall 1\leq i\leq n.$ (9)

By Theorem 2.1(ii) and (4), it follows that

$\begin{array}[]{ll}Z-zz^{T}&=\frac{1}{4}(ee^{T}-e(x^{*})^{T}-x^{*}e^{T}+X^{*})-\frac{1}{4}(e-x^{*})(e-x^{*})^{T}\\\
&=\frac{1}{4}(X^{*}-x^{*}(x^{*})^{T})\succeq 0.\end{array}$ (10)

Combining (10) with (5), (6), (8) and (9), it follows that $(z,Z)$ defined by
(4) is a feasible solution for problem $\rm{(DNP)}$.

Moreover, again from (4), we have

$\begin{array}[]{ll}4Q\bullet Z-4z^{T}(Qe+c)+e^{T}Qe+2c^{T}e\\\
=Q\bullet(ee^{T}-e(x^{*})^{T}-x^{*}e^{T}+X^{*})-2(e-x^{*})^{T}(Qe+c)+e^{T}Qe+2c^{T}e\\\
=Q\bullet X^{*}+2c^{T}x^{*}=\rm{Opt(SDR2)},\end{array}$

which further imply that $\rm{Opt}(DNNP)\leq\rm{Opt}(SDR2)$.

On the other hand, given an optimal solution $(z^{*},Z^{*})$ to problem
(DNNP), and let

$X_{ij}=1-2z_{i}^{*}-2z_{j}^{*}+4Z_{ij}^{*},\ x_{i}=1-2z^{*}_{i},\ \forall
1\leq i\leq j\leq n,$ (11)

which imply that

$X_{ii}=1-4z^{*}_{i}+4Z^{*}_{ii}=1$ (12)

since $Z^{*}_{ii}=z^{*}_{i},\ \forall i=1,2,\ldots,n$. Moreover,

$\begin{array}[]{ll}1-x_{i}-x_{j}+X_{ij}&=1-(1-2z_{i}^{*})-(1-2z_{j}^{*})+1-2z_{i}^{*}-2z_{j}^{*}+4Z_{ij}^{*}\\\
&=4Z_{ij}^{*}\geq 0,\ \forall 1\leq i\leq j\leq n.\end{array}$ (13)

From (11) and $2a_{i}^{T}z^{*}=a_{i}^{T}e-b_{i},\ \forall i\in I$, it follows
that

$a_{i}^{T}x=a_{i}^{T}(e-2z^{*})=b_{i},\ \forall i\in I.$ (14)

Again from (11) and $4a_{i}^{T}Z^{*}a_{i}=(a_{i}^{T}e-b_{i})^{2},\ \forall
i\in I$, we have

$\begin{array}[]{ll}a_{i}^{T}Xa_{i}&=a_{i}^{T}(ee^{T}-2e(z^{*})^{T}-2z^{*}e^{T}+4Z^{*})a_{i}\\\
&=b_{i}^{2},\ \forall i\in I.\end{array}$ (15)

From (11) and Theorem 2.1(ii), it holds that

$\begin{array}[]{lll}X-xx^{T}&=ee^{T}-2z^{*}e^{T}-2e(z^{*})^{T}+4Z^{*}-(e-2z^{*})(e-2z^{*})^{T}\\\
&=4(Z^{*}-z^{*}(z^{*})^{T})\succeq 0.\end{array}$ (16)

By (13), (14), (15) and (16), we can conclude that $(x,X)$ defined by (11) is
a feasible solution for problem $\rm{(SDR2)}$. Furthermore, we have

$\begin{array}[]{ll}X\bullet
Q+2c^{T}x&=(ee^{T}-2e(z^{*})^{T}-2z^{*}e^{T}+4Z^{*})\bullet
Q+2c^{T}(e-2z^{*})\\\ &=4Z^{*}\bullet Q-4(z^{*})^{T}(Qe+c)+e^{T}Qe+2c^{T}e\\\
&=\rm{Opt(DNNP)},\end{array}$

which imply that $\rm{Opt}(SDR2)\leq\rm{Opt}(DNNP)$. Summarizing the analysis
above and according to Definition 3.1, we can conclude that problem (DNNP) is
equivalent to problem (SDR2). ∎

Although $\rm{Opt}(SDR2)=\rm{Opt}(DNNP)$ in view of Theorem 3.1 and Definition
3.1, problem (DNNP) has $n$ equality constraints more than problem (SDR2) in
form. So, the amount of computation for solving problem (DNNP) may be much
greater than that one of solving problem (SDR2). In order to illustrate this
point of view, the compared performance results are shown in Figure 3 and
Figure 4, respectively, which are based on the number of iterations and CPU
time for solving problems RdBQP and RdsBQP. The results in Figure 3 show that
the performance of problem (SDR2) is better than that one of problem (DNNP)
for problems RdBQP, but the performance of problem (DNNP) is better than that
one of problem (SDR2) for problems RdsBQP, in view of the points of the number
of iterations. From the results of the performance of CPU time, it is
obviously that problem (SDR2) is more efficient than problem (DNNP) for
solving problems RdBQP and RdsBQP, respectively. Summarizing the analysis
above, we can efficiently solving problem (BQP) by soling problem (SDR2) or
problem (DNNP) in practice.

Figure 3: Left figure is based on the number of iterations of problems RdBQP,
right figure is based on the number of iterations of problems RdsBQP.

Figure 4: Left figure is based on CPU time of problems RdBQP, right figure is
based on CPU time of problems RdsBQP.

##  4 An application to max-cut problem

The max-cut (MC) problem is a kind of important combinatorial optimization
problem on undirected graphs with weights on the edges, and also is NP-hard
[20]. Given such a graph, (MC) problem consists in finding a partition of the
set of nodes into two parts so as to maximize the total weight of edges cut by
the partition.

Let $G$ be an $n$-node graph, vertex set $V:=\\{1,2,\ldots,n\\}$, $A(G)$ the
adjacency matrix of graph $G$, $L$ the Laplacian matrix associated with the
graph, i.e., $L:={\rm{Diag}}(A(G)e)-A(G)$. Let the vector
$u\in\\{+1,-1\\}^{n}$ represent any cut in the graph $G$ via the
interpretation that the sets $\\{i:u_{i}=+1\\}$ and $\\{i:u_{i}=-1\\}$ form a
partition of the node set of $G$, we can get the following formulation for
(MC) problem

$\rm{(MC)}\begin{array}[]{lll}&\max&\frac{1}{4}u^{T}Lu\\\ &{\rm
s.t.}&u\in\\{+1,-1\\}^{n}.\end{array}$

On one hand, by using the standard semidefinite relaxation technique to (MC)
problem, we can get the following problem

$\rm{\widehat{(SDR)}}\begin{array}[]{lll}&\max&\frac{1}{4}L\bullet U\\\ &{\rm
s.t.}&U_{ii}=1,\ \forall i=1,2,\ldots,n,\\\ &&U\succeq 0.\end{array}$

Goemans and Williamson [5] have provided estimates for the quality of problem
$(\rm\widehat{SDR})$ bound for (MC) problem. By a randomly rounding a solution
to problem $(\rm\widehat{SDR})$, they propose a $0.878$-approximation
algorithm for solving problem (MC) based on problem $(\rm\widehat{SDR})$,
which is known to be the best approximation ration of polynomial-time
algorithm for solving problem (MC).

On the other hand, according to the technique introduced in Section 2.2,
problem (MC) can also be relaxed to the following doubly nonnegative
programming problem

$\rm{\widehat{(DNNP)}}\begin{array}[]{lll}&\max&L\bullet
X-x^{T}Le+\frac{1}{4}e^{T}Le\\\ &{\rm s.t.}&X_{ii}=x_{i},\ \forall
i=1,2,\ldots,n,\\\ &&\left[\begin{array}[]{ccc}1&x^{T}\\\
x&X\end{array}\right]\in S_{1+n}^{+}\cap(S_{1+n})^{+}.\end{array}$

######  Remark 4.1.

(i) Note that for two relaxation problems $\rm{\widehat{(SDR)}}$ and
$\rm{\widehat{(DNNP)}}$, the feasible sets are all nonempty. It is obviously
that the identity matrix $E$ is a feasible solution for problem
$\rm{\widehat{(SDR)}}$, and $(x,X)=(0,\mathbf{0})$ feasible for problem
$\rm{\widehat{(DNNP)}}$.

(ii) Compared with problem $\rm{\widehat{(SDR)}}$, problem
$\rm{\widehat{(DNNP)}}$ has not only $n+\frac{n(n+1)}{2}$ new inequality
constraints, but also $n$ variables.

Thus, according to Theorem 3.1 and Remark 4.1(i), we have the following
theorem.

######  Theorem 4.1.

Problem $\rm\widehat{(SDR)}$ is equivalent to problem $\rm\widehat{(DNNP)}$.

###### Proof.

On one hand, suppose that $U^{*}$ is an optimal solution for problem
$\rm\widehat{(SDR)}$, and let $X_{ij}=\frac{1}{4}(U^{*}_{ij}+1)$ and
$x_{i}=\frac{1}{2}$, $\forall 1\leq i\leq j\leq n$, i.e.,

$X=\frac{1}{4}(U^{*}+ee^{T}),\ x=\frac{1}{2}e,$ (17)

which imply that

$X_{ii}=\frac{1}{4}(U^{*}_{ii}+1)=x_{i}=\frac{1}{2}>0,\ \forall 1\leq i\leq
n,$ (18)

since $U_{ii}^{*}=1$. Then, from $U^{*}\succeq 0$, it follows that

$0\leq U^{*}_{ii}U^{*}_{jj}-(U^{*}_{ij})^{2}=1-(U^{*}_{ij})^{2},$

i.e.,

$-1\leq U^{*}_{ij}\leq 1,\ \forall 1\leq i<j\leq n,$

combining with (17), we have

$X_{ij}=\frac{1}{4}(U^{*}_{ij}+1)\geq 0,\ 1\leq i<j\leq n.$ (19)

Moreover, from (17), it follows that

$X-xx^{T}=\frac{1}{4}(U^{*}+ee^{T})-\frac{1}{4}ee^{T}=\frac{1}{4}U^{*}\succeq
0,$ (20)

it followed by $U^{*}\succeq 0$. Combining (18), (19) and (20) as well as
Theorem 2.1(ii), it holds that $(x,X)$ is a feasible solution for problem
$\rm\widehat{(DNNP)}$. Again from (17), we have $L\bullet
X-x^{T}Le+\frac{1}{4}e^{T}Le=\frac{1}{4}L\bullet
U^{*}=\rm{Opt}\widehat{(SDR)}$, which further imply that
$\rm{Opt}\widehat{(DNNP)}\geq\rm{Opt}\widehat{(SDR)}$.

On the other hand, suppose that $(x^{*},X^{*})$ is an optimal solution for
problem $\rm\widehat{(DNNP)}$, and let

$U=4X^{*}-2x^{*}e^{T}-2e(x^{*})^{T}+ee^{T},$ (21)

which imply that

$U_{ii}=4X_{ii}^{*}-2x^{*}_{i}-2x^{*}_{i}+1=1,\ \forall 1\leq i\leq n,$ (22)

since $X_{ii}^{*}=x_{i}^{*},\ \forall 1\leq i\leq n$. From (21), it follows
that

$\begin{array}[]{ll}U&=4X^{*}-2e(x^{*})^{T}-2x^{*}e^{T}+ee^{T}\\\
&=4(X^{*}-x^{*}(x^{*})^{T})+(2x^{*}-e)(2x^{*}-e)^{T}\succeq 0.\end{array}$
(23)

From (22) and (23), we can conclude that $U$ defined by (21) is a feasible
solution for problem $\rm\widehat{(SDP)}$. Furthermore, again from (21), we
have

$\frac{1}{4}L\bullet U=L\bullet
X^{*}-(x^{*})^{T}Le+\frac{1}{4}e^{T}Le=\rm{Opt}\widehat{(DNNP)},$

which imply that $\rm{Opt}\widehat{(SDR)}\geq\rm{Opt}\widehat{(DNNP)}$. The
proof is completed. ∎

By Theorem 4.1, we can obtain doubly nonnegative relaxation for problem (MC)
exactly equal to the standard semidefinite relaxation, i.e. problem
$\rm{\widehat{(DNNP)}}$ and problem $\rm{\widehat{(SDR)}}$ are equivalent
according to Definition 3.1, without the boundedness assumption of two
feasible sets of two problems.

##  5 Conclusions

In this paper, a class of nonconvex binary quadratic programming problem is
considered, which is NP-hard in general. In order to solve this problem
efficiently by some popular packages for solving convex programs, two convex
representation methods are proposed. One of the methods is semidefinite
relaxation, by the structure of the binary constraints of original problem,
which results in a new tighter semidefinite relaxation problem (SDR2). The
other method is doubly nonnegative relaxation. The original problem is
equivalently transformed into a convex problem (CPP), which is also NP-hard in
general. Then, by virtue of the features of constraints in this problem, a
computable convex problem (DNNP) is obtained through doubly nonnegative
relaxation. Moreover, the two convex relaxation problems are equivalent. These
results are applied to (MC) problem, we can conclude that doubly nonnegative
relaxation for problem (MC) is equivalent to the standard semidefinite
relaxation for it. Furthermore, some compared numerical results are reported
to show the performance of two relaxed problems.

## References

  * Pardalos and Vavasis [1991] P. Pardalos, S. Vavasis,  Quadratic programming with one negative eigenvalue is np-hard,  Journal of Global Optimization 1 (1991) 15–22.
  * McBride and Yormark [1980] R. McBride, J. Yormark,  An implicit enumeration algorithm for quadratic integer programming,  Management Science (1980) 282–296.
  * Phillips and Rosen [1994] A. Phillips, J. Rosen,  A quadratic assignment formulation of the molecular conformation problem,  Journal of Global Optimization 4 (1994) 229–241.
  * Chardaire and Sutter [1995] P. Chardaire, A. Sutter,  A decomposition method for quadratic zero-one programming,  Management Science (1995) 704–712.
  * Goemans and Williamson [1995] M. Goemans, D. Williamson,  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,  Journal of the Association for Computing Machinery 42 (1995) 1115–1145.
  * Li and Sun [2006] D. Li, X. Sun, Nonlinear integer programming, Springer, New York, 2006\.
  * Poljak et al. [1995] S. Poljak, F. Rendl, H. Wolkowicz,  A recipe for semidefinite relaxation for (0, 1)-quadratic programming,  Journal of Global Optimization 7 (1995) 51–73.
  * Ma et al. [2002] W. Ma, T. Davidson, K. Wong, Z. Luo, P. Ching,  Quasi-maximum-likelihood multiuser detection using semi-definite relaxation with application to synchronous cdma,  IEEE Transactions on Signal Processing 50 (2002) 912–922.
  * Ma et al. [2009] W. Ma, C. Su, J. Jalden, T. Chang, C. Chi,  The equivalence of semidefinite relaxation mimo detectors for higher-order qam,  IEEE Journal of Selected Topics in Signal Processing 3 (2009) 1038–1052.
  * Burer [2009] S. Burer,  On the copositive representation of binary and continuous nonconvex quadratic programs,  Mathematical Programming 120 (2009) 479–495.
  * Burer [2010] S. Burer,  Optimizing a polyhedral-semidefinite relaxation of completely positive programs,  Mathematical Programming Computation 2 (2010) 1–19.
  * Bomze [2012] I. Bomze,  Copositive optimization-recent developments and applications,  European Journal of Operational Research 216 (2012) 509–520.
  * Ge and Ye [2010] D. Ge, Y. Ye,  On doubly positive semidefinite programming relaxations (2010). http://www.optimization-online.org/DB_HTML/2010/08/2709.pdf.
  * Boyd and Vandenberghe [2004] S. Boyd, L. Vandenberghe, Convex optimization, Cambridge University Press, 2004.
  * Grant and Boyd [2011] M. Grant, S. Boyd, CVX: Matlab software for disciplined convex programming, version 1.21, http://cvxr.com/cvx, 2011.
  * Dolan and Moré [2002] E. Dolan, J. Moré,  Benchmarking optimization software with performance profiles,  Mathematical Programming 91 (2002) 201–213.
  * Dickinson and Gijben [2011] P. Dickinson, L. Gijben, On the computational complexity of membership problems for the completely positive cone and its dual, Technical Report, Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen, The Netherlands, 2011.
  * Diananda [1962] P. Diananda,  On non-negative forms in real variables some or all of which are non-negative,  in: Mathematical Proceedings of the Cambridge Philosophical Society, volume 58, Cambridge University Press, pp. 17–25.
  * Berman and Shaked-Monderer [2003] A. Berman, N. Shaked-Monderer, Completely positive matrices, World Scientific Pub Co Inc, 2003.
  * Karp [2010] R. Karp,  Reducibility among combinatorial problems,  50 Years of Integer Programming 1958-2008 (2010) 219–241.