Alan Stewart
email: a.stewart@qub.ac.uk

Under consideration for publication in Formal Aspects of Computing

Keywords: BSP, state-based reasoning, partitioned synchronisation, UTP, parallel by merge, refinement, weakest preconditions

A BSP superstep is a distributed computation comprising a number of simultaneously executing processes which may generate asynchronous messages. A superstep terminates with a barrier which enforces a global synchronisation and delivers all ongoing communications. Multilevel supersteps can utilise barriers in which subsets of processes, interacting through shared memories, are locally synchronised (partitioned synchronisation). In this paper a state-based semantics, closely related to the classical sequential programming model, is derived for distributed BSP with partitioned synchronisation.

Introduction

One inherent difficulty in the development of scientific software is the reconciliation of the requirements that code be both correct and efficient. Placing too much emphasis on correctness may result in an abstract, but inefficient, programming model. Many members of the scientific programming community have unjustly rejected functional programming languages because of perceived performance inadequacies. Alternatively, striving for optimal efficiency can run the risk of comprising software correctness and can result in the employment of architecture-specific programming models. In this paper it is proposed that the BSP [START_REF] Bisseling | Parallel Scientific Computation: A Structured Approach using BSP and MPI[END_REF][START_REF] Mccoll | Scalable computing[END_REF][START_REF] Valiant | A bridging model for parallel computation[END_REF][START_REF] Valiant | A Bridging Model for Multi-core Computing[END_REF] model of distributed computation combines the benefits of a well-established cost calculus (for evaluating program efficiency) with the advantages of a simple programming framework closely related to sequential program refinement.

A BSP computation comprises a sequence of supersteps. A superstep contains a set of independent processes, each with local memory, which perform computations and generate asynchronous communications. A superstep terminates with a global barrier which synchronises processes and delivers ongoing communications. The cost of a superstep S with p processors can be calculated using the following assumptions:

• a basic arithmetic operation or local memory access has unit cost;

• the maximum number of local operations performed by a process is w;

• the maximum number of I/O operations performed by a process is h; • the ratio of communication cost to the unit cost is g and Correspondence and offprint requests to: Alan Stewart • the cost of synchronising all of the processes within S is L.

The total cost of superstep S is defined to be w + h × g + L. A wide range of parallel algorithms have been developed and analysed using the BSP cost calculus.

A variant shared memory version of BSP, BSPRAM, has been proposed by Tiskin [START_REF] Tiskin | The Bulk-Synchronous Parallel Random Access Machine[END_REF]. Again superstep processes are independent with being used to synchronise processes and update shared memory. BSPRAM has been refined to a multilevel variant [START_REF] Valiant | A Bridging Model for Multi-core Computing[END_REF] by partitioning shared memory into a hierarchy. Memory at the top of the hierarchy is assumed to have the highest access cost while cache memories at the process level have the lowest access costs. Figure 1 shows a memory configuration for four processes, P 1 , . . . , P 4 : processes P 1 and P 2 have access to memory M 12 while processes P 3 and P 4 have access to memory M 34 . All processes can (indirectly) access the memory M 1234 . Processes can be synchronised in various ways: for example,

• processes P 1 and P 2 and processes P 3 and P 4 can be synchronised independently (partitioned synchronisation); P 1 and P 2 interact through M 12 while P 3 and P 4 interact through M 34 . The notion of having sub-machine synchronisations in BSP was first proposed by de la Torre and Kruskal [START_REF] De La | Submachine Locality in the Bulk Synchronous Setting[END_REF]. • all processes can be synchronised with global interactions occurring via the shared memory M 1234 .

Multilevel BSP can be used to analyse the computational cost of BSP algorithms on multicore architectures. For example, the architecture in Figure 1 has an associated 3-level cost model [START_REF] Valiant | A Bridging Model for Multi-core Computing[END_REF]. Each level is associated with four cost parameters: (p i , g i , L i , m i ) where p i is the number of level i -1 components inside a level i component, g i is the communication bandwidth (relative to the basic computational cost) from level i to level i + 1, L i is the cost of synchronising all of a level i's sub-components and m i is the size of memory available at level i. More realistically, consider a cost model for an architecture containing 4 identical multicores, each having 8 cores 1 . Each core has a cache memory and associated cost parameters:

(p 1 = 1, g 1 = 1, L 1 = 3, m 1 = 8kB)
Here L 1 refers to the cost of synchronising internal core threads. Each multicore has memory accessible by all its cores -L 2 is the cost of internal core synchronisation at the chip level while g 2 is the cost for a multicore to access level 3 memory:

(p 2 = 8, g 2 = 3, L 2 = 23, m 2 = 3M B)
1 The example given here is based on the cost model for Sun Niagara UltraSparc T1 multicore chips given in [START_REF] Valiant | A Bridging Model for Multi-core Computing[END_REF].

The overall architecture contains a large globally accessible memory:

(p 3 = 4, g 3 = ∞, L 3 = 108, m 3 ≤ 128GB)
This example illustrates how partitioned synchronisation has the potential to be much less computationally expensive than global synchronisation (see the L 2 and L 3 costs above). Architectures comprising a number of multicores may be assembled either by building an interconnect network linking the multicores or by adding an overarching memory hierarchy (as described above). The intent of this paper is to model different forms of synchronisation patterns (rather than the details of memory hierarchies). In particular, localised barriers are distinguished from global synchronisations.

A state-based semantics [START_REF] Back | Invariant based programming: basic approach and teaching experiences[END_REF][START_REF] Back | Refinement Calculus: A Systematic Introduction[END_REF][START_REF] Backhouse | Program Construction: Calculating Implementations from Specifications[END_REF][START_REF] Dijkstra | A constructive approach to the problem of program correctness[END_REF][START_REF] Dijkstra | A Discipline of Programming[END_REF] for distributed BSP with partitioned synchronisation is derived. The intent is twofold:

