О БАЛАНСИРОВКЕ ВЫЧИСЛИТЕЛЬНОЙ НАГРУЗКИ ПРИ РАСПАРАЛЛЕЛИВАНИИ РЕШЕНИЯ ЗАДАЧИ НАХОЖДЕНИЯ ПОКРЫТИЯ 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 80
- Downloads 0
СТЕГАНОАНАЛІТИЧНИЙ АЛГОРИТМ, ЗАСНОВАНИЙ НА АНАЛІЗІ ПРОСТОРОВОЇ ОБЛАСТІ ЦИФРОВИХ КОНТЕЙНЕРІВ STEGANALYTIC ALGORITHM, BASED ON THE ANALYSIS OF THE SPATIAL DOMAIN OF DIGITAL CONTAINERS
В роботі запропонований стеганоаналітичний алгоритм, заснований на врахуванні відмінностей характеру змін кількості блоків з однаковими значеннями яскравості колірних матриць послідовності зображень/кадрів відео послідов...
СИНТЕЗ И МОДЕЛИРОВАНИЕ РЕГУЛЯТОРА ДЛЯ ОБЪЕКТА С ИЗМЕНЯЮЩИМИСЯ ПАРАМЕТРАМИ SYNTHESIS AND MODELING OF THE REGULATOR FOR THE OBJECT WITH CHANGING PARAMETERS
Проведен синтез регулятора для объекта, параметры которого – коэффициент усиления и постоянная времени, могут изменяться в широких пределах. Заданная часть системы включает в себя исполнительный механизм (звено первого п...
ПОДДЕРЖКА ПРИНЯТИЯ РЕШЕНИЙ О РЕАЛИЗАЦИИ ПРИЛОЖЕНИЙ В ГИБРИДНОЙ ОБЛАЧНОЙ ИНФРАСТРУКТУРЕ SUPPORT FOR THE DECISION MAKING ON IMPLEMENTATION OF APPLICATIONS IN THE HYBRID CLOUD INFRASTRUCTURE
Облачные технологии и платформы активно развиваются и становятся все более востребованными. Наибольшую популярность последнее время завоевывают гибридные облака и мультиоблачные услуги, в которых реализуется распределенн...
SUBMISSION OF ALGORITHM FOR WORKS SEQUENCES FINDING WITH PETRI NET
An easy and close to the optimal heuristic algorithm to solve a problem of scheduling theory with some restriction is offered. Such algorithms it is useful to represent of a secure Petri net. The figure steps for solving...
POSSIBILITY OF OBTAINING FUNCTIONAL DEPENDENCES FROM DATABASE STRUCTURE
We study the possibility of obtaining functional dependencies from the scheme of the existing database, as well as the data contained in it. Statistical methods for finding dependencies between data were used to generate...