Аппаратное обеспечение компьютеров

на один, финальный уровень абстракции и посягнем на рассмотрение самого общего предмета Computer Science.
Это
model of computation

Для начала выясним, что же мы такое изучаем? Что есть computation и почему пока мы не можем корректно поименовать этот термин по-русски?
Все дело в чертовой путанице с терминами, она везде, даже в русской Wikipedia.
Вот как обстоит дело:

время вы изучали одну модель вычислений, одну парадигму программирования, один основной принцип построения ЭВМ – императивный.
Хорошо это или плохо, что это значит и возможны ли иные пути вы узнаете сейчас, но перед этим нам требуется определить фундаментальные понятия, лежащие в самой основе Computer Science с которыми вы либо не знакомы совсем,
либо знакомы слишком мало.

такое АЛГОРИТМ?

как подобает, начнем издалека и определим, что такое ЯЗЫК.
Язык, это то, что состоит из двух частей: синтаксиса и семантики.
Грубо говоря это то, как мы записываем язык и то, что мы подразумеваем под этой записью.
Синтаксис строго формален и однозначен, семантика – то, как мы интерпретируем синтаксическую структуру в голове.
Например:

(правила записи) и семантику (то, что означают слова и предложения для каждого человека )

Формальный.
Не предназначен для человеческого общения, имеет только синтаксис (правила записи).
Например, математика – формальный язык, как и все языки программирования.

Формальный язык всегда состоит из 4-х элементов:
Σ – конечное множество произвольных символов, называемое терминальный алфавит.
N - конечное множество произвольных символов, называемое нетерминальный алфавит.
S – аксиома, также называемое начальное правило вывода
P – конечный набор правил, называемых продукциями, вида «α→β», где α и β принадлежат Σ и N.
Задав эти 4 элемента можно полностью описать любой формальный язык.

например:
(2+3)-10=5-10=-5
и неправильные, например:
+3=5=-10+(

Пример формального языка:

Обратите внимание: второе выражение неправильно чисто синтаксически! Семантических, т.е. смысловых ошибок в формальных языках нет в принципе!

Как нам сочинить формальный язык, на котором можно выразить только правильные формулы (т.е. если сначала идет скобка «(» то потом обязательно «)», а не наоборот и т.д.)?

Σ=(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, (, ), +, -, *, /, =)
N=(формула, знак, число, цифра)
S= формула → формула знак формула
P= знак → +, -, *, / , =
цифра → 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
число →цифра число
формула → (формула)
формула →число

Записанная таким образом четверка {Σ, N, S, P} полностью определяет формальный язык правильных арифметических формул.

Простым языком, это какая-то последовательность действий, но здесь есть важная деталь.
Эта последовательность, в любом случае, как-то записана на каком-либо языке.
Любой алгоритм можно записать на произвольном формальном языке.
Алгоритм может быть правильным или нет, работать или не работать, машине это без разницы.
Машине важна только формальная интерпретация – прочитать строку, что-нибудь сделать, прочитать следующую строку.
Она не различает СМЫСЛ данного ей текста – это программа для вычисления простых чисел или текст «Войны и мира». Для нее и то, и то – просто последовательности символов.
С точки зрения машины АЛГОРИТМ – ЭТО ЛЮБОЙ ПРОИЗВОЛЬНЫЙ НАБОР СИМВОЛОВ НА ФОРМАЛЬНОМ ЯЗЫКЕ.
Очевидно, что машина полностью игнорирует человеческое значение этого слова. Для людей тексты делятся на: программы (алгоритмы в стандартном смысле) и просто тексты.
Для машины тексты делятся на работающие алгоритмы (т.е. программы без ошибок) и не работающие алгоритмы (т.е. программы с ошибками, случайные тексты, «Анну Каренину» и т.п. – что именно там не работает и почему ей без разницы).

смысле включает множество уточнений:
это программа, выражающая какую-то последовательность действий, она имеет разные блоки – начало, конец и т.п., она может иметь ошибки (а лучше не иметь) и она явно отличается от простого текста, допустим, художественного романа или случайной последовательности бит: 0101010101.
Но машине все эти лингвистические изыски безразличны.
Способ ее работы:
прочитать символ-> распознать символ-> выполнить аппаратную инструкцию-> прочитать еще один символ
не позволяет понимать, в человеческом смысле слова, смысл, который мы закладываем в текст. Значит ей без разницы, что разбирать и без разницы, почему она остановилась на первом же шаге – потому, что я забыл написать ключевое слово BEGIN или потому, что я скормил ей все тексты Сорокина в двоичном коде вместо программы.
Что бы понимать машину – надо мыслить как машина и для нас отныне алгоритм это
ПРОИЗОЛЬНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ СИМВОЛОВ НА ЛЮБОМ ФОРМАЛЬНОМ ЯЗЫКЕ

логики нас ожидает одна большая неприятность.

В чем проблема?

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

Как не включая семантику
(которая нам недоступна, помните об этом!)
сузить поле игры и таки выделять программы в человеческом смысле слова, даже если они ошибочные?

с которой мы начали лекцию –
модель вычислений - model of computation

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

Вычисление (1) как calculation это произвольный процесс, трансформирующий входные данные в выходные. Это очень широкий термин, который корректнее переводить как «исчисление». Например, в расписании западных студентов есть дисциплина Calculus, по традиции так сокращенно называют «исчисление бесконечно малых» (то есть математический анализ).
Вычисление (2) как computation – это calculation с использованием абстрактной вычислительной машины. Заметим, что не все, что может быть вычислено в смысле (1) может быть вычислено в смысле (2), поэтому для корректности используют два разных термина. В дальнейшем, везде где мы будем говорить «вычисление» - мы будем использовать термин в смысле (2)!

Automata
Lambda Calculus
Fractran
Tiling Systems
Circuits
Boltzmann Machines
Neural Networks
Hopfield Networks
Boolean Algebra
String Rewriting Systems
Semigroups
Cellular Automata
Diophantine Equations
Tag Systems
etc.

Существует огромное количество моделей вычислений:

текст)

