High-throughput HEVC CABAC decoding
| dc.contributor.advisor | Juurlink, Ben | |
| dc.contributor.author | Habermann, Philipp | |
| dc.contributor.grantor | Technische Universität Berlin | en |
| dc.contributor.referee | Sikora, Thomas | |
| dc.contributor.referee | Stabernack, Benno | |
| dc.contributor.referee | Brandenburg, Jens | |
| dc.date.accepted | 2020-11-02 | |
| dc.date.accessioned | 2020-12-09T11:35:00Z | |
| dc.date.available | 2020-12-09T11:35:00Z | |
| dc.date.issued | 2020 | |
| dc.description.abstract | Video applications have emerged in various fields of our everyday life. They have continuously enhanced the user experience in entertainment and communication services. All this would not have been possible without the evolution of video compression standards and computer architectures over the last decades. Modern video codecs employ sophisticated algorithms to transform raw video data to an intermediate representation consisting of syntax elements, which allows enormous compression rates before reconstructing the video with minimal objective quality losses compared to the original video. Modern computer architectures lay the foundation for these computationally intensive tasks. They provide multiple cores and specialized vector architectures to exploit the massive amount of parallelism that can be found in video applications. Customized hardware solutions follow the same principles. Parallel processing is essential to satisfy real-time performance constraints while optimizing energy efficiency, the latter being the most important design goal for mobile devices. One of the main tasks in modern video compression standards implements a highly sequential algorithm and lacks data-level parallelism in contrast to all other compute-intensive tasks: Context-based Adaptive Binary Arithmetic Coding (CABAC). It is the entropy coding module in the state-of-the-art High Efficiency Video Coding (HEVC) standard and also its successor Versatile Video Coding. Its purpose is the compression and decompression of the intermediate video representation by exploiting statistical properties, thus achieving minimal bitrates. CABAC is one of the main throughput bottlenecks in video coding applications due to the limited parallelization opportunities, especially for high-quality videos. Close-distance control and data dependencies make CABAC even more challenging to implement with modern computer architectures. This thesis addresses the critical CABAC decoding throughput bottleneck by proposing multiple approaches to uncover new parallelization opportunities and to improve the performance with architectural optimizations. First of all, we quantitatively verify the severity of the CABAC decoding throughput bottleneck by evaluating the HEVC decoding performance for various workloads using a representative selection of state-of-the-art computer architectures. The results show that even the most powerful processors cannot provide real-time performance for several high-quality workloads. The profiling results clearly show that CABAC decoding is the main reason for that in most cases. Wavefront Parallel Processing (WPP) is a well-established high-level parallelization technique used in video coding and other applications. It can lead to a high degree of parallelism, however, it suffers from inefficiencies due to the dependencies between consecutive rows in a frame. We present three WPP implementations for HEVC CABAC decoding with improved parallel efficiency. The WPP versions based on more fine-grained dependency checks allow speed-ups up to 1.83x at very low implementation cost. We also present a bitstream partitioning scheme for future video compression standards. It enables additional parallelism in CABAC decoding by distributing syntax elements among eight bitstream partitions. Besides the parallelization opportunities, this allows specialization of the subdecoders responsible for the processing of their corresponding partitions as they have to process fewer types of syntax elements. This leads to further improvements in clock frequency and significant hardware savings compared to a full replication of the CABAC decoder as it is required for approaches such as WPP. Decoding speedups up to 8.5x at the cost of only 61.9% extra hardware area and less than 0.7% bitstream overhead for typical Full High Definition videos make this technique a promising candidate for use in future video compression standards. Furthermore, a cache-based architectural optimization is presented. It replaces the context model memory - a critical component in the CABAC decoder pipeline - by a smaller cache, thus increasing the achievable clock frequency. An application-specific adaptive prefetching algorithm is used together with a context model memory layout optimized for spatial and temporal locality. We perform a design space exploration of different cache configurations, finding that a cache of 2x8 context models provides the best performance. It allows for a 17% increase in clock frequency and miss rates of less than 2%, resulting in performance improvements up to 16.7%. We also propose techniques for more efficient CABAC decoding on general-purpose processors. Frequent hardly predictable branches lead to very inefficient implementations with these processors. Using more complex but linear arithmetic functions for the parallel decoding of binary symbols provides a speedup of up to 2.04x. A separate bitstream partition for this type of binary symbol even allows speedups up to 2.45x at the cost of not more than 0.2% higher bitrate for typical Full High Definition videos. Finally, we provide recommendations for future video compression standards and computer architectures as well as further research ideas for video coding in general and CABAC in particular. The research conducted in this thesis shows multiple approaches that can substantially improve the performance of CABAC decoding, thereby addressing one of the most critical throughput bottlenecks in modern video coding applications. | en |
| dc.description.abstract | Videoanwendungen haben sich in vielen Bereichen unseres täglichen Lebens etabliert und dabei die Nutzererfahrung in den Bereichen Unterhaltung und Kommunikation zunehmend verbessert. Das wäre ohne die ständige Weiterentwicklung von Videokompressionsstandards und Computerarchitekturen nicht möglich gewesen. Moderne Videocodecs nutzen komplexe Algorithmen, um rohe Videodaten in eine aus Syntaxelementen bestehende Zwischenrepräsentation zu transformieren, was enorme Kompressionsraten erlaubt. Die anschließende Rekonstruktion der Videodaten kann mit minimalen Qualitätsverlusten im Vergleich zum Originalvideo durchgeführt werden. Modern Computerarchitekturen legen die Grundlage für diese rechenintensiven Prozesse. Sie stellen zahlreiche Rechenkerne und spezialisierte Vektorarchitekturen zur Verfügung, welche die zahlreichen Parallelisierungsmöglichkeiten in Videoanwendungen ausnutzen. Die parallele Datenverarbeitung ist essenziell, um die Echtzeitfähigkeit zu gewährleisten und gleichzeitig die Energieeffizienz zu optimieren, was insbesondere für Mobilgeräte eines der wichtigsten Entwicklungsziele darstellt. Context-based Adaptive Binary Arithmetic Coding (CABAC) ist das Entropiekodierungsverfahren im aktuellen High Efficiency Video Coding (HEVC) Standard, sowie in dessen Nachfolger Versatile Video Coding. CABAC ist für die Kompression und Dekompression der Zwischenrepräsentation eines Videos unter Ausnutzung statistischer Gegebenheiten verantwortlich, wodurch minimale Bitraten erreicht werden können. Dafür wird ein sequentieller Algorithmus verwendet, der CABAC im Vergleich zu allen anderen rechenintensiven Komponenten aktueller Videokompressionsstandards keine Ausnutzung von Datenparallelität ermöglicht. Durch die mangelnden Parallelisierungsmöglichkeiten ist CABAC eine der kritischsten Komponenten, welche die Gesamtleistung eines Videodekoders beschränken. Das gilt insbesondere für Videos mit hoher Qualität und dementsprechend hohen Bitraten. Außerdem stelle eine Vielzahl an Steuer- und Datenabhängigkeiten in CABAC moderne Computerarchitekturen vor große Herausforderungen. Das Ziel dieser Doktorarbeit ist die Verbesserung der Leistung des CABAC-Dekoders, da er die Gesamtleistung aktueller Videodekoder maßgeblich beeinflusst. Wir stellen dafür verschiedene Ansätze vor, die einerseits neue Parallelisierungsmöglichkeiten schaffen und andererseits durch architekturelle Optimierungen effizientere Implementierungen ermöglichen. Zuerst verifizieren wir quantitativ, dass CABAC für den Dekodierungsprozess in HEVC eine kritische Komponente ist. Dafür analysieren wir die Dekodierleistung einer repräsentativen Auswahl aktueller Computersysteme für verschiedene typische Videoanwendungen. Die Ergebnisse zeigen, dass selbst die performantesten Prozessoren nicht für alle Anwendungen echtzeitfähig sind. Weitere Untersuchungen bestätigen deutlich, dass CABAC in den meisten Fällen dafür hauptverantwortlich ist. Anschließend beschäftigen wir uns mit der Optimierung von Wavefront Parallel Processing (WPP). Dabei handelt es sich um eine weit verbreitete Parallelisierungstechnik, die in der Videokodierung und vielen anderen Anwendungen verwendet wird. WPP erlaubt ein hohes Maß an Parallelisierung, erleidet aber wegen der Abhängigkeiten zwischen benachbarten Bildbereichen Einbußen in seiner Effizienz. Wir stellen drei Implementierungsvarianten vor, die die Effizienz der Parallelisierung mit WPP für CABAC in HEVC deutlich verbessern. Dies wird durch eine feingranularere Prüfung von Abhängigkeiten im Vergleich zu konventionellen WPP-Implementierungen erreicht. So kann die Dekodierung von Videos um einen Faktor von bis zu 1.83x beschleunigt werden, während die Implementierung nur unwesentlich komplexer wird. Dann stellen wir ein Bitstreampartitionierungsschema für zukünftige Videokompressions-standards vor, welches zusätzliche Parallelisierungsmöglichkeiten schafft. Dies wird durch die Aufteilung aller Syntaxelemente unter Berücksichtigung ihrer Abhängigkeiten auf acht Partitionen erreicht. Zusätzlich ermöglicht dies deutliche Erhöhungen der Taktfrequenz eines Hardwaredekoders, da die spezialisierten Teildekoder für die verschiedenen Partitionen weitaus weniger verschiedene Syntaxelemente bearbeiten müssen. Die reduzierte Komplexität der Teildekoder erlaubt außerdem drastische Hardwareeinsparungen, vor allem im Vergleich zu Techniken wie WPP, die eine vollständige Replikation des CABAC-Dekoders erfordern. Der vorgestellte Dekoder erlaubt eine Beschleunigung um bis zu 8.5x bei lediglich 61.9% zusätzlichen Hardwarekosten und einer Erhöhung der Bitrate um maximal 0.7% bei typischen Full-HD-Videos. Außerdem stellen wir einen Cache-basierten CABAC-Dekoder vor. Dieser ersetzt den Context-Model-Speicher durch einen kleineren Cache und ermöglicht somit den Betrieb mit höheren Taktfrequenzen, da der Speicherzugriff den kritischen Pfad beeinflusst. Die auftretenden Fehlzugriffe auf den Cache werden mit einem optimierten Speicherlayout und einem adaptiven Vorhersagealgorithmus effektiv reduziert. Die Untersuchung verschiedener Cache-Architekturen zeigt, dass ein 2x8 Context-Model-Cache die beste Leistung liefert. Durch die Erhöhung der Taktfrequenz um 17% und eine Fehlzugriffsrate von maximal 2% kann der Durchsatz des Dekoders um bis zu 16.7% erhöht werden. Die letzte vorgestellte Optimierung behandelt die Software-CABAC-Dekodierung. Der Algorithmus beinhaltet viele schwer vorhersagbare Verzweigungen im Steuerfluss, was für aktuelle Prozessoren eine große Herausforderung darstellt und zu ineffizienten Implementierungen führt. Der Einsatz komplexer arithmetischer Instruktionen zur parallelen Dekodierung führt zu einer Beschleunigung bis zu 2.04x. Die Nutzung von zwei Bit-streampartitionen für verschiedene Arten von binären Symbolen ermöglicht es sogar, die Dekodierung einer davon ohne Rechenaufwand durchzuführen. Folglich ist eine noch höhere Beschleunigung bis zu 2.45x bei höchstens 0.2% höherer Bitrate möglich. Abschließend sprechen wir Empfehlungen für die Entwicklung zukünftiger Videokompressionsstandards und Computerarchitekturen aus. Weitere Forschungsideen für Videokodierung im Allgemeinen und CABAC im Besonderen werden ebenfalls diskutiert. Die dieser Arbeit zugrunde liegende Forschung demonstriert bereits einige vielversprechende Ansätze, welche die Leistung von CABAC und damit des gesamten Dekoders deutlich erhöhen können. Durch die Behandlung dieser kritischen Komponente leisten wir einen wichtigen Beitrag zur Verbesserung vieler aktueller und zukünftiger Videoanwendungen. | de |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/11858 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-10748 | |
| dc.language.iso | en | en |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | en |
| dc.subject.ddc | 004 Datenverarbeitung; Informatik | de |
| dc.subject.ddc | 629 Andere Fachrichtungen der Ingenieurwissenschaften | de |
| dc.subject.other | video compression | en |
| dc.subject.other | entropy coding | en |
| dc.subject.other | HEVC | en |
| dc.subject.other | CABAC | en |
| dc.subject.other | arithmetic coding | en |
| dc.subject.other | Videokompression | de |
| dc.subject.other | Entropiekodierung | de |
| dc.subject.other | arithmetische Kodierung | de |
| dc.title | High-throughput HEVC CABAC decoding | en |
| dc.title.translated | HEVC CABAC Dekodierung | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | acceptedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 4 Elektrotechnik und Informatik::Inst. Technische Informatik und Mikroelektronik::FG Architektur eingebetteter Systeme | de |
| tub.affiliation.faculty | Fak. 4 Elektrotechnik und Informatik | de |
| tub.affiliation.group | FG Architektur eingebetteter Systeme | de |
| tub.affiliation.institute | Inst. Technische Informatik und Mikroelektronik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |