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

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

После перехода на транзисторную технологию и определения фирмой Intel процессора как отдельного чипа в 1971 году история процессоров вошла в довольно спокойное русло. Все, что происходило в этой области за последние тридцать с лишним лет, концептуально сводится к росту числа транзисторов с 2,3 тысячи в процессоре Intel 4004 (1971 год) до более чем 410 миллионов в процессоре Intel Madison Itanium-2, чья презентация состоялась на конференции DAC в 2003 году.

Инженер, а впоследствии директор ряда исследовательских лабораторий, Гордон Мур был первым, кто обратил внимание на тривиальность развития событий на рынке компьютеров. В 1965 году в своей знаменитой статье об увеличении числа элементов в интегрированных платах он отметил тенденцию экспоненциального роста количества транзисторов за период 1959–65 гг., а также предположил, что в 1975 году количество транзисторов в процессоре возрастет до 65 тысяч. Мур не давал никаких прогнозов на более поздний срок, но предугадал экспоненциальный характер скорости роста количества транзисторов. Однако впоследствии наблюдение Мура было обобщено на период после 1975 года, и за ним закрепилось название "закон Мура", хотя в обычном смысле законом оно не является.

Закон Мура не может работать вечно, и на то есть много причин. Не касаясь проблем синтеза схем для новых процессоров, физики размещения транзисторов, проблем с охлаждением и прочих важнейших аспектов, связанных с проектированием, производством и использованием новых чипов, упомянем о стоимости запуска фабрики, которая выпускала бы новые процессоры. Оказывается, фабрика, производящая процессоры на (пока еще) новой 90-нанометровой технологии, обходится вдвое дороже фабрики, производившей чипы на предыдущей, 130-нанометровой технологии. Что же касается стоимости фабрик, которые предположительно будут работать на проектируемых 70- и 55-нанометровых технологиях, то каждая, по предварительным расчетам, будет еще в два раза дороже. Вопрос упирается в то, смогут ли компании продать столько процессоров, чтобы финансировать строительство подобных производств. Инженеры ведущих изготовителей, с которыми автор смог поговорить лично, скептически относятся к будущему закона Мура и предрекают снижение скорости роста производительности процессоров именно в связи с удорожанием новых фабрик. Возможно, этот эффект проявится уже в ближайшие два-три года, когда обнаружится, что 90-нанометровая технология слишком долго задержалась на рынке. С другой стороны, пока лишь малый процент населения планеты обладает компьютером, поэтому ситуация с расширением рынка продаж вполне может оказаться разрешимой. Обратимся к принципиально неразрешимым вопросам.

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

Современные процессоры выделяют очень много тепла. Это хорошо видно, например, при сравнении размеров кулеров для, скажем, серии процессоров 486 и Pentium III. Известен также забавный опыт: достаточно одиннадцати минут, чтобы на работающем процессоре Athlon XP1500+ пожарить яйцо (www.phys.ncku.edu.tw/~htsu/humor/fry_egg.html). Попытаемся разобраться, откуда берется проблема с отводом избыточного тепла и преодолима ли она.

В настоящее время главная причина выделения тепла — несовершенство материалов. Тем не менее опыт последних тридцати лет показал, что за счет использования новых материалов удавалось поддерживать экспоненциальный рост производительности компьютеров, и гипотетически можно было бы свести тепловыделение почти к нулю. Камень преткновения вовсе не в несовершенстве материалов, а в так называемом принципе Ландауэра (Rolf Landauer), основывающемся на принципе неубывания энтропии замкнутой системы, коей в данном контексте является совокупность компьютера и источника питания. Принцип Ландауэра¹ гласит, что независимо от физики и технологии вычислительного процесса при потере 1 бита информации в процессе вычисления выделяется (как минимум) энергия, равная kT*ln 2 Дж. Здесь k — константа Больцмана (примерно 1,3807*10–23 Дж/К), Т — температура в абсолютной шкале, при которой ведутся вычисления (комнатная температура примерно равна 300 градусам Кельвина). Эта энергия настолько мала, что кажется несущественной. Однако даже поверхностный анализ объема энергии, выделяемой в связи с потерей информации, проведенный для процессора Intel Madison Itanium 2, показывает, что в рамках современной технологии просто отбрасывать или списывать на погрешность измерений ее уже нельзя. Каждый транзистор теряет 1 бит информации всякий раз, когда срабатывает (транзистор имеет два входа и один выход; имея информацию о наличии тока на выходе, нельзя сказать, какой был ток на входах, а значит, информация потеряна), а выделяемая им при этом энергия оказывается примерно в пятьсот раз больше установленного Ландауэром минимума. Искусственным образом можно заставить сработать около 75% всех транзисторов на каждом такте. Частота работы процессора — 1,5 ГГц, а количество транзисторов — 410 миллионов. Учет всех перечисленных факторов дает тепловыделение, связанное с потерей информации, порядка 0,147 Вт, что само по себе, конечно, не критично, но в связи с вышеупомянутым законом Мура наводит на определенные подозрения.

