[ Introduction | Algorithm and circuit simulator | Download | GPU implementation | Papers | Presentations ]
This web page contains resources for the ESFA research project, including documentation, software, papers, and presentations. The topic brings together several subjects, including data structures, algorithms, functional programming, parallelism, and digital circuit design.
The latest draft of the User's Guide (html version) contains full documentation. See the section What is an ESF array? for a more detailed overview than the brief Introduction below. The user's guide also contains a series of example programs, with extensive comments, that introduce the main ideas. The source for the user's guide is written in markdown, and is in esfa-i.j.k/doc/src.
Note: the user's guide is a draft and is developing almost on a daily basis (June 2013). Currently I'm working on the sections on Shadowing and the algorithms. Check back later for an updated version.
A sparse array can have gaps where there is no value, and it lets you traverse directly from one defined element to the next, without having to spend time looking at the gaps. A further generalization is to allow associative searching within an array.
An extensible array lets you extend the size of the array at any time, simply by defining an element at a lower (or higher) index than already existed.
All of these facilities can be implemented using standard algorithms, but they increase the time complexity of array access. This is unfortunate, because conventional imperative arrays offer O(1) time update and lookup.
ESFA -- estensible sparse functional arrays -- combine all of these genereralisations in one data structure, and they implement all array operations in O(1) time (measured in clock cycles) and space (measured in words) without placing any restrictions at all on how you use the operations. In addition, ESFA provides facilities for deleting an array and mechanisms for interfacing ESFA with a regular heap garbage collector. Again, the delete operation takes O(1) time, and it's guaranteed to reclaim all space that is inaccessible -- in O(1) time! Every operation always takes a small constant number of clock cycles: the worst case time for any operation, regardless of the past history, is O(1). This property is particularly important for real time applications.
It is conjectured that it is impossible to implement ESFA on a conventional architecture (the RAM theoretical model, the von Neumann architecture), such that all operations take O(1) time and O(1) space. There is a simple motivation for this conjecture: if you make several updates to an array, you can't afford to replicate the elements of the original array even though they are now shared among several arrays, and you also can't afford to connect them up in a linked data structure because you can't afford the time required to follow pointers through the data structure. Naturally, if you restrict the way the arrays are used, you can achieve O(1) time, but we are concerned with what happens when there are no restrictions on the array operations.
The ESFA system described here uses a hardware/software codesign. The operations are implemented in three levels; the top two levels are software, but the lowest level is a digital circuit that implements a "smart memory". The crux of the system is that the smart memory has essentially the same complexity as a conventional RAM memory (in terms of gate delay and component count), yet it makes it possible to implement the ESFA operations in a constant number of clock cycles -- exactly what it is conjectured that the RAM cannot do.
Although the ideal foundation for ESFA is a digital circuit, the system can be implemented on a massively parallel host, essentially by using parallel circuit simulation. This approach allows ESFA to be used on multicore and GPGPU systems. The algorithm is now running on a GPGPU with 1024 processing elements.
A good way to see how ESF arrays behave is to try some experiments. The esfa package, a Haskell package using the Cabal installer, supports this.
The library simulates the parallel circuit, and runs the ESFA algorithm on the simulated circuit. You don't need any special parallel hardware: the program runs on an ordinary computer (but of course it's slow, because you are simulating the hardware).
The examples directory contains several programs showing how to use ESFA, and illustrating how they work. See the comments at the beginning of each module; also, several of the examples are discussed in detail, along with their output, in the User's Guide. The examples let you see how the data structures evolve with update, lookup, sharing, deletions, sparse traversal, and even zombies. You can also turn on tracing to watch the intermediate steps in the operations.
The software is written in Haskell and C, and it contains the library, a circuit simulator for the machine, various tools for diagnostics, and a collection of examples.
Software requirements:
To install the library and run an example:
Note: I'm currently taking the experimental programs used for writing a draft paper, cleaning them up, and turning them into a cabal package. The software is in a preliminary state: excellent for research but not a polished product yet. It works, and it contains some documentation and some useful example programs. The examples really do help to see what's going on. I plan to post upgrades to the package frequently during the summer of 2013 (April and beyond). So go ahead and try the system now, but please do check back later!
There is an implementation for a general purpose GPU (GPGPU), written in C+CUDA. This is available on the GPU research page, including the source code and test data.