Конкурс по оптимизации 2015

931 views
Skip to first unread message

Alexey Sidnev

unread,
Nov 25, 2015, 5:47:28 AM11/25/15
to Основы программирования
Каждому студенту необходимо реализовать поставленную задачу. Подробную постановку можно посмотреть на странице: https://sites.google.com/site/alexeysidnev/studentam/optimization-competition-2015

В ветке можно задавать вопросы.

edding....@gmail.com

unread,
Nov 30, 2015, 12:27:02 PM11/30/15
to Основы программирования
Добрый день.

1. Обязательна ли регистрация?
2. Правильно ли я понимаю, что результат каждого возведения подматрицы в квадрат сохраняется в A, и, таким образом, второе возведение в квадрат уже будет использовать данные потенциально отличающиеся от начальных?

Alexey Sidnev

unread,
Nov 30, 2015, 1:04:49 PM11/30/15
to Основы программирования
1. Регистрация обязательна. Только зарегистрированные студенты получат доступ к кластеру и только их реализации я буду проверять.
2. Да, всё верно.

israfilov.rusl...@gmail.com

unread,
Dec 5, 2015, 11:05:48 AM12/5/15
to Основы программирования
Здравствуйте.
Считается, что матрицы, которые приходят в функцию Solve, хранятся в RowMajor формате?

ganina...@gmail.com

unread,
Dec 6, 2015, 4:53:09 AM12/6/15
to Основы программирования
Здравствуйте.
Зарегистрировался. На почту ничего не пришло. Нужен доступ к кластеру для тестирования.

ann...@gmail.com

unread,
Dec 6, 2015, 5:24:07 AM12/6/15
to Основы программирования
Добрый день!
Аналогично. Заполнила форму для регистрации в четверг вечером.
Когда можно ожидать ответ?

Alexey Sidnev

unread,
Dec 6, 2015, 5:40:17 AM12/6/15
to Основы программирования
1. Все матрицы хранятся в RowMajor формате (плотное по строкам).
2. Доступ к кластеру я предоставлю сегодня всем тем, кто зарегистрировался. Сейчас вы можете разрабатывать программу на своих домашних компьютерах (программный код будет компилироваться как под Windows, так и под Linux).

Alexey Sidnev

unread,
Dec 7, 2015, 3:02:45 AM12/7/15
to Основы программирования
1. Вчера вечером я отправил на почту всем зарегистрировавшимся параметры доступа к кластеру. Если кому-то письмо не пришло, то это может означать, что вы ошиблись в написании своего почтового адреса. Необходимо повторно зарегистрироваться и/или написать мне письмо.
2. В архив с шаблоном реализации я добавил пример выходного файла для первого набора входных параметров.

Alexey Sidnev

unread,
Dec 7, 2015, 7:21:51 AM12/7/15
to Основы программирования
Обновлен файл с постановкой задачи. При проверке будет использоваться компилятор Intel C++ Compiler 15. Для его использования необходимо загрузить модуль intel2015.

alex75...@gmail.com

unread,
Dec 9, 2015, 5:39:43 PM12/9/15
to Основы программирования
Здравствуйте!

Хотелось бы уточнить задачу. Результат, как я понимаю, будет зависеть от того какая подматрица возвелась в квадрат и записалась обратно в матрицу А первой. То есть обход по подматрицам должен быть фиксированный, чтобы получить конретный ответ?

Alexey Sidnev

unread,
Dec 9, 2015, 11:43:07 PM12/9/15
to Основы программирования
Верно, в общем случае результат зависит от порядка обхода матриц. Я преполагаю, что обход будет классический для языка C/C++. Сначала выполняется проход по 1-ой строке слева направо, потом по 2-ой и т.д.

sovras...@gmail.com

unread,
Dec 11, 2015, 1:34:25 AM12/11/15
to Основы программирования
Здравствуйте.

Я правильно понимаю, что файлы example.input и example1.output нельзя использовать для проверки корректной работы программы?
В файле main.cpp нет вызова функции srand, поэтому результат генерации матриц непредсказуем.

Alexey Sidnev

