最近(以及预感接下来的一年)会读很多很多的paper......不如开个帖子记录一下读paper心得

Mark一个上海交通大学东岳网络工作室的paper notebook

Mark一个大神的笔记


Edge computing

DLion: Decentralized Distributed Deep Learning in Micro-Clouds

在Distributed DL中,一个很常见的场景就是要在edge侧(Edge Device表示性能和稳定性都不太好的设备,比如用流量上网的手机)得到一些新的数据,然后去refine一个之前已经train好的model(incrementalor online deep learning over newly generated data in real-time)。但是广域网是很慢的,如果要所有edge把数据传给一个总服务器要耗费很大的带宽,而且现在手机的性能已经有点够用了,所以我们希望搞个decentralize的DL framework,直接在edge侧就解决问题。

相对于纯Decentralize DL的工作,本文提出了一个micro-cloud的概念:micro-clouds—small-scale clouds deployed near edge devices in many different locations(用于给本地的一小部分edge服务,感觉有点类似CDN的意思?),然后重点关注如何在micro-cloud内部去实现Distributed DL。micro-cloud内部具有如下特点:每个node的性能(计算资源)有差异;网络情况有差异;micro-cloud的总量是很大的,而且分布在不同地区。本文就要针对这三个问题,既要提高速度也要提高accuracy,然后还得handle system scalability。

  • ch3.1:每个node的性能(计算资源)有差异,那么每个node根据自己的能力来设置batch size就完了。另外还应用了三种learning rate的调节方式。
  • ch3.2:为了保证性能,node之间的数据通信涉及到交换weights和gradient。然后我们需要实时根据网络情况(controlling the quality of data and considering the available network bandwidth)来调整通信策略。这个又要考虑以下几个因素:
    • when-to-do: when to exchange data, e.g., more frequently early or late in training, or periodically
    • what-to-do: whether to exchange whole or partial data
    • whom-to-do: whether to exchange data with all workers or a subset of workers
    • how-to-do: whether to exchange data synchronously or asynchronously

    这些是通过一个system parameter来调节的。然后Fig4和Fig5展示了不同策略的实验效果。

  • ch3.3:在system scalability这里,我们要考虑的是在WAN环境下,不同micro-cloud之间的通信问题啦,这个涉及到broadcast gradient。本文选择了只在两个micro-cloud之间通信,而不是直接broadcasting。然后根据micro-cloud各自的特征来选择谁是sender/receiver:性能好的batch size大(ch3.1),会有更多的informative gradient,所以作为sender。反之就作为receiver。micro-cloud之间的通信也采用ch3.2里提到的方法。

Future work:

  1. 用更大的scale来实验
  2. data migration:低性能的node上可能数据多。在migrate和load balancing(ch3.1)之间要有个tradeoff
  3. 考虑edge device的电量消耗问题

DeCaf: Iterative Collaborative Processing over the Edge

最近有一个很火的概念叫做Federated Learning:意思就是在不能接触到数据(因为可能涉及用户隐私)的情况下来训练ML model。那么在geo-distributed以及edge computing的场景下,就需要在不能将用户数据从edge侧传到central服务器的前提下analysis data(there is a need for approaches which enable analytics without transferring the raw data out of the edge devices.)。本文的idea就是解决在edge设备上performing ICP computation时,如何处理geo-distributed的edge device的drop out率太高等问题,并设计了一套计算框架。

(ICP的含义[ch3.1]:Iterative Collaborative Processing(ICP) involves performing a set of computations in multiple iterations.    ML中的training就是一种典型的ICP。比如在典型的参数服务器系统中,中心服务器上维护一套中心的parameter,各个edge负责用本地的数据训练自己的individual parameter,再和central进行同步。)