1. to devise a BSP program development framework akin to the classical sequential refinement approach of Dijkstra. To this end a superstep is treated as a state transformer (in much the same way that assignments are treated in Dijkstra's guarded command language [START_REF] Dijkstra | A Discipline of Programming[END_REF]); and 2. to provide an abstraction (partitioned synchronisation) which distinguishes different kinds of barrier.

Alternative BSP semantics have been developed with different goals in mind:

1. Jifeng, Miller and Chen [START_REF] He | Algebraic Laws for BSP Programming in Euro-Par'96[END_REF] give a reactive trace-based semantics for BSP; 2. Yifeng Chen [CS04, CS03] has devised a design logic, LOGS (logic of global synchrony), for use in the formal development of BSP programs. LOGS uses a process-based approach to program design; and 3. Loulergue, Hains, and Fosy have developed a functional model of BSP [START_REF] Loulergue | A calculus of BSP Programs[END_REF] with the aim of combining the speed gains of parallel computation with the benefits of algebraic reasoning. The approach has been developed to provide a BSP skeleton framework [START_REF] Javed | OSL: Optimized Bulk Synchronous Parallel Skeletons on Distributed Arrays[END_REF].

In §2 a brief overview of some of the pertinent features of the UTP [START_REF] Hoare | Unifying Theories of Programming[END_REF] framework for program construction is presented. A distributed stated-based superstep semantics is devised in §3. Superstep laws and termination properties are listed in §4 while a weakest precondition semantics for barrier synchronisation is defined in §5. Under certain conditions a superstep can be decoupled into less computationally expensive, localised, operations [START_REF] De La | Submachine Locality in the Bulk Synchronous Setting[END_REF][START_REF] Valiant | A Bridging Model for Multi-core Computing[END_REF]. In §6 a variant form of barrier, partitioned synchronisation, is defined. In §7 a superstep program environment is described and in §8 a specification of PrefixSum is refined into a BSP system which utilises a number of partitioned synchronisations. Finally, in §9 it is shown how to refine superstep systems into compositions of interfering processes.

Preliminaries: Unified Theories of Programming (UTP)

UTP [START_REF] Hoare | Unifying Theories of Programming[END_REF] is a framework for refining predicates into programs. Here a brief overview of those features of UTP that are relevant to the development of a multilevel BSP programming model is given. A predicate P is defined over a finite set of (free) variables αP where αP = inαP ∪ outαP and where inαP is a set of undashed variables (initial values) and outαP is a set of dashed variables (final values). The predicate x ′ = a + x ∧ a ′ = a with alphabet {x, a, x ′ , a ′ } corresponds to the program x := a + x. The operation SKIP over an alphabet A = {x, x ′ } is defined as

II A = df x ′ = x
Predicates may be composed using the operators ¡ £ (selection), (independent parallel composition), ⊓ (non-deterministic choice) and ; (sequential composition):

P ¡ b £ Q = df (P ∧ b) ∨ (Q ∧ ¬b)
where αb

⊆ αP = αQ P Q = df P ∧ Q where outαP ∩ outαQ = {} P ⊓ Q = df P ∨ Q where αP = αQ P (m, m ′ ); Q(m, m ′ ) = df ∃v.P (m, v) ∧ Q(v, m ′ ) where outαP = {m ′ } ∧ inαQ = {m}
An additional operation (separating simulation) is used to rename an output variable of a predicate (and adjust the alphabet of the predicate accordingly). For example, the simulation U 0 renames m ′ as 0.m ′ :

U 0 (m) = df ∃0.m.∃m ′ .0.m ′ = m αU 0 (m) = df {m, 0.m ′ } A simulation U 1 (m)
which renames m ′ as 1.m ′ can be defined in a similar way. Finally, the alphabet of a predicate R can be extended to include the variables x and x ′ as follows: R +x = df R ∧ x ′ = x. For example suppose that a predicate P has variable m in its alphabet. The predicate P ; U 0 (m) +outαP \{m} has alphabet (αP \{m ′ })∪{0.m ′ } and is such that the output m ′ of P is equivalent to output 0.m ′ of P ; U 0 (m) +outαP \{m} .

Barrier Synchronisation

A superstep contains a set of independent processes which perform computations and generate asynchronous communications. A superstep terminates with a global barrier which synchronises processes and delivers ongoing communications. Let variable m denote a set of ongoing asynchronous communications that have been generated but have not, as yet, been delivered. A set of communications is modelled as a relationship between destinations (i.e. the variables to be updated) and values -see [HMC96, SC01, SCG04]:

m : V AR → V AL
Here V AR is a set of variable names and V AL is a set of values.

Superstep SS(P, Q) comprises process bodies P and Q; SS(P, Q) is well-defined if the variables occurring in P and the variables occurring in Q have, at most, the name m in common:

αP ∩ αQ ⊆ {m, m ′ } For example, if αP = {x, m, x ′ , m ′ } and αQ = {y, m, y ′ , m ′ } then SS(P, Q) is a valid superstep.

The definedness condition above permits superstep processes to be executed independently (see below).

A superstep process is a sequence of conventional programming instructions and asynchronous communication operations. Execution of the asynchronous communication put(x, e) evaluates the local expression e and sends the resulting value, asynchronously, to the "foreign" variable x; semantically put(x, e) is defined to update the communication space m as follows: put(x, e) = df m := m ∪ {x → e} An asynchronous send put(x, e) in process P is well-defined if αe ⊆ αP where αe denotes the set of variables that occur in expression e. In a superstep different processes may generate and send inconsistent messages to the same destination variable. For example, P may contain the statement put(x, 1) while Q contains put(x, 2). In this case the combined set of ongoing communications has the form m = {. . . , x → 1, x → 2, . . .} SS(P, Q) is defined in such a way that component processes utilise disjoint output communication spaces. The separate communication spaces are merged ( §7.2 [START_REF] Hoare | Unifying Theories of Programming[END_REF]) and the resulting messages are delivered in a terminating barrier, SY N C.

Let P 0 = ∃m.m ′ = {}; P ; U 0 (m) +αP \m Q1 = ∃m.m ′ = {}; Q; U 1 (m) +αQ\m
be independent processes generated by renaming the output variable m ′ in both P and Q. Note that P 0 and Q1 are initialised using empty communication relations. Superstep SS(P, Q) first executes P 0 and Q1, thereby performing local computations and generating asynchronous communications. Subsequently the asynchronous messages are delivered in parallel. Let A = αP \{m, m ′ } and B = αQ\{m, m ′ }: Then:

SS(P, Q) = df ∃0.m ′ , 1.m ′ .(P 0||Q1); SY N C((A ∪ B) ¡ (0.m ∪ 1.m)) A∪B
Here γ ¡ m denotes the restriction of the domain of map m to the set γ:

γ ¡ m = df {x → y|(x → y) ∈ m ∧ x ∈ γ}
The operation SY N C(m) γ is a variant form of parallel assignment which models the behaviour of a barrier synchronisation for a communication map m and an alphabet γ where dom(m) ⊆ γ and where dom is a function which returns the domain of its argument.

αSY N C(m) γ = γ If f is a function then SY N C(f ) γ is a deterministic set of parallel assignments: SY N C(f ) γ = ∀x ∈ γ.x ′ = f (x) ¡ x ∈ dom(f ) £ x ′ = x (1) = || x∈dom(f ) x := f (x)
Here x is a meta-variable (rather than a conventional programming variable). It follows that

SY N C({}) γ = II γ
If the map m is not a function then SY N C(m) γ is defined non-deterministically:

SY N C(m) γ = df ⊓ f m SY N C(f ) γ (2)
Here f m denotes the set of functions f which cover m and are consistent with it:

f m = df f ⊆ m ∧ f unction(f ) ∧ dom(f ) = dom(m)
For example, if m = {x → 1, x → 2, y → 1, y → 2} four functions can be extracted from m using :

f 1 = {x → 1, y → 1}, f 2 = {x → 2, y → 1}, f 3 = {x → 1, y → 2} and f 4 = {x → 2, y → 2}.
The set {f |f m} is guaranteed to be non-empty. The degree of non-determinism of SY N C(m) γ is bound for finite m (if the cardinalities of the domain and range of m are a and b, respectively, then at most b a functions can be extracted from m). Synchronisation is destructive in that destination variables are overwritten; an alternative form of barrier SY N C + (m) γ updates destination variables by adding message content to destination content. For functional f :

SY N C + (f ) γ = ∀x ∈ γ.x ′ = x + f (x) ¡ x ∈ dom(f ) £ x ′ = x For non-functional m, SY N C + (m) γ = ⊓ f m SY N C + (f ) γ A superstep with barrier SY N C + is denoted SS + (P, Q) (see §8).

Superstep laws and termination

Supersteps inherit many of the properties of parallel composition:

SS(P, Q) = SS(Q, P ) SS(II A , II B ) = II A∪B SS(P ¡ b £ Q, R) = SS(P, R) ¡ b £ SS(Q, R) SS(P ⊓ Q, R) = SS(P, R) ⊓ SS(Q, R) If αP ⊆ αP ′ \{m, m ′ } and αQ ⊆ αQ ′ \{m, m ′ } then (P Q); SS(P ′ , Q ′ ) = SS(P ; P ′ , Q; Q ′ ).
The semantics of supersteps can be extended to reason about termination. In UTP a design P ⊢ Q is such that if assumption P holds then it is guaranteed that Q terminates in a state specified by Q [START_REF] Hoare | Unifying Theories of Programming[END_REF].

P ⊢ Q = df (ok ∧ P ) ⇒ (ok ′ ∧ Q)
Here the variables ok and ok ′ are used to record whether a program has been started and whether it has terminated, respectively. Predicate true denotes arbitrary behaviour (including possible non-termination) and can be represented by either f alse ⊢ f alse or f alse ⊢ true. The termination properties of supersteps are closely related to those of independent parallel composition. If a superstep process diverges then so too does the superstep:

SS(true, Q) = true
If the component processes of a superstep terminate then so too does the superstep:

P 0 ⊢ P , Q 0 ⊢ Q P 0 ∧ Q 0 ⊢ SS(P, Q)
Terminating superstep processes can only generate finite communication spaces.

A Weakest Precondition semantics for SY NC

A weakest precondition semantics of SY N C(m) γ is derived below. Let P be a predicate and f be a finite function with dom(f ) ∈ αP . P f denotes P modified by the application of the simultaneous substitutions {x → f (x)|x ∈ dom(f )}. Let x and y be variables, c a constant, P and Q predicates, R a relation and k a fresh variable name: P f is defined over the structure of P as follows:

(¬P ) f = ¬(P f ) (x R y) f = x f R y f (P ∧ Q) f = P f ∧ Q f (P ∨ Q) f = P f ∨ Q f (∀x.P ) f = ∀k.(P x k ) f (∃x.P ) f = ∃k.(P x k ) f y f = f (y) ¡ y ∈ dom(f ) £ y c f = c (3)
Here e 1 ¡ b £ e 2 is e 1 if b is true and e 2 otherwise. It follows that P {} = P and P {x →v} = P x v (conventional substitution). The weakest precondition of a deterministic barrier SY N C(f ) γ is:

SY N C(f ) γ WP P = || x∈dom(f )∩γ x := f (x) WP P = P γ¡f
A substitution over a finite mapping m is defined as:

P m = df f m P f (4)
If dom(m) = {x} then f m P f degenerates to Dijkstra's semantics of non-determinism [START_REF] Dijkstra | A Discipline of Programming[END_REF] v∈rng(m) P x v . Thus, P m generalises the WP semantics of non-deterministic choice (⊓):

(P ⊓ Q) WP R = (P WP R) ∧ (Q WP R) P m is used to define the WP semantics of non-deterministic SY N C: SY N C(m) γ WP P = ⊓ f (γ¡m) SY N C(f ) γ WP P = f (γ¡m) (SY N C(f ) γ WP P ) = f (γ¡m) P f = P γ¡m
A weakest precondition of SY N C + can be devised by modifying the substitution rule P f to P +f :

y +f = y + f (y) ¡ y ∈ dom(f ) £ y

Partitioned synchronisation

Global synchronisation is often considered to be prohibitively expensive to implement. In certain situations superstep barriers can be implemented using localised forms of synchronisation. Let SS({P i |i ∈ I}) be a superstep comprising a set of processes indexed by a set I and let P S be a partition of I:

partition(I, P S) = df ( J∈P S J) = I ∧ ∀J, K ∈ P S. J ∩ K = {} ⇒ J = K
Superstep processes can always be decoupled since they are independent:

|| i∈I P i = || J∈P S (|| j∈J P j )
A termination barrier can be decoupled using partition P S if the set of messages generated within each partitioned set of processes is destined for delivery within the same process set: partition(I, P S) ∧ ∀J ∈ P S. j∈J dom(j.m) ⊆ j∈J αP j

SY N C( i∈I i.m) = || J∈P S SY N C( j∈J i.m) (5)
In such circumstances an implementation need only synchronise sets of processes within the same partition.

The smallest partition partition(I, {I}) contains one index set and corresponds to complete inter-dependence. The largest partition, partition(I, {{i}|i ∈ I}) corresponds to a completely decoupled system. Consider a superstep SS({P i |i ∈ I 1 ∪ I 2 }) where I 1 = {2, 4, . . . , 2 n } and I 2 = {1, 3, . . . , 2 n -1}. If even(odd) indexed processes communicate only with other even(odd) indexed processes then

SS({P i |i ∈ I 1 ∪ I 2 }) = SS({P i |i ∈ I 1 })||SS({P i |i ∈ I 2 })
If the process sets {P i |i ∈ I 1 } and {P i |i ∈ I 2 } are assigned for execution to sets of cores which either have a shared memory or a fast localised interconnect network then SS({P i |i ∈ I 1 ∪I 2 }) can be implemented in a way that exploits the computing potential of the hardware. Such a partitioned synchronisation is likely to execute faster than a conventional BSP barrier which enforces a global synchronisation. Partitioned synchronisation can be characterised by the following algebraic law:

A ∩ B = {} ∧ dom(m) ⊆ A ∧ dom(n) ⊆ B SY N C(m ∪ n) A∪B = SY N C(m) A SY N C(n) B (6)

Superstep systems

Supersteps may be embedded within a sequential programming framework; in this way BSP systems can be developed using conventional "sequential refinements" while the inherent parallelism of superstep programs can be used to exploit the computational potential of multiprocessor architectures (see §9).

The embedding of supersteps within a sequential programming environment requires a generalisation of the definition of superstep. Consider the repetitive ( * ) construct below:

var i = 0; (i = n) * (SS(P, Q); i := i + 1) end i
Here superstep processes P and Q share a "global" variable, i; in order to maintain superstep process independence i must be read-only for both P and Q (although i can be updated at a barrier). Let α W P denote those variables which can be updated by P . For example, α W put(i, e) = {m} and α put(i, e) = {i, m} ∪ αe. Processes P and Q are independent if

α W P ∩ αQ ⊆ {m} ∧ α W Q ∩ αP ⊆ {m}
This modified definition of independence allows P and Q to share read-only variables.

All supersteps in a system must have a fixed degree of parallelism, say k. The ith superstep process P i , 1 ≤ i ≤ k, has write access to a set of local variables, D i , and read-only access to a set of "global" variables, D 0 where ∀i, j.

1 ≤ i < j ≤ k ⇒ D i ∩ D j = {} ∧ D i ∩ D 0 = {} (i.e. α W P i ⊆ D i and αP ⊆ D 0 ∪ D i , 1 ≤ i ≤ k).
The structure of a superstep computation is outlined in Figure 2. The definition of a partitioned superstep is modified to ensure that "global" variables are not updated at barriers: partition(I, P S) ∧ ∀J ∈ P S.

j∈J dom(j.m)

⊆ j∈J D j SY N C( i∈I i.m) = || J∈P S SY N C( j∈J i.m) (7) C k ∈ Comp ::= SS(P 1 , . . . P k ) | J∈P S SS({P i |i ∈ J}) | x := e | C k 1 ; C k 2 | C k 1 ¡ b £ C k 2 | b * C k where P 1 , . . . P k ∈ Process, αP 1 ⊆ D 1 ∪ D 0 , . . . αP k ⊆ D k ∪ D 0 b ∈ BooleanExp, αb ⊆ D 0 , x ∈ D 0 , αe ⊆ D 0

The derivation of parallel prefix sum

The superstep framework above is used to derive a parallel program from a specification. The resulting program contains barriers with varying degrees of synchronisation. The derivation starts from a predicate specification and a number of refinement steps are carried out [START_REF] Back | Invariant based programming: basic approach and teaching experiences[END_REF][START_REF] Dijkstra | A constructive approach to the problem of program correctness[END_REF] until a superstep program is derived. The program development is heavily influenced by R. Back's approach to constructing programs from invariants. Given an integer l, 1 ≤ l, and an array A with integer elements

{a i |1 ≤ i ≤ 2 l } parallel prefix sum [Akl89] is specified as PrefixSum(l , A) = df ∀i.1 ≤ i ≤ 2 l .a ′ i = 1 ≤k ≤i a k
Here a i and a ′ i denote the initial and final states of array element a i , respectively. For example:

PrefixSum(2 , A) = a ′ 1 = a 1 ∧ a ′ 2 = a 1 + a 2 ∧ a ′ 3 = a 1 + a 2 + a 3 ∧ a ′ 4 = a 1 + a 2 + a 3 + a 4
The first step in the development of a program satisfying the specification is the creation of a predicate I(j, l, A) which generalises PrefixSum(l , A):

I(j, l, A) = df ∀i.1 ≤ i ≤ 2 j .a ′ i = 1≤k≤i a k ∧ ∀i.2 j < i ≤ 2 l .a ′ i = i-2 j <k≤i a k
It follows that I(0, l, A) = II and that I(l, l, A) = PrefixSum(l , A). A program which satisfies PrefixSum can be constructed by finding a mechanism for transforming I(0, l, A) into I(l, l, A). Using composition [START_REF] Hoare | Unifying Theories of Programming[END_REF] it can be shown (see refinement 1, Appendix) that 0 ≤ j < l ⇒ I(j, l, A); (|| 2 j <i≤2 l a ′ i = a i + a i-2 j ) = I(j + 1, l, A) Thus, in a conventional way PrefixSum(l , A) = var j := 0 ; (j = l) * ((|| 2 j <i≤2 l a i := a i + a i-2 j ) ; j := j + 1) end j The parallel assignment || 2 j <i≤2 l a ′ i := a i + a i-2 j can be refined (see refinement 2, Appendix) to: SS + (P 1 , . . . , P 2 l ) where

P i = df (put(a i+2 j , a i )) ¡ 1 ≤ i ≤ 2 l -2 j £ II ), 1 ≤ i ≤ 2 l
In this superstep program the set of global variables D 0 is {j} and each superstep process P i , 1 ≤ i ≤ 2 l has an alphabet α W P i = {a i }, 1 ≤ i ≤ 2 l . Consequently: PrefixSum(l , A) = var j := 0 ; (j = l) * (SS + (P 1 , . . . , P 2 l ) ; j := j + 1) end j Finally, the superstep within the loop body can be partitioned (see refinement 3, Appendix):

