Intel® Cilk Plus 中的左侧和右侧 holder

本文将针对 Cilk 和 TBB 编程人员都感兴趣的一个主题进行讨论,即,关于 Intel® Cilk 中 holder 和 TBB 中的类似模式,了解相关内容对您利用这些框架进行编程非常实用。本文探讨的关键点是“左侧 holder”与“右侧 holder”之间的差异以及每种 holder 适用的场景。

两类 holder

Cilk Plus 中的“holder”是超类对象,支持归约操作 op“忘记”其中一个值。共有两种类型的 holder:

  • “左侧 holder”,其中 x op y x.
  • “右侧 holder”,其中x op y y.

TBB 无法像 Cilk 一样为 holder 提供直接支持,但可利用 tbb::parallel_reduce 支持并行归约,您可以为归约操作指定任何一种 op 变量。对于TBB 和 Cilk,op 相互关联但不可代替。在左侧 holder 中对序列 a b c ... z a 的结果进行归约,在右侧 holder 中对 z 的结果进行归约。以下是在 Cilk Plus 中应用右侧 holder 的一种方式:

    #include <cilk/reducer.h>
    template<typename U>
    class RightHolder {
        struct Monoid : cilk::monoid_base<U> {
            static void reduce(U *left, U *right) {
                swap(*left,*right);
            }
        };

        cilk::reducer<Monoid> impl;
    public:
         inline U& get_view() {
            return impl.view();
        }
    };

顺序 reduce 必须采用 *left = *left op *right,并假设 *right 将永不再使用。调用 swap 可实现这一目标,并且在某些情况下比执行 *left=*right 更高效。在 C++0x中,利用“移动赋值操作(move assignment)”而不是 swap可能比较合适。.左侧 holder 与之类似,但删除了 swap 。因此,左侧 holder 具有稍高的效率,即使在 U 类型不支持 swap. 时也可发挥作用。如上所述,针对左侧 holder 在 a 中对序列 a b c ... z 的结果进行归约,针对右侧 holder 在 z 中对结果进行归约。因此,如果您正在利用最终结果,使用哪类 holder 显而易见。但是有时,在将使用最终结果的情况下使用 holder,仅中间结果受到影响。以下三节针对本使用案例提供实例,为您选择左侧 holder 和右侧 holder 提供建议。

模式 1:可选的循环传递相关性

该模式时,可选择性地消除循环传递相关性,但消除代价高昂。利用右侧 holder 减少实际并行化所需开销,而无需为潜在并行化支付开销。以下是该模式的大致情况,在串行编程中非常普遍。

    x = initial_value;
    for( int k=0; k<n; ++k ) {
        foo(x);
        x = next(x);
    }

假定并行运行多个 foo(x) 调用非常安全。唯一一件能阻止我们并行执行迭代的方式是赋值 x=next(x)。这称为“循环传递相关性”。有时,通过转换代码可以消除这种相关性。例如,如果 next(x) 为“x+c”,则 foo 调用的 x 的值通常是 foo(initial_value+k*c)。假设我们可以创建一个函数 kth(initial_value,k),我们可以归纳这种转换。该函数 kth 计算进入 kth 迭代时,x 所拥有的值。常见的转换是:

    x = initial_value;
    cilk_for( int k=0; k<n; ++k ) {
        foo(xkth(initial_value,k));
        x = next(x);
    }
    x = kth(initial_value,n);

进行此类手动转换时,如果在循环之后使用 x,不要忘记计算 x 的最后一个值。有时,kth 的评估开销比 next 要高很多,这可能会抵消并行化带来的益处。理想的解决方案是,评估连续性迭代时利用 next,当我们不知道 x 之前的值时,仅使用 kth。例如,在 TBB 版本的典型查找器示例中,x 是充满计数器的 std::vector。计数器通过 foo 运算,由多个跨步值实现改进。在该代码中,next 无需执行任何操作,而 kth需要进行一些计算来计算每个矢量元素。以下我们将介绍如何利用 holder 实施理想的解决方案。利用特殊值将 holder 链条(view)定义为未经初始化。当值为默认值时,情况最为简单。例如,在“典型”示例中,x 是通常不为空的 std::vector,因此空矢量可作为特殊值使用。然后,右侧的 holder 可以达到理想的效果。常用的方法是:

    RightHolder<X> x;
    ...
    x = initial_value;
    cilk_for( int k=0; k<n; ++k ) {
        if( x is default value )
            x = kth(initial_value,k);
        foo(x);
        x = next(x);
    }

