Hvorfor din AI ikke længere behøver skyen for at køre hurtigere

Forfattere: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Abstrakt: Deep neural network (DNN) inferens på streamingdata kræver databehandlingsressourcer for at opfylde kravene til inferens gennemløb. Latency- og privatlivsfølsomme deep learning-applikationer kan dog ikke offloade beregninger til fjerntliggende clouds på grund af de implicitte transmissionsomkostninger og manglende tillid til tredjeparts cloud-udbydere. Blandt løsninger til at øge ydeevnen, mens beregninger holdes inden for et begrænset miljø, kan hardwareacceleration være besværligt, og modeloptimering kræver omfattende designindsats, samtidig med at nøjagtigheden hæmmes. DNN-partitionering er en tredje komplementær tilgang og består i at distribuere inferensarbejdsbyrden over flere tilgængelige edge-enheder, idet der tages hensyn til edge-netværkets egenskaber og DNN-strukturen, med det formål at maksimere inferens gennemløbet (antal inferenser per sekund). Dette papir introducerer en metode til at forudsige inferens- og transmission latenser for multitrådede distribuerede DNN-implementeringer og definerer en optimeringsproces til at maksimere inferens gennemløbet. En branch and bound-løser præsenteres og analyseres derefter for at kvantificere den opnåede ydeevne og kompleksitet. Denne analyse har ført til definitionen af accelerationsregionen, som beskriver deterministiske betingelser for DNN- og netværksegenskaber, hvorunder DNN-partitionering er gavnlig. Endelig bekræfter eksperimentelle resultater simuleringerne og viser forbedringer i inferens gennemløb i eksempel-edge-implementeringer. DNN-partitionering ved kanten muliggør acceleration af inferens-gennemløbet, samtidig med at båndbreddebrug og latency til centraliserede servere, f.eks. i skyen, reduceres. Introduktion Forbundne enheder genererede anslået 2,5 quintillion bytes data hver dag i 2020. I denne sammenhæng er kunstig intelligens (AI) en af de teknologier, der bedst kan håndtere den stadigt voksende mængde producerede data inden for områder som objektgenkendelse i computer vision, ansigtsgenkendelse, talegenkendelse, naturlig sprogbehandling eller autonom kørsel. AI, og specifikt Deep Learning (DL), kræver ud over store mængder data betydelige ressourcer til processorkraft og hukommelse, hvilket gør cloud computing til den *de facto* hostingsløsning for AI-arbejdsbyrder. Følgelig blev 96% af AI-opgaverne i 2019 kørt i skyen. 1 2 AI-applikationer kan have strenge latency-begrænsninger, *f.eks.*, i autonom kørsel, produktionsmonitorering eller enhver realtidsinferens, der involverer interaktion med den virkelige verden. For eksempel kræves gennemsnitlige responstider i autonom kørsel at være under 100 millisekunder , hvilket gør rundrejsetider til skyen for lange for sådanne applikationer. Ligeledes kan visse applikationer medføre en betydelig netværksbelastning, *f.eks.*, i tilfælde af høj kvalitet videobehandling i computer vision, hvilket forhindrer dem i at køre i skyen. Databeskyttelsespolitikker eller databeskyttelsesregulativer kan også forbyde data i at forlade specifikke miljøer. Dette fremmer AI-implementeringer i edge computing, som består i at flytte beregningsopgaver fra datacentre tættere på edge-enheder, *dvs.*, i nærheden af datakilderne. [](javascript:void()) Sammenlignet med offentlige clouds er kanten et ressourcebegrænset miljø med vigtige begrænsninger , og udvikling af AI til kanten er derfor i bund og grund anderledes end udvikling af AI til skyen. Analyse af data tæt på dets kilde kan være udfordrende på grund af lavere enhedskapaciteter, uelastisk tilgængelige ressourcer og heterogenitet af edge-netværk. Reduktion af beregningskapaciteten indebærer en reduktion af den opnåelige inferens-gennemløb, hvilket yderligere komplicerer flytning af tunge arbejdsbyrder fra skyen til kanten. I nogle applikationer kan inferens-gennemløbet, *dvs.*, den opnåelige inferens per sekund af en DNN, være forbundet med DNN-nøjagtigheden, *f.eks.*, med objektsporing i videostreams, hvor en reduktion af inferenshastigheden fra 15 til 5 inferenser per sekund har vist sig at sænke F1-scoren__3__ af en objekt-detektor med 10 % . Med andre ord kan implementeringer med lavt inferens-gennemløb forårsage kritisk informationstab, *f.eks.*, tab af detektioner i videoovervågningsapplikationer. [](javascript:void()) [](javascript:void()) Der er to primære metoder til rådighed for at opfylde ydeevnekrav på begrænsede edge-netværk: modelkomprimering eller hardwareacceleration. *Modelkomprimering* består i at reducere og optimere neurale netværk til en letvægts, ofte underpræsterende, version af modellen. Standardmodelkomprimeringsmetoder inkluderer pruning , *dvs.*, fjernelse af unødvendige parametre i modellen, kvantisering , *dvs.*, reduktion af den allokerede hukommelse til lagring af modellen, og knowledge distillation , *dvs.*, træning af et mindre neuralt netværk med viden udvundet fra et større. Modeloptimering kræver omfattende designindsats og kan være en hindring for modelnøjagtighed. *Hardwareacceleration* på edge-enheder indebærer at finde hardware, der kan være både energieffektiv og letvægts, samtidig med at den stadig er i stand til at udføre inferens med tilstrækkelig ydeevne. Der findes flere typer kandidat-hardware til acceleration ved kanten, der varierer i effektivitet og specificitet, men standardprocessorenheder lever ikke op til forventningerne, og dedikeret hardware som ASICs har vist sig at være upraktisk og dyr . [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) DNN-partitionering er en komplementær metode til at accelerere inferens ved at udnytte mangfoldigheden af eksisterende enheder i edge-netværk til at distribuere inferensberegningen – som kan bruges alene eller i forbindelse med de to andre metoder. DNN-partitionering består i at betragte et neuralt netværk som en pipeline, der skal segmenteres i partitioner, og distribuere disse partitioner på edge-enheder. Placeringen af disse partitioner er baseret på både DNN og de underliggende netværkskarakteristika. DNN-partitionering hviler på identifikation af splitpunkter, som er punkter i modelgrafen, hvor modellen adskilles i partitioner. Under kørsel udføres partitioner sekventielt, hvor hver sender mellemliggende inferensresultater til den næste partition. Dette tillader hver partition at begynde at behandle den næste inputdata, mens de andre enheder fortsætter med at behandle den offloaded, hvilket derved forbedrer inferens-gennemløbet, som vist i . I resten af dette papir illustreres DNN-partitionering gennem eksemplet med realtidsinferens på videostreams. figur 1 A. Relateret arbejde Metoder til DNN-partitionering, afledt af mobil edge-cloud offloading, søger at optimere varierende ydeevneindikatorer, såsom beregningslatency, energiforbrug, ressourceudnyttelse, omkostninger eller gennemløb. DNN-partitionering hviler på associationen af et eller flere af disse metrikker til at definere et optimeringsmål og en metode, der udnytter denne metrik til at finde partitionsordninger. Neurosurgeon søger for eksempel et enkelt splitpunkt, hvor den første partition forbliver ved kanten og den anden partition offloades til skyen, for at minimere latency og energiforbrug. Applikationer i IoT har også overvejet den fælles partitionering og offloading af flere DNN'er for at optimere energi, forsinkelse og/eller omkostninger, ved hjælp af forskellige løsere som SPSO-GA der kombinerer Particle Swarm Optimization (PSO) og Genetics Algorithm (GA), eller DDPQN der bruger Deep Reinforcement Learning til at finde partitionsordninger. Andre eksempler inkluderer DINA , der definerer et Integer Non Linear Programming (INLP) problem og bruger en løser baseret på matchingsteori til at optimere forsinkelse og ressourceudnyttelse i fog-netværk. Metoder, der optimerer inferens-gennemløb, inkluderer DNN surgery , der bruger den lavere størrelse af mellemliggende DNN-lag-output til at partitionere inferensberegningen mellem kanten og skyen. Begge algoritmer skaber to partitioner, en ved kanten og den anden i skyen. Andre studier inden for mobil edge-cloud inkluderer også multitrådet beregning i skyen for yderligere at accelerere det samlede inferens-gennemløb. At stole på skyen for den anden partitions inferensberegning antager god netværksforbindelse, hvilket kan være usikkert med den dårlige forbindelse i visse isolerede edge-implementeringer. Edgent tilpasser den tidligere metodologi til mobile enheder og tilgængelige edge-servere, hvilket afslapper begrænsningen for offloading til skyen. Denne metode er knyttet til en specifik trænings- og modelarkitektur og begrænser stadig partitioneringen til to partitioner. Andre metoder har overvejet flere splitpunkter, *f.eks.*, IONN , der beskriver problemet med partitionering for at minimere latency og energiforbrug, og også tager højde for tiden til at uploade modellerne til edge-servere. [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) Disse metoder interagerer enten med fjerntliggende clouds eller er begrænset i naturen af partitioneringen, *f.eks.*, krævet at dele i præcis to dele, med eller uden multithreading. Ingen af de anførte DNN-partitioneringsstudier tager hensyn til både flere splitpunkter og multithreading. B. Bidrag Dette papir præsenterer et distribueret inferens-framework til at maksimere inferens-gennemløbet af realtids DNN-beregning på streamingdata, med flere splitpunkter og multitrådet partitionering. Bidragene fra dette papir er følgende: En model til beregnings- og transmissionslatenser af en distribueret DNN, hvorigennem det forventede inferens-gennemløb af en given partitionsordning kan estimeres. Formulering af optimeringsproblemet for DNN-partitionering, implementering af en branch and bound-løser til dette problem og evaluering af dens kompleksitet. Simuleringer til at udforske de mulige ydeevneforbedringer med varierende netværks- og DNN-egenskaber. Identifikation af deterministiske regioner i netværks- og DNN-egenskaberne, der fører til eksistensen af optimale partitioneringer og omkostningen ved at beregne sådanne løsninger, *dvs.*, betingelserne, hvorunder DNN-partitionering er gavnlig. Eksperimentelle resultater, der illustrerer de regioner, der er defineret i simuleringerne, samt forudsigelsesnøjagtigheden og den endelige inferens-gennemløbsacceleration for homogene og heterogene miljøer. I resten af dette papir vil den partitionerede deep neural network blive refereret til som *DNN*, og udtrykket *netværk* vil betegne det underliggende fysiske kommunikationsnetværk for at undgå forvirring. C. Papir-oversigt Resten af dette papir er organiseret som følger. præsenterer baggrunden for Deep Learning og hvordan DNN'er repræsenteres i denne undersøgelse. detaljerer inferens- og transmissions-latency-forudsigelsesmetoderne, der kræves til , der definerer optimeringsproblemet, samt branch and bound-algoritmen til at træffe partitionsbeslutninger. præsenterer simuleringsresultater for at kvantificere ydeevnen og kompleksiteten af branch and bound-algoritmen, samt betingelser, der fører til eksistensen af en partitionering, der forbedrer inferens-gennemløbet i et homogent netværk. præsenterer eksperimentelle resultater, der bekræfter simuleringerne i , og viser forbedringer i inferens-gennemløb i et heterogent eksperimentelt setup. Endelig diskuterer resultaterne og udvider den bredere anvendelighed af denne metode. Afsnit II Afsnit III Afsnit IV Afsnit V Afsnit VI Afsnit V afsnit VII AFSNIT II. Baggrund: Deep Learning Inden for maskinlæring refererer Deep Learning (DL) til metoder, der er baseret på brugen af DNN'er, *dvs.*, kunstige neurale netværk (eller relaterede maskinlæringsmetoder), der indeholder mere end ét skjult lag. En af de tidligste referencer til deep learning-arkitekturer blev offentliggjort i 1967 , men det var først i 2010'erne, at DL fik fart, først inden for talegenkendelse, derefter inden for objektgenkendelse i billeder, på grund af evnen til at fange komplekse relationer i højdimensionelle data. Deep Learning forventes at udgøre størstedelen af AI-applikationer i 2022, hvor mere end 75 % af organisationerne bruger DNN'er til applikationer, der kunne bruge klassiske metoder. DL-metoder er defineret som "teknikker til maskinlæring, hvor hypoteser har form af komplekse algebraiske kredsløb med justerbare forbindelsesstyrker" . Disse algebraiske kredsløb er normalt organiseret i lag, som danner trin i beregningen. Udtrykket *deep* henviser til algoritmer, der består af mere end ét lag. [](javascript:void()) 4 [](javascript:void()) Der er to primære DNN-strukturer: feed-forward neurale netværk og rekurrent neurale netværk. Begge typer DNN'er kan repræsenteres som beregningsgrafer, hvor den største forskel er, at feed-forward netværk kan repræsenteres som direkte acycliske grafer (DAG'er), mens rekurrent neurale netværk kan indeholde cyklusser. Rekurrent neurale netværk er bygget til sekvenser af data, hvor hvert datapunkt har en potentiel afhængighed af tidligere datapunkter i sekvensen, mens feed-forward neurale netværk ikke tager højde for interaktioner mellem punkter i en datasekvens. Resten af dette papir vil overveje tilfældet med feed-forward DNN'er. 5 AFSNIT III. Modellering af distribueret inferens Dette afsnit præsenterer en model til at repræsentere DNN- og netværksegenskaber for at kunne forudsige beregningslatenser, transmissionslatenser og det endelige inferens-gennemløb af en given partitionsløsning. A. DNN- og netværksrepræsentation En feed-forward DNN med N lag modelleres som en DAG GA=(L,E) med L=(L1,…,LL) som DNN'ens lag. Kanter (Li,Lj)∈E er forbindelserne mellem lagene Li og Lj . Hvert lag Li har et tilhørende beregningsforbrug ci , målt i antallet af flydende-komma-operationer, der kræves for at beregne et forward pass gennem laget. Kanter (Li,Lj) tildeles en vægt si,j , der svarer til størrelsen af data, der transmitteres mellem lagene Li og Lj i bytes. Det fysiske netværk modelleres som en fuldt forbundet graf G=(N,V) , hvor N=(N1,…,NN) er sættet af beregningsnoder, og V er sættet af forbindelser mellem noder. Det antages, at beregningsnoderne N1,…,NN har processeringshastigheder η1,…,ηN , målt i flydende-komma-operationer per sekund. Endelig betegnes link-gennemløbet mellem to tilstødende noder Na og Nb som θa,b , målt i bytes per sekund. Hver node Ni er forbundet til sig selv med uendeligt gennemløb for at repræsentere loopback-forbindelsen, og forbindelser antages at være symmetriske, *dvs.*, θa,b=θb,a . Partitioneringer defineres som maps P:L→N , *dvs.*, en partitionering tildeler et nodenummer til hvert lag i DNN'en. En partitionering kan beskrives som en matrix P af dimensionen (N×L) , hvor N er antallet af noder i netværket og L er antallet af DNN-lag, og med Pa,i=1 hvis laget Li er placeret på noden Na , ellers 0. Med eksemplet givet i , L=7 lag og N=2 beregningsnoder, repræsenteres den viste partitionering med lagene {L1,L2,L3,L6,L7} på noden N1 , og lagene {L4,L5} på noden N2 , som: figur 2 Givet en partitionering defineres en *thread* som en gruppe af fortløbende lag mellem to splitpunkter, kørt sekventielt på samme node. I eksemplet ovenfor vil noden N1 køre to threads, den første indeholdende lagene {L1,L2,L3} , og den anden {L6,L7} . Med disse definitioner udledes resten af dette afsnit en lukket udtryk for inferens-gennemløbet opnået af en given partitionering, som funktion af inferens- ( ) og transmissionslatenser ( ). afsnit III-B afsnit III-C B. Forudsigelse af inferens-latency Givet en partitionering ser dette afsnit på forudsigelse af inferens-latency på en isoleret node. Latencyet induceret af beregningen af et lag Li med forbrug ci , der skal beregnes på noden Na , med processeringshastighed ηa , udtrykkes som Tci(Na)=ci/ηa . Givet et sæt af lag L′⊂L på tværs af alle threads, der kører på noden Na med processeringshastighed ηa , kan inferens-latencyet udtrykkes som: Dette udtryk er en førsteordens approximation af en estimering af inferens-latency baseret på antallet af flydende-komma-operationer (FLOPs) krævet for at behandle DNN'en, *dvs.*, antallet af multiplikation-addition-operationer i modellen. Estimering af inferens-latency på edge-enheder kompliceres af run-time optimeringer. Eksisterende løsninger som nn-Meter forudsiger inferens-latency baseret på FLOPs. Andre løsninger er baseret på en opslagstabel med forudberegnede inferenstider til latency-forudsigelse. For eksempel bruger BRP-NAS et forudtrænet graf-konvolutionelt netværk til at forudsige inferens-latenser, samtidig med at run-time modeloptimeringer tages i betragtning. [](javascript:void()) [](javascript:void()) I antages det yderligere, at processorerne bruger deres fulde kapacitet, hvilket indebærer, at multikern-processorer modelleres som singlekern-processorer med en processeringshastighed lig med summen af deres kernprocesseringshastigheder. Det antages også, at beregningsressourcen deles ligeligt mellem threads, *dvs.*, en processor allokerer den samme andel af sin tid til hver thread. ligning 1 På tværs af alle noder sætter den thread med højest latency inferens-gennemløbet for den distribuerede DNN. Uden transmission latenser indebærer dette, at når denne begrænsende thread er færdig med at beregne en dataramme, starter den direkte på den næste. Andre threads vil have tomgangstid, før de behandler den næste dataramme, fordi deres inferens-latency er lavere end denne maksimale latency, som vist i . figur 1 Givet en partitionsmatrix P , kan inferens-latenserne udtrykkes som en enkelt vektor Tc af størrelse N , hvor den a -te komponent er den højeste thread inferens-latency på noden Na , *dvs.*, Tca=Tc(Na) : hvor H er diagonalmatricen af inverse nodeprocesseringshastigheder diag(η−11,…,η−1N) og c er kolonnevektoren af individuelle lagforbrug (c1,…,cL) . C. Forudsigelse af transmissions-latency Transmissions-latency kan forudsiges som følger: tiden det tager at sende datamængden si,j mellem lagene Li og Lj på kanten (Na,Nb) over en forbindelse med målt gennemløb θa,b er Tti,j(Na,Nb)=si,j/θa,b . Tiden til at opnå dataoverførsler si,j∈E′⊂E over forbindelsen (Na,Nb) er: Ligesom med inferens-latency-forudsigelse indebærer dette, at forbindelserne deles ligeligt mellem dataoverførsler fra Na til Nb . Transmissions-latency-forudsigelsen er baseret på estimering af link-gennemløbet mellem noder, mere præcist *goodput*, *dvs.*, den mængde nyttig data, der transmitteres per sekund. Ligesom estimering af inferens-latency er dette en førsteordens approximation, der effektivt giver gode forudsigelsesresultater, som vist i c, med en korrelationskoefficient på R2=0.9998 . Ulempen ved denne metode er, at den kræver mætning af forbindelserne for at opnå et gennemløbsestimat. figur 3 Givet en partitionsmatrix P , kan transmissions-latency-matricen Tt defineres som en kvadratisk matrix af størrelse L , med Tta,b=Tt(Na,Nb) : hvor ° er det termvise produkt, eller Hadamard-produktet, Θ er den inverse gennemløbsmatrix, *dvs.*, en kvadratisk matrix af størrelse N med Θa,b=θ−1a,b og S er transmissionsstørrelsesmatricen, *dvs.*, en kvadratisk matrix af størrelse L med Si,j=si,j hvis Li sender data til Lj , ellers 0. AFSNIT IV. DNN-partitionering Målet med DNN-partitionering i denne undersøgelse er at maksimere inferens-gennemløbet, betegnet med C , hvilket svarer til den inverse af den maksimale latency mellem alle de forskellige beregnings- og transmissionslatenser. Givet en partitionering P , defineres inferens-gennemløbet som: Maksimering af inferens-gennemløbet svarer til at finde den fælles min-max mellem alle ledene i Tc og Tt . Dette kan defineres som et diskret optimeringsproblem: med Ji,j som alle-ettaller-matricen af størrelse i×j , kræver betingelserne og , at hvert lag placeres på én og kun én node. (6) (7) Dette optimeringsproblem er et Mixed Integer Non-linear Programming (MINLP) problem. Partitionsmatricen kan ses som den one-hot-encodede version af en vektor af størrelse (1×L) med værdier i [[1,N]] . MINLP-problemer er NP-hårde, hvilket indebærer, at kompleksiteten ved at finde en optimal DNN-partitionering er O(NL) , da hvert af de L lag kan placeres på N noder. Der findes adskillige heuristikker til at opnå optimale eller suboptimale løsninger på dette problem på kortere tid end en brute-force-algoritme, *f.eks.*, Genetic Algorithms (GA) , Particle Swarm Optimization (PSO) [](javascript:void()) [](javascript:void())