{"action":"created","issue":{"url":"https://api.github.com/repos/flux-framework/flux-sched/issues/193","repository_url":"https://api.github.com/repos/flux-framework/flux-sched","labels_url":"https://api.github.com/repos/flux-framework/flux-sched/issues/193/labels{/name}","comments_url":"https://api.github.com/repos/flux-framework/flux-sched/issues/193/comments","events_url":"https://api.github.com/repos/flux-framework/flux-sched/issues/193/events","html_url":"https://github.com/flux-framework/flux-sched/issues/193","id":176773118,"number":193,"title":"Revise Sched's find() and select() operations to leverage visitor/matcher design patterns","user":{"login":"lipari","id":740218,"avatar_url":"https://avatars.githubusercontent.com/u/740218?v=3","gravatar_id":"","url":"https://api.github.com/users/lipari","html_url":"https://github.com/lipari","followers_url":"https://api.github.com/users/lipari/followers","following_url":"https://api.github.com/users/lipari/following{/other_user}","gists_url":"https://api.github.com/users/lipari/gists{/gist_id}","starred_url":"https://api.github.com/users/lipari/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lipari/subscriptions","organizations_url":"https://api.github.com/users/lipari/orgs","repos_url":"https://api.github.com/users/lipari/repos","events_url":"https://api.github.com/users/lipari/events{/privacy}","received_events_url":"https://api.github.com/users/lipari/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2016-09-13T23:05:10Z","updated_at":"2016-09-16T17:28:19Z","closed_at":null,"body":"Spinning off the issue from the discussions in [PR 189](https://github.com/flux-framework/flux-sched/pull/189).\r\n\r\n@dongahn said:\r\n\r\nI believe providing matcher and visitor patterns from resrc and the friends can make resrc APIs more ease to use and robust, and make it be better adaptable when @trws's job spec design comes along, as mentioned in this [comment](https://github.com/flux-framework/rfc/pull/53#issuecomment-234016452)\r\n\r\n[ROSE's AstPrePostProcessing class](http://rosecompiler.org/ROSE_HTML_Reference/classAstPrePostProcessing.html) is one of the examples. It is an abstract class that defines` preOrderVisit` and `postOrderVisit` interfaces for an Abstract Syntax Tree (AST). One can override (e.g., C++ lingo -- meaning, implement) these interfaces in his or her AST analysis class to plug their analysis into the system. Then, this class takes care of an AST traversal and lets the user-defined analysis to be invoked `on post visit` and `on pre visit` during this depth first traversal. \r\n\r\nI actually used this interface for the STAT project. One example code can be found in STAT's TemporarlOderAnalysisAPI in our internal bitbucket repo ([here](https://lc.llnl.gov/bitbucket/projects/STAT/repos/temporalorderingapi/browse/src/TO_LexicographicalOrdering.C#160)).  I used this pattern to implement a way to identify all of the lexical scopes in a C/C++ source file, which contain a specific program point or points. This static information,  along with the runtime stack trace, then allowed me to temporally order points of execution among MPI processes (i.e., determining relative progress). \r\n\r\nOur case can be viewed in a similar way. Our scheduling plugins traverse each resrc hierarchy and act on a vertex that they wants to operate on. But plugins don' t need to implement raw traversal logic by themselves.  Since our language is C, we can't use a OOP concept. But I think a callback that gets invoked on each node visit can bring us similar benefits.  \r\n\r\nIf we abstract out data structures and visitor/match patterns from resource details (e.g., node type, PDU type, switch type and etc), a scheduler plugin writer can focus on scheduling operations like matched/unmatched, allocate/deallocate etc while leaving the traversal across potentially many different resource hierarchy to the visitor pattern provider.  Good separations of concerns. \r\n\r\nIf we were to do this, I would see if we can turn some of the tree traversing logic in our current scheduler plugin to use such visitor/matcher patterns. \r\n\r\nBTW, Clang also has Matcher patterns [in here](http://clang.llvm.org/docs/LibASTMatchersReference.html) though I don't have hands-on experience. \r\n\r\n@trws said:\r\n\r\nClang matchers are, for the record, one of the most awesome features ever written for manipulating C/C++.\r\n\r\nAnyway, actual on-topic comment, the classic [twalk](https://www.gnu.org/software/libc/manual/html_node/Tree-Search-Function.html) style pattern could work well for this, but I'd probably want to simplify it to a DFS only where the function pointer's return value informs the walker as to whether to process children, skip children and continue, or abort completely.  I say DFS specifically because a DFS from the root of the hardware tree, restricted to the hardware tree, can most rapidly identify branches to skip in that ordering IIRC.\r\n"},"comment":{"url":"https://api.github.com/repos/flux-framework/flux-sched/issues/comments/247659189","html_url":"https://github.com/flux-framework/flux-sched/issues/193#issuecomment-247659189","issue_url":"https://api.github.com/repos/flux-framework/flux-sched/issues/193","id":247659189,"user":{"login":"dongahn","id":862123,"avatar_url":"https://avatars.githubusercontent.com/u/862123?v=3","gravatar_id":"","url":"https://api.github.com/users/dongahn","html_url":"https://github.com/dongahn","followers_url":"https://api.github.com/users/dongahn/followers","following_url":"https://api.github.com/users/dongahn/following{/other_user}","gists_url":"https://api.github.com/users/dongahn/gists{/gist_id}","starred_url":"https://api.github.com/users/dongahn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dongahn/subscriptions","organizations_url":"https://api.github.com/users/dongahn/orgs","repos_url":"https://api.github.com/users/dongahn/repos","events_url":"https://api.github.com/users/dongahn/events{/privacy}","received_events_url":"https://api.github.com/users/dongahn/received_events","type":"User","site_admin":false},"created_at":"2016-09-16T17:28:19Z","updated_at":"2016-09-16T17:28:19Z","body":"[Rough Idea] \r\n\r\nWondering if we can use an one-pass algorithm using matcher/visitor patterns to merge `find()` and `select()` (also related to Issue #184)... Looking at `find` and `select` from a scalability lens, roughy speaking we have to traverse the entire tree once with `find` and then again with `select`. I mean, there are cutoff tricks, but complexity looks to me that way. If we can design visitor patterns as well as transactional aggregate updates, I am guessing an efficient one-pass algorithm with many unnecessary traversing pruned. \r\n\r\nRoughly sketch:\r\n\r\n- A scheduler plugin implements a function that can perform as a matcher and scorer on a resrc object on each visit:\r\n   ```\r\nint match_and_score (resrc *in)\r\n```\r\n\r\n- There is a generic priority queue that the scheduler can use within this match function\r\n\r\n\r\n- The scheduler calls a traversal API with the matcher passed in\r\n   ```\r\nint (*matcher_and_score_f) (resrc *) = match_and_score_f;\r\npostorder_walk (resrc *root, matcher_and_scorer_f);\r\n```\r\n\r\n- postorder_walk will take the matcher to each resrc objects to be evaluated.\r\n    - On a visit, matcher first looks at the aggregates and uses them to decide a further descent and telling the walk about descent or no descent with a return code\r\n    - On a visit, the target resrc object is scored according to the scheduler's goal. Here, a flow-aware matcher can also evaluate all flow objects if the resrc object has a link to that flow. \r\n    - If the object matches, matcher pushes that object into a priority queue with its evaluation score as the priority. \r\n\r\n- Once this pruned walk is done, the resulting priority queue will have all of the qualified resources ordered by the match score\r\n\r\n- Scheduler can either allocate or reserve the top resrc and also update the aggregates accordingly. \r\n\r\n- In case the objects in the priority queue is not enough, backfill scheduler will start this algorithm to all of the resource used by the job that will complete earliest. Repeat until all resources are reserved...\r\n\r\n\r\n\r\n\r\n\r\n"}}
{"actor":{"display_login":"dongahn"}}