Agenda items are in blue.

1. Where we've been
  • Vis'06 (DD / RB)
  • VMV (RB)
  • FUN afternoon (CR)

DJD sent Vis trip report earlier.

Quality of VMV conference disappointing. Mostly modelling and rendering (medically oriented), mostly German (only two foreign papers), and mostly student or early-career submissions. Our paper was rather harshly received, an interesting contrast with Vis's openness. Smaller community tends to want more pretty pictures. Mathematics (and code) are less welcome. A real application would help in presentation.

FUN in the afternoon. Once per term, UK academics, seminar with a few (invited) talks. No formal proceedings, just for interest. First held at Oxford, next one in Nottingham. Common focus was mainly functional programming itself, rather than e.g. applications.

2. Generics (DD)
  • review of two approaches
  • vis combinators, program construction & transformation

Deferred until DJD is available.

3. Laziness
  • streaming vs out-of-core memory layout methods (RB)

RB introduced the problem of traversing irregular grids, e.g. triangular meshes. One alternative is to take the spanning tree of the adjacency graph, yielding a linear stream of cells. The difficulty is that this kind of streaming is not suitable for some views: bad for the user, because the interesting data might appear last in the stream; bad for the implementer, because they have to traverse the whole stream.

A better alternative is space-filling curves, e.g. Hilbert, Peano, Lebesgue, Sierpinski. Maps an n-dimensional space to a 1-dimensional interval (stream), but preserves locality. Because of their fractal nature, they can be used for increasing hierarchical refinement of graphical rendering. SFCs can be defined by simple recursive grammars. They have a cache-efficient implementation. Dataset files are essentially re-ordered into SFC sequence, and the old file discarded.

The Lebesgue curve is widely used, good locality, orders data in a hierarchical granularity. Sierpinski is 2D only - question of 3D curve is open! In principle has better locality (for tetrahedra) than Lebesgue. RB has implemented marching cubes with a Lebesgue SFC.

Suggestion: is there any scope for polytypic SFCs? i.e. generic over the particular curve chosen.

Reference: Hans Sagan, "Space Filling Curves", Springer-Verlag, 1994.

4. Grid
  • progress at Leeds (RB)
  • progress at York (MW)
  • proto-tasks

MW is preparing a memo that sets out a combinator-library-like scheme such as we might want to use for our applications. Discussion about concurrent Haskell, parallel Haskell, distributed Haskell, Eden, positions in the design space, and where distribution combinators fit in. (Note that concurrent haskell now works on multi-core processors.) Memo will also compare toolkits and underlying infrastructure e.g. MPI, PVM, Globus.

Idea of the combinators is to replace high-level glue like the composition operator (.) with distributed versions of the same operators (<.>). New combinators can be defined at will, in terms of just three new primitives for I/O based message-passing between machines:

  • distribute -- like fork, but starts one thread on another machine
  • send -- communication
  • recv -- communication 
(f <.> g) a = unsafePerformIO $
    distribute (\tid-> let loop []     = do send tid Nothing
                           loop (x:xs) = do send tid (Just x)
                                            loop xs
                       in loop (g a) )
               (\tid-> do xs <- lazyGetContents tid
                          return (f xs))
  where lazyGetContents tid =
	    do v <- recv tid
	       case v of
		 Nothing -> return []
                 Just x  -> do xs <- unsafeInterleaveIO (lazyGetContents tid)
			       return (x:xs)

Example given here is one-way communication of a stream of values. Other examples could have two-way communication e.g. for computational steering.

Explicit message-passing currently exists in concurrent Haskell (standard in GHC, Hugs), but assumes multi-threading on a single shared-memory machine (possibly multi-CPU).

Parallel Haskell (GpH, Eden) has implicit communication (no message-passing at user level), and the runtime system goes to a lot of trouble to give the illusion of a shared memory machine distributed over many machines.