PrefixSum(l , A) = var j := 0 ; (j = l) * (|| J∈P I SS + ({P j |j ∈ J}) ; j := j + 1) end j
where the partition P I is:

P I = {{k, k + 2 j , . . . , k + 2 l -2 j }|1 ≤ k ≤ 2 j }.
Initially, when j = 0, P I = {{1, 2, . . . , 2 l }} -hence the initial superstep cannot be decoupled. When j = 1 P I = {{1, 3, . . . , 2 l -1}, {2, 4, . . . 2 l }} and the corresponding superstep can be partitioned into sets of even and odd indexed processes. When j = 2 P I = {{1, 5, . . . , 2 l -3}, {2, 6, . . . , 2 l -2}, {3, 7, . . . 2 l -1}, {4, 8, . . . 2 l }}. On the last iteration of the loop j = l -1 and P I = {{1, 1 + 2 l-1 }, {2, 2 + 2 l-1 }, . . . , {2 l-1 , 2 l }}: the superstep is decoupled into 2 l-1 independent parts. Each successive superstep contains fewer barrier dependencies and, consequently, has greater potential for efficient implementation.

The synchronisation cost for executing PrefixSum, for l ≥ 5, on the multicore architecture described in §1 is given under the assumption that processes are distributed over multicore chips as follows:

• Multicore 1 (M C 1 ): processes {P i |i ∈ {1, 5, . . . , 2 l -3}} • Multicore 2 (M C 2 ): processes {P i |i ∈ {2, 6, . . . , 2 l -2}} • Multicore 3 (M C 3 ): processes {P i |i ∈ {3, 7, . . . , 2 l -1}} • Multicore 4 (M C 4 ): processes {P i |i ∈ {4, 8, . . . , 2 l }}
The first two iterations of an execution of PrefixSum (see j = 0, 1 above) require two global synchronisations (cost 2L 3 ).

Further assume that processes assigned to M C 1 etc. are internally distributed over cores as follows:

• Core 1 (C 1 ): processes {P i |i ∈ {1, 33, . . . , 2 l -31}} • Core 2 (C 2 ): processes {P i |i ∈ {5, 37, . . . , 2 l -27}} . . .

• Core 8 (C 8 ): processes {P i |i ∈ {29, 61, . . . , 2 l -3}}

Iterations 3,4 and 5 can be synchronised using partitioned synchronisations at the multicore level (cost 3L 2 ). Finally the remaining iterations involve synchronisations at core level (cost (l -5) × L 1 , provided that the cores have sufficient memory). Thus, a non-partitioned version of the prefix sum program has associated synchronisation cost l × L 3 whereas the partitioned version has associated synchronisation cost 2 × L 3 + 3 × L 2 + (l -5) × L 1 where it is assumed that L 3 >> L 2 >> L 1 .

Implementation Projections

The proposed framework for developing BSP programs has a simple semantics because it is given at a system level. Unfortunately, a direct implementation of such a system would involve unnecessary synchronisations over statements containing shared variables (e.g. j := j +1 in PrefixSum). To resolve this problem a renaming process projection is defined. Projection P {x →i.x|x∈D0∪{m}} i maps a superstep system onto its ith component process where each shared variable, say x, is renamed i.x (see the definition of substitution in §5). P f i is defined by structural induction over superstep programs: P f i (SS(P 1 , . . . P k )) = df var i.m := {}; P f i (P i ); LSY N C i ({1, . . . , k}); end i.m

P f i (SS({P j |j ∈ I 1 }) SS({P j |j ∈ I 2 })) = df var i.m := {}; P f i (P i ); (LSY N C i (I 1 ) ¡ i ∈ I 1 £ LSY N C i (I 2 )); end i.m P f i ( x := e ) = df x f := e f P f i ( put(x, e) ) = df i.m := i.m ∪ ({j.x → e|1 ≤ j ≤ k} ¡ x ∈ D 0 £ {x → e}) P f i ( P ; Q ) = df P f i (P ); P f i (Q) P f i ( P ¡ b £ Q ) = df P f i (P ) ¡ b f £ P f i (Q) P f i ( b * P ) = df b f * P f i (P ) Here local synchronisation LSY N C is defined as a communicating CSP [HH98] process: LSY N C i (I) = df (( CSP j∈I-{i} c ij !αP j ¡ i.m) CSP ( CSP j∈I-{i} c ji ?j.m)) → SY N C( j∈I j.m)
where || CSP is the interfering parallel composition operator of CSP and {c ij |i, j ∈ I} is a set of communication channels connecting processes. LSY N C synchronises participating processes in a partition, acquires nonlocal communication data and updates its variables accordingly. Note that an asynchronous communication to a "global variable" is projected onto a set of communications to "local variables" -thus, supersteps with communications to "global variables" cannot be partitioned. A system S, with k processes per superstep, is implemented as a message passing system as follows: CSP i∈{1,...,k} P {x →i.x|x∈D0∪{m}} i (S)

The resulting composition can be directly implemented using an MPI-like [START_REF] Snir | MPI: The Complete Reference[END_REF] programming environment.

Conclusion

Ideally a computing environment should be designed in a top-down fashion, starting with a high-level programming model and ending with an architecture which supports the required high-level operations. One example of such an environment was the CSP \ OCCAM \ transputer system. Unfortunately, programming languages and computer architectures are usually designed independently. Currently there are acute difficulties (particularly in high performance computing) in finding a programming model which has a simple semantics appropriate for program development and which, at the same time, can be efficiently mapped onto multicore architectures. Co-Array Fortran (CAF) is a Single Program Multiple Data parallel language designed to exploit the computing potential of multicore architectures: processes can asynchronously read and write non-local data. Unless great care is taken when using synchronisation statements, process compositions may be associated with multiple execution paths -some of these may be unwanted (e.g. data a is read by P 1 from P 2 before P 2 has initialised a). It is highly undesirable that high-level languages offer the potential for programs to be subject to race conditions. It is proposed here that the BSP computational model should be re-evaluated for the following reasons:

1. Multicore chips are now being designed with 16 and 32 cores -on-chip synchronisation in such environments has the potential to be relatively inexpensive compared with synchronisation on distributed processor architectures. 2. For large scale architectures comprising numerous multicore chips the multilevel BSP model offers the potential for efficient execution of many applications (e.g. divide and conquer algorithms) through the use of partitioned synchronisation. 3. It has been demonstrated in this paper that multilevel BSP has an associated programming model with simple reasoning and refinement laws It is proposed that BSP programs be constructed in two phases: an initial sequential-like system development followed by a projection onto localised process computations. The first phase provides the benefits of reasoning about systems in a sequential-like way while there is potential for developing tools to carry out the second phase automatically.

Appendix: Program refinement proofs Refinement 1: Let I(j, l, A) = ∀i.1 ≤ i ≤ 2 j . a ′ i = 1≤k≤i a k ∧ ∀i.2 j < i ≤ 2 l . a ′ i = i-2 j <k≤i a k .

Then 0 ≤ j < l ⇒ I(j, l, A); (|| 2 j <i≤2 l a ′ i = a i + a i-2 j ) = I(j + 1, l, A)

Proof:

Assume that 0 ≤ j < l Then I(j, l, A); (|| 2 j ≤i≤2 l a ′ i = a i + a i-2 j ) = (by the rule of sequential composition and expansion of I )

∃v 1 , . . . v 2 l . ∀i.1 ≤ i ≤ 2 j .   v i = 1≤k≤i a k   ∧ ∀i.2 j < i ≤ 2 l .   v i = i-2 j <k≤i a k   ∧ ∀i.1 ≤ i ≤ 2 j . a ′ i = v i ∧ ∀i.2 j < i ≤ 2 l . a ′ i = v i + v i-2 j = (by re-arrangement) ∀i.1 ≤ i ≤ 2 j+1 .   a ′ i = 1≤k≤i a k   ∧ ∀i.2 j+1 < i ≤ 2 l .   a ′ i = i-2 j+1 <k≤i
a k   = I(j + 1, l, A) P Refinement 2: Let P i ≡ put(a i+2 j , a i ) ¡ 1 ≤ i ≤ 2 l -2 j £ Π), 1 ≤ i ≤ 2 l Then: SS + (P 1 , . . . , P 2 l ) = (|| 2 j <i≤2 l a ′ i := a i + a i-2 j ) Proof: SS + (P 1 , . . . , P 2 l ) = (by expansion) SY N C + ({a i+2 j → a i |1 ≤ i ≤ 2 l -2 j }) = (by index rearrangement) SY N C + ({a i → a i-2 j |2 j < i ≤ 2 l }) = (definition SY N C) (|| 2 j <i≤2 l a ′ i := a i + a i-2 j ) P Refinement 3: α dom(i.m) = {a i+2j } ¡ 1 ≤ i ≤ 2 l -2 j £ {} ⇒ ∀J ∈ P S. j∈J dom(j.m) ⊆ j∈J αD j where P S = {{k, k + 2 j , . . . , k + 2 l -2 j }|1 ≤ k ≤ 2 j } and D i = {a i }, 1 ≤ i ≤ 2 l Proof: Consider an arbitrary J ∈ P S. J must have the form {k, k + 2 j , . . . , k + 2 l -2 j )}, for some k, 1 ≤ k ≤ 2 j . Then j∈J α dom(j.m) = {a k+2 j , a k+2 j+1 , . . . , a k+2 l -2 j } ⊆ j∈J αD j P.

Fig. 1 .

 1 Fig. 1. A multilevel BSP architecture

Fig. 2 .

 2 Fig. 2. Structure of superstep systems.

Acknowledgement

The author is grateful to M. Clint J. Gabarro, P. Kilpatrick and the referees for their comments on earlier drafts of this paper.


M.D Myriam Remmelink

M.D Laurence De Leval

Ph.D Christine Decaestecker

Anaelle Duray

M.D Nicolas Sirtaine

Emerence Crompot

Ph.D Sabine André

Vet M.D Herbert Kaltner

M.D Xavier Leroy

Ph.D Hans-Joachim Gabius

Myriam De Leval

M.D Sven ; Saussez
email: sven.saussez@umons.ac.be

Quantitative immunohistochemical fingerprinting of adhesion/growth-regulatory galectins in salivary gland tumours: Divergent profiles with diagnostic potential

Keywords: salivary gland, galectin, diagnosis, immunohistochemistry diagnosis, galectin, immunohistochemistry, salivary gland

First of all, as recommended by the associate editor and the reviewer 1 we have reduced the length of the manuscript of about 10%.

Answers to the reviewer 1:

-In the Table 2, we provide a footnote explaining more precisely the data: "For each type of tissue, the number of cases and the percentage of immunopositive cases relative to the intracellular localization are provided. " We have also clarified the Table 2.

-As recommended, we rewritten the discussion more concisely and add a more elaborate part on the differential diagnostic implications for pathologists: "The stratification based on intracellular distribution disclosed notable shifts and differences.

For pathologists, this point could be relevant in the histopathological MEC diagnosis because these tumours presented a unique profile based on cytoplasmic localization of

Gals-1, -3, -7, and -8 in the intermediate cells. Here, combination with Gal-7 presence has potential to increase the reliability of subtype diagnosis to separate solid-pattern from tubular/cribriform-patterns malignancies. Moreover, the absence of Gal-7 expression is also observed in ACC. This could help with distinction from MEC, especially the microcystic variant of ACC. When material is limited, the differential diagnosis between ADCCs and PAs is sometimes challenging. Our study shows that the expression profile of Gals-1, -3, and -7 is different when considering these histopathological specimens. In PA, the absence of nuclear Gal-1 signal and the cytoplasmic and nuclear presence of Gal-3 constitute a characteristic Gal-1, -3 signature, whereas the Gal-3 signal was confined to the cytoplasmic compartment of ADCCs." -As recommended, key messages for pathologists are also add in the abstract: -As recommended by the associate editor and the reviewer 1, we have reduced the length of the manuscript of about 10% (reduction of more than 300 words).

-In the abstract, we provide a clearly worded sentence on the aims/objectives of our study: "Aims: Histopathological fingerprinting of galectins, emerging multifunctional effectors in cell sociology, is suggested to refine differential diagnosis. This hypothesis is tested for salivary tumours."

-As recommended, we provide in the table 1 a list of the histopathological type of tumour.

-In Table 2, 0 is written 0 and not 0%. Respective studies may reveal new diagnostic tools and insights into clinical correlations.

Toward this end we focus on a family of endogenous lectins regulating cell adhesion and growth, i.e. the galectins sharing the β-sandwich fold [START_REF] Cooper | Galectinomics: finding themes in[END_REF][START_REF] Schwartz-Albiez | Inflammation and glycosciences[END_REF]. Systematic RT-PCR screening on tumour cell lines has revealed that galectin expression is subject to intricate control [START_REF] Gabius | Localization of endogenous lectins in normal human breast, benign breast lesions and mammary carcinomas[END_REF][START_REF] Lahm | Comprehensive galectin fingerprinting in a panel of 61 human tumor cell lines by RT-PCR and its implications for diagnostic and therapeutic procedures[END_REF]. Using non-crossreactive antibodies presence of distinct members of the three subgroups, i.e. proto-type, chimera-type and tandem-repeat-type proteins, in routine tissue sections can be detected [START_REF] Saussez | Galectin-7 (p53-induced gene-1): a new prognostic predictor of recurrence and survival in stage IV hypopharyngeal cancer[END_REF][START_REF] Cada | Immunohistochemical fingerprinting of the network of seven adhesion/growth-regulatory lectins in human skin and detection of distinct tumor-associated alterations[END_REF]. Thus, questions on relation of galectins to malignancy and on contributions to differential diagnosis can hereby be answered.

Previous work on salivary gland tumors has attracted our attention in this respect. Presence of galectins-1 and -3 (Gal-1 and Gal-3) was initially described, further work extending the data basis for Gal-3 with its potential to distinguish polymorphous low-grade adenocarcinoma from adenoid cystic carcinoma (AdCC) remaining controversial [START_REF] Xu | Differential expression of galectin-1 and galectin-3 in benign and malignant salivary gland neoplasms[END_REF][START_REF] Penner | C-kit expression distinguishes salivary gland adenoid cystic carcinoma from polymorphous low-grade adenocarcinoma[END_REF][START_REF] Teymoortash | Expression of galectin-3 in adenoid cystic carcinoma of the head and neck and its relationship with distant metastasis[END_REF][START_REF] Ferrazzo | Galectin-3 immunoprofile in adenoid cystic carcinoma and polymorphous low-grade adenocarcinoma of salivary glands[END_REF][START_REF] Ferrazzo | Differential expression of galectin-3, β-catenin, and cyclin D1 in adenoid cystic carcinoma and polymorphous low-grade adenocarcinoma of salivary glands[END_REF]. Since the tandem-repeat-type protein Gal-8, is of prognostic relevance in bladder and colon (Dukes C/D) cancer [START_REF] Nagy | Refined prognostic evaluation in colon cancer using immunohistochemical galectin fingerprinting[END_REF][START_REF] Langbein | Gene-expression signature of adhesion/growthregulatory tissue lectins (galectins) in transitional cell cancer and its prognostic relevance[END_REF], it was also monitored. Prototype Gal-7 completes our panel of four galectins due to its proven regulation by the tumour suppressor p53, its effectiveness as growth regulator, and its characteristic distribution different from Gal-1 in laryngeal/hypopharyngeal squamous cell carcinomas [START_REF] Saussez | Galectin-7 (p53-induced gene-1): a new prognostic predictor of recurrence and survival in stage IV hypopharyngeal cancer[END_REF][START_REF] Polyak | A model for p53-induced apoptosis[END_REF][START_REF] Bernerd | Galectin-7 overexpression is associated with the apoptotic process in UVB-induced sunburn keratinocytes[END_REF][START_REF] Kopitz | Homodimeric galectin-7 (p53-induced gene 1) is a negative growth regulator for human neuroblastoma cells[END_REF][START_REF] Saussez | Increased expression and altered intracellular distribution of adhesion/growth-regulatory lectins galectins-1 and -7 during tumour progression in hypopharyngeal and laryngeal squamous cell carcinomas[END_REF][START_REF] Cada | Galectin-7: will the lectin's activity establish clinical correlations in head and neck squamous cell and basal cell carcinomas?[END_REF]. Since Gal-1 expression is under the control of p16 INK4a in vitro [START_REF] André | Tumor suppressor p16 INK4a : modulator of glycomic profile and galectin-1 expression to increase susceptibility to carbohydrateinduction of anoikis in pancreatic carcinoma cells[END_REF], detection of this tumour suppressor protein together with p53 was performed in serial sections. In total, we studied material from 111 cases of salivary gland tumours (SGTs), assessing positivity first, then localization and finally quantitative parameter on percentage of stained area and signal intensity. The questions on i) distribution profiles of the four

Materials and Methods

Patients' Characteristics

A total of 111 tumour cases, comprised of 72 patients with benign SGTs and 39 patients with malignant SGTs who underwent surgery aimed at curative tumour resection, were studied (see Table 1 for clinical data). In 29 specimens of Warthin's tumour, intra-and interlobular ducts in adjacent tumour-free parotid tissue was evaluated. Tumour specimens were obtained by retrospective compilation from the records of the Departments of Pathology of the Hôpital Claude Huriez (XL, Lille, France), the Hôpital Erasme (MR, Brussels, Belgium), the CHU Saint-Pierre-Institut Bordet (NS, Brussels, Belgium) and the CHU Sart-Tilmant (LD, Liège, Belgium). The Institutional Review Boards of these hospitals approved the study. H&E sections of the 111 tumours were examined by two pathologists to confirm the diagnosis and then processed immunohistochemically under identical conditions to semiquantitatively and quantitatively monitor presence of Gals-1, -3, -7 and -8 and the two tested tumour suppressor proteins.

Antibodies

To raise polyclonal antibodies in rabbits, human Gals-1, -3, -7 and -8 were produced in bacteria, purified to homogeneity as ascertained by one-and two-dimensional gel electrophoresis and mass spectrometry and then used as antigens <<<PLEASE INSERT HERE REF 13,[START_REF] Kopitz | Homodimeric galectin-7 (p53-induced gene 1) is a negative growth regulator for human neuroblastoma cells[END_REF][START_REF] André | Tumor suppressor p16 INK4a : modulator of glycomic profile and galectin-1 expression to increase susceptibility to carbohydrateinduction of anoikis in pancreatic carcinoma cells[END_REF]. The immunoglobulin G fractions resulting from protein A-Sepharose affinity chromatography were rigorously checked for cross-reactivity among this lectin family systematically testing human Gals-1, -2, -3, -4, -7, -8 and -9 in Western blot and ELISA assays, and chromatographic affinity depletion was performed in any case of positivity followed by quality controls to verify complete elimination of cross-reactivity as described previously [START_REF] Lohr | Cell-type-specific expression of murine multifunctional galectin-3 and its association with follicular atresia/luteolysis in contrast to pro-apoptotic galectins-1 and -7[END_REF].

Immunohistochemistry

All tumour samples were fixed for 24 h in 10% buffered formaldehyde, dehydrated and routinely embedded in paraffin. Immunohistochemistry was routinely performed on 5 µm-thick sections mounted on silane-coated glass slides, as detailed recently [START_REF] Saussez | Galectin-7 (p53-induced gene-1): a new prognostic predictor of recurrence and survival in stage IV hypopharyngeal cancer[END_REF][START_REF] Saussez | Galectin-3 upregulation during tumor progression in head and neck cancer[END_REF]. Before starting the immunohistochemistry protocol, dewaxed tissue sections were briefly subjected to microwave pretreatment in a 0.01 M citrate buffer (pH 6.0) for 2 x 5 min at 900 W. The sections were then incubated with a solution of 0.4% hydrogen peroxide for five min to block endogenous peroxidase activity, rinsed in phosphate-buffered saline (PBS; 0.04 M Na 2 HPO 4 , 0.01 M KH 2 PO 4 and 0.12 M NaCl, pH 7.4) and successively exposed for 20 min to solutions containing avidin (0.1 mg/ml in PBS)

and biotin (0.1 mg/ml in PBS) to avoid false-positive staining reactions resulting from endogenous biotin. After a thorough washing with PBS to remove the reagents, the sections were incubated for 20 min with a solution of 0.5 % casein in PBS, again carefully washed and thereafter sequentially exposed at room temperature to solutions of i) the specific primary anti-galectin antibodies; ii) the corresponding biotinylated secondary antibody (polyclonal goat anti-rabbit IgG); and iii) the avidinbiotin-peroxidase complex (ABC kit). Incubation steps were separated by thorough washing steps to remove any unbound proteins. Antigen-dependent presence of the peroxidase complex in the sections was visualized by incubation with solution containing the chromogenic substrates diaminobenzidine and H 2 O 2 . After rinsing, the sections were counterstained with luxol fast blue and mounted with a synthetic medium. To exclude antigen-independent staining, the incubation step with primary/secondary antibodies was omitted from the protocol in controls. In all cases these controls were negative. The biotinylated secondary antibodies and the ABC kit came from DakoCytomation (Glostrup, Denmark), antibodies against the tumour suppressors p16 INK4a from Abcam (Cambridge, UK) and p53 from DakoCytomation.

