Задачи, стадии и этапы проектирования

Вопросы для самоконтроля

1. В каком порядке выполняются следующие этапы по проектированию технических проектов: ОКР, Изготовление опытных образцов, НИР, Испытания и приемка, Разработка технической документации.

2. В чем суть проектирования методами «сверху вниз» и «снизу вверх»?

3. Кем разрабатывается ТЗ на ОКР и почему?

4. Кем разрабатывается ТЗ на НИР и почему?

5. Какой этап предшествует техническому проектированию?

6. Назовите основные этапы ОКР.

7. Перечислите основные цели автоматизации проектирования.

8. Назовите основные методы уменьшения трудоемкости инженерного труда.

9. Какими методами достигается улучшение качества проектирования?

10. Какие из перечисленных методов используются для сокращения трудоемкости проектных работ: автоматизация оформления проектной документации, совмещенное (параллельное) проектирование, вариативное проектирование и оптимизация?

11. Какие из перечисленных задач автоматизации проектных работ могут противоречить друг другу: сокращение трудоемкости проектирования, сокращение себестоимости проектирования, сокращение цикла «проектирование – изготовление»?

12. Назовите основные виды обеспечения САПР.

13. Классический и системный подходы. Два определение системного подхода, их отличия.

14. Какие преимущества дает использование электронных чертежей (схем) перед бумажной технологией?

15. Для чего нужна ассоциативная связь между принципиальной электрической схемой и редактором печатных плат?

16. Какие основные программные пакеты входят в EDA-систему?

Проектирование элементов мехатронных систем

Мехатроника – инструментарий для разработки робототехники

Мехатроникой называют «систему средств совместного проектирования и моделирования узлов точной механики с электронными, электротехническими и компьютерными компонентами, обеспечивающими проектирование и производство качественно новых модулей, машин и систем с интеллектуальным управлением их функциональными движениями», «технологии трансляторов между EDA- и MCAD- системами» [2]. Иными словами, это – инструментарий для разработки интеллектуальных подвижных систем, как правило, робототехнических компонент (манипуляторов, беспилотных транспортных средств и иных интеллектуальных электромеханических устройств и систем).

Первые электромеханические системы состояли, как правило, из условно независимых компонент: механических узлов, электрических узлов и электронных управляющих систем. Деление системы на подсистемы осуществляется для более простого описания ее функционирования, путем выделения отдельных функций и соотнесения их по признаку, какие функции какой подсистемой выполняются.

Например, систему управления радиолокатором можно разделить на чисто механическую часть, состоящую из антенны, редукторов и элементов конструкции, электромеханическую – электродвигатель, электротехническую – усилитель для питания электродвигателя, датчики положения и управляющую электронику.

Современные электромеханические системы уже не могут быть адекватно разделены на условно независимые компоненты: механические узлы, электрические узлы и цифровые электронные управляющие системы. Если такое деление искусственно осуществить, оно не вполне точно будет отражать реальную систему. Промышленность выпускает готовые системы, содержащие встроенные датчики угла поворота, прецизионные системы управления углом поворота, двигатели и редукторы – все в единой сборке. Для управления такой системой достаточно подать на нее электропитание и цифровые сигналы предписанных углов поворота (в соответствии с протоколом обмена). Встроенная управляющая система может содержать собственный микроконтроллер и общаться с внешним устройством как обычный или промышленный компьютер, или, как, например, периферийное устройство (сканер, принтер и т.п.).

Программное обеспечение VisSim

Из курса «Моделирование систем» слушатели должны быть знакомы с программным обеспечением VisSim, которое позволяет не только моделировать работу замкнутых динамических систем, но также и оптимизировать регулятор, включая многоканальные регуляторы.

Отметим основные достоинства этой программы.

1. Моделирование осуществляется по шагам, что в точности соответствует действию цифровых управляющих устройств, то есть устройств на основе микропроцессора. Поэтому если при моделировании получен удовлетворительный результат, то и при работе реального цифрового управляющего устройства (в том числе – в контуре с отрицательной обратной связью) результат также будет удовлетворительным. Данное утверждение не распространяется на случаи неадекватной модели объекта или некорректного моделирования, а также на случае некорректно выбранного метода интегрирования. В учебном пособии по программному обеспечению VisSim отмечено, что следует использовать простой метод Эйлера (в опции «выбор метода интегрирования»).

