概述
本页描述如何使用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
以下是一些简短的说明,详细信息将在后面给出。
- 在Unix系统下,多线程需要`cthreads`单元,正如在Multithreaded Application Tutorial中所述。
- 出于速度考虑,推荐使用`cmem`堆管理器,尽管在此示例中它并没有任何差异。
- 并行过程`DoSomethingParallel`会获取一些固定和预定义的参数。
- `Index`定义了此次调用应完成的工作块。
- `Data`是指针,作为第四个参数传递给`ProcThreadPool.DoParallel`。它是可选的,你可以自由地使用它来做任何事情。
- `Item`可用于访问线程池的一些更复杂的功能。
- `ProcThreadPool.DoParallel`的工作方式就像一个普通的过程调用。当它完全运行时返回,这意味着所有线程都已完成它们的工作。
- 输出显示了典型的多线程行为:调用的顺序是不确定的。多次运行可能会导致不同的顺序。
特性
并行运行一个过程意味着:
- 一个过程或方法从任意的StartIndex到任意的EndIndex执行,带有Index。
- 一个或多个线程并行执行这些索引。例如,如果Index从1运行到10,并且池中有3个线程可用,那么3个线程将同时运行三个不同的索引。每次一个线程完成一个调用(一个索引)时,它就会分配下一个索引并运行它。结果可能是:线程1执行索引3、5、7,线程2执行1、6、8、9,线程3执行2、4、10。
- 线程的数量在运行期间可能会变化,并且没有最小线程数的保证。在最坏的情况下,所有索引都将由一个线程执行,即线程本身。
- 最大线程数是根据当前系统的良好猜测进行初始化的。它可以通过以下代码随时手动设置:
ProcThreadPool.MaxThreadCount := 8;
- 你可以为每个过程设置最大线程数。
- 一个并行过程(或方法)可以递归地调用其他并行过程(或方法)。
- 线程是重用的,这意味着它们不是为了每个索引而销毁和创建的,而是存在一个全局的线程池。在双核处理器上,将有两个线程完成所有工作,即主线程和池中的一个额外线程。
开销、减速
开销在很大程度上取决于系统(核心的数量和类型、共享内存的类型、关键部分的速度、缓存大小)。以下是一些一般性的提示:
- 每个工作块(索引)应该至少占用几毫秒的时间。
- 开销与并行过程的递归级别无关。
与MTProcs单元无关的多线程开销,但仅仅是由于当今的计算机架构而产生的:
- 一旦创建了一个线程,你的程序就变成了多线程,内存管理器必须使用关键部分,这会减慢速度。因此,即使你没有用这个线程做任何事情,你的程序也可能会变慢。
- 在一些系统上,对于多线程来说,`cmem`堆管理器要快得多。在我的基准测试中,特别是在Intel系统上,特别是在OS X下,速度差异可能超过10倍。
- 字符串和接口是全局引用计数的。每次访问都需要一个关键部分。因此,在多个线程中处理字符串几乎不会提高速度。请使用`PChars`代替。
- 每个工作块(索引)应该在内存的不同部分上工作,以避免交叉缓存更新。
- 不要处理大量的内存。在一些系统上,仅一个线程就足以填满内存总线速度。当达到内存总线的最大速度时,任何额外的线程都会减慢速度,而不是使其更快。
设置过程的最大线程数
你可以将过程的最大线程数作为第五个参数指定。
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;
这可以节省大量重构工作,并使并行过程更加易读。