Skip to content
New issue

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

Spawn a second spawner for parAlgos #36

Open
hugosenari opened this issue Aug 28, 2024 · 0 comments
Open

Spawn a second spawner for parAlgos #36

hugosenari opened this issue Aug 28, 2024 · 0 comments

Comments

@hugosenari
Copy link

I was thinking about optimizations for #35 using the following logic:

Serial is T = op * N or 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

proc parallel(list, op):
  for i in list:
    m.spawn op(i)
  • When our schedule cost is near to 0op: O(1op).
    ie. op takes 1s, spawn takes 1us is (to be precise is O(1op + 0.000.0001*nspawn)).
  • When our schedule cost is half op time: O(1op + 2/nspawn),
    ie. op takes 2us, spawn takes 1us
  • When our schedule cost is equal to op time: 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:

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant