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

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

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

• плоское (линейное) ЛАП: состоит из массива байтов, не имеющего определенной структуры; трансляция адреса не требуется, так как логический адрес совпадает с физическим;
• сегментированное ЛАП: состоит из сегментов - непрерывных областей памяти, содержащих в общем случае переменное число байтов; логический адрес содержит 2 части: идентификатор сегмента и смещение внутри сегмента; трансляцию адреса проводит блок сегментации MMU;
• страничное ЛАП: состоит из страниц - непрерывных областей памяти, каждая из которых содержит фиксированное число байтов. Логический адрес состоит из номера (идентификатора) страницы и смещения внутри страницы; трансляция логического адреса в физический проводится блоком страничного преобразования MMU;
• сегментно-страничное ЛАП: состоит из сегментов, которые, в свою очередь, состоят из страниц; логический адрес состоит из идентификатора сегмента и смещения внутри сегмента. Блок сегментного преобразования MMU проводит трансляцию логического адреса в номер страницы и смещение в ней, которые затем транслируются в физический адрес блоком страничного преобразования MMU.

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

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

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

В реальном режиме сегментные регистры процессора содержат старшие 16 бит физического адреса начала сегмента. Сдвинутый на 4 разряда влево селектор дает 20-разрядный базовый адрес сегмента. Физический адрес получается путем сложения этого адреса с 16-разрядным значением смещения в сегменте, формируемого по заданному режиму адресации для операнда или извлекаемому из регистра EIP для команды (рис. 3.1). По полученному адресу происходит выборка информации из памяти.

Рис. 3.1. Схема получения физического адреса

Наиболее полно возможности микропроцессора по адресации памяти реализуются при работе в защищенном режиме. Объем адресуемой памяти увеличивается до 4 Гбайт, появляется возможность страничного режима адресации. Сегменты могут иметь переменную длину от 1 байта до 4 Гбайт.

Общая схема формирования физического адреса микропроцессором, работающим в защищенном режиме , представлена на рис. 3.2.

Как уже отмечалось, основой формирования физического адреса служит логический адрес. Он состоит из двух частей: селектора и смещения в сегменте .

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

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

Рис. 3.2. Формирование физического адреса при сегментно-страничной организации памяти

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

Структура дескриптора сегмента представлена на рис. 3.3.

Рис. 3.3. Структура дескриптора сегмента

Мы будем рассматривать именно структуру, а не формат дескриптора, так как при переходе от микропроцессора i286 к 32-разрядному МП расположение отдельных полей дескриптора потеряло свою стройность и частично стало иметь вид "заплаток", поставленных с целью механического увеличения разрядности этих полей.

32-разрядное поле базового адреса позволяет определить начальный адрес сегмента в любой точке адресного пространства в 2 32 байт (4 Гбайт).

Поле предела (limit) указывает длину сегмента (точнее, длину сегмента минус 1: если в этом поле записан 0, то это означает, что сегмент имеет длину 1) в адресуемых единицах, то есть максимальный размер сегмента равен 2 20 элементов.

Величина элемента определяется одним из атрибутов дескриптора битом G (Granularity - гранулярность, или дробность):

Таким образом, сегмент может иметь размер с точностью до 1 байта в диапазоне от 1 байта до 1 Мбайт (при G = 0). При объеме страницы в 2 12 = 4 Кбайт можно задать объем сегмента до 4 Гбайт (приG = l):

Так как в архитектуре IA-32 сегмент может начинаться в произвольной точке адресного пространства и иметь произвольную длину, сегменты в памяти могут частично или полностью перекрываться.

Бит размерности (Default size) определяет длину адресов и операндов, используемых в команде по умолчанию:

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

Байт доступа определяет основные правила обращения с сегментом.

Бит присутствия P (Present) показывает возможность доступа к сегменту. Операционная система (ОС) отмечает сегмент, передаваемый из оперативной во внешнюю память, как временно отсутствующий, уставливая в его дескрипторе P = 0. При P = 1 сегмент находится в физической памяти. Когда выбирается дескриптор с P = 0 (сегмент отсутствует в ОЗУ), поля базового адреса и предела игнорируются. Это естественно: например, как может идти речь о базовом адресе сегмента, если самого сегмента вообще нет в оперативной памяти? В этой ситуации процессор отвергает все последующие попытки использовать дескриптор в командах, и определяемое дескриптором адресное пространство как бы"пропадает".

Возникает особый случай неприсутствия сегмента. При этом операционная система копирует запрошенный сегмент с диска в память (при этом, возможно, удаляя другой сегмент), загружает в дескриптор базовый адрес сегмента, устанавливает P = 1 и осуществляет рестарт той команды, которая обратилась к отсутствовавшему в ОЗУ сегменту.

Двухразрядное поле DPL (Descriptor Privilege Level) указывает один из четырех возможных (от 0 до 3) уровней привилегий дескриптора , определяющий возможность доступа к сегменту со стороны тех или иных программ (уровень 0 соответствует самому высокому уровню привилегий).

Бит обращения A (Accessed) устанавливается в"1" при любом обращении к сегменту. Используется операционной системой для того, чтобы отслеживать сегменты, к которым дольше всего не было обращений.

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

Поле типа в байте доступа определяет назначение и особенности использования сегмента. Если бит S (System - бит 4 байта доступа) равен 1, то данный дескриптор описывает реальный сегмент памяти. Если S = 0, то этот дескриптор описывает специальный системный объект, который может и не быть сегментом памяти, например, шлюз вызова, используемый при переключении задач, или дескриптор локальной таблицы дескрипторов LDT. Назначение битов <3...0> байта доступа определяется типом сегмента (рис. 3.4).

Рис. 3.4. Формат поля типа байта доступа

В сегменте кода: бит подчинения, или согласования, C (Conforming) определяет дополнительные правила обращения, которые обеспечивают защиту сегментов программ. При C = 1 данный сегмент является подчиненным сегментом кода. В этом случае он намеренно лишается защиты по привилегиям. Такое средство удобно для организации, например, подпрограмм, которые должны быть доступны всем выполняющимся в системе задачам. При C = 0 - это обычный сегмент кода; бит считывания R (Readable) устанавливает, можно ли обращаться к сегменту только на исполнение или на исполнение и считывание, например, констант как данных с помощью префикса замены сегмента. При R = 0 допускается только выборка из сегмента команд для их выполнения. При R = 1 разрешено также чтение данных из сегмента.

Запись в сегмент кода запрещена. При любой попытке записи возникает программное прерывание.

В сегменте данных:

• ED (Expand Down) - бит направления расширения. При ED = 1 этот сегмент является сегментом стека и смещение в сегменте должно быть больше размера сегмента. При ED = 0 - это сегмент собственно данных (смещение должно быть меньше или равно размеру сегмента);
• бит разрешения записи W(Writeable). При W = 1 разрешено изменение сегмента. При W = 0 запись в сегмент запрещена, при попытке записи в сегмент возникает программное прерывание.

В случае обращения за операндом смещение в сегменте формируется микропроцессором по режиму адресации операнда, заданному в команде. Смещение в сегменте кода извлекается из регистра - указателя команд EIP.

Сумма извлеченного из дескриптора начального адреса сегмента и сформированного смещения в сегменте дает линейный адрес (ЛА).

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

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

Рассмотрим теперь все этапы преобразования логического адреса в физический более подробно.

Микропроцессор 80386 является полной 32-разрядной версией предыдущих 16-разрядных микропроцессоров 8086/80286 и символизирует значительное достижение в архитектуре процессоров - поворот от 16-разрядной к 32-разрядной архитектуре. Наряду с увеличением разрядности имеется также много усовершенствований и дополнительных функций. Микропроцессор 80386 обеспечивает: переключение задач, более совершенное управление памятью, управление виртуальной памятью со страничной трансляцией адресов (paging) или без нее, защиту программного обеспечения и возможность использования запоминающей системы большой емкости. Все программное обеспечение, написанное для прежних микропроцессоров 8086/8088 и 80286 совместимо снизу вверх и для микропроцессора 80386. Объем адресуемой памяти процессором увеличился с 1 Мбайта (для микропроцессора 8086/8088) или 16 Мбайт (для микропроцессора 80286) до 4 Гбайт, доступных процессору 80386 в защищенном режиме. Микропроцессор 80386 может переходить из защищенного режима работы в реальный режим без аппаратного сброса микропроцессора, который требует значительных затрат времени и был необходим в случае использования процессора 80286.

Микропроцессор 80486 является улучшенной версией микропроцессора 80386 и выполняет многие его команды за один период тактовых импульсов. Микропроцессор 80486 также имеет внутренний кэш первого уровня емкостью на 8 Кбайт и встроенный высокопроизводительный математический сопроцессор, программно совместимый с сопроцессором 80387. Следует отметить, что процессор 80486DX4 имеет кэш-память емкостью 16 Кбайт. Микропроцессор 80486, работая на такой же тактовой частоте, что и микропроцессор 80386, является на 50% более производительным.

Микропроцессор 80386

Наиболее распространены были две версии микропроцессора 80386: процессор 80386DX, и упрощенный процессор 80386SX с внешней 16-разрядной шиной данных, хотя внутри он использовал 32-разрядную шину.

Процессор 80386DX был помещен в 132-контактный корпус типа PGA (pin grid array), т. е. корпус с матричным расположением штырьковых вы­водов. Более новая версия микропроцессора 80386 - 80386ЕХ содержит в себе: блок управления шиной АТ, блок управления регенерацией динамического ОЗУ, программируемый блок выбора кристалла, контроллер прерываний, контроллер DMA, блок таймеров, блок последовательной передачи данных, 26 выводов шины адреса, 16 выводов шины данных.

Микропроцессор 80386DX, имея 32-разрядную шину данных и 32-разрядную шину адреса, способен адресовать 4 Гбайта физической памяти. Микропроцессор 80386SX, подобно микропроцессору 80286, адресует 16 Мбайт памяти и имеет в своем распоряжении только 24-разрядную шину адреса и 16-разрядную шину данных. Микропроцессор 80386SX был разработан после микропроцессора 80386DX для использования, не требующего полной версии 32-разрядной шины. Микропроцессор 80386SX применялся во многих персональных компьютерах, которые использовали ту же самую системную плату, что и для микропроцессора 80286. В то время, когда большинству приложений, включая Windows, требовалось менее 16 Мбайт памяти, процессор 80386SX был популярной и менее дорогостоящей версией микропроцессора 80386. В дальнейшем, несмотря на то, что процессор 80486 становился все более дешевым для построения новых вычислительных систем, все равно процессор 80386 долгое время оставался востребованным для многих приложений. Например, микропроцессор 80386ЕХ, хотя в персональных компьютерах и не исполь­зовался, но был очень популярен во встраиваемых системах.

Микропроцессору 80386, как и предыдущим версиям семейства микропроцессоров Intel, для работы требуется только один источник питания напряжением +5,0 В. Средний ток потребления процессором 80386 составляет: 550 мА для процессора, работающего на тактовой частоте 25 МГц, 500 мА для процессора с частотой 20 МГц и 450 мА для процессора, работающего на частоте 16 МГц. Кроме того, имелась версия процессора с тактовой частотой 33 МГц, который имел ток потребления, равный 600 мА. Ток потребления микропроцессора 80386ЕХ составляет 320 мА при работе на частоте 33 МГц.

Ток потребления процессора во время некоторых режимов его работы может возрастать до 1,0 А. Это означает, что источник питания и схема разводки питания должны быть рассчитаны на эти всплески тока. Процессор имеет многочисленные выводы V CC и V SS , которые для правильной работы микропроцес­сора должны быть все подключены к источнику постоянного тока с напряжением +5,0 В (V CC) и заземлены (V SS). Некоторые выводы процессора обозначены как N/C (no connection) и не должны быть куда-либо подключены. Помимо названных, были и несколько другие версии микропроцессоров 80386SX и 80386ЕХ, имеющие пониженное напряжение питания +3,3 В. Эти процессоры применялись в портативных блокнотных компьютерах (notebook) или портативных компьютерах (laptop).

Система памяти

Система физической памяти, к которой микропроцессор 80386DX может обращаться, имеет емкость 4 Гбайт. Кроме того, процессор имеет поддержку виртуальной памяти объемом до 64 Тбайт, отображаемой на физическую память с помощью блока управления памятью и дескрипторов. Следует заметить, что виртуальная адресация позволяет использовать программу более 4 Гбайт при наличии метода свопинга (swapping) и при большой емкости винчестера. На рис. 6.4 показана организация системы физической памяти микропроцессора 80386DX.

Память разделена на четыре 8-разрядных банка памяти, с емкостью до 1 Гбайт в каждом. Такая 32-разрядная организация памяти позволяет иметь доступ к байту, слову или двойному слову. Микропроцессор 80386DX способен передать 32-разрядные данные за один цикл памяти, тогда как для этого микропроцессору 8088 требовалось четыре цикла, а микропроцессорам 80286 и 80386SX необходимо два цикла. Большая разрядность данных очень важна, особенно для чисел с плавающей точкой одинарной точности, которые занимают 32 разряда. Достаточно развитое программное обеспечение использует числа с плавающей точкой для хранения данных, поэтому 32-разрядные ячейки памяти ускоряют выполнение программы, если она написана с учетом разрядности памяти.

Адрес каждого байта памяти представляется в шестнадцатеричной системе счисления, как и для прежних версий процессоров. Разница состоит в том, что микропроцессор 80386DX использует 32-разрядную шину адреса с памятью, адресуемой в диапазоне 00000000H-FFFFFFFFH.

Доступ к двум банкам памяти в системе, построенной на микропроцессорах 8086, 80286 и 80386SX, осуществляется посредством сигналов BLE (А0 - на 8086 и 80286) и ВНЕ. Доступ к банкам памяти микропроцессор 80386DX выполняет с помощью четырех сигналов ВЕ3 - BE0 . Такая организация памяти позволяет получить доступ к одному байту при активизации микропроцессором одного разрешающего сигнала.

При активизации двух разрешающих сигналов процессор адресуется к слову. В большинстве случаев при адресации к слову осуществляется обращение к банку 0 и 1 или к банку 2 и 3. Ячейка памяти 00000000Н находится в банке 0, ячейка 00000001Н - в банке 1, ячейка 00000002Н - в банке 2 и ячейка 00000003 - в банке 3. Микропроцессор 80386DX не имеет адресных выводов А0 и A1, поскольку они дешифрируются внутри процессора как сигналы разрешения байтов. Аналогично в 16-разрядном микропроцессоре 80386SX нет адресного вывода А0, поскольку он дешифрируется в сигналы BLE и ВНЕ. Микропроцессор 80386ЕХ адресуется к слову данных, размещаемому в двух банках 16-разрядной системы памяти, при пассивном сигнале BS8 (высоком логическом его уровне) или же к байту в 8-разрядной системе при активизации этого сигнала.

Управляющие регистры

В микропроцессоре 80386, дополнительно к регистру флагов EFLAGS и указателю инструкций EIP, имеются и другие управляющие регистры. Управляющий регистр CR0 (control register) идентичен регистру состояния машины MSW (machine status word) микропроцессора 80286, за исключением того, что он 32-разрядный, а не 16-разрядный регистр. Дополнительными управляющими регистрами являются CR1, CR2 и CR3.

На рис. 6.5. показана структура управляющих регистров микропроцессора 80386.

Управляющий регистр CR1 в микропроцессоре 80386 не используется, однако зарезервирован для будущих изделий. Управляющий регистр CR2 фиксирует линейный адрес, по которому был получен последний отказ страницы памяти. Наконец, управляющий регистр CR3 фиксирует базовый адрес таблицы страниц. Младшие 12 разрядов с 0 по 11 из 32-разрядного регистра содержат нули и объединяются с остальными разрядами регистра, чтобы определить начало таблицы страниц размером 4К.

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

Бит PG (paging enable) предназначен для выбора преобразования таблицы стра­ниц из линейных адресов в физические адреса при PG = 1. Страничная переадресация памяти позволяет присваивать линейному адресу любую физическую ячейку памяти.

□ ЕТ

Бит ЕТ (extension type) является индикатором поддержки инструкций математического сопроцессора. Если ЕТ - 0, то выбран сопроцессор 80287, а если ЕТ = 1, то сопроцессор 80387. Этот бит был добавлен, чтобы отражать то обстоятельство, что в данной системе имеется сопроцессор 80387.

Бит TS (task switch) указывает, что микропроцессор выполнил переключение задач (изменение содержимого регистра задачи TR в защищенном режиме устанавливает бит TS). Если бит TS установлен, то команда цифрового сопроцессора приводит к прерыванию типа 7 (сопроцессор недоступен).

□ ЕМ

Бит ЕМ (emulate coprocessor) устанавливается для вызова прерывания типа 7 при попытке выполнения каждой ESC-команды, т. е. команды, относящейся к сопроцессору. Это часто используется для программной эмуляции сопроцессора. Эмуляция снижает стоимость системы, но для выполнения эмулированных команд сопроцессора часто требуется больше времени, примерно где-то в 100 раз.

Бит MP (monitor coprocessor) устанавливается для вызова прерывания типа 7 при выполнении каждой команды wait, когда установлен бит TS.

□ РЕ

Бит РЕ (protection enable) устанавливается, чтобы перевести микропроцессор 80386 в защищенный режим. Он может также сбрасываться, чтобы начать довольно длинную последовательность инструкций переключения в реальный режим работы. В микропроцессоре 80286 этот бит может только устанавливаться. Микропроцессор 80286 не способен переходить обратно в реальный режим работы без выполнения аппаратного сброса, что исключает его использование в большинстве систем, использующих защищенный режим.

Дескрипторы и селекторы

Перед тем как перейти к обсуждению блока страничной трансляции адресов, рассмотрим дескрипторы и селекторы микропроцессора 80386. Микропроцессор 80386 использует дескрипторы во многом таким же образом, как и микропроцессор 80286. Дескриптор в обоих микропроцессорах - это последовательность из восьми байтов, которая содержит информацию о сегменте памяти и о его расположении. Селектор (содержимое сегментного регистра) используется для идентификации дескриптора, заданного в таблице дескрипторов. Основное отличие между микропроцессорами 80286 и 80386 состоит в том, что последний имеет два дополнительных селектора (FS и GS), и для микропроцессора 80386 определены два самых старших байта дескриптора. Другое отличие состоит в том, что дескрипторы микропроцессора 80386 используют 32-разрядный базовый адрес сегмента и 20-разрядное поле предела (limit) сегмента вместо 24-разрядного базового адреса и 16-разрядного поля предела сегмента, имеющихся в микропроцессоре 80286.

Микропроцессор 80286 адресуется к области памяти размером 16 Мбайт за счет своего 24-разрядного базового адреса и имеет протяженность сегмента в 64 Кбайт благодаря 16-разрядному полю предела. Микропроцессор 80386 за счет 32-разрядного базового адреса адресуется к области памяти в 4 Гбайт, а размер сегмента определяется благодаря 20-разрядному полю предела, который используется двумя разными способами. Бит гранулярности G (granularity) дескриптора или, иначе, бит дробности определяет единицу измерения для размера сегмента: при G = 0, размер задается в байтах, а если G = 1, то - в страницах по 4К. Таким образом, размер сегмента при 20-разрядном поле предела может составить соответственно 1 Мбайт или 4 Гбайт.

Бит гранулярности G появился в дескрипторе, начиная с микропроцессора 80386. Если бит G = 0, то сохраняемое в поле предела значение трактуется непосредственно, как предельный размер сегмента, позволяющий иметь доступ к любой области 00000Н-FFFFFG сегмента емкостью в 1 Мбайт. Если же бит G = 1, то сохраняемое в поле предела число интерпретируется как 00000XXXH-FFFFFXXXH, где XXX имеет любую величину между 000Н и FFFH. Таким образом обеспечивается доступ к размеру сегмента от 0 байт до 4 Гбайт участками по 4 Кбайт. Значение предела, равное 00001Н, указывает на то, что предельный размер сектора составляет 4 Кбайт, когда бит G = 1 или же 1 байт, когда бит G = 0. Примером может служить сегмент, начинающийся с физического адреса 10000000H. Для значения предела 00001Н и бита G = 0 данный сегмент начинается в 10000000H и заканчивается в 10000001Н. Если же бит G = 1 при этом же значении предела (00001Н), то сегмент начинается в ячейке 100000000Н и заканчивается в 10001FFFH.