2. Система не допускает моделирования некорректно заданных звеньев, то есть звеньев, которые не могут быть физически реализованы. Это также является достоинством, поскольку снижает вероятность ошибки проектировщика.

3. Программа содержит инструментарий для численной оптимизации нескольких параметров (в зависимости от версий – от 5 и более параметров) по заданной стоимостной функции. Это позволяет легко и просто рассчитать регулятор. В соединении с разработанными нами методами эта методика может быть распространена и на случаи многоканальных объектов с многоканальными регуляторами.

4. Программа допускает различные методы задания математических моделей элементов сложной структуры. В одном проекте отдельные элементы могут быть заданы разными путями, например, описанием в форме передаточной функции (для линейных объектов), в форме нелинейных функций во временной области (для нелинейных объектов), в виде логических элементов, булевых функций, генераторов детерминированных функций и псевдослучайных функций, блоков программы MATLAB и других.

5. Результаты оптимизации могут быть отражены в графической форме (графики переходных процессов).

6. Наряду с сигналами во временной области (входные, выходные и промежуточные сигналы), могут быть получены графики в иных осях, в том числе – в режиме фигур Лиссажу, в частотной области, диаграммы Боде (то есть амплитудно-частотная и фазо-частотная характеристики), в виде фазовых траекторий и так далее. Все полученные графики могут быть сохранены в файл данных для дальнейшей обработки другими программными средствами.

7. Программа допускает режим реального времени.

8. В профессиональной версии программа допускает использование входных портов компьютера в качестве выходов реальных блоков и выходных портов компьютера в качестве входов реальных блоков. Таким образом, в работе моделируемой системы могут участвовать реальные устройства. При этом должен использоваться режим реального времени.

9. Поскольку программа сохраняет лишь проект (структуру), но не сохраняет получаемые графики (кроме случая импортирования их в файлы), накопленные наработки занимают малый объем памяти, как и сами дистрибутивы этого программного средства.

Вопросы для самоконтроля

1. Что такое мехатроника?

2. Что называют проектом при программировании структуры цифроаналогового устройства на основе аналогового процессора или микроконтроллера?

3. Для каких целей могут быть использованы программные средства MexBIOS Development Studio и VisSim? Какие из указанных программных средств (или оба) позволяют автоматически осуществлять оптимизацию регуляторов для замкнутых систем?

4. Перечислите достоинства программы VisSim.

Требования к физической реализуемости модели

Все элементы системы должны быть физически реализуемы. Это условие формально требует, чтобы степень числителя была меньше степени знаменателя. Действительно, следует учесть, что аргумент s представляет собой некий аналог частоты. С ростом частоты передаточная функция отдельных элементов не обязательно ниспадает, но если продлить этот рост частот достаточно далеко, то передаточная функция любого реального объекта непременно ниспадет до сколь угодно малых величин. Мало того: для любого объекта всегда можно указать такие частоты, на которых передаточная функция не просто мала, а отклик объекта на этих частотах строго отсутствует (либо намного меньше шумов его измерения).

Частотные характеристики, как правило, представляют в логарифмическом масштабе, поэтому на графике достаточно быстро достигается «практическая бесконечность», т. е. очень большие значения частоты и значения передаточной функции, как и «практический нуль», т. е. очень маленькие значения этих величин. На логарифмических графиках наглядно видны значения частот, во много раз превышающих область частот пропускания объекта. Таким образом, правая часть логарифмической амплитудно-частотной характеристики (ЛАЧХ) любого реализуемого звена должна на графике ниспадать вниз, чем правее, тем ниже. Это достигается только при условии, что знаменатель указанной дробной передаточной функции больше, чем числитель.

Иногда в отношении отдельных звеньев этим требованием пренебрегают, поскольку полоса пропускания этих звеньев может оказаться существенно шире полосы пропускания объекта. Так, затуханием отдельных элементов можно пренебречь в сравнении с затуханием других звеньев, входящих в тот же контур. Если же какое-либо звено является единственным звеном рассматриваемого контура, то в этом контуре нет других более инерционных звеньев, в сравнении с которыми можно было бы пренебречь затуханием данного элемента. В этом случае указанный элемент недопустимо описывать безынерционным звеном.

