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

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

2012-10-26
Программная реализация нейросетевых алгоритмов синтеза оптимальной логической структуры распределенной базы данных

Назначение: Программа предназначена для решения NP-трудной нелинейной целочисленной задачи дискретной оптимизации из области распределенных баз данных. В программе реализованы три нейросетевых алгоритма синтеза оптимальной логической структуры (ОЛС) распределенной базы данных (РБД) по критерию минимума общего времени последовательной обработки множества запросов пользователей.
Область применения: Проектирование и оптимизация логических структур распределенных баз данных.
Используемый алгоритм: В программе реализованы нейросетевые алгоритмы оптимизации, разработанные автором программы:

  • НС-ГА-алгоритм (HNN) – эволюционный алгоритм оптимизации, основанный на искусственных нейронных сетях Хопфилда и генетических алгоритмах;
  • ТМ-алгоритм (ТМ) – нейросетевой алгоритм оптимизации, основанный на модифицированном табу-поиске;
  • РТМ-алгоритм (DTM) – распределенный нейросетевой алгоритм оптимизации, основанный на модифицированном табу-поиске.

Входными данными алгоритмов являются формализованные описания характеристик предметной области задачи, включающие множества пользователей РБД, узлов вычислительной сети (ВС), групп данных канонической структуры РБД и детерминированных запросов, а также ограничения и целевую функцию задачи синтеза ОЛС РБД. Результатом работы алгоритмов является логическая структура РБД в виде множества типов логических записей и их безызбыточного размещения по серверам узлов ВС, обеспечивающие оптимальное значение заданного критерия эффективности функционирования РБД.
Все алгоритмы обладают возможностью останова на субоптимальных допустимых решениях при дефиците вычислительных ресурсов или времени.
Описание реализованных в программе алгоритмов можно найти в следующих статьях:

  • Карпунина М.Е. Использование генетических алгоритмов для повышения эффективности работы искусственных нейронных сетей // Известия Академии инженерных наук им. А.М. Прохорова. Бизнес-информатика. / Под ред. Ю.В.Гуляева. – Москва – Н.Новгород: ТАЛАМ, 2005. – 11 с.
  • Карпунина М.Е. Табу-машина как средство решения задач дискретной оптимизации: улучшение качества решения и уменьшение времени его нахождения по сравнению с альтернативным методом использования нейросетей Хопфилда. Материалы 1-ой Международной конференции по бизнес-информатике, Россия, Московская область, Звенигород, 2007. – 18 с.
  • Babkin E., Karpunina M. Comparative study of the Tabu machine and Hopfield networks for discrete optimization problems // Information technologies’ 2008 – Proceedings of 14th Conference on Information and Software Technologies, IT 2008. – April, 2008. – Kaunas University of Technology, Kaunas, Lithuania. – P.25–41.
  • Бабкин Э.А., Карпунина М.Е. Сравнительный анализ использования табу-машины и нейронных сетей Хопфилда для решения задач дискретной оптимизации из области распределенных баз данных // Научно-технический вестник СПбГУ ИТМО. Технологии высокопроизводительных вычислений и компьютерного моделирования. – Санкт-Петербург: Университетские телекоммуникации, 2008. – № 54. – С.120–127.
  • Babkin E., Karpunina M. The analysis of tabu machine parameters applied to discrete optimization problems // Proceedings of 2009 ACS/IEEE International Conference on Computer Systems and Applications, AICCSA’2009.  – Rabat, Morocco. – P.153–160. (http://www.congreso.us.es/aiccsa2009);
  • Babkin E., Karpunina M. and Aseeva N. Parallel Tabu Search Algorithm for Data Structure Composition // Lecture Notes in Business Information Processing. / J.Grabis and M.Kirikova (Eds.): BIR 2011, LNBIP. – Vol. 90, Perspectives in Business Informatics Research, Part 3. – P.110–123. 
  • Babkin E., Karpunina M. A new method of DDB logical structure synthesis using distributed tabu search // Proceedings of International Workshop on Soft Computing Applications and Knowledge Discovery,  – June, 2011. – National Research University Higher School of Economics, Moscow, Russia. – P.1–11.

 Тексты статей доступны по ссылке http://www.scopus.com/authid/detail.url?authorId=55274973600.

Функциональные возможности: Программная реализация алгоритмов не содержит ограничений на максимальное количество пользователей РБД, количество узлов ВС и другие числовые харатеристики задачи. Поэтому они могут быть ограничены лишь размером свободной динамической памяти ЭВМ, объемом ОЗУ. РТМ-алгоритм является наиболее производительным, так как способен работать в параллельном режиме на вычислительном кластере.
Инструментальные средства создания: Язык С++, среда разработки Microsoft Visual Studio 2008, библиотека Microsoft HPC Pack 2008 SDK.
2012-10-15
Вычисление сверхбольших чисел вида M=a^p, в том числе чисел Мерсенна и чисел Евклида

 

