Железо на службе у алгоритма

Борис Бабаян о прошлом, настоящем и будущем вычислительной техники

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

Мне удалось побеседовать на эту тему с Борисом Арташесовичем Бабаяном, директором по архитектуре компании «Интел».

Борис Бабаян известен как главный архитектор компьютерных вычислительных систем «Эльбрус-1», «Эльбрус-2» и «Эльбрус-3». Некоторые из его идей использованы в архитектуре Transmeta. В настоящее время Борис возглавляет разработку новой микропроцессорной архитектуры в компании «Интел».

Чтобы совсем покончить с формальностями, перечислю звания, степени и должности Бориса: член-корреспондент РАН, доктор технических наук, профессор, заведующий кафедрой «Микропроцессорные технологии» МФТИ, Intel Fellow, лауреат Государственной и Ленинской премий.

Дальнейшее повествование построено от лица Бабаяна. Мои скупые комментарии оформлены в виде врезок либо ссылок на интернет-страницы.


Уместно задать вопрос, о чем я буду говорить. Ответ, возможно, покажется очень необычным: обо всём. Обо всём, чем занимаюсь я и мои коллеги. Я думал о проблемах своего нынешнего проекта и о том, что дальше делать. И я глубоко прочувствовал, что в нашем деле всё между собой тесно связано. И архитектура, и языки программирования, и операционная система. Ну, всё-всё-всё вместе, понимаете? Об этом и будет мой рассказ.

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

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

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

Всё, это было последнее предисловие. Теперь начнем.

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

Начнем с алгоритмов. Алгоритмы – это нечто абстрактное, нечто вечное. Как числа, например. Может существовать множество разных алгоритмов, и каждый из них вечен.

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

Теперь пространственная компонента. Пространственная компонента тоже параллельна и структурирована. Что она из себя представляет? Это объекты, с которыми работают операции. Масса объектов. Эти объекты могут ссылаться друг на друга, быть вложенными друг в друга. Но их много и с ними работают разные операции. Очень всё параллельно.

Вот что такое алгоритмы.

А железо? А железо, в отличие от алгоритмов, не вечно. Оно сильно меняется в течение времени. Вначале железо было очень примитивным. Когда я начинал… — а начинал я на Физтехе, в 51-ом году туда поступил – так вот, тогда ещё первая БЭСМ не работала. Один бит информации тогда был представлен двумя электронными лампами. Это кубический дециметр! Невероятный объем. И было всего одно исполняющее устройство. Оно занимало три комнаты. Как я всегда шучу, перенос бита начинался в одной комнате, а заканчивался через две комнаты. Это ужасный размер.

И посмотрите, что сейчас. На одном кристалле невероятное количество исполняющих устройств размещается.

А ведь БЭСМ-первая была уже далеко не первая. Самые первые машины я не видел. Например, Урал. Это была строго последовательная машина. Бит-последовательная машина. То есть был магнитный барабан. По одному биту с него считывалась информация. Далее считанные значения, например, складывались и снова по одному биту писались на барабан. Ужасно. Но нужно было такие машины проектировать. Куда деваться? Тогда не было никакой возможности отразить на аппаратуру такое невероятное великолепие, как параллелизм и во времени, и в пространстве. Просто даже нечего было говорить об этом.

Нужно было упрощение. Ну какое упрощение было бы в данном случае естественным? Линеаризовать всё! Всё в линеечку превратить. Это очень просто. Ничего не стоит параллельный алгоритм превратить в линейку. Причем и в пространстве, и во времени. Вот первые машины так и были сделаны. И это гениальное решение, конечно. Хотя… трудно назвать его гениальным, раз уж оно такое простое. Но это эффективное решение для того времени. Потому что превратить сложный алгоритм в линейку – никакой оптимизации не нужно. Компилятору это делать проще простого. Правда, тогда про компиляторы и языки программирования вообще не слышали. Все в битах программировали. Состояние вычислительной техники было такое, что не позволяло ориентироваться на программистов. С ними вообще не считались. Программисты работали с тем, что давали им разработчики аппаратуры. Да и программы были крошечные. Поэтому проще и эффективнее было в битах писать, чем на каком-либо языке. Тогда использование языков было пустой тратой машинного времени.

Моей любимой шуткой в те времена было, что настоящие мужчины работают в ассемблере, а языки – это так, баловство.

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

Сейчас без моделирования нельзя. Современные архитектуры очень динамичны. Невозможно их оптимизировать, не проводя моделирования. А в ту эпоху время исполнения приложения равнялось сумме времен исполнения отдельных операций. Ничего не нужно было моделировать, всё и так было понятно. Никаких регистров не было и кешей не было. Первый БЭСМ так и работал: считывал одно число из памяти, второе число, выполнял операции, писал обратно. Считывание из памяти, по сравнению с операцией, происходило мгновенно. Операции тогда занимали многие такты.

Пространство тоже было очень простым. Никаких объектов не было. Была просто последовательность битов.

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