Даже ограничиваться рассмотрением лишь отличием степени знаменателя от степени числителя также недостаточно для адекватного анализа устойчивости любого реального контура с отрицательной обратной связи. Однако если в контуре присутствует элемент запаздывания и если достоверно известно, что влияние следующей постоянной времени модели на фазо-частотную характеристику (ФЧХ) существенно меньше, допускается ограничивать рассмотрение динамической части объекта элементами первого порядка.

3.3. Формализация требований к системе: целевая функция

Целевая функция может быть сформирована, например, следующим образом:

Это – положительно определенная функция, то есть она не может быть отрицательной ни при каких значениях ее аргументов. Требуется найти такие значения коэффициентов регулятора, при которых целевая функция достигает минимального значения. Поскольку ошибка в системе зависит от коэффициентов регулятора, то и вся целевая функция будет зависеть от этих коэффициентов. Решение этой задачи называется оптимумом, в нашем случае – минимум. Следует различать локальные и глобальный минимумы. Локальные минимумы – это такие решения, при которых небольшие изменения любого параметра вызывают рост целевой функции, однако, это не относится к любым изменениям этих параметров. Глобальный минимум может быть лишь один – это такое решение, которое обеспечивает наименьшее значение целевой функции для всех параметров из области их допустимых значений.

Могут быть применены различные алгоритмы поиска минимума. Правильность выбора метода оптимизации зависит от свойств задачи: наилучший метод для одной задачи может оказаться наихудшим или вовсе неприменимым для другой задачи.

Можно разбить методы оптимизации на следующие виды:

1. Итеративный поиск.

2. Случайный перебор.

3. Систематический перебор.

4. Генетические алгоритмы.

Итеративный поиск эффективен в том случае, если целевая функция плавно изменяется при плавном изменении ее аргументов. Гладкость предполагает, что небольшое приращение любого аргумента дает небольшое приращение функции. В этом случае можно предполагать, что в точках максимума или минимума целевой функции приращение любого аргумента в любом направлении дает приращение целевой функции только в одном направлении, а именно: в случае максимума целевая функция уменьшается при любом приращении аргумента, а в случае минимума – увеличивается. Во всех остальных точках малое положительное приращение какого-либо из аргументов дает малое приращение величины целевой функции одного знака, а малое отрицательное приращение этого же аргумента даст малое приращение противоположного знака.

Поэтому итеративные процедуры осуществляют изменения всех аргументов (поочередно или совместно) до тех пор, пока не будет достигнута такая ситуация, при которой любое приращение любого из аргументов вызовет лишь увеличение целевой функции. Это будет означать достижение, по меньшей мене, локального минимума. Проверка на глобальность этого минимума, то есть на наличие других минимумов, необходима, поскольку могут существовать несколько минимумов.

Для того чтобы можно было применять итеративный поиск, требуется обеспечить специальные свойства целевой функции. В частности, она должна быть гладкой. Если это не так, то итеративный метод не даст результата, поскольку в этом случае результат приращения целевой функции при каком-либо малом приращении аргумента никаким образом не связан с результатом приращения этой целевой функции ни при каком ином сколь угодно малом приращении этого же аргумента. Для такой ситуации может быть применен лишь случайный или систематический перебор.

Систематический перебор предполагает решение задачи для всех возможных сочетаний всех параметров объекта. Эта процедура чрезвычайно громоздка для любой практической задачи, поэтому затруднительно указать случаи целесообразности ее применения.

Случайный перебор отличается от систематического лишь тем, что выбор параметров регулятора осуществляется не по какому-либо наперед заданному закону и не с целью перебора всех возможных вариантов, а случайным или псевдослучайным образом. Этот метод позволяет сократить процедуру настройки регулятора в предположении, что в достаточной степени удовлетворительный (хотя и далеко не оптимальный) результат может выпасть значительно раньше, чем будут исследованы все возможные сочетания всех параметров. Это позволит прекратить дальнейший поиск, выбрав это решение. Этот метод напоминает попытку угадать счастливое число в казино, поэтому он получил название метода Монте-Карло (по названию столицы игорного бизнеса). Именно такой метод применяется при «оптимизации» регуляторов в программе Simulink. Хотя результат такого численного поиска зачастую вполне удовлетворительный, строго говоря, этот результат не является результатом оптимизации, поскольку невозможно исключить, что могут быть найдены лучшие решения, дающие меньшее значение целевой функции. Все же следует признать, что этот метод – единственный приемлемый метод для случая отсутствия какой-либо гладкой зависимости между изменениями аргументов и изменениями самой функции.

