Parallelcoding.com

If anyone is having trouble compiling (no makefiles) or finding (not in the downloaded source) the IEEE 802.15.14 examples that go along with MiXiM like I did, I suggest the following steps:

1. Check out the source using the command

    svn co https://mixim.svn.sourceforge.net/svnroot/mixim mixim

2. Move the contents of the trunk directory into the omnetpp-4.1/samples/MiXiM/ directory
3. Change directories to omnetpp-4.1/samples/MiXiM/examples/ieee802154Narrow
4. Build the project using the command

   opp_makemake -f -O out -L../../out/gcc-debug/base -L../../out/gcc-
   debug/modules -L../../out/gcc-debug/tests/testUtils -lmiximbase -
   lmiximmodules -I../../modules/utility -I../../base/messages -I../../
   base/utils -I../../base/modules -I../../base/phyLayer -o
   ieee802154Narrow

5. Change directories to omnetpp-4.1/samples/MiXiM/examples/ieee802154A
6. Build the project using the command

   opp_makemake -f -O out -L../../out/gcc-debug/base -L../../out/gcc-
   debug/modules -L../../out/gcc-debug/tests/testUtils -lmiximbase -
   lmiximmodules -o ieee8021514a

Now everything should work!

I haven’t posted here in quite a while, mainly because I’ve been so busy and also because I didn’t have the time to complete a proper post. As this blog is mainly about my professional career and academic interests, let me start by sharing some of my most recent work.

I have spent quite a bit of time pursuing an area of research concerned with State Space Pruning for Monte Carlo  Simulation (MCS) when calculating Reliability Indices for Power Systems. This is a necessity due to the curse of dimensionality. Simply stated, in a power system with 32 generators one finds themselves with a need to examine states. Expand this to a larger system and suddenly the state space size explodes. In this work we’ve used Genetic Algorithms (GA), Repulsive Binary Particle Swarm Optimization (RBPSO), and Ant Colony Optimization (ACO) in order to reduce MCS time and iterations before convergence. In all cases we have used a binary representation (each bit represents a generator’s on/off state) with a DC Optimal Power Flow (DCOPF) that has been tailored to minimize load curtailment instead of cost. The algorithms are customized in order to server our particular needs (specifically generating states in which there is no load curtailment quickly). We have had a rather good success rate over two different test systems: IEEE-RTS79 and IEEE-RTS96. For those not familiar with them, these two test systems are designed specifically for reliability testing (RTS = Reliability Testing System). RTS-79 came first and RTS-96 (for the most part) is simply 3 RTS-79 that are connected to each other with minor changes. The table below shows a brief comparison between the two systems.

1. R. Green, L. Wang, Z. Wang, M. Alam, and C. Singh, “Power System Reliability Assessment Using Intelligent State Space Pruning Techniques: A Comparative Study” Submitted to 2010 Conference on Power System Technology, Hangzou China, October 2010.
2. R. Green, L. Wang, M. Alam, and C. Singh, “State space pruning for Reliability Evaluation using Binary Particle Swarm Optimization,” Submitted to Hawaii International Conference on System Sciences,University of Hawaii at Manoa, January 2011.
3. R. Green, L. Wang, and C. Singh, “State space pruning for power system reliability evaluation using genetic algorithms,” IEEE Power & Energy Society General Meeting 2010, Minneapolis, MN, July 2010.
4. R. Green, Z. Wang, L. Wang, M. Alam, and C. Singh, “Evaluation of loss of load probability for power systems using intelligent search based state space pruning,” The 11th International Conference on Probabilistic Methods Applied to Power Systems, Singapore, June 2010

Some further resources for this work that may be helpful to others include:

1. Matpower Formulation of IEEE-RTS79 [IEEE-RTS79 MatPower]
2. Matpower Formulation of IEEE-RTS96 [IEEE-RTS96 MatPower]
3. DCOPF for RTS79 in LP_Solve format [RTS-79 DC Optimal Power Flow]
4. DCOPF for RTS96 in LP_Solve format [RTS-96 DC Optimal Power Flow]

As well as some references:

