Swagata Mandal

Yaswanth Tavva

Debjyoti Bhattacharjee

Anupam Chattopadhyay

ReRAM based In-Memory Computation of Single Bit Error Correcting BCH Code

Keywords: Error Correcting Code, BCH code, In memory Computing, ReRAM

Error resilient high speed robust data communication is the primary need in the age of big data and Internet-of-things (IoT), where multiple connected devices exchange huge amount of information. Different multi-bit error detecting and correcting codes are used for error mitigation in the high speed data communication though it introduces delay and their decoding structures are quite complex. Here we have discussed the implementation of single bit error correcting Bose, Chaudhuri, Hocquenghem (BCH) code with simple decoding structure on a state-of-the art ReRAM based in-memory computing platform. ReRAM devices offer low leakage power, high endurance and non-volatile storage capabilities, coupled with stateful logic operations. The proposed lightweight library presents the mapping for generation of elements on Galois field (GF ) for computation of BCH code, along with encoding and decoding operations on input data stream using BCH code. We have verified the results for BCH code with different dimensions using SPICE simulation. For (15,11) BCH code, the number of clock cycles required for element generation, decoding and encoding of BCH code are 103, 230 and 251 respectively, which demonstrates the efficacy of the mapping.

Introduction

In the age of big data and IoT, error resilient data storage, analysis and transmission are very crucial in different fields like social media, health care, deep space exploration and underwater surveillance etc. Even though the chances of data corruption in the silicon based semiconductor memory has grown with the shrinking of technology node, semiconductor based storage devices like random access memory (RAM), read only memory (ROM) and flash memory popularly used in the memory industry still have large footprint [START_REF] Ibe | Impact of scaling on neutron-induced soft error in srams from a 250 nm to a 22 nm design rule[END_REF]. In order to prevent data corruption in the semiconductor memories, various traditional error mitigation techniques like triple modular redundancy (TMR), concurrent error detection (CED) [START_REF] Krasniewski | Concurrent error detection in sequential circuits implemented using fpgas with embedded memory blocks[END_REF] and readback with scrubbing [START_REF] Asadi | Soft error mitigation for sram-based fpgas[END_REF] are generally used. The above mentioned methods consume large area, power and are not suitable for real time applications. Sometimes interleaving is used for error mitigation in memory but it increases the complexity of the memory and is not useful for small memory devices.

In order to alleviate the drawbacks of TMR, CED or scrubbing, various error detecting and correcting (EDAC) codes are used for error mitigation in the data memory as well as in the communication channels. In general, single bit errors in the memory are corrected by using single bit error correcting code such as Hamming or Hisao code. In order to correct multiple erroneous bits, multi-bit error correcting block codes like Bose, Chaudhuri, Hocquenghem (BCH) code [START_REF] Reviriego | Efficient error detection in double error correction bch codes for memory applications[END_REF], Reed-Solomon code [START_REF] Chen | Error correction for multi-level nand flash memory using reed-solomon codes[END_REF] are used. They have greater decoding complexity and large overhead due to the presence of more number of redundant bits compared to single bit error correcting code. Data in the memory is arranged as a matrix. Hence, different product codes are used for error mitigation in the memory where two low complexity block codes are used as component codes. Product codes formed using only Hamming codes as component codes [START_REF] Park | Soft-error-resilient fpgas using built-in 2-d hamming product code[END_REF] or Hamming code and parity code as component codes [START_REF] Park | Soft-error-resilient fpgas using built-in 2-d hamming product code[END_REF], are used to correct multi-bit upset in the SRAM based semiconductor memory. Error detection capability of different complex EDAC codes can be concatenated with Hamming code to generate low complexity multi-bit error correcting code, such as RS code concatenated with Hamming code [START_REF] Neuberger | A multiple bit upset tolerant sram memory[END_REF] and BCH code concatenated with Hamming code [START_REF] Poolakkaparambil | Low complexity cross parity codes for multiple and random bit error correction[END_REF]. In addition to block code, memory based convolutional codes [START_REF] Jacobvitz | Writing cosets of a convolutional code to increase the lifetime of flash memory[END_REF] are also used for error mitigation in the storage devices.

Error detection and correction methods discussed so far are implemented separately that read data from memory, perform encoding and decoding operation and finally write back data into the memory. With the rise of emerging technologies, computing can be performed in the memory itself, alongside storage of data unlike traditional von Neumann computing models [START_REF] Chen | Efficient in-memory computing architecture based on crossbar arrays[END_REF]. Redox based Random Access Memory (ReRAM) is one of the non-volatile storage technology which supports such in memory computing [START_REF] Chen | Reram technology evolution for storage class memory application[END_REF]. Due to high circuit density, high retention capability and low power consumption, ReRAM technology is capable of being used as an alternative of NAND or NOR flash in the industry. Unlike CMOS or TTL based semiconductor memory technology, ReRAM uses different dielectric materials to develop its crossbar structure. ReRAM demonstrates good switching characteristics between high and low resistance state compared to other emerging memories like magnetic random access memory (MRAM), ferroelectric random access memory (FRAM) [START_REF] Yu | Emerging memory technologies: Recent trends and prospects[END_REF], etc. ReRAM based memory technology is compatible with conventional CMOS based design flow and provides inherent parallelism due to its crossbar structure. The working principle of ReRAM technology involves formation of low resistance conducting path through dielectric material by applying a high voltage across it. The conducting path arises due to multiple mechanisms like metal defect, vacancy, etc [START_REF] Zhu | An overview of materials issues in resistive random access memory[END_REF]. The conducting tunnel through insulator can be controlled by an external voltage source for performing SET or RESET operations on the device.

Several in-memory computation platforms have already been proposed using ReRAMs, such as, general purpose in memory arithmetic circuit implementations [START_REF] Siemon | A complementary resistive switchbased crossbar array adder[END_REF], neuromorphic computing platforms [START_REF] Sah | Brains are made of memristors[END_REF] and general purpose Programmable Logic-in-Memory (PLiM) [START_REF] Gaillardon | The programmable logic-in-memory (PLiM) computer[END_REF]. Apart from these general purpose applications, ReRAM based computation platforms are also used to implement different domain specific algorithms like machine learning [START_REF] Song | Pipelayer: A pipelined reram-based accelerator for deep learning[END_REF][START_REF] Wang | Replacing linear hamming codes by robust nonlinear codes results in a reliability improvement of memories[END_REF], encryption [START_REF] Bhattacharjee | SHA-3 implementation using ReRAM based in-memory computing architecture[END_REF] or compression algorithm [START_REF] Bhattacharjee | In-memory data compression using ReRAMs[END_REF].

Authors in [START_REF] Haroussi | Vhdl design and fpga implementation of a fully parallel bch siso decoder[END_REF] proposed efficient hardware implementation of BCH code. Further, hardware implementation of non-binary BCH code or RS code is also proposed by authors in [START_REF] Khan | Hardware implementation of shortened (48,38) reed solomon forward error correcting code[END_REF]. The basic building blocks of error correcting code is the finite field arithmetic. The hardware implementation of high throughput finite field multiplier circuit on field programmable gate array (FPGA) and application specific integrated circuit (ASIC) are discussed by authors in [START_REF] Xie | High-throughput finite field multipliers using redundant basis for fpga and asic implementations[END_REF]. Recently, ReRAM based in memory computation of Galois field (GF ) arithmetic is described by authors in [START_REF] Mandal | ReRAM-based In-Memory Computation of Galois Field arithmetic[END_REF]. In this work, we propose the first in-memory BCH encoding and decoding operation library. Specifically, our contributions are as follows :--This work presents the first in-memory implementation of encoding and decoding operation of BCH code using ReRAM crossbar array. -The proposed mapping harnesses the bit-level parallelism offered by ReRAM crossbar arrays and supports a wide variety of crossbar dimensions. -In order to perform matrix multiplication during encoding and decoding operations, we have proposed a new method of implementation of binary matrix multiplication using ReRAM crossbar array. We refer the method as BiBLAS-3, since it is a level-3 binary basic linear algebra subprogram. -The proposed implementation has a very low footprint in terms of devices required as well as energy, which makes it suitable for use as building blocks for different applications.

The rest of the paper is organized as follows. Section 2 presents the fundamentals of GF arithmetic, basics of encoding and decoding operations using BCH code along with a succinct introduction to ReVAMP, a state-of-the-art ReRAM based in-memory computing platform. Section 3 presents detailed implementation of element generation of GF , encoding and decoding operations for the ReVAMP plaftorm using BiBLAS-3. Experimental results are described in section 4, followed by conclusion in section 5.

Preliminaries

In this section, we present the fundamentals of encoding and decoding operation using BCH code. We introduce the preliminaries of logic operation using ReVAMP architecture. The encoding and decoding operations of the BCH code will be performed on binary GF , that we describe briefly.

Galois Field Arithmetic

