Implementing Awkward CUDA Kernels

[ManasviGoyal]

These are the 88(+13)/147 CUDA kernels that need to be implemented.

1. awkward_ByteMaskedArray_numnull
2. awkward_ByteMaskedArray_reduce_next_nonlocal_nextshifts_fromshifts_64
3. awkward_Index_nones_as_index
4. awkward_IndexedArray_fill
5. awkward_IndexedArray_flatten_none2empty
6. awkward_IndexedArray_index_of_nulls
7. awkward_IndexedArray_local_preparenext_64 (A)
8. awkward_IndexedArray_numnull
9. awkward_IndexedArray_numnull_parents
10. awkward_IndexedArray_numnull_unique
11. awkward_IndexedArray_ranges_carry_next_64
12. awkward_IndexedArray_ranges_next_64
13. awkward_IndexedArray_unique_next_index_and_offsets_64 (A)
14. awkward_ListArray_broadcast_tooffsets
15. awkward_ListArray_combinations (B)
16. awkward_ListArray_combinations_length
17. awkward_ListArray_fill
18. awkward_ListArray_getitem_jagged_apply
19. awkward_ListArray_getitem_jagged_carrylen
20. awkward_ListArray_getitem_jagged_descend
21. awkward_ListArray_getitem_jagged_numvalid
22. awkward_ListArray_getitem_jagged_shrink
23. awkward_ListArray_getitem_next_array_advanced
24. awkward_ListArray_getitem_next_at
25. awkward_ListArray_getitem_next_range (C)
26. awkward_ListArray_getitem_next_range_carrylength (C)
27. awkward_ListArray_getitem_next_range_counts
28. awkward_ListArray_getitem_next_range_spreadadvanced
29. awkward_ListArray_localindex
30. awkward_ListArray_min_range
31. awkward_ListArray_rpad_and_clip_length_axis1
32. awkward_ListArray_rpad_axis1
33. awkward_ListOffsetArray_argsort_strings
34. awkward_ListOffsetArray_drop_none_indexes
35. awkward_ListOffsetArray_local_preparenext_64
36. awkward_ListOffsetArray_reduce_local_nextparents_64
37. awkward_ListOffsetArray_reduce_local_outoffsets_64
38. awkward_ListOffsetArray_reduce_nonlocal_maxcount_offsetscopy_64
39. awkward_ListOffsetArray_reduce_nonlocal_nextshifts_64
40. awkward_ListOffsetArray_reduce_nonlocal_nextstarts_64
41. awkward_ListOffsetArray_reduce_nonlocal_outstartsstops_64
42. awkward_ListOffsetArray_reduce_nonlocal_preparenext_64
43. awkward_ListOffsetArray_rpad_length_axis1
44. awkward_ListOffsetArray_toRegularArray
45. awkward_NumpyArray_fill
46. awkward_NumpyArray_pad_zero_to_length
47. awkward_NumpyArray_prepare_utf8_to_utf32_padded
48. awkward_NumpyArray_rearrange_shifted
49. awkward_NumpyArray_sort_asstrings_uint8
50. awkward_NumpyArray_subrange_equal
51. awkward_NumpyArray_unique_strings_uint8
52. awkward_NumpyArray_utf8_to_utf32_padded
53. awkward_RecordArray_reduce_nonlocal_outoffsets_64
54. awkward_RegularArray_combinations (B)
55. awkward_RegularArray_getitem_next_array_regularize
56. awkward_RegularArray_reduce_local_nextparents_64
57. awkward_RegularArray_reduce_nonlocal_preparenext_64
58. awkward_RegularArray_rpad_and_clip_axis1
59. awkward_UnionArray_fillindex
60. awkward_UnionArray_fillindex_count
61. awkward_UnionArray_filltags
62. awkward_UnionArray_filltags_const
63. awkward_UnionArray_flatten_combine (B)
64. awkward_UnionArray_flatten_length (B)
65. awkward_UnionArray_nestedfill_tags_index (overlapping start and stops cause race condition)
66. awkward_UnionArray_regular_index
67. awkward_UnionArray_regular_index_getsize
68. awkward_UnionArray_simplify
69. awkward_UnionArray_simplify_one
70. awkward_argsort
71. awkward_index_rpad_and_clip_axis0
72. awkward_reduce_argmax_complex
73. awkward_reduce_argmin_complex
74. awkward_reduce_countnonzero_complex
75. awkward_reduce_max_complex
76. awkward_reduce_min_complex
77. awkward_reduce_prod
78. awkward_reduce_prod_bool_complex
79. awkward_reduce_prod_complex
80. awkward_reduce_sum_bool_complex
81. awkward_reduce_sum_complex
82. awkward_sort
83. awkward_sorting_ranges
84. awkward_sorting_ranges_length
85. awkward_unique (A)
86. awkward_unique_copy (A)
87. awkward_unique_offsets (A)
88. awkward_unique_ranges (A)

(A) if condition uses the counter to update the counters
(B) one of the argument is of double pointer type
(C) kernel calls another function

Also, the following 13 kernels that use atomicAdd() need to be reimplemented.

89. awkward_reduce_argmax.cu
90. awkward_reduce_argmax_bool_64.cu
91. awkward_reduce_argmin.cu
92. awkward_reduce_argmin_bool_64.cu
93. awkward_reduce_count_64.cu
94. awkward_reduce_countnonzero.cu
95. awkward_reduce_max.cu
96. awkward_reduce_min.cu
97. awkward_reduce_prod_bool.cu
98. awkward_reduce_sum.cu
99. awkward_reduce_sum_bool.cu
100. awkward_reduce_sum_int32_bool_64.cu
101. awkward_reduce_sum_int64_bool_64.cu

[ManasviGoyal]

The following reducers kernels can be implemented by using a modified Hillis Steele algorithm. see implemntation of cupy.cumsum

1. awkward_reduce_argmax.cu
2. awkward_reduce_argmax_bool_64.cu
3. awkward_reduce_argmin.cu
4. awkward_reduce_argmin_bool_64.cu
5. awkward_reduce_count_64.cu
6. awkward_reduce_countnonzero.cu
7. awkward_reduce_max.cu
8. awkward_reduce_min.cu
9. awkward_reduce_prod_bool.cu
10. awkward_reduce_sum.cu
11. awkward_reduce_sum_bool.cu
12. awkward_reduce_sum_int32_bool_64.cu
13. awkward_reduce_sum_int64_bool_64.cu
14. awkward_reduce_argmax_complex
15. awkward_reduce_argmin_complex
16. awkward_reduce_countnonzero_complex
17. awkward_reduce_max_complex
18. awkward_reduce_min_complex
19. awkward_reduce_prod
20. awkward_reduce_prod_bool_complex
21. awkward_reduce_prod_complex
22. awkward_reduce_sum_bool_complex
23. awkward_reduce_sum_complex
24. awkward_UnionArray_regular_index