We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
I was thinking about optimizations for #35 using the following logic:
Serial is T = op * N or O(nop)
T = op * N
O(nop)
proc serial(list, op): for i in list: op(i)
Parallel is T = op + schedule * N or O(1op + nspawn) limited by available threads
T = op + schedule * N
O(1op + nspawn)
proc parallel(list, op): for i in list: m.spawn op(i)
O(1op)
O(1op + 0.000.0001*nspawn)
O(1op + 2/nspawn)
But, algorithms like README example (depth-first search) are more like O(1op + (n log nspawn))
O(1op + (n log nspawn))
Maybe parAlgos could have similar approach of DFS:
proc recursiveParallel(list, bulksize, op): if list.len == 0: return let (head, tail) = list.take(bulksize) m.spawn serial(head, op) for part in tail.take(tail.len / 2) m.spawn recursiveParallel(part, bulksize, op)
Or because previous algorithm will make pool busy of scheduling instead of busy of working, two scheduling threads is enough.
O(1op + 1spawn + 2/nspawn)
proc parAlgo(list, bulksize, op): for slice in list.split(bulksize): m.spawn serial(slice, op) proc parParAlgo(list, bulksize, op): let (l,r) = tail.take(tail.len / 2) m.spawn parAlgo(l, bulkSize, op) m.spawn parAlgo(r, bulkSize, op) # ¹
¹ second call to parAlgo should be made without m.spawn, but is there for readability.
parAlgo
m.spawn
The text was updated successfully, but these errors were encountered:
No branches or pull requests
I was thinking about optimizations for #35 using the following logic:
Serial is
T = op * N
orO(nop)
Parallel is
T = op + schedule * N
orO(1op + nspawn)
limited by available threadsO(1op)
.ie. op takes 1s, spawn takes 1us is (to be precise is
O(1op + 0.000.0001*nspawn)
).O(1op + 2/nspawn)
,ie. op takes 2us, spawn takes 1us
O(1op + nspawn)
,ie. op takes 1us, spawn takes 1us
But, algorithms like README example (depth-first search) are more like
O(1op + (n log nspawn))
Maybe parAlgos could have similar approach of DFS:
Or because previous algorithm will make pool busy of scheduling instead of busy of working, two scheduling threads is enough.
O(1op + 1spawn + 2/nspawn)
¹ second call to
parAlgo
should be made withoutm.spawn
, but is there for readability.The text was updated successfully, but these errors were encountered: