n-ary tree functions

n-ary tree functions

n-ary trees are used quite frequently in communication patterns because they require only logarithmic time (in the number of tasks) for a message to propagate from the root to a leaf. coNCePTuaL supports n-ary trees in the form of the TREE_PARENT and TREE_CHILD functions.

Function: TREE_PARENT (task_ID [, fan-out])

TREE_PARENT takes a task number and an optional tree fan-out (n) and returns the task’s parent in an n-ary tree. n defaults to ‘2’, i.e., a binary tree. Taking the TREE_PARENT of any task less than 1 returns the value ‘-1’.

Function: TREE_CHILD (task_ID, child [, fan-out])

TREE_CHILD takes a task number, a child number (0 <= i < N), and an optional tree fan-out (n), which again defaults to ‘2’. It returns the task number corresponding to the given task’s childth child.

The following illustrations show how tasks are numbered in, respectively, a 2-ary and a 3-ary tree:

As shown by the 2-ary tree, task 1’s children are task 3 and task 4. Therefore, ‘TREE_PARENT(3)’ and ‘TREE_PARENT(4)’ are both ‘1’; ‘TREE_CHILD(1, 0)’ is ‘3’; and, ‘TREE_CHILD(1, 1)’ is ‘4’. In a 3-ary tree, each task has three children. Hence, the following expressions hold:

• ‘TREE_PARENT(7, 3)’ ⇒ ‘2’
• ‘TREE_PARENT(8, 3)’ ⇒ ‘2’
• ‘TREE_PARENT(9, 3)’ ⇒ ‘2’
• ‘TREE_CHILD(2, 0, 3)’ ⇒ ‘7’
• ‘TREE_CHILD(2, 1, 3)’ ⇒ ‘8’
• ‘TREE_CHILD(2, 2, 3)’ ⇒ ‘9’