unread,
Dec 11, 2015, 2:32:55 AM12/11/15
to Основы программирования
Абсолютно верное замечание! Файл example1.output не несёт какой-либо полезной информации, т.к. неизвестно c каким seed`ом выполнялась инициализация генератора случайных чисел.
В архив с задачей добавил исправленный файл main.cpp и выложил два выходных файла:
  example1.output.linux - получен на кластере с использованием icc 15.0.0 20140723;
  example1.output.windows - получен под Windows с использованием icl 15.0.0.108 (при использовании Microsoft Compiler 17.00.61030 результат такой же).

ganina...@gmail.com

unread,
Dec 13, 2015, 1:45:48 AM12/13/15
to Основы программирования
При тестировании получаю матрицу с размерами:
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 3 0 0 0 0
0 0 4 0 0 4 0 0 0 0 0
0 0 3 3 0 0 0 0 0 0 0
0 0 4 0 0 0 8 0 8 8 0
0 0 0 0 7 0 8 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
size: 11, i: 7, j: 6, subSize: 8
size: 11, i: 7, j: 8, subSize: 8
size: 11, i: 7, j: 9, subSize: 8
size: 11, i: 8, j: 4, subSize: 7
size: 11, i: 8, j: 6, subSize: 8

Не гарантируется что подматрица указанного размера укладывается в матрицу?

Alexey Sidnev

unread,
Dec 13, 2015, 3:58:21 AM12/13/15
to unn_pro...@googlegroups.com
По условию задачи гарантируется, что каждый элемент матрицы B не превосходит размеров матрицы A. Если выделяемая подматрица выходит за границу матрицы A, то необходимо брать элементы матрицы по порядку с обратного края матрицы A, т.е. матрица A замкнута по горизонтали и вертикали.

Alexey Sidnev

unread,
Dec 13, 2015, 9:55:27 AM12/13/15
to Основы программирования
Внимание! Я обновил тестовый выходной файл, т.к. обнаржуил ошибку в реализации алгоритма. Скачайте архив снова.

edding....@gmail.com

unread,
Dec 14, 2015, 4:08:52 AM12/14/15
to Основы программирования
Какой максимальный размер матриц A и B будет использован в тестах?

Alexey Sidnev

unread,
Dec 14, 2015, 5:04:58 AM12/14/15
to Основы программирования
Размеры матриц не будут превосходить 10000.

edding....@gmail.com

unread,
Dec 14, 2015, 12:26:24 PM12/14/15
to Основы программирования
Алексей Александрович, возведённую в квадрат подматрицу нужно поэлементно прибавлять к исходной подматрице в A? Из формул в постановке можно сделать вывод, что возведённую в квадрат подматрицу нужно перезаписывать поверх исходной.

Alexey Sidnev

unread,
Dec 14, 2015, 1:33:10 PM12/14/15
to Основы программирования
Действительно, в архиве лежали выходные данные для случая A[i : i + B[i,j], j : j + B[i,j]] += S. Т.к. в постановке задачи это не было указано, то добавлять матрицу S не надо, её необходимо просто перезаписывать поверх элементов матрицы A. Выходные файлы с тестами обновил.

При проверке завтра я буду считать корректными оба варианта. При проверке работа 25-го необходимо предоставить вариант из постановки задачи: A[i : i + B[i,j], j : j + B[i,j]] = S.

Alexey Sidnev

unread,
Dec 17, 2015, 2:05:09 AM12/17/15
to Основы программирования
Я в командировке и у меня, увы, нет возможности проверить работы. Я постараюсь выложить результаты проверки в пятницу.
До этого момента можно прислать мне улучшенные реализации (или первые, если вы ещё не присылали).

Alexey Sidnev

unread,
Dec 22, 2015, 2:30:12 PM12/22/15
to Основы программирования
Прошу прощения за опоздание, я только сейчас смог проверить присланные работы.
В столбцах содержится величина относительной ошибки.

ФИО Тест 1 Тест 2 Тест 3 Тест 4
1. BabintsevaAnna 0 0 0 0
2. GolodyaevAndrey 0 0 0 0
3. IsrafilovRuslan 0 1 0 1
4. kudriavtsev 0 0 0 0
5. KukushkinDaniil 0 0 0 0
6. LarinAnton 0 0 0 0
7. MatveevaSvetlana 0 0 0 0
8. NesmelovAleksey 0 0 0 0
9. Shishkin 0 0 0 0
10. Skrebkov 0 0 0 0
11. sovrasovvladislav 0 0 0 0
12. zhbanovaanna 0 0 0 0

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

Alexey Sidnev

unread,
Dec 22, 2015, 4:11:06 PM12/22/15
to Основы программирования
1. В реализациях запрещается использовать сторонние функции и библиотеки (например, dgemm). Реализации MatveevaSvetlana и IsrafilovRuslan не засчитываются.
2. При сборке одной из реализаций произошла ошибка компиляции (см. аттач). Я удалил OpenMP директиву, чтобы проверить корректность.
3. Я обновил постановку задачи, архив и выложил результаты на сайте. В презентации можно найти пороговые значения для получения зачёта.
4. Я обновил файл main.cpp. Для запуска программы необходимо указать выходной файл в качестве аргументов командной строки (см. презентацию).
5. Я взял за основу стороннюю реализацию, которая (как оказалось) содержала ошибки. Я самостоятельно решил задачу, сейчас выходные файлы корректны и совпадают с подавляющим большинством реализаций.
6. При проверке работ я буду пользоваться системой поиска плагиата. Если будут найдены две одинаковые или близкие работы, то будет засчитываться только та, которая прислана первой.
build.log

israfilov.rusl...@gmail.com

unread,
Dec 22, 2015, 4:42:09 PM12/22/15
to Основы программирования
В моей реалзации (IsrafilovRuslan) не используется функция dgemm (иначе работало бы правильно).
Возникла она там, потому что используется для проверки и включается макроссом.

#ifdef CHECK_WITH_MKL

edding....@gmail.com

unread,
Dec 22, 2015, 4:44:46 PM12/22/15
to Основы программирования
Что находится в test1.out, test2.out, test3.out в архиве?

Alexey Sidnev

unread,
Dec 22, 2015, 10:02:03 PM12/22/15
to Основы программирования
Руслан, в следующий раз перед отправкой работы удалите вызов функции dgemm. Это поможет избежать подобного рода проблем.

Alexey Sidnev

unread,
Dec 22, 2015, 10:04:09 PM12/22/15
to Основы программирования
Я обновил файл с тестами example.input. Файлы test1.out, test2.out, test3.out соответствуют результатам работы программы на первых 3-х тестах на кластере (под Linux).

israfilov.rusl...@gmail.com

unread,
Dec 27, 2015, 1:03:18 PM12/27/15
to Основы программирования
Алексей Александрович, каким образом проверяется корректность работы?

Alexey Sidnev

unread,
Dec 27, 2015, 1:54:06 PM12/27/15
to Основы программирования
Сравнивается результат работы вашей программы с результатом работы моей программы. Результатом сравнения является максимальная относительная ошибка между элементами результирующих матриц. Я буду считать результат корректным, если совпадают 10 значимых цифр числа.

Alexey Sidnev

unread,
Dec 28, 2015, 3:50:36 AM12/28/15
to Основы программирования
Отмечу, что для получения зачёта необходимо уложиться по времени по всем 3-м тестам!

Добавлю некоторые замечания по реализации:
  1. Совершенно понятно, что выполнять параллельно малый объём работы не имеет смысла, т.к. большие накладные расходы на организацию параллельных вычислений будут сопоставимы или больше самих вычислений. Тесты time_test.input выбраны таким образом, чтобы умножаемые матриц имели разный размер (разный объём работы).
  2. На паре я обращал внимание, что классическое умножение в три цикла можно существенно ускорить, изменив порядок циклов. Блочная реализация может ещё больше ускорить умножение матриц (требуется аккуратная реализация).
  3. (?) Упаковка подматрицы в плотный участок памяти может ускорить операцию умножения матриц (зависит от размера подматрицы и её расположения).
  4. (?) Создание транспонированной копии подматрицы может ускорить операцию умножения, но это потребует дополнительной памяти.

n.yu.kud...@gmail.com

unread,
Dec 28, 2015, 8:27:54 AM12/28/15
to Основы программирования
Добрый день!
Я сегодня запускал одну и ту же версию программы несколько раз днем и несколько раз вечером на одних и тех же тестах time_test.input. Днем программа в среднем работала значительно быстрее, чем вечером. Алексей Александрович, вы не подскажете, почему такое может произойти?

Alexey Sidnev

unread,
Dec 28, 2015, 8:47:08 AM12/28/15
to unn_pro...@googlegroups.com
Причин подобного поведения может быть много, поэтому мне нужна дополнительная информация:
  1. Как выполнялся запуск программы (строка запуска)?
  2. Использовалась ли утилита taskset?
  3. Известны ли узлы на которых выполнялся запуск днём и вечером?

n.yu.kud...@gmail.com

unread,
Dec 28, 2015, 8:51:01 AM12/28/15
to Основы программирования
Запуск осуществлялся строкой
srun -p all --reservation=optimization cat example.input | taskset -c 16-31 App.out > log task
То есть утилиту использовал. На третий вопрос не могу ответить.

Alexey Sidnev

unread,
Dec 28, 2015, 8:56:13 AM12/28/15
to Основы программирования
Я обнаружил, что 3 и 4-х узлов на которых проводятся эксперименты содержат "паразитный" процесс, который полностью загружает одно ядро. Потенциально это может быть причиной, но использование утилиты taskset решает эту проблему.
Другой причиной может быть использование динамического планирования в программе. В этой случае разброс времени выполнения программы может быть существенным.

Можете привести на сколько отличалось время выполнения программы (с указанием абсолютного времени выполнения для каждого запуска)?

n.yu.kud...@gmail.com

unread,
Dec 28, 2015, 9:13:37 AM12/28/15
to Основы программирования
Точных значений сейчас привести не могу.
Примерные результаты таковы (в секундах):
Тест: время днём; время вечером.
Тест1: 3;9
Тест2: 9; 35
Тест3 8; 30

Alexey Sidnev

unread,
Dec 28, 2015, 10:45:49 AM12/28/15
to Основы программирования
Попробуйте выполнить запуск непосредственно на узле:
  1. salloc -N 1 -p all --reservation=optimization
salloc: Pending job allocation 158888
salloc: job 158888 queued and waiting for resources
salloc: job 158888 has been allocated resources
salloc: Granted job allocation 158888
salloc: Waiting for resource configuration
salloc: Nodes node51 are ready for job
  2. ssh node51
  3. export LD_LIBRARY_PATH=/common/intel/composer_xe_2013_sp1.2.144/compiler/lib/intel64:/common/intel/composer_xe_2013_sp1.2.144/mkl/lib/intel64:/common/intel/parallel_studio/composer_xe_2015.0.090/compiler/lib/intel64:/opt/intel/mic/coi/host-linux-release/lib:/opt/intel/mic/myo/lib:/common/intel/parallel_studio/composer_xe_2015.0.090/mpirt/lib/intel64:/lib:/usr/lib:/usr/X11R6/lib:/usr/local/lib:$LD_LIBRARY_PATH
  4. cat example.input | taskset -c 16-31 app.out ouput_name

iosif....@gmail.com

unread,
Dec 28, 2015, 1:40:32 PM12/28/15
to Основы программирования
А гонок данных точно нет? Гонки вполне могут вызывать такие "фокусы".

iosif....@gmail.com

unread,
Dec 28, 2015, 1:42:27 PM12/28/15
to Основы программирования
Коллеги,
Сегодня в 13-00 подходил на кафедру (время, назначенное учебным отделом), но студентов там не обнаружил. В принципе, это не страшно, главное, чтобы все успешно подготовили и сдали свои программы.
Надеюсь, это случится до нового года.

n.yu.kud...@gmail.com

unread,
Dec 28, 2015, 2:40:09 PM12/28/15
to Основы программирования
У меня один массив на запись, но в один элемент массива алгоритмически только один процесс может записывать данные. Остальные массивы используются на чтение. Как я понимаю, гонок данных не должно быть.
К слову, не только у меня сегодня плавало время работы.

Alexey Sidnev

unread,
Dec 28, 2015, 2:47:08 PM12/28/15
to Основы программирования
А вы не проверяли результаты работы программы от этих двух типов запусков? Возможно это результаты разных тестов (разные seed`ы) или (что странно) на узлах по разному работают генераторы случайных чисел.

n.yu.kud...@gmail.com

unread,
Dec 28, 2015, 2:54:07 PM12/28/15
to Основы программирования
Я не проверял результаты работы на этих тестах и, к сожалению, ничего сказать не могу по этому поводу. Единственное, что запускал на одних и тех же тестах.

n.yu.kud...@gmail.com

unread,
Dec 28, 2015, 3:18:24 PM12/28/15
to Основы программирования
Запустил программу по вашей инструкции непосредственно на узле, но в четвертом пункте поменял команду на следующую:
cat example.input | ./App.out log
Получил как раз те времена, что были днем. 2.91386;10.8646;8.07498

Alexey Sidnev

unread,
Dec 28, 2015, 3:22:27 PM12/28/15
to Основы программирования
Если запускать без taskset, то разброс времени выполнения может быть очень существенным, поэтому все тесты я выполняю с его использованием.

n.yu.kud...@gmail.com

unread,
Dec 28, 2015, 3:23:50 PM12/28/15
to Основы программирования
С taskset не получается запустить. Ошибка появляется.

Alexey Sidnev

unread,
Dec 28, 2015, 3:33:46 PM12/28/15
to Основы программирования
Ошибка - это отлично! Если есть разумное сообщение, то почему бы им не поделиться. Какая ошибка?

n.yu.kud...@gmail.com

unread,
Dec 28, 2015, 3:37:49 PM12/28/15
to Основы программирования
execpv: No such file or directory
failed to execute App.out

edding....@gmail.com

unread,
Dec 28, 2015, 3:40:48 PM12/28/15
to Основы программирования
Возможно, проблема в том, что PATH не экспортировали в довесок к LD_LIBRARY_PATH.

Alexey Sidnev

unread,
Dec 28, 2015, 3:41:39 PM12/28/15
to Основы программирования
Это сообщение говорит о том, что приложение App.out не найдено.
Если у вас есть строка, которая работает, например: "cat example.input | ./app.out ./ouput_name". То преобразуйте её в "cat example.input | taskset -c 16-31 ./app.out ./ouput_name". Этого должно быть достаточно для успешного запуска.

Alexey Sidnev

unread,
Dec 28, 2015, 3:44:09 PM12/28/15
to Основы программирования
С переменной PATH проблем быть не должно.

Alexey Sidnev

unread,
Dec 29, 2015, 1:29:00 PM12/29/15
to Основы программирования
Я выложил результаты проверки работ. Если у кого-то были результаты отличные от представленных, то сообщите какие они были и как они были получены. Будем разбираться.

Alexey Sidnev

unread,
Dec 29, 2015, 2:11:19 PM12/29/15
to Основы программирования
Т.к. ведомость будет заполнена и сдана уже после НГ, то у тех, кто ещё не реализовал достаточно быструю версию программы, есть возможность сделать это в новогодние праздники. Дата проверки работ будет объявлена позже.

Alexey Sidnev

unread,
Jan 9, 2016, 2:57:16 PM1/9/16
to Основы программирования
Я проверю все присланные работы утром 11.01.2016. До этого времени можете прислать версии для получения зачёта или первые версии для сдачи экзамена. Т.к. вычислительная система на которой будут проводится эксперименты доступна каждому, то неожиданностей в результатах не должно быть. Если наблюдаются расхождения в результатах, то необходимо связаться со мной.
13.01.2016 буду оглашены критерии для получения оценок 4 и 5.

Alexey Sidnev

unread,
Jan 11, 2016, 9:20:22 AM1/11/16
to Основы программирования
Работы проверены, результаты можно посмотреть тут: https://sites.google.com/site/alexeysidnev/studentam/optimization-competition-2015/results
  1. Напомню, что заголовок письма должен быть "Конкурс по оптимизации 2015".
  2. Работу необходимо называть solve_ФИО.cpp. Если работа не соответствовала данному названию, то она автоматически переименовывалась в solve_XXX.cpp. В дальнейшем такие работа не будут засчитаны.
  3. Обратите внимание на лог сборки (можно скачать внизу страницы с результатами).
  4. Прочерки в таблице означают, что программа упала во время теста.
  5. Работа Gatchenko Viktor не засчитана, т.к. решающая функция выполняет вывод на экран (это, как минимум, замедляет работу программы). Лог работы программы:
max threads = 16


end work
43.2551;max threads = 16


end work
30.3774;max threads = 16


end work
198.971;


iosif....@gmail.com

unread,
Jan 11, 2016, 9:23:49 AM1/11/16
to Основы программирования
Я планирую внести всех сдавших корректную версию программы, удовлетворяющую критериям, в ведомость и сдать ее в деканат либо во вторник вечером, либо в среду утром.

iosif....@gmail.com

unread,
Jan 12, 2016, 5:33:58 AM1/12/16
to Основы программирования
Всем добрый день!

Я составил списки тех, кто сдал программу, которая работает правильно и укладывается в заданные временные рамки (для получения зачета), а также сопоставил эти списки с ведомостями.

Вот, что у меня получилось.

****ПМИ, группа M0813-2, сдали зачет***
1. Исрафилов Руслан Алиярович
2. Кудрявцев Никита Юрьевич
3. Ларин Антон Вячеславович
4. Соврасов Владислав Валерьевич
5. Скребков Артемий Олегович
6. Кукушкин Даниил Александрович
7. Шишкин Владислав Геннадьевич

****ПМИ, группа M0816-2, сдали зачет***
1. Есягин Иван Николаевич
2. Коротаев Алексей Евгеньевич
3. Смирнов Вячеслав Сергеевич

Кроме того, есть два студента группы M0812, сдавших программу.
1. Костров Алексей Александрович
2. Сабанов Денис Владимирович

Вопросы:
1. Никого не пропустил?
2. Студентам группы M0812: вы собираетесь сдавать зачет или экзамен? Как Вы согласовали этот вопрос с теми, кто курирует магистерскую программу "Математика"? Напишите мне, пожалуйста, в почту.
3. Судя по спискам, которые дал деканат, есть целый ряд студентов, которым нужно сдавать зачет. В какие сроки можно ждать программу? Если есть принципиальное непонимание, как решать задачу, я готов провести консультацию в конце этой/начале следующей недели.

Message has been deleted

Alexey Sidnev

unread,
Jan 15, 2016, 3:58:03 AM1/15/16
to Основы программирования
С критериями на оценку 4 и 5 вышла заминка. Сегодня они будут озвучены.

Alexey Sidnev

unread,
Jan 15, 2016, 12:43:54 PM1/15/16
to Основы программирования
1. Критерии для получения оценок подготовлены (см. презентацию).
2. Я нашёл ошибку в коде, выполняющем проверку корректности. Часть сданных результатов оказалась с ошибками. Обратие ваниение на изменение таблицы с результатами.
3. Следующая дата проверки работ - 17 января.

ganina...@gmail.com

unread,
Jan 15, 2016, 1:00:46 PM1/15/16
to Основы программирования
Алексей Александрович, выложите пожалуйста код, которым вы проверяете корректность во избежании недопониманий задачи. Спасибо.

ganina...@gmail.com

unread,
Jan 16, 2016, 5:16:30 AM1/16/16
to Основы программирования

Alexey Sidnev

unread,
Jan 16, 2016, 1:59:29 PM1/16/16
to Основы программирования
Добавил в архив с шаблоном реализации код программы для проверки корректности (cmp.cpp).
Если ошибка меньше 10^-6, то программа считается корректной.

Alexey Sidnev

unread,
Jan 16, 2016, 2:09:07 PM1/16/16
to Основы программирования
Все свежие присланные работы я проверю завтра во второй половине дня.

Alexey Sidnev

unread,
Jan 17, 2016, 10:11:34 AM1/17/16
to Основы программирования
Проверка работа запущена. Через несколько часов результаты появятся на сайте.

Alexey Sidnev

unread,
Jan 17, 2016, 1:07:57 PM1/17/16
to Основы программирования
Таблица обновлена.

Отмечу большое количество неверных решений.
Выложил выходной файл для 1-го теста с seed=1, чтобы можно было отладить программу: https://drive.google.com/file/d/0B-W6XTyb1bPua1ZNMDl4ajZPZFE/view?usp=sharing

Следующая проверка работ будет завтра днём (около 14:00).

Alexey Sidnev

unread,
Jan 17, 2016, 1:10:57 PM1/17/16
to Основы программирования
Тесты оказались с неправильным seed, запустил снова. Времена появятся позже. Сейчас можно обратить внимание на корректность реализаций.

Alexey Sidnev

unread,
Jan 17, 2016, 3:24:53 PM1/17/16
to Основы программирования
Выложил выходные файлы для всех 3-х тестов с seed=1: /common/optimization

iosif....@gmail.com

unread,
Jan 17, 2016, 3:26:45 PM1/17/16
to Основы программирования
Коллеги,если кто-то хочет найти меня на завтрашней консультации, чтобы получить роспись в зачетке или что-то спросить по поводу алгоритма решения задачи, это можно сделать в 16-00, как и предполагается расписанием. Я буду в аудитории 110 (в расписании обещали заменить аудиторию, но пока этого не сделали).

Что касается вторника, 8-30 выглядит экстремальным временем. Я буду в 110 с 9-40. В 11-00 у меня совещание, желательно пересечься до этого времени. Если для кого-то критично более раннее время, напишите.

lio...@gmail.com

unread,
Jan 17, 2016, 3:29:05 PM1/17/16
to Основы программирования
Алексей Александрович, а что значит зелёное и красное выделение в результатах тестов?

iosif....@gmail.com

unread,
Jan 17, 2016, 3:31:39 PM1/17/16
to Основы программирования
Завтра мне все-таки придется сдать зачетную ведомость, иначе деканат меня не поймет.
Тем, кто не успеет сдать программу (зачет), придется далее брать индивидуальные ведомости.

