Групповой выбор вычислительных кластеров по многим критериям

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Групповой выбор вычислительных кластеров по многим критериям

Петровский А. Б.

Аннотация

Рассматривается задача сравнения и выбора вычислительных кластеров, обладающих требуемыми для прикладных применений параметрами, как задача многокритериального стратегического выбора. Выбор варианта кластера производится на основе многих критериев, среди которых могут быть как количественные, так и качественные. Предложены способы формирования набора составных критериев, составляющих кластер с использованием интерактивного метода снижения размерности признакового пространства, исходя из технических и стоимостных характеристик аппаратных средств. По сконструированным таким образом составным критериям осуществляется многокритериальный выбор вычислительных кластеров с применением методов группового вербального анализа решений. Работа поддержана программами фундаментальных исследований президиума РАН «Интеллектуальные информационные технологии, математическое моделирование, системный анализ и автоматизация» и ОНИТ РАН «Информационные технологии и методы анализа сложных систем», Российским фондом фундаментальных исследований (проекты 11-07-00230, 11-07-00398), Российским гуманитарным научным фондом (проект 11-02-00131а).

Введение

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

Необходимость в разработке более дешевой аппаратной части суперкомпьютеров побудила обратить более пристальное внимание на кластерные технологии. По определению компании Digital Equipment Corporation (DEC), кластер -- это группа вычислительных машин, которые связаны между собою и функционируют как один узел обработки информации [16]. Активное развитие кластерных технологий обусловлено тем, что, используя стандартные компоненты - обычные процессоры, материнские платы, сетевые компоненты и тому подобное, которыми буквально «завален» весь мировой рынок, - стало возможным создание значительно более дешевых вычислительных комплексов не только не уступающих, но и порой превосходящих по производительности продукцию известных фирм, например, таких как Cray.

Кластеры можно разделить на две большие категории. Первая категория - кластеры высокой готовности или отказоустойчивые кластеры [5]. Для таких кластерных систем на первое место выходит понятие надежности. Вторая категория - высокопроизводительные или вычислительные кластеры. Для этой категории главным является производительность. Кластеры можно также разделить на однородные (состоящие из вычислительных узлов одной и той же конфигурации) и неоднородные (состоящие из вычислительных узлов различной конфигурации). В данной работе акцент сделан на однородные вычислительные кластеры (далее ВК).

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

Построение системы критериев

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

Выбор ВК зависит от следующих основных факторов.

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

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

Точность расчетов в ряде случаев также оказывает влияние на выбор типа процессора. Чем выше требуемая точность, тем больше времени нужно для расчета.

Интенсивность обмена данными между вычислительными узлами позволяет выбрать технологию построения сети ВК.

Вошедшие в перечень варианты ВК должны удовлетворять следующим основным требованиям: (а) совместимость компонентов ВК с имеющимся программным обеспечением для выполнения расчетов; (б) приемлемая производительность ВК; (в) приемлемая стоимость ВК.

Особенность рассматриваемых объектов выбора (сложные технические системы, в частности, ВК) состоит в том, что они характеризуются большим числом показателей. Поскольку вариантов немного, то обычно все варианты несравнимы друг с другом по своим характеристикам. В этой ситуации известные методы решения задачи выбора лучшего объекта оказываются неэффективными. Поэтому прежде, чем применять какой-либо метод вербального анализа решений, необходимо решить еще одну вспомогательную, но крайне важную задачу: построить процедуру, которая позволяет агрегировать большое число базовых (технических, эксплуатационных, стоимостных) характеристик ВК в небольшое число критериев, имеющих порядковые шкалы оценок (количественные и качественные). Сокращенное описание объектов позволит упростить процедуру решения исходной задачи выбора. Выбор критериев и формирование шкал оценок проводится ЛПР самостоятельно или с привлечением системного аналитика. Предлагается следующий подход формирования набора критериев [12, 13].

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

