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

  Повний текст PDF - 305.586 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"