Российские распределенные вычисления на платформе BOINC
Форум участников распределённых вычислений.

Добро пожаловать, Гость! Чтобы использовать все возможности Вход или Регистрация.

Уведомление

Icon
Error

102 Страницы«<100101102
Опции
К последнему сообщению К первому непрочитанному
Offline evatutin  
#2021 Оставлено : 2 мая 2017 г. 1:57:27(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,286
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 899 раз
Поблагодарили: 1448 раз в 706 постах
До нашей конференции остается еще 2 недели, а сборник материалов уже готов. Пользуясь случаем, работы с моим участием я выложил в открытый доступ:

1. Затолокин Ю.А., Ватутин Э.И., Титов В.С. Оценка реальной производительности вычислений на графических процессорах с поддержкой технологии OpenCL в задаче умножения матриц // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание – 2017). Курск: изд-во ЮЗГУ, 2017. С. 164–167.

2. Попов Д.В., Наджаджра М.Х., Ватутин Э.И. Анализ временных затрат эвристических методов в задаче поиска кратчайшего пути в графе с использованием современных видеокарт с поддержкой технологии CUDA // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание – 2017). Курск: изд-во ЮЗГУ, 2017. С. 285–287.

3. Ватутин Э.И., Кочемазов С.Е., Заикин О.С. Оценка комбинаторных характеристик диагональных латинских квадратов // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание – 2017). Курск: изд-во ЮЗГУ, 2017. С. 98–100.

4. Манзюк М.О., Ватутин Э.И., Кочемазов С.Е., Заикин О.С. Интересные свойства ортогональных диагональных латинских квадратов 7 и 8 порядка // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание – 2017). Курск: изд-во ЮЗГУ, 2017. С. 235–237.

5. Пшеничных А.О., Ватутин Э.И. Сравнение качества решений эвристических методов оценки хроматического числа графа // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание – 2017). Курск: изд-во ЮЗГУ, 2017. С. 287–289.


Коротко по каждой из них.

Первая работа выполнена моим магистрантом, в ней он попробовал умножать матрицы на OpenCL (я думаю многие помнят, что не так давно мы совместно тестировали CPU- и CUDA-реализации данного действия). Краткий вывод: где-то получается быстрее CUDA'ы около 2 раз, где-то медленнее в те же 2 раза. Самое неприятное то, что на данный момент в 2 раза медленнее получается как раз для самой быстрой реализации Не получается. Сейчас мы готовим большую статью по этой тематике, там будут графики и более подробное исследование.

Во второй работе еще один мой магистрант попробовал переложить группу эвристических методов с последовательным формированием решений с CPU на CUDA'у. При этом был получен выигрыш в среднем от 5 до 15 раз, что с одной стороны неплохо по сравнению с однопоточной CPU-реализацией, однако с другой сильно меньше потенциальных вычислительных возможностей GPU с тысячами вычислителей на борту. Данный факт является в общем-то известным: задачи комбинаторики плохо ложатся на GPU.

В третьей работе был произведен расчет нескольких последовательностей, имеющих прямое отношение к диагональным латинским квадратам:
* 1, 0, 0, 8, 3, 32, 7 — минимально возможное число трансверсалей в диагональных латинских квадратах порядка N от 1 до 7;
* 1, 0, 0, 8, 15, 32, 133 — максимально возможное число трансверсалей в диагональных латинских квадратах порядка N от 1 до 7;
* 1, 0, 0, 4, 1, 2, 0 — минимально возможное число диагональных трансверсалей в диагональных латинских квадратах порядка N от 1 до 7;
* 1, 0, 0, 4, 5, 6, 27 — максимально возможное число диагональных трансверсалей в диагональных латинских квадратах порядка N от 1 до 7;
* 0, 2, 64, 3612672 — число симметричных нормализованных диагональных латинских квадратов порядка 2, 4, 6 и 8 (для нечетных порядков симметричные ДЛК не существуют);
* 0, 2, 0, 15780 — число дважды симметричных (по вертикали и горизонтали одновременно) нормализованных диагональных латинских квадратов порядка 2, 4, 6 и 8 (как видно, они существуют только для порядков, кратных 4).
Указанные последовательности являются новыми, они не представлены в OEIS и будут добавлены туда в самое ближайшее время. Одно исключение: последовательность 1 совпадает с аналогичной для ЛК (а у нас для ДЛК), кроме размерностей 2 и 3, для которых ДЛК не существуют.

В четвертой работе, большая часть которой сделана hoarfrost'ом, им было найдено несколько интересных особенностей:
* Для некоторых размерностей ортогональные диагональные латинские квадраты представляют собой пару квадратов с переставленными строками (для некоторых размерностей существуют только такие ОДЛК, для других и такие, и общего вида). Интерес этого наблюдения в том, что перестановка строк с сохранением ограничений диагональности квадрата выполняется быстрее, чем построение множества трансверсалей, поэтому соответствующие ОДЛК можно также находить быстрее. К сожалению оказалось, что для интересующей нас размерности N=10 таких пар нет (по крайней мере среди найденных и вошедших в список, формируемый citerra'ой при непосредственной поддержке текущей серии WU'шек Gerasim@Home и не только).
* Для N=10 мы ищем и не можем найти тройку, а тут были найдены несколько квартетов попарно-ортогональных ДЛК порядка 7 (в тезисы поместился один из них).
* Для размерности N=8 были найдены 6-ки из попарно-ортогональных ДЛК (в тезисах есть один из квадратов 6-ки, остальные можно достроить).
* Для размерности N=10 сегодня известны и входят в список citerra'ы однушки, двушки, трешка, четверки, шестерки и восьмерки ОДЛК; а для N=8 существует семейство ОДЛК, в котором одному квадрату (в тезисах он тоже есть) ортогональны сразу 824 других!

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

PS. Всех интересующихся подробностями ждем на конференции, которая, напомню, стартует 16 мая на базе нашей кафедры вычислительной техники Юго-Западного государственного университета Present. Может быть в последний раз...

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 3 пользователей поблагодарили evatutin за этот пост.
Dancer King оставлено 03.05.2017(UTC), Vitalii Koshura оставлено 06.05.2017(UTC), Duce H_ K_ оставлено 22.05.2017(UTC)
Offline Vitalii Koshura  
#2022 Оставлено : 6 мая 2017 г. 15:07:25(UTC)
Vitalii Koshura


Статус: Новичок

Группы: Member
Зарегистрирован: 24.04.2015(UTC)
Сообщений: 9
Мужчина
Украина
Откуда: Odessa

Сказал «Спасибо»: 11 раз
Поблагодарили: 12 раз в 6 постах
Сайт http://gerasim.boinc.ru/ , кажется, немножечко упал.
Offline AlexA  
#2023 Оставлено : 6 мая 2017 г. 15:21:04(UTC)
AlexA


Статус: Administration

Медали: Переводчику: За помощь в создании сайта

Группы: Editors, Member, Administration, Russia Team Group, Moderators
Зарегистрирован: 02.10.2007(UTC)
Сообщений: 6,060
Мужчина
Российская Федерация
Откуда: "Russia Team"

Сказал «Спасибо»: 1172 раз
Поблагодарили: 1491 раз в 823 постах
Автор: Vitalii Koshura Перейти к цитате
Сайт http://gerasim.boinc.ru/ , кажется, немножечко упал.

Запросто. Раньше они с BOINC.RU "падали вместе", поскольку "крутились" на одном компе и в одном месте. Теперь их разнесли и проблемы возникают независимо друг от друга Не получается

Offline evatutin  
#2024 Оставлено : 25 мая 2017 г. 15:34:11(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,286
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 899 раз
Поблагодарили: 1448 раз в 706 постах
Что-то мы все о квадратах, да о квадратах... smile Опубликована статья

Ватутин Э.И., Титов В.С. К вопросу о выборе структуры логического мультиконтроллера // Телекоммуникации. 2017. № 3. С. 2–12.

Она находится несколько в стороне от результатов расчетов в проекте, но косвенно связана с ними. В ней показано, что если допустить незначительное 5%-е ухудшение качества основных показателей, то на этом можно до 5-10 раз снизить аппаратную сложность проектируемой системы логического управления (в статье даны конкретные оценки параметров подобных систем, ориентированных на выполнение алгоритмов логического управления с заданным числом вершин). Кроме того показано, что структура системы управления с большим числом простых контроллеров является предпочтительной.



И на предстоящий BOINC FAST отправлено 2 статьи:

Vatutin E.I., Kochemazov S.E., Zaikin O.S., Valyaev S.Yu. Enumerating the Transversals for Diagonal Latin Squares of Small Order
Vatutin E.I. Comparison of decisions quality of heuristic methods with sequential formation of the decision in the graph shortest path problem

Отредактировано пользователем 25 мая 2017 г. 15:54:30(UTC)  | Причина: Не указана


kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 1 пользователь поблагодарил evatutin за этот пост.
Vitalii Koshura оставлено 28.05.2017(UTC)
Offline evatutin  
#2025 Оставлено : 27 мая 2017 г. 16:49:39(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,286
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 899 раз
Поблагодарили: 1448 раз в 706 постах
И снова о квадратах smile. Опубликована работа

