Содержание к диссертации
Введение
ГЛАВА 1. Workflow-методология: обзор основных понятий, подходов и технологий 13
1.1 Workflow-методология. Основные понятия и стандарты 13
1.1.1. Основные понятия 13
1.1.2 Производственные и научные сценарии 14
1.1.3 Стандарты в области систем управления сценариями 17
1.2 Способы описания сценариев 19
1.2.1 Скриптовые языки 19
1.2.2 Представление сііенариев в виде графов 19
1.2.3 Смешанные подходы 21
1.2.4 Модели, ориентированные на потоки данных 22
1.3 Обзор существующих workflow-систем 22
1.3.1 GridAnt 22
1.3.2 Karajan 23
1.3.3 Condor DAGMan 24
1.3.4 jFern 26
1.3.5 Petri Net Kernel 29
1.3.6 Renew 30
1.3.7 YAWL 31
1.3.8 eXeGrid 32
1.3.9 Business Process Execution Language for Web Services 34
1.3.10 jOpera 37
1.3.11 jBPM 35
1.3.12 Triana 41
1.3.13 Kepler 44
1.3.14 Taverna 45
1.3.15 Yahoo! Pipes 47
1.4 Обзор научных приложений workflow-методологии 48
1.4.1 Проект EMBRACE 49
1.4.2 Проект MlASGrid. 51
1.4.3 Анализ бактерий сибирской язвы 52
1.4.4 Измерение характеристик ферментов у дрожжей 53
1.5 Задачи работы 54
ГЛАВА 2. Принципы построения службы управления сценариями для распределенных вычислительных сред 56
2.1 Сервис-ориентированная архитектура 56
2.1.1 Концепция SOA 56
2.1.2 Ачгоритмические сервисы 57
2.1.3 Базовые технологии SOA 58
2.2 Функциональность службы управления сценариями 60
2.3 Архитектура службы управления сценариями 61
2.4 Жизненный цикл сценария 62
2.4.1 Развертывание сценария 63
2.4.2 Запуск сценария на выполнение 63
2.4.3 Получение результатов и контроль состояния выполнения сценария 63
2.5 Требования к реализации службы управления сценариями 63
ГЛАВА 3. Реализации службы управления сценариями 66
3.1 Реализация распределенного вычислительного сценария на языке BPEL 66
3.1.1 Общие соображения
3.1.2 Схема распределенного решения системы обыкновенных дифференциальных уравнений 67
3.1.3 Перенос алгоритма на BPEL 68
3.1.4 Схема физической реализации тестового прототипа 69
3.1.5 Ход эксперимента 70
3.1.6 Выводы 72
3.2 Реализация прототипа сус iarnet на основе формализма сетей петри 72
3.2.1 Реализация прототипа СУС IARnet 73
3.2.2 Тестирование прототипа СУС IARnet 75
3.2.3 Результаты вычислительных экспериментов 78
3.2.4 Измерения пропускной способности СУС 7Р
3.2.5 Выводы 82
3.3 Текущая реализация СУС 82
3.3.1 Архитектура системы 83
3.3.2 Редактор сценариев 84
3.3.3 Сервис управления сценариями 98
3.3.4 Среда выполнения сценариев 99
ГЛАВА 4. Применение службы управления сценариями для решения прикладных задач 102
4.1 Графическая среда для работы с трехмерными моделями на основе пакета antiprism 102
4.2 Моделирование железнодорожных перевозок 111
4.3 Распределенный алгоритм безошибочного обращения плохо обусловленных матриц большой размерности 114
Заключение 120
Список литературы 121q
- Стандарты в области систем управления сценариями
- Business Process Execution Language for Web Services
- Функциональность службы управления сценариями
- Распределенный алгоритм безошибочного обращения плохо обусловленных матриц большой размерности
Стандарты в области систем управления сценариями
Срабатыванием переходов описывается выполнение любого действия в системе; такое срабатывание порождает новое размещение фишек в сети. Благодаря фишкам, сети Петри, в отличие от ориентированных ациклических графов, позволяют описывать не только поведение процесса, но и наглядно представлять его состояние в ходе вьшолнения сценария.
В терминах сетей Петри сценарии задаются довольно прямолинейно: участники сценария моделируются переходами, условия (при выполнении которых задания передаются тому или иному участнику) - предписаниями (условиями срабатывания) переходов, а сами задания - фишками. Сценарий, описанный при помощи сети Петри, задается строго и точно, потому что семантика классических сетей Петри, как и некоторых дополнений к ним (двет, время, иерархия) введены формально. Сети Петри поддерживают все базисные логические элементы, необходимые для описания сценария. С их помощью могут быть смоделированы все управляющие конструкции, существующие в современных системах управления сценариями. Кроме того, сети Петри отличаются наличием формальных методов анализа. Это их ценное преимущество с точки зрения использования для описания сценариев.
Кроме систем, представляющих сценарии в чистом виде при помощи скриптовых языков или в виде графов, существуют разработки, в которых сделана попытка синтеза двух этих подходов. В таких разработках в разной степени присутствуют элементы и того, и другого подхода. Пример такого смешанного языка - BPEL [35], созданный на основе использующего графовое представление языка WSFL, прежде разрабатываемого IBM, и обладающего элементами языков структурного программирования язьжа XLANG, создаваемого Microsoft.
Также в качестве примеров смешанного подхода к представлению сценариев можно привести программные пакеты, способных наряду с графовым описанием поддерживать реализацию отдельных частей сценария в виде программ, реализованных на том или ином языке программирования или отрывков программного кода, встраиваемых непосредственно в сценарий. Из соображений переносимости и кроссплатформенности, среди таких пакетов нас более всего будут интересовать те, что используют для этих целей язык Java. Наиболее яркими примерами такого подхода на наш взгляд являются пакеты jOpera [58] и jBPM [57]. 1.2.4 Модели, ориентированные на потоки данных
Помимо уже упомянутых выше методов описания сценариев, существует еще один подход, в котором для представления сценариев могут использоваться как скриптовые языки, так и графы, но который несколько отличается от обсуждавшихся ранее подходов своей спецификой.
Речь идет о системах управления научными вычислительными сценариями, ориентированными на потоки данных. Часто в научных приложениях все необходимые действия сводятся к различным операциям над данными, то есть в подобных процессах потоки управления и потоки данных совпадают. Поэтому во многих случаях нет необходимости вводить специальные элементы языка для описания логических конструкций, а достаточно только обеспечить средства объединения элементарных модулей обработки данных в сеть. В таких моделях каждый модуль имеет один или несколько входов и выходов, дуги графа соответствуют соединениям выхода одного модуля с входом другого, по которым осуществляется передача данных между модулями. Как только на вход модуля поступили все необходимые данные, происходит запуск программного кода модуля, который производит обработку входных данных, после чего полученные результаты (выходные данные) поступают на выходы модуля и передаются по соединениям на вход других модулей.
Систем, обеспечивающих описанную функциональность, довольно много: Triana [83], Kepler [61], Discovery Net [40], SCIRun [74], Scitegic Pipeline Pilot [75], Taverna [81]. Но все эти системы довольно схожи как по своим возможностям, так и по принципам, использованным в них. Поэтому ниже будут обсуждены подробно только некоторые из этих пакетов. Для того, чтобы проиллюстрировать использование упомянутых выше способов описания сценариев в различных программных системах, составить представление о текущей ситуации в сфере СУС, а также оценить существующие системы на предмет возможности их использования в качестве основы разрабатываемой СУС для распределенных вычислений, был проведен обзор ряда наиболее характерных из существующих на настоящий момент программных пакетов для работы со сценариями, а также формализмов описания сценариев, предлагаемых авторами этих пакетов.
В качестве примера успешного использования скриптового языка для конструирования сценариев стоит упомянуть систему GridAnt [51], модификацию Apache Ant [31] (популярного средства автоматической сборки и интеграции Java-кода), разработанную для автоматизации процессов Grid-вычислений.
GridAnt — это программный инструмент, основанный на языках Java и XML, состоящий из интерпретатора и набора визуальных компонентов, которые обеспечивают динамическое отображение хода выполнения заданий. GridAnt является расширением Apache Ant и обладает полной обратной совместимостью с ним.
GridAnt был разработан для использования в рамках Grid-среды [3] на основе ПО Globus Toolkit 2 и 3 [48] и поэтому наследует особенности работы с ресурсами в рамках подобных сред. В частности, работа с вычислительными ресурсами сводится к набору элементарных шагов сценария, соответствующих низкоуровневым операциям с файлами: копирование файлов с одной машины на другую, запуск исполняемых файлов на удаленных машинах, создание файла, содержащего результаты выполнения исполняемого файла, и т.д. GridAnt обеспечивает функциональность, которая обычно требуется программам для распределенных Grid-вычислений [3], то есть: безопасную передачу файлов, запуск заданий на удаленных вычислительных ресурсах и просмотр результатов их выполнения.
Запуск скрипта, содержащего описание сценария, производится при помощи специальной программной оболочки вокруг стандартного интерпретатора Apache Ant, которая позволяет следить за потоками данных, выполнять асинхронные вызовы (без ожидания), обработку исключительных ситуаций и ошибок. Файловый монитор предоставляет информацию о новых файлах или их новых версиях.
Business Process Execution Language for Web Services
Использование сервис-ориентированной архитектуры является основополагающим принципом реализации СУС для распределенных вычислительных сред. Поэтому представляется целесообразным подробно рассмотреть основные понятия, относящиеся к данной области.
Сервис-ориентированная архитектура (англ. SOA, service-oriented architecture) — модульный подход к разработке программного обеспечения, где в качестве модулей выступают сервисы (службы) со стандартизованными интерфейсами.
Наиболее точным представляется следующее определение сервиса: - это законченный функциональный компонент, многократно используемый в различных процессах [12]. SOA также может рассматриваться как стиль архитектуры информационных систем, который позволяет создавать приложения, построенные путём комбинации слабосвязанных и взаимодействующих сервисов. Эти сервисы взаимодействуют на основе некоторого строго определённого платформенно-независимого и языково-независимого интерфейса.
Суть концепции SOA заключается в стандартизации автоматизации различных процессов при помощи многократного использования типовых компонентов — сервисов. В основе SOA лежит идея ликвидации дублирования функциональности в ПО и унификации типовых процессов. Таким образом, чем больше сервисов будет доступно в рамках какой-либо архитектуры, тем быстрее и проще будет происходить в ней внедрение новых автоматизированных процессов и оптимизация уже существующих.
Компоненты программы, разработанной согласно принципам SOA, могут быть распределены по разным узлам сети, и быть доступны пользователям в качестве независимых, слабо связанных, заменяемых приложений. Подобные программные системы, разработанные в соответствии с SOA, часто представляют собой набор сервисов, интегрированных при помощи известных стандартных протоколов (например, архитектуры SOAP [76], WSDL [87], REST [42] и т. п.).
Интерфейс компонентов SOA-программы скрывает детали реализации конкретного компонента (операционной системы, платформы, языка программирования, производителя, и т. п.) от пользователей. Таким образом, SOA предоставляет гибкий способ комбинирования и многократного использования компонентов для построения сложных распределённых программных систем.
В наиболее общем виде внутренняя активность такой системы сводится к взаимодействию трех основных компонентов: поставщика сервиса, потребителя сервиса и реестра сервисов. Взаимодействие компонентов реализуется следующим образом: поставщик сервиса помещает информацию о своих сервисах в реестр, а потребитель обращается к реестру с запросом. Потребитель сервиса для нахождения описания сервиса может напрямую использовать универсальный идентификатор ресурса (URI) или же может найти описание сервиса в реестре, с последующей привязкой и вызовом сервиса.
Архитектурный стиль, определяющий SOA, содержит набор параметров и рекомендаций для создания слабосвязанных проблемно-ориентированных сервисов. Главное, что отличает SOA, это использование независимых программных компонентов, с чётко определёнными интерфейсами, которые, для реализации необходимой функциональности, могут быть вызваны некоторым стандартным способом. Важно отметить, что при этом сервисы изначально не имеют никакой информации о приложении, которое их вызывает, а приложение не имеет информации о внутренних деталях реализации сервисов.
В частности, для объединения таких программно-независимых распределенных компонентов в приложения может использоваться методология сценариев. В случае с распределенными вычислительными сценариями такими компонентами могут являться т.н. алгоритмические сервисы, предназначенные для решения научных и прикладных вычислительных задач.
Алгоритмический сервис [25] представляет собой доступный по сети программный компонент, поддерживающий решение определенного класса задач с помощью соответствующих вычислительных алгоритмов. В соответствии с моделью клиент-сервер, сервис обслуживает приходящие к нему запросы клиентов на решение конкретных задач. Запрос клиента содержит параметризованное описание задачи, формулируемое в виде конечного набора входных параметров. После успешной обработки запроса сервис возвращает клиенту результат, оформленный в виде конечного набора выходных параметров.
Такими клиентами, в частности, могут являться служба управления сценариями а через неё и сами распределенные приложения, созданные при её помощи и, в свою очередь, реализованные в виде сервисов.
Для взаимодействия с сервисом клиенту необходимо знать список входных и выходных параметров сервиса. Данная информация является частью описания сервиса, публикуемого в общедоступном месте или предоставляемого сервисом по запросу клиента. Описание параметров сервиса определяет форматы сообщений (контракт), которым должны следовать клиент и сервис. Данное описание должно поддерживать машинную интерпретацию, например для валидации сообщений, генерации клиентского кода или динамических вызовов.
Приведенное выше описание модели является общим для большого класса сервисов, таких как сервисы доступа к базам данных или сервисы, осуществляющие обработку и преобразование данных. Поэтому рассмотрим особенности, возникающие при работе с именно с алгоритмическими сервисами.
Во-первых, каждый запрос обрабатывается сервисом независимо от других запросов. Иными словами, результат запроса определяется исключительно значениями передаваемых клиентом входных параметров и не зависит от результатов других запросов. Данная особенность играет роль ограничения, накладываемого на рассматриваемые сервисы.
А именно, за рамками описываемой модели сервиса остаются клиент-серверные приложения, в которых требуется поддерживать состояние (сессию) между последовательными запросами клиента к серверу. Примером такого приложения может являться удаленная работа в интерактивном режиме с пакетом MATLAB, когда пользователь передает пакету команды, которые используют уже хранящиеся на сервере результаты предыдущих команд. Исключение подобных случаев позволяет существенно упростить интерфейс и реализацию сервисов, а главное, повысить масштабируемость и отказоустойчивость приложений в целом. Отметим, что данное ограничение часто накладывается на сервисы той или иной сервис-ориентированной архитектуры.
Вторая важная особенность алгоритмических сервисов заключается в том, что обработка запросов клиентов (решение задач) часто сопряжена с проведением длительных вычислений и может сопровождаться запуском вычислительных заданий на многопроцессорных вычислительных комплексах и в Grid. В этом случае сервис не может сразу вернуть клиенту ответ на его запрос, и обработка подобных запросов должна вестись в асинхронном режиме. В ответ на вызов клиенту может возвращаться идентификатор запроса, используя который, клиент может опрашивать статус запроса (т.н. режим pull) и получить готовый результат. Клиент также может получать от сервиса уведомления об изменении статуса его запроса (режим push). Стоит отметить, что поддержка асинхронной обработки запросов неизбежно приводит к появлению внутреннего состояния на стороне сервиса в следствие того, что запрос и получение его результата реализуется в виде нескольких вызовов сервиса. Однако данное состояние существует исключительно в контексте одного конкретного запроса к сервису.
Функциональность службы управления сценариями
Пусть интегрирование каждого из этих уравнений производится отдельным ресурсом, который представляет собой «обычную» (не распределенную) реализацию какого-нибудь метода решения задачи Коши (например, метода Эйлера). Для краткости, в дальнейшем будем обозначать эти ресурсы R1 и R2.
Перед началом вычислений эти два ресурса обмениваются «прогнозными» (экстраполирующими) траекториями «своих» переменных, аппроксимирующими неизвестную пока траекторию х(0 ( »( j(0}. Пусть прогнозом изменения первой переменной является функция Pi (0, а второй - А (О. Располагая этими функциями, каждый из вычислительных ресурсов независимо от другого может решить приближенное уравнение со «старыми» начальными условиями, отличающееся от точного тем, что в правой части вместо точных значений «чужих» переменных стоят их прогнозные значения. Результатом будут две аппроксимирующие траектории si (О и & (О.
Ясно, что при этом возникнет ошибка, которая будет возрастать с ростом времени /. Каждый ресурс следит за отклонением своей компоненты аппроксимирующей траектории от прогноза, который был отослан другому ресурсу. Для определенности пусть это отклонение превысило пороговое значение у ресурса. R1. И пусть это произошло в момент времени h. .Тогда ресурс R1 должен: оповестить ресурс R2, что вычисления следует приостановить, пока не будут получены обновленные значения прогноза; уточнить прогноз своих переменных "і на промежутке [ ,Т]; послать ресурсу R2 новый прогноз. Получив обновленные данные, ресурс R2 сформирует и начнет решать на промежутке [{i,T] новую задачу Копій, заменив в своем аппроксимирующем уравнении старый «чужой» прогноз на новый. Начальные условия в новой задаче соответствуют непрерывному продолжению ранее полученного решения.
Важно заметить, что в момент времени h пороговое ограничение у ресурса R2, вообще говоря, не нарушается, и необходимость в построении им нового прогноза Рг\0 и пересылки его ресурсу R1 в этот момент отсутствует. Поэтому первый ресурс, не останавливаясь, продолжает интегрировать свое «текущее» аппроксимирующее уравнение. Если первым будет превышено пороговое значение погрешности прогноза у второго ресурса, он должен будет вести себя аналогично. Далее все повторится. В конечном итоге, в процессе работы алгоритма каждый ресурс сформирует «свою» компоненту кусочно-гладкой аппроксимирующей функции 4(0 (і(0»&(0), приближающей точное решение Алгоритм очевидным образом обобщается на случай более двух групп уравнений, решаемых совместно.
Рассмотренный алгоритм интересен тем, что для его реализации необходимо обеспечить синхронизацию работы ресурсов, например, при помощи службы рассылки сообщений. Та же служба может рассылать и обновленные значения прогнозов.
Типизация интерфейса соответствующего агента доступа потребует, прежде всего, сузить типы рассылаемых прогнозов, поскольку затруднительно реализовать процедуру обмена произвольными непрерывными функциями. Однако если ограничиться, например, только линейными или квадратичными прогнозами, то задача пересылки данных легко решается, так как для этого достаточно передавать конечный набор коэффициентов соответствующих зависимостей.
Приведенный выше алгоритм был реализован на языке BPEL следующим образом: BPEL-процесс получает от клиента (в данном случае через сгенерированную программой Collaxa BPEL Console HTML-форму, см. Рис. 29) систему уравнений, начальные условия, шаг по времени и пороговую точность. После чего параллельным образом в потоке initFlow (Рис. 28) запускаются механизмы инициализации решателей. Затем, с помощью двух последовательных активностей assign (prognosislnputl и PrognosisInput2) происходит генерация первоначальных прогнозов.
После этого мы входим в главный поток процесса - SetPrognosisAndRunFlow, состоящий из трех параллельных нитей: две нити Run, передающие решателям первоначальные прогнозы и запускающие решатели (через активности invoke), и третья нить, отвечающая за обмен прогнозами между ними в ходе распределенного решения системы.
Остановимся на третьей нити подробнее. Для начала флаги решателей IsFinished выставляются в положение false. После этого процесс входит в стадию ожидания от решателей четырех типов сообщений (по два на решатель), от прихода которых и зависит то, как будут развиваться дальнейшие события (цикл Main Loop).
Если от первого решателя приходит сообщение о том, что он сгенерировал новый прогноз, то происходит обновление прогноза у второго решателя, и наоборот. Флаг IsFinished в этом случае выставляется в положение false, чтобы процесс, получивший новый прогноз, произвел «откат» к моменту обновления прогноза даже в том случае, если он успел завершиться. Для второго решателя все происходит аналогично, зеркальным образом.
Если от первого решателя приходит сообщение о том, что он завершил свою работу, то флаг IsFinished, соответствующий этому процессу переводится в состояние true. Как уже говорилось, если позднее от второго решателя придет новый прогноз, то первому придется снова начать работать с момента обновления, и его флаг IsFinished снова придет в положение false.
Если же в какой-то момент окажется, что оба решателя завершили свою работу, и соответствующие им флаги IsFinished одновременно находятся в положении true, то в потоке getResultFlow параллельно запускаются два метода getResult, которые и получают от решателей результаты их работ — окончательные решения.
На этом поток SetPrognosisAndRunFlow завершается, через активность assign полученные результаты записываются в переменную ProcessOutput. После чего вызывается метод onResult, передающий полученные результаты клиенту.
Приведенная выше схема была реализована распределенным образом на двух машинах - сервере dcs.isa.ru (с операционной системой Linux) и локальном компьютере (операционная система Windows 2000). На последнем был запущен Collaxa BPEL Server, на котором и выполнялся данный BPEL-процесс. На сервере dcs.isa.ru были запущены Grid-сервисы solverl и soIver2, отсылающие и принимающие прогнозы от BPEL-процесса. Они были созданы и размещены на сервере с применением пакета Globus Toolkit 3. Их мы использовали в качестве агентов доступа к программе-решателю отдельных дифференциальных уравнений методом Эйлера (Java-класс ODESolver). Подобнее об агентах доступа можно узнать в [9].
Распределенный алгоритм безошибочного обращения плохо обусловленных матриц большой размерности
По инициативе компании Lester [20], занимающейся разработкой программного обеспечения класса ERP для железнодорожных экспедиторов, была проведена работа над задачей расчета оптимальной диспетчеризации полученных заказов между свободными вагонами [22].
Данная задача состоит в следующем: пусть некоторый экспедитор имеет собственный или арендованный подвижной состав (вагоны и контейнеры). При получении заказа экспедитор должен решить, принимает ли он заказ, или же отказывается от него, и если принимает, то какими вагонами он планирует его перевозить. Оптимальное решение должно максимизировать прибыль экспедитора с учетом всех факторов, влияющих на прибыль и расходы.
Общее описание задачи Ниже рассматривается задача создания системы оптимального назначения свободных вагонов заявкам на перевозки.
Пусть некоторый железнодорожный оператор имеет в распоряжении парк вагонов и обслуживает заявки на перевозки различных грузов между несколькими пунктами. Каждый день ему приходят различные заявки, и ему необходимо решать на какие заявки соглашаться, и назначать на них вагоны, а от каких заявок отказываться. Количество вагонов порядка 10000, а количество заявок порядка нескольких сотен. Численное моделирование
Итак, мы имеем вычислительно сложную транспортную задачу нахождения соответствия имеющегося парка вагонов поданным заявкам с целью максимизации прибыли. Эта задача в исходной формулировке является NP-полной. Однако, структура данной задачи позволяет легко сформулировать упрощенную задачу в терминах линейного и смешанно-целочисленного программирования (МІР). О такой реализации данной задачи в терминах линейного и смешанно-целочисленного программирования и пойдет речь ниже. После составления линейной модели задачи эта модель подается на вход двум независимым реализациям решателя задач линейного программирования симплекс-методом, а также методом ветвей и границ для MIP-модели. Это решатели Ip_solve и glpk. Кроме того, в дальнейшем планируются испытания других решателей.
Каждая заявка содержит список параметров (в скобках указано обозначение, используемое в математической модели): расстояние между пунктами, зависящее от пункта 1 и пункта 2 Ниже перечислены компоненты математической задачи 1. Переменные. Переменные в задаче задаются таблицей хс,г размерности Сх R причем 1 с Си l r R, где С - число доступных вагонов, a R - количество заявок, поданных на данный момент. Элементами таблицы являются числа от 0 до 1 в случае модели линейного программирования и целые числа 0 и 1 в случае МІР. Ноль соответствует решению не использовать данный вагон для перевозки данной заявки, единица соответствует использованию вагона в данной заявке. Промежуточное значение -частичному использованию вагона (например, в случае неполной загрузки). Результатом решения задачи является заполненная таблица переменных и соответствующее этой таблице значение целевой функции. Конкретный набор значений таблицы называется назначением.
Целевая функция. В линейном случае целевой функцией задачи, подлежащей максимизации, является скалярное произведение матрицы переменных с матрицей стоимостей. Матрица стоимостей - это матрица Рс, г той же размерности, что и матрица переменных, в каждой ячейке которой находится число. То есть, целевая функция является линейной функцией, зависящей от переменных задачи. В общем случае целевая функция может иметь нелинейные компоненты — например, быть представимой в виде многочлена.
В методе ветвей и границ для отсечения лишних подмножеств здесь используется линейная оценка, в силу чего скорость работы алгоритма будет тем больше, чем меньше будет нелинейная составляющая этой функции.
Условия - ограничения. Условия на переменные в таблице имеют различную природу и перечислены в порядке добавления их к задаче. Индексы сиг пробегают значения от 1 до С и от 1 до R соответственно и соответствуют номеру вагона и номеру заявки. выполнение остальных из данного множества. Данное условие используется для разделения заявок по времени - если данный вагон после выполнения одной заявки успевает выполнить и другую, то эти заявки попадают в разные множества. Множества заявок Rj вычисляются предварительно.
Для проведения вычислительного эксперимента были выбраны т.н. матрицы Гильберта, являющиеся частным случаем матриц Коши, которые широко применяются в теории и численных методах аппроксимации произвольных функций многочленами (при обработке сигналов, коррекции ошибок и т.п.). Формальное определение матрицы Гильберта размера NxN выглядит следующим образом:
Чтобы оценить объем вычислений, с которым пришлось бы иметь дело в случае использования «традиционных» вычислений с ограниченной разрядностью, в следующей таблице приведены значения чисел обусловленности матриц Гильберта для некоторых размерностей. Отметим, что это не оценки, а «точные» значения, полученные в Maxima округлением точно вычисленных значений произведений норм Фробениуса прямой и обратной матриц.
Итак, из соображений производительности было решено прибегнуть к распределенному решению данной задачи. Был разработан распределенный сценарий обращения матрицы на основе блочной декомпозиции и дополнения Шура.
Был исследован следующий, частично распараллеливаемый сценарий. Его схема приведена ниже на Рис. 62. Стрелками показаны информационные зависимости между отдельными частями сценария. Пунктирные стрелки означают, что вычисления могут быть продолжены после получения результата от любого из предшествующих этапов. Сдвоенные вертикальные линии означают, что результирующая матрица (слева) может быть получена в результате различных «расстановок скобок» в стоящем справа произведении матриц.
