基于MapReduce的高阶矩阵乘法分布式并行算法研究

Distributed Parallel Algorithm Based on MapReduce for High-order Matrix Multiplication

高阶矩阵的存储和处理在信息、经济、生物等学科领域都有十分重要的应用,但是由于单节点计算机CPU、内存等资源的限制,导致了对高阶矩阵的处理存在一定的困难.在研究云计算平台Hadoop及其核心组件MapReduce的基础上,研究实现了处理高阶矩阵乘法的通用并行算法(内积法),在此基础上,对内积法进行了改进,提出一种基于缓存的分布式并行算法(缓存法),通过实验仿真表明,缓存法相比内积法执行效率更高,不仅适合处理高阶稀疏矩阵,而且可以处理高阶稠密矩阵,并且在并行效果上接近理论线性加速比.

High-order matrix storage and processing plays an important role in the field of the information, economic, biological and so on, but due to the limitation of resources such as CPU and memory in the single node computer,it is difficult to deal with high-order matrix. Based on the study of cloud computing platform Hadoop and its core component MapReduce, this paper proposes two distribu- ted parallel algorithms to handle high-order matrix, the simulation show that the modified algorithm （ Cache-based algorithm ） is more effective than traditional algorithm （ Direct algorithm）, and it is suitable for processing not only high-order sparse matrix but also dense matrix. The algorithms have high speedup which is close to the linear speedup in the theory.