multithreading - Parallel processing - Connected Data -

problem

summary: parallely apply function f each element of array f not thread safe.

i have set of elements e process, lets queue of them. want process these elements in parallel using same function f( e ).

now, ideally call map based parallel pattern, problem has following constraints.

• each element contains pair of 2 objects.( e = (a,b) )
• two elements may share object. ( e1 = (a1,b1); e2 = (a1, b2) )
• the function f cannot process 2 elements share object. e1 , e2 cannot processing in parallel.

what right way of doing this?

my thoughts so,

1. trivial thought: keep set of active , bs, , start processing element when no other thread using or b.
   • so, when give element thread add , bs active set.
   • pick first element, if elements not in active set spawn new thread , otherwise push of queue of elements.
   • do till queue empty.
   • will cause deadlock ? ideally when processing on elements become available right?

2.-the other thought make graph of these connected objects. each node represents object (a / b) . each element edge connecting & b, , somehow process data such know elements never overlapping.

questions

• how can achieve best?
• is there standard pattern ?
• is there problem these approaches?
• not necessary, if tell tbb methods use, that'll great.

the "best" approach depends on lot of factors here:

1. how many elements "e" have , how work needed f(e). --> check if it's worth work elements in parallel (if need lot of locking , don't have work do, you'll slow down process working in parallel)
2. is there possibility change design can make f(e) multi-threading safe?
3. how many elements "a" , "b" there? there logic elements "e" share specific versions of , b? --> if can sort elements e separate lists each , b appears in single list, can process these lists parallel without further locking.
4. if there many different a's , b's , don't share many of them, may want trivial approach lock each "a" , "b" when entering , wait until lock.

whenever "lock , wait" multiple locks it's important take locks in same order (e.g. first , b second) because otherwise may run deadlocks. locking order needs observed everywhere (a single place in whole application uses different order can cause deadlock)

edit: if "try lock" need ensure order same. otherwise can cause lifelock:

1. thread 1 locks a
2. thread 2 locks b
3. thread 1 tries lock b , fails
4. thread 2 tries lock , fails
5. thread 1 releases lock a
6. thread 2 releases lock b
7. goto 1 , repeat...

chances happens "endless" relatively slim, should avoided anyway

edit 2: principally guess i'd split e(ax, bx) different lists based on ax (e.g 1 list e's share same a). process these lists in parallel locking of "b" (there can still "trylock" , continue if required b used.