Модель вычислений

Непрофильные тексты и невычислимые функции

Вычислимые функции
(программы в человеческом
смысле слова)

Формальная верификация

Безошибочные программы

Зацикливающиеся программы

Исследование сложности

Простые программы (P, NL)

Сложные программы (NP, BP)

отсеиваем

отсеиваем

отсеиваем

полностью эквивалентны: все, что можно описать с помощью одной, можно описать и с помощью другой, вопрос в том, насколько удобно и быстро.
Каждая модель вычислений порождает свой класс языков программирования и свой класс аппаратной реализации.
Модели можно классифицировать по разным критериям:
Аналоговые и дискретные
Последовательные, параллельные и конкурентные
Пакетные и интерактивные
Классические и квантовые
Рациональные и вещественные (гипервычислительные модели)
Обратимые и необратимые
и так далее.

Сейчас нас интересует математическая классификация по характеру обращения с двумя основными абстракциями – командами и данными.
Это:
императивные вычисления, машины и языки
и
декларативные вычисления, машины и языки

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

Чтобы осознать разницу между императивным и декларативным подходом,
разберемся, чем отличаются команды и данные,
ведь с точки зрения машины и то и то – просто последовательности из 0 и 1.

Вот так выглядит императивная модель вычислений с явной сменой состояний и делением на команды и данные. Это то, к чему вы все привыкли.

императивной модели, сам процесс вычислений, как смена состояний σ от начального до конечного:

И то, что скрывается за каждой стрелкой-командой, меняющей состояние: оператор присвоения набору переменных какого-то значения, рассчитанного на основе предыдущего набора:

Несложно видеть, что финальное значение σ‘ полностью определяется начальным значением σ . Следовательно, вместо цепочки операторов переходов, математически проще рассмотреть функцию:

В результате мы пишем программу, как последовательность операторов присвоения и у нас присутствует явная дихотомия – есть команды (операторы) и есть данные.

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

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

Основой императивной модели послужила машина Тьюринга – абстрактная вычислительная модель, разработанная Аланом Тьюрингом в 1930-е годы. Основой декларативной модели послужило лямбда-исчисление, сознанное Алонзо Чёрчем примерно в это же время.
Машина фон Неймана была императивной, как и первые компьютеры, такой подход к вычислениям воплотился во всех первых языках программирования – от Fortran и Algol до C и Pascal, в архитектуре фон Неймана и подавляющем большинстве компьютеров, вплоть до 70-х.
Идеи Чёрча не нашли практического воплощения в железе и программах до 60-х годов, когда был разработан язык LISP – один из первых чисто функциональных языков.
Все языки, с которыми вы работаете или будете работать – скорее всего императивные
это Pascal, Delphi, C, C++, C#, Java, Perl, Python и многие другие.
К декларативным языкам относятся LISP, Prolog, Scheme, ML, Haskell, Erlang и другие. Естественно, декларативная модель вычислений воплощается не только в языках, но и в железе.

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

Основные особенности функциональной модели вычислений:

в ФП каждый символ является неизменяемым, то функции не имеют побочных действий. Вы не можете менять значения переменных, к тому же функция не может поменять значение вне своей области видимости, и тем самым повлиять на другие функции. Всегда можно воспроизвести проблему, потому что ошибка в функции не зависит от постороннего кода, который выполнялся ранее. Если возвращаемое значение неправильное, то оно всегда будет неправильным, не зависимо от того, какие куски кода выполнялись прежде.
Многопоточность из коробки. Функциональная программа сразу готова к распараллеливанию без каких-либо изменений. Вам не придётся задумываться о deadlock-ах или race conditions потому что вам не нужны блокировки! Если вы пишете по сути однопоточное приложение, то компилятор всё равно может оптимизировать функциональную программу так, чтобы она использовала несколько CPU.
Горячее развертывание и обновление. Для установки обновлений Windows надо перезагружать компьютер. В Unix необходимо остановить обновляемый сервис. Телекоммуникационные системы должны быть включены 100% времени, ведь если из-за обновления человек не сможет вызвать скорую, то жизни могут быть потеряны. В идеале нужно обновить все нужные участки кода не останавливая систему в принципе. В императивном мире это невозможно, но инженеры, имеющие дело с Erlang, годами обновляют свои системы без остановки их работы.
Доказательные вычисления и оптимизация. ФП можно изучать с математической точки зрения. Компилятор, например, может конвертировать участок кода в эквивалентный, но более эффективный кусок, при этом математически обосновав их эквивалентность. Реляционные базы данных годами производят такие оптимизации. Дополнительно вы можете использовать математический аппарат, чтобы доказать корректность участков ваших программ. При желании можно написать инструменты, которые анализируют код и автоматически создают Unit-тесты.
Ленивые вычисления. В императивных языках программирования каждая функция может повлиять или зависеть от внешнего состояния, значит необходимо соблюдать чёткую очерёдность вызовов. Ленивый компилятор рассматривает код в точности как математик изучает алгебраические выражения — он может отменять некоторые вещи, отменять выполнение тех или иных участков кода, менять очерёдность вызовов для большей эффективности, даже располагать код таким образом, чтобы уменьшить количество ошибок, при этом гарантируя целостность программы.

Джон Алан Робинсон реализовал метод автоматического доказательства теорем, получивший название «принцип резолюции».
1964 Питер Ландин продемонстрировал связь языков программирования с лямбда-исчислением, придумал абстрактную машину для вычисления лямбда-выражений - SECD-машину. Появляется язык APL – предшественник Matlab.
1966 Появляется РЕФАЛ, единственный советский функциональный язык, придуманный математиком В. Ф. Турчиным.
1971 Ален Колмероэ положил резолюцию в основу языка PROLOG
1973 Роберт Милнер создает язык ML
1975 Появляется Scheme - один из самых популярных диалектов LISP
1985 Дэвид Тернер создает Miranda – предшественника знаменитого Haskell
1987 В лабораториях Ericsson создан язык Erlang
1990 Появляется один из самых успешных и сложных функциональных языков – Haskell
2005 Microsoft создает F# - функциональный язык для .NET
2007 Clojure - современный диалект LISP

Haskell

жизни какое-нибудь интересное железо, основанное на декларативных принципах?

Конечно, это Data Flow машины, также называемые потоковыми ЭВМ.

компьютеры делятся на Control Flow (управляемые потоком команд, т.е. традиционные императивные) и Data Flow (управляемые потоком данных, т.е. декларативные).
Функциональные языки, такие как LISP, Haskell, Prolog очень хороши для многих задач, но когда мы запускаем их на своем компьютере, то их замечательные функции все равно перемалываются в императивную систему команд.
Как нам создать компьютер, не имеющий системы команд принципиально и управляемый единственным потоком абстрактных данных?

