Parallel procedures

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

概述

本页描述如何使用MTProcs单元并行运行单个过程,该单元简化了并行运行过程并实现并行算法。

并行过程和方法通常出现在并行算法中,并且一些编程语言为它们提供了内置支持(例如gcc中的OpenMP)。有关向FPC添加此类语言功能的计划,请参阅OpenMP支持。将这些内容嵌入到语言中可以节省一些键入,并允许编译器生成开销较小的代码。另一方面,有许多方法可以将单线程代码段转换为并行代码。事实上,简单的方法往往会减慢代码速度。为了获得良好的结果,必须指定一些编译器无法猜测的参数。例如,请参见OpenMP和OpenCL的大量设置和讨论。你需要并行算法。MTProcs有助于实现并行算法。

获取MTProcs

单元mtprocs.pas是multithreadprocslaz.lpk包的一部分,该包不需要其他包,只需要FPC >= 2.6.0。

你可以在sourceforge上找到其源代码:

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

或者在Lazarus的components/multithreadprocs中找到。

一如既往:在IDE中打开一次multithreadprocslaz.lpk包,以便它学习路径。 要在你的项目中使用该包:使用“IDE菜单/包/打开最近的包/.../multithreadprocslaz.lpk/更多/添加到项目”将其用于当前项目。或者通过项目检查器添加它。

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: 以下是一个简短的示例,它并不执行任何有用的操作,但展示了并行过程的外观以及如何调用它:

program Test;  
  
{$mode objfpc}{$H+}  
  
uses  
  {$IFDEF UNIX}  
  cthreads, cmem,  
  {$ENDIF}  
  MTProcs;  
  
// - 一个简单的并行过程  
procedure DoSomethingParallel(Index: PtrInt; Data: Pointer; Item: TMultiThreadProcItem);  
var  
  i: Integer;  
begin  
  writeln(Index); // 输出当前索引  
  for i:=1 to Index*1000000 do ; // 执行一些工作  
end;  
  
begin  
  ProcThreadPool.DoParallel(@DoSomethingParallel,1,5,nil); // 地址,起始索引,结束索引,可选数据  
end.

输出结果将类似于:

2
3
1
4
5

以下是一些简短的说明,详细信息将在后面给出。

特性

并行运行一个过程意味着:

ProcThreadPool.MaxThreadCount := 8;

开销、减速

开销在很大程度上取决于系统(核心的数量和类型、共享内存的类型、关键部分的速度、缓存大小)。以下是一些一般性的提示:

与MTProcs单元无关的多线程开销,但仅仅是由于当今的计算机架构而产生的:

设置过程的最大线程数

你可以将过程的最大线程数作为第五个参数指定。

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

This can be useful, when the threads work on the same data, and 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:

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;

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:

if not Item.WaitForIndexRange(3,5) then exit; // wait for 3,4 and 5

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:

try
  ...
  ProcThreadPool.DoParallel(...);
  ...
except
  On E: Exception do ...
end;

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

Synchronize

When you want to call a function in the main thread, for example to update some gui element, you can use the class method TThread.Synchronize. It takes as arguments the current TThread and the address of a method. Since 1.2 mtprocs provides a threadvar CurrentThread, which makes synchronizing simple:

TThread.Synchronize(CurrentThread,@YourMethod);

This will post an event on the main event queue and wait until the main thread has executed your method. Keep in mind that a bare fpc program does not have an event queue. A LCL or fpgui program has it.

If you create your own TThread descendants, you should set the variable in your Execute method. For example:

procedure TYourThread.Execute;
begin
  CurrentThread:=Self;
  ...work...
end;

示例:并行循环

本示例逐步解释如何将一个循环转换为一个并行过程。该示例计算整数数组“BigArray”中的最大值。

原始循环

type
  TArrayOfInteger = array of integer;

function FindMaximum(BigArray: TArrayOfInteger): integer;
var
  i: PtrInt;
begin
  Result:=BigArray[0];
  for i:=1 to length(BigArray)-1 do begin
    if Result<BigArray[i] then Result:=BigArray[i];
  end;
end;

分配工作

工作应平均分配给n个线程。为此,将BigArray分割成大小相等的块,并使用外层循环遍历每个块。通常,n是系统中的CPU/核心数量。MTProcs有一些实用函数来计算块大小和数量:

function FindMaximum(BigArray: TArrayOfInteger): integer;
var
  BlockCount, BlockSize: PtrInt;
  i: PtrInt;
  Index: PtrInt;
  BlockStart, BlockEnd: PtrInt;
begin
  Result:=BigArray[0];
  ProcThreadPool.CalcBlockSize(length(BigArray),BlockCount,BlockSize);
  for Index:=0 to BlockCount-1 do begin
    Item.CalcBlock(Index,BlockSize,length(BigArray),BlockStart,BlockEnd);
    for i:=BlockStart to BlockEnd do begin
      if Result<BigArray[i] then Result:=BigArray[i];
    end;
  end;
