Flip C Lang
  1. Flip C Lang
  3. Слияние треугольной петли для распараллеливания, вычисление подиндексов
Intereting Posts
Как отключить предупреждения Visual Studio 2012? Вызов основной функции более одного раза является хорошей практикой в ​​C? Самый простой способ работы с промежуточным форматом В какой области помещается идентификатор элемента структуры? ввод данных от пользователя Упакованные битовые поля в c-структурах – GCC Вывод не корректно выполняется в файловой операции Как (переносимо) получить DBL_EPSILON в C / C ++ Использование функции C-callback с .NET Использовать strlen с scanf (% ms) Переполнение стека из встроенной DLL, вызванной из управляемого приложения Есть что-то вроде официальной документации C? Почему я могу изменить значение переменной const char *? Bubble Сортировать с помощью указателей для функции Как реализовать макрос, который создает строку с кавычками для _Pragma?

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

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

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.
  • Поплавковые переменные обычно больше, чем простые целые числа на большинстве систем и поэтому более медленны по этой причине.
  • Первая версия кода, скорее всего, наиболее дружественна кэш-памяти. Что касается любого случая ручной оптимизации, это полностью зависит от того, какой процессор вы используете.
  • В большинстве систем разделение обычно медленное, независимо от того, сделано ли это для простых целых чисел или поплавков.
  • Любая форма сложной арифметики будет медленнее, чем простой подсчет.

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