Reduce by Key Worklet Type
Added a Reduce By Key worklet type. This is a very helpful type of worklet that lets you gather associated values. It typically follows a parallel operation where several threads produce values that are coincident or otherwise have to be gathered together.
Merge request reports
Activity
added 41 commits
-
81a8e919...f0413c48 - 35 commits from branch
vtk:master - f5f917b6 - Add Keys class
- b78ca64d - Add WorkletReduceByKey and dispatcher
- 8e0d5e44 - Add Value[In][Out] tags for WorkletReduceByKey
- 2c3a2129 - Add ValueCount tag to WorkletReduceByKey
- 32789281 - Add ReducedValues[In][Out] tags to WorkletReduceByKey
- 025bbf6e - Remove static assert from templated function
Toggle commit list-
81a8e919...f0413c48 - 35 commits from branch
added 8 commits
- 4d1da547 - Fix ArrayHandleZip::PrepareForInPlace
- cd64b69a - Add Keys class
- 58eb8f16 - Add WorkletReduceByKey and dispatcher
- add10f56 - Add Value[In][Out] tags for WorkletReduceByKey
- ffa3b167 - Add ValueCount tag to WorkletReduceByKey
- 72b85559 - Add ReducedValues[In][Out] tags to WorkletReduceByKey
- 05843985 - Remove static assert from templated function
- d6eb477a - Minor fixes to UnitTestWorkletReduceByKey
Toggle commit list@robertmaynard Thus MR introduces a reduce by key worklet. It should help with a lot of operations that find related or coincident data.
vtkm/worklet/Keys.h 0 → 10064479 } 80 81 VTKM_CONT 82 vtkm::Id GetInputRange() const 83 { 84 return this->UniqueKeys.GetNumberOfValues(); 85 } 86 87 VTKM_CONT 88 KeyArrayHandleType GetUniqueKeys() const 89 { 90 return this->UniqueKeys; 91 } 92 93 VTKM_CONT 94 vtkm::cont::ArrayHandle<vtkm::Id> GetSortedValuesMap() const No.
SortedValuesMapis very different from the unique keys.SortedValuesMapallows you to take an index in the sorted keys and find the corresponding value.Typically in a reduce-by-key, you do a
SortByKeyusing the keys and values. However, in the worklet you can have an arbitrary number of values that you want to reduce, and it would be inefficient to do aSortByKeyfor all of them. So instead we shuffle the indices and do a lookup of which value would have been sorted to there.
- vtkm/worklet/Keys.h 0 → 100644
91 } 92 93 VTKM_CONT 94 vtkm::cont::ArrayHandle<vtkm::Id> GetSortedValuesMap() const 95 { 96 return this->SortedValuesMap; 97 } 98 99 VTKM_CONT 100 vtkm::cont::ArrayHandle<vtkm::Id> GetOffsets() const 101 { 102 return this->Offsets; 103 } 104 105 VTKM_CONT 106 vtkm::cont::ArrayHandle<vtkm::IdComponent> GetCounts() const I think I was considering it, but it seemed like a hassle. You have to carry around the size of the values array and do a special case at the end of the array. Considering that you would have to do this not in the
Keysclass but somewhere in the fetch mechanism, it seemed more trouble than it was worth (at least initially).This has not been the first time this has come up. It happens in the scatter counting class as well. Actually, it even happens in the explicit cell set. If we want to worry about sharing offset/count arrays, we should probably have helper classes and/or fancy arrays to manage that.
- vtkm/worklet/Keys.h 0 → 100644
55 /// needed to use the keys. 56 /// 57 /// The same \c Keys structure can be used for multiple different \c Invoke of 58 /// different dispatchers. When used in this way, the processing done in the \c 59 /// Keys structure is reused for all the \c Invoke. This is more efficient than 60 /// creating a different \c Keys structure for each \c Invoke. 61 /// 62 template<typename _KeyType> 63 class Keys 64 { 65 public: 66 using KeyType = _KeyType; 67 using KeyArrayHandleType = vtkm::cont::ArrayHandle<KeyType>; 68 69 VTKM_CONT 70 Keys() I don't think that will work because you still need to create the
SortedValuesMap.For what it's worth, the whole point of having the
Keysclass is to mange and reuse sorted/unique keys and the value map so you can apply it to multiple worklet invocations. I'm not sure why you would want to sort a keys array except for operations that you use theKeysclass for anyway.
@robertmaynard Did you have any other questions about these changes?
@robertmaynard The automatic merge failed. Should I click the button instead?
-
@kmorel yes
mentioned in commit 28b86692
