Applying dataflow and transactions to Lee routing.January 2012
Programming multicore shared-memory systems is a challenging combination of exposing parallelism in your 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. We are extending the Scala language with dataow for creating parallelism and transactions for the controlled mutation of shared state. We take an early look at applying this work to Lee's algorithm for routing circuit boards and consider the potential bene_ts of programming with this system with regard to the elegance of expression and the resulting performance.We show how our approach reduces the number of lines of code and synchronisation operations needed, at the same time as improving real-world performance.
Authors: Chris Seaton, Daniel Goodman, Mikel Lujan, Ian Watson
Venue: Workshop on Programmability Issues for Heterogeneous Multicores (MultiProg)