Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только... - Страница 158 - Исследование свойств диагональных латинских квадратов в проектах добровольных распределенных вычислений и не только... - Страница 158 - Форум

#1571 · 11.10.2022, 12:49

Цитата: Yura12 от 08.10.2022, 10:51

Вопрос, а будет ли в этой статье руководство для людей, как установить BOINC и присоединиться к счёту?

И второй вопрос к SerVal, а сам сервер для Gerasim сейчас что-нибудь считает, пока там нет заданий?

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

PS. Меня тут зовут в местный Кванториум (https://vk.com/kvantorium46) порешать задачки по программированию с продвинутыми школьниками — порешаем, отказываться грех. Если по итогам сойдемся на том, что данная встреча получилась обоюдно интересной, в следующей встрече попробую осветить BOINC...

PinkFloyd, V0d01ey и Шмяка отреагировали на эту запись.

#1572 · 13.10.2022, 01:03

Интересно, а сам сервер для Gerasim сейчас что-нибудь считает, пока там нет заданий?

Считает yoyo@home в 24 потока.

#1573 · 13.10.2022, 11:05

А почему не отечественные RakeSearch и SiDock ?

#1574 · 13.10.2022, 16:08

Цитата: Yura12 от 13.10.2022, 11:05

А почему не отечественные RakeSearch и SiDock ?

Потому, что я не считаю проект SiDock отечественным. А RakeSearch иногда выдаёт задания, которые считаются сутками (непонятно почему, и за такими заданиями надо следить) .

#1575 · 14.10.2022, 01:18

Цитата: evatutin от 14.10.2022, 01:18
Эксперимент по построению спектров быстровычислимых числовых характеристик ДЛК порядка 9 успешно завершен!

Напомню краткую историю вопроса, а затем перейдем к анализу полученных результатов... К быстровычислимым числовым характеристикам ДЛК относятся число трансверсалей, диагональных трансверсалей и интеркалятов (еще сюда же можно отнести число ОДЛК, но данный спектр уже был построен ранее, его сейчас не рассматриваем). Полный спектр для выбранной числовой характеристики строится следующем образом: полным перебором перечисляются все ДЛК заданной размерности N, для каждого из них вычисляется значение числовой характеристики, неповторяющиеся значения в совокупности с одним из подтверждающих квадратов добавляются в формируемый спектр. При перечислении квадратов полным перебором можно ограничиться только нормализованными ДЛК (одним из способом), т.к. значение числовой характеристики инвариантно относительно нормализации. Такой подход к построению спектров работает для порядков до N=7 включительно, начиная с N=8 уже начинаются первые проблемы, т.к. так считать становится долго. Выходом из ситуации является либо хитрый перебор на базе главных классов ДЛК, либо использование эвристических методов. С использованием первого подхода спектры для N=8 строятся довольно быстро, размерность N=9 является последней, для которой на современном уровне развития математики и аппаратного обеспечения в принципе можно построить полные спектры, далее (с N=10 и выше) можно строить только эвристические аппроксимации спектров.

Перебор всех СКФ ДЛК порядка 9 в совокупности с расчетом быстровычислимых числовых характеристик занимает около 3-4 месяцев на гриде, ввиду чего сперва была предпринята попытка эвристической аппроксимации данных спектров. Для этого было выполнено построение ряда начальных опорных спектров с последующим их расширением путем поворотов циклов и интеркалятов. В результате были получены спектры со следующими мощностями:

* число трансверсалей — 359 элементов;
* число диагональных трансверсалей — 176 элементов;
* число интеркалятов — 62 элемента.

В графическом виде данные спектры представлены на рисунке слева. Данные эксперименты были выполнены на моей машине с относительно небольшими вычислительными затратами. Ну а далее пришла очередь полнопереборного эксперимента. С использованием разработанного генератора СКФ ДЛК порядка 9 (соответствующая статья про это, напомню, принята к опубликованию в журнале Телекоммуникации) были получены все СКФ для каждой из 20 линеек. В каждой линейке было сгенерировано около 40 - 60 тыс. WU'шек со временем счета от нескольких десятков минут до 3-4 часов в зависимости от кратности линейки (и зависящего от нее числа дозаполнений (СНДЛК) и СКФ). Линейки с 1 по 8 были обработаны в проекте Gerasim@Home, линейки с 9 по 20 — в проекте RakeSearch. Расчет был выполнен с кворумом 2, т.к. в данном эксперименте правильными должны быть все постобрабатываемые результаты, ошибок в ходе обработки и последующей постобработки выявлено не было. В общей сложности на выполнение обработки всех линеек потребовалось около 5 месяцев расчетов с реальной производительностью порядка 7—8 TFLOP/s при нескольких параллельно работающих подпроектах. В результате постобработки были получены следующие спектры:

* число трансверсалей — 406 элементов;
* число диагональных трансверсалей — 182 элемента;
* число интеркалятов — 64 элемента.

Графическое представление данных спектров приведено в правой части рисунка.

Число обработанных СКФ ДЛК составило -1913760638 и совпало с полученным ранее значением 3292326155394 :). Точнее, оно конечно же вроде бы не совпало и вообще не может быть отрицательным, но вина здесь в том, что по ошибке для подсчета их числа был взят знаковый 4-байтовый целый тип, а надо было брать 8-байтовый, в итоге получили переполнение. Если не полениться и сравнить младшие биты полученных чисел в двоичном представлении, то они совпадут, что с близкой к единице вероятностью гарантирует корректность выполненных расчетов: были проанализированы все СКФ ДЛК.

