Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов




Скачать 389.32 Kb.
НазваниеМатематико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов
страница5/6
Дата17.04.2013
Размер389.32 Kb.
ТипЗадача
1   2   3   4   5   6

Метод адаптивной балансировки1


В этом разделе излагается решение методами стохастической аппроксимации типичной для распределенных вычислений задачи балансировки загрузки. Применимость предлагаемого подхода растет с числом параллельных вычислителей, как будет видно из обоснований предложенного ниже алгоритма. Таким образом, не только постановка задачи, но и сам метод решения дают право говорить об актуальности подхода для GRID-вычислений. Современные исследователи считают очень важным при определении GRID понятие виртуальной организации. «Виртуальной организацией GRID называется сообщество пользователей GRID с динамически меняющимся составом, необходимое для совместного использования … ресурсов в рамках общих задач»[38]. GRID – это «согласованная, открытая и стандартизованная среда, обеспечивающая гибкое, безопасное, раздельное использование разнообразных компьютерных ресурсов виртуальными организациями»[38].

Широкое внедрение GRID-систем для научных вычислений в последнее время привело к быстрому росту числа компьютеров, включенных в активно развивающиеся GRID, например для EGEE это 20 000, для Nordugrid 6000 процессоров [38].

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

Для выполнения в GRID характерны программы со слабой связью по данным и управлению между выполняющимися параллельно участками кода. В этой работе рассматривается случай Single Program Multi Data (SPMD) вычислений. SPMD – это тип параллельных программ, для которых характерно выполнение одного и того же программного кода на разных фрагментах данных (параллелизм по данным).

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

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

Отправка заданий осуществляется через клиентский интерфейс. Затем задание поступает на брокер, который выделяет ресурсы для выполнения. После этого задание вместе с необходимыми данными передается на рабочий узел (отдельный компьютер или кластер) и выполняется.

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

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

Таким образом, вычисление SPMD-задания в GRID начинается с распределения атомарных заданий между рабочими узлами. Затем на каждом из рабочих узлов запускается процесс, обрабатывающий атомарные задания. В тот момент, когда задания на рабочем узле заканчиваются, процесс переходит в режим ожидания до тех пор, пока не получит новых заданий либо сигнала о завершении работы.

Далее уделим внимание задаче балансировки наборов атомарных заданий на рабочих узлах.

Задача балансировки


Пусть имеется r рабочих узлов, общее число атомарных заданий W >> r. Между узлами изначально распределены атомарные задачи, на i-м узле Wi(0) заданий. Пусть, далее, задан временной интервал такой, что каждые секунд инициируется процесс балансировки. Распределение невыполненных заданий между рабочими узлами в момент t: k (k+1) задается вектором Wi(k). Общее число невыполненных заданий обозначим как W(k)= i Wi(k).

Будем считать, что с использованием средств мониторинга GRID есть возможность определить текущее распределение выполненных и не выполненных заданий на рабочих узлах. Обозначим число выполненных заданий на i-м рабочем узле в момент t как Wi(t), Wi(0) =0, Wi(t) Wi(t-1) для k≥1. Пусть имеется возможность выполнения высокоуровневой процедуры с векторным параметром по переносу невыполненных заданий так, чтобы в итоге они оказались распределены в пропорции, так что. Такая операция может быть оптимизирована с целью минимизации времени переноса заданий, что выходит за рамки основной задачи балансировки.

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

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

.

Алгоритм балансировки


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

Вводя в рассмотрение величину pi как производительность (число обрабатываемых заданий за определенный промежуток времени) i-го рабочего узла, мы можем проанализировать предлагаемый ниже алгоритм и обосновать его сходимость для данной задачи.

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



Алгоритмы такого вида подробно рассмотрены в [6]. Определим особенности его применения для решения описанной задачи балансировки в GRID, а затем определим условия на используемую последовательность εnR.

Величина yi(k) с использованием pi выражается как:, где vi является величиной отклонения фактической производительности узла от его средней производительности на временном интервале (0, k). Эта величина является случайной, предположим, что в среднем она равна 0 для всех i. Разделив на r числитель и знаменатель выражения, приходим к формуле




что верно в силу усиленного закона больших чисел для достаточно больших r.

Используя полученные выражения, получим следующее выражение для разности