1. Joydeep Mitra and Chanan Singh. Incorporating the dc load flow model in the decomposition-simulation method of multi-area reliability evaluation. IEEE Transactions on Power Systems, 11(3):1245-1254, Aug 1996.
2. Chanan Singh and Joydeep Mitra. Composite system reliability evaluation using state space pruning. IEEE Transactions on Power Systems, 12(1):471-479, 1997.
3. Joydeep Mitra and Chanan Singh. Pruning and simluation for determination of frequency duration indices of composite power systems. IEEE Transactions on Power Systems, 14(3):899-905, 1999.
4. M. Wall. GAlib: A C++ library of genetic algorithm components. Mechanical Engineering Department, Massachusetts Institute of Technology, 1996.
5. Lingfeng Wang and Chanan Singh. Stochastic combined heat and power dispatch based on multi-objective particle swarm optimization. International Journal of Electrical Power & Energy Systems, 30(3), 2007.
6. Lingfeng Wang and Chanan Singh. Population-based intelligent search in reliability evaluation of generation systems with wind power penetration. IEEE Transactions on Power Systems, 23(3):1336-1345, May 2008.
7. Lingfeng Wang and Chanan Singh. Reliability-constrained optimum placement of reclosers and distributed generators in distribution networks using an ant colony system
   algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 38(6), 2008.
8. Chanan Singh and Lingfeng Wang. Role of artificial intelligence in the reliability evaluation of electric power systems. Turkish Journal of Electrical Engineering & Computer Science,
   16(3):189-200, 2008.
9. David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, 1 edition, Jan 1989.
10. Genetic algorithm, 2009. [ Wikipedia: Genetic Algorithms ]
11. Ray D. Zimmerman, E. M.-S. Carlos, and Deqiang Gan. MATPOWER: A MATLAB Power System Simulation Package, Version 3.1b2, User’s Manual. Technical report, Power Systems Engineering Research Center, 2006. [ Matpower ]
12. Michel Berkelaar, Kjell Eikland, and Peter Notebaert. lp_solve : Open source (mixed-integer) linear programming system. 2004.
13. IEEE Committee Report. IEEE reliability test system. IEEE Transactions on Power Apparatus and Systems, PAS-98(6):2047-2054, 1979.
14. C. Grigg, P. Wong, P. Albrecht, and et al. The IEEE reliability test system-1996. IEEE Transactions on Power Systems, 14(3):1010-1020, 1999.
15. Final report on research project 2473-10. Technical report, EPRI, 1987.
16. M.V.F Pereira and N.J. Balu. Composite generation/transmission reliability evaluation. Proceedings of the IEEE, 80(4):470-491, apr 1992.
17. Roy Billinton and Wenyuan Li. Reliability Assessment of Electric Power Systems using Monte Carlo Methods. Plenum, New York; London, 1994.
18. J. Kennedy and R. Eberhart. Particle swarm optimization. In Neural Networks, 1995. Proceedings., IEEE International Conference on, volume 4, August 2002.
19. Del, G. K. Venayagamoorthy, S. Mohagheghi, J. C. Hernandez, and R. G. Harley. Particle swarm optimization: Basic concepts, variants and applications in power systems. Evolutionary Computation, IEEE Transactions on, 12(2):171-195, 2008.
20. D. K. Agrafiotis and W. Cedeño. Feature selection for structure-activity correlation using binary particle swarms. Journal of Medicinal Chemistry, 45:1098-1107, 2002.
21. A. Moraglio, C. Di Chio, and R. & Poli. Geometric particle swarm optimization. In Proceedings of the European conference on genetic programming
    (EuroGP), volume 4445, pages 125-136, 2007.