Distributed Haskell goes for explicit messages, but built on top of the GpH runtime system, so same shared-memory model. Might be OK as a basis, but implementation is alpha-quality, might have bit-rotted.

Our point in the design space is explicit distribution, explicit messages, but no shared memory assumption.

We don't yet know how implementable it is. Toolkits like MPI, PVM, Globus, might give us some help, but unclear which is best.

The intent is for MW, CR, progressively to implement all of the mini grid tasks we suggested early in the quarter, in C and Haskell, using whatever tools we have to hand. This is to get some idea of possible good avenues, and pitfalls. RB raised a query about whether 64-bit ghc is a problem on the WRG. Also, Leeds currently has Globus 4.0.2, York has 4.0.3.

5. Where we're going (ALL)
  • shaping our view of FP + grid + vis

Deferred until DJD is available.

6. Opportunities / open issues
  • graphic quality

Current graphic interface is naive, not really suitable for actual deeper investigation of the visualised dataset. Does this undermine the credibility of our results? Even though it is independent of the goals of the project? Is it that HOpenGL is insufficient? Partly just that showing a single isosurface is not enough - need more richness in the quality of the data displayed - but the quality of the final rendering is not really something we can address. Build a better GUI using something like Qt, Gtk, or wxHaskell.

  • parallelism (IBM cell multiprocessor)

Multi-core processors - link with concurrency in Haskell for true parallelism? Student project? Summer of Code project? Interesting to do something with graphics and Haskell and IBM Cell processor. (Student at York, because of better foundation in functional programming?) Could be relevant to Grid, since Grids involve shared-memory multi-processors in addition to distributed machines.

  • real applications

Locate a realistic problem, even if small, involving a collaborator local to Leeds or York e.g. seismology, medical, biochemists. Idea is to gain understanding of the real things people try to do with visualisation. Probably one of the most important opportunities to seize.

7. Future plans
  • Edinburgh meeting - what is our agenda?

CR suggested we each write down three things we hope to achieve at the Edinburgh meeting.

Malcolm

  1. sanity check on our initial grid ideas, by more experienced folks
  2. find out whether GRID-GUM is of any use to us
  3. get Edinburgh folks to take an application from us and GRID-ise it(!)

Colin

  1. get a view/feedback on our provisional approach to grid, and other topics like concurrency
  2. by proxy, learn about state of the art in grid computing: what were the big thinking points
  3. ideas for what kinds of benchmark problems can separate techniques that work, from those that do not.
  4. establish friendly relations with possible collaborators, future exchange of information, possible mutual grid access

Rita

  1. learn from experiences in applying FP to Grid (State of the Art experts, achievements, limits)
  2. what is a feasible target for us?
  3. have they thought about polymorphism/polytypism?

Rough plan for meeting:

  1. general introduction to PolyFunViz project, rerun of Vis ideas (DJD?)
  2. outline of MW's tentative grid combinators
  3. hear about GRID-GUM (Edinburgh people)
  4. discussion, maybe focussed by a couple of questions from the above list

CR to send out our hopes ahead of time by email, and ask for their hopes too. (CR to make contact, after talking with DJD.)

  • VMLS book chapter

deadlines: abstract mid Jan, paper end Jan.

  • EG'07?

deadline: Feb

  • Vis'07?

deadline: Mar/Apr

  • supercomputing - do we need to track the community there?

go to conference just to see what it is like? hot topics, whether we can contribute, etc.

  • FUN afternoon

Next in Nottingham in Feb, elsewhere in May, possibly York next Nov. DJD suggested offering a talk, CR not clear on exactly what contribution to give. Perhaps telling a story about how far we have got with polytypic things?

8. Any other business

CR to provide roadmap of FP-related conferences coming up:

ICFP TFP IFL

Wonders if there is a Grid-related workshop as a venue for describing our grid experiments. Europe: super-grid (or similar). Difficulty in finding an honest, non-hyped one. (Good question to ask the Edinburgh people!)

PolyFunViz meet again early in the new year. Before end Jan?