Why VCG auctions can hardly be applied to the pricing of inter-domain and ad hoc networks Abstract-The use of Vickrey-Clarke-Groves (VCG) auction is gaining popularity in the networking community, where it seems compulsory to incentivize selfish nodes (in ad hoc networks) or domains (in inter-domain communications) to forward the traffic of their peers. Indeed, VCG auctions are known to both be efficient and produce proper incentives.

In this note, we argue that, in fact, VCG auctions can hardly be applied to those problems, for different reasons depending on the model studied:

• if some resource constraints (bandwidth, spectrum, and/or power) have to be taken into account, then computing allocations and prices implies solving optimization problems that are computationally hard for general network topologies.

• If there are no such resource constraints, then VCG auctions, even if verifying many important and satisfactory properties, cannot verify a major one that is budget balance: the sum of subsidies given to relay nodes exceeds the sum of charges paid by traffic senders. This means that the auction regulator is required to continuously inject money to make the scheme work, which is unlikely to happen. In a second step, we discuss the combinations of properties that can be verified together, and prioritize them for finding out a proper pricing scheme.

I. INTRODUCTION

The Internet has become a commercial and competitive network with many service providers. Those providers need to exchange traffic to ensure end-to-end delivery, which requires peering agreements so that go-between domains accept to forward traffic. Very similar problems occur in ad hoc networks where nodes, the terminals, are assumed to forward the traffic of others at the expense of their own battery power.

Pricing appears a promising way to introduce incentives for forwarding traffic in both of those contexts. Vickrey-Clarke-Groves (VCG) auctions especially have recently received a lot of attention since they are known to yield efficient outcomes, with enjoyable properties such as incentive compatibility, meaning that players' best interest is to reveal their true valuation of the proposed service, or individual rationality, meaning that players will always benefit from entering the auction.

Here, we aim at showing that, actually, VCG auctions are difficult to implement in inter-domain or ad hoc networks. While they enjoy the incentive compatibility, individual rationality, and efficiency properties, they present at least one prohibitive drawback: either they need a computationally difficult optimization problem to be solved, or they require that the auction manager insert money into the game since the sum of payments from those sending (or receiving) traffic is always less than the sum of awards distributed to those forwarding. This last problem is not only verified on the specific problems of pricing inter-domain and ad hoc networks, but has been shown in the literature in a general setting, making it irrelevant to try and get budget balance by modifying the original models.

This situation of non-balance seems to us likely to deter from implementation. We therefore further discuss the properties that a pricing scheme should enjoy, try to prioritize them, and look at the possible combinations, in order to provide hints on the families of pricing schemes that should be dealt with.

Note that this kind of problem has recently received some attention in the economics community. Indeed, in [START_REF] Moulin | Strategyproof sharing of submodular costs: Budget balance versus efficiency[END_REF], it is shown that when preferences are quasi-linear, an incentive compatible mechanism can be efficient or can balance the budget, but it cannot do both at the same time. The authors then characterize a class of budget balanced and incentive compatible mechanisms, and single out the one with the smallest welfare loss (based on the Shapley value formula). They also conversely look at mechanisms which are efficient and not balanced budget. Though, the context of that work is slightly different from ours, since their problem consists in sharing the cost of a given service among users, where the cost is a submodular function of the set of receiving service, and where users cannot be partially served. The objective function is therefore different: there is no allocation rate involved, and there is no real focus on a network topology.

II. PRINCIPLES AND PROPERTIES OF VCG AUCTIONS

Again, pricing has been seen as a means of interest to introduce incentives in situations where each new user introduces an added-value to the network capability; interdomain routing and ad hoc networks being typical areas of applications. Indeed, a very basic idea would be for instance to extend the current Border Gateway Protocol (BGP) to allow interdomain routing. The extension would consist in introducing pricing such that each intermediate provider would receive a financial incentive for accepting to forward packets of concurrent providers. It is exactly the same problem in ad hoc networks where forwarding packets of neighbors is at the expense of limited battery capacities, and therefore needs to be compensated in some way. VCG auctions have been regarded as one of the most prevalent ways to introduce rewarding issues. In all those applications, each player (a domain in case of interdomain routing or a node of the ad hoc network) tries to maximize its own benefits, that is the valuation for sending its own traffic (depending on the volume of traffic he sends), plus the amount of money gained from the forwarded traffic, minus the cost of sending traffic (financial cost plus engineering cost, in terms of battery for instance).

