Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ А.Н. Сазонов
- 1. Составление расписаний 1.1. Проблемы составления расписаний
| Литература
1. Хоар Ч. Э. Р. Взаимодействующие последовательные процессы. М: Мир, 1989. 264с. СТАТИЧЕСКОЕ ПОСТРОЕНИЕ РАСПИСАНИЯ ВЫПОЛНЕНИЯ ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ А.Н. Сазонов Московский Государственный университет им. М.В. Ломоносова 1. Составление расписаний 1.1. Проблемы составления расписаний Загрузка процессоров, распределение задач между процессорами, накладные расходы на пересылку сообщений являются главными про- блемами, возникающими в процессе составления расписаний. 1.1.1. Загрузка процессоров В процессе работы распределенной вычислительной системы, из- за ограниченности скоростей связи, в общем случае будут происходить простои процессоров. На самом деле избежать этих простоев можно, только специальным образом создав алгоритм так, что данные всегда приходили бы с опережением. Ясно, что далеко не во всех случаях это возможно. Таким образом, задача составления расписаний, в частности, ре- шает проблему увеличения нагрузки на вычислительные устройства. Ясно, что точное составление оптимального расписания совершенно необязательно, т.к. в процессе вычислений будут неизбежно прояв- 150 ляться недетерминированные отклонения в работе системы, связанные с невозможностью точно оценить время выполнения каждой задачи, предугадать все столкновения данных и задержки в буферах. 1.1.2. Назначение задач на процессоры В процессе составления расписания выполнения задач одной из главных проблем является распределение задач на конкретные вычис- лительные устройства. Если задачи таким образом распределены так, что все необходимые данные находятся на процессоре, исполняющем каждую задачу, тогда процессоры системы лишь читают локальные данные, обеспечивая максимальный параллелизм. В реальных прило- жениях такое распределение встречается весьма редко, т.к. требуется распараллелить задачи таким образом, чтобы они были полностью независимы друг от друга. Ясно, что такая ситуация вряд ли возможна в реальных задачах. Но если процессор не имеет нужных ему данных, требуется пере- сылка информации от процессора, который содержит нужные данные. Только после такой пересылки можно производить вычисления. Пло- хое распределение задач между процессорами вызывает всевозможные задержки данных. Таким образом, от распараллеливающей системы требуется, чтобы она составляла расписание задач и распределяла их между вычислителями так, чтобы минимизировать задержки. Следова- тельно, требуется обеспечить максимальное упреждение данных. 1.1.3. Накладные расходы на пересылку информации Как было описано выше, если процессор не обладает нужными ему данными, это вызывает задержку выполнения задач. Время, требую- щееся на пересылку требуемой информации, называется накладными расходами на пересылки. Для сокращения таких расходов требуется оптимально распределять задачи между процессорами и составлять расписание их выполнения. 1.1.4. Накладные расходы на составление расписаний Алгоритм назначения задач на параллельную систему и упорядо- чивания их во времени требует значительных вычислительных ресур- сов, особенно, если требуется получить весьма точное решение этой оптимизационной задачи. Это время называется накладными расхода- ми на распараллеливание. Системы, в которых такое распараллелива- ние происходит динамически, должны работать таким образом, чтобы 151 не вызывать задержки выполнения задач. Хотя для статического рас- параллеливания, когда расписание составляется еще до выполнения параллельной системы, имеется значительно большее количество вре- мени, очевидно, оно должно быть много меньше самого выигрыша от такого распределения, иначе он будет просто бессмысленным. жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|