Нам Хаос строить и жить помогает

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

Первому из младенцев, квантовому когерентному компьютеру, была посвящена тема номера в "Компьютерре" #224. Второй - компьютер на ДНК - более похож пока на "неведому зверюшку". Третий же сын родился совсем недавно, и уже не дурак, хотя и "хаотичен" по натуре. Весть о новом процессоре, основанном на динамических системах, была поведана миру 4 сентября журналом "Sciencedaily" (www.sciencedaily.com). Сразу уточним, что речь идет о математической модели-прототипе, а не об экспериментальном образце.

Родителями процессора стали Судешна Синха (Sudeshna Sinha) из мадрасского института математики (Индия) (www.imsc.ernet.in/~sudeshna) и Вильям Дитто (William L. Ditto), глава лаборатории прикладного хаоса (звучит в духе Стругацких, но название настоящее) в технологическом институте штата Джорджия (США) (www.physics.gatech.edu/chaos). Лаборатория Дитто занимается исследованиями на стыке физики, математики и биологии. В числе тем - как исследования хаоса в динамических системах (от механических маятников до переходов Джозефсона и сердечной мышцы), так и нейронных сетей. Такое соседство не случайно: дело в том, что живые нейроны - это существенно нелинейные элементы, и из биологических исследований становится все более явным, что именно эта нелинейность и хаотичность позволяет нашему мозгу - массиву из нейронов - адаптироваться, обучаться и решать сложные задачи, недоступные современным компьютерам.

В оригинальной статье (Phys. Rev. Lett. 7sept98) описана математическая модель процессора, собранного из ячеек с так называемым детерминированным хаосом. В цепочке таких ячеек, описываемой всего одним параметром, может реализоваться бесконечное число видов динамического поведения с различным периодом. Но в то же время это поведение детерминировано - по начальному значению всегда можно вычислить конечное. Состоянием ячейки называется величина x, она определяется по рекуррентной формуле: x = 4·a·x·(1 - x); в статье Синха и Дитто а = 1 (о других значениях a - см. врезку). Каждая ячейка снабжена адаптивным механизмом: извне задается пороговое значение x* (одинаковое для всех ячеек), при превышении которого ячейка сбрасывается в состояние x = x*, а остаток передается той ячейке, с которой она связана. Если вторая ячейка была в таком состоянии, что "энергия", переданная ей от предыдущей, переводит ее в надпороговое состояние, то такая ячейка тоже сбрасывает излишек в следующую. Передача информации ("энергии") по цепочке из ячеек происходит синхронно, за время одной итерации. Ячейка в конце цепочки сбрасывает избыток в "окружающую среду". Это значение регистрируют, и оно является результатом вычисления.

В зависимости от величины x* цепочка ведет себя по-разному; при значениях, меньших 0,75, все ячейки релаксируют к x*, и избыток сбрасывается каждую итерацию; при значениях от 0,75 до 0,905 состояние цепочки изменяется циклически с периодом в две итерации; далее, при увеличении x* вплоть до 1, этот период бесконечно возрастает, удваиваясь.

Претендент на роль компьютера прежде всего должен уметь выполнять логические операции. В статье приведен пример построения логических элементов 2ИЛИ-НЕ, которых достаточно для построения всех других элементов. Для этого в цепочке из двух ячеек устанавливают определенное значение x*, при котором она работает с периодом в две итерации. То есть ячейки колеблются между двумя значениями, и на выходе цепочки появляется периодическая последовательность значений. Логические 0 и 1 в такой схеме представляются, соответственно, значениями x, меньшими и равными x*. При значениях x*, лежащих в промежутке от 0,835 до 0,905, возможно два режима с периодом 2. В первом (когда ячейки сбрасывают "энергию" одновременно, или когерентно) на выходе попеременно появляются ноль и 2·D1 (D - излишек, сбрасываемый одной ячейкой), а во втором (некогерентном) - ноль и относительно маленькое D2. При x*, близких к 0,84, D2 много меньше D1 и может считаться равной нулю. Если в обеих ячейках установить одинаковые значения, то цепочка будет работать в когерентном режиме. Если это два нуля, то на выходе первым появится значение 2·D1 (единица), а затем ноль. Если две единицы, то наоборот: сначала ноль, а потом 2·D1 (это просто математический факт, свойство такой цепочки). Если значения разные, то в зависимости от конкретного значения (0 или 1) в конкретной ячейке на выходе первым появится ноль или D2, которую мы считаем равной нулю. Таким образом, в первый момент логическая единица на выходе появляется только при двух логических нулях на входе. Именно это и требовалось получить.

В принципе, имея элементы 2ИЛИ-НЕ, уже можно строить компьютер. Но изобретение Дитто и Синха не было бы таким интересным, если бы на этом все и закончилось. В их статье описан способ кодирования натуральных чисел в излишек x - x*, а также схемы, позволяющие складывать и умножать эти числа. Для x* в пределах (0;0,75) ячейка в допороговом состоянии сбрасывает излишек каждую итерацию. Значение излишка - это однозначная ограниченная функция порога x*. В таком случае, определив единицу как отношение максимального значения излишка к максимальному числу, которое мы хотели бы закодировать, получим соответствие между порогом в ячейке и натуральным числом, туда записанным. Для сложения достаточно соединить ячейки со слагаемыми в цепочку в произвольном порядке, а результат снять с последней. Такой подход позволяет проводить сложение параллельно, объединяя выходы нескольких цепочек.

Но и это еще не все. Как уже было сказано, для порогов, больших 0,75, рассматриваемые динамические системы могут работать с любым периодом - положительной степенью двойки. Но тогда естественным решением было бы использовать такие ячейки для кодирования двоичных чисел, аналогично суммирующему ЦАП. Младший разряд кодировался бы ячейкой с наибольшим периодом, а старший - с наименьшим. А результат получится, как обычно, в виде суммы излишков, сброшенных каждой ячейкой за время, равное периоду ячейки, представляющей наибольший разряд. Необходимо только подобрать пороговые значения так, чтобы излишки, сбрасываемые всеми ячейками, были одинаковы независимо от периода ячейки. Комбинируя параллельное и последовательное соединение цепочек и отдельных ячеек, можно получить сколь угодно сложные вычислительные схемы, в том числе для параллельных вычислений. В статье предложен также алгоритм построения схемы для умножения, но мы его описывать здесь не будем, так как он является лишь естественным усложнением схемы сложения. Больший принципиальный интерес представляет алгоритм нахождения наименьшего общего кратного (НОК). Для нахождения НОК n чисел используется n цепочек с периодами, равными этим числам. Период суммы излишков этих цепочек и есть НОК. Этот пример демонстрирует, что схемы, основанные на динамических системах, обладают потенциалом для эффективного выполнения специализированных математических операций, а не только для эмуляции логических элементов и элементарных арифметических действий.

Еще предстоит понять, как сопоставлять динамические системы определенным вычислительным задачам. Авторы статьи считают, что главная особенность динамических вычислений - возможность выполнять общие вычислительные задачи. Возможность, которой в гораздо меньшей мере обладают квантовый когерентный компьютер и компьютер на ДНК.

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

В числе других проектов лаборатория прикладного хаоса проводит исследования в области искусственных нейронных сетей (ИНС) в проекте, финансируемом DARPA. Ее задача состоит в анализе и консультациях при разработке компьютера на ИНС, который строят Texas Instruments и Raytheon. Лабораторией прикладного хаоса разрабатываются средства анализа динамических свойств и самоорганизации ИНС, а также управления ИНС в реальном времени на платформе Windows NT.

Конечно, идея построения компьютера на хаотических элементах появилась не на пустом месте. С начала 90-х годов несколько групп ученых, в том числе и в России, ведут исследования по использованию детерминированного хаоса в прикладных науках, не только в информатике. Ключевой идеей является то, что хаотическое движение скрывает под собой запутанную, но хорошо упорядоченную структуру - сложное переплетение периодических траекторий. И группой Дитто найден способ малым воздействием на систему заставлять ее выбирать одну из этих траекторий (Phys. Rev. Lett. 24dec94). Самое интересное, что для этого не нужно знать математический закон, описывающий поведение конкретной системы. "Вы сможете применить этот метод к любой системе, где вы можете производить измерения", - сказал Дитто, объясняя свои результаты. Достаточно понаблюдать за системой и получить картину ее хаотического аттрактора (орбиты, к которой стремятся траектории независимо от начальных условий). Авторы сравнивают свой метод с балансированием шарика на поверхности седла: вперед или назад шарик не свалится, но необходимо слегка поворачивать седло, чтобы он не упал влево или вправо. Разработанный подход может быть применен для контроля нежелательных вибраций, например, в авиационной технике, а также для конструирования стимуляторов сердца - существенно хаотической системы. В последнем лаборатория прикладного хаоса весьма преуспела (www.physics.gatech.edu/research/acl).

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