Go to main content

School of Computer Science Intranet

Lee's Routing Algorithm: An Application for Transactional Memory

[TM project] [TM publications][PACT 2007 source code]

Lee's routing algorithm is one of the first algorithms used in automatic circuit routing. Lee's routing algorithm is interesting for TM because: it is an example of a real-world application, it contains an abundance of potential parallelism due to the number of routings that need to be performed in a typical realistic circuit, and this abundance of parallelism is difficult to exploit efficiently using locks. This website contains the code and data for Lee-TM used in our papers. It does not contain the code for the different software TM systems.

Circuit layout used in experiments

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. Unless otherwise mentioned, the code copyright is held by the University of Manchester, and the code is provided "as is" without any guarantees of any kind and is distributed as open source under a BSD license.

We would be grateful if you referenced the papers [1, 2] when you use the code. We would like to hear from you if you have any feedback or bugs to report.

RSTM

The source files for the RSTM implementation are available here; lee-rstm-v1.0.zip. This is the first release, version 1.0.

tinySTM

The source files for the tinySTM implementation are available here; lee-tinystm-v1.0.zip. This is the first release, version 1.0.

TL2

The source files for the TL2 implementation are available here; lee-tl2-v1.0.zip. This is the first release, version 1.0.

Java Lock-based

The source files for the coarse-grain implementation published in [2] is available here; lee-cg-v1.0.zip. This is the first release, version 1.0.

Acknowledgements

Thanks to Aleksandar Dragojevic of EPFL for porting Lee-TM to TL2 and tinySTM.
This project is funded by EPSRC.

References

[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.
[PDF] [BibTeX][source code]

[2] Mohammad Ansari, Christos Kotselidis, Kim Jarvis, Mikel Luján, Chris Kirkham, and Ian Watson.
Lee-TM: A Non-trivial Benchmark for Transactional Memory.
In Proceedings of the 8th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2008), Aiya Napa, Cyprus, June 2008.
[PDF] [BibTeX]