Рассмотрим классический пример. Допустим, нам надо вычислить простое выражение:

Потоковая машина, прежде всего, должна представить это выражение в виде ориентированного графа потоков данных:

В нем есть 2 вида узлов – сами данные, изображенные квадратами (т.е. значение переменных) и обрабатывающие элементы (статичные монозадачные блоки, реализующие обычные операции сложения деления и т.п.).

Все действия над данными проводят обрабатывающие элементы (операторы, собираемые из обычных вентилей).
Каждый элемент начинает обработку, когда ему на вход поступают готовые и подходящие данные.
В нашем примере, на первом такте, автоматически и параллельно начинают работу 2 цепи сложения и одна умножения, затем, на втором такте, умножение и 2 деления, на третьем такте снова происходит умножение, на четвертом остается одно вычитание и расчет закончен.
Вообще говоря, такая штука немного похожа на внутренности логического вентиля – в определенном смысле каждый такой – маленькая монозадачная потоковая машина – он получает на входе произвольные данные и обрабатывает их фиксированными пересылками от транзистора к транзистору.
Естественно, данные необходимо снабдить какими-то меняющимися тегами, на которые будут реагировать обрабатывающие элементы, это необходимо для задания пути их прохождения через АЛУ.
Вообще, дерзость разработчиков сначала дошла до того, что бы упразднить АЛУ вообще за ненадобностью, точнее совместить блоки обработчиков и ОЗУ.
Граф потока данных и является программой для DF-машины, а программы в традиционном смысле здесь не существует. Конечно, описать это все на обычном языке не представляется возможным (точнее представляется, но уж очень громоздко и уродливо), так что параллельно с разработкой железа, продвигалась и работа над DF-языками (Data Flow Language).
Помимо концептуальной изысканности, DF-машины имеют колоссальное преимущество – естественный врожденный параллелизм – любые готовые данные тут же поступают на соответствующие обработчики. Ясно, что при наличии оптимального графа, решить задачу быстрее, чем на DF-компьютере невозможно в принципе.

из Стэндфордского университета.
1970 В MIT разрабатывается первый DF-язык Id (Irvine dataflow).
1974 Там же разрабатывают прототип MIT Static Dataflow Machine. На конференции в Стокгольме впервые явна озвучена идея «антимашины фон Неймана» , продвигаемой Хартенштайном и Глушковым.
1977 Burroughs строит Data Driven Machine
1979 В Тулузе (Франция) в исследовательском центре CERT-ONERA строят первый многопроцессорный DFC-компьютер LAU (Language a Assignation Unique) на 32 процессорах. Компания Texas Instruments разрабатывала свою версию dataflow – DDP (Data-Driven Processor). В MIT разработан язык VAL.
1980 Строится прототип MDM - Manchester Dataflow Machine
1983 Разработан язык SISAL
1986 В MIT строят машину, работающую с моделью «тегированных токенов» - дальнейшее развитие DF. В Electrotechnical Laboratory (Япония ) изготовлен прототип EM-4 Data Flow Machine на 1024 процессорах.
1987 В СССР Глушков строит прототип ЕС-2701 на 48 процессорах, показывающий линейное ускорение в зависимости от их числа.
1989 threaded dataflow процессор Epsilon
1995 Первый коммерческий DF-процессор Data-Driven Media Processor (DDMP) предложен компанией Sharp для обработки мультимедийных данных.
2000-е DF-процессоры применяются в DSP, роутерах, графических сопроцессорах, процессорах телеметрии.

EM-4 Data Flow Machine

Marvell Xelerated X11 и его применение

данные передаются и хранятся в виде т.н. токенов (token).
Токен это структура, содержащая собственно передаваемое значение и метку — указатель узла назначения.
Простейшая потоковая вычислительная система состоит из двух устройств: исполнительного (execution unit) и устройства сопоставления (matching unit).
Исполнительное устройство служит для выполнения инструкций и формирования токенов с результатами операций. Как правило, оно включает в себя память команд, доступную только для чтения. Готовность входных данных узла определяется по наличию набора токенов с одинаковыми метками. Для поиска таких наборов и служит устройство сопоставления. Обычно оно реализуется на базе ассоциативной памяти CAM.

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

(1974)

Машина и один ее
процессорный элемент

