Часть I: Методология клеточно-автоматного моделирования в контексте «дорожной карты» микроэлектроники Матюшкин И.В., кфмн, ОАО «НИИ молекулярной электроники», Москва, Зеленоград Впервые зачитывалось на школе в г.Нальчик в феврале 2013 г. Здесь уточненная версия

Содержание Шесть точек зрения на клеточные автоматы (КА) Творцы современной теории и практики КА Подходы к визуализации и аудизации КА КА в проектировании и реализации программно- аппаратных комплексов КА в проектировании и реализации программно- аппаратных комплексов Квантовые клеточные автоматы От игры к моделям, от моделей к мышлению 2 Лексическое уточнение: при переводе на английский – (cellular) automata во множ. числе, а в единственном – automaton (следуя правилам латыни)

I. Шесть точек зрения на клеточные автоматы Тезис Комментарий КА – это лишь не более чем математическая игрушка наподобие детского калейдоскопа и упражнение для молодых программистов Чтобы понять, что такое КА, нужно просто немного поиграть в игру «Жизнь» (Game of Life). Конечный автомат - фундаментальная абстракция для последовательных вычислений, КА – для параллельных Классический КА работает синхронно, однако возможны и асинхронные КА. Дж. Фон Нейман. КА – это лишь некий численный метод дискретизации модельного дифф. уравн. continuous valued cellular automata, КА Ооно-Кохомото для диффузии КА – это особый язык составления мат. моделей, описывающих пространственно распределенные системы Как же тогда находить локальные правила, чтобы система обладала желаемой динамикой? КА – раздел математики, где весьма значим вычислительный эксперимент Стивен Вольфрам, «Новый вид науки» Вся Вселенная есть гигантский КА, есть «вычисляющее пространство» Эдвард Фредкин, направление digital philosophy 3

Шестая точка зрения (продолжение): КА – «дискретный взгляд на мир» Для математики XXI-го века аппарат КА имеет такое же фундаментальное значение, как и дифференциальные уравнения в XVIII-XX вв. Значение КА сравнимо с теорией относительности Эйнштейна в физике, с теорией естественного отбора Дарвина в биологии. Фундаментальность КА подтверждается расширяющимся спектром приложений от квантовой хромодинамики до поведения толпы. Чтобы задать классический КА, нужно определить: Состояние ячейки (бит) Размерность поля и сетку КА (квадрат) Шаблон окрестности (Мура – 8 клеток плюс одна) Локальные правила перехода (local transition rules) Условия перехода для граничных ячеек (нет границ) Начальное состояние поля КА Режим работы (синхронный, не блочный) Степень однородности структуры Эти семь условий создают многообразие КА, не считая смысловой нагрузки 4

II. Творцы современной теории и практики КА Готфрид Вильгельм Лейбниц, 1646 – 1716, великий немецкий философ, один из основателей исчисления бесконечно малых, предтеча современной математической логики, автор «Монадологии» (1714), где на 15 страницах суммировано учение о монадах. Грубые соответствия: Ячейка КА монада («атом»), глобальная функция перехода принцип предустановленной гармонии Отличия от классического КА: Нет одинаковых монад, нелокальность шаблона (монада есть «живое серкало Вселенной») Майоров Г.Г. Теоретическая философия Готфрида В. Лейбница. М.:МГУ, с. «Монады вовсе не имеют окон, через которые что-либо могло бы войти туда или оттуда выйти… когда мы падаем в обморок… душа не отличается заметным образом от простой монады; но так как это состояние непродолжительно и душа освобождается от него, то она есть нечто большее, чем простая монада» Природу Лейбниц толковал как привычку Бога 5

Джон фон Нейман (John von Neumann), , Один из крупнейших математиков XXв. (эргодическая теория и т.д.), дал алгебраическую формулировку (на языке теории операторов) квантовой механики, изобретатель одноименной архитектуры ЭВМ, основоположник теории КА (1953) КА как матрица конечных автоматов / процессоров, обменивающихся сигналами с равными задержками. Ниже – правила для автомата Неймана с 29-ю состояниями. >200 тыс. ячеек – самовоспроизведение. В гг. работал в атомном проекте Оппенгеймера «вычислителем» на EDVAC – ENIAC, что привело к ранней смерти от рака мозга. Первые работы по нейронным сетям, в частности, Уолтера Питтса Логическое исчисление идей, относящихся к нервной активности (1943) впечатлили Неймана. Если Бэббидж искал аналогии между блоками счетной машины и производственными структурными единицами ("мельница", "склад"), то фон Нейман находил эти аналогии в живом организме («орган», «нейрон»). J. von Neumann, Theory of Self-Reproducing Automata, A. Burks, Ed., University of Illinois Press, 1966 на русском: 1971 и

В предлагаемой книге наряду с однородными структурами также описаны более общие модели однородных структур, отличающихся от описанных наличием свободных выходов и выходов у образующих автоматов. Кудрявцев В.Б., Подколзин А.С., Болотов А.А. Основы теории однородных структур. – М.: Наука, – 296 с. В.З. Аладьев. Классические однородные структуры. Клеточные автоматы, Fultus Publishing, Edward F. Moore. "Gedanken-experiments on Sequential Machines," pp. 129 – 153, Automata Studies, Annals of Mathematical Studies, no. 34, Princeton University Press, Princeton, N. J., 1956 Конечный автомат (finite state machine) Теория конечных автоматов, несмотря на логическое предшествование, развивалась одновременно с КА и почти теми же людьми из Принстона, в рамках направления кибернетики, AI/ALife Отсюда рукой подать до игр (коллективного поведения) в мультиагентных системах Э. Мур: проблема одновременных залпов (firing squad synchronization problem), теорема о садах Эдема М.Л. Цетлин. Конечные автоматы и моделирование простейших форм поведения // УФМ, т.18, 4,с.3-28, 1963 Psakhie, S.G. et al. (1995). «Method of movable cellular automata as a tool for simulation within the framework of mesomechanics». Russian Physics Journal, 38 (11). 7 МИХАИЛ ЛЬВОВИЧ ЦЕТЛИН( ) Крупный советский ученый и выдающийся инженер, много сделавший в таких разных областях, как математика, физика, биология и медицина (например, им был разработан протез управляемой кисти руки). Открыл новое продуктивное научное направление - коллективное поведение автоматов, которое сейчас во многом определяет перспективные пути развития систем искусственного интеллекта. Один из основоположников отечественной кибернетики, подвергавшейся в те годы незаслуженной критике; например, с его помощью было решительно изменено отношение к структурной лингвистике.

Конрад Цу́се (нем. Konrad Zuse), , Пионер немецкого компьютера, Остался в разрушенной Германии (ФРГ), чтобы продолжать работу над ЭВМ серий Z1-Z2-Z3-Z4 ( ), на полгода опередив Неймана. Накопив деньги за счет продажи ЭВМ в Европе, отдался живописи и утопии «компьютерного социализма», т.е. плановой экономике с тотальной компьютеризацией. В 1969 году он издал книгу «Вычисляющее пространство» (нем. Rechnender Raum), переведённую через год сотрудниками MTI. На её почти ста страницах он описывает тройной союз «математика – физика – специалиста по обработке данных», в дилемме «аналоговая VS цифровая» ЭВМ выступает на стороне последней, и в рамках этой парадигмы пытается через КА дискретизировать уравнения Максвелла. 8

M. Gardner. The fantastic combinations of John Conway's new solitaire game "life" // column Mathematical games, Scientific American, v. 223 (October 1970): Мартин Гарднер, Популяризатор КА в нашей стране, 3-я глава книги (1988) Джон Хортон Конвэй, John Horton Conway (1937 -), Английский математик с широким спектром интересов, особенно в топологии и теории игр; в 2004 г. Сформулировал и доказал (вместе с Коэном) «теорему свободной воли» в квантовой механике: если экспериментатор свободен, то и частица свободна; в 1986 занял место Неймана в Принстоне; сейчас читает лекции по философии Изобрел КА «Игра Жизнь» (Game of Life, 1970), пытаясь улучшить автомат фон Неймана... only after the rejection of many patterns, triangular and hexagonal lattices as well as square ones, and of many other laws of birth and death, including the introduction of two and even three sexes. Acres of squared paper were covered, and he and his admiring entourage of graduate students shuffled poker chips, foreign coins, cowrie shells, Go stones or whatever came to hand, until there was a viable balance between life and death.... только отклонив много паттернов, треугольные и гексагональные решетки, как и квадратные, и многие другие законы рождения и смерти, включая введение двух и даже трех полов. Акры бумаги в клетку были исписаны, и он вместе с окружающими его аспирантами перетасовывал фишки для покера, иностранные монеты, раковины каури, камнями Го и прочее, пока не был найден верный баланс между жизнью и смертью. 9