Ватутин Э.И., Кочемазов С.Е., Заикин О.С., Манзюк М.О., Титов В.С. Оценка комбинаторных характеристик для пар ортогональных диагональных латинских квадратов // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов (МППОС'2017). Барнаул: Изд-во Алт. ун-та, 2017. С. 104–111.

В ней основное внимание было уделено подсчету числа пар ОДЛК в зависимости от размера квадрата N — последовательность

1, 0, 0, 2, 4, 0, 320

и определению максимального числа различных ДЛК, ортогонального одному ДЛК — последовательность

1, 0, 0, 1, 1, 0, 3, 824?, ?, 8?.

Последние 3 члена последней последовательности определены не точно, т.к. полный перебор в данном случае на одной машине провести затруднительно. Найденные последовательности новые, они не представлены в OEIS и будут добавлены туда в самое ближайшее время 199. Кроме того, в статье приведены ДЛК с соответствующими рекордными характеристиками

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
thanks 1 пользователь поблагодарил evatutin за этот пост.
Vitalii Koshura оставлено 28.05.2017(UTC)
Offline whitefox  
#2026 Оставлено : 27 мая 2017 г. 17:50:19(UTC)
whitefox


Статус: Интересующийся

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 85

Сказал(а) «Спасибо»: 23 раз
Поблагодарили: 78 раз в 48 постах
Автор: evatutin Перейти к цитате

и определению максимального числа различных ДЛК, ортогонального одному ДЛК — последовательность

1, 0, 0, 1, 1, 0, 3, 824?, ?, 8?.

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

Полагаю, что для N = 8 полный перебор вполне возможен. На моём десятилетнем ноутбуке проверка ДЛК10 на ОДЛК выполняется примерно в 600 раз медленнее чем проверка на КФ (для ДЛК8 этот коэффициент будет меньше), а перебор всех 4873096 КФ ДЛК8 занял 93 секунды. То есть в 16 часов вполне можно уложиться.

Отредактировано пользователем 27 мая 2017 г. 18:10:09(UTC)  | Причина: Не указана

Offline evatutin  
#2027 Оставлено : 27 мая 2017 г. 19:33:04(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,286
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 899 раз
Поблагодарили: 1448 раз в 706 постах
Автор: whitefox Перейти к цитате
Полагаю, что для N = 8 полный перебор вполне возможен. На моём десятилетнем ноутбуке проверка ДЛК10 на ОДЛК выполняется примерно в 600 раз медленнее чем проверка на КФ (для ДЛК8 этот коэффициент будет меньше), а перебор всех 4873096 КФ ДЛК8 занял 93 секунды. То есть в 16 часов вполне можно уложиться.


Эти вещи считались тогда, когда КФы я строить еще не умел. Теперь умею и разумеется данный эксперимент будет работать куда быстрее. Но на самом деле для N=8 значения уже посчитаны, но еще не опубликованы 199. Раз так, то раскрываю карты: 824 — максимальное число ОДЛК для N=8, а общее число ОДЛК у меня получилось 1322496, можете меня перепроверить, если есть такое желание smile

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#2028 Оставлено : 27 мая 2017 г. 19:55:37(UTC)
whitefox


Статус: Интересующийся

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 85

Сказал(а) «Спасибо»: 23 раз
Поблагодарили: 78 раз в 48 постах
Автор: evatutin Перейти к цитате
можете меня перепроверить, если есть такое желание smile

Не буду, я вам верю. smile

Offline evatutin  
#2029 Оставлено : 27 мая 2017 г. 20:16:01(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,286
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 899 раз
Поблагодарили: 1448 раз в 706 постах
Автор: whitefox Перейти к цитате
Не буду, я вам верю. smile


Никому нельзя доверять, мне можно (с)
На самом деле перепроверить надо, чтобы не ошибиться. При подсчете ДЛК порядка 9 я ошибся, хорошо, что перепроверили. Тут я тоже напортачил при генерации WU'шек, но это потом получилось легко исправить. И тут проверить надо бы 199

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#2030 Оставлено : 28 мая 2017 г. 17:59:08(UTC)
whitefox


Статус: Интересующийся

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 85

Сказал(а) «Спасибо»: 23 раз
Поблагодарили: 78 раз в 48 постах
Автор: evatutin Перейти к цитате
И тут проверить надо бы 199


Ок, на досуге напишу программу.