В динамической потоковой архитектуре (dynamic dataflow) каждый узел может иметь множество экземпляров. Для того, чтобы различать токены, адресованные в разные экземпляры одного узла, в структуру токена вводится дополнительное поле — контекст. Сопоставление токенов теперь ведется не только по меткам, но и по значениям контекста. По сравнению со статической архитектурой появляется целый ряд новых возможностей.
Рекурсия. Узел может направлять данные в свою копию, которая будет отличаться контекстом (но при этом иметь ту же метку).
Поддержка процедур. Процедурой в рамках данной модели вычислений будет последовательность узлов, связанных между собой и имеющая входы и выходы. Можно одновременно вызывать несколько экземпляров одной и той же процедуры, которые будут отличаться контекстом.
Распараллеливание циклов. Если между итерациями цикла нет зависимости по данным, можно обрабатывать сразу все итерации одновременно. Номер итерации, как вы уже наверное догадались, будет содержаться в поле контекста.

кажется?

Одна из самых мощных рабочих станций начала 1980-х
Sun 3/260 с традиционным процессором архитектуры SPARC
решает задачу за 85 секунд

Транспьютер INMOS T800, о котором мы уже говорили, самый мощный процессор в мире до времен Pentium справляется в 8 раз быстрее

Прототип DF-микропроцессора εpsilon , быстрее в 16 раз при частоте меньшей в 2 раза!

Достоинства:

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

задача – расчет чисел Фибоначчи, заданных линейным рекуррентным соотношением:

2. Как написать это на традиционном императивном языке:

видеть, что граф состоит из (MAX_I-2) одинаковых узлов, отличающихся только значениями контекста (цифры под изображением узла). Логика работы узла (в псевдокоде) будет выглядеть так:

3. Как написать это на языке Id – одном из первых языков для DF-машин? Сначала создается потоковый граф вычислений:

делает вот эта штука?

DF-языков: VAL, Id, SISAL, Lucid, Quil. Программирование на них выглядит, как составление графов потоков данных:

Факториал на языке Id

Сумма значений произвольной функции на языке VAL

давали огромные возможности для параллелизма выполнения. Обратной стороной этого преимущества было то, что на последовательных участках вычислительного графа они показывали резкое падение производительности.
Загрузка исполнительных устройств была далека от максимально возможной. Большая часть машинного времени тратилась на поиск соответствия операндов, выборку инструкций, а исполнительное устройство все это время простаивало, выполняя лишь по одной инструкции на каждую пару токенов.
Трудным было конструирование устройств сопоставления. Ассоциативная память сложнее, дороже, медленнее, занимает больше места и потребляет больше энергии, по сравнению с обычной оперативной памятью такого же объема.
Сам принцип управления потоком данных не позволял организовать эффективный конвейер. Почти все устройства работали асинхронно, требовались буферы и очереди в линиях связи.
По сравнению с классической многопроцессорной архитектурой, в dataflow-машинах значительно выше была нагрузка на коммутационную сеть. Ведь фактически, каждая операция требовала пересылки двух токенов.
Дико сложная модель программирования, по сравнению с которой, эзотерические языки типа Brainfuck – тривиальны, как 2+2. Для массового внедрения DF-машин требовались специальные чудовищно сложные компиляторы и специальная Host-машина, которая могла автоматически переводить код в графы DF-языков.

вычислительные системы с управлением по запросу или редукционные машины
(Demand-driven control computer, DDCC).

Концепция DDCC основана на уже упомянутых lazy evaluations – ленивых вычислениях. Как это работает:
Любое вычисление активизируется только тогда, когда в нем возникает потребность.
Любое вычисление перестает быть активным, когда потребность в нем исчезает.
Выполнение программы в целом активизируется запросом на получение результата.

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

усилия, не удалось установить, были ли прототипы чистых редукционных машин построены и испытаны. В принципе, к ним можно отнести процессоры, использующие в качестве внутреннего функциональные языки, типа Lisp, Haskell и подобные. Такие проекты существовали, например, инженеры EPRSC (Совет по физическим и техническим наукам Великобритании) в 2011 г. разработали Reduceron – FPGA чип, оптимизированный для выполнения функционального кода.
При тактовой частоте 96 МГц, на специальных задачах он характеризуется высоким параллелизмом и показывает производительность 25% от Core 2 Duo с частотой 3 ГГц, тогда как в обычных процедурных задачах Core 2 Duo на порядок быстрее FPGA. Если сравнить с Pentium 4 2,8 ГГц, то очевидно, что код Haskell, например, быстрее выполняется на Reduceron.

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