Для полученных полных спектров была произведена попытка эвристического расширения путем вращения циклов и интеркалятов: расширить их не удалось, что не удивительно и является косвенным подтверждением их корректности и полноты. Таким образом, полученные значения мощностей с большой долей вероятности являются верными и позволяют получить значения членов a(9) числовых рядов A344105, A345370 и A345760 в OEIS, соответствующие правки будут добавлены по мере подтверждения текущей серии. До этого благодаря мощностям эвристически полученных аппроксимаций спектров были известны только нижние ограничения.

Ну и в заключение, полученные цифры позволяют оценить эффективность эвристических методов построения аппроксимаций спектров. Так для спектра числа трансверсалей эвристически удалось получить 88% входящих в него значений, а для спектров числа диагональных трансверсалей и интеркалятов — по 97%, что подтверждает достаточно высокую эффективность применяемых эвристик.

Эксперимент по построению спектров быстровычислимых числовых характеристик ДЛК порядка 9 успешно завершен!

Напомню краткую историю вопроса, а затем перейдем к анализу полученных результатов... К быстровычислимым числовым характеристикам ДЛК относятся число трансверсалей, диагональных трансверсалей и интеркалятов (еще сюда же можно отнести число ОДЛК, но данный спектр уже был построен ранее, его сейчас не рассматриваем). Полный спектр для выбранной числовой характеристики строится следующем образом: полным перебором перечисляются все ДЛК заданной размерности N, для каждого из них вычисляется значение числовой характеристики, неповторяющиеся значения в совокупности с одним из подтверждающих квадратов добавляются в формируемый спектр. При перечислении квадратов полным перебором можно ограничиться только нормализованными ДЛК (одним из способом), т.к. значение числовой характеристики инвариантно относительно нормализации. Такой подход к построению спектров работает для порядков до N=7 включительно, начиная с N=8 уже начинаются первые проблемы, т.к. так считать становится долго. Выходом из ситуации является либо хитрый перебор на базе главных классов ДЛК, либо использование эвристических методов. С использованием первого подхода спектры для N=8 строятся довольно быстро, размерность N=9 является последней, для которой на современном уровне развития математики и аппаратного обеспечения в принципе можно построить полные спектры, далее (с N=10 и выше) можно строить только эвристические аппроксимации спектров.

Перебор всех СКФ ДЛК порядка 9 в совокупности с расчетом быстровычислимых числовых характеристик занимает около 3-4 месяцев на гриде, ввиду чего сперва была предпринята попытка эвристической аппроксимации данных спектров. Для этого было выполнено построение ряда начальных опорных спектров с последующим их расширением путем поворотов циклов и интеркалятов. В результате были получены спектры со следующими мощностями:

* число трансверсалей — 359 элементов;
* число диагональных трансверсалей — 176 элементов;
* число интеркалятов — 62 элемента.

В графическом виде данные спектры представлены на рисунке слева. Данные эксперименты были выполнены на моей машине с относительно небольшими вычислительными затратами. Ну а далее пришла очередь полнопереборного эксперимента. С использованием разработанного генератора СКФ ДЛК порядка 9 (соответствующая статья про это, напомню, принята к опубликованию в журнале Телекоммуникации) были получены все СКФ для каждой из 20 линеек. В каждой линейке было сгенерировано около 40 - 60 тыс. WU'шек со временем счета от нескольких десятков минут до 3-4 часов в зависимости от кратности линейки (и зависящего от нее числа дозаполнений (СНДЛК) и СКФ). Линейки с 1 по 8 были обработаны в проекте Gerasim@Home, линейки с 9 по 20 — в проекте RakeSearch. Расчет был выполнен с кворумом 2, т.к. в данном эксперименте правильными должны быть все постобрабатываемые результаты, ошибок в ходе обработки и последующей постобработки выявлено не было. В общей сложности на выполнение обработки всех линеек потребовалось около 5 месяцев расчетов с реальной производительностью порядка 7—8 TFLOP/s при нескольких параллельно работающих подпроектах. В результате постобработки были получены следующие спектры:

* число трансверсалей — 406 элементов;
* число диагональных трансверсалей — 182 элемента;
* число интеркалятов — 64 элемента.

Графическое представление данных спектров приведено в правой части рисунка.

Число обработанных СКФ ДЛК составило -1913760638 и совпало с полученным ранее значением 3292326155394 :). Точнее, оно конечно же вроде бы не совпало и вообще не может быть отрицательным, но вина здесь в том, что по ошибке для подсчета их числа был взят знаковый 4-байтовый целый тип, а надо было брать 8-байтовый, в итоге получили переполнение. Если не полениться и сравнить младшие биты полученных чисел в двоичном представлении, то они совпадут, что с близкой к единице вероятностью гарантирует корректность выполненных расчетов: были проанализированы все СКФ ДЛК.

Для полученных полных спектров была произведена попытка эвристического расширения путем вращения циклов и интеркалятов: расширить их не удалось, что не удивительно и является косвенным подтверждением их корректности и полноты. Таким образом, полученные значения мощностей с большой долей вероятности являются верными и позволяют получить значения членов a(9) числовых рядов A344105, A345370 и A345760 в OEIS, соответствующие правки будут добавлены по мере подтверждения текущей серии. До этого благодаря мощностям эвристически полученных аппроксимаций спектров были известны только нижние ограничения.

Ну и в заключение, полученные цифры позволяют оценить эффективность эвристических методов построения аппроксимаций спектров. Так для спектра числа трансверсалей эвристически удалось получить 88% входящих в него значений, а для спектров числа диагональных трансверсалей и интеркалятов — по 97%, что подтверждает достаточно высокую эффективность применяемых эвристик.

hoarfrost, Yura12 и 3 отреагировали на эту запись.

#1576 · 14.10.2022, 03:29

Цитата: SerVal от 13.10.2022, 16:08

А RakeSearch иногда выдаёт задания, которые считаются сутками (непонятно почему, и за такими заданиями надо следить) .

Так а что мешает раз в неделю заходить на сервер, отследить такие задания и сообщить о них автору проекта, чтобы разобрался бы с ними?

У меня вот при круглосуточном счёте на компьютере с 32 Гб ОЗУ через месяц примерно становится невозможен запуск ни одной программы (эта проблема была и раньше в Gerasim).

#1577 · 16.10.2022, 21:20

Спектры быстровычислимых числовых характеристик в ДЛК порядка 9 теперь доступны онлайн:

* трансверсали — http://evatutin.narod.ru/spectra/spectrum_dls_transversals_n9_406_items.txt
* диагональные трансверсали — http://evatutin.narod.ru/spectra/spectrum_dls_diagonal_transversals_n9_182_items.txt
* интеркаляты — http://evatutin.narod.ru/spectra/spectrum_dls_intercalates_n9_64_items.txt

Шмяка отреагировал на эту запись.

#1578 · 16.10.2022, 21:22

Цитата: Yura12 от 14.10.2022, 03:29

У меня вот при круглосуточном счёте на компьютере с 32 Гб ОЗУ через месяц примерно становится невозможен запуск ни одной программы (эта проблема была и раньше в Gerasim).

Эта ошибка нестабильная и скорее всего формируется wrapper'ом, а не моим расчетником (автор кода wrapper'а не я, а разработчики BOINC'а). Подозреваю, что где-то есть утечка ресурсов. Посмотреть подробнее пока руки не дошли...

#1579 · 18.10.2022, 18:25

Цитата: evatutin от 18.10.2022, 18:25
Опубликован сборник трудов конференции Интеллектуальные информационные системы: тенденции, проблемы, перспективы (ИИС — 2022), которая проходила на нашей кафедре в сентябре в онлайн-формате. В нем есть 2 работы с моим участием, имеющие отношение к латинским квадратам и расчетам, выполняемым в настоящее время в проекте добровольных распределенных вычислений RakeSearch.

Мальков В.В., Ватутин Э.И. Построение псевдотроек ДЛК порядка 10 с использованием метода случайного перебора // Интеллектуальные информационные системы: тенденции, проблемы, перспективы (ИИС — 2022). Курск: изд-во ЮЗГУ, 2022. С. 113—116. http://evatutin.narod.ru/evatutin_dls_pseudotriples.pdf

