JP7199283B2 - accelerator device - Google Patents

Description

The present disclosure relates to an accelerator device for parallel computing of sparse matrix-vector products.

In recent years, in the fields of AI (Artificial Intelligence) and machine learning, calculations using large-scale matrices are performed in the calculation process. For example, in the computation of a fully-connected neural network, a large-scale parameter matrix is used, and the computation of the parameter matrix is processed by a processor. When a processor processes a large-scale parameter matrix, the amount of calculation increases and the processing load of the calculation increases.

Therefore, by reducing the parameters by pruning or the like, the parameter matrix is converted to a sparse matrix in which many elements are composed of zeros, thereby reducing the parameter capacity and the amount of calculation. Since a sparse matrix is a matrix in which most of the elements are composed of zeros, the processor calculates only the nonzero elements, thereby reducing the amount of calculation.

Accelerator devices have been developed to compute sparse matrices obtained by transforming such large-scale parameter matrices. Examples of accelerator devices are disclosed in Patent Document 1, Non-Patent Documents 1 and 2, and the like. These accelerator devices realize high-speed computation by performing parallel computation of sparse matrix-vector multiplication (SpMV).

U.S. Patent Application Publication No. 2018/0046900

Fowers, J. et al., ``A High Memory Bandwidth FPGA Accelerator for Sparse Matrix-Vector Multiplication'', IEEE Int. Symp. on Field-Programmable Custom Computing Machines (2014) Song Han. et al., "ESE: Efficient Speech Recognition Engine with Sparse LSTM on FPGA", International Symposium on FPGA 2017

However, in the sparse matrix vector product (SpMV), the elements of the output vector are calculated from the sum of the products of the non-zero elements of the sparse matrix and the corresponding elements of the input vector. Therefore, in an accelerator device that performs sparse matrix vector multiplication (SpMV), only the nonzero elements of the sparse matrix are calculated, so access to the elements of the input vector is discontinuous based on the structure of the nonzero elements of the sparse matrix. becomes.

In addition, in order to perform parallel calculation of a sparse matrix-vector product (SpMV) in an accelerator device, for example, the calculation of one element of an output vector is assigned to one parallel execution unit (thread) for parallel calculation. . In this case, in the accelerator device, it is necessary to provide a mechanism for parallel access to discontinuous input vector elements between threads executing in parallel.

In order to perform discontinuous access to the elements of the input vector, the accelerator device requires a configuration in which the input data is duplicated and stored in the memory for each thread. In addition, in order to access discontinuous input vector elements in parallel, the accelerator device requires a configuration in which input data is divided and stored in a large number of independent memory banks, and parallel accesses are distributed among threads. there were. In the accelerator device, by providing these configurations, there is a problem that a lot of hardware resources are required, such as redundant duplicated memory for each thread and a large number of independent memory banks. there were.

Therefore, the present disclosure is intended to solve the above-described problems, and an object thereof is to provide an accelerator device capable of reducing required hardware resources in an accelerator device for parallel calculation of a sparse matrix-vector product. and

According to an embodiment of the present disclosure, an accelerator apparatus for performing an arithmetic operation comprising computing a sparse matrix-vector product, the output comprising the sum of products of each non-zero element of a sparse matrix and each element of an input vector a parallel computing unit that executes computation processing of each element of the vector in parallel; and a storage unit that stores each of the non-zero elements of the sparse matrix, each of the input vector elements, and each of the output vector elements. , the parallel computing unit includes a data loading unit that can access each of the elements stored in the storage unit in parallel, each of the elements of the input vector accessed by the data loading unit and the nonzero Each non-zero element of the sparse matrix is processed in accordance with the order in which the operation unit that calculates the sum of products with each element and the data load unit access each element of the input vector stored in the storage unit in parallel. an insert for inserting padding into the arrangement.

In the accelerator device of the present disclosure, by inserting padding into the placement of each non-zero element of the sparse matrix according to the order in which each element of the input vector stored in the storage unit is accessed in parallel, hardware resources to be used can be reduced.

