Beskyttelse af væsentlige forbindelser i en sammenfiltret bane

Det er vinter. Og som enhver hyppig rejsende ved, vinter kan betyde forsinkelser i lufthavnen. En snestorm i Minneapolis, en stor lufthavnshub, kan hurtigt føre til forsinkelser i lune Miami eller tåget London.

For at minimere forstyrrelser, flyvekontrolanalytikere arbejder på at prioritere genopretningsindsatsen. Men med så mange variabler, det er svært for dem at komme med sikre anbefalinger. Men dette er bare den slags datadrevne problem, som en computer kan programmeres til at løse. Spørgsmålet er tid. De nuværende metoder er ikke hurtige nok til at levere løsninger i realtid.

Nu, et forskerhold ledet af computerforskere på PNNL har udviklet et nyt grafværktøj, kaldet Ripples, der kan løse et komplekst grafanalyseproblem som lufthavnsforstyrrelsesanalyse på mindre end et minut på en supercomputer. Det bedste sammenlignelige værktøj kan tage en hel dag på en almindelig computer for at løse det samme problem. En dag, computermilepælen kan gøre analyse af netværkseffekter som lufttrafikforstyrrelser tilgængelig for beslutningstagere i realtid.

"Vores tilgang udnytter en streng social netværksanalysemetodologi, formelt kendt som indflydelsesmaksimeringsproblemet, og skalerer den til at køre på højeffektive parallelle computerplatforme, " sagde Arun Sathanur, en PNNL -datalog, der ledede lufthavnsmodelleringsarbejdet. "Disse modeller udmærker sig ved at finde indflydelsesrige enheder, analysere virkningen af ​​forbindelse, og påpege, hvor forstyrrelser har den største kaskadeeffekt."

Forskerholdet, som også omfatter forskere fra Northeastern University og Department of Transportation's Volpe National Transportation Systems Center, præsenterede deres lufthavnsnetværksanalyse på IEEE International Symposium on Technologies for Homeland Security i november 2019.

Ved at bruge offentligt tilgængelige data leveret af Department of Transportation's Federal Aviation Administration, de grupperede lufthavne i klynger af indflydelse og viste, hvilke lufthavne der er de mest indflydelsesrige, samt hvordan den vigtigste "influencer"-liste ændrer sig i løbet af kalenderåret.

Resultaterne giver et proof-of-princip, som i sidste ende kunne bruges til at håndtere forstyrrelser i lufthavnsnetværket, Tilføjede Sathanur.

"Ripples giver et kraftfuldt værktøj til proaktiv strategisk planlægning og operationer, og har bred anvendelighed på tværs af netværkede transportinfrastruktursystemer, " sagde Sam Chatterjee, en operationsforsker ved PNNL og hovedefterforsker for lufthavnsmodelleringsarbejdet ledet af Sathanur.

Den ultimative logistik

I en stadig mere overbelastet verden, at være i stand til hurtigt at genoprette service efter utilsigtede systemfejl eller cybersikkerhedsbrud ville være en stor fordel. Dette er netværksanalysens område, som først blev udviklet for at forstå, hvordan mennesker i sociale netværk er forbundet med hinanden. I stigende grad, netværksanalyse og visuel analyse bliver brugt til at gøre ting som at opdage uautoriseret adgang til computernetværk, opdage forhold mellem proteiner i kræftsvulster, og løse trængselsdilemmaer i forbindelse med transport som f.eks.

Imidlertid, for at analyseresultaterne er troværdige, der skal udføres en række beregninger for at beregne indflydelsesspredningen. Dette viser sig at være et regnemæssigt svært problem, sagde Mahantesh Halappanavar, seniorforsker ved PNNL og hovedforsker af ExaGraph, et applikations-co-designcenter finansieret af Department of Energy's (DOE's) Exascale Computing Project.

"For mange scenarier i den virkelige verden, det er ikke altid klart, hvordan man tildeler nøjagtig vægt til styrken af ​​forbindelser mellem individuelle enheder i netværket, sagde han. Vi, derfor, gentag simuleringer med flere indstillinger for at øge tilliden til computerløsninger." Selv når vægtene er velkendte, metoden er stadig afhængig af at udføre et stort antal simuleringer for at identificere indflydelsesrige enheder.

De estimerer de vigtigste influencers i enhver gruppe ved at køre disse gentagne simuleringer af en indflydelseskaskademodel, indtil de når frem til et nøjagtigt estimat. Denne tilgang er det, der gør det skræmmende at finde selv et lille sæt vigtige influencers i et moderat stort netværk, tager dage at gennemføre.

Det er derfor, at Ripples' dramatiske forbedring i speed-to-solution er så betydelig.

"Nulstilling af de mest indflydelsesrige enheder i store netværk kan hurtigt blive tidskrævende, " sagde Ananth Kalyanaraman, en medudvikler af Ripples og Boeing 100-års stol i datalogi ved School of Electrical Engineering and Computer Science, Washington State University, i Pullman. "Krusninger, og dens nyere variant cuRipples, bruger en strategi for at udnytte enorme mængder computerkraft, herunder dem i moderne grafikbehandlingsenheder for at søge den 'næste mest indflydelsesrige' enhed under sin søgning. "

Pålidelige svar

Yderligere, Ripples er baseret på den løsning, der følger med det, der kaldes en "tilnærmelsesgaranti, "som giver brugeren mulighed for at afveje kvaliteten af ​​løsningen med tiden til at beregne en løsning, samtidig med at de har evnen til at bedømme kvaliteten af ​​den beregnede løsning. De PNNL- og WSU-baserede teams arbejdede tæt sammen for at skalere Ripples-værktøjet effektivt på de hurtigste supercomputere, der administreres af DOE.

Denne strategi giver Ripples mulighed for effektivt at konvergere til en løsning af højere kvalitet, op til 790 gange hurtigere end tidligere metoder, der ikke er designet til parallelle systemer.

"Hvis vi kunne nå frem til en løsning på under et minut, vi kan begynde at bruge dette som et interaktivt værktøj, " siger Marco Minutoli hos PNNL, hovedudvikleren af ​​Ripples. "Vi kan stille og besvare nye spørgsmål i tæt på realtid."

PNNL-forskere gør allerede netop det. De er begyndt at bruge Ripples til at knuse enorme mængder data og finde de vigtigste influencers i:

• Identifikation af de vigtigste arter inden for et samfund af jordmikroorganismer, da det reagerer på ændringer i fugt;
• Sporing af spredningen af ​​infektionssygdomme og foreslå indeslutningsstrategier til at kontrollere spredningen af ​​en epidemi; og
• Identifikation af de vigtigste komponenter i luftprøver til inklusion i detaljerede klimamodeller for at studere deres indflydelse på luftforurening.

"Så vidt vi ved, dette er den første indsats for at parallelisere indflydelsesmaksimeringsoperationen i skala, " sagde Minutoli.

Forskergruppen har gjort metoden tilgængelig for forskningsmiljøet på Github. De planlægger det næste store fremskridt (cuRipples), hvilket vil være at optimere metoden på topmødet, verdens hurtigste supercomputer.