📊 statistics

Dynamic Core Allocation for Malleable Jobs with Unknown Speed-up Parameters

Dit artikel stelt een iteratief leer-en-regelbesturingskader voor dat de maximum likelihood-schatting van onbekende versnellingsparameters combineert met op Markov-beslissingsprocessen gebaseerde beleidsupdates om kernen dynamisch toe te wijzen aan vervormbare taken en de gemiddelde responstijd op de lange termijn in een multicore-systeem te minimaliseren.

Oorspronkelijke auteurs: S. ~A. Bodas, J. ~L. Dorsman, M. Mandjes, L. Ravner

Gepubliceerd 2026-06-19

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: S. ~A. Bodas, J. ~L. Dorsman, M. Mandjes, L. Ravner

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je de manager bent van een drukke keuken met een vast aantal chefs (de cores). Elke dag komen er bestellingen binnen (de jobs). Sommige bestellingen zijn simpel, zoals het maken van een salade, terwijl andere complex zijn, zoals het bakken van een meerlaagse taart.

De grote uitdaging in jouw keuken is parallellisme: Kun je meer chefs aan één bestelling laten werken om deze sneller af te krijgen?

De Addertjes onder het gras: Het is niet altijd een perfecte 1-op-1 snelheidstoename. Als je 10 chefs hebt, ben je een taart misschien niet 10 keer sneller klaar dan met 1 chef. Misschien zijn er 5 chefs aan het snijden, maar 2 aan het wachten op de oven, en 3 staan gewoon in de weg. Dit wordt diminishing returns (afnemende meeropbrengst) genoemd.

In het verleden gingen managers ervan uit dat ze precies wisten hoe efficiënt hun chefs waren voor elke soort bestelling. Maar in de echte wereld (zoals moderne cloud computing of AI-training) verandert er veel. Hardware wordt geüpgraded, software gedraagt zich anders, en je weet eigenlijk niet de "geheime receptuur" voor hoe snel je bestellingen gaan met meer hulp.

Dit artikel presenteert een slim systeem dat dit geheime recept leert terwijl het de keuken runt.

De Twee Soorten Bestellingen

De keuken handelt twee soorten bestellingen af (Classificatie 1 en Classificatie 2).

Classificatie 1 kan een type bestelling zijn dat een enorme snelheidsboost krijgt wanneer je meer chefs toevoegt.
Classificatie 2 kan een bestelling zijn waarbij het toevoegen van meer chefs slechts een klein beetje helpt.
Het Probleem: Je kunt zien welk type bestelling zojuist is binnengekomen, maar je weet niet de specifieke "speed-up parameter" (het geheime getal dat precies vertelt hoe veel sneller het gaat met meer hulp).

De "Leer en Pas Aan"-Strategie

De auteurs stellen een cyclus voor van Leren en Handelen, zoals een chef die de soep proeft en de hitte aanpast:

De Gok (Allocatie): Je begint met een gok over hoe snel de bestellingen gaan. Je wijst je chefs toe aan de bestellingen op basis van deze gok.
De Observatie (Gegevensverzameling): Je observeert de keuken. Je merkt precies op hoe lang het duurt voordat bestellingen klaar zijn en hoeveel chefs er op elk gegeven moment aan werkten.
De Les (Schatting): Je gebruikt een wiskundig hulpmiddel genaamd Maximum Likelihood Estimation (denk aan een zeer slime detective) om naar de vertrektijden te kijken. Het vraagt: "Gezien hoe snel deze bestellingen daadwerkelijk klaar waren, wat was het meest waarschijnlijke 'geheime versnellingsgetal' voor elk type bestelling?"
De Update (Optimalisatie): Je neemt deze nieuwe, nauwkeurigere getallen en lost een complex puzzelstuk op (een Markov Decision Process) om uit te rekenen wat de perfecte manier is om je chefs tussen de twee soorten bestellingen te verdelen om de keuken het snelst te laten draaien.
Herhalen: Je runt de keuken met dit nieuwe plan, verzamelt meer gegevens, leert opnieuw, en wordt zelfs beter.

De "Gelijke Verdeling"-Regel

Binnen elk type bestelling volgt het systeem een simpele regel: Verdeel de chefs gelijkmatig.
Als je 3 bestellingen van Type 1 hebt en je besluit ze in totaal 6 chefs te geven, krijgt elke bestelling 2 chefs. Je geeft niet 5 chefs aan de één en 1 aan de ander. Het artikel bewijst dat voor dit specifieke type keuken, deze gelijke verdeling de beste manier is om het werk af te handelen zodra je weet hoe snel de bestellingen gaan. Het moeilijke deel is uitzoeken hoe snel ze gaan.

Wat de Experimenten Lieten Zien

De auteurs testten dit systeem met computer-simulaties:

