Applying Dataflow and Transactions to Lee Routing

Date Added: Mar 2012
Format: PDF

Programming multicore shared-memory systems is a challenging combination of exposing parallelism in their program and communicating between the resulting parallel paths of execution. The burden of communication can introduce complexity that is hard to separate from the pure expression of the algorithm and can negate the performance that is gained from parallelism. The authors are extending the Scala language with data flow for creating parallelism and transactions for the controlled mutation of shared state. They take an early look at applying this paper to Lee's algorithm for routing circuit boards and consider the potential benefits of programming with this system with regard to the elegance of expression and the resulting performance.