1 is a block diagram showing the configuration of an accelerator device according to Embodiment 1; FIG. 2 is a block diagram showing the configuration of an SpMV unit according to the first embodiment; FIG. 3 is a block diagram showing the configuration of a post-process unit according to the first embodiment; FIG. FIG. 2 is a diagram showing an example of a sparse matrix in which many elements are zero; 5 is a diagram showing an example of the sparse matrix shown in FIG. 4 expressed in ELLPACK format; FIG. FIG. 3 is a diagram showing an example of an ELLPACK format sparse matrix stored in an external memory; FIG. 10 is a diagram showing an example of a program for calculating a sparse matrix-vector product; FIG. 10 is a diagram showing an example of a program for calculating a sparse matrix-vector product for each row of a sparse matrix; FIG. 9 is a diagram showing an example of parallel execution of the program shown in FIG. 8 as a plurality of threads for each row of a sparse matrix; FIG. 10 is a diagram showing an example of a list of indices of a sparse matrix; FIG. 11 is a diagram showing an example of the order of accessing elements of an input vector based on the list of indices of the sparse matrix shown in FIG. 10; FIG. 11 is a diagram showing an example in which padding is leveled and inserted into the sparse matrix index list shown in FIG. 10 ; FIG. 11 is a flowchart showing a procedure for leveling and inserting padding into a list of indices of a sparse matrix; FIG. 3 is a block diagram showing a memory configuration of a data buffer according to the first embodiment; FIG. 15 is a diagram showing an example of an index for accessing the data buffer shown in FIG. 14; FIG. 2 is a block diagram showing the configuration of a load unit according to the first embodiment; FIG. FIG. 9 is a block diagram showing a memory configuration of a data buffer according to the second embodiment; FIG. 18 is a diagram showing an example of an index for accessing the data buffer shown in FIG. 17; FIG. FIG. 9 is a block diagram showing the configuration of a load unit according to the second embodiment; FIG.

Below, an accelerator device according to an embodiment of the present disclosure will be described in detail with reference to the drawings. The same reference numerals in the drawings indicate the same or corresponding parts.

(Embodiment 1)
A hardware accelerator device for high-speed calculation of large-scale sparse matrices can be implemented using, for example, an FPGA (Field Programmable Gate Array). Accelerator devices using FPGAs use hardware resources such as memories, logics, and computing units to perform parallel computation of sparse matrix-vector products (SpMV). In the following embodiments, an accelerator device using FPGA will be described, but the accelerator device is not limited to an accelerator device using FPGA as long as it is configured by hardware.

First, the configuration of an accelerator device using FPGA for parallel calculation of sparse matrix-vector product (SpMV) will be described. FIG. 1 is a block diagram showing the configuration of the accelerator device 100 according to the first embodiment. An accelerator device (FPGA accelerator) 100 shown in FIG. 1 is, for example, an accelerator device for executing computation of a fully-connected neural network. The accelerator device 100 is connected to a system bus (System Bus) 200 connected to a host processor (not shown) and an external memory (External Memory) 300 .

When the accelerator device 100 performs computation of the fully-connected neural network, input data and output data from the host processor are stored in a data buffer inside the accelerator device 100 via the system bus 200 . Weight parameters (sparse matrix) used for calculation of the fully-connected neural network are stored in the external memory 300 from the host processor via the system bus 200 and the accelerator device 100 .

The accelerator device 100 includes a memory interface/interconnect 10 , a data buffer 20 , an SpMV unit 30 and a post-process unit 40 . Memory interface/interconnect 10 is connected to system bus 200 and external memory 300, respectively. Memory interface/interconnect 10 is connected to the host processor via system bus 200 . Memory interface/interconnect 10 interconnects between data buffer 20 , SpMV unit 30 and post-processing unit 40 within accelerator device 100 .

The data buffer 20 stores input data and output data (next layer input data) from the host processor. The SpMV unit 30 performs parallel calculation of sums of products of input data strings (input vector elements) read from the data buffer 20 and weight parameter strings (sparse matrix non-zero elements) read from the external memory 300 . Post-processing unit 40 performs post-processing of SpMV unit 30 . For example, the process of adding the bias and the process of the activation function are calculated in parallel, and the output data string (element of the output vector) is stored in the data buffer 20 .

Next, the configuration of the SpMV unit 30 will be described. FIG. 2 is a block diagram showing the configuration of the SpMV unit 30 according to the first embodiment. The SpMV unit 30 includes a sparse matrix load unit 31, an index buffer 32 that stores a list of sparse matrix indices, and a value buffer ( Value Buffer) 33 , Data Load Unit 34 , FMA (Fused Multiply Add) Array (FMA Array) 35 , and Control Unit 36 .