Для последнего слагаемого, используя оценку для y(k)i, полученную выше, выводим . Вслед за [6] введем обозначение .

Естественно предположить независимость vi от vi-1,…,v1, называя , вслед за [6], мартингальными разностями:. Использование этого дополнительного предположения обосновывает постепенное исчезание слагаемых вида : при выборе малого d, такого что получается




где дисперсия отклонения будет выражаться как O(d)εn. Представленные выражения обосновывают, что изменение параметра в сторону оптимального значения для больших n и малых d много более значительны, чем отклонения. Тогда можно сделать вывод, что асимптотическое поведение алгоритма может быть аппроксимировано асимптотикой решения обыкновенного дифференциального уравнения



В [6] для сходимости алгоритма предлагаются условия



Реализация предложенного алгоритма опирается на использование алгоритма стохастической оптимизации из семейства методов, подробно описанных в [6]. Рассмотрим модель описанного алгоритма. Здесь активно участвует как инициатор элемент delay. В то же время, если RecService работает с GRID как с внешней системой, delay может быть исключен из компонентов модели сервиса и рассмотрен как часть GRID-контейнера.

Рис. 3

Метод подстройки пользовательских приоритетов при поиске по коллекциям изображений2


Информационный поиск является хорошо известной задачей современной информатики. Методы поиска хорошо разработаны для текстовой информации, в то время как поиск по более сложно организованной информации не имеет устоявшихся классических подходов. Последнее утверждение косвенно подтверждается в [39]: авторы статьи выражают неуверенность по поводу введения единой метрики для поиска по коллекции неаннотированных текстовыми метками изображений, обосновывая это тем, что поиск подходящего изображения сложно представить в виде уменьшения некоего расстояния. Ставятся под сомнение рефлексивность (зачем искать то, что и так имеется), симметричность (если A хочется найти при подаче запроса B, не факт, что хочется найти B при запросе A), и, тем более, неравенство треугольника.

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

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

Задача подстройки приоритетов


Пусть заданы N пространств , каждому из которых соответствует класс характеристик изображения. Так, одно пространство соответствует характеристикам цвета, другое - формы, третье - текстуры и пр. На каждом из пространств задана своя метрика , где , отражающая объективную схожесть двух изображений на основе характеристик пространства с номером i, и , - объединенные вектора характеристик изображения во всех пространствах. Метрике однозначно соответствует метод поиска по i-му пространству. Метрика пространства удовлетворяет в полной мере определению метрики (3 свойства). Она не обязательно является евклидовой.

Для поиска в базе данных изображений пользователь предоставляет изображение-запрос (q). На основании образца производится поиск. Механизм поиска может быть итеративным, на каждом шаге выявляя новую информацию о желании пользователя и корректируя результаты с ее учетом.

Пусть поиск производится на основе общей функции схожести, или суммарной оценки схожести, определяющей для каждого изображения его схожесть с тем, что хочет получить пользователь. Требуется построить такую функцию суммарной оценки от изображения x и пользовательского запроса q, что она определяет наиболее подходящие пользователю изображения. Ограничений на функцию σ не так много. Исходя из общих соображений, при равных координатах во всех пространствах, кроме одного, близость изображений в этом пространстве должна определять итоговую их близость, то есть должна соблюдаться монотонность функции σ по отношению к метрикам пространств.

Пусть есть возможность разделить изображения на непересекающиеся категории. Будем предполагать, что внутри каждой категории существует некая наилучшая суммарная оценка, которую и призвана определить система поиска. Иными словами, считаем приоритеты пользователя постоянными для запросов определенной категории. За рамками пока остается вопрос наилучшего разделения на категории множества всех возможных изображений, принадлежащих декартову произведению имеющихся пространств . Это может быть сделано известными методами кластеризации, см., напр., [40]. Каким образом выражается в таком случае суммарная оценка?

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

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

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

Первой подзадачей этой общей задачи является создание модели представления приоритетов в виде суммарной оценки.

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

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

Адаптивный метод рандомизированных сводных показателей


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

