README
1 METAPROGRAMMED GEMM 2 =================== 3 4 The two main goals of this library are: 5 - providing a new matrix multiplication kernel. 6 - providing the optimized codepaths for as many possible user scenarios without 7 enforcing additional input data constraints (padding, sizes, strides, layout) 8 9 To enable this code add -DGEMMLOWP_USE_META_FASTPATH to your build setup. 10 11 The new kernel 12 -------------- 13 14 The multiplication kernel - the most inner loop of the matrix multiplication, 15 which is responsible for the row/column products was rewritten. The new code 16 produces a 3x3 result patch and processes the row/column arrays in 8 element 17 packs (the kernel 'shape' is 3x3x8 compared to the previous 12x4x2). By using 18 specialized 8bit multiplication, aggregating to vector aggregators and then 19 reduction with parallel horizontal addition we devised code that achieved 20 higher arithmetical density (arithmetical operation per assembly instruction). 21 The arithmetical performance of the new kernel exceeds 18 GOps/s on a vanilla 22 Nexus 5 phone (which is practically peak for this device). 23 24 In order to feed the kernel with input data and minimize the number of 25 instructions other than the arithmetical operations a different packing 26 scheme was used. Three rows (columns) are interweaved every 8 elements so that 27 they can be read from continuous memory in one op inside the kernel. Additional 28 memory preload hint operations are inserted into the kernel to hide memory 29 latency behind arithmetical operations. 30 31 Generated code 32 -------------- 33 34 The basic kernel used in this approach is of shape 3x3x8. Obviously this 35 kernel can be easily applied to multipications where matrix sizes are: 36 M x K, K x N where M and N are multiplies of 3 and K is a multiply of 8. 37 38 We rejected two obvious solutions of: padding the matrix sizes to appropriate 39 sizes, or using the reference implementation for the leftovers. Neither did 40 we consider enforcing extra constraints on the caller. 41 42 In order to allow all matrix sizes the kernels processing all combinations of 43 1, 2 or 3 rows and 1, 2 or 3 columns are required. Similarily to allow all 44 possible depths the leftover values (up to 7 elements) needed to be handled. 45 46 Instead of writing those kernels by hand we decided to generate them with 47 some python scripts. 9 Versions of the multiplication kernel were prepared. 48 Additionally packing and unpacking code for different row/column counts and 49 depth leftovers was generated. Finally different code was generated for 50 aligned memory reads/writes and unaligned memory reads/writes. 51 52 Using those multiplication and packing/unpacking primitives 144 gemm function 53 versions were prepared. On top of them one high level gemm function that would 54 switch to one of those preoptimized versions. 55 56 This approach allowed moving all unnecessary branching and conditional execution 57 outside of the inner loops. It also allowed removing of all short loops required 58 for leftover handling. Finally aligned memory reads/writes are used everywhere 59 where the provided input data allows. 60 61 Results 62 ------- 63 64 The library shows up to 35% faster gemm execution in some cases (e.g. ImageNet 65 benchmark). 66 67 Files 68 ----- 69 70 single_thread_gemm.h 71 -- generated ARM/NEON 8bit x 8bit gemm implementation. Contains all the 72 optimized, unrolled and curried pack/unpack, and multiply procedures and 73 a single gemm function that switches between the optimized versions based 74 on the runtime parameters. 75 76 multi_thread_gemm.h 77 -- a simple parallelization scheme for the gemm function. 78 79 generators/gemm_NxMxK_neon.py 80 -- script that generates the single_thread_gemm.h header library. 81 Usage: python gemm_NxMxK_neon > single_thread_gemm.h 82