Related work中涉及到如下几个方面:1).Distributed ML system有很多,最著名的是parameter server,但它是centralized。2).Geo-distributed的系统也有很多,但针对ML workload的研究还不多。3).Federated ML的框架也有一些,但没有考虑edge computing中的一些场景:比如edge device经常会drop out(没电了或者关流量了)。    【所以知道idea都是怎么憋出来的了吧?】

我们这个system是一个星型拓扑的结构:所有edge连接到central controller上,但其实edge之间也可以P2P的通信。所有edge把本地计算结果推给controller,controller更新model parameter,再更新所有edge上的parameter。这个system要实现以下几个feature:

  • 1. Proactive(主动的) Monitoring and Prediction

    • edge设备的计算资源是很奇怪的(high variations in resource availability over time in edge environments),因此我们需要对edge device的资源(比如cpu使用率、剩余电量、网速等)进行实时监控,在后面会用到这些监控数据。这个就是很工程的东西了...安个鲁大师就行了hhhh
    • 另外还可以通过记录过去的resource utilization pattern,来试着预测未来的resource availability。有些related work表明这玩意其实也是可以ML的...(the application usage on mobile devices indeed exhibits temporal patterns)。
  • 2. Adaptive Tuning
    • 在controller向edge分发计算任务后,edge就开始计算啦,当然这个也是会被controller指定一个deadline的。为了确保every edge device finishes the model update within the deadline stipulated by the controller,有些edge device可能等不及处理完所有的数据,就要把结果发给central了(based on the resource availability, we can choose a subset of data points to iterate through)。当然这个subset的percentage的选择也是很有讲究的,需要在保证能赶得上deadline的情况下,选择尽量多的percentage(因为数据多的训练效果肯定好嘛,参考Fig2)
    • 那么这个percentage怎么选呢?可以构建一个resource-computation profile,意思就是根据当前device的resource availability来选择这个percentage。构建这个profile也是个很工程的东西(大体意思和鲁大师跑个分差不多......)
    • 本文中使用了一个比较基本的方法:在计算的过程中,根据已经计算了的数据量和已用时间,来推算deadline前还能处理多少数据。实验证明这个方法还可以。
  • 3. Fault Tolerance and Load Balancing
    • 前面说过数据太少的时候,训练出来的模型的quality是不大能用的。那么如果当前设备的available resource实在太少(比如快没电了),完成不了多少运算了,就需要直接放弃这个设备(也就是drop out),然后migrating the task to another edge device。但是在Federated Learning的场景下,migrate也要考虑用户数据的隐私问题。因此提出了下面的概念:Trusted Device Set。
    • Trusted Device Set:每个设备都可以指定自己的一个Trusted Device Set,表示数据可以在这些设备之间进行migrate(比如一个人有很多个手机、电脑、平板)。当某个设备发现自己蹦跶不了多久了,需要migrate时,就像trust set里的设备发出请求,然后在respond了的设备中选择一个migrate成本最小的进行migrate。因为local dataset一般是很小的,所以这个开销也不会很大。
    • 另外,在load balancing中,可能也会涉及到migration。比如把负责太重的device上的workload移到它的trust set中负载较轻的设备里。

本文以SVM为例测试了整个framework的效果。

An Edge-based Framework for Cooperation in Internet of Things Applications

111


Cloud

Rethinking Adaptability in Wide-Area Stream Processing Systems

111

Multi-Query Optimization in Wide-Area Streaming Analytics

这是SOCC2018的一篇文章,关注的是如何在Geo-Distributed的情况下进行data analysis,提高WAN bandwidth的使用效率并提高性能。

在streaming analysis query中,很多情况下执行情况都是类似的,比如使用相同的input dataset或者perform the same data processing procedure(比如大家都用Twitter data,只是进行的analyze任务不同,有人做sentiment analysis,有人做topic啥的),这种就是本文所说的multi-query。本文的idea关注的就是optimizing multiple queries by applying multi-query optimization in a WAN-aware manner。这里有两个key point:multi-query optimization、WAN awareness(这是为保证multi-query的性能必须要加的)。

