Design And Implementation Of Writing Efficient Linear Algebra Subprograms

New non-volatile memories are playing an increasingly important role.Intel Optane series memory has been offificially put into use.The new non-volatile memory has low latency,low energy consumption,persistent storage,high storage density,and byte addressing.These characteristics allow the nonvolatile memories to be used as the main memory.However,an important feature of the new non-volatile memories is reading and writing asymmetry.Writing operation has a higher cost on time and energy comparing to the reading operation.The linear algebra,as the cornerstone of mathematics,is also widely used in computer science.Linear algebra is used in high-performance computing,graph computing,and deep learning.Open source basic linear algebra subprograms,and commercial linear algebra libraries such as Intel’s math kernel library are optimized for algorithms on symmetric memory.These libraries focus on parallel and distributed expansion and were not optimized for reducing communications,especially writing communication.The write-optimal matrix multiplication(WO-MM)algorithm is an improved algorithm based on the communication-avoiding algorithm and write-effificient algorithm.The most signifificant feature of the write-optimal matrix multiplication algorithm is that it reduces the reading and writing overheads simultaneously.Implementations of the write-optimal matrix multiplication algorithm have successively overcome the issues of hardware and software such as parallelization and vectorization.The main subprograms include matrix multiplication,triangular system solver,cholesky factorization,lower-upper factorization,and matrix inversion.In the experiment,the matrix multiplication algorithm reduces the execution time over 50%compared to the traditional algorithm.For other subprograms,time reduction is generally 25%.