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

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

Почти три месяца прошло с момента публикации первой части этой работы. Всё это время вызревала вторая часть и… наконец, созрела!

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

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

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

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

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

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

И важным моментом здесь является то, что базовый адрес для операций чтения и записи памяти может браться только с таких указателей. С их помощью аппаратура осуществляет контроль выхода за границу массива. О том, что ещё дают пространственные дескрипторы, я скажу позже, когда буду говорить о «контекстной защите».

Теперь временнОй дескриптор – это указатель на функцию, право запускать какую-то процедуру. Указатель на функцию содержит адрес перехода. Во времена Эльбруса был популярен upper-level addressing, то есть статически вложенные процедуры.

Поэтому тогда указатель на функцию включал ещё и ссылку на глобальные данные той процедуры, внутри которой эта функция была описана. То есть, если процедура А описана внутри процедуры Б, то процедура А, вообще говоря, имеет доступ до всех данных, которые доступны процедуре Б. Поэтому в дескрипторе функции А, во-первых, есть адрес перехода и, во-вторых, ссылка на глобальные данные функции Б. Причём на глобальные данные конкретной инкарнации Б. Сейчас я это поясню. В результате цепочки рекурсивных вызовов, процедура Б может иметь несколько живущих одновременно инкарнаций. У каждой инкарнации будут свои собственные глобальные данные. За счёт этого указатели на функцию А, порожденные внутри разных инкарнаций Б, будут разными указателями. Они будут ссылаться на данные, соответствующие различным копиям охватывающей процедуры.

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

Если запускается какая-то процедура, то у неё изначально есть доступ только к регистрам. Регистры доступны все. Но если в них нет ни одного дескриптора, то процедура ни с чем не может работать, кроме как с этими регистрами. Не сработает ни операция чтения памяти, ни операция записи в неё (т.к. процедуре не доступен ни один пространственный указатель). Если на регистрах лежит ровно один указатель, то процедура может обратиться только к одному объекту – тому, на который ссылается указатель.

То есть у каждой процедуры есть контекст. Мы это даже называли «контекстной защитой».

Теперь допустим, что процедуре в какой-то момент времени понадобилось новый массив завести. А это одно из самых привилегированных действий в современных системах. В Эльбрусах для этого использовался контекст операционной системы. В нём содержались указатели на функции. В том числе указатель на функцию «дай новый массив». То, что «get space» называлось в операционной системе Burroughs.

Когда запускается процедура типа «get space», контекст вызвавшей её процедуры закрывается в стеке и открывается контекст самой «get space». В этом контексте, вообще говоря, существует гигантский дескриптор. На всю виртуальную память. А пользователь при запуске «get space», например, запросил массив на 25 слов. У «get space» есть таблица, в которой прописано какие места заняты, а какие свободны. Она находит свободное место и делает непривилегированную операцию: взять подмассив. В результате, получается дескриптор на ту память, которую процедура хочет дать новому массиву. Дополнительно ещё таблица корректируется соответствующим образом.

После возврата из «get space», у вызвавшей её процедуры расширился контекст. И для этого не потребовалось никакого привилегированного действия.

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

Далее смотрите… Вроде бы, из сказанного следует, что дескрипторы нельзя менять. Но это неверно. Дескрипторы можно менять, если нужно. Опять же без привилегированного режима. Смотрите, каким образом. В машине есть операции, которые позволяют менять дескрипторы. Однако они зашиты внутрь специальных процедур, в контексте которых указан особый параметр, позволяющий пользоваться этими операциями. Таких процедур очень мало, и указатели на них есть только в контексте небольшого количества системных процедур. Никаким другим процедурам «ручное» изменение дескрипторов недоступно!

Например, у процедуры «дай память» имеется указатель на функцию, способную изменять дескрипторы. Дело в том, что в действительности мы не пользовались гигантским дескриптором, о котором я говорил выше. Я упомянул о нём только в качестве иллюстрации. На практике большой дескриптор очень неудобен, т.к. приводит к большим виртуальным адресам. Вновь создаваемые дескрипторы будут занимать много места. К тому же «get space» всё равно может через аппаратуру любой указатель выдать, т.к. ей доступна вся память. Почему бы не разрешить ей напрямую создавать дескрипторы?

