Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
Организация параллельных процессов на системе кластерного
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
| Организация параллельных процессов на системе кластерного
типа для решения задачи о рюкзаке Параллельный алгоритм разрабатывался с учетом следующих фак- торов: • алгоритм должен обладать свойством масштабируемости, т.е. спо- собностью сохранять работоспособность независимо от числа процессоров в системе; • обмен информацией между процессами должен быть минималь- ным. Среди параллельных процессов выделяется управляющий процесс, который передает остальным процессам необходимые начальные дан- ные, распределяет подзадачи обхода поддеревьев дерева поиска между процессами и постоянно собирает построенные решения. Распределе- ние подзадач происходит следующим образом. На начальном этапе выделяются поддеревья, корневые вершины которых лежат на первом ярусе и каждый из процессов начинает левый обход в глубину выде- ленного ему поддерева. Процессы, которым не хватило поддеревьев, корни которых лежат на первом ярусе, а также процессы, закончившие обход своего поддерева подключаются «в помощь» к другим процес- сам. Для этого задача выбранного процесса дробится на подзадачи, т.е. 19 в соответствующем дереве выделяется поддерево, обход которого бу- дет выполняться подключенным процессом. Пусть P k – освободившийся процесс, а P s – процесс, задача кото- рого будет дробиться. Задача процесса P s заключается в левом обходе в глубину выделенного ему поддерева. Определяется максимальный номер яруса, обход всех ветвей которого уже был выполнен процессом P s . На следующем ярусе выбирается первая непройденная ветвь, и то- гда задача процесса P k заключается в обходе поддерева с корнем, соот- ветствующим концевой вершине выбранной ветви. Другими словами, он решает задачу построения всех ω-совместимых подмножеств, уже содержащих элементы соответствующие ветвям, ведущим от корня всего дерева к корню выделенного поддерева. При организации такого взаимодействия между процессами воз- никают проблемы, снижающие эффективность параллельного алго- ритма, такие как: определение процесса, задача которого будет разби- ваться на подзадачи; организация протокола связи с выбранным про- цессом; синхронизация работы всех процессов для избежания возник- новения состояния дедлока. жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|