Применительно к задаче численной оптимизации регулятора ситуация далеко не столь бесперспективна: целевая функция, как правило, всегда является гладкой, и производная этой целевой функции по любому параметру может указать на то направление изменения этого параметра, которое ведет к минимуму целевой функции.

Действительно, если производная положительна, то положительное приращение параметра увеличивает функцию. Следовательно, необходимо уменьшать этот параметр. Если производная отрицательна, следует этот параметр увеличивать, а если она равна нулю, данная точка находится на минимуме при фиксированных значениях остальных параметров, и, следовательно, как минимум, эта точка находится в «ложбине», которая ведет к минимуму. Дальнейшее изменение этого параметра целесообразно делать лишь совместно с изменениями других параметров. Если частные производные целевой функции по всем параметрам равны нулю, данная точка может оказаться минимумом. Специальные случаи, когда это не так, могут быть учтены процедурой поиска, в итоге которого должна быть найдена точка, в которой любые линейные комбинации любых малых приращений любых параметров порождают лишь увеличение целевой функции.

Оптимизация ансамбля систем

При моделировании может быть создано несколько параллельно работающих систем. Возможны два случая: а) параллельное моделирование систем с одинаковыми объектами и различными регуляторами; б) параллельное моделирование разных объектов с одинаковыми регуляторами.

В случае (а) это может ускорить процесс отыскания экстремума и сделать его более наглядным. Случай (б) позволяет осуществлять расчет робастных регуляторов, то есть таких регуляторов, которые обеспечивают удовлетворительное решение задачи не только для фиксированных параметров объекта, но при их изменении в некотором небольшом (заранее известном) диапазоне.

Методы оптимизации

Метод золотого сечения

Метод чисел Фибоначчи

Метод локальной оптимизации

Метод локальной оптимизации [1, с.182] предполагает при движении из каждой новой точки давать приращение по каждой координате отдельно, получать набор ближайших значений параметров, анализировать набор значений целевых функционалов, и двигаться в направлении минимального из них. В таком случае порядок начертания параметров регулятора не будет иметь значения, в этом смысле этот метод предпочтителен, поскольку движение идет преимущественно по той координате, по которой градиент целевого функционала существенней.

ПРИМЕР 1. Получили регулятор после 5000 шагов [60/40/5]. После следующей итерации, например, получаем [60, 5/40, 2/5, 1]. Изменения всех коэффициентов идут в одну сторону. Поэтому можно предположительно начать новую итерацию не с новых значений, а с тех, которые отличаются от старых на удвоенную величину полученных приращение, то есть [61/40, 4/5, 2].

ПРИМЕР 2. В тех же условиях, что и пример 1, после третьей итерации получаем [60, 8/40, 4/5, 2]. Это говорит о том, что изменения коэффициентов идут монотонно, и в одном направлении, то есть мы достаточно далеки от экстремума. Скорее всего, следует повысить точность в настройках оптимизации, поскольку оптимизация, предположительно, завершается по признаку достаточно малого отличия полученного результата от истинного экстремума, то есть определена слишком грубая точность результата.

Эволюционные методы

Генетический алгоритм

Генетический алгоритм – это подражание живой природе в методах решения технических задач. Хотя механизм эволюции не раскрыт, и не понят, имеется некая теория его действия, и этому действию можно подражать, что приносит свои положительные плоды.

Последовательность действий такова.

1. Выделяется совокупность свойств объектов, которые называют условно «генами».

2. Формируется количественная оценка полезности получаемой популяции, состоящей из носителей некоторых комбинаций генов. Это – функция полезности F, аналогичная «приспособленности» некоторой популяции к выживанию.

3. Разрабатывается математическая модель жизнедеятельности объекта в среде, осуществляющей «естественный отбор», то есть алгоритм вычисления функции полезности для заданного вектора – набора генов .

4. Вектор X, содержащий данный набор генов, получает по аналогии название «хромосома».

Терминология

Ген – управляемый параметр.

Аллель – значение гена.

