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个）处理核心。中央控制器可以实时跟踪为每个内核分配了数量的任务是可行的。可以将一项新的任务分配给当前负载最小的核心。>现在想象一个现代设置，具有成千上万个单独的核心 - 截至2019年，大都会办公室的设置约为500,000。对于中央控制器而言，这太多了，无法实时跟踪；必须在没有完整信息的情况下分配任务。这是 *平衡分配 *（BA）框架所在的地方。流行的协议随机选择两个内核，检查其负载并将任务分配给最小负载。这是计算上有效的，只需要检查两个核心。在理论上和实践中，它都非常有效。这适用于某些情况：例如，Dropbox数据存储使用此“两项选择”协议的变体。但是，它不太适用于上述动态计算设置：一旦核心完成计算任务，它就会移至下一个任务，并且已完成的任务将从系统中删除。另外，如果核心还没有准备好其他任务，它将是空闲的，浪费资源。最小化此的可能性是经典BA框架中未涵盖的重要方面。Enter *排队理论 *（QT）。从经典上讲，这用于建模客户的行为，例如在超市结帐行或电话中心。客户 *输入 *系统，然后 *exit *（被 *删除 *）。设置相似：客户/任务到达并分配到线/核心。关键区别是在QT中删除了客户。传统的BA和QT观点有些不同，甚至相反。> QT Research *模型 *客户行为。属性和特征是通过对所得概率系统的分析来学习的。> BA的目的是 *设计 *一种用于分配作业的智能协议。进行分析以确定协议的工作程度。当然，这是一个简化的：有一些QT进行配置系统的研究，但更多的是例外，而不是规则。该提案的总体目的是将基于设计的BA的观点对QT设置进行QT设置，从而使“与removals”的工作分析“。到达，根据某些协议将它们分配给核心，并加入其队列。-处理器以1（平均每秒为单位1）在其队列中完成每个任务。这些动态提供了一个更现实，更适用的框架，以设计，测试和分析任务平衡分配的协议，以进行平衡分配任务。我们有三个主要目标。电流BA协议可以轻松移植到“动态”框架中。> o1：分析流行的BA协议移植到此动态框架上，从而获得了严格的性能范围；目前，这些仅存在于静态框架中。这些BA协议是针对静态设置设计和优化的。因此，虽然可以移植它们，但直接在动态框架中设计协议肯定可以获得很多。我们放松一下。> O3：分析嘈杂和/或延迟测量对协议的影响。