为什么OpenMP不允许使用!=运算符？

Question

我试图编译以下代码：

#pragma omp parallel shared (j)
{
   #pragma omp for schedule(dynamic)
   for(i = 0; i != j; i++)
   {
      // do something
   }
}

但我遇到了以下错误：error: invalid controlling predicate。

根据OpenMP标准，对于parallel for构造器，它“仅允许”使用以下操作符之一：<，<=，> >=。

我不理解为什么不允许使用i != j。在静态调度的情况下，我可以理解，因为编译器需要预先计算分配给每个线程的迭代次数。但是，我无法理解为什么在这种情况下限制使用此操作符。有什么线索吗？

---

编辑： 即使我使用 for(i = 0; i != 100; i++)，尽管我可以直接使用 “<” 或 “<=”。

- dreamcrash

Answer 1

我向OpenMP开发人员发送了一封电子邮件询问这个问题，得到的答复是:

对于有符号的整型，溢出行为是未定义的。如果我们允许使用!=，程序员可能会得到意外的tripcount计数。问题在于编译器是否能生成用于计算循环的trip count的代码。

对于一个简单的循环，例如：

for( i = 0; i < n; ++i )

如果n≥0，编译器可以确定有'n'次迭代，如果n < 0，则没有迭代。

对于像下面这样的循环：

for( i = 0; i != n; ++i ) 

编译器应该能够确定有'n'个迭代次数，如果 n >= 0; 如果 n < 0，我们就不知道它有多少次迭代。

对于像下面这样的循环：

for( i = 0; i < n; i += 2 )

如果n大于等于0，编译器可以生成代码来计算循环次数（即迭代次数），公式为floor((n+1)/2)； 如果n小于0，则循环次数为0。

对于像下面这样的循环：

for( i = 0; i != n; i += 2 )

编译器无法确定 'i' 是否会到达 'n'，如果 'n' 是奇数呢？

对于以下类似的循环：

for( i = 0; i < n; i += k )

编译器可以生成代码来计算循环次数，如果n >= 0，则为floor((n+k-1)/k)，如果n < 0，则为0，因为编译器知道该循环必须递增计数；在这种情况下，如果k < 0，则它不是一个合法的OpenMP程序。

对于像下面这样的循环：

for( i = 0; i != n; i += k )

编译器甚至不知道变量'i'是在递增还是递减。它也不知道'i'是否会到达'n'，这可能导致无限循环。

鸣谢: OpenMP ARB

- dreamcrash

Answer 2

与表面看起来的不同，schedule(dynamic)并不能处理动态数量元素的情况。实际上，迭代块分配给线程的方式是动态的。静态调度在工作共享结构的开始预先计算此分配。而在动态调度中，迭代块则按照先到先得的原则分配给线程。

OpenMP标准非常清楚，一旦遇到工作共享结构，迭代次数就会预先计算，因此循环计数器可能不会在循环体内被修改(参见OpenMP 3.1规范，§2.5.1 - 循环结构)：

对于每个关联的循环，迭代计数是在进入最外层循环之前计算的。如果执行任何关联的循环会改变用于计算任何迭代计数的任何值，则行为是未指定的。

用于计算折叠循环的整数类型(或Fortran的种类)是由实现定义的。

工作共享循环有逻辑迭代号0,1,...,N-1，其中N是循环迭代次数，逻辑编号表示如果相关的循环由单个线程执行，则迭代将按顺序执行。 schedule 子句指定如何将相关循环的迭代划分为连续的非空子集(称为块)，以及如何将这些块分配给团队中的线程。每个线程在其隐式任务的上下文中执行其分配的块。对于在循环结构中作为私有变量的任何变量的原始列表项，将使用其原始值计算chunk_size表达式。未指定此表达式的副作用以何种顺序、多少次发生。在循环结构的schedule 子句表达式中使用变量会导致在所有封闭结构中隐式引用该变量。

这些关系运算符的限制背后的逻辑非常简单-它提供了循环方向的明确指示，允许轻松计算迭代次数，并且提供了类似于C/C++和Fortran中OpenMP工作共享指令的语义。此外，其他关系运算需要仔细检查循环体以了解循环如何进行，这在许多情况下都是不可接受的，并且会使实现复杂。

OpenMP 3.0引入了显式任务构造，允许并行化具有未知迭代次数的循环。然而，有个问题：任务会引入一些严重的开销，每个循环迭代一个任务只有在这些迭代需要执行相当长的时间时才有意义。否则，开销将主导执行时间。

- Hristo Iliev

Answer 3

答案很简单。 OpenMP不允许线程组的过早终止。 使用==或!=时，OpenMP无法确定循环何时停止。 1.一个或多个线程可能会达到终止条件，这可能不是唯一的。 2.OpenMP无法关闭其他可能永远无法检测到条件的线程。

- bobcgausa

Answer 4

如果我看到这个语句

for(i = 0; i != j; i++)

用于替代语句的

for(i = 0; i < j; i++)

我会一直想知道程序员为什么会做出那个选择，尽管它可能意味着相同的事情。可能是OpenMP在做出艰难的语法选择以强制代码的某种清晰度。

下面的代码提出了使用“!=”时的挑战，并可能有助于解释为什么不允许使用它。

#include <cstdio>

int main(){
    int j=10;
   #pragma omp parallel for
   for(int i = 0; i < j; i++){
    printf("%d\n",i++);
   }
}

请注意，在for语句和循环本身中都对i进行了递增，这可能导致（但不保证）无限循环的可能性。如果断言是<，则在并行上下文中仍然可以定义好循环的行为，而不需要编译器在循环内部检查i的变化并确定这些变化将如何影响循环的范围。如果谓词是!=，则循环的行为不再被定义为良好的，并且它可能具有无限的范围，阻止了轻松的并行子分割。

- Richard

---

你的样例不符合OpenMP规范。你不能在循环体内修改循环计数器。单线程版本按预期产生0 2 4 6 8，但即使使用两个线程，它也会产生以下输出：0 2 4 5 7 9。 - Hristo Iliev

如果您在普通的顺序C程序中这样做，您的示例也会失败。尽管如此，编译器允许这样做。 - dreamcrash

该示例并不意味着会失败（虽然随意更改限制条件使其失败），它旨在演示编译器遇到的困难：定义 < 的行为很容易，而定义 != 的行为则相当困难。 - Richard

@dreamcrash，他的例子在作为顺序C代码时有什么问题吗？它是一个完全有效的串行C代码，并且按预期工作，但不是一个有效的OpenMP代码。 - Hristo Iliev

我认为这个答案最重要的部分是循环子句对程序员也有意义。<比!=包含更多信息，平均而言多两倍，正如@Richard所说，如果我看到循环中使用了这种符号，那么在我理解循环中实际发生了什么之前，我必须阅读循环体。 - Jonathan Dursi

抱歉，我表达得不够清楚。我指的是以下代码：int i; int j = 9; for(i = 0; i != j; i++) { printf("%d\n",i++); } - dreamcrash

Answer 5

我认为除了扩展现有功能以达到这一点之外，可能没有其他好的理由。

如果我没记错的话，最初这些必须是静态的，以便在编译时确定如何生成循环代码...这可能只是那个时期的遗留问题。

- jheriko