Следующим этапом является формирование вспомогательных шкал оценок для каждого базового показателя. Шкалы могут иметь числовые точечные, интервальные или вербальные (словесные) оценки. Шкалы оценок могут совпадать с обычно используемыми на практике, либо конструироваться специально для данного критерия. Например, производительность ВК оценивается в Гфлопсах, стоимость - в млн. рублей. Для сокращения размерности описания объекта часто бывает удобно перейти от непрерывной шкалы оценки к дискретной шкале, имеющей небольшое число оценок на шкале, и от количественной шкалы к качественной шкале. Например, можно оценивать стоимость оценками «низкая», «средняя», «высокая», указав для каждой из оценок соответствующие интервалы величин. Все сформированные оценки ЛПР упорядочивает от лучшей к худшей.

Далее ЛПР по своему усмотрению определяет число и состав критериев, их содержание. В качестве критерия можно выбрать один из базовых показателей (например, производительность, стоимость) или несколько характеристик, объединенных в составной критерий. ЛПР устанавливает, какие технические и эксплуатационные показатели будут считаться самостоятельными критериями, а какие будут отнесены к тому или иному составному критерию. Шкалы простых критериев, являющихся базовыми показателями, уже построены на предыдущем этапе. Для формирования шкал оценок по составным критериям можно воспользоваться несколькими процедурами. При формировании шкалы оценок составного критерия важно учесть, что одна часть характеристик, входящих в состав подобного критерия, может рассматриваться как самостоятельная, а другая часть характеристик может быть составной. Поэтому процедура построения шкалы составного критерия сама может состоять из нескольких этапов.

На основе анализа литературы [1, 2, 4, 5, 13, 14, 18, 19] был предложен список характеристик ВК, которые разделены на несколько групп. К первой отнесем технические характеристики кластера (процессор, базовая аппаратная платформа, технология построения сети, оперативная память, дисковая память).

Используемая операционная система и кластерное программное обеспечение составляют вторую группу. Производными от них является третья группа показателей: производитель технических и программных средств; производительность кластера; стоимость кластера (группа «Обобщенные характеристики»). И, наконец, в последнюю группу «Эксплуатационные характеристики» входят: энергопотребление, тепловыделение, уровень шума и условия окружающей среды.

Построение составных критериев

Исходя из базовых характеристик ВК, были предложены четыре критерия оценки ВК и разработаны шкалы их оценок. В качестве самостоятельных критериев для сравнения ВК были выбраны две базовые характеристики: стоимость и производительность кластера. Двумя другими являются составные критерии: возможность модернизации и сложность эксплуатации кластера, сконструированные из базовых характеристик и составных критериев нижнего уровня. Для построения шкал составных критериев использовался интерактивный метод снижения размерности признакового пространства [10]. Рассмотрим особенности шкал составных критериев.

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

Порядковая шкала оценок по критерию «Возможность модернизации кластера», сконструированная методом стратификации кортежей [9], включает в себя следующие оценки:

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

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

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

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

Таким образом, в составной критерий «Сложность эксплуатации кластера» входят базовые характеристики: производитель, стоимость владения и составной критерий «Эксплуатационные характеристики».

Шкала составного критерия «Эксплуатационные характеристики» была сформирована с использованием метода порядковой классификации ОРКЛАСС [6]. В составной критерий «Эксплуатационные характеристики» вошли следующие базовые показатели: энергопотребление, тепловыделение, уровень шума, требования к условиям окружающей среды. Для каждого из представленных базовых показателей ЛПР определил соответствующие порядковые вербальные шкалы оценок, которые были получены путем преобразования исходных интервальных шкал. Например:

K1 - энергопотребление (0 - низкое, 1 - среднее, 2 - высокое); K2 - тепловыделение (0 - низкое, 1 - среднее, 2 -- высокое); K3 - уровень шума (0 - низкий, 1 - средний, 2 - высокий); K4 - условия окружающей среды (0 - повышенные требования к условиям окружающей среды не предъявляются, 1 - кластер предъявляет повышенные требования к условиям окружающей среды).