Экзаменационную ведомость нужно будет сдать вовремя, вряд ли можно задержать больше, чем на день. Прошу всех это учитывать.

Alexey Sidnev

unread,
Jan 17, 2016, 3:32:09 PM1/17/16
to unn_pro...@googlegroups.com
Тесты оказались с неправильным seed и я их запустил снова. Это не должно повлиять на корректность. Времена появятся позже (завтра утром).
Цветом показана корректность реализованного алгоритма (зелёный - алгоритм корректен).


dmitr...@gmail.com

unread,
Jan 18, 2016, 12:36:01 PM1/18/16
to Основы программирования
Здравствуйте, Иосиф Борисович!

Не могли бы вы выложить изменённые критерии по сдаче экзамена?

С уважением,
Д. Водопьянов

Alexey Sidnev

unread,
Jan 18, 2016, 2:20:39 PM1/18/16
to Основы программирования
Программы, которые были присланы утром я добавил в таблицу от 17-го числа. Програмы, которые были присланы днём я добавил в новую таблицу. Сейчас запущу тестироваться программы, которые присланы к текущему моменту.

Alexey Sidnev

unread,
Jan 18, 2016, 2:52:00 PM1/18/16
to Основы программирования
Несколько общих замечаний по реализации:
  1. Для получения оценки 5 достаточно реализовать блочный алгоритм умножения матриц. При этому разбивка на блоки должна выполняться по всем трём размерностям (m, k, n). Размер блока не должен быть квадратным (обычно оптимум достигается на прямоугольных блоках). Однако из-за специфики задачи размер блока по m и n могут совпадать.
  2. В наиболее эффективных реализациях уделяется особое внимание программному коду, который выполняет умножение блоков, т.к. именно на это тратится большая часть времени выполнения программы. Учитывая большое количество информации об этой операции можно реализовать отдельную функцию, которая выполняет умножение блоков. При этом размерность блоков (итераций циклов) необходимо задать константами (размеры блоков). В этом случае компилятор сможет выполнить большое количество операций.
  3. Если есть возможность, то лучше выделять память один раз. Часто выделение динамической памяти снижает производительность.
  4. При умножении матриц A*B, транспонирование матрицы B повышает эффективность, но это не справедливо для матриц малой размерности.
  5. Большое количество параллельных секций негативно сказывается на производительности программы.
      - Не имеет смысла выполнять параллельно маленькие вычислительные участки. 
      - Если есть возможность, то лучше объединить два цикла в один. Например:
Исходный код:
#pragma omp parallel for
for (int i = 0; i < N; ++i)
 
for (int j = 0; j < M; ++j)

Более эффективный:
#pragma omp parallel for
for (int k = 0; k < N*M; ++k)
 
// Вычислить i и j по значению k

iosif....@gmail.com

unread,
Jan 18, 2016, 4:32:01 PM1/18/16
to Основы программирования
Добрый вечер!

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

destro...@gmail.com

unread,
Jan 19, 2016, 1:11:10 AM1/19/16
to Основы программирования
Здравствуйте

Я вам присылал в 8 вечера, а в списке меня не появилось от 18-ого. Почему?

Alexey Sidnev

unread,
Jan 19, 2016, 1:14:22 AM1/19/16
to Основы программирования
Я сейчас занимаюсь проверкой других работ (которые были присланы сегодня ночью). Ваша работа будет внесена в таблицу позже.

michael...@me.com

unread,
Jan 19, 2016, 12:08:13 PM1/19/16
to Основы программирования
Иосиф Борисович, есть ли возможность завтра проставить оценку в зачетку?

michael...@me.com

unread,
Jan 19, 2016, 12:08:59 PM1/19/16
to Основы программирования

iosif....@gmail.com

unread,
Jan 19, 2016, 12:52:09 PM1/19/16
to Основы программирования
Всем добрый вечер!

Завтра нет, можно в четверг.
___________________________________

Итоговые состояния ведомостей (потом удалим из общего доступа, но сейчас нужно для верификации данных). Если увидите ошибку, пишите.

ЭКЗАМЕН
"№
п/п" Фамилия Имя Отчество Экзаменационная оценка
1 Винницкий Владимир Игоревич Отлично
2 Водопьянов Дмитрий Юрьевич Хорошо
3 Ганин Алексей Алексеевич Хорошо
4 Гарина Анастасия Алексеевна Удовлетворительно
5 Голодяев Андрей Сергеевич Отлично
6 Горохов Дмитрий Сергеевич Отлично
7 Еремеева Александра Александровна Удовлетворительно
8 Жбанова Анна Сергеевна Отлично
9 Казанбаев Дмитрий Николаевич Оч. хорошо
10 Карпунин Ярослав Игоревич Оч. хорошо
11 Коротаев Павел Васильевич Оч. хорошо
12 Костин Сергей Сергеевич Отлично
13 Кочанова Ксения Владимировна Оч. хорошо
14 Кумаев Василий Николаевич Отлично
15 Ларин Сергей Игоревич Удовлетворительно
16 Мошков Юрий Александрович Оч. хорошо
17 Несмелов Алексей Евгеньевич Отлично
18 Николаев Кирилл Александрович Хорошо
19 Парамузов Владимир Владимирович Хорошо
20 Сабанов Денис Владимирович Хорошо
21 Смирнов Александр Сергеевич Хорошо
22 Смирнов Михаил Александрович Отлично
23 Тимонова Анастасия Николаевна Оч. хорошо
24 Французова Наталья Сергеевна Оч. хорошо
25 Чатаев Глеб Сергеевич Удовлетворительно
26 Чебоксаринов Андрей Сергеевич Удовлетворительно

ЗАЧЕТ
1 Исрафилов Руслан Алиярович зачтено
2 Кудрявцев Никита Юрьевич зачтено
3 Ларин Антон Вячеславович зачтено
4 Соврасов Владислав Валерьевич зачтено
5 Скребков Артемий Олегович зачтено
6 Кукушкин Даниил Александрович зачтено
7 Шишкин Владислав Геннадьевич зачтено
8 Бабинцева Анна Николаевна зачтено
9 Матвеева Светлана Игоревна зачтено
10 Есягин Иван Николаевич зачтено
11 Коротаев Алексей Евгеньевич зачтено
12 Смирнов Вячеслав Сергеевич зачтено
13 Гатченко Виктор Сергеевич зачтено
14 Костров Алексей Александрович зачтено

Message has been deleted

kuzne...@gmail.com

unread,
Jan 23, 2016, 10:06:48 PM1/23/16
to Основы программирования
icc: error #10236: File not found: '–o'
icc: error #10236: File not found: 'App.out'
А с чем может быть связана эта ошибка?

Alexey Sidnev

unread,
Jan 24, 2016, 3:45:11 AM1/24/16
to Основы программирования
На сколько я понял, вы пытались выполнить команду: icc -std=c++11 -openmp -mkl=parallel main.cpp solve_IvanovII.cpp -o App.out

Скорее всего, вы скопировали строку запуска из презентации и вставили её в консоль. Часто, при сохранении документов короткий дефис превращается в длинный и во время запуска программ могут возникнуть ошибки разбора командной строки. Думаю, что замена '–o'  на '-o' решит проблему. Для надёжности попробуйте набрать команду с клавиатуры, не копируя её.

Alexey Sidnev

unread,
Jan 27, 2016, 2:17:53 PM1/27/16
to Основы программирования
Напомню, что экзаменационная ведомость экзамена была сдана 20.01.2016. Это означает, что всем, у кого работы были присланы и проверены после этой даты необходимо получить в деканате ведомость на пересдачу и подойти с ней к Иосифу Борисовичу.

iosif....@gmail.com

unread,
Feb 15, 2016, 4:15:22 AM2/15/16
to Основы программирования
Прошу тех, кто не сдал зачет/экзамен в установленные сроки, действовать следующим образом:
1. Сдать программу на проверку.
2. При выполнении достаточных для получения положительной оценки показателей написать мне, взять индивидуальную ведомость в уч. отделе, подойти, чтобы я в ней расписался, отнести подписанную ведомость в уч. отдел.

iosif....@gmail.com

unread,
Feb 18, 2016, 12:50:56 PM2/18/16
to Основы программирования
Всем добрый вечер!

Воспользуюсь этой темой, чтобы оповестить всех, что завтра имеет место накладка в расписании. Лекция по моему курсу у вас стоит в пятницу в 14-40 параллельно с другой моей лекцией у первого курса, причем в той же самой аудитории :)
Я заблаговременно сообщил об этом в учебный отдел, но пока ничего не изменилось.
В связи с этим я вынужден сказать, что моя лекция в магистратуре завтра, судя по всему, не состоится.
Просьба оповестить заинтересованных лиц и следить за расписанием.
Приношу извинения за неудобство.

Reply all
Reply to author
Forward
0 new messages