Mengapa AI Anda Tidak Lagi Memerlukan Awan untuk Berjalan Lebih Pantas

```html Penulis: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Abstrak: Penyampaian rangkaian saraf tiruan dalam (DNN) pada data aliran memerlukan sumber daya komputasi untuk memenuhi persyaratan hasil inferens. Namun, aplikasi pembelajaran mendalam yang sensitif terhadap latensi dan privasi tidak dapat memindahkan komputasi ke awan jarak jauh karena biaya transmisi yang tersirat dan kurangnya kepercayaan pada penyedia awan pihak ketiga. Di antara solusi untuk meningkatkan kinerja sambil menjaga komputasi di lingkungan terbatas, percepatan perangkat keras bisa memberatkan, dan optimasi model memerlukan upaya desain yang ekstensif sambil menghambat akurasi. Partisi DNN adalah pendekatan pelengkap ketiga, dan terdiri dari mendistribusikan beban kerja inferensi ke beberapa perangkat tepi yang tersedia, dengan mempertimbangkan properti jaringan tepi dan struktur DNN, dengan tujuan memaksimalkan hasil inferens (jumlah inferensi per detik). Makalah ini memperkenalkan metode untuk memprediksi latensi inferensi dan transmisi untuk penyebaran DNN terdistribusi multi-utas, dan mendefinisikan proses optimasi untuk memaksimalkan hasil inferens. Pemecah masalah *branch and bound* kemudian disajikan dan dianalisis untuk mengukur kinerja dan kompleksitas yang dicapai. Analisis ini telah mengarah pada definisi wilayah percepatan, yang menggambarkan kondisi deterministik pada properti DNN dan jaringan di mana partisi DNN bermanfaat. Akhirnya, hasil eksperimental mengonfirmasi simulasi dan menunjukkan peningkatan hasil inferensi dalam penyebaran tepi sampel. Partisi DNN di tepi memungkinkan percepatan hasil inferensi sambil menurunkan penggunaan bandwidth dan latensi ke server terpusat, contohnya, di awan. Pendahuluan Perangkat terhubung menghasilkan perkiraan 2,5 kuintiliun byte data setiap hari pada tahun 2020. Dalam konteks ini, Kecerdasan Buatan (AI) adalah salah satu teknologi yang paling mampu mengatasi jumlah data yang terus meningkat, dalam berbagai bidang seperti deteksi objek dalam visi komputer, pengenalan wajah, pengenalan ucapan, pemrosesan bahasa alami, atau mengemudi otonom. AI, dan khususnya Pembelajaran Mendalam (DL), memerlukan, selain data dalam jumlah besar, kemampuan signifikan dalam kekuatan pemrosesan dan memori, yang menjadikan komputasi awan sebagai solusi hosting *de facto* untuk beban kerja AI. Akibatnya, pada tahun 2019, 96% tugas AI dijalankan di awan. 1 2 Aplikasi AI dapat memiliki batasan latensi yang kuat, *contohnya*, dalam mengemudi otonom, pemantauan manufaktur, atau inferensi waktu nyata apa pun yang melibatkan interaksi dunia nyata. Misalnya, waktu respons rata-rata dalam mengemudi otonom diharuskan kurang dari 100 milidetik , membuat waktu bolak-balik ke awan terlalu lama untuk aplikasi tersebut. Demikian pula, beberapa aplikasi dapat menimbulkan penggunaan tautan yang signifikan pada jaringan, *contohnya*, dalam kasus pemrosesan video berkualitas tinggi dalam visi komputer, yang mencegahnya berjalan di awan. Kebijakan privasi data atau peraturan perlindungan data juga dapat melarang data meninggalkan lingkungan tertentu. Hal ini mendorong penyebaran AI dalam komputasi tepi, yang terdiri dari memindahkan tugas komputasi dari pusat data lebih dekat ke perangkat tepi, *yaitu*, berdekatan dengan sumber data. [[1]](javascript:void()) Dibandingkan dengan awan publik, tepi adalah lingkungan terbatas sumber daya dengan keterbatasan penting , dan mengembangkan AI untuk tepi karenanya secara intrinsik berbeda dari mengembangkan AI untuk awan. Menganalisis data di dekat sumbernya bisa menjadi tantangan karena kapasitas perangkat yang lebih rendah, ketidakfleksibelan sumber daya yang tersedia, dan heterogenitas jaringan tepi. Menurunkan kapasitas komputasi berarti menurunkan hasil inferensi yang dapat dicapai, semakin mempersulit pemindahan beban kerja berat dari awan ke tepi. Dalam beberapa aplikasi, hasil inferensi, *yaitu*, inferensi yang dapat dicapai per detik dari DNN, dapat dikaitkan dengan akurasi DNN, *contohnya*, dengan pelacakan objek dalam aliran video, di mana penurunan tingkat inferensi dari 15 menjadi 5 inferensi per detik telah terbukti menurunkan skor F1__3__ dari pendeteksi objek sebesar 10% . Dengan kata lain, penyebaran dengan hasil inferensi rendah dapat menyebabkan hilangnya informasi kritis, *contohnya*, hilangnya deteksi dalam aplikasi pengawasan video. [[2]](javascript:void()) [[3]](javascript:void()) Ada dua metode utama yang tersedia untuk memenuhi persyaratan kinerja pada jaringan tepi yang terbatas: kompresi model atau percepatan perangkat keras. terdiri dari mengurangi dan mengoptimalkan jaringan saraf menjadi versi model yang ringan, seringkali berkinerja buruk. Metode kompresi model standar meliputi pemangkasan , *yaitu*, menghapus parameter yang tidak perlu dalam model, kuantisasi , *yaitu*, mengurangi alokasi memori untuk menyimpan model, dan distilasi pengetahuan , *yaitu*, melatih jaringan saraf yang lebih kecil dengan pengetahuan yang diekstraksi dari yang lebih besar. Optimasi model memerlukan upaya desain yang ekstensif dan dapat menjadi hambatan terhadap akurasi model. pada perangkat tepi menyiratkan menemukan perangkat keras yang efisien daya dan ringan, sambil tetap mampu menjalankan inferensi dengan kinerja yang memadai. Ada beberapa jenis perangkat keras kandidat untuk percepatan di tepi, bervariasi dalam efisiensi dan kekhususan, tetapi unit pemrosesan standar tidak memenuhi harapan dan perangkat keras khusus seperti ASIC telah ditemukan tidak praktis dan mahal . Kompresi model [[4]](javascript:void()) [[5]](javascript:void()) [[6]](javascript:void()) Percepatan perangkat keras [[7]](javascript:void()) Partisi DNN adalah metode pelengkap untuk mempercepat inferensi dengan memanfaatkan banyaknya perangkat yang ada di jaringan tepi untuk mendistribusikan komputasi inferensi– yang dapat digunakan sendiri, atau bersama dengan dua metode lainnya. Partisi DNN terdiri dari mempertimbangkan jaringan saraf sebagai *pipeline* untuk disegmentasi menjadi partisi, dan mendistribusikan partisi ini pada perangkat tepi. Penempatan partisi ini didasarkan pada karakteristik DNN dan jaringan yang mendasarinya. Partisi DNN bergantung pada identifikasi titik pemisahan, yang merupakan titik-titik dalam grafik model di mana model dipisahkan menjadi partisi. Selama waktu proses, partisi dijalankan secara berurutan, masing-masing mengirimkan hasil inferensi perantara ke partisi berikutnya. Hal ini memungkinkan setiap partisi untuk mulai menghitung data input berikutnya sementara perangkat lain terus memproses data yang dialihkan, sehingga meningkatkan hasil inferensi, seperti yang ditunjukkan pada . Selanjutnya dalam makalah ini, partisi DNN diilustrasikan melalui contoh inferensi waktu nyata pada aliran video. gambar 1 A. Pekerjaan Terkait Metode untuk partisi DNN, yang berasal dari pengalihan beban *edge-cloud* seluler, berusaha mengoptimalkan berbagai indikator kinerja, seperti latensi komputasi, konsumsi energi, pemanfaatan sumber daya, biaya, atau hasil. Partisi DNN bergantung pada asosiasi satu atau beberapa metrik ini untuk mendefinisikan tujuan optimasi, dan metode yang memanfaatkan metrik ini untuk menemukan skema partisi. Misalnya, Neurosurgeon mencari satu titik pemisahan, menyimpan partisi pertama di tepi dan mengalihkan partisi kedua ke awan, untuk meminimalkan latensi dan konsumsi energi. Aplikasi dalam IoT juga telah mempertimbangkan partisi dan pengalihan gabungan dari beberapa DNN untuk mengoptimalkan energi, penundaan, dan/atau biaya, menggunakan pemecah yang berbeda seperti SPSO-GA menggabungkan Optimasi Kawanan Partikel (PSO) dan Algoritma Genetika (GA), atau DDPQN yang menggunakan Pembelajaran Penguatan Mendalam untuk menemukan skema partisi. Contoh lain termasuk DINA , yang mendefinisikan masalah Pemrograman Non-Linear Integer (INLP), dan menggunakan pemecah berbasis teori pencocokan, untuk mengoptimalkan penundaan dan pemanfaatan sumber daya dalam jaringan kabut. Metode yang mengoptimalkan hasil inferensi termasuk *DNN surgery* , yang menggunakan ukuran keluaran lapisan DNN perantara yang lebih kecil untuk mempartisi komputasi inferensi antara tepi dan awan. Kedua algoritma membuat dua partisi, satu di tepi dan yang lain di awan. Studi lain di bidang *mobile edge-cloud* juga mencakup komputasi multi-utas di awan untuk lebih mempercepat hasil inferensi keseluruhan. Bergantung pada awan untuk komputasi inferensi partisi kedua mengasumsikan konektivitas jaringan yang baik, yang dapat tidak pasti dengan konektivitas yang buruk dari beberapa penyebaran tepi terisolasi. Edgent mengadaptasi metodologi sebelumnya ke perangkat seluler dan server tepi yang tersedia, mengendurkan batasan pengalihan ke awan. Metode ini terkait dengan arsitektur pelatihan dan model tertentu, dan masih membatasi partisi menjadi dua bagian. Metode lain telah mempertimbangkan beberapa titik pemisahan, *contohnya*, IONN , yang menjelaskan masalah partisi untuk meminimalkan latensi dan konsumsi energi, juga mempertimbangkan waktu untuk mengunggah model ke server tepi. [[8]](javascript:void()) [[9]](javascript:void()) [[10]](javascript:void()) [[11]](javascript:void()) [[12]](javascript:void()) [[13]](javascript:void()) [[14]](javascript:void()) [[15]](javascript:void()) Metode-metode ini berinteraksi dengan awan jarak jauh, atau terbatas pada sifat partisi, *contohnya*, diharuskan membagi menjadi tepat dua bagian, dengan atau tanpa multi-threading. Tidak ada studi partisi DNN yang terdaftar yang mempertimbangkan beberapa titik pemisahan dan multi-threading. B. Kontribusi Makalah ini menyajikan kerangka kerja inferensi terdistribusi untuk memaksimalkan hasil inferensi komputasi DNN waktu nyata pada data aliran, dengan beberapa titik pemisahan dan partisi multi-utas. Kontribusi makalah ini adalah sebagai berikut: Model untuk memprediksi latensi komputasi dan transmisi DNN terdistribusi, di mana hasil inferensi dari skema partisi tertentu dapat diperkirakan. Formulasi masalah optimasi untuk partisi DNN, implementasi pemecah *branch and bound* untuk masalah ini, dan evaluasi kompleksitasnya. Simulasi untuk mengeksplorasi kemungkinan peningkatan kinerja dengan variasi properti jaringan dan DNN. Identifikasi wilayah deterministik dalam properti jaringan dan DNN yang mengarah pada keberadaan partisi optimal dan biaya untuk menghitung solusi tersebut, *yaitu*, kondisi di mana partisi DNN bermanfaat. Hasil eksperimental yang mengilustrasikan wilayah yang didefinisikan dalam simulasi, serta akurasi prediksi dan percepatan hasil inferensi akhir untuk lingkungan homogen dan heterogen. Selanjutnya dalam makalah ini, untuk menghindari kebingungan, jaringan saraf tiruan yang dipartisi akan disebut sebagai , dan istilah akan menunjukkan jaringan komunikasi fisik yang mendasarinya. DNN jaringan C. Garis Besar Makalah Sisa makalah ini diorganisir sebagai berikut. menyajikan latar belakang Pembelajaran Mendalam dan bagaimana DNN direpresentasikan dalam studi ini. merinci metode prediksi latensi inferensi dan transmisi yang diperlukan untuk yang mendefinisikan masalah optimasi, serta algoritma *branch and bound* untuk mengambil keputusan partisi. menyajikan hasil simulasi untuk mengukur kinerja dan kompleksitas algoritma *branch and bound*, serta kondisi yang mengarah pada keberadaan partisi yang meningkatkan hasil inferensi dalam jaringan homogen. menyajikan hasil eksperimental yang mengonfirmasi simulasi , dan menunjukkan peningkatan hasil inferensi pada pengaturan eksperimental heterogen. Akhirnya, membahas hasil dan memperluas penerapan metode ini secara lebih luas. Bagian II Bagian III Bagian IV Bagian V Bagian VI Bagian V Bagian VII BAGIAN II. Latar Belakang: Pembelajaran Mendalam Dalam bidang Pembelajaran Mesin, Pembelajaran Mendalam (DL) mengacu pada metode yang bergantung pada penggunaan DNN, *yaitu*, jaringan saraf tiruan (atau metode pembelajaran mesin terkait) yang mengandung lebih dari satu lapisan tersembunyi. Salah satu referensi paling awal tentang arsitektur pembelajaran mendalam diterbitkan pada tahun 1967 , tetapi baru pada tahun 2010-an DL mendapatkan daya tarik, pertama dalam pengenalan ucapan, kemudian dalam deteksi objek dalam gambar, karena kemampuannya menangkap hubungan kompleks dalam data berdimensi tinggi. Pembelajaran Mendalam diperkirakan mewakili sebagian besar aplikasi AI pada tahun 2022, dengan lebih dari 75% organisasi menggunakan DNN untuk aplikasi yang dapat menggunakan metode klasik. Metode DL telah didefinisikan sebagai "*teknik pembelajaran mesin di mana hipotesis berbentuk sirkuit aljabar kompleks dengan kekuatan koneksi yang dapat disesuaikan*" . Sirkuit aljabar ini biasanya diorganisir ke dalam lapisan, yang membentuk langkah-langkah dalam komputasi. Istilah merujuk pada algoritma yang terdiri dari lebih dari satu lapisan. [[16]](javascript:void()) 4 [[17]](javascript:void()) mendalam Ada dua struktur DNN utama: jaringan saraf *feed-forward* dan jaringan saraf rekuren. Kedua jenis DNN dapat direpresentasikan sebagai grafik komputasi, dengan perbedaan utama adalah bahwa jaringan *feed-forward* dapat direpresentasikan sebagai grafik asiklik langsung (DAG), sedangkan jaringan saraf rekuren mungkin mengandung siklus. Jaringan saraf rekuren dibangun untuk urutan data, di mana setiap titik data memiliki ketergantungan potensial dengan titik data sebelumnya dalam urutan, sedangkan jaringan saraf *feed-forward* tidak mempertimbangkan interaksi antar titik dalam urutan data. Selanjutnya dalam makalah ini akan dipertimbangkan kasus DNN *feed-forward*. 5 BAGIAN III. Pemodelan Inferensi Terdistribusi Bagian ini menyajikan model untuk merepresentasikan properti DNN dan jaringan untuk memprediksi latensi komputasi, latensi transmisi, dan hasil inferensi akhir dari solusi partisi tertentu. A. Representasi DNN dan Jaringan DNN *feed-forward* dengan N lapisan dimodelkan sebagai DAG GA=(L,E) dengan L=(L1,…,LL) lapisan DNN. Tepi (Li,Lj)∈E adalah koneksi antara lapisan Li dan Lj . Setiap lapisan Li memiliki konsumsi komputasi terkait ci , diukur dalam jumlah operasi *floating-point* yang diperlukan untuk menghitung lintasan maju melalui lapisan. Tepi (Li,Lj) diberi bobot si,j yang sesuai dengan ukuran data yang ditransmisikan antara lapisan Li dan Lj dalam byte. Jaringan fisik dimodelkan sebagai grafik terhubung penuh G=(N,V) di mana N=(N1,…,NN) adalah himpunan node komputasi dan V adalah himpunan tautan antar node. Diasumsikan bahwa node komputasi N1,…,NN memiliki tingkat pemrosesan η1,…,ηN , masing-masing, diukur dalam operasi *floating-point* per detik. Akhirnya, *throughput* tautan antara dua node yang berdekatan Na dan Nb ditandai sebagai θa,b , diukur dalam byte per detik. Setiap node Ni terhubung ke dirinya sendiri dengan *throughput* tak terbatas untuk mewakili tautan *loopback*, dan tautan diasumsikan simetris, *yaitu*, θa,b=θb,a . Partisi didefinisikan sebagai peta P:L→N , *yaitu*, partisi menetapkan nomor node ke setiap lapisan dalam DNN. Partisi dapat digambarkan sebagai matriks P berdimensi (N×L) , dengan N adalah jumlah node dalam jaringan dan L adalah jumlah lapisan DNN dan, dengan Pa,i=1 jika lapisan Li ditempatkan pada node Na , 0 jika tidak. Dengan contoh yang diberikan pada , L=7 lapisan dan N=2 node komputasi, partisi yang ditampilkan dengan lapisan {L1,L2,L3,L6,L7} pada node N1 , dan lapisan {L4,L5} pada node N2 , direpresentasikan sebagai: gambar 2 Mengingat partisi, *utas* didefinisikan sebagai sekelompok lapisan berurutan di antara dua titik pemisahan, yang dijalankan secara berurutan pada node yang sama. Dalam contoh di atas, node N1 akan menjalankan dua utas, yang pertama berisi lapisan {L1,L2,L3} dan yang kedua berisi {L6,L7} . Dengan notasi ini didefinisikan, sisa Bagian ini menurunkan ekspresi tertutup dari hasil inferensi yang dicapai oleh partisi tertentu, sebagai fungsi dari latensi inferensi (Bagian III-B) dan transmisi (Bagian III-C). B. Prediksi Latensi Inferensi Mengingat partisi, Bagian ini melihat prediksi latensi inferensi pada node yang terisolasi. Latensi yang disebabkan oleh komputasi lapisan Li dengan konsumsi ci , yang akan dihitung pada node Na , dengan tingkat pemrosesan ηa diungkapkan sebagai Tci(Na)=ci/ηa . Mengingat himpunan lapisan L′⊂L di semua utas yang berjalan pada node Na dengan tingkat pemrosesan ηa , latensi inferensi dapat diungkapkan sebagai: Ekspresi ini adalah perkiraan orde pertama dari estimasi latensi inferensi berdasarkan jumlah operasi *floating-point* (FLOP) yang diperlukan untuk memproses DNN, *yaitu*, jumlah operasi perkalian-penambahan dalam model. Estimasi latensi inferensi pada perangkat tepi dikomplikasi oleh optimasi waktu proses. Solusi yang ada seperti nn-Meter memprediksi latensi inferensi berdasarkan FLOP. Solusi lain mengandalkan tabel pencarian dengan waktu inferensi yang telah dihitung sebelumnya untuk inferensi latensi. Misalnya, BRP-NAS menggunakan jaringan konvolusional yang telah dilatih sebelumnya untuk memprediksi latensi inferensi, sambil memperhitungkan optimasi model waktu proses. [[18]](javascript:void()) [[19]](javascript:void()) Dalam , diasumsikan lebih lanjut bahwa prosesor menggunakan kapasitas penuhnya, yang menyiratkan bahwa prosesor multi-inti dimodelkan sebagai prosesor inti tunggal dengan tingkat pemrosesan yang sama dengan jumlah tingkat pemrosesan inti mereka. Juga diasumsikan bahwa sumber daya komputasi dibagi secara merata di antara utas, *yaitu*, prosesor mengalokasikan proporsi waktu yang sama untuk setiap utas. persamaan 1 Di semua node, utas dengan latensi tertinggi menetapkan hasil inferensi untuk DNN terdistribusi. Mengabaikan latensi transmisi, ini menyiratkan bahwa setelah utas pembatas ini selesai menghitung bingkai data, ia langsung memproses yang berikutnya. Utas lain akan memiliki waktu idle sebelum memproses bingkai data berikutnya karena latensi inferensinya lebih rendah dari latensi maksimum ini, seperti yang ditunjukkan pada . gambar 1 Mengingat matriks partisi P , latensi inferensi dapat diungkapkan sebagai vektor tunggal Tc berukuran N di mana komponen ke-a adalah latensi utas inferensi tertinggi pada node Na , *yaitu*, Tca=Tc(Na) : di mana H adalah matriks diagonal dari invers tingkat pemrosesan node diag(η−11,…,η−1N) dan c adalah vektor kolom dari konsumsi lapisan individu (c1,…,cL) . C. Prediksi Latensi Transmisi Latensi transmisi dapat diprediksi sebagai berikut: waktu yang dibutuhkan untuk mengirim jumlah data si,j antara lapisan Li dan Lj pada tepi (Na,Nb) melalui tautan dengan *throughput* terukur θa,b adalah Tti,j(Na,Nb)=si,j/θa,b . Waktu untuk mencapai transfer data si,j∈E′⊂E melalui tautan (Na,Nb) adalah: Serupa dengan prediksi latensi inferensi, ini menyiratkan bahwa tautan dibagi secara merata di antara transfer data dari Na ke Nb . Prediksi latensi transmisi bergantung pada estimasi *throughput* tautan antara node, lebih tepatnya *goodput*, *yaitu*, jumlah data berguna yang ditransmisikan per detik. Serupa dengan estimasi latensi inferensi, ini adalah perkiraan orde pertama, yang secara efisien menawarkan hasil prediksi yang baik, seperti yang ditunjukkan pada c, dengan koefisien korelasi R2=0.9998 . Kerugian dari metode ini adalah persyaratannya untuk menjenuhkan tautan untuk mendapatkan estimasi *throughput*. gambar 3 Mengingat matriks partisi P , matriks latensi transmisi Tt dapat didefinisikan sebagai matriks persegi berukuran L , dengan Tta,b=Tt(Na,Nb) : di mana ° adalah produk suku demi suku, atau produk Hadamard, Θ adalah matriks invers *throughput*, *yaitu*, matriks persegi berukuran N dengan Θa,b=θ−1a,b dan S adalah matriks ukuran transmisi, *yaitu*, matriks persegi berukuran L dengan Si,j=si,j jika Li mengirim data ke Lj , 0 jika tidak. BAGIAN IV. Partisi DNN Tujuan dari partisi DNN dalam studi ini adalah untuk memaksimalkan hasil inferensi, yang ditandai dengan C , yang sesuai dengan kebalikan dari latensi maksimum di antara semua latensi komputasi dan transmisi yang berbeda. Mengingat partisi P , hasil inferensi didefinisikan sebagai: Memaksimalkan hasil inferensi sama dengan menemukan *min-max* gabungan di antara semua suku dari Tc dan Tt . Ini dapat didefinisikan sebagai masalah optimasi diskrit: dengan Ji,j menjadi matriks semua-satu berukuran i×j , kondisi dan mengharuskan setiap lapisan ditempatkan pada satu dan hanya satu node. (6) (7) Masalah optimasi ini adalah masalah Pemrograman Non-linear Campuran Integer (MINLP). Matriks partisi dapat dilihat sebagai versi *one-hot encoded* dari vektor berukuran (1×L) dengan nilai dalam [[1,N]] . Masalah MINLP bersifat NP-hard, menyiratkan bahwa kompleksitas menemukan partisi DNN optimal adalah O(NL) karena setiap L lapisan dapat ditempatkan pada N node. Ada beberapa heuristik untuk mendapatkan solusi optimal atau sub-optimal untuk masalah ini dalam waktu yang lebih sedikit daripada algoritma *brute force*, *contohnya*, Algoritma Genetika (GA) , Optimasi Kawanan Partikel (PSO) , atau *Branch and Bound* (B&B) . Metodologi yang dipilih adalah implementasi B&B yang diadaptasi, yang disajikan pada . [[21]](javascript:void()) [[22]](javascript:void()) [[23]](javascript:void()) Bagian IV-A A. Algoritma Branch and Bound Bagian ini menyajikan adaptasi *branch and bound* (B&B) untuk masalah optimasi partisi DNN yang didefinisikan pada . Bagian IV Dalam algoritma B&B, ruang solusi direpresentasikan oleh sebuah pohon. Prosesnya terdiri dari menghilangkan seluruh cabang dalam pohon berdasarkan evaluasi skor node akar. Hal ini menyiratkan keberadaan topologi pohon yang menciptakan hubungan antara skor node dalam pohon dan batas pada skor semua daunnya. Representasi pohon dari ruang solusi ini mendukung penggunaan algoritma B&B dalam studi ini. Dengan asumsi ps adalah daftar parsial berukuran s , anak-anak dari node ps dalam topologi pohon adalah semua daftar yang dimulai dengan ps , *yaitu*, semua partisi di mana s lapisan pertama ditempatkan sesuai dengan ps . Node daun di bawah ps yang sesuai dengan ps yang diisi dengan nilai terakhir dari ps dilabeli ps~ . Misalnya, jika L=5 dan p2=(2,1) , maka p2~=(2,1,1,1,1) . Mengingat Ttmax=maxTt(ps~) nilai maksimum matriks latensi transmisi untuk partisi ps~ , semua node daun p di bawah ps akan memiliki latensi transmisi maksimum yang lebih tinggi daripada ps~ , *yaitu*, ∀p,maxTt(p)≥Ttmax . Hal ini dijelaskan oleh fakta bahwa mengingat partisi parsial, setiap perpindahan pada lapisan lain hanya akan menambah transfer data antar node. Selama proses pencarian partisi optimal p , yang memaksimalkan hasil inferensi C(p,GA,GN) , dan mengingat hasil yang dapat dicapai terbaik saat ini best_throughput , optimasi B&B terdiri dari menghilangkan seluruh cabang pohon yang mewakili ruang solusi dengan mengevaluasi waktu transmisi dalam partisi parsial. Proses ini memungkinkan optimasi B&B untuk dengan cepat menghilangkan banyak kasus dibandingkan dengan algoritma *brute force*. Misalnya, jika hasil antara node rendah dibandingkan dengan kapasitas komputasi, *yaitu*, dengan node yang terhubung melalui koneksi nirkabel *throughput* rendah, solusi optimal sering kali adalah menjaga semua komputasi pada satu node. Keunggulan algoritma B&B adalah ia berakhir setelah N operasi dalam kasus-kasus sederhana seperti itu dengan menghilangkan semua partisi parsial pada tahap pertama pohon. Sebaliknya, dalam kasus di mana tautan memiliki *throughput* yang lebih tinggi, kompleksitas B&B bisa lebih tinggi karena ia tidak dapat menghilangkan cabang besar. B. Kompleksitas Branch and Bound Beban tambahan yang disebabkan oleh jumlah total partisi dalam implementasi dunia nyata diabaikan dalam pendekatan ini. Latensi tambahan ini berkorelasi dengan jumlah total partisi. Dengan setiap partisi, transfer data dari Pengontrol Antarmuka Jaringan (NIC) ke memori menyebabkan latensi tambahan, terkait dengan *throughput* PCIe, *throughput* memori, dan ukuran data yang ditransfer. Dengan asumsi bahwa *throughput* transfer data dibatasi oleh *throughput* memori, evaluasi sederhana dari latensi ini akan mengubah latensi komputasi dalam menjadi: persamaan 1