Жизнь программиста была непростой. Каждая новая машина – новая система команд. Все программы переписывались. Спасало только то, что программ очень мало было, так что с переписыванием можно было мириться.

Таким было начало.

Трагедия заключается в том, что совместимость с этим началом мы имеем до сегодняшних дней. Все современные системы команд – линейны. Хотя аппаратура сейчас очень параллельная. И это очень плохо. Это усложняет программирование. Масса ошибок возникает. Мы имеем большие проблемы с безопасностью из-за указателей, которые позволяют из произвольного места до любой информации достучаться. Ужасно! Но и это ещё не всё. От первых персональных машин нам досталась шина. Аппаратура в то время ещё не была параллельной, и процессоры имели только одно исполнительное устройство. Но сами процессоры уже могли работать параллельно друг с другом на общей памяти. Как раз для этого им и нужна была шина. Шина создавала строгую упорядоченность всех обращений к памяти со стороны всех процессоров. То, что сейчас называется strong ordering или memory model.

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

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

Отсюда пошли проблемы с совместимостью.

Сейчас уже давно нет шины. Тем не менее, во всех машинах моделируется та шина, которая была в самых первых машинах. Конечно, ее чуть-чуть изменили. Разработчики P6 посмотрели, что если строго выполнять memory ordering, то теряется 25% производительности. Поэтому они ввели одно облегчение: чтения из памяти могут обгонять записи в память. Но по-прежнему чтения не могут обгонять друг друга, записи не могут обгонять друг друга, а также записи не могут обгонять чтения.

А можно было бы все отменить и сделать по-новому. Мы в Эльбрусах никогда шинами не пользовались. У нас cross-bar-switch с самого начала был.

Так вот: юмор заключается в том, что до сих пор моделируются первые машины. Причем не только в железе, но и в языках программирования. Все языки программирования испорчены. Они очень далеки от алгоритмов – от того, что я назвал параллельным временем и параллельным пространством. Они ближе к самым первым машинам, где все последовательно.

Мы видим, что совместимость взяла всё мертвой хваткой, и изменить это очень трудно.

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

Итак, пространственная… С ней все очень просто. Это объекты. Значит, машина должна работать с объектами. Когда мы начинали первый Эльбрус, мы не думали о безопасности.

Как я уже говорил, никаких проблем с безопасностью тогда не было. Мы занялись объектами, чтобы поддержать языки высокого уровня. Мы тогда задумались: что должен собой представлять язык высокого уровня? В то время, в 72-ом году, считалось, что программирование высокого уровня обеспечивалось такими языками как Algol и Fortran. Но мы быстро сообразили, что существующие языки ориентированы на существующие машины, где всё последовательно. Следовательно, пытаясь поддержать существующие языки в новой машине, мы бы фактически ориентировались косвенно, через языки, на существующие архитектуры. Это глупость!

Отмечу, что в то время уже существовали машины с поддержкой языков высокого уровня. Например, фирма Burroughs выпускала машину, которая исполняла Extended Algol. Типы данных там реализовывались через теги, которые хранились в памяти вместе с данными. Это была хорошая идея, и мы позаимствовали её у Burroughs. Но то, как они использовали эти теги, было просто недоразумением. С помощью тегов Burroughs поддержала на аппаратном уровне статические типы. Работало это так: каждой используемой ячейке памяти жестко приписывался некоторый тип. Эта информация применялась для автоматического преобразования данных во время их записи в память. Если, например, вещественное число сохранялось в область памяти, отмеченную тегом целого числа, то машина динамически превращала вещественное в целое перед тем, как осуществить запись.

Поддержав существующие статические языки, Burroughs, по сути, поддержала старую аппаратуру, потому что именно на нее были ориентированы статические языки. Просто глупость получается! Burroughs, разрабатывая новую архитектуру, в итоге ориентировалась на старые машины. К тому же теги можно было менять на ходу в непривилегированном режиме, что тоже большая глупость.

Однако, справедливости ради, надо отметить, что динамическое приведение типов далось Burroughs почти бесплатно. Для такого преобразования необходимо было при каждой записи в память узнавать тип ячейки, в которую сохранялись данные. Это нужно было для того, чтобы узнать, каким образом данные должны быть преобразованы. Получается, что каждая запись в память требовала предварительного считывания. Такие лишние чтения выглядят ужасным расточительством. Но дело в том, что тогда использовалась ториковая память. Перед тем, как писать в такую память, её нужно было размагничивать. А размагничивание делалось посредством чтения. Поэтому считывание типа ячейки во время записи не приводило к дополнительным накладным расходам. Оно просто совмещалось к размагничиванием.

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

Вот как устроены алгоритмы? Представим, что исполняется некоторый алгоритм. Если он генерирует новый объект, ему не нужны никакие биты. Объект, ну, в пространстве появляется, что ли. К этому объекту, вновь сгенерированному, только текущий алгоритм может обращаться. Никто больше про него просто даже не знает. Потому что его сгенерировал конкретный алгоритм. Абстрактный алгоритм, а никакое не железо, понимаете? Такое должно быть и в железе поддержано как-то.

