О БАЛАНСИРОВКЕ ВЫЧИСЛИТЕЛЬНОЙ НАГРУЗКИ ПРИ РАСПАРАЛЛЕЛИВАНИИ РЕШЕНИЯ ЗАДАЧИ НАХОЖДЕНИЯ ПОКРЫТИЯ ABOUT BALANCING THE COMPUTATIONAL LOAD WHEN THE PARALLELIZATION OF THE SOLUTION OF PROBLEM OF FINDING A COVERAGE
Journal Title: Інформатика та математичні методи в моделюванні - Year 2018, Vol 8, Issue 2
Abstract
Рассматривается известная комбинаторная задача нахождения покрытия методом теорем о свойствах таблицы покрытия. В более ранней работе автора приводится последовательное решение данной задачи, имеющей циклический характер. В новой работе автора предлагается способ распараллеливания решения этой задачи, основанный на свойстве независимости ветвей вычислительного процесса (подпроцессов); таким свойством обладают внешние циклы подпроцесов поиска ядерных/антиядерных строк и поглощающих столбцов/поглощаемых строк. Строится последовательно-параллельный информационный граф такого решения, приводится его описание. Особую важность имеет определение такого распараллеливания вычислительного процесса, при котором вычислительная нагрузка на процессоры является равномерной, то есть сбалансированной. На практике во многих случаях циклов имеет место постепенное снижение объёма вычислений в теле цикла от максимального до единичного, в результате чего нагрузка на процессоры становится существенно неравномерной. Рассматриваемая задача нахождения покрытия является таким случаем. В работе предлагается геометрическое представление вычислительной нагрузки. Описанный выше случай неравномерной нагрузки представляется треугольником вычислительной нагрузки. Показывается способ преобразования треугольника нагрузки в равновеликий прямоугольник, что обеспечивает эффективную балансировку нагрузки на процессоры в параллельной системе. Предлагается оценка недогруженности процессоров.
Authors and Affiliations
О. Н. Паулин
Keywords
Related Articles
- EP ID EP341709
- DOI -
- Views 85
- Downloads 0
ДИСКРИМІНАЦІЯ ЗА НАЦІОНАЛЬНИМИ ОЗНАКАМИ В МЕРЕЖІ ІНТЕРНЕТ
Сьогодні мережа Інтернет не має дієвих засобів захисту для різнорідних верств населення у випадках розповсюдження певних стереотипних думок щодо расового, національного, релігійного, політичного або етнічного походження...
МАТЕМАТИЧНА МОДЕЛЬ СПОЖИВАННЯ ПАЛИВА МОДЕРНІЗОВАНИМ МАНЕВРОВИМ ТЕПЛОВОЗОМ MATHEMATICAL MODEL OF FUEL CONSUMPTION BY THE MODERNIZED SHUNTING LOCOMOTIVE
Наведено результати статистичної обробки експлуатаційних даних споживання палива для «гарячого» простою та виконання маневрової роботи модернізованим маневровим тепловозом ЧМЕ3М. Розроблено математичну модель витрати пал...
ПОЛУТОРАБАЙТНЫЕ НЕЛИНЕЙНЫЕ ПРЕОБРАЗОВАНИЯ КОНСТРУКЦИИ НИБЕРГ NIBERG CONSTRUCTION 12 BIT NONLINEAR TRANSFORMS
Статья посвящена актуальным вопросам конструирования полуторабайтных S- блоков подстановки для повышения эффективности современных шифров. Построены полуторабайтные S-блоки конструкции Ниберг над всеми изоморфными GF(2^1...
МОДЕЛІ РОЗПОДІЛЕНИХ СИСТЕМ ІЗ ЗАПІЗНЮЮЧИМ АРГУМЕНТОМ MODELS OF DISTRIBUTED SYSTEMS WITH DELAYED ARGUMENT
Запропоновано математичні моделі систем з розподіленими параметрами, які характеризуються запізнюваннями по аргументу за часом. Моделі отримано для систем k-го порядку, що дозволяє застосовувати їх у більшості прикладни...
АНАЛИЗ РЕАЛИЗАЦИИ МЕТОДА РЕГИСТРАЦИИ АКТИВНОСТИ БЛОКОВ LUT В СОСТАВЕ FPGA-БАЗИРОВАННЫХ УСТРОЙСТВ
Рассмотрена проблема контроля целостности FPGA-базированных компонентов компьютерных систем критического применения. Отмечено, что одним из наиболее опасных видов нарушения целостности FPGA проектов является злонамеренно...