История вычислительных машин

Когда я был студентом, мне на книжных развалах попалась книжка, и называлась она «Малая математическая энциклопедия». Книга была выпущена в Будапеште, и меня довольно сильно удивило, что она была издана на русском языке и в ней хорошо был подобран материал. Я подумал: «Что же такого в Будапеште есть, что там издаются такие книги по математике?» А потом я узнал, что Венгрия — это кузница очень крутых математиков.

Например, в начале XIX века в Венгрии работал Янош Бойяи. И со своим отцом они вместе развивали то, что потом стало называться неевклидовой геометрией, и то, что мы знаем под названием «геометрия Лобачевского». Тогда они создали набор трудов, которые считаются классическими в этой области. Спустя довольно много времени, на границе XIX–XX веков, там работал Альфред Хаар. Он сделал то, что на самом деле «выстрелило» только через век. Он придумал то, что сейчас называется «вейвлет Хаара». Вейвлет — специальная функция, а вейвлет Хаара — это очень простой вейвлет, который повсеместно применяется в цифровой обработке сигнала. И в его честь названы также каскады Хаара. И практически все, кто занимается машинным зрением, знают, что с помощью каскадов Хаара построен алгоритм Виолы — Джонса, который можно встретить в любом фотоаппарате, когда вокруг лица появляется квадратик. Это возможно благодаря каскадам Хаара и его изобретению столетней давности.

Также можно вспомнить, наверное, самого плодовитого ученого всех времен и народов — это Пал Эрдеш, который трудился в середине и второй половине XX века. Он известен тем, что он самый цитируемый человек на Земле. Его ученик и ученик Израиля Моисеевича Гельфанда Эндре Семереди получил в 2012 году премию Абеля за вклад в развитие дискретной математики, теории чисел и информатики. Какие-то из его открытий используются и сейчас. И это тоже венгерский ученый.

Надо сказать, что Эрдеш и Семереди были выпускниками Будапештского университета. И тот же самый университет в 1926 году окончил Джон фон Нейман, только тогда он был не Джон, а Янош. И здесь я бы хотел остановиться. Он защитил диссертацию в 1926 году. Его диссертация очень показательна, потому что она затрагивает очень важный аспект математики. В 1880 году Георг Кантор предложил теорию множеств — то, что теперь называется «наивная теория множеств». И это, конечно, было прорывное открытие, потому что теория множеств обещала объединить всю математику. Это было что-то вроде теории всего для физики. И эта теория говорила, что практически любой объект в математике можно сконструировать в виде множества. Все, что вы ни возьмете, — фигура, функция — это все множество. Просто надо правильно это описать в виде множеств.

И это было достаточно революционным открытием в математике. Но на границе веков Бертран Рассел сформулировал парадокс Рассела, который известен большинству под названием «парадокс брадобрея». Он звучит так: есть брадобрей, который бреет всех, кто не бреет себя. Бреет ли брадобрей себя? И соответственно, если он бреет, тогда получается, что он бреет того, кто бреет себя. А он этого не должен делать. Ровно в такой же формулировке это относится к теории множеств. Если есть какие-то множества, которые себя не содержат, можно собрать их, построить из них множество и спросить: вот это множество, которое содержит остальные множества, содержит себя или нет? Если оно себя содержит, тогда оно не удовлетворяет требованию к своим элементам. А если оно себя не содержит, значит, оно, очевидно, неполное, потому что оно как раз такое же множество. Этот парадокс очень сильно пошатнул положение теории множеств. И ученые бросились спасать теорию множеств, потому что это очень хороший инструмент, который жаль было терять. И начало XX века было посвящено попытке аксиоматизации теории множеств так, чтобы этот парадокс было возможно как-нибудь исключить. И в начале века этим занимались Цермело и Френкель. Они придумали некоторую систему аксиом, которая положила начало аксиоматизации теории множеств. А сам Джон фон Нейман в 1926 году защитил диссертацию, в которой он предложил два способа, которыми можно спасти теорию множеств. И одним из способов была аксиома основания. Она заключалась в следующем: мы не можем утверждать, что что-то является множеством, если мы не можем его последовательно сконструировать, опираясь на известные нам аксиомы.

То есть прежде, чем мы получили какое-то множество, мы должны пройти весь путь от самых простых элементов, от пустого множества и тех аксиом, которые есть, до этого множества просто путем конструирования. Если мы этого сделать не можем, тогда, соответственно, это и не множество. Мы не можем говорить, что оно существует.

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

Затем, после окончания университета, он работал какое-то время в Берлине и в 1930 году уехал в США, где поступил на работу в Принстонский университет. Там он проработал всего три года, и там он пытался заниматься аксиоматизацией уже более сложных задач квантовой механики. То есть он придумал какую-то математику для квантовой механики. В 1933 году фон Нейман согласился на работу в Institute of advanced studies в Принстоне, который был создан совсем недавно, в 1930 году. И в этом институте работали Альберт Эйнштейн, Алан Тьюринг, Гедель, очень многие известные математики и физики, потому что это стало такой Меккой для эмигрантов-ученых. Многие уезжали из Европы в 1930–1940-е годы и находили себе пристанище в этом институте.

В Институте перспективных исследований Джон фон Нейман тоже занимался задачами, связанными с теорией множеств. В том числе он доказал частный случай пятой проблемы Гилберта. Проблемы Гилберта — это те проблемы, которые Гилберт поставил в начале XX века, и он сказал, что их будут решать весь век. И фон Нейман доказал одну из этих проблем в частном случае. А потом круг его интересов начинает немного меняться.

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

В то же самое время параллельно с институтом, в котором работал Джон фон Нейман, этими задачами занимался Конрад Цузе в Германии. И он создавал свои машины Z1, Z2 и так далее, которые тоже являлись универсальными вычислительными машинами. В 1940-х годах одним из военных проектов, который и стал наиболее известным, был проект создания машины ENIAC. Это была первая машина, которая должна была стать универсальным вычислителем. Джон фон Нейман работал над созданием этой машины в качестве консультанта. Он не был основным разработчиком, но проделал довольно важную работу: проанализировал проблемы, возникающие с такой машиной, и написал документ, который назывался «Первый проект для создания универсальной вычислительной машины EDVAC». Это вторая машина, которая должна была появиться в результате работы над ошибками первой машины.

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

Что же это за архитектура? Что предложил фон Нейман и его коллеги, для того чтобы сделать некую хорошую универсальную вычислительную машину? Во-первых (это было, наверное, неочевидно в те годы), он предложил принцип двоичного кодирования. Надо сказать, что сейчас для нас это просто данность. Мы знаем, что вся информация кодируется в двоичный код. Однако в 1940-е годы существовали альтернативные подходы, например троичная логика: 0, -1, +1. И такие машины тоже были. Но именно двоичное кодирование давало существенные преимущества в выполнении некоторых простых операций. Например, очень удобно складывать двоичные числа. И оказалось, что именно этот подход с двоичным кодированием выстрелил в будущем.

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

Затем был очень простой принцип последовательного исполнения: если процессор выполняет программу и выполнил какую-то команду, если не сказано иного, пусть он берет команду из следующей ячейки памяти. Такая архитектура позволяла очень сильно упростить программирование машин. Процессор знал, что ему делать в любом случае, если ему не сказано иное. Например, иное — это команда безусловного перехода. Или команда ветвления, когда процессору говорят: «Подожди, следующая команда будет не здесь, а в каком-нибудь другом месте в оперативной памяти».

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

Надо сказать, что сам Джон фон Нейман после работы над ENIAC вернулся в свой Institute of advanced studies (IAS) и продолжил работу над машиной, которую строил по тем же принципам. То есть параллельно разрабатывалась машина EDVAC и IAS. Это были две разные машины, построенные по похожим принципам. Антиподом Принстонской архитектуры, или архитектуры фон Неймана, является гарвардская архитектура. Она явно постулирует в четвертом принципе совершенно противоположную вещь: давайте мы будем хранить данные и команды в раздельной памяти, а доступ к ним будет по разным каналам, по разным шинам. На основе гарвардской архитектуры построены, например, современные микроконтроллеры. Большинство остальных вычислительных устройств построены по архитектуре фон Неймана (Принстонской архитектуре). К чему же привело использование архитектуры фон Неймана в современном мире? Довольно забавно, что не учли очень важный момент: если вы собираетесь хранить данные и команды в одном и том же месте, вам придется и забирать их одним и тем же способом. И то, что называется шиной (набор проводов, которые соединяют процессор и память), стало узким местом в архитектуре фон Неймана. Оказалось, что доступ к данным, доступ к командам — это очень долгая операция по сравнению со скоростью работы процессора. И поэтому приходится иногда очень долго ждать того, чтобы данные были предоставлены для вычислений.

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

И что же в результате? Получилось, что мы сумели ускорить машины. И в 2017 году произошло очень интересное событие: исследователи обнаружили две очень неприятные уязвимости в большинстве современных процессоров. Они называются Meltdown and Spectre. Они как раз опираются на то, что было использовано для решения проблемы фон Неймана, — на кэш-память. Идея примерно следующая: в большинстве современных процессоров реализуется «спекулятивное исполнение»: если вы исполняете какую-то программу и вам нужно подождать данные из оперативной памяти, то придется простаивать, и вы можете начать исполнять программу немного заранее. У спекулятивного исполнения есть проблема, связанная с тем, что, когда оно утыкается в ветвление программы, оно не знает, по какой веточке идти. И приходится выбирать каким-то образом, используя предсказание переходов. Часто может оказаться, что это не та ветка, которая вам нужна. И оказалось, что только у процессоров компании Intel перед входом в эту ветку в спекулятивном исполнении не проверяются права доступа, имеет ли право программа в эту память «ходить».

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

Эти уязвимости, конечно, очень сильно пошатнули сейчас акции компании Intel и вообще создали прецедент, который надо очень срочно решать. Многие компании, например Microsoft, выпускают патчи для решения этой проблемы. И наверное, очевидным решением является то, что в будущем появятся новые подходы к созданию процессоров либо новые архитектуры. Уже сейчас, например, для вычислений мы далеко не всегда используем классические процессоры компаний Intel и AMD. Многие ученые считают на графических процессорах. Компания Google разрабатывает то, что называется tensor processing unit, для быстрого перемножения матриц. И вообще говоря, процессоры начинают специализироваться. И вполне возможно, что ближайшее время мы увидим какие-то новые архитектуры, которые сильно отличаются от архитектуры фон Неймана и гарвардской архитектуры.