活捉那只抢算力的谷歌员工!挤占计算资源?博弈论或可破解数据中心“囚徒困境”_谷歌公布的数据中心 集群计算工作负载数据集-程序员宅基地

技术标签: 人工智能  

大数据文摘出品

来源:IEEE

编译:赵吉克、武帅、钱天培

 

把“数据中心”和“博弈游戏”两个词放在一起,你会想到什么?经济学家们研究的“囚徒困境”?还是《魔兽世界》的用户数据?

 

我们今天要讲的,正是“数据中心”和“博弈游戏”的结合,但和在线游戏一点关系没有。

 

今天的话题,是切实发生在数据中心的博弈——从共享的大量计算机和存储系统中抢占资源

 

即使是在算力最为充足的的公司——谷歌,员工们也常常进行这样的博弈。

 

当要求提交任务的计算需求时,一些员工会夸大了他们对资源的请求,以减少与他人共享的数量。有趣的是,其他一些员工则会减少了他们的资源请求,假装他们的任务可以轻松地在任何一台计算机上完成。一旦他们在一台机器上开始任务,相关的操作就会耗尽机器上所有可用的资源,并挤掉他们同事的任务。

 

这些伎俩看起来有点滑稽,但它直指一个真正的问题——效率低下

 

2018年,全球数据中心耗电量为2050亿千瓦时,几乎和澳大利亚全境的用电量相当,约占世界总量的1%。由于服务器未被充分利用,因此大量能源被浪费掉了。一台空闲服务器所浪费的电力相当于其峰值用电量的50%;而当服务器开始工作时,其固定的电力成本就将分摊到该工作上。

 

由于运行单个任务的用户通常只占用服务器资源的20%到30%,因此多个用户必须共享服务器以提高其利用率,从而提高其能源效率。共享还可以降低资本、运营和基础设施成本。毕竟,不是每个人都有足够的钱来建立自己的数据中心。

 

 

为了分配共享资源,数据中心部署有资源管理系统,根据用户需求和系统自身目标,对可用的处理器内核、内存容量和网络资源进行划分。乍一看,这个任务应该很简单,因为用户经常有补充需求。但事实并非如此。共享在用户之间产生了竞争,正如我们看到的谷歌员工,很可能会扭曲资源的使用。

 

因此,我们可以使用博弈论(game theory),即描述理性决策者之间战略交互的数学模型,进行了一系列项目,以此来管理这些自私用户之间的资源分配,同时最大化地提升数据中心的效率。在这种情况下,这种博弈还确实有利于解决资源分配问题。

 

货币兑换机制失效,博弈论登场

 

帮助一群理性和自私的用户有效地共享资源并不仅仅是大数据时代的产物。经济学家们几十年来一直在这样做。

 

在经济学中,市场机制根据供求来决定资源的价格。实际上,目前不少公共数据中心就在这么做,比如Amazon EC2和Microsoft Azure。在那里,真实货币的转移充当了一种工具,将用户的动机(绩效)与提供商的目标(效率)结合起来。

 

然而,在许多情况下,货币兑换机制是失效的

 

 

让我们考虑一个简单的例子。

 

假设在你最好朋友的婚礼上,你得到了一张歌剧演出的门票,你决定把票给最喜欢该演出的人。所以你要进行所谓的第二价拍卖:让你的朋友们为这张票出价,规定赢家支付给你第二高的出价。数学上已经证明,在这种拍卖中,你的朋友没有动机去谎报他们对这张歌剧票的估价。

 

如果你不想要钱或不能让你的朋友付你钱,你的选择就会变得非常有限。如果你问你的朋友他们有多想去看歌剧,没有什么能阻止他们夸大他们对门票的渴望。歌剧票只是一个简单的例子,但在很多地方——比如谷歌的私人数据中心或学术计算机集群——金钱要不不能转手,要不就是不该转手,更不能以此来决定谁得到什么。

 

博弈论为这类问题提供了可行的解决方案——实际上它已被应用于计算机网络和计算机系统。我们从这两个领域获得了灵感,但我们也必须解决它们的局限性。在计算机网络中,有很多工作通过设计机制来管理自利的和不协调的路由器以避免拥塞。但是这些模型只考虑对单个资源网络带宽的争用。在数据中心计算机集群和服务器中,有各种各样的资源需要争夺。

 

在计算机系统中,人们对考虑多种资源的资源分配机制产生了浓厚的兴趣,特别是一种称为支配资源公平性的机制。然而,这类工作仅限于性能模型和处理器与内存的比率,它们并不总是反映数据中心的真实场景。

 

“计算冲刺”引起“公地悲剧”

 