A field is a set of elements on which basic mathematical operations like addition and multiplication can be performed without leaving the set. Hence, these basic operations must satisfy distributive, associative and commutative laws [START_REF] Couveignes | Computational aspects of modular forms and Galois representations[END_REF]. The order of a field is the number of elements in the field. A field with finite number of elements is known as GF . The order of the GF is always a prime number or the power of a prime number. If p be a prime number and m be a positive integer, then GF will contain p m elements and can be represented as GF (p m ). For m = 1, p = 2, the elements in GF will be {0,1} and this is known as binary field. Here, we will consider GF of 2 m elements from the binary field GF (2) where m > 1. If U be the set of the elements of the field and α be an element of GF (2 m ), then U can be represented by equation [START_REF] Ibe | Impact of scaling on neutron-induced soft error in srams from a 250 nm to a 22 nm design rule[END_REF].

U = [0, α 0 , α 1 , α 2 , α 3 , ......., α 2 m -1 ] (1)
Let f (x) be a polynomial over GF (2 m ) and it is said to be irreducible if f (x) is not divisible by any other polynomial in GF (2 m ) with degree less than m, but greater than zero [START_REF] Kyuregyan | Recurrent methods for constructing irreducible polynomials over fq of odd characteristics[END_REF]. The irreducible polynomial is a primitive polynomial, if the smallest positive integer q for which f (x) divides x q + 1, where q = 2 m -1.

For each value of m, there can be multiple primitive polynomials, but we will use the primitive polynomial with least number of terms for computation over GF . x 2 + x + 1 2 3

x 3 + x + 1 2 4

x 4 + x + 1 2 5

x 5 + x 2 + 1 2 6

x 6 + x + 1 2 7

x 7 + x 3 + 1 (b)

Power

Repr.

Polynomial

Repr.

4-Tuple

Repr. 0 0 (0, 0, 0, 0) 1 α 0 (0, 0, 0, 1) α α 1 (0, 0, 1, 0) α 2 α 2 (0, 1, 0, 0) α 3 α 3 (1, 0, 0, 0) α 4 α + 1 (0, 0, 1, 1)

α 5 α 2 + α (0, 1, 1, 0) α 6 α 3 + α 2 (1, 1, 0, 0) α 7 α 3 + α + 1 (1, 0, 1, 1) α 8 α 2 + 1 (0, 1, 0, 1) α 9 α 3 + α (1, 0, 1, 0) α 10 α 2 + α + 1 (0, 1, 1, 1) α 11 α 3 + α 2 + α (1, 1, 1, 0) α 12 α 3 + α 2 + α + 1 (1, 1, 1, 1) α 13 α 3 + α 2 + 1 (1, 1, 0, 1) α 14 α 3 + 1 (1, 0, 0, 1)
α k = α k-2 + α k-3 4 ( 15, 11) α k = α k-3 + α k-4 5 ( 31, 26) α k = α k-3 + α k-5 6
( 63, 57)

α k = α k-5 + α k-6 7
(127,120)

α k = α k-4 + α k-7
elements of GF . For the generation of elements of GF , we will start from two basic elements 0, 1 and another new element α.

In this paper, we have discussed encoding and decoding operation of single bit error correcting BCH code on GF (2 m ) where m varies from 3 to 7. As α is an element of GF (2 m ), it must satisfy the primitive polynomial corresponding to GF (2 m ). With the variation of m, not only primitive polynomial changes but also dimension of BCH code changes as shown in Table 1. If α be an element in GF (2 m ), α k (where k is an positive integer and k > 2) is also be an element of GF (2 m ) and the recursive expression that will be used to calculate α k for different values m in GF (2 m ) are shown in Table 1. Here in Figure 1b we have illustrated the power, polynomial and 4-Tuple representation of all the elements of GF (2 4 ) are shown in Fig 1b . Based on the elements of GF , the encoding and decoding operations of BCH code will be performed.

Basics of BCH encoding and decoding operation

BCH is a powerful random error correcting cyclic code which is basically general purpose multi-bit error correcting Hamming code. Given two integers m and t such that m > 3 and t < 2 m -1, then there exists a binary BCH code whose block length will be n = 2 m -1 with the number of parity check bits equal to (n -k) ≤ mt and the minimum distance will be d min ≥ (2t + 1). This will represent t error correcting BCH code. If α be a primitive element in GF (2 m ), then generator polynomial g(x) of t error correcting BCH code of length 2 m -1 will be lowest degree polynomial over GF (2) and α, α 2 ,. . .,α 2t will be its root. Hence, the equation (2) must satisfy.

g(α i ) = 0 ∀i ∈ {1, 2, . . . , t} (2)
If φ i (x) be the minimal polynomial of α i , then g(x) will be formed using the equation (3).

g(x) = LCM {φ 1 (x), φ 2 (x), . . . , φ 2t (x)} (3)
As α i and α i (where i = i 2 l , i is odd and l > 1) are conjugate to each other φ i (x) = φ i (x). Hence, g(x) will be formed using the equation (4).

g(x) = LCM {φ 1 (x), φ 3 (x), . . . , φ 2t-1 (x)} (4)
Since we will use single bit error correcting BCH code, the generator polynomial g(x) for GF (2 4 ) is given by

g(x) = φ 1 (x) = x 4 + x + 1
The degree of g(x) will be at most mt and the number of parity bits will be (n-k).

After the generation g(x), the encoding operation will involve multiplication of input data D(x) with g(x), i.e, C(x) = D(x) × g(x).

The decoding operation of BCH code will involve the following steps:

1. Syndrome computation.

2. Determine the error locater polynomial λ from the syndrome components S 1 , S 2 ,. . .,S 2t . 3. Find the error location by solving the error locater polynomial λ(x).

Let r(x) = r 0 + r 1 x + r 2 x 2 + . . . + r n-1 x n-1 be the received data and e(x) be the error pattern, then r(x) = D(x) + e(x). For t error correcting BCH code, the parity check matrix will be

H =        1 α α 2 α 3 . . . α (n-1) 1 α 3 (α 3 ) 2 (α 3 ) 3 . . . (α 3 ) (n-1) 1 α 5 (α 5 ) 2 (α 5 ) 3 . . . (α 5 ) (n-1) . . . . . . . . . . . . . . . . . . 1 α (2t-1) (α (2t-1) ) 2 (α (2t-1) ) 3 . . . (α (2t-1) ) (n-1)       
The syndrome is a 2t-tuple S = (S 1 , S 2 , . . . , S 2t ) = r × H T where H is the parity check matrix. Since we are considering single bit error correcting BCH code, t will be equal to 1 and S = S 1 = r × H T . In the next step, from the syndrome values 2t nonlinear equations are formed which will be solved using either Berlekamp-Massey or Euclid's algorithm [START_REF] Joiner | Decoding binary bch codes[END_REF] and an error locater polynomial is formed using the roots obtained by solving the 2t nonlinear equations. Finally, the roots of the error locater polynomial is solved using Chien search algorithm [START_REF] Joiner | Decoding binary bch codes[END_REF]. Single bit error correcting BCH code generate only one syndrome whose value can directly locate the position of the erroneous bit and hence, we have not discussed the detailed implementation of step 2 and step 3 of the decoding of BCH code.

In-memory computing using ReRAM

In this subsection, we describe the ReRAM-based in-memory computing platform -ReVAMP, introduced in [START_REF] Bhattacharjee | ReVAMP: ReRAM based VLIW architecture for in-memory computing[END_REF]. The architecture, presented in Figure 2 utilizes ReRAM crossbar with lightweight peripheral circuitry for in-memory computing. The ReRAM crossbar memory is used as data storage and computation memory (DCM). This is where in-memory computation using ReRAM devices takes place. A ReRAM crossbar memory consists of multiple 1-Select 1-Resistance (1S1R) ReRAM devices [START_REF] Siemon | Simulation of taox-based complementary resistive switches by a physics-based memristive model[END_REF], arranged in the form of a crossbar [START_REF] Linn | Beyond von neumannlogic operations in passive crossbar arrays alongside memory operations[END_REF]. Fig. 3: ReVAMP instruction format. A V/2 scheme is used for programming the ReRAM array. Unselected lines are kept to ground. In a readout phase, the presence of a high current (≈ 5 µA) is considered as logic '1' while presence of a low current (< 2 µA) is interpreted as logic '0'. Like conventional RAM arrays, ReRAM memories are accessed as w D -bit wide words. Each ReRAM device has two input terminals, namely the wordline wl and bitline bl. The internal resistive state Z of the ReRAM acts as a third input and stored bit. The next state of the device Z n can be expressed as Boolean majority function with three inputs, where the bitline input is inverted.

Z n = M 3 (Z, wl, bl) (5)
This forms the fundamental logic operation that can be realized using ReRAM devices. Using the intrinsic function Z n , inversion operation can be realized. Since majority and inversion operation form a functionally complete set, any Boolean function can be realized using the Z n .

The ReVAMP architecture has a three-stage pipeline with Instruction Fetch, Instruction Decode and Execution stages, as shown in Fig. 2. The instruction memory (IM) can be a regular memory or a ReRAM memory, with the program counter being used to address and fetch the stored instructions in the Instruction Fetch stage.