удельной производительности процессоров.
За шесть лет удельная производительность DEC Alpha сократилась в 100 раз, а процессоров IBM- в шесть раз.

Алана Тьюринга.
1949 Создан ENIAC – предшественник реконфигурируемых систем
1954 В США построены монозадачные компьютеры для дешифровки советских переговоров - Johnson и Oedipus. Производительность их была на порядок выше лучшей универсальной ЭВМ тех лет – IBM 701.
1959 Один из создателей атомной бомбы и коллега фон Неймана Джон Паста предложил идею реконфигурируемых машин.
1960 Профессор Калтеха Джеральд Эстрин выступил на конференции Western Joint Computer Conference с докладом «Организация вычислительной системы, состоящей из постоянной и переменной структур».
1971 Компания DEC выпускает прототип PDP-16 – компьютера с частично реконфигурируемой структурой собранной на основе модульной схемы Register-Transfer Modules. PDP-16 представлял собой своего рода конструктор, из которого можно было собирать компьютер, адаптированный к конкретным алгоритмам управления. Машина была разработана на основе программируемого логического контроллера PDP-14.

Реконфигурируемые компьютеры

Simatic S5 с программатором

Omron CJ1 – современная реализация
программируемого логического контроллера

управления до сих пор и программируются на языках релейных схем LD (Ladder Diagram), SFC (Sequential Function Chart) и FBD (Function Block Diagram):

Реконфигурируемые компьютеры

логике было практически невозможно. Возникшую проблему нужно было решать с помощью микроэлектроники:

Реконфигурируемые компьютеры

1967 Появление первых ASIC-микросхем под названием Fairchild Semiconductor Micromosaic, однако широкого распространения они не получили. ASIC (Application-Specific Integrated Circuit) – монозадачная интегральная схема, выполненная на заказ для решения конкретной проблемы. Способна выполнять ограниченный набор функций, однако эффективность реализации этих функций обычно очень высока.
1970 Разработан первый тип SPLD (Complex/Simple Programmable Logic Device) – микросхема, содержащая относительно крупные программируемые логические блоки - макроячейки (macrocells), соединённые с внешними выводами и внутренними шинами. Функциональность CPLD кодируется в энергонезависимой памяти, поэтому нет необходимости их перепрограммировать при включении.
1975-1980 Появление и активное использование монозадачных микросхем ASIC, разработанных на основе технологий PLA (Programmable Logic Arrays), PAL (Programmable Array Logic) и ULA (Uncommitted Logic Array). С помощью таких чипов собирают все более-менее мощные компьютеры от Cray до Fujitsu и активно используют их в разработке нестандартных архитектур – от систолических массивов до DF-машин.
1984 Изобретена Flash-память, основаны компании Altera и Xilinx два ведущих разработчика реконфигурируемых чипов. Изобретена FPGA (Field-Programmable Gate Array)-микросхема – вершина технологии реконфигурируемых чипов.
1992 NASA впервые применило FPGA в космических технологиях.
1995 Altera и Xilinx начали выпуск FPGA-микросхем, обладающих достаточной мощностью для выполнения цифровой обработки сигналов.
2004 Компания Cray выпустила FPGA-сопроцессоры XD1.

аппаратная часть неизменна,
меняется программное обеспечение

ENIAC
Динамическая реконфигурируемая машина:
Программного управления нет,
машина конфигурируется на решение
одной текущей задачи

Архитектура фон Неймана
и традиционные машины IAS, IBM и т.п.

Традиционный статичный процессор с программным управлением – x86 и другие архитектуры.

PDP-16 и реконфигурируемые машины на дискретных элементах.

ASIC – заказные микросхемы для решения конкретных задач

FPGA – чипы, программируемые пользователем под конкретную задачу

и FPGA нужно уяснить базовые принципы схемотехники ЭВМ:

Реконфигурируемые компьютеры

Любая операция в компьютере на самом низком уровне – по сути преобразование двоичных чисел.
Любое такое преобразование можно выразить посредством логических операций, таких как И, ИЛИ, НЕ и так далее.
Любую комбинацию логических операций можно воплотить физически в виде набора логических вентилей.

