Balanced Allocation Meets Queueing Theory

平衡分配与排队理论的结合

• 批准号: EP/Y032691/1
• 负责人: Sam Olesker-Taylor
• 金额: $ 10.43万
• 依托单位: University of Warwick
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FY032691%2F1
• 关键词: Balanced; Allocation; Meets; Queueing; Theory

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.

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