Category: компьютеры

Category was added automatically. Read all entries about "компьютеры".

with Cat The Cat

OpenRISC.

Дал себе труд почитать архитектуру OpenRISC и систему команд оного.

Я бы сказал, что так себе творение.

Зачем, например, теневые регистровые файлы? Аж до 4-х штук зарезервировано. Регистровый файл - это, приблизительно, 5% площади процессора типа MIPS-III. Два файла добавят всего 5%, а три и четыре добавят уже больше 10% дополнительной площади, что становится заметно. Большую часть времени эти регистровые файлы будут простаивать.

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

Команды переходов (не все!) имеют команду такта задержки (branch delay slot).

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

Один из вариантов команды деления устанавливает флаг и может бросить исключение, другой - только бросает исключение.

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

Что на выходе.

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

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

Польза от OpenRISC в его "открытости" и в том, что под него есть компилятор и Линукс. Линукс ладно, полезен, но вот кому нужна "открытость" такой неприятной архитектуры...
with Cat The Cat

Ещё про out-of-order.

Мне известно два алгоритма внеочередного исполнения команд: инженера IBM Tomasulo и доска ресурсов.

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

Второй много проще. Этап "записи в регистровый файл" сообщает блоку выдачи команд, какой регистр имеет установленное значение. Команда cmd dest, srca, srcb запустится, только если регистры srca и srcb установленны. На время выполнения команды регистр dest будет считаться не установленным.

Этот алгоритм легко реализуется на битовых операциях над битовым вектором размером с количество регистров. Заметные изменения касаются только блока выдачи команд и они нисколько не революционны.
with Cat The Cat

Про команды переходов. И про out-of-order.

(я не буду рассказывать про технику предсказания переходов вообще, я лучше про выгоды предпросмотра - и out-of-order выполнения, - расскажу)

Итак, есть у нас процессор, который выполняет команды последовательно, друг за другом.

Вот встретилась ему последовательность:

ld t1, 4(t2)
j t1

Загрузить в регистр адрес и перейти. Что плохого может произойти с процессором? В принципе, при достижении команды j он должен остановить конвейер до момента поступления значения t1 в счётчик команд (PC). То есть, команда дойдёт, как минимум, до этапа чтения операндов и мы потеряем один или два такта. Далее мы можем потерять время на ожидание данных из общей памяти, если в кэше их не оказалось.

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

Однако, запуск t1 произойдёт только после записи в t1, а команда загрузки может выполняться довольно долго. Поэтому мы потеряем 3 и более тактов на ожиданиях.

Представим себе, что мы можем заглядывать в будущее и выбирать команды.

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

После получения адреса в t1 мы можем запустить на выполнение команду перехода. Команда перехода сможет быть выполнена, если повезёт, ранее, чем команды до загрузки t1. А если мы следим за командами перехода и считаем их приоритетными, то можно это гарантировать.

В результате, пока выполняются команды, у процессора есть время подкачать команды в кэш.

Это мы рассмотрели самый сложный случай. Обычно случаи попроще. Типа такого:

beqz r1,label

Если регистр r1 равен 0, то перейти. Если не равен - продолжить.

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

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

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

В случае такого использования окна предпросмотра команды подкачки данных в кэша программисту вставлять не обязательно. Это сделает сам процессор.

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

Наша модель MIPS имела весьма похожий алгоритм работы.

PS
Branch delay slot - ненавижу! ;)
with Cat The Cat

В связи с iteratees...

Вот их тип:
data Iteratee el m a = IE_done ! a
		     | IE_cont ! (Maybe ErrMsg)
		               (Stream el -> m (Iteratee el m a, Stream el))
data Stream el = EOF (Maybe ErrMsg) | Chunk [el] deriving Show
Взят отсюда.

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

Хочу напомнить про Fudgets, а точнее, про их stream processors.

И вот их тип:
data SP i o = Nil | O o (SP i o) | I (i -> SP i o)
Здесь три варианта: "стоа", "выдать кусок результата и продолжить" и "продолжить, получив вход".

IE_done выше может быть записано, как O a Nil. IE_cont maybeErrMsg cont записывается, как O maybeErrMsg (I cont).

Ну, я немного слукавил. Сейчас исправлюсь.

Что, если мы SP параметризуем монадами? Получится вот, что:
data SPM m i o = Nil | O o (m (SP m i o)) | I (i -> SPM m i o)
Тогда IE_done result эквивалентно O (Right result) Nil. А IE_cont mbMsg cont эквивалентно O (Left mbMsg) cont.

Полный эквивалент получается такой:
newtype SPIteratee m el a = SPIteratee (SPM m (Stream el) (Either (Maybe ErrMsg) (Stream el,SPIteratee m el a)))
Правда, не проверял, работает ли. Но всё равно, получилось близко, наверняка. Ещё подкрутить, и заработает. ;)

И iteratee, и потоковые процессоры растут ногами из ленивых списков, поэтому структура у них похожа.

Давно уже хотел сделать это - напомнить о потоковых процессорах в связи с бумом iteratee.

Если что, то потоковые процессоры были одним из первых более-менее работающих вариантов взаимодействия с внешним миром в чистых функциональных языках. Они были параллельно сделаны для Haskell и LazyML. Что ещё интересней, на них была построена библиотека пользовательского интерфейса - те самые фуджеты. В начале 2000-ных я даже играл в Space Invaders, дав программе на фуджетах подключиться к моему X Window Server-у.

Пожалуй, всё.
with Cat The Cat

Вуаля!

Итак, моя модель MIPS начала выдавать первые выборки (если возвращать NOP ;).