The architecture supports two instructions -Read and Apply, as presented in Fig. 3. Read instruction reads a specified word, wl from the DCM and stores it in the Data Memory Register (DMR). The read out word, available in the DMR, can be used as input by the following instructions. The Apply instruction is used for computation in the DCM. The address wl specifies the word in the DCM that will be computed upon. A bit flag s chooses whether the inputs will be from primary input register (PIR) or DMR. Two-bit flag ws is used to select the wordline input -11 selects '1', 10 selects '0', 00 selects wb bit within the chosen data source for use as wordline input while 01 is an invalid value for ws. The pairs (v, val) are used to specify individual bitline inputs. The bit flag v indicates if the input is NOP or a valid input. Similar to wb, the bits val specify the bit within the chosen data source for use as bitline input. . Fig. 4 shows a 2 × 3 ReRAM crossbar array, which can act as the DCM. The operation in Fig. 4 (a) can be expressed as an Apply instruction, Apply 0 00 00 00 1 00 1 01 1 10 and the PIR contents are set to bl 0 bl 1 bl 2 . The operation in Fig. 4 (b) can be expressed as Read 0. From here on, we express the in-memory compute operations in the crossbar representation.

Methodology

The ReVAMP architecture performs in-memory computing operation using ReRAM devices capable of computing three-input Boolean majority with a single input inverted. Boolean majority with inverter is a functionally complete set. Therefore, it can be used for computation of arbitrary Boolean functions. The ReVAMP allows simultaneous computation on all devices that share a common wordline. A signal is required to read out the contents of a word. A recent work demonstrated multiple mathematical operation on the elements of GF using ReVAMP architecture [START_REF] Mandal | ReRAM-based In-Memory Computation of Galois Field arithmetic[END_REF]. In this section, we present the mapping of encoding and decoding operation of BCH code using these mathematical operation on the ReVAMP architecture. It involves three steps: generation of GF elements, encoding using BCH code and decoding using BCH code. The encoding and decoding operation using BCH code basically involves matrix multiplication which we will implement using ReRAM crossbar with the help of the BiBLAS operations proposed in [START_REF] Bhattacharjee | Enabling in-memory computation of binary BLAS using ReRAM crossbar arrays[END_REF]. We use the terms wordline and rows interchangeably. Similarly, the terms bitline and columns are used interchangeably.

Generation of GF elements

Here, we will illustrate the generation of elements of GF (2 3 ) as an example. As each element in GF (2 3 ) is a three tuple, the number of the columns in the Table 2: Generation operation for elements in GF (2 3 ) using 8 × 3 DCM.

Step 1

Step 2

Step 3

Step 4. . .

Step 6

Step 7. . . '1' 0 0 0 a00 a01 a02 a00 a01 a02 a00 a01 a02 a00 a01 a02 a00 a01 a02 0 0 0 '1' 0 0 0 a10 a11 a12 a10 a11 a12 '1' a10 a11 a12 a10 a11 a12 0 0 0 0 0 0 '1' 0 0 0 a20 a21 a22 a20 a21 a22 a20 a21 a22 0 0 0 0 0 0 0 0 0 '1' 0 0 0 a00 a01 a02 '0' a00 a01 a02 0 0 0 0 0 0 0 0 0 0 0 0 a00 a01 a02 a00 a01 a02 . . . . . . . . . . . . . . . . . . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 a00 a01 a02 a10 a11 a12 a20 a21 a22 a00 a01 a02 0 0 0 a10 a11 a12

Step 9

Step 10

Step 11

Step Step 13

Step 14

Step 15. . .

Step 41

Step 42

Step 43. . . a00 a01 a02 a00 a01 a02 a00 a01 a02 a00 a01 a02 a00 a01 a02 a00 a01 a02 a10 a11 a12 a10 a11 a12 a10 a11 a12 a10 a11 a12 a10 a11 a12 a10 a11 a12 a20 a21 a22 a20 a21 a22 a20 a21 a22 a20 a21 a22 a20 a21 a22 a20 a21 a22 a30 a31 a32 a30 a31 a32 a30 a31 a32 a30 a31 a32 a30 a31 a32 a30 a31 a32 '1' 0 0 0 '1' a10 a11 a12 '1' a10 a11 a12 a40 a41 a42 a40 a41 a42 a40 a41 a42 . . . . . . . . . a50 a51 a52 '1' a50 a51 a52 a50 a51 a52 0 0 0 0 0 0 0 0 0 a40 a41 a42 a40 a41 a42 '0' a40 a41 a42 0 0 0 0 0 0 0 0 0 '1' 0 0 0 a40 a41 a42 a40 a41 a42 a10 a11 a12 0 0 0 a10 a11 a12 a40 a41 a42 0 0 0 a50 a51 a52

Step 45

Step 46

Step DCM should either three or a multiple of three. For this purpose, we need DCM having 8 wordlines and 3 bitlines. Table 2 presents the intermediate state of the DCM and the inputs used for the generation of elements of GF . In Step 1, '1' is applied on 7 th wordline and a 00 , a 01 , a 02 are applied to the bitlines. Here, (a 00 , a 01 , a 02 ) represent 1, 1 and 0 respectively (from the 3-tuple representation shown in Fig. 1b). Similarly, 0, 0 and 1 are loaded into the 7 th row which basically represents α 0 . In the next two steps, α and α 2 are loaded into the sixth and fifth row applying (a 10 , a 11 , a 12 ) and (a 20 , a 21 , a 22 ) to the bitlines respectively that represent (1,0,1) and (0,1,1). Now α 3 will be calculated by modulo-2 addition of elements in 7 th and 6 th row. Modulo-2 addition between a i,j and a (i+1),j can be broken down into two op-

Encoding and Decoding Operations

The encoding and decoding operations primarily involve binary matrix multiplications. During the encoding operation, the input data will be multiplied with the generator matrix which will give the encoded data. Similarly, during the decoding operation, the received data will be multiplied with the transpose of parity check matrix to generate the syndromes which helps to locate the error in the received data. Even though the decoding of BCH codes involve multiple steps as presented in section 2, we only require syndrome computation for achieving single-bit error correction. Suppose A and B are two matrices with dimensions 2×2 and C be the matrix obtained after multiplication of A and B. We will explain mapping of BiBLAS-3 on ReRAM crossbar using 2 × 2 matrix. The parameters involved in the BiBLAS-3 implementation are described in Table 3. We consider the following configuration for the BiBLAS-3 implementation.

-Matrices A,B are available in within the crossbar and the product matrix C is stored crossbar after computation. -First five rows(r 1 ,r 2 ,. . .,r 5 ) are reserved for storage and last four rows (reserve1,. . .,reserve4) are used for computation.

The minimum dimensions of the matrix in mapping for BiBLAS-3 should be 1 × 2. Algorithm 1 shows step by step mapping of BiBLAS-3. In step 1, the elements of product matrix C is divided into a groups of size c. In this example, C is of 2 × 2 size with a total of 4 product terms. As the column size of choosen crossbar is 3, product terms are divided into two groups with elements 1, 3, 2 in group 1 and element 4 in group2. In step 2, the terms from matrices A and B, responsible for the formation of each product term in a group, are obtained. Each product constitutes a series of XORed dot products. The first and second dot products of each element in group 1 is computed in reserve1 and reserve2 rows respectively. Before computing third dot product if there are reserve1, reserve2 they will be XORed first and followed by a clear operation on reserve2. Likewise, the following dot products are computed in reserve2 and Algorithm 1 BiBLAS-3 1: groups ← getgroups(m1, n2, c) divides m1×n2 product terms into groups, with c being maximum size of each group 2: for each groups do 3:

partialproducts ← getpartialproduts(group) 4:

for each partialproducts do 5:

if first partial product then 6:

LoadEleFromA(r1) load elements from matrix A present in partial product to row r1 7:

ANDEleFromB(r1) load elements from matrix B present in partial product and dot product with row r1 8: else 9:

LoadEleFromA(r2) 10:

ANDEleFromB(r2) 11:

XOR(r1, r2).

xor rows r1 and r2 12:

RESET(r2) reset row r2 13:

end if 14:

end for 15:

Copy(r1, x) copy r1 to an empty row x in crossbar 16:

RESET(r1) reset row r1 17: end for accumulated to reserve1 by XOR. This is repeated till all the dots products in the choosen group are completed. By the end of step 2, reserve1 contains the products are of group 1. In step 3, the products from reserve1 are copied to free memory and then reserve1 is cleared. steps 2 and 3 are iterated till all the groups are computed on the crossbar. A detailed example is shown in Table 4.

Experiment

In this section, we analyze the performance of in-memory computation of encoding and decoding operations of BCH code on GF for various order m and crossbar dimensions. The experiments were performed using Cadence Virtuoso, using device-accurate model of ReRAM devices [START_REF] Siemon | Simulation of taox-based complementary resistive switches by a physics-based memristive model[END_REF]. The dimension of single bit error correcting BCH code varies with change in the order m of GF . Figure 6 and Figure 7 show the delay in terms of number of clock cycles and area in terms of the number of ReRAM devices required to perform encoding and decoding operations, along with element generation of GF elements respectively using ReVAMP. The encoding operation involves generation of the generator matrix from parity check matrix and multiplication of the input data with the generator matrix whereas the decoding operation involves multiplication of the received data with the transpose of parity check matrix. Hence, the number of cycles required for encoding operation are more than the number of cycles required for decoding operation, that can be verified from Figure 6. Generation of generator matrix from the parity check matrix and multiplication of the input data with the generator matrix are sequential operations, so the same ReRAM Table 4: BiBLAS-3 computation with the input matrices A and B to compute the product matrix C. devices will be used for both the operations. Thus, the area required for both encoding and decoding operations are basically ReRAM devices used for matrix multiplication. Hence, the area required for encoding and decoding operations are same as shown in Figure 7. The increase in dimension of BCH code increases the order of GF , i.e, the delay as well as area requirements for computation of BCH code grow exponentially. Specifically, the number of instructions I m required for generating all the elements of GF (2 m ) can be expressed by equation [START_REF] Poolakkaparambil | Low complexity cross parity codes for multiple and random bit error correction[END_REF].