Semi-quantitative analysis

For each specimen (15 microscopic fields), the intensity of the immunostaining (Mean Intensity, MI) was scored as 0 (negative), 1 (weak), 2 (moderate) or 3 (strong), and its presence (Labelling Index, LI)

was graded into categories of percentage of positive cells as 0 (0% positive cells), 1 (1-25%), 2 (>25% and < 75%) or 3 (>75% up to 100%). The quick score (QS) was calculated by multiplying the score of intensity of reactivity with the category of the percentage of immunopositive cells.

Quantitative analysis using computer-assisted microscopy

Following the immunohistochemical processing steps, the quantitative aspects of signal intensity and distribution were determined using a computer-assisted KS 400 imaging system (Carl Zeiss Vision, Hallbergmoos, Germany) connected to a Zeiss Axioplan microscope, as detailed previously [START_REF] Saussez | Increased expression and altered intracellular distribution of adhesion/growth-regulatory lectins galectins-1 and -7 during tumour progression in hypopharyngeal and laryngeal squamous cell carcinomas[END_REF]. For each microscopic field, we focused analysis on the tumoural region using computer-assisted morphometry after interactive identification. In each case, we scanned 15 fields covering a surface area ranging from 60,000 to 120,000 µm 2 . In each case, the quantitative analysis of immunohistochemical staining for a given marker yielded data on two variables: 1) the Labelling Index (LI), i.e. the percentage of positive cells, and 2) the Mean Optical Density (MOD), i.e. staining intensity of positive cells [START_REF] Saussez | Increased expression and altered intracellular distribution of adhesion/growth-regulatory lectins galectins-1 and -7 during tumour progression in hypopharyngeal and laryngeal squamous cell carcinomas[END_REF]. For each case of SGTs, the respective fields were defined by one of us (MR, XL, LD, NS) specialised in this diagnostic procedure.

Data analysis

Independent groups of quantitative data were compared using the non-parametric Kruskall-Wallis (more than two groups). In the case of more than two groups, post-hoc tests (Dunn procedure) were used to compare pairs of groups (to avoid multiple comparison effects). The statistical analyses were carried out using Statistica software (Statsoft, Tulsa, USA).

Results

Our study started with comparative analysis of the staining profiles of the four antibody preparations in 29 control cases, examining the adjacent tumour-free tissue in sections of Warthin's tumour. Whereas acini were generally negative, a clear difference was seen between Gal-1, here lymphoid cells serving as positive controls (Fig. 1A,B), and the other three types of galectins (Fig. 1A-F). The profiles of Gal-7 immunopositivity in intra-and interlobular ducts were remarkably comparable. Both types of duct (intra-and interlobular)

presented very strong cytoplasmic and nuclear immunostaining of the basal layer and moderate cytoplasmic expression in the luminal layer (Fig. 1E,F). Of particular note, nucleocytoplasmic presence was detected in inter-and intralobular ducts consistently for Gals-1, -3 and -7 (Fig. 1A-F). In contrast, Gal-8 was exclusively cytoplasmic (Fig. 1G,H;

Table 2).

Moving on to benign lesions, these cases were first classified. 44 out of the 72 cases (66%) of pleomorphic adenoma (PA) presented both epithelial and chondroid compartments.

These two components are shown separately in Fig. 2A-H, revealing moderate to strong nucleocytoplasmic positivity for Gal-1 in 73% or 75% of the cases, respectively (Fig. 2A,E;

Table 2). Gal-3 presence was detected in 68% of the cases with epithelial component, showing either cytoplasmic (59%) or also nucleocytoplasmic positivity (44%) (Fig. 2B; Table 2). Also, the chondroid component was positive for Gal-3 in 50% of the cases with similar intracellular distribution (Fig. 2F). While the epithelial part harboured Gal-7 in 60% of the cases with nucleocytoplasmic localization, only 33% presented a signal for the chondroid part (Fig. 2C, G; Table 2). In contrast, Gal-8 expression was abundant in 90% and 82% in these two components, with staining seen both in the cytoplasm and in nuclei (Fig. 2D,H; Table 2).

PA formation is apparently associated with a shift of Gal-3 from nuclear also to cytoplasmic sites and of Gal-8 from exclusively cytoplasmic also to nuclear sites, maintaining the 2). Regarding frequency, there appears to be a graded occurrence instead of uniform expression with a ranking from Gal-8, then to Gal-1, -3 and -7 in terms of positivity by cases.

Analysis of the adenoid cystic carcinomas (AdCC; total of 15 cases) was subdivided into cases with solid (eight patients), cribriform (five patients) and tubular patterns (two patients). Gal-1 was invariably present in tumour cells, detected both in nuclei and in cytoplasm (66%) or exclusively in nuclei (markedly for cribriform types, not at all for solidpattern-type tumours) and in stroma (Fig. 3A-C; Table 2). All eight cases with the solid pattern showed nucleocytoplasmic presence (Table 2). In contrast to Gal-1, peritumoral cells were consistently negative for Gal-3, while 13 from 15 cases yielded cytoplasmic signals of weak to moderate intensity (Fig. 3D-F; Table 2). No nuclear signals were seen. In terms of subtype selectivity no immunopositivity for Gal-7 was detected in tubular tumors, only one 2). As described already for Gals-1 and -3 in terms of occurrence, the tandem-repeat-type Gal-8 was present in most cases (14 from 15 cases), invariably localized in the cytoplasm, with added nuclear presence in three cases of the cribriform and solid types (Fig. 3J-L; Table 2).

In muco-epidermoid carcinomas (MEC; six cases) intermediate cells were always positive for Gal-1, mucus cell invariably negative (Fig. 4A). Overall, except for one case with Gal-8 positivity, staining was consistently cytoplasmic (Table 2). Intertumoral heterogeneity was observed for Gals-3 and -7, with positivity restricted to intermediate cells in three cases (Fig. 4B,C). Immunolabelling for Gal-8 was observed cytoplasmically in both cell types in five from six cases (Fig. 4D; Table 2).

Acinic cell carcinomas (ACC; nine cases) were generally positive for Gal-1 in the intercalated duct-type cells (Fig. 5A). This nucleocytoplasmic staining pattern contrasted with exclusively cytoplasmic positivity for Gal-3 in three of nine cases (Fig. 5B) and even complete lack of positivity for Gal-7 (Fig. 5C; Table 2). Gal-8, however, shared staining properties with Gal-1 in signal intensity and site of staining, four cases also presenting nuclear positivity (Fig. 5D; Table 2). This distribution is in conspicuous contrast to the profile of galectin presence in carcinoma ex pleomorphic adenomas (CA-ex-PA) with immunopositivity for Gals-1, -3 and -8 in all cases (Fig. 6A,B,D) and for Gal-7 in five of nine cases (Fig. 6C).

Staining was invariably nucleocytoplsamic for Gal-1 and -7, in eight of nine cases exclusively cytoplasmic for Gal-8 (Table 2). Combining signal presence and localization adds up to a distinct signature. Among the 39 cases with malignancy, p53 was detectable in four cases (two ACCs, two CA-ex-PAs), of which one CA-ex-PA was strongly immunopositive for Gal-7. Weak p16 INK4a -dependent signals were picked up in six cases (four AdCCs, two CA-ex-PA), always associated with Gal-1 presence.

Analyzing the quantitative data for each galectin with respect to the different tumour types (Fig. 7), an increase for Gal-1 pertains to the percentage of positive cells (LI parameter;

Kruskall-Wallis: p=0.001). A highly significant difference (post-hoc comparison; p = 0.0006) concerned the labelling index between the chondroid component in PAs and the CA-ex-PAs (Fig. 7B). These two correlations also showed up in the case of Gal-3, albeit with reduced level of statistical significance at p=0.01 and p=0.004, respectively (Fig. 7D). In contrast, presence of Gals-7 and -8 was subject to downregulation. Prominent differences in this respect led to a separation in two groups constituted by PA and the corresponding carcinoma vs the other three studied types of malignancy for Gal-7 in both categories of quantitative data (MOD, LI; Kruskall-Wallis: p < 10 -6 ) (Fig. 8A,B). Post-hoc comparisons between the CA-ex- Thus, while percentage of labelled cells for Gals-1 and -3 increased in CA-ex-PA, a decrease was noted for Gal-7 (excluding the CA-ex-PAs) and for Gal-8 (excluding MECs).

Discussion

Galectins are capable to turn presence of distinct glycans into cellular responses, e.g. in growth control of tumour cells [START_REF] Kopitz | Homodimeric galectin-7 (p53-induced gene 1) is a negative growth regulator for human neuroblastoma cells[END_REF][START_REF] André | Tumor suppressor p16 INK4a : modulator of glycomic profile and galectin-1 expression to increase susceptibility to carbohydrateinduction of anoikis in pancreatic carcinoma cells[END_REF][START_REF] Kopitz | Negative regulation of neuroblastoma cell growth by carbohydrate-dependent surface binding of galectin-1 and functional divergence from galectin-3[END_REF][START_REF] Fischer | Galectin-1 interacts with the α 5 β 1 fibronectin to restrict carcinoma cell growth via induction of p21 and p27[END_REF][START_REF] Patsos | Compensation of loss of protein function in microsatellite-unstable colon cancer cells (HCT116): a gene-dependent effect on the cell surface glycan profile[END_REF][START_REF] Gabius | The Sugar Code. Fundamentals of glycosciences[END_REF]. In addition, they are also known to be present within the cell, and act in concert with distinct target proteins such as oncogenic Hras or effectors in the apoptotic or splicing cascades [START_REF] Schwartz-Albiez | Inflammation and glycosciences[END_REF][START_REF] Rotblat | Galectin-1(L11A) predicted from a computed galectin-1 farnesyl-binding pocket selectively inhibits Ras-GTP[END_REF][START_REF] Wang | Nucleocytoplasmic lectins[END_REF][START_REF] Smetana | Nuclear presence of adhesion/growthregulatory galectins in normal/malignant cells of squamous epithelial origin[END_REF]. As case studies for salivary gland tumours have documented [START_REF] Xu | Differential expression of galectin-1 and galectin-3 in benign and malignant salivary gland neoplasms[END_REF][START_REF] Penner | C-kit expression distinguishes salivary gland adenoid cystic carcinoma from polymorphous low-grade adenocarcinoma[END_REF][START_REF] Teymoortash | Expression of galectin-3 in adenoid cystic carcinoma of the head and neck and its relationship with distant metastasis[END_REF][START_REF] Ferrazzo | Galectin-3 immunoprofile in adenoid cystic carcinoma and polymorphous low-grade adenocarcinoma of salivary glands[END_REF][START_REF] Ferrazzo | Differential expression of galectin-3, β-catenin, and cyclin D1 in adenoid cystic carcinoma and polymorphous low-grade adenocarcinoma of salivary glands[END_REF], the investigation of this lectin group has so far mainly been focused on Gals-1 and -3. Analysis of further family members, at best by fingerprinting studies, is at a rather early stage. Emerging data from head and neck tumours underscore its pertinence, i.e. by revealing association of presence of Gals-1 and -7 with progression to malignancy and inverse shifts between nuclear and cytoplasmic localization in laryngeal/hypopharyngeal squamous cell carcinomas as well as the upregulation of Gal-8 in these tumours in contrast to an often encountered downregulation in other tumour types, hereby strongly indicating intriguing divergence between different galectins [START_REF] Saussez | Increased expression and altered intracellular distribution of adhesion/growth-regulatory lectins galectins-1 and -7 during tumour progression in hypopharyngeal and laryngeal squamous cell carcinomas[END_REF][START_REF] Danguy | Immunohistochemical profile of galectin-8 expression in benign and malignant tumors of epithelial, mesenchymatous and adipous origins, and of the nervous system[END_REF][START_REF] Cludts | Galectin-8 upregulation during hypopharyngeal and laryngeal tumor progression and comparison with galectins-1, -3, and -7[END_REF]. In order to pursue these indications, a promising methodological approach exemplified in this study is a.) monitoring presence of galectins from the three subgroups in parallel This study examines proto-type (Gal-1/-7), chimera-type (Gal-3) and tandem-repeat-type (Gal-8) galectins comparatively. It teaches several key lessons, starting with detection of a definitely non-uniform regulation of the individual, closely related proteins. The patterns of presence in PA with grading from Gal-8 to Gal-1, Gal-3 and finally Gal-7 illustrates this point. Of note, specimens of Warthin's tumour were consistently negative for Gal-1, while maintaining features for Gals-3, -7, and -8 [START_REF] Saussez | Galectin fingerprinting in Warthin's tumors: lectin-based approach to trace its origin?[END_REF]. As internal standard for validity of inter-study comparison our data are in accord with high degree of positivity of Gal-3 in AdCCs [START_REF] Xu | Differential expression of galectin-1 and galectin-3 in benign and malignant salivary gland neoplasms[END_REF][START_REF] Penner | C-kit expression distinguishes salivary gland adenoid cystic carcinoma from polymorphous low-grade adenocarcinoma[END_REF][START_REF] Teymoortash | Expression of galectin-3 in adenoid cystic carcinoma of the head and neck and its relationship with distant metastasis[END_REF][START_REF] Ferrazzo | Galectin-3 immunoprofile in adenoid cystic carcinoma and polymorphous low-grade adenocarcinoma of salivary glands[END_REF][START_REF] Ferrazzo | Differential expression of galectin-3, β-catenin, and cyclin D1 in adenoid cystic carcinoma and polymorphous low-grade adenocarcinoma of salivary glands[END_REF].

