Next: , Previous: , Up: Communication statements   [Contents][Index]


4.4.6 Reducing

A reduction operation is, in a sense, a complementary operation to a multicast (see Multicasting). While a multicast delivers a message from one source to multiple targets, a reduction combines messages from multiple sources (by applying a commutative/associative operator to corresponding elements) to a single target. Reduction is a collective operation: all parties collaborate to calculate the reduced value(s). As an example, if tasks 0, 1, and 2 collectively reduce the messages {5, 1}, {2, 7}, and {3, 4} to task 2 using the “+” operator, then task 2 will receive the message {10, 12}. In fact, coNCePTuaL’s implementation of reductions also supports reductions to multiple targets with each target receiving a copy of the reduced value.

The following grammatical rules define coNCePTuaL’s many-to-many and many-to-one reduction facilities:

<reduce_stmt> ::= <source_task>
REDUCES
<reduce_message_spec>
TO <source_task>
[ WHO RECEIVES THE RESULT <reduce_target_message_spec>]
| <source_task>
REDUCES
<reduce_message_spec>
[ TO <reduce_message_spec>]

<reduce_message_spec> is defined in Message specifications. Both the data providers and data receivers are specified as <source_task> nonterminals (see Source tasks). This design enables any set of tasks to provide the data to reduce and any disjoint or overlapping set of tasks to receive the reduced data. As with all communication in coNCePTuaL, message contents are opaque. Furthermore, the grammar does not currently enable the programmer to specify the commutative/associative operator to use.

A simple many-to-one reduction can be expressed in coNCePTuaL with ‘ALL TASKS REDUCE 5 DOUBLEWORDS TO TASK 0’. Note that the definition of <reduce_message_spec> and <reduce_target_message_spec> (see Message specifications) supports reductions only of INTEGERs and DOUBLEWORDs, not arbitrary <data_type> values. Omitting the optional ‘ TO <reduce_message_spec>’, as in ‘TASKS rt SUCH THAT 3 DIVIDES rt REDUCE AN INTEGER’, specifies that all tasks performing the reduction will receive a copy of the reduced value. The sources and targets can also be designated explicitly as in ‘TASKS xyz SUCH THAT xyz<num_tasks/2 REDUCE 100 DOUBLEWORDS TO TASKS xyz+num_tasks/4’. When that code is run with 8 tasks, tasks 0–3 reduce 100 doublewords (800 bytes) apiece and tasks 2–5 each receive identical copies of the 100 doublewords of reduced data.

Message data used with REDUCES can be transferred WITH DATA TOUCHING (but not WITH VERIFICATION); data alignment can be specified; and, messages buffers can be named explicitly. The following example represents fairly complex many-to-many usage of REDUCES:

TASKS rsrc SUCH THAT rsrc IS EVEN REDUCE 32 64-BYTE-ALIGNED INTEGERS
WITH DATA TOUCHING FROM BUFFER 2 TO TASKS rtarg SUCH THAT
rtarg<num_tasks/4 \/ rtarg>(3*num_tasks)/4 WHO RECEIVE THE RESULT AS
32 UNIQUE PAGE-ALIGNED INTEGERS WITHOUT DATA TOUCHING.

Next: , Previous: , Up: Communication statements   [Contents][Index]

Scott Pakin, pakin@lanl.gov