Randomized Spanning Tree Mazes.
418 Final Project Check In
Title: Randomized Spanning Tree Mazes.
Members : Bryce Summers (bwsummer)
Brandon Lum (jiajunbl)
1 Sentence Description.
We are using Union Find Data Structures to construct mazes by computing randomized planar embedded spanning trees from large sets of potential edges.
Background
Please click on this image to see an example of a random maze generated on the 2D lattice set.
Power Point Description
The Challenge
Constructing data structures that use synchronization while also using them in the implementation of an actual algorithm.
Work so far
- C++ Project created and hosted on git hub. GIT HUB project
- Interface and abstract algorithmic design completed.
- Testing Suite mostly done.
- Implementation of serial, global locking, and per node locking Union find Structures done.
- Conceptual design of the lock free Union find structure done.
Schedule
- 4/19/2015 : Done with everything listed in the Work so far section above. Done writing the Check in writeup. ~ Bryce
- 4/24/2015 : Implement the Lock free Union find structure ~ Bryce / Brandon. Implement some test mazes and finish testing suite. ~Bryce.
- 4/27/2015 : Generate initial performance comparison graphs and do testing and evaluation of the system. ~Bryce Implement some of the traditional 2d array based maze implementations for some baseline context for the performance of maze algorithms.
- 5/1/2015 : Implement UF_CAS_TO_CPC lock free data structure with optimized path compression characteristics. ~ Brandon
- 5/4/2015 : Optimize the data structures. ~ Brandon / Bryce
- 5/8/2015 : Write a simple image output generator to display the resultant generated mazes. Work on Documentation. ~ Bryce
- 5/11/2015 : Final testing and documentation done. Ready to present. ~Bryce / Brandon
Progress Comments
I believe that it is highly probable that we will be able to complete the project with the time we have left.
Demo
For the parallelism competition, we will show graphs detailing how the various implementation decisions affect the performance of the Union find sturctures and the algorithm as a whole.
We may also display some of the generated mazes along with time annotations.
We may discuss the ramifications and practicality for using our system to make mazes that allows for objects such as curves,
versus the traditional methods that only work on 2d grids.
Potential Issues
The testing of the uniformity of the distribution of generated mazes bothers me a little bit.
I do not know if we will be able to make any definitive claims of results about the randomized mathematics of our system.
While I can foresee several optimizations that may speed up the generation of mazes, they may inhibit the distribution of randomness.
The important nuance of this angst is that we could potentially make a blazing fast algorithm that computes a spanning tree for a graph in a deterministic fashion. If we did this then our system would likely not need a union find structure or any other intellectually interesting work,
but our system would also be inept at the task of generating interesting disparate mazes.
We may encounter some difficulties in clearly defining designing and refining the lock free implementation of the Union Find Structure and using it correctly in parallel to generate a maze.
There are many questions of how each of the functions should be guaranteed to perform in the various cases.
We have done a lot of work on the algorithmic end, but we still need to choose the method of real world implementation and what parallel system we will be running the code on.