The sparse matrix load unit 31 reads the weight parameter string (non-zero elements of the sparse matrix) from the external memory 300, and stores a list of sparse matrix indexes from the read weight parameter string (non-zero elements of the sparse matrix) in the index buffer 32. , a list of non-zero elements of the sparse matrix are stored in the value buffer 33, respectively. The index buffer 32 and value buffer 33 are configured to have a data width required for parallel computation.

The data load unit 34 refers to the index columns for parallel calculation from the sparse matrix index list stored in the index buffer 32 and reads out the input data columns (input vector elements) for parallel calculation from the data buffer 20 . The process by which the data load unit 34 accesses the data buffer 20 and reads the elements of the input vector based on the list of sparse matrix indices will be described in detail below.

The FMA array 35 is composed of a plurality of FMA units, each of which receives an input data string (input vector elements) from the data load unit 34 and a data string of non-zero elements of the sparse matrix from the value buffer 33, Parallel calculation of the fused sum of products. After FMA array 35 computes all the columns of the sparse matrix in parallel, it transfers the output data columns (elements of the output vector) to post-processing unit 40 . The control unit 36 performs sequence control for repeatedly executing calculations in each layer of the fully-connected neural network.

In the SpMV unit 30, a plurality of FMA units constituting the sparse matrix load unit 31, the data load unit 34, and the FMA array 35 are provided in correspondence with the threads in order to perform parallel calculation of the sparse matrix-vector product (SpMV). and are connected in parallel.

Next, the configuration of the post-process unit 40 will be described. FIG. 3 is a block diagram showing the configuration of the post-process unit 40 according to the first embodiment. The post-processing unit 40 includes a bias load unit 41, a bias buffer 42 that stores bias, a bias add unit 43 that performs bias addition processing, and a LUT (Look Up Table). It includes a load unit (LUT Load Unit) 44 , an activation unit (Activation) 45 that executes activation function processing, a data store unit (Data Store Unit) 46 , and a control unit (Control Unit) 47 .

The bias load unit 41 reads bias parameters from the external memory 300 and stores them in the bias buffer 42 . This bias buffer 42 is configured to have a data width required for parallel computation. The bias addition unit 43 receives the output data string (element of the output vector) of the SpMV unit 30 and the corresponding bias parameter string from the bias buffer 42, and performs parallel calculation of adding the biases.

The LUT load unit 44 presets the activation function algorithm (assumed to be a LUT configuration). Activation unit 45 performs parallel computation processing activation functions on the output data from bias summation unit 43 . The data store unit 46 receives the output data string from the activation unit 45 and stores (writes back) it in the data buffer 20 via the memory interface/interconnect 10 . The control unit 47 performs sequence control for repeatedly executing calculations in each layer of the fully-connected neural network.

In the post-processing unit 40, a bias load unit 41, a bias addition unit 43, an LUT load unit 44, an activation unit 45, and a data store unit are used for parallel calculation of bias addition processing and activation function processing. A plurality of 46 exist corresponding to the threads, and are connected in parallel.

Next, the processing of a sparse matrix in parallel calculation of a sparse matrix vector product in the accelerator device 100 will be described in detail. A sparse matrix is stored in the external memory 300 in a data format in which only non-zero elements are compressed. In this embodiment, the ELLPACK format is used as an example of a storage format for a sparse matrix. In the ELLPACK format, a sparse matrix is represented by a list of non-zero element values of the sparse matrix and a list of sparse matrix indices indicating the column positions of the non-zero elements.

A specific example of a sparse matrix expressed in the ELLPACK format will be described. FIG. 4 is a diagram showing an example of a sparse matrix in which many elements are zero. FIG. 5 is a diagram showing an example of the sparse matrix shown in FIG. 4 expressed in ELLPACK format. Among the elements shown in FIG. 5, the elements indicated by "*" indicate the elements in which padding is inserted. Note that the value of the element into which the padding is inserted is arbitrary. In the ELLPACK format, the data stores the values of non-zero elements in the sparse matrix, and the index stores the column position of the non-zero element values. In the row [3,7,0,0], non-zero elements are present in the 0th column and the 1st column. Therefore, when expressed in the ELLPACK format, data[3,7] becomes index[0,1]. Since the second row [1, 0, 5, 9] has three non-zero element values, padding is inserted in the other rows.

