Parallel procedures

This is an old revision of Parallel procedures, edited by Mattias2 at . The current revision is 57076.

/* Exceptions */

Overview

This page describes how to run single procedures in parallel using the MTProcs unit, which simplifies running procedures in parallel and simplifies implementing parallel algorithms.

Parallel procedures and methods are often found in parallel algorithms and some programming languages provide built-in support for them (e.g. OpenMP in gcc). See here for the plans adding such language features to FPC. Embedding these things into the language can save some typing and allows the compiler to generate code with less overhead. On the other hand there is no single algorithm to run code in parallel. In fact simple approaches often slows down the code. To get good results one must specify some parameters, which a compiler can not guess. For examples see the vast amount of settings and discussions of OpenMP and OpenCL. You need parallel algorithms. MTProcs helps to implement parallel algorithms.

Getting MTProcs

The unit mtprocs.pas is part of the multithreadprocslaz.lpk package, which can be downloaded via svn:

svn co https://lazarus-ccr.svn.sourceforge.net/svnroot/lazarus-ccr/components/multithreadprocs multithreadprocs 

As always: Open the package multithreadprocslaz.lpk in the IDE once, so that it learns the path. To use the package in your project: Either use IDE Menu / Package / Open recent package / .../multithreadprocslaz.lpk / More / add to project to use it in your current project. Or add it via the project inspector.

Simple example

Here is a short example, that does not do anything useful, but to demonstrate how a parallel procedure looks like and how it is called:

<Delphi> program Test;

{$mode objfpc}{$H+}

uses

 {$IFDEF UNIX}
 cthreads, cmem,
 {$ENDIF}
 MTProcs;

// a simple parallel procedure procedure DoSomethingParallel(Index: PtrInt; Data: Pointer; Item: TMultiThreadProcItem); var

 i: Integer;

begin

 writeln(Index);
 for i:=1 to Index*1000000 do ; // do some work

end;

begin

 ProcThreadPool.DoParallel(@DoSomethingParallel,1,5,nil); // address, startindex, endindex, optional data

end. </Delphi>

The output will be something like this:

2
3
1
4
5

Here are some short notes. The details follow later.

Features

Running a procedure in parallel means:

 ProcThreadPool.MaxThreadCount:=8;

Overhead, slow down

The overhead heavily depends on the system (number and types of cores, type of shared memory, speed of critical sections, cache size). Here are some general hints:

Multi threading overhead, which is independent of the MTProcs units, but simply results from todays computer architectures:

Setting the maximum number of threads for a procedure

You can specify the maximum number of threads for a procedure as the fifth parameter.

<Delphi> begin

 ProcThreadPool.DoParallel(@DoSomethingParallel,1,10,nil,2); // address, startindex, endindex, 
     // optional: data (here: nil), optional: maximum number of threads (here: 2)

end. </Delphi>

This can be useful, when the threads work on the same data, and a too many threads will create so many cache conflicts, that they slow down each other. Or when the algorithm uses a lot of WaitForIndex, so that only a few threads can actually work. Then the threads can be used for other tasks.

Wait for index / executing in order

Sometimes an Index depends on the result of a former Index. For example a common task is to first compute chunk 5 and then combine the result with the result of chunk 3. Use the WaitForIndex method for that:

<Delphi> procedure DoSomethingParallel(Index: PtrInt; Data: Pointer; Item: TMultiThreadProcItem); begin

 ... compute chunk number 'Index' ...
 if Index=5 then begin
   if not Item.WaitForIndex(3) then exit;
   ... compute ...
 end;

end; </Delphi>

WaitForIndex takes as an argument an Index that is lower than the current Index or a range. If it returns true, everything worked as expected. If it returns false, then an exception happened in one of the other threads.

There is an extended function WaitForIndexRange that waits for whole range of Index: <Delphi> if not Item.WaitForIndexRange(3,5) then exit; // wait for 3,4 and 5 </Delphi>

Exceptions

If an exception occur in one of the threads, the other threads will finish normally, but will not start a new Index. The pool waits for all threads to finish and will then raise the exception. That's why you can use try..except like always:

<Delphi> try

 ...
 ProcThreadPool.DoParallel(...);
 ...

except

 On E: Exception do ...

end; </Delphi>

If there are multiple exceptions, only the first exception will be raised. To handle all exceptions, add a try..except inside your parallel method.

Example: Parallel loop

This example explains step by step how to convert a loop into a parallel procedure. The example computes the maximum integer of BigArray.

The original loop

<Delphi> type

 TArrayOfInteger = array of integer;

function FindMaximum(BigArray: TArrayOfInteger): integer; var

 i: Integer;

begin

 Result:=BigArray[0];
 for i:=1 to length(BigArray)-1 do begin
   if Result<BigArray[i] then Result:=BigArray[i];
 end;

end; </Delphi>

Splitting the work

The work should be equally distributed over n threads. The BigArray is split into equal blocks and the loop runs over each block:

<Delphi> function FindMaximum(BigArray: TArrayOfInteger): integer; var

 i: Integer;

var

 BlockCount: LongInt;
 BlockSize: Integer;
 Index: Integer;
 BlockStart: Integer;
 BlockEnd: Integer;

begin

 Result:=BigArray[0];
 BlockCount:=ProcThreadPool.MaxThreadCount;
 BlockSize:=(length(BigArray) div BlockCount)+1;
 for Index:=0 to BlockCount-1 do begin
   BlockStart:=BlockSize*Index;
   BlockEnd:=Min((BlockSize+1)*Index,length(BigArray))-1;
   for i:=BlockStart to BlockEnd do begin
     if Result<BigArray[i] then Result:=BigArray[i];
   end;
 end;

end; </Delphi>