I m = m + 11(2 m -m -1) (8)
Similarly, the number of instructions required for encoding (I en ) and decoding operation (I de ) of BCH code can be calculated by equation [START_REF] Jacobvitz | Writing cosets of a convolutional code to increase the lifetime of flash memory[END_REF] and equation [START_REF] Chen | Efficient in-memory computing architecture based on crossbar arrays[END_REF] respectively, where n and k are the length of encoded data and input data respectively.

I en = 2n + (n -1)12 + (k * (n -k)) (9)
I de = 2n + (n -1)12 (10)
Addition operation involves XORing the individual bits of the input operands, which is done in parallel using the rows of ReRAM crossbar. Hence, the delay of performing XOR between any number of elements in two rows of crossbar operation remain constant, even with increase in the number of bitlines. The change in the length of encoded data n and input data k leads to change in the delay as well the number of ReRAM devices required for mapping.

The number of bit-level parallel operations on ReRAM crossbar arrays is dependent on the number of bitlines present in the crossbar. Figure 8 demonstrates the impact of number of bitlines on the mapping delay for operations in [START_REF] Sah | Brains are made of memristors[END_REF][START_REF] Chen | Reram technology evolution for storage class memory application[END_REF] BCH code. With the increase in the number of bitlines, the delay of operations reduce, which demonstrate the effectiveness of the proposed mapping in harnessing the bit-level parallelism offered by the ReRAM crossbar array. Figure 9 presents the mean energy required for element generation and encoding with decoding operation. Due to the large runtime of device-accurate simulations for all possible input combinations, we only report energy number for operations till BCH code with dimension (63,57). With the increase in dimension of BCH code, the dimensions of parity check and generator matrix also increases and hence, the total number of multiplications also increase. This drastically increases delay, area and energy consumption with the increase in dimension of BCH code. Even though the contemporary technologies such as ASIC and FPGA cannot be directly compared with ReRAM based implementation, we report a coarse comparison for the sake of completeness in Table 5. For ReRAM, we assume mature ReRAM technology with 1 ns read/write times [START_REF]Emerging research devices (ERD) report[END_REF]. The DCM column presents the size of the DCM used for in-memory computation, in terms of number of bits. Hence the size of DCM is calculated by multiplying number of wordline with the number of bitlines. The Instruction Memory (IM) column in the Table 5 presents the number of bits required for instruction storage in the IM of the ReVAMP architecture. The FPGA implementation (synthesized at 100 MHz) is on Kintex-7 evaluation board. The ASIC implementation (synthesized at ≈ 1GHz) was performed using Synopsys Design Compiler with TSMC 65nm technology library. As computing using ReRAM is inherently sequential, increase in the dimension of BCH code leads to direct increase in delay, along with corresponding increase in area (DCM size). For ASIC and FPGA, the increase in delay is relatively lesser. The main advantage of ReRAM is low area requirement in terms of number of devices required for implementation. For example, encoding and decoding operation of [START_REF] Bhattacharjee | Enabling in-memory computation of binary BLAS using ReRAM crossbar arrays[END_REF][START_REF] Kyuregyan | Recurrent methods for constructing irreducible polynomials over fq of odd characteristics[END_REF] BCH code requires ≈ 8k GE for ASIC, 510 LUT for FPGA but only 590 devices for ReVAMP.

Conclusion

In this work, efficient mapping of encoding and decoding operation of single bit error correcting BCH code was proposed on state-of-the-art ReRAM based inmemory computing platform. Further, we have devised a technique for efficient in-memory realization of BiBLAS-3 operations using ReRAM crossbar array. We have explored multiple configurations for the crossbar dimensions and demonstrated performance trade-offs while varying the dimensions of BCH code. The proposed implementation has a low energy footprint and shows good improve-

Fig. 1 :

 1 Fig. 1: (a) Primitive polynomial for various order GF. (b) Representation of elements in GF (2 4 ). The list of primitive polynomials for different values of m is shown in Figure 1a. These primitive polynomials are the basis of computation using the

Fig. 2 :

 2 Fig. 2: ReVAMP architecture. Read wl Apply wl s ws wb (v valw D -1) . . . (v val0)

Fig. 4 : 2 × 3

 423 Fig.4: A 2 × 3 ReRAM crossbar, i.e., a crossbar with two rows and three bitlines. Z ij represents the state of device at wordline i and bitline j. (a) Computation on 0 th row with '0' and {bl 0 , bl 1 , bl 2 } as the wordline and bitline inputs respectively. Valid inputs can be either {'1' (+2.4V ) or '0' (-2.4V ) }. (b) 0 th row is being read out, by setting wordline to '1' (+2.4V ) and the bitlines to 0 (0V ).

A = a 11 a 12 a 21 a 22 B = b 11 b 12 b 21 b 22 C = c 11 c 12 c 21 c 22 = a 11 b 11 ⊕

 2211 a 12 b 21 a 11 b 12 ⊕ a 12 b 22 a 21 b 11 ⊕ a 22 b 21 a 21 b 12 ⊕ a 22 b 22

Fig. 6 :

 6 Fig. 6: Delay of mapping for various operations on different dimension of single bit error correcting BCH code.

Fig. 7 :

 7 Fig.7: Area or the number of ReRAM devices required for generation of the elements of GF, encoding and decoding operation of BCH code on that GF.

Fig. 8 :

 8 Fig.8: Impact of the number of bitlines on delay for computation of[START_REF] Sah | Brains are made of memristors[END_REF][START_REF] Chen | Reram technology evolution for storage class memory application[END_REF] BCH code.

Fig. 9 :

 9 Fig. 9: Impact of BCH code dimensions on energy required for computation.

Table 1 :

 1 Variation of dimension of single bit error correcting BCH code with the order of GF.

	Order of GF (m) Dimension of BCH code	α k
	3	( 7, 4)

Table 3 :

 3 BiBLAS-3 parameters.

	Parameter Description
	m1, n1	Dimensions of Matrix A
	m2, n2	Dimensions of Matrix B
	m1, n2	Dimensions of Matrix C
	r	Number of rows in crossbar
	c	Number of columns in crossbar

Table 5 :

 5 Comparison of area and delay for BCH computation on ReVAMP, ASIC and FPGA.

	BCH	ReVAMP		ASIC	FPGA
	Op. Dimension Delay DCM	IM	Delay	Area Delay	Area
	ns	bits	bits	ns	GE	ns #LU T

START

a i,j ⊕ a (i+1),j = a i,j .a (i+1),j + (a i,j + a (i+1),j )

To compute f i,j and g i+1,j , we require two copies of a i,j . Here i represents power of α and j represents postion of a bit when α i is expressed in 3-tuple format. Hence, in Step 5 and Step 6, we have loaded a 00 , a 01 and a 02 in 4 th and 3 rd row. f 0,j and g 1,j are calculated by applying '0' in 4 th row, '1' in 3 rd row and 0 along all the bitlines in Step 7 and Step 8 respectively. In order to do OR operation between f 0,j and g 1,j , g 1,j is read from the 3 rd row in Step 9 and then in Step 10, apply g 1,j along all the bitlines and '1' in wordline of 4 th row. Finally, 4 th row will store the value α 3 . Obeying the same procedure, α 4 , α 5 and α 6 will be calculated and stored in the 3 rd , 2 nd and 1 st row of the crossbar respectively. The flowchart shown in Figure 5 describes the generation of elements for GF (2 m ) using DCM with u wordlines and m bitlines. ments in terms of area requirements compared to traditional ASIC and FPGA based design. In future, the work can be extended for in-memory implementation of multi-bit error correcting BCH code.


Francesco Barchi
email: francesco.barchi@polito.it

Gianvito Urgese
email: gianvito.urgese@polito.it

Enrico Macii
email: enrico.macii@polito.it

Andrea Acquaviva
email: andrea.acquaviva@polito.it

Mapping Spiking Neural Networks on Multi-Core Neuromorphic Platforms: Problem Formulation and Performance Analysis

Keywords: Graph Mapping, Multicore Neuromorphic Architectures, Spiking Neural Networks

In this paper, we propose a methodology for efficiently mapping concurrent applications over a globally asynchronous locally synchronous (GALS) multi-core architecture designed for simulating a Spiking Neural Network (SNN) in real-time. The problem of neuron-to-core mapping is relevant as a non-efficient allocation may impact real-time and reliability of the SNN execution. We designed a task placement pipeline capable of analysing the network of neurons and producing a placement configuration that enables a reduction of communication between computational nodes. We compared four Placement techniques by evaluating the overall post-placement synaptic elongation that represents the cumulative distance that spikes generated by neurons running on a core have to travel to reach their destination core. Results point out that mapping solutions taking into account the directionality of the SNN application provide a better placement configuration.

