DHPC Technical Report DHPC-098

DHPC Technical Report DHPC-098

An Implementation of k-tiling Algebra

Matthew Swan

Archived: 7 November 2000

Adelaide University Honours thesis, October 2000.

Supervisors: P.D. Coddington and K.A. Hawick

Abstract

A large amount of regular multi-dimensional data exists in the field of Computer Science. This multi-dimensional data comes from a variety of sources. Satellite data, data gathered from scanners in medical equipment and the Visible Human data set are just a few examples of multi-dimensional data sets. What is required is a general method to perform mappings of this multi-dimensional data onto other multi-dimensional data sets. In 1993, the k-tile format for performing a number of different mappings from one multi-dimensional array onto another was described. A number of extensions to the k-tile format were also described, adding to the types of mappings that could be performed. A complete implementation of the k-tile format however has not been developed, so much of this work remains untested. A revision of both the k-tile format and the k-tile extensions from those previously described in the PhD thesis of Fletcher is described here. In forming the revision, a complete implementation of the k-tile format and the k-tile extensions was developed for the first time, and the algorithms developed are also described here. In order to perform mappings however, a language was required to specify the k-tile mapping; this led to the development of the k-script language. The k-script language uses XML to define a k-tile, and the data on which to perform the mapping. A simple compiler called kScript was built to parse the k-script language into code that could be executed by a k-tile implementation. In addition to k-script, a number of other new additions have been made to the k-tile format. These include the k-blocking extension, the subsection extension and generic k-tiles. A number of example mappings are presented here, demonstrating the working implementation developed.

PDF version

Postscript version (gzip compressed)

webmaster@dhpc.adelaide.edu.au