Bug #1442

CkLoop fixed tree limits helper recruitment

Added by Jim Phillips over 2 years ago. Updated over 1 year ago.

Target version:
Start date:
Due date:
% Done:


Spent time:


CkLoop uses a tree of branching 4 when CkMyNodeSize() >= 8. This means that if you have ppn=9 and rank 0 calls CkLoop, then ranks 5-8 are only recruited if rank 1 is available. If ranks 1-4 are busy then no helpers are activated. This is unexpected and performance-limiting for the use case where CkLoop work is urgent but PEs are generally busy with lower-priority tasks of small grainsize.

A more dynamic approach would be to use messages in the node queue to push notify messages for the PEs, one message per X PEs on the node (probably large X to amortize overhead, but some limit to allow scaling to large thead counts).

ckloop_node.patch View (2.36 KB) Jim Phillips, 02/22/2017 01:59 PM


#1 Updated by Jim Phillips over 2 years ago

Proof-of-concept patch attached. With this change I see the expected behavior, with all PEs able to steal work.
Issues with this patch:
1) Had to declare CmiPushNode() in CkLoop.C, should be added to converse.h and made non-static in all machine layers.
3) Modifies srcRank in notifyMsg, which I think might be enqueued from previous entries on other PEs. This would be unsafe if int write was non-atomic, or if CkLoop is sensitive to extra notify messages being received. It is done because there is no way to tell if message came from node queue or pe queue.
4) Only modified USE_CONVERSE_NOTIFICATION branch. Do we need the other side?

Other possible improvements:
1) For numChunks << nodesize it would be better to put numChunks/numChunks-1 messages in the node queue rather than messaging every PE.
2) If no work left don't send the notifies.
3) The implementation of tree broadcast notification broke tracing by over-writing srcRank to -1.

#2 Updated by Eric Bohm over 2 years ago

  • Assignee set to Seonmyeong Bak

#3 Updated by Phil Miller over 2 years ago

  • Target version changed from 6.8.0 to 6.8.1

I'm inclined to defer this as not release-critical, since CkLoop could do better, but it's not something that's gotten worse, and the issue doesn't prevent its usage or break other things in the system.

#4 Updated by Phil Miller almost 2 years ago

  • Target version changed from 6.8.1 to 6.9.0

#5 Updated by Seonmyeong Bak over 1 year ago

I think this patch can increase the overhead of CkLoop initialization by eliminating the use of implicit tree in CkLoop. (One PE pushes all the messages).
We provide this option but it seems better to add this scheduling with existing scheduling based on tree.

We may not care about other implementations for CkLoop because they are not used and perform slower than USE_CONVERSE_NOTIFICATION.

We may add a field in converseNotifyMsg so that we can tell if the message comes from node queue or pe queue.

#6 Updated by Jim Phillips over 1 year ago

Actually, the overhead (number of messages sent and received) is at worst identical. The latency is only higher if all of the other non-leaf PEs in the tree are idle, which is unlikely in practice, and then the delay is only the time to send nodesize messages. If no other PE is available then the overhead is lower since the calling PE only sends the one node message and receives it after finishing the entry. The calling PE even gets to start its work earlier since it only sends one message.

#7 Updated by Seonmyeong Bak over 1 year ago

  • Status changed from New to In Progress

#8 Updated by Seonmyeong Bak over 1 year ago

  • Status changed from In Progress to Implemented

Added API to set scheduling policy for CkLoop: CkLoop_SetSchedPolicy(sched schedPolicy);

Three options available: NODE_QUEUE, TREE, LIST.

NODE_QUEUE works as this issue suggests.
TREE is the original implementation which uses Tree for delivering CkLoop work.
LIST is the original implementation which doesn't use Tree.

#10 Updated by Sam White over 1 year ago

  • Status changed from Implemented to Merged

Also available in: Atom PDF