Планирование банд

В информатике потоков групповое планирование — это алгоритм планирования для параллельных систем, который планирует одновременное выполнение связанных процессов на разных или процессорах . Обычно это потоки, принадлежащие одному и тому же процессу, но они также могут быть из разных процессов, причем процессы могут иметь отношения производитель-потребитель или исходить из одной и той же программы MPI .

Групповое планирование используется для того, чтобы гарантировать, что если два или более потоков или процессов взаимодействуют друг с другом, все они будут готовы к взаимодействию одновременно. Если бы они не были запланированы группой, то можно было бы подождать, чтобы отправить или получить сообщение другому, пока он спит, и наоборот. Когда процессоры перегружены и групповое планирование не используется внутри группы процессов или потоков, которые взаимодействуют друг с другом, каждое коммуникационное событие может пострадать от накладных расходов, связанных с переключением контекста .

Планирование банд основано на структуре данных, называемой матрицей Оустерхаута. В этой матрице каждая строка представляет собой интервал времени, а каждый столбец — процессор. Потоки или процессы каждого задания упакованы в одну строку матрицы. ^[1] Во время выполнения скоординированное переключение контекста выполняется на всех узлах для переключения с процессов в одной строке на процессы в следующей строке.

Групповое планирование более строгое, чем совместное планирование . ^[2] Он требует, чтобы все потоки одного и того же процесса выполнялись одновременно, в то время как совместное планирование допускает фрагменты , которые представляют собой наборы потоков, которые не выполняются одновременно с остальной частью группы.

Групповое планирование было реализовано и использовалось в производственном режиме на нескольких параллельных машинах, в первую очередь на Connection Machine CM-5.

Типы

Сумка банд (BoG)

При групповом планировании происходит сопоставление один к одному, что означает, что каждая задача будет сопоставлена с процессором. Обычно рабочие места рассматриваются как независимые банды, но при использовании схемы «мешок банд» все банды можно объединить и отправить в систему вместе. Когда задания выполняются в системе, выполнение никогда не может быть завершено до тех пор, пока все банды, принадлежащие к одному и тому же BoG, не завершат свое выполнение. ^[3] Таким образом, если одна банда, принадлежащая к какому-то заданию, завершит его выполнение, ей придется подождать, пока все банды завершат свои выполнения. Это приводит к увеличению накладных расходов на задержку синхронизации.

Время ответа $R_{j}$ из $j^{th}$ Bag of Gangs определяется как временной интервал от прибытия BoG к сетевому диспетчеру до завершения работ всех подгрупп, принадлежащих BoG. Среднее время ответа определяется следующим образом:

Время отклика (RT)= ${\frac {1}{N}}\textstyle \sum _{j-1}^{N}R_{j}\displaystyle$ . ^[3]

На время ответа дополнительно влияет поступление приоритетного задания. Всякий раз, когда приоритетное задание поступает в систему, этому заданию будет присвоен приоритет по отношению ко всем другим заданиям, даже над теми, которые в данный момент выполняются на процессорах. В этом случае, когда поступит приоритетное задание, подгруппа, выполняющаяся в данный момент в системе, будет остановлена, и весь достигнутый прогресс будет потерян, и его необходимо будет переделать. Это прерывание задания еще больше задержит общее время ответа BoG. ^[3]

Адаптированная система в порядке очереди (AFCFS)

Адаптированная схема «первым пришел — первым обслужен» (AFCFS) — это адаптированная версия схемы «первым пришел и первым обслужен». По схеме «первым пришел — первым обслужен» любое задание, которое придет первым, будет передано на выполнение. Но в схеме AFCFS, как только задание поступает в систему, оно не будет запланировано до тех пор, пока не будет доступно достаточное количество процессоров для выполнения соответствующего задания. ^[3] Когда большое задание поступает в систему и присутствует в начале очереди готовности, но доступно недостаточно процессоров, политика AFCFS запланирует меньшее задание, для которого доступно достаточное количество процессоров, даже если это задание находится в конце очереди. очередь. Другими словами, эта схема отдает предпочтение заданиям меньшего размера по сравнению с заданиями большего размера в зависимости от доступности процессора, что приводит к усилению фрагментации системы. ^[3]^[4]

Самая крупная банда, которую сначала обслужили (LGFS)

В приведенной выше схеме выполнения задачи, соответствующие увеличению размера задания, помещаются в очередь, при этом задачи, принадлежащие наибольшей группе, планируются первыми, но этот метод выполнения имеет тенденцию приводить к истощению ресурсов меньших заданий и, следовательно, непригоден для выполнения в системах со сравнительно небольшим количеством процессоров. ^[5]

AFCFS и LGFS также приходится иметь дело с возможным сбоем процессора. В таком случае задачи, выполняющиеся на этом процессоре, передаются на выполнение другим процессорам. Задачи ожидают в начале очереди на этих процессорах, пока текущий процессор находится в ремонте.

Из вышеуказанной проблемы вытекают два сценария: ^[5]

Случай блокировки: процессоры, назначенные прерванным заданиям, блокируются и не могут выполнять другие задания в своей очереди до тех пор, пока задания поврежденных процессоров не будут удалены. ^[5]
Неблокирующий случай: этот случай возникает, когда задания, уже выполняющиеся в процессорах, обрабатываются раньше, а не ждут возобновления выполнения заблокированных заданий. ^[5]

Планирование парной банды

Групповое планирование при выполнении процессов, связанных с вводом-выводом, удерживает процессоры в режиме ожидания ответов от других процессоров, тогда как простаивающие процессоры могут использоваться для выполнения задач. Если группа состоит из смеси ЦП и процессов ввода-вывода, поскольку эти процессы мало вмешиваются в работу друг друга, можно определить алгоритмы, которые будут одновременно загружать как ЦП, так и процессы ввода-вывода, используя параллелизм. Этот метод представляет идею сопоставления пар групп, одна из которых основана на вводе-выводе, а другая — на процессоре. Каждая банда предполагает, что она работает изолированно, поскольку использует разные устройства. ^[6]

Алгоритм планирования

Общий случай: В общем случае в сети назначается центральный узел для управления распределением задач и распределением ресурсов. Он хранит информацию в матрице Оустерхаута. При строгом групповом планировании за раз выбирается одна строка, после чего планировщик узла планирует процесс в соответствующей ячейке этой строки. ^[6]
Парная группа: при планировании парной группы выбираются две строки вместо одной, по одной для каждой группы, связанной с вводом-выводом, и группы ЦП. Локальный планировщик может по своему усмотрению распределять задания соответствующим процессорам, чтобы обеспечить максимально допустимый параллелизм. ^[6]

Методы синхронизации

Одновременное планирование банд (CGS)

Параллельное планирование группы представляет собой высокомасштабируемый и универсальный алгоритм, предполагающий наличие синхронизатора, использующего внутренние часы каждого узла. СКГ в основном состоит из следующих трех компонентов. ^[7]

Модуль процессора/памяти (также называемый элементом обработки).
Двусторонняя сеть, обеспечивающая связь 1-1.
Синхронизатор, который выполняет синхронизацию всех PE через постоянный интервал.

Алгоритм синхронизации выполняется в два этапа. ^[7]

При изменении нагрузки планировщик внешнего интерфейса создает специальный график.
Затем локальный планировщик следует расписанию, переключаясь между заданиями, которые были распределены им внешним планировщиком.

Мы предполагаем существование синхронизатора, который отправляет сигнал всем узлам кластера с постоянным интервалом. CGS использует тот факт, что наиболее распространенными событиями, которые происходят в ПК, являются прерывания таймера, и они используют тот же параметр, что и внутренние часы. ^[7]

Инициализируется общий счетчик, который увеличивается каждый раз при возникновении прерывания и называется внутренними часами ОС.
Все узлы синхронизируются после интервала проверки «t» и используют внутренние часы отдельных узлов.
Если по истечении времени t нет расхождения индивидуальных часов узлов и глобальных часов, интервал времени t продлевается. В противном случае оно сокращается.
Постоянно проверять и обновлять интервал проверки t.

Система планирования SHARE

Система планирования SHARE использует внутреннюю систему синхронизации каждого узла и синхронизируется с использованием протокола NTP . Вариант планирования реализуется путем сбора заданий с одинаковыми требованиями к ресурсам в группе и их выполнения в течение заранее определенного интервала времени. Незавершенные задания вытесняются после истечения интервала времени. ^[8]

Локальная память узла используется как пространство подкачки для предварительно освобожденных заданий. Основные преимущества плановой системы SHARE заключаются в том, что она гарантирует время обслуживания принятых заданий и поддерживает как пакетные, так и интерактивные задания.

Синхронизация:

Каждая группа процессов, использующая одни и те же ресурсы, отображается на отдельный процессор. Система SHARE в основном состоит из трех взаимодействующих модулей. ^[8]

Глобальный планировщик. Этот планировщик указывает локальному планировщику определенный порядок выполнения процессов (членов локальной банды).
Локальный планировщик: после того, как локальному планировщику предоставляются задания для выполнения глобальным планировщиком, он гарантирует, что на любом из процессоров в заданном временном интервале выполняется только один параллельный процесс. Локальному планировщику требуется переключение контекста, чтобы вытеснить задание по истечении его временного интервала и заменить его новым.
Интерфейс с системой связи. Подсистема связи должна удовлетворять нескольким требованиям, которые значительно увеличивают требования к накладным расходам планировщика. В первую очередь они состоят из:
- Эффективность: необходимо предоставлять производительность оборудования межсоединения на уровне клиента.
- Контроль доступа: необходимо управлять доступом к подсистеме связи.
- Защита и безопасность: соединение должно поддерживать разделение процессоров, не позволяя одному влиять на производительность другого.
- Многопротокольность: соединение должно иметь возможность одновременно отображать различные протоколы для удовлетворения различных потребностей клиентов.

Критерии упаковки

Новый слот создается, когда мы не можем упаковать задание в доступный слот. В случае открытия нового слота, даже если задание можно упаковать в доступный слот, доля выполнения, равная единице от количества используемых слотов, увеличится. Поэтому были разработаны определенные алгоритмы по критериям упаковки, которые упомянуты ниже:

Алгоритм на основе мощности

Этот алгоритм контролирует емкость слотов и решает, есть ли необходимость в открытии нового слота. Есть два варианта этого алгоритма:

1. Первая примерка. Здесь используемые слоты проверяются на емкость в последовательном порядке, затем выбирается первый, имеющий достаточную емкость. Если ни один из доступных слотов не имеет достаточной емкости, открывается новый слот и элементы обработки (PE) распределяются в слоте в последовательном порядке. ^[9]

2. Лучше всего подходит. В отличие от первой подгонки, используемые слоты сортируются по емкости, а не в последовательном порядке. Выбирается слот с наименьшей достаточной емкостью. Если ни один из используемых слотов не имеет достаточной емкости, то открывается только один новый слот. После открытия нового слота элементы обработки (PE) распределяются в слоте в последовательном порядке согласно предыдущему алгоритму. ^[9]

Алгоритмы, основанные на левом и правом

Этот алгоритм представляет собой модифицированную версию алгоритма наилучшего соответствия. В алгоритме наилучшего соответствия PE распределяются в последовательном порядке, но в этом алгоритме PE можно вставлять с обоих направлений, чтобы уменьшить перекрытие между различными наборами PE, назначенными разным заданиям. ^[9]

1. Левый-правый по размеру. Здесь PE можно вставлять как в последовательном, так и в обратном последовательном порядке в зависимости от размера задания. Если размер задания небольшой, PE вставляются слева направо, а если задание большое, PE вставляются справа налево. ^[9]

