| Ամփոփում: | Data with spatial relationships are often represented in modern programs using multidimensional arrays or other tensor structures, along with the associated metadata necessary to track the location of each piece of data. For example, a program can represent a video as a multidimensional array and a frame within the video as another multidimensional array with a timestamp that gives the location relative to the start of the video. Current programs cannot natively associate this location-based metadata with the arrays, causing the burden of tracking location to fall on to the user. It quickly becomes an arduous task within domains that have numerous arrays with spatial relationships spread across them. The task becomes further complicated when domains have multiple ways to represent the data, such as using projections, permutations, refinement, and coarsening. One such domain, block-based compression, has this type of heterogeneous, spatial data all throughout it, leading to overly complex implementations.
Block-based compression forms the core of many common image and video standards such as JPEG, H.264, H.265, and H.266. The fundamental data unit in block-based compression, the block, represents everything from a video down to an individual pixel, all of which need to maintain their location relative to other blocks in a program. Due to the lack of support for this spatial data, each implementation largely starts from scratch, leading to inconsistencies in data representation and data access.
This dissertation provides a critical look at the association between location and tensors, and defines a core abstraction called the Universal Tensor abstraction (UniTe). UniTe mathematically describes what it means to associate tensors with location and quantify spatial relationships across multiple tensors in a single program.
While UniTe itself is not tied to a particular domain, this dissertation also provides a practical look at implementing UniTe in the context of block-based compression. An initial library implementation highlights the overhead incurred from UniTe due to computing spatial relationships and underlying array indices at the innermost level of computations.
To combat this overhead, this dissertation also presents two different domain-specific languages, CoLa (Compression Language) and SHiM (Staged Hierarchical Multidimensional arrays), and their accompanying compilers built around UniTe. CoLa and SHiM show that it is possible to remove the overhead and achieve performance parity with hand-implemented C code, while also providing users with an intuitive way to represent and utilize spatial data.
|
|---|