Вот три простых операции алгебры логики: И, ИЛИ и НЕ. Как они работают можно понять, просто записав в виде таблицы чему равно их значение в зависимости от аргументов:

И

ИЛИ

НЕ

Существуют и более сложные операции:

Естественно, через них можно выразить и традиционные операции алгебры, например, сложение:

допустим, на реле:

Реконфигурируемые компьютеры

Если реле замкнуто (RY=1), то Vout =0
Если реле разомкнуто (RY=0), то Vout=1
В результате мы построили инвертор.
Вот то же самое, только на транзисторе:

штуки?

и много-много другого:

Реконфигурируемые компьютеры

Вот, например, мажоритарный клапан с тремя входами:

сложную схемотехнику, вот, например, CMOS-вентиль 2И-НЕ:

Реконфигурируемые компьютеры

Что бы проектировать такие штуки используют специальный софт, где можно нарисовать нужную схему буквально по транзистору:

САПР Microwind

получить собственную монозадачную микросхему, нам надо пройти следующие шаги:

Анализ задачи, для которой производится микросхема и составление ее математической модели, например, обработка звука – быстрое преобразование Фурье.
Представление оной модели через стандартные логические операции.
Параллельно другие специалисты изучают наиболее эффективную реализацию логических ячеек на физическом уровне и подготавливают библиотеки standard cell.
С использованием данных библиотек инженеры-проектировщики в САПР (типа уже показанного Microwave) полностью описывают топологию заказной микросхемы.
На основе файла САПР создается фотошаблон и начинается производство.
Результатом становится заказная монозадачная интегральная схема – ASIC:

Одна стандартная ячейка с 3 слоями
металлизации (а бывает до 7!)

Готовые микросхемы ждут заказчика

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

Реконфигурируемые компьютеры

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

Есть лишь пара проблем:
Все-таки это не полноценный реконфигурируемый компьютер, а монозадачный. С одним делом он справляется намного быстрее, чем любое другое устройство вообще, но только с одним.
Полная разработка и изготовление одной заказной микросхемы, в зависимости от ее сложности, стоит от 1000.000 до 20.000.000-30.000.000$. Естественно, что для окупаемости этой разработки, тираж чипов должен исчисляться миллионами штук, только тогда себестоимость одного чипа будет около 10-20 центов. Такое под силу оплатить только крупным компаниям.

Но эти проблемы можно победить с помощью истинного шедевра техники
– программируемой пользователем вентильной матрицы (FPGA).

Микросхема, которая не использует программного управления, но конфигурируется пользователем на языке описания аппаратуры для решения любой задачи.
Конфигурация может быть выполнена в любой момент и неограниченное число раз.
Чип состоит из конфигурируемых логических блоков, подобных переключателям с множеством входов и одним выходом (gates).
И функции блоков, и конфигурация соединений между ними могут меняться с помощью специальных сигналов, посылаемых схеме.
FPGA могут постоянно перепрограммироваться и менять топологию соединений в процессе использования, однако, такая гибкость требует существенного увеличения количества транзисторов микросхемы.

Придумываем задачу и
схему которая ее решает

Моделируем схему на
языке VHDL или Verilog

Вставляем FPGA в программатор
и прошиваем

Наслаждаемся собственной архитектурой

1

2

3

Повторять пока не надоест!

4

себя (зеленым выделены программируемые элементы):

Маршрутизаторы каналов (routing channels)

Некоммутированные программируемые логические блоки
(Configurable Logic Block – CLB или Logic Array Block - LAB)

Блоки ввода-вывода (I/O pads)

Память (RAM)

Тактовый генератор (Clock)

Типичная ячейка (ALM, LE, Slice)
состоит из триггера и
4-х входовой логики

Современные FPGA часто включают и
продвинутые блоки, такие как DSP

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

Также в состав чипа могут входить различные контроллеры, видеоядро
и т.п. – получается программируемая
система-на-кристалле (SoC)

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

Реконфигурируемые компьютеры

Xilinx
Altera
Lattice Semiconductor
Microsemi (Actel)
SiliconBlue Technologies
Achronix
QuickLogic
Tabula

Производители:

FPGA (Microsemi)

о тысячах фанатов железа!