QLSA-MOEAD-integration för precis schemaläggning av uppgifter i heterogena beräkningsmiljöer

Varför smartare schemaläggning i datorer spelar roll

Från jordskalvssimuleringar till rymdteleskop, dagens vetenskap körs på stora datorsystem som blandar många typer av kretsar—traditionella CPU:er, grafikprocessorer och omkonfigurerbar hårdvara. Att avgöra vilken krets som ska köra vilken del av arbetet, och i vilken ordning, är förvånansvärt svårt och kan slösa både tid och energi om det görs dåligt. Denna artikel presenterar ett nytt sätt att orkestrera dessa komplexa arbetsbelastningar så att stora jobb blir klara snabbare, hårdvaran används mer effektivt och, i vissa fall, att energiförbrukningen minskar.

Olika kretsar, invecklade uppgifter

Moderna högpresterande datorer är ”heterogena”: de kombinerar CPU:er, GPU:er, FPGA:er och andra acceleratorer, var och en med skilda styrkor. Vetenskapliga och industriella applikationer delar ofta upp arbetet i många små uppgifter som är kopplade via databeroenden och bildar naturligt ett riktat acykliskt graf (DAG). Vissa uppgifter måste vara färdiga innan andra kan starta, och uppgifter kan gå snabbare eller långsammare beroende på vilken krets de hamnar på. Utmaningen är att tilldela hundratals inbördes beroende uppgifter till en blandning av processorer så att total avslutningstid blir kort, maskinerna hålls sysselsatta snarare än lediga, och för vissa arbetsflöden hålls energianvändningen under kontroll. Matematiskt är detta ett NP‑hårt problem, vilket betyder att brute‑force-sökning är ogenomförbar för realistiska system.

Varför äldre metoder inte räcker

Traditionella schemaläggningsmetoder antar ofta en stabil miljö och fokuserar på ett enda mål, till exempel att minimera avslutningstid. Välkända heuristiker som HEFT ordnar uppgifter efter prioritet, medan metaheuristiker som simulerad glödgning eller tabu‑sökning utforskar rymden av möjliga scheman i jakt på förbättringar. Dessa metoder kan fungera bra på mindre eller enklare system, men de börjar ofta från slumpmässiga initialscheman, anpassar sig inte när förhållanden ändras och har svårt att jonglera flera mål samtidigt—som tid, lastbalans över hårdvaran och energi. Nyligen framväxande schemaläggare baserade på maskininlärning tillför visst anpassningsförmåga, men kräver vanligtvis stora träningsdata och saknar fortfarande ett principfast sätt att producera en komplett uppsättning lösningar som visar avvägningar mellan flera mål.

En hybridinlärare som planerar och förfinar

Författarna föreslår QLSA‑MOEAD, en hybridramverk som förenar tre idéer: Q‑inlärning, simulerad glödgning och en multiobjektiv evolutionär teknik kallad MOEA/D. Först tränas en Q‑inlärningsagent för att bygga ordningar av uppgifter genom trial‑and‑error. Den konstruerar upprepade gånger scheman, observerar hur lång tid de tar att slutföra och uppdaterar en tabell med ”Q‑värden” som fångar vilka val som tenderar att leda till bättre utfall. Istället för att förlita sig på fasta regler lär sig agenten gradvis goda mönster för att kartlägga uppgifter till processorer, inklusive hur den ska reagera när nya uppgifter dyker upp under körning. Med denna inlärda policy genererar systemet ett starkt initialt schema istället för ett slumpmässigt, vilket ger optimeringsprocessen en fördel från start.

Finjustering och avvägning av konkurrerande mål

Därefter finjusterar simulerad glödgning det inlärda schemat genom att byta plats på uppgiftsparet och ibland acceptera sämre alternativ för att ta sig ur lokala återvändsgränder, ungefär som att skaka ett pussel för att hitta en bättre placering. Slutligen behandlar MOEA/D schemaläggningsproblemet som riktigt multiobjektivt. Istället för att slå ihop alla mål till ett enda mått, delar det upp problemet i många delproblem, var och en som representerar en annan avvägning mellan att bli färdig snabbt och att hålla processorerna jämnt belastade—och för ett seismiskt riskarbetsflöde kallat CyberShake, även att sänka energianvändningen. En evolutionär process utforskar dessa avvägningar parallellt och utbyter information mellan närliggande delproblem för att producera en mångsidig Pareto‑front av scheman där förbättring av ett mål skulle försämra ett annat.

Metoden i praktiken

För att bedöma prestanda testades QLSA‑MOEAD på 20 arbetsflödesfall, inklusive syntetiska Fast Fourier Transform‑ och molekylära arbetsbelastningar, ett stort astronomiskt bildsammansättningsarbetsflöde (Montage) och verkliga CyberShake‑jordskalvssimuleringen. I 16 syntetiska fall levererade den nya metoden bästa lösningskvalitet i 14, förkortade genomförandetider och förbättrade hårdvaruanvändningen jämfört med flera avancerade baslinjer. För CyberShake, där energi också optimerades, uppnådde den två- till fyrafaldiga förbättringar i en standardiserad multiobjektiv kvalitetsmätare jämfört med tidigare state of the art, samtidigt som den bibehöll en god spridning av avvägningslösningar. I dynamiska tester där nya uppgifter anländer löpande kunde den inlärda schemaläggaren reagera på under två millisekunder och justera planerna mycket snabbare än att räkna om allt från grunden, även om det ibland skedde på bekostnad av minskad optimalitet när kommunikationsförseningarna var extrema.

Vad det betyder för vardaglig datoranvändning

För icke‑specialister är budskapet att smartare, lärande‑baserade schemaläggare kan göra stora, blandade kretsdatorer både snabbare och grönare utan ständig manuell fininställning. Genom att kombinera en erfarenhetsbaserad planerare (Q‑inlärning), en noggrann lokal sökning (simulerad glödgning) och en avvägningsutforskare (MOEA/D) hittar det föreslagna ramverket konsekvent scheman som färdigställer stora jobb snabbare, håller dyrbar hårdvara bättre använd och, för vissa applikationer, minskar energianvändningen. Det finns fortfarande begränsningar—såsom träningskostnad och prestandaförsämringar i de mest extrema situationerna—men studien visar en praktisk väg mot mer autonom och effektiv orkestrering av komplexa vetenskapliga och industriella arbetsflöden.

Citering: Saad, A., Abd el-Raouf, O., Hadhoud, M. et al. QLSA-MOEAD integration for precision task scheduling in heterogeneous computing environments. Sci Rep 16, 7194 (2026). https://doi.org/10.1038/s41598-026-36916-1

Nyckelord: uppgiftsschemaläggning, heterogen beräkning, förstärkningsinlärning, multiobjektiv optimering, energieffektiva arbetsflöden