Это позволит уменьшить их размер. Пусть “get space” сама, выделив какую-то память, нарисует нужный дескриптор. Кроме неё всё равно никто не сможет этого сделать, т.к. только у неё есть необходимый для этого контекст.

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

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

Из-за того, что в памяти всё типизировано, отлаживаться можно просто проверяя дампы памяти. Когда мы сдавали машину Эльбрус два, при этом присутствовал Лёня Райков, руководитель проекта в НИЦЭВТ. А НИЦЭВТ – это организация, которая машины IBM копировала. Мы тогда только-только сделали операционную систему; часто сто терминалов работают; часто там ошибки какие-то возникают. Наши ребята брали дамп памяти. Он структурированный, там типы. Программисты сидели два часа, шли исправлять операционную систему. Лёня Райков негодовал! Потому что у них, когда ошибка в IBMовской операционной системе обнаруживается, несколько месяцев нужно добираться до этой ошибки.

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

Если в памяти реализован ECC-код, то это просто. В Эльбрусе-3 ECC-код есть, поэтому там никаких сложностей не было. Но сейчас во многих машинах нет ECC-кода. Тогда нужно чего-то придумывать. Если, конечно, мы хотим прикрутить к ним поддержку дескрипторов.

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

После всего этого остается добавить чистку памяти. Я сейчас поясню, что это такое.

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

А это будет нарушением защиты. Поэтому память нужно чистить. Но это просто, это операционная система и сейчас может делать.

Сложнее разобраться с указателями на почищенную память. После того, как память освобождена, все указатели на неё нужно найти и уничтожить. Иначе, после того, как освобожденная память будет снова переиспользована, с помощью этих указателей можно будет добраться до чужих объектов.

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

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

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

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

Всё! Помимо тех трудностей, которые я описал, никаких сложностей нет. То есть поддержку объектов ничего не стоит сделать! Но этого до сих пор ни в одной машине нет!

Просто катастрофа, понимаете? Такого свойства, как программирование высокого уровня – до сих пор не существует.

Всё, о чём я говорил выше, практически полностью относилось к пространственной компоненте.

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

И тогда начались работы по ускорению арифметики. Вот я могу похвастаться: моя первая научная работа – в 54-ом году я это сделал, на четвертом курсе Физтеха – это введение carry-save арифметики. Сейчас те, кто арифметикой занимаются, очень хорошо это знают. Это умножение, деление и квадратный корень без переноса разрядов. Довольно очевидная и простая вещь. До сих пор является основой всех вещественных операций. Есть два базовых алгоритма. Один из них я представил в 55-ом году на физтеховской конференции. Первая западная открытая публикация на ту же тему вышла в 56-ом году. Надлер опубликовал.

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

Второй базовый алгоритм carry-save арифметики указывает, каким образом действия первого алгоритма должны выполняться в системах счисления с основанием больше двух. Например, в четверичной или восьмеричной. Введение многоразрядной арифметики позволяет сократить общее количество операций. Эта идея и ее реализация принадлежит Робертсону.

Он в 58-ом году приезжал в Москву, и мы с ним общались очень много.

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

Дальше, конечно, Крэй ввел конвейер. Всего один конвейерный модуль, но тем не менее это тоже параллелизм. Очень серьезный шаг был сделан.

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

К 78-му году мы сделали первый в мире out-of-order супер-скаляр.

Правда, он имел всего 2 конвейера. Сейчас суперскаляр дорос уже до 6 конвейеров. У Power 8 их вообще десять. Но это RISC. Там проще сделать большое количество конвейеров.

Интел сделал out-of-order машину в 95-ом году. Очень большое расстояние получается. 78-ой год и 95-ый. 17 лет! Ужас!

Такой получилась борьба за параллелизм.

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

Теперь посмотрите на нынешний микропроцессор суперскалярный. Это что-то невероятное. Ужасная вещь. Сначала компилятор превращает изначально параллельный алгоритм в линеечку. Потом суперскалярная машина из этой линеечки снова извлекает параллелизм. А затем, из-за того, что языки последовательные, retirement unit выстраивает параллельно исполненные инструкции снова в линейку.

Вот такой зигзаг получается! Ну разве можно это терпеть? Это же просто ужасно. Но люди терпят.

