1 | // Copyright 2019 The Marl Authors. |
2 | // |
3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
4 | // you may not use this file except in compliance with the License. |
5 | // You may obtain a copy of the License at |
6 | // |
7 | // https://www.apache.org/licenses/LICENSE-2.0 |
8 | // |
9 | // Unless required by applicable law or agreed to in writing, software |
10 | // distributed under the License is distributed on an "AS IS" BASIS, |
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | // See the License for the specific language governing permissions and |
13 | // limitations under the License. |
14 | |
15 | // This is an example application that uses Marl to find and print all the prime |
16 | // numbers in the range 1 to 10000000. |
17 | |
18 | #include "marl/defer.h" |
19 | #include "marl/scheduler.h" |
20 | #include "marl/thread.h" |
21 | #include "marl/ticket.h" |
22 | |
23 | #include <vector> |
24 | |
25 | #include <math.h> |
26 | |
27 | // searchMax defines the upper limit on primes to find. |
28 | constexpr int searchMax = 10000000; |
29 | |
30 | // searchChunkSize is the number of numbers searched, per task, for primes. |
31 | constexpr int searchChunkSize = 10000; |
32 | |
33 | // isPrime returns true if i is prime. |
34 | bool isPrime(int i) { |
35 | auto c = static_cast<int>(sqrt(i)); |
36 | for (int j = 2; j <= c; j++) { |
37 | if (i % j == 0) { |
38 | return false; |
39 | } |
40 | } |
41 | return true; |
42 | } |
43 | |
44 | int main() { |
45 | // Create a marl scheduler using the full number of logical cpus. |
46 | // Bind this scheduler to the main thread so we can call marl::schedule() |
47 | marl::Scheduler scheduler(marl::Scheduler::Config::allCores()); |
48 | scheduler.bind(); |
49 | defer(scheduler.unbind()); // unbind before destructing the scheduler. |
50 | |
51 | // Create a ticket queue. This will be used to ensure that the primes are |
52 | // printed in ascending order. |
53 | marl::Ticket::Queue queue; |
54 | |
55 | // Iterate over the range [1, searchMax] in steps of searchChunkSize. |
56 | for (int searchBase = 1; searchBase <= searchMax; |
57 | searchBase += searchChunkSize) { |
58 | // Take a ticket from the ticket queue for this task. |
59 | auto ticket = queue.take(); |
60 | |
61 | // Schedule the task. |
62 | marl::schedule([=] { |
63 | // Find all the primes in [searchBase, searchBase+searchChunkSize-1]. |
64 | // Note this is run in parallel with the other scheduled tasks. |
65 | std::vector<int> primes; |
66 | for (int i = searchBase; i < searchBase + searchChunkSize; i++) { |
67 | if (isPrime(i)) { |
68 | primes.push_back(i); |
69 | } |
70 | } |
71 | |
72 | // Wait until the ticket is called. This ensures that the primes are |
73 | // printed in ascending order. This may cause this task to yield and allow |
74 | // other tasks to be executed while waiting for this ticket to be called. |
75 | ticket.wait(); |
76 | |
77 | // Print the primes. |
78 | for (auto prime : primes) { |
79 | printf("%d is prime\n" , prime); |
80 | } |
81 | |
82 | // Call the next ticket so that those primes can be printed. |
83 | ticket.done(); |
84 | }); |
85 | } |
86 | |
87 | // take a ticket and wait on it to ensure that all the primes have been |
88 | // calculated and printed. |
89 | queue.take().wait(); |
90 | |
91 | return 0; |
92 | } |
93 | |