Библиотека сайта rus-linux.net
Применение принципов оптимизации к средствам компонентного развертывания и конфигурирования систем
Глава 6 из книги "Производительность приложений с открытым исходным кодом".
Оригинал: Applying Optimization Principle Patterns to Component Deployment and Configuration Tools,
Авторы: Doug C. Schmidt, William R. Otte, and Aniruddha Gokhal
Перевод: Н.Ромоданов
Оптимизация анализа плана развертывания
Контекст
После того, как план развертывания компонент будет загружен в память, то прежде, чем будет выполнено какое-либо действие по развертыванию, план должен быть проанализирован инфраструктурой развертывания, представляющей собой средний слой. Этот анализ осуществляется на фазе подготовки плана, описанной в разделе «Процесс развертывания компонентов OMG D&C». Цель этого анализа заключается в определении (1) количества подзадач развертывания, которые являются частью плана развертывания, и (2) того, какие экземпляры компонентов относятся к каждой из подзадач.
Как уже упоминалось в разделе «Процесс развертывания компонентов OMG D&C», результат этого процесса анализа представляет собой набор «локально ограниченных» подпланов. В локально ограниченном подплане имеются все метаданные, необходимые для выполнения успешного развертывания. Таким образом в нем есть копия всей информации, которая присутствует в исходном плане (описано в разделе «Модель данных развертывания D&C»).
В действительности, анализ плана, осуществляемый во время выполнения, выполняется на фазе подготовки плана развертывания два раза: один раз на глобальном уровне и еще раз на каждом узле. Планы глобального развертывания разделяются на подпланы в соответствии с тем, на какой узел какие назначаются отдельные экземпляры компонентов. В результате этого двухэтапного анализа создается новый подплан для каждого узла, в котором содержатся только те экземпляры, соединения и другие метаданные компонентов, которые необходимы именно для данного узла.
Алгоритм разделения планов, используемый в нашей реализации DAnCE спецификации D&C, является сравнительно простым. Для каждого экземпляра, который должен быть развернут согласно плану развертывания, алгоритм определяет, в каких подпланах он должен присутствовать, и ищет (или создает новую) структуру данных для соответствующего подплана. Как только такое соответствие будет выяснено, в подплан будут скопированы все метаданные, необходимые для этого экземпляра компонента, в том числе соединения, метаданные, описывающие исполняемые модули, зависимости совместно используемых библиотек и т. д.
Проблема
Хотя такой подход концептуально прост, он чреват неожиданными сложностями, которые на практике ведут к следующей неэффективности:
- Представление ссылок в IDL. Как правило планы развертывания передаются через сети, поэтому в них должны соблюдаться правила отображения языка CORBA IDL. Поскольку в языке IDL нет никаких понятий ссылок или указателей, то для описания связи между элементами плана следует использовать некоторый альтернативный механизм. В плане развертывания все основные элементы хранятся в виде последовательности, так что ссылки на другие сущности могут быть представлены в виде простых индексов этих последовательностей. Несмотря на то, что доступ по ссылкам возможен за константное время, это также означает, что эти ссылки станут неправильными в случае, когда сущности, указываемые в плане, будут скопированы в подплан, поскольку их положение в последовательности плана развертывания, скорее всего, будет другим. Также невозможно без поиска подплана, на что затрачивается время, определить, скопирована ли сущность, на которую указывает ссылка.
- Выделение памяти в последовательности плана развертывания. Отображение в языке CORBA IDL требует, чтобы последовательность запоминалась в последовательно идущих адресах памяти. Поэтому если последовательность изменяется, то для того, чтобы разместить последовательность увеличенного размера, ее содержимое, скорее всего, будут скопировано в другое место в памяти. По мере того, как будет увеличиваться размер плана, то согласно подходу, кратко изложенному выше, возникнут значительные расходы ресурсов, связанные с копированием. Эти накладные расходы особенно проблематичны в системах с ограниченными ресурсами (например, как наш случай с SEAMONSTER), ограниченная память времени выполнения в которых должна резервироваться для компонентов приложения. Если инфраструктура развертывания неэффективна с точки зрения использования этого ресурса, то она либо потратит всю доступную память, либо будет существенной нагрузкой для любого варианта виртуальной памяти (как за счет увеличения задержки развертывания, так и за счет увеличения текущей загрузки флэш-памяти).
- Неэффективное распараллеливание при анализе плана. Казалось бы, что описанный выше алгоритм должен был бы получить существенный выигрыш благодаря распараллеливанию, т. к. процесс анализа каждого отдельного компонента и определение того, какие элементы должны быть скопированы в подплан, не зависят от всех других компонентов . Однако многопоточность этого алгоритма, скорее всего, не будет эффективной, поскольку для того, чтобы данные не были испорчены, доступ к подпланам при копировании метаданных экземпляра должен выполняться последовательно. На практике экземпляры компонентов в плане развертывания обычно группируются в соответствие с узлом и/или процессом, поскольку планы развертывания часто генерируются с помощью средств моделирования. В результате несколько потоков, скорее всего, полностью заблокируют тот же самый подплан, что вынудит «распаралелленный» алгоритм работать в значительной степени последовательно. Несмотря на то, что исторически распараллеливание рассматривалось как неприменимое к системам DRE с ограниченными ресурсами (например, SEAMONSTER), появление многоядерных процессоров в одноплатных компьютерах побуждает в этих средах внедрять распараллеливание в большей степени.
Принципы оптимизации, используемые при анализе плана развертывания
Эту проблему с производительностью потенциально можно решить с помощью применения принципа Specification vs Implementation (Спецификация или реализация), а также применение тех же самых принципов оптимизации, которые были описаны ранее для компилятора XSC, в частности принципа, согласно которому нужно знать стоимость ваших абстракций, и использовать абстракции, подходящие для вашей конкретной ситуации. Например, при обращении к связанным структурам данных можно вместо последовательно идущих индексов использовать указатели/ссылки, что потенциально устранит необходимость аккуратно перезаписывать ссылки, когда сущности плана будут копироваться из одного плана в другой. Точно также объекты плана можно хранить в ассоциативном контейнере (например, в структуре map библиотеки STL), а не в в виде последовательности, тем самым увеличивая эффективность вставки сущностей плана в подпланы.
Хотя эти и другие подобные возможности выглядят заманчиво, есть некоторая сложность, присущая требованиям стандарта D&C, которая делает такие оптимизации менее привлекательными. Поскольку эти данные, как часть процесса развертывания, должны передаваться в другие сущности, использование более эффективного представления при анализе добавит в процесс развертывания еще один шаг преобразования. Это преобразование потенциально может свести на нет любые выгоды, полученные с помощью такого нового представления.
Более привлекательный результат достигается применением для решения этой проблемы другого набора принципов оптимизации, которые изложены ниже:
- Кэширование заранее вычисленных результатов для их последующего использования. Этот принцип является примером использования принципов Shifting in Time (Сдвиг операций по времени) и Exploiting State (Использование состояний). Можно выполнить простой шаг предварительного анализа, предварительно рассчитав значения, на которые будет затрачиваться много времени, когда они будут выполняться позже. В этом случае при повторном проходе по плану сначала определите окончательный размеры памяти, в которой будут находится рассчитанные подпланы, и закэшируйте это состояние для последующего использования.
- По возможности предварительно выделяйте память под любые структуры данных. В результате использования дополнительных состояний, полученных на шаге предварительного анализа, описанного выше, мы можем применить принцип Avoiding Waste (Избегайте излишних затрат) и избежать ненужных потерь за счет предварительного определения последовательности обработки, которую ранее нужно было переопределять каждый раз, когда обнаруживался новый элемент плана.
- Создавайте свои алгоритмы так, чтобы можно было пользоваться преимуществом распараллеливания. Хотя этот подход можно рассматривать как применение принципа Adding Hardware (Добавление аппаратных возможностей), согласно этому принципу можно от аппаратных средств получить гораздо больше, например, за счет влияния размера слова на эффект кэширования. Кроме того, согласно этому принципу для выполнения специализированных вычислений нужно пользоваться устройствами специального назначения.
Получение преимуществ от использования нескольких процессоров общего назначения является наиболее важным принципом, выходящим на первое место. Т.к. многоядерные компьютеры получили широкое распространение среди настольных и серверных систем, и становятся все более распространенными даже среди встроенных систем, все более значимой становится разработка приложений с учетом этой важной особенности аппаратного обеспечения. Поэтому мы предлагаем дополнительный принцип
Design for Parallelization(Разработка с учетом распараллеливания), в котором мы рассматриваем оптимизацию алгоритмов и интерфейсов для распараллеливания. - Обеспечьте совместный доступ к структурам с общими данными для того, чтобы не использовать синхронизацию. Синхронизация, например, с использованием мьютексов для защиты доступа к общим данным, является сложной в использовании и чревата ошибками. Кроме того, чрезмерное использование синхронизации часто может полностью свести на нет все преимущества от распараллеливания ваших алгоритмов. Гораздо более предпочтительным подходом является изменение ваших алгоритмов таким образом, чтобы целиком устранить необходимость синхронизации; для доступа к данным потребуется только общая команда read вместо общего доступа на запись write.
Этот принцип оптимизации является не только важным дополнением к принципу Design for Parallelization (Разработка с учетом распараллеливания), предложенному выше, но это также общий практический принцип программирования: взаимные блокировки и состояния гонок, вызванные неправильной синхронизацией, являются опасными и трудно диагностируемыми ошибками. Действительно, в нашей недавней работе по разработке фреймворков для модульного космического корабля была предложена компонентная модель, в рамках которой из исходного кода приложения была полностью исключена синхронизация [33]. Для этого мы предлагаем пользоваться другим принципом оптимизации, который мы называем Avoid Synchronization (Отказ от синхронизации), согласно которому следует избегать лишний раз пользоваться синхронизацией и блокировками, о чем будет рассказано ниже.
Эти принципы можно применить к алгоритму, описанному выше, и создать версию, которая будет намного более пригодна для оптимизации; ниже описан новый алгоритм (вместе с замечаниями, касающимися влияния описанных выше принципов на выбираемые решения).
- Фаза 1: Определяем количества подпланов, которые требуется создавать. На этой фазе один поток управления проходит по всем экземплярам компонентов, которые есть в плане развертывания, с тем, чтобы определить количество необходимых подпланов. Когда эта операция выполняется на глобальном уровне, то для каждого экземпляра просто требуется константное время. Когда она выполняется на локальном уровне, то требуется соблюдать локальные ограничения (описано в разделе «Модель данных развертывания D&C»). Поскольку потенциально для этой фазы нужно много времени, ее результаты будут закэшированы для последующего использования. Это пример принципов Shifting in Time (Сдвиг операций по времени) и Exploiting State (Использование состояний).
- Фаза 2: Предварительно выделяем структуры данных для подпланов. Используя информацию, полученную на фазе 1, которая была описана выше, заранее выделяем структуры данных, необходимые для сборки подпланов.Чтобы избежать повторного изменения размеров и копирований, можно во время этого предварительного выделения структур зарезервировать память для любой последовательности, имеющейся в структуре данных подплана. Чтобы длины последовательностей задавались эффективно, на фазе 1 собираются статистические данные. Это пример применения принципа Avoiding Waste (Избегайте излишних затрат).
- Фаза 3: Собираем подпланы для конкретных узлов. Эта фаза процесса нового анализа аналогична алгоритму, описанному в начале этого раздела. Главное отличие в том, что для создания подпланов используются кэшированные результаты фазы предварительного анализа. Вместо того, чтобы последовательно рассматривать каждый экземпляр (так, как это сделано в исходной реализации движка DAnCE), в LE-DAnCE для каждого узла сразу создается подплан и сразу обрабатывая все экземпляры, относящиеся к этому узлу. Такой подход упрощает распараллеливание этой фазы за счет того, что для каждого подплана выделяется отдельный поток и разным потокам нет необходимости обращаться к общим данным, за исключением лишь чтения первоначального плана развертывания. Поэтому нет необходимости использовать какие-либо механизмы блокировки для защиты доступа к подпланам. Это пример применения принципов Design for Parallelization (Разработка с учетом распараллеливания) и Avoid Synchronization (Отказ от синхронизации).
Пересмотренный алгоритм, описанный выше, является гораздо более эффективной реализацией анализа плана, и может показать гораздо лучшие характеристики даже для случая одноядерных встраиваемых процессоров, что было типичным в случае платформы SEAMONSTER: описанный выше алгоритм по памяти гораздо эффективнее, причем как по объему используемой памяти, так и по количеству необходимой повторно выделяемой памяти. Использование многоядерных встроенных процессоров должно в сравнении со старым алгоритмом существенно повысить производительность времени выполнения.
Продолжение статьи: Оптимизация за счет сокращения числа последовательно выполняемых задач при развертывании приложений.