Tournament computation in one dimension

In the post on factorial, the following code appears:

var f = tournamentOp₁.d.n.times (default₁.d.1.n.1 (#!d)) ;;

What is going on? Let us look at the definitions from the TransLucid Standard Header:

fun default₁.d.m.n.val X = Y
where
  var Y [d : m..n] = X ;;
  var Y [d : nat] = val ;;
end ;;

fun tournamentOp₁.d.n.g X = Y @ [d <- 0]
where
  dim t <- ilog.n ;;
  var Y = fby.t X (g.(LofPair.d Y).(RofPair.d Y)) ;;
end ;;

The default₁ function creates a stream Y varying in dimension d such that in the interval [m,n], the result will be the value of X. Everywhere else, the value of Y is the default val.

As for tournamentOp₁, when #!t ≡ 0, the value of Y is X. When #!t > 0, each element of Y is the result of applying the binary function g to a pair of elements from Y when #!t was one less. This process is completed until there is just one element left. Since the number n is not necessarily a power of 2, we use default₁ to fill in the slots of X with the neutral element of g.

This form of computation is called tournament computation, and writing programs this way encourages parallel implementations.

Advertisements