predicates often depend on just a small portion of the whole
program state. Thus, we need only to record and store small
projections of program states. For example, for a deterministic specification with pre- and postpredicate set.equals
(set¢) we need only to save object set and its elements (
possibly also the memory reachable from these objects), rather
than the entire program memory. This storage cost sometimes
can be further reduced by storing and comparing check-sums
or approximate hashes.
Then, also at run-time, a call to assert(o, post) checks
post on o and all o¢ saved from previous, matching executions of the same deterministic block. If the postpredicate
does not hold for any of these executions, a determinism
violation is immediately reported. Deterministic blocks can
contain many assert’s so that determinism bugs can be
caught as early as possible and can be more easily localized.
For flexibility, programmers are free to write state projections and predicates using the full Java language. However,
it is a programmer’s responsibility to ensure that these
predicates contain no observable side effects, as there are
no guarantees as to how many times such a predicate may
be evaluated in any particular run.
Built-in Predicates: For programmer convenience, we provide two built-in predicates that are often sufficient for specifying pre- and postpredicates for determinism. The first,
Equals, returns true if the given objects are equal using
their built-in equals method—i.e., if o.equals(o¢). For
many Java objects, this method checks semantic equality—
e.g., for integers, floating-point numbers, strings, lists, sets,
etc. Further, for single- or multidimensional arrays (which
do not implement such an equals method), the Equals
predicate compares corresponding elements using their
equals methods. Figure 2 gives an example with assert
and assume using this Equals predicate.
The second predicate, ApproxEquals, checks if two
floating-point numbers, or the corresponding elements
of two floating-point arrays, are within a given margin of
each other. We found this predicate useful in specifying the
deterministic behavior of numerical applications, where it
is often unavoidable that the low-order bits may vary with
different thread interleavings.
real-World floating-Point Predicates: In practice, floating-point computations often have input-dependent error
bounds. For example, we may expect any two runs of a parallel algorithm for summing inputs x1, …, xn to return answers
4. DeteRminism checKinG LiBRaRY
In this section, we describe the design and implementation of
an assertion library for specifying and checking determinism
of Java programs. Note that, while it might be preferable to
introduce a new syntactic construct for specifying determinism, we provide the functionality as a library to simplify the
implementation.
4. 1. overview
Figure 1 shows the core API for our deterministic assertion library. Functions open and close specify the beginning and end of a deterministic block. Deterministic blocks
may be nested, and each block may contain multiple calls
to functions assume and assert, which are used to specify
the pre- and postpredicates of deterministic behavior.
Each call assume(o, pre) in a deterministic block specifies part of the prepredicate by giving some projection o of
the program state and a predicate pre. That is, it specifies
that one condition for any execution of the block to compute
an equivalent, deterministic result is that pre.apply(o, o¢)
return true for object o¢ from the other execution.
Similarly, a call assert(o, post) in a deterministic block
specifies that, for any execution satisfying every assume,
predicate post.apply(o, o¢) must return true for object o¢
from the other execution.
At run-time, our library records every object (i.e., state
projection) passed to each assert and assume in each
deterministic block, saving them to a central, persistent
store. We require that all objects passed as state projections
implement the Serializable interface to facilitate this
recording. (In practice, this does not seem to be a heavy burden. Most core objects in the Java standard library are serializable, including numbers, strings, arrays, lists, sets, and
maps/hashtables.)
figure 2. Deterministic assertions for a mandelbrot set
implementation from the Parallel Java (PJ) Library. 11
figure 1. core deterministic specification aPi.
public class Deterministic {
static void open() {...}
static void close() {...}
static void assume(Object o, Predicate p) {...}
static void assert(Object o, Predicate p) {...}
interface Predicate {
boolean apply(Object a, Object b);
}
}
main(String args[]) {
// Read parameters from command-line.
...
// Pre-predicate: equal parameters.
Predicate equals = new Equals();
Deterministic.open();
Deterministic.assume(width, equals);
Deterministic.assume(height, equals);
...
Deterministic.assume(gamma, equals);