2. Лево-право по слотам. В отличие от предыдущего алгоритма, где выбор основывался на размере задания, здесь выбор зависит от слота. Теперь слоты отображаются как заполненные, т.е. заполненные слева или справа. PE распределяются по заданиям в том же порядке. Количество прорезей с обеих сторон примерно одинаково, поэтому при открытии новой прорези направление указывается исходя из количества прорезей в обоих направлениях. ^[9]

Алгоритмы на основе нагрузки

Алгоритмы на основе емкости и левого-правого не учитывают нагрузку на отдельные PE. Алгоритмы на основе нагрузки учитывают нагрузку на отдельный PE и отслеживают перекрытие между наборами PE, назначенными на разные задания. ^[9]

1. Минимальная максимальная нагрузка. В этой схеме PE сортируются по нагрузке, которую каждое задание будет иметь на PE. Наличие свободных PE в слоте определяет емкость слота. Предположим, что PE назначены на работу, которая имеет $x$ нити, $x^{th}$ PE в порядке загрузки (последний) определяет максимальную нагрузку, которую может иметь любой PE, доступный в слоте. Выбирается слот, который имеет минимальную максимальную нагрузку на любой PE, и в слоте используется ряд наименее загруженных свободных PE. ^[9]

2. Минимальная средняя нагрузка. В отличие от предыдущей схемы, в которой слоты выбирались исходя из минимальной максимальной нагрузки на $x^{th}$ PE, здесь слоты выбираются исходя из средней нагрузки на $x$ наименее загруженные PE. ^[9]

Алгоритм на основе приятеля

В этом алгоритме PE назначаются кластерами, а не индивидуально. PE сначала делятся на группы, которые имеют степень двойки. Каждому члену группы будет назначен контроллер, и когда поступит задание размера n, оно будет назначено контроллеру размера 2. ^{[lg 2]} (наименьшая степень 2, которая больше или равна n). Назначение контроллера осуществляется путем сначала сортировки всех используемых слотов, а затем определения групп по 2 ^{[lg 2]} смежные свободные процессоры. Если в некоторых слотах контроллера все PE свободны, то этому контроллеру будет назначено только новое поступившее задание. В противном случае открывается новый слот. ^[9]

Алгоритм на основе миграции

Во всех вышеупомянутых алгоритмах политика первоначального размещения фиксирована, и рабочие места распределяются между PE на ее основе. Однако эта схема переносит задания из одного набора PE в другой набор PE, что, в свою очередь, увеличивает долю выполнения системы. ^[9]

См. также

Ссылки

^ Дрор Г. Фейтельсон (1996). Схемы упаковки для банд-планирования . В книге «Стратегии планирования заданий для параллельной обработки», Springer-Verlag, конспекты лекций по информатике, том. 1162, стр. 89-110.
^ Фейтельсон, Дрор Г.; Рудольф, Ларри (1992). «Преимущества производительности группового планирования для точной синхронизации». Журнал параллельных и распределенных вычислений . 16 (4): 306–318. CiteSeerX 10.1.1.79.7070 . дои : 10.1016/0743-7315(92)90014-e .
^ Jump up to: ^а ^б ^с ^д ^и Папазачос, Зафейриос К.; Караца, Хелен Д. (август 2010 г.). «Оценка производительности планирования группировок в гетерогенной распределенной системе». Журнал систем и программного обеспечения . 83 (8): 1346–1354. дои : 10.1016/j.jss.2010.01.009 .
^ Зафейриос К. Папазачос, Хелен Д. Караца, «Оценка эффективности планирования банд в двухкластерной системе с миграциями», IPDPS , 2009, Симпозиум по параллельной и распределенной обработке, Международный симпозиум по параллельной и распределенной обработке, Международный 2009, стр. 1-8, дои : 10.1109/IPDPS.2009.5161172
^ Jump up to: ^а ^б ^с ^д «Анализ производительности группового планирования в распределенной системе при сбоях процессора» (PDF) .
^ Jump up to: ^а ^б ^с «Планирование парных банд» (PDF) .
^ Jump up to: ^а ^б ^с Хёдо, Кадзуки; Козакай, Ясуюки; Накаяма, Ясуичи (2007). «Реализация параллельного планировщика групп для кластерной системы на базе ПК». Системы и компьютеры в Японии . 38 (3): 39–48. дои : 10.1002/scj.20458 .
^ Jump up to: ^а ^б Общество, Ieee Computer (1996). Групповое планирование для высокоэффективных распределенных многопроцессорных систем . Границы '96. стр. 4–. ISBN 9780818675515 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж «Схемы упаковки для планирования банд» (PDF) .