Я добавил тест, вот результат его запуска:
*MIPS_with_mem> fetchesOfMIPSWithSeroesMemory_S
40000000
40000004
40000008
4000000c
40000010
40000014
40000018
4000001c
40000020
40000024
*MIPS_with_mem>
(запускать надо "ghci -fcontext-stack=100 -istreams -icommon MIPS_with_mem.hs")

Мы всегда передаём 0 в качестве результата выборки, в системе команд MIPS это NOP, поэтому наш процессор последовательно перебирает адреса команд.

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

Что же там происходит.

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

Однако, в обычной функции отсутствует понятие (дискретного) времени, она не может напрямую работать с бесконечными списками данных. В основном, это ограничение операции сравнения с образцом case: если я сравниваю со значением, погруженным в конструктор (бесконечного списка), то мне надо этот конструктор разобрать. Все остальные операции могут быть подняты на бесконечные списки простой перегрузкой с помощью map_S, zipWith_S и тп.

Поэтому для введения дискретного времени необходимо прозрачно поднять эти операции. Это выполняет модуль Trans в каталоге streams, функцию transform которого можно использовать для проведения такого преобразования.

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

Вот кусочек исходного текста:
cond = case cmd of
	JALR rs rd -> True
	JR rs -> True
        ...
Вот, как он поднимается на бесконечные списки:
cond_14 = S.map_S (\caseExprVar_15 -> case caseExprVar_15 of
    MIPS.JALR rs_16 rd_17 -> GHC.Bool.True
    MIPS.JR rs_18 -> GHC.Bool.True
    ...
Всё незамысловато.

Если кому интересно, то при работе transform создаётся trans_log, куда пишутся результаты преобразований. Однако там слишком много информации.

Что хочу сделать.

Надо сделать ассемблер MIPS и запустить пару программ посложнее.

Хочу сделать ведение отчётов. Чтобы можно было написать в преобразуемой функции что-то вида currentAddressTwoLeastBits = report (currAddr .&. 3) и в результаты работы, в выходы функции, попадали бы все такие report в виде строки "currentAddressTwoLeastBits = 3".

После того, как заработает модель MIPS на реальной программе, я хочу сделать создание текста на настоящем HDL в виде иерархии сущностей. Само собой, сразу должен получаться синтезируемый код. Пока в качестве основного претендента выступает VHDL, он поудобней будет, хотя и многословен. Вариант - SystemC, для повышения скорости моделирования.

Далее преобразование функции в конвейер (чтобы поднять тактовую частоту, будет и для модели на бесконечных списках и для синтезируемого HDL) и тому подобные мелкие улучшения.
with Cat The Cat

Хвастовство.

ARM хвастается, что его новый процессор будет быстрее в 5 раз.

Жду с нетерпением, чтобы узнать, как это им удалось.

PS
По моему опыту, набрать 2 раза довольно легко - ускорить сложение на 10%, добавить логику "закоротки" результата (bypass logic) (1/длина конвейера, обычно 1/5), сделать параллельную выдачу команд, чтобы в среднем выдавалось 1,5 команды, вот и получилось ускорение в 1,1*1,2*1,5=1,98 раз. Но у ARM всё это уже есть, и даже лучше. Как и что они собираются сделать, мне непонятно.
with Cat The Cat

Тут у ivan_ghandhi случилось обсуждение...

...и я выяснил кое-что про Reduceron.

Вся его реализация занимает 14% от 17300 слайсов (slices) Xilinx Viertex-5. Прикинув, что слайс равен 4-м 4И-НЕ вентилям, я получил оценку в 10000 вентилей. Или 80000 транзисторов.

Ещё он занимает 90% полуторакилобайтной памяти. Это, исходя из оценки в 6 транзисторов на бит памяти, даёт ещё 66000 транзисторов.

Итого, 150 тысяч транзисторов. Это уровень количества транзисторов процессоров GreenArrays, творений Чака Мура.

В тысячи раз меньше, чем современные процессоры уровня Core2 Duo. Да добавим кэш, всё равно площадь будет в сотни раз меньше - единицы квадратных миллиметров.

Тактовая частота синтеза в ASIC поднимается раз в 8-10 по сравнению с частотой FPGA. Reduceron получит частоту в районе 700-800 MHz. Отставая сейчас в три раза, он будет быстрее в два раза, если сделать ASIC.

Получается, что эта штука будет работать быстрее и меньше занимать.

Сейчас в haskell-cafe напишу. ;)

PS
http://www.1-core.com/library/digital/fpga-logic-cells/

Ошибся в количестве эквивалентных 4И-НЕ. Там их 8 на slice. Ошибся в два раза.

Ну, не в 10, и то хорошо. ;)
PPS
С частотой я тоже поторопился. 5-8 раз.
with Cat The Cat

Две статьи.

Design and implementation of a simple, typed language based on the lambda-calculus, цель её - получить минимальный язык программирования, чтобы даже встроенных типов было минимум. "Оптимизатор справится". ;)

Реализация лямбда-исчисления "в железе". Пока не очень нравится - не очень "железно", по-моему, - но в паре с предыдущей смотрится интересно.
with Cat The Cat

Пока суть, да дело...

...Чак Мур сотоварищи выпустили 144-ядерный процессор. Каждое ядро 18-тиразрядно, в нём RAM на 64 слова и ROM на 64 слова. В каждое слово команды должно умещаться 3 команды MISC, наверное.

Ест программируемый ввод-вывод, на программной реализации.

В общем, чип-загадка. Из AppNote есть только "как считать MD5 на этой штуке". ;)