По моим понятиям, суперскалярные машины очень несовершенны (хотя в своё время они оказались очень даже кстати). Мы с коллегами уже давно осознали, что суперскаляр имеет предел… Почему он имеет предел? Потому что вот это преобразование из последовательного в параллельное имеет предел. Декодер в современном интеловском супескаляре должен каждый такт выдавать четыре или шесть команд расшифрованных. А считывание при этом последовательное. Поэтому декодировать шесть операций каждый такт не так-то легко. Декодер x86 ужасно сложен.

В RISKах декодер, конечно, гораздо проще, потому что там фиксированная длина команды. Но там мы всё равно упираемся в ограничение уже следующего порядка, в renaming. Renaming связывает аргументы и результаты различных операций друг с другом, т.е. фактически обрабатывает операции друг за другом по цепочке, что, конечно же, ограничивает распараллеливание. Однако даже если преодолеть каким-то образом ограничения renaming’а, на передний план выйдут задержки bypass-логики.

Но если даже с этим справиться, то всё окончательно упрётся в branch predictor. Точность предсказания переходов резко падает при увеличении уровня вложенности ветвлений.

Таким образом, у суперскаляра есть лимит, предел производительности. Мы это поняли после второго поколения наших суперскаляров, после Эльбруса два. Хотя на момент второго Эльбруса суперскаляр был хорошей идеей. Мы на нём обыграли IBM, в том смысле, что обыграли наших конкурентов из НИЦЕВТ, сделавших EC-1060 – полную копию IBM System/360 (с процессором 3033, который не был суперскаляром).

Мы их обыграли в два раза. Но это было соревнование не с НИЦЭВТ, а с IBM, потому что в НИЦЕВТ сделали clock-precise копию американской машины, то есть повторили её с точностью до такта. И матобеспечение у них всё шло IBMовское. А у нас всё своё.

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

Мы думали: ну, сделать 32 цуга – и будет у нас настоящий параллелизм! Но я допустил тогда ошибку. Я подумал, что это очень сложно, а ведь есть подход попроще – подход широкой команды. Ну мы и решили его попробовать. Ведь мы тогда минусов не знали этой широкой команды…

В итоге, мы сделали широкую команду. Но не такую, как в Itanium. Itanium – это тоже полное, так сказать, недоразумение. Потому что по ширине он такой же, как суперскаляр: 6 команд. И при этом использует статическое планирование. Почему он должен быть быстрее, чем суперскаляр? Не понимаю.

Мы в Эльбрусе три применили подход кластеров.

Из-за того, что в широкой команде нет динамического преобразования из последовательного в параллельное, там обслуживание единого instruction pointer уже не является расточительством.

Каждая команда у нас могла включать до 22 операций. То есть было 22 исполнительных устройства.

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

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

После этого уже в Интеле мы начали делать проект, который позволил бы уйти от ограничений обоих подходов.

Вот я и дошел до сегодняшнего времени. Рассказал и время как менялось, и пространство как менялось. Давайте теперь более внимательно посмотрим на нынешнее время.

Что нужно менять? Почему всё плохо? Ну, во-первых, я уже сказал, что суперскаляр очень сложен. Но самое плохое, что он имеет предел производительности. Его предел — 6 конвейеров – больше нельзя. В Power 8 их 10, но это RISK. Там это легче дается, в x86 – посложнее. Но это «посложнее» сейчас с лихвой компенсируется высоченной квалификацией интеловского коллектива. Квалификация в этом деле имеет огромное значение.

Теперь смотрите, к чему этот лимит привёл. Начинают думать как расширять машину, как логическую скорость подымать. Ну как это можно сделать? Рост частоты сейчас ограничен. Значит, вводится векторная арифметика.

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

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

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

Вектора – это усложнение аппаратуры, причем это усложнение во многих случаях просто не используется. Оно не очень-то популярное.

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

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

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

Это стало одной из причин, по которым провалился проект Larrabee.

А что в идеале нужно для графики? Нужна адекватная аппаратура для реализации явного параллелизма.

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

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

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

То есть фактически что потребовалось? Потребовался явный параллелизм. Вот это последовательное представление программы и в памяти, и во времени стало обузой. Из-за линейного пространства у нас нет type-safety, потому что нет поддержки объектов. В пространстве все упорядочено.