22. R. Green, L. Wang, and C. Singh. State space pruning for power system reliability evaluation using genetic algorithms. In Proceedings of the IEEE PES General Meeting, Minneapolis, MN, July 2010.
23. R. Green, Z. Wang, L. Wang, M. Alam, and C. Singh. Evaluation of loss of load probability for power systems using intelligent search based state space pruning. In Proceedings of the 11th International Conference on Probabilistic Methods Applied to Power Systems, Singapore, June 2010.
24. R. Green, L. Wang, M. Alam, and C. Singh. State space pruning for reliability evaluation using binary particle swarm optimization. Jan 2011.
25. J. Kennedy and R.C. Eberhart. A discrete binary version of the particle swarm algorithm.In IEEE International Conference on Systems, Man, and Cybernetics, volume 5, pages 4104-4108, 1997.
26. Riccardo Poli, James Kennedy, and Time Blackwell. Particle swarm optimization. Swarm Intelligence, 1(1):33-57, June 2007.
27. C. K. Mohan and B. Al-Kazemi. Discrete particle swarm optimization. Indianapolis, IN, 2001. Purdue School of Engineering and Technology.
28. R. Eberhart and James Kennedy. A new optimizer using particle swarm theory. In Proceedings of the Sixth International Symposium on Micro Machine and Human Science, pages 39-43, 1995.
29. M. Dorigo. Optimization, Learning and Natural Algorithms. PhD thesis, Politecnico di Milano, Italy, 1992.
30. Thomas Stützle and Holger H. Hoos. Max-min ant system. Future Gener. Comput. Syst., 16(9):889-914, 2000.
31. Min Kong and Peng Tian. A binary ant colony optimization for the unconstrained function optimization problem. In CIS (1), pages 682-687, 2005.
32. Onay Urfalioglu. Robust estimation of camera rotation, translation and focal length at high outlier rates. Computer and Robot Vision, Canadian Conference, 0:464-471, 2004.
33. T. Krink, J. S. Vesterstrom, and J. Riget. Particle swarm optimisation with spatial particle extension. In CEC ’02: Proceedings of the Evolutionary Computation on 2002. CEC ’02. Proceedings of the 2002 Congress, pages 1474-1479, Washington, DC, USA, 2002. IEEE Computer Society.
34. T. Krink, J. S. Vesterstrom, and J. Riget. Particle swarm optimisation with spatial particle extension. In CEC ’02: Proceedings of the Evolutionary Computation on 2002. CEC ’02. Proceedings of the 2002 Congress, pages 1474-1479, Washington, DC, USA, 2002. IEEE Computer Society.
35. J. Riget and J.S. Vesterstrøm. A diversity-guided particle swarm optimizer – the arpso. Technical report, 2002.

An interesting article has been posted over at Linux Magazine. The article interests me mainly because it gets to the heart of an issue that I myself ponder over: As hardware overtakes software, how will software catch up? This is a very important question, especially in the HPC world as there is no single language that elegantly translates across multiple architectures.


Read the rest of the article here.

This article is very interesting. A very hot topic in parallel computing these days is power consumption and this is the first that I’ve heard of the parallel power law. I’m intrigued.

In pursuing some of my research as of late, I needed to use Particle Swarm Optimization. All I wanted was some simple code for both Real and Binary PSO – but I couldn’t find anything I like! So, I’m providing a file containing both along with the RNG that I used. Please be aware that this code has not been refined. It’s clear, but rather ugly.

Particle Swarm Optimization Code

Mersenne Twister

While I never participated in the Intel Threading Challenge, I still find the problems really intriguing. Why? Because they are problems designed to test threaded development which is not only cool but is also going to play a large part in the future of computing. I would call all this problem for the most part concurrent, not parallel. Why? Read this and you’ll understand completely. Now, on to the challenge!

Problem # 1 states:

Problem description: Given a set of unsorted items with keys that can be considered as a binary representation of an integer, the bits within the key can be used to sort the set of items. This method of sorting is known as Radix Sort.

Write a program that includes a threaded version of a Radix Sort algorithm that sorts the keys read from an input file, then output the sorted keys to another file. The input and output file names shall be the first and second arguments on the command line of the application execution.

The first line of the input text file is the total number of keys (N) to be sorted; this is followed by N keys, one per line, in the file.  A key will be a seven-character string made up of printable characters not including the space character (ASCII 0×20). The number of keys within the file is less than 2^31 – 1.  Sorted output must be stored in a text file, one key per line.

Timing: If you put timing code into your application to time the sorting process and report the elapsed time, this time will be used for scoring.  If no timing code is added, the entire execution time (including time for input and output) will be used for scoring.

Example Input file:
8
H@skell
surVEYs
sysTEMS
HASKELL
Surveys
1234567
SURveys
systEMS

Example Output file:
1234567
H@skell
HASKELL
SURveys
Surveys
surVEYs
sysTEMS
systEMS

My solution (both serial and parallel):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
using System.Threading;
using System.IO;
 
namespace RadixSort {
 
    class Program {
        static void Main(string[] args) {
            StreamReader sr;
            int length;
            TimeSpan serial, parallel;
            sr = File.OpenText(@"C:\Documents and Settings\rgreen\Desktop\Threading\Threading\rsTestK100.dat");
 
            length = Convert.ToInt32(sr.ReadLine().Trim());
            string[] values = new string[length];
            string[] newValues = new string[length];
            for(int x = 0; x < length; x++) {
                values[x] = sr.ReadLine().Trim();
            }
 
            Stopwatch sw = new Stopwatch();
 
            //
            // Serial
            //
            sw.Start();
            RadixSort(values).CopyTo(newValues, 0);
            sw.Stop();
            serial = sw.Elapsed;
 
            //
            // Parallel
            //
            sw.Reset();
            sw.Start();
            ParallelRadixSort(values).CopyTo(newValues, 0);
            sw.Stop();
            parallel = sw.Elapsed;
 
 
            Console.WriteLine("Serial Time: " + serial);
            Console.WriteLine("Parallel Time: " + parallel);
            Console.ReadLine();
        }
 