stratification based on intracellular distribution disclosed notable shifts and differences. A-H x 320.

"

  Acinic cell and adenoid cystic carcinomas (specifically tubular and cribriform types) shared the expression signature of galectin-1, -3 and -8 presence combined with galectin-7 absence. Mucoepidermoid carcinomas presented a unique profile based on cytoplasmic galectin 1-3-7-8 localization in the intermediate cells." -As recommended, we add in the discussion a comment about the utility of galectin immunohistochemistry in routine laboratory: "-page 13, line 2: "In summary, our study supports the concept for characteristic signatures of galectin presence when monitoring several proteins of this class, constituting progress in mapping presence of these lectins and indicating potential for differential diagnosis, especially for MEC/ACC." Answers to associate editor:

  IntroductionProteins serving as multifunctional effectors are promising candidates as markers in histopathology. When gene diversification has led to a family of homologous proteins it is an attractive project line to define individual expression profiles comparatively in tumour material.

  cribriform tumour was positive, solid ones revealing strong nucleocytoplasmic signals in four of eight cases (Fig 3G-I; Table

  PAs and AdCCs yielded p-values at 0.03 for the MOD parameter and at 0.01 for the LI variable. As shown in Fig.8A, B, the epithelial component in PA showed strikingly stronger signal presence than cases with malignancy (also p-value for comparison to MECs at 0.01 for MOD variable). The chondroid component, too, differed from adenoid cystic and acinic cell carcinomas. Concerning Gal-8, malignancies -except for the MECs -were associated with a decrease in signal (Fig.8C, D). As documented in Fig.8C, the groups of CA-ex-PAs and pleomorphic adenoma (epithelial component) were separated at p = 0.03 in post-hoc comparison. The difference between epithelial component of adenoma and AdCC reached significance for both quantitative parameters (p = 0.049 for the labelling index, here also for ACCs (Fig.8C, D)). The p-value between the chondroid component and ACCs was at 0.02.

  .) determining their localization profiles and c.) assessing staining parameters quantitatively.

