Balanced Allocation Meets Queueing Theory

每天，我们都被依赖于大规模计算的情况所包围，从人工智能，通过并行处理的巨大数据集训练，到数据存储，如Dropbox。执行这些大规模的多核计算本身也带来了许多挑战。想象一下，一台有几个（比如说8个）处理核心的旧电脑。中央控制器可以实时跟踪每个内核分配了多少任务。可以将一个新任务分配给当前负载最小的核心。现在想象一个拥有数千个独立核心的现代设施——截至2019年，英国气象局拥有约50万个核心。这对中央控制器来说是太多了，无法实时跟踪；必须在没有完整信息的情况下分配任务。这就是*平衡分配* (BA)框架的用武之地。一种流行的协议是随机选择两个核，检查它们的负载并将任务分配给负载最小的核。这是计算效率高，只需要检查两个核心。它在理论上和实践中都很有效。不幸的是，经典的BA是“静态的”：任务被分配给处理器，但从未被删除。这适用于某些场景：例如，Dropbox数据存储使用这种“两种选择”协议的变体。然而，它在上面的动态计算设置中不太适用：一旦一个核心完成了一个计算任务，它就会转移到下一个任务，并且已完成的任务将从系统中删除。此外，如果核心没有准备好另一个任务，它将处于空闲状态，从而浪费资源。最小化这种可能性是经典BA框架中没有涉及的一个重要方面。进入排队理论（QT）。通常，这被用来模拟顾客的行为，比如在超市结账或电话呼叫中心排队时。客户*进入*系统，然后*退出*（被*删除）后，他们已经服务。设置是相似的：客户/任务到达并分配到一条线/核心。关键的区别在于客户在QT中被移除。传统的BA和QT观点有些不同，甚至是对立的。> QT研究*模型*客户行为。属性和特征是通过分析得到的概率系统来学习的。> BA的目的是*设计*一个智能协议来分配工作。执行分析以确定协议的工作效果如何。当然，这是一种简化：有一些QT对配置系统的研究，但它更多的是例外，而不是规则。这个提议的首要目标是将BA基于设计的观点引入QT设置，允许对“带有移除的任务分配”进行分析。任务到达的速率r < 1（比如每秒r次，缩放不重要）。-到达后，它们根据某些协议被分配到一个核心，并加入其队列。—处理器以1（平均每秒1个）的速率完成队列中的每个任务。这些动态提供了一个更现实和适用的框架，在其中设计，测试和分析协议的平衡分配任务。我们有三个主要目标。当前的BA协议可以很容易地移植到“动态”框架中。> 01：分析移植到这个动态框架的流行BA协议，获得其性能的严格界限；目前，这些只存在于静态框架中。这些BA协议针对静态设置进行了设计和优化。因此，虽然它们可以被移植，但是直接在动态框架中设计协议肯定会有很多好处。> O2：直接在动态框架中设计新的定制协议，使用QT的丰富性来开发动态。我们的框架假设每个处理器完全知道有多少作业在它那里排队，并且可以将此信息传递给中央控制器。我们放松它。> O3：分析噪声和/或延迟测量对协议的影响。

Everyday, we are surrounded by situations that depend on large-scale computations, from Artificial Intelligence, trained on enormous datasets with parallel processing, to data storage, such as Dropbox. Performing these massive, multi-core computations introduces many challenges of its own.> Imagine an old computer with a handful (8, say) of processing cores. It was feasible for the central controller to track how many tasks are assigned to each cores in real time. A new task can be allocated to the core with the smallest current load.> Now imagine a modern set-up, with thousands of individual cores---the Met Office has one with ~500,000, as of 2019. This is far too many for the central controller to track in real time; tasks must be allocated without complete information.This is where the *balanced allocation* (BA) framework comes in. A popular protocol chooses two cores randomly, inspects their load and assign the task to the least-loaded. This is computationally efficient, only requiring inspection of two cores. It works very well, both in theory and in practice.Unfortunately, classic BA is *static*: tasks are assigned to processors, but never removed. This is appropriate for certain scenarios: eg, Dropbox data storage uses a variant of this 'two-choice' protocol. However, it is less applicable in the dynamic computing set-up above: once a core completes a computational task, it moves onto the next task and the completed task is removed from the system. Also, if the core does not have another task ready, it will be idle, wasting resources. Minimising the likelihood of this is an important aspect not covered in the classical BA framework.Enter *queueing theory* (QT). Classically, this is used to model the behaviour of customers, such as at supermarket checkout lines or telephone call centres. Customers *enter* the system, then *exit* (are *removed*) after they have been served. The set-ups are similar: customers/tasks arrive and are assigned to a line/core. The key difference is that customers are removed in QT.The traditional BA and QT viewpoints are somewhat different, even opposing.> QT research *models* customer behaviour. Properties and characteristics are learnt via analysis of the resulting probabilistic system.> The purpose of BA is to *design* a smart protocol for assigning jobs. The analysis is performed to determine how well the protocol works.This is, of course, a simplification: there is some QT research into configuring systems, but it is more the exception, rather than the rule.The overarching aim of this proposal is to take the design-based viewpoint of BA to the QT set-up, allowing analysis of "job allocation with removals".- Tasks arrive at rate r < 1 (r per second, say; the scaling is unimportant).- Upon arrival, they are assigned to a core according to some protocol, and they join its queue.- The processor completes each task in its queue at rate 1 (1 per second on average).These dynamics provide a more realistic and applicable framework in which to design, test and analyse protocols for balanced allocation of tasks. We have three primary objectives.Current BA protocols can easily be ported to the 'dynamic' framework.> O1: Analyse popular BA protocols ported to this dynamic framework, obtaining rigorous bounds on their performance; currently, these only exist in the static framework.These BA protocols were designed and optimised for the static set-up. So, whilst they can be ported, there is there is surely much to be gained by designing protocols directly in the dynamic framework.> O2: Design new, bespoke protocols directly in the dynamic framework, using the richness of QT to exploit the dynamics.Our framework has assumed that each processor knows how many jobs are queueing at it perfectly, and can communicate this to the central controller. We relax this.> O3: Analyse the effect of noisy and/or delayed measurements on protocols.