Streaming按照computional model又可以分为两类:dataflow和bulk-synchronous parallel。本文先focus on dataflow model,意思是data streams flow continuously
from data sources into the system and are transformed by a set of stream operators。streaming query可以被视为像SQL一样的查询语句。另外,本文中的系统是geo-distributed,意味着数据可能一开始存在A地,然后由B地的服务器处理,又交给C地的用户,数据就要飞过来飞过去。如果系统能对WAN的拓扑结构有所了解,就可以设计更优化的执行方案了。这也就是需要WAN-aware的原因。

Multi-Query Optimization这个概念也是在DB那边学来的,目的是identify the commonality between queries and potentially combine their executions to mitigate redundant executions。另外在我们这个场景中,Multi-Query Optimization需要be done in an online manner as new queries arrive by sharing any common execution incrementally。因为streaming analysis query通常都是deployed once and run indefinitely,中间停个机改一改是不现实的。2.2节的后半部分举了个例子:Query1和Query2虽然业务逻辑不完全相同,但仍然有很多可以share的元素(both queries partially share common input streams (US and EU) and perform similar data processing (e.g., filtering user info)),如果这些只执行一次就可以省下很多带宽。

下面详细介绍下这两个组件:

  • Multi-Query Optimization:
  • WAN-aware Optimization:

Wiera: Policy-Driven Multi-Tiered Geo-Distributed Cloud Storage System

本文关注的是Cloud Storage System的问题,重点关注在storage system具有很多tier(专门为不同application优化的,不同种类的Storage System。比如ElasticCache/S3/...)、分布在很多location(multi-DC)的情况下,如何进行data placement。目标是achieve desired fault tolerance or to serve a dispersed set of end-users。

本文提出了一个叫做Wiera的存储系统,将data placement的问题抽象成一个constrained optimization problem(比如minimize total cost),然后用一些算法来优化它。另外还要处理一些类似fault tolerance之类的问题。

看起来很像5105的pa3啊......一致性协议都用的一样的Quorum......


Distributed ML

Mark一个MLsys大神的Blog

Decentralized distributed deep learning in heterogeneous WAN environments

这篇文章的idea一目了然:在geo-distributed的节点上进行Decentralized DL

这个场景下的Decentralized DL是有很多问题要解决的:

  1. WAN网络带宽很有限
  2. 节点之间计算能力差异很大,容易导致训练变慢,甚至不coverage

本文感觉没有提出啥自己的idea......就总结了下面几个方法,然后implement了一个framework:

  • automatically adjust:
  • 1) the frequency of parameter sharing
  • 2) the size of parameters shared depending on individual network bandwidth and data processing power
  • 3) introduces a new scaling factor to control the degree of contribution to parameter updates by considering the amount of data trained during unit time in each device.

本文主要参考了Ako这篇文章,他们通过sharing partial parameters来减少了通信开销。

好水啊。。。

Link:

https://www-users.cs.umn.edu/~chandra/tfako/home.html

Ako:  Decentralised  Deep  Learning with  Partial  Gradient  Exchange

23333

Towards Federated Learning at Scale: System Design

联邦学习是一个最近提出的概念。大概意思就是:假设A和B各自有不同数据,由于隐私需要他们的数据都不能公开,但A、B各自训练的小模型都不大好。因此他们希望结合AB双方的数据,来训练一个比较好的大模型。

联邦学习是要解决这个问题: 它希望做到各个企业的自有数据不出本地,而后联邦系统可以通过加密机制下的参数交换方式,即在不违反数据隐私法规情况下,建立一个虚拟的共有模型。这个虚拟模型就好像大家把数据聚合在一起建立的最优模型一样。但是在建立虚拟模型的时候,数据本身不移动,也不泄露隐私和影响数据合规。这样,建好的模型在各自的区域仅为本地的目标服务。在这样一个联邦机制下,各个参与者的身份和地位相同,而联邦系统帮助大家建立了“共同富裕”的策略。 这就是为什么这个体系叫做“联邦学习”。

