Предлагается эффективный параллельный алгоритм решения NP-полной задачи о рюкзаке в ее исходном, так называемом 0-1 варианте. Для нахождения ее точного решения издавна применяются алгоритмы, относящиеся к категории "методов ветвей и границ". Для ускорения получения результата с разной степенью эффективности применяются также различные варианты организации параллельных вычислений. Мы предлагаем здесь алгоритм решения задачи, основанный на парадигме рекурсивно-параллельных вычислений. Он представляется нам хорошо пригодным для задач такого рода, когда трудно сразу разбить вычисления на достаточное количество сравнимых по трудоемкости подзадач, поскольку она проявляется динамически во время вычислений. В качестве основного инструмента для программной реализации алгоритма использовалась разработанная автором библиотека RPM_ParLib, позволяющая создавать эффективные приложения для вычислений на локальной сети в среде .NET Framework. Такие приложения обладают способностью порождать параллельные ветви вычислений непосредственно во время выполнения программы и динамически перераспределять работу между вычислительными модулями. При этом в качестве языка программирования может использоваться любой язык с поддержкой .NET Framework. Для проведения экспериментов было написано несколько программ на языке C# с использованием упомянутой библиотеки. Основной целью этих экспериментов было исследование ускорения, достигаемого за счет рекурсивно-параллельной организации вычислений. Подробное описание алгоритма и эксперимента, а также полученные результаты приводятся в работе.          

Рассматривается задача проверки допустимости конфигураций модульных вычислительных систем реального времени (МВС РВ). Конфигурация считается допустимой, если все работы успевают выполниться на МВС РВ в рамках своих директивных интервалов. Предложена обобщенная модель функционирования МВС РВ и метод построения на её основе модели для конкретной конфигурации. Модель представляет собой сеть временных автоматов с остановкой таймеров. По вычислению сети автоматов предлагается строить временную диаграмму (ВД) функционирования МВС РВ, необходимую для проверки допустимости. В работе обосновывается корректность предложенного подхода. Из спецификаций на МВС РВ был выделен ряд требований, применимых к моделям МВС РВ и их компонентов на выбранном уровне абстракции. Модели считаются корректными, если удовлетворяют этим требованиям. Доказано, что если все модели компонентов системы удовлетворяют соответствующим требованиям, то модель МВС РВ, построенная согласно предложенному подходу, удовлетворяет требованиям к модели системы в целом (то есть корректна), а также является детерминированной. Под детерминированностью понимается однозначность построения ВД сети автоматов, соответствующей заданной конфигурации. Это позволяет использовать для проверки допустимости конфигурации любое вычисление соответствующей сети автоматов, что крайне важно для эффективности предложенного подхода, так как число возможных вычислений сети автоматов растет экспоненциально с числом работ в системе. Выполнение требований корректности к моделям компонентов системы может быть проверено автоматически с использованием верификатора и подхода автоматов-наблюдателей. Все разработанные нами модели компонентов системы удовлетворяют соответствующим требованиям, что было доказано с помощью верификатора UPPAAL. Если пользовательские модели компонентов системы удовлетворяют требованиям корректности, то они могут быть включены в модель МВС РВ, которая при этом останется корректной и детерминированной.

Программно-конфигурируемая сеть (ПКС) – это перспективная парадигма управления сетью, в которой для повышения производительности уровень управления сетью отделен от уровня передачи данных и реализуется программно на выделенном сервере. Несмотря на очевидные преимущества подхода централизованной архитектуры управления ПКС, она создает новые проблемы, связанные с надежностью, масштабируемостью, отказоустойчивостью и интероперабельностью сети. Эти проблемы встают особенно остро для больших сетей дата-центров и решаются путем объединения нескольких контроллеров ПКС в кластер, называемый мультиконтроллером. В данной статье представлен обзор некоторых наиболее популярных мульти-контроллеров ПКС, выделены их сильные и слабые стороны, а также приведена классификация используемых ими подходов к организации распределенного взаимодействия. Подробно рассматриваются различия между несколькими типами архитектур мульти-контроллеров, среди которых есть как находящиеся на этапе разработки, так и успешно функционирующие в данное время в дата-центрах. Авторы на примере разработанной ими классификации мульти-контроллеров показывают, что, несмотря на наличие неоспоримых преимуществ, все рассмотренные контроллеры имеют недостатки, которые необходимо устранить. Устранение данных недостатков поможет развитию мульти-контроллеров и сделает возможным их широкое использование в корпоративных сетях. В заключение авторы приходят к выводу, что на данный момент нельзя найти решение, способное в полной мере решить все поставленные задачи. Статья публикуется в авторской редакции.

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

