Approximate Computing - Cheatsheet

Fehlertolerierende Entwürfe

Definition:

Fehlertolerierende Entwürfe zielen darauf ab, Systeme so zu gestalten, dass sie trotz Fehlern in der Hardware oder Software funktionsfähig bleiben.

Details:

• Fehlertoleranz ermöglicht es, dass Systeme weiterhin korrekt arbeiten, auch wenn einzelne Komponenten ausfallen.
• Diverse Techniken wie Redundanz, Fehlerkorrektur-Codes und Checkpoints werden eingesetzt.
• Wichtige metriken: Zuverlässigkeit (Reliability) und Verfügbarkeit (Availability).
• Redundanzarten: Räumliche (gleiche Operation mehrfach ausführen) und zeitliche (Operation bei Fehlererkennung wiederholen).
• Fehlererkennung durch: Paritätsbits, Prüfsummen, CRC (Cyclic Redundancy Check).
• Fehlerkorrekturverfahren: Hamming-Code, Reed-Solomon-Code.
• Fehlertoleranz ist besonders wichtig in sicherheitskritischen Systemen (z.B. Luft- und Raumfahrt, Medizintechnik).

Energieeinsparung durch Reduzierung der Rechengenauigkeit

Definition:

Reduzierung der Rechengenauigkeit zur Einsparung von Energie, z.B. durch Approximate Computing.

Details:

• Approximative Berechnungsverfahren: geringere Genauigkeit, mehr Energieeinsparung
• Fehlertolerante Anwendungen: Multimedia, Machine Learning
• Energieeinsparung proportional zur Reduktion der Genauigkeit
• Verwendete Strategien: Fixed-Point-Arithmetik, Approximate Storage
• Trade-off: Genauigkeit vs. Energieverbrauch

Grundlagen und Definitionen von Approximate Algorithms

Definition:

Approximate Algorithmen bieten Lösungen, die nahe an die exakte Lösung kommen, aber mit weniger Rechenaufwand. Verwendung bei Problemen, die NP-schwer sind oder keine effizienten exakten Algorithmen haben.

Details:

• Ziel: Annäherung an optimale Lösung mit reduzierter Komplexität
• Effizienzsteigerung: Weniger Rechenzeit, Speicherverbrauch
• Gütemaße: Approximationsfaktor, Fehler-Grenzen
• Beispiele: Greedy-Algorithmen, Randomisierte Algorithmen
• Wichtige Konzepte: Pseudopolynomielle Algorithmen, PTAS (Polynomial Time Approximation Scheme)

Statistische Analyse von Approximationsfehlern

Definition:

Analyse der Abweichungen zwischen exakten und approximierten Berechnungen mit statistischen Methoden.

Details:

• Wichtige Messgrößen: Mittelwert, Varianz, Standardabweichung
• Fehlerverteilung mithilfe von Histogrammen und Wahrscheinlichkeitsverteilungen analysieren
• Konfidenzintervalle zur Bestimmung des Vertrauensbereichs der Fehler
• Hypothesentests zur Bewertung der Signifikanz von Abweichungen
• Berechnung der mittleren quadratischen Abweichung (MSE): \[ \text{MSE} = \frac{1}{n} \sum_{i=1}^n (\hat{y}_i - y_i)^2 \]

Integration der Konzepte in bestehende Systeme

Definition:

Definition und Erklärung der Integration von Approximate Computing in bestehende Systeme. Ziel ist die Verbesserung von Effizienz und Leistung durch bewusste Einführungen von Ungenauigkeiten in nicht-kritischen Berechnungen.

Details:

• Identifizierung von tolerierbaren Fehlerbereichen in bestehenden Anwendungen.
• Techniken: Approximate Storage, Approximate Communication, Approximate Computing Units.
• Anpassung der Hardware und Softwareebenen zur Unterstützung approximativer Methoden.
• Sicherstellung der Akzeptanz der Näherungen durch Endnutzer und Anwendungen.
• Methoden zur Bewertung und Validierung der Performance und Fehlergrenzen.
• Beispiel: Reduzierung der Rechenpräzision bei Bild- und Videoverarbeitung.
• Software-Frameworks: Modifikationen auf Compiler- und Laufzeitebene.
• Designprinzipien und -muster zur Integration in bestehende Architektur.

Adaptive Energieverwaltungsstrategien

Definition:

Anpassung der Energieverwaltung in Computersystemen zur Optimierung des Energieverbrauchs basierend auf aktuellen Lastbedingungen und Systemanforderungen.

Details:

• Dynamische Skalierung der Spannung und Frequenz (DVFS) zur Reduzierung des Energieverbrauchs bei geringer Last.
• Nutzung verschiedener Modi (z.B. Idle, Sleep, Deep Sleep) zur Energieeinsparung während Inaktivität.
• Anwendung von Approximate Computing zur Duldung kleiner Berechnungsfehler zur Energieeinsparung.
• Erhöhter Energiebedarf bei hoher Rechenlast und Reduktion bei geringer Auslastung.
• Überwachungssysteme erforderlich zur Analyse und Anpassung des Energieverbrauchs in Echtzeit.
• Ziel: Effizientere Nutzung von Energiequellen und Verlängerung der Batterielebensdauer bei mobilen Geräten.

Analyse der Komplexität und Effizienz von Approximate Algorithms

Definition:

Analyse der Komplexität und Effizienz von Approximate Algorithms befasst sich mit der Bewertung der Rechenzeit (Zeitkomplexität) und des Ressourcenverbrauchs (Speicherkomplexität) von Näherungslösungen im Vergleich zu exakten Lösungen.

Details:

• Zeitkomplexität: Laufzeitanalyse, meist in Big-O-Notation \(O(n)\).
• Speicherkomplexität: Bewertung des Speicherbedarfs, ebenfalls in Big-O.
• Approximation Ratio: Verhältnis der Güte der Näherungslösung zur optimalen Lösung \(APX(I) ≤ \rho \times OPT(I)\).
• Effizienz: Abwägung der Handelsbeziehung zwischen Genauigkeit und Ressourcenverbrauch.
• Anwendungsfälle: Situationen, wo exakte Lösungen zu teuer oder unmöglich sind.
• Beispiele: Knapsack, Traveling Salesman Problem.

Redundanz und Wiederherstellungstechniken

Definition:

Techniken zur Sicherstellung der Zuverlässigkeit und Verfügbarkeit im Approximate Computing. Nutzen Redundanz zur Fehlerminderung.

Details:

• Redundanz: Bereitstellung mehrerer Instanzen kritischer Komponenten
• Nutzung von Fehlerkorrekturverfahren wie ECC (Error-Correcting Code)
• Heterogene Redundanz: Kombination von verschiedenen Implementierungen derselben Funktion
• Wiederherstellung: Mechanismen zur Rückkehr in einen fehlerfreien Zustand
• Checkpointing: Regelmäßiges Speichern des Systemzustands zur Fehlerbehebung