|
процедура Хью позволяет установить взаимооднозначное соответствие между возможной длительностью реализации процесса и составом мультиресурсной среды. Автором предлагается модифицировать процедуру анализа и коррекции временных параметров распределенного процесса с корневой структурой (на базе ВВР и ВР, определяющих предписанное время обработки процесса) для возможности учета мультиресурсного распределения единичных операций, размеченных в соответствии с процедурой Хью. Отметим, что в общем случае неединичные операции (например, с весами больше единицы) представляются в виде потока операций с единичным весом, чья сумма равна весу изначальной операции. Такое представление позволяет определять оптимальное неприоритетное решение, используя алгоритм Хью, так как граф является деревом, а использование алгоритма наидлиннейшего пути Кауфмана (или G-алгоритма) не позволяет прерывать ресурс до завершения этой составной операции, которая является членом потока операций, представляющего задачу неединичного веса. Для выше описанной среды имеет существенное значение понятие уровень задачи, который определим следующим образом. Уровень задачи, которая не имеет последователей, равен 1. Уровень задачи, имеющей одного или более последователей, равен единице плюс максимальное значение уровня из уровней последующих элементов задачи. Простой уровневый алгоритм (simple level algorithm, SLA) это уровневый алгоритм, в котором планируемые внутри одного уровня задачи полностью произвольны. Если Wsta общее время выполнения плана, полученного с помощью SLA, и Wo общее время выполнения оптимального плана, то можно показать, что для двухресурсной системы ^/%<4/3. Для трехресурсной системы получено следующее соотношение: 57 |
Хью позволяет установить взаимооднозначное соответствие между возможной длительностью реализации алгоритма и составом мультипроцессорной среды. В данной работе автором предлагается модифицировать процедуру анализа и коррекции временных параметров распределенного алгоритма с корневой структурой (на базе ВВР и ВР, определяющих предписанное время обработки алгоритма, рассмотренных в следующем параграфе) для возможности учета мультипроцессорного распределения единичных операций, размеченных в соответствии с процедурой Хью. Отметим, что в общем случае неединичные операции (например, с весами больше единицы) представляются в виде потока операций с единичным весом, чья сумма равна весу изначальной операции; Такое представление позволяет определять оптимальное неприоритетное решение, используя алгоритм Хью, так как граф является деревом, а использование алгоритма наидлиннейшего пути Кауфмана (или (7-алгоритма) не позволяет прерывать процессор до завершения этой составной операции, которая является членом потока операций, представляющего алгоритмическую задачу неединичного веса. Для выше описанной среды имеет существенное значение понятие уровень задачи, который определим следующим образом. Уровень задачи, которая не имеет последователей, равен 1. Уровень задачи, имеющей одного или более последователей, равен* единице плюс максимальное значение уровня из уровней последующих элементов задачи. Простой уровневый; алгоритм (simple level algorithm, SLA) это уровневый алгоритм, в котором планируемые внутри одного уровня задачи полностью произвольны. Если Wsia общее время выполнения плана, полученного с помощью SLA, и Wo общее время выполнения оптимального плана, то можно показать, что для двухпроцессорной системы <4/3. 63 формирования распределенных алгоритмов, используемых в реальных вычислительных средах АСУ можно считать выполненной. Возможным способом решения практических задач (предположения о детерминированности процессов не всегда применимы на практике) формирования распределенных параллельных алгоритмов обработки информации и управления может оказаться либо хорошо проверенный эвристический алгоритм, либо некоторый статистический, метод, что и представляет собой новый авторский подход к решению проблемы. 2. Постановка задачи анализа’ реализуемости распределенных алгоритмов определяет пути исследования совместных свойств процессов распределенной обработки и управления и ВС АСУ, на которых эти процессы реализуются. Задача может быть описана как задача минимизации функционала времени реализации совокупности алгоритмов заданного процесса на множестве решений системы линейных неравенств с ограничениями, регламентация которых осуществляется на практике режимом реального времени. 3. Шаги разработанной аналитико-оптимизационной процедуры ресурсно-временного анализа и формирования алгоритмов распределенной обработки и управления требуют многократного повторения последовательных этапов оптимизации, целевого функционала (при выборе оптимального времени реализации совокупности алгоритмов, согласно составу аппаратно-программного комплекса управления), анализа реализуемости (корректность заданных временных ограничений) и коррекции алгоритмов. 4. Предлагается модифицировать процедуру анализа и коррекции временных параметров распределенного алгоритма с корневой структурой (на базе ВВР и ВР, определяющих предписанное время обработки алгоритма) для возможности учета мультипроцессорного распределения единичных операций, размеченных в соответствии с процедурой Хью. 93 |