Vickrey-Clarke-Groves auctions [START_REF] Vickrey | Counterspeculation, auctions, and competitive sealed tenders[END_REF], [START_REF] Clarke | Multipart pricing of public goods[END_REF], [START_REF] Groves | Incentives in teams[END_REF] apply to any problem where players (users) have a quasi-linear utility function. This means that the utility U i of each user i depends on the outcome (say, the resource allocation vector) a and on the price c i he is charged (notice that c i can be non-positive when i is subsidized), and can be written

U i (a, c i ) = θ i (a) -c i ,
where θ i is called the valuation or willingness-to-pay function of user i.

VCG auctions work as follows:

1) each user is asked to reveal his valuation function (let us denote by θi the function declared by user i with real valuation function θ i ); 2) the mechanism computes an outcome a( θ) that maximizes the declared social welfare1 :

a( θ) ∈ arg max x i θi (x); (1)
3) the price paid by each user corresponds to the loss of declared welfare he imposes to the others through his presence:

c i = max x j =i θj (x) - j =i θj (a( θ)). (2)
Then the mechanism verifies three major properties:

• Incentive compatibility: for each user, bidding truthfully (i.e. declaring θi = θ i ) is a dominant strategy. • Individual rationality: each truthful player obtains a nonnegative utility. • Efficiency: when players bid truthfully, social welfare ( i θ i ) is maximized.

III. VCG AUCTIONS IN INTER-DOMAIN OR AD HOC

NETWORKS

In networks, the form of each agent i's valuation function θ i can be precised:

• traffic initiators (senders) are accepting to pay up to a threshold to obtain a given transmission rate from one point to another: therefore their valuation function depends only on their own resource allocation. Depending on the type of flow, the individual demand of a sender can be elastic (that is tolerant to variations in the obtained service) or inelastic (that is with strict requirements). • Intermediate nodes or domains have a negative valuation function, that reflects their perceived costs for transferring traffic. Generally, those costs depend on the total amount of traffic that has to be transferred, or (in ad hoc networks using power control) on the total power needed to transfer that traffic. The goals of introducing VCG auctions in inter-domain or ad hoc networks is to obtain an efficient routing (by enforcing cooperation) and to incentivize participation for transferring traffic. The rules are designed such that the senders (or receivers) pay for the traffic that is carried and the intermediate nodes are subsidized for transferring traffic, compensating their transmission costs. The amount to be awarded is defined by the specific pricing rule (2) employed.

In the following, we argue that VCG auctions applied to such networks present at least one prohibitive drawback, large computational complexity and/or negative budget balance, depending on whether resource constraints are taken into account when determining the outcome.

A. Networks with resource constraints: VCG and computational complexity

When communication links are not overdimensioned (which is particularly true in ad hoc networks where the transmission rates are limited by the radio spectrum, and where interference degrades even more those transmission rates), it may not be possible to satisfy all requests because of congestion. VCG auctions in such contexts would then serve at the same time (i) as an incentive for intermediate nodes to transfer traffic, and (ii) as a rule for selecting the accepted and rejected requests.

Following VCG principles, each potential sender declares his willingness-to-pay function, and each potential intermediate node (i.e. each node, since all node are likely to transfer traffic) declares his cost function. Then allocations are computed in order to maximize the sum of declared valuations (social welfare), that is the sum of prices senders are willing to pay minus the sum of transfer costs (by summing over all senders and intermediate nodes). However, a problem due to the complexity of that computation appears when the set of possible allocations is constrained by resource bounds. More precisely, determining in general the most efficient allocation is a NP-hard problem. As an example, consider a very simple model with only one intermediate node, say A, that cannot transfer more than a given amount Q of traffic, and N potential senders with inelastic demand that need the help of A to reach their destination, as represented in Figure 1. The valuation function θ i of each potential sender i with non-elastic demand is θ i (a i ) = β i 1l ai≥αi , which means that sender i is willing to pay β i if he is allocated at least α i , and 0 otherwise. Then, even if the transferring cost for A is null, maximizing the social welfare i θ i (a i ) under the constraint i a i ≤ Q resumes to solving the knapsack problem, which is known to be NP-hard [START_REF] Woeginger | Exact algorithms for NP-hard problems: A survey[END_REF]. In the above example, NP-hardness comes from the inelasticity of demands. For elastic demands, determining the most efficient allocation through both routing and allocations is also NP-hard for non-trivial network topologies when routes have to be single-path [START_REF] Wang | Can shortest-path routing and tcp maximize utility[END_REF].

To emphasize on the complexity problems that stem from the application of VCG auctions in networks with capacity constraints, remember that the computation of the price paid (resp. the subsidy received) by each sender (resp. intermediate) needs another optimization problem to be solved (see Equation ( 2)). Applying VCG auctions with N users therefore implies N + 1 optimization problems to be solved: those problems must be computationally simple enough.

B. Transfer costs with no resource constraints: VCG and budget balance

Some networks can be dimensioned such that congestion never occurs. This might be the case for example in core networks, that use the latest technologies and allow high communication rates. It can therefore be assumed that interdomain routing never introduces new constraints due to resource limits. The transfer costs for an intermediate domain are then modelled as being proportional to the amount of traffic to transfer.

Vickrey-Clarke-Groves auctions seem consequently wellsuited to this context, since a request has no effect on another one, and maximizing the overall social welfare can then be done by performing independently a least-cost path search for each request, removing the complexity issue of previous subsection.

This kind of model is assumed in [START_REF] Feigenbaum | A BGPbased mechanism for lowest-cost routing[END_REF], [START_REF] Hershberger | Vickrey prices and shortest paths: What is an edge worth?[END_REF], where VCG auctions are used to produce the incentives to transfer traffic. The model consists of n domains (or autonomous systems), numbered from 1 to n. Inter-domain routing is handled by a simple modification of the Border Gateway Protocol (BGP) [START_REF] Feigenbaum | A BGPbased mechanism for lowest-cost routing[END_REF]. It is assumed that the amount of traffic is T ij from domain i to domain j, and that the per-packet transit cost is c k for domain k (1 ≤ k ≤ n). Valuation of intermediate domain k for a given allocation (here, a routing decision) is thus

θ k (routing) = -c k {(i,j) routed trough k} T ij . ( 3
)
Each domain is asked to declare its transit cost c k , and the least (declared) cost route path(i, j) is computed for each origindestination pair (i, j). Since there are no resource constraint, those routes minimize the total (declared) cost i,j

T ij k∈path(i,j) c k ,
which amounts to the maximization problem (1) when using [START_REF] Clarke | Multipart pricing of public goods[END_REF]. Equivalently, the computation of VCG subsidies for each domain k can be done per each origin-destination pair (i, j), by applying the pricing rule (2) to the problem of routing only the traffic from i to j. Those subsidies ensure that intermediate domains, acting selfishly, truthfully reveal their transfer costs, and therefore that the routing is efficient. Nevertheless, one question not addressed in [START_REF] Feigenbaum | A BGPbased mechanism for lowest-cost routing[END_REF], [START_REF] Hershberger | Vickrey prices and shortest paths: What is an edge worth?[END_REF] is: who pays the subsidies? It is natural to think that the origin2 should pay them, but would that be suitable if the sum of subsidies equals 10$ while the sender is willing to pay only 1$ for his traffic to reach destination?

Actually, an efficient scheme should take into account the willingness-to-pay of the traffic sender to determine whether it is socially optimal for that traffic to be carried (which is the case if and only if the sender valuation for the traffic exceeds the sum of tranfer costs of the intermediate domains). VCG auctions fit perfectly with that case: just consider the traffic sender as a player that is asked to declare the maximum price he is willing to pay. Then because of social welfare maximization [START_REF] Moulin | Strategyproof sharing of submodular costs: Budget balance versus efficiency[END_REF], that traffic will only be sent if it socially profitable, and the pricing rule (2) will determine a price to pay for the sender such that truthfully declaring his willingnessto-pay is a dominant strategy.

The same kind of model is presented by Anderegg and Eidenbenz [START_REF] Anderegg | Ad hoc-VCG: A truthful and costefficient routing protocol for mobile ad hoc networks with selfish agents[END_REF] for incentivizing cooperation in ad hoc networks, with the same drawbacks as in [START_REF] Feigenbaum | A BGPbased mechanism for lowest-cost routing[END_REF], [START_REF] Hershberger | Vickrey prices and shortest paths: What is an edge worth?[END_REF]. Basically, transfer costs depend here on the minimum power required to reach the next neighbour. The model therefore generalizes the one in [START_REF] Feigenbaum | A BGPbased mechanism for lowest-cost routing[END_REF] by associating several costs to each node, one per neighbour, instead of just one. The analysis and results are identical though. The sender's willingness-to-pay is (again) not taken into account, but it is assumed that the sender should pay the total declared transfer cost. Though, for a VCG auction where both intermediates and senders are treated as selfish players, the VCG price that the sender should pay according to [START_REF] Vickrey | Counterspeculation, auctions, and competitive sealed tenders[END_REF] is the sum of declared costs if the traffic is effectively sent. However, as highlighted in [START_REF] Anderegg | Ad hoc-VCG: A truthful and costefficient routing protocol for mobile ad hoc networks with selfish agents[END_REF], this price is always below the sum of subsidies. That problem of non budget balance is defined as the overpayment; a relative bound with respect to what is paid is provided. The balance of the mechanism is therefore always negative, which means that money has to be inserted to make the scheme work.

