FastFlow多核库设计问题的解决方法

可在www.sciencedirect.com在线获取理论计算机科学电子笔记279（3）（2011）73-84www.elsevier.com/locate/entcsFastFlow多核库的生成版本Zala'nSzugyi1Norbert Pataki2埃奥特维奥斯·洛兰德大学编程语言与语言学系匈牙利布达佩斯摘要如今，编程中最重要的挑战之一是多核处理器的有效使用。许多新的编程语言和库都支持多核编程。FastFlow是最有前途的多核C++库之一。不幸的是，库中出现了一个设计问题。最重要的方法之一是基类中的纯虚函数。此方法支持不同线程之间的通信。虽然，由于虚拟性，它不能是模板函数，因此，线程传递并将参数作为void*指针。基类也不是模板。这不是类型安全的方法。在生成技术的帮助下，我们使图书馆更高效、更安全关键词：多核编程，C++，FastFlow，模板1介绍最近的趋势，增加核心数量的处理器，导致了新的兴趣，est在设计的方法和机制，有效的并行编程的共享存储器的计算机体系结构。这些方法主要基于传统的并行计算方法通常，低级方法仅为程序员提供控制权管理（创建，销毁），同步和数据共享的原语，这些原语通常在互斥（互斥）访问的关键区域中完成。例如，POSIX线程库可以用于此目的。以这种方式对并行复杂应用程序进行编程当然很难;由于内存围栏（用于实现互斥）对核心缓存中复制的数据产生的非平凡影响，调优它们的性能通常更难1电子邮件地址：lupin@ludens.elte.hu2电子邮件：patakino@elte.hu1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.11.03974Z. Szualgyi，N. Pataki/ElectronicNotesinTheoreticalComputerScience279（3）（2011）73事实上，内存围栏是通信密集型（如流）并行应用程序的性能下降的关键来源之一避免内存围栏不仅意味着避免锁，还意味着避免内存中的任何类型的原子虽然存在用于异步对称通信的若干评估的无栅栏解决方案，但是这些结果不能容易地扩展到支持任意流网络所必需提高并发管理对象的抽象层次是减轻程序员工作负担、提高程序效率的重要途径例如，线程可以抽象为更高级别的实体，这些实体可以根据特定的策略在用户空间中进行池化和调度，以最大限度地减少缓存溢出或最大限度地提高内核的负载平衡。同步原语也可以被抽象出来，并与代码中语义上有意义的点相关联，比如函数调用和返回、循环等。这种抽象大大简化了应用程序的手工编码。然而，它仍然太低级，无法有效地自动化par-task代码的优化：这里最重要的弱点是缺乏关于代码意图的信息（习惯用法识别）;过程间/组件优化进一步加剧了这个问题。最近，有一种从高级规范生成程序的趋势。这被称为生成方法，它专注于从更高级别的规范合成实现，而不是转换它们。通过这种方法，程序员的目标被规范捕获。此外，代码生成技术也得到了很好的发展（分段、部分求值、自动编程、生成式编程）[7]。[4]，[13]，[14]，[15]，[16]，[17]，[18]，[19]，[程序员需要通过使用适当的构造来明确地定义解析行为，这些构造明确地约束了控制权、只读数据、累积操作的关联性和对共享数据结构的并发访问FastFlow是一个基于非阻塞无锁/无栅栏同步机制的多核平台并行编程框架。该框架是由一个堆栈的层，逐步抽象出的程序明共享内存并行应用程序。 该堆栈有两个不同的目标：简化应用程序的开发，并使它们非常快速和可扩展。FastFlow特别针对流媒体应用程序的开发模板是C++编程语言的关键元素[15]。它们使数据结构和算法能够通过类型进行参数化，从而在编译时捕获抽象的公共性，而不会在运行时造成性能损失。泛型编程是最近出现的用于编写可重用组件（大多数情况下是数据结构和算法）的编程范例FastFlow的工作线程通过void*指针在彼此之间传递数据，然后由接收线程处理。这对于执行来说是非常必要的。在FastFlow框架的核心，Z. Szualgyi，N. Pataki/ElectronicNotesinTheoreticalComputerScience279（3）（2011）7375抽象类ff节点。它有一个纯虚方法svc，这是应用程序中每个线程的主方法。然而，它需要处理任何类型的数据类型，但虽然它是一个虚函数，但它不能是模板。但是，基类可以是类模板。然而，这种解决方案既不优雅，也不是类型安全的[17]。在本文中，我们提出了我们的解决方案，如何FastFlow库可以扩展到类型安全。我们将抽象基类模板化，通过巧妙地重复模板模式，用静态多态代替动态多态这样一方面系统将是类型安全的，另一方面可以消除方法的虚拟性，因此系统变得更有效。本文的组织结构如下。在第2节中，展示了FastFlow库，并给出了从程序正确性角度来看有风险的典型示例。我们在第3节中提出了一种可以通过C++的类型系统来克服这个问题的方法，在第4节中描述了实现细节。第5节和第6节介绍了我们的管道和缓冲器实现。 在第七章中，我们通过一个例子演示了我们扩展的FastFlow库的使用。最后，本文在第8节中结束。2FastFlowFastFlow是最有效的多核C++框架之一。它类似于Intel的TBB，提倡一种基于模式（骨架）的并行编程方法。FastFlow旨在提供一组底层机制，能够在SCM上运行的线程网络中支持低延迟和高带宽数据流。作为流应用中的典型，这些流被认为是大多数非规则的和异步的。在这些架构上，关键问题是内存围栏，这是保持各种缓存一致所必需的该库为程序员提供了两种基本机制：多生产者多消费者（MPMC）队列和内存分配器。内存分配器构建在MPMC队列之上，可以用OS标准分配器（付出性能代价）或第三方分配器（例如Intel TBB可扩展分配器）替代。FastFlow下的关键直觉是为程序员提供无锁的MP队列和MC队列（可以在管道中用于构建MPMC队列），以支持快速流网络。传统上，MPMC队列是作为被动实体构建的：线程并发同步以访问数据。同步通常由一个或多个原子操作（例如Compare-And- Swap）支持，这些操作的行为就像内存围栏一样。FastFlow设计遵循不同的方法：队列读取器或写入器之间的同步由活动实体（例如线程）仲裁根据它们的角色，我们将这些实体称为ESCOM（E）或Collector（C）;它们实际上从一个或多个无锁的简单生产者简单消费者（SPSC）队列中读取项目，并写入一个或多个无锁的SPSC队列。因此，这需要一个内存拷贝。另一方面，不需要原子操作。76Z. Szualgyi，N. Pataki/ElectronicNotesinTheoreticalComputerScience279（3）（2011）73该解决方案的性能优势来自于相对于存储器围栏的更高的复制速度，该优势进一步增加通过避免由栅栏触发的高速缓存失效。这也取决于复制数据的大小和内存布局。前一点是使用数据指针而不是数据来解决的，并强制数据不被并发写入：在许多情况下，这可以通过使用MPMC队列实现的骨架的语义来导出（例如，这在无状态农场和许多其他情况下得到保证）。当使用动态分配内存时，内存分配器在性能方面起着重要的作用。动态内存分配器（malloc/free）依靠互斥锁来保护多线程下共享数据结构的一致性。因此，使用内存分配器可以巧妙地在无锁应用程序中重新引入锁FastFlow包括自己的自定义内存分配器，专门针对SPMC模式进行了优化。基本假设是，在流应用中，通常，一个线程分配内存，一个或多个其他线程释放内存。这个假设允许开发多线程存储器分配器，其在分配器线程和执行释放的通用线程之间使用SPSC通道，避免使用昂贵的基于锁的协议来维持内部结构的存储器一致性。然而，FastFlow分配器不是通用分配器，它有局限性。让我们考虑以下利用FastFlow库的代码片段：Estrom向worker提供数据，现在它只发送整数。Worker处理数据，并将其传递给另一个Worker或Collector，这取决于FastFlow的初始化。现在它只是将接收到的整数值打印到屏幕上，并将其传递给收集器。 Collector收集Workers完成的计算结果。现在它只接收整数值什么都不做//泛型worker结构Worker：ff：：ff_node{void * svc（void * task）{intn=（int n）;std：：cout“Worker“ff_node：：get_my_id（）<<“已接收任务“*t“\n”;返回任务;}};//gatherer过滤器结构收集器：ff：：ff_node{void * svc（void * task）{intn=（int n）;if（*t==-1）returnNULL;return task;}};//负载均衡器过滤器结构体Eclock：ff：：ff_node{public int findDuplicate（intfindDuplicate）：nDuplicate（int findDuplicate）{Z. Szualgyi，N. Pataki/ElectronicNotesinTheoreticalComputerScience279（3）（2011）7377void * svc（void *）{intn= new int n（n）;--ntask;如果（ntask<0）返回NULL;返回task;}私人：int n;};int main（）函数{farm> farm;String s（String s）;String s（&String s）;std：：move_iterator*> w;for（int i=0;i nworkers; ++i）w.push_back（newWorker）;structBase{ voidf1（）{static_cast *>（this）->f（）;}};结构派生：基础派生>{voidf1（）{//实际实现}};当然，这种模式有其局限性：派生类型不能依赖于运行时信息.然而，在我们的例子中，我们可以在编译时区分发射器，收集器和工人类型，因此我们不需要处理运行时信息。因此，这种限制对FastFlow的使用没有影响78Z. Szualgyi，N. Pataki/ElectronicNotesinTheoreticalComputerScience279（3）（2011）734实现细节在FastFlow中，并行计算的基类是ff节点。这个类有一个名为svc的纯虚方法，它有一个void*参数。所有参与并行计算的类都必须派生自ff节点，并且必须实现成员函数svc。由于svc的参数类型是void*，它可以接受任意数据，但是，它不是类型安全的解决方案。在函数内部，我们需要将参数转换为适当的类型。转换为不正确的类型会导致运行时错误。然而，它可以在没有任何错误或警告消息的情况下编译，这使得bug修 复 更 加 困难。我们的解决方案基于第1.1节3 .第三章。这样，函数svc就不需要是虚的，它的参数类型可以是一个正确类型的指针。参数的类型是ff节点类的模板参数。类ff节点有另一个模板参数，该参数引用其派生类的类型。下面的代码片段显示了类ff node的声明：模 板 类 Derived ， classT> classff_node;FastFlow中有三种类型的节点：发射器、工作器和收集器或回退。 任务由发射器调度。工人们独立地计算它们最后，收集器收集结果。ff农场类表示农场骨架。最初，该类有两个模板参数，即负载平衡器的类型和收集器的类型。 这些模板参数有默认值，因此程序员可以跳过它们，让FastFlow使用默认类型。我们另外定义了ff farm的五个模板参数。前三个模板参数指的是发射器、工作器和收集器的类型，第四个参数指的是作为成员函数svc参数传递的类型，第五个参数是一个布尔值，它设置FastFlow使用循环还是非循环缓冲器。最后两个是原始的模板参数。缓冲器的详细信息见第6节。由于fffarm是ff node的子类，因此它需要将自身传递给ff node的模板参数。下面的代码片段显示了ff场类的声明。模板类E，W 类 ，C 类 ，T类，bool is_circular= false，class lb=ff_loadbalancer E ， W ， C ，T>，class gt=ff_gatherer C，W，T>>ff_farm类：public ff_node ff_farm E，W，C，T，is_circular，lb，gt>，T>;有几种场方案不需要发射器或收集器类型。在FastFlow的原始实现中，这不是问题。程序员只是跳到添加发射器或收集器到农场。在我们的解决方案中，程序员需要指定各种节点的类型：发射器，工人和收集器。为了解决这个问题，我们创建了一个名为Void的类。这个类也是ff node类的一个子类，它有一个模板参数，表示成员函数svc的参数类型。这个类实现了svc对象-Z. Szualgyi，N. Pataki/ElectronicNotesinTheoreticalComputerScience279（3）（2011）7379BER函数，但是在该实现中，该函数什么也不做。实例化ff场，程序员可以使用Void类型来指示不需要发射器或收集器类型。Void类的定义如下：模板类T>结构体Void： ff：：ff_node Void，T>{T*svc（ T*task）{返回0;}};5管道FastFlow还支持高级管道模式流水线的框架类称为ff流水线。 管道包含阶段，一个阶段可以是独立的ff节点或场骨架。 在原始版本中，流水线将阶段存储在ff节点 * 的向量中，其中ff节点是阶段的基本类型，并且虚拟函数svc进行计算。在我们的解决方案中，动态多态性被静态多态性取代，这种方法不起作用。虽然stage类必须将自己添加为ff节点的模板参数，但它们的基本类型将是不同的。因此，它们不能存储在一个向量中。为了克服这个问题，我们将类ff pipeline定义为模板类，其模板参数是boost：：mpl：：list [1，20]。这个模板参数定义了阶段的类型。vector存储void* 指针，模板元程序-在模板参数的帮助下-将它们转换为正确的类型。这个强制转换过程将在编译时完成，以保持类型安全，并且对程序员是隐藏的在FastFlow的原始版本中，ff类流水线通过ff节点和虚函数的接口来处理阶段。请参见下面的示例：for（int i=0; i ++i）<{stage_list[i]->do（）}我们的解决方案应用以下模式：template classtypes>structff_pipeline{std：：vector void*> stages;void do（）{多奥<0,boost：：mpl：：size types>：：value>：：do（stages）;}template intI， intN>structdo_aux{static void do（std：：vector void*> stages）{静态转换<类型化boost：：mpl：：在类型化时，boost：：mpl：：int_I>80Z. Szualgyi，N. Pataki/ElectronicNotesinTheoreticalComputerScience279（3）（2011）73>：：type>（stages[I]）->do（）;do_stages_auxI+1，boost：：mpl：：size types>：：value>：：do（stages）;}};template int N>structdo_aux N，N>/* specialization */{public static void do（std：：vector void*>）{};/**......我的天！* */};我们的解决方案基于递归模板实例化[1]。结构体do aux具有两个模板参数：I是循环变量，N是类型的大小。这个结构体有一个名为do的静态成员函数，它将相应的stage转换为正确的类型并调用其do成员函数。之后，它用I+1和N实例化自己，并递归调用其do成员函数。当I等于N时，选择do aux的专用版本。当它的静态成员函数什么也不做时，递归将被停止。计算从struct ff pipeline的成员函数do开始。它用0和类型符的大小实例化结构do aux，并调用其静态成员函数。作用域boost：：mpl中的实体在[20]中描述。下面的示例显示了如何在FastFlow中创建管道：structStage1：ff_node Stage1，my_data_type>; structStage2：ff_nodeStage2，my_data_type>;//...typedef boost：：mpl：：vector Stage1，Stage2>：：type stage_types; ff_pipelinestage_types，my_data_type>* pipe =new ff_pipeline stage_types，my_data_type>（）; pipe->add_stage（new Stage1（））;pipe->add_stage（new Stage2（））;从ff节点派生的结构体Stage1和Stage2是管道的阶段，阶段类型引用它们的类型。 ff管道就是用它实例化的。在最后两行中，添加了这些阶段虽然ff管道的模板参数引用了阶段的类型，但它们的结构必须在编译时已知。因此，它引入了使用的限制。然而，在大多数情况下，管道的结构是在编译时定义的，因此它不是一个真正的限制。6布赫莱尔斯FastFlow的原始版本可以使用圆形或非圆形缓冲器作为工作线程之间的通道。这些缓冲器存储void*，以便能够处理不同类型的数据。默认情况下使用非循环缓冲器，但程序员可以通过定义预处理器宏来选择另一个缓冲器FF有界缓冲区。下面的预处理器代码片段显示了如何选择合适的缓冲器#ifdefined（FF_BOUNDED_BUFFER）#define FFBUFFER SWSR_Ptr_BufferZ. Szualgyi，N. Pataki/ElectronicNotesinTheoreticalComputerScience279（3）（2011）7381#else// non-circular buffer#defineFFBUFFERuSWSR_Ptr_Buffer #endif后来，FFBUFFER宏被用作缓冲器类型。编写预处理器宏的想法与C++中的现代开发方法背道而驰。代码将变得可读性更低，更难理解，并且预处理器不知道语言的语法。可能的错误只有在编译时（预处理后）才被发现，错误的行号（由编译器呈现）可能会令人困惑，因为它们指的是应用预处理器宏的地方，而不是定义它们的地方另一方面，在我们的类型安全解决方案中，缓冲器需要存储一个指向正确类型的指针，而不是void*，因此它们需要是模板。用预处理器宏定义模板缓冲器会使代码更加混乱。在我们的解决方案中，我们避免使用预处理器宏来定义缓冲器。相反，我们向ff farm添加一个额外的布尔模板参数，名为iscircular，以指示要使用哪种布尔模板。 true值表示我们想要使用圆形缓冲器，false值表示我们选择了非圆形缓冲器。该模板参数的默认值为false。在buffer的定义中，我们应用模板参数作为条件在模板元程序if[1]上，它在编译期间选择适当的缓冲器类型。下面的代码片段显示了这一点，其中T是存储在缓冲器中的类型：if_is_circular，SWSR_Ptr_Buffer T>，uSWSR_Ptr_Buffer T> >：：type buffer;if的定义如下：模板bool条件，class then_，class else_>struct if_{typedef then_type;};模板类then_，class else_>结构if_false>{typedef else_type;}如果参数条件为真，则一般的if结构被选择为实例化，因此类型引用模板类型参数。 如果参数条件为false，则在实例化过程中选择部分专用的if结构，因此type定义模板类型参数else。7例如在本章中，我们展示了第2章的例子，用模板重写从ff节点派生的每个类都用自身和任务类型int实例化。每个类中的函数svc都有一个正确类型的指针，而不是void*。main函数创建场、发射器、工人和收集器类，并开始计算。82Z. Szualgyi，N. Pataki/ElectronicNotesinTheoreticalComputerScience279（3）（2011）73//泛型workerstruct Worker：ff：：ff_node Worker，int>{int* svc（ int* task）{std：：cout“Worker“<<<：：get_my_id（）<<“已接收任务“* 任务“\n”;返回任务;}};//gatherer过滤器struct Collector：ff：：ff_node Collector，int>{int* svc（ int* task）{if（*task==-1）returnNULL;return task;}};//负载均衡过滤器struct EQUIPMENT：ff：：ff_node EQUIPMENT，int>{public int findDuplicate（intfindDuplicate）：nDuplicate（int findDuplicate）{int* svc（int*）{intn= new int n（n）;--ntask;如果（ntask 0）返回NULL;返回task;}私人：int n;};int main（）函数{ff_farm Estrom，Worker，Collector，int> farm;Estrom（TASK_NUM）;捕收剂c;std：：vector ff：：ff_node Worker，int>*>worker; for（int i=0;i

下载后可阅读完整内容，剩余1页未读，立即下载