{"action":"created","comment":{"url":"https://api.github.com/repos/gnuradio/greps/pulls/comments/175628310","pull_request_review_id":105187861,"id":175628310,"diff_hunk":"@@ -0,0 +1,124 @@\n+# GREP 0011 -- Create new scheduler to increase performance \n+\n+- Original Author: David Hofstee <gnuradio@c001.nl>\n+- Champion: David Hofstee <gnuradio@c001.nl>\n+- Status: Draft \n+\n+History:\n+- 15-Feb-2018: Initial Draft\n+\n+## Abstract\n+\n+Recent presentations at GRCon showed that performance of Gnuradio can\n+be enhanced by simple scheduling improvements. We propose to write a new scheduler\n+(framework) in Gnuradio in order to get better overal performance. This scheduler\n+will be based on the Criticality function[1] or a derivative. This function is \n+suitable to analyze performance of Kahn Process Network applications like Gnuradio \n+and their scheduling in both homogeneous and heterogeneous processing environments.\n+\n+This scheduling framework should provide profiling (analysis), scheduling\n+for Gnuradio and provide feedback to the user to show scheduling hot spots (in\n+processing, bandwidth and memory usage) to allow for optimization.\n+\n+Another goal is to document, present and explain the effort and results to the\n+Gnuradio community. \n+\n+## Copyright / License\n+\n+This GREP is licensed as CC-BY-ND.\n+Copyright 2018 David Hofstee\n+\n+## Motivation\n+\n+### Background in scheduling\n+The scheduler from Gnuradio can be enhanced. Most schedulers work with a priority\n+of a process and schedule based on that. Although this can work on a \n+homogeneous processing platform (like a single CPU, multi core CPU or NUMA \n+architecture), it is not sufficient to describe what choices need to be made on \n+a heterogeneous system (such as a CPU combined with GPU or FPGA) where processors \n+have different execution speeds. \n+\n+One example that proves this is by imagining a processing architecture with a fast, \n+a medium fast and a slow processor. If a scheduler had to preempt a thread for \n+another, which thread would it need to pause? And why? Priority scheduling does \n+not answer that question. Because it does not take the execution speed into account. \n+\n+Another important aspect of scheduling a KPN is in the fact that memory access and \n+data transfers are usually not taken into account. But their behavior can be \n+detrimental in the performance of the KPN due to cache misses, interrupts, delays, \n+etc. \n+\n+Some background on traditional scheduling can be found in [6] [7] [8] [9]\n+\n+### The role of the Criticality function\n+Contrary to priority schedulers, the Criticality function takes the differences \n+in execution speed in heterogeneous environments into account. It allows the \n+scheduler to analyze which KPN node must be scheduled for optimal performance.\n+\n+I stress the use of heterogeneous processing environments because the \n+homogeneous environment is a simplified version of it. Also, many GR users do have \n+options to execute the KPN on other processors next to their main CPU. Furthermore\n+it helps software engineers focus their effort in optimisations (using SIMD, \n+other languages or better compilers). \n+\n+No prior implementation of a Criticality-type scheduler, a scheduler using the \n+Criticality function, exists. So it has to be made from scratch. All tooling, \n+needed to analyze the performance of the Gnuradio application blocks need to be \n+created too. This is necessary to calculate the Criticality function for the\n+scheduler. \n+\n+After creating the Criticality function for a KPN, other (sometimes conflicting) \n+goals exist, such as having the scheduler:\n+- Optimize for low memory usage\n+- Optimize for cache hit rate at processors\n+- Optimize for latency\n+- Optimize for data throughput (at various data busses)\n+- Optimize for execution time jitter\n+\n+If a user wants to accelerate the Gnuradio application, optimalisation needs to\n+be done. It would be useful if the scheduler can analyze the following for a user:\n+- What processes can be optimized and explain the required speedup needed to\n+  attain maximum performance. \n+- Predict performance (bottlenecks) on multiple architectures\n+\n+At some point, the GR scheduler must cooperate with the scheduler of the operating\n+system. Some consideration must also be taken into account for the differences \n+of optimization that can be done. E.g. a RT kernel has different options for\n+high performance than a normal kernel. Other workloads of a system come into play\n+as well (e.g. a browser from a user). \n+  \n+## Description\n+\n+### Origins\n+There are a number of papers on GRCon17 describing that enhancements in scheduling\n+can be worthwile [2][3][4][5]. Some information on this topic was shared at FOSDEM18","path":"grep-0011-scheduler.md","position":94,"original_position":94,"commit_id":"e1a75fb817159f3952f7d185c60288cf420aa83a","original_commit_id":"e1a75fb817159f3952f7d185c60288cf420aa83a","user":{"login":"mbr0wn","id":508035,"avatar_url":"https://avatars0.githubusercontent.com/u/508035?v=4","gravatar_id":"","url":"https://api.github.com/users/mbr0wn","html_url":"https://github.com/mbr0wn","followers_url":"https://api.github.com/users/mbr0wn/followers","following_url":"https://api.github.com/users/mbr0wn/following{/other_user}","gists_url":"https://api.github.com/users/mbr0wn/gists{/gist_id}","starred_url":"https://api.github.com/users/mbr0wn/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mbr0wn/subscriptions","organizations_url":"https://api.github.com/users/mbr0wn/orgs","repos_url":"https://api.github.com/users/mbr0wn/repos","events_url":"https://api.github.com/users/mbr0wn/events{/privacy}","received_events_url":"https://api.github.com/users/mbr0wn/received_events","type":"User","site_admin":false},"body":"Typo (\"worthwhile\")","created_at":"2018-03-20T00:44:23Z","updated_at":"2018-03-20T00:50:12Z","html_url":"https://github.com/gnuradio/greps/pull/12#discussion_r175628310","pull_request_url":"https://api.github.com/repos/gnuradio/greps/pulls/12","author_association":"OWNER","_links":{"self":{"href":"https://api.github.com/repos/gnuradio/greps/pulls/comments/175628310"},"html":{"href":"https://github.com/gnuradio/greps/pull/12#discussion_r175628310"},"pull_request":{"href":"https://api.github.com/repos/gnuradio/greps/pulls/12"}}},"pull_request":{"url":"https://api.github.com/repos/gnuradio/greps/pulls/12","id":175777837,"html_url":"https://github.com/gnuradio/greps/pull/12","diff_url":"https://github.com/gnuradio/greps/pull/12.diff","patch_url":"https://github.com/gnuradio/greps/pull/12.patch","issue_url":"https://api.github.com/repos/gnuradio/greps/issues/12","number":12,"state":"open","locked":false,"title":"Proposal for scheduler work","user":{"login":"DavidHofstee","id":36516408,"avatar_url":"https://avatars1.githubusercontent.com/u/36516408?v=4","gravatar_id":"","url":"https://api.github.com/users/DavidHofstee","html_url":"https://github.com/DavidHofstee","followers_url":"https://api.github.com/users/DavidHofstee/followers","following_url":"https://api.github.com/users/DavidHofstee/following{/other_user}","gists_url":"https://api.github.com/users/DavidHofstee/gists{/gist_id}","starred_url":"https://api.github.com/users/DavidHofstee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/DavidHofstee/subscriptions","organizations_url":"https://api.github.com/users/DavidHofstee/orgs","repos_url":"https://api.github.com/users/DavidHofstee/repos","events_url":"https://api.github.com/users/DavidHofstee/events{/privacy}","received_events_url":"https://api.github.com/users/DavidHofstee/received_events","type":"User","site_admin":false},"body":"Hi,\r\n\r\nDiscussed some stuff with Marco earlier on Fosdem. Please read and comment. \r\n\r\nYours,\r\n\r\n\r\nDavid ","created_at":"2018-03-18T22:37:39Z","updated_at":"2018-03-20T00:50:12Z","closed_at":null,"merged_at":null,"merge_commit_sha":"733b66258d6e85b3996cf6884232abdb67585aec","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/gnuradio/greps/pulls/12/commits","review_comments_url":"https://api.github.com/repos/gnuradio/greps/pulls/12/comments","review_comment_url":"https://api.github.com/repos/gnuradio/greps/pulls/comments{/number}","comments_url":"https://api.github.com/repos/gnuradio/greps/issues/12/comments","statuses_url":"https://api.github.com/repos/gnuradio/greps/statuses/e1a75fb817159f3952f7d185c60288cf420aa83a","head":{"label":"DavidHofstee:master","ref":"master","sha":"e1a75fb817159f3952f7d185c60288cf420aa83a","user":{"login":"DavidHofstee","id":36516408,"avatar_url":"https://avatars1.githubusercontent.com/u/36516408?v=4","gravatar_id":"","url":"https://api.github.com/users/DavidHofstee","html_url":"https://github.com/DavidHofstee","followers_url":"https://api.github.com/users/DavidHofstee/followers","following_url":"https://api.github.com/users/DavidHofstee/following{/other_user}","gists_url":"https://api.github.com/users/DavidHofstee/gists{/gist_id}","starred_url":"https://api.github.com/users/DavidHofstee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/DavidHofstee/subscriptions","organizations_url":"https://api.github.com/users/DavidHofstee/orgs","repos_url":"https://api.github.com/users/DavidHofstee/repos","events_url":"https://api.github.com/users/DavidHofstee/events{/privacy}","received_events_url":"https://api.github.com/users/DavidHofstee/received_events","type":"User","site_admin":false},"repo":{"id":125772987,"name":"greps","full_name":"DavidHofstee/greps","owner":{"login":"DavidHofstee","id":36516408,"avatar_url":"https://avatars1.githubusercontent.com/u/36516408?v=4","gravatar_id":"","url":"https://api.github.com/users/DavidHofstee","html_url":"https://github.com/DavidHofstee","followers_url":"https://api.github.com/users/DavidHofstee/followers","following_url":"https://api.github.com/users/DavidHofstee/following{/other_user}","gists_url":"https://api.github.com/users/DavidHofstee/gists{/gist_id}","starred_url":"https://api.github.com/users/DavidHofstee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/DavidHofstee/subscriptions","organizations_url":"https://api.github.com/users/DavidHofstee/orgs","repos_url":"https://api.github.com/users/DavidHofstee/repos","events_url":"https://api.github.com/users/DavidHofstee/events{/privacy}","received_events_url":"https://api.github.com/users/DavidHofstee/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/DavidHofstee/greps","description":"GNU Radio Enhancement Proposals","fork":true,"url":"https://api.github.com/repos/DavidHofstee/greps","forks_url":"https://api.github.com/repos/DavidHofstee/greps/forks","keys_url":"https://api.github.com/repos/DavidHofstee/greps/keys{/key_id}","collaborators_url":"https://api.github.com/repos/DavidHofstee/greps/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/DavidHofstee/greps/teams","hooks_url":"https://api.github.com/repos/DavidHofstee/greps/hooks","issue_events_url":"https://api.github.com/repos/DavidHofstee/greps/issues/events{/number}","events_url":"https://api.github.com/repos/DavidHofstee/greps/events","assignees_url":"https://api.github.com/repos/DavidHofstee/greps/assignees{/user}","branches_url":"https://api.github.com/repos/DavidHofstee/greps/branches{/branch}","tags_url":"https://api.github.com/repos/DavidHofstee/greps/tags","blobs_url":"https://api.github.com/repos/DavidHofstee/greps/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/DavidHofstee/greps/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/DavidHofstee/greps/git/refs{/sha}","trees_url":"https://api.github.com/repos/DavidHofstee/greps/git/trees{/sha}","statuses_url":"https://api.github.com/repos/DavidHofstee/greps/statuses/{sha}","languages_url":"https://api.github.com/repos/DavidHofstee/greps/languages","stargazers_url":"https://api.github.com/repos/DavidHofstee/greps/stargazers","contributors_url":"https://api.github.com/repos/DavidHofstee/greps/contributors","subscribers_url":"https://api.github.com/repos/DavidHofstee/greps/subscribers","subscription_url":"https://api.github.com/repos/DavidHofstee/greps/subscription","commits_url":"https://api.github.com/repos/DavidHofstee/greps/commits{/sha}","git_commits_url":"https://api.github.com/repos/DavidHofstee/greps/git/commits{/sha}","comments_url":"https://api.github.com/repos/DavidHofstee/greps/comments{/number}","issue_comment_url":"https://api.github.com/repos/DavidHofstee/greps/issues/comments{/number}","contents_url":"https://api.github.com/repos/DavidHofstee/greps/contents/{+path}","compare_url":"https://api.github.com/repos/DavidHofstee/greps/compare/{base}...{head}","merges_url":"https://api.github.com/repos/DavidHofstee/greps/merges","archive_url":"https://api.github.com/repos/DavidHofstee/greps/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/DavidHofstee/greps/downloads","issues_url":"https://api.github.com/repos/DavidHofstee/greps/issues{/number}","pulls_url":"https://api.github.com/repos/DavidHofstee/greps/pulls{/number}","milestones_url":"https://api.github.com/repos/DavidHofstee/greps/milestones{/number}","notifications_url":"https://api.github.com/repos/DavidHofstee/greps/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/DavidHofstee/greps/labels{/name}","releases_url":"https://api.github.com/repos/DavidHofstee/greps/releases{/id}","deployments_url":"https://api.github.com/repos/DavidHofstee/greps/deployments","created_at":"2018-03-18T22:21:51Z","updated_at":"2018-03-18T22:35:21Z","pushed_at":"2018-03-18T22:35:20Z","git_url":"git://github.com/DavidHofstee/greps.git","ssh_url":"git@github.com:DavidHofstee/greps.git","clone_url":"https://github.com/DavidHofstee/greps.git","svn_url":"https://github.com/DavidHofstee/greps","homepage":null,"size":22,"stargazers_count":0,"watchers_count":0,"language":null,"has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":null,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"gnuradio:master","ref":"master","sha":"2e3305788b25b0244ead84b921f5b9c8bde0309c","user":{"login":"gnuradio","id":1278659,"avatar_url":"https://avatars2.githubusercontent.com/u/1278659?v=4","gravatar_id":"","url":"https://api.github.com/users/gnuradio","html_url":"https://github.com/gnuradio","followers_url":"https://api.github.com/users/gnuradio/followers","following_url":"https://api.github.com/users/gnuradio/following{/other_user}","gists_url":"https://api.github.com/users/gnuradio/gists{/gist_id}","starred_url":"https://api.github.com/users/gnuradio/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gnuradio/subscriptions","organizations_url":"https://api.github.com/users/gnuradio/orgs","repos_url":"https://api.github.com/users/gnuradio/repos","events_url":"https://api.github.com/users/gnuradio/events{/privacy}","received_events_url":"https://api.github.com/users/gnuradio/received_events","type":"Organization","site_admin":false},"repo":{"id":71032138,"name":"greps","full_name":"gnuradio/greps","owner":{"login":"gnuradio","id":1278659,"avatar_url":"https://avatars2.githubusercontent.com/u/1278659?v=4","gravatar_id":"","url":"https://api.github.com/users/gnuradio","html_url":"https://github.com/gnuradio","followers_url":"https://api.github.com/users/gnuradio/followers","following_url":"https://api.github.com/users/gnuradio/following{/other_user}","gists_url":"https://api.github.com/users/gnuradio/gists{/gist_id}","starred_url":"https://api.github.com/users/gnuradio/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gnuradio/subscriptions","organizations_url":"https://api.github.com/users/gnuradio/orgs","repos_url":"https://api.github.com/users/gnuradio/repos","events_url":"https://api.github.com/users/gnuradio/events{/privacy}","received_events_url":"https://api.github.com/users/gnuradio/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/gnuradio/greps","description":"GNU Radio Enhancement Proposals","fork":false,"url":"https://api.github.com/repos/gnuradio/greps","forks_url":"https://api.github.com/repos/gnuradio/greps/forks","keys_url":"https://api.github.com/repos/gnuradio/greps/keys{/key_id}","collaborators_url":"https://api.github.com/repos/gnuradio/greps/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/gnuradio/greps/teams","hooks_url":"https://api.github.com/repos/gnuradio/greps/hooks","issue_events_url":"https://api.github.com/repos/gnuradio/greps/issues/events{/number}","events_url":"https://api.github.com/repos/gnuradio/greps/events","assignees_url":"https://api.github.com/repos/gnuradio/greps/assignees{/user}","branches_url":"https://api.github.com/repos/gnuradio/greps/branches{/branch}","tags_url":"https://api.github.com/repos/gnuradio/greps/tags","blobs_url":"https://api.github.com/repos/gnuradio/greps/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/gnuradio/greps/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/gnuradio/greps/git/refs{/sha}","trees_url":"https://api.github.com/repos/gnuradio/greps/git/trees{/sha}","statuses_url":"https://api.github.com/repos/gnuradio/greps/statuses/{sha}","languages_url":"https://api.github.com/repos/gnuradio/greps/languages","stargazers_url":"https://api.github.com/repos/gnuradio/greps/stargazers","contributors_url":"https://api.github.com/repos/gnuradio/greps/contributors","subscribers_url":"https://api.github.com/repos/gnuradio/greps/subscribers","subscription_url":"https://api.github.com/repos/gnuradio/greps/subscription","commits_url":"https://api.github.com/repos/gnuradio/greps/commits{/sha}","git_commits_url":"https://api.github.com/repos/gnuradio/greps/git/commits{/sha}","comments_url":"https://api.github.com/repos/gnuradio/greps/comments{/number}","issue_comment_url":"https://api.github.com/repos/gnuradio/greps/issues/comments{/number}","contents_url":"https://api.github.com/repos/gnuradio/greps/contents/{+path}","compare_url":"https://api.github.com/repos/gnuradio/greps/compare/{base}...{head}","merges_url":"https://api.github.com/repos/gnuradio/greps/merges","archive_url":"https://api.github.com/repos/gnuradio/greps/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/gnuradio/greps/downloads","issues_url":"https://api.github.com/repos/gnuradio/greps/issues{/number}","pulls_url":"https://api.github.com/repos/gnuradio/greps/pulls{/number}","milestones_url":"https://api.github.com/repos/gnuradio/greps/milestones{/number}","notifications_url":"https://api.github.com/repos/gnuradio/greps/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/gnuradio/greps/labels{/name}","releases_url":"https://api.github.com/repos/gnuradio/greps/releases{/id}","deployments_url":"https://api.github.com/repos/gnuradio/greps/deployments","created_at":"2016-10-16T05:31:24Z","updated_at":"2018-03-17T16:33:58Z","pushed_at":"2018-03-18T22:37:40Z","git_url":"git://github.com/gnuradio/greps.git","ssh_url":"git@github.com:gnuradio/greps.git","clone_url":"https://github.com/gnuradio/greps.git","svn_url":"https://github.com/gnuradio/greps","homepage":null,"size":12,"stargazers_count":10,"watchers_count":10,"language":null,"has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":4,"mirror_url":null,"archived":false,"open_issues_count":7,"license":null,"forks":4,"open_issues":7,"watchers":10,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/gnuradio/greps/pulls/12"},"html":{"href":"https://github.com/gnuradio/greps/pull/12"},"issue":{"href":"https://api.github.com/repos/gnuradio/greps/issues/12"},"comments":{"href":"https://api.github.com/repos/gnuradio/greps/issues/12/comments"},"review_comments":{"href":"https://api.github.com/repos/gnuradio/greps/pulls/12/comments"},"review_comment":{"href":"https://api.github.com/repos/gnuradio/greps/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/gnuradio/greps/pulls/12/commits"},"statuses":{"href":"https://api.github.com/repos/gnuradio/greps/statuses/e1a75fb817159f3952f7d185c60288cf420aa83a"}},"author_association":"NONE"}}
{"actor":{"display_login":"mbr0wn"}}