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.
|