4. Планирование процессов параллельного выполнения ФП на ВС

4.1. Основные подходы к построению эффективных алгоритмов планирования

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

Рис. 1

То, что с увеличением количества компьютеров больше k_опт, время выполнения ФП уже не может быть уменьшено существенно, есть известный факт. Более того, оно может далее увеличиваться, если глубина распараллеливания [1], определяющая вычислительную сложность компонентов параллельной программы, которые разрешено перемещать между компьютерами ВС в процессе выполнения ФП, окажется настолько малой, что заметно начнут расти «накладные расходы» на управление и обмены между компьютерами [1].

Задача поиска оптимальных алгоритмов планирования, минимизирующих время выполнения параллельной программы на ВС с заданным количеством компьютеров, пока не имеет строго решения, имеющего широкое применение [1, 2, 3, 4, 5]. Это связано с тем, что для этого, как правило, требуется знание истории выполнения программы или модель, достаточно точно отражающая ее поведение при выполнении, время выполнения ее компонентов и др.

Поэтому для построения алгоритмов планирования, имеющих практическое значение, обычно используются эвристики [1, 2, 3], основанные на эмпирическом опыте, адаптивных схемах управления [1, 2, 3] привлечении результатов, касающихся планирования в областях, далеких от компьютерной техники (например, как в кластере MOSIX [6], применение механизмов рыночного регулирования цен для назначения ресурсов и достижения равномерной загрузки компьютеров).

При этом в качестве основных критериев, определяющих эффективность алгоритмов планирования, рассматриваются следующие:

• уменьшение времени простоев процессоров, используемых в ВС компьютеров;

• достижение равномерной загруженности ресурсов ВС, исключающее большую интенсивность обменов (swapping) между оперативной и дисковой памятью, между компьютерами ВС;

• уменьшение «накладных расходов» на управление параллельными процессами и на планирование.

Рассмотрим возможные пути для достижения сформулированных критериев.

Уменьшению времени простоя процессоров, с одной стороны, способствует равномерная загруженность компьютеров ВС. С другой стороны, фронт работ – множество готовых для выполнения процессов параллельной программы. Чем больше (в среднем) мощность этого множества, тем, очевидно, с большей вероятностью можно устранять простой того или иного процессора ВС, перераспределив процессы (работы). Как следствие, эффективное планирование должно иметь механизм, регулирующий фронт готовых для выполнения процессов.

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

Поддержание равномерной загруженности компьютеров ВС требует уточнения самого критерия загруженности. Следующие наиболее значимые параметры, измерение которых сегодня доступно средствами ОС (UNIX/Linux, Windows и др.), позволяют получить общую характеристику использования различных узлов компьютера:

• объем свободной памяти,

• время простоя процессора,

• интенсивность обменов между дисковой и оперативной памятью,

• интенсивность обменов с другими компьютерами.

Если первые два параметра измеряются ОС достаточно просто, то вторые требуют значительных временных затрат, являясь в то же время наиболее информативными.

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

Оба эти параметра несложно определяются ИН и планировщиком компьютера (см. п. 3), а также средствами ОС, позволяющими контролировать количество активизированных процессов.

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

Ясно, что измерение параметров загруженности требует времени, также как и сама процедура планирования. Уменьшение этого времени возможно за счет грамотной реализации управляющих программ, ясного понимания того, какой эффект может дать принимаемое решение по планированию и каковы будут временные издержки, связанные с его реализацией. Описанные в п. 3 правила параллельного вычисления значений функций на ВС являются хорошей иллюстрацией этого. В частности, мы уже обсуждали, что правильный выбор параметров L и L позволяет ограничить время, которое ИН тратит на обход контекста, а введение стека _о-вершин сокращает время на обратный обход контекста и др.

Характеризуя комплексно загруженность компьютера ВС, можно ввести нечеткую шкалу, которая в грубой форме имеет градации: простаивает, недогружен, нормально загружен, перегружен.

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

Можно считать, что компьютер недогружен, если доля времени простоя его процессора достаточно велика (больше некоторого эмпирически установленного значения, например, 70% для параллельных программ вычислительного характера, не предполагающих активную работу с внешними устройствами) и есть достаточного объема свободная оперативная память.

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

Компьютер нормально загружен, если доля времени простоя процессора не превышает некоторого порога, например 50%, и есть свободная память или невелика интенсивность обменов между дисковой и оперативной памятью.

Очевидно, что эти «пороги» могут уточняться в процессе работы и эффективно использоваться доля построения адаптивных алгоритмов планирования и управления процессами [1].

4.2. Реализация системы планирования процессов параллельного выполнения ФП

Планирование параллельных процессов выполнения ФП на ВС осуществляется на двух уровнях: компьютерном и общесистемном. На общесистемном уровне (Рис. 2) планировщик на сервере ВС (или узле ВС, кластера) решает задачу3 достижения равномерной загрузки компьютеров (процессоров) ВС.

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

Рис. 2. Схема взаимодействия планировщиков компьютера и сервера

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

Более сложные стратегии предполагают использование описанной в предыдущем разделе нечеткой шкалы, в соответствии с которой решается вопрос о снижении загруженности компьютера и адаптивно (в процессе выполнения на ВС функциональных программ) определяются в некотором смысле ее оптимальные значения.

Вычисленные на определенном интервале значения средней загруженности компьютеров ВС и ее девиации, а также корреляционные функции, характеризующие изменения загруженности, - естественный математический аппарат, используемый планировщиком сервера для оценки и прогнозирования загруженности компьютеров ВС.

Рассмотрим более подробно стратегию планирования процессов на компьютере.

Как следует из п. 3, задачу планирования на компьютере его планировщик решает совместно с ИН. Описанная стратегия обхода контекста при вычислениях и правильного подобранные параметры L и L позволяют ИН управлять фронтом готовых для выполнения процессов на компьютере.

Если обход контекста K_i невозможен, ИН пытается сначала продолжить вычисления, используя результаты вычисленных на других компьютерах фп, из списка , а если список пуст – их списка (см. блок-схемы на рис. Д.ВП.1.2, Д.ВП.1.3). Аналогичные действия выполняются для других контекстов, если списки и пусты. При этом ИН может выбирать на вычисления из списков контекстов K_j, j = 1, 2, …, N, фп, которые имеют большую или меньшую рекурсивную сложность, которая вычисляется для каждой фп программы перед ее выполнением (см. приложение). Если фронт готовых для вычисления фп небольшой, ИН может назначать на вычисление фп в порядке уменьшения их рекурсивной сложности. Если он большой (количество готовых для вычисления фп близко к L), то ИН вместе с планировщиком действуют в противоположном направлении, назначая на вычисление сначала фп с меньшей рекурсивной сложностью, оставляя, таким образом, возможность для пересылки на другие простаивающие или недогруженные компьютеры фп с максимальной рекурсивной сложностью с целью их более полной загрузки и уменьшения межкомпьютерных обменов.

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

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

5. Реализация системы управления параллельным выполнением ФП на ВС

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

Сервер узла – логическая единица, возможно, реализуемая на более мощном компьютере с большей физической памятью. Узлы могут объединяться путем введения новых, более высокого уровня логических серверов, реализующих функции управления подчиненными им узлами (управление их загруженностью, реконфигурированием и др.).

Рассмотрим более детально реализацию функций управления параллельным выполнением ФП на ВС, которые представлены на рис. 3.

Литература

1. Об интеллектуальных компьютерах

2. Пособие

3. Барский А.Б. Планирование параллельных вычислительных процессов. М.: Машиностроение, 1980.

4. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983.

5. Тиц П.Г. Организация параллельных вычислений на многомашинных (многопроцессорных) вычислительных системах. Кандид. диссертация, М.: МЭИ, 1975.

6. Описание MOSIX