为了了解为什么使用右侧比使用左侧 holder 更重要,假设 n==6。串行执行循环如下总结:

每个 ... 代表“foo(x); x=next(x);”。在串行执行过程中,x 从不为默认值。存在许多可能的循环并行执行。以下是验证为什么右侧 holder 更恰当的示例:

三个箭头中的每个箭头是执行串。每个串都有各自的 x 链条。“k=0”串进入初始链条。“k=2”串进入默认的初始值。在连接点上,两个链条缩减为“k=4”串使用的一个链条。当串利用“k=4”执行迭代时,应使用由 k=3 的“x=next(x)”所更新的 x 值,而不是 k=1 的“x=next(x)”之后的 x 值。这样,右侧的链条将被继续进行,左侧的链条被丢弃。这就是右侧 holder 的工作原理。当我写出使用上述模式的 TBB 典型示例时,我错误地对 tbb::parallel_reduce 中的归约操作使用了 x op y x直到最近我才发现这个错误,因为使用归约值的执行步骤非常少。

模式 2:构建对象

该模式有时在串行循环中出现:

    for( int k=0; k<n; ++k ) {
        ExpensiveToConstructObject x;
        ...use x...
    }

如果在 ... 中,无论对象是否为全新构建,程序员都应通过构建和删除对象进行优化,如下所示:

    {
        ExpensiveToConstructObject x;
        for( int k=0; k<n; ++k ) {
            ...use x...
        }
    }

当 ExpensiveToConstructObject 是供暂存空间使用的堆分配阵列时,通常会出现这种情况。尽管转换有助于加快串行优化速度,但阻止了利用 cilk_for 实现并行化,这是由于并行迭代会彼此干扰。我们希望在需要阻止干扰时仅创建 ExpensiveToConstructObject。将 x 置入 holder 可以达到理想的效果:

    {
        LeftHolder<ExpensiveToConstructObject> x;
        for( int k=0; k<n; ++k ) {
            ...use x...
        }
    }

每次串启动 ab initio时,它获得一个新构建的 ExpensiveToConstruct 对象,如其链条一样。链条将在相同串上的后续迭代中传输。在连接点上,其中一个进入串将提供其链条,供向外串使用。无论是左侧还是右侧 holder 都没有关系,因为迭代之间传输或归约返回哪些值都无关紧要。但是,选择 LeftHolder 而非 RightHolder 的理由在于 RightHolder 需要交换操作,而 LeftHolder 不需要。ExpensiveToConstructObject 可能不支持交换操作,或交换操作可能代价高昂。

模式 3:监测“偷窃”

我的关于监测“偷窃”的博文对 holder 的应用进行了说明。出于简单,我使用了左侧 holder,但实际上,如果在那篇博文的示例中使用右侧 holder 也无关紧要。归约通常为“true op true”,因此参数 op 返回哪些值都无所谓。但是,Pablo Halpern 向我指出,在以下情况下应使用右侧 holder。假定函数 spawns 有效,则在 cilk_sync 之后,您希望检测是否有“偷窃”行为存在。然后应使用右侧 holder,如下所示:

    void f() {
        RightHolder<bool> x;
        x.get_view() = true;
        cilk_spawn g();
        cilk_spawn h();
        cilk_sync;
        if( !x.get_view() )
            printf("continuation of g() or h() was stolenn";
    }

如果 g() 或 h() 后的延续被盗,则它将获得 x 新链条,默认初始值为 false。当执行到达 cilk_sync 时,链条出现。使用右侧 holder 确保最终的链条将成为新链条之一(如有链条产生)。这样,x 将在 cilk_sync 后为假值,除非未发生偷窃行为。

总结

Holder 分为左侧和右侧形式。右侧 holder 可用于在并行代码中充分利用可选的循环传递相关性。左侧和右侧 holder 均可用于优化循环中使用的临时对象,此时迭代之间传输的值无关紧要,但左侧 holder 在这种情况下稍有优势。尽管概念直接映射至 Cilk Plus,它们还适用于 tbb::parallel_reduce。

Reportez-vous à notre Notice d'optimisation pour plus d'informations sur les choix et l'optimisation des performances dans les produits logiciels Intel.