Эдгар Франк Кодд (Edgar Frank "Ted" Codd), , Будучи сотрудником IBM, разработал концепцию реляционных баз данных и нотацию Бойса-Кодда, автор КА универсального конструктора Кодда (1968), улучшившего результат Неймана (8 состояний вместо 29), автор первого учебника: Codd, Edgar F. (1968). Cellular Automata. Academic Press, New York. Кристофер Лэнгтон, (Christopher Langton), Основатель направления кибернетики Artificial Life (1989), связанного с КА; предложил использовать - параметр для априорной оценки «эффективности» правил перехода КА, автор (1986) двумерной машины Тьюринга «муравья Лэнгтона» (дается как КА) и КА «петля Лэнгтона» Christopher Langton, "Self- Reproduction in Cellular Automata", Physica D 10, 1984, pp КА WireWorld («Мир – проволока») приобрел популярность с момента релиза в 1987 г. программы Брайана Силвермана Phantom Fish Tank (программа для обучения детей особенностям языку Лого и «черепашьей графики») и заметки Дьюдени. Ячейка может пребывать в одном из 4-х состояний: «непроводящее/пустота», «голова» (электрона), «хвост» и «проводник». A. K. Dewdney. Column "Computer Recreations": WireWorld // Scientific American, January, 1990.

Разработчик системы САМ6, придумал идею окрестности М. (блочно- поворотные КА) для моделей диффузии (80-е) Норман Марголус (Norman Margolus), Стивен Вольфрам, (Stephen Wolfram) Ученый-бизнесмен Автор бестстеллера- компиляции на 1379 стр (2002); Двоичные 1D-КА и нотация правил (напр.,rule 110); Классификация КА на 4 типа; Томазо Тоффоли (Tommaso Toffoli), Продолжатель идей Фредкина, Автор (вместе с Марголусом) книги «Машины КА» (1987/1991 – en/ru), автор вентиля Тоффоли Занимается физическим аспектом вычислимости, соавтор теоремы Левитина-Тоффоли-Марголуса (1998) о пределе скорости вычислений, доказал ряд теорем по обратимым КА (в т.ч. биллиардным КА) Эд Фредкин (Edward Fredkin), 1934 – В 19 лет после года обучения в CalTech выбрал карьеру пилота истребителя, разработчик машины PDP-1 (1959), в молодости хакерствовал, был директором проекта MAC (1971/74) по искусственному интеллекту в MTI, автор сайта изобретатель КА Фредкина (репликатор), а также вентиля Фредкина. Шефствовал над Тоффоли и Марголусом. Fredkin, Edward; Toffoli, Tommaso (1982), "Conservative logic", Int. J. of Theoretical Physics 21 (3-4): 219–253 11

12 Цит. по: Аноприенко А.Я., Коноплева А.П., Моделирование постбинарных клеточных автоматов // Матер. конф. «Моделирование-2010» (13-14 мая 2010 года, Киев). С

III. Подходы к визуализации и аудизации КА КА часто используются непосредственно с целью создания образов искусства (арт- визуализация, алгоритмическая музыка ). Scientific Visualization – новая отрасль науки, посвященная методам визуализации данных (1987). Полезные ссылки: У. Боумен. Графическое представление информации, изд. «Мир», Москва, 1971, 225 с.; literacy.org/periodic_table/periodic_table.html Размерность КА еще не фиксирует размерность модели визуализации; Нужно относиться к хранящейся в памяти или на жестком диске матрице КА как к неопределенной метафизической сущности, допускающей многообразие вариантов представления; Методы Data Mining и внедрения математических структур для КА еще ожидают своего применения 13

Если обратиться к КА- моделям нанотехнологий, то при описании процессов кристаллизации вещества или образования пор МКА желательно реализовывать интеллектуальные функции определения числа кластеров в системе КА, момента (и условий) перколяционного порога и т.д. В конечном счете КА- модель только тогда имеет научное значение, когда она в состоянии предсказывать макроскопические параметры, а для этого каким-либо способом нужно агрегировать микроскопические и непосредственно доступные параметры КА- данных. КА даже могут использоваться для морфинга 3D-объектов: Sudhanshu Kumar Semwal, K. Chandrashekhar. Cellular Automata for 3D Morphing of Volume Data // The 13-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision'2005: Матюшкин И.В. и др. // Компьютерные исследования и моделирование (2012)

