Under Original/Normal_Java/ one would find the original Labyrinth project ported...

[IRC.git] / Robust / src / Benchmarks / Java-Single / Labyrinth / mlp / rBlocked / Original README

diff --git a/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Original README b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Original README
new file mode 100644 (file)
index 0000000..3bcaf63
--- /dev/null
+++ b/Robust/src/Benchmarks/Java-Single/Labyrinth/mlp/rBlocked/Original README
@@ -0,0 +1,71 @@
+Introduction
+------------
+
+Given a maze, this benchmark finds the shortest-distance paths between pairs of
+starting and ending points. The routing algorithm used is Lee's algorithm [2].
+
+In this algorithm, the maze is represented as a grid, where each grid point can
+contain connections to adjacent, non-diagonal grid points. The algorithm
+searches for a shortest path between the start and end points of a connection by
+performing a breadth-first search and labeling each grid point with its distance
+from the start. This expansion phase will eventually  reach the end point if a
+connection is possible. A second traceback phase then forms the connection by
+following any path with a decreasing distance. This algorithm is guaranteed to
+find the shortest path  between a start and end point; however, when multiple
+paths are made, one path may block another.
+
+When creating the transactional version of this program, the techniques
+described in [3] were used. When using this benchmark, please cite [1].
+
+
+Compiling and Running
+---------------------
+
+To build the application, simply run:
+
+    make -f <makefile>
+
+in the source directory. For example, for the sequential flavor, run:
+
+    make -f Makefile.seq
+
+By default, this produces an executable named "labyrinth", which can then be
+run in the following manner:
+
+    ./labyrinth -i <input_file>
+
+The following input file is recommended for simulated runs:
+
+    ./labyrinth -i inputs/random-x32-y32-z3-n96.txt
+
+For non-simulator runs, a larger input can be used:
+
+    ./labyrinth -i inputs/random-x512-y512-z7-n512.txt
+
+
+Input Files
+-----------
+
+More input sets can be generated by using "inputs/generate.py". For example,
+
+    inputs/generate.py 128 128 3 64
+
+Will create a 128x128x3 maze grid and select 64 uniformly random start/end
+point pairs.
+
+
+References
+----------
+
+[1] C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford 
+    Transactional Applications for Multi-processing. In IISWC '08: Proceedings
+    of The IEEE International Symposium on Workload Characterization,
+    September 2008. 
+
+[2] C. Lee. An algorithm for path connections and its applications. IRE Trans.
+    On Electronic Computers, 1961.
+
+[3] I. Watson, C. Kirkham, and M. Lujan. A Study of a Transactional Parallel
+    Routing Algorithm. Proceedings of the 16th International Conference on
+    Parallel Architectures and Compilation Techniques, 2007.
+