Next: Synchronizing, Previous: Multicasting, Up: Communication statements [Contents][Index]
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_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 INTEGER
s
and
DOUBLEWORD
s, 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: Synchronizing, Previous: Multicasting, Up: Communication statements [Contents][Index]