Слияние треугольной петли для распараллеливания, вычисление подиндексов

Общей методикой распараллеливания является слияние вложенных для таких циклов

for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { 

в

 for(int x=0; x<n*n; x++) { int i = x/n; int j = x%n; 

Мне интересно, как я могу это сделать, чтобы закрепить треугольную петлю, подобную этой

 for(int i=0; i<n; i++) { for(int j=0; j<i+1; j++) { 

Это имеет n*(n+1)/2 итераций. Назовем сплавленную итерацию x . Используя квадратичную формулу, я пришел к следующему:

 for(int x=0; x<(n*(n+1)/2); x++) { int i = (-1 + sqrt(1.0+8.0*x))/2; int j = x - i*(i+1)/2; 

В отличие от сплавления квадратного цикла, это требует использования функции sqrt и преобразований из int в float и от float до int.

Мне интересно, есть ли более простой или эффективный способ сделать это? Например, решение, которое не требует функции sqrt или преобразований из int для float или float в int.

Изменить: мне не нужно решение, зависящее от предыдущих или последующих итераций. Мне нужны только решения, такие как int i = funci(x) and int j = funcj(x,i)

Вот какой код показывает, что это работает:

 #include  #include  int main() { int n = 5; int cnt = 0; for(int i=0; i<n; i++) { for(int j=0; j<i+1; j++) { printf("%d: %d %d\n", cnt++, i,j); } } printf("\n"); int nmax = n*(n+1)/2; for(int x=0; x<nmax; x++) { int i = (-1 + sqrt(1.0+8.0*x))/2; int j = x - i*(i+1)/2; printf("%d: %d %d\n", x,i,j); } } 

Учитывая, что вы пытаетесь сплавить треугольник с целью распараллеливания, неочевидным решением является выбор нетривиального отображения x на (i, j):

 j |\ i -> | \ ____ | | \ => |\\ | V |___\ |_\\__| 

В конце концов, вы не обрабатываете их в каком-либо специальном порядке, поэтому точное отображение не важно.

Поэтому вычислите x->i,j как и для прямоугольника, но если i > j тогда { i=Ni, j = Nj } (зеркальная ось Y, затем зеркальная ось X).

  ____ |\\ | |\ |\ |_\\__| ==> |_\ __ => | \ / | | \ /__| |___\ 

Самой разумной формой является, конечно, первая форма.

Тем не менее, сплавленная форма лучше выполняется с условностями:

 int i = 0; int j = 0; for(int x=0; x<(n*(n+1)/2); x++) { // ... ++j; if (j>i) { j = 0; ++i; } } 

Мне интересно, есть ли более простой или эффективный способ сделать это?

Да, код, с которого вы должны были начать. Пожалуйста, имейте в виду следующее:

  • Не существует случая, когда арифметика с плавающей запятой выполняется быстрее, чем простые целые числа.
  • Однако существует множество случаев, когда плавающая точка намного медленнее, чем простые целые числа. FPU или нет FPU.
  • Поплавковые переменные обычно больше, чем простые целые числа на большинстве систем и поэтому более медленны по этой причине.
  • Первая версия кода, скорее всего, наиболее дружественна кэш-памяти. Что касается любого случая ручной оптимизации, это полностью зависит от того, какой процессор вы используете.
  • В большинстве систем разделение обычно медленное, независимо от того, сделано ли это для простых целых чисел или поплавков.
  • Любая форма сложной арифметики будет медленнее, чем простой подсчет.

Таким образом, ваш второй пример в значительной степени гарантированно будет намного медленнее, чем первый пример, для любого данного процессора в мире. Кроме того, он также полностью не читается.