Разработки СО РАН - каталоги программ и БД

Поиск по каталогам:

2019-12-30

Назначение - программа предназначена для проверки сверхбольших чисел Мерсенна на принадлежность их к простым числам.
Область применения - теория чисел, тестирование производительности вычислительных систем.

Используемый алгоритм - Используется алгоритм теста Люка-Лемера, в котором сверхбольшие числа представлены в виде динамических линейных массивов в двоичной системе счисления. Арифметические операции над числами выполняются по алгоритмам длинной арифметики. Поиск очередного самого большого простого числа Мерсенна вида 2^PM - 1 , где РM, в свою очередь, простое число, принимающее значения более 57 млн, является весьма трудоемкой задачей. В соответствии с тестом Люка-Лемера выполняется (PM -2) итераций цикла, на каждой из которых определяется целочисленный остаток от деления на число Мерсенна. Эта операция и определяет в основном трудоемкость теста. Только при представлении чисел в двоичной системе счисления представляется возможность упростить эту операцию до одной элементарной операции сложения.

В программе реализован разработанный авторами алгоритм вычисления целочисленного остатка при делении на сверхбольшое чисто Мерсенна в двоичной системе счисления. Целочисленный остаток в двоичной системе счисления определяется как сумма двух частей в записи делимого. Первая часть записи от разряда единиц (нулевой разряд) до разряда с номером (PM - 1), где PM - показатель степени числа Мерсенна. Вторая часть записи от разряда с номером PM и до старшего разряда в записи делимого. Использование данного алгоритма позволяет существенно снизить трудоемкость теста Люка-Лемера и время работы программы. Дополнительно к ранее зарегистрированному алгоритму "Тест Люка-Лемера для сверхбольших чисел Мерсенна" в два раза сокращено количество итераций вложенных циклов при вычислении квадрата целочисленного остаттка с предыдущей итерации теста. При возведении числа в квадрат в двоичной системе счисления сочетание цифр множимого и множителя с одинаковыми номерами разрядов встречаются однократно и в итог сносится 1, а с разными - дважды и в итог сносится 2. Учет этого обстоятельства во фрагменте программы позволил в два раза снизтить общую трудоемкость теста. 
Функциональные возможности - Функциональные возможности могут быть ограничены размером свободной динамической памяти ЭВМ. Размер используемых в программе двух динамических линейных массивов равен значению степени PM числа Мерсенна, которое в современных вычислениях принимает значение более 57 млн. В программе предусматривается проверка достаточности оперативной памяти для текущих вычислений.
Инструментальные средства создания - Microsoft  Visual Studio 2010, Visual C++.

2019-12-30

Назначение – программа предназначена для точного расчета надежности сети с использованием на суперЭВМ с распределённой памятью.

Область применения - анализ надёжности и живучести сетей различного назначения

Необходимость в расчёте и оценке показателей надёжности возникает, прежде всего, при структурной оптимизации сетей, как на этапе проектирования, так и при расширении существующих структур. При этом задача точного расчёта надёжности сети с NP-трудна, поэтому без использования суперЭВМ точно вычислить надёжность можно, как правило, только для сетей с количеством элементов около сотни.

Данная программа позволяет осуществлять параллельный точный расчёт надёжности сетей с ненадёжными каналами связи, под надёжностью понимается вероятность связности всех узлов сети. Распараллеливание расчёта основано на известном методе факторизации (ветвления, Мура-Шеннона), соответствующий алгоритм опубликован в [1]. По сравнению с первой версией программы оптимизированы параметры, повышающие масштабируемость программы. Рост производительности является линейным вплоть до 1000 вычислительных ядер. Однако, для структур разной плотности возможны разные оптимальные значения параметров [1].

Входные данные программы – структура сети в виде графа, значения надёжности каналов связи (т.е. вероятности их присутствия).

Выходные данные программы – значение надёжности сети, время расчёта.

Программа работает с представлением графов при помощи полного файла предшественников (списки KAO,FO). Информация в файле должна располагаться следующим образом: первая строка – количество вершин, вторая строка – количество рёбер, третья и четвёртая строка – списки представления графа (элементы списка разделяются запятыми).

[1] Denis A. Migov. Parallel Methods for Network Reliability Calculation and Cumulative Updating of Network Reliability Bounds // Proceedings of the IEEE 3rd Russian-Pacific Conference on Computer Technology and Applications. 2018. P. 1-5.  (DOI: 10.1109/RPC.2018.8482197)

Функциональные возможности – расчёт надёжности сетей с количеством элементов в несколько сотен.

Инструментальные средства создания – C++, MPI .

Алгоритм разработан в рамках гранта РФФИ № 18-07-00460

2019-12-30