When the ELLPACK format sparse matrix shown in FIG. 5 is stored in the external memory 300, it is stored in column priority. FIG. 6 is a diagram showing an example of an ELLPACK format sparse matrix stored in the external memory 300 . In the data shown in FIG. 6, the values of the non-zero elements of the sparse matrix are stored in the external memory 300 in the order of the first, second, and third columns. In the index shown in FIG. 6, the column positions of the values of the non-zero elements are arranged in the order of the first column, the second column, and the third column and stored in the external memory 300 .

Next, calculation processing of a sparse matrix vector product (SpMV) for a sparse matrix expressed in ELLPACK format will be described. FIG. 7 is a diagram showing an example of a program for calculating a sparse matrix-vector product (SpMV). The program shown in FIG. 7 calculates y=Ax where A is a sparse matrix and x and y are column vectors. The size of the sparse matrix A is M rows×N columns, and the size of the sparse matrix A expressed in ELLPACK format is M rows×K (≦N) columns. Note that the value inserted by padding is a value (zero) that does not affect the calculation, and the process is skipped in the calculation of the sparse matrix-vector product (SpMV). Also, the program shown in FIG. 7 is executed by the SpMV unit 30 shown in FIG.

In the present embodiment, parallel computation of sparse matrix-vector product (SpMV) may be performed by SIMD (Single Instruction Multiple Data), which applies the same processing to a plurality of data. In this SIMD method, when performing parallel computation among a plurality of threads, an execution mechanism configured with a data width required for parallel computation can be shared. Therefore, by adopting the SIMD method for the SpMV unit 30, parallel calculation of sparse matrix-vector product (SpMV) can be realized with fewer hardware resources than a method of implementing a mechanism for each thread.

Furthermore, in the present embodiment, a loop-type program is constructed so that the program shown in FIG. 7 can be expanded for each row of a sparse matrix. FIG. 8 is a diagram showing an example of a program for calculating a sparse matrix vector product (SpMV) for each row of a sparse matrix. Parallel computation of the sparse matrix-vector product (SpMV) can be realized by executing the sparse matrix-vector product program shown in FIG. 8 in parallel as a plurality of threads for each row of the sparse matrix. FIG. 9 is a diagram showing an example of parallel execution of the program shown in FIG. 8 as a plurality of threads for each row of a sparse matrix. The SpMV unit 30 can be realized by parallelly executing the program shown in FIG. 8 in the method shown in FIG. 9 when the SIMD method is adopted, and the same program is applied to a plurality of data.

In this embodiment, the external memory 300 that stores the sparse matrix and the data buffer 20 that stores the input data (input vector) and the output data (output vector) are each of a shared memory system, and the same memory is accessed between threads. . The index buffer 32 that stores the list of indices of the sparse matrix and the value buffer 33 that stores the list of non-zero element values of the sparse matrix are also of the shared memory type.

When reading a sparse matrix from the external memory 300, the sparse matrix load unit 31 can access consecutive elements in parallel between threads. Also, when reading the output vector from the data buffer 20, the data load unit 34 can access consecutive elements in parallel between threads. However, when reading an input vector from the data buffer 20, the data load unit 34 indirectly references the sparse matrix index list stored in the index buffer 32 to access discontinuous elements in parallel between threads. .

A specific example will be shown and explained. FIG. 10 is a diagram showing an example of a sparse matrix index list. FIG. 11 is a diagram showing an example of the order of accessing the elements of the input vector based on the sparse matrix index list shown in FIG. The data load unit 34 reads [4, 6, 2, 9] in the 0th column of the index shown in FIG. 13] is read in the second iteration (Iteration 2) (FIG. 11).

However, when the SpMV unit 30 adopts the SIMD method, the execution mechanisms such as the memory access mechanism and arithmetic units are shared between threads executing in parallel. Therefore, when the data load unit 34 reads an input vector from the data buffer 20, access to the memory is configured with a data width required for parallel calculation, and consecutive data strings are accessed in parallel between threads.

When the data load unit 34 accesses discontinuous data (elements) in parallel between threads, the discontinuous data (elements) may not fit within the data width of memory access. In this case, the data load unit 34 requires a mechanism (Gather mechanism) that repeats memory access multiple times and gathers discontinuous data (elements) into a continuous data string.

Here, the elements of the sparse matrix are reduced at a constant rate by the ELLPACK format or the like. As a result, the non-zero elements of the sparse matrix are arranged at certain intervals, and the non-zero elements accessed in parallel between threads have a high probability of being within a certain range of data width. The intervals and ranges may be, for example, multiples of the mean and standard deviation of the distances between non-zero elements. In the example shown in FIG. 10, the non-zero elements of the sparse matrix are arranged at intervals of four elements, and the non-zero elements accessed in parallel between threads are within the data width of six elements.

Therefore, the data load unit 34 requires a mechanism (Gather mechanism) for gathering discontinuous data (elements) into a continuous data string. With this mechanism, the data load unit 34 can access the data buffer 20 in parallel between threads using this interval as the memory access stride width and this range as the memory access data width.

However, in the SpMV unit 30, for example, the list of sparse matrix indices is padded so that a plurality of elements of an input vector accessed in parallel between threads by the data load unit 34 can be accommodated within the data width of one memory access. can be inserted. By inserting padding into the list of sparse matrix indices in the SpMV unit 30, the gather mechanism in the data load unit 34 can be made unnecessary. Specifically, the SpMV unit 30 inserts padding so that the number of elements inserted with padding included in each column of the index of the sparse matrix is leveled. That is, the SpMV unit 30 inserts padding to the list of sparse matrix indices, for example, in the sparse matrix load unit 31 .

The sparse matrix load unit 31 reads the non-zero elements of the sparse matrix from the external memory 300, inserts padding so that the number of padding elements included in each column of the index of the sparse matrix is leveled, and restores the sparse matrix. An index list is generated and stored in the index buffer 32 . The sparse matrix load unit 31 functions as an inserter that inserts padding. An example will be described in which padding is inserted into the sparse matrix index list shown in FIG. 10 so that the number of padding elements included in each column is equalized. FIG. 12 is a diagram showing an example in which padding is leveled and inserted into the sparse matrix index list shown in FIG. In the example shown in FIG. 12, the padding is leveled and inserted so that each column of the sparse matrix index fits within the stride width of 4 elements and the data width of 8 elements for memory access.

[4, 6, 2, *] in the 0th column of the index shown in FIG. Read by iteration process (Iteration2). Therefore, the data load unit 34 performs memory access to the data width of 8 elements from 0th to 7th in the first iteration (Iteration 1), and accesses the 4th to 11th elements in the second iteration (Iteration 2). Memory access is performed for the data width of 8 elements up to the th. In other words, the data load unit 34 does not need to repeat memory access multiple times, and does not need a mechanism (Gather mechanism) for gathering discontinuous data (elements) into a continuous data string.

Next, a procedure for leveling and inserting padding into a sparse matrix index list by the sparse matrix load unit 31 will be described. FIG. 13 is a flowchart showing a procedure for leveling and inserting padding into a list of indices of a sparse matrix.

First, the sparse matrix load unit 31 repeats the following process for all columns of the sparse matrix in ELLPACK format, starting from the first column (step S1). The sparse matrix load unit 31 finds the minimum index among the elements included in the column (step S2). Next, the sparse matrix load unit 31 uses the stride width memory area as a memory block and the data width memory block as a window, and obtains the range of the window starting from the memory block containing the minimum index obtained in step S2 (step S3).

The sparse matrix load unit 31 inserts one column of padding in the corresponding row for elements outside the window range (step S4). For example, in the example shown in FIG. 11, if the data width of eight elements from the 0th to the 7th elements in the first iteration (Iteration1) is set as the window range, the 9th sparse matrix index is out of the window range. So insert padding. Inserting one column of padding into the row corresponding to the ninth index of the sparse matrix results in the first iteration (Iteration 1) shown in FIG. When the sparse matrix load unit 31 finishes processing one column, it repeats the processing for the next column (step S5).

Next, the memory configuration of the data buffer 20 will be explained. FIG. 14 is a block diagram showing the memory configuration of the data buffer 20 according to the first embodiment. The data buffer 20 shown in FIG. 14 is a configuration example of a buffer with 256 data. consists of one buffer.

The data width of one memory bank corresponds to the stride width of memory access, and the total data width of all memory banks corresponds to the data width of memory access. In the example shown in FIG. 14, the memory access stride width is 4 and the data width is 2×4.

The data load unit 34 accesses the data buffer shown in FIG. 14 using an 8-bit index. 15 is a diagram showing an example of an index for accessing the data buffer shown in FIG. 14. FIG. In the index shown in FIG. 15, a row of data is represented by 5 bits, a memory bank by 1 bit, and a column of data by 2 bits.

Next, the configuration of the load unit that accesses the data buffer shown in FIG. 14 in parallel using a plurality of indexes will be described. FIG. 16 is a block diagram showing the configuration of the load unit according to the first embodiment.