Н.И. Хованов [41] предлагает использовать метод, названный им Методом рандомизированных сводных показателей для решения данной задачи. Метод основан на построении большого числа случайных примеров и принятии среднего значения показателя по этим примерам как искомой суммарной оценки. В данном случае, предлагается ввести коэффициенты αi, выражающие вес (значимость) метрики ρi в суммарной оценке. Из указанные величин составлены векторы α и ρ(q,x). Кроме того, для масштабирования шкал друг относительно друга следует также ввести коэффициенты , которых нет в исходном методе рандомизированных показателей потому, что показатели берутся из отрезка [0,1]. На основе введенных величин составляются помеченные упорядоченными парами (i,j) неравенства вида



выражающие приоритеты. С помощью αi можно получить скалярный показатель



где символ ‘’ обозначает скалярное произведение. Далеко не единственный набор коэффициентов {αi} удовлетворяет указанным неравенствам. Предлагается провести опыты по расчету показателя : будут сгенерированы случайные наборы α(k) с равномерным распределением на интервале U(0,1), отброшены те из них, что не удовлетворяют неравенствам, а затем суммарная оценка будет положена равной среднему значению показателя для всех векторов показателей. Таким образом, если некоторый эксперт (или сам пользователь) перед началом поиска задал приоритеты, то с их использованием можно получить результат поиска. Подстройку sij следует производить однажды алгоритмом типа стохастической аппроксимации на основании наблюдений за реакцией пользователей. Однажды нормированные с помощью корректно настроенных sij, шкалы остаются далее неизменными друг относительно друга.

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

Схема подстройки приоритетов задается с помощью введения параметров важности учета приоритета для каждой пары пространств. Параметр важности в вычислительной схеме может интерпретироваться как вероятность применения неравенства. Отсюда можно выявлять новые приоритеты, в явном виде пользователем не обозначенные, корректировать важность применения имеющихся приоритетов, если они противоречат соотношениям между фактически выделенными пользователем изображениями. Предлагается использовать вероятностный параметр , определяющий вероятность того, что ограничение (i,j) будет проверено для очередного сгенерированного набора α(k). Корректировку параметра можно производить после каждого шага работы с пользователем по следующей схеме:



Здесь - значение параметра на шаге n, Nij+ - число изображений, для которых данный приоритет соблюден, среди всех помеченных (как подходящие) изображений, Nseld - число всех помеченных изображений, - дисконтирующий коэффициент. Для упрощения понимания схемы можно принять условие , однако это не обязательно: можно считать, что одновременная проверка противоречащих неравенств будет означать отсутствие ограничения.

Данная вероятностная схема позволяет динамически подстраивать приоритеты, доверять различным приоритетам по-разному, постепенно избавляться от учета приоритетов, потерявших свою актуальность.

Метод, названный нами «Адаптивным методом рандомизированных сводных показателей», по природе итеративный и соответствует общей направленности реализуемых в RecService алгоритмов. Рассмотрим модель алгоритма в терминах RecService. Для краткости ограничимся наглядной схемой с отмеченными задачами, компонентами и типами передаваемых между ними данных, а также направлениями этих связей (рис. 4).

Рис. 4
1   2   3   4   5   6

Похожие:

Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconПетербургский Государственный Университет Математико-Механический Факультет Кафедра Системного Программирования
Сравнение различных методов хранения xml в реляционных базах данных и в разных системах
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования «Мультиагентные платформы и их применение в сетевых задачах»
Мас концентрируют все необходимые для таких технологий свойства с наибольшей выразительностью и полнотой. Результаты внедрения агентных...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Генерация веб-сервисов C#. net на основе bpel
Задача кодогенерации веб-сервисов возникла в рамках проекта «К700». «К700» — это проект создания рабочих мест оператора и инженера...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Поддержка структурных изменений в процессах загрузки данных
Исследование необходимости поддержки структурных изменений в источниках данных 35
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Разработка системы сравнения производительности субд
Существует большое количество разнообразных субд (Система управления базами данных), предназначенных для разных задач, однако обычно...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Разработка jre на ecma cli
Виртуальная машина, включая сборщик мусора и jit компилятор, является наиболее крупным монолитным компонентом среды управляемого...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет Кафедра системного программирования Создание режима быстрого прототипирования в case-системе qreal
Использование различных видов диаграмм и сущностей позволяет пользователям наглядно и подробно описать необходимые модули и поведение...
Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет

Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет

Математико-механический факультет Кафедра системного программирования Сервис для моделей оптимизации на основе рекуррентных алгоритмов iconМатематико-механический факультет

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница