Исправляюсь :) У меня одна итерация (т.е. одно изменение per) занимает всего 21 такт, все данные выровнены на 4. ММХ привязать пока сложно, не зная характера и объема данных.

	lea esi, mas1
	lea edi, mas2
	xor eax, eax
	mov ecx, per
	lea esi, [esi+ecx*4]
@@next_line:
	push ecx
	mov edx, esi
	mov ecx, per2
	mov ebx, per3
@@:	add eax, dword ptr [esi]
	lea esi, [esi+ebx*4]
	dec ecx
	jnz @B
	lea esi, [edx+4]
	mov [edi], eax
	add edi, 4
	pop ecx
	dec ecx
	jnz @@next_line

Black_mirror
УВЕЛИЧИТЬ В 100 раз? для чего?

emergenter
Время выполнения вашего алгоритма k0+per*(k1+per2*k2), где:
k0 - затраты на инициализацию счеткика внешнего цикла
k1 - затраты на выполнение итерации внешнего цикла( включая проверку и изменение счетчика внешнего цикла и инициализацию счетчика внутреннего цикла и не включая время выполнения внутреннего цикла)
k2 - время выполнения итерации внутреннего цикла
Затратами k0 при увеличении per или per2 можно пренебречь.
Также можно пренебреч затратами k1 при увеличении per2.
Таким образом время выполнения этого цикла: per*per2*k2.

А вот немного улучшенный мой алгоритм:

int n3=min(per3,per);
int sum[]=new int[n3];
for(i=0;i<n3;i++) //цикл 1
   sum[i]=0;
int n=per2*per3;
for(i=0;i<n;i+=per3)      //цикл 2
   for(j=0;j<n3;j++)
     sum[j]+=mas1[i+j];
int m=per/per3;
int r=per%per3;
for(int i=0;i<m;i+=per3)  //цикл 3
  for(j=0;j<per3;j++)
  {
    summa+=sum[j];
    sum[j]+=mas1[per+i+j+n]-mas1[per+i+j];
    mas2[i+j]=summa;
  }
for(j=0;j<r;j++)          //цикл 4
{
  summa+=sum[j];
  mas2[m+j]=summa;
}
delete[] sum;

Я не буду писать все слагаемые а выпишу только главные:
k0 - время на выделения памяти(сильно влияет при маленьких значениях per и per2)
per2*min(per3,per)*k2 - время выполнения второго цикла
per*max(k3,k4) - время выполнения 3 и 4 циклов.
При больших per и per2 можно исключить k0 и время выполнения будет порядка per2*per3*k2+per*max(k3,k4),
то есть оно пропорционально per и per2, а в вашем алгоритме оно пропорционатьно per*per2. Поэтому нельзя говорить что один алгоритм в 1.5 раза медленее другого.

Думаю что при per и per2 порядка 10000-100000 и при per3 раз в 10 меньше чем per, ваш алгоритм будет проигрывать.

Black_mirror
Классный АЛГОРИТМ!!!!
щас быстренько разберусь и протестирую...

emergenter
Кстати а что предлагал с этим алгоритмом сделать Крис? Или у него был другой пример?

Black_mirror
не у Криса этот алгоритм не описан!! У него собраны примитивы. Как раз из них ты этот алгоритм и сделал!! Прямо по книге.

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

Black_mirror
Я так понимаю чем в алгоритме меньше зависимости по данным тем больше появляется возможности параллельной обработки данных. И надо стремиться чтобы вычисления и работа с памятью ЗАГРУЗКА / ЗАПИСЬ выполнялись параллельно. Из чего следует минимум времени выполнения..
Ведь так? Поправьте если не прав.

Возможности процессора по параллельной обработке очень ограничены. А чтобы ими воспользоватся тебе придется почитать статьи по низкоуровневой оптимизации, которые находятся на данном сайте. Другое дело многопроцессорные системы. Там стремятся устранить зависимость по данным чтобы можно было выполнить разные итерации цикла одновременно на различных процессорах.
Зависимость по данным вытекает их структуры самого алгоритма. Но каждую задачу можно решить несколькими способами. И из них мы можем выбирать.

если можно ссылочку на статьи...
Вроде только Агнер Фог есть...

Уважаемый,Black_mirror
ваш алгоритм работает неправильно. Я мозги себе чуть не сломал пытаясь разобраться.

Sm_Andrei
Спасибо!
Вот исправленный:

int n3=min(per3,per);
int sum[]=new int[n3];
for(i=0;i<n3;i++) //цикл 1
   sum[i]=0;
int n=per2*per3;
for(i=0;i<n;i+=per3)      //цикл 2
   for(j=0;j<n3;j++)
     sum[j]+=mas1[per+i+j];
int m=per/per3*per3;
int r=per%per3;
for(int i=0;i<m;i+=per3)  //цикл 3
  for(j=0;j<per3;j++)
  {
    summa+=sum[j];
    sum[j]+=mas1[per+i+j+n]-mas1[per+i+j];
    mas2[i+j]=summa;
  }
for(j=0;j<r;j++)          //цикл 4
{
  summa+=sum[j];
  mas2[m+j]=summa;
}
delete[] sum;

Black_mirror

Что-то у меня все равно не получается запустить ваш кусман проги - не того считает.

У меня выдает тоже самое что и алгоритм на первой странице. Может у вас обращение за пределы массива происходит? Число элементов в первом массиве должно быть не меньше чем min(per,per3)+per2*per3, а во втором не меньше чем per.

Black_mirror

Если per<per3 то в цикле 3 (j=0;j<per3;j++) sum[j] не выделено в памяти и неинициализировано.