Archive for March, 2009

Work stealing and implementation of runtime systems

Monday, March 16th, 2009 by Graham

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 [3]. There was a brief passage about the optimality of work stealing [1], to get straight into the new paper about the runtime support for multicore Haskell [2]. 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” [4] 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 [5].

[1] Scheduling multithreaded computations by work stealing
[2] Runtime Support for Multicore Haskell
[3] Erlang Multicore
[4] Idempotent Work Stealing
[5] Dynamic Circular Work-stealing deque

Breadth first labelling

Friday, March 6th, 2009 by Graham

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)