The load unit shown in FIG. 16 includes an address coreless unit (address generator) 34a that generates addresses for each of the two memory banks, and a data crossbar (data output section) 34b that selects output data from the two memory banks. contains.

Address coreless unit 34a fuses row indices for each memory bank from multiple indices of parallel access to generate an address for each memory bank. Since multiple indexes for parallel access are restricted to the same memory access range, only one address (row index) is determined for each memory bank.

The data crossbar 34b selects a memory bank with a memory bank index shown in FIG. 15 and selects output data from the memory bank with a column index for each of a plurality of indexes for parallel access.

As described above, the accelerator device 100 according to the first embodiment is an accelerator device that executes arithmetic processing including calculation of a sparse matrix-vector product. Accelerator device 100 includes an SpMV unit 30 that executes in parallel computation processing of each element of an output vector including sums of products of each nonzero element of a sparse matrix and each element of an input vector; A data buffer 20 for storing each element, each element of the input vector, and each element of the output vector. The SpMV unit 30 section has a data load unit 34, an FMA array 35, and a sparse matrix load unit 31 (insertion section). Data load unit 34 can access each of the elements stored in data buffer 20 in parallel. FMA array 35 calculates the sum of products (fused sum of products) between each element of the input vector accessed by data load unit 34 and each non-zero element of the sparse matrix. Sparse matrix load unit 31 inserts padding into the placement of each non-zero element of the sparse matrix according to the order in which data load unit 34 accesses each of the elements of the input vector stored in data buffer 20 in parallel. do.

As a result, in the accelerator device 100 according to the first embodiment, padding is applied to the placement of each non-zero element of the sparse matrix in accordance with the order in which the elements of the input vector stored in the storage unit are accessed in parallel. By inserting , there is no need for a mechanism for gathering discontinuous data (elements) into a continuous data string, and hardware resources can be reduced.

The sparse matrix load unit 31 accesses each element of the input vector in parallel in an access unit defined by a predetermined stride width and data width in the order of parallel access. The padding is inserted for placements of non-zero elements of the sparse matrix that are not filled. As a result, the SpMV unit 30 can insert padding while leveling the number of elements into which padding is inserted in each column of the index of the sparse matrix.

The data load unit 34 includes an address coreless unit 34a that generates an address to be accessed for each memory bank and a memory corresponding to the address generated by the address coreless unit 34a when accessing each element of the input vector in parallel. and a data crossbar 34b for selecting output data from the bank. As a result, the data load unit 34 can be configured to access the data buffer 20 in parallel using a plurality of indexes.

The data load unit 34 may use the stride width of the access unit as the number of columns of data held by one memory bank, and the data width of the access unit as the total number of columns of data held by all memory banks. This allows the data load unit 34 to access the data buffer 20 at memory bank granularity.

The accelerator device 100 may be configured with an FPGA. Thereby, the cost of the accelerator device 100 can be reduced.

Although the sparse matrix load unit 31 has been described as an example of an insertion unit that smoothes and inserts padding, an insertion unit other than the sparse matrix load unit 31 may be provided.

(Embodiment 2)
In the accelerator device 100 according to the first embodiment, an example will be described in which one memory bank is configured with a memory of 32 rows×4 columns (data width of 4 elements), and two memory banks configure one buffer. did. Since the data buffer 20 performs access at the granularity of the memory bank, unnecessary memory access occurs due to the structure of the non-zero elements of the sparse matrix.

When the granularity of memory access is finer, the data width of memory banks must be equal to the stride width of memory access, and the total number of memory banks must match the data width of memory access. In the accelerator device according to the second embodiment, a case where the granularity of memory access is made fine will be described. The accelerator device according to the second embodiment has the same configuration as accelerator device 100 according to the first embodiment except for the configuration of the data buffer, and detailed description thereof will not be repeated.

A memory configuration of the data buffer according to the second embodiment will be described. FIG. 17 is a block diagram showing the memory configuration of the data buffer according to the second embodiment. The data buffer shown in FIG. 17 is a configuration example of a buffer with 256 data. constitute a buffer.

The data width of one memory bank corresponds to the stride width of memory access, and the total data width of all memory banks corresponds to the data width of memory access. In the example shown in FIG. 17, the memory access stride width is 2 and the data width is 4×2.

