Next generation compression algorithm

Abstract

Kompresjon har en viktig rolle i dagens datasystemer. Neste generasjons kompressorer forsøker å tilfredsstille dagens økende krav om å kunne håndtere stadig økende datamengder. På tross av rask utvikling innen programvarebaserte komprimeringsalgoritmer, kan maskinvareimplementasjoner gi betydelige gevinster. Eksempler på slike gevinster er forbedret beregningshastighet, rimeligere elektronikk og redusert strømforbruk.

Historisk sett tilbyr entropibaserte kompresjonsteknikker kompresjonsforhold nær de teoretiske grensene. Da Asymmetric Numeral Systems (ANS)-algoritmen av Jarosław Duda kom i 2014 fikk verden tilgang til et nytt og innovativt medlem av kompressorfamilien. Sammenlignet med andre entropibaserte kompressorer tilbyr algoritmen meget konkurransedyktige kompresjonsforhold, samtidig som den kan skilte med hurtig beregning.

Avhandlingens hovedmål er å lage en syntetiserbar maskinvareimplementasjon av høy kvalitet basert på Uniform Binary Variant (uABS) av ANS. Dette gjøres ved hjelp av maskinvare-beskrivende språk og industristandardverktøy. Den endelige maskinvareimplementasjonen ble oppnådd gjennom en iterativ prosess, først ved å implementere en programvaremodell på høynivå og så en programvaremodell på lavnivå, før maskinvaremodellen ble implementert. En iterativ tilnærming ble brukt for å håndtere maskinvaredesignkompleksiteten og en grunnleggende mangel på liknende programvareimplementasjoner. Maskinvareimplementasjonen ble senere optimalisert for å oppnå høyere ytelse og for å sikre et enkelt kretsdesign samt en skalerbar arkitektur. Det måtte samtidig oppnås en god balanse mellom forbruk, ytelse og elektronikkareal (PPA). Denne balansen ble oppnådd uten å måtte ofre presisjon og robusthet, og uten negative påvirkning på kompresjonsforholdet.

Til slutt ble maskinvaredesignene verifisert gjennom bruk av både UVM og ikke-UVM testbenker. Maskinvareimplementasjonen ble blant annet undersøkt med tanke på korrekthet, nøyaktighet og ytelse (kompresjonsforhold). Verifikasjonen viste at både timing og kompresjonsresultater tilfredsstiller kravene til en fullverdig ANS-kompressor. Den endelige maskinvareimplementasjonen ga kompresjonsforhold som konvergerte mot den teoretiske grensen, samtidig som lave behandlingstider ble beholdt. Verifikasjonsprosessen viste også at kompressoren kunne håndtere en betydelig økning i unøyaktighet i sannsynlighetsmodelleringen.

Implementasjonsrapportene viste encodings- og dekodingshastigheter i megabitområdet. Selv uten ytterligere optimaliseringer vil den dermed kunne håndtere betraktelige bitstrømmer med data, og gjøre implementasjonen nyttig for moderne anvendelser, spesielt gitt det lave ressursbehovet. Ut fra resultatene av implementasjons- og verifikasjonsrapportene kan det derfor konkluderes med en vellykket maskinvareimplementasjon.

Compression serves an instrumental role in today's computer systems. Next generation compressors seek to bring modern innovation to the field of compression and answer today's demand for transmitting more data between devices. Although rapid development is happening with software-based compression algorithms, hardware implementations may also bear significant gains. Such gains are improved computational speed, cheaper circuitry and decreased power consumption.

Historically, entropy-based compression techniques offer compression ratios close to the theoretical limits. However, the emergence of the Asymmetric Numeral Systems (ANS) algorithm in 2014 by Jarosław Duda provides a new and innovative take on the family of compressors. Contrary to numerous other entropy-based compressors, the algorithm offers highly competitive compression ratios while still boasting low computation times.

The thesis's main objective is to create a high-quality synthesizable hardware implementation of the Uniform Binary Variant (uABS) of ANS. This is done in hardware descriptive language using industry-standard tools. The final hardware implementation was achieved through an iterative process, first by implementing a higher level software model and a lower level software model, before implementing the hardware model. An iterative approach was needed due to the increased complexity of implementing a hardware design and the lack of software implementation.

The hardware implementation was later optimized to achieve higher performance and to ensure lightweight circuitry. A balance between high performance and resource usage (Power, Performance and Area) had to be found. This balance was struck without sacrificing precision and robustness, thus not adversely affecting compression ratios.

Lastly, the hardware designs were verified with UVM and non-UVM testbenches. The hardware implementation was tested for correctness, accuracy, and performance(compression ratios), among other metrics. It revealed that both timing and results satisfy the conditions of a full-fledged ANS compressor, where the hardware implementation yielded compression ratios converging the theoretical limit while maintaining low processing times. The verification process also revealed how the compressor was suited to handle a considerable amount of inaccuracy in the probability modelling.

The implementation reports revealed peak encoding and decoding speeds in the mega-bit range. Being able to handle sizeable bitstreams of data situates the implementation as useful for modern world applications, especially given its low resource requirements. Therefore, based on the implementation and verification reports results, one may conclude that the hardware implementation is successful.