Работающий в США российский исследователь Виктор Жирнов (Victor Zhirnov) недавно проанализировал ITRS-2001 (International Technology Roadmap for Semiconductors), план-проект развития транзисторной технологии после 2001 года. Его вычисления, основанные на принципе Шеннона — Фон-Неймана — Ландауэра (развивающем принцип Ландауэра) и использующие принцип неопределенности Гейзенберга, показывают, что если, согласно плану ITRS, к 2016 году будет использоваться 22-нанометровая технология, то выделение тепла даже при использовании идеальных материалов составит 5–10 миллионов ватт на квадратный сантиметр поверхности процессора². Для сравнения, мощность обыкновенной домашней лампочки 60–100 Вт (трогать горящую лампочку голой рукой не рекомендуется), а Солнце выделяет только (?!) 6000 Вт/см2. Что же касается скорости отвода тепла, то теоретический потолок при использовании самого перспективного из известных конвективного способа охлаждения жидкостью под давлением составляет около 1000 Вт/см2, а практически даже охлаждение со скоростью 93 Вт/см2 пока относится к разряду проблем с неизвестным решением. Итак, обеспечить необходимое охлаждение принципиально невозможно, а значит, развиваться технологии CMOS осталось недолго. В научном же смысле она уже изжила себя.

Какие же имеются альтернативные способы вычисления и альтернативные технологии создания вычислительных устройств? Разберемся сначала с первыми. Вынесенный нами из анализа транзисторной технологии урок гласит: для достижения высокой производительности надо делать вычисления без потери информации, то есть обратимо. Беннет (Charles Bennett) показал, что нулевая потеря энергии возможна только при использовании обратимых вычислительных блоков³. Обратимый вычислительный блок позволяет точно восстановить входные данные по выходным данным. Например, блок, вычисляющий булево отрицание NOT (NOT(0)=1, NOT(1)=0), обратим. Блок с булевыми входами a и b и выходом aЕb (сумма по модулю два) не обратим, так как по значению суммы aЕb невозможно установить, что за числа были на входе. Однако если рассмотреть блок со входами a и b и выходами a и aЕb, он будет обратим. Такой блок имеет специальное название, Feynman gate, или чаще употребляемое CNOT. Итак, чтобы обратимо вычислить сумму двух булевых величин, достаточно просто не забывать хотя бы одно из слагаемых. Но если требуется перемножить два булевых значения a и b, то оказывается, что никакой обратимый блок с двумя входами и двумя выходами этого сделать не может. Для вычисления булевого произведения чисел a и b был разработан обратимый блок Тоффоли (Tommaso Toffoli) с тремя входами a, b и c и тремя выходами a, b и cЕab. Он вычисляет булево произведение, когда входная переменная с равна нулю. Плохая новость в том, что для вычисления элементарных функций приходится вводить не вполне понятные новые переменные (переменная с в последнем примере), которым приписываются значения констант, а многие выходы блоков нужны только для обратимости (как, например, первые два выхода блока Тоффоли). Хорошая новость — блоков NOT, CNOT и Тоффоли достаточно для вычисления любой функции. Однако при попытке синтеза обратимых схем оказывается, что обратимые блоки можно выстраивать только каскадом, а количество константных переменных необходимо минимизировать, так как очень часто цена за использование дополнительной переменной очень высока. Это сильно осложняет задачу такого синтеза, и хороших методов ее решения пока не существует, а значит, невозможно и использование обратимой технологии вычислений. Впрочем, исследования в этой области ведутся очень активно, и есть надежда, что будут найдены решения, пригодные для создания нового типа схем.

Перейдем теперь к технологиям обратимых вычислений, которые могли бы физически обеспечить такие вычисления, а не просто симулировали их. Начнем с биллиардной модели (Billiard Ball Model, BBM), предложенной Фредкиным (Edward Fredkin). Вычисление проводится с помощью столкновений биллиардных шариков между собой и с препятствиями (рис. 1а); специальные датчики определяют наличие шариков в той или иной точке пространства. На рис. 1b схематически изображен блок, вычисляющий произведение двух булевых величин, c и x (средний выход равен этому произведению). Здесь наличие шарика кодирует единицу, а его отсутствие — нуль. Неплохую симуляцию BBM можно найти и протестировать на hex.org.uk/diffusion.

