Warum Ihre KI nicht mehr die Cloud benötigt, um schneller zu laufen

```html Autoren: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Zusammenfassung: Deep-Neuronale-Netzwerk (DNN)-Inferenz auf Streaming-Daten erfordert Rechenressourcen, um die Anforderungen an den Inferenzdurchsatz zu erfüllen. Latenz- und datenschutzsensible Deep-Learning-Anwendungen können es sich jedoch nicht leisten, die Berechnung in entfernte Clouds auszulagern, da dies Übertragungskosten und mangelndes Vertrauen in Drittanbieter-Cloud-Anbieter mit sich bringt. Unter den Lösungen zur Leistungssteigerung bei gleichzeitiger Beibehaltung der Berechnung in einer eingeschränkten Umgebung ist die Hardwarebeschleunigung aufwändig und die Modelloptimierung erfordert umfangreiche Designbemühungen, während die Genauigkeit beeinträchtigt wird. DNN-Partitionierung ist ein dritter ergänzender Ansatz, der die Verteilung der Inferenzlast auf mehrere verfügbare Edge-Geräte beinhaltet, wobei die Eigenschaften des Edge-Netzwerks und die DNN-Struktur berücksichtigt werden, mit dem Ziel, den Inferenzdurchsatz (Anzahl der Inferenzen pro Sekunde) zu maximieren. Dieses Papier stellt eine Methode zur Vorhersage von Inferenz- und Übertragungslatenzen für Multi-Thread-verteilte DNN-Bereitstellungen vor und definiert einen Optimierungsprozess zur Maximierung des Inferenzdurchsatzes. Anschließend wird ein Branch-and-Bound-Solver vorgestellt und analysiert, um die erzielte Leistung und Komplexität zu quantifizieren. Diese Analyse hat zur Definition des Beschleunigungsbereichs geführt, der deterministische Bedingungen für die DNN- und Netzwerkeigenschaften beschreibt, unter denen die DNN-Partitionierung vorteilhaft ist. Schließlich bestätigen experimentelle Ergebnisse die Simulationen und zeigen Verbesserungen des Inferenzdurchsatzes in Beispiel-Edge-Bereitstellungen. DNN-Partitionierung am Edge ermöglicht die Beschleunigung des Inferenzdurchsatzes bei gleichzeitiger Reduzierung der Bandbreitennutzung und Latenz zu zentralisierten Servern, z. B. in der Cloud. Einleitung Verbundene Geräte erzeugten im Jahr 2020 täglich schätzungsweise 2,5 Trillionen Bytes an Daten. In diesem Kontext ist künstliche Intelligenz (KI) eine der Technologien, die mit der ständig wachsenden Menge an produzierten Daten am besten umgehen kann, in einer Reihe von Bereichen wie Objekterkennung in der Computer Vision, Gesichtserkennung, Spracherkennung, Verarbeitung natürlicher Sprache oder autonomes Fahren. KI, und insbesondere Deep Learning (DL), erfordert zusätzlich zu großen Datenmengen erhebliche Verarbeitungsleistung und Speicherplatz, was Cloud Computing zur De-facto-Hosting-Lösung für KI-Workloads macht. Folglich wurden 2019 96 % der KI-Aufgaben in der Cloud ausgeführt. 1 2 KI-Anwendungen können starke Latenzanforderungen haben, z. B. beim autonomen Fahren, in der Produktionsüberwachung oder bei jeder Echtzeit-Inferenz, die eine Interaktion mit der realen Welt beinhaltet. Beispielsweise müssen die durchschnittlichen Antwortzeiten beim autonomen Fahren unter 100 Millisekunden liegen , was Round-Trip-Zeiten zur Cloud für solche Anwendungen zu lang macht. Ebenso können einige Anwendungen eine erhebliche Link-Nutzung im Netzwerk verursachen, z. B. bei der Verarbeitung von hochwertigem Video in der Computer Vision, was ihre Ausführung in der Cloud verhindert. Datenschutzrichtlinien oder Datenschutzbestimmungen können auch verbieten, dass Daten bestimmte Umgebungen verlassen. Dies fördert KI-Bereitstellungen im Edge Computing, bei dem Rechenaufgaben von Rechenzentren näher an Edge-Geräte verlagert werden, d. h. in die Nähe der Datenquellen. [[1]](javascript:void()) Im Vergleich zu öffentlichen Clouds ist das Edge eine ressourcenbeschränkte Umgebung mit erheblichen Einschränkungen , und die Entwicklung von KI für das Edge unterscheidet sich daher grundlegend von der Entwicklung von KI für die Cloud. Die Analyse von Daten nahe ihrer Quelle kann aufgrund geringerer Gerätekapazitäten, der Inelastizität der verfügbaren Ressourcen und der Heterogenität von Edge-Netzwerken eine Herausforderung darstellen. Die Senkung der Rechenkapazität bedeutet eine Senkung des erreichbaren Inferenzdurchsatzes, was die Verlagerung von schweren Workloads von der Cloud zum Edge weiter erschwert. Bei einigen Anwendungen kann der Inferenzdurchsatz, d. h. die erreichbaren Inferenzen pro Sekunde eines DNN, mit der DNN-Genauigkeit verknüpft sein, z. B. bei der Objektverfolgung in Videoströmen, wobei die Verringerung der Inferenzrate von 15 auf 5 Inferenzen pro Sekunde den F1-Score__3__eines Objektdetektors um 10 % gesenkt hat . Mit anderen Worten, Bereitstellungen mit niedrigem Inferenzdurchsatz können zu kritischen Informationsverlusten führen, z. B. zu Verlusten von Erkennungen bei Videoüberwachungsanwendungen. [[2]](javascript:void()) [[3]](javascript:void()) Es gibt zwei Hauptmethoden, um Leistungsanforderungen in eingeschränkten Edge-Netzwerken zu erfüllen: Modellkomprimierung oder Hardwarebeschleunigung. besteht darin, neuronale Netze zu einer leichtgewichtigen, oft unterdurchschnittlichen Version des Modells zu reduzieren und zu optimieren. Standard-Modellkomprimierungsmethoden umfassen Pruning , d. h. das Entfernen unnötiger Parameter im Modell, Quantisierung , d. h. die Reduzierung des zugewiesenen Speichers für das Modell, und Knowledge Distillation , d. h. das Trainieren eines kleineren neuronalen Netzes mit Wissen, das aus einem größeren extrahiert wurde. Modelloptimierung erfordert umfangreiche Designbemühungen und kann die Modellgenauigkeit beeinträchtigen. auf Edge-Geräten beinhaltet die Suche nach Hardware, die sowohl energieeffizient als auch leichtgewichtig ist und dennoch Inferenz mit ausreichender Leistung ausführen kann. Es gibt verschiedene Arten von Kandidatenhardware für die Beschleunigung am Edge, die sich in Effizienz und Spezifität unterscheiden, aber Standardverarbeitungseinheiten erfüllen die Erwartungen nicht und dedizierte Hardware wie ASICs hat sich als unpraktisch und teuer erwiesen . Modellkomprimierung [[4]](javascript:void()) [[5]](javascript:void()) [[6]](javascript:void()) Hardwarebeschleunigung [[7]](javascript:void()) DNN-Partitionierung ist eine ergänzende Methode zur Beschleunigung der Inferenz, indem die Vielfalt vorhandener Geräte in Edge-Netzwerken genutzt wird, um die Inferenzberechnung zu verteilen – die allein oder in Verbindung mit den beiden anderen Methoden verwendet werden kann. DNN-Partitionierung besteht darin, ein neuronales Netzwerk als Pipeline zu betrachten, in Partitionen zu segmentieren und diese Partitionen auf Edge-Geräte zu verteilen. Die Platzierung dieser Partitionen basiert sowohl auf der DNN als auch auf den zugrunde liegenden Netzwerkeigenschaften. DNN-Partitionierung basiert auf der Identifizierung von Split-Punkten, d. h. Punkten im Modellgraphen, an denen das Modell in Partitionen aufgeteilt wird. Während der Laufzeit werden Partitionen sequenziell ausgeführt, wobei jede Zwischeninferenzergebnisse an die nächste Partition sendet. Dies ermöglicht jeder Partition, die Berechnung der nächsten Eingabedaten zu beginnen, während die anderen Geräte die ausgegebene berechnen, wodurch der Inferenzdurchsatz verbessert wird, wie in gezeigt. Im Rest dieses Papiers wird die DNN-Partitionierung anhand des Beispiels der Echtzeit-Inferenz auf Videoströmen veranschaulicht. Abbildung 1 A. Verwandte Arbeiten Methoden zur DNN-Partitionierung, abgeleitet von Mobile-Edge-Cloud-Offloading, zielen darauf ab, verschiedene Leistungsindikatoren wie Berechnungslatenz, Energieverbrauch, Ressourcenauslastung, Kosten oder Durchsatz zu optimieren. DNN-Partitionierung beruht auf der Zuordnung einer oder mehrerer dieser Metriken, um ein Optimierungsziel und eine Methode zu definieren, die diese Metrik nutzt, um Partitionierungsschemata zu finden. Zum Beispiel versucht Neurosurgeon , einen einzigen Split-Punkt zu finden, wobei die erste Partition am Edge verbleibt und die zweite Partition in die Cloud ausgelagert wird, um Latenz und Energieverbrauch zu minimieren. Anwendungen in IoT haben auch die gemeinsame Partitionierung und das Offloading mehrerer DNNs zur Optimierung von Energie, Verzögerung und/oder Kosten berücksichtigt, wobei verschiedene Solver wie SPSO-GA , die Partikelschwarmoptimierung (PSO) und genetische Algorithmen (GA) kombinieren, oder DDPQN , das Deep Reinforcement Learning verwendet, um Partitionierungsschemata zu finden. Weitere Beispiele sind DINA , das ein Integer Non Linear Programming (INLP)-Problem definiert und einen auf Matching-Theorie basierenden Solver verwendet, um Verzögerung und Ressourcenauslastung in Fog-Netzwerken zu optimieren. Methoden zur Optimierung des Inferenzdurchsatzes umfassen DNN Surgery , die die geringere Größe von Zwischen-DNN-Ausgaben nutzt, um die Inferenzberechnung zwischen Edge und Cloud zu partitionieren. Beide Algorithmen erstellen zwei Partitionen, eine am Edge und die andere in der Cloud. Andere Studien im Bereich Mobile Edge-Cloud beinhalten auch Multi-Thread-Berechnungen in der Cloud, um den gesamten Inferenzdurchsatz weiter zu beschleunigen. Die Nutzung der Cloud für die zweite Partition-Inferenzberechnung setzt eine gute Netzwerkverbindung voraus, die bei der schlechten Konnektivität einiger isolierter Edge-Bereitstellungen unsicher sein kann. Edgent passt die vorherige Methodik an mobile Geräte und verfügbare Edge-Server an und lockert die Einschränkung des Auslagerns in die Cloud. Diese Methode ist mit einem bestimmten Trainings- und Modellarchitektur verbunden und beschränkt die Partitionierung immer noch auf zwei Partitionen. Andere Methoden haben mehrere Split-Punkte berücksichtigt, z. B. IONN , das das Problem der Partitionierung zur Minimierung von Latenz und Energieverbrauch beschreibt und auch die Zeit für den Upload der Modelle zu Edge-Servern berücksichtigt. [[8]](javascript:void()) [[9]](javascript:void()) [[10]](javascript:void()) [[11]](javascript:void()) [[12]](javascript:void()) [[13]](javascript:void()) [[14]](javascript:void()) [[15]](javascript:void()) Diese Methoden interagieren entweder mit entfernten Clouds oder sind in der Art der Partitionierung begrenzt, z. B. müssen sie in genau zwei Teile aufgeteilt werden, mit oder ohne Multithreading. Keine der aufgeführten DNN-Partitionierungsstudien berücksichtigt sowohl mehrere Split-Punkte als auch Multithreading. B. Beiträge Dieses Papier stellt ein verteiltes Inferenz-Framework vor, um den Inferenzdurchsatz der Echtzeit-DNN-Berechnung auf Streaming-Daten mit mehreren Split-Punkten und Multi-Thread-Partitionierung zu maximieren. Die Beiträge dieses Papiers sind die folgenden: Ein Modell zur Berechnung und Übertragung von Latenzen einer verteilten DNN, durch das der erwartete Inferenzdurchsatz eines gegebenen Partitionierungsschemas geschätzt werden kann. Formulierung des Optimierungsproblems für die DNN-Partitionierung, Implementierung eines Branch-and-Bound-Solvers für dieses Problem und Bewertung seiner Komplexität. Simulationen zur Untersuchung möglicher Leistungsverbesserungen bei variierenden Netzwerk- und DNN-Eigenschaften. Die Identifizierung deterministischer Regionen in den Netzwerk- und DNN-Eigenschaften, die die Existenz optimaler Partitionierungen und die Kosten für die Berechnung solcher Lösungen bedingen, d. h. die Bedingungen, unter denen die DNN-Partitionierung vorteilhaft ist. Experimentelle Ergebnisse, die die in den Simulationen definierten Regionen sowie die Vorhersagegenauigkeit und die endgültige Inferenzdurchsatzbeschleunigung für homogene und heterogene Umgebungen veranschaulichen. Im Folgenden wird zur Vermeidung von Verwechslungen die partitionierte tiefe neuronale Netzwerk als und der Begriff bezeichnet das zugrunde liegende physikalische Kommunikationsnetzwerk. DNN Netzwerk C. Gliederung des Papiers Der Rest dieses Papiers ist wie folgt organisiert. stellt den Hintergrund von Deep Learning vor und wie DNNs in dieser Studie dargestellt werden. beschreibt die Methoden zur Vorhersage von Inferenz- und Übertragungslatenzen, die für erforderlich sind, der das Optimierungsproblem sowie den Branch-and-Bound-Algorithmus zur Entscheidungsfindung bei der Partitionierung definiert. stellt Simulationsergebnisse zur Quantifizierung der Leistung und Komplexität des Branch-and-Bound-Algorithmus sowie Bedingungen dar, die zur Existenz einer Partitionierung führen, die den Inferenzdurchsatz in einem homogenen Netzwerk verbessert. präsentiert experimentelle Ergebnisse, die die Simulationen von bestätigen und Inferenzdurchsatzverbesserungen auf einem heterogenen experimentellen Aufbau zeigen. Schließlich die Ergebnisse und erweitert die breitere Anwendbarkeit dieser Methode. Abschnitt II Abschnitt III Abschnitt IV Abschnitt V Abschnitt VI Abschnitt V diskutiert Abschnitt VII ABSCHNITT II. Hintergrund: Deep Learning Im Bereich des maschinellen Lernens (Machine Learning) bezieht sich Deep Learning (DL) auf Methoden, die auf der Verwendung von DNNs basieren, d. h. künstliche neuronale Netze (oder verwandte Methoden des maschinellen Lernens), die mehr als eine versteckte Schicht enthalten. Eine der frühesten Referenzen zu Deep-Learning-Architekturen wurde 1967 veröffentlicht , aber erst in den 2010er Jahren gewann DL an Bedeutung, zuerst in der Spracherkennung, dann in der Objekterkennung in Bildern, aufgrund der Fähigkeit, komplexe Beziehungen in hochdimensionalen Daten zu erfassen. DL wird voraussichtlich den Großteil der KI-Anwendungen im Jahr 2022 ausmachen, wobei mehr als 75 % der Organisationen DNNs für Anwendungen nutzen, für die auch klassische Methoden verwendet werden könnten. DL-Methoden wurden definiert als „ “ . Diese algebraischen Schaltungen sind normalerweise in Schichten organisiert, die Schritte in der Berechnung bilden. Der Begriff bezieht sich auf Algorithmen, die aus mehr als einer Schicht bestehen. [[16]](javascript:void()) 4 Techniken für maschinelles Lernen, bei denen Hypothesen die Form komplexer algebraischer Schaltungen mit abstimmbaren Verbindungstärken annehmen [[17]](javascript:void()) deep Es gibt zwei Haupttypen von DNN-Strukturen: Feed-Forward-Neuronale Netze und Rekurrente Neuronale Netze. Beide Arten von DNNs können als Berechnungsgraphen dargestellt werden, wobei der Hauptunterschied darin besteht, dass Feed-Forward-Netze als gerichtete azyklische Graphen (DAGs) dargestellt werden können, während rekurrente neuronale Netze Zyklen enthalten können. Rekurrente neuronale Netze sind für Datensequenzen ausgelegt, bei denen jeder Datenpunkt eine potenzielle Abhängigkeit von früheren Datenpunkten in der Sequenz hat, während Feed-Forward-Netze keine Wechselwirkungen zwischen Punkten in einer Datensequenz berücksichtigen. Im Rest dieses Papiers wird der Fall von Feed-Forward-DNNs betrachtet. 5 ABSCHNITT III. Modellierung verteilter Inferenz Dieser Abschnitt stellt ein Modell zur Darstellung von DNN- und Netzwerkeigenschaften vor, um Berechnungslatenzen, Übertragungslatenzen und den endgültigen Inferenzdurchsatz einer gegebenen Partitionierungslösung vorherzusagen. A. DNN- und Netzwerkdarstellung Ein Feed-Forward-DNN mit N Schichten wird als DAG GA=(L,E) modelliert, wobei L=(L1,…,LL) die Schichten des DNN sind. Kanten (Li,Lj)∈E sind die Verbindungen zwischen den Schichten Li und Lj . Jede Schicht Li hat einen zugehörigen Rechenaufwand ci , gemessen in der Anzahl der Fließkommaoperationen, die für die Berechnung eines Forward-Passes durch die Schicht erforderlich sind. Kanten (Li,Lj) wird ein Gewicht si,j zugewiesen, das der Größe der zwischen den Schichten Li und Lj übertragenen Daten in Bytes entspricht. Das physikalische Netzwerk wird als vollständig verbundener Graph G=(N,V) modelliert, wobei N=(N1,…,NN) die Menge der Rechenknoten und V die Menge der Verbindungen zwischen den Knoten ist. Es wird angenommen, dass die Rechenknoten N1,…,NN Verarbeitungsraten η1,…,ηN haben, gemessen in Fließkommaoperationen pro Sekunde. Schließlich wird der Durchsatz der Verbindung zwischen zwei benachbarten Knoten Na und Nb als θa,b bezeichnet, gemessen in Bytes pro Sekunde. Jeder Knoten Ni ist mit sich selbst mit unendlichem Durchsatz verbunden, um die Loopback-Verbindung darzustellen, und die Verbindungen werden als symmetrisch angenommen, d. h. θa,b=θb,a . Partitionierungen sind als Abbildungen P:L→N definiert, d. h. eine Partitionierung weist jeder Schicht im DNN eine Knotennummer zu. Eine Partitionierung kann als Matrix P der Dimension (N×L) beschrieben werden, wobei N die Anzahl der Knoten im Netzwerk und L die Anzahl der DNN-Schichten ist und Pa,i=1 , wenn Schicht Li auf Knoten Na platziert ist, andernfalls 0. Mit dem in gegebenen Beispiel, mit L=7 Schichten und N=2 Rechenknoten, wird die dargestellte Partitionierung mit den Schichten {L1,L2,L3,L6,L7} auf Knoten N1 und den Schichten {L4,L5} auf Knoten N2 wie folgt dargestellt: Abbildung 2 Gegeben eine Partitionierung ist ein eine Gruppe von aufeinanderfolgenden Schichten zwischen zwei Split-Punkten, die sequenziell auf demselben Knoten ausgeführt werden. Im obigen Beispiel wird Knoten N1 zwei Threads ausführen, der erste enthält die Schichten {L1,L2,L3} und der zweite {L6,L7} . Thread Mit diesen definierten Notationen leitet der Rest dieses Abschnitts einen geschlossenen Ausdruck für den Inferenzdurchsatz ab, der durch eine gegebene Partitionierung erreicht wird, als Funktion der Inferenz- ( ) und Übertragungslatenzen ( ). Abschnitt III-B Abschnitt III-C B. Vorhersage der Inferenzlatenz Gegeben eine Partitionierung betrachtet dieser Abschnitt die Vorhersage der Inferenzlatenz auf einem isolierten Knoten. Die Latenz, die durch die Berechnung einer Schicht Li mit dem Verbrauch ci auf Knoten Na mit der Verarbeitungsrate ηa verursacht wird, wird als Tci(Na)=ci/ηa ausgedrückt. Gegeben eine Menge von Schichten L′⊂L , die über alle auf Knoten Na laufenden Threads mit der Verarbeitungsrate ηa verteilt sind, kann die Inferenzlatenz ausgedrückt werden als: Dieser Ausdruck ist eine Näherung erster Ordnung einer Inferenzlatenzschätzung, die auf der Anzahl der Fließkommaoperationen (FLOPs) basiert, die zur Verarbeitung des DNN erforderlich sind, d. h. der Anzahl der Multiplikations-Additions-Operationen im Modell. Die Schätzung der Inferenzlatenz auf Edge-Geräten wird durch Laufzeitoptimierungen erschwert. Bestehende Lösungen wie nn-Meter sagen die Inferenzlatenz basierend auf FLOPs voraus. Andere Lösungen stützen sich auf eine Nachschlagetabelle mit vorab berechneten Inferenzzeiten für Latenzvorhersagen. Zum Beispiel verwendet BRP-NAS ein vortrainiertes Graph-Convolutional-Netzwerk, um Inferenzlatenzen vorherzusagen, wobei Laufzeitmodelloptimierungen berücksichtigt werden. [[18]](javascript:void()) [[19]](javascript:void()) In wird ferner angenommen, dass Prozessoren ihre volle Kapazität nutzen, was bedeutet, dass Mehrkernprozessoren als Einkernprozessoren mit einer Verarbeitungsrate modelliert werden, die der Summe ihrer Kernverarbeitungsraten entspricht. Es wird auch angenommen, dass die Rechenressource gleichmäßig auf Threads aufgeteilt wird, d. h. ein Prozessor widmet jedem Thread den gleichen Zeitanteil. Gleichung 1 Über alle Knoten hinweg bestimmt der Thread mit der höchsten Latenz den Inferenzdurchsatz für das verteilte DNN. Ohne Übertragungslatenzen bedeutet dies, dass, sobald dieser limitierende Thread die Berechnung eines Datenrahmens abgeschlossen hat, er direkt den nächsten verarbeitet. Andere Threads haben Leerlaufzeiten, bevor sie den nächsten Datenrahmen verarbeiten, da ihre Inferenzlatenz niedriger als diese maximale Latenz ist, wie in gezeigt. Abbildung 1 Gegeben eine Partitionierungsmatrix P , können die Inferenzlatenzen als einzelner Vektor Tc der Größe N ausgedrückt werden, wobei die a -te Komponente die höchste Thread-Inferenzlatenz auf Knoten Na ist, d. h. Tca=Tc(Na) : wobei H die Diagonalmatrix der inversen Knotenverarbeitungsraten diag(η−11,…,η−1N) und c der Spaltenvektor der einzelnen Schichverbräuche (c1,…,cL) ist. C. Vorhersage der Übertragungslatenz Die Übertragungslatenz kann wie folgt vorhergesagt werden: Die Zeit, die benötigt wird, um die Datenmenge si,j zwischen den Schichten Li und Lj an der Kante (Na,Nb) über eine Verbindung mit dem gemessenen Durchsatz θa,b zu senden, ist Tti,j(Na,Nb)=si,j/θa,b . Die Zeit für die Datenübertragung si,j∈E′⊂E über die Verbindung (Na,Nb) beträgt: Ähnlich wie bei der Vorhersage der Inferenzlatenz impliziert dies, dass die Verbindungen gleichmäßig zwischen Datenübertragungen von Na nach Nb aufgeteilt werden. Die Vorhersage der Übertragungslatenz basiert auf der Schätzung des Verbindungsdurchsatzes zwischen den Knoten, genauer gesagt des , d. h. der Menge der pro Sekunde übertragenen nützlichen Daten. Goodputs Ähnlich wie bei der Schätzung der Inferenzlatenz ist dies eine Näherung erster Ordnung, die effizient gute Vorhersageergebnisse liefert, wie in c gezeigt, mit einem Korrelationskoeffizienten von R2=0.9998 . Der Nachteil dieser Methode ist die Notwendigkeit, die Verbindungen zu sättigen, um eine Durchsatzschätzung zu erhalten. Abbildung 3 Gegeben eine Partitionierungsmatrix P kann die Übertragungslatenzmatrix Tt als quadratische Matrix der Größe L definiert werden, wobei Tta,b=Tt(Na,Nb) : wobei ° das elementweise Produkt oder Hadamard-Produkt ist, Θ die inverse Durchsatzmatrix ist, d. h. eine quadratische Matrix der Größe N mit Θa,b=θ−1a,b und S die Übertragungsgrößenmatrix ist, d. h. eine quadratische Matrix der Größe L mit Si,j=si,j , wenn Li Daten an Lj sendet, andernfalls 0. ABSCHNITT IV. DNN-Partitionierung Das Ziel der DNN-Partitionierung in dieser Studie ist die Maximierung des Inferenzdurchsatzes, bezeichnet mit C , was der Kehrwert der maximalen Latenz zwischen allen verschiedenen Berechnungs- und Übertragungslatenzen ist. Gegeben eine Partitionierung P , ist der Inferenzdurchsatz definiert als: Die Maximierung des Inferenzdurchsatzes entspricht dem Auffinden des gemeinsamen Min-Max zwischen allen Termen von Tc und Tt . Dies kann als diskretes Optimierungsproblem definiert werden: wobei Ji,j die Alle-Eins-Matrix der Größe i×j ist. Die Bedingungen und erfordern, dass jede Schicht auf genau einem Knoten platziert wird. (6) (7) Dieses Optimierungsproblem ist ein Mixed Integer Non-linear Programming (MINLP)-Problem. Die Partitionierungsmatrix kann als One-Hot-kodierte Version eines Vektors der Größe (1×L) mit Werten in [[1,N]] betrachtet werden. MINLP-Probleme sind NP-schwer, was bedeutet, dass die Komplexität der Suche nach einer optimalen DNN-Partitionierung O(NL) beträgt, da jede der L Schichten auf N Knoten platziert werden kann. Es gibt verschiedene Heuristiken, um optimale oder suboptimale Lösungen für dieses Problem in kürzerer Zeit als ein Brute-Force-Algorithmus zu erhalten, z. B. genetische Algorithmen (GA) , Partikelschwarmoptimierung (PSO) , oder Branch and Bound (B&B) . Die gewählte Methodik ist eine angepasste B&B-Implementierung, die in vorgestellt wird. [[21]](javascript:void()) [[22]](javascript:void()) [[23]](javascript:void()) Abschnitt IV-A A. Branch-and-Bound-Algorithmus Dieser Abschnitt stellt die Branch-and-Bound (B&B)-Anpassung an das in definierte DNN-Partitionierungsoptimierungsproblem vor. Abschnitt IV In B&B-Algorithmen wird der Lösungsraum durch einen Baum dargestellt. Der Prozess besteht darin, ganze Zweige im Baum zu eliminieren, basierend auf der Bewertung der Punktzahl des Wurzelknotens. Dies impliziert die Existenz einer Baumtopologie, die eine Beziehung zwischen der Punktzahl eines Knotens im Baum und den Grenzen der Punktzahlen aller seiner Blätter schafft. Diese Baumdarstellung des Lösungsraums begünstigt die Verwendung des B&B-Alg