0

I'm wondering, in general, if a part of a program can be safely parallelized with significant performance gains, should we? Or do we need consider the importance of this work because it can affect scalability. What is your thought process when deciding to parallelize something?

For example, in my application, users are able to submit a graph data structure to our server side for processing. Each node can be processed independently in parallel and is non-blocking IO Work. Users will on average submit 3-4 nodes, but it could be up to 100. On average a node takes about a second to process. This is a high-traffic area but performance is not critical in that the user needs a response right away.

Parallelization in this case can speed it up dramatically. But my concern is because it is high traffic and there can be many nodes, it could potentially hog a lot of resources, slowing down other areas. But I've also heard an argument that it should be parallelized anyway because the OS is smart enough to the manage all the threads and scheduling.

Would you parallelize the scenario above? Would your answer change if the work became IO blocking work?

1
  • 2
    There are two ways for dealing with performance questions: (1) ask strangers on the internet about your requirements and let them guess what may happen in your system when you optimize certain parts of it. (2) analyse your specific performance requirements, identify bottlenecks by measuring and try out what helps in your system. Now guess which approach will be more successful.
    – Doc Brown
    Commented Dec 11, 2019 at 7:21

2 Answers 2

1

The main reason not to parallelize could be the added complexity and risks, especially for algorithm that expect sequentiality by design.

Take for example the A* path-finding algorithm for graphs: parallelizing it from a technical perspective is not too difficult: just use several threads to expand the paths in the queue ASAP in parallel: it works technically, but depending on a lot of factors, you might no longer find the shortest path first, or you might even process a lot more of additional suboptimal paths, not really benefiting from the parallelization.

It seems that such issues are not relevant for your problem. So, you could think about parallelization without major concerns.

The approach would consider the following aspects:

  • the extra threads/processes might consume extra resources, so there is a balance to be found about the number of active threads
  • the launch of an extra thread/process requires some overhead. So instead of launching them ad-hoc, you may want to use a thread-pool.
  • If the ratio active_threads/waiting_thread exceeds in average the multicore capacity, the extra threads will be put on hold, decreasing the benefit of parralelism. However, in your case, with a lot of threads waiting for IO, this should not be an issue.
  • On a multicore CPU, practical experiments show for example that distributing an algorithm on several cores, make each core slightly slower (individual throughput decreased) whereas the many cores process more (collective throughput higher).

Therefore, you’ll probably not launch an extra thread or process on-the-fly for each graph node to be processed. You may rather want:

  • to enqueue the nodes to be processed as they come;
  • to have working threads (aka “workers”) take nodes from the queue and process them in parallel
  • to use a thread pool of ready to run threads

This is scalable: you could decouple the enqueuing from the processing, add mor workers, add more queues and more workers if the thing becomes very huge.

But before reengineering your system, I’d advise to cross-check the assumption of independent processing. As the A* example shows: the relative independence of individual tasks might hide some hidden/emerging interdependence at the graph level.

0

Yes, by all means parallelise.

This is the golden scenario. The work is independent of all the other pieces and has no temporal dependencies.

If you are worried about hogging, you can limit throughput in a number of ways.

  • Queue the work, just because it can happen in parallel doesn't mean it must happen now.
  • Restrict the total number of workers. It won't be worked on unless someone is there to pick it up.
  • Lower the priority of node workers relative to other workers so that they can not out compete higher priority tasks.

IO complicates matters, but you can handle it be ensuring that IO is handled asynchronously.

When a blocking IO call is to be made, place the task on bucket representing blocked by IO and then make the IO call asynchronously.

When the IO completes the task is moved back to the ready to process queue (or is processed on the spot by workers waiting for IO completion).

If there are multiple points at which IO occurs, task progress will be harder to understand. Try using a state machine with either the task being the state machine, or with the tasks representing states and the IO waits representing transitions.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.