Parallelizing a for loop

Question

I have a for loop where the computation at iteration i does not depend on the computations done in the previous iterations.

I want to parallelize the for loop(my code is in java) so that the computation of multiple iterations can be run concurrently on multiple processors. Should I create a thread for the computation of each iteration, i.e. number of threads to be created is equal to the number of iterations(number of iterations are large in the for loop)? How to do this?

Answer 1

Here's a small example that you might find helpful to get started with parallelization. It assumes that:

1. You create an Input object that contains the input for each iteration of your computation.
2. You create an Output object that contains the output from computing the input of each iteration.
3. You want to pass in a list of inputs and get back a list of outputs all at once.
4. Your input is a reasonable chunk of work to do, so overhead isn't too high.

If your computation is really simple then you'll probably want to consider processing them in batches. You could do that by putting say 100 in each input. It uses as many threads as there are processors in your system. If you're dealing with purely CPU intensive tasks then that's probably the number you want. You'd want to go higher if they're blocked waiting for something else (disk, network, database, etc.)

public List<Output> processInputs(List<Input> inputs)         throws InterruptedException, ExecutionException {      int threads = Runtime.getRuntime().availableProcessors();     ExecutorService service = Executors.newFixedThreadPool(threads);      List<Future<Output>> futures = new ArrayList<Future<Output>>();     for (final Input input : inputs) {         Callable<Output> callable = new Callable<Output>() {             public Output call() throws Exception {                 Output output = new Output();                 // process your input here and compute the output                 return output;             }         };         futures.add(service.submit(callable));     }      service.shutdown();      List<Output> outputs = new ArrayList<Output>();     for (Future<Output> future : futures) {         outputs.add(future.get());     }     return outputs; }