为了提出适用于数据中心的博弈论模型,我们深入研究了硬件架构的细节,从最小的层次开始:晶体管

 

长期以来,晶体管在缩小体积的同时耗散的功率越来越小,部分原因是降低了工作电压。然而,到2005年左右,这种被称为登纳德缩放比例的定律已被打破

 

 

结果就是,对于固定的电力预算,处理器不再以我们习惯的速度变快。一个临时的解决方案是将多个处理器核心放在同一块芯片上,这样大量的晶体管仍然可以在经济上得到冷却。然而,很明显,你不可能同时全速运转所有的核心,否则芯片会熔化。

 

2012年,计算机架构师提出了一种名为“计算冲刺”(computational sprinting)的变通方法。其概念是处理器核心可以在短时间间隔(称为冲刺)内安全地突破它们的能量预算。在一次冲刺之后,处理器必须在下一次冲刺之前冷却下来;否则芯片就会被熔毁。如果处理正确,“冲刺”可以使系统对工作负载的变化做出更快速的响应。“计算冲刺”最初是为智能手机等移动设备的处理器而提出的,因为这些处理器必须限制用电量,以节省电量,同时避免“烫伤”用户。但“冲刺”很快就应用于数据中心来处理计算需求的激增。

 

这就是问题所在。假设自私的用户们拥有启用了带有“冲刺”的服务器,这些服务器在数据中心中共享一个电源供应。用户可以通过冲刺来提高处理器的计算能力,但如果大部分处理器同时冲刺,那么电力负荷将会激增。然后断路器跳闸。这就迫使不间断电源(UPS)中的电池在系统恢复时提供电力。在这样的紧急情况之后,所有的服务器都必须在电池充电的时候以额定功率运行——不允许冲刺

 

这种情形是经典的“公地悲剧”(tragedy of the commons)的一个版本,英国经济学家威廉·福斯特·劳埃德(William Forster Lloyd)在1833年的一篇文章中首次提出了这一观点。他描述了如下的情况:假设牧牛人共享一块土地来放牧他们的牛。如果一个牧民把超过分配数量的牛放到公共草地上,这个牧民可以获得边际收益;但如果许多牧民这样做,过度放牧将破坏土地,伤害所有人。

 

我们与当时杜克大学(Duke University)的博士生Songchun Fan一起,把“冲刺”战略当作公地悲剧来研究。我们建立了一个关注两个主要物理约束的系统模型。首先,对于服务器处理器,冲刺要求处理器在芯片散热时等待,从而限制了未来的操作。其次,对于一个服务器集群,如果断路器跳闸,那么所有的服务器和处理器必须在UPS电池充电时处于等待状态

 

我们设计了一个博弈游戏。在每一轮比赛中,用户可能处于三种状态中的一种:活跃状态、冲刺后的冷却状态、紧急断电后的恢复状态。在每一轮游戏中,用户唯一能决定的就是当他们的处理器处于活动状态时是否进行冲刺。用户希望优化他们的冲刺以获得好处,比如提高吞吐量或减少执行时间。但也要注意,这些好处会随着冲刺的发生时间而变化。例如,冲刺在需求量大的时候更有益。

 

 

考虑一个简单的例子。在第5轮,你知道如果此时冲刺将获得10个单位的收益,然而处理器必须冷却几个回合才能再次冲刺。假设现在你冲刺了,那么在第6轮,你会发现冲刺可以获得20个单位的收益。另一种情况是,你将冲刺权保存到了下一轮但所有其他用户都决定在第5轮时冲刺,这导致电力紧急情况,使你无法在后续几轮中冲刺。更糟的是,到那时你的收益就不会那么高了。

 

短跑游戏中的“平均场博弈分析”

 

玩家们使用一个数据中心来共享信息。如果其中一个玩家选择在第5轮冲刺,他们将获得一定的收益,但他们必须要等处理器冷却一段时间才能再次加速。如果他们等到第6轮或者之后再冲刺,他们会获得更多收益。

 

如果太多的玩家同时冲刺,电流大幅度增加会导致断电。在计算机集群的不间断电源电池充电之前,任何人都不能再冲刺,即使是没有冲刺的玩家4也不行。

 

所有用户都必须权衡他们获得的效用的多少和其他用户的冲刺策略,之后再做出相应的决定。虽然少数用户竞争的例子可能很有趣,但随着竞争对手的数量增长到数据中心的规模,做出这些决定就变得非常棘手。

 

幸运的是,我们找到了这种叫做“平均场博弈分析”的方法,可以在在大型系统中优化每个用户的策略。这种方法将所有用户策略考虑为一个整体,避免了考虑每个竞争对手策略的复杂性。这种统计方法的关键在于假设任何单个用户行为都不会显著地改变系统的平均行为。正是由于这一假设,我们可以用单个平均效应来近似所有其他用户对任何给定用户的影响。

 

这有点类似于数百万上班族试图优化他们的日常出行。我们以文摘菌这样一个上班族为例。虽然不能用她以一概全。但是,文摘菌的行为模式可以推断出上班族这一总体在特定一天中希望到达的时间,以及他们的出行计划会如何加剧道路拥堵等。

 

平均场分析允许我们找到冲刺游戏的“平均场平衡”。用户会优化他们对群体的响应。这也意味着,在平衡状态下,偏离他们对整体的最佳响应将没有任何好处

 

在交通情况中,文摘菌会根据对通勤人群平均行为的理解来优化通勤。如果优化后的计划没有产生预期的交通模式,她就会修正自己的预期并重新考虑自己的计划。随着每一个通勤者在几天内的一次优化,交通收敛到一些重复的模式,通勤者的独立行动产生一个平衡。

 

通过平均场平衡,我们制定了冲刺游戏的最优策略:当性能收益超过某个阈值时,用户应该冲刺

 

该阈值根据用户的不同而不同。我们可以使用数据中心的工作负载及其物理特性来计算这个阈值。

 

当每个人都在平均场平衡下以他们的最优阈值运行时,系统将会受益良多。首先,数据中心的电源管理可以是分布式的,因为用户可以实现他们自己的策略,而不需要向中心管理员请求加速许可。这种独立性使得功率控制更加灵敏、节能。用户可以在微秒或更少的时间内调节处理器的功耗。而如果他们必须等待几十毫秒来获得许可,才能通过数据中心,那么这种效果将难以实现。其次,用户可以根据自己的工作负载需求来及时优化加速策略,使得均衡条件下可以完成更多计算工作。最后,当增益超过阈值时,用户的策略就变成了简单的冲刺。这是非常容易执行的。

 

贪得无厌必自毙:在冲刺游戏中,与“贪心”策略相比,使用平均场均衡策略可以用更少的力完成更多的功。

 

博弈论必将发挥巨大作用

 

“冲刺管理项目”只是我们在过去五年中开发的一系列数据中心管理系统中的一个。在每一款游戏中,我们都使用了硬件架构和系统的关键细节来设计游戏。而这样利用这一管理机制使得,当参与者行为表现得过于自私利己时,系统依旧可以稳定运行。我们有理由相信,这样的保证只会鼓励共享系统的参与,并为节能和可扩展的数据中心奠定坚实的基础

 

尽管我们已经设法在服务器多处理器、服务器机柜和服务器集群级别解决了资源分配问题,但是将它们用于大型数据中心仍需要很多工作。一方面,你必须能够生成数据中心的性能概要。因此,数据中心必须部署必要的基础设施来监视硬件活动、评估性能结果和推断对资源的偏好。

 

这类系统的大多数博弈论解决方案都要求分析阶段离线进行。相反,构建可以从一些先验知识开始,然后在执行过程中随着特征变得更清晰,而更新其参数的在线机制可能干扰更小。在线机制甚至可能通过强化学习或另一种形式的人工智能来改进游戏。

 

 

还有一个现实问题就是:在数据中心,用户可以随时进出系统,任务可以在计算过程中随意穿插,服务器可能会失败并重新启动。所有这些事件都需要重新分配资源,但是这些重新分配可能会破坏整个系统的计算,并要求对数据进行分流,从而耗尽资源。

 

在保持每个人公平竞争的同时,应付所有这些变化肯定需要更多的工作,但我们坚信博弈论必将发挥巨大作用

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/BigDataDigest/article/details/105365601

智能推荐

仿着锤子科技官网进行的一个angular4.0项目~~~-程序员宅基地

文章浏览阅读1k次。关于项目关于angular4的一个项目项目功能还没完全实现 代码我放在了GitHub上

基于阿里云容器镜像服务加速K8S镜像下载_kubectl 阿里云下载-程序员宅基地

文章浏览阅读4.5k次。简单说明:部署K8S最大的难题是镜像下载可以使用阿里云容器镜像服务由海外机器构建国内同时可以使用阿里云的镜像加速器加速镜像下载仅需要将含有相关镜像的Dockerfile提交到阿里云即可申请云Code代码托管账号作为代码源可以绑定到阿里云镜像仓库的代码托管服务有很多,这里选用云Code登陆阿里云:https://www.aliyun.com打开云Code账户设置:https:/..._kubectl 阿里云下载

Aptina MT9M114 1.26M camera spec 学习_mt9m114点亮代码-程序员宅基地

文章浏览阅读1.5k次。MT9M114是出自ON半导体公司的CMOS (CMOS与CCD的区别) digital image sensor, active-pixel array是1296 (H) × 976 (V)=1.26Mp.关键参数 Parameter Typical Value 中文解释 Optical Format 1/6-inch ..._mt9m114点亮代码

计算机科学与技术在军中的应用,计算机科学技术的应用及发展趋势-程序员宅基地

文章浏览阅读2.5k次。114 ?电子技术与软件工程 Electronic Technology & Software Engineering计算机技术应用? the Application of Computer Technology【关键词】计算机科学技术 应用 发展趋势计算机科学技术的发明是人类社会史上的重要财富之一,并经过不断的改革创新,使得计算机科学技术在人们的生活中得到广泛应用。并涉及到社会上各个领域...

Android画板的实现-程序员宅基地

文章浏览阅读87次。这是一个常见的画板功能,常用于画画和手写输入等等,今天就教大家实现这个小功能,这个功能还是比较简单的,只有一个Java文件先看效果图布局代码,只有三个按钮和一张图片<?xml version="1.0" encoding="utf-8"?><LinearLayout ="http://schemas.android.com/a..._androi画板代码

论文代码不开源,应该被直接拒稿?-程序员宅基地

文章浏览阅读4.9k次,点赞3次,收藏5次。公众号关注“GitHubDaily”设为 “星标”,每天带你逛 GitHub!转自机器之心前不久,图灵奖得主 Yann LeCun 公开质疑谷歌大脑的论文无法复现,引起了社区热议。Le..._代码没有开源 如何复现论文

随便推点

r语言显示找不到read_html,R语言答疑:txt文件无法被R正确读入-程序员宅基地

文章浏览阅读1.6k次。今天来解答一个网友的疑惑,或许你也曾遇到过这个问题噢~R语言中,txt无法正确的读入的可能性有很多种。有位网友提供的一个无法正确读入的文本文件,使用记事本打开,看起来一切正确(见图片)。但读入的时候,报错如下。>read.table('1.txt')Error intype.convert(data[], as.is = as.is, dec = dec, numerals = numera..._error in read_html(url) : 没有"read_html"这个函数

恒生电子工作经历-程序员宅基地

文章浏览阅读1w次。2012年7月开始正式入职恒生

ZYNQ接口分析_zynq的b35接口是什么意思-程序员宅基地

文章浏览阅读4.1k次,点赞3次,收藏21次。有人说,自动生成工程时,有可能将所有axi-lite连接到了zynq_us的m_axi_hpm0_lpd上,好像默认lpd不能用,需要开启时钟、电源?还是什么使能信号才可以用,所以会导致sdk中的例子不能直接访问pl上的外设,并导致cpu挂死。可以将lpd改为fpd,这样应该就没问题了。是否是这个原因,未确认,还有可能是“ID转换”无法(2条消息)2. ZCU102 HDMI Demo【P..._zynq的b35接口是什么意思

linux系统挂载光盘设备,文件系统的挂载、usb设备光盘的使用-程序员宅基地

文章浏览阅读389次。一、 文件系统的挂载mount:1. 挂载命令mount使用:(1)挂载: 将额外文件系统与根文件系统某现存的目录建立起关联关系,进而使得此目录做为其它文件访问入口的行为,挂载点下原有文件在挂载完成后会被临时隐藏(2) 卸载:为解除此关联关系的过程,可使用设备,也可以使用挂载点(3) 用法:mount 设备 挂载点设备类型:1) 可以使用设备文件如/dev/sda;2) 可以使..._linux 挂载光盘 df

openoffice module or group “X Window System“ is not available_module or group 'x window system' is not available-程序员宅基地

文章浏览阅读6.7k次,点赞2次,收藏10次。openoffice 安装最后一步启动提示"X Window System" is not available 图形化窗口_module or group 'x window system' is not available.

基于MATLAB的FIR滤波器的设计及应用(图像_matlab如何绘制fir滤波器的幅值曲线-程序员宅基地

文章浏览阅读945次,点赞23次,收藏25次。利用等波纹最佳逼近准则设计线性相位FIR数字滤波器数学模型的建立及其求解算法的推导复杂,所以求解必须借助MATLAB信号处理工具箱函数remezord和remez,只要简单的调用这两个函数就可以完成线性相位FIR数字滤波器的等波纹最佳逼近设计。1.该课题设计是先画出原始图像,然后画出加噪图像,然后由各项参数求出单位脉冲响应和其频率响应,再分别用布莱克曼窗函数法和等波纹最佳逼近法画出信号波形和去噪图像,并分析和比较,在分别求出损耗函数。_matlab如何绘制fir滤波器的幅值曲线

推荐文章

热门文章

相关标签