Function Load Balancing Over Networks
Function Load Balancing Over Networks
复制标题
DOI：
10.1109/jsait.2021.3101762
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Derya Malak;Muriel M'edard
中科院分区：
文献类型：
--
作者：
Derya Malak;Muriel M'edard
使用网络作为计算手段可以减少网络上的通信流量。我们建议在固定网络中分配计算负载，并制定一个基于流的延迟最小化问题，共同捕获通信和计算的成本。我们利用分布式压缩方案的Slepian-Wolf，适用于任何协议信息。我们引入熵满射性的概念作为函数稀疏性的度量，并理解函数压缩对计算的限制。我们利用固定系统的小定律来提供满射性和计算处理因子之间的连接，该计算处理因子反映了需要通信的流量比例。这个连接让我们了解了一个节点（孤立地）应该计算多少才能在网络中传递所需的功能。我们的研究结果表明，为了有效地计算具有不同满射性的不同函数类，可以用为函数量身定制的转移概率来重构网络，即，基于任务的链接预留，这可以实现不同功能类的混合与单独处理。我们数值评估我们的搜索，MapReduce和分类功能的技术，并推断处理因素对每个计算任务的满射性有多敏感。
Using networks as a means of computing can reduce the communication flow over networks. We propose to distribute the computation load in stationary networks and formulate a flow-based delay minimization problem that jointly captures the costs of communications and computation. We exploit the distributed compression scheme of Slepian-Wolf that is applicable under any protocol information. We introduce the notion of entropic surjectivity as a measure of function’s sparsity and to understand the limits of functional compression for computation. We leverage Little’s law for stationary systems to provide a connection between surjectivity and the computation processing factor that reflects the proportion of flow that requires communications. This connection gives us an understanding of how much a node (in isolation) should compute to communicate the desired function within the network. Our results suggest that to effectively compute different function classes with different surjectivities, the networks can be restructured with the transition probabilities being tailored for functions, i.e., task-based link reservations, which can enable mixing versus separately processing of a diverse function class. We numerically evaluate our technique for search, MapReduce, and classification functions, and infer how sensitive the processing factor to the surjectivity of each computation task is.