[1] Дрор Г. Фейтельсон (1996). Схемы упаковки для банд-планирования . В книге «Стратегии планирования заданий для параллельной обработки», Springer-Verlag, конспекты лекций по информатике, том. 1162, стр. 89-110.

[2] Фейтельсон, Дрор Г.; Рудольф, Ларри (1992). «Преимущества производительности группового планирования для точной синхронизации». Журнал параллельных и распределенных вычислений . 16 (4): 306–318. CiteSeerX 10.1.1.79.7070 . дои : 10.1016/0743-7315(92)90014-e .

[:0-3] Jump up to: ^а ^б ^с ^д ^и Папазачос, Зафейриос К.; Караца, Хелен Д. (август 2010 г.). «Оценка производительности планирования группировок в гетерогенной распределенной системе». Журнал систем и программного обеспечения . 83 (8): 1346–1354. дои : 10.1016/j.jss.2010.01.009 .

[4] Зафейриос К. Папазачос, Хелен Д. Караца, «Оценка эффективности планирования банд в двухкластерной системе с миграциями», IPDPS , 2009, Симпозиум по параллельной и распределенной обработке, Международный симпозиум по параллельной и распределенной обработке, Международный 2009, стр. 1-8, дои : 10.1109/IPDPS.2009.5161172

[:3-5] Jump up to: ^а ^б ^с ^д «Анализ производительности группового планирования в распределенной системе при сбоях процессора» (PDF) .

[:4-6] Jump up to: ^а ^б ^с «Планирование парных банд» (PDF) .

[:5-7] Jump up to: ^а ^б ^с Хёдо, Кадзуки; Козакай, Ясуюки; Накаяма, Ясуичи (2007). «Реализация параллельного планировщика групп для кластерной системы на базе ПК». Системы и компьютеры в Японии . 38 (3): 39–48. дои : 10.1002/scj.20458 .

[:2-8] Jump up to: ^а ^б Общество, Ieee Computer (1996). Групповое планирование для высокоэффективных распределенных многопроцессорных систем . Границы '96. стр. 4–. ISBN 9780818675515 .

[:1-9] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж «Схемы упаковки для планирования банд» (PDF) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v т и Планирование процессора
Алгоритмы	Срок-монотонный Самый ранний срок Сначала самый ранний подходящий виртуальный срок Справедливая доля Преимущественный фиксированный приоритет Передний план-фон Прогулка Обобщенный передний план-фон Самый высокий коэффициент отклика следующий Лотерея Многоуровневая очередь обратной связи Область разногласий в процессе Пропорциональная доля Скорость-монотонная Круговой Самая короткая работа следующая Кратчайшее оставшееся время Статистическое мультиплексирование с временным разделением Страйд Двухуровневый Windows НТ Алгоритм YDS
Линукс	Мозговой трах Абсолютно справедливо О(1) На) ЗАПЛАНИРОВАННЫЙ СРОК ПЛАНИРОВАНИЕ ФИФО РАСПИСАНИЕ НОРМАЛЬНОЕ
Другой	Совместимость процессоров Голод