雷锋网|星云 Clustar 首席科学家胡水海：GPU 在联邦机器学习中的探索( 三 )
本文插图
基于这个思想 ， 我们可以通过递归的方式将大整数乘法分解成很多可并行计算的小整数乘法 ， 这样GPU就能发挥并行计算的优势完成大整数乘法的快速计算 。 不仅如此 ， 对于联邦学习涉及的其他大整数运算 ， 也可以做类似的元素级并行 。
本文插图
第二个解决方案是用平方乘算法+蒙哥马利算法解决GPU做模幂运算代价大的问题 。 其核心是如何高效计算模幂运算abmodc ， 其中a,b,c均为N比特大整数 。 对于这个问题 ， 最容易想到的朴素算法是先计算ab的值 ， 然后将计算结果对c取模 。 但这样会使问题计算复杂度高达O(2^N) ， 并且中间的乘积结果很大 。 我们采用的方法是通过平方乘算法进行优化 。 平方乘算法主要基于的观察是：我们要计算a^K ， 并不一定需要将a自乘k次 ， 而是可以先计算出a^k/2的值 ， 然后求平方 。
以此类推 ， 我们只需要logk次的乘法运算就可以得到ak的值 。 根据这个思想 ， 我们可以将b表示为2进制数 ， 然后通过O(N)次乘法以及取模运算得到计算结果 。 这类方法的优点是将复杂度降低到O(N)并且中间计算结果的大小不超过c 。
缺点是需要做2N次取模运算 ， 对GPU来说 ， 做取模运算的时间代价很高 。 为了解决这个问题 ， 我们引入了蒙哥马利模乘算法来高效完成第3步中的模乘计算 。 蒙哥马利算法的优点能够让复杂度下降到O(N) ， 中间结果大小不超过c ， 完全避免了取模/除法运算 ， 从而大大加快了运算速度 。
本文插图
对于第三个挑战 ， 如何减少中间计算结果 ， 我们给出的解决方案是通过中国剩余定理 。 中国剩余定理是数论领域的一个著名定理 ， 说的是给定一组两两互质的整数n1,n2,…,nk和任意一组整数a1,a2,…,ak ， 那么通过这两组数构造的下面这个同余方程组一定有解 ， 并且解一定同余于N 。
本文插图
那么怎么使用呢？首先定义mp跟mq这两个子项 ， 并依据这两个子项构造一个满足中国剩余定理的同余方程组 。 如上图所示 ， 并用CRT(mp,mq)来表示这个同余方程组的解 。 可以证明解密计算公式等价于同余方程组的解modpq ， 所以可以通过计算这个新的表达式来求解m的值 。 根据上面三个计算表达式 ， 会有两个观察结论 。 首先 ， 三部分的中间计算结果都不超过N比特 ， 因此减小了中间计算结果 。 此外 ， 计算公式从2N比特数的模幂运算简化成N比特数的模幂运算 ， 计算量大幅减小 。
本文插图
最后看一下GPU加速联邦学习的初步评测结果 。 我们主要评测了四种运算：同态加密、同态解密、密态乘法和密态加法在三种优化下的速比 。 对比的baseline是14核2.2Ghz的服务器级CPU ， 而使用的CPU代码是高度优化的 。
结果如上图：对于比较复杂的同态加密和解密 ， 在经过三种优化手段后 ， GPU为联邦学习带来了差不多6倍的加速比 。 对于计算相对简单的密态乘法和密态加法 ， GPU为联邦学习分别带来了30倍以上和400倍以上的加速比 。
加速联邦学习跨机构跨区域通信的探索
上面讲的是如何应对联邦学习计算方面的挑战 ， 那么在传输方面 ， 即在加速联邦学习跨机构跨区域通信方面 ， 主要考虑联邦学习通信的两大场景：场景一是数据中心内部不同机构间通信（主要是云服务器） ， 场景二是不同机构的数据中心跨区域通信（地理位置不同） 。
推荐阅读
![[坦言]收入提高了？滴滴司机坦言：因为平台这波操作，现在收入](/renwen/images/defaultpic.gif)
- 科学|在30300光年外的星云中，发现0.01倍太阳质量的行星盘！
- 公众号旗帜网络笔记|宇宙中很多恒星在星云内，其实也包括太阳系，但它却又是不同的
- 雷锋网|海康，为何强？
- |?神经拟态计算的“一小步”，AI发展的“一大步”
- 雷锋网|Hey，苹果罕见地让步了！以后“苹果税”还要交吗？
- 趣投稿|火星云矿商思林：穿越迷雾，写给Filecoin新矿工的3条建议
- cnBeta|哈勃太空望远镜展示行星星云的新图像
- 雷锋界面|物联网卡是流量卡吗？和手机流量卡有什么区别？
- 雷锋网|为付费用户提供差异化服务，Dropbox增添新功能
- 雷锋网|继亚马逊后，IBM、微软相继美国警方禁售面部识别技术