Introduction
Sometimes the terms concurrency and parallelism are used interchangeably. But a multi-threaded application can have threads execute simultaneously while residing on one physical chip. Parallelism, however, is achieved only when those concurrent threads are executing on separate cores of a multi-core chip. When we write an algorithm to use concurrency, our most important design choice should be to figure out how to partition the original problem into individual sub-parts. Most programs spend a lot of their execution time running loops over an iteration range, so parallelizing those loops enables concurrency.
The purpose of this article to show how to use parallel programming to build a Windows Forms application that is able to use a random number generator to implement an encryption of a quote. The reader will find that when the parallel check box is checked, the number of random number generations is much greater than if done sequentially. Apart from the Windows designer code that is generated by IDE while building form, there is a program file that contains the main function of source execution. The complicated part is understanding the two classes: the TextMatchGeneticAlgorithm.cs and the ThreadSafeRandom.cs algorithm. The ThreadSafeRandom file contains objects that are constructed in the TextMathGeneticAlgorithm file. Both of these files are mutually inclusive to the main form files and the Program.cs files.
Because we are dealing with random number generation of certain types, I am going to begin this article explaining the .NET provisions for these mechanisms. After exemplifying the basics about random number generator (RNGCryptoServiceProvider), the downloadable source ThreadSafeRandom.cs should not appear too complicated. The TextMatchGeneticAlgorithm.cs follows after these parallel patterns. An excellent source of information regarding parallel programming resides at the MSDN Parallel Programming Center. Most of the articles are must reads and useful for both reference and developing your own content.
The .NET Framework has two ways of generating random numbers. Most programs will instantiate a System.Random object instance and call one of the member functions to get random numbers. The numbers returned aren't truly random, but rather pseudo random. But they're good enough for most applications that call for randomness. But the pseudo random nature of the numbers returned by System.Random objects is not good enough for cryptographic purposes. The algorithm used by System.Random to generate random numbers is actually generating a sequence in which the next number generated is dependent on the previous number generated. The algorithm is deterministic and predictable. Somebody who knows how the algorithm works can use that information to trivially break any encryption based on the pseudorandom numbers. Cryptographic applications require truly random sequences that can't be predicted. In .NET, the System.Security.Cryptography.RandomNumberGenerator abstract class serves as the base class for all cryptographic random number generators. System.Security.Cryptography.RNGCryptoServiceProvider provides an implementation of that abstract class.
Generating Secure Random Values
The first step in generating truly random values is to create an instance of the RNGCryptoServiceProvider class. Then, allocate an array of bytes and pass that array to the GetBytes method. The random number generator will fill the byte array with a sequence of random values. Here's how to do it in C#:
using System;
using System.Security;
using System.Security.Cryptography;
public class Program
{
public static void Main()
{
RNGCryptoServiceProvider
random = new RNGCryptoServiceProvider();
byte[]
randomBytes = new byte[1024];
random.GetBytes(randomBytes);
foreach
(var b in
randomBytes)
{
Console.Write("{0:X2} ", b);
}
}
}
Here is the output:
7D
96 7D EB C3 A1 81 64 52 7E 80 57 7D 3B 10 2C 8E 7D 27 D8 4F 38 29 99 2E
32
BB 23 74 4E 61 65 43 45 EB 15 53 9B 50 F2 74 A5 83 9E C0 AF CB 72 53 86
75
7F 6A 83 D7 74 8A B5 CF D1 B8 F8 BF 2A 7D A6 62 44 6F E9 8B F8 26 C4 CE
D2
A7 F0 29 94 A9 F8 F6 E6 95 58 6F DF 4F DE 60 2D 56 A4 93 35 3A CA B3 17
E9
E6 19 C3 41 D7 C6 D1 9E E6 A3 94 C8 A3 20 14 4F F5 83 30 EB 08 C7 39 D2
65
B3 F1 65 6B 23 1E 61 D9 AA 22 D0 59 BC 02 B5 CC 06 D2 48 0E 14 CD FC D2
5F
77 17 26 79 40 C6 F9 FE 00 69 EF 9A 3F E4 BE E5 9D FB 89 1D 7F E6 1E A1
F7
DF BA B6 CC 9F B4 F9 5A 37 FE 58 B5 2F 9F 51 86 FE 69 57 7E F8 45 16 34
52
3C 8E 87 AF 59 5E 9B EF 61 79 59 AC 73 81 52 7A C9 F4 3F EC E0 C9 5B FE
30
E8 E9 00 7B DC E6 C5 F4 88 30 93 48 80 B2 0E D9 F5 B4 1F 1D E7 F4 A1 DA
DA
CD CE 26 5F 30 A0 D1 9E 73 01 8D 2D 70 34 51 80 97 08 39 3B C8 0F EC 2A
18
BD C1 06 95 20 3D F7 3F 79 8A 9C 26 76 10 22 47 01 38 3A 94 04 30 BB A4
DB
A1 FD 3D 43 45 EA F3 0D 1C 87 77 DC C3 41 AC 0D 82 28 05 54 61 42 F5 BC
1D
92 AC BD 36 53 C7 1F E9 F3 D4 9C 51 B3 69 77 E3 A5 92 52 FF 18 E7 5C 11
95
09 C2 EE 53 D9 E7 D9 D4 6A 6B 5F D8 B6 08 36 6C 5B 95 A6 24 49 BD 1F B6
5A
18 1D C5 30 54 33 9B 3C 30 95 83 C3 48 B2 AB 21 92 65 35 E9 86 EC 26 71
65
5A 94 05 CA 1D FB DE 81 B3 ED 7F 04 20 16 A5 68 2D E2 EC 46 B5 6D 00 17
2F
81 76 3A 86 11 05 31 ED BA BF 1D 3D D6 69 8F AD 3F 18 94 61 E2 CE B3 08
2D
6A E7 AF 17 02 75 48 60 00 7D 9B 92 0B A1 A3 62 D6 46 D0 C9 6A E9 FB D5
03
1C 43 4A 6A 76 1D 45 90 0D D8 6B 64 3A 2C 38 F1 42 4F 98 79 2C 6C 77 69
3B
87 A4 7E 00 87 15 92 02 67 5C C0 20 1C 81 E7 DF F7 7A 28 6F 7F 70 10 51
8A
17 67 2C 75 9C 2E 20 C2 5E 80 98 11 CC 46 87 FB 4A 85 65 99 58 06 6D 86
E2
50 2C FB EA 69 47 DE 3E B2 39 B0 E4 5D B3 63 F3 70 C6 52 67 F1 09 C8 AC
and so on . . . . . . . .
Generating Random Integers
In general, applications that require the use of truly random values don't typically need random integers or random floating point numbers. They just need random bytes. But if you really want random integers or other multi-byte values, you'll have to construct them yourself from the bytes returned by GetBytes. The code below generates 256 random positive integers from the random bytes returned by GetBytes.
using System;
using System.Security.Cryptography;
public class Program
{
public static void Main()
{
RNGCryptoServiceProvider
random = new RNGCryptoServiceProvider("testo");
byte[]
randomBytes = new byte[256
* sizeof(int)];
random.GetBytes(randomBytes);
for (int i = 0; i < 256; ++i)
{
int
val = BitConverter.ToInt32(randomBytes, i *
4);
val &= 0x7fffffff;
Console.WriteLine(val);
}
}
}
And the output is:
317550161
422861278
526562124
449336275
991713816
1652487604
880619295
633790643
1397989797
696122560
2081704890
338459605
1023259457
903093930
630767348
554883809
809901421
685484127
1992278417
1651570395
1606911073
1970878803
1813967620
1119285127
1545465870
1674136843
212937010
1301413975
1144306793
997391586
234662339
1345235759
1055049749
914349757
1286666161
506392153
1768422944
914725219
335875720
720919927
1278360239
1362332549
270292310
1587219133
403765394
1192342225
597086276
802359086
864984234
and so on . . . . .
BitConverter.ToInt32 gets the next four bytes in the array and returns a 32 bit integer. The next line of code just makes sure that the number is positive. If you don't mind getting negative numbers, then you can skip that. Or, you can get unsigned integers by calling BitConverter.ToUInt32.
The
Two Class Library Files
Here is ThreadSafeRandom.cs:
using System;
using System.Security.Cryptography;
namespace System.Threading
{
public class ThreadSafeRandom
: Random
{
private
static readonly
RNGCryptoServiceProvider _global =
new RNGCryptoServiceProvider();
private
ThreadLocal _local = new ThreadLocal(() =>
{
var buffer = new byte[4];
_global.GetBytes(buffer); //
RNGCryptoServiceProvider is
//
thread-safe for use in this manner
return
new Random(BitConverter.ToInt32(buffer, 0));
});
public override int Next()
{
return
_local.Value.Next();
}
public override int Next(int maxValue)
{
return
_local.Value.Next(maxValue);
}
public override int Next(int minValue, int
maxValue)
{
return
_local.Value.Next(minValue, maxValue);
}
public override double
NextDouble()
{
return
_local.Value.NextDouble();
}
public override void
NextBytes(byte[] buffer)
{
_local.Value.NextBytes(buffer);
}
}
}
And here is the TextMatchGeneticAlgorithm.cs
file:
using System;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Security.Cryptography;
namespace ShakespeareanMonkeys
{
public class TextMatchGeneticAlgorithm
{
private
static ThreadSafeRandom _random = new ThreadSafeRandom();
private
static char[]
_validChars;
private
string _targetText;
private
GeneticAlgorithmSettings _settings;
private
TextMatchGenome[] _currentPopulation;
private
bool _runParallel;
static
TextMatchGeneticAlgorithm()
{
//
Initialize the valid characters to newlines plus
// all
the alphanumerics and symbols
_validChars = new char[2 + (127 -
32)];
_validChars[0] = (char)10;
_validChars[1] = (char)13;
for
(int i = 2, pos = 32; i <
_validChars.Length; i++, pos++)
{
_validChars[i] = (char)pos;
}
}
public
TextMatchGeneticAlgorithm(bool runParallel,
string
targetText, GeneticAlgorithmSettings settings)
{
if
(settings == null) throw
new ArgumentNullException("settings");
if
(targetText == null) throw
new ArgumentNullException("targetText");
_runParallel = runParallel;
_settings = settings;
_targetText = targetText;
}
public void MoveNext()
{
// If
this is the first iteration, create a random population
if
(_currentPopulation == null)
{
_currentPopulation =
CreateRandomPopulation();
}
// Otherwise, iterate
else
_currentPopulation = CreateNextGeneration();
}
public
TextMatchGenome CurrentBest { get { return _currentPopulation[0]; } }
private
TextMatchGenome[] CreateRandomPopulation()
{
return
(from i in
Enumerable.Range(0, _settings.PopulationSize)
select
CreateRandomGenome(_random)).ToArray();
}
private
TextMatchGenome CreateRandomGenome(Random
rand)
{
var sb = new StringBuilder(_targetText.Length);
for
(int i = 0; i < _targetText.Length; i++)
{
sb.Append(_validChars[rand.Next(0, _validChars.Length)]);
}
return
new TextMatchGenome { Text = sb.ToString(),
TargetText = _targetText };
}
private
TextMatchGenome[] CreateNextGeneration()
{
var
maxFitness = _currentPopulation.Max(g => g.Fitness) + 1;
var
sumOfMaxMinusFitness = _currentPopulation.Sum
(g => (long)(maxFitness - g.Fitness));
if
(_runParallel)
{
return
(from i in
ParallelEnumerable.Range
(0,
_settings.PopulationSize / 2)
from child in CreateChildren(
FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),
FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))
select
child).
ToArray();
}
else
{
return
(from i in
Enumerable.Range(0, _settings.PopulationSize / 2)
from child in CreateChildren(
FindRandomHighQualityParent(sumOfMaxMinusFitness,
maxFitness),
FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))
select child).
ToArray();
}
}
private
TextMatchGenome[] CreateChildren(
TextMatchGenome parent1,
TextMatchGenome parent2)
{
//
Crossover parents to create two children
TextMatchGenome child1, child2;
if
(_random.NextDouble() < _settings.CrossoverProbability)
{
Crossover(_random, parent1,
parent2, out child1, out
child2);
}
else
{
child1 = parent1;
child2 = parent2;
}
//
Potentially mutate one or both children
if
(_random.NextDouble() < _settings.MutationProbability)
Mutate(_random, ref child1);
if
(_random.NextDouble() < _settings.MutationProbability)
Mutate(_random, ref child2);
// Return
the young'ens
return
new[] { child1, child2 };
}
private
TextMatchGenome FindRandomHighQualityParent
(long sumOfMaxMinusFitness, int
max)
{
long
val = (long)(_random.NextDouble() *
sumOfMaxMinusFitness);
for
(int i = 0; i < _currentPopulation.Length;
i++)
{
int
maxMinusFitness = max - _currentPopulation[i].Fitness;
if
(val < maxMinusFitness) return
_currentPopulation[i];
val -= maxMinusFitness;
}
throw
new InvalidOperationException("Not to be, apparently.");
}
private
void Crossover(Random
rand, TextMatchGenome p1,
TextMatchGenome p2, out TextMatchGenome child1, out
TextMatchGenome child2)
{
int
crossoverPoint = rand.Next(1, p1.Text.Length);
child1 = new
TextMatchGenome
{
Text = p1.Text.Substring(0,
crossoverPoint) +
p2.Text.Substring(crossoverPoint),
TargetText = _targetText
};
child2 = new
TextMatchGenome
{
Text = p2.Text.Substring(0,
crossoverPoint) +
p1.Text.Substring(crossoverPoint),
TargetText = _targetText
};
}
private
void Mutate(Random
rand, ref TextMatchGenome genome)
{
var
sb = new StringBuilder(genome.Text);
sb[rand.Next(0,
genome.Text.Length)] = _validChars[rand.Next
(0,
_validChars.Length)];
genome.Text = sb.ToString();
}
}
public struct TextMatchGenome
{
private
string _targetText;
private
string _text;
public string Text
{
get
{ return _text; }
set
{
_text = value;
RecomputeFitness();
}
}
public string TargetText
{
get
{ return _targetText; }
set
{
_targetText = value;
RecomputeFitness();
}
}
private
void RecomputeFitness()
{
if
(_text != null && _targetText != null)
{
int
diffs = 0;
for
(int i = 0; i < _targetText.Length; i++)
{
if
(_targetText[i] != _text[i]) diffs++;
}
Fitness = diffs;
}
else
Fitness = Int32.MaxValue;
}
public int Fitness { get; private set; }
}
public class GeneticAlgorithmSettings
{
public int PopulationSize
{
get
{ return _populationSize; }
set
{
if
(value < 1 ||
value
% 2 != 0)
throw
new ArgumentOutOfRangeException("PopulationSize");
_populationSize = value;
}
}
public double MutationProbability
{
get
{ return _mutationProbability; }
set
{
if
(value < 0 || value
> 1)
throw
new ArgumentOutOfRangeException("MutationProbability");
_mutationProbability = value;
}
}
public double CrossoverProbability
{
get
{ return _crossoverProbability; }
set
{
if
(value < 0 || value
> 1)
throw
new ArgumentOutOfRangeException("CrossoverProbability");
_crossoverProbability = value;
}
}
private
int _populationSize = 30;
private
double _mutationProbability = .01;
private
double _crossoverProbability = .87;
}
}
Those files are downloadable as a
zip file. When you open the zip file, press Ctrl-A to select all of the files
(or the initial folder) and then extract to a new folder in the Projects
folder of the Visual Studio 2010 folder. Visual Studio 2010 is an easy download
as an ISO file and is easy to burn to a DVD. Once the files are exposed, click
the solution file, build the solution, and then choose "run without debugging".
Now we run the application first in sequential mode (i.e.,
we don't check the parallel check box). Take care to note the number of
generations per second, as well as the number of generations altogether:
Parts of this article have been referenced from MSDN's Parallel Computing Center