Hyperobjects

Description

Cilk Plus defines a category of objects called “hyperobjects”. Hyperobjects allow thread-safe access to shared objects by giving each parallel strand running in parallel a separate instance of the object.

Parallel code uses a hyperobject by performing a hyperobject lookup operation. The hyperobject lookup returns a reference to an object, called a view, that is guaranteed not to be shared with any other active strands in the program. The sequencing of a hyperobject lookup within an expression is not specified. The runtime system creates a view when needed, using callback functions provided by the hyperobject type. When strands synchronize, the hyperobject views are merged into a single view, using another callback function provided by the hyperobject type.

The view of a hyperobject visible to a program may change at any spawn or sync (including the implicit spawns and syncs within a _Cilk_for loop). The identity (address) of the view does not change within a single strand. The view of a given hyperobject visible within a given strand is said to be associated with that view. A hyperobject has the same view before the first spawn within a task block as after a sync within the same task block, even though the thread ID may not be the same (i.e., hyperobject views are not tied to threads). A hyperobject has the same view upon entering and leaving a _Cilk_for loop and within the first iteration (at least) of the _Cilk_for loop. A special view is associated with a hyperobject when the hyperobject is initially created. This special view is called the leftmost view or earliest view because it is always visible to the leftmost (earliest) descendent in the depth-first, left-to-right traversal of the program's spawn tree. The leftmost view is given an initial value when the hyperobject is created.

Programmer note: If two expressions compute the same address for a view, then they have not been scheduled in parallel. This property yields one of the simplest ways by which a program can observe the runtime behavior of the scheduler.

Implementation note: An implementation can optimize hyperobject lookups by performing them only when a view has (or might have) changed. This optimization can be facilitated by attaching implementation-specific attributes to the hyperobject creation, lookup, and/or destruction operations.

Reducers

The vast majority of hyperobjects belong to a category known as “reducers.” Each reducer type provides a reduce callback operation that merges two views in a manner specific to the reducer. For a pair of views V₁ and V₂, the result of calling reduce(V₁, V₂) is notated as V₁⊗V₂. Each reducer also provides an identity callback operation that initializes a new view.

The reduce callback for a “classical” reducer implements an operation ⊗ such that (a⊗b)⊗c==a⊗(b⊗c) (i.e., ⊗ is associative). The view-initialization callback for such a reducer sets the view to an identity value I such that I⊗v==v and v⊗I==v for any value v of value_type. Given an associative ⊗ and an identity I, the triplet (value_type, ⊗, I) describes a mathematical monoid. For example, (int, +, 0) is a monoid, as is (list, concatenate, empty). If each individual view, R, of a classical reducer is modified using only expressions that are equivalent to R←R⊗v (where v is of value_type), then the reducer computes the same value in the parallel program as would be computed in the serialization of the program. (In actuality, the “⊗” in the expression “R←R⊗v” can represent a set of mutually-associative operations. For example, += and -= are mutually associative.) For example, a spawned function or _Cilk_for body can append items onto the view of a list reducer with monoid (list, concatenate, empty). At the end of the parallel section of code, the reducer's view contains the same list items in the same order as would be generated in a serial execution of the same code.

Given a set of strands entering a sync, S₁,S₂,S₃,…S_n, associated with views V₁,V₂,V₃,…V_n, respectively such that S_i is earlier in the serial ordering than S_i+1, a single view, W, emerges from the sync with value W←V₁⊗V₂⊗V₃⊗…⊗V_n, such that the left-to-right order is maintained but the grouping (associativity) of the operations is unspecified. The timing of this “reduction” is unspecified – in particular, subsequences typically will be computed asynchronously as child tasks complete. Every view except the one emerging from the sync is destroyed after the merge. If any of the strands does not have an associated view, then the invocation of the reduce callback function can be elided (i.e., the missing view is treated as an identity).

A strand is never associated with more than one view for a given reducer, but multiple strands can be associated with the same view if those strands are not scheduled in parallel (at run time). Specifically, for a given reducer, the association of a strand to a view of the reducer obeys the following rules:

1. The strand that initializes the reducer is associated with the leftmost view.
2. If two strands execute in series (i.e., both strands are part of a larger strand), then both are associated with the same view.
3. The child strand of a spawn is associated with the same view as the strand that entered the spawn.
4. If the continuation strand of a spawn is scheduled in parallel with the child, then the continuation strand is associated with a new view, initialized using identity. The implementation may create the new view at any time up until the first hyperobject lookup following the spawn. If the continuation strand does not perform a hyperobject lookup, then the implementation is not required to create a view for that strand.
5. If the continuation strand of a spawn is not scheduled in parallel with the child strand (i.e., the child and the continuation execute in series), then the continuation strand is associated with the same view as the child strand.
6. The strand that emerges from a sync is associated with the same view as the leftmost strand entering the sync.

Even before the final reduction, the leftmost view of a reducer will contain the same value as in the serial execution. Other views, however, will contain partial values that are different from the serial execution.

If ⊗ is not associative or if identity does not yield a true identity value then the result of a set of reductions will be non-deterministic (i.e., it will vary based on runtime scheduling). Such “non-classical” reducers are nevertheless occasionally useful. Note that, for a classical reducer, the ⊗ operator needs to be associative, but does not need to be commutative.

Hyperobjects in C++

C++ hyperobject syntax

At present, reducers and holders are the only kind of hyperobject supported. In C++, every reducer hyperobject has a hyperobject type, which type is an instantiation of the cilk::reducer class template, which is defined in the header <cilk/reducer.h>. The cilk::reducer class template has a single template type parameter, Monoid, which shall be a class type. (See C++ Monoid class requirements, below.)

For a given monoid, M, the type cilk::reducer<M> defines a hyperobject type. The cilk::reducer class template provides constructors, a destructor, and (const and non-const versions of) value_type& operator() operator*() and value_type& view(), both of which return a an lvalue reference to the current view, and operator->(), which returns the address of the current view.

A hyperobject reducer is created by defining an instance of cilk::reducer<M>:

cilk::reducer<M> hv(args);

Where args is a list of M::valueview_type constructor arguments used to initialize the leftmost view of hv. A hyperobject lookup is performed by invoking the member function, view() or member operator*() or operator->() on the hyperobject, as in the following examples:

hv.view().append(elem);
(*hv).append(elem);
hv->append(elem); hv().append(elem);

In these examples, append is an operation to be applied to the current view of hv, and is presumably consistent with the associative operation defined in the monoid, M.

Modifying a hyperobject view in a way that is not consistent with the associative operation in the monoid can lead to subtle bugs. For example, addition is not associative with multiplication, so performing a multiplication on the view of a summing reducer will almost certainly produce incorrect results. To prevent this kind of error, it is common to wrap reducers in proxy classes that expose possible for the monoid to define a separate view_type class that wraps the value_type and exposes only the valid associative operations. (See Monoid and View class requirements, below.) All of the reducers included in the standard reducer library have such wrappers.

C++ reducer class template

Where the below table indicates that the signature of a function includes the form Args&&..., in an implementation that supports C++ variadic templates, the function shall be defined as a variadic function template. In an implementation that does not support variadic templates, the function shall be defined as a set of templates taking from 0 to N arguments of type const Arg &, where N is at least 4.

typename Monoid

typedef
typename Monoid::value_type
	value_type;

typedef
typename Monoid::view_type
	view_type;

template<typename... Args>
reducer(const Args&&... args);

template<typename... Args>
reducer(const Monoid& m,
	const Args&&... args);

Monoid& monoid();
Monoid const& monoid() const;

view_type& view();
view_type& view() const;

void move_in(value_type& obj);

void move_out(value_type& obj);

void set_value(const value_type& obj);

type get_value() const;

C++ Monoid class requirements

To define a reducer, a program defines a monoid class with public members representing the monoid, (T, ⊗, identity) as follows:

value_type

view_type

reduce(value_type* left,
	value_type* right)

identity(value_type* p)

destroy(value_type* p)

allocate(size_t size)

deallocate(value_type void* p)

If any of the above functions do not modify the state of the monoid (most monoids carry no state), then those functions may be declared static or const. The monoid type may derive from an instantiation of cilk::monoid_base<T,V>, which defines value_type and view_type as aliases for T and V, respectively (where V defaults to T), and provides default implementations for identity, destroy, allocate, and deallocate. The derived class needs to define reduce and override only those functions for which the default is incorrect.

C++ View class requirements

By default, view_type is the same as value_type. Commonly, however, it is a wrapper around value_type that presents a more limited interface in order to achieve a measure of static safety. For example, for a summing reducer, view_type might support += and ++ but not operations like *= that are inconsistent with a summing reduction. Other times, view_type holds a more complex type that allows for more efficient reduction operations.

When view_type is identical to value_type the reducer imposes no further requirements on it beyond those already required by the identity and reduce operations in the monoid.

When view_type differs from value_type, then view_type must provide the following member functions:

view_move_in(value_type& v)

view_move_out(value_type& v)

view_set_value(const value_type& v)

view_get_value() const

C++ hyperobject behavior

An object of type M::value_type is constructed by the reducer constructor. This object is called the initial view or leftmost view of the hyperobject. When a hyperobject goes out of scope, the destructor is called on the leftmost view. It is unspecified whether M::allocate and M::deallocate are called to allocate and deallocate the leftmost view (they are not called in the current Intel implementation).

The implementation may create a view at any spawn that has been scheduled in parallel, or may lazily defer creation until the first access within a strand. The implementation creates a view by calling M::allocate followed by M::identity. (This is in addition to the initial view created by construction of the hyperobject.) The calls to M::allocate and M::identity are part of the strand for the purpose of establishing the absence of a data race.

At any sync or at the end of any spawned (child) function, the runtime may merge two views by calling M::reduce(left, right), where right is the earliest remaining view that is later than left. The M::reduce function is expected to store the merged result in the left view. After the merge, the runtime destroys the right view by calling M::destroy followed by M::deallocate. Every view except the leftmost view is passed exactly once as the second argument to reduce. The calls to M::reduce, M::destroy and M::deallocate happen after completion of both of the strands that formerly owned the left and right views.

If a monoid member function executes a hyperobject lookup (directly or through a function call), the behavior of the program is undefined.

For purposes of establishing the absence of a data race, a hyperobject view is considered a distinct object in each parallel strand. A hyperobject lookup is considered a read of the hyperobject.

Hyperobjects in C

C hyperobject syntax

The C mechanism for defining and using hyperobjects depends on a small number of typedefs and preprocessor macros provided in the Cilk library header <cilk/reducer.h>. C does not have the template capabilities of C++ and thus has a less abstract hyperobject syntax. Unlike C++, each C hyperobject variable is unique – there is no named type that unites similar hyperobjects. There is, however, an implicit “hyperobject type” defined by the operations that comprise the hyperobjects' monoid. The provided macros facilitate creating reducer variables, which are the only type of hyperobject currently supported. The terms “reducer” and “hyperobject” are used interchangeably in this section.

To define a C reducer, the program defines three functions representing operations on a monoid (T, ⊗, identity):

void T_reduce(void* r, void* left, void* right);
void T_identity(void* r, void* view);
void T_destroy(void* r, void* view);

The names of these functions are for illustration purposes only and must be chosen, as usual, to avoid conflicts with other identifiers. The purposes of these functions are as follows:

The r argument to each of these functions is a pointer to the actual reducer variable and is usually ignored. Since most C types do not require cleanup on destruction, the T_destroy function often does nothing. As a convenience, the Cilk library makes this common implementation available as a library function, __cilkrts_hyperobject_noop_destroy.

A reducer, hv, is defined and given an initial value, init, using the CILK_C_DECLARE_REDUCER and CILK_C_INIT_REDUCER macros as follows:

CILK_C_DECLARE_REDUCER(T) hv =
	CILK_C_INIT_REDUCER(T_identity, T_reduce, T_destroy,
		init);

The init expression is used to initialize the leftmost reducer view. The CILK_C_DECLARE_REDUCER macro defines a struct and can be used in a typedef or extern declaration as well:

extern CILK_C_DECLARE_REDUCER(T) hv;

The CILK_C_INIT_REDUCER macro expands to a static initializer for a hyperobject of any type. After initialization, the leftmost view of the reducer is available as hv.value.

If The behavior is undefined if a reducer is local to a function, it shall be with automatic storage duration is not registered before first use using the CILK_C_REGISTER_REDUCER macro and unregistered after its last use using the CILK_C_UNREGISTER_REDUCER macro:

CILK_C_REGISTER_REDUCER(hv);
/* use hv here */
CILK_C_UNREGISTER_REDUCER(hv);

For the purpose of registration and unregistration, first use and last use are defined with respect to the serialization of the program. If the reducer view immediately before unregistration shall be is not the same (does not have the same address) as the reducer view immediately after registration, the behavior is undefined. In practice, this means that any spawns after the registration have been synced before the unregistration and that no spawns before the registration have been synced before the unregistration. Registration and unregistration are optional for reducers declared in global scope. The value member of the reducer continues to be available after unregistration, but a hyperobject lookup on an unregistered reducer results in undefined behavior unless the reducer is registered again.

A hyperobject lookup is performed using the REDUCER_VIEW macro:

REDUCER_VIEW(hv) += expr;

As in the case of a C++ reducer, modifying a reducer other than through the correct associative operations can cause bugs. Unfortunately, C does not have sufficient abstraction mechanisms to prevent this kind of error. Nevertheless, the Cilk library provides wrapper macros to simplify the declaration and initialization, though not the safety, of library-provided reducers in C. For example, you can define and initialize a summing reducer this way:

CILK_C_DECLARE_REDUCER(long) hv =
	REDUCER_OPADD_INIT(long, 0);

A C reducer can be declared, defined, and accessed within C++ code, but a C++ reducer cannot be used within C code.

C hyperobject behavior

The macro CILK_C_DECLARE_REDUCER(T) defines a struct with a data member of type T, named value. The macro CILK_C_INIT_REDUCER(T,I,R,D,V) expands to a braced-init-list appropriate for initializing a variable, hv, of structure type declared with CILK_C_DECLARE_REDUCER(T) such that hv, can be recognized by the runtime system as a C reducer with value type T, identity function I, reduction function R, destroy function D, and initial value V.

Invoking CILK_C_REGISTER_REDUCER(hv) makes a call into the runtime system that registers hv.value as the initial, or leftmost, view of the C hyperobject hv. The macro CILK_C_UNREGISTER_REDUCER(hv) makes a call into the runtime system that removes hyperobject hv from the runtime system's internal map. Attempting to access hv after it has been unregistered will result in undefined behavior. If a hyperobject is never registered, the leftmost view will be associated with the program strand before the very first spawn in the program and will follow the leftmost branch of the execution DAG. This association is typically useful only for hyperobjects in global scope.

The implementation may create a view at any spawn the start of any strand that has been scheduled in parallel, or may lazily defer creation until the first access within a strand. The implementation creates a view by allocating it with malloc, then calling the identity function specified in the reducer initialization. (This is in addition to the initial view created by construction of the reducer.) The call to the identity function is part of the strand for the purpose of establishing the absence of a data race.

At any sync or at the end of any spawned (child) function, the runtime may merge two views by calling the reduction function (specified in the reducer initialization) on the values left and right, where right is the earliest remaining view that is later than left. The reduction function is expected to store the merged result in the left view. After the merge, the runtime destroys the right view by calling the destroy function for the hyperobject, then deallocates it using free. Every view except the leftmost view is passed exactly once as the second argument the reduction function. The calls to reduction and destroy functions happen after completion of both of the strands that formerly owned the left and right views.

If a monoid function executes a hyperobject lookup, the behavior of the program is undefined.

For purposes of establishing the absence of a data race, a hyperobject view is considered a distinct object in each parallel strand. A hyperobject lookup is considered a read of the hyperobject.