Proč vaše AI už nepotřebuje cloud, aby běžela rychleji

Autoři: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Abstrakt: Hluboké neuronové sítě (DNN) pro zpracování proudových dat vyžadují výpočetní zdroje pro splnění požadavků na propustnost inference. Latencí a soukromím citlivé aplikace hlubokého učení si však nemohou dovolit offloadovat výpočty do vzdálených cloudů kvůli implikovaným nákladům na přenos a nedostatku důvěry ve třetí strany poskytující cloudové služby. Mezi řešeními pro zvýšení výkonu při zachování výpočtů v omezeném prostředí jsou hardwarová akcelerace nákladná a optimalizace modelu vyžaduje rozsáhlé návrhové úsilí a zároveň snižuje přesnost. Třetím doplňkovým přístupem je rozdělení DNN, které spočívá v distribuci zátěže inference mezi několik dostupných okrajových zařízení, s ohledem na vlastnosti okrajové sítě a strukturu DNN, s cílem maximalizovat propustnost inference (počet inferencí za sekundu). Tento článek představuje metodu pro predikci latencí inference a přenosu pro distribuované DNN nasazení s více vlákny a definuje optimalizační proces pro maximalizaci propustnosti inference. Poté je prezentován a analyzován řešitel větvení a mezí (branch and bound) pro kvantifikaci dosaženého výkonu a složitosti. Tato analýza vedla k definici oblasti akcelerace, která popisuje deterministické podmínky týkající se vlastností DNN a sítě, za kterých je rozdělení DNN přínosné. Konečně, experimentální výsledky potvrzují simulace a ukazují zlepšení propustnosti inference ve vzorových okrajových nasazeních. Rozdělení DNN na okraji umožňuje akceleraci propustnosti inference při současném snížení využití šířky pásma a latence k centralizovaným serverům, např. v cloudu. Úvod Připojená zařízení vygenerovala v roce 2020 odhadem 2,5 quintilionů bajtů dat denně. V tomto kontextu je umělá inteligence (AI) jednou z technologií, která si nejlépe poradí s neustále rostoucím množstvím produkovaných dat, a to v celé řadě oblastí, jako je detekce objektů ve vizuálním rozpoznávání, rozpoznávání obličejů, rozpoznávání řeči, zpracování přirozeného jazyka nebo autonomní řízení. AI, a zejména hluboké učení (DL), vyžaduje kromě velkého množství dat také značné schopnosti ve zpracovatelském výkonu a paměti, což činí cloud computing de facto hostitelským řešením pro zátěže AI. V důsledku toho bylo v roce 2019 96 % úloh AI spuštěno v cloudu. Aplikace AI mohou mít silná latencí omezení, např. při autonomním řízení, monitorování výroby nebo jakékoli inferenci v reálném čase zahrnující interakci s reálným světem. Například průměrné reakční časy u autonomního řízení musí být kratší než 100 milisekund, což činí obousměrné cesty do cloudu pro tyto aplikace příliš dlouhé. Podobně některé aplikace mohou představovat významné využití linky v síti, např. v případě zpracování videa ve vysoké kvalitě ve vizuálním rozpoznávání, což brání jejich spuštění v cloudu. Zásady ochrany soukromí dat nebo předpisy o ochraně dat mohou také zakazovat opuštění dat určených prostředí. To podporuje nasazení AI v edge computingu, který spočívá v přesunu výpočetních úloh z datových center blíže k okrajovým zařízením, tj. do blízkosti zdrojů dat. Ve srovnání s veřejnými cloudy je okraj omezeným prostředím s významnými omezeními a vývoj AI pro okraj se proto zásadně liší od vývoje AI pro cloud. Analýza dat v blízkosti jejich zdroje může být náročná kvůli nižším kapacitám zařízení, neelasticitě dostupných zdrojů a heterogenitě okrajových sítí. Snížení výpočetní kapacity znamená snížení dosažitelné propustnosti inference, což dále komplikuje přesun náročných zátěží z cloudu na okraj. V některých aplikacích může být propustnost inference, tj. dosažitelné inference za sekundu DNN, spojena s přesností DNN, např. u sledování objektů ve video proudech, kde snížení rychlosti inference z 15 na 5 inferencí za sekundu snížilo F1 skóre detektoru objektů o 10 %. Jinými slovy, nasazení s nízkou propustností inference mohou způsobit kritickou ztrátu informací, např. ztrátu detekcí v aplikacích pro video dohled. Existují dvě hlavní dostupné metody pro splnění požadavků na výkon v omezených okrajových sítích: komprese modelu nebo hardwarová akcelerace. Komprese modelu spočívá ve zmenšení a optimalizaci neuronových sítí na odlehčenou, často méně výkonnou, verzi modelu. Standardní metody komprese modelu zahrnují prořezávání, tj. odstranění nepotřebných parametrů v modelu, kvantizaci, tj. snížení alokované paměti pro uložení modelu, a destilaci znalostí, tj. trénování menší neuronové sítě se znalostmi extrahovanými z větší. Optimalizace modelu vyžaduje rozsáhlé návrhové úsilí a může být překážkou pro přesnost modelu. Hardwarová akcelerace na okrajových zařízeních znamená nalezení hardwaru, který může být jak energeticky účinný a lehký, tak stále schopen provádět inferenci s dostatečným výkonem. Existuje několik typů hardwaru pro akceleraci na okraji, lišících se účinností a specifičností, ale standardní zpracovatelské jednotky nesplňují očekávání a dedikovaný hardware, jako jsou ASIC, se ukázal jako nepraktický a drahý. Rozdělení DNN je doplňková metoda pro akceleraci inference tím, že využívá multiplicity existujících zařízení v okrajových sítích k distribuci výpočtu inference – která může být použita samostatně nebo v kombinaci s ostatními dvěma metodami. Rozdělení DNN spočívá v považování neuronové sítě za pipeline pro segmentaci na části a distribuci těchto částí na okrajová zařízení. Umístění těchto částí je založeno na charakteristikách DNN i podkladové sítě. Rozdělení DNN závisí na identifikaci bodů rozdělení, což jsou místa v grafu modelu, kde je model rozdělen na části. Během běhu se části provádějí sekvenčně a každá odesílá mezilehlé výsledky inference do další části. To umožňuje každé části začít zpracovávat další vstupní data, zatímco ostatní zařízení pokračují ve zpracování offloadovaného datového proudu, čímž se zlepšuje propustnost inference, jak je znázorněno na obrázku 1. Ve zbytku tohoto článku je rozdělení DNN ilustrováno na příkladu inference v reálném čase na video proudech. A. Související práce Metody pro rozdělení DNN, odvozené z offloadingu z mobilního okraje do cloudu, se snaží optimalizovat různé ukazatele výkonu, jako je latence výpočtu, spotřeba energie, využití zdrojů, náklady nebo propustnost. Rozdělení DNN závisí na přiřazení jednoho nebo více z těchto metrik k definování optimalizačního cíle a metody, která tuto metriku využívá k nalezení schémat rozdělení. Například Neurosurgeon hledá jediný bod rozdělení, přičemž první část zůstává na okraji a druhá část je offloadována do cloudu, aby se minimalizovala latence a spotřeba energie. Aplikace v IoT také zvažovaly společné rozdělení a offloading několika DNN pro optimalizaci energie, zpoždění a/nebo nákladů pomocí různých řešitelů, jako je SPSO-GA kombinující částicovou optimalizaci (PSO) a genetický algoritmus (GA), nebo DDPQN, který využívá hluboké posilované učení k nalezení schémat rozdělení. Mezi další příklady patří DINA, která definuje celočíselný nelineární programovací (INLP) problém a používá řešitel založený na teorii párování k optimalizaci zpoždění a využití zdrojů v mlhových sítích. Metody optimalizující propustnost inference zahrnují DNN surgery, která využívá nižší velikost mezilehlých výstupů vrstev DNN k rozdělení výpočtu inference mezi okraj a cloud. Oba algoritmy vytvářejí dvě části, jednu na okraji a druhou v cloudu. Další studie v oblasti mobilního okraje-cloudu také zahrnují vícevláknové výpočty v cloudu pro další zrychlení celkové propustnosti inference. Spoléhání se na cloud pro výpočet inference druhé části předpokládá dobré síťové připojení, které může být nejisté s horším připojením některých izolovaných okrajových nasazení. Edgent přizpůsobuje předchozí metodologii mobilním zařízením a dostupným okrajovým serverům, čímž uvolňuje omezení offloadingu do cloudu. Tato metoda je spojena s konkrétním tréninkem a architekturou modelu a stále omezuje dělení na dvě části. Další metody zvažovaly více bodů rozdělení, např. IONN, která popisuje problém rozdělení pro minimalizaci latence a spotřeby energie, přičemž bere v úvahu také čas potřebný k nahrání modelů na okrajové servery. Tyto metody buď interagují se vzdálenými cloudy, nebo jsou omezeny povahou rozdělení, např. vyžadují rozdělení na přesně dva díly, s vícevláknovým zpracováním nebo bez něj. Žádná ze zmíněných studií rozdělení DNN nebere v úvahu více bodů rozdělení a vícevláknové zpracování současně. B. Příspěvky Tento článek představuje distribuovaný rámec pro inferenci za účelem maximalizace propustnosti inference reálného času DNN výpočtů na proudových datech s více body rozdělení a vícevláknovým dělením. Příspěvky tohoto článku jsou následující: Model pro predikci latencí výpočtu a přenosu distribuované DNN, pomocí kterého lze odhadnout očekávanou propustnost inference daného schématu dělení. Formulace optimalizačního problému pro dělení DNN, implementace řešitele větvení a mezí pro tento problém a vyhodnocení jeho složitosti. Simulace pro prozkoumání možných zlepšení výkonu s různými vlastnostmi sítě a DNN. Identifikace deterministických oblastí ve vlastnostech sítě a DNN vedoucích k existenci optimálních rozdělení a nákladů na výpočet takových řešení, tj. podmínek, za kterých je rozdělení DNN přínosné. Experimentální výsledky ilustrující oblasti definované v simulacích, jakož i přesnost predikce a konečné zrychlení propustnosti inference pro homogenní a heterogenní prostředí. Pro zbytek tohoto článku, abychom se vyhnuli nedorozuměním, bude dělená hluboká neuronová síť označována jako DNN a termín síť bude označovat podkladovou fyzickou komunikační síť. C. Osnova článku Zbytek tohoto článku je organizován následovně. Kapitola II představuje pozadí hlubokého učení a jak jsou DNN v této studii reprezentovány. Kapitola III podrobně popisuje metody predikce latence inference a přenosu potřebné pro Kapitolu IV, která definuje optimalizační problém, a také algoritmus větvení a mezí pro rozhodování o rozdělení. Kapitola V představuje výsledky simulací pro kvantifikaci výkonu a složitosti algoritmu větvení a mezí, jakož i podmínky vedoucí k existenci rozdělení, které zlepšuje propustnost inference v homogenní síti. Kapitola VI představuje experimentální výsledky potvrzující simulace z Kapitoly V a ukazuje zlepšení propustnosti inference na heterogenním experimentálním nastavení. Konečně Kapitola VII diskutuje výsledky a rozšiřuje se o širší použitelnost této metody. KAPITOLA II. Pozadí: Hluboké učení V rámci strojového učení se hluboké učení (DL) vztahuje na metody založené na použití DNN, tj. umělých neuronových sítí (nebo souvisejících metod strojového učení) obsahujících více než jednu skrytou vrstvu. Jedna z nejstarších referencí na architektury hlubokého učení byla publikována v roce 1967, ale teprve v roce 2010 získalo DL trakci, nejprve v rozpoznávání řeči, pak v detekci objektů na obrázcích, díky schopnosti zachytit složité vztahy ve vysoce dimenzionálních datech. Odhaduje se, že hluboké učení představuje většinu aplikací AI v roce 2022, přičemž více než 75 % organizací používá DNN pro aplikace, které by mohly využívat klasické metody. Metody hlubokého učení byly definovány jako "techniky pro strojové učení, kde hypotézy mají formu složitých algebraických obvodů s laditelnými silami spojení". Tyto algebraické obvody jsou obvykle organizovány do vrstev, které tvoří kroky ve výpočtu. Termín "hluboké" se vztahuje k algoritmům skládajícím se z více než jedné vrstvy. Existují dva hlavní typy struktur DNN: dopředné neuronové sítě a rekurentní neuronové sítě. Oba typy DNN lze reprezentovat jako výpočetní grafy, přičemž hlavním rozdílem je, že dopředné sítě lze reprezentovat jako přímé acyklické grafy (DAG), zatímco rekurentní neuronové sítě mohou obsahovat cykly. Rekurentní neuronové sítě jsou stavěny pro sekvence dat, kde každý datový bod má potenciální závislost na předchozích datových bodech v sekvenci, zatímco dopředné neuronové sítě neberou v úvahu interakce mezi body v datové sekvenci. Ve zbytku tohoto článku se budeme zabývat případem dopředných DNN. KAPITOLA III. Modelování distribuované inference Tato kapitola představuje model pro reprezentaci vlastností DNN a sítě za účelem predikce latencí výpočtu, latencí přenosu a konečné propustnosti inference daného řešení pro rozdělení. A. Reprezentace DNN a sítě Dopředná DNN s N vrstvami je modelována jako DAG GA=(L,E), kde L=(L1,…,LL) jsou vrstvy DNN. Hrany (Li,Lj)∈E jsou spojení mezi vrstvami Li a Lj. Každá vrstva Li má přidruženou spotřebu výpočtu ci, měřenou v počtu operací s plovoucí čárkou potřebných k výpočtu dopředného průchodu vrstvou. Hrany (Li,Lj) mají přiřazenou váhu si,j odpovídající velikosti dat přenášených mezi vrstvami Li a Lj v bajtech. Fyzická síť je modelována jako plně propojený graf G=(N,V), kde N=(N1,…,NN) je množina výpočetních uzlů a V je množina spojení mezi uzly. Předpokládá se, že výpočetní uzly N1,…,NN mají rychlosti zpracování η1,…,ηN, měřené v operacích s plovoucí čárkou za sekundu. Nakonec je propustnost spojení mezi dvěma sousedními uzly Na a Nb označena jako θa,b, měřená v bajtech za sekundu. Každý uzel Ni je spojen sám se sebou s nekonečnou propustností, aby se reprezentoval zpětný kanál, a předpokládá se, že spojení jsou symetrická, tj. θa,b=θb,a. Rozdělení jsou definována jako mapy P:L→N, tj. rozdělení přiřazuje číslo uzlu každé vrstvě v DNN. Rozdělení lze popsat maticí P o rozměrech (N×L), kde N je počet uzlů v síti a L je počet vrstev DNN, a P a,i=1, pokud vrstva Li je umístěna na uzlu Na, 0 jinak. S příkladem uvedeným na obrázku 2, L=7 vrstev a N=2 výpočetních uzlů, zobrazené rozdělení s vrstvami {L1,L2,L3,L6,L7} na uzlu N1 a vrstvami {L4,L5} na uzlu N2, je reprezentováno jako: Vzhledem k rozdělení je "vlákno" definováno jako skupina po sobě jdoucích vrstev mezi dvěma body rozdělení, prováděná sekvenčně na stejném uzlu. V příkladu výše uzel N1 spustí dvě vlákna, první obsahující vrstvy {L1,L2,L3} a druhé obsahující {L6,L7}. S definovanými těmitoNotacemi, zbytek této kapitoly odvozuje uzavřený výraz pro propustnost inference dosaženou daným rozdělením, jako funkci latencí inference (Kapitola III-B) a přenosu (Kapitola III-C). B. Predikce latence inference Pro dané rozdělení se tato podkapitola zabývá predikcí latence inference na izolovaném uzlu. Latence indukovaná výpočtem vrstvy Li se spotřebou ci, která má být vypočítána na uzlu Na, s rychlostí zpracování ηa, je vyjádřena jako Tci(Na)=ci/ηa. Pro danou sadu vrstev L'⊂L napříč všemi vlákny běžícími na uzlu Na s rychlostí zpracování ηa, lze latenci inference vyjádřit jako: Tento výraz je aproximace prvního řádu pro odhad latence inference založený na počtu operací s plovoucí čárkou (FLOPs) potřebných ke zpracování DNN, tj. počtu násobně-aditivních operací v modelu. Odhad latence inference na okrajových zařízeních je komplikován optimalizacemi za běhu. Existující řešení, jako je nn-Meter, předpovídají latenci inference na základě FLOPs. Jiná řešení se spoléhají na vyhledávací tabulku s předem vypočítanými časy inference pro predikci latence. Například BRP-NAS používá předtrénovanou grafovou konvoluční síť k predikci latencí inference, přičemž bere v úvahu optimalizace modelu za běhu. V rovnici 1 se dále předpokládá, že procesory využívají svou plnou kapacitu, což znamená, že vícejádrové procesory jsou modelovány jako jednojádrové procesory s rychlostí zpracování rovnou součtu rychlostí zpracování jejich jader. Předpokládá se také, že výpočetní zdroj je rovnoměrně sdílen mezi vlákny, tj. procesor přiděluje stejný podíl svého času každému vláknu. Napříč všemi uzly vlákno s nejvyšší latencí určuje propustnost inference pro distribuovanou DNN. Bez započítání latencí přenosu to znamená, že jakmile je toto limitující vlákno hotové s výpočtem datového rámce, začne přímo zpracovávat další. Jiná vlákna budou mít nečinný čas před zpracováním dalšího datového rámce, protože jejich latence inference je nižší než tato maximální latence, jak je znázorněno na obrázku 1. Pro danou matici rozdělení P lze latence inference vyjádřit jako jeden vektor Tc o velikosti N, kde a-tá složka je nejvyšší latence vlákna na uzlu Na, tj. Tca=Tc(Na): kde H je diagonální matice inverzních rychlostí zpracování uzlů diag(η−11,…,η−1N) a c je sloupcový vektor individuálních spotřeb výpočtu vrstev (c1,…,cL). C. Predikce latence přenosu Latenci přenosu lze předpovědět následovně: čas potřebný k odeslání množství dat si,j mezi vrstvami Li a Lj na hraně (Na,Nb) přes spojení s naměřenou propustností θa,b je Tti,j(Na,Nb)=si,j/θa,b. Čas pro dosažení přenosů dat si,j∈E′⊂E přes spojení (Na,Nb) je: Podobně jako při predikci latence inference, to znamená, že spojení jsou rovnoměrně sdílena mezi přenosy dat z Na do Nb. Predikce latence přenosu závisí na odhadu propustnosti spojení mezi uzly, přesněji na "goodputu", tj. množství užitečných dat přenášených za sekundu. Podobně jako u odhadu latence inference, jde o aproximaci prvního řádu, která efektivně poskytuje dobré výsledky predikce, jak je vidět na obrázku 3c, s korelačním koeficientem R²=0,9998. Nevýhodou této metody je její požadavek na nasycení spojení pro získání odhadu propustnosti. Pro danou matici rozdělení P lze matici latence přenosu Tt definovat jako čtvercovou matici o velikosti L, s Tta,b=Tt(Na,Nb): kde ° je součin po prvcích, neboli Hadamardův součin, Θ je matice inverzní propustnosti, tj. čtvercová matice o velikosti N s Θa,b=θ−1a,b a S je matice velikosti přenosu, tj. čtvercová matice o velikosti L se Si,j=si,j, pokud Li posílá data do Lj, 0 jinak. KAPITOLA IV. Rozdělení DNN Cílem rozdělení DNN v této studii je maximalizovat propustnost inference, označenou C, která odpovídá inverzi maximální latence mezi všemi různými výpočty a přenosy. Pro dané rozdělení P je propustnost inference definována jako: Maximalizace propustnosti inference se rovná nalezení společného minimaxu mezi všemi členy Tc a Tt. To lze definovat jako diskrétní optimalizační problém: s Ji,j being the all-ones matrix of size i×j, podmínky (6) a (7) vyžadují, aby každá vrstva byla umístěna na jeden a pouze jeden uzel. Tento optimalizační problém je problémem smíšeného celočíselného nelineárního programování (MINLP). Matice rozdělení lze považovat za jednohotově kódovanou verzi vektoru o velikosti (1×L) s hodnotami v [[1,N]]. Problémy MINLP jsou NP-těžké, což znamená, že složitost nalezení optimálního rozdělení DNN je O(NL), protože každá z L vrstev může být umístěna na N uzlů. Existuje několik heuristik pro získání optimálních nebo suboptimálních řešení tohoto problému v kratším čase než hrubá síla algoritmu, např. genetické algoritmy (GA), částicová optimalizace (PSO) nebo větvení a meze (B&B). Zvolenou metodologií je adaptovaná implementace B&B, která je prezentována v Kapitole IV-A. A. Algoritmus větvení a mezí Tato podkapitola představuje adaptaci větvení a mezí (B&B) na problém optimalizace rozdělení DNN definovaný v Kapitole IV. V algoritmech B&B je prostor řešení reprezentován stromem. Proces spočívá v eliminaci celých větví ve stromě na základě vyhodnocení skóre kořenového uzlu. To znamená existenci topologie stromu, která vytváří vztah mezi skóre uzlu ve stromě a mezemi na skóre všech jeho listů. Tato stromová reprezentace prostoru řešení podporuje použití algoritmu B&B v této studii. Za předpokladu, že ps je částečný seznam o velikosti s, jsou potomky uzlu ps ve stromové topologii všechny seznamy, které začínají ps, tj. všechna rozdělení, kde prvních s vrstev je umístěno podle ps. Listový uzel pod ps odpovídající ps doplněné poslední hodnotou ps je označen ps~. Například, pokud L=5 a p2=(2,1), pak p2~=(2,1,1,1,1). Vzhledem k Ttmax=maxTt(ps~) maximální hodnota matice latence přenosu pro rozdělení ps~, všechny listové uzly p pod ps budou mít vyšší maximální latenci přenosu než ps~, tj. ∀p,maxTt(p)≥Ttmax. To je vysvětleno faktem, že pro dané částečné rozdělení, jakýkoli přesun v ostatních vrstvách pouze přidá přenosy dat mezi uzly. Během procesu hledání optimálního rozdělení p, které maximalizuje propustnost inference C(p,GA,GN), a při dané aktuální nejlepší dosažitelné propustnosti best_throughput, se optimalizace B&B skládá z eliminace celých větví stromu reprezentujícího prostor řešení vyhodnocením časů přenosu v částečných rozděleních. Tento proces umožňuje optimalizaci B&B rychle eliminovat mnoho případů ve srovnání s hrubou silou algoritmu. Například, pokud je propustnost mezi uzly nízká ve srovnání s výpočetní kapacitou, např. s uzly připojenými přes nízko propustné bezdrátové spojení, optimálním řešením je často ponechat veškerý výpočet na jednom uzlu. Výhodou algoritmu B&B je, že se v takových jednoduchých případech zastaví po N operacích tím, že eliminuje všechna částečná rozdělení v první fázi stromu. Naopak, v případech, kdy spojení mají vyšší propustnosti, může být složitost B&B vyšší, protože nebude schopen eliminovat velké větve. B. Složitost větvení a mezí Režie způsobená celkovým počtem částí v reálné implementaci je v