А к чему приводит упорядоченность во времени? К тому, что языки тоже сделаны упорядоченно. Вообще разработчики языков понимали, что явный параллелизм – это важная вещь, и они вводили параллельные языки. Это Алгол 68, это Ада. Там явный параллелизм итераций. Явный параллелизм – значит, должна быть обязательно синхронизация. Вот разработчики сделали свой язык, параллельный язык с синхронизацией. А потом компилятор транслирует его на последовательную машину. Никакой пользы от того, что язык параллельный, нет. Только головная боль программистам. Потому что когда в языке есть явный параллелизм, иногда dead-lock’и получаются. Поэтому такие языки не прижились. А сейчас они крайне важны!

Значит, еще раз, чтобы проследить логику: современный суперскаляр очень сложен и к тому же имеет предел скорости. Чтобы преодолеть этот предел вводятся векторизация и multi-threading. А то, что действительно нужно – это явный параллелизм.

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

Такая ситуация сохранялась до тех пор, пока не появилась 360-ая машина от IBM. С появлением 360-ой, компания IBM фактически заявила: «вот, раньше для каждой машины свои программы писали. Новая система команд — новое поколение, новые программы. Давайте сделаем так, чтобы 360-ая имела одну и ту же систему команд для многих моделей. Есть быстрые, есть медленные модели, но компилятор транслирует код всего один раз, и этот код может исполняться на всех моделях». Это то, что мы сейчас имеем.

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

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

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

Когда подкачка эта отлаживается на конкретной модели, программа исполняется быстрее. Через два-три года появляются другие модели – и эта же программа может работать на них медленнее, чем на старой машине. Мне один коллега байку рассказывал: когда ему необходимо было выйти к пользователям, у которых программа медленно работала, он прежде всего программную подкачку отключал. Программа обычно быстрее начинала работать. Это всё потому, что подкачка model-dependent. Компилятор не может её делать эффективно.

Таким образом, что мы имеем? Компилятор не совсем хорошо знает алгоритм и совсем не знает аппаратуру. Поэтому аппаратуре приходится самой выкручиваться. В частности, в ней запрограммирована работа кеша. Но как запрограммирована эта работа? Железо не может делать предподкачку, оно качает код только с оглядкой назад. По типу least recently used. Всё это может идти в разрез с тем, как данные используются алгоритмом.

Чтобы хорошо оптимизировать, нужно алгоритм знать. Что, конечно же, недоступно аппаратуре.

Но что теперь нужно сделать, чтобы исправить ситуацию? Нужно компилятор сделать model-dependent. Притащить его прямо к аппаратуре.

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

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

Сейчас доступ к общей памяти занимает 200 тактов, что значительно больше времени выполнения любой операции. Поэтому мы имеем кеши. Кеш, по смыслу, — это локальная вещь. А из-за того, что моделируется шина, работа с кешем воспроизводит в некотором смысле работу с общей памятью. В результате имеем сложный алгоритм взаимодействия кешей. Если происходит запись в конкретный кеш, то приходится брать ownership над лайном и пр.

Простой подход здесь – это ввести локальную память вместо кеша. Тогда промахов в кеш почти не будет. Локальная память должна обслуживать только конкретное ядро.

Ведь сейчас же как делается? Идёт программа, работает какое-то ядро. Оно с какой-то памятью работает. И не известно: есть ли на другом ядре параллельная работа с той же памятью или нет. На всякий случай, приходится предполагать, будто такая работа ведётся. Приходится memory-model выдерживать. Это сильно замедляет машину. Это глупо!

Имей мы явный параллелизм, всё можно было бы сделать гораздо эффективнее. Если программист в языке явного параллелизма сказал, что с какой-то конкретной частью вычислений никто в параллель на общей памяти не работает, то ядро может никуда наружу не обращаться. Может работать с прямо адресуемой локальной памятью. Нынешние кеши – это дикая дань старому. Уже давно технология изменилась, а все равно имитируется bus structure.

Оговорюсь, что локальную память я очень осторожно предлагаю. Я эту идею пока ещё не прорабатывал. Но думаю, это можно сделать.

Посмотрим на ещё один архаизм – retirement. С введением явного параллелизма, его нужно будет убрать. Не нужна единая последовательность инструкций. Полная линеаризация сильно затрудняет достижение эффективности. Конечно, как-то придётся решить зависимость между чтением из памяти и записью в память, но это другое дело. Я считаю, что такие зависимости должны быть явно указаны программистом, а их эффективное отрабатывание – уже дело компилятора и аппаратуры. В частности, если зависимость не лежит на критическом пути алгоритма, то с ней и делать особо ничего не надо. Зависимая операция просто должна дождаться выполнения той операции, от которой она зависит. С зависимостями, через которые проходит критический путь, всё немного сложнее. Если здесь упорядочить все зависимые операции, то можно сильно потерять в производительности. Поэтому нужно использовать data speculation и грамотное планирование, которое будет стараться разнести зависимые операции на как можно большее расстояние друг от друга.

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