Локус – позиция гена в хромосоме.

Генотип – экземпляр хромосомы.

Генофонд – множество возможных генотипов.

Функция полезности F – целевая функция «приспособленности».

Фенотип – совокупность гена и соответствующего значения F.

Кроссовер (скрещивание)

Разрыв и замещение могут быть осуществлены в любом месте, так как порядок следования генов условный.

Пример.

Родитель A	a	b	c	d	e	f	g	h
Родитель B	i	j	k	l	m	n	o	p

Потомок С	a	b	c	d	m	n	o	p
Потомок D	i	j	k	l	e	f	g	h

Мутации. Оператор мутации расширяет область генетического поиска. С некоторой вероятностью происходит замена гена не от родителя. Новые гены, не из имеющегося набора только так и могут возникать. Мутации остро необходимы в экстремальных случаях, например, при сокращении количества особей до критического уровня (Адам + Ева).

Селекция. Из каждой генерации пары потомков (или более) в новое поколение включается только лучший потомок из пары. Внутренний цикл оканчивается, когда количество экземпляров нового поколения достигает количества экземпляров старого поколения. Следовательно, происходит замена поколения на новое. (Например, по мере приобретения гражданами телевизоров Sharp, телевизоры «Рубин» оказываются на помойке).

Количество циклов (внешних) определяется по признакам стагнации (застоя, вырождения) популяции, но с условием превышения заданного предельного времени.

Если реальная эволюция практически не прекращается никогда, то большинство технических задач когда-то все же должны быть решены. Исключение: адаптивное генетическое управление или аналогичные задачи. В этом случае процесс обновления поколения (регуляторов) может происходить все время, пока длится управление.

Важное применение генетического алгоритма: выживание и оптимизация (существования) системы с резервированием (например, выбор каналов связи). Эти алгоритмы могут работать в условиях изменяющейся надежности отдельных элементов, их быстродействия (скорости передачи) и т.п.

Люди интуитивно используют некоторые приемы, схожие с генетическими алгоритмами. Например, замки и запоры – результат противодействия хищениям, при этом те ценности, которые часто расхищают, хранят более тщательно и учитывают детально, те же ценности, на которые мало кто льстится, хранят небрежно. «Только в России ядерную кнопку хранят в пластмассовом чемоданчике, а спирт – в железном сейфе» (неизвестный автор).

Метод частично спаренных скрещиваний PMX (Partly Matched Crossover). Метод состоит в том, что после скрещивания анализируется результат на наличие повторов. При наличии повторов лишние «гены» меняются на их парно-сопряженные гены. Этот метод целесообразно применять в том случае, когда наличие одинаковых «генов» нежелательно, либо нецелесообразно, а разнообразие, наоборот, приветствуется. Такая ситуация имеет место далеко не всегда.

Пример.

Родитель A
Родитель B

Предполагаемый «Потомок_С» получает запрещенную комбинацию «генов».

Потомок С

Повторяющиеся «гены» заменяем на сопряженные с ними: 1→ 3, 2→ 5, 9→ 4. Получаем «разрешенного потомка».

Потомок D

Селекция может осуществляться тут же.

Вариант 1. Рассмотрим всех потомков, выберем из них лучшего, вместо родителя включим его в результат.

Вариант 2. Выберем двух лучших потомков, и вместо двух родителей включим в результат.

Вариант 3. Из M родителей создадим много больше, чем M потомков (и мутантов), выберем M лучших особей и включим в результат.

Уточнение: При анализе для определения «лучших» родителей тоже целесообразно принимать во внимание наряду с потомками (можно считать, что в частности наряду с потомками всегда имеются клоны) – в качестве претендентов в «лучшие». Если родители (клоны) не попадают в список лучших, они не включаются в результат, если попадают, включаются на правах полноценного члена нового поколения.

Признак стагнации популяции: «клоны» лучше всех потомков от скрещиваний и мутаций. Т.е развития нет, развитие из этой ситуации противопоказано, зашло в тупик.

Выбор из совокупности клонов, потомков и мутантов может быть жестким или «по вероятности». По тем же правилам, по которым выбирались родители, выбирается и новое поколение (не следует путать – это не «такое же» правило, это то же самое правило, оно же).

где N_r – размер репродукционной группы.

