Neden Yapay Zekanızın Artık Daha Hızlı Çalışmak İçin Buluta İhtiyacı Yok

Yazarlar: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Özet: Akış verileri üzerinde derin sinir ağı (DNN) çıkarımı, çıkarım verimliliği gereksinimlerini karşılamak için bilgi işlem kaynakları gerektirir. Ancak, gecikme ve gizlilik açısından hassas derin öğrenme uygulamaları, zımni iletim maliyeti ve üçüncü taraf bulut sağlayıcılarına güven eksikliği nedeniyle hesaplamayı uzak bulutlara boşaltamaz. Kısıtlı bir ortamda hesaplamayı tutarken performansı artırmaya yönelik çözümler arasında, donanım hızlandırma zahmetli olabilir ve model optimizasyonu kapsamlı tasarım çabaları gerektirirken doğruluğu engeller. DNN bölümlemesi, üçüncü bir tamamlayıcı yaklaşımdır ve çıkarım iş yükünü, çıkarım verimliliğini (saniye başına çıkarım sayısı) en üst düzeye çıkarma hedefiyle kenar ağının özelliklerini ve DNN yapısını dikkate alarak birkaç mevcut kenar cihazına dağıtmaktan oluşur. Bu makale, çok iş parçacıklı dağıtılmış DNN dağıtımları için çıkarım ve iletim gecikmelerini tahmin etme yöntemini tanıtmaktadır ve çıkarım verimliliğini en üst düzeye çıkarmak için bir optimizasyon süreci tanımlar. Daha sonra, elde edilen performansı ve karmaşıklığı ölçmek için bir dallanma ve sınırlama çözücüsü sunulur ve analiz edilir. Bu analiz, DNN bölümlemesinin faydalı olduğu durumlarda DNN ve ağ özelliklerindeki deterministik koşulları açıklayan hızlandırma bölgesinin tanımına yol açmıştır. Son olarak, deneysel sonuçlar simülasyonları doğrulamakta ve örnek kenar dağıtımlarında çıkarım verimliliği iyileştirmeleri göstermektedir. Kenardaki DNN bölümlemesi, çıkarım verimliliğini hızlandırırken bant genişliği kullanımını ve merkezi sunuculara (örneğin, buluta) olan gecikmeyi düşürür. Giriş Bağlı cihazlar, 2020'de günde tahmini olarak 2.5 kentilyon bayt veri üretti. Bu bağlamda, Yapay Zeka (YZ), nesne tespiti gibi bilgisayarlı görü alanlarında, yüz tanıma, konuşma tanıma, doğal dil işleme veya otonom sürüş gibi çok çeşitli alanlarda giderek artan veri miktarıyla en iyi şekilde başa çıkabilen teknolojilerden biridir. YZ, özellikle Derin Öğrenme (DÖ), büyük veri miktarlarına ek olarak önemli işlem gücü ve bellek yetenekleri gerektirir, bu da bulut bilişimini YZ iş yükleri için fiili barındırma çözümü haline getirir. Sonuç olarak, 2019'da YZ görevlerinin %96'sı bulutta çalıştırıldı. 1 2 YZ uygulamaları, otonom sürüş, üretim izleme veya gerçek dünya etkileşimi içeren herhangi bir gerçek zamanlı çıkarım gibi güçlü gecikme kısıtlamalarına sahip olabilir. Örneğin, otonom sürüşte ortalama yanıt sürelerinin 100 milisaniyenin altında olması gerekir , bu da buluta gidiş-dönüş sürelerini bu tür uygulamalar için çok uzun hale getirir. Benzer şekilde, bazı uygulamalar ağda önemli bir bağlantı kullanımı getirebilir, örneğin bilgisayarlı görü alanında yüksek kaliteli video işleme durumunda, bu da onların bulutta çalışmasını engeller. Veri gizliliği politikaları veya veri koruma düzenlemeleri de verilerin belirli ortamlardan ayrılmasını yasaklayabilir. Bu, hesaplama görevlerini veri merkezlerinden kenar cihazlarına daha yakın, yani veri kaynaklarına yakın bir yere taşıyan kenar bilişimi teşvik eder. [](javascript:void()) Genel bulutlarla karşılaştırıldığında, kenar, önemli sınırlamalara sahip kaynak kısıtlı bir ortamdır , ve bu nedenle kenar için YZ geliştirmek bulut için YZ geliştirmekten temelden farklıdır. Verilerin kaynağına yakın analiz edilmesi, daha düşük cihaz kapasiteleri, mevcut kaynakların esnek olmaması ve kenar ağlarının heterojenliği nedeniyle zor olabilir. Hesaplama kapasitesini düşürmek, elde edilebilir çıkarım verimliliğini düşürmek anlamına gelir ve buluttan kenara ağır iş yüklerinin taşınmasını daha da karmaşık hale getirir. Bazı uygulamalarda, çıkarım verimliliği, yani bir DNN'nin saniyede elde edilebilen çıkarım sayısı, DNN doğruluğu ile ilişkilendirilebilir, örneğin video akışlarındaki nesne takibinde, çıkarım hızını saniyede 15'ten 5 çıkarıma düşürmenin bir nesne dedektörünün F1 puanını %10 düşürdüğü gösterilmiştir__3__ . Başka bir deyişle, düşük çıkarım verimliliğine sahip dağıtımlar kritik bilgi kaybına neden olabilir, örneğin video gözetim uygulamalarında tespitlerin kaybı. [](javascript:void()) [](javascript:void()) Kısıtlı kenar ağlarında performans gereksinimlerini karşılamak için iki ana yöntem mevcuttur: model sıkıştırma veya donanım hızlandırma. , sinir ağlarını hafif, genellikle düşük performanslı bir model versiyonuna indirmeyi ve optimize etmeyi içerir. Standart model sıkıştırma yöntemleri arasında budama , yani modeldeki gereksiz parametrelerin kaldırılması, niceleme , yani modeli depolamak için ayrılan belleğin azaltılması ve bilgi damıtma , yani daha büyük bir sinir ağından çıkarılan bilgiyle daha küçük bir sinir ağının eğitilmesi yer alır. Model optimizasyonu kapsamlı tasarım çabaları gerektirir ve model doğruluğu için bir engel olabilir. kenar cihazlarında, hem güç verimli hem de hafif olan, ancak yine de yeterli performansla çıkarım çalıştırabilen donanımı bulmayı içerir. Kenarda hızlandırma için çeşitli türde donanım adayı vardır, verimlilik ve özgüllük açısından farklılık gösterir, ancak standart işlem birimleri beklentileri karşılamakta başarısız olur ve ASIC'ler gibi özel donanımların pratik olmadığı ve pahalı olduğu bulunmuştur . Model sıkıştırma [](javascript:void()) [](javascript:void()) [](javascript:void()) Donanım hızlandırma [](javascript:void()) DNN bölümlemesi, çıkarım hızlandırması için tamamlayıcı bir yöntemdir ve çıkarım hesaplamasını dağıtmak üzere kenar ağlarının çokluğunu kullanarak (yalnızca kullanılabilir veya diğer iki yöntemle birlikte kullanılabilir). DNN bölümlemesi, bir sinir ağını bölümlemelere ayırabilen bir boru hattı olarak kabul etmeyi ve bu bölümleri kenar cihazlarına dağıtmayı içerir. Bu bölümlerin yerleşimi hem DNN hem de alttaki ağ özelliklerine dayanır. DNN bölümlemesi, modelin bölümlere ayrıldığı model grafiğindeki noktalar olan bölünme noktalarının tanımlanmasına dayanır. Çalışma zamanı sırasında, bölümler sıralı olarak çalıştırılır, her biri ara çıkarım sonuçlarını bir sonraki bölüme gönderir. Bu, her bölümün bir sonraki girdi verilerini işlemeye başlamasına olanak tanırken, diğer cihazlar boşaltılan verileri işlemeye devam eder, böylece 'de gösterildiği gibi çıkarım verimliliğini artırır. Bu makalenin geri kalanında, DNN bölümlemesi video akışlarındaki gerçek zamanlı çıkarım örneğiyle gösterilmektedir. şekil 1 A. İlgili Çalışmalar Mobil kenar-bulut boşaltımından türetilen DNN bölümlemesi yöntemleri, hesaplama gecikmesi, enerji tüketimi, kaynak kullanımı, maliyet veya verimlilik gibi çeşitli performans göstergelerini optimize etmeyi hedefler. DNN bölümlemesi, bir optimizasyon hedefi tanımlamak için bu metriklerden bir veya birkaçının ilişkilendirilmesine ve bölümleme şemalarını bulmak için bu metriği kullanan bir yönteme dayanır. Örneğin, Neurosurgeon gecikmeyi ve enerji tüketimini en aza indirmek için tek bir bölünme noktası arar, ilk bölümü kenarda tutar ve ikinci bölümü buluta boşaltır. IoT uygulamaları ayrıca enerji, gecikme ve/veya maliyeti optimize etmek için SPSO-GA Parçacık Sürü Optimizasyonu (PSO) ve Genetik Algoritma (GA) birleştiren veya bölümleme şemalarını bulmak için Derin Pekiştirme Öğrenmesini kullanan DDPQN gibi farklı çözücüler kullanarak birden fazla DNN'nin ortak bölümlemesini ve boşaltılmasını dikkate almıştır. Diğer örnekler arasında DINA , bir Tamsayı Doğrusal Olmayan Programlama (INLP) problemi tanımlayan ve sis ağlarında gecikme ve kaynak kullanımını optimize etmek için eşleştirme teorisi tabanlı bir çözücü kullanan yer alır. Çıkarım verimliliğini optimize eden yöntemler arasında, ara DNN katman çıktıların düşük boyutunu kullanarak kenar ve bulut arasında çıkarım hesaplamasını bölümlendiren DNN cerrahisi yer alır. Her iki algoritma da biri kenarda, diğeri bulutta olmak üzere iki bölüm oluşturur. Mobil kenar-bulut alanındaki diğer çalışmalar, genel çıkarım verimliliğini daha da hızlandırmak için bulutta çok iş parçacıklı hesaplamayı da içermektedir. İkinci bölüm çıkarım hesaplaması için buluta güvenmek, bazı izole kenar dağıtımlarıyla belirsiz olabilen iyi ağ bağlantısı varsayar. Edgent önceki metodolojiyi mobil cihazlara ve mevcut kenar sunucularına uyarlar ve buluta boşaltma kısıtlamasını gevşetir. Bu yöntem belirli bir eğitime ve model mimarisine bağlıdır ve bölümlemeyi hala iki bölüme sınırlar. Diğer yöntemler birden fazla bölünme noktası dikkate almıştır, örneğin IONN , gecikmeyi ve enerji tüketimini en aza indirmek için bölümlemeyi, aynı zamanda modellerin kenar sunucularına yüklenme süresini de dikkate alarak tanımlar. [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) Bu yöntemler ya uzak bulutlarla etkileşim kurar ya da bölümlemenin doğasıyla sınırlıdır, örneğin tam olarak iki parçaya bölünme gerekliliği, çok iş parçacıklı olsun veya olmasın. Listelenen DNN bölümlemesi çalışmalarının hiçbiri hem birden fazla bölünme noktası hem de çok iş parçacıklığı dikkate almamıştır. B. Katkılar Bu makale, birden fazla bölünme noktası ve çok iş parçacıklı bölümleme ile akış verileri üzerinde gerçek zamanlı DNN hesaplamasının çıkarım verimliliğini en üst düzeye çıkarmak için dağıtılmış bir çıkarım çerçevesi sunmaktadır. Bu makalenin katkıları şunlardır: Verilen bir bölümleme şemasının beklenen çıkarım verimliliğinin tahmin edilebileceği dağıtılmış bir DNN'nin hesaplama ve iletim gecikmelerini hesaplamak için bir model. DNN bölümlemesi için optimizasyon probleminin formülasyonu, bu problem için bir dallanma ve sınırlama çözücüsünün uygulanması ve karmaşıklığının değerlendirilmesi. Farklı ağ ve DNN özellikleriyle olası performans iyileştirmelerini araştırmak için simülasyonlar. Optimal bölümlemelerin varlığına yol açan ağ ve DNN özelliklerindeki deterministik bölgelerin tanımlanması ve bu çözümleri hesaplama maliyeti, yani DNN bölümlemesinin faydalı olduğu koşullar. Simülasyonlarda tanımlanan bölgeleri, ayrıca tahmin doğruluğunu ve homojen ve heterojen ortamlarda nihai çıkarım verimliliği hızlandırmasını gösteren deneysel sonuçlar. Bu makalenin geri kalanında kafa karışıklığını önlemek için, bölümlenmiş derin sinir ağı olarak, fiziksel iletişim ağı ise olarak anılacaktır. DNN ağ C. Makale Taslağı Bu makalenin geri kalanı aşağıdaki gibi düzenlenmiştir. Derin Öğrenme'nin arka planını ve bu çalışmada DNN'lerin nasıl temsil edildiğini sunmaktadır. çıkarım ve iletim gecikmesi tahmin yöntemlerini ayrıntılı olarak ele almaktadır; bu yöntemler için gereklidir, bu bölüm optimizasyon problemini ve bölümleme kararları almak için dallanma ve sınırlama algoritmasını tanımlar. dallanma ve sınırlama algoritmasının performansını ve karmaşıklığını ölçmek için simülasyon sonuçlarını ve homojen bir ağda çıkarım verimliliğini artıran bir bölümleme varlığına yol açan koşulları sunmaktadır. deneysel sonuçları sunmaktadır; bu sonuçlar 'teki simülasyonları doğrulamakta ve heterojen bir deneysel kurulumda çıkarım verimliliği iyileştirmelerini göstermektedir. Son olarak, sonuçları tartışmakta ve bu yöntemin daha geniş uygulanabilirliğini açıklamaktadır. Bölüm II Bölüm III Bölüm IV Bölüm V Bölüm VI Bölüm V Bölüm VII BÖLÜM II. Arka Plan: Derin Öğrenme Makine Öğrenmesi alanında Derin Öğrenme (DÖ), birden fazla gizli katman içeren DNN'lere, yani yapay sinir ağlarına (veya ilgili makine öğrenmesi yöntemlerine) dayanan yöntemlere atıfta bulunur. Derin öğrenme mimarilerine ilişkin en eski referanslardan biri 1967'de yayınlanmıştır , ancak DÖ'nün ilk olarak konuşma tanımada, ardından görüntüdeki nesne tespitinde, yüksek boyutlu verilerdeki karmaşık ilişkileri yakalama yeteneği nedeniyle ilgi görmesi 2010'lara kadar olmamıştır. Derin Öğrenme'nin 2022'de YZ uygulamalarının çoğunluğunu oluşturduğu tahmin edilmektedir; kuruluşların %75'inden fazlası, klasik yöntemlerin kullanılabileceği uygulamalar için DNN'ler kullanmaktadır. DÖ yöntemleri, “ ” olarak tanımlanmıştır . Bu cebirsel devreler genellikle hesaplama adımlarını oluşturan katmanlar halinde düzenlenir. terimi, birden fazla katman içeren algoritmalara atıfta bulunur. [](javascript:void()) 4 hipotezlerin ayarlanabilir bağlantı gücüne sahip karmaşık cebirsel devreler biçimini aldığı makine öğrenmesi teknikleri [](javascript:void()) Derin İki ana DNN yapısı vardır: ileri beslemeli sinir ağları ve tekrarlayan sinir ağları. Her iki DNN türü de hesaplama grafikleri olarak temsil edilebilir, aralarındaki temel fark, ileri beslemeli ağların doğrudan devirsiz grafikler (DAG'ler) olarak temsil edilebilmesi, tekrarlayan sinir ağlarının ise döngüler içerebilmesidir. Tekrarlayan sinir ağları, her veri noktasının dizideki önceki veri noktalarıyla potansiyel bir bağımlılığının olduğu veri dizileri için oluşturulurken, ileri beslemeli sinir ağları bir veri dizisindeki noktalar arasındaki etkileşimleri dikkate almaz. Bu makalenin geri kalanı ileri beslemeli DNN'ler durumunu dikkate alacaktır. 5 BÖLÜM III. Dağıtılmış Çıkarım Modellemesi Bu Bölüm, bir bölümleme çözümünün hesaplama gecikmelerini, iletim gecikmelerini ve nihai çıkarım verimliliğini tahmin etmek için DNN ve ağ özelliklerini temsil etmek üzere bir model sunmaktadır. A. DNN ve Ağ Temsili N katmanlı ileri beslemeli bir DNN, katmanları L=(L1,…,LL) olan bir DAG GA=(L,E) olarak modellenir. Kenarlar (Li,Lj)∈E katmanlar Li ve Lj arasındaki bağlantılardır. Her katman Li bir ileri geçişi hesaplamak için gereken kayan nokta işlemleri sayısı cinsinden ölçülen bir hesaplama tüketimi ci ile ilişkilidir. Kenarlar (Li,Lj) katmanlar Li ve Lj arasında aktarılan veri boyutu bayt olarak karşılık gelen bir ağırlık si,j ile atanır. Fiziksel ağ, düğüm kümesi N=(N1,…,NN) ve düğümler arasındaki bağlantılar kümesi V olan tam bağlı bir grafik G=(N,V) olarak modellenir. N1,…,NN düğüm kümesinin sırasıyla saniyede kayan nokta işlemleri cinsinden ölçülen işlem hızları η1,…,ηN olduğu varsayılmaktadır. Son olarak, iki bitişik düğüm Na ve Nb arasındaki bağlantı verimi θa,b ile gösterilir, saniyede bayt cinsinden ölçülür. Her düğüm Ni kendine sonsuz verimli bir döngü bağlantısını temsil eden bir döngü bağlantısıyla bağlanır ve bağlantıların simetrik olduğu varsayılır, , θa,b=θb,a . yani Bölümlemeler, P:L→N eşlemeleri olarak tanımlanır, , bir bölümleme, DNN'deki her katmana bir düğüm numarası atar. Bir bölümleme, N×L boyutunda bir P matrisi olarak tanımlanabilir, N ağdaki düğüm sayısı ve L DNN katman sayısıdır ve Pa,i=1 katman Li düğüm Na 'ya yerleştirilirse, aksi takdirde 0'dır. 'de verilen örnekle, L=7 katman ve N=2 işlem düğümü, katmanlar {L1,L2,L3,L6,L7} düğüm N1 'de ve katmanlar {L4,L5} düğüm N2 'de yerleştirilmiş olarak gösterilen bölümleme şu şekilde temsil edilir: yani Şekil 2 Verilen bir bölümlemeye göre, bir , aynı düğümde sıralı olarak çalışan iki bölünme noktası arasındaki ardışık katmanlar grubudur. Yukarıdaki örnekte, N1 düğümü iki iş parçacığı çalıştıracaktır, ilki {L1,L2,L3} katmanlarını, ikincisi ise {L6,L7} katmanlarını içerecektir. iş parçacığı Bu gösterimler tanımlandığında, bu Bölümün geri kalanı, çıkarım ( ) ve iletim ( ) gecikmelerinin bir fonksiyonu olarak verilen bir bölümlemenin elde ettiği çıkarım verimliliğinin kapalı bir ifadesini türetecektir. bölüm III-B bölüm III-C B. Çıkarım Gecikmesi Tahmini Verilen bir bölümleme için bu Bölüm, izole bir düğümde çıkarım gecikmesini incelemektedir. Tüketimi ci olan bir katmanın Li hesaplanmasıyla indüklenen gecikme, işlem oranı ηa olan Na düğümünde hesaplanacak şekilde Tci(Na)=ci/ηa olarak ifade edilir. ηa işlem oranına sahip Na düğümünde çalışan tüm iş parçacıkları üzerinde yer alan L′⊂L katman kümesi verildiğinde, çıkarım gecikmesi şu şekilde ifade edilebilir: Bu ifade, kayan nokta işlemleri (FLOP'lar) sayısına dayanan bir çıkarım gecikmesi tahmininin birinci dereceden bir yaklaşımıdır, yani modeldeki çarpma-toplama işlemleri sayısıdır. Kenar cihazlarında çıkarım gecikmesi tahmini, çalışma zamanı optimizasyonları nedeniyle karmaşıklaşır. nn-Meter gibi mevcut çözümler, FLOP'lara dayanarak çıkarım gecikmesini tahmin eder. Diğer çözümler, gecikme tahmini için önceden hesaplanmış çıkarım sürelerini içeren bir arama tablosuna dayanır. Örneğin, BRP-NAS çıkarım gecikmelerini tahmin etmek için önceden eğitilmiş bir grafik evrişimli ağ kullanır, aynı zamanda çalışma zamanı model optimizasyonlarını da dikkate alır. [](javascript:void()) [](javascript:void()) Denklem 1'de işlemcilerin tam kapasitelerini kullandıkları varsayılır, bu da çok çekirdekli işlemcilerin çekirdek işlem hızlarının toplamına eşit bir işlem hızı ile tek çekirdekli işlemciler olarak modellendiği anlamına gelir. Ayrıca, hesaplama kaynağının iş parçacıkları arasında eşit olarak paylaşıldığı varsayılır, yani bir işlemci zamanının aynı oranını her iş parçacığına ayırır. 1 Tüm düğümler arasında, en yüksek gecikmeye sahip iş parçacığı dağıtılmış DNN için çıkarım verimliliğini belirler. İletim gecikmeleri hariç tutulduğunda, bu sınırlayıcı iş parçacığı bir veri çerçevesini hesaplamayı bitirdikten sonra, bir sonrakini doğrudan işlemeye başlayacağı anlamına gelir. Diğer iş parçacıkları, çıkarım gecikmeleri bu maksimum gecikmeden daha düşük olduğu için bir sonraki veri çerçevesini işlemeden önce boşta kalma süresi olacaktır, bu da 'de gösterildiği gibidir. şekil 1 Bir bölümleme matrisi P verildiğinde, çıkarım gecikmeleri N boyutlu tek bir Tc vektörü olarak ifade edilebilir, burada a -inci bileşen, Na düğümündeki en yüksek iş parçacığı çıkarım gecikmesidir, , Tca=Tc(Na) : yani burada H ters düğüm işlem hızlarının köşegen matrisidir diag(η−11,…,η−1N) ve c tekil katman tüketimleri sütun vektörüdür (c1,…,cL) . C. İletim Gecikmesi Tahmini İletim gecikmesi şu şekilde tahmin edilebilir: katmanlar Li ve Lj arasında si,j veriyi, ölçülen verim θa,b olan bir bağlantı üzerinden (Na,Nb) kenarı üzerinden gönderme süresi Tti,j(Na,Nb)=si,j/θa,b 'dir. Kenar (Na,Nb) üzerindeki si,j∈E′⊂E veri transferlerini gerçekleştirme süresi şöyledir: Çıkarım gecikmesi tahminine benzer şekilde, bu, bağlantıların veri transferlerinden Na 'dan Nb 'ye eşit olarak paylaşıldığını ima eder. İletim gecikmesi tahmini, bağlantı veriminin tahminine dayanır, daha spesifik olarak , yani saniyede iletilen kullanılabilir veri miktarı. goodput Çıkarım gecikmesi tahminine benzer şekilde, bu birinci dereceden bir yaklaşımdır ve iyi tahmin sonuçları sağlar, bu da c'de 0.9998 korelasyon katsayısı ile gösterilmiştir. Bu yöntemin dezavantajı, bir verim tahmini elde etmek için bağlantıları doyurma gerekliliğidir. şekil 3 Bir bölümleme matrisi P verildiğinde, iletim gecikmesi matrisi Tt , L boyutunda bir kare matris olarak tanımlanabilir, burada Tta,b=Tt(Na,Nb) dir: burada ° terim terim çarpımını, yani Hadamard çarpımını, Θ ters verim matrisini, yani N boyutunda bir kare matrisi Θa,b=θ−1a,b ve S iletim boyutu matrisini, yani L boyutunda bir kare matrisi Si,j=si,j eğer Li veri gönderiyorsa Lj 'ye, aksi takdirde 0'dır. BÖLÜM IV. DNN Bölümlemesi Bu çalışmada DNN bölümlemesinin amacı, çıkarım verimliliğini, yani tüm farklı hesaplama ve iletim gecikmeleri arasındaki maksimum gecikmenin tersini temsil eden C 'yi en üst düzeye çıkarmaktır. Verilen bir bölümleme P için çıkarım verimliliği şu şekilde tanımlanır: Çıkarım verimliliğini en üst düzeye çıkarmak, Tc ve Tt 'nin tüm terimleri arasında ortak bir min-maks bulmayı içerir. Bu, aşağıdaki gibi ayrık bir optimizasyon problemi olarak tanımlanabilir: burada Ji,j i×j boyutunda tüm-birler matrisidir, koşullar ve her katmanın yalnızca bir düğüme yerleştirilmesini gerektirir. (6) (7) Bu optimizasyon problemi, Karmaşık Tamsayılı Doğrusal Olmayan Programlama (MINLP) problemidir. Bölümleme matrisi, değerleri [[1,N]] arasında olan (1×L) boyutunda bir vektörün tek-sıcak kodlanmış hali olarak görülebilir. MINLP problemleri NP-zor olduğundan, optimal bir DNN bölümlemesi bulma karmaşıklığının O(NL) olduğu anlamına gelir, çünkü L katmanının her biri N düğümüne yerleştirilebilir. Bu probleme optimal veya alt-optimal çözümler elde etmek için daha az zamanda çeşitli sezgisel yöntemler mevcuttur, örneğin, Genetik Algoritmalar (GA) , Parçacık Sürü Optimizasyonu (PSO) , veya Dal ve Sınır (B&B) . Seçilen metodoloji, uyarlanmış bir B&B uygulamasıdır ve 'da sunulmaktadır. [](javascript:void()) [](javascript:void()) [](javascript:void()) Bölüm IV-A A. Dal ve Sınır Algoritması Bu Bölüm, B&B uyarlamasını 'te tanımlanan DNN bölümlemesi optimizasyon problemine sunmaktadır. Bölüm IV B&B algoritmalarında çözüm alanı bir ağaç olarak temsil edilir. Süreç, kök düğümün puanının değerlendirilmesine dayanarak ağacın tüm dallarının elenmesini içerir. Bu, ağaç topolojisinin varlığını gerektirir, bu da ağaçtaki bir düğümün puan