Can you divide up work by having each thread do one to four outer iterations between synchronization steps? If outer_size / chunk_size / threads is at least 4 or so (or maybe greater than the expected ratio between your shortest and longest inner arrays), scheduling of work is dynamic enough that you should usually avoid having one thread running for a long time on a very long array while the other threads have all finished.
(If a chunk size of 1 row aka inner array is coarse enough for efficiency, you can simply do that. You say that DoWork is so slow that even a shared counter for single elements might not be a problem)
That might still be a risk if the very last inner array is longer than the others. Depending on how common that is, and/or how important it is to avoid that worst-case scenario, you might look at the inner sizes ahead of time and sort or partition them to start working on the longest inner arrays first, so at the end the differences between threads finishing are the differences in lengths of the shorter arrays. (e.g. real-time where limiting the worst case is more important than speeding up the average, vs. a throughput-oriented use-case. Also if there's anything useful for other threads to be doing with free CPU cores if you don't schedule this perfectly.)
Atomically incrementing a shared counter for every inner element would serialize all threads on that, so unless processing each inner element was very expensive, it would be much slower than single-threaded without synchronization.
I'm assuming you don't need to start work on each element in sequential order, since even a shared counter wouldn't guarantee that (a thread could sleep after incrementing, with another thread starting the element after).
If you are going to search, start from your previous position.
If you do want to use a single shared counter, instead of linear searching from the start of the outer array every time, only search from your previous position. The shared counter is monotonically increasing, so the next position will usually be later this row, or into the very next. Should be more efficient to do that than to search from the start every time.
e.g. keep 3 variables: prev_index, and prev_i, prev_j. If j = prev_j + (index - prev_index) is still within the current array, you're done. This is likely the common case. Otherwise, move to the next row and recompute by subtracting arr[i].Length until you have a j that's in-bounds for that i.
Theodor Zoulias suggested pre-computing an array with a running total (aka prefix-sum) of the lengths. Good idea, but searching from the previous position probably makes that unnecessary, unless your rows are typically very short and you have lots of threads. In that case each step might involve multiple rows, so you could linear search from your previous position in a running-total array a bit more efficiently.
Per-row position counter: other threads can help finish a long row
If dividing work between threads only by rows isn't fine-grained enough, you could still mostly do that (with low contention), but create a way to threads to go back and help with unfinished long rows once there are no more fresh rows.
So you start as I proposed, with each thread claiming a whole row via a shared counter. When it gets to the end of a row, atomic fetch_add to get a new row to work on. Once you run out of fresh rows, threads can go back and look for arrays with arr[i].work_pos < arr[i].length.
Inside each row, you have a struct with the array itself (which records the length), and an atomic current-position counter, and another atomic counter for the number of threads currently working on this sub-array.
While working on an inner array, a thread atomically increments the position-within-array counter for that inner array, using that as the position of the next DoWork. So it's still a full memory barrier between every DoWork call (or unroll to claim 2 at a time and then do them), but contention is greatly reduced for most of the total run time because this will be the only thread incrementing that counter. (Until later threads jump in and start helping)
An atomic RMW on a cache line that stays hot in this core's L1d cache is much cheaper than an atomic RMW on a line when we have to request it from another core. So we want the per-row struct to be allocated separately, ideally contiguous with the row data like in C struct { _Atomic size_t work_pos; size_t len; atomic_int thread_active; struct work arr[]; }; with a "flexible array member" (so arbitrary-length array is contiguous with the end of the struct), or another level of indirection to just have a pointer/reference to an array.
Or if you can use the first 2 elements of an array of integers for this atomic bookkeeping, that also works. The outer array should be an array of references to these structs, not by value where multiple control blocks will share a cache line. False sharing would be about as bad as true sharing. And having pairs of threads contend with each other would be nearly as bad as all threads contending for the same single counter, if DoWork is slow enough that either way there's usually just one request for it in flight by one core.
Then the fun part comes at the end, when an Interlocked.Increment on the rowIndex returns an index past the end. Then that thread has to find an in-progress row to help with. Ideally this could be even distributed over still-working threads.
Perhaps we should have an array that records which row each thread is working on, with an entry for each thread? So threads looking for a place to help can scan through that and find the array with the highest work_left / threads_working. (That's why I suggested a thread-count member in the control block). Races in atomic stores of a pointer/reference to this array vs. readers reading one entry at a time aren't a problem; if an array was almost done, we wouldn't have wanted to pick it anyway, and we'll find somewhere useful to join.
If you naively just search backward from the end of the outer array, new threads will pile on to the last incomplete row, even if it's almost done, and create lots of contention for its atomic counters. But you also don't want to have to search over the whole outer array every time, if it could be large-ish. (If not, if rows are long but there aren't many of them, then that's fine.)
Reading the atomic work_pos counter that another thread is using will disturb that thread, as it loses exclusive ownership so its next Interlocked.Increment will be slower. So we'd like to avoid threads needing to find new rows to jump in on too frequently.
If we had a good heuristic for them to say that a row looks "good enough" and jump in immediately, instead of looking at all active / incomplete rows every time, that could reduce contention. But only if it's a good enough heuristic to make good choices.
Another way to reduce contention is to minimize how often a thread gets to the end of a row. Choosing the larger work_left / threads_working should achieve that, as that should be a decent approximation of which row will be completed last.
Multiple threads choosing at the same time might all pick the same row, but I don't think we can be perfect (or it would be too expensive). We can detect this when they use Interlocked.Increment to add themselves to the number of threads working on this row. Fallback to the second-longest estimated time row could be appropriate, or check if this is still the estimated-slowest row with the extra workers.
This doesn't have to be perfect; this is all just cleanup at the end of things, after running with minimal contention most of the time. As long as DoWork isn't too cheap relative to inter-thread latency, it's not a disaster if we sometimes have a bit more contention than was necessary.
Perhaps you'd also want some heuristic for a thread stopping itself before all the work is done could be useful, if there are other things a CPU core could be doing. (Or for this thread to be doing, in a pool of worker threads.)