thanks 3 пользователей поблагодарили whitefox за этот пост.
evatutin оставлено 28.05.2017(UTC), citerra оставлено 28.05.2017(UTC), AlexA оставлено 28.05.2017(UTC)
Offline evatutin  
#2031 Оставлено : 28 мая 2017 г. 23:40:34(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,286
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 899 раз
Поблагодарили: 1448 раз в 706 постах
В проект добавлены новые версии расчетного модуля 2.50 и 2.51. В них поиск множества трансверсалей и построение ортогонального квадрата из них делается через алгоритм танцующих связей (он же DLX), что позволяет поднять темп обработки ДЛК где-то в 1,5х раза (у меня на Core i7 4770 время обработки WU'шки уменьшается примерно с 20 до 14 мин) по сравнению с реализацией на базе битовой арифметики, которая использовалась до этого. Объем работы в рамках одной WU'шки увеличен с 200k до 300k ДЛК, время счета WU'шки сильно измениться не должно

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#2032 Оставлено : 29 мая 2017 г. 11:18:55(UTC)
whitefox


Статус: Интересующийся

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 85

Сказал(а) «Спасибо»: 23 раз
Поблагодарили: 78 раз в 48 постах
evatutin

Выполнил проверку. Результат следующий:
Код:
mate[1] = 786
mate[2] = 94
mate[3] = 24
mate[4] = 111
mate[5] = 6
mate[6] = 5
mate[7] = 11
mate[8] = 2
mate[9] = 2
mate[10] = 2
mate[11] = 2
mate[12] = 4
mate[13] = 1
mate[14] = 5
mate[16] = 9
mate[18] = 3
mate[19] = 3
mate[20] = 5
mate[22] = 3
mate[24] = 2
mate[28] = 10
mate[40] = 1
mate[45] = 3
mate[48] = 1
mate[50] = 2
mate[108] = 3
mate[116] = 2
mate[128] = 1
mate[131] = 1
mate[824] = 1

Всего КФ ОДЛК: 1105
Время работы:   702.422 сек
Offline evatutin  
#2033 Оставлено : 29 мая 2017 г. 11:50:35(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,286
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 899 раз
Поблагодарили: 1448 раз в 706 постах
Автор: whitefox Перейти к цитате
Выполнил проверку. Результат следующий:


Это я так понимаю максимальное число ОДЛК для N=8, подтверждающее цифру 824?

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Offline whitefox  
#2034 Оставлено : 29 мая 2017 г. 12:27:22(UTC)
whitefox


Статус: Интересующийся

Группы: Member
Зарегистрирован: 08.10.2016(UTC)
Сообщений: 85

Сказал(а) «Спасибо»: 23 раз
Поблагодарили: 78 раз в 48 постах
Автор: evatutin Перейти к цитате
Автор: whitefox Перейти к цитате
Выполнил проверку. Результат следующий:


Это я так понимаю максимальное число ОДЛК для N=8, подтверждающее цифру 824?

Да. Соответственно, mate[1] = 786 означает, что 786 КФ ОДЛК8 имеют по одному соквадрату (786 "однушек" ), mate[2] = 94 означает, что 94 КФ ОДЛК8 имеют по два соквадрата (94 "двойки" ) и так далее.
Offline evatutin  
#2035 Оставлено : 29 мая 2017 г. 12:46:04(UTC)
evatutin


Статус: Старожил

Медали: Первооткрывателю: Результат в проекте SAT@homeРазработчику: За организацию проекта Gerasim@home

Группы: Editors, Member
Зарегистрирован: 08.06.2010(UTC)
Сообщений: 3,286
Откуда: Russia, Kursk

Сказал(а) «Спасибо»: 899 раз
Поблагодарили: 1448 раз в 706 постах
Автор: whitefox Перейти к цитате
Да. Соответственно, mate[1] = 786 означает, что 786 КФ ОДЛК8 имеют по одному соквадрату (786 "однушек" ), mate[2] = 94 означает, что 94 КФ ОДЛК8 имеют по два соквадрата (94 "двойки" ) и так далее


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

kvt.kurskstu team founder
Gerasim@home scientist
My numbers are 5056994653507584 and 1835082219864832081920. Why not? smile
Пользователи, просматривающие эту тему
Guest (3)
102 Страницы«<100101102
Быстрый переход  
Вы не можете создавать новые темы в этом форуме.
Вы не можете отвечать в этом форуме.
Вы не можете удалять Ваши сообщения в этом форуме.
Вы не можете редактировать Ваши сообщения в этом форуме.
Вы не можете создавать опросы в этом форуме.
Вы не можете голосовать в этом форуме.

Boinc.ru theme. Boinc.ru
Форум YAF 2.1.1 | YAF © 2003-2017, Yet Another Forum.NET
Страница сгенерирована за 0.242 секунды.