Introduction

Finding the best way to map tasks to processor cores in multi and many-core systems is a relevant optimisation problem, with significant impact on application reliability, performance, and energy consumption.

The solution of this particular problem in many cases can only be computed employing heuristic methodologies capable of providing approximated or suboptimal solutions.

The task placement problem is common in many fields of applications that go from the mapping of parallel applications on stream-oriented MPSoCs [START_REF] Ruggiero | A fast and accurate technique for mapping parallel applications on stream-oriented mpsoc platforms with communication awareness[END_REF] to the placement of virtual machines in cloud data centres with parallel nodes [START_REF] Mann | Multicore-aware virtual machine placement in cloud data centers[END_REF]. Programming such architectures efficiently is a challenge because numerous hardware characteristics have to be taken into account, especially the memory hierarchy. One appealing idea to improve the performance of parallel applications is to decrease their communication costs by matching the communication pattern to the underlying hardware architecture. Such a method can be performed with the design of a strategy capable of partitioning the main application in several independent tasks with computation/communication load compatible with the capability of the parallel cores available on the architecture.

A good example of a solution for this problem has been proposed in [START_REF] Ruggiero | A fast and accurate technique for mapping parallel applications on stream-oriented mpsoc platforms with communication awareness[END_REF] where they defined a placement system that split the original application in a directed acyclic task graph where each node is an independent atomic task that communicates with the other nodes in discrete time. Moreover, they considered the number and capability of available cores and the communication infrastructure of the targeted platform for reducing the placement problem on N tasks to M processors.

In the Neuromorphic domain, we explored the task placement problem in the case of a globally asynchronous locally synchronous (GALS) multicore architecture called SpiNNaker. However, the same type of analysis can be customised for Intel Loihi [START_REF] Davies | Loihi: A neuromorphic manycore processor with on-chip learning[END_REF], IBM TrueNorth [START_REF]Real-time scalable cortical computing at 46 giga-synaptic ops/watt with 100x speedup in time-to-solution and 100,000x reduction in energy-tosolution[END_REF] and SpiNNaker2 [START_REF] Liu | Memory-efficient deep learning on a spinnaker 2 prototype[END_REF], representing the future of the neuromorphic multi-core platforms, for discovery what are the best practices to be adopted for efficiently mapping running highly parallel tasks.

SpiNNaker has been designed mainly for running neuromorphic applications. Here, tasks to be executed are physical neuron models running in parallel on the platform and communicating through messages. These messages represent signals, called spikes, which biological neurons exchange through their physical (neural) connections inside the brain.

The overall purpose of this application is to execute a Spiking Neural Network (snn) in real-time. In this case, real-time means that the timings of the spikes generated by the neurons should be compliant with the one of the real human brain. Thus opening the way for the use of neuromorphic platforms to interface external physical systems and elaborates their signals (e.g. images, sounds) in the same way as the brain does. Being the neurons executed as concurrent tasks by the general purpose cores, how to efficiently mapping neurons-to-cores is an issue that must be addressed for optimising the communication between cores.

Generalising, the problem we faced concerns the mapping of a large number of light parallel tasks with intensive communication to a many-core architecture. A non-efficient communication, in the specific case of snn execution, may impact real-time capabilities as well as the reliability of the application. Indeed, spikes can be lost due to congestion problems. In general, a possible approach to face the mapping problem is to model the tasks and their communication as a graph to be mapped over the underlying hardware architecture, represented by another graph.

Sugiarto et al. [START_REF] Sugiarto | Optimized task graph mapping on a many-core neuromorphic supercomputer[END_REF] presented an approach for improving the overall performance of general-purpose applications running as a task graph on the same many-core neuromorphic supercomputer. Whereas in a recent paper, we have used the cortical microcircuit application as a test case for demonstrating that an enhanced partitioning and placement system studied for the snn topology can produce a more reliable and stable configuration for the simulation on the SpiNNaker system [START_REF] Urgese | Top-down profiling of application specific manycore neuromorphic platforms[END_REF][START_REF] Urgese | Optimizing network traffic for spiking neural network simulations on densely interconnected many-core neuromorphic platforms[END_REF].

In this document, we expand the work presented in [START_REF] Barchi | Directed graph placement for snn simulation into a multi-core gals architecture[END_REF] presenting a methodology for mapping a task graph representing the snn computation on a multi-chip many-core architecture with communication awareness. To achieve this target, we designed a task mapping framework capable of analysing the network of neurons to find a configuration with the goal of reducing the communication between computational nodes. The neuron-to-core mapping problem has been formalised as a problem of minimisation of synaptic elongation. Intuitively, this metric represents the cumulative distance that spikes generated by neurons running on a specific core have to travel to reach their destination core.

The framework starts by extracting a graph of independent processes from a neural network description. In the case of snn, the direction of a communication path is also to be represented using a directed graph. On the platform side, the interconnect structure is described as a graph where nodes represent onchip cores while edges represent physical communication links between them. In this way, we formalised a neuron-to-core mapping as a graph-matching problem solvable through the exploitation of various algorithms available in the literature. The specific formulation we devised for snn mapping takes into account the typical organisation of these type of neural networks into neuron populations, sharing similar characteristics as well as the neuron model.

The results obtained by comparing four mapping algorithms points out and quantify the relevance of the communication direction information to achieve a better mapping if compared with non-directional algorithms.

Background

In this section, we will introduce the application and the MCSoC board selected as a target for demonstrating the advantages of adopting our task-placement communication aware framework.

Target Application: Neural Network Simulation

Spiking Neural Network (snn) is a particular neural model used by neuroscientist for simulating biologically plausible brain activity. Two of the most adopted neuron models are the Leaky Integrate-and-Fire (lif) [START_REF] Abbott | Lapicque's introduction of the integrate-and-fire model neuron (1907)[END_REF] and Izhikevich (izk) [START_REF] Izhikevich | Simple model of spiking neurons[END_REF], because they can ensure a plausible picture of the biological behaviours with reduced computational costs. During snn simulations neurons and their synapses are modelled as differential equations capable of emulating the behaviours observed in biological networks [START_REF] Maass | Networks of spiking neurons: the third generation of neural network models[END_REF]. An snn can be described as a graph where each vertex is called Population containing a homogeneous group of neurons sharing the same model and parameters. Whereas, each edge (Projection) represents the rule used to generate synaptic connections between the neurons of two Populations. Using PyNN [START_REF] Davison | Pynn: a common interface for neuronal network simulators[END_REF] scientist can describe many neurons/synapses models and configurations that can be exploited on different backends such as software simulators and neuromorphic platforms.

Using this snn description system, Van Albada et al. [START_REF] Van Albada | Full-scale simulation of a cortical microcircuit on spinnaker[END_REF] designed an snn application implementing the cell-type specific cortical microcircuit (CM) model created by Potjans et al. [START_REF] Potjans | The cell-type specific cortical microcircuit: relating structure and activity in a full-scale spiking network model[END_REF]. Then they simulated this snn on a neuromorphic multi-chip many-core platform called SpiNNaker [START_REF] Furber | The spinnaker project[END_REF] using the standard application partitioning and placement system for setting up the simulation on the board.

Target Architecture: Neuromorphic MPSoCs Board

For validating our placement methodology framework we took as target a GALS Neuromorphic many-core architecture and used its native application such as an example case. We used the SpiNNaker architecture which is a many-core platform that follows an event-driven computational approach, mainly used for simulating neural networks in real-time [START_REF] Furber | The spinnaker project[END_REF]. This system mimics the features of a biological neural network through the implementation of several features:

-Native parallelism: Each biological neuron is a fundamental computational element within a massively parallel system. Likewise, SpiNNaker uses parallel computation. -Spiking communications: In biology, neurons communicate through spikes.

The SpiNNaker architecture uses source-based Address Event Representation (AER) packets to transmit the equivalent of neural signals (i.e. action potentials) [START_REF] Rast | Aerie-p: Aer intersystem exchange protocol[END_REF]. Each AER packet identifies the event source through an addressing scheme. -Event-driven behaviour: Neurons are very power efficient, and consume much less power than other modern hardware, in fact to reduce power consumption, the hardware is put into "idle" state until an interrupt event doesn't trigger an action [START_REF] Jin | Efficient modelling of spiking neural networks on a scalable chip multiprocessor[END_REF]. -Distributed memory: In biology, neurons use only local information to process incoming stimuli. The SpiNNaker architecture features a hierarchy of memories: memory local to each of the cores and an SDRAM local to each chip.

The SpiNNaker chip (Figure 1) has 18 ARM 968 cores running at 200 MHz with no floating point units1 , a full customized router for intra/inter-chip communications, and an SDRAM external to the chip and accessible through the PL340 interface [START_REF] Furber | On-chip and inter-chip networks for modeling large-scale neural systems[END_REF]. Each core of a chip can access three four memory levels: i) a 96 kB Tightly Coupled Memory (TCM) that is part of each ARM core. It is divided into ITCM containing instructions (32 kB) and DTCM containing application data (64 kB). ii) a 32 kB System RAM integrated into the chip and shared between all the cores. iii) a 32 kB System ROM shared between all processors that contains the bootstrap software. iv) a 128 MB SDRAM shared between all cores of a chip. Fig. 1: The SpiNNaker chip is a system-on-chip with 18 compute-units based on ARM processors. Each compute-unit, in addition to the processor, is equipped with two TCM (for instructions and data), a DMA controller and it interacts with other components of the SoC (System RAM, System ROM, External SDRAM) through a communication controller.