Het Werkt: Het systeem slaagde erin om de verborgen "speed-up numbers" te leren nadat het de keuken een tijdje had geobserveerd.
Het "Stille" Probleem: Ze ontdekten dat als één type bestelling erg gevoelig is voor extra hulp (een luidruchtige bestelling), het makkelijk is om de snelheid ervan te leren. Maar als een ander type bestelling koppig is en niet veel van snelheid verandert, zelfs niet met meer hulp (een stille bestelling), is het veel moeilijker om het geheime getal ervan te achterhalen. Het systeem leerde het nog steeds, maar het duurde langer.
Veranderende Omstandigheden: Ze testten zelfs een scenario waarin de "geheime receptuur" halverwege de dag veranderde (zoals het installeren van een nieuwe oven). Het systeem was in staat om aan te passen en de nieuwe snelheden opnieuw te leren, waarbij het de toewijzing van de chefs on the fly aanpaste.

De Kern van het Verhaal

Dit artikel lost een probleem op waarbij je niet weet hoe goed je middelen (chefs/cores) zullen werken voor verschillende taken. In plaats van te gokken of aan te nemen dat je het antwoord weet, observeert het systeem de resultaten, berekent de waarheid en optimaliseert onmiddellijk opnieuw hoe het zijn middelen gebruikt. Het creëert een zelfverbeterende lus die de tijd minimaliseert die jobs doorbrengen in de wachtrij, waardoor jouw computer-"keuken" zo efficiënt mogelijk draait.

Technische Samenvatting: Dynamische Kernallocatie voor Malleable Jobs met Onbekende Versnellingsparameters

Probleemstelling
Dit artikel behandelt het probleem van dynamische resourceallocatie in multicore-computersystemen die een stroom van "malleable" (vormbare) jobs verwerken. In tegenstelling tot "moldable" jobs, waarbij het aantal toegewezen kernen bij aankomst vaststaat, laten malleable jobs de dynamische herverdeling van verwerkingscapaciteit tijdens de uitvoering toe. Het systeem bestaat uit een vast aantal identieke kernen ( $c$ ) en twee observeerbare jobklassen. Elke jobklasse wordt gekenmerkt door een afzonderlijke, onbekende versnellingsfunctie $s(z; p)$ , waarbij $z$ de toegewezen capaciteit is en $p$ een onbekende parameter die de mate van parallelliseerbaarheid bepaalt.

Het doel is om het gemiddelde aantal jobs in het systeem op de lange termijn te minimaliseren (gelijkwaardig aan de gemiddelde responstijd in stationaire toestand). Er bestaat een fundamentele afweging: het toewijzen van meer kernen versnelt de voltooiing van de job, maar vanwege de afnemende meeropbrengst (bijv. de Wet van Amdahl) neemt de marginale winst af naarman meer kernen worden toegewezen. Hoewel optimale beleidsregels voor dergelijke systemen bekend zijn wanneer de versnellingsparameters vaststaan en bekend zijn (specifiek het EQUI-beleid voor gelijke verdeling binnen klassen en een optimale fractie tussen klassen afgeleid via Markov-beslissingsprocessen), behandelt dit artikel het scenario waarin de parameters $p_1$ en $p_2$ onbekend zijn en geleerd moeten worden uit operationele gegevens. Deze kloof wordt gemotiveerd door moderne toepassingen zoals grootschalige machine learning-training op cloud-GPU's, waarbij de versnellingskenmerken kunnen variëren door evoluerende workloads of hardware-upgrades, wat statische aannames onrealistisch maakt.

Methodologie
De auteurs stellen een iteratief leer-en-controle-framework voor dat afwisselt tussen parameterestimatie en beleidsoptimalisatie.

Systeemmodel:
- Jobs arriveren via een Poisson-proces met snelheid $\lambda$ . De servicie-eisen zijn exponentieel verdeeld met snelheid $\mu$ .
- Jobs behoren tot Klasse 1 (waarschijnlijkheid $\alpha$ ) of Klasse 2 (waarschijnlijkheid $1-\alpha$ ).
- De versnellingsfunctie $s(z; p)$ is lineair voor $z \le 1$ en concave/niet-dalend voor $z > 1$ . Twee specifieke modellen worden overwogen: de Wet van Amdahl en een power-law model ( $s(z; p) = \max\{z, 1\}^p$ ).
- Het allocatiebeleid $\pi$ bepaalt de fractie kernen toegewezen aan Klasse 1 jobs op basis van de huidige systeemtoestand $(n^{(1)}, n^{(2)})$ . Binnen elke klasse worden de kernen gelijkmatig gedeeld (EQUI-beleid).
Parameterestimatie (Maximum Likelihood):
- De kern van het leermechanisme is een Maximum Likelihood Estimator (MLE) gebaseerd op toestand-afhankelijke intervallen tussen vertrek (inter-departure times).
- Het vertrekproces voor elke klasse wordt gemodelleerd als een toestand-afhankelijk Poisson-proces. De instantane vertrek-snelheid $\delta^{(i)}$ hangt af van het aantal jobs $n^{(i)}$ , de toegewezen kernen $c^{(i)}$ , en de onbekende parameter $p_i$ .
- De likelihood-functie wordt geconstrueerd door inter-vertrekintervallen te ontleden in sub-intervallen waar de systeemtoestand (en dus de vertrek-snelheid) constant blijft. De log-likelihood wordt expliciet afgeleid als een functie van de geobserveerde vertrektijden en de reeks systeemtoestanden.
- De auteurs bewijzen dat onder een vast allocatiebeleid deze MLE's sterk consistent zijn (convergeren bijna zeker naar de ware parameters) naarmate het aantal geobserveerde vertrekken toeneemt. Dit bewijs rust op de regeneratieve structuur van het wachtrijsysteem en de Lipschitz-continuïteit van de versnellingsfunctie met betrekking tot $p$ .
Beleidsoptimalisatie (MDP):
- Zodra de parameters zijn geschat, wordt het optimale allocatiebeleid berekend door het Bellman-optimaliteitsvergelijking op te lossen voor een Markov-beslissingsproces (MDP).
- De toestandsruimte wordt gedefinieerd door het aantal jobs in elke klasse. De actieruimte is de fractie kernen toegewezen aan Klasse 1.
- De kostenfunctie is het totale aantal jobs in het systeem. De MDP wordt opgelost met waarde-iteratie (value iteration) na het uniformiseren van het continue-tijd proces naar een discrete-tijd equivalent.
Leeralgoritmen:
Het artikel stelt twee specifieke algoritmen voor die deze lus implementeren:
- Algoritme 1a: Gebruikt alleen gegevens verzameld tijdens het meest recente observatievenster (gedefinieerd door een vast aantal vertrek-events $N_k$ ) om schattingen bij te werken. Dit maakt aanpassing mogelijk aan niet-stationaire omgevingen waar parameters in de tijd kunnen veranderen.
- Algoritme 1b: Gebruikt alle geaccumuleerde gegevens sinds tijd $t=0$ om schattingen bij te werken. Hoewel dit doorgaans snellere convergentie en hogere nauwkeurigheid oplevert in stationaire settings, is het minder aanpasbaar aan veranderende parameters.

