Bakit Hindi Mo Kailangan ng Cloud para Patakbuhin nang Mas Mabilis ang Iyong AI

Mga May-akda: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Buod: Ang malalim na neural network (DNN) inference sa streaming data ay nangangailangan ng mga mapagkukunan ng pag-compute upang matugunan ang mga kinakailangan sa throughput ng inference. Gayunpaman, ang mga latency at privacy-sensitive deep learning application ay hindi kayang i-offload ang pag-compute sa mga malayong cloud dahil sa ipinahihiwatig na gastos sa paglilipat at kawalan ng tiwala sa mga third-party cloud provider. Kabilang sa mga solusyon upang mapataas ang pagganap habang pinapanatili ang pag-compute sa isang nakakulong na kapaligiran, ang hardware acceleration ay maaaring maging mabigat, at ang pag-optimize ng modelo ay nangangailangan ng malawak na pagsisikap sa disenyo habang hinahadlangan ang katumpakan. Ang DNN partitioning ay isang pangatlong komplementaryong pamamaraan, at binubuo ng pamamahagi ng workload ng inference sa maraming magagamit na edge device, isinasaalang-alang ang mga katangian ng network ng edge at ang istraktura ng DNN, na may layuning mapakinabangan ang throughput ng inference (bilang ng mga inference bawat segundo). Ipinapakilala ng papel na ito ang isang paraan upang mahulaan ang mga inference at transmission latency para sa multi-threaded distributed DNN deployment, at tinutukoy ang isang proseso ng optimisasyon upang mapakinabangan ang throughput ng inference. Pagkatapos ay ipinakilala at sinuri ang isang branch and bound solver upang masukat ang nakamit na pagganap at kumplikado. Ang pagsusuring ito ay humantong sa pagtukoy ng acceleration region, na naglalarawan ng mga deterministikong kondisyon sa mga katangian ng DNN at network kung saan ang DNN partitioning ay kapaki-pakinabang. Sa wakas, kinukumpirma ng mga resulta ng eksperimental ang mga simulasyon at nagpapakita ng mga pagpapabuti sa throughput ng inference sa mga sample na edge deployment. Ang DNN partitioning sa edge ay nagbibigay-daan sa pagpapabilis ng inference throughput habang binabawasan ang paggamit ng bandwidth at latency sa mga sentralisadong server, hal., sa cloud. Introduksyon Ang mga konektadong device ay nakabuo ng tinatayang 2.5 quintillion bytes ng data bawat araw noong 2020. Sa kontekstong ito, ang Artificial Intelligence (AI) ay isa sa mga teknolohiyang pinakamahusay na makakayanan ang palaging lumalaking dami ng nalilikhang data, sa iba't ibang larangan tulad ng object detection sa computer vision, facial recognition, speech recognition, natural language processing, o autonomous driving. Ang AI, at partikular ang Deep Learning (DL), ay nangangailangan, bilang karagdagan sa malalaking dami ng data, ng malaking kakayahan sa processing power at memory, na ginagawang ang cloud computing ang _de facto_ na solusyon sa pagho-host para sa mga AI workload. Dahil dito, noong 2019, 96% ng mga AI task ay pinapatakbo sa cloud. Ang mga AI application ay maaaring magkaroon ng malakas na mga limitasyon sa latency, _hal._, sa autonomous driving, pagsubaybay sa manufacturing, o anumang real-time inference na kinasasangkutan ng interaksyon sa totoong mundo. Halimbawa, ang average response times sa autonomous driving ay kinakailangang mas mababa sa 100 milliseconds, na ginagawang masyadong mahaba ang round trip times sa cloud para sa ganitong mga aplikasyon. Gayundin, ang ilang mga aplikasyon ay maaaring magpakilala ng makabuluhang paggamit ng link sa network, _hal._, sa kaso ng mataas na kalidad na video processing sa computer vision, na pumipigil sa mga ito na tumakbo sa cloud. Ang mga patakaran sa privacy ng data o mga regulasyon sa proteksyon ng data ay maaari ding ipagbawal ang pag-alis ng data mula sa mga partikular na kapaligiran. Ito ay naghihikayat ng mga AI deployment sa edge computing, na binubuo ng paglilipat ng mga computation task mula sa mga data center papalapit sa mga edge device, _i.e._, malapit sa mga pinagmumulan ng data. Kumpara sa mga pampublikong cloud, ang edge ay isang kapaligiran na limitado ang mga mapagkukunan na may malalaking limitasyon, at ang pagbuo ng AI para sa edge ay samakatuwid ay likas na naiiba sa pagbuo ng AI para sa cloud. Ang pagsusuri ng data malapit sa pinagmulan nito ay maaaring maging mahirap dahil sa mas mababang kapasidad ng device, kawalan ng elasticidad ng mga magagamit na mapagkukunan, at pagkakaiba-iba ng mga network ng edge. Ang pagpapababa ng computing capacity ay nagpapahiwatig ng pagpapababa ng nakakamit na inference throughput, na higit na nagpapahirap sa paglilipat ng mabibigat na workload mula sa cloud patungo sa edge. Sa ilang mga aplikasyon, ang inference throughput, _i.e._, ang nakakamit na inferences bawat segundo ng isang DNN, ay maaaring maiugnay sa katumpakan ng DNN, _hal._, sa object tracking sa mga video stream, kung saan ang pagbaba ng inference rate mula 15 hanggang 5 inferences bawat segundo ay nagpakita ng pagbaba ng F1 score ng isang object detector ng 10%. Sa ibang salita, ang mga deployment na may mababang inference throughput ay maaaring maging sanhi ng kritikal na pagkawala ng impormasyon, _hal._, pagkawala ng mga detection sa mga aplikasyon ng video surveillance. Mayroong dalawang pangunahing magagamit na pamamaraan upang matugunan ang mga kinakailangan sa pagganap sa mga nakakulong na network ng edge: model compression o hardware acceleration. Ang _model compression_ ay binubuo ng pagbabawas at pag-optimize ng mga neural network sa isang magaan, kadalasan ay hindi gaanong gumaganap, na bersyon ng modelo. Kabilang sa mga karaniwang pamamaraan ng model compression ang pruning, _i.e._, pag-aalis ng mga hindi kinakailangang parameter sa modelo, quantization, _i.e._, pagbabawas ng inilaang memorya para sa pag-iimbak ng modelo, at knowledge distillation, _i.e._, pagsasanay ng mas maliit na neural network na may kaalamang nakuha mula sa mas malaki. Ang pag-optimize ng modelo ay nangangailangan ng malawak na pagsisikap sa disenyo at maaaring maging hadlang sa katumpakan ng modelo. Ang _hardware acceleration_ sa mga edge device ay nagpapahiwatig ng paghahanap ng hardware na maaaring parehong mahusay sa enerhiya at magaan, habang may kakayahan pa ring magpatakbo ng inference na may sapat na pagganap. Mayroong ilang mga uri ng kandidatong hardware para sa acceleration sa edge, na nag-iiba sa kahusayan at pagiging tiyak, ngunit ang mga karaniwang processing unit ay nabibigo na matugunan ang mga inaasahan at ang mga dedikadong hardware tulad ng mga ASIC ay napatunayang hindi praktikal at mahal. Ang DNN partitioning ay isang komplementaryong pamamaraan para sa pagpapabilis ng inference sa pamamagitan ng paggamit sa pagiging marami ng mga umiiral na device sa mga network ng edge upang ipamahagi ang inference computation– na maaaring gamitin nang mag-isa, o kasama ng dalawang iba pang pamamaraan. Ang DNN partitioning ay binubuo ng pagtingin sa isang neural network bilang isang pipeline upang hatiin sa mga partition, at ipamahagi ang mga partition na ito sa mga edge device. Ang placement ng mga partition na ito ay batay sa parehong DNN at ang mga katangian ng underlying network. Ang DNN partitioning ay nakasalalay sa pagkilala ng mga split point, na mga punto sa model graph kung saan ang modelo ay pinaghihiwalay sa mga partition. Sa panahon ng run-time, ang mga partition ay pinapatakbo nang sunud-sunod, bawat isa ay nagpapadala ng mga intermediary inference result sa susunod na partition. Ito ay nagpapahintulot sa bawat partition na magsimulang mag-compute ng susunod na input data habang ang iba pang mga device ay nagpapatuloy sa pagproseso ng offloaded na data, kaya napapabuti ang inference throughput, tulad ng ipinapakita sa _figure 1_. Sa natitirang bahagi ng papel na ito, ang DNN partitioning ay ipinapakita sa pamamagitan ng halimbawa ng real-time inference sa mga video stream. A. Kaugnay na Trabaho Ang mga pamamaraan para sa DNN partitioning, na nagmula sa mobile edge-cloud offloading, ay naglalayong i-optimize ang iba't ibang mga tagapagpahiwatig ng pagganap, tulad ng computing latency, pagkonsumo ng enerhiya, paggamit ng mapagkukunan, gastos, o throughput. Ang DNN partitioning ay nakasalalay sa asosasyon ng isa o higit pa sa mga sukatan na ito upang tukuyin ang isang layunin ng optimisasyon, at isang pamamaraan na nagsasamantala sa sukatan na ito upang makahanap ng mga partitioning scheme. Halimbawa, ang Neurosurgeon ay naglalayong sa isang solong split point, pinapanatili ang unang partition sa edge at nag-o-offload ng ikalawang partition sa cloud, upang mabawasan ang latency at pagkonsumo ng enerhiya. Ang mga aplikasyon sa IoT ay isinasaalang-alang din ang pinagsamang partitioning at offloading ng ilang DNN upang i-optimize ang enerhiya, pagkaantala, at/o gastos, gamit ang iba't ibang mga solver tulad ng SPSO-GA na pinagsasama ang Particle Swarm Optimization (PSO) at Genetics Algorithm (GA), o DDPQN na gumagamit ng Deep Reinforcement Learning upang makahanap ng mga partitioning scheme. Kabilang sa iba pang mga halimbawa ang DINA, na tumutukoy sa isang Integer Non Linear Programming (INLP) problem, at gumagamit ng isang solver na batay sa matching theory, upang i-optimize ang pagkaantala at paggamit ng mapagkukunan sa mga fog network. Kabilang sa mga pamamaraan na nag-o-optimize ng inference throughput ang DNN surgery, na gumagamit ng mas mababang laki ng mga intermediary DNN layer output upang hatiin ang inference computation sa pagitan ng edge at ng cloud. Parehong mga algorithm ay lumilikha ng dalawang partition, isa sa edge at ang isa sa cloud. Ang iba pang mga pag-aaral sa larangan ng mobile edge-cloud ay nagsasama rin ng multi-threaded computation sa cloud upang higit pang mapabilis ang kabuuang inference throughput. Ang pag-asa sa cloud para sa pangalawang partition ng inference computation ay nagpapalagay ng magandang koneksyon sa network, na maaaring hindi sigurado sa mahinang koneksyon ng ilang nakahiwalay na edge deployment. Ang Edgent ay nag-aangkop sa naunang methodology sa mga mobile device at magagamit na mga edge server, na pinapalambot ang limitasyon ng pag-o-offload sa cloud. Ang pamamaraang ito ay nauugnay sa isang partikular na pagsasanay at arkitektura ng modelo, at nililimitahan pa rin ang partitioning sa dalawang partition. Ang iba pang mga pamamaraan ay isinasaalang-alang ang maraming split point, _hal._, IONN, na naglalarawan ng problema ng partitioning upang mabawasan ang latency at pagkonsumo ng enerhiya, isinasaalang-alang din ang oras upang i-upload ang mga modelo sa mga edge server. Ang mga pamamaraang ito ay nakikipag-ugnayan sa mga malayong cloud, o limitado sa kalikasan ng partitioning, _hal._, kinakailangang hatiin sa eksaktong dalawang bahagi, na may o walang multi-threading. Wala sa mga nakalistang pag-aaral sa DNN partitioning ang isinasaalang-alang ang parehong maraming split point at multi-threading. B. Mga Kontribusyon Ipinapakilala ng papel na ito ang isang distributed inference framework upang mapakinabangan ang inference throughput ng real-time DNN computation sa streaming data, na may maraming split point at multi-threaded partitioning. Ang mga kontribusyon ng papel na ito ay ang mga sumusunod: Isang modelo para sa computing at transmission latencies ng isang distributed DNN, kung saan ang inaasahang inference throughput ng isang ibinigay na partitioning scheme ay maaaring tantyahin. Pormulasyon ng problema ng optimisasyon para sa DNN partitioning, pagpapatupad ng isang branch and bound solver para sa problemang ito, at pagsusuri ng kumplikado nito. Mga simulasyon upang galugarin ang mga posibleng pagpapabuti sa pagganap na may iba't ibang katangian ng network at DNN. Ang pagkilala sa mga deterministikong rehiyon sa mga katangian ng network at DNN na humahantong sa pagkakaroon ng mga optimal na partitioning at ang gastos sa pag-compute ng mga solusyong iyon, _i.e._, ang mga kondisyon kung saan ang DNN partitioning ay kapaki-pakinabang. Mga resulta ng eksperimental na naglalarawan ng mga rehiyon na tinukoy sa mga simulasyon, pati na rin ang katumpakan ng prediksyon at ang panghuling acceleration ng throughput ng inference para sa mga homogeneous at heterogeneous na kapaligiran. Para sa natitirang bahagi ng papel na ito, upang maiwasan ang kalituhan, ang partitioned deep neural network ay tutukuyin bilang _DNN_, at ang termino na _network_ ay tutukoy sa underlying physical communications network. C. Balangkas ng Papel Ang natitirang bahagi ng papel na ito ay nakaayos bilang mga sumusunod. Ang _Seksyon II_ ay nagpapakilala ng background ng Deep Learning at kung paano kinakatawan ang mga DNN sa pag-aaral na ito. Ang _Seksyon III_ ay nagdedetalye ng mga paraan ng prediksyon ng inference at transmission latency na kinakailangan para sa _Seksyon IV_ na tumutukoy sa problema ng optimisasyon, pati na rin ang branch and bound algorithm upang gumawa ng mga desisyon sa partitioning. Ang _Seksyon V_ ay nagpapakita ng mga resulta ng simulasyon upang masukat ang pagganap at kumplikado ng branch and bound algorithm, pati na rin ang mga kondisyon na humahantong sa pagkakaroon ng isang partitioning na nagpapabuti sa inference throughput sa isang homogeneous network. Ang _Seksyon VI_ ay nagpapakita ng mga resulta ng eksperimental na nagkukumpirma sa mga simulasyon ng _Seksyon V_, at nagpapakita ng mga pagpapabuti sa inference throughput sa isang heterogeneous experimental set-up. Sa wakas, ang _Seksyon VII_ ay tumatalakay sa mga resulta at nagpapalawak sa mas malawak na applicability ng pamamaraang ito. SEKSYON II. Background: Deep Learning Sa loob ng larangan ng Machine Learning, ang Deep Learning (DL) ay tumutukoy sa mga pamamaraan na nakasalalay sa paggamit ng mga DNN, _i.e._, mga artificial neural network (o mga kaugnay na pamamaraan ng machine learning) na naglalaman ng higit sa isang hidden layer. Isa sa mga pinakaunang sanggunian sa mga arkitektura ng deep learning ay inilathala noong 1967, ngunit noong dekada 2010 lamang naging tanyag ang DL, una sa speech recognition, pagkatapos ay sa object detection sa mga imahe, dahil sa kakayahang makuha ang mga kumplikadong relasyon sa high dimensional na data. Tinatayang ang Deep Learning ay kumakatawan sa karamihan ng mga AI application noong 2022, na may mahigit 75% ng mga organisasyon na gumagamit ng mga DNN para sa mga aplikasyon na maaaring gumamit ng mga klasikong pamamaraan. Ang mga DL method ay tinukoy bilang “_mga pamamaraan para sa machine learning kung saan ang mga hypothesis ay may anyo ng mga kumplikadong algebraic circuit na may tunable connection strengths_”. Ang mga algebraic circuit na ito ay karaniwang nakaayos sa mga layer, na bumubuo ng mga hakbang sa pag-compute. Ang terminong _deep_ ay tumutukoy sa mga algorithm na binubuo ng higit sa isang layer. Mayroong dalawang pangunahing DNN structure: feed-forward neural network at recurrent neural network. Parehong uri ng DNN ay maaaring irepresenta bilang mga computation graph, kung saan ang pangunahing pagkakaiba ay ang mga feed-forward network ay maaaring irepresenta bilang direct acyclic graphs (DAGs), habang ang mga recurrent neural network ay maaaring maglaman ng mga cycle. Ang mga recurrent neural network ay binuo para sa mga sequence ng data, kung saan ang bawat data point ay may potensyal na dependency sa mga nakaraang data point sa sequence, habang ang mga feed-forward neural network ay hindi isinasaalang-alang ang mga interaksyon sa pagitan ng mga point sa isang data sequence. Ang natitirang bahagi ng papel na ito ay isasaalang-alang ang kaso ng mga feed-forward DNN. SEKSYON III. Distributed Inference Modeling Ang Seksyon na ito ay nagpapakilala ng isang modelo upang irepresenta ang mga katangian ng DNN at network upang mahulaan ang mga computation latencies, transmission latencies, at ang panghuling inference throughput ng isang ibinigay na partitioning solution. A. DNN at Representasyon ng Network Ang isang feed-forward DNN na may N na layer ay mino-modelo bilang isang DAG GA=(L,E) kung saan ang L=(L1,…,LL) ay ang mga layer ng DNN. Ang mga edge (Li,Lj)∈E ay ang mga koneksyon sa pagitan ng mga layer Li at Lj. Ang bawat layer Li ay may kaugnay na compute consumption ci, na sinusukat sa bilang ng floating-point operations na kinakailangan upang makalkula ang isang forward pass sa layer. Ang mga edge (Li,Lj) ay binibigyan ng timbang sij na tumutugma sa laki ng data na dumadaan sa pagitan ng mga layer Li at Lj sa mga byte. Ang pisikal na network ay mino-modelo bilang isang fully connected graph G=(N,V) kung saan ang N=(N1,…,NN) ay ang set ng compute nodes at ang V ay ang set ng mga link sa pagitan ng mga node. Ipinapalagay na ang mga compute node N1,…,NN ay may mga processing rate η1,…,ηN, ayon sa pagkakabanggit, na sinusukat sa floating-point operations bawat segundo. Sa wakas, ang link throughput sa pagitan ng dalawang magkadugtong na node Na at Nb ay tinukoy bilang θa,b, na sinusukat sa mga byte bawat segundo. Ang bawat node Ni ay konektado sa sarili nito na may walang hanggang throughput upang kumatawan sa loopback link, at ang mga link ay ipinapalagay na simetriko, _i.e._, θa,b=θb,a. Ang mga Partitioning ay tinutukoy bilang mga mapa P:L→N, _i.e._, ang isang partitioning ay nagtatalaga ng isang node number sa bawat layer sa DNN. Ang isang partitioning ay maaaring ilarawan bilang isang matrix P na may sukat na (N×L), kung saan ang N ay ang bilang ng mga node sa network at ang L ay ang bilang ng mga layer ng DNN at, kasama ang halimbawa na ibinigay sa _figure 2_, L=7 na mga layer at N=2 na compute node, ang ipinakitang partitioning na may mga layer {L1,L2,L3,L6,L7} sa node N1, at mga layer {L4,L5} sa node N2, ay kinakatawan bilang: Isinasaalang-alang ang isang partitioning, ang _thread_ ay tinutukoy bilang isang grupo ng magkakasunod na mga layer sa pagitan ng dalawang split point, na pinapatakbo nang sunud-sunod sa parehong node. Sa halimbawa sa itaas, ang node N1 ay magpapatakbo ng dalawang thread, ang una ay naglalaman ng mga layer {L1,L2,L3} at ang pangalawa ay naglalaman ng {L6,L7}. Kasama ang mga notasyong ito, ang natitirang bahagi ng Seksyon na ito ay nagmumula ng isang closed expression ng inference throughput na nakakamit ng isang ibinigay na partitioning, bilang isang function ng inference (_seksyon III-B_) at transmission (_seksyon III-C_) latencies. B. Prediksyon ng Inference Latency Isinasaalang-alang ang isang partitioning, ang Seksyon na ito ay tumitingin sa prediksyon ng inference latency sa isang hiwalay na node. Ang latency na dulot ng pag-compute ng isang layer Li na may consumption ci, na kokomputin sa node Na, na may processing rate ηa, ay ipinapahayag bilang Tci(Na)=ci/ηa. Isinasaalang-alang ang isang set ng mga layer L'⊂L sa lahat ng mga thread na tumatakbo sa node Na na may processing rate ηa, ang inference latency ay maaaring ipahayag bilang: Ang expression na ito ay isang first order approximation ng isang prediksyon ng inference latency batay sa bilang ng floating-point operations (FLOPs) na kinakailangan upang iproseso ang DNN, _i.e._, ang bilang ng multiply-add operations sa modelo. Ang pagtatantya ng inference latency sa mga edge device ay pinagkakakumplika ng mga run-time optimization. Ang mga umiiral na solusyon tulad ng nn-Meter ay naghuhula ng inference latency batay sa FLOPs. Ang iba pang mga solusyon ay nakasalalay sa isang look-up table na may mga pre-computed inference time para sa latency inference. Halimbawa, ang BRP-NAS ay gumagamit ng isang pre-trained graph convolutional network upang mahulaan ang mga inference latency, habang isinasaalang-alang ang mga run-time model optimization. Sa , ipinapalagay din na ang mga processor ay gumagamit ng kanilang buong kapasidad, na nagpapahiwatig na ang mga multi-core processor ay mino-modelo bilang mga single-core processor na may processing rate na katumbas ng kabuuan ng kanilang mga processing rate ng core. Ipinapalagay din na ang computing resource ay pantay na ibinabahagi sa mga thread, _i.e._, ang isang processor ay naglalaan ng parehong proporsyon ng oras nito sa bawat thread. equation 1 Sa lahat ng mga node, ang thread na may pinakamataas na latency ang nagtatakda ng inference throughput para sa distributed DNN. Hindi isinasama ang mga transmission latency, ito ay nagpapahiwatig na sa sandaling matapos ang limiting thread na ito sa pag-compute ng isang data frame, direkta itong magsisimula sa susunod na isa. Ang iba pang mga thread ay magkakaroon ng idle time bago ang pagproseso ng susunod na data frame dahil ang kanilang inference latency ay mas mababa kaysa sa maximum latency na ito, tulad ng ipinapakita sa _figure 1_. Isinasaalang-alang ang isang partitioning matrix P, ang mga inference latency ay maaaring ipahayag bilang isang solong vector Tc na may sukat na N kung saan ang a-th component ay ang pinakamataas na thread inference latency sa node Na, _i.e._, Tca=Tc(Na): kung saan H ay ang diagonal matrix ng inverse node processing rates diag(η−11,…,η−1N) at c ay ang column vector ng mga indibidwal na layer consumptions (c1,…,cL). C. Prediksyon ng Transmission Latency Ang transmission latency ay maaaring mahulaan tulad ng sumusunod: ang oras na kinakailangan upang ipadala ang dami ng data sij sa pagitan ng mga layer Li at Lj sa edge (Na,Nb) sa ibabaw ng isang link na may nasukat na throughput θa,b ay Tti,j(Na,Nb)=si,j/θa,b. Ang oras upang makamit ang mga data transfer sij∈E′⊂E sa ibabaw ng link (Na,Nb) ay: Katulad ng prediksyon ng inference latency, ito ay nagpapahiwatig na ang mga link ay pantay na ibinabahagi sa pagitan ng mga data transfer mula Na patungo sa Nb. Ang prediksyon ng transmission latency ay nakasalalay sa pagtatantya ng link throughput sa pagitan ng mga node, mas partikular ang _goodput_, _i.e._, ang dami ng kapaki-pakinabang na data na naililipat bawat segundo. Katulad ng pagtatantya ng inference latency, ito ay isang first order approximation, na mahusay na nag-aalok ng magandang mga resulta ng prediksyon, tulad ng ipinapakita sa _figure 3_ c, na may correlation coefficient na R2=0.9998. Ang disbentaha ng pamamaraang ito ay ang pangangailangan nitong i-saturate ang mga link upang makakuha ng pagtatantya ng throughput. Isinasaalang-alang ang isang partitioning matrix P, ang transmission latency matrix Tt ay maaaring tukuyin bilang isang square matrix na may sukat na L, kung saan ang Ta,b=Tt(Na,Nb): kung saan ang ° ay ang term by term product, o Hadamard product, Θ ay ang inverse throughput matrix, _i.e._, isang square matrix na may sukat na N kung saan ang Θa,b=θ−1a,b at S ay ang transmission size matrix, _i.e._, isang square matrix na may sukat na L kung saan ang Si,j=si,j kung ang Li ay nagpapadala ng data sa Lj, 0 kung hindi. SEKSYON IV. DNN Partitioning Ang layunin ng DNN partitioning sa pag-aaral na ito ay upang mapakinabangan ang inference throughput, na tinukoy bilang C, na tumutugma sa inverse ng maximum latency sa pagitan ng lahat ng iba't ibang computation at transmission latencies. Isinasaalang-alang ang isang partitioning P, ang inference throughput ay tinutukoy bilang: Ang pagpapakinabang sa inference throughput ay katumbas ng paghahanap ng joint min-max sa pagitan ng lahat ng mga termino ng Tc at Tt. Ito ay maaaring tukuyin bilang isang discrete optimization problem: kung saan ang Ji,j ay ang all-ones matrix na may sukat na i×j, at ang mga kondisyon at ay nangangailangan na ang bawat layer ay mailagay sa isa at isa lamang na node. (6) (7) Ang optimization problem na ito ay isang Mixed Integer Non-linear Programming (MINLP) problem. Ang partitioning matrix ay maaaring tingnan bilang one-hot encoded na bersyon ng isang vector na may sukat na (1×L) na may mga value sa [[1,N]]. Ang mga MINLP problem ay NP-hard, na nagpapahiwatig na ang kumplikado ng paghahanap ng isang optimal na DNN partitioning ay O(NL) dahil ang bawat isa sa L na layer ay maaaring ilagay sa N na node. Mayroong ilang mga heuristics upang makakuha ng optimal o sub-optimal na mga solusyon sa problemang ito sa mas kaunting oras kaysa sa isang brute force algorithm, _hal._, Genetic Algorithms (GA), Particle Swarm Optimization (PSO), o Branch and Bound (B&B). Ang napiling methodology ay isang inangkop na B&B implementation, na ipinakilala sa _Seksyon IV-A_. A. Branch and Bound Algorithm Ang Seksyon na ito ay nagpapakilala ng branch and bound (B&B) adaptation sa DNN partitioning optimization problem na tinukoy sa _Seksyon IV_. Sa mga B&B algorithm, ang solution space ay kinakatawan ng isang tree. Ang proseso ay binubuo ng pag-aalis ng buong mga sangay sa tree batay sa pagsusuri ng score ng root node. Ito ay nagpapahiwatig ng pagkakaroon ng isang tree topology na lumilikha ng relasyon sa pagitan ng score ng isang node sa tree at ang mga bound sa mga score ng lahat ng mga dahon nito.