Рис.1. Эволюция r-пентамино в игре «Жизнь». Левая колонка (a,c,e) – классическая визуализация для 25-го хода (a,b), для 175-го хода (с,d) и для 1103-го хода (e,f). Правая колонка – визуализация средним арифметическим, причем (b,d) даны для цветовой схемы А, (f) – для цветовой схемы B (см. Приложение). На рис. (a) кадрированно показано исходное r-пентамино, занимающее 5 клеток. Диагональный след отвечает траектории полета «планера». Условие «линии смерти» на границах КА приводит к тому, что улетевшие «планеры» порождают белые точки на границах рис. (e,f). Эволюция r-пентамино в игре «Жизнь». Левая колонка (a,c,e) – классическая визуализация для 25-го хода (a,b), для 175-го хода (с,d) и для 1103-го хода (e,f). Правая колонка – визуализация средним арифметическим, причем (b,d) даны для цветовой схемы А, (f) – для цветовой схемы. На рис. (a) кадрированно показано исходное r-пентамино, занимающее 5 клеток. Диагональный след отвечает траектории полета «планера». Условие «линии смерти» на границах КА приводит к тому, что улетевшие «планеры» порождают белые точки на границах рис. (e,f). Метод изометрической проекции в МКА SoftCAM. Сверху: случайные конфигурации игры «Жизнь» (на стене xz – состояние в момент t– 1, на стене zy – состояние в момент t, на полу xy – светлыми вокселами показаны клетки, изменившие состояние на текущем ходе). Снизу: три среза в произвольной точке (x,y,z) битового 3D КА. 15

Аудизация (audization) – сопоставление данным по некоторому алгоритму звукового ряда, в частности, речи и музыки (см. также «алгоритмическая музыка»). Термин пока малоупотребителен. В 1779 году австрийский композитор Максимилиан Штадлер выпустил наборы таблиц тактов для сочинения менуэтов с помощью игральных костей. Но самая известная работа «Музыкальная игра в кости», объяснявшая, как с помощью двух игральных костей сочинять сколько угодно немецких вальсов, «вовсе не зная музыки»; она была впервые опубликована в 1792 году, через год после смерти Моцарта, которому и приписывалось авторство этого сочинения. И.С. Бах нотами выложил свое имя B-A-C-H Иосиф Шиллингер ( ) Яннис Ксенакис ( ) Лежарен Хиллер ( ) Брайан Ино (1948-) КА способны генерировать периодические фигуры (а любая музыка содержит повторяющиеся части) и вместе с тем способны к хаотическому поведению. Простая схема генерация midi-звукоряда с помощью 1D КА. L=3. Простая схема генерации wav-звукоряда с помощью 1D КА. Три временных отрезка умещаются в одном такте (шаге) КА. S=8, состояние ячейки – 1 байт. 16