Для составного критерия «Эксплуатационные характеристики» была предложена вспомогательная шкала, состоящая из 3-х порядковых вербальных оценок: (D1 - вычислительный кластер не предъявляет серьезных требований по организации условий эксплуатации, D2 - вычислительный кластер предъявляет незначительные требования по организации условий эксплуатации, D3 - вычислительный кластер предъявляет повышенные требования по организации условий эксплуатации).

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

Класс D1 (верхняя граница: 0000; нижняя граница: 0000); Класс D2 (верхняя граница: 1000,0100,0010,0001; нижняя граница: 2210,2120,2001,1101,0201,0111,0021); Класс D3 (верхняя граница: 0220,2101,1201,1011, 0211,0121; нижняя граница: 2221).

Порядковая шкала оценок по составному критерию «Сложность эксплуатации», сконструированная методом стратификации кортежей, включает в себя следующие оценки:

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

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

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

Пример

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

Предположим, что перед ЛПР стоит задача выбора ВК из трех конфигураций, представленных различными производителями вычислительной техники. Оценки ВК по предложенному набору составных критериев приведены в таблице 1.

Таблица 1. Оценки вычислительных кластеров по критериям

Как следует из таблицы 1, все варианты ВК теперь сравниваются по гораздо меньшему набору показателей (по четырем критериям), однако по-прежнему остаются несравнимыми. Для выбора лучшего ВК можно воспользоваться методом вербального анализа решений ЗАПРОС [6, 7], установив субъективную предпочтительность оценок по разным критериям и построив единую порядковую шкалу. Возможность сформировать разные наборы критериев позволяет сравнить полученные результаты выбора для разных вариантов с целью оценки качества выбора. В ряде случаев для надежности выбора целесообразно проранжировать варианты ВК сразу несколькими методами (например, ПАРК [7], AHP [15]) и сопоставить результаты.

Групповой выбор

Задача выбора ВК существенно осложняется в ситуации, когда присутствуют несколько ЛПР (экспертов). В этом случае один и тот же объект (ВК) может существовать в нескольких версиях или копиях с разнообразными, несогласованными или противоречивыми значениями признаков, а свертывание числовых и/или вербальных оценок является или математически некорректным или невозможным. При наличии многих признаков и нескольких экспертов или ЛПР, необходимо агрегировать индивидуальные ранжировки по отдельным признакам, которые, как правило, не совпадают. В рассмотренном примере пять ЛПР проранжировали три варианта конфигураций ВК тремя различными методами многокритериального выбора (ЗАПРОС [6], ПАРК [7], AHP [15]) по предложенному набору составных критериев.

Для групповой сортировки многопризнаковых объектов (ВК) использован метод АРАМИС (Агрегирование и Ранжирование Альтернатив около Многопризнаковых Идеальных Ситуаций) [11], который, в общем случае, не требует предварительного построения индивидуальных ранжировок и позволяет упорядочивать многопризнаковые объекты на основе противоречивых предпочтений нескольких ЛПР. Многопризнаковые объекты были представлены как мультимножества [8] и упорядочивались по показателю близости к «идеальной» точке в метрическом пространстве мультимножеств.

В методе АРАМИС объекты описываются множеством повторяющихся количественных и/или качественных атрибутов Q1,…,Qm представленных в виде мультимножеств. Многопризнаковые объекты A1,...,An рассматриваются как точки метрического пространства мультимножеств (A,d) с различными метриками d [8], которые можно сравнивать и упорядочивать по показателю относительной близости к наилучшему (идеальному) объекту Amax или наихудшему (антиидеальному) Amin в этом пространстве. Наилучший и наихудший объекты (которые могут быть гипотетическими) имеют наилучшие и наихудшие оценки по всем критериям Qs. Объекты упорядочиваются по показателю относительной близости к наилучшему объекту lmax(Ai)=d(Amax,Ai)/[d(Amax,Ai)+d(Amin,Ai)], где d(Amax,Ai) расстояние до наилучшего объекта Amax и d(Amin,Ai) расстояние до наихудшего объекта Amin.

Рассмотрим методы M1 (АРАМИС (равная важность критериев) ЗАПРОС), M2 (ПАРК), M3 (AHP), использованные ЛПР для ранжирования ВК, как новые атрибуты, которые характеризуют ВК. Каждый атрибут Mj имеет оценки mj1, mj2, mj3, соответствующие порядковым номерам ВК в ранжировках, полученным ЛПР (т.е. mj1, означает, что методом Mj объект имеет в ранжировке порядковый номер 1 и т.д.). Теперь каждый ВК Ai можно представить как множество с повторяющимися элементами или мультимножество Ai, порожденное множеством методов X=M1M2M3:

Ai={kAi(m11)?m11,…,kAi(m13)?m13;…; kAi(m31)?m31,…,kAi(m33)?m33}.

Здесь kAi(mjhj), hj=1,…,3, j=1,…,3 показатель кратности, соответствующий тому, сколько значений атрибута встречается в мультимножестве Ai, который показывает, сколько раз порядковый номер ВК в ранжировке mjhj получен всеми ЛПР во время ранжирования соответствующим методом Mj; знак ? обозначает, сколько kAi(mjhj) раз атрибут mjhj встречается в описании объекта Ai.

Соответственно, ВК A1, A2 и A3 представляются в виде следующих мультимножеств:

A1={3?m11, 2?m12, 0?m13; 2?m21, 2?m22, 1?m23; 2?m31, 2?m32, 1?m33},

A2={2?m11, 2?m12, 1?m13; 2?m21, 1?m22, 2?m23; 1?m31, 3?m32, 1?m33},

A3={0?m11, 1?m12, 4?m13; 1?m21, 2?m22, 2?m23; 2?m31, 0?m32, 3?m33},

наилучший ВК Amax и наихудший ВК Amin представлены мультимножествами:

Amax={5?m11,0, 0; 5?m21,0, 0; 5?m31,0, 0}, Amin={0, 0, 5?m13; 0, 0, 5?m23; 0, 0, 5?m33}.

Расстояния между отдельными мультимножествами (ВК) Ai, наилучшим (идеальным) Amax и наихудшим (антиидеальным) мультимножествами Amin, полученные после обработки результатов, равны соответственно: d1max(A1)=16, d1max(A2)=20, d1max(A3)=24; d1min(A1)=26, d1min(A2)=22, d1min(A3)=12, где d1 -- метрика типа Хемминга. Значения показателя lmax(Ai) относительной близости ВК Ai к наилучшему ВК Amax задаются величинами: lmax(A1)=0,381, lmax(A2)=0,4762, lmax(A3)=0,6667. Итоговое упорядочение ВК по увеличению показателя относительной близости к наилучшему ВК Amax имеет вид: A1A2A3.

Заключение

В работе предложен «прозрачный» подход индивидуального и группового выбора ВК. Выбор ВК рассматривается как слабоструктурированная задача многокритериального стратегического выбора. Составные критерии при этом формируются индивидуально или несколькими ЛПР (экспертами) по многим числовым, символьным или вербальным критериям. Используя интерактивную процедуру снижения размерности признакового пространства, сконструированы составные критерии «Возможность модернизации» и «Сложность эксплуатации» ВК путем агрегирования более простых критериев (базовых характеристик), например технических, эксплуатационных, стоимостных и т.п. Важной особенностью процедуры является возможность сформировать разные наборы критериев, с тем, чтобы сравнить полученные результаты для разных вариантов с целью оценки качества выбора. Для индивидуального выбора ВК по составным критериям использован метод вербального анализа решений ЗАПРОС. Используя метод АРАМИС для группового упорядочивания многопризнаковых объектов, основанный на теории метрических пространств мультимножеств, были построены ранжировки ВК с использованием комбинации различных методов многокритериального выбора (ЗАПРОС, ПАРК, AHP). Подход теории мультимножеств позволяет обнаруживать, представлять и использовать доступную информацию, анализировать полученные результаты и их особенности, особенно для несогласованных многокритериальных оценок ВК и противоречивых предпочтений ЛПР.