Норман Марголус (Norman Margolus), обобщая идею биллиардных вычислений, пришел к идее обратимых клеточных автоматов, не делая, впрочем, никаких утверждений о возможности их физической реализации⁴. Обратимый клеточный автомат работает по следующему принципу. Плоскость разбивается на квадраты размером 2x2 непрерывными и пунктирными линиями, как показано на рис. 2. Создается правило переписывания, по которому клеточки на каждом шаге эволюции автомата во времени меняют свой цвет (правила, показанные на рис. 2 справа, выписаны с учетом всех возможных поворотов). Затем в каждый нечетный момент времени правило используется для перекраски клеточек разбиения, заданного непрерывными линиями, а в каждый четный момент времени то же самое правило применяется к клеткам разбиения, заданного пунктиром.

В частности, Марголус проделывает эксперимент с моделью Фредкина, в котором модель BBM симулируется с помощью правил клеточных автоматов. На рис. 3 слева даны правила перекраски клеточек для симуляции модели Фредкина. В стартовой конфигурации берется квадрат размером 512x512 клеточек, раскрашенных случайным образом в черный и белый цвета. Квадрат посередине содержит ячейки, окрашенные в черный цвет. Картинка на рис. 3 справа показывает эволюцию системы после двухсот применений правила переписывания. Если интерпретировать черные точки как молекулы газа, то средняя иллюстрация показывает ситуацию, при которой посреди емкости с газом образован участок с повышенной концентрацией молекул. После двухсот итераций правила переписывания можно увидеть "ударную волну", распространяющуюся от центра сосредоточения плотного газа. Это навело на мысль о нетривиальности модели Фредкина и возможности моделирования с ее помощью физических явлений; позже клеточные автоматы аналогичного типа были применены для анализа сложных антенн⁵ и симуляции трехмерной гидродинамики^6,7.

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

Естественно поставить вопрос: допускает ли природа физически обратимые технологии, которые могли бы быть использованы для обратимых вычислений? CMOS не является обратимой технологией ввиду необратимости единичного блока (транзистора), из которых строятся схемы. Требуются новые физические объекты или явления, которые могли бы быть использованы для представления информации. Сложными для понимания, но более простыми, чем модель Фредкина, с точки зрения технологической реализации являются, например, кодирование информации магнитными спинами в технологии ЯМР или поляризацией фотонов в оптической технологии. Имеются и другие способы. Технологии ЯMР, оптическую технологию, технологии ионных ловушек, нейтральных атомов, сверхпроводников чаще всего объединяют под именем квантовых технологий.

В квантовых технологиях эволюция вычислительной системы возможна только при условии ее обратимости, тем самым физика вычисления обратима⁸. Уже существует ряд устройств, работающих на квантовых принципах. Речь пока не идет, разумеется, о полноценных квантовых компьютерах, способных выполнить, например, быстрый квантовый алгоритм Шора факторизации целых чисел — даже вопрос о принципиальной физической реализуемости таких компьютеров для практически значимых вычислений (скажем, факторизация 100-значных чисел) остается предметом острых дискуссий⁹. Однако квантовые устройства уже способны генерировать случайные простые числа, реализованы и некоторые квантовые коммуникационные протоколы¹⁰. Мы надеемся рассказать о ряде новых достижений в этой области в одном из следующих номеров "КТ".

1 Сформулированный им еще в 1961 году; русский перевод см. в сборнике "Квантовый компьютер & квантовые вычисления", том 2, "Регулярная и хаотическая динамика", 1999. — Л.Л.-М.
2 Proceedings of the IEEE, Vol. 91, No. 11, November 2003, pp. 1934-1939.
3 См. сборник, упомянутый в сноске 1. — Л.Л.-М.
4 Т. Тоффоли, Н. Марголус, "Машины клеточных автоматов". — М.: "Мир", 1991.
5 N. R. S. Simons, M. Cuhaci, N. Adnani and G. E. Bridges, "On the potential use of cellular-automata machines for electromagnetic-field solution", Int. J. Numer. Model. Electron. N. 8:3/4, 301–312 (1995).
6 G. Doolen (ed.), Lattice-Gas Methods for Partial Di.erential Equations (Addison-Wesley, 1990).
7 C. Adler, B. Boghosian, E. Flekkoy, N. Margolus and D. Rothman, "Simulating three-dimensional hydrodynamics on a cellular-automata machine", chao-dyn/9508001.
8 См. "КТ" ## 364, 414.
9 S. Aaronson. Multilinear Formulas and Skepticism of Quantum Computing, in Proceedings of ACM STOC 2004.
10 www.idquantique.com , www.magiqtech.com .