Sun Oct 05 2003 09:05, Roman Khvatov wrote to Ilia Tarasov:
IT>>>> Представим, что действительно все (ну или почти все) команды в IT>>>> исходном алгоритме зависимы по данным. RK>>> Так практически не бывает. IT>> y=sin(sqrt(abs(2*x))) Что здесь независимого?
RK> И это вся программа? Или в ней есть еще что-то? Вот это 'что-то' и будет RK> 'независимым'
Формально согласен. Добавлю, развивая тему, что данное вычисление занимает большую часть времени... Тогда какая, по большому счету, разница, на сколько процентов медленнее будут выполняться куски, и так занимающие малую часть кода?
IT>> Hапример, алгоритмы цифровой обработки часто сводятся к умножению с IT>> накоплением. Представим, что перемножитель один, и является, IT>> соответственно, узким местом. Что в этом случае можно распараллелить?
RK> Можно разделить умножаемый массив на 2 подмассива (с четными и нечетными RK> индексами), и умножать с накоплением эти половины отдельно, потом RK> результаты сложить, тогда 2 этих цикла умножений можно параллелить.
Не понял... Устройство умножения всего одно, что можно параллелить? Допустим, что накладные расходы на подготовку операндов равны нулю, они могут подаваться на вход АЛУ каждый такт (с автоинкрементом адресов). Что здесь можно еще запараллелить, если за такт может появиться только один результат умножения?
IT>> Кроме того, давай припомним, к какому ценовому классу относятся IT>> эмбеддед-процессоры, которые хотя способны выполнять по несколько IT>> инструкций за такт.
RK> Все вышеизложенное относится _именно_ к таким процессорам. Для обычных RK> процессоров (не суперскаляров) Форт процессор не будет уступать по RK> производительности.
Fixed. А Форт-процессор с запараллеленными стеками?
IT>> Когда есть надобность параллелить - таки фатально. Hо скажи, зачем мы IT>> пойдем направо, если знаем, что надо налево?
RK> Еще раз повторяю - когда нужно добится топовых скоростей, тогда и нужно RK> параллелить.
Fixed.
Кстати, я предпочитаю в таких случаях параллельный КА, и Форт-процессор, выполняющий настройку перед блочной конвейеризованной обработкой....
IT>> Кстати, завести именно пару стеков - не самоцель. А один стек IT>> возвратов и несколько стеков данных, работающих в параллель? (Идея, IT>> кстати!)
RK> Интересно, если объединить в один 3 плохих процессора, то получится один RK> хороший? Или все таки лучше объединять 3 хороших процессора :)
Конечно, 3 хороших :) Например, стековая архитектура на FPGA Xilinx дает ровно в 16 раз больший объем стековой памяти на тех же ресурсах... ;)))
RK>>> А это дело компилятора, обычно они неплохо справляются не только RK>>> со стековыми машинами :) IT>> А компилятор - это такая программка, которая ставится с IT>> компакт-диска?
RK> Угу.
Ну, кому как. Согласен, для подавляющего большинства разработчиков разработка собственного компилятора - далеко не первоочередная задача.
IT>> :) И она безглючна, бесплатна, осваивается в момент доставания диска IT>> из коробочки?
RK> Тебе шашечки или ехать? Хочешь получить производительность - покупай RK> компилятор (или пиши на асме, если в запасе есть неограниченное время :)
Мне - ехать с шашечками... :) Вот я обычно начинаю на асме, но использую ряд приемов кодирования, позволяющие писать слова "второго слоя" в стиле постфиксной стековой машины. Можно заводить переменные, можно пытаться упихать все в регистры... можно имитировать стиль процедурных языков - готовить стековый кадр, а потом снимать результат. Мне вот нравится на асме писать в стиле ЯВУ, и стиль Форта реализуется с наименьшими временными затратами...
RK> Что касается глюков - как ты думаешь, в чем проще исправить глюки, в RK> компиляторе или в процессоре? Или ты думаешь, что процессоры рождаются RK> сами по себе и абсолютно безглючные? И как ты думаешь, в каком процессоре RK> будет больше глюков - в том, который сложнее, или в том, который проще?
Проще исправить глюки в более простой системе. Форт-процессор (как и любой другой) представляет собой разновидность конечного автомата, и проектируется по соответствующим методикам.
RK> (А я уже писал, что Форт процессор будет сложнее аналогичного RISC RK> процессора)
Гораздо проще суперскаляра, и практически эквивалентен обычному регистровому (я пробовал в ПЛИС разные подходы). Удобство стекового процессора с командами, эквивалентными словам Форта, гораздо выше удобства регистрового процессора с тем же объемом ресурсов - для стековой архитектуры сразу готовы все алгоритмы, а для регистровой надо долго думать, как все туда упихать, и не завести ли еще регистр, а то что-то места мало и в память лезть приходится...
IT>>>> Для сравнения рассмотрим 4 симметричных регистра, и добавим к IT>>>> ним пятый. RK>>> Такой же симметричный? IT>> Такой же, или не такой же... не столь важно.
RK> Это важно. Если набор регистров не нимметричный (как в x86), то RK> распределение регистров усложняется (но не фатально)
Ага! То есть все-таки разница есть, и тут уже надо найти компромисс между разработчиком компилятора (которому желательно симметричный набор) и разработчиком железа, которому проще соединить этот новый регистр с каким-нибудь аккумулятором, но никак не реализовывать набор соединений вида "каждый с каждым".
RK>>> Если для задачи хватало 4х регистров - то повышения RK>>> производительности не будет вообще, а если не хватало - то быдет RK>>> весьма значительная.
IT>> Как понять "хватало"?
RK> Это когда компилятору хватало 4х регистров для хранения промежуточных RK> результатов.
(*)
IT>> Это когда в программе только 4 переменные,
RK> Hет
Очевидно. Это была одна крайность.
IT>> или когда зависимость по данным не вызывает простоев конвейера?
RK> Hет.
А как это соотносится с (*)? А вот держи примерчик:
a = b + c + d (1) b = a + d - с (2) c = a + b + 3 (3) d = a + b + c (4)
Налицо WAR при подстановке любой из строк 2-4 после 1.
IT>> Стоит ли делать новый процессор с дополнительным регистром,
RK> Если такая задача только одна, то очевидно не стоит, а если почти все RK> задачи такие - то стоит.
Так будет ли выигрыш - это ведь еще не решено....
IT>> будет ли он иметь лучшее соотношение цена/производительность?
RK> Это надо оценивать. В любом случае для ответа на такие вопросы надо знать RK> примерный круг задач, для которого используют процессор.
Ну и как же прикажешь начинать работу над новым процессором, если сначала для него (пока еще виртуального) надо написать кучу программ, протестировать их на моделях, и узнать у технологов, как будет меняться частота процессора в зависимости от сложности внутренних соединений? Да, это очень реально при многомиллионных вложениях в проект, я с этим и не спорю. Однако высказываю мнение, что со стековой архитектурой проблем будет меньше, поскольку увеличение глубины стека не сопровождается пересмотром основных алгоритмов.
IT>> И главное, не съестся ли эта добавка общим снижением рабочей частоты IT>> кристалла из-за усложнения схемы?
RK> Опять же надо оценивать реальный процессор, откуда я знаю, как в него RK> врезали 5й регистр?
Вот о чем и речь. А врезать можно по-разному, и программисту может быть почти все равно, а для технолога - сплошная головная боль. И наоборот.
RK>>> Hикак, просто исправить константу в распределении регистров в RK>>> компиляторе. IT>> Hеужели так просто? :)
RK> Если регистры равноправные - то да. Если нет - то степень изменений будет RK> варьироваться от изменения константы до полного переписывания RK> распределения регистров.
Не удержусь от цитатки: "Поиск оптимального назначения регистров переменным представляет собой сложную задачу, с точки зрения математики являющуюся NP-полной. Проблема усложняется ЕЩЕ И ТЕМ [выделено мной, IT], что аппаратное обеспечение и/или операционная система могут накладывать дополнительные ограничения по использованию регистров" (Ахо, Сети, Ульман "Компиляторы. Принципы, технологии, инструменты)
IT>> Hапример, надо в 80x86 сложить что-нибудь с AX. IT>> В какой регистр будем грузить второй операнд: BX, CX, DX?
RK> Тут скорее всего понадобится алгоритм с привлечением динамического RK> программирования.
Skipped & Fixed, ибо мы, имхо, поняли друг друга в этом вопросе...
RK> Я не утверждаю, что Форт никуда не годится. Есть приложения, где он RK> категорически не подходит, а есть, где он имеет преимущество:
RK> Форт процессор категорически не подходит для: RK> 1) Изготовления на его базе top-preformance процессора
В целом соглашусь, и придерживаюсь той же позиции. Стековое ядро мне сейчас очень нравится для реализации embedded-процессоров в ПЛИС, где оно занимает мало места, позволяя при этом писать на ЯВУ для 16-32 разрядов и 20-40 МГц.
RK> Форт процессор подходит для: RK> 1) Применения в качестве процессора для которого ассемблером является ЯВУ RK> (если Форт таковым можно назвать :), при этом имеет значение компактность RK> кода и не имеет значение производительность. (Весьма умозрительный пример RK> :)
Да. Кстати, производительность все же не так плоха, регистровая архитектура не дает существенного выигрыша... если вообще дает его в ПЛИС.
RK> Форт, как система програмирования, подходит для: RK> 1) Платформ, типа OpenBoot (Форт зашит в ПЗУ и служит для загрузки RK> системы). При этом драйвера различных карт (сеть, диск и др.), с которых RK> производится загрузка, написаны на этом самом Форте и зашиты в ПЗУ на RK> этих картах. (Кстати, в спецификации PCI есть перечисление платформ, для RK> которых на PCI картах могут находится драйвера ввода-вывода, это x86 - RK> расширения BIOS'а, и OpenBoot) 2) Платформ, где необходимо иметь RK> интерпретатор для исполнения кода из большой внешней памяти (процессор, RK> типа PIC и AVR плюс большой внешний EEPROM). И то, в этом случае Форт как RK> язык програмирования для этих платформ мало пригоден (из за его RK> необычности), а вот Форт VM вполне пригодна.
И с этим полностью соглашусь. Заметь, однако, что сфера применения все же появляется, и довольно обширная... И стоит ли в таком случае исключать Форт из обсуждаемых тем из-за непривычного синтаксиса или плохой производительности отдельных трансляторов?