The SpiNNaker system is built with boards of 48 chips interconnected to form a toroidal shaped triangular mesh where each chip is connected to six nearby chips. Each router is in charge to dispatch packets along intra-chip and inter-chip cores, and it can manage transmission of four types of packets:

-Multi-Cast (MC) packets are used for reaching many cores across the board.

They are widely used during neural simulations for spreading neural potentials to multiple destinations (emulating synapses potential transmission). These packets are routed using a routing table of 1024 entries, stored in a ternary CAM with three values per entry: routing key, routing mask and routing rule. The routing header of a multicast packet is compared with all the table entries and then redirected following the selected rule. The length of those packets could be up to 72 bits. -Point-to-Point (PP) packets are used for reaching an exact core of the board uniquely identified by the coordinates of the belonging chip and its relative number (from 0 to 17). These packets are routed using a dedicate routing table . If the destination is within the local chip, the packet is delivered to the monitor processor. This type of packet can transport a payload of 32 bits over the available 72 bits. -Nearest Neighbour (NN) packets are used for initialising the board and for implementing a keep-alive mechanism useful for understanding if there are broken links and, in this case, calculate a different path. -Fixed Route (FR) packets are used for reaching a fixed destination (by default, the chip attached to the ethernet controller). The advantage of this type of packet is that it provides 64 bits of payload.

Configuration and management of this neuromorphic architecture need a set of software tools for translating the application source code in executables to be processed on the SpiNNaker processors. The software needed for configuring and running a simulation on the system involves the board-side C/Assembly code and the host-side Python code [START_REF] Rhodes | spynnaker: A software package for running pynn simulations on spinnaker[END_REF]. We will briefly discuss the host-side modules currently in charge to perform the snn mapping on the architecture. Further details on the configuration software stack can be found in [START_REF] Jin | Algorithm and software for simulation of spiking neural networks on the multi-chip spinnaker system[END_REF].

A mapping manager is necessary for configuring the board when the application to be executed on the SpiNNaker is a snn represented as a graph of sets of neurons interconnected in a biological-inspired network. The current implementation of the SpiNNaker mapping manager splits each snn population in a set of partial populations and performs a simple radial placement of the partial populations on the SpiNNaker processors.

The host-side software allows running simulations, loading modules and to managing connections and data transfer. It is made of five modules:

-sPyNNaker: a module that provides a wrapper of the PyNN [START_REF] Davison | Pynn: a common interface for neuronal network simulators[END_REF] neural network software simulator implementing the neural models (implemented by both Python and C/Assembly code), synapse models, populations and projections. The tool parses all the parameters from the configuration files and translates the PyNN rappresentation into executables and configuration data to be loaded into SpiNNaker. -SpiNNMachine: implements a set of classes that represents at a high level all the SpiNNaker components (e.g. Processor, SDRAM, Router ). The main class, Machine, is the representation of the whole architecture. -PACMAN: The Partition and Control Manager performs the partitioning of the snn graph splitting each Population in a set of vertices (partialpopulations) and performs the placement of the partial-populations on the SpiNNaker processors. -SpiNNMan: is a tool that implements at a lower level the communication between the computer host end the SpiNNaker board allowing to send and receive messages (SDP packets, SCP commands, EIEIO Packets) using the UDP protocol. It is widely used by the other modules for load executables and data. -DataSpecification: contains a tool that allows specifying data (synaptic matrices, data structures and configuration rules) for the application running on a processor.

This full software stack can be combined with a new protocol [START_REF] Siino | Data and commands communication protocol for neuromorphic platform configuration[END_REF] designed for simplifying configuration and execution of applications by enabling: i) A more efficient generation of data structures during the configuration phase, ii) An onthe-fly reconfiguration of specific parameters, avoiding the re-load of simulation data, and iii) The possibility of embedding alternative computational flows in the applications, allowing users to switch between predefined tasks.

Problem Formulation

The snn placement into the neuromorphic architecture can be view as an optimisation problem that involves two graphs: G N and G CPU .

A graph G = (V, E, W) is a mathematical representation for describing a set of elements V and a set of relations E ⊆ {(v i , v j ) : v i , v j ∈ V } among them. The elements are called nodes of the graph and the relations are called edges of the graph. An edge e ij ∈ E binds two nodes v i , v j ∈ V to each other. A graph can have a W : E → W function that associates an edge e ij ∈ E to a value w ij ∈ W . The value w ij = W(e ij ) is called edge weight. A graph can be categorised according to two properties: i) If the nodes on edges form unordered pairs e ij : {v i , v j } the graph is said undirected otherwise it is said directed and the nodes on edges form ordered pairs e ij : (v i , v j ). ii) If the weight set W is empty the graph is said unweighted, otherwise it is said weighed.

A Spiking Neural Network (snn) can be represented using a directed and weighted graph called neuron graph G N . In G N the nodes are the snn neurons and the edges are the snn synapses. Taking into account a synapse e ij : (v i , v j ), the neuron v i is called pre-synaptic neuron and the neuron v j is called postsynaptic neuron. The edge weight w ij (called synaptic weight) represents the synapse contribution to injected current into the post-synaptic neuron after a stimulus received by the pre-synaptic neuron.

The neuromorphic architecture can be represented using an undirected and weighed graph, called target graph G T . If the target graph is coarse-grain, all edges represent the inter-chip communication links. If the target graph is fine-grain, all edges between two processors located on the same chip have a weight of one, while all edges between two processors belonging to adjacent chips have a weight of two.

This choice is determined by the structure of the arbiter which feeds the SpiN-Naker Routers. A SpiNNaker Router has two branches for introducing packets according to their origin: the 18 internal processors and the six nearby chips. It has been demonstrated in [START_REF] Urgese | Top-down profiling of application specific manycore neuromorphic platforms[END_REF] that the arbiter does not correctly manage some traffic configurations coming from the external links. It was therefore decided to disadvantage all inter-chip communications with twice the weight of intrachip communications. The Fig. 2 shows the differences between the coarse-grain model and the fine-grain model through the distance matrices obtained from the graphs of the target nodes.

We can define the placement problem Π :

G N → G T as a minimization problem (1). minimize f (π) f : eij ∈E N d(π(v i ), π(v j )) (1a) subject to π(i) = π(j) → M(i) = M(j), i, j ∈ V N (1b) |π(i) = p| ≤ S(M(i)), i ∈ V N , p ∈ V T (1c)
Where π : V N → V T is the placement rule, M : V N → M is the neuronmodel association rule and, S : M → N is the association rule between a neuron model and the maximum number of neurons per node. The goal of the placement procedure is to minimise the overall synaptic stretching (1a) to reduce the communication along the network nodes. The synaptic stretching is the distance between the nodes where two adjacent neurons are placed. Two constraints affecting the placement problem: i) All neurons mapped into a target node must be of the same model (1b). ii) Each node can simulate only a certain number of neurons, and the quantity depends on the complexity of the neuron model (1c).

Problem Relaxation

A snn is almost never described in G N form, due the high complexity in manage all neurons and synapses, but it is normally described in terms of Populations and Projections. A Population P is a set of neurons that share the same model and the same properties. A Projection between two Population P (a) and P (b) defines the rule in charge to generate a set of synapses where the pre-synaptic neurons are in P (a) and the post-synaptic neurons are in P (b) . We will refer to the Population-Projection graph using the notation G P . We can eliminate the two constrains (1b, 1c) redefining the problem Π working with G P and splitting each population P (i) into a set of partial populations

P (i) 1 , P (i) 2 , . . . , P (i) z
. All partial populations must contains at most a number of neurons equal to the maximum number of neurons allowed to be simulated in a target node:

|P (i) j | ≤ n (i) ∀j = 1, . . . , z, with n (i) = S(M(P (i) )).
In this way we obtain the partial population graph G pp . The edges of the partial population graph are weighed and ordered. Given an edge e ij ∈ E pp between two partial population, its weight w ij is equal to the number of synapses shared between the neurons belonging to the two partial populations.

We can redefine (1) using the placement rule π : V pp → V T that map a partial population into a processor [START_REF]Real-time scalable cortical computing at 46 giga-synaptic ops/watt with 100x speedup in time-to-solution and 100,000x reduction in energy-tosolution[END_REF]. minimize

f (π) eij ∈Epp d(π(v i ), π(v j )) * w ij (2a) subject to |π(i) = p| ≤ 1, i ∈ V pp , p ∈ V T (2b)
In (2a) we modify the cost function to take into account the number of synapses shared between the target nodes. The rule in (2b) describes the single constraint of the problem: a target node can only contain one partial population.

Graph Partitioning

The partition problem of G P can be solved in different ways. In [START_REF] Urgese | Optimizing network traffic for spiking neural network simulations on densely interconnected many-core neuromorphic platforms[END_REF] it was treated as a problem of clustering. The provided solution was divided into three step:

-Graph expansion:

G P → G N -Spectral embedding: G N → L -Clustering and legalisation: L → G pp .
In the first step the neuron graph G N is created by applying the synaptic generation rules defined in G P (the populations graph). In the second step, a spectral embedding procedure is applied to the neuron graph.

The spectral embedding involves the eigendecomposition of a representative matrix of the graph. In the case of G N (a directed graph) it was used a Laplacian Matrix (3) obtained throught a transition matrix induced by a random walk [START_REF] Chung | Laplacians and the cheeger inequality for directed graphs[END_REF].

L = I - (Φ 1 2 P Φ -1 2 + Φ -1 2 P T Φ 1 2 ) 2 (3)
The results of the spectral embeddings is the rapresentation of G N in the eigenspace L, a space belonging to R |V N | . The neurons can be clustered in the eigenspace using the KMeans algorithm. After the clustering, a legalisation phase gathers in groups all neurons belonging to the same cluster and the same population. Finally, a second legalisation phase, called fusion, builds the partial populations putting together the nearby groups of neurons until reach the maximum number of neurons that a processor can simulate.

Other techniques of graph clustering are Multilevel Graph Partitioning and Markov Cluster Algorithm [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF][START_REF] Van Dongen | Graph clustering via a discrete uncoupling process[END_REF]. These techniques, like the Spectral Clustering, was born for undirected graph and their usage should be analysed using different symmetrisation techniques if applied to a directed graph.

Placement

As seen in section 3 our goal is placing G N into a set of nodes G T . In subsection 3.1 we have relaxed the constraints of the problem separating it into two subproblems: i) Clustering G N (or partitioning if consider G P as a starting point) into the partial population graph. ii) Placement of G pp into G T . We have briefly described the clustering (or partitioning problem) in the section 3.2. In this section, we independently explore the placement problem (2) by comparing different techniques: Naïve, Spectral Embedding, Scotch and Simulated Annealing.

Naïve Placement

The Naïve approach is the standard mapping procedure adopted in the SpiN-Naker toolchain for assigning populations of neurons to be simulated on the cores available in the SpiNNaker Platform. It is a computationally light method to perform the graph placement without taking into account neither the connectivity of the source graph and the connectivity of the target graph.

The target graph was ordered following a polar coordinate system (ρ, ϕ) starting from a chip of choice. The radius ρ = max(|x|, |y|, |x -y|) has been calculated using the hexagonal distance. The angle ϕ ∈ [0, 2π) is expressed in radians. The procedure starts to place a partial population into each processor and change the chip when all processors inside a chip are used. As the ρ increases, the sub-populations will be distributed along chips separated by a greater and greater distance.

Spectral Embedding

The Spectral Embedding placement was partially used in a previous work described in [START_REF] Urgese | Optimizing network traffic for spiking neural network simulations on densely interconnected many-core neuromorphic platforms[END_REF]. The procedure involves the spectral analysis of the graph and a dimension reduction procedure to obtain a planar representation of it. By doing so, the target graph can be directly superimposed on the graph of the partial populations. Contrary to previous work, in which the association of partial populations with processors was performed through a greedy heuristic, in this work the mapping was performed through an Integer Linear Programming (ILP) problem.

This procedure requires the extraction of the first five eigenvalues, and the relative eigenvectors, from the matrix L. The eigenvectors form a matrix Λ that represents the partial populations in a R 5 space. We apply a non-linear dimension reduction procedure using Sammon Mapping obtaining a space in R 2 .

The Sammon Mapping algorithm minimise the error function in (4) where d ij is the distance in the high-dimensional space (eigenspace) and d * ij is the distance in the low-dimensional space (placement space) [START_REF] Sammon | A nonlinear mapping for data structure analysis[END_REF].

E = 1 i<j d ij i<j (d ij -d * ij ) 2 d ij (4)
Each chip is represented as a point (x, y) using an axial coordinate system on an hexagonal grid (the chip mesh). We superimpose the graph G T on G pp projecting the chip mesh in the placement space [START_REF] Davies | Loihi: A neuromorphic manycore processor with on-chip learning[END_REF].

x * y * = 2A h 3 √ 3    √ 3 - √ 3 2 0 3 2    x y (5)
Where (x, y) is the chip coordinate in the hexagonal grid, and (x * , y * ) is the chip coordinate in the placement space. The side length of the hex is used as a normalising factor and calculated using the area A h = A m occupied by each chip (with m the number of chips). The normalising factor allows scaling the chip mesh making it compatible with the area A occupied by the partial populations.

In the case where the target graph is fine-grain, we need to introduce the processors in the placement space. To ensuring spatial coherence, it was decided to place them equidistant along a circumference centred on the chip coordinate. The radius is chosen in such a way that it is smaller than the distance between two processors belonging to different chips.

After projecting the points into the placement space, they are translated to centre them on the median of the points representing the partial populations. Now we can describe the placement problem using the ILP formulation [START_REF] Davison | Pynn: a common interface for neuronal network simulators[END_REF]. x i,j = 1 ∀i ∈ {1, . . . , n}

minimize f (X) f : n i=1 m j=1 x i,j d i,j (6a)
Where the matrix X = (x ij ), x ij ∈ {0, 1} is the placement matrix. An entry x ij = 1 means that a partial population i is mapped on a target node j. Two constraints affecting this ILP formulation: i) Each target node can host at most k partial populations (6b). ii) Each partial population can be associated to only one target node (6c).

The ILP problem was modelled using PuLP Python library and solved with COIN-OR branch and cut (CBC) solver.

Scotch

The Scotch mapping procedure makes use of the programs available in the homonym software suite (scotch). The Dual Recursive Bipartitioning (DRB) is the primary procedure used by this tool [START_REF] Pellegrini | Static mapping by dual recursive bipartitioning of process architecture graphs[END_REF]. The DRB can use a plethora of other bi-partitioning methods according to a strategy defined by the user or deducted by graph properties. The main available methods are: Gibbs-Poole-Stockmeyer [START_REF] Gibbs | A comparison of several bandwidth and profile reduction algorithms[END_REF], Fiduccia-Mattheyses [START_REF] Fiduccia | A linear-time heuristic for improving network partitions[END_REF], Greedy Graph Growing [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF] and Diffusion [START_REF] Pellegrini | A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries[END_REF].

The mapping workflow with scotch plans to pre-partition the target graph through the amk grf program. The amk grf program take in input a graph (grf format) and create a target file (tgt format) which contains a decompositiondefined target architecture of same topology as the input graph.

Once a decomposition of the target graph has been obtained, the graph of the partial populations is placed on the target graph using the gmap program. The program gmap take in input the partial population graph in grf format and the target graph in tgt format and perform the DRB procedure minimising the communication cost function 2 . The gmap output file is a mapping file (map format) that contains the association between the Source and the Target nodes.

We had developed a Python module able to exporting a NetworkX graph to a file according to the grf format used by scotch and capable of automating the procedures described above.

Simulated Annealing

The Simulated Annealing is a well know procedure used to find a good solution to an optimisation problem [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF]. Given the problem in (2a), it is convenient to express the overall synaptic stretching in a matrix form and define a cost function to minimise. Given the partial population graph G pp we build its Adjacency matrix A = (a ij ) as described in [START_REF] Fiduccia | A linear-time heuristic for improving network partitions[END_REF].

a ij = w ij if ∃(v i , v j ) ∈ E pp 0 otherwise ∀i, j ∈ {1, . . . , n} (7)
Given the target graph G T we build its distance matrix D = (d ij ) where each entry d ij is the lenght of the mimimum path between two target nodes cpu i and cpu j . The distance matrix can be build using the Floyd-Warshall algorithms or repeating Dijkstra's algorithms if |E T | |V T | 2 . Assuming to have as many partial populations as target nodes and a placement rule Π : {v 1 , . . . , v n } → {cpu 1 , . . . , cpu n } we construct the permutation vector π : (Π(v 1 ), . . . , Π(v n )) and the permutation matrix P π = (p ij ) in row form [START_REF] Furber | The spinnaker project[END_REF].

p ij = 1 if i = π j 0 otherwise ∀i, j ∈ {1, . . . , n} (8)
The permutation matrix is applied to D to permutate its rows and columns. We obtain the matrix D π = P π DP π . The overall synaptic stretching can be expressed in a matrix form and used as the cost function for the simulated annealing algorithm [START_REF] Furber | On-chip and inter-chip networks for modeling large-scale neural systems[END_REF].

f : e T (A D π )e = i,j a ij * d (π) ij (9)
Where is an element-wise multiplication and e is a column vector whose all elements are equal to one. In the case of a fine-grain G T , before perform the synaptic stretching evaluation, the matrix A D π should be collapsed in order to aggregate the processors belonging to the same chip. We used the Simulated Annealing implementation provided in the SciPy ecosystem using the temperature to decide how many elements of the permutation vector π are to be swapped.

Results

In this section, we present the exploration experiments using the methods described in Section 4.

We use the Cortical Microcircuit (cm) as benchmark network [START_REF] Potjans | The cell-type specific cortical microcircuit: relating structure and activity in a full-scale spiking network model[END_REF]. This network represents the connectivity of neurons inside a slice of the cerebral cortex with an area of 1 mm 2 . The cm has been chosen because it is a rapresentative biological model with a relativly high global connectivity (5%) and natural clusters defined by the four cerebral cortex layers {L 23 , L 4 , L 5 , L 6 }. The cm is described in terms of Populations and Projections with two populations for each layer, for a total of 8 Populations and 64 Projections.

The network is composed of Leaky Integrate-and-Fire (lif) and Spike Source (src) neuron models. The lif neurons are models that mimic the biological neurons behaviour. The src neurons are simple programmable applications for outputting signals when desired. In this network, the src neurons are used to simulate the background activity of cortical neurons not in the model. Each src neuron is connected to only one lif neuron, so they can be excluded by the G N provided that processors are reserved for their execution.

The cm model has 7.72e+4 lif neurons and 2.99e+8 synapses. A network cm p is a down-scaled cm to a percentage p:

cm 5% has 3.86e+3 neurons and 7.47e+5 synapses.

cm 10% has 7.72e+3 neurons and 2.99e+6 synapses.

cm 50% has 3.86e+4 neurons and 7.47e+7 synapses.

For each processor in charge of simulating a lif partial population, we must reserve two further processors. A processor is reserved for the simulation of src neurons and a further processor is reserved to host a special application necessary to manage synapses with delays greater than 10 ms, as described in [START_REF] Urgese | Top-down profiling of application specific manycore neuromorphic platforms[END_REF]. Taking into account a set of 16 processors belonging to the same chip, we can place five partial populations per chip for a total of a thousand neurons per chip. 5% 10% 15% 20% 25% 30% 35% 40% 45% 50% 0.10 For simplifying the problem we perform a sequential slicing of each population in order to obtain partial populations with at most 1 000 neurons. In this way, we can use a coarse-grain target graph where the nodes are the spinnaker chips (each chip with 5 processors and 200 lif neurons per processor).

The experiment environment is composed of four different mapping procedures: Naïve, Spectral, Scotch and Simulated Annealing. We had generated 5 cm networks for 10 different scale factors, from 5% to 50%, for a total of 50 networks. For each network, we applied all mapping procedures 20 times. We evaluate the performance of each mapping procedure for each scale factor, using the fitness function [START_REF] Furber | On-chip and inter-chip networks for modeling large-scale neural systems[END_REF]. As a result, we obtain a distribution of 100 different placement results concerning overall synaptic stretching.

The performance of mapping procedures is compared to the performance of random placement. The median value of the results obtained with the Random procedure is used to compute the percentage improvement of the results obtained with other techniques.

In Fig. 3 is depicted a chart that summarize all the experiments. On the xaxis, there are the network scale factors, on the y-axis the percentage placement improvements versus random. The data series are represented by polylines of different colours representing the medians of the results set. Each polyline is drawn within an area whose extremes delimit the first and third quartile of the results set.

In Fig. 4 are depicted the mapping results of a cm 20% into a target graph of 19 chip using the four placement techniques. Each hex represents a SpiNNaker chip connected with six neighbours. The colour of the hex area points out the belonging of the neurons, mapped on the chip, to one of the eight populations of the cm. The number of synapses shared between two partial populations is highlighted with the colour intensity of the edge that connects them. The different concentration of the connections with more synapses can be appreciated qualitatively from the figures 4a to 4f and quantitatively from the figures 4c to 4h. In Fig. 4a can be seen how the Näive method does not consider the connectivity but place each partial population sequentially following the polar ordering of the chip. Indeed there are many connections with a large number of synapses directed towards distant chips. This not happens in Fig. 4f where the Simulated Annealing can localise in a defined area all partial populations with a high number of shared synapses. In Fig. 4c and Fig. 4h the same information can be appreciated quantitatively. The chart has a bar for each partial population. Each bar represents the overall outgoing synapses of a partial population and shows the percentage of synapses at different levels of elongation. The white line depicts the number of synapses belonging to each partial population. The partial populations are sorted in descending order according to the total number of synapses.

We can see how better methods improve the percentage of synapses at a distance of one chip (Green) and decrease the percentage of synapses at a distance of four chips (Red).

While the results of the coarse-grain model were obtained by imposing a maximum of 1000 neurons per chip belonging to the same population, the re- Fig. 5: The three graphs represent the improvement of a mapping technique compared to the median of the results obtained with a random placement using three different constraints for the number of neurons in a processor.

sults obtained with the fine-grain model were evaluated using three different values that limit the neurons per processor: 100, 150, 200. The results obtained using 200 neurons per processor are shown in Fig. 5a. In the Table1, the results are shown in terms of processors involved. Where possible, a maximum of 5 processors per chip was used, because the network CM, in addition to the lif neurons considered there, makes use of other applications including a manager for synapses for high delays and a manager of external stimuli [ src]. For each processor that simulates lif neurons, two other processors are required for a total of 15 processors per chip. In any case, in this exploration some configurations required more processors than theoretically available, so we ignored this constraint where necessary. Each chip, therefore, hosts from 500 to 1000 neurons belonging to different populations. As the Fig. 5 shows, the results show a profile similar to the one obtained with the coarse-grain model. However, it is noted, mainly for problems with many processors are involved, that the use of the methodology based on SCOTCH obtains results slightly inferior to Simulated Annealing. Considering the high efficiency of the solution offered by the SCOTCH suite and the simple A + A T symmetrisation necessary to use the tool, it is possible to renounce to the 2% of improvement but obtain a fast and acceptable solution.

Conclusions

In this paper, we described a mapping problem that involves a complex directed graph to be placed in a mesh of processors. We have modelled the mapping problem of an snn into the SpiNNaker processors-mesh splitting the problem into 3 phases: population graph expansion, neuron graph clustering, and partial populations graph mapping. Focusing on the mapping phase, we have identified and tested 4 methodologies to solve the problem. The Naïve method (a simple heuristics) tries to maintain the location of the populations by placing them according to the order of creation without taking into account the real connectivity of the network. The Spectral method uses the graph eigendecomposition to obtain a planar representation of the snn graph and performs the node association with the chip mesh through an ILP formulation. The Scotch method uses the Dual Recursive Bipartitioning heuristic for fast mapping of a source graph into a target graph. The Simulated Annealing method uses the well-known SA procedure to minimise a cost function, the synaptic elogation.

We are redefining the cost function of the placement problem (the synaptic elongation) bringing it into matrix form as a function of a permutation vector. We have chosen the cortical microcircuit at different scale factors as our benchmark network, preferring it for its high connectivity and the presence of clusters. After performing several tests on the chosen benchmark network, the results highlight the superiority of the Simulated Annealing method that works natively on direct graphs. Using a fine-grain model, the gap between the SA and SCOTCH based method has narrowed, especially when dealing with large graphs. In these cases, the SCOTCH-based method has the advantage of providing an acceptable solution in a shorter time.

This modelling system for snn placement problems can be adapted to other architectures such as Intel Loihi and SpiNNaker 2 for investigating new mapping techniques to be adopted for improving the usability of these emerging architectures. In the next works, we will implement these techniques within the placement pipeline of the SpiNNaker neuromorphic architecture, to offer an alternative to the currently implemented method (Naïve) and evaluating experimentally the reduction of communications between the chips involved.

Fig. 2 :

 2 Fig.2:The distance matrix of a placement area using a coarse-grain and a finegrain target graph.

  j ≤ k ∀j ∈ {1, . . . , m} (6b) m j=1

Fig. 3 :

 3 Fig.3: The graph represents the improvement of a mapping technique compared to the median of the results obtained with a random placement using a constraint of 1000 neurons per chip. The x-axis shows the CM scale factor. The areas represent the first and third quartile of the results obtained on 100 samples.

Fig. 4 :

 4 Fig.4: The figures in the first row represent the placement of the partial population graph build from a CM 20% with 1000 neurons per chip on 19 chip (5 processors per chip). The figures in the second-row represent for each partial population the number of synapses (white line) and the percentage of synapse stretching.

Table 1 :

 1 The size of the target graph in terms of number of cores and number of chips. We have always tried to keep five processors per chip using different constraints for the number of neurons per chip. Configurations marked with (*) can not be mapped on five processors per chip.

			Neurons per Node
		200		150		100
	CM Core Chips Core /Chips Core Chips Core /Chips Core Chips Core /Chips
	5% 24	5	4.8 28	6	4.7 42	9	4.7
	10% 42	9	4.7 54	11	4.9 80	16	5.0
	15% 62	13	4.8 80	16	5.0 120	24	5.0
	20% 80	16	5.0 107	22	4.9 157	32	4.9
	25% 100	20	5.0 132	27	4.9 196	40	4.9
	30% 120	24	5.0 157	32	4.9 236	48	4.9
	35% 140	28	5.0 184	37	5.0 274	46	6.0*
	40% 157	32	4.9 209	42	5.0 312	45	6.9*
	45% 178	36	4.9 236	48	4.9 351	44	8.0*
	50% 196	40	4.9 261	44	5.9* 390	44	8.9*

The SpiNNaker simulator applies a mechanism of rescaling that allows working with only integers, even if in the equations of the neural models are in the domains of real numbers