Sunday, July 31, 2011

Genetic Algorithm - Part 10 - Algorithm Correctness

How do you know that the genetic algorithm one has coded is correct. It is possible that the algorithm is arriving at a solution, but how one verifies that the algorithm is correct.

I have been rewriting the solution in C#, I have already created the basic structure for genetic algorithm using multithreading. Since I already had a SQL implementation of the same, I was importing the generated DNAs for a generation in C# and applying the fitness function on it in C#.
So the next step was to complete the full algorithm in C#. I coded the complete algorithm and ran it but the solution was not converging. The fitness score increased to 460 (maximum being 500 which is a solution) and it started coming down. I obviously cannot debug a genetic algorithm as I usually debug the code. I looked at the code for a couple of days but couldn't find the problem. So I need to try another way.

I already have a SQL version of the solution, so I exported the set of DNAs for the generation where the fitness score started coming down into SQL server. I realized that the DNAs in that generation had different parents which is incorrect. This was causing the solution not to converge.

I looked at the code and found that the multiple threads which were creating the DNAs for a generation, finds the DNAs with the best fitness score from each of its set of DNAs. Now in the common list used by main thread, the parents were getting overwritten which was causing the issue.

One criteria for the algorithm correctness is that the fitness score should always increase as the generations progress, that is by definition of evolution. And it is evolution what we are using in the algorithm.

So far i have successfully implemented a multi-threading solution for the problem. The next step is to have more realistic conditions in the algorithm which I will describe in the next post.

Tuesday, July 5, 2011

Genetic Algorithm – Part 9 - Optimum number of threads

How many threads one should create to get optimum performance? In my case how many child threads should I create on an given environment. I would be running this on different configurations. Some might have four processor core and some sixteen.

The logical answer is number of threads should be equal to number of processor cores. The idea is to keep all the processor cores busy at all times.Below are timings for tests done on 16 processor core machine, the code contains CPU intensive algorithm.

As we can see the best performance we get is when number of thread is slightly less than total number of cores i.e. between 12 to 16 threads. We need to keep couple of cores idle for other OS related threads.


In the application I would allow user to select number of child thread he wants to use. This would give user a chance to evaluate performance.

Genetic Algorithm – Part 8 - “Lock” can be expensive

I was doing multithreaded implementation of this this solution. I came out with two approaches.

Approach 1

There will be main thread and number of child thread ( number of child thread is equal to number of processor cores).
The main thread does following
  • Randomly selects cross over and mutation points for all children.
  • Selects top two children which would be parents for the next generation. 
  • Wait for all child threads to complete its tasks.
A Child thread does following
  • Creates new child from parents using cross over and mutation points.
  • Use fitness function to calculate score of child.
Looking back at the approach, I thought the main thread would do its work and wait for all the children to complete their work. To optimize I thought of other approach, which is summarized below.

Approach 2
There is no “designated” main thread, the child which complete its work first becomes main thread, it does task outlined in approach 1 for main thread and then transforms into child thread. I thought using this approach no thread would be significantly idle now. 

I had already used Approach 1, so I quickly but properly modified the code to use Approach 2. I took readings which I have outlined below.I was bit shocked. The time taken for Approach 2 was significantly higher (21%) than Approach 1. Below are the comparison.


I did some analysis to find out what went wrong. I ran the code for 10000 generations, instead of 1000 generations. Art of multithreading requires minimum use of  synchronization constructs between threads. In writing this implementation I have taken great pain to avoid “locks”, even main and child thread approach looked like producer and consumer pattern I had implemented it without “locks”. I will post the strategy for that in another post.

In Approach 2 however I had to use “one” additional “lock” statement so as to decide which child thread becomes main thread and it does main thread tasks while other “late” child thread waits. 

Below are the wait timings of child thread for both approaches which would reveal why Approach 2 took longer time.

Wait timings for child thread in Approach 1


















Wait timings for child thread in Approach 2


















In approach 1 average wait time was 22 secs which had become almost 1 minute 21 sec in approach 2, which accounts for the difference of timings. 

Remember take great care in adding “lock” in multithreaded code, even one additional synchronizing construct can your affect your applications scalability and performance.

In next post i will write about how many threads I should create on a given environment.

Sunday, July 3, 2011

Genetic Algorithm – Part 7 - Compare SQL and C# code

Now it is time to compare SQL and C# implementation. Below are the comparisons for 1000 generations.


The results are staggering the C# code is working way faster. There is couple of reason for that. First one uses of all processor cores. Picture below is for C# code, use can see all the processor cores being utilized properly.

(click on image to enlarge)


Below is the CPU utilisation for SQL code.






If you look at the CPU utilization in case C# all the cores are being used, while in case of SQL only one core is being used. If you look carefully in picture at the CPU usage percentage is 78.03 % for C#, while it is 8.77% for SQL.

Second reason is I have to represent DNA, board and other constructs as string in SQL and do manipulations, while I have data structure like arrays in C#, which has proved to be faster. Remember each code path runs one million times, so even slight benefit turns out to be significant gain in the end.

Friday, July 1, 2011

Genetic Algorithm – Part 6 - Benchmark multithreaded C# code

I did several runs on various machines and below are the reading and they speak for itself. First up comparison on 2 core and 16 core.



























Above reading might be puzzling to some who might have thought 16 core machine should have taken 9 sec. I have been part of discussions where software engineers have argued that if one thread takes X time then then eight thread should do work in X / 8 time.Apart from IO, memory bottlenecks that can happen between threads.Even before you can do multithreading the moment you have multiple processor there are bottlenecks.

When we have a system with just one processor, and if we add three more, we will not have four times the performance. This is because each time we add a processor, the time they dedicate to coordinate their work and the task assignment process increases. Table below summaries it best.



In next post I will compare performance between SQL and C#.

Genetic Algorithm – Part 5 - Multithreading bugs

I almost completed skeleton code for C# implementation and it was time to test. I did several round of testing with various configurations on different machines. I found a strange defect in code which took me almost 5 hours to resolve. Below is a screenshot where the application hangs as main thread waits for all child thread to complete. You can see the application stopped after 47 iterations.


The error was with following code.
Interlocked.Decrement(ref threadStartedCounter);
This is supposed to "Decrements (decreases by one) the value of the specified 32-bit variable as an atomic operation." but i figured out it was not on Windows XP when I had 16 threads on 2 core processor. I modified the code not to use Interlocked class and it was working fine.

If you are testing on XP (chances are high as when Vista was developed it was not Microsoft's finest hour) , you might have to apply patch below so that optimum use of cores takes place.
http://support.microsoft.com/kb/896256

Now I have to take readings which will be published in next post.

Wednesday, June 29, 2011

Genetic Algorithm – Part 4 - Benchmark existing solution

The first step was to benchmark performance for SQL server implementation. I did benchmark on two machines. Below are the readings for 1000 Generations. On both machines it takes 20 min. 


Remember the high end machine has 16 cores. However it is observed that SQL implementation is not able to take any advantage of huge processing power. Ironically there are only few products which scale to such huge processing power and one of the reasons for that is difficulty in re-writing existing software to use multiple cores effectively. Note also multithreaded programs are difficult to write and test. 

So now for C# implementation time to beat is 20 mins.

P.S.
One of the product which does fantastic use of multithreading is Metal Ray.