Mengapa AI Anda Tidak Lagi Membutuhkan Cloud untuk Berjalan Lebih Cepat

Penulis: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Abstrak: Inferensi jaringan saraf 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 melakukan offload komputasi ke cloud jarak jauh karena biaya transmisi yang tersirat dan kurangnya kepercayaan pada penyedia cloud pihak ketiga. Di antara solusi untuk meningkatkan kinerja sambil menjaga komputasi 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 edge yang tersedia, dengan mempertimbangkan properti jaringan edge 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 solver branch and bound kemudian disajikan dan dianalisis untuk mengukur kinerja dan kompleksitas yang dicapai. Analisis ini telah menghasilkan definisi wilayah akselerasi, yang menjelaskan kondisi deterministik pada properti DNN dan jaringan di mana partisi DNN bermanfaat. Akhirnya, hasil eksperimental mengkonfirmasi simulasi dan menunjukkan peningkatan throughput inferensi dalam penerapan edge sampel. Partisi DNN di edge memungkinkan akselerasi throughput inferensi sambil menurunkan penggunaan bandwidth dan latensi ke server terpusat, mis., di cloud. Pendahuluan Perangkat yang terhubung menghasilkan perkiraan 2,5 quintiliun 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 suara, pemrosesan bahasa alami, atau mengemudi otonom. AI, dan khususnya Pembelajaran Mendalam (DL), memerlukan, selain sejumlah besar data, kemampuan yang signifikan dalam kekuatan pemrosesan dan memori, yang menjadikan komputasi cloud sebagai solusi hosting untuk beban kerja AI. Akibatnya, pada tahun 2019, 96% tugas AI dijalankan di cloud. 1 de facto 2 Aplikasi AI dapat memiliki batasan latensi yang kuat, , 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 pulang-pergi ke cloud terlalu lama untuk aplikasi tersebut. Demikian pula, beberapa aplikasi dapat menimbulkan penggunaan tautan yang signifikan pada jaringan, , dalam kasus pemrosesan video berkualitas tinggi dalam visi komputer, yang mencegahnya berjalan di cloud. Kebijakan privasi data atau peraturan perlindungan data juga dapat melarang data meninggalkan lingkungan tertentu. Hal ini mendorong penerapan AI di edge computing, yang terdiri dari memindahkan tugas komputasi dari pusat data lebih dekat ke perangkat edge, , berdekatan dengan sumber data. misalnya [](javascript:void()) misalnya yaitu Dibandingkan dengan cloud publik, edge adalah lingkungan yang terbatas sumber dayanya dengan batasan penting , dan mengembangkan AI untuk edge oleh karena itu secara intrinsik berbeda dari mengembangkan AI untuk cloud. Menganalisis data di dekat sumbernya bisa menjadi tantangan karena kapasitas perangkat yang lebih rendah, inelastisitas sumber daya yang tersedia, dan heterogenitas jaringan edge. Menurunkan kapasitas komputasi berarti menurunkan throughput inferensi yang dapat dicapai, semakin mempersulit relokasi beban kerja berat dari cloud ke edge. Dalam beberapa aplikasi, throughput inferensi, , inferensi yang dapat dicapai per detik dari DNN, dapat dikaitkan dengan akurasi DNN, , dengan pelacakan objek dalam aliran video, di mana menurunkan laju inferensi dari 15 menjadi 5 inferensi per detik telah terbukti menurunkan skor F1__3__ pendeteksi objek sebesar 10% . Dengan kata lain, penerapan dengan throughput inferensi rendah dapat menyebabkan kehilangan informasi kritis, , kehilangan deteksi dalam aplikasi pengawasan video. [](javascript:void()) yaitu misalnya [](javascript:void()) misalnya Ada dua metode utama yang tersedia untuk memenuhi persyaratan kinerja pada jaringan edge yang terbatas: kompresi model atau akselerasi perangkat keras. terdiri dari mengurangi dan mengoptimalkan jaringan saraf menjadi versi model yang ringan, seringkali berkinerja buruk. Metode kompresi model standar termasuk pemangkasan , , menghapus parameter yang tidak perlu dalam model, kuantisasi , , mengurangi memori yang dialokasikan untuk menyimpan model, dan distilasi pengetahuan , , 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. pada perangkat edge menyiratkan pencarian perangkat keras yang hemat daya dan ringan, sambil tetap mampu menjalankan inferensi dengan kinerja yang memadai. Ada beberapa jenis perangkat keras kandidat untuk akselerasi di edge, bervariasi dalam efisiensi dan kekhususan, tetapi unit pemrosesan standar gagal memenuhi harapan dan perangkat keras khusus seperti ASIC ditemukan tidak praktis dan mahal . Kompresi model [](javascript:void()) yaitu [](javascript:void()) yaitu [](javascript:void()) yaitu Akselerasi perangkat keras [](javascript:void()) Partisi DNN adalah metode pelengkap untuk mempercepat inferensi dengan memanfaatkan banyaknya perangkat yang ada di jaringan edge untuk mendistribusikan komputasi inferensi– yang dapat digunakan sendiri, atau bersama dengan dua metode lainnya. Partisi DNN terdiri dari menganggap jaringan saraf sebagai pipa untuk disegmentasi menjadi partisi, dan mendistribusikan partisi-partisi ini pada perangkat edge. Penempatan partisi ini didasarkan pada karakteristik DNN dan jaringan yang mendasarinya. Partisi DNN bergantung pada identifikasi titik pemisahan, yang merupakan titik dalam grafik model di mana model dipisahkan menjadi partisi. Selama runtime, 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 melanjutkan pemrosesan 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. Pekerjaan Terkait Metode partisi DNN, yang berasal dari offloading edge-cloud seluler, berupaya mengoptimalkan berbagai indikator kinerja, seperti latensi komputasi, konsumsi energi, utilisasi 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 edge dan melakukan offloading partisi kedua ke cloud, untuk meminimalkan latensi dan konsumsi energi. Aplikasi di IoT juga telah mempertimbangkan partisi dan offloading gabungan dari beberapa DNN untuk mengoptimalkan energi, penundaan, dan/atau biaya, menggunakan berbagai solver seperti SPSO-GA menggabungkan Optimasi Kawanan Partikel (PSO) dan Algoritma Genetik (GA), atau DDPQN yang menggunakan Pembelajaran Penguatan Dalam untuk menemukan skema partisi. Contoh lain termasuk DINA , yang mendefinisikan masalah Pemrograman Non-Linear Integer (INLP), dan menggunakan solver berbasis teori pencocokan, untuk mengoptimalkan penundaan dan utilisasi sumber daya di jaringan kabut. Metode yang mengoptimalkan throughput inferensi termasuk bedah DNN , yang menggunakan ukuran keluaran lapisan DNN perantara yang lebih kecil untuk mempartisi komputasi inferensi antara edge dan cloud. Kedua algoritma membuat dua partisi, satu di edge dan yang lainnya di cloud. Studi lain di bidang edge-cloud seluler juga mencakup komputasi multi-utas di cloud untuk lebih mempercepat throughput inferensi secara keseluruhan. Bergantung pada cloud untuk komputasi inferensi partisi kedua mengasumsikan konektivitas jaringan yang baik, yang dapat tidak pasti dengan konektivitas yang buruk dari beberapa penerapan edge yang terisolasi. Edgent mengadaptasi metodologi sebelumnya ke perangkat seluler dan server edge yang tersedia, mengendurkan batasan offloading ke cloud. Metode ini terkait dengan arsitektur pelatihan dan model tertentu, dan masih membatasi partisi menjadi dua partisi. Metode lain telah mempertimbangkan beberapa titik pemisahan, , IONN , yang menjelaskan masalah partisi untuk meminimalkan latensi dan konsumsi energi, juga mempertimbangkan waktu untuk mengunggah model ke server edge. [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) misalnya [](javascript:void()) Metode-metode ini baik berinteraksi dengan cloud jarak jauh, atau terbatas dalam sifat partisinya, , diharuskan terbagi menjadi tepat dua bagian, dengan atau tanpa multi-threading. Tidak ada studi partisi DNN yang terdaftar yang mempertimbangkan beberapa titik pemisahan dan multi-threading. misalnya 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 solver 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, , kondisi di mana partisi DNN bermanfaat. yaitu Hasil eksperimental yang mengilustrasikan wilayah yang ditentukan dalam simulasi, serta akurasi prediksi dan percepatan throughput inferensi akhir untuk lingkungan homogen dan heterogen. Untuk sisa makalah ini, untuk menghindari kebingungan, jaringan saraf dalam 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 throughput inferensi di jaringan homogen. menyajikan hasil eksperimental yang mengonfirmasi 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 Pembelajaran Mesin, Pembelajaran Mendalam (DL) merujuk pada metode yang bergantung pada penggunaan DNN, , jaringan saraf tiruan (atau metode pembelajaran mesin terkait) yang berisi 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 suara, 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 “ ” . Sirkuit aljabar ini biasanya diorganisir menjadi lapisan, yang membentuk langkah-langkah dalam komputasi. Istilah merujuk pada algoritma yang terdiri dari lebih dari satu lapisan. yaitu [](javascript:void()) 4 teknik untuk pembelajaran mesin di mana hipotesis mengambil bentuk sirkuit aljabar kompleks dengan kekuatan koneksi yang dapat disesuaikan [](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 berisi siklus. Jaringan saraf rekuren dibangun untuk urutan data, di mana setiap titik data memiliki potensi ketergantungan dengan titik data sebelumnya dalam urutan, sementara jaringan saraf feed-forward tidak mempertimbangkan interaksi antar titik dalam urutan data. Sisa makalah ini akan mempertimbangkan kasus DNN feed-forward. 5 BAGIAN III. Pemodelan Inferensi Terdistribusi Bagian ini menyajikan model untuk merepresentasikan properti DNN dan jaringan guna memprediksi latensi komputasi, latensi transmisi, dan throughput inferensi akhir dari solusi partisi tertentu. A. Representasi DNN dan Jaringan DNN feed-forward dari N lapisan dimodelkan sebagai DAG GA=(L,E) dengan L=(L1,…,LL) adalah 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) diberi 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 dengan dirinya sendiri dengan throughput tak terbatas untuk mewakili tautan loopback, dan tautan diasumsikan simetris, , θa,b=θb,a . yaitu Partisi didefinisikan sebagai pemetaan P:L→N , , partisi menetapkan nomor node ke setiap lapisan dalam DNN. 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: yaitu gambar 2 Diberikan sebuah partisi, sebuah didefinisikan sebagai sekelompok lapisan berurutan di antara dua titik pemisahan, 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} . utas Dengan notasi yang didefinisikan 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 sebuah 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 laju pemrosesan ηa diekspresikan 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 diekspresikan sebagai: Ekspresi ini adalah perkiraan urutan pertama dari perkiraan latensi inferensi berdasarkan jumlah operasi floating-point (FLOP) yang diperlukan untuk memproses DNN, , jumlah operasi perkalian-penjumlahan dalam model. yaitu Estimasi latensi inferensi pada perangkat edge dipersulit oleh optimasi runtime. 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 mempertimbangkan optimasi model runtime. [](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 sama dengan jumlah laju pemrosesan intinya. Juga diasumsikan bahwa sumber daya komputasi dibagi secara merata di antara utas, , prosesor mengalokasikan proporsi waktu yang sama untuk setiap utas. persamaan 1 yaitu 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 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 Diberikan matriks partisi P , latensi inferensi dapat diekspresikan sebagai vektor tunggal Tc berukuran N di mana komponen ke- a adalah latensi inferensi utas tertinggi pada node Na , , Tca=Tc(Na) : yaitu di mana H adalah matriks diagonal dari laju pemrosesan node terbalik diag(η−11,…,η−1N) dan c adalah vektor kolom dari konsumsi lapisan individual (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 edge (Na,Nb) melalui tautan dengan throughput yang 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 antara transfer data dari Na ke Nb . Prediksi latensi transmisi bergantung pada estimasi throughput tautan antara node, lebih tepatnya , , jumlah data berguna yang ditransmisikan per detik. goodput yaitu Mirip dengan estimasi latensi inferensi, ini adalah perkiraan urutan pertama, yang secara efisien memberikan 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 terbalik throughput, , matriks persegi berukuran N dengan Θa,b=θ−1a,b dan S adalah matriks ukuran transmisi, , matriks persegi berukuran L dengan Si,j=si,j jika Li mengirim data ke Lj , 0 jika sebaliknya. yaitu yaitu BAGIAN IV. Partisi DNN Tujuan dari partisi DNN dalam studi ini adalah untuk memaksimalkan throughput inferensi, ditunjukkan oleh C , yang sesuai dengan kebalikan dari latensi maksimum di antara semua latensi komputasi dan transmisi yang berbeda. Diberikan sebuah 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 pengkodean one-hot 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 singkat daripada algoritma brute force, , Algoritma Genetik (GA) , Optimasi Kawanan Partikel (PSO) , atau Branch and Bound (B&B) . Metodologi yang dipilih adalah implementasi B&B yang diadaptasi, yang disajikan pada . misalnya [](javascript:void()) [](javascript:void()) [](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 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 , , 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~ , , ∀p,maxTt(p)≥Ttmax . Hal ini dijelaskan oleh fakta bahwa mengingat partisi parsial, setiap perpindahan pada lapisan lain hanya akan menambahkan transfer data antar node. yaitu yaitu Selama proses pencarian partisi optimal p , yang memaksimalkan throughput inferensi C(p,GA,GN) , dan diberikan throughput terbaik yang dapat dicapai 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, , 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 berhenti 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 ia tidak dapat menghilangkan cabang besar. misalnya 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 sederhana dari latensi ini akan mengubah latensi komputasi dalam menjadi: persamaan 1