Visual Basic 2010 Parallel Programming techniques

Purpose

The purpose of this document is

• To write down my experience with Visual Basic 2010 related to Parallel Programming using the Background Worker.
• To explain what the easiest way is to implement Parallel Programming

This document is related to the following Visual Basic 2010 programs, which all use Parallel Programming:

• VSTest2 discussed in: CPU performance Part 1
• Planet, PlanetPP discussed in: CPU performance Part 2
• FibonacciPP discussed in: Fibonacci
• VB2010 FGalalay PP discussed in: Visual Basic 2010 Fractal Galaxy Program: VB2010 FGalaxy and VB2010 FGaxaly PP

For executables of each program go to: VB2010 exe.zip

• For a detailed evaluation of Visual Basic 2010 go here: Visual Basic 2010 Evaluation
• For a general discussion about parallel programming and threads go here: Advantages and disadvantages. This document also contains comments about Wikipedia

Parallel Programming Background

The reason why Parallel Programming becomes a hot issue is the Hardware. With the Intel Pentium 4 2.80 GHz Intel has reached the highest clock rate to build a CPU which consists of 1 processor or 1 Core. The next Intel CPU Intel Pentium 4 3.00 GHz also consists of 1 Core but supports 2 threads (2 Virtual CPU's).
Suppose you have one physical application and you want to solve that problem as quick as possible using your PC at full capacity for 100%.

• With a Pentium 2.80 this is "easy". You write one program and that is it.
• With a Pentium 3.00 this is much more complicated. When you execute the same program you will see that it takes roughly twice as long to find the solution. The reason is because with this program you only use one thread or virtual CPU. That means you use your PC only for 50%. To use this processor at full capacity you must use parallel Programming. General speaking you must divide your application into two parts and execute both parts in parallel in order to reach full capacity.

Parallel Programming Introduction

Suppose you want to implement the following two programs and use parallel programming:

1 x = 1: y = 2 2 for i = 1 to 100 3 x = x + 1 / i 4 y = y + 1 / i 5 next i program 1

1 x = 1: y = 2 2 for i = 1 to 100 3 x = x + 1 / i 4 y = x + y + 1 / i 5 next i program 2

When you study those two programs you will see that they are almost identical. The difference is in line 4. This is the line were the parameter y is calculated.

• When you study program 1 the two lines 3 and 4, were the parameters x and y are calculated, are independent of each other. The parameter x in line 3 is a function of x and the parameter y in line 4 is a function y
  The result is that you can divide each program in two parts and execute them in parallel.
• When you study program 2 the two lines 3 and 4 are not independent of each other. The parameter x in line 3 is a function of x but the parameter y in line 4 is a function of both x and y
  Line 4 is dependent of the result of the previous line. That means you can not divide the program into 2 parts and execute those in parallel.

When you divide program 1 in two parts the result will be like this:

1 x = 1 2 for i = 1 to 100 3 x = x + 1 / i 4 next i program 3

1 y = 2 2 for i = 1 to 100 3 y = y + 1 / i 4 next i program 4

When you start those programs at the same time and when they are executed in parallel you get the result quicker as in the case of program 1

• Parallel execution is possible when your processor contains (at least) 2 CPU's. In that case program 3 is executed in CPU 1 and program 4 in CPU 2.
• Parallel execution is also possible when your processor contains 1 CPU and supports 2 threads (Virtual CPU's). In that case program 3 is executed in thread 1 and program 4 in thread 2.

Parallel Programming Example 2

Suppose you want to execute the following set of equations continuous in a loop:

1 x1(0) = a(0,0) * x0(0) + a(0,1) * x0(1) + a(0,2) * x0(2) 2 x1(1) = a(1,0) * x0(0) + a(1,1) * x0(1) + a(1,2) * x0(2) 3 x1(2) = a(2,0) * x0(0) + a(2,1) * x0(1) + a(2,2) * x0(2) 4 x0(0) = x1(0) X0(1) = x1(1) x0(2) = x1(2)

The Visual Basic program which does that, is the following:

1 x0(0) = ? x0(1) = ? x0(2) = ? a(0,0) = ? etc 2 DO 3 For i = 0 to 2 4 x1(i) = 0 5 For j = 0 to 2 6 x1(i) = x1(i) + a(i,j) * x0(j) 7 next j 8 next i 9 For i = 0 to 2 : x0(i) = x1(i) : next i 10 LOOP UNTIL ?

What this program does is rather straight forward:

1. In line 1 the arrays x0() and a(,) are intialised.
2. In line 6 the values of the array x1() are calculated as a function of the array x0()
3. In line 9 the array x0() is set equal to the array x1() and the whole process is repeated.

This example resembles the PlanetPP simulation. In that case the next positions of the planets and are calculated as a function of the previous positions. The previous positions are stored in the array x0() and the next positions in the array x1()
The program is written to be executed with one CPU with 1 processor. The importance of the program is that each calculation of the values in the array x1() is independent of each other. That means the calculations can be performed in parallel. This requires modifications of the programming i.e. parallel programming.

The following Visual Basic program shows how this is done in slave processor 2.

1 i = 2 2 DO 3 If state(i) = 1 then ' request from Master 4 x1(i) = 0 5 For j = 0 to 2 6 x1(i) = x1(i) + a(i,j) * x0(j) 7 next j 8 End If 9 state(i) = 2 ' done 10 LOOP UNTIL ?

The general way to communicate between the different processors is by means of the array: state()
See for details in the next paragraph.

Parallel Programming Implementation

Parallel Programming does not mean that you run the same program in parallel in different processors/cores or threads. This is equivalent with performing many applications at the same time.
Parallel Programming means that you only perform one application. That means that you subdivide the application in independent tasks and you write your program in such a way that you can execute the different tasks of your program (in order to solve one application) in parallel in different cores/threads in the same CPU. Each of those tasks which are executed in parallel are called a Branch in this document.
In order to perform Parallel Programming at least 2 programs are used.

• One is called the Master.
• All the other ones are called Slaves.

There is also a third party involved and that is the User. The User uses tools to control and monitor the application. In the Visual Basic context those tools are: text boxes, labels, numericupdown's and pushbuttons.
The communication between the User, the Master and the Slaves follows certain rules.
Rule number one is that there are two separate communication channels:

1. Communication between the user and the Master. This communication channel is used to start and stop the Master and to start and stop the slaves. In order to do that the user uses the Start Button, the Stop Button, the Cancel Button and the End Button. In some cases also numericupdown's are used. The numerics involved are called requests and display variables
2. Communication between the Master and the Slaves. This communication channel is primarily used to inform the Slave about the specifics what to do and to inform the Master when finished. The numerics involved is the STATE array.

The rules involved are:

1. Rule nr 1: There are two communication channels. One between the user/outside world and the Master. One between the Master and the Slaves.
2. Rule nr 2: Each of the two communication channels requires its own set of variables (integers, numerics or arrays).
   • For user - master communication this are the variables npreq, cancelreq and holdreq.
   • For master - slave communication this is the variables np and the array STATE(i).
3. Rule nr 3: is that the link between the two communication channels is controlled by the Master Program. The Master Program consists of an endless loop. At the beginning of the loop the connection between both communication channels is established.
4. Rule nr 4: a minimal use of events.
5. Rule nr 5: only the Slaves are implemented as Backgroundworkers.

the variables npreq and np

The two parameters npreq and np are used to control the number of processors or parallel branches.

• npreq is a variable meaning the number of processors and is used for the communication between user and master.
• np is a variable also meaning the number of processors and is used for the communication between master and slave.

             -------------------------------------------------------     
            |                        (1)|                        (3)|    
*****************(1)(3)                 V                           V    
*StartButton EH *----               **********                  *********
*****************    |   *******    * MASTER *      *******     * Slave *
                     |-->*npreq*--->*        *----->*  np *---->*       *
*****************    |   *******    *  BGW   *      *******     *  BGW  *
*CancelButton EH*----               **********                  *********
***************** (6)                (2)(4)(7)                     (5)(8)
                           Figure 1: Communication channels

1. The StartButton EventHandler starts the Master BackGroundWorker, after the StartButton is pressed. npreq is set equal to 1
2. The Master BackGroundWorker will execute a continuous loop. The loop consists of two parts. At the beginning of the loop np is set equal to npreq. That means to 1. The second half are the calculations of one iteration of the planet simulation. This part will be executed continuously. Because np = 1 all the calculations will be performed continuously by the Master.
3. After the StartButton is again pressed the first Slave BackGroundWorker will be started (as an event). npreq will be increased and set to 2.
4. The Master at the beginning of the loop will set np equal to npreq. Because np = 2 the Master will perform 50% of the calculations of each iteration. That means half of all the calculations.
5. The Slave will immediate start to execute a continuous loop. This loop is identical as the calculations of the Master . Because np = 2 the Slave will also perform 50% the calculations of each iteration. That means the second half of all calculations.
6. The CancelButton Eventhandler decreases npreq with one (set to 1), after the CancalButton is pressed.
7. The Master at the beginning of the loop will set np equal to npreq. Because np is now again equal to 1 the Master will perform all the calculations of the simulation.
8. The Slave 1 (processor 2) because np = 1 will terminate.

In this text the actual communication between the Master and the Salves is not discussed. That comes next.

Processor Control and Synchronization

In order to control and to synchronize the communication between the Master and the Slaves a STATE array variable is used.

Master np = npreq Start Loop Set all STATE array variables equal to 1 perform calculations STATE(1) = 0 Wait all STATE array variables equal to 0 End Loop

Slave 1 Start Loop If STATE(2) = 1 Then perform calculations STATE(2) = 0 End if End LOOP

Figure 2: Synchronization

(*) In order to understand the above program it is important to remark that the sentence "Set all STATE array variables equal to 1" means: only for the relevant threads.

• When np = 1 this means: none.
• When np = 2 : only state (2)
• When np = 3 : state (2) and state(3)

Parallel Programming - Load Sharing

In order to take care that the calculations are equally shared among the different threads or processor: a Loop is used.
The Loop starts with the Start Loop statement and ends with the End Loop statement.

Master np = npreq Start Slave 1, 2 Start Loop Set all STATE variables equal to 1 For i = 0 to maxi step np perform calculations next i STATE(1) = 0 Wait all STATE variables equal to 0 End Loop

Slave 1 Start Loop If STATE(2) = 1 Then For i = 1 to maxi step np perform calculations next i STATE(2) = 0 End if End LOOP

Slave 2 Start Loop If STATE(3) = 1 Then For i = 1 to maxi step np perform calculations next i STATE(3) = 0 End if End LOOP

Figure 3: Load Sharing

The above program, in the case that maxi is 10, means :

1. when np = 1 the Master performs all calculations for i = 0,1,2...9,10
2. when np = 2 the Master performs the calculations for i = 0,2,4,6,8,10
   Slave 1 performs the calculations for i = 1,3,5,7 and 9
   This means a load sharing of 50%

   When np = 3 the Master performs the calculations for i = 0,3,6 and 9

   Slave 1 performs the calculations for i = 1,4,7 and 10

   Slave 2 performs the calculations for i = 2,5 and 8

   This means (roughly) a load sharing of 33 %

   When np = 4 the load sharing is roughly 25 %

Cancel Request

The Cancel Request is in the CancelAsyncPushbutton handler implemented with a CancelReq numeric (Set to 1)
The difference between a cancel request and a hold request that:

• In the case of a cancel request the background worker is terminated.
• In the case of a Hold request the simulation is stopped but the Backgroundworkers are not terminated.

There are two types of cancel requests:

• Individual cancel requests. That means only one Backgroundworker is terminated. This is the case when the number of processors is decreased with one. That is the parameter npreq
• Total cancel requests. That means all Background workers are terminated. This is the case when the End Push button is pressed by the EndAsyncPushbutton Handler. npreq is set to zero.

The both cancel requests are processed by the Master. When the master detects that that npreq is smaller than np the Master changes the STATE(np) array parameter to the CancelSt and decreases np with one. This is repeated as many times as required until npreq = np.
When a Slave receives the Cancelst command the slave (program) will end. That means the BackGroundWorker terminates its execution.

Hold Request

BackgroundworkerBackgroundworker The Hold Request is implemented with a holdreq numeric
The difference between a cancel request and a hold request is:

• In the case of a cancel request the background worker is terminated.
• In the case of a Hold request the simulation is stopped but the Background workers are not terminated.

There are two types of hold requests:

• Operator generated hold requests. This is the case when the operator selects the Stop Pushbutton. The handler sets the holdreq to 2.
• Program generated hold requests. This is the case when the program reaches it target. In the planet programs this is after a selected number of revolutions of planet 1. This is the parameter holdrev

Both types of of requests are handled by the Master. The number of revolutions of planet 1 is stored in the parameter rev(1). When the master detects that holdreq = 2 or that rev(1) = holdrev , in both cases holdreq is set equal to 1 and the he Master changes the STATE array parameters to the HoldSt value.
When a slaves receives the Holdst command the slave (program) will perform the sleep operation. That means that the BackGroundWorker stays active but its load changes to zero.

Disadvantage Backgroundworker

In the above explanation of Parallel Programming (Figure 1, Figure 2 and Figure 3) the Master is implemented as a Backgroundworker.
The general problem with the Backgroundworker is that there exist no direct communication between the Backgroundworker and the control form. That means the Backgroundworker cannot directly read from and write values to the tools (Boxes, Labels etc) of the control form.
The following Microsoft MSDN document showed two examples: BackGroundWorker. Those two examples use the events ProgressChanged and RunworkerCompleted. The problem is that that solution is rather complex specific if many BackGroundworkers are involved.
The Visual Basic 2010 Programs VStest2 and Planet follow that approach.
In the case of the VB program Planet this means:

There are 5 Backgroundworkers, 5 ProgressChanged event handlers and 5 RunworkerCompleted event handlers.

The Visual Basic 2010 programs PlanetPP and FibonacciPP follow a different approach:

In both the Master is implemented as a subroutine with the name "Master" and directly called from the StartAsyncButton EH. That means the Master is an integral part of the StartAsyncButton EH.

• This approach is much simpler and the performance is even better.
• A separate advantage is that this philosophy gives the best performance (no overhead) in case of one thread i.e. when no parallel programming is required. This means that the Master performs all calculations of the application.

**************** (1) ---------------------- *StartButton EH*--------------- | (4) | **************** | | | V V | ********** ********* **************** (3) ******* -->* * ******* * Slave * * NProcT EH *----->*npreq*----->* Master *----->* np *---->* * **************** (6) ******* -->* * ******* * BGW * | ********** ********* **************** (9) ******** | (2)(4)(7)(10) (5)(8) * EndButton EH *---->*cancel*-- **************** ******** Figure 4: Communication channels

1. After the StartButton is pressed, the StartButton EventHandler calls the Master (subroutine). npreq is set equal to 1
2. The Master will execute as a continuous loop. The loop consists of two parts. At the beginning of the loop np is set equal to npreq. That means to 1. The second half are the calculations of one iteration of the planet simulation. This part will be executed continuously.
   Because np = 1 all the caluations will be performed continuously by the Master.
3. After the NProcT numeric is increased and set to 2, the NProcT EventHandler will start the first Slave BackGroundWorker. npreq will be set equal to NProcT and set to 2.
4. The Master at the beginning of the loop will detect that npreq is greater than np and start Slave 1. np will be set equal to npreq.
   Because np = 2 the Master will perform 50% of the calculations of each iteration. That means half of all the calculations.
5. The Slave will immediate start to execute a continuous loop. This loop is identical as the calculations of the Master . Because np = 2 the Slave will also perform 50% the calculations of each iteration. That means the second half of all calculations.
6. After NprocT is decreased and set to 1 the NprocT Eventhandler will set npreq equal to NProcT, that means to 1.
7. The Master at the beginning of the loop will detect that npreq is smaller than np and set STATE(2) equal to CancelSt command for Slave 1. np will be set equal to npreq.
   Because np is now again equal to 1 the Master will perform all the calculations of the simulation.
8. Slave 1 (processor 2) because STATE(2) is equal to Cancelst command, will terminate.
9. After the EndButton is pressed the EndButton EH will set the the cancelreq.
10. The Master will, because the cancelreq is set, terminate.
11. when the EndButton again is pressed the application will end.

DOevents and Sleep

In the microsoft 2003 Excel and Visual Basic context if you temporarily want to give control to the operating system the statement DOevents is used. This is required for example if you want to update the values on a form. The statement is required if the program is in an almost endless loop, which is the case in simulation programs if you want to test the CPU with 100% load.
In the case of Visual Basic 2010 the equivalent is the Applications.DOevents statement. The duration is roughly 0.016 m sec.

The sleep function is way to temporarily stop program (Backgroundworker) operation.
The full statement is: System.Threading.Thread.Sleep(1) . The 1 means 1 m second. In general n means n m second.
The sleep function in the programs Planet and PlanetPP are used in the Hold mode.

DOevents implementation

Visual Basic 2010 recognizes two types of operating modes: The debug mode and the publish mode.
In both modes you can execute the program, however the publish mode is faster.
The user expects that the results of the debug mode and the publish mode are identical.
That is not the case.

1. In both modes you can execute the program, however the performance in publish mode is faster.
2. Secondly there is no guarantee that if the programs works in the debug mode, the same program also works in the publish mode. The reason is in some cases the DOevents function statement.

Many programs require what is called a WAIT function. A WAIT function is normally implemented as a DO LOOP in which certain tests are done. When one of those tests is true the WAIT function is finished, the DO LOOP terminates and the program continues.

The DOEvents function is not used in the Slave Backgroundworkers in those DO LOOPs.

In the PlanetPP program in the Master is implemented as subroutine which is called in the StartAsyncButton Event Handler. The Master Subroutine requires two WAIT functions that means two DO LOOP statements. Each of those loops require the DOEvents statement for proper operation. In the Debug mode they are not required !. The same for the FibonacciPP program, but only once.

The planetS program requires one DOEvents function.

The Planet program does require the DOEvents function because the Master is implemented as a BackGroundWorker.
However the program requires a piece of what is called "dead code". This code is only the END statement and is required within the DO LOOP statements of the Master BackGroundWorker, If you remove the END statement the program works in the Debug mode, but not in the Publish mode. This all seems rather strange but it is true. The reason is unknown.

Reflection

The INTEL philosophy requires Parallel Programming when different Cores are used. There is nothing wrong with that if new hardware approaches require that.
However, this becomes obligatory when each core supports Hyper-Threading (Virtual Processors) in order to use the CPU for a 100%. The results of my tests indicate that this philosophy does not improve overall performance and does not benefit the extra work involved of parallel programming.
I expect that the best overall performance only can be reached, when the number of threads is equal to the number of Cores.

Feedback