Третья, расширенная версия системы имитационного моделирования ИМОДО, разработанной для решения задач, связанных с транспортной сетью (зарегистрирована в ФАП СО РАН, № PR18002).

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

Назначение Расчет эффективности расстановки устройств на транспортных средствах, с целью определения наиболее точного уровня загрезнения.
Область применения Современные и перспективные сети передачи данных, например, VANET.

Используемый алгоритм

Поиск оптимальной расстановки устройств сбора данных осуществляется с помощью генетического алгоритма с учетом основных характеристик модели:

– скорость движения транспорта;

–  маршруты движения транспортных средств, на которых размещены устройства мониторинга;

– предельное количечство автомобилей на каждом участке дороги (пробки, возникающие в "узких" местах);

– источники загрязнения.

В качестве модели транспортной сети рассматривается граф с взвешенными ребрами.

Редактирование графа можно производить непосредственно в системе.

Подложкой является карта, взятая из открытых источников. Алгоритм описан в [1].

[1] TKACHEV K.V., VOLZHANKINA K.A., SOKOLOVA O.D. On a problem of the monitoring device placement on transport networks, Novosibirsk. https://cloud.mail.ru/public/4Tsd/NymmFx5wP

[2] TKACHEV K.V., VOLZHANKINA K.A., MIGOV D.A. Comparison of the Work of Algorithms for Arranging Message Distribution Devices in Transport Networks, Novosibirsk. https://cloud.mail.ru/public/4Tsd/NymmFx5wP

[3] TKACHEV K.V. The Interaction Interface Between the Model and the Observer Agent in the Simulation System, Novosibirsk. https://cloud.mail.ru/public/4Tsd/NymmFx5wP

В прилагаемом архиве находится проект для запуска на Visual Studio.

2019-12-29

Назначение - оптимизация сетей различного назначения с целью повышения надёжности.

Область применения - проектирование сетей различного назначения.

Используемый алгоритм - генетический алгоритм. Программа позволяет для заданной структуры сети с ненадёжными вершинами определить оптимальное количество необходимых стоков (узлов, предназначенных для сбора информации с остальных) и их расстановку. Предполагается, что стоки могут быть размещены в узлах сети. Для каждого узла сети задаются значения надёжности и стоимости установки стока в этом узле. Под надёжностью сети понимается вероятность связности заданной доли (Т) узлов с каким-либо из стоков. Этот показатель подробно описан в статье [1], наряду с методом его расчёта. Алгоритм расстановки представлен в работе [2].

[1] D. Migov, V. Shakhov. Reliability of Ad Hoc Networks with Imperfect Nodes // Springer Lecture Notes in Computer Science (in MACOM 2014). Vol. 8715, 2014, p. 49-58. (http://link.springer.com/chapter/10.1007%2F978-3-319-10262-7_5)

[2] Волжанкина К.А., Мигов Д.А. Генетический алгоритм размещения стоков в беспроводной сенсорной сети с ненадёжными узлами для повышения вероятности успешного мониторинга // Материалы Межд. конференции "Актуальные проблемы вычислительной и прикладной математики", Новосибирск, 2019. Новосибирск: ИВМиМГ СО РАН, 2019, стр. 328-332.

Поиск ведётся в условиях наперёд заданных ограничений.

Входные данные программы: структура сети в виде графа, пример входных данных предоставлен в сопутствующих файлах (массивы KAO FO или полный файл предшественников), значения надёжности для всех узлов связи (числа от 0 до 1), параметры генетического алгоритма (размер популяции, кол-во поколений, размер турнира, вероятность мутации), количество устанавливаемых узлов, Т - доля узлов сети, которые должны быть связны с каким-либо из стоков, условия остановки алгоритма: количество поколений, ограничение на время работы алгоритма и стагнация (задаётся количество поколений, в которых вырождается решение).

Инструментальные средства создания - Delphi.

Алгоритм разработан в рамках гранта РФФИ № 18-07-00460.

2019-12-27

Назначение - установление оптимальных значений длин фаз на светофорных объектах в городской транспортной сети.
Область применения - оптимизация и увеличение эффективности транспортной сети мегаполисов.
Используемый алгоритм - в основе программы лежит эвристический алгоритм роя частиц, позволяющий осуществлять эффективный поиск решений с малой или нулевой относительной погрешностью. Для определения качества получаемых решений используется пакет микросимуляционного моделирования SUMO.
Функциональные возможности - расчет длин фаз и сдвигов фаз для заданного участка городской транспортной сети. Размерность решаемых задач - до 50 светофорных объектов (до 5 фаз на каждом СО). 
Инструментальные средства создания - среда разработки VisualStudio 12.0, язык программирования C#, микросимуляционный пакет SUMO