Обзор компании Intel в рамках параллельного программирования
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
r * 2 > (signed) dstSize) ? (1) : (0); /* updated line */
/* correct the array to make sum of all elements near to zero */(i = 0; i < dstSize; i += 1)
{[i] -= mean;
}
Параметры a, b и seed0 даются программе на вход, как и размер генерируемой матрицы.
Функция PRNG выглядит так:
PRNG(seed, a, b, m)
{(a * seed + b) % m;
}
В коде выше первый цикл заполняет матрицу неотрицательными значениями, а второй цикл вычитает из всех элементов округленное среднее значение всех ее элементов. В результате этого в матрице появляются нулевые и отрицательные элементы.
Формулировка задачи
Написать параллельную программу для генерации матрицы целых значений и найти прямоугольную подматрицу с максимальной суммой элементов в ней. На вход программе дается один текстовый файл, содержащий размерность матрицы и параметры псевдослучайного алгоритма. Программа должны вывести в выходной файл координаты двух противоположных углов подматрицы с максимальной суммой элементов в ней.
Описание входных данных
Первый параметр командной строки - имя входного файла, второй параметр - имя выходного файла.
Во входном файле содержится несколько тестов. На первой строке входного файла дано число C - количество тестов, которые нужно решить. Далее описываются C тестов. Для каждого из них в файле дана одна строка, содержащая 6 целых чисел через пробел.
Первые два числа (M и N) - количество строк и столбцов в матрице, соответственно. Четыре следующих числа - параметры псевдослучайного алгоритма seed0, a, b и m соответственно.
Ограничения для входных параметров:
1 ? C ? 1000
? M, N, a, b, m, seed0 ? 20000
Входные параметры таковы, что сумма элементов в любой подматрице исходной матрицы убирается в int32.
Описание выходного файла
Для каждого теста в выходной файл нужно вывести строку "Case #x: ", за которой следуют 6 целых чисел (через пробел) и символ переноса строки.
Первые 4 числа - две пары координат, задающих подматрицу с максимальной суммой элементов (в первой паре оба числа должны быть меньше или равны соответственным числам во второй паре, т.е. сначала описывается координаты левого верхнего, а потом правого нижнего угла). В каждой паре первое число - номер строки, а второе число - номер столбца (нумерация начинается с нуля). Если вы нашли несколько подматриц с одинаковой максимальной суммой элементов, выведите координаты любой из них.
Последние 2 числа - сумма элементов в найденной подматрице и площадь этой подматрицы соответственно.
Весь вывод должен идти в выходной файл, имя которого задается вторым параметром командной строки.
Пример вызова вашей программы
./msp input.txt output.txt
Пример входного файла (input.txt):
3 10 3 4 17
31 11 4 5 18
Пример выходного файла (output.txt):
#1: 0 2 3 2 17 4#2: 0 4 5 9 18 36
Объяснение вывода по первому тесткейсу:
Сгенерирована матрица размером 4x3:
-4 8
-1 0
-5 5
6 4
Координаты подматрицы с максимальной суммой элементов: [0][2] .. [3][2] (в этом примере это последний столбец исходной матрицы).
Сумма элементов подматрицы = 17
Площадь этой подматрицы = 4
О сервере
Все участники в течение конкурса могли протестировать свой код на 40 ядерном сервере лаборатории Manycore Testing Lab (MTL). Некоторые характеристики:
*40 ядра 80 узла нити
*Поддержка Linux и Microsoft windows OS
*Поддержка языка программирования Intel Cilk Plus
*Обновленные GCC и TBB
Так же хочу добавить отчет по работе на 32-ядерном сервере лаборатории Manycore Testing Lab (MTL) Владимира Полина, сотрудника компании Intel. Использовалась технология TBB 3.0.
*Несколько недель назад у меня появилась возможность поработать на 32-х ядерном сервере лаборатории Manycore Testing Lab (MTL), в то время, когда принимались заявки на машинное время и академическое сообщество не успело загрузить своими задачами все серверы. Использование лаборатории бесплатно для академического сообщества (Intel Academic community). Но, конечно, есть некоторые ограничения. Информацию и инструкции о серверах и доступе можно найти на странице проекта MTL
В MTL на многоядерных серверах установлено новейшее программное обеспечение от Intel, в том числе и недавно выпущенный TBB 3.0. Доступ по ssh на сервер оказался не сложнее, чем на компьютер, установленный в соседней комнате. На форуме MTL можно найти подсказки, как использовать сервера более продуктивно, например, как назначить задачи на определенные ядра, отключить SMT, установить переменные окружения и т.д..
Когда наша команда работала над выпуском TBB 3.0, я собирал данные на сервере MTL по производительности TBB. И результаты были включены в документ Intel Threading Building Blocks 3.0 In-Depth, который доступен по ссылке:://software.intel.com/sites/products/collateral/hpc/tbb/Intel_TBB3_InDepth.pdf. Я запустил большинство примеров из дистрибутива TBB 3.0. Исходя из начальных данных примеров и количества работы примеры показали различную масштабируемость, от очень плохого для примера Фибоначчи, который совсем не масштабируется и используется для показа функциональности TBB, до отличной масштабируемости для как для 64 потоков, а особенно для 32 потоков, которые распределены по физическим ядрам. Хочу немного написать про пример Судоку (Sudoku), который был добавлен в версии 3.0 для того чтобы показать работу с новым классом task_group. Этот пример не попал в официальные данные по масштабируемости, потому что он недостаточно оптимизирован по