1 /*
2 //@HEADER
3 // ************************************************************************
4 //
5 // Kokkos v. 3.0
6 // Copyright (2020) National Technology & Engineering
7 // Solutions of Sandia, LLC (NTESS).
8 //
9 // Under the terms of Contract DE-NA0003525 with NTESS,
10 // the U.S. Government retains certain rights in this software.
11 //
12 // Redistribution and use in source and binary forms, with or without
13 // modification, are permitted provided that the following conditions are
14 // met:
15 //
16 // 1. Redistributions of source code must retain the above copyright
17 // notice, this list of conditions and the following disclaimer.
18 //
19 // 2. Redistributions in binary form must reproduce the above copyright
20 // notice, this list of conditions and the following disclaimer in the
21 // documentation and/or other materials provided with the distribution.
22 //
23 // 3. Neither the name of the Corporation nor the names of the
24 // contributors may be used to endorse or promote products derived from
25 // this software without specific prior written permission.
26 //
27 // THIS SOFTWARE IS PROVIDED BY NTESS "AS IS" AND ANY
28 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
30 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL NTESS OR THE
31 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
32 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
33 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
34 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
35 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
36 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
37 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 //
39 // Questions? Contact Christian R. Trott (crtrott@sandia.gov)
40 //
41 // ************************************************************************
42 //@HEADER
43 */
44
45 #include <Kokkos_Core.hpp>
46
47 #if !defined(KOKKOS_ENABLE_TASKDAG) || \
48 defined(KOKKOS_ENABLE_DEFAULT_DEVICE_TYPE_THREADS)
49
main()50 int main() { return 0; }
51
52 #else
53
54 #include <cstdio>
55 #include <cstring>
56 #include <cstdlib>
57 #include <limits>
58
59 #include <impl/Kokkos_Timer.hpp>
60
61 using ExecSpace = Kokkos::DefaultExecutionSpace;
62
eval_fib(long n)63 inline long eval_fib(long n) {
64 constexpr long mask = 0x03;
65
66 long fib[4] = {0, 1, 0, 0};
67
68 for (long i = 2; i <= n; ++i) {
69 fib[i & mask] = fib[(i - 1) & mask] + fib[(i - 2) & mask];
70 }
71
72 return fib[n & mask];
73 }
74
fib_alloc_count(long n)75 inline long fib_alloc_count(long n) {
76 constexpr long mask = 0x03;
77
78 long count[4] = {1, 1, 0, 0};
79
80 for (long i = 2; i <= n; ++i) {
81 count[i & mask] = 2 // this task plus the 'when_all' task
82 + count[(i - 1) & mask] + count[(i - 2) & mask];
83 }
84
85 return count[n & mask];
86 }
87
88 template <class Scheduler>
89 struct TestFib {
90 using MemorySpace = typename Scheduler::memory_space;
91 using MemberType = typename Scheduler::member_type;
92 using FutureType = Kokkos::BasicFuture<long, Scheduler>;
93
94 using value_type = long;
95
96 FutureType dep[2];
97 const value_type n;
98
99 KOKKOS_INLINE_FUNCTION
TestFibTestFib100 TestFib(const value_type arg_n) : dep{}, n(arg_n) {}
101
102 KOKKOS_INLINE_FUNCTION
operator ()TestFib103 void operator()(MemberType& member, value_type& result) noexcept {
104 auto& sched = member.scheduler();
105 if (n < 2) {
106 result = n;
107 } else if (!dep[0].is_null() && !dep[1].is_null()) {
108 result = dep[0].get() + dep[1].get();
109 } else {
110 // Spawn new children and respawn myself to sum their results.
111 // Spawn lower value at higher priority as it has a shorter
112 // path to completion.
113
114 dep[1] = Kokkos::task_spawn(
115 Kokkos::TaskSingle(sched, Kokkos::TaskPriority::High),
116 TestFib(n - 2));
117
118 dep[0] = Kokkos::task_spawn(Kokkos::TaskSingle(sched), TestFib(n - 1));
119
120 auto fib_all = sched.when_all(dep, 2);
121
122 if (!dep[0].is_null() && !dep[1].is_null() && !fib_all.is_null()) {
123 // High priority to retire this branch.
124 Kokkos::respawn(this, fib_all, Kokkos::TaskPriority::High);
125 } else {
126 Kokkos::abort("Failed nested task spawn (allocation)");
127 }
128 }
129 }
130 };
131
main(int argc,char * argv[])132 int main(int argc, char* argv[]) {
133 static const char help[] = "--help";
134 static const char alloc_size[] = "--alloc_size=";
135 static const char super_size[] = "--super_size=";
136 static const char repeat_outer[] = "--repeat_outer=";
137 static const char input_value[] = "--input=";
138
139 long total_alloc_size = 1000000;
140 int min_superblock_size = 10000;
141 int test_repeat_outer = 1;
142 int fib_input = 4;
143
144 int ask_help = 0;
145
146 for (int i = 1; i < argc; i++) {
147 const char* const a = argv[i];
148
149 if (!strncmp(a, help, strlen(help))) ask_help = 1;
150
151 if (!strncmp(a, alloc_size, strlen(alloc_size)))
152 total_alloc_size = atol(a + strlen(alloc_size));
153
154 if (!strncmp(a, super_size, strlen(super_size)))
155 min_superblock_size = std::stoi(a + strlen(super_size));
156
157 if (!strncmp(a, repeat_outer, strlen(repeat_outer)))
158 test_repeat_outer = std::stoi(a + strlen(repeat_outer));
159
160 if (!strncmp(a, input_value, strlen(input_value)))
161 fib_input = std::stoi(a + strlen(input_value));
162 }
163
164 const long fib_output = eval_fib(fib_input);
165 const long number_alloc = fib_alloc_count(fib_input);
166
167 const unsigned min_block_size = 32;
168 const unsigned max_block_size = 128;
169
170 long task_count_max = 0;
171 long task_count_accum = 0;
172 long test_result = 0;
173
174 if (ask_help) {
175 std::cout << "command line options:"
176 << " " << help << " " << alloc_size << "##"
177 << " " << super_size << "##"
178 << " " << input_value << "##"
179 << " " << repeat_outer << "##" << std::endl;
180 return -1;
181 }
182
183 using Scheduler = Kokkos::TaskSchedulerMultiple<ExecSpace>;
184
185 using Functor = TestFib<Scheduler>;
186
187 Kokkos::initialize(argc, argv);
188
189 {
190 Scheduler sched(Functor::MemorySpace(), total_alloc_size, min_block_size,
191 max_block_size, min_superblock_size);
192
193 Functor::FutureType f =
194 Kokkos::host_spawn(Kokkos::TaskSingle(sched), Functor(fib_input));
195
196 Kokkos::wait(sched);
197
198 test_result = f.get();
199
200 // task_count_max = sched.allocated_task_count_max();
201 // task_count_accum = sched.allocated_task_count_accum();
202
203 // if ( number_alloc != task_count_accum ) {
204 // std::cout << " number_alloc( " << number_alloc << " )"
205 // << " != task_count_accum( " << task_count_accum << " )"
206 // << std::endl ;
207 //}
208
209 if (fib_output != test_result) {
210 std::cout << " answer( " << fib_output << " )"
211 << " != result( " << test_result << " )" << std::endl;
212 }
213
214 if (fib_output != test_result) { // || number_alloc != task_count_accum ) {
215 printf(" TEST FAILED\n");
216 return -1;
217 }
218
219 double min_time = std::numeric_limits<double>::max();
220 double time_sum = 0;
221
222 for (int i = 0; i < test_repeat_outer; ++i) {
223 Kokkos::Impl::Timer timer;
224
225 Functor::FutureType ftmp =
226 Kokkos::host_spawn(Kokkos::TaskSingle(sched), Functor(fib_input));
227
228 Kokkos::wait(sched);
229 auto this_time = timer.seconds();
230 min_time = std::min(min_time, this_time);
231 time_sum += this_time;
232 }
233
234 auto avg_time = time_sum / test_repeat_outer;
235
236 printf(
237 "\"taskdag: alloc super repeat input output task-accum task-max\" %ld "
238 "%d %d %d %ld %ld %ld\n",
239 total_alloc_size, min_superblock_size, test_repeat_outer, fib_input,
240 fib_output, task_count_accum, task_count_max);
241
242 printf("\"taskdag: time (min, avg)\" %g %g\n", min_time, avg_time);
243 printf("\"taskdag: tasks per second (max, avg)\" %g %g\n",
244 number_alloc / min_time, number_alloc / avg_time);
245 } // end scope to destroy scheduler prior to finalize
246
247 Kokkos::finalize();
248
249 return 0;
250 }
251
252 #endif
253