Рано или поздно и Вы зададитесь вопросом, каким будет будущее процессоров. Достижения современных фабрик типа TSMC говорят, что достигнут максимум наших технологических возможностей. В результате каждый последующий технологический этап дается все большим трудом и многократно возрастающими затратами. Для транзисторов счет пошел на единицы атомов и потому, исчерпав возможность уменьшения их размеров, мы перешли к созданию многослойных "пирогов". Но и здесь не без проблем - например, отведение тепла или то же число слоев. Тем не менее, не все так плохо, т.к. есть варианты на уровне архитектур процессоров, которые не менее а, порой, даже более эффективны, чем новые технологические нормы. Об этом далее и поговорим...
Введение
Принстонская и Гарвардская архитектуры сформированы были на заре создания процессоров, но по сей день определяют основы вычислительных систем (подробнее см. [1]). Первая объединяет в единственном канале поток данных и команды программы, а вторая разделяет потоки команд, данных и стека. В результате для Принстонской архитектуры характерно наличие «бутылочного горлышка» и, соответственно, ограничение в производительности. Гарвардская же архитектура имеет множество параллельно работающих каналов, а это положительно влияет на скорость вычислительных процессов (подробнее см. [2]).
На уровне вычислительной модели, которую достаточно хорошо отражает структура языков программирования, различия упомянутых архитектур достаточно условно. Недостаток гарвардской архитектуры, связанный с неэффективным использованием памяти, на текущий момент фактически нивелирован аппаратными возможностями. Таким образом, увеличение числа каналов передачи данных не является уже проблемой и служит одним из важных ресурсов увеличения производительности вычислительных систем.
Но годы бегут, а, как и ранее, в современных программах можно выделить данные, команд, стек, ну и … все? Все остальное, что зачастую скрыто от глаз обычного программиста - многоуровневый кэш, длинные и короткие команды, предсказание команд и множество других «плюшек», в какой-то мере повышают производительность, но не настолько, чтобы это давало качественный скачек. Более того, эти механизмы могут даже негативно влиять на скорость вычислений. Серьезного прогресса теперь, похоже, можно достичь лишь путем изменения архитектуры вычислительной системы.
Ниже мы рассмотрим формальную модель, которая качественно изменяет архитектуру процессора и имеет все шансы увеличить вычислительную мощь системы. Речь пойдет об автоматном программировании (АП), модель которого рассмотрена достаточно подробно в [3]. Архитектуру на ее основе, которую по примеру упомянутых выше архитектур можно назвать по месту ее продвижения Балакиревской, мы далее и рассмотрим.
Функциональное разбиение
Разбиение программы на блоки позволяет организовать их эффективное чтение в промежуточную быструю память, с которой уже и работает центральный процессор. На роль таких блоков весьма хорошо подходят функции. Но, во-первых, они имеют большой разброс по размерам, а, во-вторых, существует большая вероятность, что в определенный момент будет работать только незначительная часть кода функции, что провоцирует большие накладные расходы на перемещение ее кода.
Технология автоматного программирования (АП) предлагает подход, естественным образом разбивающий программу на множество [небольших] функций, код которых при этом востребован в полном объеме. Такими функциями являются предикаты и действия автоматной программы. Можно ввести даже раздельную память для предикатов и действий. Так появляются уникальные возможности для тонкой оптимизации аппаратных средств, работающих с данными функциями.
Итак, имея общую медленную память, автоматные функции можно перемещать в быструю память и далее исполнять. В целях оптимизации из общего числа подобных функций можно выделять те, которые актуальны на текущем [дискретном] шаге исполнения программы. При этом предикаты будут актуальны всегда, а действия – лишь те, которые выбраны на текущем переходе автомата. Но даже, если ни одно из них не будет востребовано, это не сильно скажется на эффективности работы системы, т.к., например, при раздельных каналах памяти, загружаться действия будут параллельно предикатам.
Канал управления
Автоматная модель программ позволяет отделить логику управления программы от ее операторов и данных. И именно через это управление организуется эффективная блочная загрузка нужных функций. Выделение управления вводит в архитектуру еще один вид памяти и соответственно еще один канал передачи данных для таблиц переходов (ТП). Появляется возможность дальнейших оптимизаций, связанных с обработкой самих таблиц переходов автоматов и управления вычислительным процессом.
Для хранения ТП можно использовать более эффективную, чем обычная память, ассоциативную память [5]. Она, правда, дорогой ресурс, но поскольку она нужна в небольших объемах, то здесь ее применение вполне оправдано. Важно, что она используется здесь по своему прямому назначению: для поиска строки перехода по имени состояния программы и установки нового текущего состояния программы.
О параллелизме предикатов, действий и теневой памяти
Архитектура программ АП, кроме создания дополнительных каналов, формирует параллельные потоки исполнения кода внутри процессора. Это относится к [загруженным в быструю память] уже упомянутым предикатам и действиям. При этом предикаты автоматной программы параллельны по определению. Их можно запускать одновременно все или только те, которые необходимы в текущем состоянии автомата.
С действиями ситуация несколько сложнее. Имеет смысл загружать только те, которые актуальны для переходов из текущего состояния. Из них реально будут работать только действия активного перехода и, кстати, тоже параллельно. А чтобы корректно реализовать их параллелизм, действия должны использовать так называемую теневую память. Это еще один вид памяти, который поможет повысить эффективность работы вычислительной системы.
Заключение
Переход на автоматную архитектуру не отрицает имеющихся архитектур. Фактически идет речь о расширении последних. Совместное существование архитектур заключается в том, что на уровне функций работает обычная архитектура, а на уровне управления – автоматная. Но и при программной интерпретации автоматной модели, как в нынешней ситуации, АП зачастую более эффективно, чем существующие средства программирования, несмотря даже на поддержку последних аппаратными средствами. Речь идет о параллельном программировании - многопоточном и многоядерном.
Хотелось бы упомянуть предтечи автоматной архитектуры. Это, например, машины клеточных автоматов [6]. Схожие принципы положены в основу графических процессоров, да и собственно нейронные сети - это множество функционирующих параллельно нейронов, которые изначально замышлялись, как достаточно простые автоматные модели (см. определение нейронных сетей в [7]).
Подведем итог. Гарвардская архитектура "на пальцах" примерно в три раза эффективнее Принстонской. Автоматная по числу каналов должна быть в пять раз эффективнее Принстонской и почти в два раза - Гарвардской. Но все это без учета возможностей распараллеливания, которое вносят еще больший вклад в увеличение скорости процессора. Сюда же можно отнести работу с управлением и теневой памятью. Но еще есть новые механизмы синхронизация [автоматных] параллельных процессов на базе непосредственного доступа к их состояниям. Это заменяет нынешние тяжеловесные и неэффективные приемы синхронизации (семафоры, мютексы и т.п.). А, ведь, последние вносят, пожалуй, основной вклад в снижение скорости работы параллельных программ. Если бы не было нужды в синхронизации, то скорость вычислений увеличивалась бы пропорционально числу процессорных ядер. Однако практика подтверждает, что современное распараллеливание чаще негативно, чем позитивно, сказывается на скорости работы программ.
Ну, и как вы теперь смотрите на будущее процессоров? Если технологические возможности почти исчерпаны, то, может, пора изменить архитектурные принципы организации вычислений? Или, что точнее, перейти на более совершенные вычислительные модели. Модель автоматных программ этому пример. При этом она, в отличие, например, от того же функционального программирования, реализует "мягкий режим" перехода на новое мышление, не отказываясь от уже проверенной временем модели программирования.
Приложение. Пример автоматного алгоритма
На рис. 1 приведен алгоритм управления гильотиной, заимствованный из реального проекта системы управления линией прокатки металла. Функционально она мало чем отличается от своего аналога времен Великой французской революции. Технологический прогресс добавил ей датчики положения да сигналы управления электроприводом. И если раньше ею управлял человек (оставим в стороне его профессию), то сейчас его функции исполняет система управления. Ей в данном примере соответствуют два взаимодействующих и параллельно работающих автомата - контроль состояния датчиков гильотины и собственно управление гильотиной. Отметим, что в реальной системе к этим автоматам добавляется, порой, еще пара десятков таких же [параллельных] автоматов.
Приведенные автоматы демонстрируют описанные выше моменты распараллеливания программного кода в рамках автоматной архитектуры. Для сравнения автоматной модели с текущей моделью фон Неймана на рис. 3, 4 показаны эквивалентные автоматам модели в форме блок-схем. Они демонстрируют, как простой заменой модели управления можно перейти к качественно иной модели программирования. На фоне блок-схем преимущества автоматной модели достаточно очевидны. Не рассмотреть, что состояния автомата являются своеобразными точками распараллеливания алгоритмов и синхронизации параллельных процессов и оценить подобную возможность, не способны только программисты, мозг которых поражен многопоточным и "корутинным" мышлением.
Надо также отметить, что хотя известна формальная процедура, позволяющая для любой блок-схемы найти эквивалентный ей автомат, и, следовательно, [автоматически] выявить параллельно исполняемые блоки кода программы, тем не менее, важно и целесообразно изначально "мыслить" именно автоматными моделями. Именно это реализует ВКПа - технологии объектного визуального автоматного проектирования программ на языке С++.
Но даже если возможности аппаратных и программных средств достаточно ограничены, что присуще, например, программированию на базе ПЛК в рамках стандарта МЭК- 61131-3 (подробнее см. ГОСТ Р МЭК 61131-3-2016), существуют весьма простые приемы, которые, пусть и в ограниченном объеме, но позволяют насладиться возможностями АП даже в подобных случаях. Все это помогает реально "прощупать" возможности автоматной архитектуры, оставаясь в рамах существующих языков программирования и аппаратных архитектур. Но демонстрацией и обсуждением этого мы, надеюсь, займемся в другой раз.
Литература
1. Архитектура вычислительных машин. [Электронный ресурс], Режим доступа: https://prog-cpp.ru/comp-architecture/, свободный. Яз. рус. (дата обращения 18.07.2022).
2. Бэкус Дж. Можно ли освободить программирование от стиля фон Неймана? Функциональный стиль и соответствующая алгебра программ. [Электронный ресурс], Режим доступа: http://rkka21.ru/docs/turing-award/jb1977r.pdf, свободный. Яз. рус. (дата обращения 18.07.2022).
3. Автоматная модель управления программ. [Электронный ресурс], Режим доступа: https://habr.com/ru/post/484588/, свободный. Яз. рус. (дата обращения 18.07.2022).
4. Рылов С. Языки программирования стандарта МЭК 61131-3. [Электронный ресурс], Режим доступа: https://finestart.school/media/programming_languages, свободный. Яз. рус. (дата обращения 18.07.2022).
5. Фостер К. Ассоциативные параллельные процессоры: Пер. с англ. – М.: Энергоиздат, 1981. – 240 с.
6. Тоффоли Т., Марголус Н. Машины клеточных автоматов: Пер. с англ. – М.: Мир, 1991. – 280 с.
7. Минский М. Вычисления и автоматы. М.: Мир, 1971. – 364 с.
Комментарии (18)
SlFed
22.07.2022 21:50+7Что есть в данном контексте "автоматная функция" и чем она отличается от "автоматной программы" ? И как это все взаимодействует с предикатами? Из статьи не понятно.
flx0
22.07.2022 22:39+13Про принстонскую и гарвардскую архитектуру явно написана выдержка откуда-то человеком, который что-то где-то прочитал, но не имеет ни малейшего представления о том как оно работает на практике. Наиболее распространенные процесоры сегодня - x64, ARM, etc. выставляют интерфейс по фон Нейману "наружу", на уровень ассемблера - так удобнее работать операционной системе, у которой программы могут быть получены из разных источников. Но при этом на низком уровне разделяют кеши инструкций и данных, то есть на микроуровне имеют гарвардскую архитектуру. Поэтому перечисленные в статье "недостатки" не имеют вообще ничего общего с реальностью, а приписываются какому-то искуственно ограниченному сферическому коню в вакууме.
Ваша "автоматная архитектура" - это крайне малое подмножество того что умеет любой процессор в одну-две инструкции. Это просто передача управления по значению из таблицы переходов. Так работают switch-case конструкции и вектора прерываний. Но городить из этого полноценный автомат мало кому нужно просто потому что он крайне редко является удобной формализацией. И уж тем более, нет никакого смысла делать процессоры, которые умеют только в очень ограниченное подмножество инструкций.
Про остальную часть статьи по существу мне вообще сказать нечего, какой-то лютый бред.
DarkTiger
23.07.2022 00:07+2Мне эта статья напомнила, причем очень сильно, курсовой сына в Бауманке про создание МП из конечных автоматов. На базе 556РТ5. В 2017. Про САПР типа Vivado и разговора не было, даже Maxplus не использовался, все ручками и головой, в Ворде и Visio.
Racheengel
23.07.2022 00:56Вот, мы что то подобное на первом курсе делали, курсовой был по эмуляторам архитектур процессоров. Интересно было потом под свой же эмулятор код на ассемблере писать, а потом дебагать...
Thero
23.07.2022 01:32это ж какой-то суперриск получается в итоге? вернее даже просто современный гибридный СISC
le2
23.07.2022 04:33-2У некоторых Cortex-M есть тесносвязанная память — работающая также быстро как регистры, без кэширования, то есть на частоте ядра. А еще часть памяти может быть даже с однобитовым атомарным доступом, что также может устранить часть проблем семафоров.
Автор — вперед, докажи, что «в два раза быстрее».
Хотя и не нужно ничего доказывать. Всем понятно что одну узкую задачу можно решить на ассемблере и в сотню раз быстрее чем это позволит условный линукс. Но что с того?
В моей картине мире так: как сделать процессор — сказано в «машине Тьюринга». Всё остальное несущественно и мелочи. Далее звезды науки собрались и несколько лет пилили спецификацию Multics. В начале 70х годов на основе этого получился Unix и с тех пор за 50 лет ничего интересного не произошло кроме неграфических вычислений на GPU.
Можно что-то сделать «лучше»? И что значит лучше? Быстрее, но ни с чем не совместимо это лучше?
«Лучше» это то что должно сломать спецификацию Posix как жутко устаревшее.
amarao
23.07.2022 10:22+1Я не совсем понял. У нас есть лимит на число проводочков из процессора к памяти. Их объединяют в каналы доступа к памяти. Да, это узкое место.
А теперь, вопрос: что эффективнее - 5-канальный фон-нейман или "конечные автоматы" с 5 независимыми каналами? Очевидно, что 5-канальная память общего назначения будет быстрее, потому что если у нас tight loop, фигачащий по данным, то все 5 каналов достанутся данным. А если у нас рыхлый мономорфизированный код, то один канал будет непрерывно новые инструкции всасывать.
А в вашем варианте с жёсткими каналами большая часть мощностей будет простаивать. Очевидно, что для производительности общая очередь эффективнее набора индивидуальных очередей (хотя для latency важно обратное).
lws0954 Автор
23.07.2022 17:15-2Дж. Бэкус утверждает (см. ссылку в статье): "Основой всякого языка программирования является модель вычислительной системы, которой управляют программы на этом языке". С этим можно согласиться, но в моей "картине мира" это выглядит несколько иначе (она отражена в статье на Хабре (https://habr.com/ru/post/481998/ и других моих статьях): основой языка является алгоритмическая модель (АМ). При этом, для эффективной реализации программ, между моделью вычислительной системы (ВС), как равно ее архитектурой, и АМ должно быть соответствие, которое бы этому способствовало. Современным языкам соответствует модель Поста (МП). На ее реализацию и заточены модели/архитектуры современных процессоров. Модель Тьюринга (МТ) - это иное и она не реализуется современными языками/процессорами. Это первое.
Мою картину и картину мира Бэкуса объединяет только одно слово - "управляют" (см. цитату выше). У меня речь идет о модели управления, характерной для той или иной алгоритмической модели и языку программирования. У МП и МТ они разные. У Тьюринга она автоматная. Это второе и, может быть, наиболее важное.
И третье. Если оптимизировать архитектуру под автоматную модель (равно машину Тьюринга), то скорость ее реализации [резко] повысится (пока речь об этом - скорости). Но будет ли эта скорость выше, чем в случае МП? Будет. Просто потому, что МТ имеет гораздо больше возможностей для распараллеливания кода и создания дополнительных каналов. Где, в чем, за счет чего и как это реализовать и т.п. и повествует статья. При этом, замечу, сравнения самих языков программирования МП и МТ мы пока оставляем в стороне (этому посвящены мои предыдущие статьи). Главное, что "по науке" они абсолютно равнозначны и равносильны. Это к слову об общности, универсальности и ограниченности.
"Мелочи" же типа, что собой представляют "автоматные функции" и т.п., что понимается под "моделью управления" и т.д., что такое параллелизм достаточно подробно, как мне кажется, объяснены в моих же статьях, которые размещены здесь же на Хабре.
Вот такой мой обобщенный ответ на сделанные выше замечания.
cepera_ang
23.07.2022 21:54+2Ну и накидайте прототип на FPGA, как сейчас может любой студент сделать с традиционным CPU-ядром и покажите, что ваша архитектура такая замечательная. Потом финансирование, масштабирование и в дамки. Что бумагу изводить просто так?
flx0
24.07.2022 11:58+4Прокомментирую раздельно по технической части и по психиатрической.
По технической:
Современным языкам соответствует модель Поста
Современные языки используют разные модели. От (в первом приближении) машины с произвольным доступом к памяти в С до исчисления конструкций во всяких там Идрисах. При этом они все вычислительно эквиваленты как машине Тьюринга, так и машине Поста, но значительно выигрывают у них в лаконичности. Ведь модель Поста - это всего лишь про то как очень примитивный язык из нескольких инструкций умеет менять содержимое ячеек ленты.
Модель Тьюринга (МТ) - это иное и она не реализуется современными языками/процессорами.
Машина Тьюринга - это в первую очередь про фундаментальную вычислимость. Машинный код для любого процессора является полным по Тьюрингу. Иными словами, "МТ" реализуется любыми "современными языками/процессорами".
То как вы в одну кучу валите языки программирования и процессоры - это вообще отдельная тема. Не делайте так.
Если оптимизировать архитектуру под автоматную модель (равно машину Тьюринга), то скорость ее реализации [резко] повысится
Почему? Докажите.
МТ имеет гораздо больше возможностей для распараллеливания кода и создания дополнительных каналов.
"МТ" - это автомат и лента. Никакого распараллеливания там и близко быть не может, за один такт происходит один переход в автомате, одна запись на ленту, и одно движение ленты. Можно, впрочем, придумать извращения в виде машин с несколькими лентами, или нескольких автоматов, ездящих по одной ленте, но это и для машины Поста работает точно так же. Если же вы используете какие-то определения, отличные от общепринятых, потрудитесь их явно выписать.
Ну и вам про FPGA выше правильно сказали. Лучше написать статью про "зацените какую штуку я на верилоге запилил, какие задачи она решает, и как под нее можно кодить", чем эти ваши стены бессвязного текста.
Теперь по психиатрической части.
Дж. Бэкус утверждает ...
Ссылка на выдернутое из контекста выказывание "авторитета", не имеющее никакой научной ценности.
С этим можно согласиться, но в моей "картине мира" это выглядит несколько иначе
Незамедлительная попытка приравнять себя к оному авторитету.
(АМ), (ВС), (МП), (МТ)
Введение кучи бесполезных аббревиатур без их четких определений, по-видимому для придания тексту ощущения научности и значимости.
Современным языкам соответствует модель Поста (МП).
Ложные, не имеющие связи с действительностью, высказывания преподносятся как факты.
"Мелочи" же типа, что собой представляют "автоматные функции" и т.п., что понимается под "моделью управления" и т.д., что такое параллелизм достаточно подробно, как мне кажется, объяснены в моих же статьях, которые размещены здесь же на Хабре.
Отстутсвие определений используемых терминов, отсылки к таким же бессмысленным статьям без определений в ответ на просьбу пояснить что же все-таки имеется в виду.
Я не психиатр, и не буду вам ставить диагнозы по айпи, но рекомендую обратиться за профессиональной помощью. Проблемы психического здоровья в современном мире стоят очень остро. Если специалист вам скажет что все в пределах нормы, отлично.
lws0954 Автор
25.07.2022 13:33Сложно отвечать на подобны агрессивные посты, но попробую...
Действительно, возможно, только ненормальная психика может разглядеть то, что не способен в принципе разглядеть чел с нормальной психикой. Я могу даже согласится, что только психика, "поврежденная" многолетним автоматным мышлением, способна увидеть параллелизм там, где его не видит человек "нормальный". Меня это поражает, но исправить что-то я не берусь. Остается надеяться, что есть или найдутся когда-либо и другие "ненормальные", которые это смогут разглядеть тоже. Конкретно мои представления по МТ представлены в моей же статье на Хабре "МАШИНА ТЬЮРИНГА, КАК МОДЕЛЬ АВТОМАТНЫХ ПРОГРАММ". В ней же есть ссылки [12, 13], в которых говорится и о параллелизме абстрактных машин (как его смог рассмотреть "нормальный псих"). Так что могу порекомендовать только одно - будьте внимательны, обращайте внимание на ссылки и вопреки "нормальной лени"... читайте, читайте и читайте, т.к. втиснуть все пояснения в небольшую статью и, тем более, в рамки краткого ответа вряд ли возможно.
flx0
25.07.2022 17:17Так вы в итоге и не ответили. Вы снова даете ссылки на тексты без определений и импликации что вы тут один умный, а остальным до вашего уровня читать, читать, и читать.
Вот смотрите, я вам могу дать определение автомата:
Конечный автомат с входным алфавитом I и выходным алфавитом O - это конечное множество состояний S, и множество функций перехода T = {f: S×I →S×O}.
Здесь нет ссылок на километровые простыни текста, нет аппеляций к вашей безграмотности и рекомендаций читать книжки чтобы когда-нибудь это понять. Есть только строгое определение, состоящее из одного предложения. Теперь, когда я говорю об автоматах, вы абсолютно точно знаете что я имею ввиду.
Ваша очередь. Что такое автоматная программа?
andreishe
23.07.2022 21:12О, секта свидетелей Шалыто.
lws0954 Автор
25.07.2022 14:07О моем отношении к секте Шалыто см. ту же статью "МАШИНА ТЬЮРИНГА, КАК МОДЕЛЬ АВТОМАТНЫХ ПРОГРАММ"
lws0954 Автор
25.07.2022 16:47Посмотрите статью - Какой должна быть будущая технология параллельного программирования
И с 2007 г. мало что изменилось (добавилась поддержка корутин в С++). Но я использовал и использую технологию автоматного программирования. Создаю системы реального времени под Windows и Linux. Дискретный такт (тик) < 0.5 мсек. На потоках, насколько я в курсе, такое не достижимо (для взаимодействующих процессов, конечно). И это при том, что автоматы интерпретируются (С++). Если вместо интерпретации сделать аппаратную поддержку, то ускорение будет один-два порядка (это типовая оценка при переходе на аппаратную поддержку). Таким образом, автоматная архитектура по любому будет эффективнее многопоточгой/многоядерной. Это к слову об оценке и доказательствах простого быстродействия. А уж с точки зрения программирования преимущества - небо и земля (и конечно не в стиле Шалыто)..
vassabi
читаю начало
скипаю в конец
хмммммммм, ОК!
ColdPhoenix
----- удалено