Of threads which run in parallel

The current set of laptops come with huge amount of computational resources. Quad-core they say, but you'd often not have applications which utilize it, they never say!

This is my take on trying to do simple stuff in parallel, trying to utilize the in-built support languages like Java have for parallelism.

A multi-threaded program contains two or more parts that can run concurrently. Each part of such a program is called a thread and runs independently.

Let's try to build a simple program which would sum the numbers in a parallel way.

for( int i=0 ; i &lt; 2000000 ; i++ ){  
              numbers[i] = i+2;  
          }

A Simple for-loop like this would run for 2000000 iterations and hence take time proportional to this number. If we recognize that the execution of the ith iteration does not depend on any of the executions of the previous (i-1) iterations, this paves the way for parallelizing the code.

Java supports Parallel execution of code using things called threads. It tends to be messy to use threads directly and hence it makes sense to use a particular interface provided by Java for running a bunch of threads which are supposed to run certain tasks asynchronously, called Executor Service. It basically takes certain class objects as inputs, specifically those which implement the Runnable or the Callable interface.
These objects have special methods either run() or call(), respectively, which start executing as soon as a thread is created by the executor service which is supposed to 'run' then.

Whenever you Submit() a particular object of a runnable/callable class to this service, (think of submitting a task as asking the executor service to be ready to 'service' the task when we stop taking submissions), the action(that is the call to submit method) returns an object of interface Future, which essentially allows you to monitor the status of execution of that particular thread.

The difference between using a class object which implements Runnable and Callable interfaces is that the run() method doesn't return anything, whereas the call method ( which has to be defined by a class which implements the Callable interface) returns an Object(Callable interface can take parameters and hence is generic in that sense, it can thus return objects of any type!) , and Future helps us in keeping track of that Object.

Here is the code for the problem of summing numbers in a parallel manner. number at index i(mod4) is summed by executorservice Thread number i(mod4), and hence elements 0,4,8,16.. are summed by thread 0 and so on.
I've also included timing details so that we can check how exactly the threads run, if at all there is a happensbefore relation anywhere. ( For example, the numbers are set randomly before we start summing up, which if of course necessary for correctness. )
Also I've included a simple test for ensuring the answer matches with that which is required in summing sequentially.

package Parallelism;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;



public class ParallelismBasics {

 private static int numthreads = 4;
 private static long totalParallelSum = 0;
 private static long totalSequentialSum = 0;
 private static int totalElements = 170000000;
 private static int[] numbers = null;
 private static long startTime;
 
 public static class MyTask 
    implements Callable<Long> {
     
  private int index;
  public MyTask() {}
  public MyTask(int i) { index = i; }

  public Long call() {
   long taskStart = System.currentTimeMillis();
   System.out.println("Starting Sub-Task "
     +index
     +" at time: "
     +(taskStart-startTime)
     +" ms");
   
   long taskSum = 0;
   for(int i = index; i < totalElements; i+= numthreads){
    taskSum += numbers[i]; 
   }
   long taskEnd = System.currentTimeMillis();
   System.out.println("Sub-Task "
     +index
     +" took "
     +(double)(taskEnd-taskStart)/1000
     +" seconds with SubTaskSum = "
     +taskSum
     +" and ended at time "
     +(taskEnd-startTime)
     +" ms");
   return taskSum;
      }
  }
 
 private static void setNumbers(){
  Long seed = System.currentTimeMillis();
  numbers = new int[totalElements];
  Random random = new Random(seed);
  for( int i=0 ; i < totalElements ; i++ ){
   numbers[i] = random.nextInt();
   totalSequentialSum += numbers[i];
  }
  
  Long endTime = System.currentTimeMillis();
  System.out.println("Setting the numbers"
     +"ended at time: "
     +(endTime-startTime)
     +" ms");
 }
 
 public static void main(String[] Args) 
   throws InterruptedException{
  
  startTime=System.currentTimeMillis();
  setNumbers();
  List< Future<Long> > futuresList = 
     new ArrayList< Future<Long> >();      
     long parallelStartTime = System.currentTimeMillis();
     ExecutorService eService = 
        Executors.newFixedThreadPool(numthreads);
     for(int index = 0; index < numthreads; index++){
      futuresList.add(eService.submit(
        new MyTask(index)));
     }
     eService.shutdown();
     eService.awaitTermination(
        Integer.MAX_VALUE
        , TimeUnit.SECONDS);
     Long taskResult;
     for(Future<Long> future:futuresList) {
      try {
       taskResult =  future.get();
       totalParallelSum += taskResult;
      }
      catch (InterruptedException e) {}
      catch (ExecutionException e) {}
     }
     System.out.println("The sum as computed by" 
       + "parallel computation is "
       + totalParallelSum);
     System.out.println("The sum as computed by" 
       + "sequential computation is "
       + totalSequentialSum);
     long parallelEndTime = System.currentTimeMillis();
     System.out.println("Total time taken is:"
       + (parallelEndTime-parallelStartTime)
       + "ms");
     }
 }

Now onto some interesting things.

How exactly do we chose the number of threads to create? Why not just create 1000's of threads, why only 4?

Why not plot the total run-time of the parallel part of the code as a function of the number of threads?

Plot of Running time as a function of Number of Threads

This shows how the running time of the computation of sum varies as a function of the number of threads. Not unexpectedly, the minima occurs at number of threads = 4. . This is because my laptop uses a Intel i7 Quad-core processor, and hence 4 threads can run independently on the 4 different cores.

Why does the plot sort of increase as we increase the number of threads?

This is because the OS needs to do some sort of thread-switching when switching from one thread to another and even though the overhead wouldn't be as large as that for process-switching but some overhead is unavoidable. Thus, as the number of threads increases, we need to keep switching from one thread to another (since at a time I can only execute 4 threads) and hence the gain in terms of concurrency is lost due to these thread-switching overheads.

Why go through all these pains? Does it really matter whether it takes 0.1 seconds or 0.6?

Well, depends on what you're doing! If you're building a product for the market which is expected to crunch huge amounts of data, even a simple parallelism in terms of scanning an array can help reduce execution time by as much as close to 300%, and then there are algorithms which are readily parallelisable. For example a parallel-processing based implementation of MergeSort, Binary Search, or computing any property/function for a vector/array which is associative (sum, maximum, minimum etc).

Of threads which run in parallel

Sunday, 22 June 2014

Inception Neural Networks

Wednesday, 18 June 2014

Using Your Processor