        public static string[] ParallelRadixSort(string[] array) {
            int length = array.Length;
 
            Parallel.For(0, array[0].Length - 1, delegate(int curRadix) {
                int index = array[0].Length - 1 - curRadix;
                array = new MergeSort(array, array[0].Length - 1 - index).Results;
            });
 
            return array;
        }
 
        public static string[] RadixSort(string[] array) {
 
            int length = array.Length;
 
            for(int curRadix = array[0].Length - 1; curRadix >= 0; curRadix--) {
                array = new MergeSort(array, array[0].Length - 1 - curRadix).Results;
            }
 
            return array;
        }
    }
}

And there you have it!

Jeff Blankenburg has put together an incredible puzzle over at http://www.toughestdeveloperpuzzleever.com/tdpe/. Absolutely a ton of fun. It took me a few hours to get through it myself!

Project Euler problem #6 is

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

When I first began looking at this problem I wanted to experiment a bit with the Parallel Extensions for .NET, so I started where any parallel algorithm begins: with a sequential algorithm. The algorithm here is rather trivial: Loop over the natural numbers from 1 to 100. In order to sum the squares I will sum the square of each number. In order to square the sum I will sum the numbers and then square them. The difference is the answer. So, first, I came up with two functions: SumOfSquares and SquareOfSums.

My first attempt at these functions ended up something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static double SumOfSquares(int min, int max) {
    double result = 0;
    for(int x = min; x <= max; x++) {
        result += Math.Pow(x, 2);
     }
     return result;
}
static double SquareOfSums(int min, int max) {
    double result = 0;
    for(int x = min; x <= max; x++) {
        result += x;
    }
    return Math.Pow(result, 2);
}

Both of those functions are very straight forward. My first thought after writing these was, “Hey, why not use some LINQ?” So I did. Here is how the functions change:

1
2
3
4
5
6

static double LinqSumOfSquares(int min, int max) {
    return Enumerable.Range(min, max).Select(d => Math.Pow(d, 2)).Sum();           
}
static double LinqSquareOfSums(int min, int max) {
    return Math.Pow(Enumerable.Range(min, max).Select(d => d).Sum(), 2);    
}

Wow! Talk about incredible, shrinking functions! I love finding a way to make code more succinct, readable, and elegant and these changes seem to have hit the nail on the head! Anyways, that is basically all the pieces for the sequential algorithm. All you have to do is call each of those functions and take the difference. Simple, huh? But the real question is how can we parallelize these bad boys? I have a few thoughts.

1. Call each function in parallel. In other words let the sumOfSquares and SquareOfSum function run at the same time in different threads.
2. Parallelize each function invidvidually. In other words leverage the loops inside of each function in order to parallelize them.

So let’s take a look at each method using the Parallel Extensions for .NET. The first method is calling each function in parallel. My first thought here was to use Parallel.Invoke in order to call each function at the same time. A little further research quickly revealed that Parallel.Invoke cannot return any values. My initial response to that: “Well that sucks.” Luckily there’s another class in the Parallel library called Futures. What’s a future? From DevX –

“In TPL terms, a Future is basically a task that returns a value. It’s like a deferred function. You start it running and then use its value later. If the Future hasn’t finished calculating its value by the time you need it, it makes you wait while it finishes.”

Sounds good to me. So how do we use futures? Like this:

1
2
3
4
5
6
7
8

static long Problem6Futures(int min, int max) {
 
    Future<double> fSumOfSquares = Future.Create(() => SumOfSquares(min, max));
    Future<double> fSquareOfSums = Future.Create(() => SquareOfSums(min, max));
    double result = fSquareOfSums.Value - fSumOfSquares.Value;
 
    return result;
}

Easy, huh? All you have to remember is that Futures are deferred functions that return values. The result of Future operation gets stored in an object of type Future and the value is stored in Object.Value. So how about the second method of parallelizing this algorithm? Well, it’s even easier because of PLINQ – or Parallel LINQ. Let’s see what it looks like.