The data load unit 34 accesses the data buffer shown in FIG. 17 using an 8-bit index. 18 is a diagram showing an example of an index for accessing the data buffer shown in FIG. 17. FIG. In the index shown in FIG. 18, a row of data is represented by 5 bits, a memory bank by 2 bits, and a column of data by 1 bit.

Next, the configuration of the load unit that accesses the data buffer shown in FIG. 17 in parallel using a plurality of indexes will be described. FIG. 19 is a block diagram showing the configuration of a load unit according to the second embodiment.

The load unit shown in FIG. 19 includes an address coreless unit (address generator) 34c that generates addresses for each of the four memory banks, and a data crossbar (data output section) 34d that selects output data from the four memory banks. contains.

Address coreless unit 34c fuses row indices for each memory bank from multiple indices of parallel access to generate an address for each memory bank. Since multiple indexes for parallel access are restricted to the same memory access range, only one address (row index) is determined for each memory bank.

The data crossbar 34d selects a memory bank with a memory bank index shown in FIG. 18 and selects output data from the memory bank with a column index for each of a plurality of indexes for parallel access.

As shown in FIG. 17, finer memory access granularity increases the number of memory banks and complicates the hardware configuration. On the other hand, increasing the parallel number of threads reduces unnecessary memory accesses by uniforming memory accesses, but increases the memory bandwidth required for parallel computation. From these, the granularity of memory access (the number of memory banks) is determined by the trade-off between the non-zero element structure of the sparse matrix and the parallel number of threads.

As described above, in the accelerator device according to the second embodiment, the data load unit 34 can change the number of memory banks. Thus, in the accelerator device according to the second embodiment, the number of memory banks can be determined in consideration of the balance between the non-zero element structure of the sparse matrix and the parallel number of threads.

In Embodiments 1 and 2 above, when the number of processable threads is less than the number of rows of the sparse matrix (the number of processable threads < the number of rows of the sparse matrix), the rows of the sparse matrix are divided by the number of threads. Then, the above-described processing is repeatedly executed.

It should be considered that the embodiments disclosed this time are illustrative in all respects and not restrictive. The scope of the present invention is indicated by the scope of the claims rather than the above-described embodiments, and is intended to include all modifications within the scope and meaning of equivalents to the scope of the claims.

10 memory interface/interconnect, 20 data buffer, 30 SpMV unit, 31 row sparse column load unit, 32 index buffer, 33 value buffer, 34 data load unit, 34a, 34c address coreless unit, 34b, 34d data crossbar, 35 FMA array , 36, 47 control unit, 40 post-process unit, 41 bias load unit, 42 bias buffer, 43 bias addition unit, 44 load unit, 45 activation unit, 46 data store unit, 100 accelerator device, 200 system bus, 300 external memory.

Claims (6)

An accelerator device for performing arithmetic operations including computation of a sparse matrix-vector product,
a parallel computing unit that executes in parallel computation processing of each of the elements of the output vector including the sum of products of each of the non-zero elements of the sparse matrix and each of the elements of the input vector;
a storage unit that stores each non-zero element of the sparse matrix, each element of the input vector, and each element of the output vector;
The parallel computing unit
a data loading unit capable of accessing each of the elements stored in the storage unit in parallel;
an operation unit that calculates the sum of products of each element of the input vector accessed by the data loading unit and each non-zero element of the sparse matrix;
an inserting unit that inserts padding into the placement of each of the non-zero elements of the sparse matrix according to the order in which the data loading unit accesses each of the elements of the input vector stored in the storage unit in parallel; Accelerator device. The insertion section is
When accessing each element of the input vector in parallel in an access unit defined by a predetermined stride width and data width in the order of accessing each element in parallel,
2. The accelerator apparatus according to claim 1, wherein said padding is inserted into an arrangement of non-zero elements of said sparse matrix not included in said access unit. The data loading unit
an address generator for generating an address to be accessed for each memory bank when accessing each of the elements of the input vector in parallel;
3. The accelerator device according to claim 2, further comprising a data output section for selecting output data from said memory bank corresponding to the address generated by said address generation section. The data loading unit
The stride width of the access unit is the number of columns of data held by one memory bank,
4. The accelerator device according to claim 3, wherein said data width of said access unit is the total number of columns of data held by all said memory banks. The data loading unit
5. The accelerator device of claim 4, wherein the number of memory banks can be changed. 6. The accelerator device according to any one of claims 1 to 5, wherein said accelerator device is composed of an FPGA.

Images