В 1978 году Р.Мак-Элисом построена первая асимметричная кодовая криптосистема, основанная на применении помехоустойчивых кодов Гоппы, при этом эффективные атаки на секретный ключ этой криптосистемы до сих пор не найдены. К настоящему врмени известно достаточно много кодовых криптосистем, но их криптографическая стойкость уступает стойкости классической криптосистемы Мак-Элиса. В связи с развитием квантовых вычислений кодовые криптосистемы рассматриваются как альтернатива теоретико-числовым, поэтому актуальной представляется задача поиска перспективных классов кодов для построения новых стойких кодовых криптосистем. Для этого можно использовать некоммутативные коды, т.е. идеалы в групповых алгебрах FqG над конечными некоммутативными группами G. Ранее изучалась стойкость криптосистем на кодах, индуцированных кодами на подгруппах. Важной для исследования некоммутативных кодов является теорема Веддерберна, доказывающая существование изоморфизма групповой алгебры на прямую сумму матричных алгебр, но конкретный вид слагаемых и конструкция изоморфизма этой теоремой не определены, и поэтому для каждой группы остается задача построения представления Веддерберна. Ф.Е.Б. Мартинесом получено полное представление Веддерберна для групповой алгебры FqD_2n над диэдральной группой D_2n в случае, когда мощность поля и порядок группы взаимно просты. С использованием этих результатов в настоящей работе исследуются коды в групповой алгебре FqD_2n. Решена задача о структуре всех кодов и описана структура кодов, которые индуцированы кодами над циклическими подгруппами группы D_2n, что представляет интерес для криптографических приложений.

В данной статье представляется методология и результаты измерений и оценки накладных расходов, связанных с параллелизмом и виртуальной памятью. Для получения наиболее точных экспериментальных данных использовалась специальная методика измерений. Данная методика сфокусирована на измерениях совокупных потерь производительности, создаваемых параллелизмом, выраженным в форме легковесных потоков пользовательского режима на процессорах с архитектурой IA-32. Были получены и проанализированы данные, произведенные в средах с виртуальной памятью и без нее. Таким образом стало известно, какая потеря производительности вызывается виртуальной памятью, а также то, как она влияет на накладные расходы, связанные с параллелизмом. Эксперименты показали, что накладные расходы на параллелизм гораздо существеннее накладных расходов на виртуальную память. И тем не менее, между ними существует сложная взаимозависимость. Статья публикуется в авторской редакции.             

Рассматриваются классификация и области применения методов коммутации, их достоинства и недостатки. Построена модель вычислительной решетки в форме раскрашенной сети Петри с узлом, реализующим сквозную коммутацию пакетов. Модель состоит из узлов коммутации пакетов, генераторов трафика и пушек, которые формируют злонамеренный трафик, замаскированный под обычный пользовательский трафик. Исследованы характеристики модели решетки в условиях рабочей нагрузки с различной интенсивностью. Оценено влияние злонамеренного трафика типа «дуэль трафика» на параметры качества обслуживания решетки. Проведен сравнительный анализ устойчивости вычислительных решеток с узлами, реализующими технологию передачи пакетов с обязательной буферизацией, и сквозной коммутации. Показано, что производительности решеток примерно одинаковы в условиях рабочей нагрузки; а в условиях пиковой нагрузки решетка с узлом, реализующим технологию передачи пакетов с принудительной буферизацией, более устойчива. Решетка с узлами, реализующими технологию SAF, приходит к полному тупику через дополнительную нагрузку менее чем 10 процентов. После детального исследования показано, что конфигурация «дуэль трафика» не оказывает влияния на решетку с узлами cut-through при увеличении рабочей нагрузки до пиковой, при которой решетка приходит к полному тупику. Периодичность запуска пушек, генерирующих злонамеренный трафик, определена случайной функцией с пуассоновским распределением. Для построения моделей и измерений характеристик используется моделирующая система CPN Tools. Производительность решетки и среднее время доставки пакета оценивается при различных вариантах нагрузки на решетку.