GPU programming research

John T. O'Donnell
School of Computing Science
University of Glasgow

[ Introduction | ESFA on GPU | Download | Papers | Links ]

This web page contains resources for research on GPU programming.

Introduction

ESFA on GPU

ESFA (extensible sparse functional array) is an active data structure that uses fine grain parallelism to provide fast access, creation, traversal, and memory management for pure functional arrays. See the paper below and the ESFA page for an explanation of ESF arrays, circuit design, simulators, test generation, and more.

The ESFA algorithm has been implemented on an NVidia GPU using C+CUDA. You can download it below. The algorithm is under active development, and the code is not in final polished form.

Download esfa-gpu

• Version 0.0.2, 2013-06-16. esfa-gpu-0.0.2.tar (2013-06-16) directory containing the source code and makefile. esfa-gpu-results-0.0.2.tar directory containing two files showing results from running on the gpu; you probably won't need this but it can be useful to confirm that the program is running correctly.
• esfa-gpu-0.0.1.tgz (2013-06-15) directory containing the source code, a test data file, and results from execution (File seems corrupted; use 0.0.2 instead)
• esfa-gpu-0.0.0.cu (2013-06-08)

The standalone gpu program runs a test suite that is read in from a file. A variety of test data files can be downloaded below. It's recommended to use the "set1" directory, which contains ten files, each a randomly generated sequence of 50,000 operations. Each of these files was generated by a special test generator program which is part of the esfa software (that program is available in the esfa package which can be downloaded on the ESFA page).

The test data files have filenames that give some key parameters used in generating the data. Consider the file named test-13-50000-6-0-data1.txt. In this filename,

• 13 is the machine size (there are 2^13 cells, or 8196 cells);
• 50000 is the number of ESFA operations that are performed (a mix of update, lookup, delete);
• 6 is the range of index values (since operands are generated randomly, and the arrays may be sparse, many lookups would give Nothing if the range of indices is too large);
• 0 is the probability that notification is requested (this has to do with interfacing esfa with a heap-based system)

• esfa-test-50k-set1-tar-gz directory containing ten files with randomly generated test data. Each file contains a run with 50,000 operations, one per line, along with the correct result (generated by the executable semantic specification).
• test-12-50000-6-0-data1.txt
• test-13-50000-6-0-data1.txt

Papers

• John T. O'Donnell, Data parallel implementation of Extensible Sparse Functional Arrays, Parallel Architectures and Languages Europe (PARLE'93), Springer-Verlag, LNCS 694, pp. 68-79, 1993.
• John T. O'Donnell, Extensible Sparse Functional Arrays with Circuit Parallelism, Draft paper submitted for publication.

Links

ESFA page