Gerasim@Home | |
---|---|
Платформа | BOINC |
Объём загружаемого ПО | 2 МБ |
Объём загружаемых данных задания | 1 КБ |
Объём отправляемых данных задания | 150 КБ |
Объём места на диске | 2 МБ |
Используемый объём памяти | 10 МБ |
Графический интерфейс | нет |
Среднее время расчёта задания | до 6 часов |
Deadline | 11 дней |
Возможность использования GPU | нет |
Gerasim@Home — российский проект добровольных распределенных вычислений на платформе BOINC. Проект стартовал в тестовом режиме в феврале 2008 года[1]. Отличительной особенностью серверной части проекта, разработанной С. Ю. Валяевым, является использование операционной системы Windows Server 2008 и связки Microsoft SQL Server с ASP.NET, в то время как стандартный набор приложений от разработчиков BOINC требует использования операционной системы Linux или Unix. По состоянию на 23 июля 2015 года в проекте приняли участие 1999 пользователей (890 компьютеров) из 62 стран, обеспечивая производительность 1—5 терафлопс. Участвовать в проекте может любой желающий, обладающий компьютером с выходом в Интернет, установив на него программу BOINC Manager.
Проект стартовал в тестовом режиме в феврале 2008 года[1], используя в качестве тестового расчетного модуля программу gsm для поиска простых чисел.
В июне 2010 года на кафедре вычислительной техники Юго-Западного государственного университета было разработано расчетное приложение separator, целью которого является построение разбиений параллельных граф-схем алгоритмов логического управления, получаемых различными эвристическими методами, с целью сравнения качества получаемых решений и выработки рекомендаций о границах целесообразности применения методов. Первая часть расчетов была завершена в сентябре 2011 г.
В январе 2013 года был начат эксперимент[2] по исследованию возможностей применения жадной стратегии синтеза разбиения с ограничением на выбор вершин из смежной окрестности текущего блока[3].
В марте 2014 года начата новая серия экспериментов, целью которой является апробация применения эвристических методов применительно к решению известных задач теории графов на примере задачи поиска кратчайшего пути в графе и для поиска разбиений[4].
В июне 2014 года стартовала серия экспериментов с целью исследования возможности использования случайного перебора[5][6] с фиксированным числом итераций при построении разбиений.
В феврале 2015 года запущено продолжение серии экспериментов, целью которых является апробация применения эвристических методов применительно к решению задачи поиска кратчайшего пути в графе с использованием возвратной стратегии[7], а также методов имитации отжига[8], перебора с ограничением глубины[9][10], различных вариаций муравьиного алгоритма[11][12], генетического алгоритма[13] и алгоритма пчелиной колонии[14].
В июне 2016 года запущен вычислительный эксперимент, целью которого является подсчет числа диагональных латинских квадратов порядка 9 (последовательность A274171 в OEIS и последовательность A274806 в OEIS)[15].
В октябре 2016 в проекте был начат эксперимент, направленный на исследование эффективности методов случайных блужданий[16] и роя частиц[17][18] в задаче поиска кратчайшего пути в графе.
В начале 2017 года в проекте был организован эксперимент, направленный на определение значений ряда комбинаторных характеристик диагональных латинских квадратов и их ортогональных пар (греко-латинских квадратов) порядка 8[19]. В марте 2017 стартовал эксперимент по получению случайных пар ортогональных диагональных латинских квадратов порядка 10 с целью формирования списка их уникальных канонических форм[20]. С 3 по 16 июня 2017 года в проекта осуществлялся подсчет числа симметричных диагональных латинских квадратов порядка 10[21]. 23 октября 2017 года в проекта запущен эксперимент, направленный на анализ симметричных в одной плоскости квадратов при построении пар ортогональных диагональных латинских квадратов[22][23].
В декабре 2018 года в проекте был начат эксперимент по изучению эффективности эвристических методов в задаче раскраски графов общего вида[24].
Необходимость в отыскании разбиения, (суб)оптимального по ряду показателей качества, возникает при проектировании систем логического управления, используемых для осуществления логического управления различными дискретными системами (цифровыми схемами, станками с ЧПУ, роботизированными сборочными линиями и т. д.). При проектировании подобных систем возникает ряд комбинаторных многокритериальных оптимизационных задач на дискретных структурах (графах), к которым и относится задача синтеза разбиения заданной граф-схемы алгоритма управления[25][26][27], в соответствии с которым должна работать разрабатываемая система логического управления. Отыскание точного решения (глобального оптимума) в большинстве практических случаев невозможно из-за того, что поставленная задача принадлежит к классу NP, поэтому на практике обычно ограничиваются применением эвристических методов, дающих решения неплохого качества за приемлемое время.
Качество найденного решения оценивается как степень минимизации частных показателей качества, к которым относятся:
Интегральная оценка качества разбиения рассчитывается как взвешенная сумма нормированных значений частных показателей качества.
При практической реализации системы логического управления приходится учитывать ограничения технологического характера, к которым в первую очередь относятся:
Ограничение не является критическим и может быть исключено из рассмотрения путём дублирования контроллеров, имеющих одинаковые входы и выпоняющих однотипные микропрограммы. С целью упрощения внутренней структуры контроллера накладывается дополнительное структурное ограничение на невозможность размещения параллельных вершин в составе одного блока разбиения (контроллера).
В качестве эвристических методов поиска разбиений в вычислительных экспериментах принимали участие:
Методы характеризуются существенно различной трудоемкостью реализации, временной и емкостной сложностью алгоритмов преобразований и качеством получаемых решений при различных значениях технологических ограничений. При проведении сравнения качества методов необходимо исследование различных областей пространства параметров , где — число вершин в составе граф-схем алгоритмов, что является вычислительно сложной задачей. В процессе расчетов были проанализированы отдельные срезы пространства параметров, на основании чего было выявлено существенно различное поведение методов синтеза разбиений по мере усиления или ослабления значений технологических ограничений.
Для каждой точки выбранного среза пространства параметров осуществляется построение выборки параллельных алгоритмов логического управления с псевдослучайной структурой, построение их разбиений указанным методом и оценка качества, что требует от нескольких минут (малые значения ) до нескольких часов (большие значения ) вычислительного времени. Полученные выборки числовых значений объёмом около 200 КБ каждая передаются на сервер проекта и ожидают последующей обработки. Общий объём полученных данных (без учета избыточности) составил 235 ГБ, а вычислительные затраты — 51,6 экзафлоп (818 ГГц-лет). По сравнению с реализацией на двухъядерном процессоре Core 2 Duo с частотой 1,86 ГГц выигрыш во времени, полученный за счет параллельной обработки с использованием грид, составил 155 раз. Постобработка полученных результатов[31][32] заняла около суток вычислительного времени и заключалась в расчете средних значений параметров качества и вероятностей получения разбиения с минимальным значением выбранного показателя качества, в результате чего были получены искомые двумерные карты общим объёмом 96 МБ, которые можно использовать для подробного анализа поведения методов в различных областях пространства параметров.
В марте 2014 года стартовала[4] очередная серия вычислительных экспериментов, отличительной особенностью которой является поддержка одновременного выполнения нескольких экспериментов. С целью тестирования методов решения дискретных оптимизационных задач был реализован соответствующий расчетный модуль, статически подключаемый к приложению spstarter.exe. Помимо приложения separator, вошедшего в состав нового расчетного модуля, реализована возможность анализа качества решений тестовой задачи нахождения кратчайшего пути в графе с использованием ряда подходов (алгоритм Дейкстры, жадный алгоритм, случайный перебор, взвешенный случайный перебор[33], их модификации с поддержкой комбинаторных возвратов[7], вариации алгоритма муравьиной колонии[11][12], метод имитации отжига, перебор с ограничением глубины или числа рассматриваемых ветвей дерева, генетический алгоритм[13], алгоритм пчелиной колонии[14], метод случайных блужданий и вариации метода роя частиц) с целью выявления их сильных и слабых сторон. Наилучшие результаты были в рассматриваемой задаче были продемонстрированы методом муравьиной колонии и генетическим алгоритмом[34][35].
Асимптотическое поведение числа диагональных латинских квадратов (ДЛК) с ростом их размерности N до выполненных в проекте расчетов было неизвестно. В результате разработки высокоэффективного расчетного модуля, который использует ряд приемов алгоритмической и высокоуровневой оптимизации[36][37][38][39][40][41], удалось достичь темпа генерации в 6,6 млн. ДЛК/с, что позволило определить число ДЛК до N<10 (последовательность A274171 в OEIS и последовательность A274806 в OEIS). Для этого потребовалось 3 месяца расчетов на грид с реальной производительностью 2—5 TFLOP/s[42] и 3 месяца расчетов на вычислительном кластере «Академик В.М. Матросов» СО РАН с целью проверки и подтверждения полученного результата[43].
С использованием аналогичных алгоритмических принципов был осуществлен подсчет числа симметричных диагональных латинских квадратов порядка N<11[21] и определение минимального и максимального числа трансверсалей в диагональных латинских квадратах порядка N<9[44][45][46].
Обсуждение проекта в форумах:
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .