Параллельные вычисления расчета факториала числа N

03.01.22

Разработка - Математика и алгоритмы

Распараллеливание алгоритма с помощью фоновых заданий (асинхронные вычисления)

Цель:

1. ускорить расчет факториала числа

2. научиться распараллеливать вычисления с помощью фоновых заданий

 

Предисловие

Всем привет!

Решил протестировать расчет факториала деревом через параллельные вычисления. Про задачу читайте здесь Факториал числа N = N!

Забегу вперед и скажу, что тесты проводились на клиент-серверной базе, конфигурация Бухгалтерия предприятия, редакция 2.0 на обычных формах, платформа 1С:Предприятие 8.3 (8.3.15.1830), СУБД PostgreSQL. Сведения о процессоре и памяти - в картинках (к сожалению, не знаю как скопировать текст сведений, поэтому вырезал скрин)

Результат меня обрадовал: классический алгоритм рассчитал факториал для 50 000 за 17 сек, алгоритм деревом - за 9 сек. Параллельное вычисление в 4 потока за 0 сек. Напишу за 1 сек, поскольку по настоящему я не смог сделать замеры - отловить время завершения фоновых заданий. Я ориентировался на время начала и время завершения фоновых заданий (картинка консоли заданий приложена).

После 50 000, я быстро посчитал в 4 потока 150 000! за 4-5 сек.

Алгоритм. Решение. Распараллеливание.

Фоновые задания как раз предназначаются для организации параллельных вычислений.

Задачу расчета факториала очень удобно распараллелить на несколько потоков вычислений. Причем это касается любого алгоритма для расчета факториала: классического, рекурсией или деревом. Главное разделить всю последовательность чисел на "отрезки", для каждого из которых запускать свой расчет отдельно.

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

Я решил разделить последовательность (2...ЧислоN) на 4 группы (см. Листинг 1) и расчет по каждой группе запускать в отдельном фоновом задании (см. Листинг 2).

 
 Листинг 1. Разделим входные данные на 4 группы
 
 Листинг 2. Запуск дочернего фонового задания для потока 1

В файловой базе можно тестировать только одно фоновое задание. Или несколько, но они будут будут вставать в очередь и выполняться последовательно. А значит для распараллеливания файловая база не подходит. 

Поэтому я развернул алгоритм на клиент-серверной базе. При этом я буду запускать сначала родительское фоновое задание (см. Листинг 3), оно в свою очередь будет запускать 4 дочерних фоновых задания (см. Листинг 4).  Листинг 4 содержит все процедуры общего модуля ФоновыеПроцедуры - этого достаточно, чтобы не скачивать прилагаемый ЦФшник.

 
 Листинг 3. Запуск родительского фонового задания
 
 Листинг 4. Запуск 4-х дочерних фоновых заданий из процедуры-обработки родительского фонового задания

Обратите внимание на то, что я задействовал Константы для хранения промежуточных результатов. Тип Число для констант ограничен 32 разрядами, поэтому проверку на корректность расчета я проводил для небольших чисел: от 10 до 20, например. 

Затем запускал расчет факториала для 50 000 и 150 000. Естественно, результат я видел такой "999 999 999 999 999 ....", но в этом случае интересно было только время работы алгоритма. Платформа 1С, насколько я осведомлен, умножает и хранит в памяти большие числа корректно, а вот с отображением больших чисел имеет проблемы. 

Эпилог

Прилагаемую конфигурацию надо запускать в клиент-серверном режиме. Она содержит только общий модуль, обработку с формой для задания числа N и запуска расчета - для тестирования этого достаточно. 

В файловом режиме параллельности расчетов не будет. Для завершения фоновых заданий в файловом режиме используйте таймаут (рекомендация синтакс-помощника). Решение задачи на файловой базе не проводил, поскольку цель была именно разделить потоки вычислений.

 
 Листинг 5. Таймаут для завершения фонового задания

Если будете тестировать распараллеливание вычислений на базах с обычными формами, то можете использовать типовую КонсольЗаданий.epf для просмотра запущенных, завершенных заданий. Эта консоль заданий находится здесь ИТС. Консоль заданий для обычных форм

Если будете тестировать распараллеливание вычислений на базах с управляемыми формами, то используйте БСП (Библиотеку стандартных подсистем), которая содержит подсистему РегламентныеЗадания и свою консоль заданий Описание подсистем БСП. Регламентыне Задания

На платформе 8.3.15.1830 в синтакс-помощнике вы не найдете описание процедуры ФоновыеЗадания.ОжидатьЗавершения() - но в документации 1С найдете Метод ОжидатьЗавершения() считается устаревшим и не рекомендуется к использованию.

Но я его использовал, поскольку мне показалось это удобным.

 

Выводы:

1) ускорил расчет факториала числа

2) научился распараллеливать вычисления с помощью фоновых заданий

Собственно, это все.

 
 См. также другие полезные обработки

Лирика, мотивация, кейсы внедрения:

1) Две печатные формы на одном листе

2) JSON -> Дерево значений

3) Анализ прав и ролей: поиск подходящего профиля

4 ) Оцифровка и визуализация склада

Расширения:

1) [Расширение] УНФ. Список заказов + Структура подчиненности

2) [Расширение] БП 3.0. Список счетов/ Список реализаций + Связанные документы

3) [Расширение] УТ 11.4. Счет на оплату с факсимиле и баннерами

Внешние обработки (не расширения!):

1) Список заказов поставщикам + структура подчиненности

2) Список заказов покупателей + структура подчиненности

3) Список реализаций со структурой подчиненности + реестр документов

4) Список заказов покупателей (Расширенная версия)

Другие публикации:

1) Удаление справочников для любых баз на управляемых формах

2) Удаление документов для любых баз на управляемых формах

3) Удаление чеков ККМ в Рознице 2.2

4) Загрузка товаров, штрихкодов, цен и остатков на УФ - Розница 2.2

5) Отчет Остатки и цены (прайс с остатками)

6) Как свернуть базу УТ 10.3: принципы свертки, технология, вспомогательные обработки

7) [ЦФшник] Доработка конфигурации Конвертация Данных

8) [Внешняя обработка] Ввод показателей план-факта БП 3.0

9) [Шаблоны] Договоры для 1с-ника ТОП-скачиваний

10) Удаление документов для любых баз на обычных формах

11) Выделение документов в списках (обычные формы) для групповой обработки

12) Список номенклатуры с выводом уникального идентификатора для УТ 10.3

13) Замена задвоенных договоров в БП 3.0

Всем добра! :)

Параллельные вычисления распараллеливание алгоритмов программ асинхронные фоновые задания

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1715    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4320    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7350    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7820    7    kalyaka    11    

44

JSON -> Дерево значений

Инструментарий разработчика Платформа 1С v8.3 Конфигурации 1cv8 1С:Управление торговлей 10 Абонемент ($m)

Очередной просмотрщик json-структуры

2 стартмани

21.12.2021    9456    58    RustIG    25    

34

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4415    fishca    13    

36

Просмотр прав. Анализ прав и ролей. Поиск подходящего профиля. УТ 10.3, УПП 1.3, УТ 11.Х, КА 2.Х, БП 3.0, ЗУП 3.1, УНФ 1.6, Розница 2.Х

Роли и права Платформа 1С v8.3 Управляемые формы Управление правами Конфигурации 1cv8 Абонемент ($m)

Просмотр прав. Анализ прав и ролей. Обработка подскажет, в какой профиль включить пользователя, на основании анализа прав и ролей на документы и справочники.

3 стартмани

09.12.2021    15314    183    RustIG    35    

47
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. echo77 1868 29.06.20 07:08 Сейчас в теме
А что если использовать одну процедуру ФакториалДПоток при запуске фонового задания?
2. RustIG 1301 29.06.20 10:13 Сейчас в теме
(1) согласно синтакс-помощнику процедуры - обработчики фоновых заданий должны отличаться для фоновых заданий с одинаковым ключом. А ключ одинаковый мне нужен, чтобы фильтр наложить на ожидание одновременно завершающихся заданий.
В общем, я пробовал по разному - и текущий вариант оказался работоспособен.

Цитата из санткас-помощника:
<Ключ> (необязательный)
Тип: Строка.
Ключ задания. Если ключ задан, то он должен быть уникальным среди ключей активных фоновых заданий, имеющих такое же имя метода, что и у данного фонового задания.
3. echo77 1868 29.06.20 10:17 Сейчас в теме
(2) А что если сделать одну процедуру и разные ключи и ожидать завершения фоновых заданий с разными ключами?
4. RustIG 1301 29.06.20 10:21 Сейчас в теме
(3) в теории наверное так тоже можно - программировать придется больше проверок - проверять каждый запущенный фоновый процесс по ключу

просто одно дело теория, другое дело практика - я пока тестировал ряд фраз синтакс-помощника по разному "прочитывал" и натыкался на бездействие программы.

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

Надеюсь на силу сообщества - каждый внесет свою лепту в раздел "параллельных вычислений".
15. dusha0020 1103 30.06.20 15:18 Сейчас в теме
Я кода-то делал подобные вещи, пытаясь ускорить расчеты в серверном режиме. Отсюда у меня ряд вопросов и замечаний:
1. Мне кажется намного удобнее делать количество потоков расчета параметром для вызываемой процедуры. Ядер и потоков на каждом сервере по разному, да и соображения управления нагрузкой не надо забывать.
2. Я бы, как указал echo77 в (1), не стал в таком случае флудить 4 или сколько еще функций расчета факториала, ибо количество потоков динамическое и сколько нужно функций не понятно. Достаточно и одной.
3. Ожидать завершения фоновых заданий можно не собирая их отбором по ключу, а сразу при запуске добавлять в массив. В этом случае нам не нужно будет их потом искать и плодить лишние функции для запуска разных заданий с одним ключом.
4. Как Вы правильно заметили, константы не могут содержать результат больше 32 разрядов. Ну и количество констант не может быть динамическим, определяемым переменной числа нужных потоков. В общем как по мне константы здесь не годятся вообще. Я использовал старый добрый метод ЗначениеВФайл(), передавая имя файла для записи результата как параметр вызываемой функции фонового задания. В этом случае по завершении всех заданий я обходил файлы по списку, получал результаты и обрабатывал.

Прошу не воспринимать мои замечания, как стремление обидеть или уязвить. Пришлось когда-то заниматься этим вопросом, а раз Вы хотите разобраться, то пара-тройка советов, думаю, будет не лишней:)
dammit666; RustIG; +2 Ответить
16. RustIG 1301 30.06.20 15:54 Сейчас в теме
(15) спасибо, вот про это не додумался:
3. Ожидать завершения фоновых заданий можно не собирая их отбором по ключу, а сразу при запуске добавлять в массив. В этом случае нам не нужно будет их потом искать и плодить лишние функции для запуска разных заданий с одним ключом.


а в остальном, все верно - и про константы и их замену на файл на жестком диске, и про параметр и одну функцию-обработчик - я уже позже домыслил реализацию, но не стал экспериментировать.
5. papami 55 29.06.20 17:47 Сейчас в теме
В БСП удобно все реализовано.
В Бух КОРП 3 дроблю проведение реализаций в разрезе подразделений (количество измеряется десятками) на 4 потока.
При этом 1 поток проводит 2,5 -3 часа, 4 потока - чуть больше часа. (~10000 документов в день)
Причем прибавлять ядра/потоки больше смысла нет, т.к. там уже в другом месте упирается.
6. RustIG 1301 29.06.20 17:53 Сейчас в теме
(5)
Причем прибавлять ядра


насколько я помню, дело не в кол-ве ядер...
и с одним ядром можно несколько рабочих процессов (потоков) запускать... за этим следит кластер серверов и платформа 1с. каждый фоновый процесс запускается в отдельном рабочем процессе.
9. papami 55 29.06.20 18:30 Сейчас в теме
(6)
с одним ядром можно несколько рабочих процессов (потоков) запускать...

Можно запускать, но вопрос в эффективности (я про производительность)
7. RustIG 1301 29.06.20 17:58 Сейчас в теме
(5) с проведением документов надо программировать непересекающиеся множества документов (записей в таблицах), чтобы не создавались блокировки записей в таблицах (документов)...
все-таки принцип проведения документов - особенно расчет себестоимости - основывается на последовательном проведении документов (или фиксации факта хоз.деятельности) - поэтому параллелить именно процесс проведения документов имеет ряд ограничений и нюансов...
8. papami 55 29.06.20 18:27 Сейчас в теме
10. RustIG 1301 29.06.20 19:27 Сейчас в теме
(5) все-таки научиться проводить документы в фоне (через фоновые задания) нельзя назвать задачей распараллеливания вычислений...
При проведении вы не ожидаете завершения фоновой задачи, чтобы произвести очередной расчет, и не используете полученные промежуточные результаты.
Для распараллеливания вычислений как раз и надо собрать все промежуточные результаты всех дочерних фоновых заданий и обработать их в родительском фоновом задании.

Для распараллеливания вам придется залезть в общий модуль конфигурации, дописать логику распараллеливания и сборки промежуточных результатов. А для типовой БП КОРП 3, я думаю это критично для последующих обновлений...

А вот запустить из внешней обработки длительную операцию перепроведения документов с отбором по подразделению - можно легко в БУХ КОРП 3...

Вы как реализовали свой метод?

Кто знает, заложена ли в БСП реализация разделения родительского фонового задания на дочерние и сборка промежуточных результатов?
11. papami 55 29.06.20 19:39 Сейчас в теме
(10)
Что-то Вы тут все как-то в кучу)
Дискуссия отнимет массу времени. Я пас.
13. RustIG 1301 29.06.20 19:46 Сейчас в теме
(11) все ок. можете не отвечать :)
я полагаю, что в БСП заложена модель , о которой я спрашиваю. Например из общего неглобального модуля происходит вызов процедуры из модуля внешней обработки - в модуле обработки можно прописать любую логику и функциональность. Задача решена! :)
12. tazhitkov 29.06.20 19:41 Сейчас в теме
А зачем такой факториал считать?
14. RustIG 1301 29.06.20 19:51 Сейчас в теме
(12) хочется написать мат.пакет алгоритмов для решения СЛАУ.
Начал с простого - с факториала. Изыскания привели к написанию двух публикаций.
Шаг за шагом изучаю возможности платформы.
17. TODD22 18 01.07.20 14:11 Сейчас в теме
(14)
хочется написать мат.пакет алгоритмов для решения СЛАУ.

Если ничего не путаю, 1С вроде в платформе что то реализовывала для решения СЛАУ.
18. user1534961 13.03.21 20:06 Сейчас в теме
Спасибо. Замечательный пример организации фоновых заданий и обработки данных в многопоточном режиме. Можно использовать и для обменов, и для перепроведений...
Оставьте свое сообщение