Zealint писал(а):
Поэтому западные коллеги и шли по классическому пути – брали популярные СКА и пытались в них что-то посчитать. Но, к сожалению, они либо не догадывались, что ни одна современная СКА не приближается по эффективности к даже наскоро сляпанной на коленках бинарной реализации алгоритма, либо знали, но сами запрограммировать не умели так же хорошо, как это сделает профессионал. Здесь мне и пригодилась олимпиадная подготовка, которой не было у тех западных исследователей. Я реализовал ими придуманные алгоритмы на C++/Assembler так, что они работали быстрее в десятки, сотни и даже тысячи раз, потребляя при этом на порядки меньше оперативной памяти, что и позволило получить новые результаты.
Лет 15-20 тому назад я интенсивно занимался нейростями (было очень популярное направление и многие ими не на шутку загорелись), и пришёл к аналогичному выводу касательно СКА. В частности, я использовал для своей работы Matlab. Мне нужно было обучать нейросеть, но прямолинейные методы обучения даже относительно небольшой нейросети на большой выборке данных могло занимать совершенно невозможное количество времени. Использование алгоритма Левенберга-Марквардта в Матлабе позволяло сократить обучение до нескольких дней прогона ПК. Каково же было моё удивление, когда ручная реализация алгоритма Левенберга-Марквардта на С++ укладывалась по времени на той же выборке примерно в час-два работы!
Zealint писал(а):
Я задумался: почему Maple, например, не может вывести линейное рекуррентное соотношение или производящую функцию порядком несколько сотен, а моя программа выводит подобные соотношения порядком несколько десятков тысяч? Почему Maple сжирает два с половиной десятка гигабайт оперативной памяти на пустом месте, когда моя программа укладывается в на порядок меньший объём для решения той же задачи?
После этого я тоже задумался о причинах такой неэффективности. Для себя я нашёл следующий ответ. Матлаб, R (и прочие продукты того же класса) не являются высокоэффективными компиляторами с их языков в машинный код. Они интерпретируют программу или получают байт-код, что равносильно интерпретации. Да, я знаю, что можно скомпилировать программу Матлаб в независимое приложение, но принцип его работы по сути тот же - просто вместо непосредственной интерпретации для каждой конструкции вызывается соответствующая подпрограмма из библиотеки матлаба. А все эти библиотеки сами по себе написаны на С/С++ и вместо простых данных получают на входе сложные структуры, описывающие компоненты и входные данные вашей программы. Таким образом, копиляторы этих пакетов знать ничего не знают про архитектуру машины и про оптимизацию даже самого примитивного выражения, написанного на их языках. Побочным эффектом такого подхода, также серьёзно снижающим производительность является неэффективность использования кэш-памяти. Тот код, который мог бы поместиться в несколько килобайт, использует несколько мегабайт. В этих условиях я вижу один правильный выход. Для научных расчётов необходим язык высокого уровня, сопоставимый по удобству использования с языками этих математических пакетов, но являющийся при этом настоящим оптимизирующим компилятором.
Zealint писал(а):
Я понял, что нужен инструмент, который был бы близок к железу, но при этом имел бы высокоуровневый интерфейс. Что-то компромиссное между интерпретатором и компилятором. Некая оболочка, которая позволяет вводить команды как при работе с интерпретатором, но сами команды вызывали бы уже заранее скомпилированные подпрограммы.
Как я уже написал, компиляция неизбежна, если требуется эффективный код. Компромисс может заключаться в том, что компиляция сейчас - довольно быстрый процесс, а интеграцией компиляции и интерпретации является работа с командной строки, - командный процессор является интерпретатором, но запускает скомпилированную программу.
Zealint писал(а):
При этом всё это должно работать как можно ближе к железу, минуя функции операционной системы и масштабироваться на большое число ядер или процессоров. Вот так: включился компьютер, перешёл в 64-битовый режим, определил все ядра, затем система предлагает вводить команды. Не нужна никакая многозадачность – каждое ядро работает на полную мощность своих вычислительных команд и по сути не нужны никакие прерывания, кроме некоторых немаскируемых. Для этого не нужна полноценная ОС в привычном нам смысле.
То, что вы сейчас написали, в общем-то и является отличительными чертами
хорошей ОС, а никак не
отсутствия ОС. Операционная система должна перевести процессор в 64-битный режим (то, что вам надо), определить все ядра, всю доступную память и по максимуму предоставить приложению все имеющиеся ресурсы. Многозадачность в данном контексте означает не кучу запущенных сервисов, которые толкаются локтями, а возможность запустить несколько процессов и (что важно!) -
потоков. Без поддержки многопоточности ваша программа не сможет задействовать параллельную работу на нескольких ядрах и разные потоки не смогут обмениваться данными. Без ОС нельзя, так как она выполняет чрезвычайно важные функции - абстрагирует существующее железо и предоставляет возможности ввода/ывода. Без абстрагирования вам придётся самому писать все драйверы устройств и вы быстро повеситесь, даже всего лишь попытавшись вывести на дисплей "Hello, World!". А без ввода/вывода потребуется, например, самому писать драйверы файловых систем (ведь не будете же писать данные посекторно) и стек протоколов TCP/IP (для передачи ваших данных по сети с кластера на ваш ПК). Всё это - как раз прямые функции ОС. Другое дело, что настольные ОС больше ориентированы на обилие свистоперделок, а не на HPC (high performance computing).
Zealint писал(а):
Мне удалось поработать на двух кластерах: на одном было 80 ядер, на другом несколько тысяч и... я был глубоко разочарован в обоих. Мой домашний компьютер (Core i7 3960X @3,3 GHz, 24 Gb DDR3-1333), в котором 6 ядер (12 виртуальных) как щенка уделывал 80-ядерный кластер (10 узлов, 2xQuad-Core Intel Xeon 5430 2,66 GHz, 4 Gb DDR2-667 на каждом узле). Как такое может быть? Кластер – большой, а процессор у меня дома – маленький. Пока ядра кластера обмениваются сообщениями, проходит много времени. Я не знаю, чем руководствовались менеджеры, заказывающие такую сборку, но более глупого решения, чем поставить на один узел всего 4 Гб медленной памяти, обслуживающей 8 ядер, я бы не смог и выдумать.
Судя по конфигурации, 80-ядерный кластер не первой свежести. Я могу сказать, что выбор конфигурации - ответственный момент и стоит его учитывать до запуска расчётов. Дело в том, что память - не дешёвый ресурс и разработчики кластера (или сервера) часто вынуждены идти на компромисс: поставишь мало памяти - не хватит, много - выкинешь деньги зря. Особенно это характерно для суперкомпьютеров, поэтому узлы СК часто имеют разную конфигурацию и задача решается на тех узлах, которые подходят максимально хорошо. Тут не стоит винить создателей кластера, - вероятно, во время создания память стоила дорого, а 4ГБ на узел вполне хватало для конкретных расчётов.
Zealint писал(а):
Я быстро понял проблему архитектуры x86 в плане применимости её к задачам моего типа. Да, никто не спорит, что это мощная архитектура, но для того, чтобы «пробивать» перечислительные задачи не нужно иметь столько команд. У нас всего 4 арифметических операции, да условные переходы и доступ к памяти, а работать на x86 архитектуре – это всё равно что ездить по дому на машине. Слишком мощно.
Судя по описанию, вам подошёл бы RISC-процессор, - операций мало, ничего лишнего, но есть всё, что вам необходимо. Ошибка в том, что на самом деле скорость выполнения программ не коррелирует с набором инструкций. Даже если речь идёт всего-лишь о 4 арифместических операциях, условных переходах и доступе к памяти! В данном случае "слишком мощно" быть не может, ведь вам нужна
максимальная скорость выполнения.
Zealint писал(а):
Ещё одна проблема: почти все задачи оперируют длинными числами, доходит до нескольких миллионов бит. Я не знаю популярных архитектур, которые были бы оптимизированы для работы с длинными числами. Да, поскольку длина числа может быть любой, невозможно вот так просто взять и создать регистр в 640 миллионов бит, считая, что его «всем хватит». Не хватит : )
Тут проблема в том, что железо вообще не терпит гибкости. Резиновый регистр сделать, вероятно, возможно, но для этого потребуется масса аппаратной логики, бОльшая часть которой будет простаивать, занимая полезную площадь, а программная реализация той же работы не сильно уступала бы аппаратной. Смотрите, проблема в данном случае не в регистрах, есть процессоры, которые могут брать операнды непосредственно из памяти и возвращать результат обратно в память. Проблема в том, что аппаратная реализация определённых действий оказывается неоправданно сложна и чревата весьма неприятными проблемами. Как, например, поступать в следующей ситуации: мы одной инструкцией складываем два миллионобитных числа и вдруг оказывается, что последняя тысяча бит отсвоплена на диск? Откатывать миллион бит обратно и выкидывать промежуточные результаты? А где хранить почти миллион бит промежуточного результата, если есть вероятность отката операции? Останавливать процессорное ядро, пока другое ядро занимается вводом-выводом? А если во втором ядре при этом тоже случился page fault? В общем, поверьте, предполагаемая гибкость порождает больше проблем, нежели сулит выгоды.
Zealint писал(а):
И оперативной памяти для манипуляции с набором таких чисел тоже не хватит. По этой причине вычисления обычно выполняют в факторкольце Z/(p), а ответ восстанавливают по Китайской теореме об остатках. То есть нужно несколько раз (на практике несколько сотен тысяч раз) запустить программу с разными значениями p. Было бы здорово, чтобы в процессоре имелась возможность аппаратно проводить вычисления по модулю.
Аппаратная реализация какого-то действия имеет смысл в двух ситуациях. 1. Она может быть представлена в виде неделимого на последовательные или однородные параллельные функциональные блоки алгоритма. 2. Она существенно сокращает поток данных (например, если сама очень часто используется - не в плане цикла, а, например, в миллионе мест в программе). Насколько я знаю (может быть ошибаюсь, тогда поправьте меня), любая попытка аппаратной реализации вычислений по модулю (за исключением частных случаев) неизбежно раскладывается на две последовательные операции - например, умножение и нахождение остатка. Следовательно, реализация двух действий одной инструкцией не даст выигрыша в скорости выполнения.
Zealint писал(а):
Одна задача – одна архитектура.
То есть в идеале, когда мы ставим задачу, мы разрабатываем новую архитектуру, микроархитектуру и создаём процессор, эту задачу решающий. Однако, создать процессор очень и очень трудно, экономически несопоставимо с возможной отдачей от полученного решения задачи. Поэтому следует рассмотреть все существующие алгоритмы, разделить их на классы по тому, какие типичные операции используются в этих алгоритмах и создавать архитектуру под этот набор операций. Таким образом, менее правильным, но более экономически состоятельным образом данный тезис переформулируется, например, так:
Один класс алгоритмов – одна архитектура.
Однозначно нет. Даже классы алгоритмов не оправдают затрат на создание новых процессорных модулей (ПМ - давайте я так назову те расширения, о которых вы говорите). И причин тут множество, одна из основных - организация взаимодействия ЦП с ПМ. Раньше были сопроцессоры, но сложность современного ЦП не позволяет организовать эффективное взаимодействие с сопроцессором. Другая причина более глубинная. При внимательном изучении любого алгоритма оказывается, что он эффективно делится по операциям на универсальные базовые составные части (те же арифметические действия), и единственный выигрыш, который можно получить, это параллельное выполнение некоторых базовых действий. То есть, специализация в данном случае не добавляет новых базовых действий, а может только изменить комбинации параллельно выполняющихся действий. Но эту задачу лучше решать другим способом, не разработкой новых ПМ под каждый класс задач.
Zealint писал(а):
Каждый класс требует определённого набора операций, а значит нужно сделать максимальный упор на то, чтобы эти операции выполнялись бы как можно эффективнее, а остальные операции уже как получится. То есть мы делаем отдельный процессор для линейной алгебры, отдельный для работы с рациональными числами, отдельный для теории чисел и т. д.
Вооот. Вы говорите про определённые наборы операций, а я пока что не вижу в этих классах
разных операций, отличных от тех, которые выполняют классические CISC-процессоры.
Zealint писал(а):
* только 4 арифметические операции с целыми числами.
Ограничение в данном случае ничего не даст.
Zealint писал(а):
* как можно более высокая разрядность регистров
До определённого предела (64-бита для целых чисел) выигрыш действительно есть, дальше он исчезает.
Zealint писал(а):
* встроен генератор простых чисел, согласованных по размеру с разрядностью регистров
Простите, не понял. Генератор
простых чисел, это не описка? Может быть случайных?
Zealint писал(а):
* организована такая арифметика, в которой операции могут работать как в традиционном режиме «с переполнением», так и в классе вычетов Z/pZ.
* аппаратная поддержка некоторых функций теории чисел (НОД, функция Эйлера, и т. д.).
Вы затронули довольно интересную тему, однако, мне кажется, что тут (как и в арифметике над полем по модулю) довлеет стереотип, что аппаратная реализация обязательно быстрей программной. Она действительно быстрей, но только в том случае, если самый быстрый существующий алгоритм, который только допускает аппаратную реализацию, не может быть разбит на последовательные части или параллельные однородные части. Иначе аппаратная реализация представляет собой ничто иное, как координацию уже реализованных аппаратных блоков. Рассмотрите каждую из предложенных функций и посмотрите, существуют ли такие специфические неделимые (или параллельные неоднородные) действия для них. Кстати, современные суперскалярные процессоры способны параллельно выполять даже неоднородные действия.
Zealint писал(а):
* обеспечена суперскалярность (но не VLIW) в том смысле, что независимые по данным команды выполняются (почти) одновременно, либо какой-то другой класс параллельности выполнения независимых во всех смыслах команд.
Сейчас основные усилия компьютерных архитекторов как раз направлены на поиски способов параллельного выполнения кода. Поэтому, даже когда вы пишете на ассемблере две последовательные инструкции это совсем не означает, что они будут выполняться в той же последовательности, а не параллельно или даже наоборот.
Zealint писал(а):
[ Представьте, приходите вы в магазин, и говорите: «мне, пожалуйста, модуль линейной алгебры и два модуля дифференциальных уравнений» ] А вам продавец в ответ - а какая частота шины? а в каком корпусе нужен модуль, LGA1234 или LBGA4321? А на какое напряжение питания? А для какого поколения ЦП? С вас 3000$ (по тыще за каждый модуль). А когда вы приходите домой, то оказывается, что они не совместимы с вашей материнской платой (хотя исправны) и возврату не подлежат как "технически сложные изделия", тогда вы бежите искать совместимую материнку
. Нет уж, увольте, никаких модулей IMHO быть не должно. Надо делать ЦП изначально таким, чтобы задачи любого класса работали на нём хорошо.
Zealint писал(а):
Есть ряд идеи и по тому, каким может быть язык, но это уже повод для другой беседы.
С удовольствием обсужу.
Zealint писал(а):
Я не прошу бросаться с жёсткой критикой, нет смысла сильно критиковать смутно-интуитивные представления неспециалиста по архитектуре, если она вам не нравится. Смысл есть только указать на возможные трудности такого подхода или причины, по которым такой подход хуже имеющегося. Но если моя история нашла своё отражение в вашем сознании, поддержите беседу, поделитесь своими наработками в области разработки архитектуры, своими проблемами и своей историей, которая явилась причиной появления у вас необходимости разработки своей архитектуры. Мне интересно посмотреть на эти идеи с позиции специфики моих научных расчётов, а также собирать подобные истории, чтобы усилить и свою аргументацию.
На самом деле приятно встретить умного собеседника с большим практическим опытом. Не воспринимайте критику идей как личные нападки, критика для разработчика жизненно необходима, чтобы не совершать очевидных ошибок или по крайней мере, чтобы любое решение было взвешенным. В разработке компьютерных архитектур как раз не хватает участия основных потребителей (супер)компьютерных ресурсов и в первую очередь математиков и людей с сильной математической подготовкой.
Zealint писал(а):
Ваша идея хороша, если мы хотим прямо сейчас создать модуль и экономически не очень затратно приделать его к имеющейся архитектуре. Однако, если моя идея найдёт воплощение, то она будет ещё экономнее. Так, посмотрите не видеокарту...
Вот как раз это - самый эффективный способ, если требуется что-то совсем неординарное. Берём отладочную карту с мощным FPGA и PCI-E слотом, устанавливаем в комп и программируем наши функции непосредственно в железе. Также существуют реконфигурируемые суперкомпьютеры на FPGA именно для таких случаев. Однако, заметьте, большого распространения они не получили именно по той причине, что базовые операции нужны везде одни и те же. Считайте, что производительность шины PCI-E 16x - это примерный максимум того, что вы можете получить на нелокальной шине, т.е. установка ПМ на другую шину вам принципиально нового ничего не даст кроме проблем совместимости.
Zealint писал(а):
В Вашем предложении меня лично не устраивает скорость взаимодействия карты с процессором.
Ага, вот он важный пункт! Повод для размышления - как вы думаете, почему скорость маленькая, потому что процессор слабый, видеокарта слабая или есть какие-то другие важные причины? Подсказка уже есть выше.
Zealint писал(а):
Согласитесь, что скорость будет выше, если разрядность регистров будет не 64 бита, а 1024, например. Или я не прав?
Не правы. Если брать, например, операцию умножения, то полная аппаратная реализация пропорциональна квадрату размера чисел плюс значительный довесок на ускоренные переносы. Таким образом 1024-битный умножитель будет в 256 раз больше! На самом деле часто умножители большой разрядности часто делают на умножителях меньшей с сохранением промежуточных результатов. Если рассматривать операцию сложения, то оказывается, что начиная с какого-то значения N мы не можем сделать эффективный N-разрядный сумматор, по той причине, что он будет превышать пропускную способность памяти, т.е. не сможем обеспечить его загрузку.
Zealint писал(а):
Неплохо было бы иметь строковые команды (префикс rep в x86), которые бегут по двум массивам чисел и складывают их с переносом.
Так это уже есть.
Zealint писал(а):
Ещё я считаю, что ОС должна быть сразу кластерной.
Безусловно.
Zealint писал(а):
Совершенно верно, я об этом не говорил пока, но одним из пунктов моей будущей параллельной СКА должна была стать автоматизация распараллеливания.
Каким образом??? У вас есть проверенные на практике идеи?
Zealint писал(а):
Можно согласиться, однако далеко не всегда целесообразно из кожи вон лезть, чтобы придумать схему вычисления с возможностью 100%-го распараллеливания, равносильную по сложности защите 2-3 докторских диссертаций. Часто проще попытаться создать кластер с максимально большим числом ядер на одном узле и быстрой общей памятью. Но такие мало кто себе делает.
Вы совсем не правы. 2-3 докторские диссертации - мизерная плата за такую важную работу. Подумайте, например, о том, что счёт за электроэнергию для суперкомпьютера "Ломоносов" составляет порядка миллиона рублей в месяц по оптовым ценам (я даже не беру прочие эксплуатационные расходы) и вы поймёте, что даже 10% экономия - это огромный успех! Небольшие кластеры - совсем не тот рынок, на котором стоит акцентировать своё внимание.
Zealint писал(а):
Либо изобретать принципиально другую архитектуру ЭВМ или даже другую математику.
Есть конкретные идеи?