Figure 1 :

 1 Figure 1: Immunohistochemical staining profiles for galectins-1, -3, -7 and -8 in intralobular (A, C, E,

Figure 2 :

 2 Figure 2: Immunohistochemical staining profiles for galectins-1, -3, -7, and -8 in epithelial (A-D) and

Figure 3 :

 3 Figure 3: Immunohistochemical staining profiles for galectins-1, -3, -7, and -8 in solid (A, D, G, J),

Figure 4 :

 4 Figure 4: Immunohistochemical staining profiles for galectins-1, -3, -7, and -8 in MEC (A-D).

Figure 5 :

 5 Figure 5: Immunohistochemical staining profiles for galectins-1, -3, -7, and -8 in ACC (A-D).

Figure 6 :

 6 Figure 6: Immunohistochemical staining profiles for galectins-1, -3, -7, and -8 in CA-ex-PA (A-D).

Figure 7 :

 7 Figure 7: Quantitative determination (by computer-assisted microscopy) of the percentages of cells

Figure 8 :

 8 Figure 8: Quantitative determination (by computer-assisted microscopy) of the percentages of cells

  presence of signal in cytoplasm (C) and/or nuclei (N). For each type of tissue, the number of cases and the percentage of immunopositive cases relative to the intracellular localization are provided.

  figure 1 190x254mm (96 x 96 DPI)

Table 1 :

 1 Clinical data

	Benign Salivary Gland Tumors
	-Sex : 38 females/34males
	-Age: 46.3 years (range between 14 and 77 years)
	-Localization: 72 parotid tumors
	-Treatment: 72 superficial parotidectomies.
	-Histology: 72 cases of pleomorphic adenoma
	Malignant Salivary Gland Tumors
	-Sex: 22 females/ 17 males
	-Age: 52.4 years (range between 19 and 88 years)
	-Localization: 3 sub-mandibular specimens
	7 oral cavity specimens
	29 parotid specimens
	-Treatment: 23 superficial parotidectomies
	6 total parotidectomies
	7 neck dissections
	10 local (oral cavity or submandibular) resections.
	-Histology: 15 cases of adenoid cystic carcinoma
	9 cases of mucoepidermoid carcinoma
	9 cases of carcinoma ex-pleomorphic adenoma
	6 cases of acinic cell carcinoma.

Table 2 :

 2 Intracellular localization of galectins-1, -3, -7 and -8 a

	Type of tissue	Galectin-1			Galectin-3		Galectin-7			Galectin-8
		Localization			Localization		Localization			Localization
	C	N	C+N	C	N C+N	C	N	C+N	C	N C+N
	Intralobular
	ducts
	Interlobular
	ducts

Published on behalf of the British Division of the International Academy of Pathology Histopathology

transcription [START_REF] André | Tumor suppressor p16 INK4a : modulator of glycomic profile and galectin-1 expression to increase susceptibility to carbohydrateinduction of anoikis in pancreatic carcinoma cells[END_REF]. In summary, our study supports the concept for characteristic signatures of galectin presence when monitoring several proteins of this class, constituting in mapping presence of these lectins and indicating potential for differential diagnosis, especially for MEC/ACC.


Dr Gerlinde Mausser
email: gerlinde.mausser@medunigraz.at

Keywords: techniques < Airway, difficult < Airway, infant

Airway management and ventilation in infants with laryngotracheal stenosis is a big challenge because of the smallness of the airways. In addition to the anatomical and pathological particularities, the anaesthesiologist must be familiar with the specific features of the respiratory physiology and ventilation of infants. In our clinical routine we prefer total intravenous anaesthesia (TIVA), propofol supplemented with remifentanil, in all cases with a partial or complete open anaesthesia system to guarantee a stable level of anaesthesia during the whole procedure and to avoid gas contamination for the operating team. ECG, heart rate, blood pressure and oxygen saturation is our standard monitoring. In addition the anaesthetist should carefully monitor the children clinically by auscultation the lungs and watching the chest movements. With high frequency jet ventilation (HFJV) oxygenation and ventilation during endoscopic surgery of the upper respiratory tract can be achieved. HFJV is in many cases the precondition for endoscopic treatment without tracheotomy, especially in LASER surgery.

HFJV may be applied from a supraglottic position above the airway stenosis 1, 2 ; subglottic (infraglottic), using a catheter passed through the stenosis [START_REF] Koomen | Jet ventilation for laryngotracheal surgery in an ex-premature infant[END_REF] or transtracheal via a Ravussin cannula [START_REF] Depierraz | Percutaneous transtracheal jet ventilation for pediatric endoscopic laser treatment of laryngeal and subglottic lesions[END_REF] . Due to the anatomical narrowness of the airways in infants and neonates even a cannula with 2 -3 mm in diameter can impair the small surgical field during subglottic jet ventilation via transglottal (translaryngeal) cannulas. This fact can make endoscopic surgery impossible. Transtracheal jet ventilation via a Ravussin cannula is an invasive technique. In neonates and small infants the transcutaneous puncture of the cricothyroid membrane may be difficult and displacement of the cannula with cervical emphysema, pneumomediastinum and pneumothorax may occur. Supraglottic, prestenotic HFJV via modified Kleinsasser laryngoscope (Fig. 1) with integrated jet nozzels is a minimal-invasive ventilation technique and convenient for ventilation and oxygenation during endolaryngotracheal surgery in infants and neonates [START_REF] Grasl | Tubeless laryngotracheal surgery in infants and children via jet ventilation[END_REF][START_REF] Ihra | Tubeless combined high-frequency jet ventilation for laryngotracheal laser surgery in paediatric anaesthesia[END_REF][START_REF] Mausser | Airway management and anesthesia in neonates, infants and children during endolaryngotracheal surgery[END_REF] . In previous studies with adult trachea lung models, distal airway pressures, minute volumes and air entrainment were higher during ventilation above the stenosis compared to poststenotic HFJV [START_REF] Ng | Comparing Methods of Administering High-Frequency Jet Ventilation in a Model of Laryngotracheal Stenosis[END_REF][START_REF] Buczkowski | Air entrainment during high-frequency jet ventilation in a model of upper tracheal stenosis[END_REF] . Thus supraglottic HFJV is associated with the development of inadvertent PEEPlevels and barotrauma.

The aim of this study was to assess the total lung volumes and tidal volume variations at peak inspiratory pressure (PIP) and at positive end-expiratory pressure level (PEEP), as well as the intrapulmonary pressures (PIP and PEEP) during two conventional methods of supraglottic HFJV in an infant trachea-lung model.

Material and Methods:

An Ventilator settings in all experiments were like the settings used in the daily routine for HFJV in our department. The two sets of experiments were performed using the same lung-trachea model. We applied the various conditions (driving pressure, I:E ratio) for monofrequent high frequency jet ventilation and in the following for superimposed high frequency jet ventilation.

The ventilator setting for superimposed high frequency jet ventilation (SHFJV) was: frequency 20 breaths/min combined with 600 min -1 , I:E 1:2 and followed by 1:1. The ventilation was performed with a driving pressure 0.3 bar in the low frequency part and 0.2 bar in the high frequency part of jet ventilation, followed by driving pressures in the low/high conditions of 0.6 + 0.4, 0.8 + 0.6 and 1.0 + 0.8 bar.

Ventilator settings for the monofrequent, high frequency jet ventilation were: frequency 200 min -1 , I:E 1:2 followed by 1:1. The driving pressure for ventilation was 0.

Effect of supraglottic, superimposed HFJV with various driving pressures and stenosis

Superimposed HFJV is generated by overlaying a low-frequency jet stream with a highfrequency jet stream. With augmentation of the driving pressure in the experiment without stenosis (Rp 20), the total lung volume as well as the pulmonary pressures increased (Fig. 5). In the experiment with 1.0 + 0,8 bar driving pressure PIP increased up to a maximum of 20 ± 0 mbar and PEEP up to a maximum of 10.5 ± 0 mbar. With decreasing diameter of the stenosis (Rp 200 = 1.85 mm ID and Rp 500 = 1.3 mm ID) total lung volume at PIP level decreased and the total lung volume at PEEP level increased (Fig. 5). During ventilation with I:E ratio of 1:2 the PIP and PEEP values were lower in comparison to I:E ratio 1:1 (Fig. 6).

Effect of I:E ratio in supraglottic HFJV with various driving pressures and stenosis

For both, monofrequent HFJV (Fig. 4) and superimposed HFJV (Fig. 6), it was registered that without stenosis there was no significant difference in pulmonary pressures and tidal variation between I:E of 1:2 and 1:1. In presence of airway stenosis pulmonary pressures, especially PEEP, increased at I:E 1:1, while tidal variations hardly changed. This effect was more distinct in monofrequent HFJV. Experiment II and Experiment III, than during monofrequent supraglottic HFJV. That two settings are identical with the ventilations settings generally used in our clinical routine (Fig. 7).

Fig. 7

Discussion:

In this infant trachea lung model we tried to simulate the specific features of the respiratory physiology and ventilation of infants in the presence of airway stenosis to analyse our clinical experiences in supraglottic HFJV in neonates, infants and children. We use this technique in clinical practice since 13 years without severe complications. In all cases we have to share the airway with surgeon.

The characteristics of the respiratory system of infants in contrast to adults are the unstable functional residual capacity (FRC), a lower compliance (C) and a higher resistance (R).

Therefore a positive end-expiratory pressure (PEEP) in artificial ventilation of newborns and infants [START_REF] Hatch | Anaesthesia and the ventilatory system in infants and young children[END_REF][START_REF] Berger | Ventilation of newborns and infants[END_REF] is preferable and its occurrence in an acceptable level during supraglottic HFJV might be advantageous. Varied techniques of airway management and anaesthesia during endolaryngotracheal surgery in children are in clinical practice. Each of these techniques offers advantages and disadvantages [START_REF] Jaquet | Complications of different ventilation strategies in endoscopic laryngeal surgery[END_REF] . Conventional positive pressure ventilation via tracheal tube may not be practicable due to the stenosis itself or to the surgical request for an unhindered operating field. Spontaneous ventilation or apnoeic anaesthesia with intermittent ventilation and oxygenation is often used in pediatric ENT surgery [START_REF] Weisberger | Apneic anesthesia for improved endoscopic removal of laryngeal papillomata[END_REF][START_REF] Orr | Anesthesia for microlaryngoscopy[END_REF] . Children may develop a loss of about 45 % of their functional residual air capacity (FRC) during general anaesthesia and owing to inadequate ventilation, hypoxia may occur in a matter of seconds [START_REF] Hatch | Anaesthesia and the ventilatory system in infants and young children[END_REF][START_REF] Berger | Ventilation of newborns and infants[END_REF] . Thus the anaesthesiologist is obliged to switch to alternative ventilation and oxygenation techniques. operating field. According to our experimental results, supraglottic HFJV seems to be able to ensure adequate ventilation and provide acceptable PEEP-levels [START_REF] Hatch | Anaesthesia and the ventilatory system in infants and young children[END_REF][START_REF] Berger | Ventilation of newborns and infants[END_REF] . The efficacy and safety for ventilation and oxygenation during this specific kind of surgery is not clearly established and guidelines for the use of such techniques would be welcome [START_REF] Cook | Major complication during anaesthesia for elective laryngeal surgery in the UK: a national survey of the use of high-pressure source ventilation[END_REF] . In adult lung model suprastenotic HFJV is associated with higher airway pressures and with higher risk for barotrauma as compared to infrastenotic HFJV in the presence of airway stenosis [START_REF] Ng | Comparing Methods of Administering High-Frequency Jet Ventilation in a Model of Laryngotracheal Stenosis[END_REF][START_REF] Buczkowski | Air entrainment during high-frequency jet ventilation in a model of upper tracheal stenosis[END_REF] .

Because of the anatomical and physiological features of the respiratory system of infants, these findings concerning adult lung-trachea models can not be transferred to children. With respect to the higher resistance and lower compliance, it might be assumed that this effect is even greater in infant`s lungs. Numerous large, published series have reported their experiences with supraglottic HFJV without severe complications such as barotrauma [START_REF] Grasl | Tubeless laryngotracheal surgery in infants and children via jet ventilation[END_REF][START_REF] Ihra | Tubeless combined high-frequency jet ventilation for laryngotracheal laser surgery in paediatric anaesthesia[END_REF][START_REF] Mausser | Airway management and anesthesia in neonates, infants and children during endolaryngotracheal surgery[END_REF][START_REF] Rezaie-Majd | Superimposed high-frequency jet ventilation (SHFJV) for endoscopic laryngotracheal surgery in more than 1500 patients[END_REF][START_REF] Friedrich | Jet ventilation in laryngotracheal surgery[END_REF][START_REF] Mausser | Air entrainment during high-frequency jet ventilation[END_REF] .

Several authors of previous studies have investigated the airway pressures. In our experiment we measured the pulmonary total volume in an infant test lung at PIP-level and at PEEP-level, which probably is an indicator for impending barotrauma. We recorded the pulmonary pressures at PIP-level and at PEEP-level during ventilation of the infant test lung with two conventional methods of HFJV.

A previous report by Ihra et al [START_REF] Ihra | Airway Stenosis-Related Increase of Pulmonary Pressure During High-Frequency Jet Ventilation Depends on Injector´s Position[END_REF] demonstrated in an adult trachea-lung model, that the distance between the jet nozzle and the airway stenosis influences airway pressure, so that airway pressures decrease with increasing distance to the stenosis.

The moderate pulmonary pressures we measured in both forms of HFJV may be due to the use of the modified Kleinsasser laryngoscope, in which the distance between the plane of exit of the jet stream and the tip of the laryngoscope is constant and depending upon the size of laryngoscope in children, ranging from 7.7 cm, respectively 9.7 cm. This fact may prevent high pulmonary pressures related to the tightness of the stenosis and different driving pressures. As expected volume shifts during superimposed HFJV were higher than during monofrequent HFJV. This correlates with our clinical observations of an adequate CO 2 -elimination during superimposed HFJV [START_REF] Mausser | Airway management and anesthesia in neonates, infants and children during endolaryngotracheal surgery[END_REF] .

We assume that another factor for the reasonable pulmonary pressures may be the application of comparatively low driving pressures, as we use in the daily routine. With the ventilator settings used in our study and in both conventional methods of HFJV, no clinically inadequate pressure levels occurred in any experiment (fig. 4, fig. 6).

Furthermore our results suggest that an I:E ratio of 1:2 can be recommended for HFJV applied to a constricted airway. I:E of 1:1 is associated with higher pulmonary pressures and does not lead to augmented ventilation. The abbreviated exspiration time at 1:1 ratio may induce aggravated air trapping.

Our findings also show that augmentation of the driving pressure is inappropriate to increase ventilation in presence of airway stenosis. Increasing driving pressures only lead to higher pulmonary pressures while tidal volumes do not change significantly. This suggests that the risk for barotrauma may escalate, although ventilation cannot be improved. Hence the application of moderate driving pressures seems to be safe concerning pulmonary pressures and provides adequate ventilation.

One shortcoming of supraglottic HFJV in the clinical routine is the fact that airway pressures Further clinical and experimental studies are needed to take a closer look at the airway management and ventilation during these specific surgical procedures in infants.

On the basis of the data from this study, we conclude that supraglottic HFJV in infants with modified jet laryngoscopes is a minimally invasive and safe ventilation technique, it offers an unimpaired operating field for the surgeon especially in LASER surgery and this method ensures sufficient ventilation with adequate PEEP via optimally adjusted jet mechanismn.

Fig. 1 :

 1 Fig. 1: Modified Kleinsasser laryngoscope for supraglottic, superimposed HFJV (C. Reiner,

Fig. 2 :Fig. 3 :

 23 Fig. 2: Infant trachea -lung model. Ventilation was performed as supraglottic (suprastenotic)

Fig. 4 :Fig. 5 :Fig. 6 :Fig. 7 :

 4567 Fig. 4: Pulmonary pressures (mbar) during supraglottic monofrequent HFJV (frequency 200 min -1 , I:E 1:1 vs 1:2) in various driving pressures and diameters of stenosis: peak

1 Experimental 1 1 2 Background:

 112 Model of Laryngotracheal Stenosis in Infants: Effects of Different High-frequency Jet Ventilation Patterns on Pulmonary Parameters Mausser G. 1 , Schellauf A. 1 , Scherübl M. 1 , Arrer A. 2 , Schwarz G. Division of Anesthesiology for Neurosurgical and Craniofacial Surgery and Intensive Care Medicine, Medical University Graz, Austria 2 Cand. med., Medical University Graz, Austria Supraglottic high frequency jet ventilation (HFJV) in laryngotracheal surgery in infants with modified jet laryngoscopes offers the surgeon an unimpaired operating field. However, supraglottic HFJV is associated with the development of high airway pressures, inadvertent PEEPlevels and barotrauma. Methods: We investigated the total lung volumes and tidal volume variations at peak inspiratory pressure levels (PIP) and at positive end-expiratory pressure levels (PEEP) along with the pulmonary pressures (PIP and PEEP) during two conventional methods of supraglottic high frequency jet ventilation (HFJV) in an infant trachea-lung model without stenosis and with different degrees of stenosis.Results: With augmentation of the driving pressure in the experiment without stenosis, the total lung volume (TLV) plus the pulmonary pressures increased. With narrowing of the stenosis TLV reduced at PIP level and increased at PEEP level. Volume shifts were significantly higher during superimposed HFJV compared to monofrequent HFJV at equivalent stenosis diameter (P < 0.05) except for the setting with 0.3 bar driving pressure (P > 0.05). The pulmonary PIP was in none of the test series higher than 20 mbar and the pulmonary PEEP did not exceed 14 mbar.Conclusions:The results from our experimental model support the safe and effective clinical use of supraglottic HFJV in infants with tracheal stenosis. Moderate driving pressures provide acceptable pulmonary pressures in normal complient lungs. Keywords: barotrauma, high frequency jet ventilation, infants, laryngotracheal stenosis

  Fig.1

  Fig.2

Fig. 3 ;

 3 Fig. 3; Fig. 4

Fig. 5 ;

 5 Fig. 5; Fig. 6

  superimposed supraglottic HFJV are significantly higher (P < 0.05) in

8 Supraglottic

 8 HFJV ensures oxygenation and ventilation and offers the surgeon an unimpaired

  into the laryngoscope hold the risk of dislocation and anomalies in airway pressures with possibly consecutive high pulmonary pressures.

  and endtidal CO 2 cannot be measured continuously, because of the open ventilation system. Another problem inherent in an in vitro study is the direct translation to clinical practice. The setting of our test lung corresponds to the physiological condition of children about up to 10 kg of body weight. Larger children may present different respiratory parameters such as compliance or resistance and therefore differing pressure and volume data may occur.

  resistor) applied to the model shows the form of a blind, which can be seen in the clinical practice in subglottic stenosis after long term intubation. Airway stenosis of a length of more than a few millimetres or even centimetres could not be analysed and may change our results. Furthermore the model stenosis used, is composed of inflexible material in contrast to in-vivo airway stenosis which can consist of soft tissue. The effect of these phenomena, concerning intrapulmonary volume and pressure remains unconsidered in this study. Based on our clinical experiences, we can not say, that this technique is safe in distal tracheal stenosis also tidal volumes and driving pressures may be inadequate in poorly complient lungs which was not reviewed in our studies.

Pediatric Anesthesia

Acknowledgements

We are grateful to Mr. D. Lirsch (C. Reiner, Vienna) for his support with the laboratory work.


Josias Elisee
email: j.elisee@cs.ucl.ac.uk

Marc Bonnet

Simon Arridge

Accelerated Boundary Element Method for Diffuse Optical Imaging

whether they are published or not. The documents may come   L'archive ouverte pluridisciplinaire

Compiled September 17, 2011 The boundary element method (BEM) is a useful tool in Diffuse Optical Imaging (DOI) when modelling large optical regions whose parameters are piecewise constant, but is computationally expensive. We present here an acceleration technique, the single-level Fast Multipole Method, for a highly lossy medium. The enhanced practicability of the BEM in DOI is demonstrated through test examples on single-layer problems, where order of magnitude reduction factors on solution time are achieved, and on a realistic three-layer model of the neonatal head. Our experimental results agree very closely with theoretical predictions of computational complexity. © 2011 Optical Society of America OCIS codes: 000.3860, 000.4430, 110.0113

Numerical methods for calculating forward models of light propagation in tissue are extensively used in Diffuse Optical Imaging (DOI). These include the Finite Element Method (FEM) [1] and Finite Volume Method (FVM) [2], which describe the domain in terms of a volume mesh with locally varying absorption coefficient µ a , reduced scattering coefficent µ ′ s and refractive index n. Methods based on discretisation only of the boundaries may be prefereable if the domain of interest can be described in terms of closed regions with constant parameters, including the Kirchhoff Approximation [3] and the Boundary Element Method (BEM) [4,5].

BEM applied to DOI is based on boundary integral equations linking density φ and current q of the form

∂Ω ∂ ν G(r, r ′ )φ(r ′ ) dS(r ′ )- 1 D ∂Ω G(r ′ -r)q(r ′ ) dS(r ′ ) + α(r)φ(r) = Ω Q(r ′ )G(r ′ -r) dV (r ′ ) (1)
where the region Ω ⊂ R 3 has uniform optical properties, α is a known geometric factor, Q(r ′ ) is a known source and G(R), the full-space fundamental solution to the governing equation of DOI, satisfies (D∆ + κ 2 )G + δ = 0 and is given, in 3D, by

G(R) = exp(-ικR)/(4πR) (with R = R ), (2)
while

∂ ν G(r, r ′ ) := ν(r ′ ) • ∇G(r ′ -r) is the normal derivative of G.
The wavenumber κ = κ R + ικ I and the constant D are defined in terms of µ a and µ s , the absorption and scattering coefficients of the medium, by

κ 2 + D -1 [µ a + ιω/c] = 0, D = [3(µ a + µ ′ s )] -1
with the square root chosen such that κ I < 0. For multilayer models (1) is written for each layer, a boundary condition of the form φ + ℓq = J -(with J -denoting an incoming flux) is prescribed on the external surface, and the values of φ, q on interfaces relative to each adjacent layer are linked by transmission conditions. The BEM [4,5] then consists in discretizing all relevant surfaces into boundary elements and approximating φ, q on each element using simple shape functions, resulting in a system of linear equations of the form

Aφ -Bq -Q = 0 (3)
After accounting for all boundary and transmission conditions in (3), a matrix equation on the N remaining, complex-valued, boundary unknowns is obtained. One of the difficulties in using BEM for problems with large numbers of unknowns, such as medical imaging, is that the matrices involved are fully-populated, leading to excessive computational requirements in memory, and, by implication, solve time. However, recent acceleration strategies such as the Fast Multipole Method (FMM) [6][START_REF] Coifman | IEEE Antennas Propagat[END_REF][8][9] avoid storing dense matrices, and instead make use of matrix-vector products within iterative solvers for the system (3). Although the FMM has been applied to a variety of problems, its application to the complex-valued model used in DOI requires some special considerations, which are described in this paper.

The FMM stems from fast summation methods initially proposed in [9] and implemented in 3D in [10], based on multipole expansions of the relevant Green's function G(rr ′ ) which achieves a separation of the variables r and r ′ . For this purpose, the relative position vector

R = r ′ -r is decomposed into R = r′ + R 0 -r, with R 0 = r ′ 0 -r 0 , r = r-r 0 and r′ = r ′ -r ′ 0 in terms of two poles r 0 , r ′ 0 .
With these notations, G(r ′r) admits the decomposition [START_REF] Coifman | IEEE Antennas Propagat[END_REF]11]

G(r ′ -r) ≈ 1 4π P p=1 w p exp(-ικs p •r ′ )T p exp(ικs p •r) (4)
in the so-called diagonal form, established as a consequence of the Gegenbauer addition theorem [8,12], where the transfer function T p = T (R 0 , s p ) is given by and P ℓ are spherical Hankel functions of second kind and Legendre polynomials, respectively [12]. Decomposition ( 4) is approximate in that i) an integration over the unit sphere S 2 is replaced with a P -point numerical quadrature (with points s p ∈ S 2 and weights w p ), and ii) the infinite series defining the exact transfer function T (R 0 , s p ) is truncated at level L in (5); however, (4) holds within known error bounds on L and P if [11]

T p = 1 4π L ℓ=0 κ(-ι) ℓ+1 (2ℓ + 1)h (2) ℓ (κR 0 )P ℓ ( R0 • s p ) (5)
R -R 0 / R 0 ≤ 2/ √ 5 (6)
Decomposition of ∂ ν G is obtained in a similar way by multiplying each summand of (4) by -ικs p •ν(r ′ ).

The separation of the variables r ′ and r achieved by (4) allows to re-use integrations w.r.t. r ′ in (1) when changing the collocation point r; this is the main acceleration mechanism behind the FMM. Decomposition (4) can be applied recursively, but in this first report, only the single-level FMM is considered. The latter exploits a division of the spatial region containing ∂Ω into M cubic cells C m (m = 1 . . . M ) of equal size (Fig. 1). Integrals in (1) may be evaluated using (4) instead of (2) whenever r ′ and r belong to two non-adjacent cells C m and C m ′ . The theoretical computational complexity per GMRES iteration of the single-level FMM for Helmholtztype equations is O(N 3/2 ) [7], instead of O(N 2 ) for the standard BEM.

We summarise our algorithm (following [START_REF] Coifman | IEEE Antennas Propagat[END_REF]8,11]) as 1. Choose spatial grid edge length size a, and assign elements {τ j } to cells according to their midpoint 2. Build sparse matrices A 0 , B 0 using (2) only for elements and collocation points lying in the same or adjacent cells.

3. For each element τ n ′ assigned to cell C m ′ , compute excitation vectors V A m ′ , V B m ′ with entries:

V A m ′ n ′ (s p ) = -ικ τ n ′ exp(-ικs p •r ′ ) s p •ν(r ′ ) dS(r ′ ) V B m ′ n ′ (s p ) = 1 D τ n ′ exp(-ικs p •r ′ ) dS(r ′ ) (7)
4. For each collocation point r n assigned to cell C m , compute excitation vectors C m , with entries:

C mn (s p ) = exp(ικs p •r n ) . ( 8
)
5. For each quadrature point s p , for each pair of cells C m and C ′ m , compute the transfer matrices T(s p ), with entries T mm ′ (s p ) given by ( 5).

S m ′ (s p ) = V A m ′ (s p )φ m ′ -V B m ′ (s p )q m ′ ( 9
G m (s p ) = m ′ T mm ′ (s p )S m ′ (s p ) (10)
(c) Compute the matrix-vector product:

(Aφ-Bq) = (A 0 φ-B 0 q)+ M m=1 P p=1 G m (s p )C m (s p ) (11)
In our implementation, (s p , w p ) are taken as the Lebedev quadrature points and weights, specifically designed to integrate functions on the unit sphere [13]. For the integrals in [START_REF] Coifman | IEEE Antennas Propagat[END_REF], which do not involve any singularities, simple Gaussian quadrature was used.

The Diffusion Approximation used in DOI is such that |κ I | > κ R . This requires increasing the truncation level L in (4), which in turn affects other computational parameters such as N . Published work on the FMM with κ I = 0 is scarce. The particular case of a lossy space has been studied in [8] in a half-space and for small |κ I |/κ R (maximum 0.32) only, while a typical value for DOI is |κ I |/κ R = 9.7. However, due to the exponential decay of |G|, low accuracy in (4) for large distances R is found to affect only marginally the overall solution accuracy, and in the results presented here we used (following [14]) :

L = |κa √ 3 + ln(π + κa √ 3)| + 6 (12)
To assess the efficiency of our implementation, a series of numerical experiments were conducted on homogeneous spheres with increasing radius, and mesh density of 0.65 elements per mm², giving the number of , µ a = 0.01mm -1 , n = 1 and frequency ω/2π = 100MHz. A Gaussian distribution was used as the source term. Both a conventional BEM and the FM-BEM models were solved for each case. The machine used was a 3GHz processor with 32GB of RAM. Figure 2 shows the expected complexity O(N 2 ) for former and O(N 3/2 ) for the latter. The L2-errror between the two methods was less than 10 -3 in all cases.

As an example of direct interest in DOI of the brain, we constructed also a FM-BEM for the multilayer model developed in [4]. We used a high-resolution version of the three-layered neonate's head, with N = 44356 [15]. This had about three times as many unknowns as the mesh used in [4] and the resultant dense matrices could not be stored in memory for direct BEM. The FM-BEM solved this problem in 220s, whereas the direct BEM for the reduced problem with 16594 unknowns took 347 seconds. Figure 3 shows the photon density displayed on the inner layer (the cortical surface).

Another application of FM-BEM will be within a coupled BEM-FEM approach [16], where the sparse FEM terms can be explicitly stored and used as an extra term in the matrix-vector calculation (11). In this implementation we considered the collocation BEM framework, which is reflected in the simpler expression for C in contrast to that for V. However, a Galerkin-BEM implementation is also possible, and may improve performance due to the symmetry properties of the resulting matrices, as well as a simplification of the BEM-FEM coupling.

Development of an efficient FM-BEM code opens the potential to use high resolution anatomical models within DOI, such as in Diffuse Optical Cortical Mapping (DOCM) [17]. Such models are readily available for example from high resolution MRI using appriopriate analysis and segmentation tools. However, single-level FMM becomes sub-optimal for model sizes N = O(5 10 4 ) and beyond, so implementation of a full multilevel FMM will be required. Finally we note that FMM can be accelerated efficiently using Graphics Processing Units [18], where the difference between FM and conventional BEM is even greater. These extensions will be reported in subsequent publications.

Figure 1 .

 1 Figure 1. Single-level FMM for a 2D domain. (a) Interactions close to cell 1 marked in red, far marked in green (e.g. cell 2); (b) matrix-vector multiplication scheme between cell 1 centred at r 0 and cell 2 centred at r ′ 0

6 .

 6 Apply GMRES iterative solver, with each GMRES iteration requiring matrix-vector products Aφ -Bq (a) For each cell C m ′ , compute the far field S m ′ (s p )

  ) (b) Compute the Fourier components of the field in each cell C m (with summation running over cells C ′ m that are not adjacent to C m )

Figure 2 .

 2 Figure 2. Computation time as a function of number of degrees of freedom for the FMM (blue) and BEM (red).

Figure 3 .

 3 Figure 3. Logarithm of light intensity on cortical surface computed from a 3-layer model