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

```html Autoren: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Abstrakt: Deep Neural Network (DNN)-Inferenz auf Streaming-Daten erfordert Rechenressourcen, um die Anforderungen an den Inferenz-Durchsatz zu erfüllen. Latenz- und datenschutzsensible Deep-Learning-Anwendungen können es sich jedoch nicht leisten, Berechnungen in die Remote-Cloud auszulagern, da dies mit Übertragungskosten verbunden ist und kein Vertrauen in Drittanbieter-Cloud-Anbieter besteht. Unter den Lösungen zur Leistungssteigerung bei gleichzeitiger Beibehaltung der Berechnungen in einer eingeschränkten Umgebung kann die Hardwarebeschleunigung aufwendig sein, und die Modelloptimierung erfordert umfangreiche Designbemühungen, während die Genauigkeit beeinträchtigt wird. DNN-Partitionierung ist ein dritter komplementärer Ansatz, der die Verteilung der Inferenz-Workloads auf mehrere verfügbare Edge-Geräte vorsieht, unter Berücksichtigung der Eigenschaften des Edge-Netzwerks und der DNN-Struktur, mit dem Ziel, den Inferenz-Durchsatz (Anzahl der Inferenzen pro Sekunde) zu maximieren. Dieses Papier stellt eine Methode zur Vorhersage von Inferenz- und Übertragungslatenzen für Multi-Thread-verteilte DNN-Implementierungen vor und definiert einen Optimierungsprozess zur Maximierung des Inferenz-Durchsatzes. 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. Abschließend bestätigen experimentelle Ergebnisse die Simulationen und zeigen Verbesserungen des Inferenz-Durchsatzes in Beispiel-Edge-Implementierungen. DNN-Partitionierung am Edge ermöglicht die Beschleunigung des Inferenz-Durchsatzes bei gleichzeitiger Reduzierung der Bandbreitennutzung und Latenz zu zentralisierten Servern, z. B. in der Cloud. Einleitung Verbundene Geräte erzeugten im Jahr 2020 schätzungsweise 2,5 Trillionen Bytes an Daten pro Tag. In diesem Zusammenhang ist künstliche Intelligenz (KI) eine der Technologien, die mit der ständig wachsenden Menge an produzierten Daten in Bereichen wie Objekterkennung in der Computer Vision, Gesichtserkennung, Spracherkennung, natürliche Sprachverarbeitung oder autonomes Fahren am besten umgehen kann. KI, und insbesondere Deep Learning (DL), erfordert neben großen Datenmengen auch erhebliche Verarbeitungsleistung und Speicher, was Cloud Computing zur de facto Hosting-Lösung für KI-Workloads macht. Folglich wurden im Jahr 2019 96 % der KI-Aufgaben in der Cloud ausgeführt. 1 2 KI-Anwendungen können starke Latenzanforderungen haben, z. B. im autonomen Fahren, bei der Produktionsüberwachung oder bei jeder Echtzeit-Inferenz, die eine Interaktion mit der realen Welt beinhaltet. Beispielsweise müssen die durchschnittlichen Antwortzeiten im autonomen Fahren unter 100 Millisekunden liegen , was die Round-Trip-Zeiten zur Cloud für solche Anwendungen zu lang macht. Ebenso können einige Anwendungen eine signifikante Link-Nutzung im Netzwerk verursachen, z. B. bei der Verarbeitung hochwertiger Videos in der Computer Vision, was sie daran hindert, in der Cloud ausgeführt zu werden. Datenschutzrichtlinien oder Datenschutzbestimmungen können auch verbieten, dass Daten bestimmte Umgebungen verlassen. Dies fördert KI-Implementierungen im Edge Computing, bei dem Berechnungsaufgaben von Rechenzentren näher an die Edge-Geräte verlagert werden, d. h. in die Nähe der Datenquellen. [[1]](javascript:void()) Im Vergleich zu öffentlichen Clouds ist der Edge eine ressourcenbeschränkte Umgebung mit erheblichen Einschränkungen , und die Entwicklung von KI für den Edge unterscheidet sich daher grundlegend von der Entwicklung von KI für die Cloud. Die Analyse von Daten nahe der Quelle kann aufgrund geringerer Gerätekapazitäten, der Unelastizitä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 Inferenz-Durchsatzes, was die Verlagerung von schweren Workloads von der Cloud zum Edge weiter erschwert. In einigen Anwendungen kann der Inferenz-Durchsatz, d. h. die erzielbare Anzahl von Inferenzen pro Sekunde eines DNN, mit der DNN-Genauigkeit verknüpft sein, z. B. bei der Objektverfolgung in Videostreams, wo die Reduzierung der Inferenzrate von 15 auf 5 Inferenzen pro Sekunde zu einem Rückgang des F1-Scores__3__eines Objektdetektors um 10 % führte . Mit anderen Worten, Implementierungen mit geringem Inferenz-Durchsatz können zu kritischen Informationsverlusten führen, z. B. Verlust von Detektionen in 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. Die Modellkomprimierung besteht darin, neuronale Netze zu einer leichten, oft leistungsschwächeren Version des Modells zu reduzieren und zu optimieren. Standardmethoden zur Modellkomprimierung umfassen Pruning , d. h. das Entfernen unnötiger Parameter im Modell, Quantisierung , d. h. die Reduzierung des zugewiesenen Speichers für das Modell, und Wissensdestillation , 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. Die Hardwarebeschleunigung auf Edge-Geräten impliziert die Suche nach Hardware, die sowohl energieeffizient als auch leichtgewichtig ist und dennoch eine Inferenz mit ausreichender Leistung durchführen kann. Es gibt verschiedene Arten von potenzieller Hardware 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 . [[4]](javascript:void()) [[5]](javascript:void()) [[6]](javascript:void()) [[7]](javascript:void()) DNN-Partitionierung ist eine komplementäre Methode zur Beschleunigung der Inferenz durch Nutzung der Vielfalt vorhandener Geräte in Edge-Netzwerken zur Verteilung der Inferenzberechnung – die allein oder in Verbindung mit den beiden anderen Methoden verwendet werden kann. DNN-Partitionierung besteht darin, ein neuronales Netz als eine zu partitionierenden Pipeline zu betrachten 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 Zwischenergebnisse an die nächste Partition sendet. Dies ermöglicht es jeder Partition, die Berechnung des nächsten Eingabedatums zu beginnen, während die anderen Geräte die ausgelagerte Berechnung fortsetzen, wodurch der Inferenz-Durchsatz verbessert wird, wie in gezeigt. Im Folgenden wird die DNN-Partitionierung anhand des Beispiels der Echtzeit-Inferenz auf Videostreams veranschaulicht. Abbildung 1 A. Verwandte Arbeiten Methoden zur DNN-Partitionierung, abgeleitet vom Mobile Edge-Cloud-Offloading, zielen darauf ab, verschiedene Leistungsindikatoren zu optimieren, wie z. B. Rechenlatenz, Energieverbrauch, Ressourcennutzung, Kosten oder Durchsatz. DNN-Partitionierung basiert auf der Assoziation einer oder mehrerer dieser Metriken, um ein Optimierungsziel und eine Methode zu definieren, die diese Metrik zur Findung von Partitionierungsschemata nutzt. Neurosurgeon z. B. sucht einen einzigen Split-Punkt, wobei die erste Partition am Edge verbleibt und die zweite Partition in die Cloud ausgelagert wird, um Latenz und Energieverbrauch zu minimieren. Anwendungen im IoT haben auch die gemeinsame Partitionierung und das Offloading mehrerer DNNs zur Optimierung von Energie, Verzögerung und/oder Kosten berücksichtigt, unter Verwendung verschiedener Solver wie SPSO-GA , das Particle Swarm Optimization (PSO) und Genetic Algorithm (GA) kombiniert, oder DDPQN , das Deep Reinforcement Learning verwendet, um Partitionierungsschemata zu finden. Andere Beispiele sind DINA , das ein Integer Non Linear Programming (INLP)-Problem definiert und einen Solver auf Basis der Matching-Theorie verwendet, um Verzögerung und Ressourcennutzung in Fog-Netzwerken zu optimieren. Methoden zur Optimierung des Inferenz-Durchsatzes umfassen DNN Surgery , die die geringere Größe von Zwischen-DNN-Schichtausgaben 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 umfassen auch Multi-Thread-Berechnungen in der Cloud, um den gesamten Inferenz-Durchsatz weiter zu beschleunigen. Die Nutzung der Cloud für die Inferenzberechnung der zweiten Partition setzt eine gute Netzwerkkonnektivität voraus, die bei der schlechten Konnektivität einiger isolierter Edge-Implementierungen unsicher sein kann. Edgent passt die vorherige Methodik auf mobile Geräte und verfügbare Edge-Server an und lockert die Beschränkung des Offloadings in die Cloud. Diese Methode ist mit einem spezifischen Trainings- und Modellarchitektur verknüpft und beschränkt die Partitionierung weiterhin 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 zum Hochladen der Modelle auf Edge-Server 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 Remote-Clouds oder sind in der Art der Partitionierung eingeschränkt, z. B. müssen sie genau in zwei Teile geteilt werden, mit oder ohne Multi-Threading. Keine der aufgeführten DNN-Partitionierungsstudien berücksichtigt sowohl mehrere Split-Punkte als auch Multi-Threading. B. Beiträge Dieses Papier präsentiert ein verteiltes Inferenz-Framework zur Maximierung des Inferenz-Durchsatzes von Echtzeit-DNN-Berechnungen auf Streaming-Daten mit mehreren Split-Punkten und Multi-Thread-Partitionierung. Die Beiträge dieses Papiers sind folgende: Ein Modell zur Berechnung und Vorhersage von Inferenz- und Übertragungslatenzen einer verteilten DNN, über das der erwartete Inferenz-Durchsatz 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 der möglichen 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 DNN-Partitionierung vorteilhaft ist. Experimentelle Ergebnisse, die die in den Simulationen definierten Regionen sowie die Vorhersagegenauigkeit und die endgültige Beschleunigung des Inferenz-Durchsatzes für homogene und heterogene Umgebungen veranschaulichen. Im Folgenden wird zur Vermeidung von Verwechslungen die partitionierte tiefe neuronale Netzwerk als und der Begriff als das zugrunde liegende physische Kommunikationsnetzwerk bezeichnet. 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, welcher das Optimierungsproblem sowie den Branch-and-Bound-Algorithmus zur Entscheidungsfindung bei der Partitionierung definiert. präsentiert Simulationsergebnisse zur Quantifizierung der Leistung und Komplexität des Branch-and-Bound-Algorithmus sowie der Bedingungen, die zur Existenz einer Partitionierung führen, die den Inferenz-Durchsatz in einem homogenen Netzwerk verbessert. präsentiert experimentelle Ergebnisse, die die Simulationen von bestätigen, und zeigt Verbesserungen des Inferenz-Durchsatzes in einem heterogenen experimentellen Setup. Abschließend 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 maschinelle Lernmethoden), die mehr als eine versteckte Schicht enthalten. Einer der frühesten Verweise auf 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. Es wird geschätzt, dass Deep Learning 2022 den Großteil der KI-Anwendungen ausmacht, wobei über 75 % der Organisationen DNNs für Anwendungen nutzen, die auch klassische Methoden verwenden könnten. DL-Methoden wurden als „Techniken für maschinelles Lernen definiert, bei denen Hypothesen die Form komplexer algebraischer Schaltungen mit abstimmbaren Verbindungsstärken annehmen“ . 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 [[17]](javascript:void()) tief Es gibt zwei Haupt-DNN-Strukturen: Feed-Forward-Neuronale Netze und Rekurrente Neuronale Netze. Beide Arten von DNNs können als Berechnungsdiagramme 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 Datenfolgen konzipiert, bei denen jeder Datenpunkt eine potenzielle Abhängigkeit von früheren Datenpunkten in der Folge hat, während Feed-Forward-Neuronale Netze keine Interaktionen zwischen Punkten in einer Datenfolge berücksichtigen. Im Folgenden 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 Rechenlatenzen, Übertragungslatenzen und den endgültigen Inferenz-Durchsatz 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 Gleitkommaoperationen, die für die Berechnung eines Forward-Passes durch die Schicht erforderlich sind. Kanten (Li,Lj) werden mit einem Gewicht si,j zugewiesen, das der Größe der zwischen den Schichten Li und Lj in Bytes übertragenen Daten entspricht. Das physische Netzwerk wird als vollständig verbundener Graph G=(N,V) modelliert, wobei N=(N1,…,NN) die Menge der Rechenknoten und V die Menge der Links zwischen den Knoten ist. Es wird angenommen, dass die Rechenknoten N1,…,NN Verarbeitungsraten η1,…,ηN haben, gemessen in Gleitkommaoperationen pro Sekunde. Schließlich wird der Link-Durchsatz zwischen zwei benachbarten Knoten Na und Nb als θa,b, gemessen in Bytes pro Sekunde, bezeichnet. Jeder Knoten Ni ist mit sich selbst mit unendlichem Durchsatz verbunden, um den Loopback-Link darzustellen, und die Links werden als symmetrisch angenommen, d. h. θa,b=θb,a. Partitionierungen werden 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 mit Pa,i=1, wenn Schicht Li auf Knoten Na platziert ist, 0 sonst. Mit dem Beispiel in L=7 Schichten und N=2 Rechenknoten ist 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 wird ein als eine Gruppe von aufeinanderfolgenden Schichten zwischen zwei Split-Punkten definiert, 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 die {L6,L7}. Thread Mit diesen definierten Notationen leitet der Rest dieses Abschnitts einen geschlossenen Ausdruck für den Inferenz-Durchsatz ab, der von einer gegebenen Partitionierung erreicht wird, als Funktion der Inferenz- (Abschnitt III-B) und Übertragungslatenzen (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 Aufwand ci induziert wird, die auf dem Knoten Na mit der Verarbeitungsrate ηa berechnet werden soll, wird als Tci(Na)=ci/ηa ausgedrückt. Gegeben eine Menge von Schichten L′⊂L über alle auf Knoten Na laufenden Threads mit der Verarbeitungsrate ηa, kann die Inferenzlatenz ausgedrückt werden als: Dieser Ausdruck ist eine Approximation erster Ordnung einer Schätzung der Inferenzlatenz, die auf der Anzahl der Gleitkommaoperationen (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 prognostizieren die Inferenzlatenz basierend auf FLOPs. Andere Lösungen basieren auf einer Nachschlagetabelle mit vorab berechneten Inferenzzeiten für die Latenzvorhersage. BRP-NAS verwendet beispielsweise ein vortrainiertes Graph Convolutional Network, um Inferenzlatenzen vorherzusagen und dabei Laufzeit-Modelloptimierungen zu berücksichtigen. [[18]](javascript:void()) [[19]](javascript:void()) In wird ferner angenommen, dass die 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 die Threads aufgeteilt wird, d. h. ein Prozessor weist jedem Thread den gleichen Anteil seiner Zeit zu. Gleichung 1 Über alle Knoten hinweg bestimmt der Thread mit der höchsten Latenz den Inferenz-Durchsatz für die verteilte DNN. Ohne Berücksichtigung der Übertragungslatenzen bedeutet dies, dass, sobald dieser limitierende Thread die Berechnung eines Datenrahmens abgeschlossen hat, er direkt den nächsten verarbeitet. Andere Threads haben Leerlaufzeit, 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 Knotennennverarbeitungsraten diag(η−11,…,η−1N) ist und c der Spaltenvektor der einzelnen Schichtverbrä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 auf der Kante (Na,Nb) über einen Link mit dem gemessenen Durchsatz θa,b zu senden, beträgt Tti,j(Na,Nb)=si,j/θa,b. Die Zeit für die Durchführung von Datentransfers si,j∈E′⊂E über den Link (Na,Nb) ist: Ähnlich wie bei der Vorhersage der Inferenzlatenz impliziert dies, dass die Links gleichmäßig zwischen Datentransfers von Na nach Nb aufgeteilt werden. Die Vorhersage der Übertragungslatenz basiert auf der Schätzung des Link-Durchsatzes zwischen den Knoten, genauer gesagt des , d. h. der Menge der pro Sekunde übertragenen Nutzdaten. Goodput Ähnlich wie bei der Schätzung der Inferenzlatenz ist dies eine Approximation erster Ordnung, die effizient gute Vorhersageergebnisse liefert, wie in c gezeigt, mit einem Korrelationskoeffizienten von R2=0,9998. Der Nachteil dieser Methode ist ihre Anforderung, die Links zu sättigen, um eine Durchsatzschätzung zu erhalten. Abbildung 3 Gegeben eine Partitionierungsmatrix P kann die Übertragungslatenzmatrix Tt als eine quadratische Matrix der Größe L definiert werden, wobei Tta,b=Tt(Na,Nb): wobei ° das elementweise Produkt oder Hadamard-Produkt ist, Θ die Matrix der inversen Durchsätze 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, sonst 0. ABSCHNITT IV. DNN-Partitionierung Das Ziel der DNN-Partitionierung in dieser Studie ist die Maximierung des Inferenz-Durchsatzes, bezeichnet mit C, was der Kehrwert der maximalen Latenz zwischen allen verschiedenen Berechnungs- und Übertragungslatenzen ist. Gegeben eine Partitionierung P ist der Inferenz-Durchsatz definiert als: Die Maximierung des Inferenz-Durchsatzes entspricht dem Finden des gemeinsamen Min-Max zwischen allen Termen von Tc und Tt. Dies kann als diskretes Optimierungsproblem definiert werden: wobei Ji,j die Eins-Matrix der Größe i×j ist und die Bedingungen und erfordern, dass jede Schicht auf einem und nur einem Knoten platziert wird. (6) (7) Dieses Optimierungsproblem ist ein Mixed Integer Non-linear Programming (MINLP)-Problem. Die Partitionierungsmatrix kann als die 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 des Findens einer optimalen DNN-Partitionierung O(NL) ist, da jede der L Schichten auf N Knoten platziert werden kann. Es gibt mehrere 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) , Particle Swarm Optimization (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 Anpassung von Branch and Bound (B&B) an das in definierte DNN-Partitionierungs-Optimierungsproblem 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 Auswertung des Scores des Wurzelknotens. Dies impliziert die Existenz einer Baumtopologie, die eine Beziehung zwischen dem Score eines Knotens im Baum und den Grenzen der Scores all seiner Blätter schafft. Diese Baumdarstellung des Lösungsraums begünstigt die Verwendung des B&B-Algorithmus in dieser Studie. Angenommen, ps ist eine partielle Liste der Größe s, dann sind die Kinder des Knotens ps im Baum alle Listen, die mit ps beginnen, d. h. alle Partitionierungen, bei denen die ersten s Schichten gemäß ps platziert sind. Der Blattknoten unter ps, der ps entspricht, aufgefüllt mit dem letzten Wert von ps, wird mit ps~ bezeichnet. Zum Beispiel, wenn L=5 und p2=(2,1), dann ist p2~=(2,1,1,1,1). Gegeben Ttmax=maxTt(ps~) die maximale Übertragungszeitmatrix für die Partitionierung ps~, werden alle Blattknoten p unter ps eine höhere maximale Übertragungszeit als ps~ haben, d. h. ∀p,maxTt(p)≥Ttmax. Dies erklärt sich dadurch, dass bei einer partiellen Partitionierung jede Verlagerung in den anderen Schichten nur Datentransfers zwischen Knoten hinzufügt. Während des Prozesses der Suche nach einer optimalen Partitionierung p, die den Inferenz-Durchsatz C(p,GA,GN) maximiert, und gegeben einen aktuell besten erreichbaren Durchsatz best_throughput, besteht die B&B-Optimierung darin, ganze Zweige des Baumes, der den Lösungsraum darstellt, durch Auswertung der Übertragungszeiten in partiellen Partitionierungen zu eliminieren. Dieser Prozess ermöglicht es der B&B-Optimierung, im Vergleich zu einem Brute-Force-Algorithmus schnell zahlreiche Fälle zu eliminieren. Wenn beispielsweise der Durchsatz zwischen den Knoten im Vergleich zur Rechenkapazität gering ist, z. B. bei Knoten, die über eine drahtlose Verbindung mit geringem Durchsatz verbunden sind, ist die optimale Lösung oft, die gesamte Berechnung auf einem einzigen Knoten zu belassen. Der Vorteil des B&B-Algorithmus besteht darin, dass er in solchen einfachen Fällen nach N Operationen terminiert, indem alle partiellen Partitionierungen in der ersten Stufe des Baumes eliminiert werden. Umgekehrt kann in Fällen, in denen die Links höhere Durchsätze haben, die Komplexität von B&B höher sein, da große Zweige nicht eliminiert werden können. B. Komplexität von Branch and Bound Der Overhead, der durch die Gesamtzahl der Partitionen in einer realen Implementierung verursacht wird, wird in diesem Ansatz vernachlässigt. Diese