Автор: Issam Al-Azzoni, Douglas G. Down
Перевод с англ.: А.В. Добров
Источник: I. Al-Azzoni, D.G. Down / J. Parallel Distrib. Comput. 70 (2010) 1231–1240
Распределенные сети возникли как значимый способ использования циклов простоя миллионов пользователей рабочих ПК через Интернет. Однако, чтобы эффективно использовать ресурсы распределенной сети, необходимо воспользоваться политикой планирования, подходящей таким системам. Политика планирования должна быть применима для крупных систем, включающих в себя великое множество компьютеров. Кроме того, такая политика должна учитывать возможность отказа, в том смысле, что она должна справляться с изменчивостью (летучестью) доступных ресурсов. Еще более увеличивает сложность планирования распределенных сетей их неотъемлимая неоднородность. Результатом этого будет снижение производительности, если политика планирования не будет учитывать сведения об однородности. В этой статье мы предлагаем и развиваем несколько политик планирования для распределенных систем, включающих различные степени однородности. В частности, мы предлагаем политику, которая эффективно использует решение задачи линейного программирования, что позволяет максимизировать пропускную способность системы. Мы также предлагаем надежные модификаций для решения ряда ограничений политики.
Широкая доступность дешевого компьютерного оборудования с высокой производительностью наряду с быстрым расширением Интернета и достижениями в области компьютерных технологий привели к увеличению числа использований гетерогенных (неоднородных) вычислительных (ГВ) систем (см. Ким и др. [19] и Контосанасис и Годеу [24]). Гетерогенные вычислительные системы строятся с помощью подключения нескольких машин с различными возможностями и координирования их действий для выполнения определенного набора задач. Распределенные сети - это такие ГВ, которые характеризуются не-привязаностью своих компьютеров. Целью таких систем является собрать как можно больше настольных ПК, принадлежащих отдельным индивидуумам, чьи циклы простоя могут быть использованы для работы сетевых приложений. Распределенные сети с недавних пор получили много внимания из-за успеха нескольких популярных приложений, таких как SETI@Home [31].
Важным компонентом распределенной сетевой системы является ее планировщик. Планировщик отвечает за распределение ресурсов по задачам. Он использует политику планирования, предназначеную для оптимизации определенных требования по производительности. Для распределенных сетей, политика планирования должна поддерживать системы с очень большим числом машин. Помимо естественной сложности составления расписаний для таких крупных систем, процесс еще более осложняется несколькими факторами. Во-первых, распределенные сети характеризуются очень высокой волатильностью ресурсов. В таких системах, компьютер может отказать в любое время без какого-либо предварительного предупреждения. Поскольку распределенные сети обычно основаны на связи через Интернет, компьютеры также подвержены ошибкам связи
Кроме того, распределенные сети являются вычислительными системами с добровольным подключением, в которых участники присоединиться по собственной воле, чтобы осуществлять работу сетевых приложений. Таким образом, компьютеры распределенной вычислительной системы не целиком преданны этой цели (т.е. задачи компьютеров на их рабочих местах должны иметь более высокий приоритет чем распределенные приложения). Чтобы лучше справиться с волатильностью ресурсов, политика планирования должна принимать во внимание возможность неисправности, в том смысле, что она должна использовать информацию об эффективной вычислительной мощности предоставляемой ресурсами и распределение их времени неисправности (если такие сведения доступны).
Другой фактор, влияющий на сложность планирования для распределенных сетей, связан с гетерогенной природы таких систем. Эти системы соединяют множество неоднородных компьютеров (настольные ПК с отличающимися ресурсами: процессора, памяти, дискового пространства и т.д.) для работы приложений с интенсивными вычислениями, которые имеют разнообразные вычислительные требования. Производительность может подвергаться существенному влиянию, если политикой планирования не учитывается информацию о задаче и однородности компьютеров.
В статье Аль-Азони и Дауна [1], мы предложили политику планирования, родственную основам линейного программирования, для распределенных сетей (Linear Programming Based Affinity Scheduling policy, LPAS_DG). Наши эксперименты показали, что она превосходит по показателям иные политики для сильно неоднородных систем. В этой статье мы выполнить более тщательный анализполитики. В частности, мы смоделируем системы с более широким диапазоном уровня гетерогенности. Кроме того, мы будем использовать структуру McMaster Grid Scheduling Testing (MGST) (Kokaly и соавт. [20]) в рамках осуществления политики планирования в распределенных испытательных стендах. Наш анализ показывает, что политика LPAS_DG может не продемонстрировать такхи же хороших результатов, как другие конкурирующие политики в почти полностью однородных системах. Кроме того, политики могут быть чувствительны к ошибкам в оценке параметров. В результате, мы предлагаем модификацию, направленную на разрешения этих ограничений. Эта статья имеет цель стать исключительно ссылкой на политику планирования LPAS_DG и включает в себя изначальную работу в [1] и расширения (модификации) к ней.
Структура данной работы следующая. В разделе 2 находится детальное описание рабочей модели. Раздел 2.1 описывает несколько политики планирования для распределенных сетей. Политика LPAS_DG описывается в разделе 3. В разделе 4 мы проводим подробный анализ политики LPAS_DG и предлогаем несколько модификаций. Раздел 5 подытоживает эту статью.
В нашей модели для распределенной сети существует специальный планировщик для переназначения поступающих задач запрашивающим компьютерам. Предположим, что число доступных машин в системе будет равным M. Также предполагается, что задачи разделены на N классов. Задачи, которые принадлежат одному и тому же классу i имеют частоту поступления αi. Пускай α будет вектором частоты поступлений, где i-ый элемент α - есть αi.
Наша модель поддерживает параллельные приложения, состоящие из независимых задач. В литературе, такие приложения иногда называют Bag-of-Tasks (Мешок-с-заданиями) приложениями (как в Anglano и др. [5]) или приложениями с параметром развертки (как в Casanova и др. [11]) а. Такие приложения становятся доминирующими для сетевых архитектур (посмотрите Iosup и др. [18] и Li и Buyya [26]). Мы предполагаем, что распределенные архитектуры главным образом используются, чтобы выполнять краткосрочные приложения (Kondo и др. [22]). Эти приложения состоят из небольших задач, чьи средние продолжительности выполнения довольно малы относительно среднего времени доступности компьютера. Следовательно, для таких приложений, нет никакой потребности для включения отказоустойчивых механизмов планирования, таких как, например, установление контрольных точек, миграция и дублирование.
Администрирование ресурсов системы для распределенных сетей главным образом использует вытягивающее/выборочное планирование (посмотрите Choi и др. [12,13]). В выборочном планировании, компьютер отправляет запрос планировщику для получения одной задачи (или более) на выполнение. Использование такой стратегии планирования в распределенных системах предпочтительно из-за того свойства, что машины не выделены. Одним из результатов использования выборочного планирования является то, что очередь задач формируется на стороне планировщика. Мы рассматриваем подобные распределенные сети, в которых нет очереди задач на каждом из компьютеров и все машины выполняют не более одного процесса за раз без вытеснения (посмотрите Choi и др. [13], Domingues и др. [15], и Kondo и др. [22]). Также, в выборочном планировании, планировщик принимает решение сразу же, как только поступает запрос от компьютера [13].
В распределенной сети машины могут перестать работать (или стать недоступными), в любое время без какого-либо предварительного уведомления [5]. Если компьютер перестал работать при выполнении процесса, то такая задача должна быть вновь возвращена планировщику. Мы предполагаем, что планировщик узнает об отказе любой машины за достаточно короткий промежуток времени [22]. Некоторые статьи конкретно изучают доступность компьютеров в распределенных сетях. В Nurmi и др. [28], данные доступности собраны от распределенных сетей различных архитектур. Их результаты указывают, что либо гиперэкспоненциальное, либо распределение Weibull эффективно описывают машинную доступность в сетях предприятий и вычислительной среде Интернета. В Kondo и др. [23], собраны статистические данные от четырех распределенных систем реальных предприятий для разработки прогнозирующих моделей машинной доступности. Другой подход к прогнозам доступности компьютеров вычислительной сети представлен в Жэне и др. [29]. Авторы применяют модели процессов полу-Маркова для прогноза. Результаты экспериментов демонстрируют, что такая оценка имеет высокую точность - 86% и в среднем и устойчива.
Одно
из основных свойств распределенных сетей является не-выделенность
машин. Когда компьютер доступен, он может также выполнять
локальные
задачи (т.е., задания/процессы, утвержденные локальным пользователем).
Локальным
заданиям машин всегда
дается более высокий приоритет. Когда машина занята своими локальными
заданиями, результатом является замедление выполнения задач
распределенной системы, направленных компьютеру планировщиком. Для
моделирования свойства не-выделенности
машин мы используем подход, подобный [5]. Пускай
µ′i,j
будет номинальным уровнем выполнения для задач класса i на
j-ой машине, следовательно 1/µ′i,j
являются
средним номинальным временем выполнения для задач класса i на
компьютере j.
Обратите
внимание на то, что для политик, которые рассматриваются в этой статье,
не
имеет
значения, какое распределение используется. Когда машина становится
доступной, она
отправляет свой запрос на получение новой задачи планировщику. Как и в
[5], мы
предполагаем, что компьютер также предоставляет необходимый квант
времени, который он потрати на выполнение заданий распределенной сети в
течение его
ближайшего периода доступности (т.е., доступности его CPU).
Эти оценки
могут
быть получены с помощью методов, таких как предложенные Вольским и др.
[33] и
Янг и др. [34]. Таким образом мы можем определить эффективный уровень
выполнения µi,j
для отосланных задач следующим образом:
µi,j
= µ′i,j×
aj,
где aj представляет часть возможностей j’ой машины, которые доступны для выполнения задач распределенной сети в течение ее ближайшего периода доступности. Для доступной машины мы принимаем это aj> 0. Предположим µ будет матрицей эффективного уровня выполнения, используя (i,j) для записи µi,j. Как и в [5,22], как только задача будет представлена машине, это же задание не может быть повторно отослано, если не пришел сигнал отказ.
Существенное количество работы было сделано на измерении и характеристике доступности CPU. Работа [34] включает методы на основе прогнозирующих устройств временного ряда для того, чтобы предсказать загрузку CPU в некотором будущем моменте времени, среднюю загрузку CPU для некоторого будущего временного интервала и изменение загрузки CPU по некоторому будущему временному интервалу. Работа [33] исследует проблему создания короткого срока и среднесрочных прогнозов доступности CPU в разделенных по времени системах Unix. Их результаты демонстрируют возможность создания короткого срока и среднесрочных прогнозов доступной производительности CPU несмотря на присутствие дальней автокорреляции и потенциального самоподобия. Kondo и др. [21] мера и характеризуют доступность CPU в крупномасштабной интернет-Настольной Сетке. Их характеристика фокусируется на идентификации образцов коррелированых методов кластеризации использования доступности. В Кресте и Льюисе [30], авторы идентифицируют пять состояний доступности, получающих, почему и как ресурсы становятся недоступными в течение долгого времени. Их модель доступности с пятью состояниями мотивирована моделью рабочей нагрузки Кондора [14].
Таксономия Настольных Сеток и обзора, фокусирующегося на планировании, обеспечена в [13]. Эта таксономия определена тремя главными компонентами: перспектива приложения, перспектива провайдера ресурса и перспектива планировщика. Относительно нашей модели рабочей нагрузки мы рассматриваем заявления с независимыми, фиксированными задачами, которые интенсивны вычислением. Нет никаких сроков, связанных с задачами, и задачи прибывают недетерминировано в планировщика. С точки зрения перспективы провайдера ресурса мы предполагаем, что провайдеры ресурса (т.е., машины) не выделены публичной казни, и они являются дефектными. С точки зрения перспективы планировщика принята централизованная организация. Планировщик использует основанное на получении по запросу планирование, в котором события планирования инициируются провайдерами ресурса.
Политика планирования, которая применима к нашей рабочей модели, является классическая политика Первым-Пришел-Первым-Обслуживается (FCFS). FCFS просто реализовать, и она используется в большинстве основных планировщиков распределенных сетей (см. Domingues и др. [16] и Kondo и др. [22]). Другой политикой планирования является Выбор Кратчайшей Задачи (PST). Данная политика использует основанный на эвристике подход для того, чтобы распределять процессы по компьютерам (см. [13]). Когда машина запрашивает задачу, политика подает ей задачу, которая является самой эффективной (в данном случае, короткой). Формально, когда машина j запрашивает задачу, планировщик присваивает ей дольше всего ожидавшее задание класса i, такое, что i∈arg maxi∈I (µi,j), где I представляет собой набор классов, в которых есть, по крайней мере, одно ждущее задание.
Родственная политика является вариацией обобщенного правила cµ (Gcµ), проанализированнго Mandelbaum и Stolyar [27]. Мы рассматриваем эту версию правила Gcµ, асимптотически минимизирующего стоимость задержки. Данная политика может быть описана следующим образом: когда машина j запрашивает задание, планировщик присваивает ее дольше всего ожидающую задачу класса i, такую, что для i∈arg maxi Di(t)µ′i,j, в котором Di(t) является наибольшим временем ожидания задачи класса i на текущий момент времени t. Подобно политике PST, политика Gcµ пытается присвоить задачи самым эффективным компьютерам. Однако, она избегает несправедливости путем рассмотрения времен ожидания задач. Насколько нам известно, политика Gcµ никогда не предлагалась в качестве политики планирования в распределенных сетях.
Политика
LPAS_DG требует решения следующего распределения
LP (Andradóttir и др. [4]), где переменные решения являются
λ и δi,j
поскольку i=1..N, j=1..M. Переменные δi,j
должны быть интерпретированы
как пропорциональное выделение машины j к классу i.
max
λ
Левая
сторона (1) представляет общую способность
выполнения, присвоенную классу i всеми машинами в системе. Правая
сторона
представляет частоту поступления задач, принадлежащих к классу i,
нормированную по фактору λ. Таким образом, (1) указывает,
что суммарная
мощность, выделенная для класса, должна быть, по крайней мере, столь же
большой
как масштабированная частота поступления заявок для этого класса.
Ограничение (2)
предотвращает сверхвыделение машины, а (3) указывает на то, что
отрицательные назначения не разрешены.
Политика
LPAS_DG определена следующим образом:
1.
Каждый раз, когда машина становится доступной
или недоступной, планировщик расчитывает назначение LP.
Пускай, λ∗ и
{δ∗i,
j},
i=1..N, j=1..M, будет оптимальным решением назначения LP. Распределение
LP всегда имеет
решение, т.к. не существует ограничения
для
нижней
границы λ. Пускай δ∗
будет матрицей машинного
распределения, где (i,j) запись соответствует δ∗i,j.
Значение λ∗ может
быть
интерпретировано как максимальная способность системы (Аль-Аззони и
Даун [2]).
2.
Когда машина j запрашивает задачу, позвольте Sj отметить
набор задач класса i
такой, что значение δ∗i,j
не является нулевым (Sj =
{i : δ∗i,j
̸= 0}). Планировщик
присваивает j-ой
машине
дольше всего ожидающую задачу класса i, такую что:
LPAS_DG политику можно рассматривать как адаптивную политику. Каждый раз, когда состояние системы изменяется, политика требует только решения LP. Например, новые машины могут быть добавлены и/или удалены из системы. Кроме того, параметры, такие как частота поступления и уровень выполнения могут помениться в течение длительного времени. При возникновении каждого из этих событий нужно просто решить новое LP и продолжить с получившимися значениями.
Выделение LP рассматривает и частоты поступления и уровни выполнения и их относительные значения в решении выделения машин к задачам. Кроме того, эти выделения ограничены доступностью CPU доступных машин. Рассмотрите систему с четырьмя машинами и тремя классами задач (M=4, N=3).
Уровни прибытия и выполнения следующие:
Предположите, что все машины полностью выделены (т.е., aj=1 для всего j= 1..M). При решении выделения LP дает λ*= 2.0513 и δ*=
Таким образом задачи класса 2 и 3 никогда не присваиваются слабой машине 1. В то время как машине 2 могут быть присвоенны задачи, принадлежащие любому из классов, машинам 1, 3, и 4 присваиваются задачи только класса 1. Обратите внимание на то, что машина 2 очень быстра для задач класса 2 и 3.
Рассмотрим другой сценарий в который a2 = 0.25. При решении выделения LP дает λ∗ = 1.3218 и
Таким образом, в этом случае машине 2 присваиваются только задачи класса 2. В дополнение к задачам класса 1, машине 3 выдаются задачи класса 3, а машине 4 присваиваются задачи класса 2. Обратите также внимание на то, что при новых возможностях CPU машина 3 является самой быстрой машиной на задачах класса 3, в то время как компьютер 4 является самой быстрой машиной для задач класса 2.
Теперь предположим, что машина 2 стала недоступной. Решая новое распределение LP (M=3, N=3) получаем λ∗=1.0306 и
Таким образом, компьютеру 1 продолжают присваиваться задачи только класса 1. Кроме того, в дополнение к задачам класса 1, машинам 3 и 4 продолжают выдаваться задачи класса 3 и 2, соответственно.
Могут существовать много оптимальных решений распределения LP. Эти оптимальные решения могут иметь различное количество нулевых элементов в δ∗ матрице. Следующее предположение является основным итогом линейного программирования (доказательство может быть найдено в Andradóttir и др. [3]): Суждение 1. Существует оптимальное решение распределения LP с, по крайней мере, NM+1−N−M элементами δ∗ матрицы, равными нулю. В идеале, число нулевых элементов в δ∗ матрицы должно быть равным NM+1−N−M. Если число нулевых элементов больше, то существует меньшее число машин для выполнения данного класса задача. Это ограничило бы политику в распределении рабочей нагрузки между компьютерами, что привело бы к ухудшению производительности. Например, в крайнем случае, когда число нулевых элементов равно NM−max(N,M), рабочая нагрузка вообще не может быть перераспределена между машинами. С другой стороны, если число нулевых элементов - очень маленькое, политика LPAS_DG больше напоминает Gcµ. Фактически, если δ∗ матрица не содержит нулей вообще, то LPAS_DG вырождается до политики Gcµ. Во всей данной статье, если не указано иначе, мы используем оптимальное распределение, в котором δ∗ матрица содержит ровно NM+1−N−M нулей. Мы вновь рассмотрим данное предположение в Разделе 4.3.
Линейное программирование использовалось в случае уже установившегося (стабильного) планирования приложений Мешка-с-Заданиями (см. Бомонт и др. [7] и Бенуа и др. [8]). Однако такая работа предполагает, что приложение состоит из задач идентичного размера и что точный размер задачи известен априорно. Работа Lenstra и др. [25] использует линейное программирование для нахождения расписания, минимизирующего период выполнения данного набора неоднородных задач. Предполагается, что времена выполнения задач заранее известны.
Одна из проблем использования линейного программирования в планировании является масштабируемость. Решение больших LPs требует времени. Это может создавать проблемы при использовании LPAS_DG политики для больших распределенных сетей или в систем, динамика которых очень часто изменяется. В таких случаях мы рекомендуем использование политики Gcµ. Здесь также отмечены некоторые характеристики распределения LPs, увеличивающих масштабируемость LPAS_DG. Во-первых, часто существует небольшое количество приложений (обычно, намного меньшее, чем число машин). Во-вторых, назначение LP не слишком плотное. Наконец, LPAS_DG политика не использует фактические значения для {δ∗i,j}, иначе как для дифференциации между нулевыми и ненулевыми элементами.
Мы используем моделирование для сравнения производительности различных политик планирования. Прибытие задач смоделировано при помощи независимых процессов Пуассона, каждым с уровнем αi, i=1..N. Время выполнения распределены по экспоненте с уровнями µ′i,j, где 1/µ′i,j представляет среднее время выполнения задачи класса i на машине j, i=1..N, j=1..M. Если не указано иначе, предполагается, что по экспоненте распределены также машинное время отказа и время доступности.
Существует несколько метрик производительности, которые могут использоваться для сравнения различных политик планирования [5,22]. Мы используем долгосрочное среднее время завершения задачи W, как метрику для сравнения производительности. Время завершения задачи определено как время, между утверждением задачи на выполнение и ее завершением, включая времена повторного предоставления. Для некоторых экспериментов моделирования мы также учитываем среднее время завершения для задач класса i, Wi, для всего i=1..N.
В этом разделе мы определяем несколько систем. Каждый эксперимент моделирования симулирует определенную систему при различных предположениях по доступности CPU и компьютера в целом. Для Систем А до Е, каждый эксперимент моделирует выполнение соответствующей системы для 20,000 единиц времени. Каждый эксперимент повторяется по 30 раз. Для каждого случая мы вычисляем W, улучшение (∆) по сравнению с политикой Gcµ и Wi, i=1..N. Для W мы предоставляем точность доверительного интервала, определенного как отношение половины ширины интервала к усредненному значению (все статистические данные нходятся на 95%-ом доверительном уровне). Отрицательное улучшение производительности означает, что политики уступает Gcµ.
Таблица 1 показывает результаты моделирования для Системы A. Система A является системой среднего размера с 4 классами задач и 30 машинами. Компьютеры в ней разделены на 6 групп, машины в одной и той же группе считаются идентичными. Таким образом, если две машины находятся в той же группе, то у них одни и те же уровни выполнения. Группы T и U состоят из 3 машин каждая, в то время как группы V, W, X, и Y имеют по 6 машин. Для систем, обсуждаемых в этом разделе, компьютеры упорядочены по машинам сначала T-группы, затем группы U, и т.д. Таким образом, например, в Системе A, машина с номером j=7 принадлежит группе V, а машина j=30 принадлежит группе Y. Уровни выполнения получены следующие:
Уровни выполнения для Системы A.
Используя это разделение, мы устанавливаем, что все машины являются гомогенным для задач класса 1; 10% машин являются слишком медленными для большей части прибытий (задач), 10% машин достаточно быстры для большей части поступлений, и большинство машин (остающиеся 80%) имеют высокую неоднородность по задачам и компьютерам.
Для Системы A, Таблица 1 показывает результаты моделирования по двум различным потокам прибытия: (i) α1 = [11.25 22.5 36 63], и (ii) α2 = [17.5 35 56 98]. Частоты поступления α1 приводят легкой загруженности системы, в то время как те, что в α2, приводят к в большей степени загрузки. Обратите внимание на то, что мы не даем результаты производительности для политики, когда она приводит либо к нестабильной работе системе, либо к системе, в которой производительность на несколько порядков хуже, чем у политики Gcµ.
Следующее является случаями, смоделированными при частотах поступления α1:
Следующее является случаями, смоделированными при частотах поступления α2:
Результаты моделирования, приведенные выше, предполагают, что использование политики LPAS_DG приводит к улучшению производительности по сравнению с Gcµ. Кроме того, применение политики FCFS для Системы А приводит к серъезному ухудшению производительности. Так как FCFS не принимает неоднородность задач во внимание, она демонстрирует низкую производительность и даже приводит к нестабильности системы с увеличением уровеня неоднородности задач или когда увеличивается системная загрузка. Это наглядно демонстрирует, что FCFS не будет в состоянии поддерживать тот же уровень пропускной способности, что Gcµ и LPAS_DG политики. Кроме того, политика PST тоже показывает низкую производительность и приводит к нестабильности системы при высокой загрузке (α2). Это объясняется тем, что политика несправедливо относится к задачам класса 1. Все компьютеры являются очень медленными на задачах данного класса, и таким образом политика PST дает более высокий приоритет другим классам процессов, приводящим к исчерпанию ресурсов для задач класса 1. Обратите внимание на то, что политики Gcµ и LPAS_DG избегают возможного исчерпания ресурсов на задачи, путем рассматрения времен ожидания процессов.
Системы с B по Е моделируют различные виды системной неоднородности. Машинная неоднородность определяется средним изменением по строкам µ, а неоднородность по задачам относится к среднему изменению по столбцам (см. Армстронга [6]). Неоднородность может быть подразделена на высокую и низкую неоднородность. На основе этого мы моделируем следующие четыре категории для неоднородности [6]: (a) высокая неоднородность по задачам и высокая машинная неоднородность (HiHi), (b) высокая неоднородность по задачам и низкая машинная неоднородность (HiLo), (c) низкая неоднородность по задачам и высокая машинная неоднородность (LoHi) и (d) низкая неоднородность по задачам и низкая машинная неоднородность (LoLo).
Таблицы 2-5 показывают
результаты моделирования для Систем с B по Е, соответственно.
Мы моделируем каждую систему по двум различным потокам
поступления: α1
и α2.
Частоты поступления α1
приводят к слегка более загруженной системе по сравнению с высокой
степенью загруженности системы при частотаха
поступления α2. Следующее
является случаями,
смоделированными при частотах поступления α1:
Таблица 1. Моделирование заканчивается для Системы A.
Следующее является случаями, смоделированными при частотах поступления α2:
Для Систем с B по E, M=28 и N=4. Машины разделены на 7 групп (промаркированным начиная с T до Z). Каждая группа состоит из 4 машин, и внутри одной группы компьютеры идентичны. Система B моделирует систему HiHi. Векторы частоты поступления являются α1=[50 48 50 48] и α2=[62.5 60 62.5 60]. Демонстрирует следующие уровни выполнения:
Уровни выполнения для Системы B.
Система C моделирует систему LoHi. Векторы частоты поступления являются α1=[30 30 24 24] и α2=[40 40 32 32]. Демонстрирует следующие уровни выполнения:
Уровни выполнения для Системы C.
Система D моделирует систему HiLo. Векторы частоты поступления являются α1=[14 28 35 35] и α2=[17 34 42.5 42.5]. Демонстрирует следующие уровни выполнения:
Уровни выполнения для Системы D.
Система E моделирует систему LoLo. Векторы частоты поступления являются α1=[24 27 21 30] и α2=[32 36 28 40]. Демонстрирует следующие уровни выполнения:
Уровни выполнения для Системы E.
Результаты указывают на то, что, в то время как политика LPAS_DG достигает очень конкурентоспособной производительности по сравнению с политикой Gcµ, ее производительность обычно выше в более неоднородных и высоко загруженных системах. LPAS_DG может не продемонстрировать такие же высокие результаты, как политика Gcµ, при более низкой задачной или машинной неоднородности. Это происходит из-за того, насколько агрессивной является политика LPAS_DG при исключении машин для определенных классов задач.
Рассмотрим Систему A. Предположим, что каждая машина дает сбои с частотой 0.05 за единицу времени, а среднее время отказа равно четырем единицам. Доступности CPU даны следующие:
Мы моделируем систему при частотах поступления α=0.75×α1=[8.4375 16.875 27 47.25], где α1 является первым вектором частоты поступления, используемым в моделировании Системы A. Рассматрим два случая. В первом политика не использует оценку доступности CPU (т.е., политика предполагает что aj=1 для всех j=1..M). Во втором случае политика пользуется предполагаемой оценкой доступности CPU. Наши эксперименты по моделированию указывают на то, что политика LPAS_DG (которая включает информацию о доступности CPU) показывает результат в ∆=20.51%, в то время как LPAS_DG, не использующий эту информацию демонстрирует ∆=−156.41%. Эти результаты наглядно показывают, что политика LPAS_DG эффективно использует знание о доступности CPU. Кроме того, когда эти оценки не доступны, LPAS_DG будет исполняться весьма скверно. В таких случаях рекомендуется использование политики Gcµ.
Для моделирования более реалистичных сценариев мы используем данные, полученные из Anglano и др. [5] и Canonico [10], которые были собраны путем выполнения сравнительного тестирования инструментов в фактической системе. Мы будем называть эту систему - Система G.
В [5], авторы определяют номинальную вычислительную мощность машины как действительное число, значение которого прямо пропорционально ее скорости. Таким образом, компьютер с номинальной вычислительной мощностью в 2 единицы в дважды быстрее, чем машина с номинальной вычислительной мощностью 1. Определено, что, для Системы G имеются три различных значения номинальной вычислительной мощности машин, а именно, {1, 1.125, 1.4375}
Таблица 2. Результаты моделирования для Системы B.
Таблица 3. Результаты моделирования для Системы С.
Таблица 4. Результаты моделирования для Системы D.
Таблица 5. Результаты моделирования для Системы E.
Так как мы рассматриваем проблему планирования многочисленных приложений в распределенных системах, мы определяем Pi,j как номинальную вычислительную мощность машины j на задачах класса i. Таким образом машина j с Pi,j=2 в два раза быстрее компьютера j′ с Pi,j′=1 на задачах класса i. Используя этот способ мы можем описать системы, в которых компьютер является быстрым на некоторых приложениях, но медленным на других.
Как описывается в [5], доступность CPU описывается цепью Маркова, параметры которой вычисляются с помощью контроля (мониторинга) сети и системы прогнозирования. Новое значение для доступности CPU вычисляется примерно каждые 10 единиц времени. О фактических значениях вероятности перехода для каждой машины сообщается в [10] (см. Таблицу 4.14). Для политики LPAS_DG мы вычисляем αj как среднюю доступность CPU для каждой машины j от соответствующей цепи Маркова. Это справедливо для модели Системы G, так как среднее время выполнения для выбранной задачи намного больше, чем среднее время, проведенное в определенном состоянии марковской цепи.
Для моделирования машинной доступности мы используем распределение Weibull. Фактические значения для параметров Weibull зависят от конкретного компьютера. Для Системы G, эти параметры (форма и масштаб) даны в Таблице 4.14 в [10]. Как в [5], время отказа компьютера установлено на постоянной отметке в 120 единиц времени.
Мы моделируем две конфигурации на основе Системы G (G1 и G2). Обе системы состоят из M=300 машин. Мы моделируем выполнение каждой системы для двух миллиардов единиц времени. Группируем компьютеры в 15 групп. Каждая группа состоит из 20 машин, идентичных с точки зрения цепи Маркова, описывающей доступности CPU и параметры для Weibull распределения. Каждая группа имеет те же параметры, что и одного из 15 компьютеров Системы G, перечисленных в Таблице 4.14 в [10].
В Системе G1 мы предполагаем, что машины группы идентичны с точки зрения их номинальных вычислительных мощностей. У каждой группы есть та же номинальная вычислительная мощность, как и у одной из 15 машин Системы G. Кроме того, мы предполагаем, что номинальная вычислительная мощность компьютера зависит только от самого компьютера и независима от класса выполняемых им задач. Таким образом, если машина j принадлежит группе G, имеющей номинальную вычислительную мощность PG, то Pi,j=PG, для всех i=1..N. Таким образом быстрый компьютер будет быстрым относительно всех приложений.
Рисунок 1. Относительное среднее время завершения задачи: Система G1 при частотах поступления α1.
Рисунок 2. Относительное среднее время завершения задачи: Система G2 при частотах поступления α1.
Рисунок 3. Относительное среднее время завершения задачи: Система G2 при частотах поступления α2 (FCFS приводит к нестабильной системе).
В Системе G2 мы предположили, что каждый компьютер имеет номинальную вычислительную мощность (для задач класса i) Pi,j выбирается в произвольном порядке из списка значений {1, 1.125, 1.4375} с равной долей вероятности. Таким образом, машина может быстро выполнять некоторые приложения и в то же время медленно выполнять другие.
Наконец, мы предполагаем, что существуют N=4 класса задач (или приложений). Авторы в [5] определяют BaseTime как среднее время выполнения задачи, отправленной машине с номинальной вычислительной мощностью 1. Таким образом, каждый класс состоит из задач с одинаковым значением характеристики BaseTime (для класса i, мы обозначаем его BaseTimei). Мы предполагаем что BaseTimei={8750, 17,500, 35,000, 50,000}, для i=1..4, соответственно. Этой информации достаточно для генерации матрицы µ′. Среднее номинальное время выполнения задач класса i на компьютере j, может быть рассчитано как BaseTimei×1/Pi,j.
Рисунки 1 и 2 показывают результаты моделирования для Систем G1 и G2 под частотами поступления α1 = [0.00457 0.00229 0.00114 0.00080]. Рисунок 3 демонстрирует результаты для Системы G2 при более высокой загрузке (α1=[0.00495 0.00110 0.00214 0.00135]). Эти данные показывают значения среднего времени завершения задач, нормализованные относительно политики Gcµ (точность сгенерированных доверительных интервалов составляет 0.1% или меньше). И Gcµ, и LPAS_DG политики приводят к существенному улучшению производительности. Политика LPAS_DG демонстрирует превосходящие результаты в более неоднородных системах.
В этом разделе мы используем платформу MGST для анализа производительности политики LPAS_DG. MGST является эмулятором в том смысле, что выполняет реальную реализацию политики планирования. Данный инструмент дополняет процесс моделирования путем упрощения и автоматизации этапа реалистичного тестирования производительности на распределенном испытательном стенде (модели). Мы используем результаты развертывания MGST для создания нескольких рекомендаций по практическому применению LPAS_DG политики.
В наших экспериментах мы протестировали политику LPAS_DG в нескольких системах. Используемыми системами были компьютеры Macintosh на базе чипсетов Intel (двухъядерные 2.0 ГГц) и PowerPC (одноядерные 2.0 ГГц). Системы использовали одну и ту же сеть. Стоит обратить внимание на то, что, в то время как компьютеры имели одинаковую процессорную скорость, платформа MGST позволяет нам эмулировать различные категории системной неоднородности.
Каждый тест проводился два раза, один раз с использованием инструмента моделирования, описанного в Разделе 4.1, а другой - по средствам MGST. Метрика, использованная для моделирования и экспериментов, является средним временем отклика, включая среднюю коммуникационную задержку экспериментов MGST. Коммуникационная задержка - есть разница между временем, когда задача была отправлена на выполнение, и временем, когда она действительно начинала исполнятся. Эта главным образом связано с задержкой сетевых коммуникаций, но она также могла быть вызвана обеспечением программного уровня, ответственным за распределение и выполнение задач.
Эксперименты проводились на категориях HiHi и LoLo системной неоднородности (см. Раздел 4.1.1). Четыре эксперимента проводились на каждой категории. В некоторых экспериментах были включены сбои, что означает, что машины могли переставать работать во время выполнения задач. В некоторых экспериментах компьютеры были полностью выделены, когда все их ресурсы использовались исключительно распределенной системой. В других экспериментах только определенный процент ресурсов был доступен для сетевых задач. Мы будем использовать комбинации следующих сокращений для выражения этих свойств в экспериментах: FE, FD, MFD, MPD для моделей с включением сбоев, отключенными сбоями, полностью выделенных компьютеров и машин, назначенных лишь частично. Например, комбинация, MPD/FD описывает эксперимент, в котором машины частично выделены и отказы отсутствуют.
Окружение HiHi было создано из 21 машины и 4 классов задач. Всего было семь групп машин, по 3 компьютера в каждой. Элементы одной и той же группы имели одинаковые уровни выполнения. Машины группы 1 маркировались как 1, 2 и 3, компьютеры группы 2 - 4, 5 и 6, и т.д. У групп 1–7 были те же уровни выполнения как и у групп T–Z в Системе B, соответственно. Частоты поступления классов задач были α=[37.5 36 37.5 36]. Среднее время отклика для каждого класса задач и полное среднее время отклика показано в Таблице 6.
Среда LoLo была создана из 21 машины и 4 классов задач. Компьютеры были разделены на семь групп таким же образом, как и машины в установке HiHi. У групп 1–7 были те же уровни выполнения как и у групп T–Z из Системы E, соответственно. Частоты поступления классов задачи были α=[18 20.25 15.75 22.5]. Среднее время отклика для каждого класса задач и полное время отклика показано в Таблице 7.
Таблица 6. Результаты эксперимента на установке HiHi.
Таблица 7. Результаты эксперимента на установке LoLo.
В экспериментах MPD/FD и MPD/FE компьютеры 4, 11 и 15 имели доступность aj=0.5. Машины 7, 14 и 18 имели доступность aj=0.75. Оставшиеся машины были полностью выделены для сетевых вычислений. В MFD/FE и MPD/FE экспериментах каждый компьютер сбоил с вероятностью 0.02 раза за единицу времени и среднее время отказа составляло 2 единицы времени. Периоды имели экспоненциальное распределение.
Политика LPAS_DG была реализована впервые в MGST. Здесь мы даем несколько комментариев относительно реализации данной политики.
В некоторых экспериментах производительность политики планирования отличалась от результатов моделирования из-за компьютеров, испытывавших неожиданно высокие нагрузки. Различные источники ошибок, которые могут возникнуть в реальной системе, могут также значительно повысить нагрузку и даже потенциально вызывать нестабильности в системе. Эти ошибки могут быть вызваны:
Если что-либо или все сразу из вышеупомянутых факторов вызовут существенное увеличение загрузки, то производительность политики планирования существенно ухудшится. Обратите внимание на то, что эти факторы были обнаружены только после развертывания и применения политики LPAS_DG на MGST. Они не были обнаружены во время моделированиях.
LPAS_DG пострадала в экспериментах из-за агрессивной природы этой политики по уменьшению числа машин, выполняющих задачи каждого класса. Это привело к эксклюзивности компьютеров для определенных классов задач. Когда один класс может быть выполнен небольшим количеством машин, тогда производительность зависит только от этих машин, таким образом, увеличивается эффект упомянутых выше факторов. Сравните это с FCFS, где, если машина недорабатывает, эффект менее очевиден, так как этот компютер может получить любого другого (потенциально не перегруженного) компьютера.
Обсуждение выше указывает на то, что производительность LPAS_DG политики может пострадать, когда существуют ошибки в оценке параметров. Так как существует значительная степень неопределенности в системах ГС (см. Смита и др. [32]), представляет интерес внесение изменений в политики, позволяющих лучше справляться с подобными ошибками. В следующем разделе предлагают модификацию LPAS_DG, приводящие к повышению устойчивости.
В ходе предыдущих экспериментов мы предположили, что политика LPAS_DG использует оптимальное решение, в котором δ∗ матрица содержит ровно NM+1−N−M нулей. Такое ограничение сокращает количество машин, которые могут выполнить каждый класс задачи. В некоторых случаях, особенно в системах с низкой гетерогенностью задач, это может привести к ухудшению производительности. Кроме того, как замеченно в Разделе 4.2, это заставляет LPAS_DG политику быть менее устойчивой против потенциальных недочетов в оценке параметров и других источников ошибок.
В этом разделе мы модифицируем политику LPAS_DG путем устранения ограничения на использование оптимального решения, в котором δ∗ матрица содержит только NM+1−N−M нулей (см. Суждение 1). Однако мы избегаем использования оптимальных решений, в которых δ∗ матрица не содержит ни одного нулевого элемента, так как в этом случае LPAS_DG низводится до политики Gcµ. Для достижения этого мы используем оптимальные решения, предоставленные подпрограммой оптимизации барьера (CPXbaropt) ILOG CPLEX [17]. Путем смягчения такого ограничения на число нулевых элементов в δ∗ матрице, политика LPAS_DG становится менее агрессивной в своем исключении компьютеров для определенных классов задачи. Это приводит к улучшению производительности и увеличенной устойчивости.
Таблица 8 показывает результаты моделирования для систем различной неоднородности, которую рассматренных в Разделе 4.1.1. Эти результаты показывают, что измененный LPAS_DG политики приводит к существенному улучшению производительности по сравнению с исходной версией. Кроме того, производительность улучшилась и относительно политики Gcµ: ухудшение становится меньше в случае использования системы LoHi (Система C), а положительные изменения более заметны в cистемы HiLo (Система D).
В следующем эксперименте мы сравниваем неизмененную политику LPAS_DG с модифицированной версией учетом их устойчивости относительно оценок доступности CPU. Обсудим следующую систему (Система H). Система имеет компьютеры идентичные Системе A. Мы моделируем систему при частотах поступления α1 (см. Систему A). Каждая машина сбоит с вероятностью 0.02 за единицу времени и среднее время отказа равно двум единицам времени. Доступности CPU являются следующими:
Используя подход, подобный Iosup и др. [18] и Чжан и Иногачи [35], мы оцениваем влияние погрешности под предположением полной погрешности равной нулю [18]. Согласно этому предположению, в то время как любая индивидуальная оценка может быть неточной, (полная) средняя погрешность оценки 0. Зададим I как максимальную погрешностью, значение которой колеблется от 0% (совершенная информация) до100% (высокая погрешность). Когда компьютер j станет доступным, позвольте a′j определить предполагаемую доступность CPU для машины j, используемой политикой LPAS_DG для вычисления LP распределения. Во время нашего моделирования a′j вычислялось при помощи следующего отношения: a′j=aj×(1+E), где E выбран из универсального распределения [−I, +I], и aj является фактической доступностью CPU компьютера j. Если aj×(1+E)>1, то мы устанавливаем a′j равным 1; и точно так же если aj×(1+E)<0, мы устанавливаем a′j равным 0.
Таблица 8. Моделирование заканчивается для систем, которые рассматривают в Разделе 4.1.1.
Рисунок 4. Улучшения производительности под различными значениями для максимальной погрешности I.
Рис. 4 сравнивает две версии политики LPAS_DG с точки зрения улучшения их производительности относительно политики Gcµ. Данные показывают, что измененная версия более устойчива относительно оценок доступности CPU, в то время как оригинальная версия может привести к ухудшению эффективности при большими значениями I. Это происходит из-за агрессивности политики в уменьшении числа машин, выполнящих задачи каждого класса. Аналогичное наблюдение может быть сделано в отношении к улучшенной устойчивости против ошибок в оценках уровней прибытия и выполнения измененной LPAS_DG политики.
Отличительной особенностью нашей работы является предложение отказоустойчивых политик планирования, учитывающих неоднородность распределенных сетей. Когда информация о машинных уровнях выполнения задач доступна, мы предложили использование политики Gcµ для распределенных систем. Когда же частоты поступления задачи и доступность каждого CPU заранее известны, мы разработали политику LPAS_DG, использующую решение назначения LP. Обе политики демонстрируют намного лучшие результаты, чем FCFS, особенно в среде приложений с высокой неоднородностью задач. Мы продемонстрировали, что производительность LPAS_DG может пострадать из-за его агрессивности в разбиении на подмножества машин, которые могут выполнять данный класс задач эффективно. Существуют некоторые случаи, в которых рекомендуется политики Gcµ, а не LPAS_DG: (i) когда приложения имеют ограниченную неоднородность задач, (ii), когда система имеет ограниченную машинную неоднородность, (iii), когда существует высокий уровень погрешности при оценке частот поступления задач, машинных уровней выполнения или доступности CPU, или (iii) когда вычисление назначения LP создает существенные ограничения и задержки. В противном случае производительность политики LPAS_DG значительно выше, особенно для весьма неоднородных системах. Важным следующим шаг в нашем исследовании будет развертывание предложенных политик в крупномасштабных распределенных вычислительных системах (таких, как несколько экземпляров, разработанных при использовании промежуточного программного обеспечения BOINC [9]). В то время как это требует улучшения масштабируемости предложенных политик, может также стать необходимо включить несколько особенностей, не использованных в нашей рабочей модели, таких как создание контрольных точек, коммуникационная задержка и затраты на передачу данных.
Авторы выражают глубокую признательность Мэджуду Кокэли и Бену Кибартасу за их вклад в эксперименты на MGST.
[1]
I. Al-Azzoni, D.G. Down,
Dynamic
scheduling for
heterogeneous desktop grids, in: Proceedings of the 9th International
Conference on Grid Computing, 2008, pp. 136–143.
[2]
I. Al-Azzoni, D.G. Down,
Linear
programming based
affinity scheduling of independent tasks on heterogeneous computing
systems,
IEEE Transactions on Parallel and Distributed Systems 19 (12) (2008)
1671–1682.
[3]
S.
Andradóttir, H. Ayhan, D.G.
Down, Dynamic
server allocation for queueing networks with flexible servers,
Operations
Research 51 (6) (2003) 952–968.
[4]
S.
Andradóttir, H. Ayhan, D.G.
Down, Compensating
for failures with flexible servers, Operations Research 55 (4) (2007)
753–768.
[5]
C. Anglano, J. Brevik,
M. Canonico, D.
Nurmi, R.
Wolski, Fault-aware scheduling for bag-of-tasks applications on desktop
grids,
in: Proceedings of the 7th
International Conference on Grid
Computing, 2006, pp. 56–63.
[6]
R. Armstrong,
Investigation of effect of
different
run-time distributions on SmartNet performance, Master’s
thesis,
Naval
Postgraduate School, 1997.
[7]
O. Beaumont, L. Carter,
J. Ferrante, A.
Legrand,
Y. Robert, Bandwidth-centric allocation of independent tasks on
heterogeneous
platforms, in: Proceedings of the 16th International Parallel and
Distributed
Processing Symposium, 2002, pp. 67–72.
[8]
A. Benoit, L. Marchal,
J.-F. Pineau, Y.
Robert, F.
Vivien, Offline and online master-worker scheduling of concurrent
bags-of-tasks
on heterogeneous platforms, in: Proceedings of the 22nd International
Parallel
and Distributed Processing Symposium, 2008.
[9]
BOINC, http://boinc.berkeley.edu/.
1240 I. Al-Azzoni, D.G. Down / J. Parallel Distrib. Comput. 70 (2010)
1231–1240
[10]
M. Canonico, Scheduling
algorithms for
Bag-of-Tasks applications on faultprone desktop grids, Ph.D. thesis,
University
of Turin, 2006.
[11]
H. Casanova, D.
Zagorodnov, F. Berman,
A.
Legrand, Heuristics for scheduling parameter sweep applications in grid
environments, in: Proceedings of the 9th
Heterogeneous
Computing
Workshop, 2000, 349–363.
[12]
S. Choi, H. Kim, E.
Byun, M. Baik, S.
Kim, C.
Park, C. Hwang, Characterizing and classifying desktop grid, in:
Proceedings of
the 7th International Symposium on Cluster Computing and the Grid,
2007, pp.
743–748.
[13]
S. Choi, H. Kim, E.
Byun, C. Hwang, A
taxonomy of
desktop grid systems focusing on scheduling, Tech. Rep.
KU-CSE-2006-1120-01,
Department of Computer Science and Engeering, Korea University,
November 2006.
[14]
Condor,
http://www.cs.wisc.edu/condor/.
[15]
P. Domingues, A.
Andrzejak, L. Silva,
Scheduling
for fast turnaround time on institutional desktop grid, Tech. Rep.
TR-0027,
CoreGRID, January 2006.
[16]
P. Domingues, P.
Marques, L. Silva,
DGSchedSim: a
trace-driven simulator to evaluate scheduling algorithms for desktop
grid
environments, in: Proceedings of the 14th Euromicro International
Conference on
Parallel, Distributed, and Network-Based Processing, 2006, pp.
83–90.
[17]
ILOG CPLEX,
http://www.ilog.com/products/cplex/.
[18]
A. Iosup, O. Sonmez, S.
Anoep, D. Epema,
The
performance of bags-of-tasks in large-scale distributed systems, in:
Proceedings of the 17th International Symposium on High Performance
Distributed
Computing, 2008, pp. 97–108.
[19]
J.-K. Kim, S. Shivle,
H.J. Siegel, A.A.
Maciejewski, T.D. Braun, M. Schneider, S. Tideman, R. Chitta, R.B.
Dilmaghani,
R. Joshi, A. Kaul, A. Sharma, S. Sripada, P. Vangari, S.S. Yellampalli,
Dynamically mapping tasks with priorities and multiple deadlines in a
heterogeneous environment, Journal of Parallel and Distributed Computed
67 (2)
(2007) 154–169.
[20]
M. Kokaly, I.
Al-Azzoni, D.G. Down,
MGST: a
framework for the performance evaluation of desktop grids, in:
Proceedings of
the 24th International Parallel and Distributed Processing Symposium,
2009.
[21]
D. Kondo, A. Andrzejak,
D.P. Anderson,
On
correlated availability in internetdistributed systems, in: Proceedings
of the
9th International Conference on Grid Computing, 2008, pp.
276–283.
[22]
D. Kondo, A.A. Chien,
H. Casanova,
Resource
management for rapid application turnaround on enterprise desktop
grids, in:
Proceedings of the ACM/IEEE Conference on Supercomputing, 2004.
[23]
D. Kondo, G. Fedak, F.
Cappello, A.A.
Chien, H.
Casanova, Characterizing resource availability in enterprise desktop
grids,
Future Generation Computer Systems 23 (7) (2007) 888–903.
[24]
L. Kontothanassis, D.
Goddeau, Profile
driven
scheduling for a heterogeneous server cluster, in: Proceedings of the
34th
International Conference on Parallel Processing Workshops, 2005, pp.
336–345.
[25]
J.K. Lenstra, D.B.
Shmoys, É.
Tardos,
Approximation algorithms for scheduling unrelated parallel machines,
Mathematical Programming 46 (3) (1990) 259–271.
[26]
H. Li, R. Buyya,
Model-driven simulation
of grid
scheduling strategies, in: Proceedings of the 3rd International
Conference on
e-Science and Grid Computing, 2007, pp. 287–294.
[27]
A. Mandelbaum, A.L.
Stolyar, Scheduling
flexible
servers with convex delay costs: heavy-traffic optimality of the
generalized
cµ-rule, Operations Research 52 (6) (2004) 836–855.
[28]
D. Nurmi, J. Brevik, R.
Wolski, Modeling
machine
availability in enterprise and wide-area distributed computing
environments,
in: Proceedings of the 11th
International Euro-Par
Conference, 2005,
pp. 432–441.
[29]
X. Ren, S. Lee, R.
Eigenmann, S. Bagchi,
Prediction of resource availability in fine-grained cycle sharing
systems
empirical evaluation, Journal of Grid Computing 5 (2) (2007)
173–195.
[30]
B. Rood, M.J. Lewis,
Multi-state grid
resource
availability characterization, in: Proceedings of the 8th International
Conference on Grid Computing, 2007, pp. 42–49.
[31]
SETI@home,
http://setiathome.berkeley.edu/.
[32]
J. Smith, L. Briceno,
A.A. Maciejewski,
H.J.
Siegel, T. Renner, V. Shestak, J. Ladd, A. Sutton, D. Janovy, S.
Govindasamy,
A. Alqudah, R. Dewri, P. Prakash, Measuring the robustness of resource
allocations in a stochastic dynamic environment, in: Proceedings of the
International Parallel and Distributed Processing Symposium, 2007.
[33]
R. Wolski, N. Spring,
J. Hayes,
Predicting the
CPU availability of time-shared unix systems on the computational grid,
Cluster
Computing 3 (4) (2000) 293–301.
[34]
L. Yang, J.M. Schopf,
I. Foster,
Conservative
scheduling: using predicted variance to improve scheduling decisions in
dynamic
environments, in: Proceedings of the ACM/IEEE Conference on
Supercomputing,
2003.
[35]
Y. Zhang, Y. Inoguchi,
Influence of
inaccurate
performance prediction on task scheduling in a grid environment, IEICE
Transactions on Information and Systems E89-D (2) (2006)
479–486.