Stochastic modeling and optimization of large-scale and resource-constrained systems

QC 20261008

Abstract

Denna avhandling undersöker hur storskaliga system kan utnyttja begränsade kom\-mu\-ni\-ka\-tions-, beräknings- och observationsresurser på ett effektivt sätt under osäkerhet, ofullständig information och föränderliga förhållanden. Ett genomgående resultat är att tillförlitlig och effektiv drift inte nödvändigtvis kräver kontinuerligt uppdaterad information eller ständigt ökande kapacitet och beräkningskraft. Avgörande är i stället att identifiera systemets stokastiska struktur och använda den för att avgöra när information behövs och var resurser ger störst nytta. Mot denna bakgrund utvecklar avhandlingen stokastiska modeller, analytiska metoder och optimeringsramverk för tre problem inom edge intelligence och smart mikroskopi.

Det första bidraget behandlar lastbalansering i distribuerade beräkningssystem där användare självständigt väljer servrar utan tillgång till ett kontinuerligt uppdaterat globalt systemtillstånd. I stället bygger användarna lokala skattningar utifrån sina egna routningsbeslut och sporadiska statusuppdateringar som sänds ut av servrarna. Analysen fastställer villkor under vilka sådan decentraliserad drift förblir stabil trots gles information, kommunikationsförluster och heterogena serverkapaciteter. En högre relativ uppdateringsfrekvens minskar i allmänhet den stationära köbelastningen och för den distribuerade policyn närmare den centraliserade referensen. Vid glesa uppdateringar kan sambandet med sannolikheten att ta emot en uppdatering däremot vara icke-monotont: måttliga kommunikationsförluster skapar större variation i användarnas lokala uppskattningar och kan därmed minska synkroniserad routning baserad på inaktuella servertillstånd, medan högre mottagningssannolikhet förbättrar prestandan när den relativa uppdateringsfrekvensen är högre.

Det andra bidraget behandlar gemensam dimensionering av trådlösa resurser och beräkningsresurser i flercelliga nätverk för edge intelligence. Trådlös åtkomst, rumsligt fördelad trafik, köbildning i kantservrar och AI-inferens modelleras som ett kopplat stokastiskt system under statistiska krav på latens, täckning, serverbelastning och inferensnoggrannhet. Stokastisk geometri används för att karakterisera nätverkets rumsliga egenskaper och härleda analytiskt hanterbara uttryck för upplänkskapacitet. Dessa resultat kombineras med kömodeller och empiriskt karakteriserade inferensarbetslaster för att formulera ett end-to-end-problem för dimensionering av bandbredd och beräkningskapacitet. Analysen synliggör avvägningar som inte framträder när kommunikation och beräkning dimensioneras separat. I brusbegränsade system förbättrar tätare infrastruktur de trådlösa förhållandena, men minskar samtidigt den statistiska multiplexeringen vid servrarna och skapar därmed en motverkande beräkningskostnad. I interferensbegränsade system kan förtätning med fast frekvensåteranvändning ge liten nytta eftersom ökad interferens motverkar vinsten från kortare överföringsavstånd. Om frekvensåteranvändningen i stället anpassas till nätverkstätheten kan förtätning åter minska både kommunikations- och beräkningsbehovet.

Det tredje bidraget behandlar adaptiv observation i automatiserad mikroskopi, där många asynkront föränderliga observationsområden konkurrerar om en begränsad avbildningsbudget. De biologiska dynamikerna modelleras som stora samlingar av oberoende Markovprocesser, för vilka exakta och asymptotiska karakteriseringar möjliggör en skalbar beskrivning av den aggregerade tidsutvecklingen. Med denna struktur som grund formuleras observationsproblemet som ett restless multi-process multi-armed bandit-problem under partiell observerbarhet, och en beräkningsmässigt effektiv Whittle-indexpolicy härleds. Numeriska resultat visar att policyn är särskilt effektiv när temporal persistens gör tidigare observationer informativa om framtida aktivitet. Experiment på biologiska mikroskopidata visar dessutom att den föreslagna policyn fångar 93% fler biologiskt relevanta händelser än fast cyklisk skanning.

Sammantaget visar bidragen att tillförlitlig drift i resursbegränsade stokastiska system inte nödvändigtvis kräver fullständig information, kontinuerlig koordinering eller ständigt utbyggd infrastruktur. Det centrala är i stället att identifiera vilka aspekter av osäkerhet och systemhistorik som är relevanta för beslutsfattandet och att fördela resurser för kommunikation, beräkning och observation därefter. Avhandlingen utvecklar analytiska och algoritmiska verktyg för att avgöra när information är tillräcklig för distribuerad koordinering, hur kommunikations- och beräkningsresurser bör dimensioneras gemensamt och hur knappa observationsresurser kan riktas mot de mest informativa delarna av ett dynamiskt system. På ett övergripande plan visar resultaten hur identifiering och utnyttjande av stokastisk struktur kan omvandla osäkerhet från ett hinder till en källa till användbar information och därigenom möjliggöra mer effektiva och välgrundade beslut även när resurserna är fundamentalt begränsade.

Link to DiVA