Если функция полезности F зависит еще и от порядка «генов» то необходимо переупорядочивание. Цель – «нащупать» «полезные сочетания», «хромосомные блоки», разместить их близко друг к другу.

Дихотомическая кластеризация – разбиение множества элементов на два подмножества с минимальным числом связей между ними.

Пример – при изготовлении сложного функционального электронного устройства в виде двух микросхем. Может стоять задача разбития и на большее число кластеров.

Движение к оптимуму методом синхронного детектирования.

Вводятся девиации аргумента , синхронно с этим изучаются девиации целевой функции . Отношение характеризует градиент этой функции по данному параметру (координате).

Если это реализовать в ходе функционирования, получим адаптивную систему. Практические примеры применения этой методики назвать пока затруднительно.

Применительно к настройке, например, коэффициентов ПИД-регулятора, можно утверждать, что влияние разных коэффициентов различное. Имеет смысл обсуждать постановку задачи в следующем виде: для каждого параметра (коэффициента регулятора) можно пытаться отыскать раздельные критерии его оптимальной настройки. Разумеется, эти критерии не будут полностью независимыми, поскольку при одной паре значений двух фиксированных коэффициентов оптимальное значение третьего коэффициента не совпадет с его оптимальным значением при другой паре значений этих коэффициентов.

И все же, например, статическая ошибка устраняется введением интегрального коэффициента, устранение неустойчивости обеспечивается введением пропорционального и (или) дифференциального тракта, динамическая ошибка может быть уменьшена введением второго интегратора в низкочастотной области и так далее.

Генетические алгоритмы выходят далеко за рамки полной аналогии с живой природой. В частности, можно указать по аналогии бесполое и половое размножение, но вне этой аналогии можно по индукции предложить «трехполое» размножение и так далее.

Бесполое размножение – применение только мутаций.

Половое размножение – скрещивание пар по следующей схеме (для одного потомка):

- в потомках присутствует половина генного набора от каждого родителя. Могут браться и не равные части генных наборов:

Трехполое размножение:

- в потомках присутствует треть генного набора от каждого родителя. В случае неравных частей набора:

И так далее. В соответствии с этим можно вычислять вероятности получения тех или иных комбинаций при случайном скрещивании, а также при селекции. И наоборот, можно задавать вероятности для отбора генов от родителей на основании функции их полезности, при реализации которых будет осуществляться селекция.

Генетический алгоритм

1. Создание начального множества кодов K (популяции) – «сотворение мира».

2. Селекция (отбор) по значению целевой функции.

3. Скрещивание (обмен кодовыми последовательностями, кроссовер): а) точечный, б) двухточечный, в) равномерный, г) другой.

4. Если необходимо, то коррекция.

5. Мутации.

6. Если необходимо, то перестановка.

7. Редукция (сокращение получаемого множества K* за счет роста количества особей на этапах 3-5 до множества изначальной величины K).

8. Исследование критерия остановки, если нет, то возврат на 2, если да, то вывод результата из 7.

Вопрос: в чем отличие редукции от селекции?

Редукция – отсечение плохих вариантов.

Селекция – вероятностное участие в воспроизводстве с вероятностью, зависящей от близости к экстремуму целевой функции. То есть при селекции воспроизводятся не все варианты потомков, а только наиболее вероятные претенденты на роль «оптимальных потомков». Таким образом, в данном алгоритме заложено два этапа отбора – отбор родителей при селекции (право на участие в создании потомства) и отбор при редукции. На самом деле для работоспособности алгоритма достаточно одного отбора – либо только при создании нового поколения, либо только при редукции нового поколения. Совместное применение критерия в обеих операциях ускоряет процесс, но, возможно, это не всегда целесообразно (поскольку это все же усложняет алгоритм). Имеет право на существование и такой алгоритм, в котором оценка качества производится лишь один раз в цикле – либо только при выборе родителей, либо только при редукции нового поколения. Это целесообразно в том случае, если процесс оценивания существенно сложней всех остальных процессов.

Пример с транспьютерными технологиями