Ватутин Э.И., Титов В.С., Пыхтин А.И., Крипачев А.В., Никитина Н.Н., Манзюк М.О., Альбертьян А.М., Курочкин И.И. Эвристический метод построения аппроксимаций спектров числовых характеристик диагональных латинских квадратов // Интеллектуальные информационные системы: тенденции, проблемы, перспективы (ИИС — 2022). Курск: изд-во ЮЗГУ, 2022. С. 35—41. http://evatutin.narod.ru/evatutin_dls_heur_spectra_method.pdf

В первой работе приведена классификация псевдотроек из ЛК/ДЛК порядка 10 на 3 типа и проведен соответствующий данной проблематике обзор литературы. С использованием метода случайного перебора получена псевдотройка типа 3 из трех попарно частично ортогональных ДЛК с характеристикой ортогональности (ХО) 229 из 300. Далее выполнявший работу студент вырос (защитил бакалаврскую) и улетел, а работу можно было бы продолжить как более интеллектуальными методами, так и с большей степенью параллелизма расчетного кода с целью получения большего значения ХО...

Во второй работе приведено описание эвристического метода, базирующегося на построении окрестностей ДЛК и позволившего (в совокупности с диагонализацией) получить рекордные мощности ряда спектров для ДЛК порядков N>9. Эксперимент, который в настоящее время готовится к запуску в RakeSearch совместно с hoarfrost'ом, как раз базируется на применении этого метода в совокупности с использованием различных опорных спектров.

Опубликован сборник трудов конференции Интеллектуальные информационные системы: тенденции, проблемы, перспективы (ИИС — 2022), которая проходила на нашей кафедре в сентябре в онлайн-формате. В нем есть 2 работы с моим участием, имеющие отношение к латинским квадратам и расчетам, выполняемым в настоящее время в проекте добровольных распределенных вычислений RakeSearch.

Мальков В.В., Ватутин Э.И. Построение псевдотроек ДЛК порядка 10 с использованием метода случайного перебора // Интеллектуальные информационные системы: тенденции, проблемы, перспективы (ИИС — 2022). Курск: изд-во ЮЗГУ, 2022. С. 113—116. http://evatutin.narod.ru/evatutin_dls_pseudotriples.pdf

Ватутин Э.И., Титов В.С., Пыхтин А.И., Крипачев А.В., Никитина Н.Н., Манзюк М.О., Альбертьян А.М., Курочкин И.И. Эвристический метод построения аппроксимаций спектров числовых характеристик диагональных латинских квадратов // Интеллектуальные информационные системы: тенденции, проблемы, перспективы (ИИС — 2022). Курск: изд-во ЮЗГУ, 2022. С. 35—41. http://evatutin.narod.ru/evatutin_dls_heur_spectra_method.pdf

В первой работе приведена классификация псевдотроек из ЛК/ДЛК порядка 10 на 3 типа и проведен соответствующий данной проблематике обзор литературы. С использованием метода случайного перебора получена псевдотройка типа 3 из трех попарно частично ортогональных ДЛК с характеристикой ортогональности (ХО) 229 из 300. Далее выполнявший работу студент вырос (защитил бакалаврскую) и улетел, а работу можно было бы продолжить как более интеллектуальными методами, так и с большей степенью параллелизма расчетного кода с целью получения большего значения ХО...

Во второй работе приведено описание эвристического метода, базирующегося на построении окрестностей ДЛК и позволившего (в совокупности с диагонализацией) получить рекордные мощности ряда спектров для ДЛК порядков N>9. Эксперимент, который в настоящее время готовится к запуску в RakeSearch совместно с hoarfrost'ом, как раз базируется на применении этого метода в совокупности с использованием различных опорных спектров.

hoarfrost, AenBleidd и Шмяка отреагировали на эту запись.

#1580 · 19.10.2022, 16:33

Возьмем текущий спектр числа трансверсалей в ДЛК порядка 13, содержащий 64978 значений, и произведем для него поквадратное расширение путем анализа окрестностей образующих его квадратов, получаемых путем вращения 1 цикла. На одной машине в 1 поток данный эксперимент будет выполняться по моим оценкам 20-30 суток, поэтому запустим его в проекте RakeSearch (подпроект по спектрам). Для этого на начальной стадии было сгенерировано чуть более чем 60 тыс. WU'шек эксперимента e1066 со временем счета порядка 1 минуты, по мере постобработки небольшими партиями будут добавляться новые WU'шки. Считаем...

hoarfrost и Шмяка отреагировали на эту запись.