Peter talked about work-stealing and implementation of runtime systems. We started with briefly discussing a simple implementation of a runtime system, and the scalability problems that you get . There was a brief passage about the optimality of work stealing , to get straight into the new paper about the runtime support for multicore Haskell . At the end we concluded with questioning the premises that seems common: each task is executed exactly once. There is a nice new paper called “Idempotent Work Stealing”  which changes the premise to “each task is executed at least once” and show by microbenchmarks that puts and takes executed on this queue only costs 60% of the Chase-Lev algorithm .
Archive for March, 2009
I talked about Jones and Gibbons’ breadth first labelling algorithm, which uses cyclic programming:
-- Binary trees with labels in the nodes: data Tree a = Leaf | Node (Tree a) a (Tree a) -- Breadth first labelling function that works by taking a -- stream comprising the first label for each level as an -- additional argument, and returning a stream comprising -- the next label for each level as an additional result: label' :: Tree a -> [Int] -> (Tree Int, [Int]) label' Leaf ns = (Leaf, ns) label' (Node l x r) (n:ns) = (Node l' n r', n+1 : ns'') where (l',ns') = label' l ns (r',ns'') = label' r ns' -- The desired stream of labels itself can then be constructed -- by feeding the result stream back as the argument stream: label :: Tree a -> Tree Int label t = t' where (t',ns) = label' t (1:ns)
Various related topics were then discussed, including Banach’s fixed point theorem (Thorsten), the construction of final co-algebras (Thorsten), and a queue-based algorithm due to Okasaki (Nisse)