• 关注官方微信 微信公众号 添加方式:
    1:搜索微信号(gogolinux
    2:扫描左侧二维码
  • 登录 注册
  • 一起学LINUX - GOGOLINUX

    查看: 1465|回复: 15
    打印 上一主题 下一主题

    利用Hadoop实现超大矩阵相乘之我见(一)

    [复制链接]

    3

    主题

    3

    帖子

    22

    积分

    新手上路

    Rank: 1

    积分
    22
    跳转到指定楼层
    楼主
    发表于 2019-3-11 14:52:26 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
    前记最近,公司一位挺优秀的总务离职,欢送宴上,她对我说“你是一位挺优秀的程序员”,刚说完,立马道歉说“对不起,我说你是程序员是不是侮辱你了?”我挺诧异,程序员现在是很低端,很被人瞧不起的工作吗?或许现在连卖盗版光盘的,修电脑的都称自己为搞IT的,普通人可能已经分不清搞IT的到底是做什么的了。其实我想说,程序员也分很多种的,有些只能写if-then-else,有些只能依葫芦画瓢,但真正的程序员我想肯定是某个领域的专家,或许他是一位数学家,或许他是一...
    前记
    最近,公司一位挺优秀的总务离职,欢送宴上,她对我说“你是一位挺优秀的程序员”,刚说完,立马道歉说“对不起,我说你是程序员是不是侮辱你了?”我挺诧异,程序员现在是很低端,很被人瞧不起的工作吗?或许现在连卖盗版光盘的,修电脑的都称自己为搞IT的,普通人可能已经分不清搞IT的到底是做什么的了。其实我想说,程序员也分很多种的,有些只能写if-then-else,有些只能依葫芦画瓢,但真正的程序员我想肯定是某个领域的专家,或许他是一位数学家,或许他是一位物理学家,再或许他是计算机某个细分领域的专家,他是理论与现实的结合,是凌驾于纯理论的存在!而笔者我正立志成为这样的能让人感到骄傲的程序员。
    切入正题吧,谈到云计算,不得不提大数据,处理大数据,肯定逃不离分布式计算。互联网行业,无论是商品推荐还是好友推荐,还是PageRank,所要处理的Items规模、用户规模都是极其庞大的,小则数以百万、千万记,大则数以亿记。在此数据基础上,诞生了很多优秀的推荐算法,推荐算法中大部分会运用到矩阵运算。如此大规模的数据,一台计算机已经没有能力处理,说简单点,一台服务器的内存可能连加载半个矩阵数据都不够,更别谈处理了。“当一头牛拉不动车时,很少有人去找一头更大更强壮的牛,而是找来更多的牛一起拉。”,这就是分布式计算,而Hadoop就是在分布式集群上处理大记录集的强大利器。
    笔者最近对推荐算法挺感兴趣的,也研究了一些!部分算法数学公式研究的透彻了,便有自己想实现的冲动,可公式里的矩阵运算可不是那么简单!所以就想从研究超大规模矩阵相乘开始,一方面为以后做大规模矩阵运算、实现推荐算法做技术储备;另一方面也想真正体验一把用Hadoop实现分布式运算的乐趣;最重要的是能够写一些包含独特思想,有研究成分,有技术含量的代码。
    摘要
    本文首先讨论了目前现有的大矩阵运算方法,并指出其不足;接着提出自己的矩阵运算方法来解决目前现有方法所存在的问题,同时通过实验来观测本文方法所存在的问题,并针对这些问题,对本文方法进行再优化。
    现有方法
    行列相乘运算
    传统的矩阵运算是A矩阵中的每一行分别与B矩阵中的每一列相乘。假设矩阵A的规模为(m*r),矩阵B的规模为(r*n),则矩阵C的规模为(m*n)。矩阵C中元素C是A中第i行与B中第j列元素依次对应相乘并汇总的结果。公式表示如下:
    每一个Ci,j的计算都是独立的,所以可以交由不同的计算节点完成。
    缺点
    1、矩阵规模有一定限制,如果A矩阵或B矩阵有一个超大,则某个运算节点就很有可能由于内存限制,加载不了A矩阵的第i行或B矩阵的第j列。
    2、对于稀疏矩阵计算没优势。若A,B中有稀疏矩阵存在,需判断A中i行与B中第j列对应的位置上是否有0元素,换句话说,还是需要加载第i行,第j列的全部内容,若某个位置没有输入,在运算过程中需要将相应位置用0填充,这样会造成上一点所存在的问题:内存放不下。
    矩阵分块运算
    当矩阵大到一定程度时,一台服务器由于内存限制已经无法处理,不过由于矩阵具体天然的可分块的特性,许多基于分块的矩阵运算算法诞生了,《数学之美》这本书上介绍的大矩阵相乘方法就是基于分块的,现简单介绍如下:
    1、当A矩阵纵向很大,横向不大时,我们将A矩阵分块,将A矩阵中的分块分别与B矩阵相乘,通过Hadoop,这些计算可以并行进行,如图1所示:
    图中A1*B=C1,A2*B=C2,…,每部分计算分别可在不同的计算节点完成,最后将结果组合在一起。
    2、当A矩阵为一个真正的超大矩阵(横向纵向都很大),与之相乘的B矩阵也必是一个超大矩阵(至少纵向很大),此时A,B矩阵都需要按行按列进行分块,并将不同的分块计算交由不同的计算节点完成,如图2所示。

    图2
    图中,矩阵A中的每一块都需要和矩阵B中对应位置的块依次相乘,这些块与块之间的相乘运算可以由不同的计算节点完成,最后将不同块与块的运算结果,经过严密精确的控制,对相关结果进行合并(主要是相加),得到最终的运算结果C。
    1、对于不同的矩阵规模,如何分块是难点,同时块的大小受限于内存大小。
    2、块与块之间的运算以及组织较繁琐。
    3、不太利于稀疏矩阵的运算(0值占用较多的存储空间,以及会做很多无效运算)
    基于最小粒度相乘的算法
    为了文档的命名结构,笔者自己根据算法原理,起了这个名字。
    “行列相乘运算”和“分块运算”都受限于计算节点的内存限制。那么有没有一种运算,跟计算节点的内存大小无关呢?答案是:肯定有!总所周知,矩阵相乘的最小粒度计算是两个矩阵中的两个数相乘,比如,且计算结果是的一个组成部分。
    假设有两个超大矩阵A和B,A的规模是(m*r),B的规模是(r*n),将矩阵相乘中的最小粒度乘法运算进行统计,我们不难发现:A中每个元素A需要与B中第k行的元素B(j=1,2,...,n)依次相乘,计算结果分别为C的一个组成部分;而B中每个元素B需要与A中第j列的元素A(i=1,2,...,m)依次相乘,计算结果分别为Ci,j的一个组成部分。具体如图3所示。
    由于A*B是独立的,因此可以由不同的计算节点进行运算,最后根据key (i,j)将运算结果进行汇总相加,得到结果Ci,j。同时,每个计算节点每次计算时都是只加载两个数进行相乘,并不需要加载矩阵的某个块或者某行某列,因此没有内存的限制问题,理论上只要hadoop的HDFS文件系统够大,就可以计算任意大规模的矩阵相乘。
    在Map-Reduce过程中,由于Map的每条输入记录只被处理一次便不再使用,因此根据图3理论,对于矩阵A中的每个元素,在实质进行乘法运算之前,我们需要生成n个副本,对于矩阵B中每个元素,我们需要生成m个副本,并将相应位置上的副本进行对应好。比如对于A需生成n个副本,并与B中相应元素对应好,并以A中元素的行号,B中元素的列号作为key:
    以以上文件作为Map输入,在Map中进行乘法运算,在Reduce阶段按key进行加法运算,就得到矩阵相乘计算结果了。
    缺点及难点
    1、矩阵元素副本准备。
    如果想以以上格式作为初始Map输入,那么我们就需要事先将数据整理成以上格式。对于两个超大矩阵相乘来说,这是一个艰巨的任务。矩阵元素一般来源于亚博平台可以赌(暂且如此假设,比如说做商品推荐,用户数据,商品数据都是存在亚博平台可以赌中的),那么整理成以上格式的文档作为Map输入文件,我们需要查询亚博平台可以赌的次数为:
    m*r*n + r*n*m
    由于m,r,n都是极其庞大的,这个查询次数是我们万万不能忍受的。理想的亚博平台可以赌查询次数是:
    m*r + r*n
    即矩阵元素只取一次。
    还有一种方法是矩阵元素只取一次,每个元素的副本生成交给Map-Reduce去做,但是这样存在另一个问题:如果在Map-Reduce过程中将A矩阵和B矩阵中的元素进行副本拷贝,单个Map的运算时间有点让人接受不了,打个比方,一个Map块为64M,大约存了500万条A矩阵的元素,同时B矩阵的n为10亿,那么计算这个Map的节点需生成500万*10亿条副本,这个时间是难以忍受的。
    2、两个矩阵中需相乘的元素如何对应。
    由于利用亚博平台可以赌查询进行矩阵元素对对应时间复杂度太高,一般不太可行。所以可以考虑利用Map-Reduce对相应元素进行对应。不过Map只对输入记录进行一次处理,处理完毕便结束,不存在内存的概念,所以对两个矩阵中元素进行对应是一个难点。
    3、文件大小规模。
    对于超大规模矩阵,由于A中m和B中n太大,除去稀疏元素(值为0)不纳入计算,需拷贝的元素依旧很多,拷贝完的文件大小是极其庞大的。笔者做了个实验,将A(1000*1000) B(1000*1000)两个稠密矩阵中的元素按规定(A中每个元素拷贝1000份,B中每个元素拷贝1000份)进行副本拷贝,拷贝完的记录数为2*109条,文件大小达到24G。那么对于亿万规模的矩阵,文件大小将成指数级增长。
    本文方法
    “行列相乘运算”对于稀疏矩阵可以,但是对于大型的稠密矩阵显得有点力不从心;而对于“分块矩阵运算”很多学者做了很多研究,但是笔者不太喜欢该算法,第一是逻辑控制麻烦,第二是对块的大小优化来优化去,没有解决本质上的问题。笔者我喜欢简单的东西,所以更倾向于“基于最小粒度相乘的算法”。不过,就像我们之前所说的,“基于最小粒度相乘的运算”存在三个问题,接下来,笔者将针对其中的两个问题阐述笔者自己的想法。
    新颖的矩阵相乘元素映射方法
    矩阵A*B=C中,Ci,j是A中第i行与B中第j列相乘的结果,如公式(1)所示。通俗点可以写成如下格式:

    然后在Map端进行各条记录的相乘运算,最后在Reduce阶段进行汇总,得出最终矩阵相乘的结果。不过正像“基于最小粒度相乘的算法”中所说的,由于key i-j 不具备明显的区分度,且Map过程中,内存不保留矩阵元素,将数据组织成以上格式是极其困难的。如果在Map输入前,将数据组织成以上格式,查询亚博平台可以赌的时间复杂度也是难以接受的。
    通过思考我们不难发现,最终结果Ci,j是由r个值相加而成的,第k个组成成分为:A,为了使key更有区分度,我们将key修改为:
    这样的key所代表的两个值相乘,得到了Ci,j中第k个组成元素。所以对于A矩阵和B矩阵在Map阶段完成数据副本拷贝完后,所有的Map数据记录中,i-j-k的key有且至多只有两个(由于稀疏元素不纳入计算与拷贝,所以若为一个,则说明与之相乘的另一个元素为0,若一个也没有,则说明A与B都为0,没有纳入计算与拷贝)。
    由于A中每个元素理论上都需要被计算n遍,所以可以将A中元素按如下规则进行n遍拷贝,对于A,拷贝方式如下:
    对于B中每个元素,理论上每个元素都需要被计算m遍,所以可以将B中元素按如下规则进行m遍拷贝,对于B,拷贝方式如下:
    由于每个元素的副本拷贝都是独立的,所以可以由不同的Map进行,大大加快了拷贝速度。
    实验结果
    笔者用以上方法做了实验,A(m,r)*B(r,n)=C,其中m=r=n=1000,所以两个矩阵中共有2*106个元素,A与B都为稠密矩阵,以“A-i-k value”和“B-k-j value”的形式存储原始的A矩阵和B矩阵的元素,文件大小为24M。由于文件太小,所以只交给一个Map进行副本的拷贝工作,每个元素都被拷贝一千遍,拷贝完总记录数为2*109条。消耗时间如下:
    图4
    由图4可以看出,一个Map执行的时间非常长,这是因为Map中的每条记录都需要拷贝1000遍。如果在现实应用中,两个矩阵超大,那么许多Map的块大小都将被填满,一个块大概放500万条记录,同时由于每条记录都被拷贝m或n遍(m,n很可能就是数以亿计),那么一个Map的执行时间就是无底洞了。
    为了减少每个Map的执行时间,笔者苦苦冥想,终于想出一种方法,将在接下来的小节进行介绍。
    创新的细胞分裂拷贝算法
    上一小节中有讲到Map的执行时间过长,有同事建议我说将Map的块变小点,这样里面的记录数也少点,不同的块由不同的节点执行。但是笔者认为这种想法不合理,一个块是变小了,里面的记录也小了,但是若每条记录需拷贝的数量是庞大的,那根本于事无补。而且对于不同大小的矩阵相乘,矩阵元素需拷贝的数量也都是不一样的,因此块的大小很难控制。再者,对于Hadoop运算,正常情况下都是加大Map块的大小,这样有利于计算的集中。
    而在本方法中,Map拷贝过程之所以时间太长,笔者认为是由于每条记录拷贝的数量太多造成的,如果一条记录的拷贝能分段在不同的节点完成就好了,出于这样的想法,笔者设计了一种利用Map迭代进行拷贝的方法,由于迭代过程中Map数量的扩张有点像细胞分裂,笔者称之为“细胞分裂拷贝算法”。
    由于每个矩阵元素需要拷贝多少遍是确定的,因此我们可以设计一种分段拷贝方法来让不同的节点进行拷贝工作。这里有两个变量需要介绍,一是num_split,代表一条记录在一次迭代过程中最多被分的段数,另一个是num_copy,代表每个最终分段最多需拷贝的记录数。在迭代过程中,如果某条记录的某个分段范围大于num_copy,则继续进行分段,否则就进行拷贝工作。现举例说明迭代过程。
    对于A中元素A,其需要被拷贝1000遍,为了将其拷贝成公式(3)所示,我们利用细胞分裂拷贝算法将拷贝工作分配到不同的计算节点进行,该例中num_split和num_copy的数值都为10,那么迭代过程如下:

    图5
    而对于B中元素,我们同理利用迭代拷贝的方法将其拷贝成公式(4)所示格式,即主要的范围辨别集中在i上。

    由图5可以可以看到,每一次迭代,数据记录都是成num_split的倍数增长,这样,随着记录集文件大小的增长,文件被分成越来越多的Map,自然也就被分配到越来越多的计算节点进行执行。查看图5中的第三次迭代工作,由于记录范围符合记录生成条件,即记录范围

    本帖子中包含更多资源

    您需要 登录 才可以下载或查看,没有帐号?立即注册

    x
    分享到:

    0

    主题

    586

    帖子

    1292

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    1292
    沙发
    发表于 2019-4-3 11:48:22 | 只看该作者

    0

    主题

    568

    帖子

    1258

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    1258
    板凳
    发表于 2019-4-8 23:12:06 | 只看该作者

    0

    主题

    478

    帖子

    1062

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    1062
    地板
    发表于 2019-4-14 03:46:31 | 只看该作者

    0

    主题

    586

    帖子

    1292

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    1292
    5#
    发表于 2019-4-14 08:07:08 | 只看该作者

    0

    主题

    478

    帖子

    1062

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    1062
    6#
    发表于 2019-4-14 17:59:37 | 只看该作者

    0

    主题

    478

    帖子

    1062

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    1062
    7#
    发表于 2019-4-15 09:05:17 | 只看该作者

    0

    主题

    272

    帖子

    644

    积分

    高级会员

    Rank: 4

    积分
    644
    8#
    发表于 2019-4-16 09:25:31 | 只看该作者

    0

    主题

    271

    帖子

    640

    积分

    高级会员

    Rank: 4

    积分
    640
    9#
    发表于 2019-4-16 15:25:48 | 只看该作者

    0

    主题

    586

    帖子

    1292

    积分

    金牌会员

    Rank: 6Rank: 6

    积分
    1292
    10#
    发表于 2019-4-17 04:23:08 | 只看该作者
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    官方微博:

    官方头条号:

    官方微信

    手机访问:

    官方微信

    QQArchiver 手机版 小黑屋 一起学LINUX - GOGOLINUX 闽ICP备18025837号-1 Discuz! X3.4 Powered by © 2001-2013 Comsenz Inc. 

    本站资源均来自互联网或会员发布,如果侵犯了您的权益请与我们联系,我们将在24小时内删除!谢谢!

    快速回复 快速发帖 返回顶部 返回列表