Транспьютерами называют микропроцессоры, позволяющие строить ЭВМ не по принципу «один ведущий, остальные ведомые», а по принципу «все и ведомые и ведущие». Любой транспьютер должен обладать возможностью контролировать свою исправность и занятость (валентность), а также воспринимать сообщения об исправности и занятости сопряженных с ним транспьютеров. В случае готовности он воспринимает задачу от занятых сопряженных транспьютеров, в случае наличия более одного валентного «соседа» он дробит задачу на более простые и передает эти подзадачи «соседям». В случае отсутствия двух или более валентных соседей транспьютер решает задачу сам и возвращает ее туда, откуда она пришла. Роль транспьютера могут выполнять отдельно стоящие ЭВМ, а роль связующих с ними каналов – компьютерные сети. Таким образом, мы приходим к сетевым технологиям.

Транспьютерные алгоритмы хорошо иллюстрируются в задаче отыскания экстремумов или максимумов по множествам.

Скажем, пусть имеется 64 случайных векторов, и требуется найти самый длинный вектор.

Первый транспьютер в первом цикле разобьет задачу на две подзадачи по 32 вектора и передаст двум соседям. Соседи во втором цикле передадут еще двум парам соседей задачи по 16 векторов. Количество задействованных транспьютеров будет расти по степенному закону, а количество векторов в подзадачах по степенному закону падать. На шестом цикле транспьютер, получивший задачу из двух векторов, решит ее сам, поскольку она далее уже не упрощается, т.е. он даст значение и номер самого длинного вектора из двух. Таким образом, динамика задачи может быть описана таблицей 1.

Таблица 1. Динамика решения задачи поиска экстремума 1→ 2.

Номер цикла	Сложность задачи	Количество решающих транспьютеров	Количество ожидающих транспьютеров

При решении задачи на разных этапах в ней будет задействовано от 1 до 127 транспьютеров, вся задача будет решена за 13 циклов. В среднем при решении задачи занято 28, 23 транспьютеров, даже если учитывать ожидающие. Традиционный компьютер для решения этой задачи должен осуществить перебор всех 128 векторов, для чего потребуется 128 циклов. При некоторых технологиях во время ожидания ответа транспьютер может быть занят решением других задач. Поэтому, вообще говоря, среднее количество задействованных транспьютеров именно в данной задаче еще почти вдвое меньше – т.е. около 15. При этом для успешного решения по этому алгоритму все же требуется наличие всех 127 транспьютеров на 7-м цикле. Т.е. в среднем задействовано значительно меньше вычислителей (менее четверти), чем необходимо для работоспособности алгоритма, и вместе с тем, если система решает несколько задач, поступающих не синхронно, то пики потребности аппаратного ресурса не должны совпадать (а если они совпадут, то возникнет очередь, что не помешает решить все поставленные задачи). Поэтому в среднем система из 128 транспьютеров может решать одновременно около четырех таких задач, экономя время почти в 10 раз по сравнению с традиционным компьютером.

Членение задачи вовсе не обязательно должно происходить в соотношении 1: 2. Скажем, если один транспьютер загружает четыре соседних, то динамика решения той же задачи будет такой, как показано на таблице 2.

Таблица 2. Динамика решения задачи поиска экстремума 1→ 4.

Номер цикла	Сложность задачи	Количество решающих транспьютеров	Количество ожидающих транспьютеров

В этом случае задача решается всего за 7 циклов, максимальное значение задействованных транспьютеров 85, среднее количество занятых транспьютеров 19, 9, т.е. занятым в среднем оказывается менее четверти ресурса. Рассмотрим ситуацию для членения задачи в соотношении 1: 8 (см. таблицу 3).

Таблица 3. Динамика решения задачи поиска экстремума 1→ 8.

Номер цикла	Сложность задачи	Количество решающих транспьютеров	Количество ожидающих транспьютеров

В этом случае задача решается всего за 5 циклов, максимальное значение задействованных транспьютеров 73, среднее количество занятых транспьютеров 18, 6, т.е. занято опять менее четверти ресурса.

Итак, мы видим, что в последнем случае ресурс по сравнению с простым компьютером возрастает в 73 раза, но в среднем лишь в 19 раз, скорость же вычислений возрастает в 25, 6 раза. То есть среднее возрастание ресурса меньше, чем среднее возрастание скорости решения задачи.

Сетевая технология в соединении с принципом динамического программирования теоретически может позволить не только решать шахматную задачу, но в принципе и «закрыть» эту «проблему» раз и навсегда.

12 3 4 5 6 7 8 9 10 Следующая ⇒