Kenapa AI Anda Tidak Perlu Lagi Cloud untuk Berjalan Lebih Cepat

Penulis: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Abstrak: Penghujahan rangkaian saraf dalam (DNN) pada data aliran memerlukan sumber pengkomputeran untuk memenuhi keperluan keperluan pemprosesan. Walau bagaimanapun, aplikasi pembelajaran mendalam yang sensitif terhadap latensi dan privasi tidak mampu untuk menyerahkan pengkomputeran kepada awan jauh kerana kos penghantaran yang tersirat dan kekurangan kepercayaan kepada penyedia awan pihak ketiga. Antara penyelesaian untuk meningkatkan prestasi sambil menyimpan pengkomputeran dalam persekitaran terhad, pecutan perkakasan boleh menjadi membebankan, dan pengoptimuman model memerlukan usaha reka bentuk yang luas sambil menghalang ketepatan. Pemartisian DNN adalah pendekatan pelengkap ketiga, dan terdiri daripada mengedarkan beban kerja penghujahan ke beberapa peranti tepi yang tersedia, dengan mengambil kira sifat rangkaian tepi dan struktur DNN, dengan objektif untuk memaksimumkan keperluan pemprosesan penghujahan (bilangan penghujahan sesaat). Kertas ini memperkenalkan kaedah untuk meramalkan latensi penghujahan dan penghantaran untuk penempatan DNN teragih berbilang benang, dan mentakrifkan proses pengoptimuman untuk memaksimumkan keperluan pemprosesan penghujahan. Penyelesai cabang dan sempadan kemudiannya dipersembahkan dan dianalisis untuk mengukur prestasi dan kerumitan yang dicapai. Analisis ini telah membawa kepada definisi rantau pecutan, yang menerangkan keadaan deterministik pada sifat DNN dan rangkaian di mana pemartisian DNN bermanfaat. Akhir sekali, keputusan eksperimen mengesahkan simulasi dan menunjukkan peningkatan keperluan pemprosesan penghujahan dalam penempatan tepi sampel. Pemartisian DNN di tepi membolehkan pecutan keperluan pemprosesan penghujahan sambil mengurangkan penggunaan lebar jalur dan latensi kepada pelayan terpusat, cth, di awan. Pendahuluan Peranti bersambung menjana anggaran 2.5 quintilion bait data setiap hari pada tahun 2020. Dalam konteks ini, Kecerdasan Buatan (AI) adalah salah satu teknologi yang paling sesuai untuk menangani jumlah data yang sentiasa meningkat, dalam pelbagai bidang seperti pengesanan objek dalam visi komputer, pengecaman wajah, pengecaman suara, pemprosesan bahasa semula jadi, atau pemanduan autonomi. AI, dan khususnya Pembelajaran Mendalam (DL), memerlukan, selain daripada sejumlah besar data, keupayaan yang ketara dalam kuasa pemprosesan dan memori, yang menjadikan pengkomputeran awan sebagai penyelesaian pengehosan untuk beban kerja AI. Akibatnya, pada tahun 2019, 96% tugas AI dijalankan di awan. 1 de facto 2 Aplikasi AI boleh mempunyai kekangan latensi yang kuat, , dalam pemanduan autonomi, pemantauan pembuatan, atau sebarang penghujahan masa nyata yang melibatkan interaksi dunia sebenar. Contohnya, purata masa respons dalam pemanduan autonomi diperlukan di bawah 100 milisaat , menjadikan masa perjalanan pergi dan balik ke awan terlalu lama untuk aplikasi tersebut. Begitu juga, sesetengah aplikasi mungkin memperkenalkan penggunaan pautan yang ketara pada rangkaian, , dalam kes pemprosesan video berkualiti tinggi dalam visi komputer, yang menghalang mereka daripada berjalan di awan. Dasar privasi data atau peraturan perlindungan data juga mungkin melarang data daripada meninggalkan persekitaran tertentu. Ini menggalakkan penempatan AI dalam pengkomputeran tepi, yang terdiri daripada memindahkan tugas pengkomputeran daripada pusat data lebih dekat kepada peranti tepi, , berdekatan dengan sumber data. cth [](javascript:void()) cth iaitu Berbanding dengan awan awam, tepi adalah persekitaran terhad sumber dengan had penting , dan membangunkan AI untuk tepi oleh itu berbeza secara intrinsik daripada membangunkan AI untuk awan. Menganalisis data berdekatan sumbernya boleh mencabar kerana kapasiti peranti yang lebih rendah, ketidaklenturan sumber yang tersedia, dan kepelbagaian rangkaian tepi. Mengurangkan kapasiti pengkomputeran menyiratkan pengurangan keperluan pemprosesan penghujahan yang boleh dicapai, seterusnya merumitkan pemindahan beban kerja berat daripada awan ke tepi. Dalam beberapa aplikasi, keperluan pemprosesan penghujahan, , penghujahan sesaat yang boleh dicapai bagi DNN, boleh dikaitkan dengan ketepatan DNN, , dengan pengesanan objek dalam aliran video, di mana penurunan kadar penghujahan daripada 15 kepada 5 penghujahan sesaat telah ditunjukkan untuk menurunkan skor F1__3__ pengesan objek sebanyak 10% . Dengan kata lain, penempatan dengan keperluan pemprosesan penghujahan yang rendah boleh menyebabkan kehilangan maklumat kritikal, , kehilangan pengesanan dalam aplikasi pengawasan video. [](javascript:void()) iaitu cth [](javascript:void()) cth Terdapat dua kaedah utama yang tersedia untuk memenuhi keperluan prestasi pada rangkaian tepi terhad: mampatan model atau pecutan perkakasan. terdiri daripada mengurangkan dan mengoptimumkan rangkaian saraf kepada versi model yang ringan, selalunya berprestasi rendah. Kaedah mampatan model standard termasuk pemangkasan , , mengalih keluar parameter yang tidak perlu dalam model, pengkuantitian , , mengurangkan memori yang diperuntukkan untuk menyimpan model, dan penyulingan pengetahuan , , melatih rangkaian saraf yang lebih kecil dengan pengetahuan yang diekstrak daripada yang lebih besar. Pengoptimuman model memerlukan usaha reka bentuk yang luas dan boleh menjadi penghalang kepada ketepatan model. pada peranti tepi menyiratkan pencarian perkakasan yang boleh cekap tenaga dan ringan, sambil masih mampu menjalankan penghujahan dengan prestasi yang mencukupi. Terdapat beberapa jenis perkakasan calon untuk pecutan di tepi, yang berbeza dalam kecekapan dan kekhususan, tetapi unit pemprosesan standard gagal memenuhi jangkaan dan perkakasan khusus seperti ASIC telah didapati tidak praktikal dan mahal . Mampatan model [](javascript:void()) iaitu [](javascript:void()) iaitu [](javascript:void()) iaitu Pecutan perkakasan [](javascript:void()) Pemartisian DNN adalah kaedah pelengkap untuk mempercepatkan penghujahan dengan memanfaatkan kepelbagaian peranti sedia ada dalam rangkaian tepi untuk mengedarkan pengkomputeran penghujahan– yang boleh digunakan secara bersendirian, atau bersama-sama dengan dua kaedah lain. Pemartisian DNN terdiri daripada mempertimbangkan rangkaian saraf sebagai saluran paip untuk dibahagikan kepada bahagian, dan mengedarkan bahagian ini pada peranti tepi. Penempatan bahagian ini adalah berdasarkan kedua-dua DNN dan ciri rangkaian asas. Pemartisian DNN bergantung pada pengenalpastian titik pemisahan, iaitu titik dalam graf model di mana model dipisahkan kepada bahagian. Semasa masa jalan, bahagian dijalankan secara berturutan, masing-masing menghantar hasil penghujahan perantaraan ke bahagian seterusnya. Ini membolehkan setiap bahagian memulakan pengkomputeran data input seterusnya manakala peranti lain terus memproses yang diserahkan, dengan itu meningkatkan keperluan pemprosesan penghujahan, seperti yang ditunjukkan dalam . Dalam bahagian lain kertas ini, pemartisian DNN digambarkan melalui contoh penghujahan masa nyata pada aliran video. rajah 1 A. Kerja Berkaitan Kaedah untuk pemartisian DNN, yang berasal daripada penyerahan bebanan tepi-awan mudah alih, berusaha untuk mengoptimumkan pelbagai penunjuk prestasi, seperti latensi pengkomputeran, penggunaan tenaga, penggunaan sumber, kos, atau keperluan pemprosesan. Pemartisian DNN bergantung pada persatuan satu atau beberapa metrik ini untuk mentakrifkan objektif pengoptimuman, dan kaedah yang mengeksploitasi metrik ini untuk mencari skim pemartisian. Contohnya, Neurosurgeon mencari satu titik pemisahan, menyimpan bahagian pertama di tepi dan menyerahkan bahagian kedua kepada awan, untuk meminimumkan latensi dan penggunaan tenaga. Aplikasi dalam IoT juga telah mempertimbangkan pemartisian dan penyerahan bebanan bersama beberapa DNN untuk mengoptimumkan tenaga, kelewatan, dan/atau kos, menggunakan penyelesai yang berbeza seperti SPSO-GA menggabungkan Pengoptimuman Kawan Zarah (PSO) dan Algoritma Genetik (GA), atau DDPQN yang menggunakan Pembelajaran Pengukuhan Mendalam untuk mencari skim pemartisian. Contoh lain termasuk DINA , yang mentakrifkan masalah Pengaturcaraan Tak Linear Integer (INLP), dan menggunakan penyelesai berasaskan teori padanan, untuk mengoptimumkan kelewatan dan penggunaan sumber dalam rangkaian kabut. Kaedah yang mengoptimumkan keperluan pemprosesan penghujahan termasuk pembedahan DNN , yang menggunakan saiz output lapisan DNN perantaraan yang lebih kecil untuk memartisi pengkomputeran penghujahan antara tepi dan awan. Kedua-dua algoritma mencipta dua bahagian, satu di tepi dan satu lagi di awan. Kajian lain dalam bidang tepi-awan mudah alih juga termasuk pengkomputeran berbilang benang di awan untuk mempercepatkan lagi keperluan pemprosesan penghujahan keseluruhan. Bergantung pada awan untuk pengkomputeran penghujahan bahagian kedua menganggap sambungan rangkaian yang baik, yang boleh menjadi tidak pasti dengan sambungan lemah sesetengah penempatan tepi terpencil. Edgent menyesuaikan metodologi sebelumnya kepada peranti mudah alih dan pelayan tepi yang tersedia, melonggarkan kekangan penyerahan bebanan kepada awan. Kaedah ini dikaitkan dengan latihan dan seni bina model tertentu, dan masih mengehadkan pemartisian kepada dua bahagian. Kaedah lain telah mempertimbangkan berbilang titik pemisahan, , IONN , yang menerangkan masalah pemartisian untuk meminimumkan latensi dan penggunaan tenaga, juga mengambil kira masa untuk memuatkan model ke pelayan tepi. [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) cth [](javascript:void()) Kaedah ini sama ada berinteraksi dengan awan jauh, atau terhad dalam sifat pemartisian, , dikehendaki berpecah kepada tepat dua bahagian, dengan atau tanpa berbilang benang. Tiada kajian pemartisian DNN yang disenaraikan mempertimbangkan kedua-dua berbilang titik pemisahan dan berbilang benang. cth B. Sumbangan Kertas ini mempersembahkan rangka kerja penghujahan teragih untuk memaksimumkan keperluan pemprosesan penghujahan pengkomputeran DNN masa nyata pada data aliran, dengan berbilang titik pemisahan dan pemartisian berbilang benang. Sumbangan kertas ini adalah seperti berikut: Model untuk mengira latensi pengkomputeran dan penghantaran DNN teragih, melalui mana keperluan pemprosesan penghujahan yang dijangkakan bagi skim pemartisian yang diberikan boleh dianggarkan. Perumusan masalah pengoptimuman untuk pemartisian DNN, pelaksanaan penyelesai cabang dan sempadan untuk masalah ini, dan penilaian kerumitannya. Simulasi untuk meneroka peningkatan prestasi yang mungkin dengan sifat rangkaian dan DNN yang berbeza-beza. Pengenalpastian rantau deterministik dalam sifat rangkaian dan DNN yang membawa kepada kewujudan pemartisian optimum dan kos untuk mengira penyelesaian tersebut, , keadaan di mana pemartisian DNN bermanfaat. iaitu Keputusan eksperimen menggambarkan rantau yang ditakrifkan dalam simulasi, serta ketepatan ramalan dan pecutan keperluan pemprosesan penghujahan akhir untuk persekitaran homogen dan heterogen. Untuk bahagian lain kertas ini, untuk mengelakkan kekeliruan, rangkaian saraf dalam yang dipartisikan akan dirujuk sebagai , dan istilah akan merujuk kepada rangkaian komunikasi fizikal asas. DNN rangkaian C. Garis Masa Kertas Baki kertas ini disusun seperti berikut. mempersembahkan latar belakang Pembelajaran Mendalam dan bagaimana DNN diwakili dalam kajian ini. memperincikan kaedah ramalan latensi penghujahan dan penghantaran yang diperlukan untuk yang mentakrifkan masalah pengoptimuman, serta algoritma cabang dan sempadan untuk membuat keputusan pemartisian. mempersembahkan keputusan simulasi untuk mengukur prestasi dan kerumitan algoritma cabang dan sempadan, serta keadaan yang membawa kepada kewujudan pemartisian yang meningkatkan keperluan pemprosesan penghujahan dalam rangkaian homogen. mempersembahkan keputusan eksperimen yang mengesahkan simulasi , dan menunjukkan peningkatan keperluan pemprosesan penghujahan pada persediaan eksperimen heterogen. Akhir sekali, membincangkan keputusan dan memperluas kebolehgunaan yang lebih luas kaedah ini. Bahagian II Bahagian III Bahagian IV Bahagian V Bahagian VI Bahagian V Bahagian VII BAHAGIAN II. Latar Belakang: Pembelajaran Mendalam Dalam bidang Pembelajaran Mesin, Pembelajaran Mendalam (DL) merujuk kepada kaedah yang bergantung pada penggunaan DNN, , rangkaian saraf tiruan (atau kaedah pembelajaran mesin berkaitan) yang mengandungi lebih daripada satu lapisan tersembunyi. Salah satu rujukan terawal kepada seni bina pembelajaran mendalam telah diterbitkan pada tahun 1967 , tetapi sehingga tahun 2010-an barulah DL mendapat perhatian, pertama dalam pengecaman suara, kemudian dalam pengesanan objek dalam imej, kerana keupayaan untuk menangkap hubungan kompleks dalam data berdimensi tinggi. Pembelajaran Mendalam dianggarkan mewakili majoriti aplikasi AI pada tahun 2022, dengan lebih daripada 75% organisasi menggunakan DNN untuk aplikasi yang boleh menggunakan kaedah klasik. Kaedah DL telah ditakrifkan sebagai “ ” . Litar algebra ini biasanya diatur ke dalam lapisan, yang membentuk langkah-langkah dalam pengkomputeran. Istilah merujuk kepada algoritma yang terdiri daripada lebih daripada satu lapisan. iaitu [](javascript:void()) 4 teknik untuk pembelajaran mesin di mana hipotesis mengambil bentuk litar algebra kompleks dengan kekuatan sambungan yang boleh dilaraskan [](javascript:void()) mendalam Terdapat dua struktur DNN utama: rangkaian saraf suapan hadapan dan rangkaian saraf berulang. Kedua-dua jenis DNN boleh diwakili sebagai graf pengkomputeran, dengan perbezaan utama ialah rangkaian suapan hadapan boleh diwakili sebagai graf asiklik langsung (DAG), manakala rangkaian saraf berulang mungkin mengandungi kitaran. Rangkaian saraf berulang dibina untuk urutan data, di mana setiap titik data mempunyai kebergantungan yang berpotensi dengan titik data sebelumnya dalam urutan, manakala rangkaian saraf suapan hadapan tidak mempertimbangkan interaksi antara titik dalam urutan data. Baki kertas ini akan mempertimbangkan kes DNN suapan hadapan. 5 BAHAGIAN III. Pemodelan Penghujahan Teragih Bahagian ini mempersembahkan model untuk mewakili sifat DNN dan rangkaian untuk meramalkan latensi pengkomputeran, latensi penghantaran, dan keperluan pemprosesan penghujahan akhir bagi penyelesaian pemartisian yang diberikan. A. Perwakilan DNN dan Rangkaian DNN suapan hadapan dengan N lapisan dimodelkan sebagai DAG GA=(L,E) dengan L=(L1,…,LL) ialah lapisan DNN. Tepi (Li,Lj)∈E ialah sambungan antara lapisan Li dan Lj. Setiap lapisan Li mempunyai penggunaan pengkomputeran yang berkaitan ci, diukur dalam bilangan operasi titik terapung yang diperlukan untuk mengira laluan hadapan melalui lapisan. Tepi (Li,Lj) ditugaskan pemberat si,j yang sepadan dengan saiz data yang transit antara lapisan Li dan Lj dalam bait. Rangkaian fizikal dimodelkan sebagai graf lengkap G=(N,V) di mana N=(N1,…,NN) ialah set nod pengkomputeran dan V ialah set pautan antara nod. Adalah difikirkan bahawa nod pengkomputeran N1,…,NN mempunyai kadar pemprosesan η1,…,ηN, masing-masing, diukur dalam operasi titik terapung sesaat. Akhir sekali, keperluan jalur pautan antara dua nod bersebelahan Na dan Nb dilambangkan sebagai θa,b, diukur dalam bait sesaat. Setiap nod Ni disambungkan kepada dirinya sendiri dengan keperluan jalur yang tidak terhingga untuk mewakili pautan ulangan, dan pautan dianggap simetri, iaitu, θa,b=θb,a. Pemartisian ditakrifkan sebagai peta P:L→N, iaitu, pemartisian menetapkan nombor nod kepada setiap lapisan dalam DNN. Pemartisian boleh digambarkan sebagai matriks P berdimensi (N×L), N ialah bilangan nod dalam rangkaian dan L ialah bilangan lapisan DNN dan, dengan Pa,i=1 jika lapisan Li diletakkan pada nod Na, 0 sebaliknya. Dengan contoh yang diberikan dalam , L=7 lapisan dan N=2 nod pengkomputeran, pemartisian yang dipaparkan dengan lapisan {L1,L2,L3,L6,L7} pada nod N1, dan lapisan {L4,L5} pada nod N2, diwakili sebagai: rajah 2 Diberi pemartisian, a ditakrifkan sebagai kumpulan lapisan berturutan antara dua titik pemisahan, dijalankan secara berturutan pada nod yang sama. Dalam contoh di atas, nod N1 akan menjalankan dua benang, yang pertama mengandungi lapisan {L1,L2,L3} dan yang kedua mengandungi {L6,L7}. benang Dengan notasi ini ditakrifkan, baki Bahagian ini menurunkan ungkapan tertutup bagi keperluan pemprosesan penghujahan yang dicapai oleh pemartisian yang diberikan, sebagai fungsi latensi penghujahan ( sezione III-B) dan penghantaran ( sezione III-C). B. Ramalan Latensi Penghujahan Diberi pemartisian, Bahagian ini melihat ramalan latensi penghujahan pada nod terpencil. Latensi yang disebabkan oleh pengkomputeran lapisan Li dengan penggunaan ci, untuk dikomputasikan pada nod Na, dengan kadar pemprosesan ηa dinyatakan sebagai Tci(Na)=ci/ηa. Diberi satu set lapisan L′⊂L merentasi semua benang yang berjalan pada nod Na dengan kadar pemprosesan ηa, latensi penghujahan boleh dinyatakan sebagai: Ungkapan ini ialah anggaran tertib pertama bagi anggaran latensi penghujahan berdasarkan bilangan operasi titik terapung (FLOP) yang diperlukan untuk memproses DNN, iaitu, bilangan operasi penambahan pendaraban dalam model. Anggaran latensi penghujahan pada peranti tepi dikomplikasikan oleh pengoptimuman masa jalan. Penyelesaian sedia ada seperti nn-Meter meramalkan latensi penghujahan berdasarkan FLOP. Penyelesaian lain bergantung pada jadual carian dengan masa penghujahan yang telah dikira untuk ramalan latensi. Contohnya, BRP-NAS menggunakan rangkaian konvolusional terlatih untuk meramalkan latensi penghujahan, sambil mengambil kira pengoptimuman model masa jalan. [](javascript:void()) [](javascript:void()) Dalam , ia juga difikirkan bahawa pemproses menggunakan kapasiti penuh mereka, yang menyiratkan bahawa pemproses berbilang teras dimodelkan sebagai pemproses teras tunggal dengan kadar pemprosesan bersamaan dengan jumlah kadar pemprosesan teras mereka. Ia juga difikirkan bahawa sumber pengkomputeran dikongsi secara merata di seluruh benang, iaitu, pemproses memperuntukkan bahagian masa yang sama kepada setiap benang. persamaan 1 Merentasi semua nod, benang dengan latensi tertinggi menetapkan keperluan pemprosesan penghujahan untuk DNN teragih. Dengan mengabaikan latensi penghantaran, ini menyiratkan bahawa sebaik sahaja benang terhad ini selesai mengkomputasikan bingkai data, ia terus memproses yang seterusnya. Benang lain akan mempunyai masa terbiar sebelum memproses bingkai data seterusnya kerana latensi penghujahan mereka lebih rendah daripada latensi maksimum ini, seperti yang ditunjukkan dalam . rajah 1 Diberi matriks pemartisian P, latensi penghujahan boleh dinyatakan sebagai vektor tunggal Tc bersaiz N di mana komponen ke-a ialah latensi benang penghujahan tertinggi pada nod Na, iaitu, Tca=Tc(Na): di mana H ialah matriks pepenjuru kadar pemprosesan nod songsang diag(η−11,…,η−1N) dan c ialah vektor lajur penggunaan lapisan individu (c1,…,cL). C. Ramalan Latensi Penghantaran Latensi penghantaran boleh diramalkan seperti berikut: masa yang diambil untuk menghantar jumlah data si,j antara lapisan Li dan Lj pada tepi (Na,Nb) merentasi pautan dengan keperluan jalur yang diukur θa,b ialah Tti,j(Na,Nb)=si,j/θa,b. Masa untuk mencapai pemindahan data si,j∈E′⊂E merentasi pautan (Na,Nb) ialah: Serupa dengan ramalan latensi penghujahan, ini menyiratkan bahawa pautan dikongsi secara merata di antara pemindahan data dari Na ke Nb. Ramalan latensi penghantaran bergantung pada anggaran keperluan jalur pautan, lebih tepat lagi , , jumlah data berguna yang dihantar sesaat. jalur lebar yang baik iaitu Serupa dengan anggaran latensi penghujahan, ini adalah anggaran tertib pertama, yang dengan cekap menawarkan hasil ramalan yang baik, seperti yang ditunjukkan dalam c, dengan pekali korelasi R2=0.9998. Kelemahan kaedah ini ialah keperluannya untuk menjenuhkan pautan untuk mendapatkan anggaran keperluan jalur. rajah 3 Diberi matriks pemartisian P, matriks latensi penghantaran Tt boleh ditakrifkan sebagai matriks segiempat sama bersaiz L, dengan Tta,b=Tt(Na,Nb): di mana ° ialah produk istilah demi istilah, atau produk Hadamard, Θ ialah matriks songsang keperluan jalur, iaitu, matriks segiempat sama bersaiz N dengan Θa,b=θ−1a,b dan S ialah matriks saiz penghantaran, iaitu, matriks segiempat sama bersaiz L dengan Si,j=si,j jika Li menghantar data kepada Lj, 0 sebaliknya. BAHAGIAN IV. Pemartisian DNN Objektif pemartisian DNN dalam kajian ini adalah untuk memaksimumkan keperluan pemprosesan penghujahan, dilambangkan oleh C, yang sepadan dengan songsang daripada latensi maksimum di antara semua latensi pengkomputeran dan penghantaran yang berbeza. Diberi pemartisian P, keperluan pemprosesan penghujahan ditakrifkan sebagai: Memaksimumkan keperluan pemprosesan penghujahan bersamaan dengan mencari min-max bersama di antara semua istilah Tc dan Tt. Ini boleh ditakrifkan sebagai masalah pengoptimuman diskret: dengan Ji,j ialah matriks semua-satu bersaiz i×j, syarat (6) dan (7) memerlukan bahawa setiap lapisan diletakkan pada satu dan hanya satu nod. Masalah pengoptimuman ini ialah masalah Pengaturcaraan Tak Linear Campuran Integer (MINLP). Matriks pemartisian boleh dilihat sebagai versi pengekodan satu-panas bagi vektor bersaiz (1×L) dengan nilai dalam [[1,N]]. Masalah MINLP adalah NP-sukar, menyiratkan bahawa kerumitan mencari pemartisian DNN optimum ialah O(NL) kerana setiap L lapisan boleh diletakkan pada N nod. Terdapat beberapa heuristik untuk mendapatkan penyelesaian optimum atau suboptimum kepada masalah ini dalam masa yang kurang daripada algoritma brute force, iaitu, Algoritma Genetik (GA) [](javascript:void()), Pengoptimuman Kawan Zarah (PSO) [](javascript:void()), atau Cabang dan Sempadan (B&B) [](javascript:void()). Metodologi yang dipilih ialah pelaksanaan B&B yang diadaptasi, yang dipersembahkan dalam Bahagian IV-A. A. Algoritma Cabang dan Sempadan Bahagian ini mempersembahkan adaptasi cabang dan sempadan (B&B) kepada masalah pengoptimuman pemartisian DNN yang ditakrifkan dalam Bahagian IV. Dalam algoritma B&B, ruang penyelesaian diwakili oleh pokok. Prosesnya terdiri daripada menghapuskan keseluruhan cabang dalam pokok berdasarkan penilaian skor nod akar. Ini menyiratkan kewujudan topologi pokok yang mewujudkan hubungan antara skor nod dalam pokok dan sempadan pada skor semua daunnya. Perwakilan pokok ruang penyelesaian ini memihak kepada penggunaan algoritma B&B dalam kajian ini. Dengan andaian ps ialah senarai separa bersaiz s, anak-anak kepada nod ps dalam topologi pokok ialah semua senarai yang bermula dengan ps, iaitu, semua pemartisian di mana s lapisan pertama diletakkan mengikut ps. Nod daun di bawah ps yang sepadan dengan ps yang diisi dengan nilai terakhir ps dilabelkan ps~. Contohnya, jika L=5 dan p2=(2,1), maka p2~=(2,1,1,1,1). Diberi Ttmax=maxTt(ps~) latensi penghantaran maksimum untuk pemartisian ps~, semua nod daun p di bawah ps akan mempunyai latensi penghantaran maksimum yang lebih tinggi daripada ps~, iaitu, ∀p,maxTt(p)≥Ttmax. Ini dijelaskan oleh fakta bahawa diberi pemartisian separa, sebarang anjakan dalam lapisan lain hanya akan menambah pemindahan data antara nod. Semasa proses mencari pemartisian optimum p, yang memaksimumkan keperluan pemprosesan penghujahan C(p,GA,GN), dan diberi keperluan pemprosesan penghujahan terbaik yang boleh dicapai semasa best_throughput, pengoptimuman B&B terdiri daripada menghapuskan keseluruhan cabang pokok yang mewakili ruang penyelesaian dengan menilai masa penghantaran dalam pemartisian separa. Proses ini membolehkan pengoptimuman B&B menghapuskan banyak kes berbanding algoritma brute force. Contohnya, jika keperluan jalur antara nod adalah rendah berbanding kapasiti pengkomputeran, iaitu, dengan nod disambungkan melalui sambungan wayarles keperluan jalur yang rendah, penyelesaian optimum selalunya adalah untuk menyimpan semua pengkomputeran pada satu nod. Kelebihan algoritma B&B ialah ia tamat selepas N operasi dalam kes mudah seperti itu dengan menghapuskan semua pemartisian separa pada peringkat pertama pokok. Sebaliknya, dalam kes di mana pautan mempunyai keperluan jalur yang lebih tinggi, kerumitan B&B boleh menjadi lebih tinggi kerana ia tidak akan dapat menghapuskan cawangan besar. B. Kerumitan Cabang dan Sempadan Kos tambahan yang disebabkan oleh jumlah bahagian dalam pelaksanaan dunia sebenar diabaikan dalam pendekatan ini. Latensi tambahan ini berkorelasi dengan jumlah bahagian. Dengan setiap bahagian, pemindahan data daripada Pengawal Antara Muka Rangkaian (NIC) ke memori menyebabkan latensi tambahan, berkaitan dengan keperluan jalur PCIe, keperluan jalur memori dan saiz data yang dipindahkan. Dengan andaian bahawa keperluan jalur pemindahan data dihadkan oleh keperluan jalur memori, penilaian simplistik latensi ini akan mengubah latensi pengkomputeran dalam kepada: persamaan 1 Dalam ungkapan ini, ν ialah keperluan jalur memori, iaitu, kelajuan baca/tulis ke dan dari memori, dan (i,j)∈C ialah semua lapisan Li dan Lj sedemikian rupa sehingga tepi (Li,Lj) ialah titik pemisahan dengan pemindahan data yang berkaitan si,j. 1) Berhenti Awal Dengan peningkatan bilangan bahagian, kedua-dua prestasi dan ketepatan ramalan latensi penghujahan akan berkurangan. Atas sebab ini, dan untuk peningkatan kerumitan dalam kes dengan keperluan jalur rangkaian yang tinggi, mekanisme berhenti awal ditambah untuk mengehadkan bilangan titik pemisahan dalam pemartisian akhir, iaitu, B&B hanya akan meneroka pemartisian separa dengan maksimum S titik pemisahan, seterusnya mengehadkan saiz pokok yang diterokai. Algoritma B&B lengkap dengan titik pemisahan terhad ditunjukkan dalam <