На рис. 6.6 показано, как микропроцессор 80386 адресуется к сегменту памяти в защищенном режиме, используя селектор и дескриптор. Приведенная адресация идентична со способом адресации сегмента микропроцессором 80286. Разница состоит в размере доступного для микропроцессора 80386 сегмента. Старшие 13 разрядов (биты 15-3) селектора используются для выбора дескриптора из таблицы дескрипторов. Бит индикатора таблицы TI (table indicator) (бит 2 селектора) указывает на тип таблицы дескрипторов: локальную, если бит TI = 1, или глобальную, если бит TI = 0. Младшие два бита RPL (requested privilege level) (биты 1-0) селектора определяют запрашиваемый уровень привилегий для доступа к сектору.

Поскольку селектор использует 13-разрядный код для доступа к дескриптору, то каждая таблица (локальная или глобальная) содержит не более 8192 дескриптора. Поскольку возможный размер сегмента для микропроцессора 80386 достигает 4 Гбайт, то единовременно можно получить доступ к 16 384 сегментам, используя две таблицы дескрипторов. Все это позволяет микропроцессору 80386 иметь поддержку виртуальной памяти объемом до 64 Тбайт (1 Тбайт = 1024 Мбайт). Разумеется, что реально может существовать система памяти емкостью только до 4 Гбайт. Если же для программы в какой-то момент времени потребуется память более 4 Гбайт, то требуемые данные могут подкачиваться в систему памяти с дисковода или какого-либо другого накопителя большого объема.

Микропроцессор 80386 использует таблицы дескрипторов для глобальных (GDT ) и локальных (LDT) дескрипторов. Третья таблица дескрипторов используется дескрипторами прерываний (GОТ ) или вентилями (gates). Первые шесть байт дескриптора микропроцессора 80386 такие же, как в микропроцессоре 80286, что обеспечивает программную совместимость с ним снизу вверх. Два старших байта дескриптора микропроцессора 80286 были зарезервированы и содержали значение 00H. Дескрипторы для микропроцессоров 80286 и 80386 показаны на рис. 6.7.

Дескриптор микропроцессора 80386 содержит 32-разрядный базовый адрес, 20-разрядное поле предела сегмента и бит гранулярности G, определяющий множитель предела сегмента (1 или 4К раз) или, иначе, в каких единицах задан предел: в байтах (G = 0) или страницах по 4К (G = 1). Далее представлено назначение полей дескриптора микропроцессора 80386:

□База (В31-В0)

Поле База (Base) определяет базовый (начальный) 32-разрядный адрес сегмента в физическом 4 Гбайтном адресном пространстве микропроцессора 80386.

□ Предел (L19-L0)

ПолеПредел (Limit) определяет предельный размер сегмента в байтах, если бит гранулярности G = 0, или в страницах по 4К, если G = 1. Это позволяет иметь любой размер сегмента от 1 байта до 1 Мбайт, если бит G = 0 или от 4 Кбайт до 1 Гбайт, если бит G = 1. Следует напомнить, что предел указывает на последний байт в сегменте.

□Права доступа

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

Бит гранулярности G (granularity) выбирает множитель 1 или 4К для поля предела сегмента. Если бит G = 0, то множитель равен 1, если бит G = 0, то множитель равен 4К.

Бит D (default size) определяет разрядность используемых операндов и регистров по умолчанию. Если D = 0, тогда 16 бит, как в микропроцессоре 80286; если D = 1, то 32 бит, как в микропроцессоре 80386. Этот бит определяет, требуются ли префиксы к 32-разрядным данным и индексным регистрам. Если D = 0, тогда требуется префикс для доступа к 32-разрядным регистрам и для использования 32-разрядных указателей. Если D = 1, тогда префикс требуется для доступа к 16-разрядным регистрам и для 16-разрядных указателей. Атрибуты use16 и use32, используемые с директивой segment в языке ассемблера, управляют установкой бита D. Реальный режим работы всегда предполагает, что регистры 16-разрядные, поэтому к любой команде, адресуемой 32-разрядным регистром или указателем, должен применяться префикс.

Бит AVL (available) доступен для операционной системы и может использоваться ею при необходимости. Он не применяется и не анализируется процессором и предназначен для использования прикладными программами.

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

Суперкомпьютеры всегда представлялись особенным классом вычислительной техники. Поскольку строят такие машины для решения задач необычных, то и бюджеты имеют необычные, а это, в свою очередь, давало ощущение бесконечных возможностей: казалось, проблема всегда только в деньгах и, влей ещё десяток–другой миллионов, производительность можно наращивать бесконечно. Случившееся в последние месяцы и годы и выраженное свежим списком 500 самых мощных числогрызов планеты - известным вам TOP500.org - даёт, однако, повод утверждать, что «бесконечность» кончилась. Суперкомпьютеры первыми из современных компьютерных систем ткнулись в физический предел возможностей полупроводниковой электроники - и для них прежде всего необходимо теперь отыскать выход из тупика. Новую технологию компьютинга.

Формальной зацепкой для такого далекоидущего утверждения стала странная закономерность, подмеченная составителями вышеназванного списка. Топ-500 обновляется дважды в год, и в верхних позициях его последней версии, опубликованной на прошлой неделе, изменений почти не произошло (в десятку «лучших» добавился всего один новый участник, да суммарная производительность всех пяти сотен машин немного выросла, с 0,223 до 0,250 эксафлопс). Зато случилась качественная общая перемена: «центр тяжести» списка сместился в верхнюю его часть, или, говоря проще, основная вычислительная мощь теперь сконцентрирована в сравнительно небольшом (исторически - рекордно малом) количестве самых быстрых машин. Выглядит это так: половина кумулятивной мощи Топ-450 обеспечивается всего лишь 17 первыми компьютерами списка. Тренд этот обозначился не вчера, однако за последние шесть лет оформился настолько, что над ним необходимо задуматься.

Единого несомненного объяснения нет. Одно из самых убедительных - финансовое: за последние годы суперкомпьютеры стали сильно дороже (примерно вчетверо, в сравнении, скажем, с числогрызами середины “нулевых”), а потому доступны теперь лишь относительно немногим государственным агентствам и крупным компаниям. Вдобавок конструкторы и покупатели новых не слишком мощных машин не стремятся засветиться в рейтинге, чтобы не портить себе имидж. Так и получается, что чем дальше, тем ярче проявляется тренд: сильные становятся сильней, слабые нелинейно быстро отстают.

Важный вывод: суперкомпьютеры не перестали быть нужными, они лишь стали менее доступными. Но как же неумирающий закон Мура? Разве он не должен компенсировать рост цен более плотной компоновкой и, соответственно, повышением производительности? Вот тут-то и всплывает главное подозрение. Похоже, мы вышли на финишную прямую, где закон Мура хоть ещё и работает, но воспользоваться им уже слишком дорого для большинства игроков.

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

И тут очень кстати вспомнить про готовящуюся замену знаменитого теста Linpack , который с самого начала публикации Топ-500 (двадцать лет назад) служит главным мерилом производительности суперкомпьютерных систем. Заменить его предлагается на недавно разработанный тест HPCG (High Performance Conjugate Gradient). Причина: Linpack - написанный на «Фортране» аж в 1979 году - отражает истинную производительность измеряемых систем неудовлетворительно и расхождение растёт.

Вообще, внятно объяснить отличие Linpack от HPCG не может даже их общий соавтор Джек Донгарра. Но, сильно упрощая, разницу можно свести к следующему: Linpack оценивает главным образом способность суперкомпьютера к чистым вычислениям (что хорошо делают GPU-акселераторы), тогда как HPCG учитывает ещё и важную при решении практических научных и технических задач производительность внутренних коммуникаций (то есть частое нерегулярное обращение к памяти, например).

HPCG если и не заменит, то дополнит Linpack уже через несколько лет «обкатки» (кому интересно, исходники доступны под BSD-лицензией с сайта лабораторий Sandia). И это может привести к значительным перестановкам по всему списку Топ-500, возврату в него мелких участников, которые станут получать более высокие, более справедливые оценки, и даже внесению корректировок в архитектуру суперкомпьютеров, когда их перестанут оптимизировать под Linpack. Хоть на последнее, конечно, особенно надеяться не следует - ведь прорывной технологии компьютинга по-прежнему нет!

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

Что может обеспечить такой рывок? Западная пресса засматривается на нанотрубки, из которых ребятам в Стэнфорде удалось построить одномерные полярные транзисторы (CNFET), научиться делать микросхемы с гарантированной функциональностью (главная проблема: всё ещё трудно избежать большого числа неправильно уложенных нанотрубок) и даже построить MIPS-совместимый компьютер, продемонстрированный как раз на прошлой неделе, на суперкомпьютерной конференции ACM/IEEE SC13 («Компьютерра» писала об этом проекте: см. « »). В перспективе эта технология способна дать 13-кратное превосходство в производительности на единицу энергопотребления к полупроводниковым чипам. Интересно, занимается ли нанотрубками кто-то у нас?

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

Все эти изменения произошли не потому, что разработчики столкнулись с физическими пределами дальнейшего развития существующих процессоров. Скорее, производительность оказалась ограничена тем фактом, что прогресс в некоторых областях — в первую очередь энергоэффективности — был медленнее прогресса в других сферах, вроде расширения функциональных возможностей и наборов команд. Однако может ли быть так, что теперь физический предел процессоров и их вычислительной мощности уже близок? Игорь Марков из Университета Мичигана рассмотрел этот вопрос в статье в журнале Nature.

Рассматриваем преграды

Марков отмечает, что, основываясь на чисто физических ограничениях, некоторые учёные подсчитали, что закона Мура хватит ещё на сотни лет. С другой стороны, группа International Technology Roadmap for Semiconductors (ITRS) даёт ему пару десятилетий жизни. Впрочем, прогнозы ITRS можно ставить под сомнение: раньше эта группа предсказывала процессоры с частотой 10 ГГц во времена чипов Core2. Причина этого расхождения состоит в том, что многие жёсткие физические ограничения так и не вступили в игру.

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

Суть аргумента Маркова можно понять примерно так: хотя существуют жёсткие физические пределы, они часто не имеют отношения к проблемам, сдерживающим современный полупроводниковый прогресс. Вместо этого, мы сталкиваемся с более мягкими ограничениями, которые зачастую можно обойти. «Когда наступает момент определённого препятствующего прогрессу ограничения, понимание его природы является ключом к его преодолению», пишет он. «Некоторые ограничения можно просто проигнорировать, в то время как другие остаются гипотетическими и основаны только на эмпирических данных; их трудно установить с высокой степенью определённости».

В результате то, что кажется преградами развития, часто преодолевается сочетанием творческого мышления и усовершенствованной технологии. Пример Маркова — дифракционный предел. Первоначально он должен был удержать лазеры на основе аргона-фтора от травления любых структур тоньше 65 нанометров. Но с помощью субволновой дифракции мы в настоящее время работаем над 14 нм структурами, используя этот же лазер.

Где находятся современные пределы?

Марков уделяет внимание двум вопросам, которые считает крупнейшими пределами: энергетика и связь. Вопрос энергопотребления происходит из того, что количество энергии, используемой современными цепями, не сокращается пропорционально уменьшению их физических размеров. Основной результат этого: усилия, сделанные с целью блокировать части чипа в те моменты, когда они не задействованы. Но с нынешними темпами развития данного подхода в каждый конкретный момент времени неактивной является большая часть чипа — отсюда происходит термин «тёмный кремний».

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

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

Что дальше?

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

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

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

Другой физический предел по Маркову: стирание бита информации имеет термодинамическую стоимость, которую нельзя избежать — вычисления всегда расходуют энергию. Одна из идей для того, чтобы избежать этого предела — «обратимые вычисления», когда компоненты возвращаются в исходное состояние после расчёта. Этот способ может, по крайней мере в теории, позволить получить обратно часть использованной энергии.

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

За пределами физики

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

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

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

От редакции. Наши постоянные читатели знают, что изредка в нашей газете появляются перепечатки наиболее знаменитых, классических статей и работ в области информатики. “Физические пределы вычислений” мы хотели напечатать давно… лет пятнадцать. Но этой замечательной статье все как-то не находилось места с точки зрения композиции других материалов, слишком странно она смотрелась бы в газете, будучи напечатанной “просто так”. И тут такая удача! Статья была упомянута (абсолютно заслуженно) в последней лекции нашего курса повышения квалификации, как один из немногих источников информации по данной теме на русском языке. Конечно, мы не могли не воспользоваться возможностью. Надеемся, вы получите удовольствие от знакомства с этим прекрасным популярным материалом. Ведь даже 24 (!) года, прошедшие со времени его публикации, не сделали его “устаревшим”, хотя, конечно, технологии ушли вперед на парсеки! Но фундаментальные законы не по зубам даже технологиям!

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

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

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

Подобный поиск фундаментальных ограничений уже имел прецеденты. В 40-х годах К.Шеннон, в то время сотрудник фирмы Bell Telephone Laboratories, установил, что существуют ограничения на количество информации, которое можно передать по каналу связи при наличии шума. Эти ограничения действуют независимо от того, каким образом кодируется сообщение. Работа Шеннона ознаменовала собой рождение современной теории информации. Еще раньше, в середине и конце прошлого столетия, физики, пытаясь определить фундаментальные ограничения на эффективность парового двигателя, создали науку, получившую название “термодинамика”. Приблизительно в 1960 г. Ландауэр (один из авторов данной статьи) совместно с Дж. Суонсоном, работая в фирме IBM, попытались применить анализ подобного рода к процессу вычисления. Начиная с середины 70-х годов к этим исследованиям стали подключаться все более многочисленные группы ученых из других организаций.

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

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

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

Приведем другой пример исчезновения информации. Выражение “2 + 2” содержит больше информации, чем выражение “= 4”. Если нам известно лишь то, что число 4 было получено в результате сложения двух чисел, то мы не сможем определить, какие именно числа складывались: 1 + 3, 2 + 2, 0 + 4 или какая-нибудь другая пара чисел. Поскольку выходная информация содержится неявным образом уже во входной, можно считать, что никакое вычисление не порождает информации.

Обычные логические вентили рассеивают энергию потому, что отбрасывают ненужную информацию. Например, если на выходе вентиля И имеется 0, то мы не можем определить, что было на входах.

На самом деле вычисления, выполняемые на современных вычислительных машинах, проводятся при помощи многих операций, уничтожающих информацию. Так называемый “вентиль И ” - это устройство с двумя входными линиями, на каждой из которых может быть установлен сигнал, равный 1 или 0, и одной выходной линией - значение ее сигнала определяется значениями входов. Если на обоих входах 1, то на выходе также будет 1. Если на одном или на обоих входах 0, то и на выходе будет 0. Всякий раз, когда на выходе вентиля 0, мы теряем информацию, потому что нам неизвестно, в каком из трех возможных состояний находились входные линии (0 и 1; 1 и 0 или 0 и 0). На самом деле в любом логическом вентиле, у которого количество входов превышает количество выходов, неизбежно происходит потеря информации, поскольку мы не можем определить состояние входов по состоянию выходов. Поэтому всякий раз, когда мы пользуемся подобным “логически необратимым” вентилем, мы рассеиваем энергию в окружающую среду. Стирание одного бита данных в памяти ЭВМ - другая часто используемая при вычислениях операция, которая также диссипативна по своей природе. При стирании одного бита данных мы теряем всю информацию о предшествовавшем состоянии этого бита.

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

Как показал Бенне (один из авторов этой статьи) в 1973 г., при вычислении можно обойтись как без необратимых логических элементов, так и без стирания информации. С тех пор справедливость этого положения была продемонстрирована на нескольких моделях. Проще всего описать модели, основанные на так называемых “обратимых логических элементах”, таких, как вентиль Фредкина, названный по имени Эдуарда Фредкина из Массачусетсского технологического института. У вентиля три входные и три выходные линии. Сигнал на одной входной линии, называемой “управляющим каналом”, не изменяется при прохождении через вентиль. Если сигнал на управляющем канале установлен равным 0, то входные сигналы на двух других линиях также проходят без изменения. Но если на управляющей линии 1, то на двух других выходных линиях происходит переключение: входной сигнал одной линии становится выходным другой, и наоборот. Вентиль Фредкина не теряет информации, поскольку состояние входов можно всегда определить по состоянию выходов.

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

Обратимый логический вентиль Фредкина может и не рассеивать энергию - состояние на его входах можно определить по состоянию выходов. У вентиля имеется “управляющая” линия, состояние которой не меняется вентилем. Если на управляющей линии 0, то значения сигнала на двух других линиях также не меняются, если же на управляющей линии 1, то вход линии А становится выходом линии S, и наоборот. С помощью обратимых вентилей, соединенных соответствующим образом, можно реализовать любую функцию, выполняемую обычным необратимым устройством. Чтобы реализовать операцию И (справа), один вход устанавливается равным 0 и два выходных бита, называемых “мусорными”, временно игнорируются. Когда вычисление завершено, эти биты используются при работе вентиля в обратном направлении, чтобы вернуть компьютер к исходному состоянию.

У вентилей Фредкина больше выходных линий, чем у тех, которые они моделируют. Поэтому в процессе вычислений образуются, казалось бы, “мусорные биты”, т.е. биты информации, не требующиеся для получения результата. Перед тем как начать другое вычисление, нужно каким-то образом очистить компьютер от этих битов. Но если мы сотрем их, то произойдет та самая диссипация энергии, которой мы хотели избежать.

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

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

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

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

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

Идеализированная физическая модель вентиля Фредкина: трубки играют роль проводников, а присутствие или отсутствие шарика интерпретируется как 1 или 0. Узкий расщепленный участок трубки - это управляющий канал. Когда в него попадает шарик, стенки трубки расходятся в стороны, приводя в действие переключающий механизм. Последний, в свою очередь, переводит любой прибывший шарик из линии А в линию В и наоборот. Две пружинки поддерживают управляющий канал выключенным, когда в нем нет шарика. Такой вентиль не требует статического трения для выполнения операций. Его можно погрузить в вязкую жидкость, и тогда силы трения будут зависеть лишь от скорости шариков. В этом случае рассеиваемая энергия может быть произвольно малой: чтобы уменьшить количество рассеиваемой энергии, нужно лишь уменьшить скорость прохождения шариков через вентиль.

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

Они продемонстрировали это на модели вычислительного устройства, в котором вычисления проводятся путем выстреливания навстречу друг другу идеальных бильярдных шаров в отсутствие сил трения. В бильярдной модели идеально отражающие “зеркала” - поверхности, меняющие направление движения шаров, расположены таким образом, что движение шаров по столу моделирует прохождение битов информации через логические вентили (см. рисунок). Как и раньше, присутствие шара в определенной части “компьютера” интерпретируется как 1, а отсутствие - как 0. Если два шара одновременно достигают логического вентиля, то они сталкиваются, и траектории их движения изменяются; новые траектории представляют при этом выходные данные вентиля. Фредкин, Тоффоли и другие разработали схемы расположения зеркал, соответствующие различным типам логических вентилей, и доказали, что можно построить бильярдную модель любого логического элемента, необходимого для вычислений.

Бильярдная модель компьютера: движение бильярдных шаров по поверхности стола моделирует прохождение битов информации через логический вентиль. В бильярдных логических вентилях (слева) траектории шаров изменяются при их столкновениях друг с другом или с “зеркалами”. Кроме функций, выполняемых ими в вентилях, зеркала могут менять угол траектории шара (а), сдвигать ее в сторону (b), задерживать шар, не меняя его конечного направления или скорости (с), или заставлять траектории пересекаться (d). Зеркала можно расставить таким образом, чтобы получившийся в результате “компьютер” выполнял функции любого логического устройства. Например, можно построить бильярдный компьютер для распознавания простых чисел. Такой компьютер (справа) на входе принимает произвольное пятизначное двоичное число (в данном случае 01101, или 13) и фиксированную входную последовательность 01. Как и вентиль Фредкина, бильярдный компьютер возвращает больше битов на выходе, чем нужно пользователю. В рассматриваемом случае он возвращает само исходное число (представляющее собой “лишний” выход) и “ответ”: последовательность 10, если число на входе простое, и 01, если оно составное.

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

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

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

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

Многих трудностей, с которыми приходится сталкиваться при использовании бильярдной модели компьютера, можно было бы избежать или, во всяком случае, уменьшить их, если вместо бильярдных шаров воспользоваться субмикроскопическими частицами, такими, например, как электроны. Как указал У.Зурек из Национальной лаборатории в Лос-Аламосе, благодаря законам квантовой механики, накладывающим ограничения на состояние элементарных частиц, возможность небольших отклонений в движении частиц может быть устранена.

Хотя до сих пор наши рассуждения основывались главным образом на классической динамике, несколько исследователей предложили другие модели обратимых вычислительных машин, основанных на принципах квантовой механики. Такие машины, впервые предложенные П.Бениоффом из Национальной лаборатории в Аргонне (Франция) и усовершенствованные другими, в особенности Р.Фейнманом из Калифорнийского технологического института, до сих пор были описаны лишь в самых общих выражениях. По существу, частицы в этих моделях компьютеров должны быть расположены таким образом, чтобы правила квантовой механики, управляющие их взаимодействием, были в точности аналогичны правилам, предсказывающим значения сигналов на выходах обратимых логических вентилей. Предположим, например, что спин частицы может иметь только два возможных значения: направление вверх (соответствующее двоичной 1) и вниз (соответствующее 0). Взаимодействие между значениями спинов частиц должно проходить таким образом, чтобы значение спина данной частицы изменялось в зависимости от спина частиц, находящихся поблизости. При этом спин частицы будет соответствовать одному из выходов логического вентиля.

Выше мы говорили в основном об обработке информации. Но компьютер должен не только обрабатывать данные, но и запоминать их. Взаимодействие между хранением и обработкой информации, пожалуй, лучше всего можно описать на примере устройства, называемого “машиной Тьюринга” (по имени Алана М. Тьюринга, первого, кто предложил такую машину в 1936 г.). Машина Тьюринга может произвести любое вычисление, выполняемое современной ЭВМ. Ш.Бенне (один из авторов этой статьи) доказал возможность построения машины Тьюринга, т.е. такой, которая не теряет информации и, следовательно, в процессе работы может затрачивать любое заранее заданное малое количество энергии.

Машина Тьюринга способна выполнить любое вычисление, которое может выполнить ЭВМ. Бесконечно длинная лента поделена на дискретные сегменты, в каждом из которых записан 0 или 1. “Головка для считывания и записи”, которая может находиться в любом из нескольких внутренних состояний (здесь только два состояния: А и В), перемещается вдоль ленты. Каждый цикл начинается с того, что головка считывает один бит с сегмента ленты. Затем, в соответствии с фиксированным набором правил перехода, она записывает в сегмент ленты бит данных, изменяет свое внутреннее состояние и перемещается на одну позицию влево или вправо. Поскольку данная машина Тьюринга обладает всего двумя внутренними состояниями, ее возможности ограничиваются лишь тривиальными вычислениями. Более сложные машины с большим числом состояний способны смоделировать поведение любой ЭВМ, в том числе и значительно более сложной, чем они сами. Это оказывается возможным благодаря тому, что они хранят полное представление логического состояния большей машины на бесконечной ленте и разбивают каждый вычислительный цикл на большое количество простых шагов. Показанная здесь машина логически обратима: мы всегда можем определить предшествующие состояния машины. Машины Тьюринга, обладающие другими правилами перехода, могут и не быть логически обратимыми.

Машина Тьюринга состоит из нескольких компонентов. Один из них - лента, поделенная на отдельные участки или сегменты, в каждом из которых записаны 0 или 1, представляющие собой входные данные. “Головка для считывания и записи” движется вдоль ленты. Головка может выполнять несколько функций - считать с ленты один бит данных, записать один бит на ленту и переместиться на один сегмент влево или вправо. Чтобы на следующем цикле сохранять информацию о том, что делалось на предыдущем, у механизма головки имеется ряд так называемых “состояний”. Каждое состояние представляет собой свою, несколько отличную от других конфигурацию внутренних частей головки.

На каждом цикле головка считывает бит с того сегмента ленты, напротив которого она в данный момент находится. Затем она записывает новое значение бита на ленту, изменяет свое внутреннее состояние и перемещается на один сегмент влево или вправо. Значение бита, который она записывает, состояние, к которому она переходит, и направление, в котором она перемещается, определяются фиксированным набором правил перехода. Каждое правило описывает определенные действия. Какому правилу следует машина в данный момент, определяется состоянием головки и значением бита, только что прочитанного с ленты. Например, правило может быть следующим: “Если головка находится в состоянии А и расположена напротив сегмента, в котором записан 0, то она должна изменить значение этого бита на 1, перейти к состоянию В и переместиться на один сегмент вправо”. Согласно какому-нибудь другому правилу, машина не должна менять своего состояния или не записывать нового бита на ленту, или же должна остановиться. Не все машины Тьюринга обратимы, но можно построить такую обратимую машину Тьюринга, которая способна выполнить любое вычисление.

Модели, основанные на обратимой машине Тьюринга, имеют преимущество над такими машинами, как бильярдный компьютер, в котором отсутствует трение. В бильярдном компьютере случайное тепловое движение молекул приводит к неизбежным ошибкам. Обратимые машины Тьюринга на самом деле используют случайное тепловое движение: они построены таким образом, что именно тепловое движение при содействии слабой вынуждающей силы переводит машину из одного состояния в другое. Развитие вычислительного процесса напоминает движение иона (заряженной частицы) в растворе, находящемся в слабом электрическом поле. Если наблюдать за поведением иона в течение короткого периода времени, то оно покажется случайным: вероятность движения в одном направлении почти такая же, как и в другом. Однако вынуждающая сила, обусловленная действием электрического поля, придает движению предпочтительное направление. Вероятность того, что ион будет двигаться в этом направлении, несколько больше. На первый взгляд может показаться невероятным, что целенаправленная последовательность операций, свойственная процессу вычисления, может быть реализована аппаратом, направление движения которого в любой момент времени можно считать почти случайным. Однако такой характер действий очень распространен в природе. Его, в частности, можно наблюдать в микроскопическом мире химических реакций. Происходящее по методу проб и ошибок броуновское движение, или случайное тепловое движение, оказывается достаточно эффективным, чтобы реагирующие молекулы вступили в контакт, расположились должным образом относительно друг друга, как этого требует данная реакция, и образовались новые молекулы, представляющие собой продукты реакции. В принципе все химические реакции обратимы: то же броуновское движение, которое обеспечивает выполнение реакции в прямом направлении, иногда заставляет продукты реакции пройти через обратный переход. В состоянии равновесия обратное направление реакции так же вероятно, как и прямое. Чтобы заставить реакцию идти в прямом направлении, нужно постоянно добавлять молекулы, вступающие в реакцию, и удалять молекулы - продукты реакции. Другими словами, мы должны приложить небольшую вынуждающую силу. Когда эта сила очень мала, реакция будет происходить в прямом и обратном направлениях, но в среднем она будет идти в прямом направлении. Чтобы обеспечить наличие вынуждающей силы, мы должны затрачивать энергию, однако, как и в модели вентиля Фредкина из трубок и шариков, количество энергии может быть произвольно малым. Если нас устраивает очень медленное выполнение операций, то не существует минимального необходимого количества энергии, которую нужно затратить на эти операции. Объяснение заключается в том, что полное количество рассеиваемой энергии зависит от числа шагов в прямом направлении, деленного на число шагов в обратном. (На самом деле оно пропорционально логарифму этого отношения; когда само отношение увеличивается или уменьшается, его логарифм изменяется в ту же сторону.) Чем медленнее реакция проходит в прямом направлении, тем меньше будет отношение. (Здесь опять уместна аналогия с быстрым и медленным пловцами: если реакция проходит медленнее, полное количество затрачиваемой энергии будет меньше, несмотря на то что число промежуточных распадов и соединений остается тем же.)

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

ПОСМОТРИМ, как работает броуновская машина Тьюринга на примере броуновской машины для копирования ленты. Такая машина уже существует в природе. Это РНК-полимераза - фермент, участвующий в процессе синтеза РНК, являющейся копией ДНК, из которой состоят гены. Одноцепочечная ДНК во многом напоминает ленту машины Тьюринга. В каждом ее элементе, т.е. в каждой позиции вдоль цепи, находится один из четырех нуклеотидов, или оснований: аденин, гуанин, цитозин или тимин (сокращенно A, G, С, Т). Структура РНК очень сходна с ДНК. Это так же длинная цепеобразная молекула, состоящая из оснований четырех типов - аденина, гуанина, цитозина и урацила (соответственно A, G, С и U). Основания РНК способны связываться с комплементарными им основаниями ДНК.

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

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

РНК-полимераза просто копирует информацию, не обрабатывая ее, нетрудно представить себе, как могла бы работать гипотетическая химическая машина Тьюринга. Лента представляет собой одну длинную скелетную молекулу, к которой через равные промежутки прикрепляются основания двух типов, интерпретируемые как биты 0 и 1. Еще одна небольшая молекула прикреплена к одной из позиций в цепи нулей и единиц. Позиция, к которой прикреплена эта молекула, - не что иное, как сегмент ленты, на котором находится головка машины Тьюринга. Имеется несколько различных типов “молекулы-головки”. Каждый тип представляет одно из возможных внутренних состояний машины.

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

Предположим, что молекула-головка относится к типу А (это означает, что машина находится в состоянии А ) и прикреплена к нулевому основанию. Предположим также, что действует следующее правило перехода: “Когда головка находится в состоянии А и считывает 0, заменить 0 на 1, перейти к состоянию В и переместиться вправо”. Молекула фермента, представляющего это правило, имеет место, подходящее для прикрепления молекулы-головки типа А , связанной с основанием 1. Она имеет также место, подходящее для прикрепления основания 0, и место, подходящее для головки типа В (см. рисунок).

Чтобы осуществить требуемый переход, молекула фермента сначала приближается к позиции на ленте, находящейся непосредственно справа от основания, к которому в данный момент прикреплена головка типа А . Затем она отделяет от ленты и молекулу-головку, и основание 0, к которому головка прикреплена, и помещает на их место основание 1. Затем она прикрепляет головку типа В к основанию, находящемуся справа от единичного основания, только что прикрепленного к ленте. На этом переход завершается. На исходном сегменте ленты 0 был заменен на 1, молекула-головка относится теперь к типу В и прикреп­лена к основанию, находящемуся на одну позицию правее исходной.

Гипотетическая ферментная машина Тьюринга может выполнить вычисление с произвольно малой затратой энергии. Молекулы, представляющие биты 0 и 1, прикрепляются к скелетной молекуле. Молекула, представляющая головку машины Тьюринга, присоединена к одной из позиций в цепи (7). Различные типы молекул-головок представляют разные состояния машины. Правила перехода представлены ферментами. На каждом цикле фермент соединяется с головкой и молекулой-битом, связанной с головкой (2), отделяет их от цепи, помещает на их место нужную молекулу-бит (3). Делая это, он вращается, прикрепляя соответствующую молекулу-головку к следующему биту справа или слева от только что измененного. Теперь цикл завершен (4): значение бита изменено, головка изменила состояние и переместилась. Реакции, подобные синтезу РНК, могут рассеивать произвольно малое количество энергии.

Броуновская машина Тьюринга - часовой механизм, состоящий из жестких гладких деталей, неплотно прилегающих друг к другу и поддерживаемых в нужном положении не трением, а системой пазов и зубцов. Несмотря на свободное соединение деталей, они могут совершать только такое крупномасштабное движение, которое соответствует шагу вычислений в прямом или обратном направлении, другими словами, они могут следовать только по одному “вычислительному пути”. Механизм слегка подталкивается очень слабой внешней силой, так что вероятность движения вперед почти такая же, как и назад. Однако в среднем машина будет двигаться вперед и вычисление в конце концов будет завершено. Можно заставить машину затрачивать произвольно малое количество энергии за счет соответствующего уменьшения вынуждающей силы.

Сегменты ленты представлены дисками с канавками, а биты - Е-образными блоками, которые прикрепляются к диску либо в верхнем (7), либо в нижнем (0) положении. Головка состоит из жестких деталей, соединенных в сложный механизм (большая часть которого здесь не показана). К нему подвешены читающий элемент, манипулятор и стержень, имеющий форму отвертки. Машина управляется валиком с нанесенными на его поверхность канавками наподобие валика для проигрывания записей на фонографе (слева вверху, справа в глубине). Различные канавки соответствуют разным состояниям головки.

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

Если инструкция требует изменить значение бита, манипулятор приводится в действие и зацепляет за выступ блока, затем отвертка поворачивает диск, пока блок не освободится, манипулятор поворачивает блок вверх или вниз, а отвертка опять поворачивает диск, так что блок занимает свое место. Пройдя сегмент “записи” управляющего валика, игла входит в сегмент “сдвига” (4). Каждая канавка этого сегмента содержит инструкцию перемещения головки на одну позицию влево или вправо. Далее игла входит в сегмент “изменения состояния” (5), где канавки сливаются таким образом, что игла попадает в канавку, представляющую следующее состояние головки. Теперь цикл завершен (6). Диски, соседние со считываемым в данный момент, удерживаются в нужном положении головкой. Диски, отстоящие дальше, заперты на специальный “замок”. Замок каждого диска связан со специальным битом, называемым Q-битом, соседнего диска. Устройство этой связи таково, что диск, читаемый в данный момент, освобожден и его можно двигать, в то время как диски, удаленные от него как слева, так и справа, поддерживаются в неподвижном состоянии.

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

Машина Тьюринга на основе ферментов не будет свободна от ошибок. Время от времени могут происходить реакции, протекающие без катализа ферментами. Например, основание 0 может спонтанно отделиться от скелетной молекулы, а основание 1 - занять его место. На самом деле подобные ошибки действительно возникают в процессе синтеза РНК.

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

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

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

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

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

Таким образом, принцип неопределенности, по-видимому, не накладывает фундаментальных ограничений на процесс вычисления. Не накладывает их также классическая термодинамика. Означает ли это, что у вычислений нет вообще никаких физических ограничений? Нет, это далеко не так. Реальные ограничения связаны с вопросами, на которые значительно труднее ответить, чем на те, которые мы поставили и рассмотрели в настоящей статье. Например, тре­буют ли элементарные логические операции некоторого минимального конечного времени? Каковы минимальные размеры устройства, способного выполнить такие операции? Поскольку масштабы размера и времени связаны с конечной скоростью света, то, по-видимому, ответы на эти вопросы каким-то образом взаимосвязаны. Однако мы не сможем найти эти ответы, во всяком случае, пока не решится вопрос о том, существует ли какая-то элементарная дискретность в универсальной шкале длины и времени.

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

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