因为数据是分散在各地的,联邦学习天然的自带分布式属性。本文通过一个例子来关注联邦学习系统的system design,目的是对于很多手机上的data训练一个global的模型,同时要保证这些data不能离开手机本地。The weights are combined in the cloud with Federated Averaging。Federated Learning System的大致流程如下:

Paper Reading_Distributed System-LMLPHP

  • (1)、Device们联系FL Server,申请加入当前轮的FL job。但是Device太多啦,目前只能先接受一部分Device。剩下的下一轮再说。(这个选择策略参考ch2.2的selection部分)
  • (2)(3)、FL Server从persistent store(可以理解成server的硬盘)读取模型,然后将current global model parameters打包成FL checkpoints,发给参与本次任务的device们。
  • (4)、所有的device使用收到的model和本地的data,在本地进行training(performs a local computation based on the global state and its local dataset)。完了之后将更新后的FL checkpoints发回FL server。
  • (5)、FL server根据devices发来的checkpoints进行incorporate(比如使用Federated Averaging),更新global的模型。然后GOTO (1)开始下一轮的job。

Fault tolerance:在(4)中没有按时向FL server返回checkpoints的device会被直接丢弃。而在(1)的select阶段中, 也会有一个timeout或者counter之类的约束规则。

Flow control:ch2.3

接下来分别来看两个重要的部件:Device(ch3)和Server(ch4)。这两节讲的比较工程化......

  • Device:Device上要存储本地的training data。还要通过一个schedule来控制启动training。
  • FL Server:FL server的实现基于Actor Programming Model,这是一种并发编程中的常用模型,用于处理系统中不同部件的通信和并发控制。整个结构如图Fig3所示。
    • Selector:负责直接和device通信。device请求加入时也是和selector联系,selector选好设备后forward给Aggregator。selector相当于公司的HR...
    • Aggregator:又分为master aggregator和aggregator,用于管理FL task中的每一轮。相当于公司里的一个个部门
    • Coordinator:负责控制整个FL训练的流程。比如要决定需要多少device然后报告给selector。然后让Aggregator来具体管理FL task。相当于公司的老总...

Secure Aggregation:uses encryption to make individual devices` updates uninspectable by a server.

上面balabala了这么多理论,那么一个FL模型的开发和上线过程是什么样的呢?可以分解为这么几步:

  1. Modeling and simulation:指的是MLE在本地先写好model(个人理解就像平时写个deep learning模型一样)。这里提出了proxy data的概念:MLE用来模拟用户端training data的一些data(Proxy data is similar in shape to the on-device data but drawn from a different distribution – for example, text from Wikipedia may be viewed as proxy data for text typed on a mobile keyboard.)。MLE在开发阶段可以拿这些data来调试自己的模型。同时可以用simulated FL server and devices来模拟FL的场景。
  2. Plan Generation:一个FL Plan可以理解为MLE针对某个任务开发好的FL模型,FL Plan会被部署到device和server上。device端包括tensorflow graph、模型的一些参数(比如batch size、epoch之类)、还有对training data的一些处理规则。而server端包括aggregation logic(用于把各个device的模型拼起来)。

正好学姐让我implement一下......那来看看用tensorflow如何实现吧!

Scaling Distributed Machine Learning with the Parameter Server

https://blog.csdn.net/stdcoutzyx/article/details/51241868


Streaming

TTL-based Approach for Data Aggregation in Geo-Distributed Streaming Analytics

这是一篇OSDI poster,后来转手就中了SIGMETRICS....orz

A TTL-based Approach for Data Aggregation in Geo-distributed Streaming Analytics

就是上面poster对应的长文...


Others

Flexible Paxos: Quorum intersection revisited

https://www.bilibili.com/video/av70763749

https://www.zhihu.com/question/320838210

....

05-28 00:58