|
WsIaIWQ<3ll. Данные соотношения позволяют сравнить производительность, полученную с помощью алгоритма с теоретически возможным оптимумом. Далее при анализе планов формирования распределенных процессов, полученных с помощью эвристического или приближенного метода, сравнение будем выражать в виде коэффициента, сравнивающего почти оптимальный (субоптимальный) план с оптимальным. Эта величина может быть больше или равна единице и показывает, насколько производительность упрощенного подхода сравнима с оптимальным решением. Здесь следует сделать два замечания. Во-первых, часто случается, что эвристические планы выдают решение, которое не хуже оптимального. Тем самым появляется желание приписать такому подходу незаслуженное качество, до того как определены его границы производительности в наихудшем случае. Во-вторых, при сравнении эвристического плана с оптимальным необходимо помнить, что последний не обязательно является детерминированным, так как, за исключением уже обсужденных специальных случаев, не перечисляемые решения для определения оптимального результата не доступны. То есть оптимальное решение не может быть найдено простым перебором всех возможных решений и затем выбором лучшего. Для задач с малым количеством альтернатив перебор может быть не очень сложен. Однако когда количество альтернатив достаточно велико и для их обработки требуется экспоненциально растущее время, эвристические подходы выглядят более привлекательно по сравнению с переборными. Для списочных планов также важны следующие условия, которые могут привести к увеличению времени выполнения сформированного плана: 1. Замещение списка задач L другим списком L’ с неизменными набором временных параметров задач т, порядком предшествования < и количеством сопроцессоров п. 58 |
Для трехпроцессорной системы получено следующее соотношение: ^,a/^0<3/2.. Данные соотношения позволяют сравнить производительность,, полученную с помощью алгоритма с теоретически возможным оптимумом. Далее при анализе планов формирования распределенных алгоритмов, полученных с помощью эвристического или приближенного метода, сравнение будем выражать-в виде коэффициента, сравнивающего почти оптимальный (субоптимальный) план с оптимальным. Эта величина может быть больше или равна единице и показывает, насколько производительность упрощенного подхода сравнима с оптимальным решением. Здесь, следует сделать два замечания. Во-первых, часто случается j что эвристические планы выдают решение, которое.не хуже оптимального. Тём, самым появляется желание приписать такому подходу незаслуженное качество, до того как определены его границы производительности в наихудшем случае. Во-вторых, при сравнении эвристического плана с оптимальным необходимо помнить, что последний не обязательно является детерминированным, так как, за исключением уже обсужденных специальных случаев, неперечисляемые решения для определения: оптимального результата не доступны. То есть оптимальное решение не может быть найдено простым перебором всех возможных решений и затем выбором лучшего. Для1 задач с малым количеством альтернатив перебор может быть не; очень сложен. Однако когда количество альтернатив достаточно велико и для их обработки, требуется экспоненциально растущее время, эвристические подходы выглядят более привлекательно по сравнению с переборными. Для списочных планов также важны следующие условия, которые могут привести к увеличению времени выполнения сформированного плана: 1. Замещение списка задач L другим списком £’ с неизменными набором временных параметров задач т, порядком предшествования < и количеством сопроцессоров п. 2. Ослабление некоторых ограничений частичного упорядочивания. 64 |