«Слабо загрузить 40 ядер?» или простой конкурс параллельного программирования Acceler8 2011

Продолжая неделю высказывания мнений о высшем образовании на Хабре, расскажу о конкурсе, который находится где-то посередине, между работой (так отрицаемой уважаемым AlexanderLarin) и умением учиться (так продвигаемым хабрапользователем Alexnn).

А расскажу я о конкурсе параллельного программирования Acceler8. Да, это конкурс, в котором есть возможность не только научиться, но и заработать один из «небольших» призов: 2 мощных лэптопа HP и 10 нетбуков Asus.
Хотите попробовать свои силы?

На первый взгляд, в этот раз конкурс достаточно простой: нужно решить всего одну задачку по программированию.
На второй взгляд, решение должно быть параллельным и по возможности масштабируемым.
Итак, о чем речь?

Кратко о задаче

Дана двумерная матрица значений, нужно найти в ней прямоугольную подматрицу с максимальной суммой элементов в ней среди всех подматриц.
Подробнее о задаче можно прочитать на странице конкурса.

Кратко о решении

Понятно, что последовательным перебором в лоб задача решается, однако решение будет слишком медленным:

int maxSum = A[0][0];
int maxI0 = 0, maxJ0 = 0, maxI1 = 1, maxJ1 = 1;
for (int i = 0; i < M; i++) 
	for (int j = 0; j < N; j++) 
	  for (int width = 1; width <= M - i; width++)
		for (int height = 1; height <= N - j; height++)
		{
		  int currentSum = sum_subarray(A, i, j, i + width, j + height);
		  if (currentSum > maxSum)
		  {
			maxSum = currentSum;
			maxI0 = i;
			maxJ0 = j;
			maxI1 = i + width - 1;
			maxJ1 = j + height - 1;
		  }
		}
cout << "Max subarray: [" << maxI0 << "][" << maxJ0 << "] .. [" << maxI1 << "][" << maxJ1 << "]";
cout << endl <<  "Max value = " << maxSum << endl;
cout << "Area = " << (maxI1 - maxI0 + 1) * (maxJ1 - maxJ0 + 1) << endl;

Очевидно, что такой подход — «совсем не epic».

Как решать по-умному

Существует множество подходов к этой задаче.

• Во-первых, можно использовать интересное кеширование (основанное на свойствах матриц), описанное в Daily One Algorithm:
  Для начала создадим промежуточную матрицу B, изначально заполенную нулями, в которой в каждом элементе B[i][j] хранится сумма элементов подматрицы от верхнего левого угла (A[0][0]) до A[i][j].
  Теперь сумма элементов в любой подматрице может быть найдена как
  

  
  sum = B[i2][j2]- B[i1-1][j2] - B[i2][j1-1] + B[i1-1][j1-1]
  

  
  
• Во-вторых, можно попробовать применить алгоритм Кадане, изначально написанный для одномерного массива или портировать и параллелизовать модифицированный алгоритм, приведенный одним из пользователей stackoverflow.com
• В-третьих, можно немного подумать и написать красивое, параллельное и быстрое решение ;)

Не будем раскрывать всех карт. Сейчас все в равных условиях — месяц времени (решения принимаются до 15 ноября) и свободный доступ к гуглу и учебникам.
Звучит просто, не правда ли?
А самое вкусное — на закуску.

Как мы будем оценивать масштабируемость?

Есть много подходов и много флуда по этому вопросу. Мы решили взять самое простое в реализации, но и самое близкое к реальности решение:
Код будет тестироваться на двух разных платформах. Первая — 40-ядерная машина Manycore Testing Lab, с известными хардварными характеристиками, известной маркой процессора и известным размером кэша второго уровня (см. «Конфигурация MTL»). Вторая — маленькая система, о которой неизвестно почти ничего (2-4 ядра, несколько гигов памяти — вот и вся информация).
Сложно ли в такой ситуации оптимизировать решение? Да.
С другой стороны — можно работать быстрее всех на «маленькой машине» и средне на MTL — этого может быть достаточно для выигрыша.
А может быть кто-то добьется лучшего результата на обеих машинах? Это покажет время.
Итак, для заинтересовавшихся, маленькая ссылка: регистрация на конкурс. Вопросы можете писать в комментариях или оставлять на форуме конкурса.

И, это, be epic! ;)