The model in [START_REF] Anderegg | Ad hoc-VCG: A truthful and costefficient routing protocol for mobile ad hoc networks with selfish agents[END_REF] is modified by Eidenbenz et al in [START_REF] Eidenbenz | COMMIT: A sender-centric truthful and energy-efficient routing protocol for ad hoc networks[END_REF]: subsidies are still computed according to [START_REF] Vickrey | Counterspeculation, auctions, and competitive sealed tenders[END_REF], but the sender charged the total declared cost of a "second least-cost path", i.e. the least-cost path with all nodes in the cost-efficient path removed 3 , if that charge is below his declared willingness-topay. The authors argue that such charges are closer to the sum of subsidies than VCG charges, and that the receiver should compensate the difference to reach budget balance (from which the scheme is closer). The scheme is also shown to be incentive compatible. Nevertheless, that mechanism is not efficient anymore, since situations may occur where a request is rejected whereas it would maximize social welfare (this is the case when the sender's valuation is between the total costs of the first and the second least-cost paths). Therefore, introducing budget balance results here in a loss of efficiency.

In the next subsection, we review general results about auctions that give some hints about the properties we can expect from a properly designed mechanism.

C. General results on auctions

Green and Laffont [START_REF] Green | Characterization of satisfactory mechanisms for the revelation of preferences for public goods[END_REF] establish that when players have quasi-linear utility functions, every allocation and pricing mechanism that is simultaneously efficient and incentive compatible is a Groves mechanism, VCG auctions being a particular case of them.

More recently, Krishna and Perry [START_REF] Krishna | Efficient mechanism design[END_REF] prove that among the mechanisms that are efficient, Bayesian incentive compatible 4 , and Bayesian individually rational, VCG prices maximize the expected price paid by each agent (that can be negative). Since incentive compatibility (resp. individual rationality) respectively imply Bayesian incentive compatibility (resp. individual rationality), VCG auctions minimize the overpayment (always existing without capacity constraints; otherwise, it may amount to maximizing the benefits, if any) among the schemes that verify the three properties: incentive compatibility, individual raionality and efficiency. The fact that the introduction of capacity constraints may result in no overpayment stems from the appearance of congestion charges for the sender that can overtake the overpayment.

Therefore, for a network without resource constraints as studied in subsection III-B, the negative balance of VCG auctions imply that the four properties • incentive compatibility, • efficiency, • individual rationality, • budget balance, cannot hold simultaneously. 3 For that price to be defined, the authors assume that every pair (s, t) of nodes is 2-connected, meaning that there exist two node-disjoint paths connecting (s, t). 4 In [START_REF] Krishna | Efficient mechanism design[END_REF], Krishna and Perry take a Bayesian approach: they consider that valuation functions are distributed according to a given probability distribution, and that each player, knowing his own valuation, derives a conditional distribution on the valuation of the others. Bayesian incentive compatibility means here that playing truthfully ensures each player to maximize his expected utility conditionally on his valuation. Moreover, the scheme is Bayesian individually rational if that conditional expected utility is non-negative.

IV. DISCUSSION: WHICH COMBINATION OF PROPERTIES TO PREFER?

This paper focused on the applicability of VCG auctions in inter-domain and ad hoc networks. We have exhibited prohibitive disadvantages of that scheme, related to the computational complexity involved and/or the financial cost of the mechanism.

Consequently, a pricing scheme adapted to that context must relax at least one of the four properties given in subsection III-C. It seems to us that budget balance cannot be relaxed, since such a mechanism would not be economically viable. Second, we think that individual rationality is also compulsory: users may be unwilling to risk having a negative utility and would perceive the scheme badly. Moreover, the revelation principle [START_REF] Myerson | Optimal auction design[END_REF] states that the outcome of any auction game is reachable by an incentive compatible mechanism, which implies that incentive compatibility is always reachable.

The only property that remains to be relaxed is efficiency (notice that this property is relaxed in [START_REF] Eidenbenz | COMMIT: A sender-centric truthful and energy-efficient routing protocol for ad hoc networks[END_REF], but budget balance is not assured either in that work). However, it is still desirable that the allocation remain close to the social optimum, thus a direction for future work in that context could be to design a scheme with bounded inefficiency.

3 NFig. 1 .

 31 Fig. 1. Allocation problem in case of congestion

The maximization is over the set of feasible outcomes, that may be limited by resource constraints.

Or the termination for some applications like file downloading. Since those considerations do not change the reasoning, we assume in the following that the traffic sender is charged.

ACKNOWLEDGEMENT

The authors acknowledge the partial support of EuroNGI NoE through the AUCTIONS project, and the anonymous referees for pointing out the work of Moulin and Shenker [1].


Sarah A El-Sayed

Luis A Camuñas-Mesa

Bernabé Linares-Barranco

Haralampos-G Stratigopoulos

Self-Testing Analog Spiking Neuron Circuit

Hardware-implemented neural networks are foreseen to play an increasing role in numerous applications. In this paper, we address the problem of post-manufacturing test and self-test of hardware-implemented neural networks. In particular, we propose a self-testable version of a spiking neuron circuit. The self-test wrapper is a compact circuit composed of a low-precision ramp generator and a small digital block. The self-test principle is demonstrated on a spiking neuron circuit design in 0.35µm CMOS technology.

I. INTRODUCTION

Artificial intelligence (AI) and deep learning [START_REF] Goodfellow | Deep Learning[END_REF] algorithms are increasingly dominating the computer industry, with applications ranging from speech and object recognition all the way to robotics, Internet-of-Things (IoTs), autonomous vehicles, smart healthcare, etc.

To this day, the actual processing typically runs on giant servers in the cloud using general-purpose central processing unit (CPU) clusters. This hardware is too large to fit inside a portable device and it needs far more power than a device battery can provide. Compared to the human brain that has a neuron density of around 10,000/mm 2 and consumes approximately 10 -11 Joules per spike [START_REF] Poon | Neuromorphic silicon neurons and largescale neural networks: challenges and opportunities[END_REF] -which means it runs on 20 Watts-, CPUs are estimated to be about 10 8 less efficient in terms of size and energy consumption. In addition, several AI applications require a real-time response, in which case performing inference or on-line learning with a neural network running in software on a CPU is not an option. Similar limitations are observed when graphic processing units (GPUs) and field-programmable gate arrays (FPGAs) are used instead. All of these restrictions, along with other more technical challenges, such as the von Neumann bottleneck and the approaching end of Moore's law [START_REF] Theis | The end of moore's law: A new beginning for information technology[END_REF], have made it crucial to find alternative architectures.

The answer comes with neuromorphic computing, a term introduced by Carver Mead in the late 1980s [START_REF] Mead | Neuromorphic electronic systems[END_REF] referring to special purpose very large-scale integration (VLSI) artificial neural network (ANN) implementations that resemble -or are inspired from-biology. The work that followed has led to the advent of VLSI implementations of neural networks that can work as customized hardware accelerators or can offer a much smaller form factor and better energy efficiency, such that they can be used in resource-constrained IoT nodes for near-sensor computation and near-sensor intelligence.

Today, there exist many hardware neural network architectures [START_REF] Serrano-Gotarredona | CAVIAR: A 45k neuron, 5m synapse, 12g connects/s AER hardware sensory-processing-learning-actuating system for high-speed visual object recognition and tracking[END_REF]- [START_REF] Schuman | A survey of neuromorphic computing and neural networks in hardware[END_REF] that can be digital, mixed analog-digital, or purely analog. Analog implementations are more efficient in terms of power consumption and form factor [START_REF] Valle | Analog VLSI implementation of artificial neural networks with supervised on-chip learning[END_REF]. However, they are less robust than digital implementations since digitally stored synaptic weights and digital arithmetic operations carried out by neurons are not affected by process variations. On the other hand, there are emerging architectures that use nonvolatile memory devices for implementing efficiently the synapses [START_REF] Yu | Neuro-inspired computing with emerging nonvolatile memorys[END_REF].

With the foreseen industrialization and high-volume production of hardware neural networks in the coming years, testing strategies specific to hardware neural networks is an emerging topic that is largely unexplored [START_REF] Anghel | Neuromorphic computing -from robust hardware architectures to testing strategies[END_REF].

Post-manufacturing testing aims at detecting manufacturing errors and is done per manufactured chip. For a high-volume production, testing is performed on automated test equipment (ATE) and needs to be completed in a few seconds. For safety-and mission-critical applications, testing also needs to be performed in the field concurrently with the operation or in idle times, in order to detect latent defects, aging, etc. For this purpose, built-in self-test (BIST) capabilities need to be added into the design that allow stand-alone evaluation of the health status of the chip without relying on external test instruments. BIST is a critical block for putting in place a selfhealing and self-repair methodology towards fault-tolerance and dependable design, where the chip is capable of detecting and correcting errors in its operation on its own.

Testing strategies vary depending on the type of the integrated circuit (IC), i.e. digital or analog. Techniques for postmanufacturing testing and BIST for digital ICs are considered quite mature nowadays [START_REF] Bushnell | Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits[END_REF], [START_REF] Mitra | Which concurrent error detection scheme to choose ?[END_REF]. For analog ICs, postmanufacturing testing still relies mostly on measuring sequentially the performances that are promised in the data sheet and comparing them to their specifications [START_REF] Roberts | An Introduction to Mixed-Signal IC Test and Measurement[END_REF]. BIST solutions are specific to the IC class (i.e. ADC, DAC, PLL, filter, op-amp, RF, etc.) and specific to different architectures within each IC class (i.e. SAR, pipeline, Σ∆, etc., architectures for the ADC class). BIST for analog ICs is not very widespread because of the many practical challenges. For example, analog signal paths are sensitive and BIST circuitry tapping into them loads the IC and degrades the performance.

Most likely, post-manufacturing testing for digital neural network implementations will not be any different than testing of regular digital ICs. Developing BIST solutions, however, can benefit from the modularity observed in neural network architectures. On the other hand, for purely analog neural network implementations or implementations with analog subblocks, i.e. analog neurons, new post-manufacturing and BIST test strategies will need to be developed since, in the first place, it is not clear what specifications we should test for.

While the "inverse" problem of applying machine learning for solving test-related tasks is extensively studied [START_REF] Stratigopoulos | Machine learning applications in IC testing[END_REF], a few papers have been published recently on testing of hardware neural networks. In [START_REF] Maliuk | Analog neural network design for RF built-in selftest[END_REF], a neuromorphic BIST architecture was proposed for analog ICs that has as its central block an on-chip neural network that can classify simple measurements directly to 1-bit pass or fail test decisions. However, the test of the neuromorphic BIST wrapper was not studied. In 978-1-7281-1201-5/19/$31.00 c 2019 IEEE [START_REF] Pandey | Error resilient neuromorphic networks using checker neurons[END_REF], it is proposed to use a checker neuron for real-time resilience against soft errors in feed-forward neural network architectures. The checker neuron estimates the output of a layer, compares it against the output of the actual neuron layer, and when the difference is outside a specified limit, it triggers an error signal. In this case, the error can be corrected by bypassing the whole layer and subsequently retraining. In [START_REF] Zhang | Analyzing and mitigating the impact of permanent faults on a systolic array based neural network accelerator[END_REF], a fault-tolerant design of Google's Tensor Processing Unit (TPU) hardware accelerator is proposed. The TPU is composed of a grid of Multiply-And-Accumulate (MAC) units. If a MAC unit is detected to be faulty, then it is pruned, i.e. bypassed, using multiplexers that are added into the design. Fault-tolerance design of Resistive Random Access Memory (RRAM)-based neuromorphic architectures is discussed in [START_REF] Liu | Design of fault-tolerant neuromorphic computing systems[END_REF]. A fault-tolerant design of a spiking neural network used for controlling the motion of a robotic car and implemented in an FPGA is proposed in [START_REF] Johnson | Homeostatic fault tolerance in spiking neural networks: A dynamic hardware perspective[END_REF]. The faulttolerance is based on employing redundancy, i.e. additional synapses, and is application-specific.

In this paper, we focus on spiking neural networks and we propose a self-test approach for an analog spiking neuron circuit. The self-test approach is based on applying a lowprecision ramp to the biases of the neuron and using a digital block at the output to register the output firing patterns and match them to all expected firing patterns that the neuron is capable of producing. If one or more firing patterns are missing, then the neuron is declared faulty. A single compact BIST wrapper can be used to sequentially test all neurons.

The rest of the paper is structured as follows. In Section II, we provide a brief description of the neuron employed in our study and the principle of its operation. In Section III, we describe the BIST architecture. In Section IV, we provide test coverage results based on the proposed BIST architecture. Finally, Section V concludes the paper.

II. ANALOG SPIKING NEURON CIRCUIT

According to their computational paradigm, ANNs can be classified into three generations [START_REF] Maass | Networks of spiking neurons: The third generation of neural network models[END_REF]. The first generation is based on the McCulloch-Pitts neurons and designed to give digital outputs, while the second generation is based on neurons that implement an "activation function", such as the sigmoid function. Structure-wise, these two generation models are very different from biological neural networks and they cannot match their efficiency. The third generation of neural networks employs spiking neurons that can code information in a spacio-temporal manner, making them more biologically realistic compared to the previous two models.

The spiking neuron is the basic building block of neuromorphic systems. Spiking neurons communicate -much like their biological counterparts-through discrete electrical pulses called spikes or action potentials. This means that instead of constantly firing, as in the case of first and second generation neurons, a spiking neuron accumulates inputs from preceding neurons, and if a certain number of spikes occur within a specific time frame, it generates a spike of its own. This eventdriven operation is the basis of the huge power savings offered by neuromorphic computing. There are numerous models of spiking neurons used in neuromorphic systems [START_REF] Indiveri | Neuromorphic silicon neuron circuits[END_REF], and most of them perform this accumulation and firing function, albeit with different mechanisms. Of these models, the integrate-and-fire (I&F) neuron is perhaps the simplest model that is still complex enough to be considered biologically inspired [START_REF] Schuman | A survey of neuromorphic computing and neural networks in hardware[END_REF].

As known from neurobiology, neurons in the brain respond to post-synaptic stimuli in one of four basic patterns [START_REF] Connors | Intrinsic firing patterns of diverse neocortical neurons[END_REF]. The first pattern, called Regular Spiking (RS), is when the neuron fires repeatedly with a gradually decreasing frequency, i.e. it adapts, until it settles to a stable frequency. The second, called Fast Spiking (FS), is when the neuron fires at a high frequency with little or no adaptation. The third, called Intrinsic Bursting (IB), is when the neuron starts with a cluster of spikes followed by repetitive smaller clusters or single spikes. And the fourth pattern, called Chattering (CH), is when the neuron response is in the form of long clusters of spikes occurring at regular intervals.

The transistor-level design of the neuron chosen for this work is shown in Fig. 1. It is a compact CMOS implementation of an I&F neuron [START_REF] Wijekoon | Compact silicon neuron circuit with spiking and burtsing behaviour[END_REF] based on the mathematical model proposed in [START_REF] Izhikevich | Simple model of spiking neurons[END_REF]. While most I&F models are incapable of generating both spiking and bursting behaviors in a single circuit, this neuron uses only 14 transistors and 2 capacitors to produce all four basic firing patterns of a real neuron by varying two control voltages, namely V c and V d .

Fig. 2 explains the most important aspects of the circuit's operation. The spiking behavior of the circuit is represented by two variables, V and U , which are the voltages accumulated on capacitors C V and C U , respectively. Capacitor C V integrates the post-synaptic input current in addition to a positive feedback current I V . When V reaches the threshold value, the comparator generates two short-duration pulses, namely V A and V B , and the circuit spikes. Pulse V A activates transistor M 5 , discharging capacitor C V and hyperpolarizing V to a predetermined value V c . Pulse V B turns on transistor M 8 , which has a narrow channel, so that only a small amount of charge from V d passes to capacitor C U . The two capacitors are sized so that C U charges more slowly than C V . With every spike, voltage on C U increases a little, thus increasing the leakage current through M 4 and the current through M 6 , which is diode-connected to act like a non-linear resistor that discharges C U . Leakage slows down the charging of C V , allowing the refractory period between spikes. By varying control voltages V c and V d , the relative speeds of V and U can be controlled and the four basic firing patterns can be obtained.

The neuron circuit is designed in the ams 0.35um HV CMOS H35B4D3 technology. Fig. 3 shows the four nominal combinations of control voltages V c and V d that produce the four distinct firing patterns. Fig. 3 also shows approximate areas in the V c -V d space that produce each firing pattern.

III. BIST ARCHITECTURE

The proposed BIST architecture for the spiking analog neuron is illustrated in Fig. 4. The BIST wrapper includes a ramp generator block that applies ramps at the two control voltages of the neuron aiming to excite the neuron across its different operation modes and produce the four firing patterns. In particular, V d is ramped from 1.9V to 2.8V, and during this duration V c is ramped once from 0.1 to full scale and then ramped again from 0.1 to half the full scale, as shown with the saw-tooth stimulus in Fig. 4. The rationale behind this ramping strategy can be made clear by looking in the approximated areas in Fig. 3. During the first full V c ramp, the neuron should produce the RS, CH, and FS firing patterns. During the second half V c ramp, the neuron should produce the IB firing pattern. The ramps do not have any stringent requirements. Low-precision step-wise ramp generators can be used in this context.

A digital block is connected to the output of the neuron and its role is to digitize the analog output, store the digital signature, and try to identify within this digital signature the four firing patterns, i.e. to match excerpts of the digital signature to the desired firing patterns. The rationale of our approach is that a functional neuron should be able to generate all intended firing patterns. If one or more firing patterns are missing, then the neuron is declared to be faulty. In essence, the proposed BIST architecture targets verifying one of the functional specifications of the neuron, which is its ability to provide all firing patterns.

A single BIST wrapper is required to test the complete spiking neural network. In this case, the neurons can be connected sequentially to the BIST wrapper.

The proposed BIST architecture can be used for both postmanufacturing testing and self-test in the field in idle times or before on-line re-learning is attempted. Neurons identified as faulty can be neutralized by setting their input synapses to zero. In this way, having a neural network with only functional neurons will enable a faster and more robust learning.

Finally, the proposed BIST architecture tests the neurons themselves independently of the application and of the data that is processed through the neural network for training or inference. This dissociates the test procedure from the underlying training algorithm and the cognitive task that the neural network is performing. In other words, this BIST architecture is suitable for versatile use as it looks solely at the hardware.

IV. RESULTS Fig. 5 shows the simulation of the nominal neuron by applying the BIST stimuli, i.e. by ramping the two control voltages. As it can be seen, the four firing patterns appear at the output. Specifically, RS appears first between 5 and 10 µs, CH follows between 10 and 20 µs, FS comes next between 20 and 25 µs, and IB appears last between 25 and 30 µs. A few µs is enough to excite the neuron in all four operation modes, thus the test is very fast.

The BIST principle is that a faulty neuron looses its ability to produce one or more firing patterns. A neuron could be faulty due to process variations or due to defects, i.e. random spots or voids on the die surface that may occur due to errors during the manufacturing steps and that translate into shortand open-circuits or extreme variation.

Neurons with process variations are generated by performing a Monte Carlo (MC) analysis with mismatch and interdie variations using the statistical process design kit (PDK) of the technology. Specifically, we performed a MC analysis with 100 runs. Fig. 6 shows the response of the neurons in the first 5 runs. As it can be seen, the second and fifth neuron are not producing all four firing patterns, thus they are detected by the BIST. In total, the test yield by the BIST is around 70%, showing that analog neuron circuits can suffer a lot from process variations, thus requiring a thorough and comprehensive post-manufacturing test procedure.

Defective neurons are generated by assuming a classical defect modeling approach [START_REF] Sunter | Using mixed-signal defect simulation to close the loop between design and test[END_REF]. Specifically, for transistors we consider open-gate defects following the simulation method in [START_REF] Esen | Effective DC fault models and testing approach for open defects in analog circuits[END_REF], and drain-to-source shorts; considering additional shorts across other terminals and opens in other terminals are shown to be redundant in practice and only increase defect simulation time. For capacitors, we consider short-and opencircuits and ±50% variation. One defect is injected in the neuron at a time manually. The proposed BIST approach was capable of achieving 90.6% defect coverage. Only three defects are not detected, namely ±50% variation in C U and +50% variation in C V . It turns out that the neuron can be tuned to accommodate these variations.

V. CONCLUSIONS

We proposed a compact BIST architecture for an analog spiking neuron that can be shared among all neurons in the neural network. This architecture consists of a ramp generator block that controls two bias voltages to produce all four different firing patterns at the output in the fault-free case, and a digital block that checks if any of these patterns is missing, in which case it flags a fault detection. The BIST achieves a test yield of 70% in the case of process variations and over 90% defect coverage.

Fig. 1 .

 1 Fig. 1. Transistor-level design of spiking neuron circuit.

Fig. 2 .

 2 Fig. 2. High-level model of spiking neuron circuit.

Fig. 3 .

 3 Fig. 3. Approximate areas in the control voltages space Vc-V d that produce the different firing patterns. The diamond points correspond to the nominal control voltages combinations used to produce each firing pattern.

Fig. 4 .

 4 Fig. 4. BIST architecture.

Fig. 5 .

 5 Fig. 5. Neuron output response to BIST stimuli.

Fig. 6 .

 6 Fig. 6. Monte Carlo analysis showing the neuron output response to BIST stimuli for 5 runs.

ACKNOWLEDGMENTS

This work has been carried out in the framework of the Penta HADES project. Luis A. Camuñas-Mesa was funded by the VI PPIT through the Universidad de Sevilla.