Я много уже сказал. Но какой, в итоге, у меня облик самой прогрессивной машины будущего?

Вот смотрите. Есть алгоритмы. Надо сделать так, чтобы и пространственная, и временнАя компоненты в программах были полностью эквивалентны алгоритму. Для этого вводится язык явного параллелизма. Над ним надо поработать. В этом языке обязательно присутствует type safety. Это первое.

Второе – вводится простой перекодировщик. Упаси бог какие-то оптимизации на этом этапе делать. Это задача компилятора, а перекодировщик должен просто перевести программу в двоичное представление.

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

Далее нужно решить вопрос с кешем.

Это наиболее сложное место. Наименее исследованное. Я с некоторой опаской, с некоторым прогнозом вперёд утверждаю, что кеши просто нужно выкинуть. Кеши – это дань старинке. Нужно ввести прямо адресуемую память.

Потом retirement тоже нужно выкинуть.

После всего этого машина становится дико простой. В такой системе необходимо будет ввести спекулятивность: и data speculation, и control speculation. Далее будет очень простой scheduler, значительно проще, чем в суперскаляре. Кое-что нужно будет добавить для правильного исполнения условных переходов и входов в процедуры. Ну и исполнительные устройства понадобятся. А больше ничего не нужно.

Теперь немного про универсальность такой машины. Но это я с некоторой опаской говорю… Недавно я посмотрел на структуру кристалла смартфона Qualcomm’овского. Там приблизительно 11 квадратиков. Один из квадратиков – это универсальный процессор, всего 15% площади занимает. Дальше, стоит графика. Её на современных языках и машинах программно нельзя сделать. Это мы знаем. А на машине с поддержкой явного параллелизма она элементарно получается. Значит, квадрат с графикой в универсальный квадрат уходит. Дальше мы видим DSP. DSP – это же цикл, причем не самый сложный. На универсальной машине его легко будет исполнить. Что касается остальных квадратиков, я не очень знаю алгоритмы, для которых они предназначены. Но я попросил людей разобраться с каждым из них. Дополнительно я связался с человеком в США, который со смартфонами работает, и попросил у него информацию о задачах, которые исполняются этими квадратиками.

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

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

Однако если это так, то жизнь разработчиков смартфонов станет значительно легче.

Сейчас они вынуждены работать сами с большим количеством сложных устройств. Их конкуренция становится очень тяжелой.

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

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

Ещё раз подчеркну, что сейчас происходит. Современное состояние вычислительной техники не сильно отдалилось от того первоначального, когда всё было линейно.

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

А этот предел в каком-то смысле уже неулучшаемый. Тут мне могут сказать: наверное, что-то у тебя с головой не в порядке. Что значит «неулучшаемый»? Прогресс остановился, что ли?

Ну, так бывает. Сейчас все признают, что суперскаляр почти остановился в развитии. Машина – это конечное образование. Если это конечное оборудование, значит число различных процессоров, по крайней мере, теоретически конечно. Среди этого конечного множества какой-то есть самый хороший. Значит в принципе есть неулучшаемость. Гениальность интеловских разработчиков в том, что они практически достигли эту неулучшаемость. Они не теоретически, а на практике достигли её. Сейчас нужно через это перешагнуть – ввести явный параллелизм. Тогда пределом будет сам алгоритм. Если в алгоритме есть какой-то параллелизм – его уже не перепрыгнуть. Если кто-то скажет: а я могу модифицировать алгоритм, и он станет быстрее – я скажу: ага, ну давай, модифицируй, мы возьмем этот модифицированный алгоритм и исполним его лучшим образом. Пожалуйста, всё хорошо.

Ну вот, пожалуй, всё, что я хотел сказать. Не знаю, как вам, ну а на меня это очень большое впечатление производит.

Автор благодарит Александра Останевича и Сергея Шишлова за помощь в подготовке материала.

Спасибо!

Автор: TechThink

Источник