比传统
集群计算可能的粒度更小,并且用户不因空闲资
源
而被收费。然而,为了有效地管理资源,云提供商对每
个资源的使用进行了限制接下来我们讨论这些约束如何影响
我们系统的设计
。
计算。
在无服务器 平 台 中运行的计 算 资 源
通常限于单个
CPU核心和
短的计算窗口。例如,AWS Lambda在单个
AVX核心上提供900秒的计算,并可访问高达3 GB的内存
和512 MB的磁盘存储。
用户可以执行许多并行功能,并
且
这些执行的聚合计算性能
几乎呈线性扩展。
函数执行中的线性可伸缩性仅适用于单个工作者之间没
有通信的并行计算不幸的是,由于单个工作者是短暂的,
并且由于他们的启动时间可能是错开的,因此传统的类似
MPI
的对等通信模型在这种环境中将不起作用
。这鼓励我
们利用存储,它可以用作工作人员之间的间接通信渠道
。
存储. 云提供商提供了从键值存储到关系数据库的许多存储
选项。有些服务并不是纯粹的弹性服务,因为它们需要预先
配置
资源。 然而,
像Amazon S3或Google Cloud这样的分布
式对象存储系统拥有无限的存储空间,用户只需要
为存储的
数据量付费。 从 [25]中完成的研究中
,我们看到AWS
Lambda 函 数 调 用 可 以 以 800 GB/s 或 更 高 的聚合带宽读写
AmazonS3,如图1所示,大致将数据中心网络带宽饱和到每个
核心。 这意味着我们可以在
分布式对象存储中存储计算期间
的中间状态,并且仍然可以获得
与从其他节点的RAM访问
相同的带宽。
最后,对象存储系统中的数据存储成本
与实例存储器相比, TEM 通常低几个数量级 例如,在
Amazon S3上,
数据存储的价格为每TB小时0.04美元;相
比之下,最便宜的
大型内存实例的价格为每TB小时6美
元。 这
意味着如果
访问模式不需要实例内存,则使用存
储系统可能更便宜。S3请求也按每个读请求4 e-6美元和每
个写请求5e-6美元收费 然而,在我们的实验中,我们发
现,如果
存储粒度足够粗,则与总存储成本相比,每个
请求的成本是微不足道的。
除了存储服务之外,云提供商
还提供订阅服务,如Amazon
SQS或
Google Task Queue。 这些服务通常不支持
高数据访
问带宽,但提供了一致性保证
比如至少一次交付,并且可以用于
“控制平面”状态,比如在所有
无服务器函数调用之间共享的任务队列。 云供应商还提供一致的
键值
存储(例如,DynamoDB),可用于
跨无服务器函
数
调用存储和
2.2 线性代数算法
在这项工作中,我们广泛关注的情况下,大规模的
稠密
线性代数。这个领域有丰富的文献
并行通信避免算法和
现有
的高性能实现[2,5,6,19]。
为了激励设计决策,在随后的章节中
,我们简要回顾
了解决线性系统的核心子程序
Cholesky因式分解的通信
和计算模式。
Cholesky因式分解是求解线性方程组最流行的算法之一,广
泛应用于矩阵求逆、偏微分方程和蒙特卡罗模拟等领域。
为了说明Cholesky分解的使用,考虑
求解线性方程Ax =
b
的问题
,其中A是对称
正定矩阵。 首先对A进行
Cholesky
分解
,
得到两个三角矩阵A = LL
T
(
n3
),然后
求解两个相对简单的方程
Ly
=
b
(
n2
通过前向
代换)和
LTx
= y
(
n2
通过后
向
代换),得到解
x
. 从这个过程中,我们可以看到分解是最
昂贵的步骤。
[5]这是一个很好的学习方法。
Cholesky分解的计算方法该算法
将矩阵分为块,并推导
出一个
计算顺序,使总的数据传输最小化。我们选择这
个例程不仅是因为它是最高性能的例程之一,
还因为它
展示
了许多线性代数算法中
算法1中示出了用于避免通信的Cholesky分解的伪代码
在
外部循环(j)的每一步,算法rst计算
单个块A
jj
的
Cholesky
分解
(图1)。2(a))。该结果用于
更新由A ij下方的
列块组成的
2(b))。最后
,通过根据它们各自的
位置对
面板进行索引来更新列j右侧的所有块(图11)。2(c))。 这
个过程是重复移动下
对角线(图。2(d))。
我们从分析
算法1的计算结构中首先,我们看到算法
在执行过程中表现出
动态并行性
外部循环由三个不同的
步骤组成,它们具有
不同的并行度,从1,K到 其中K
是
每一步的封闭子矩阵大小。此外,随着
K
在每次迭代中减
小,可用的总体并行性