end;

添加的几行代码适用于任何循环。最终可以编写一个工具来自动化这一过程。

现在工作被分割成了小块。接下来,这些小块必须变得更加独立。

局部变量和共享变量

对于循环中使用的每个变量,你必须决定它是由所有线程使用的共享变量,还是每个线程都使用自己的局部变量。共享变量BlockCount和BlockSize仅被读取且不更改,因此不需要对它们进行处理。但是,像Result这样的共享变量将被所有线程更改。这可以通过同步(例如临界区)来实现,但这样速度较慢,或者每个线程可以使用一个局部副本,稍后将这些局部变量合并。

以下是一个解决方案,它将“Result”变量替换为一个数组,该数组在最后进行合并:

function FindMaximum(BigArray: TArrayOfInteger): integer;
var
  // 共享变量
  BlockCount, BlockSize: PtrInt;
  BlockMax: PPtrInt;
  // 局部变量
  i: PtrInt;
  Index: PtrInt;
  BlockStart, BlockEnd: PtrInt;
begin
  ProcThreadPool.CalcBlockSize(length(BigArray),BlockCount,BlockSize);
  BlockMax:=AllocMem(BlockCount*SizeOf(PtrInt)); // 为局部变量分配空间
  // 计算每个块的最大值
  for Index:=0 to BlockCount-1 do begin
    // 计算块的最大值
    Item.CalcBlock(Index,BlockSize,length(BigArray),BlockStart,BlockEnd);
    BlockMax[Index]:=BigArray[BlockStart];
    for i:=BlockStart to BlockEnd do begin
      if BlockMax[Index]<BigArray[i] then BlockMax[Index]:=BigArray[i];
    end;
  end;
  // 计算所有块的最大值
  // (如果你有数百个线程,则有更好的解决方案)
  Result:=BlockMax[0];
  for Index:=1 to BlockCount-1 do
    Result:=Max(Result,BlockMax[Index]);

  FreeMem(BlockMax);
end;

这种方法简单明了,可以自动化。不过,此过程将需要程序员提供一些提示。

DoParallel

最后一步是将内部循环移入子过程,并用DoParallelNested调用替换循环。

...
{$ModeSwitch nestedprocvars}
uses mtprocs;
...
function TMainForm.FindMaximum(BigArray: TArrayOfInteger): integer;
var
  BlockCount, BlockSize: PtrInt;
  BlockMax: PPtrInt;

  procedure FindMaximumParallel(Index: PtrInt; Data: Pointer;
                                Item: TMultiThreadProcItem);
  var
    i: integer;
    BlockStart, BlockEnd: PtrInt;
  begin
    // 计算块的最大值
    Item.CalcBlock(Index,BlockSize,length(BigArray),BlockStart,BlockEnd);
    BlockMax[Index]:=BigArray[BlockStart];
    for i:=BlockStart to BlockEnd do
      if BlockMax[Index]<BigArray[i] then BlockMax[Index]:=BigArray[i];
  end;
var
  Index: PtrInt;
begin
  // 将工作分割成大小相等的块
  ProcThreadPool.CalcBlockSize(length(BigArray),BlockCount,BlockSize);
  // 分配局部/线程变量
  BlockMax:=AllocMem(BlockCount*SizeOf(PtrInt));
  // 计算每个块的最大值
  ProcThreadPool.DoParallelNested(@FindMaximumParallel,0,BlockCount-1);
  // 计算所有块的最大值
  Result:=BlockMax[0];
  for Index:=1 to BlockCount-1 do
    Result:=Max(Result,BlockMax[Index]);
  FreeMem(BlockMax);
end;

这主要是复制和粘贴,因此同样可以自动化。

示例:并行排序

mtputils单元包含函数“ParallelSortFPList”,它使用mtprocs对TFPList进行并行排序。必须提供一个比较函数。

procedure ParallelSortFPList(List: TFPList; const Compare: TListSortCompare; MaxThreadCount: integer = 0; const OnSortPart: TSortPartEvent = nil);

此函数使用并行归并排序算法。参数MaxThreadCount传递给DoParallel。0表示使用系统默认值。

可选地,你可以提供自己的排序函数(OnSortPart)来对每个单线程的部分进行排序。例如,你可以通过快速排序对块进行排序,然后再进行合并。这样你就拥有了一个“并行快速排序”。有关快速排序的示例实现,请参见TFPList.Sort。

使用嵌套过程

procedure DoSomething(Value: PtrInt);
var
  p: array[1..2] of Pointer;

  procedure SubProc(Index: PtrInt; Data: Pointer; Item: TMultiThreadProcItem);
  begin
    p[Index]:=Pointer(Value); // 可以访问局部变量和参数!
  end;

var
  i: Integer;
begin
  ProcThreadPool.DoParallelNested(@SubProc,1,2);
end;

这可以节省大量重构工作,并使并行过程更加易读。

See also