Литература

Авен О. И. Что же такое АСУ?-- М.: Наука, 1981.-- 175 с.

Масштабируемые мультипроцессорные вычислительные системы высокой производительности / Буравлёв А., Чельдиев М., Барыбин А., Костенко В., Тумакин Д., Петрова Г. // Современные технологии автоматизации. -- 2009. -- № 3. -- С. 72-76.

Еремеев А. П. Организация параллельных вычислений на основе моделей потока данных // Известия РАН. Техническая кибернетика. -- 1993.-- № 3.-- С. 212-225.

Иванилов Е. И. Некоторые аспекты выбора серверов // Корпоративные системы. -- 2003. -- № 4.-- С. 34-36.

Климанов В. П., Сутягин М. В., Быстрикова В. А. Задачи катастрофоустойчивости кластерных вычислительных систем // Новости искусственного интеллекта.-- 2002.-- Т. 3, № 51.-- С. 22-30.

Ларичев О.И. Вербальный анализ решений / Под ред. А.Б.Петровского. -- М.: Наука, 2006.

Ларичев О. И., Мошкович Е. М. Качественные методы принятия решений.-- М.: Физматлит, 1996.-- 208 с.

Петровский А.Б. Пространства множеств и мультимножеств. - М: Едиториал УРСС, 2003.

Петровский А. Б., Ройзензон Г. В. Снижение размерности признакового пространства в задачах многокритериальной классификации: стратификация кортежей // Одиннадцатая национальная конференция по искусственному интеллекту с международным участием (КИИ-2008). Труды конференции. -- Т. 2.-- М.: Ленанд, 2008. -- С. 262-270.

Петровский А. Б., Ройзензон Г. В. Снижение размерности признакового пространства в задачах многокритериальной классификации // Decision Making and Business Intelligence Strategies and Techniques / Ed. by K. Markov, K. Ivanova, I. Mitov. -- No. 3. -- Sofia: FOI ITHEA, 2008. -- Pp. 81-86.

Петровский А. Б. Теория принятия решений. -- М.: Издательский центр «Академия», 2009.

Ройзензон Г. В. Выбор вычислительных кластеров на основе анализа количественной и качественной информации // Искусственный интеллект.-- Т. 2.-- Донецк, Украина: Наука i освiта, 2004. -- С. 375-379.

Ройзензон Г. В. Многокритериальный выбор вычислительных кластеров // Методы поддержки принятия решений: Сборник трудов Института системного анализа Российской академии наук / Под ред. С. В. Емельянова, А. Б. Петровского.-- М.: Едиториал УРСС, 2005. -- Т. 12. -- С. 68-94.

Рытиков А. М., Ройтман Е. Я., Шафрин Ю. А. Что мешает эффективному внедрению типовых АСУ? // Цветные металлы. -- 1988. -- № 1. -- С. 98-101.

Саати Т. Принятие решений. Метод анализа иерархий.-- М.: Радио и связь, 1993.-- 278 с.

Савяк В. Эффективные кластерные решения [Электронный ресурс]. -- 2002. -- Режим доступа: www.ixbt.com/cpu/clustering.shtml.

Смирнов А. В., Юсупов Р. М. Технология параллельного проектирования: основные принципы и проблемы внедрения // Автоматизация проектирования. -- 1997. -- № 2. -- С. 50-55.

Создание и применение системы высокопроизводительных вычислений на базе высокоскоростных сетевых технологий / В. Е. Фортов, Г. И. Савин, В. К. Левин и др. // Информационные технологии и вычислительные системы. -- 2002. -- № 1. -- С. 3-9.

Применение суперкомпьютеров для молекулярно-динамического моделирования процессов в конденсированных средах / Янилкин А.В., Жиляев П.А., Куксин А.Ю., Норман Г.Э., Писарев В.В., Стегайлов В.В. // Вычислительные методы и программирование. -- 2010. -- Т. 11. -- С. 111-116.

Размещено на Allbest.ru