Далее, каждый объект имеет тип. Значит, мы должны и типы поддерживать. Сначала мы пытались очень экстремистский подход применить: целые, вещественные в тегах были написаны. Но потом мы увидели, что это совершенно не нужно. Не нужно любые типы поддерживать в тегах. И вот почему.

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

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

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

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

В итоге, мы пришли к тому, что язык высокого уровня – это динамический язык со строгим контролем указателей. Точно к такому выводу, фактически независимо – мы особо не контактировали и почти не читали друг друга – пришел Никлаус Вирт. Это человек номер один в языках. Он тоже осознал, что программирование высокого уровня строится на type safety и динамике типов.

Вирт создал динамический по типам язык Эйлер. Он был невероятно интересный. Все просто в восторге были от этого языка. Но ему недоставало эффективности. Потому что он не поддерживался аппаратурой. Была масса динамического контроля. Тогда Вирт сдал назад. Он сказал: да, типы должны быть, но пусть они будут статическими. И контроль должен быть… но, может быть, не очень сильный, потому что, например, контроль выхода за границу массива требует дополнительных команд.

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

И что в результате получилось? Мы сделали настоящий язык. У нас были теги. То есть ко всем данным добавлялись несколько разрядов, описывавших тип. Мы сделали контроль указателей. Одним словом, мы создали Эль-76. Это покойный Володя Пентковский сделал. Он тогда программистом был.

На Эль-76 была написана операционная система Эльбруса. Это уже Сережа Семенихин сделал. 26 человек в середине 70-х годов сделали операционную систему: мультипрограммную, мультипроцессорную, мультитерминальную. В то время в основном пакетный режим везде использовался. А у нас такая развитая операционная система!

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

Наши машины использовались в очень ответственных системах. Противоракетная оборона Москвы, контроль космоса, атомные проекты в Арзамасе. При этом все наши пользователи говорили: отлаживать на этой машине – в 10 раз быстрее, чем на старых машинах. Впечатление было такое, будто работаешь с постоянно включенной отладочной системой. Причем без потери эффективности.

Когда наши ребята получили западные машины – в начале 90-х годов – они ко мне стали подходить и говорить: как на этих машинах можно работать? На них нельзя отлаживать программы. Ужасно!

Теперь посмотрите, что же стало с этим подходом! Исторически. Мы выпустили первую машину в 78 году. Тогда же прошел первый тест по операционной системе. До 82-83 года широко в нашей стране использовались Первые Эльбрусы. Примерно в это же время во многих университетах мира шли исследовательские работы в области type safety. И Интел тоже заинтересовался этим подходом. Они тоже сделали type-safety-машину, 432-ую. Спросите у любого интеловца, знает ли он, что Интел в истории имеет 432-ю машину. Ответ будет: нет, не знает. Об этом вспоминать-то стыдно! Просто позорная машина. Она обеспечивала type safety. Но там элементарные ошибки были.

В 432-ой была реализована защита укзателей, что конечно же, очень правильно. Однако все указатели хранились в отдельном сегменте. Назывался он program reference table. Машина контролировала, что находиться в этом сегменте могут только указатели. И нигде, помимо него, указателей больше не могло быть. Я почитал их бумаги. Они говорят, что всё это очень здорово, но очень неудобно указатели в отдельном сегменте держать.

Указатели должны рассылаться как обычные данные. Мы так и сделали. У нас указатели – просто данные. А 432-ая держала указатели в отдельном сегменте. Это приводило к ужасным результатам. Например, для индексации массива требовалась трёхадресная операция. Нужно было указать три операнда: положение указателя на массив в поинтерном сегменте, положение индекса в сегменте данных и снова смещение в поинтерном сегменте, по которому требовалось записать результат. Но самое ужасное даже не это, а то, что при входе в процедуру, у операционной системы запрашивалось четыре сегмента! Два сегмента для параметров: поинтерный и скалярный. И два сегмента для локальных данных: тоже поинтерный и скалярный.

ЦК и Совмин тогда копировали западные машины, и с появлением 432-ой распространили по учёным бумагу: вот, надо копировать эту машину. Так как я был защитник идеологии type-safety, меня включили в комиссию. Эрнст Фильцев возглавлял её. И я написал тогда большую телегу против Интела. Написал, что машина плохая и что через несколько месяцев она провалится. И она провалилась. Когда я пришел в Интел, то нашел статью Боба Колвелла, того гениального человека, который P6 создал. Он анализировал 432-ую машину и пришел к тому же выводу, что и я: идея колоссальная, но реализация никудышная. В статье Колвелла есть конкретные цифры. Например, вход в процедуру занимал до пятидесяти обращений к памяти. Как можно было на такой машине работать?

Как я уже сказал, 432-ая прожила недолго. Но что после этого стало с type safety? В каких направлениях стали развиваться языки и аппаратура?

Продолжение следует…

Автор благодарит Андрея Доброва, Александра Кима, Дмитрия Масленникова и Александра Останевича за помощь в подготовке материала