Граф - алгоритм
Cтраница 3
Во-вторых, для каждого основного оператора Va необходимо определить среднее количество операций ka, составляющих оператор, и для каждого оператора ввода - вывода Ур - среднее количество информации / р, передаваемой при выполнении оператора. Так как вычислительный процесс не может приостановиться в вершине Vt, то с вероятностью 1 произойдет переход к какой-либо вершине графа алгоритма. [31]
Разработан ряд стохастических методов решения поставленной оптимизационной задачи распараллеливания вычислений. В первом методе - стохастическом методе попарной оптимизации подграфов - поиск оптимального решения осуществляется за счет взаимного ( стохастического) переноса вершин между различными парами подграфов графа алгоритма. Второй метод - метод Монте-Карло случайного блуждания вершин графа алгоритма по подграфам - основан на отождествлении вершин графа алгоритма с некоторыми частицами, совершающими случайные блуждания по областям-подграфам в потенциальном силовом поле, роль потенциала которого играет минимизируемый функционал. Наиболее вероятное состояние подобной системы частиц соответствует минимуму потенциала - - и, следовательно, является искомым решением. Поиск такого состояния осуществляется методом Монте-Карло с использованием специальной процедуры имитации отжига. Третий метод - стохастический метод наискорейшего спуска - основан на использовании дискретного аналога градиента минимизируемого функционала. Все разработанные методы реализованы программно и являются частью системы программ PARALLAX. Проведено тестирование созданных программ и сравнение их работы на простейших примерах. [32]
 |
Зависимость ускорения 5, достигаемого при распараллеливании явного метода решения нелинейной динамической системы, от времени ( передачи единицы информации по каналам ВС. [33] |
Разработан ряд стохастических методов решения поставленной оптимизационной задачи распараллеливания вычислений. В первом методе - стохастическом методе попарной оптимизации подграфов - поиск оптимального решения осуществляется за счет взаимного ( стохастического) переноса вершин между различными парами подграфов графа алгоритма. Второй метод - метод Монте-Карло случайного блуждания вершин графа алгоритма по подграфам - основан на отождествлении вершин графа алгоритма с некоторыми частицами, совершающими случайные блуждания по областям-подграфам в потенциальном силовом поле, роль потенциала которого играет минимизируемый функционал. Наиболее вероятное состояние подобной системы частиц соответствует минимуму потенциала - и, следовательно, является искомым решением. [34]
Разработан ряд стохастических методов решения поставленной оптимизационной задачи распараллеливания вычислений. В первом методе - стохастическом методе попарной оптимизации подграфов - поиск оптимального решения осуществляется за счет взаимного ( стохастического) переноса вершин между различными парами подграфов графа алгоритма. Второй метод - метод Монте-Карло случайного блуждания вершин графа алгоритма по подграфам - основан на отождествлении вершин графа алгоритма с некоторыми частицами, совершающими случайные блуждания по областям-подграфам в потенциальном силовом поле, роль потенциала которого играет минимизируемый функционал. Наиболее вероятное состояние подобной системы частиц соответствует минимуму потенциала - - и, следовательно, является искомым решением. Поиск такого состояния осуществляется методом Монте-Карло с использованием специальной процедуры имитации отжига. Третий метод - стохастический метод наискорейшего спуска - основан на использовании дискретного аналога градиента минимизируемого функционала. Все разработанные методы реализованы программно и являются частью системы программ PARALLAX. Проведено тестирование созданных программ и сравнение их работы на простейших примерах. [35]
Разработан ряд стохастических методов решения поставленной оптимизационной задачи распараллеливания вычислений. В первом методе - стохастическом методе попарной оптимизации подграфов - поиск оптимального решения осуществляется за счет взаимного ( стохастического) переноса вершин между различными парами подграфов графа алгоритма. Второй метод - метод Монте-Карло случайного блуждания вершин графа алгоритма по подграфам - основан на отождествлении вершин графа алгоритма с некоторыми частицами, совершающими случайные блуждания по областям-подграфам в потенциальном силовом поле, роль потенциала которого играет минимизируемый функционал. Наиболее вероятное состояние подобной системы частиц соответствует минимуму потенциала - и, следовательно, является искомым решением. [36]
В любом случае применение точных методов решения задачи назначения для больших размеров используемых графов является проблематичным либо из-за их большой сложности, либо из-за чересчур узкого класса допустимых графов. Эти методы также можно разделить на специализированные ( рассчитанные на ограниченный класс графов алгоритмов и / или ВС) и универсальные. К первым относится семейство методов, описанных в [80] и предназначенных для решения ряда задач с ограничениями и на граф алгоритма и на граф ВС. Описывается процедура Probe, которая для заданного числа а определяет, существует или нет назначение, значение функционала на котором меньше или равно а. Если такое отображение существует, то оно строится. [37]
Разработан ряд стохастических методов решения поставленной оптимизационной задачи распараллеливания вычислений. В первом методе - стохастическом методе попарной оптимизации подграфов - поиск оптимального решения осуществляется за счет взаимного ( стохастического) переноса вершин между различными парами подграфов графа алгоритма. Второй метод - метод Монте-Карло случайного блуждания вершин графа алгоритма по подграфам - основан на отождествлении вершин графа алгоритма с некоторыми частицами, совершающими случайные блуждания по областям-подграфам в потенциальном силовом поле, роль потенциала которого играет минимизируемый функционал. Наиболее вероятное состояние подобной системы частиц соответствует минимуму потенциала - - и, следовательно, является искомым решением. Поиск такого состояния осуществляется методом Монте-Карло с использованием специальной процедуры имитации отжига. Третий метод - стохастический метод наискорейшего спуска - основан на использовании дискретного аналога градиента минимизируемого функционала. Все разработанные методы реализованы программно и являются частью системы программ PARALLAX. Проведено тестирование созданных программ и сравнение их работы на простейших примерах. [38]
Разработан ряд стохастических методов решения поставленной оптимизационной задачи распараллеливания вычислений. В первом методе - стохастическом методе попарной оптимизации подграфов - поиск оптимального решения осуществляется за счет взаимного ( стохастического) переноса вершин между различными парами подграфов графа алгоритма. Второй метод - метод Монте-Карло случайного блуждания вершин графа алгоритма по подграфам - основан на отождествлении вершин графа алгоритма с некоторыми частицами, совершающими случайные блуждания по областям-подграфам в потенциальном силовом поле, роль потенциала которого играет минимизируемый функционал. Наиболее вероятное состояние подобной системы частиц соответствует минимуму потенциала - и, следовательно, является искомым решением. [39]
Алгоритм функционирования такого устройства управления представляется в виде содержательного графа алгоритма микропрограммы. После выбора типа автомата ( автомат Мили или Мура) осуществляется переход к отмеченному закодированному графу алгоритма. Этот переход выполняется человеком. Цель его - подготовить граф алгоритма к виду, который может быть использован для ввода в машину. [40]
В любом случае применение точных методов решения задачи назначения для больших размеров используемых графов является проблематичным либо из-за их большой сложности, либо из-за чересчур узкого класса допустимых графов. Эти методы также можно разделить на специализированные ( рассчитанные на ограниченный класс графов алгоритмов и / или ВС) и универсальные. К первым относится семейство методов, описанных в [80] и предназначенных для решения ряда задач с ограничениями и на граф алгоритма и на граф ВС. Описывается процедура Probe, которая для заданного числа а определяет, существует или нет назначение, значение функционала на котором меньше или равно а. Если такое отображение существует, то оно строится. [41]
Выбор конкретной микрокоманды определяется ( значениями входных сигналов X. При этом переключение в следующее состояние осуществляется в конце такта, ва время которого выполняются микрооперации, соответствующие текущим значениям входных сигналов X. Поэтому реализация УА по этой схеме требует несколько больше лементои памяти. Уя, применяемый в lo J ( си.рис. 1), выполнен по схеме Мура, имеет десять состоянии и реализует граф алгоритма обработки ( ом.рис. 2), где Q0 - т ( Jg - состояния автомата, XI Х12 - множество входных осведомительных сигналов. УА реаливо -; ван в автономной системе контроля геометрических параметров скважин, разработанной МЛНХ и ГП совместно с ВНИИКАнефтегав. [42]
Вершины таких графов соответствуют некоторым частям алгоритма, в дальнейшем называемыми операциями. Дуги графа, соединяющие вершины, означают наличие информационной зависимости между соответствующими операциями алгоритма - результат выполнения одной операции является аргументом для другой. Веса вершин пропорциональны времени выполнения соответствующих операций - будем измерять их числом некоторых элементарных операций, содержащихся в соответствующей данной вершине операции. Дуги графа алгоритма также являются взвешенными, и их вес равен объему ( например, в байтах) передаваемой по этой дуге информации. [43]
Вершины таких графов соответствуют некоторым частям алгоритма, в дальнейшем называемыми операциями. Дуги графа, соединяющие вершины, означают наличие информационной зависимости между соответствующими операциями алгоритма - результат выполнения одной операции является аргументом для другой. Веса вершин пропорциональны времени выполнения соответствующих операций - будем измерять их числом некоторым элементарных операций, содержащихся в соответствующей данной вершине операции. Дуги графа алгоритма также являются взвешенными, и их вес равен объему ( например, в байтах) передаваемой по этой дуге информации. [44]
Минимальная и максимальная трудоемкость алгоритмов, содержащих циклы, находится пв аналогии с методом определения средней трудоемкости алгоритмов с циклами. Находится минимальная А и максимальная В трудоемкость тела цикла. Минимальная и максимальная трудоемкость цикла определяется значениями Anmin и Вптах, где nmln и лтах - минимальное и максимальное число повторений цикла. Затем цикл заменяется оператором с трудоемкостью kminAnm - ln и kmaxBnmax и вновь применяется процедура исключения циклов. Процесс повторяется до тех пор, пока граф алгоритма не будет преобразован к форме без циклов. [45]
Страницы: 1 2 3