grid-ireland – New Execution Models and Different Algorithms

grid-ireland has been established to link compute clusters at three partner sites in Ireland: the Departments of Computer Science in Trinity College Dublin, University College Cork and NUI Galway.

What if grids were better served by a totally different execution models and substantially different algorithms than heretofore? University College Cork and NUI Galway intend to explore these possibilities, both on grid-ireland.

Revolution
Like both dataflow and demand-driven execution models, condensed graphs (CGs) view an execution as a set of computational nodes, connected by paths along which data-values move, in a manner determined by the exact graph, and the rules underlying that model. CGs however, offer a generalisation of both data-flow and demand-driven configurations: each can be straightforwardly transformed into a CG equivalent, and furthermore CGs can be constructed which contain elements exhibiting both behaviours. The same model is inherently parallel, but can equally well express sequential, imperative-style computations.

An important property of CGs is their multi-level, hierarchical, structure. Replacing a cluster by a single node representing the same computation may condense structured graphs; this is analogous to a fold operation in a source-level program transformation. The dual operation, evaporation, is comparable to a program transformation unfold. By this device, it is possible to alter how much detail of a computation it is desired to expose at any given time, thereby making the representation more or less abstract.

Condensed Graphs can act equally well as both an abstract or physically realized machine, and as an intermediate representation: compiling the C intermediate code now requires, not an actual translation into a different representation, but rather is a matter of transforming the code into graphs which are less abstract, and which have more specificity to given hardware. Many of the techniques of source-to-source program transformation can be carried over into the CG world, allowing code optimisations to be expressed as graph transformations. Having done this we can then either execute the 'intermediate' representation directly, using the Condensed Graph Abstract Machine (CGAM) model; or it can be used as a true intermediate representation, compiling the CG code down to native code as a final step.

The Centre for Unified Computing in University College Cork is implementing CGs on a rich variety of platforms, and this work is already well under way. The grid offers a valuable opportunity to test the process of obtaining different machine-level CG realizations.

Algorithms
It is clear to the emerging grid community that the grid is so different that existing application-level algorithms are often quite unsuited. NUI Galway intends to explore and advance the algorithmic base via real medical applications. NUI Galway is currently developing algorithms for determining the passage of low energy optical photons through the body, and intends to apply them to the higher energy regime where different nuclear cross sections and scattering behaviour is expected.

These algorithms will be in the area of simulations for radiotherapy purposes. Patient treatment planning is a crucial aspect of any course of radiotherapy. In essence this consists of some scans that determine the best machine configuration to give the optimum dose to the patient. The best method is via Monte-Carlo simulations where the track of a large number of particles is followed through the scattering material. Although analytical techniques have been used they are not as accurate. Monte-Carlo simulations, however, require the use of many particles to gauge accurately the degree of scatter and attenuation, see Figure 1. Such calculations can also help determine when a particular round of treatment has not given the tumour the desired dose. Figure 2 illustrates this problem.

Figure 1: A scan followed by simulations involving 10,000 to 10 million particles (courtesy Lawrence Livermore Labs).

Figure 2: The tumour is shown in the first figure, the planned treatment in the second (analytical approach). In the third a Monte Carlo simulation shows that not all the tumour has been irradiated.

NUI Galway intends to develop similar Monte-Carlo code but without the requirement for a large computer to be on-site within each hospital. This can be done by taking the code developed for optical imaging and photo-dynamic therapy purposes, and modifying the underlying physics for X-rays rather than photons. The results could be used for setting radiotherapy machines, and so are expected to be of interest to the major local hospitals employing radiotherapy at each of the grid sites, that is, in Dublin, Cork and Galway.

Finally we intend to investigate the emerging technique of adaptive mesh simulation. In a typical analytical simulation a fixed grid is used to describe a physical phenomena and the forces at each node are calculated for a series of time steps. A better solution is to vary the grid spacing and structure dynamically through the calculation. The grid with its different architectures is an ideal platform for both calculating the node forces and the subsequent grid topology.

Please contact:
John Morrison - University College Cork
Tel: +353 21 4902 914
E-mail: j.morrsion@cs.ucc.ie

grid-ireland - New Execution Models and Different Algorithms