Belangrijkste Bijdragen

Uitbreiding van Malleable Job Modellen: Het artikel breidt klassieke modellen voor de allocatie van malleable-job kernen uit door een leermechanisme voor onbekende versnellingsparameters te introduceren, waarmee het verder gaat dan de aanname van a priori kennis.
Statistische Inferentie in Wachtrijsystemen: Het ontwikkelt een specifieke MLE-procedure voor het schatten van parallelliseringskenmerken met behulp van toestand-afhankelijke inter-vertrekintervallen, en bewijst de sterke consistentie onder vaste beleidsregels.
Geïntegreerd Leerframework: Het stelt en analyseert twee iteratieve algoritmen (1a en 1b) die statistische schatting combineren met dynamische programmering-gebaseerde beleidsupdates.
Numerieke Validatie: Door middel van uitgebreide numerieke experimenten demonstreert het artikel dat de voorgestelde methoden nauwkeurige parameter-schattingen en bijna-optimale systeemprestaties bereiken na relatief korte observatieperioden. Het benadrukt ook een "quasi-identificeerbaarheid"-probleem waarbij het schatten van parameters voor jobs met lage parallelliseerbaarheid (lage $p$ ) moeilijker is dan voor zeer paralleliseerbare jobs.

Resultaten

Convergentie: Numerieke experimenten bevestigen dat de estimators convergeren naar de ware parameters. Algoritme 1b convergeert over het algemeen sneller dan 1a in stationaire settings vanwege het gebruik van de volledige gegevensgeschiedenis.
Aanpasbaarheid: In een niet-stationair experiment waarbij de versnellingsparameters op specifieke tijdstippen veranderen, slaagt Algoritme 1a erin de evoluerende parameters te volgen en het allocatiebeleid dienovereenkomstig aan te passen, wat het nut in dynamische omgevingen aantoont.
Prestaties: De geleerde beleidsregels bereiken gemiddelde responstijden die dicht bij het theoretische optimum liggen dat zou worden bereikt als de ware parameters vanaf het begin bekend waren.
Asymmetrie in Schatting: De resultaten wijzen erop dat het schatten van de parameter voor de klasse met lagere parallelliseerbaarheid (kleinere $p$ ) inherent uitdagender is en langzamer convergeert dan voor de klasse met hogere parallelliseerbaarheid, vanwege de zwakkere gevoeligheid van de versnellingsfunctie voor veranderingen in kernallocatie in dat regime.

Betekenis
Het artikel claimt significant te zijn door een kritische kloof in de literatuur aan te pakken: de aanname dat versnellingsfuncties bekend en statisch zijn. Door een framework te bieden om deze parameters online te leren, biedt het werk een praktische oplossing voor moderne, dynamische computing-omgevingen (zoals cloud-gebaseerde AI-training) waar de efficiëntie van resources cruciaal is maar systeemkenmerken onzeker zijn. De auteurs merken op dat hoewel het framework zich natuurlijk uitbreidt naar meer dan twee jobklassen, de computationele complexiteit van het oplossen van de bijbehorende Bellman-vergelijkingen aanzienlijk toeneemt, wat een afweging benadrukt tussen modelexpressiviteit en traceerbaarheid. Het werk legt de basis voor toekomstig onderzoek naar niet-stationaire settings, algemene servicetijdverdelingen en schaalbare benaderingsmethoden voor hoog-dimensionale systemen.