Назначение: Программа предназначена для вычисления сверхбольших чисел вида Mp =  ap, представляемых в памяти ЭВМ линейными динамическими массивами. При этом показатель степени p может принимать значение порядка 40-100 млн и более.

Область применения: В теории чисел известны числа Мерсенна  вида Mp =  2p-1 и числа Евклида  вида Mn  = 2n-1 *(2n-1). Программа может использоваться при определении сверхбольших чисел Мерсенна, чисел Евклида, простых чисел, при определении закономерности распределения простых чисел. Также программа может использоваться в теоретической физике, при тестировании мощности вычислительных систем.

Используемый алгоритм: В программе реализован алгоритм, разработанный автором. Пользователь вводит  показатель степени двойки для вычисления числа Мерсенна. Алгоритм предусматривает максимальное использование ранее вычисленных значений степени двойки, которые можно использовать в соответствии с правилом сложения степеней. Способ умножения этих значений в виде линейных динамических массивов описан в  программе "Ускоренное умножение сверхбольших чисел" (зарегистрировано в Каталоге ФАП, номер PR12011). Пользователю предоставляется возможность внести имя файла бинарного типа, в котором хранится ранее вычисленное значение числа  с меньшей степенью двойки. Значение считывается в линейный динамический массив в виде последовательности десятичных цифр, начиная с разряда единиц. Значение степени двойки, которое пользователь вводил в начале выполнения программы будет больше, чем у считанного из бинарного файла числа, поэтому определяется их разность - как значение недостающей степени. Далее, уже без участия пользователя, алгоритм предусматривает вторую возможность использования ранее вычисленных значений степеней двойки, которые хранятся в бинарных файлах с соответствующими именами. Циклически можно использовать значения со степенями 1000, 10 000, 100 000 и 1 млн. В программе можно предусмотреть и другие заготовки степеней двойки, например 2^10 млн. Когда до заданной пользователем степени остается значение меньше 1000, то предварительно сформированное значение циклически умножается на 2 необходимое количество раз, например 999 раз, что для современных процессоров выполняется достаточно быстро. Высокая скорость выполнения расчетов в предлагаемой программе обеспечивается двумя факторами: максимальное использование ранее вычисленных значений степеней двойки; многократное использование в ходе вычислений умножения по алгоритму "Ускоренное умножение сверхбольших чисел" (PR12011). Конечные результаты вычислений чисел Мерсенна и чисел Евклида формируюся в виде динамических линейных массивов, эти значения сохраняются в бинарных и текстовых файлах. Значения, сохраненные в бинарных файлах, можно в последующем использовать для вычисления еще больших степеней двойки, что похоже на восхождение на большую высоту с ранее достигнутого места по разновеликим ступенькам лестницы.

Функциональные возможности: Функциональные возможности могут быть ограничены размером свободной динамической памяти ЭВМ. В представленном во вложении листинге программы предусматривается разрядность формируемых чисел порядка 100 млн, что намного превышает разрядность самых больших  известных простых чисел Мерсенна с разрядностью до 15 млн.

Инструментальные средства создания: Microsoft  Visual Studio 2010, Visual C++.
2012-10-12
База данных событий широких атмосферных ливней

Назначение: хранение, обновление и предоставление данных по событиям широких атмосферных ливней (ШАЛ), вызываемых космическими лучами сверхвысоких энергий (КЛСВЭ), зарегистрированных Якутской комплексной установкой ШАЛ (ЯКУ ШАЛ).

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

Функциональные возможности:

База Данных обеспечивает:

  • хранение и обновление данных по заряженной, мюонной и черенковской компонентам ШАЛ;
  • формирование выборки событий ШАЛ согласно желаемым критериям отбора для дальнейшего анализа;
  • многокомпонентный анализ характеристик ШАЛ;
  • анализ астрофизических параметров КЛСВЭ с энергиями выше 1018 эВ;
  • мониторинг качества работы детекторов установки в течение анализируемых периодов.

БД содержит события ШАЛ, начиная с 1995 г., в настоящий момент в ней 1511955 событий. БД содержит 10 таблиц. 

Подробное описание структуры БД - в приложенном файле.

Инструментальные средства создания - СУБД Postgresql-8.4.11
2012-10-09
Программа ЭВМ, реализующая модель процесса передачи голосовых и видеопотоков в условиях помех

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

Область применения: Современные сети связи. Многошаговые сети IEEE 802.11s (Wi-Fi Mesh)

Используемый алгоритм : Рассматривается  беспроводная многошаговая сеть стандарта IEEE 802.11s (Wi-Fi Mesh). Между двумя станциями этой сети передается поток мультимедийных данных переменной интенсивности – неординарный поток пакетов одинакового размера, группы которых приходят регулярно с периодом T . Количество пакетов в группах – независимые одинаково распределенные случайные величины.
Для передачи пакетов станция-источник устанавливает периодическую последовательность резервирований, то есть временных интервалов одинаковой длительности, позволяющей совершить ровно одну попытку передачи  пакета. При этом на интервал T приходится ровно m резервирований. Вероятность успешной передачи пакета в каждом резервировании одинакова. При неудачной попытке передачи обслуживание пакета продолжается. Требование к качеству обслуживания (QoS) мультимедийного потока определяется ограничением D на максимальное время доставки пакета. При превышении этого времени обслуживание пакета прекращается, даже если он еще не был успешно передан. 
 
Данная программа позволяет найти долю PLR потерянных пакетов, являющуюся  важным показателем качества обслуживания мультимедийного трафика. Для нахождения доли PLR используется алгоритм, схожий с описанным в работе Shvets Evgeny, Lyakhov Andrey, Safonov Alexander, Khorov Evgeny. Analyt­ical model of IEEE 802.11s MCCAbased streaming in the presence of noise // SIGMETRICS Perform. Eval. Rev. 2011. Vol. 39, no. 2. Pp. 38–40, и отличающийся от него тем, что входной поток - неординарный.

Входные параметры:

• распределение числа пакетов в каждой группе пакетов мультимедийного потока;
• вероятность удачной попытки передачи пакета;
• длительность T интервала между группами пакетов в мультимедийном потоке;
• максимальное допустимое время доставки пакетов D;
• число резервирований m, приходящихся на интервал T .
 
Выходные параметры:

• Доля потерянных пакетов PLR.

Функциональные возможности: Время работы программы зависит от входных параметров. Для того, чтобы программа расчитывала результат в реальном режиме, необходимо выполнение условий:

Период резервирований от 100 мкс до 1 с

Длительность резервирований от 100 мкс до 1 с

Размер пакетов от 100 до 1500 байт.

Канальная скорость от 6 до 54 Мбит/с

Максимальное допустимое время доставки пакетов D больше периода резервирований T.

Размер группы пакетов - не более 50.

Вместо генерации случайного потока, описанного распределением, программа может использовать поток, записанный в файл "in.txt".

Инструментальные средства создания: Среда имитационного моделирования GPSS World
2012-10-09
Программа ЭВМ, реализующая расчет моделей передачи мультимедийных потоков с помощью механизма детерминированного доступа в сетях IEEE 802.11s

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

Область применения: Современные сети связи. Многошаговые сети IEEE 802.11s (Wi-Fi Mesh)

Используемый алгоритм: Рассматривается многошаговая беспроводная сеть, работающая под управлением технологии IEEE 802.11s с использованием детерминированного метода доступа к среде MCCA (Mesh Coordinated Channel Access). Между двумя станциями этой сети передается поток мультимедийных данных переменной интенсивности – поток пакетов одинакового размера, приходящих регулярно с периодом T . Моделируется передача такого потока по многошаговому маршруту от станции-источника до станции-получателя. Для передачи пакетов потока каждая станция-ретранслятор  маршрута, используя механизм MCCA, устанавливает поток резервирований - периодическую последовательность резервирований, то есть временных интервалов одинаковой длительности, позволяющей совершить ровно одну попытку передачи пакета. Вероятность успешной передачи пакета в каждом резервировании одинакова. При неудачной попытке передачи обслуживание пакета продолжается.

Требование к качеству обслуживания (QoS) мультимедийного потока определяется ограничениями на максимальное время передачи пакета на каждой станции. При превышении этого времени обслуживание пакета прекращается, даже если он еще не был успешно передан. 

 Данная программа позволяет найти долю PLR потерянных пакетов на всем маршруте. Этот показатель, также как и время доставки,  является важным показателем качества обслуживания мультимедийного трафика.

Входные параметры программы:

• вероятность  удачной попытки передачи пакета на каждом шаге маршрута;
• период T поступления пакетов (входной поток станции-источника);
• максимальная допустимая  задержка пакетов на каждом шаге маршрута;
• период резервирований на каждом шаге маршрута.
 
Выходные параметры:
 
•  Доля потерянных пакетов PLR при удовлетворении требований на задержку на каждом шаге маршрута.
 
Алгоритм расчета описан в работе Shvets Evgeny, Lyakhov Andrey, Safonov Alexander, Khorov Evgeny. Analyt­ical model of IEEE 802.11s MCCAbased streaming in the presence of noise //SIGMETRICS Perform. Eval. Rev. 2011. Vol. 39, no. 2. Pp. 38–40. http://dl.acm.org/citation.cfm?id=2034841

Функциональные возможности: Время работы программы зависит от входных параметров. Для того, чтобы программа расчитывала результат в реальном режиме, необходимо выполнение условий:

Число шагов маршрута не больше 7

Максимальная допустимая задержка пакетов на каждом шаге маршрута больше периода поступления пакетов;

Вероятность успешной попытки пеередачи на каждом шаге больше 0.1

Инструментальные средства создания:  Среда разработки Eclipse