Companion source code for our PACT 2007 paper

Lee Router - An Application for Transactional Memory

[TM project] [TM publications] [Lee-TM benchmark]

This website contains the code and data used in our study on implementing a realistic application using transactional memory [1]. The application is circuit routing using Lee's algorithm and was selected for its abundance of parallelism, but difficulty of expressing it with locks. Each route between a source and a destination point in a grid can be considered a unit of parallelism. Starting from this simple approach, we evaluated the exploitable parallelism on an abstracted transactional memory implementation and explore how it can be adapted to deliver better performance. Note that Lee-TM Benchmark contains the source code for this application using various software transactional memory systems.

Note that industrial strength routers use more elaborate techniques than those implemented in the code available for download in this website. We make no claim about the suitability of the code for commercial routing. The code is provided "as is" without any guarantees of any kind and is distributed as open source under a BSD license. The copyright is held by the University of Manchester. If you use the information on this page in any way, we would be grateful if you would reference our PACT paper [1]. If you make improvements (find errors) to the code, we would like to hear from you.

We have developed a simple two-layer routing software written in Java. We wanted to keep the routing program simple, as the study is concerned with understanding the behavior of a transactional memory program rather than developing sophisticated routing software. However, it was necessary, in order to achieve successful and realistic routing of the example circuit (see below), to add a certain amount of refinement in both the expansion and backtracking phases of the algorithm. These are concerned with constraining the routes in certain ways so that the layout does not become a complete “spaghetti”. For example, routes are sorted by increasing length and each grid point is assigned a weight to attempt to keep routes away from pins. The layout contains over 3000 connections points and 1506 interconnections, and the data is available in the file mainboard.txt.

For our study we developed four versions of the Lee routing code:

• Lee_Router contains the sequential version of the application.
• Lee_TM contains the straightforward transactional memory version of the application.
• Lee_TM_p contains the transactional memory version but privatization has been applied to the grid representing the circuit.
• Lee_TM_p_ws contains the transactional memory with privatization version plus the write set optimization (read [1] for more details). Domain knowledge allow us to reduce the read set of a transaction to be equal to the write set.

To run any of the four versions of the application you will also need some extra classes (Frontier, Frontier_List, WorkQueue, and Viewer).

Download and Run it

The source files are available individually (see above links) or as a ZIP file; lee-pact2007-v1_0.zip. This is the first release and its version number is 1.0. We have compiled and run the application as far back as a Java JDK 1.3. up to JDK 1.6. To run the non-transactional version, do
java Lee_Router mainboard.txt
and to run any of the transactional versions, do (e.g.)
java Lee_TM_p_ws mainboard 100
where 100 is the number of simultaneous transactions attempted (or “batch size” - see [1] for more details on the abstracted transactional memory system). If this parameter is <= 0, its value is treated as infinite, i.e. all transactions are run. Note it is generally necessary to increase the amount of heap space, using -Xmx512M, for example.

Reference

[1] Ian Watson, Chris Kirkham and Mikel Luján. A Study of a Transactional Parallel Routing Algorithm. In Proceedings of the 16th International Conference on Parallel Architectures and Compilation Techniques (PACT 2007), Brasov, Romania, Sept. 2007, pp 388-398.[BibTex][EndNote][IEEE PDF][preprint PDF]
IEEE Copyright Notice. Personal use of this material is permitted. However, permission to reprint/republish this materialfor advertising or promotional purposes or for creating newcollective works for resale or redistribution to servers or lists,or to reuse any copyrighted component of this work in other worksmust be obtained from the IEEE.