1
2
3
4
5
6

static double ParallelSumOfSquares(int min, int max) {
    return Enumerable.Range(min, max).AsParallel().Select(d => Math.Pow(d, 2)).Sum();
}
static double ParallelSquareOfSums(int min, int max) {
    return Math.Pow(Enumerable.Range(min, max).AsParallel().Sum(), 2);
}

Hah! Even easier! All that I did was add .AsParrallel() to our data. That tells LINQ to do the processing in parallel!

So, there’s Project Euler Problem #6 for you. Was it a hard problem? Not really. Are you going to see major performance results through the parallelization of this algorithm? No. But you gotta’ start somewhere when you’re learning how to parallelize algorithms using a new library. Today I used Futures and PLINQ and that sound’s like a pretty solid start to me.

Project Euler #3 is :

Find the largest prime factor of a composite number.

My first attempt at this whipped up some typical code that simply brute forced my way to the solution. My code looked like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

static void Problem3() {
    long n = 600851475143;
    int factor = 2;
    int lastFactor = 1;
 
 
    if(n % 2 == 0) {
        lastFactor = 2;
        n = n / 2;
        while(n % 2 == 0) {
            n = n / 2;
        }
     } else {
         lastFactor = 1;
     }
     factor = 3;
 
     double maxFactor = Math.Sqrt(n);
     while(n > 1 && factor <= maxFactor) {
          if(n % factor == 0) {
              n = n / factor;
              lastFactor = factor;
              while(n % factor == 0) {
                  n = n / factor;
              }
              maxFactor = Math.Sqrt(n);
          }
          factor += 2;
      }
 
      if(n == 1) {
          Console.Write(lastFactor.ToString() + " ");
      } else {
          Console.Write(n.ToString() + " ");
      }
}

Not very elegant, but it works. So I set out to find something a bit prettier and I came across I LINQ solution here. All I did was tack on the .AsParallel() in order to give it a little speed boost. The code looks like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

static void LinqProblem3() {
    long largeNumber = 600851475143;
    var allPrimeFactors = from p in Primes.PrimeFactors(largeNumber).AsParallel()
                                 orderby p descending
                                 select p;
 
    foreach(var f in allPrimeFactors){
        Console.WriteLine(f);
    }
}
 
public static class Primes {
 
    // Find all prime factors.
    public static IEnumerable<int> PrimeFactors(long number) {
        // Start by removing the lowest prime (2)
        return MorePrimeFactors(number, 2);
    }
 
    // This recursive method finds all prime factors.
    private static IEnumerable<int> MorePrimeFactors(long number, int factor) {
        // Find the next prime factor
	while(number % factor != 0)
	    factor++;
	// Return it.
	yield return factor;
 
	// look again...
	if(number > factor)
		// recursively look for this factor again, using Num/factor
		// as the new big number
		foreach(int factors in MorePrimeFactors(number / factor, factor))
			yield return factors;
	}
}

For some reason it seems that I often need to perform a left join in LINQ. Every time I need to do this I find myself scouring the web one more time in order to remember how a left join works in LINQ. So how does it work? The best example that I’ve found is here. The example looks something like this:

1
2
3
4
5
6
7
8
9
10

var list = from r in dc.tblRooms
             join ui in dc.tblUserInfos
             on r.UserName equals ui.UserName into userrooms
             where r.CourseID == 1848
             from ur in userrooms.DefaultIfEmpty()
             select new{
                 FirstName = (ur.FirstName == null) ? "N/A" : ur.FirstName,
                 LastName = (ur.LastName == null) ? "N/A" : ur.LastName,
                 RoomName = r.Name
              };

I like this example a lot because it is very straight forward. Personally I would like to make the statement a bit more generic. In order to do that all we need to remember is that every Left Join has a left table A and a right table B. All the results from the A will be returned regardless of the join with B. In my example I will call table A the LEFT_TABLE and table B the RIGHT_TABLE.

1
2
3
4
5
6

var list =  from LT in LEFT_TABLE
	      join RT in RIGHT_TABLE
	      on LT.key equals RT.KEY into NEW_TABLE
              where <CONDITIONS>
              from NT in NEW_TABLE.DefaultIfEmpty()
              <SELECT_STATEMENT>;

The only problem that may occur with this left join occurs with the DefaultIfEmpty() operator. A better practice would be to pass in a default value so that we can know what to expect in return.