Comments 55
фундаментальный труд, нынче редкость на хабре
Вот это фундаментально. Я читать-то устал (это при том, что процентов 90 материала мне знакомо), а уж сколько трудов это потребовало для написания... Снимаю шляпу.
Спасибо.
Такое (статьи состоящие сильно более чем из кликбейтного заголовка и вступления) надо как-то поощрять.
Спасибо за хорошую подачу материала (и отдельно за конструкцию на обложке - она тоже потрясающая). Есть что обдумать.
Весьма и весьма позновательно. Вроде и знал большую часть, но неупорядоченно и невыровненно. А тут прям знания выстроились последовательно, разлеглись по страницам памяти и выровнялись по смещению.
PS: "Три архитектуры эльфам, семь гномам, девять людям… где же искать ту, что объединит их все?" - жаль, но в Мордоре точно нет.
Спасибо за статью. Идеальный баланс сложности темы и уровня подачи. Нынче это редкость.
Статья очень подробная, хотя в начале статьи подача материала неравномерная, что-то можно было бы сократить, что-то разжевать более подробно.
Предложенные в конце идеи - интересные. Планируется ли работа над реализацией предложенных идей в виде процессора - пусть даже на FPGA? Было бы интересно сравнение производительности предложенной архитектуры с современными суперскалярными на реальных задачах.
Что же, на Nios II/f есть и предсказания переходов и какой-никакой кэш.
В данный момент нет у меня таких планов.
Спасибо, огромный труд. По существу это overview книги о микропроцессорных архитектурах.
ПС
Интересно про TRIPS-архитектуры (может быть вы в курсе): по существу компилятор какого-нибудь pure functional language сохраняет весь необходимый параллелизм при построении лямбда-функции (если его насильно не стирать раньше времени) -- там же непосредственно готовность по аргументам идёт.
То есть это собственно таргет для связки "хаскель без монад" + TRIPS.
Но нагуглить запрос с TRIPS + execution / emulation + Haskell / pure functional language не удалось.
Неужели такая идея (использовать FP-languages + TRIPS) совсем не рассматривалась, а если рассматривалась - то что из этого вышло (навскидку узкое место вероятно опять же память)?.
Хаскель без монад - это Clean - https://clean.cs.ru.nl/Clean , там вместо них используется подход Rust (вернее это Rust использует наработки Clean).
Вообще, внутри современных компиляторов типа Шланг, используется представление SSA - это как раз и есть "функциональщина".
Простите но называть SSA-IR "функциональщиной" - это крайне вольная трактовка.
Ну и вопрсо был, разумеется о другом. А именно о том какой код создаёт высокоуровневый ЯП.
И насколько этот код "дружесвенет" \ "не дружесвенен" к архитектуре процессоров.
В любом случае спасибо за ответ.
Ну высокоуровневый ЯП создаёт такой код, какой компилятор вы делаете. Сейчас массовый компилятор целится либо в RISC, либо в x86, либо в стековую виртуальную машину, выполняющуюся на том же RISC/x86.
В учебном курсе nanopass, где отлично прописаны стадии, начинаете вы со Scheme, потом:
1. Переименовываете переменные так, что все имена уникальные; явно вычисляете аргументы всех арифметических операций и функций, присваивая их временным переменным.
2. Переходите в трёхадресный код, разделённый на блоки с последовательными командами - это упрощённый C, где все выражения имеют вид x = f(y, z) (y, z - переменные)
3. Распределение регистров и перевод в ассемблер.
То есть, какая-то там параллельность кмк "теряется" на шаге 2.
----------------------------------------
В статье "Баллада о Мультиклете" - https://habr.com/ru/post/163057/ в конце как раз упоминалась "параллельная" обработка pattern matching, но там Хаскель не нужен - достаточно того, что код в ветвлениях очевидно для компилятора "чистый", а ветвления сложные и многоветочные. То есть, не if, а switch. Подобное есть и в С, но в языках без алгебраических типов данных удобнее многоступенчатый if.
То есть, чтобы одновременно спекулятивно идти по 3 веткам, нужно, чтобы люди использовали языки с pattern-matching, где писали что-то вроде
match orders with
| [] -> "No orders"
| (Some name)::tl -> "Order " ^ name ^ " out of " ^ string_of_int ((List.lenght tl) + 1)
| None::_ -> "Nameless order - error"
Есть ещё статья "C is not a low level language", которая тоже близка к поднятой вами теме. Мы с коллегой обсуждали её - ощущение, что не хватает каких-то инструкций ассемблера в современных десктопных процессорах, то есть их API неполон. Поэтому просто замена С на что-то не спасёт - нужно как-то изменять ассемблер.
Я не понимаю какую мысль вы хотите донести этим набором вполне разумных утверждений.
Если мы говорим о параллельности уровня "спекулятивно загрузить 3-4 АЛУ через ОоО" - то да вполне можно "подправить" практики программирования на императивных языках.
Но разумеется у нас будет trade-off: в архитектурах (стандартных на сегодняшний день) где нет большой избыточности АЛУ - будет падение производительности, в архитектурах с большой избыточностью АЛУ (по сегодняшним меркам) - ожидаем повышения производительности.
-- Это примерно то, о чём вы написали.
===========================================================
Но мой поинт совсем не в этом.
DataFlow архитектуры предполагают десятки простых АЛУ.
А тут уже как ни правь "практики программирования на Си" - такое в параллель не загрузишь: look-ahead для компилятора императивного ЯП крайне сильно ограничен: обычно это до следующего "volatile глобала" или "мубательного глобала без доказанного отсутствия alias", или до нечистой функции. Дальше всё - в IR посылается непараллельный код.
Так вот семантика (высокоуровневой!) программы на чистом функциональном ФП как раз такова, что можно десятки АЛУ в параллель загрузить, если эту параллельность искусственно не резать.
Поэтому идея такая: либо TRIPS + Haskell (без монад, которые рвут параллельность) хорошо работают на эмуляторе. Либо TRIPS не работает вообще.
Удивительно, что таких оценок мне не удалось нагуглить.
Проблема еще в том, что нет операционной системы, написанной на Haskell,
т.е. для работы с TRIPS всё равно нужет компилятор С, а он сильно неэффективный.
Если предположить, что это так: то зачем тогда вообще такие процессоры рассматривать (вкладыть деньги, проводить R&D) как GP-процессоры?
Это программа DARPA Polymorphous Computing Architectures,
"пусть расцветают сто цветов" и всё такое.
Спасибо за упоминание этого языка. A в Clean есть Termination checker?
По-моему, нет. Там есть, кмк, основные интересные штуки из Хаскеля, за исключением многопоточности и STM (software transactional memory). Плюс компилятор Клина очень быстрый, а линейные (уникальные) типы занятны. Но, увы, сообщения об ошибках ужасны, а сам он отдаёт некоторой наркоманией самобытностью (к примеру руководство написано на самом Clean, вместо LaTeX, как делают нормальные люди).
В общем, я его использую как эргономичный компилятор Хаскеля (0.1 сек компиляции 200 строк простого кода на Core2 Duo/ALT Linux - запредельная скорость для GHC).
пусть не постесняется написать об этом
А если полностью убрать понятие регистра, понятие адреса памяти.
Ввести понятие «нет данных».
Исполнение команд по готовности данных (большим числом уровней).
Сделать программу в виде ациклического направленного графа
Убрать циклы и ветвления (за счет конструкции «нет данных»).
Сделать что то похожее на NArch(+), но с числом исходных данных (параллельных) в районе миллиона, представьте пиковая производительность 10Е15 команд в секунду.
Принципы организации сети передачи данных для такой вычислительной системы уже есть ( habr.com/ru/post/512652) потенциальные скорости передачи от 10Тбит (сегодняшние технологические возможности позволяют). Данные для обработки «лежат» в буферных регистрах сети (доступны параллельно). Результат можно сразу отправить в такие же буферные регистры (даже на соседнем кристалле) и самое главное в оптимальном для обработки порядке.
Понятно что не все так просто, но…
Сделать миллион сумматоров и заставить их параллельно что-то суммировать не проблема.
Вопрос в осмысленности такой конструкции.
Какую задачу вы собираетесь решить?
Какую задачу вы собираетесь решить?
Заставить такой процессор исполнять программы написанные на языках высокого ровня (СИ и тд), преобразовать ассемблер будет даже проще.
Проведите мысленный эксперимент:
Возьмем любую функцию (Изначально созданную на языке высокого уровня).
Выполним ее и запишем последовательность исполненных ассемблерных команд.
Для простоты понимания выделим из этих команд только те, которые производят изменения данных, их будет примерно 20% от общего количества.
Построим граф где вершиной будет команда, ребра будут результатами исполнения или данными имеющимися на момент начала вычисления
Получаем ориентированный ациклический граф, вычисляющий значение функции для данного конкретного набора данных. Эксперимент показывает, что есть возможность превращать обычную программу в программу (ациклический граф) для новой вычислительной парадигмы.
Да, реальный компилятор будет сложнее, но принципиальная возможность есть.
Превращение программы в ациклический граф - одна из стадий компиляции.
Это не совсем новая вычислительная парадигма.
А как насчет зависимостей по данным?
Зависимость по данным: строго последовательные задачи такая же редкость как и строго параллельные.
Можно использовать такой подход:
Решаемая задача имеет текущее состояние (память переменных, обрабатываемые данные и тд), в момент прихода воздействия (сигнал обработать данные, тик таймера, или любой сигнал) производит вычисление нового состояния (значений и списка переменных).
Каждая переменная зависит только от текущего состояния и пришедшего воздействия. Значит можно параллельно (полностью независимо) запустить вычисления всех переменных нового состояния.
Только после вычисления нового состояния, программа начнет влиять на связанные с ней «сущности». Если на кого то влияют от промежуточные переменные, то этот объект не является самостоятельным (является частью этой программы).
Можно даже сказать, что средняя персоналка это программа, входными данными для которой является нажатие клавиши и другие внешние воздействия.
Понятно, что вычислять все это строго независимо смысла нет и можно обмениваться промежуточными данными (если это эффективно), но базовый посыл именно такой.
А если гарантировать последовательное исполнение (без циклов и ветвлений), получится очень эффективная система. Вычислять всю «операционную систему» за один раз не эффективно, если «технология» выстрелит, то лишние зависимости будут удалены.
Вот примерно из таких мыслей проистекает уверенность в возможности прокормить «миллион сумматоров». Скажу даже что их будет сотни миллиардов (не все одновременно). Изобретенная символьная сеть позволит передать данные в темпе: одно данное на 5 инструкций. Реализацией DSM на символьной сети уже начали интересоваться крупные компании — пока медленно (большая компания большая бюрократия). Мелкие говорят (те кто откликнулись), что это слишком серьезный проект. Военные все выслушали, позадавали вопросы и вынесли вердикт: «Официального ответа на Ваше обращение не будет». Надеюсь что надписи на терминаторе будут кирилические, хотя есть вероятность что и китайские.
Статья действительно эпохальная, но всё же отмечу исторические неточности:
В статье у 68000 становится то 8 РОН, то 16, но на самом деле у него 8 регистров данных, которые не могут быть указателями (но могут быть индексами), и 8 регистров адреса, которые могут быть указателями, но с ними можно делать только, по сути, адресную арифметику, и при этом один из них -- указатель стека.
DEC J11 никак не относится к VAX'у, это реализация архитектуры PDP-11. И к тому же 16-битный.
Ни NS32K не был развитием VAXа, ни interdata 8/32 не была реализацией IBM/360, об этом прямо по ссылкам в вики написано. Влияние было, но не более того.
Ещё. Я бы не стал жёстко связывать дихотомию микрокод-не микрокод с дихотомией CISC-RISC. Ну например, некоторые машины из семейств IBM/360, PDP-7, PDP-10, PDP-11 были БЕЗ микрокода, при этом являясь махровыми CISCами (собственно микрокод и изобрели, как способ сэкономить на железе ещё в те времена). С другой стороны, та же ISA PowerPC настолько сложна, что некоторые процессоры этой архитектуры вынуждены разбивать некоторые инструкции на микроинструкции при декодировании -- что это, если не современная имплементация микрокода?
Ещё можно упомянуть транспьютер с языком программирования Occam.
Не помню как назывался процессор, где было два блока регистров общего назначения. Когда поток ожидал загрузки данных из памяти, то ядро переключалось на другой поток с другим набором регистров. GPU эксплуатируют эту идею.
Про VLIW - qualcomm hexagon DSP, наверняка, самый массовый
Отличная статья! Но мне кажется, в рассуждения закралась одна неточность: предполагается, что в программах часто вызываются функции, и поэтому количество регистров нельзя увеличивать. А на деле не так, потому что функции вызываются редко, т.к. в большинстве случаев инлайнятся. В современных реалиях даже рамки obj-файла не являются помехой из-за link-time кодогенерации (ну а в случае сред вроде JVM проблемы вообще нет by design). Большие объёмы памяти, большие кэши, большие ресурсы для компилятора позволяют инлайнить очень агрессивно, и это как правило идёт на пользу, причём не столько из-за того, что реже делаются вызовы, а из-за того, что инлайнинг как правило даёт возможности для межпроцедурных оптимизаций, которые таким образом делаются гораздо проще и эффективнее.
Плюс, в закладки однозначно. Спасибо за вашу работу, это было эпохально.
Заранее предупреждаю, я не настоящий сварщик, но вот какая идея пришла в голову.
Делаем процессор с большим количеством регистров. Каждый регистр имеет дополнительный флаг занят/свободен. Инструкция вызова функции содержит дополнительный аргумент — число используемых функцией регистров. Сами регистры не именуются, доступ к ним по номерам. Т.е. вместо команд вида
mov ax, bx
будут
movreg 1, 2
При вызове функции процессор видит сколько ей требуется регистров, также ему известно сколько регистров свободно (по флагам). Если свободных регистров достаточно, они распределяются для функции, помечаются как занятые и происходит вызов функции. "Распределяются для функции" означает, что номера регистров в инструкциях типа movreg 1, 2 виртуальные, не означающие конкретно первый и второй регистры, привязка номеров к физическим регистрам происходит при вызове функции и действительна только внутри неё. Если свободных регистров недостаточно, недостающая часть освобождается из занятых (необходимое количество занятых регистров сохраняется в память), дальше как в первом случае. При возврате из функции использованные ею регистры помечаются как свободные, если при вызове происходило сохранение занятых регистров, они восстанавливаются из памяти (естественно помечаются как занятые).
При вызове функции внутри функции всё происходит аналогично. Сохранение и восстановление регистров происходит без каких-либо дополнительных команд в исполняемом коде, полностью инициируется процессором. Компилятор в этом участия не принимает. Распределение регистров компилятору нужно осуществлять только в пределах каждой отдельной функции, причём как если бы ему были доступны все регистры. Количество физических регистров можно произвольно наращивать, при этом перекомпияция программ под новый процессор не потребуется.
Подозреваю, что я упустил что-то важное, что не даст реализовать данную схему в железе, либо приведёт к её неэффективности. (Ведь иначе она давно была бы реализована)
Выглядит так, будто весь стек засунут в регистры.
Регистр 0 - адрес возврата,
Регистры -1, -2, -3,... - аргументы/возвращаемые значения
Регистры 1,2,3,... - локальные переменные.
Скорее всего, при переключении потоков это вылезет боком.
Придется сохранять весь стек старого потока в память и загружать весь стек нового потока из памяти. Вместо небольшого набора доступных компилятору регистров сейчас.
**** Подозреваю, что я упустил что-то важное, что не даст реализовать данную схему в железе, либо приведёт к её неэффективности. (Ведь иначе она давно была бы реализована) ****
Да, и я, как сварщик, вам могу сказать что именно упустили: у этой схемы будет плохой тайминг, много мультиплексоров, много слоев комбинационной логики, и как результат - низкая тактовая частота.
Если хотите в этом разобраться - купите книжку https://dmkpress.com/catalog/electronics/circuit_design/978-5-97060-961-3/ - там есть про задержки и доступ к массивам регистров в главах 2-5.
Есть еще проблема.
Пусть у нас самый первый вызов и все регистры свободны.
При работе функции регистры не обязаны быть заняты подряд, минимально сложный код неизбежно породит мешанину из занятых и свободных регистров.
Вот что-то вызвали и еще и еще, пришла пора вытолкать кого-то в стек. Хорошо бы вытолкать не абы кого, а регистры функции с самой вершины стека.
Для этого функция обязана хранить не только потребное число регистров, но и их фактические индексы в пуле регистров.
Т.е. фактически появляется потребность еще в одном стеке - для индексов регистров.
Ну или стеке контекстов функций. Вытолкали регистры в обычный стек, в стек контексов положили контекст функции, которая их использовала.
Можно ли всё сериализовать в одном стеке? Можно, но в догонку появятся проблемы с выравниванием.
И чем всё это лучше регистровых окон в духе AMD29K или Итаниума?
Или регистровой машины с volatile|non-volatile регистрами?
Да, кстати, а как вы собираетесь узнавать какие регистры свободны?
Вот, например, прилетела инструкция ADD R1,R2,R3; R1=R2+R3
R1, понятно, занят, а как насчет других? Компилятор, конечно, знает, нужны ли ему значения в R2 & R3 далее, но процесор то нет.
Можно, пожалуй, добавить пару флагов в инструкцию, но в результате код распухнет.
Полагаю, относительно VLIW надо бы сделать несколько поправок:
Во-первых, более-менее нормальные алгоритмы планирования инструкций и регистров вроде как есть. Например, я зашёл на страницу публикаций МЦСТ и нашёл статью 2010 года: http://mcst.ru/doc/ivanov_101228.pdf Выглядит достаточно адекватно.
Для VLIW в случае Эльбруса есть возможность скомпилировать универсальный код, который запустится на всех версиях от v2 (или v3, не помню уже, всё равно это уже старое железо) до современной v6. Правда, придётся пожертвовать частью производительности.
1) спасибо
2) это и называется отсутствие масштабирования
7za b в сборках под elbrus-v3/v4, на v4; разница была устойчивой, но порядка процента (ЕМНИП на v4/v5 схожая картина для конкретно этого кода, который никак не заточен под архитектуру и слабо параллелится в потоке).Если интересно пощупать своими руками, см. тж. доступ по SSH (e2kv2..v5) — и могу предоставить шелл/виртуалку на v6, с которой и пишу эти строки (домашняя машинка).
Спасибо за статью!
*** Итого. С технологической точки зрения, сколь-нибудь существенным элементом новизны в RISC процессорах было лишь увеличение числа регистров общего назначения. ***
Я не согласен. В CISC из-за двухоперандных инструкций и других черт CISC (скажем аутоинкремент в PDP-11 и 68K) возникает больше конфликтов конвейера (hazard), следовательно нужно больше байпасов, больше логики для обнаружения конфликтов, переименование регистров итд итп.
Это сильносвязанные вещи, IMHO.
Да, в CISC меньше регистров и больше работы по обнаружению и избежанию конфликтов.
Да, в CISC меньше регистров и их приходится экономить в ассемблере в том числе.
Дело не только в количестве, но и в их использовании. Допустим у вас последовательность из диких PDP-11 или VAX-11 или 68K инструкций с аутоинкрементом и аутодекрементом, причем следующая инструкция использует тот же регистр, который аутоинкрементируется в предыдущей, типа:
add@-(R2)@ (R1)+
sub @(R1)+, (R2)+
а потом непрямой переход по регистру.
Здесь же целый букет read-after-write, write-after-write конфликтов в конвейере, на куче стадий, в который будет вовлечены обращенения к памяти, делаться байпасы из нескольких стадий в более ранние, и stalls, даже если вы сразу перекодируете это в load-store и регистровые операции.
При суперскаляре это превращается в нечто совсем ядреное, требующее огромных инженерных ресурсов на дизайн и верификацию.
А если возникнет исключение или прерывание? Вы же не можете выполнить только кусок инструкции - отменять прийдется всю.
Ваш (довольно экстремальный) пример на С соответствует
*R1++ += *(--R2);
*R2++ -= *(R1++);
писать в таком стиле - верный способ призвать дьявола.
Но разве, если скомпилировать это на RISC архитектуре,
не вылезут эти задержки и конфликты так или иначе?
Что такого умеет (в данном контексте) компилятор RISC,
чего не может сделать декодер CISC?
Увы, декодером и началом конвейера проблемы не ограничатся. Они будут преследовать вас весь конвейер до конца. В частности;
Вам нужно будет привязать к каждой приготовленной микроинструкции некую метку, к какой исходной инструкции она относится, и если в процессе выполнения произойдет исключение (деление на нуль, обращение к защищённой странице памяти или прерывание), пометить как саму микроинструкцию, так и все другие из той же исходной команды до нее и после нее, дотащить их до конца конвейера и там отменить , перед записью результатов в память.
Перед передачей управления на обработчик исключения вам нужно сохранить адрес именно исходной инсрукции, так как у порожденной микроинструкции своего адреса нет
Не дотаскивать до конца конвейера вы не можете, потому что другое, более раннее исключение может произойти в предшествующей CISC инструкции (группе микроинструкций), что отменяет более позднее исключение.
Кроме этого, инструкция с исключением может находится в ветке спекулятивного выполнения.
Помимо проблем с исключениями, из-за меньшего количества регистровнужно вносить аналоги алгоритма Томасуло, иначе прийдется все время останавливать конвейер для решения WAW и RAW конфликтов. А reservation stations аппаратно дорогие - много триггеров и гейтов, много переключений, энергопотребления.
Дополнительные конфликты возникают из -за флагов операций, которые ставят CISC, вводят зависимости.
Использование арифметических операций с операндом из памяти - либо транслируется в две микроинструкции, либо требует отдельного ALU для вычисления суммы адрес+смещение. А если учитывать, что у некоторых cisc-ов ещё и происходит масштабирование , сдвиг индекса и использование суммы двух регистров для адреса - это все дополнительные конфликты в конвейере, дополнительные ALU или более сложноетдекодирование
На RISC архитектуре этот код будет использовать больше регистров, чтобы возникало меньше конфликтов в конвейере. Инкремент будет стоять в конце всей группы, чтобы не было конфликтов при использовании регистра в середине. Это может сделать компилятор.
На CISC же для такой оптимизации нужно переименовывать регистры / алгоритм Томасуло и хранить соответствие внутренних регистров архитектурным до конца конвейера. А это дорогая операция.
Т.е. в конечном счете всё упирается в количество регистров (шутка).
Огромное спасибо за развёрнутый ответ, с вашего разрешения я со сноской включу его в текст статьи.
Хотелось бы конечно для объективности услышать мнение кого-нибудь из разработчиков CISC, насколько указанные проблемы критичны с их точки зрения для итоговой производительности процессоров. Впрочем, факты говорят, что к началу 90-х для равной производительности CISC требовалось вдвое большее к-во транзисторов.
Да, можете вносить.
Не только количество регистров, а и двухоперандность (переиспользование регистра как как чтения так и для записи результата), флаги результатов после всех операций (порождает болше конфликтов), одновременный доступ к памяти с арифметикой в одной инструкции, а также увеличение сложности при обработке исключений и спекулятивном выполнении (в том случае если мы превращаем cisc инструкцию в микроинструкции, так как исключения относятся к целой инструкции).
Очень интересная статья, стренды давно интересовали.
Спасибо! Благодарен.
Три архитектуры эльфам, семь гномам, девять людям… где же искать ту, что объединит их все?