{"action":"created","issue":{"url":"https://api.github.com/repos/chapel-lang/chapel/issues/9542","repository_url":"https://api.github.com/repos/chapel-lang/chapel","labels_url":"https://api.github.com/repos/chapel-lang/chapel/issues/9542/labels{/name}","comments_url":"https://api.github.com/repos/chapel-lang/chapel/issues/9542/comments","events_url":"https://api.github.com/repos/chapel-lang/chapel/issues/9542/events","html_url":"https://github.com/chapel-lang/chapel/issues/9542","id":323332568,"node_id":"MDU6SXNzdWUzMjMzMzI1Njg=","number":9542,"title":"Design of User-Defined Reduction Interface","user":{"login":"vasslitvinov","id":8039635,"node_id":"MDQ6VXNlcjgwMzk2MzU=","avatar_url":"https://avatars0.githubusercontent.com/u/8039635?v=4","gravatar_id":"","url":"https://api.github.com/users/vasslitvinov","html_url":"https://github.com/vasslitvinov","followers_url":"https://api.github.com/users/vasslitvinov/followers","following_url":"https://api.github.com/users/vasslitvinov/following{/other_user}","gists_url":"https://api.github.com/users/vasslitvinov/gists{/gist_id}","starred_url":"https://api.github.com/users/vasslitvinov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vasslitvinov/subscriptions","organizations_url":"https://api.github.com/users/vasslitvinov/orgs","repos_url":"https://api.github.com/users/vasslitvinov/repos","events_url":"https://api.github.com/users/vasslitvinov/events{/privacy}","received_events_url":"https://api.github.com/users/vasslitvinov/received_events","type":"User","site_admin":false},"labels":[{"id":499565193,"node_id":"MDU6TGFiZWw0OTk1NjUxOTM=","url":"https://api.github.com/repos/chapel-lang/chapel/labels/area:%20Language","name":"area: Language","color":"d4c5f9","default":false},{"id":112762321,"node_id":"MDU6TGFiZWwxMTI3NjIzMjE=","url":"https://api.github.com/repos/chapel-lang/chapel/labels/type:%20Design","name":"type: Design","color":"e99695","default":false}],"state":"open","locked":false,"assignee":{"login":"vasslitvinov","id":8039635,"node_id":"MDQ6VXNlcjgwMzk2MzU=","avatar_url":"https://avatars0.githubusercontent.com/u/8039635?v=4","gravatar_id":"","url":"https://api.github.com/users/vasslitvinov","html_url":"https://github.com/vasslitvinov","followers_url":"https://api.github.com/users/vasslitvinov/followers","following_url":"https://api.github.com/users/vasslitvinov/following{/other_user}","gists_url":"https://api.github.com/users/vasslitvinov/gists{/gist_id}","starred_url":"https://api.github.com/users/vasslitvinov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vasslitvinov/subscriptions","organizations_url":"https://api.github.com/users/vasslitvinov/orgs","repos_url":"https://api.github.com/users/vasslitvinov/repos","events_url":"https://api.github.com/users/vasslitvinov/events{/privacy}","received_events_url":"https://api.github.com/users/vasslitvinov/received_events","type":"User","site_admin":false},"assignees":[{"login":"vasslitvinov","id":8039635,"node_id":"MDQ6VXNlcjgwMzk2MzU=","avatar_url":"https://avatars0.githubusercontent.com/u/8039635?v=4","gravatar_id":"","url":"https://api.github.com/users/vasslitvinov","html_url":"https://github.com/vasslitvinov","followers_url":"https://api.github.com/users/vasslitvinov/followers","following_url":"https://api.github.com/users/vasslitvinov/following{/other_user}","gists_url":"https://api.github.com/users/vasslitvinov/gists{/gist_id}","starred_url":"https://api.github.com/users/vasslitvinov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vasslitvinov/subscriptions","organizations_url":"https://api.github.com/users/vasslitvinov/orgs","repos_url":"https://api.github.com/users/vasslitvinov/repos","events_url":"https://api.github.com/users/vasslitvinov/events{/privacy}","received_events_url":"https://api.github.com/users/vasslitvinov/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/chapel-lang/chapel/milestones/18","html_url":"https://github.com/chapel-lang/chapel/milestone/18","labels_url":"https://api.github.com/repos/chapel-lang/chapel/milestones/18/labels","id":3349505,"node_id":"MDk6TWlsZXN0b25lMzM0OTUwNQ==","number":18,"title":"PB Sprint 6","description":"","creator":{"login":"benjamin-robbins","id":30993993,"node_id":"MDQ6VXNlcjMwOTkzOTkz","avatar_url":"https://avatars1.githubusercontent.com/u/30993993?v=4","gravatar_id":"","url":"https://api.github.com/users/benjamin-robbins","html_url":"https://github.com/benjamin-robbins","followers_url":"https://api.github.com/users/benjamin-robbins/followers","following_url":"https://api.github.com/users/benjamin-robbins/following{/other_user}","gists_url":"https://api.github.com/users/benjamin-robbins/gists{/gist_id}","starred_url":"https://api.github.com/users/benjamin-robbins/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/benjamin-robbins/subscriptions","organizations_url":"https://api.github.com/users/benjamin-robbins/orgs","repos_url":"https://api.github.com/users/benjamin-robbins/repos","events_url":"https://api.github.com/users/benjamin-robbins/events{/privacy}","received_events_url":"https://api.github.com/users/benjamin-robbins/received_events","type":"User","site_admin":false},"open_issues":4,"closed_issues":7,"state":"open","created_at":"2018-05-15T17:54:31Z","updated_at":"2018-06-01T05:29:44Z","due_on":"2018-05-29T07:00:00Z","closed_at":null},"comments":8,"created_at":"2018-05-15T18:29:18Z","updated_at":"2018-06-01T18:33:54Z","closed_at":null,"author_association":"MEMBER","body":"Previous work on User-Defined Reduction Interface aka UDRI is here: #5248  #5470 .\r\n\r\nThe current proposal differs in accounting for the needs of a partial reduction.\r\nIt puts synchronization in the reduce op rather than in accumulation state,\r\nretains `identity()`, and offers simpler interface methods.\r\n\r\nKey decisions:\r\n\r\n* ReduceOp is a record, not a class.\r\n\r\nRationale: avoids malloc+free in the common case\r\nwhen class functionality is not needed and a record suffices.\r\n\r\n* Accumulation state (AS) is outside the ReduceOp record.\r\nThe AS variables are managed by the compiler.\r\nThe initial value for AS is given by ReduceOp.identity().\r\n\r\nThe alternative is to embed AS in the ReduceOp record.\r\nIf so, the compiler would access AS by creating, for example:\r\n`ref AS = currentReduceOp.refToAccumState();` .\r\n\r\nIn both cases, AS is what the reduce-intent shadow variable\r\nrepresents in the forall loop body. It does not include any\r\nsupport for synchronization. Background: synchronization is needed\r\nto avoid data races when multiple child tasks may be combine()-ing\r\ntheir results into the parent task's AS.\r\n\r\nRationale: \"AS outside ReduceOp\" simplifies the setup for partial\r\nreductions. For example, if AS is `real`, it is easier to initialize\r\nand bulk-transfer an array of reals than an array of records\r\nthat contain a single real field.\r\n\r\nThe downsides of this choice are:\r\n- More arguments for the interface functions. Because now we need\r\nto pass the reduce op and the AS separately.\r\n- Perhaps a loss of generality. The initial value given by identity()\r\ndoes not know about the parent ReduceOp and the parent AS.\r\nAlso, initialization and deinitialization of the AS and the reduce op\r\nare forced to occur separately, ex. in two separate deinit() methods\r\ninstead of one deinit().\r\n\r\nIf needed in the future, we can add support for the \"AS is in ReduceOp\"\r\nstyle, for example, by detecting whether ReduceOp.refToAccumState()\r\nis available.\r\n\r\nAlso if needed in the future, within the \"AS separate from ReduceOp\"\r\nsetup, we can add support for an alternative to identity()\r\nthat accepts the parent ReduceOp/AS or the outer variable, as in #5470.\r\n\r\n* Allow the optimization where the outer variable and the global AS\r\nare the same variable. This requires that AS type and the output type\r\nare the same. If so, the initialization of globalAS and the call\r\nto initialAccumulate should be skipped.\r\n\r\n* ReduceOp is to support two modes: with synchronization and without\r\nsynchronization.\r\n\r\nThe first mode is for use with full reductions and\r\nreduce intents. ReduceOp must include the needed state.\r\n\r\nThe second mode is for partial reductions. There, a single ReduceOp\r\nmay be shared among multiple AS-s performing independent full reductions.\r\nChapel implementation will provide synchronization outside ReduceOp.\r\n\r\nHere is the proposed interface.\r\n\r\n```chpl\r\n\r\nrecord ReduceOp {    // user to choose the name\r\n\r\n  // fields or type/param procs\r\n  type InputType\r\n  proc AccumType\r\n  proc OutputType\r\n  param parSafe\r\n  // ReduceOp to provide synchronization when parSafe=true.\r\n\r\n  // Create the global reduce op.\r\n  proc init(type InputType, param parSafe)\r\n\r\n  // Given a parent reduce op and AS, create a child reduce op.\r\n  proc newLocalOp(parentAS, param parSafe)\r\n\r\n  // \"zero\" value for the reduction\r\n  proc identity() : AccumType\r\n\r\n  // Add 'input' onto 'AS'.\r\n  // Synchronization is not required.\r\n  proc accumulate(ref AS: AccumType, input) \r\n\r\n  // Accumulate the initial value of the outer variable,\r\n  // in the case of a reduce intent.\r\n  // Synchronization is not required.\r\n  // If this is not defined, accumulate() will be invoked instead.\r\n  proc initialAccumulate(ref AS: AccumType, ovar) \r\n\r\n  // Combine the child's AS onto the parent's.\r\n  // Must synchronize to avoid data races on parentAS when parSafe=true.\r\n  proc combine(ref parentAS, ref childOp, ref childAS)\r\n\r\n  // Produce the reduction result given the global AS.\r\n  proc generate(ref AS) \r\n\r\n  // Note: exactly one of the following methods will be invoked prior to\r\n  // deinitializing an AS: combineNoSync(), combine(), generate().\r\n\r\n}\r\n\r\n```\r\n\r\nAs an extension, we could allow ReduceOp, instead of defining `combine`,\r\nto define the following:\r\n\r\n```chpl\r\n  // Combine the child's AS onto the parent's.\r\n  // Synchronization is responsibility of the caller.\r\n  proc combineNoSync(ref parentAS, ref childOp, ref childAS)\r\n\r\n  // Lock/unlock accesses to this op and its AS, when parSafe=true.\r\n  // User to provide necessary state ex. a field.\r\n  proc lock()\r\n  proc unlock()\r\n```\r\n\r\nSo that the compiler will invoke combineNoSync or\r\nlock+combineNoSync+unlock, depending on parSafe.\r\n\r\nWe can also provide a helper record in the modules:\r\n\r\n```chpl\r\n  record ReduceLock {\r\n    private var l: atomicbool;\r\n    proc lock() { ... } // see ChapelReduce.chpl\r\n    proc unlock() { l.clear(); }\r\n  }\r\n```\r\n\r\nSo the lock+unlock requirements are satisfied simply\r\nby declaring this in ReduceOp:\r\n\r\n```chpl\r\n  // defines lock(), unlock()\r\n  forwarding var locker: ReduceLock;\r\n```"},"comment":{"url":"https://api.github.com/repos/chapel-lang/chapel/issues/comments/393971538","html_url":"https://github.com/chapel-lang/chapel/issues/9542#issuecomment-393971538","issue_url":"https://api.github.com/repos/chapel-lang/chapel/issues/9542","id":393971538,"node_id":"MDEyOklzc3VlQ29tbWVudDM5Mzk3MTUzOA==","user":{"login":"vasslitvinov","id":8039635,"node_id":"MDQ6VXNlcjgwMzk2MzU=","avatar_url":"https://avatars0.githubusercontent.com/u/8039635?v=4","gravatar_id":"","url":"https://api.github.com/users/vasslitvinov","html_url":"https://github.com/vasslitvinov","followers_url":"https://api.github.com/users/vasslitvinov/followers","following_url":"https://api.github.com/users/vasslitvinov/following{/other_user}","gists_url":"https://api.github.com/users/vasslitvinov/gists{/gist_id}","starred_url":"https://api.github.com/users/vasslitvinov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/vasslitvinov/subscriptions","organizations_url":"https://api.github.com/users/vasslitvinov/orgs","repos_url":"https://api.github.com/users/vasslitvinov/repos","events_url":"https://api.github.com/users/vasslitvinov/events{/privacy}","received_events_url":"https://api.github.com/users/vasslitvinov/received_events","type":"User","site_admin":false},"created_at":"2018-06-01T18:33:54Z","updated_at":"2018-06-01T18:33:54Z","author_association":"MEMBER","body":"One thing that jumps at me is that the ReduceOp author may want to distinguish per-locale state vs. per-task state. In the spirit of per-locale vs. per-task task-private variables."}}
{"actor":{"display_login":"vasslitvinov"}}