В 1998 г. КА-аудизация была использована в программе Virtual Waves, впоследствии приобретенной компанией Synoptic - Популярность приобрел Java-апплет проекта На рис. скриншоты: САsounds ( и Cellular Automata pieces ( (2 фрагмента) CAMUS: Cellular Automata music generator -- Otomata : Cellular Automata Music Generator -- Первые шаги были сделаны С.Вольфрамом в 80-е гг. и отчасти поэтому 1D-КА стали использоваться для КА-аудизации. ( нужен проигрыватель от С.Вольфрама ). В нач х гг. Эдуардо Мирандо (Sony Corp.) опубликовал ряд статей на эту тему и создал для инструмент CAMUS. Существует хороший обзор: Digital Creativity 2005, Vol. 16, No. 3, pp. 165–

Когда создается какое-нибудь мультимедиа-приложение, разработчики часто заходят в тупик, сталкиваясь с проблемой фоновой музыки. Такая музыка должна по возможности варьироваться, к тому же есть немало проблем с авторскими правами и объемами памяти для хранения мелодий. Выход из этой ситуации видится прежде всего в использовании различных генераторов сэмплов. Намного выгоднее генерировать музыку «на лету», причем собственную, чем подкачивать чужую через сеть. Недавно (2010) фирма Novation выпустила USB-контроллер Launchpad, предназначенный для живой работы с программой Ableton Live, сделав шаг на пути к простому и наглядному управлению музыкальным редактором. Контроллер имеет 8x8 назначаемых клавиш и кнопки выбора режимов, которые позволяют полностью контролировать программное обеспечение. В 2009 г. один любитель запрограммировал аудизацию игры Конвэя для этого устройства /3015/ c.com/midi-controllers- digital-dj/launchpad Цена новинки – 7000 р, целевая аудитория – диджеи 18

IV. КА в проектировании и реализации программно-аппаратных комплексов Широко применяемые в настоящее время методы, основанные на решении систем дифференциальных уравнений в частных производных, оказываются недостаточно эффективными при моделировании процессов создания структур, размер которых сравним с размерами атомных дефектов поверхности, а также при моделировании многокомпонентных систем [1]. В микроэлектронике КА применялись, например, для моделирования процесса травления при получении пористого кремния [2] или процесса термического окисления кремния [3]. C нач. 90-х гг. XX в. появились публикации, посвященные применению КА в топологическом проектировании, например, при исследовании планарных графов в задач уплотнения упаковки элементов СБИС [4]. В функционально-логическом проектировании приложения КА связаны c созданием встроенных тестовых структур и задачей аппаратной генерации псевдослучайных чисел [5]. Нашли применение КА и в криптографии [6, 7]. Отдельным направлением является разработка на басе КА специализированных микропроцессоров для высокоскоростной обработки графической информации в режиме реального времени [8, 9]; здесь в одно целое связаны алгоритмическая и аппаратная составляющая задачи [10]. И наоборот, можно поставить вопрос, какими аппаратными средствами может быть реализован тот или иной (или даже семейство) КА? 19

1.А. Н. Агафонов и др. Разработка физических принципов и алгоритмов компьютерного моделирования базовых процессов формирования микроструктур методами вероятностного клеточного автомата // Вестн. Сам. гос. техн. ун-та. Сер. Физ.-мат. науки, 1(14) (2007), 99– Than O., Buttgenbach S. Simulation of anisotropic chemical etching of crystalline silicon using a cellular automata model // Sensors and actuators. Part a, 45(1):85, October G. Sirakoulis et al. A new simulator for the oxidation process in integrated circuits fabrication based on cellular automata // Materials Science and Engineering, 7, 1999, pp Fawaz S. Al-Anzi. Efficient Cellular Automata Algorithms for Planar Graph and VLSI Layout Homotopic Compaction // International Journal of Computing and Information Sciences, Vol.1 1, 2003, paper Biplab K. Sikdar et al. Cellular Automata Based Test Structures with Logic Folding // Proc. of 18th International Conference on VLSI Design (VLSID'05), 2005 – p Benny Applebaum, Yuval Ishaiy, Eyal Kushilevitz. Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature? // Proc. of Conference Innovations in Computer Science (ICS2010), held in Beijing, China, January 5-7, Somanath Tripathy, Sukumar Nandi. LCASE: Lightweight Cellular Automata-based Symmetric-key Encryption // International Journal of Network Security, Vol.8, No.2, 2009, p Takeshi Ikenaga. Highly-parallel Two-dimensional Cellular Automaton Architecture and its Application to Real-time Image Processing – PhD Thesises – Waseda University, Japan, 2001, 165c. 9. Pradipta Maji et al. Theory and Application of Cellular Automata For Pattern Classification // Fundamenta Informaticae 58 (2003) 321– Woudenberg M. Using FPGAs to Speed Up Cellular Automata Computations / Master's thesis for University of Amsterdam

V. Квантовые клеточные автоматы Принцип Ландауэра гласит, что независимо от физики и технологии вычислительного процесса при потере одного бита информации в процессе вычисления выделяется энергия, по меньшей мере равная k b Tln2 (здесь и далее: k b – постоянная Больцмана, T – абсолютная температура). Каждый транзистор теряет 1 бит информации всякий раз, когда срабатывает, а выделяемая им при этом энергия на практике оказывается примерно в 500 раз больше установленного Ландауэром фундаментального минимума. Вычисления, основанные на принципе Шеннона Фон-Неймана Ландауэра (развивающем принцип Ландауэра) и использующие принцип неопределенности Гейсенберга, показывают, что если, согласно плану ITRS, к 2016 году будет использоваться 22- нм технология, то выделение тепла процессором даже при использовании идеальных материалов составит 5–10 млн. ватт/см 2 R. W. Keyes and R. Landauer. Minimal energy dissipation in logic // IBM J. R&D, vol. 14, Mar – pp. 152–

Место тематики квантовых клеточных автоматов (QCA) в развитии наноэлектроники. QCA предстает одновременно и как принцип архитектуры/вычислений (A – automation), и как класс приборов (A – automata). QCA следует определить как физическую структуру, реализующую в строгом смысле классическую функциональную модель клеточного автомата (CA) и содержащую четко различаемые ячейки микро- или наноразмерного масштаба, для поведенческого описания которых существенны законы квантовой механики. CNN= cellular non-linear (neural) network Концепция коннекционизма: «Связи – все, элементы – ничто». CNN предполагает своим элементом процессор, а модель QCA/QDCA – ячейку-кубит. Прогнозируется до миллиона процессоров на 3D-чипе (уже сейчас созданы многоядерные процессоры с 1000-ю ядрами): Chagaan Baatar, Wolfgang Porod, Tam´as Roska. Cellular Nanoscale Sensory Wave Computing – Springer, 1st Edition., 2010, VIII, 249p. Матюшкин И.В. Квантовые клеточные автоматы // Электронный научный журнал «Исследовано в России», стр , pdf 22

Anton Zeilinger, 1988 R. Feynman. Simulating physics with computers // Int. J. Theor. Phys. 21 (1982) G. Grossing and A. Zeilinger. Quantum cellular automata // Complex Systems 2 (2), 1988: pp. 197–208 and 611–623. Craig S. Lent et al. Quantum cellular automata // Nanotechnology 4 (1993) Wolfgang Porod. Quantum-dot devices and quantum-dot cellular automata // J. Franklin Inst. Vol. 334B, #5/6, pp , 1997 Richard Phillips Feynman, 1965/1982 Craig S. Lent, 1993 Wolfgang Porod, 1997 Существует еще и третья точка зрения на QCA как математическую модель квантово-размерного устройства и/или системы, например, решеточного «газа» (quantum lattice gas). Такая модель (Ватроуза – ван Дама) должна по необходимости содержать пси-функции для описания состояния ячейки и работать с матрицами перехода между состояниями. Второе условие – нулевое (основное, ground) состояние в ячейке и во всей её окрестности обязательно порождает нулевое. Спиновая модель Изинга показывает пограничный случай между классичным CA и QCA. QDCA=quantum dot cellular automate Исторически произошел синтез довольно старой идеи параллелизма вычислений и клеточных автоматов 40-хх гг. XXв. и результатов исследований в теоретической физике (с 90-х гг. XXв. по настоящее время) ансамблей квантовых точек, в том числе и неатомарных (на основе нанокристаллов). С этим связана трехзначность и противоречивость дефиниции QCA. Большой вклад в развитие проблематики QCA внесла исследовательская группа университета Нотр-Дам (Индиана, США), финансировавшаяся в рамках программ DARPA, а также проект QUADRANT, осуществленный в гг. в соответствии с программой Еврокомиссии по MEL-ARI (Исследовательская Инициатива развития микроэлектроники) и объединивший усилия университетов Пизы, Кембриджа, Тюбингена и других городов Европы и Северной Америки, включая Нотр-Дам. Последние 5 лет наблюдается стагнация QCA-тематики, быть может, временная. 23

Ячейка QCA Лента Провод из 4-х QD ячеек, повернутых на 45 0 (слева) и инвертор из ячеек с 6-ю QD (справа) Элемент majority, взятый для вычисления булевых функций A B, A B и (A B). Схема устройства элемента majority и его условное графическое обозначение QCA-схемная реализация полного одноразрядного сумматора Сейчас уже реализованы несколько вариантов QCA (металлические, магнитные и молекулярные), с помощью которых выполнены простейшие логические функции и схемы, в частности, OR/AND/XOR, «голосования большинства», сумматоры, триггеры и мультиплексоры 2424

В 1994 г. Лент разработал (без физической реализации!) модель одноразрядного сумматора с тремя входами, содержащем на площади 1.5 мкм 2 более 100 ячеек QCA при размере QD 10 нм, который обладал ультранизким энергопотреблением и быстродействием в терагерцовом диапазоне; для реализации такого логического элемента в классическом исполнении понадобилось бы около 30 транзисторов. В более абстрактном виде преимущества QCA над КМОП-базисом были суммированы Лентом в его первой работе: устранение необходимости многослойной металлизации за счет локальности взаимодействия между ячейками, которое также не требует энергетических затрат на перенос/переключение сигнала внутри ячейки, а также за счет снятия потребности в существенном энергопереносе внутрь массива QCA (концепция концевых вычислений); ультравысокая плотность упаковки логических элементов (если принять проектную норму за 10 нм, а линейный размер ячейки за 50 нм, то плотность составит около бит/см 2 ); ультранизкая диссипация энергии на уровне Вт/бит или В на переключение состояния бита, что обусловлено нахождением ячейки в одном из двух основных (ground) энергетических состояний и близостью возбужденного состояния (в расчетах предполагается функционирование QCA при температуре вблизи 0К); ультрабыстрые вычисления за счет того, что релаксация внутри ячейки достигается фонон- фононными и электрон-фононными взаимодействиями; в частности, время переключения элемента majority оценивается в пс. В 2007 г. экспериментально был реализован QCA на основе GaAs/AlGaAs. Возможности реализации полупроводниковых QCA, совместимых технологически с базовыми процессами микро- и наноэлектроники, до сих пор остаются недооцененными. 25

Микрофотография и схема ячейки металлического QCA. Красными кругами показаны 4 островка алюминия, фиолетовыми – островки алюминия, необходимые для электрометрических измерений. Туннельные переходы между QD показаны двумя смежными полосками. Главное преимущество заключается в относительной простоте технологического маршрута их изготовления, предполагающего всего три базовых операции, а также хорошей однородности ячеек (сопротивление перехода варьирует в пределах 20-30%) и высоком проценте выхода годных. Основной недостаток связан с необходимостью поддерживать криогенные температуры из-за невысокой (в сравнении с k b T) энергии, нужной для активации Al QD – эВ. Схема ячейки магнитного QCA (слева) и фотография 64-х наномагнитного QCA- провода, полученная с помощью атомно-силовой и магнитно-силовой микроскопии (справа) Достоинство этого класса QCA состоит в функционировании при комнатной температуре, но главным недостатком является большая инерционность (в частности, максимальная частота переключения сигнала оценивается в к Гц). Однако в редакции Маршрутной карты 2009 г. магнитные QCA рассматриваются перспективным направлением «логики на основе наномагнитов» Наиболее перспективным считается исследование молекулярных QCA. Основная их идея заключается в способности молекул хранить заряд, причем для переноса заряда требуются заметно б Ольшая энергия активации, чем k b T, и нет необходимости в протекании токов между молекулами. Поскольку размер молекулы обычно лежит в пределах 1-2 нм (что потенциально дает ультравысокую плотность кубитов см -2 ), то емкость С такой молекулярной структуры мала, а энергия активации оценивается величиной e 2 /C. Одна большая молекула может репресентировать собой полностью ячейку QCA Лента. 26

Можно сформулировать три общих требования к молекулам, используемым в QCA: Молекула должна обладать по крайней двумя стабильными зарядовыми конфигурациями, т.е. быть бистабильной; как правило, присутствие металлов (или групп) с переменной валентностью или возможность окисления/восстановления стерически удаленных атомарных комплексов обеспечивает такое требование; Молекула должна химически контактировать, т.е. образовывать прочную химическую связь, с подложкой (как правило, с кремниевой); Зарядовая конфигурация молекулы может быть изменена под влиянием соседней молекулы посредством кулоновского взаимодействия Структура и электронная плотность, рассчитанная ab initio, для молекулы катиона декатриена. Первое требование означает присутствие на профиле энергии Гиббса двух минимумов и одного максимума, лежащего между ними. При реализации второго требования необходимо учитывать, чтобы изменения конфигурации групп переменной валентности не сказывались на прочности связи всей молекулы с кремнием. Заметим, что наличие контакта молекулы с подложкой заметно усложняет расчеты ab initio таких молекул. На рис. показан один из кандидатов, а именно 1,5,9 - катион декатриона, три двойные С=С – связи соответствуют трем QD и обуславливают три устойчивых состояния «0», «1» (активные) и «null» (основное); энергия активации составляет 0.15 эВ (соответственно величина поля тайминга составляет несколько В/нм), а время переключения равно примерно с. 27

Среди кандидатов на роль активной молекулы рассматривались: 1,4 – диаллилбутан катион (молекула короткая, размером чуть более 0.7 нм, и ячейка Лента реализуется четырьмя аллильными группами на двух молекулах при энергии активации E kink =0.55–0.65 эВ); Органическое соединение кобальта с четырьмя ферроценовыми группами {(η 5 -C 5 H 5 )Fe(η 5 -C 5 H 4 )} 4 (η 4 - C 4 )Co(η 5 -C 5 H 5 ) 2+ (ячейка Лента реализована одной молекулой); Фталоцианин кремния (группа фталоцианинов широко применяется в фармакологии, а также есть попытки использовать их в солнечной энергетике); Эндоэдральные фуллерены (спин атома, захваченного внутри фуллерена, например, 60, обеспечивает возможность магнитно-дипольного взаимодействия кубитов, а реализация логических функций отличается от схемы Лента и основана на чередовании двух или трех типов эндоэдральных фуллеренов) – возможно, следует выделить такие QCA, связанные с учетом спина ядра атома, в отдельный класс. Общий вид молекулярного QCA. Под поверхностью кремния с присоединенными к нему молекулами декатриена располагаются электроды управления, несущие сигналы линий А, В, С, D (вычисляется булева функция F(A, B, C, D)) и электроды тайминга. Возникает вопрос, как неразрушающе считывать состояния ячеек молекулярного QCA? 28

Другой, даже более важный вопрос: как организовывать и как физически реализовывать тайминг (timing/clocking)? Схема К. Лихарева трассировки нанопроводов для гибридных наноприборов. Классическая четырехфазная схема тайминга (справа), поданная на закольцованную реализацию элемента majority (слева). В первую четверть такта проводник С 0 устанавливает фазу RELEASE, С 1 – HOLD, С 2 – SWITCH, C 3 – RELAX. Разной интенсивности серого цвета показаны ячейки разных зон. «Оконная» концепция параллелизма вычислений в QCA. 29

Лент показал, что классические вычисления могут быть реализованы с помощью QCA на основе ячеек из 4-6 квантовых точек (что породило волну публикаций, связанных с соответствующими САПР и вопросами обратимости вычислений, тепловыделения, исчисления задержек и трассировки в QCA). Но достигнуто это было за счет придания QCA черт псевдоодномерности модели «Мира-проволоки», за счет увлечения квантовыми механизмами меж- и внутриклеточного взаимодействия. Такие конструкции, как QCA-провод, по нашему мнению, являются паллиативом и компромиссом, предполагая направленность информационного потока, а значит, реализовывают последовательные вычисления. Тем самым искусственно снижается и затеняется перспектива параллелизма вычислений, заложенная изначально в QCA. Иными словами, в термине «квантовые клеточные автоматы» следует больший акцент делать на слове «клеточные», а не «квантовые». Остается недооцененной, в частности, самими её авторами, идея концевых вычислений. Обобщая, можно предложить разделить по функциональной роли ячейки QCA на три группы : примерно 5-10% ячеек удерживают свое состояние неизменным, являясь «окном» ввода информации в QCA; примерно 5-10% ячеек QCA предоставляют для считывания/детекции свое квантовое (например, зарядовое) состояние, являясь «окном» вывода информации; остальные 80-90% ячеек управляются только схемой тайминга, а их массив служит для низкоуровневой обработки информации. Такое понимание идеи концевых вычислений предполагает отсутствие вектора переноса информации (в частности, следует отказаться от наивно-пространственного представления о расположении ячеек входа и выхода на противоположных концах QCA), а также преднамеренный отказ от контроля за состоянием всех ячеек QCA. Последняя особенность, обусловленная желанием снизить диссипацию энергии, а для молекулярных QCA и вовсе необходимая ввиду влияния процесса измерения на волновую функцию кубита, придает дополнительные черты «квантовости» QCA, т.е. по сути дела мы не будем знать в принципе, что происходит внутри QCA в процессе вычисления. Однако надо отчетливо понимать, что столь радикальная смена парадигмы вычислений предполагает интенсивную работу математиков (несмотря на достигнутые ими успехи, например, при установлении факта Тьюринг-полноты игры Конуэя). Иными словами, сложные физические процессы, происходящие по совокупности ячеек QCA, несомненно, означают трансформацию глобального информационного состояния QCA, но сможем ли мы направлять это преобразование в нужном направлении? Не исключен и отрицательный ответ, и тогда нам придется вернуться в «Мир-проволоку». Одно из возражений против QCA-провода состояло в возможности неуправляемого обратного, т.е. противоположного по направлению распространения сигнала, влияния ячеек друг на друга. 30

VI. От игры к моделям, от моделей к мышлению Разделенный КА (partitioned CA) Каждая ячейка разбита на три субъячейки: левую, среднюю и правую. Последующее состояние ячейки зависит от состояний: правой субъячейки левого соседа, собственной средней субъячейки и левой подъячейки правого соседа Ячейка обратимого QCA Дельгадо, разделенная на регистры: состояния (state), вентиля (gate), таймер (clock) и активности (active). Carlos A. P´erez-Delgado and Donny Cheung. Local Unitary Quantum Cellular Automata // arXiv: v1 [quant-ph] 31 Aug Важное отличие КА от нейронной сети: формально можно прописать неизменной или почти неизменной часть состояния ячейки, а значит де факто ввести ПАМЯТЬ, что является необходимым условием мышления в системах искусственного интеллекта 1) Введение глобальных переменных КА, от которых зависит путь исполнения локальных функций перехода; 2) синхронизация работы двух КА (coupled CA) по принципу «ведущий-ведомый», причем поля КА могут не совпадать по геометрии; 3) Исследование иерархии КА – сходное описывается в Complex Systems, 17 (2007) 47–64; 31