Mengapa AI Anda Tidak Perlu Lagi Mengandalkan Cloud untuk Berjalan Lebih Cepat

Penulis: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Abstrak: Inferensi jaringan saraf tiruan dalam (DNN) pada data streaming memerlukan sumber daya komputasi untuk memenuhi persyaratan throughput inferensi. Namun, aplikasi pembelajaran mendalam yang sensitif terhadap latensi dan privasi tidak mampu mengalihkan 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 tetap di lingkungan yang terbatas, akselerasi 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 throughput inferensi (jumlah inferensi per detik). Makalah ini memperkenalkan metode untuk memprediksi latensi inferensi dan transmisi untuk penerapan DNN terdistribusi multi-utas, dan mendefinisikan proses optimasi untuk memaksimalkan throughput inferensi. Sebuah pemecah branch and bound kemudian disajikan dan dianalisis untuk mengukur kinerja dan kompleksitas yang dicapai. Analisis ini telah menyebabkan definisi wilayah akselerasi, yang menggambarkan kondisi deterministik pada properti DNN dan jaringan di mana partisi DNN bermanfaat. Akhirnya, hasil eksperimental mengkonfirmasi simulasi dan menunjukkan peningkatan throughput inferensi dalam penerapan tepi sampel. Partisi DNN di tepi memungkinkan akselerasi throughput inferensi sambil menurunkan penggunaan bandwidth dan latensi ke server terpusat, mis., 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 dapat mengatasi jumlah data yang terus bertambah, dalam berbagai bidang seperti deteksi objek dalam visi komputer, pengenalan wajah, pengenalan suara, pemrosesan bahasa alami, atau mengemudi otonom. AI, dan khususnya Pembelajaran Mendalam (DL), memerlukan, selain data dalam jumlah besar, kemampuan yang signifikan dalam daya 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, *misalnya*, dalam mengemudi otonom, pemantauan manufaktur, atau inferensi waktu nyata apa pun yang melibatkan interaksi dunia nyata. Misalnya, waktu respons rata-rata dalam mengemudi otonom diperlukan kurang dari 100 milidetik , membuat waktu bolak-balik ke awan terlalu lama untuk aplikasi semacam itu. Demikian pula, beberapa aplikasi dapat menimbulkan penggunaan tautan yang signifikan pada jaringan, *misalnya*, 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. Ini mendorong penerapan AI dalam komputasi tepi, yang terdiri dari memindahkan tugas komputasi dari pusat data lebih dekat ke perangkat tepi, *yaitu*, kedekatan dengan sumber data. [](javascript:void()) Dibandingkan dengan awan publik, tepi adalah lingkungan yang terbatas sumber dayanya dengan keterbatasan penting , dan oleh karena itu mengembangkan AI untuk tepi secara inheren berbeda dari mengembangkan AI untuk awan. Menganalisis data di dekat sumbernya bisa menjadi tantangan karena kapasitas perangkat yang lebih rendah, inelastisitas sumber daya yang tersedia, dan heterogenitas jaringan tepi. Menurunkan kapasitas komputasi berarti menurunkan throughput inferensi yang dapat dicapai, semakin mempersulit relokasi beban kerja berat dari awan ke tepi. Dalam beberapa aplikasi, throughput inferensi, *yaitu*, inferensi yang dapat dicapai per detik DNN, dapat dikaitkan dengan akurasi DNN, *misalnya*, dengan pelacakan objek dalam aliran video, di mana penurunan laju inferensi dari 15 menjadi 5 inferensi per detik telah terbukti menurunkan skor F1__3__ dari detektor objek sebesar 10% . Dengan kata lain, penerapan dengan throughput inferensi rendah dapat menyebabkan kehilangan informasi kritis, *misalnya*, kehilangan deteksi dalam aplikasi pengawasan video. [](javascript:void()) [](javascript:void()) Ada dua metode utama yang tersedia untuk memenuhi persyaratan kinerja pada jaringan tepi yang terbatas: kompresi model atau akselerasi perangkat keras. *Kompresi model* terdiri dari mengurangi dan mengoptimalkan jaringan saraf menjadi versi model yang ringan, seringkali berkinerja buruk. Metode kompresi model standar termasuk pemangkasan , *yaitu*, menghapus parameter yang tidak perlu dalam model, kuantisasi , *yaitu*, mengurangi memori yang dialokasikan 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 bagi akurasi model. *Akselerasi perangkat keras* pada perangkat tepi berarti menemukan perangkat keras yang efisien daya dan ringan, sambil tetap mampu menjalankan inferensi dengan kinerja yang memadai. Ada beberapa jenis perangkat keras kandidat untuk akselerasi di tepi, bervariasi dalam efisiensi dan kekhususan, tetapi unit pemrosesan standar gagal memenuhi harapan dan perangkat keras khusus seperti ASIC ditemukan tidak praktis dan mahal . [](javascript:void()) [](javascript:void()) [](javascript:void()) [](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 bersamaan dengan dua metode lainnya. Partisi DNN terdiri dari menganggap jaringan saraf sebagai pipeline untuk disegmentasi menjadi partisi, dan mendistribusikan partisi-partisi ini ke 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 berjalan, partisi dijalankan secara berurutan, masing-masing mengirimkan hasil inferensi perantara ke partisi berikutnya. Hal ini memungkinkan setiap partisi untuk mulai menghitung data masukan berikutnya sementara perangkat lain terus memproses yang dialihkan, sehingga meningkatkan throughput inferensi, seperti yang ditunjukkan pada . Di sisa makalah ini, partisi DNN diilustrasikan melalui contoh inferensi waktu nyata pada aliran video. gambar 1 A. Karya Terkait Metode untuk partisi DNN, yang berasal dari pengalihan cloud tepi seluler, berusaha untuk mengoptimalkan berbagai indikator kinerja, seperti latensi komputasi, konsumsi energi, pemanfaatan sumber daya, biaya, atau throughput. 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, menjaga partisi pertama di tepi dan mengalihkan partisi kedua ke awan, untuk meminimalkan latensi dan konsumsi energi. Aplikasi dalam IoT juga telah mempertimbangkan partisi gabungan dan pengalihan beberapa DNN untuk mengoptimalkan energi, penundaan, dan/atau biaya, menggunakan pemecah yang berbeda seperti SPSO-GA menggabungkan Particle Swarm Optimization (PSO) dan Genetics Algorithm (GA), atau DDPQN yang menggunakan Deep Reinforcement Learning untuk menemukan skema partisi. Contoh lain termasuk DINA , yang mendefinisikan masalah Integer Non Linear Programming (INLP), dan menggunakan pemecah berbasis teori pencocokan, untuk mengoptimalkan penundaan dan pemanfaatan sumber daya di jaringan kabut. Metode yang mengoptimalkan throughput 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 lainnya di awan. Studi lain di bidang cloud tepi seluler juga mencakup komputasi multi-utas di awan untuk lebih mempercepat throughput 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 penerapan 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, *misalnya*, IONN , yang menjelaskan masalah partisi untuk meminimalkan latensi dan konsumsi energi, juga mempertimbangkan waktu untuk mengunggah model ke server tepi. [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) Metode-metode ini baik berinteraksi dengan awan jarak jauh, atau terbatas pada sifat partisi, *misalnya*, diperlukan untuk 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 throughput inferensi komputasi DNN waktu nyata pada data streaming, 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 throughput inferensi yang diharapkan 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 akselerasi throughput inferensi akhir untuk lingkungan yang homogen dan heterogen. Untuk sisa makalah ini, untuk menghindari kebingungan, jaringan saraf tiruan yang dipartisi akan disebut sebagai , dan istilah akan merujuk pada jaringan komunikasi fisik yang mendasarinya. DNN jaringan C. Garis Besar Makalah Sisa makalah ini diatur 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 throughput inferensi di jaringan homogen. menyajikan hasil eksperimental yang mengkonfirmasi simulasi , dan menunjukkan peningkatan throughput inferensi pada pengaturan eksperimental heterogen. Akhirnya, membahas hasil dan memperluas penerapan yang lebih luas dari metode ini. Bagian II Bagian III Bagian IV Bagian V Bagian VI Bagian V Bagian VII BAGIAN II. Latar Belakang: Pembelajaran Mendalam Dalam bidang Machine Learning, Deep Learning (DL) mengacu pada metode yang mengandalkan penggunaan DNN, *yaitu*, jaringan saraf tiruan (atau metode pembelajaran mesin terkait) yang mengandung lebih dari satu lapisan tersembunyi. Salah satu referensi paling awal untuk arsitektur pembelajaran mendalam diterbitkan pada tahun 1967 , tetapi baru pada tahun 2010-an DL mendapatkan daya tarik, pertama dalam pengenalan suara, kemudian dalam deteksi objek dalam gambar, karena kemampuannya untuk menangkap hubungan kompleks dalam data berdimensi tinggi. Pembelajaran mendalam diperkirakan mewakili mayoritas 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 untuk pembelajaran mesin di mana hipotesis mengambil bentuk sirkuit aljabar kompleks dengan kekuatan koneksi yang dapat disesuaikan* " . Sirkuit aljabar ini biasanya diatur ke dalam lapisan, yang membentuk langkah-langkah dalam komputasi. Istilah *mendalam* mengacu pada algoritma yang terdiri dari lebih dari satu lapisan. [](javascript:void()) 4 [](javascript:void()) Ada dua struktur DNN utama: jaringan saraf maju (feed-forward) dan jaringan saraf berulang (recurrent). Kedua jenis DNN dapat direpresentasikan sebagai grafik komputasi, dengan perbedaan utama adalah bahwa jaringan maju dapat direpresentasikan sebagai grafik asiklik langsung (DAG), sementara jaringan saraf berulang mungkin mengandung siklus. Jaringan saraf berulang dibangun untuk urutan data, di mana setiap titik data memiliki ketergantungan potensial dengan titik data sebelumnya dalam urutan, sementara jaringan saraf maju tidak mempertimbangkan interaksi antar titik dalam urutan data. Sisa makalah ini akan mempertimbangkan kasus DNN maju. 5 BAGIAN III. Pemodelan Inferensi Terdistribusi Bagian ini menyajikan model untuk merepresentasikan properti DNN dan jaringan untuk memprediksi latensi komputasi, latensi transmisi, dan throughput inferensi akhir dari solusi partisi tertentu. A. Representasi DNN dan Jaringan DNN maju dengan N lapisan dimodelkan sebagai DAG GA=(L,E) dengan L=(L1,…,LL) lapisan-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) diberikan bobot si,j yang sesuai dengan ukuran data yang transit antara lapisan Li dan Lj dalam byte. Jaringan fisik dimodelkan sebagai grafik yang 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 laju pemrosesan η1,…,ηN , masing-masing, diukur dalam operasi floating-point per detik. Akhirnya, throughput tautan antara dua node yang berdekatan Na dan Nb ditunjukkan 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. Sebuah partisi dapat digambarkan sebagai matriks P berdimensi (N×L) , N adalah jumlah node di jaringan dan L adalah jumlah lapisan DNN dan, dengan Pa,i=1 jika lapisan Li ditempatkan pada node Na , 0 sebaliknya. 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 Diberikan partisi, *utas* didefinisikan sebagai kelompok 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 yang ditentukan ini, sisa Bagian ini menurunkan ekspresi tertutup dari throughput inferensi yang dicapai oleh partisi tertentu, sebagai fungsi dari latensi inferensi ( ) dan transmisi ( ). bagian III-B bagian III-C B. Prediksi Latensi Inferensi Diberikan partisi, Bagian ini melihat prediksi latensi inferensi pada node terisolasi. Latensi yang disebabkan oleh komputasi lapisan Li dengan konsumsi ci , yang akan dihitung pada node Na , dengan laju pemrosesan ηa diungkapkan sebagai Tci(Na)=ci/ηa . Diberikan himpunan lapisan L′⊂L di semua utas yang berjalan pada node Na dengan laju 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 berjalan. 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 saraf konvolusional yang telah dilatih sebelumnya untuk memprediksi latensi inferensi, sambil memperhitungkan optimasi model waktu berjalan. [](javascript:void()) [](javascript:void()) Dalam , lebih lanjut diasumsikan bahwa prosesor menggunakan kapasitas penuhnya, yang menyiratkan bahwa prosesor multi-inti dimodelkan sebagai prosesor inti tunggal dengan laju pemrosesan yang sama dengan jumlah laju pemrosesan intinya. Diasumsikan juga 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 menentukan throughput inferensi untuk DNN terdistribusi. Dengan mengabaikan latensi transmisi, ini menyiratkan bahwa setelah utas pembatas ini selesai menghitung bingkai data, ia langsung memproses bingkai 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 Diberikan matriks partisi P , latensi inferensi dapat diungkapkan sebagai vektor tunggal Tc berukuran N di mana komponen ke- a adalah latensi inferensi utas tertinggi pada node Na , *yaitu*, Tca=Tc(Na) : di mana H adalah matriks diagonal dari laju pemrosesan node terbalik 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: Mirip 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 yang berguna yang ditransmisikan per detik. Mirip 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 . Kekurangan metode ini adalah persyaratannya untuk menjenuhkan tautan untuk mendapatkan estimasi throughput. gambar 3 Diberikan 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 kebalikan 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 sebaliknya. BAGIAN IV. Partisi DNN Tujuan dari partisi DNN dalam studi ini adalah untuk memaksimalkan throughput inferensi, yang ditunjukkan oleh C , yang sesuai dengan kebalikan dari latensi maksimum di antara semua latensi komputasi dan transmisi yang berbeda. Diberikan partisi P , throughput inferensi didefinisikan sebagai: Memaksimalkan throughput inferensi sama dengan menemukan min-max gabungan di antara semua suku Tc dan Tt . Ini dapat didefinisikan sebagai masalah optimasi diskrit: dengan Ji,j adalah matriks semua-satu berukuran i×j , kondisi dan memerlukan bahwa setiap lapisan ditempatkan pada satu dan hanya satu node. (6) (7) Masalah optimasi ini adalah masalah Mixed Integer Non-linear Programming (MINLP). Matriks partisi dapat dilihat sebagai versi one-hot encoded dari vektor berukuran (1×L) dengan nilai dalam [[1,N]] . Masalah MINLP adalah 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 lebih singkat daripada algoritma brute force, *misalnya*, Genetic Algorithms (GA) , Particle Swarm Optimization (PSO) , atau Branch and Bound (B&B) . Metodologi yang dipilih adalah implementasi B&B yang diadaptasi, yang disajikan pada . [](javascript:void()) [](javascript:void()) [](javascript:void()) Bagian IV-A A. Algoritma Branch and Bound Bagian ini menyajikan adaptasi branch and bound (B&B) ke masalah optimasi partisi DNN yang didefinisikan pada . Bagian IV Dalam algoritma B&B, ruang solusi direpresentasikan oleh pohon. Prosesnya terdiri dari menghilangkan seluruh cabang di pohon berdasarkan evaluasi skor node akar. Ini menyiratkan keberadaan topologi pohon yang menciptakan hubungan antara skor node di 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) . Diberikan 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 . Ini dijelaskan oleh fakta bahwa mengingat partisi parsial, setiap perpindahan pada lapisan lain hanya akan menambah transfer data antar node. Selama proses mencari partisi optimal p , yang memaksimalkan throughput inferensi C(p,GA,GN) , dan mengingat throughput 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 throughput antar node rendah dibandingkan dengan kapasitas komputasi, *misalnya*, dengan node yang terhubung melalui koneksi nirkabel throughput rendah, solusi optimal seringkali adalah menjaga semua komputasi pada satu node. Keuntungan algoritma B&B adalah ia berakhir setelah N operasi dalam 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 tidak akan dapat menghilangkan cabang besar. B. Kompleksitas Branch and Bound Overhead 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 Network Interface Controller (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 simplistik dari latensi ini akan mengubah latensi komputasi dalam menjadi: persamaan 1 Dalam ekspresi ini, ν adalah throughput memori, *yaitu*, kecepatan baca/tulis dari dan ke memori, dan (i,j)∈C adalah semua lapisan&