OSDev http://osdev.su/ |
|
Беседа о создании новых архитектур для ЭВМ http://osdev.su/viewtopic.php?f=18&t=1024 |
Страница 3 из 5 |
Автор: | Yoda [ 01 дек 2014, 23:58 ] |
Заголовок сообщения: | Re: Беседа о создании новых архитектур для ЭВМ |
SII писал(а): Лично я вообще не вижу возможности создать универсальную архитектуру "на все случаи жизни". Думается, любая архитектура, подходящая для любых задач, будет более-менее одинаково плохо подходить для этих самых "любых задач". Тут я, пожалуй, не соглашусь, но это из категории тех идеологических разногласий, которые может разрешить только практика. SII писал(а): Проблемы создаются не самой абстрактной системой, а кучей бесполезных "свистоперделок", которыми набиты современные версии систем ... На самом деле, нужно иметь эффективную ОС, пожирающую минимум ресурсов и предоставляющую максимум реально полезного функционала, и на ней уже делать прикладные программы. Удивительная степень совпадения взглядов на эту тему, доходящая порой до совпадения формулировок . |
Автор: | Yoda [ 02 дек 2014, 01:20 ] |
Заголовок сообщения: | Re: Беседа о создании новых архитектур для ЭВМ |
Zealint писал(а): Вот я и предлагаю задачи общего назначения (офис, видеопроигрыватель) решать на обычном процессоре, а специфические задачи - на специальном дополнительно модуле. То есть когда появляется новая сложная задача, требующая новой архитектуры, мы делаем не весь процессор, а только модуль к нему. Давайте так порассуждаем. Моё [сильное] утверждение состоит в том, что [почти] все рассматриваемые вами задачи на самом деле не требуют специализированной архитектуры и могут быть эффективно реализованы на ЦП общего применения (не обязательно существующих, к ним у меня тоже серьёзные претензии). Предлагаю взять любую задачу и детально проанализировать её. Zealint писал(а): Автоматическое распараллеливание никогда не было и не будет эффективнее ручного, поскольку в ручном можно переписать алгоритм, заведомо заложив в него возможность работать параллельно. Поэтому в моей концепции модули будущей СКА уже будут спроектированы как параллельные, поэтому пользователь, вызывая функции СКА, сразу будет получать параллельную реализацию. ОС же должна грамотно раскидывать уже параллельные модули по нужному числу ядер. То есть в моём понимании задача автоматического распараллеливания должна сводиться к тому, как уже параллельные модули программы грамотно распределить по всей системе: кому-то вот эти 10 ядер, а кому-то вот эти 20 и т. д. Ааа, вон оно что. Я полагал, у вас есть идея распараллеливания алгоритмов, а не процессов по ядрам. По моей практике, только ручное распараллеливание алгоритма даёт хороший результат. Zealint писал(а): В моей практике есть случаи, когда замена алгоритма позволяла увеличить эффективность распараллеливания на десятки тысяч процентов. Отличный результат! |
Автор: | Zealint [ 02 дек 2014, 18:32 ] |
Заголовок сообщения: | Re: Беседа о создании новых архитектур для ЭВМ |
Yoda, Спасибо за столь подробное описание своего видения моих проблем и свою поучительную историю. Приятно, что есть в некоторой степени общее понимание ситуации. В целом, всё понятно, однако некоторые Ваши замечания мне кажутся не до конца аргументированными по отношению ко мне. Вы пишите, что не будет выигрыша от уменьшения числа операций в архитектуре. Я неявно предполагал, что уменьшение числа операций как раз позволит освободить место и сделать больше регистров, больше схем для независимых арифметических действий. Представьте, что если убрать весь мусор из x86, то на уровне микроархитектуры в тот же объём, наверное, можно будет всунуть ещё пару десятков регистров, увеличить кэш в разы и тогда одна из самых частых операций в моих программах (сумма чисел) будет работать быстрее именно за счёт того, что очень много регистров будут складываться параллельно. Не совсем понятно замечание по поводу модулярной арифметики. Если мы объединим в одну инструкцию сложение и взятие остатка, то разве не уменьшит это размер самой операции? Разве не станет от этого более эффективно работать кэш команд? И разве не сможет процессор исполнять больше таких независимых команд за одно действие? Я помню Вашу оговорку, что здесь есть смысл только когда количество таких операций большое и находятся не в цикле, иначе ясно, что кэш сразу возьмёт весь цикл и всё влезет. Но есть практика разворачивания циклов. Например, 4 операции в цикле, разворачиваем раза 4, получаем уже 16. В некоторых задачах удаётся разворачивать 8 раз. Хотелось бы и больше, но регистров не хватает, а обращаться к памяти внутри самого жёсткого цикла – это значит убить смысл разворачивания цикла. Да, я знаю, что разворачивать 100 раз нет смысла, но золотую середину можно сдвинуть гораздо дальше её нынешнего положения, если уменьшить размер инструкции и увеличить число регистров. По поводу генератора простых чисел там не описка. Чтобы выполнить расчёты по модулю, нужны, как правило, простые числа (иногда хватает более слабых ограничений – попарно взаимно простых чисел, но простые более удобны по ряду причин). Почему бы не генерировать их аппаратно? Там я говорил про то, чтобы увеличить размер регистра. Для регистра в 128 бит, например, сгенерировать простое число, затем получить следующее за ним или предыдущее – очень удобно. Как правило, вычисления начинают от максимального большого простого числа, умещающегося в регистр, а затем берут предыдущее, снова предыдущее и т. д., пока число модулей не окажется достаточным. В моих задачах было до десяти тысяч простых чисел. Здесь уже смысл не в скорости, а в удобстве. Программно-то генерируются они и так мгновенно. Мне почему-то этот стереотип по поводу быстроты аппаратной реализации над программной не кажется столь уж необоснованным. Я вижу это так, действуя по аналогии. Допустим, мы программируем алгоритм, состоящий из нескольких независимых операций А, Б и С. И вдруг оказывается, что у них есть что-то общее (хотя бы даже взятие операторов из памяти), мы это общее «выносим за скобки» - и упрощаем набор действий. Теперь, допустим, есть электронная схема, «зашитая» в процессор. Допустим, есть операции А и Б. Есть отдельная схема для А, есть отдельная схема для Б. Вот, мы решили, что нам нужна операция АБ (сумма + взятие остатка, например). Разве у них совсем нет общих элементов на уровне микроархитектуры? Я не знаю, как в процессоре устроены эти операции, но разве нельзя, посмотрев на схемы внимательно, объединить их в одну? С точки зрения математики, я не вижу такого способа, а с точки зрения электроники? Например, после операции сложения, не помещать промежуточные данные в регистр, чтобы потом вызвать операцию взятия по модулю для этого регистра, а сразу подсоединить выводы сумматора к блоку взятия модуля? Если бы я разбирался в этих схемах, то, может, нашёл бы возможность что-нибудь там упростить при таком объединении двух операций. Знаете, всё-таки я не верю, что эти операции совсем-совсем разные, что у них нет ничего общего. Мой второй аргумент в пользу объединения операций в одну состоит в следующем. Допустим, мы хотим сложить два числа, размером 64 бита. Мы можем вызвать одну команду add на 64-битовыми регистрами, а можем две add / adc над 32-битовыми. Первый способ будет быстрее, но второй, который, как Вы говорите, является комбинацией уже реализованных блоков, будет всё-таки медленнее. Ещё не до конца ясен момент с размером регистров. Я не понял, каков предел размера регистра для суммы и для умножения (они ведь должны быть разными). С какого размера операция сложения начинает тормозить? А умножения и деления? Здесь тоже есть аналогия с параллельными алгоритмами: часто при сильном увеличении числа ядер алгоритм начинает тормозить из-за квадратичного роста побочных эффектов взаимодействия, потому часто алгоритмист пытается разбить алгоритм на как можно большее число независимых кусочков (пусть даже теряя эффективность алгоритма), так как сумма квадратов меньше чем квадрат суммы (для положительных чисел). Аналогично, операция умножения может иметь квадратичный рост по числу бит. Но можно, например, выполнить один-два шага метода Карацубы, когда оба регистра разбиваются пополам, далее вместо 4-х умножений и сложений этих половинок выполняется только 3 умножения и чуть больше сложений/вычитаний. И вместо квадратичного роста (n^2) мы получаем n^(log_2(3)). То есть вместо квадратичного роста получаем значительно более медленный, что может позволить отодвинуть «тормоза» умножения подальше. Я понимаю, что Вы имеете в виду, когда говорите, что мой ПМ (процессорный модуль) будет медленно взаимодействовать с ЦП, ведь они будут передавать друг другу данные по медленной шине. Но я предполагаю, что есть способ как-то «близко» подключить ПМ к ЦП, чтобы взаимодействие стало быстрым. Или это невозможно никак? Насколько я понимаю, раньше кэш L3 на многих процессорах был на отдельном кристалле, но он же не тормозил из-за этого. Или я не о том думаю? Далее буду цитировать. Цитата: Компромисс может заключаться в том, что компиляция сейчас - довольно быстрый процесс, а интеграцией компиляции и интерпретации является работа с командной строки, - командный процессор является интерпретатором, но запускает скомпилированную программу. Собственно, я это и сказал : ) Цитата: То, что вы сейчас написали, в общем-то и является отличительными чертами хорошей ОС, а никак не отсутствия ОС.< . . . >. Другое дело, что настольные ОС больше ориентированы на обилие свистоперделок, а не на HPC (high performance computing). Я могу согласиться. Однако вот Вы сами пишите, что современные ОС не ориентированы на HPC. Вот я и думаю, почему бы не сделать сразу ОС и СКА одновременно, чтобы СКА была бы неотъемлемой частью ОС и диктовала бы её развитие. Развивая СКА, мы будем вынуждены развивать ОС, подчиняя её развитие потребностям HCP. Это не обязательно значит, что СКА будет зашита в ОС, а это значит, что развиваться они будут «когерентно». А если я возьму чью-то готовую систему, то кто мне даст гарантии, что наши пути не станут настолько ортогональным, что сила нашего взаимодействия будет разрывать точку её приложения на части? Либо систему должен разрабатывать профессиональный учёный. Что-то такое можно было наблюдать в ОС/2, как мне сказали современники тех событий. Цитата: Судя по конфигурации, 80-ядерный кластер не первой свежести. Я могу сказать, что выбор конфигурации - ответственный момент и стоит его учитывать до запуска расчётов. Да, свежесть была не первой. Но я и сам удивился, ведь наш «научный» центр заказал этот кластер в 2009 году. Сказать, что уже тогда это было ведро с гвоздями – это ничего не сказать. Более того, недавно, буквально год-два назад, наш университет тоже купил ведро с гвоздями, причём подержанное из 90-х! И, что самое безответственное с их стороны, они даже не проконсультировались со мной, как с единственным на тот момент человеком, который мог бы что-то подсказать из своего опыта, хотя именно мою команду собирались на этот кластер посадить. Потом меня выбросили, а ведро с гвоздями теперь ржавеет. Я пытался понять, зачем его купили, и выяснил, что оказывается, в рейтинге вузов есть такой пункт «наличие кластера». Вот руководство и решило выполнить этот пункт. Бестолочи : ) Цитата: Как, например, поступать в следующей ситуации: мы одной инструкцией складываем два миллионобитных числа и вдруг оказывается, что последняя тысяча бит отсвоплена на диск? Откатывать миллион бит обратно и выкидывать промежуточные результаты? А где хранить почти миллион бит промежуточного результата, если есть вероятность отката операции? Останавливать процессорное ядро, пока другое ядро занимается вводом-выводом? А если во втором ядре при этом тоже случился page fault? В общем, поверьте, предполагаемая гибкость порождает больше проблем, нежели сулит выгоды. Такой ситуации не может быть, если у нас миллионбитные регистры, значит они сначала полностью загружаются слагаемыми, а затем складываются без проблем. Кроме того, я никогда не пишу программы, которые уходят в своп, вернее, пишу, но стараюсь, чтобы так не происходило. Мне проще получить ошибку «нет памяти» с потерей всех промежуточных данных, что были в ОЗУ, чем останавливать процесс самому. Сама концепция свопа мне как-то не очень нравится. Нужна возможность выделять память так, чтобы помечать её как запрещённую к сбросу на диск и пусть лучше ОС даёт отказ в выделении памяти в таких случаях. В моих задачах своп был всегда равносилен потере времени, так как в этом случае, если программа и так считает месяц, увеличивать это время раз в 40 нет возможности. По поводу гибкости я могу согласиться. «Резиновый» регистр заводить не обязательно и даже слишком большой тоже, но хотелось бы иметь что-то побольше, чем 64 бита. Цитата: А вам продавец в ответ - а какая частота шины? а в каком корпусе нужен модуль, LGA1234 или LBGA4321? А на какое напряжение питания? А для какого поколения ЦП? С вас 3000$ (по тыще за каждый модуль). А когда вы приходите домой, то оказывается, что они не совместимы с вашей материнской платой (хотя исправны) и возврату не подлежат как "технически сложные изделия", тогда вы бежите искать совместимую материнку . Нет уж, увольте, никаких модулей IMHO быть не должно. Надо делать ЦП изначально таким, чтобы задачи любого класса работали на нём хорошо. Но там я подразумевал, что вся архитектура вычислительной машины будет выполнена по единому стандарту, то есть нужно делать что-то одно, что всегда со всем совместимо. Кроме того, я предполагал, что стоимость их не будет уж слишком высокой. Допустим, Вы против модулей, а имеет ли смысл создавать тогда мощный процессор, в котором есть «научный сопроцессор», содержащий наборы базовых алгоритмов математики, если эти алгоритмы удастся реализовать более эффективно, чем программно? Цитата: Берём отладочную карту с мощным FPGA и PCI-E слотом, устанавливаем в комп и программируем наши функции непосредственно в железе. Можете ли Вы подробнее описать этот процесс? Где берём и что конкретно делать? Какую дисциплину для повышения квалификации изучать? Цитата: Цитата: Неплохо было бы иметь строковые команды (префикс rep в x86), которые бегут по двум массивам чисел и складывают их с переносом. Так это уже есть. Правда? Я гляну в руководство по командам. Не знал, что rep можно использовать в таких случаях. Цитата: Вы совсем не правы. 2-3 докторские диссертации - мизерная плата за такую важную работу. Подумайте, например, о том, что счёт за электроэнергию для суперкомпьютера "Ломоносов" составляет порядка миллиона рублей в месяц по оптовым ценам (я даже не беру прочие эксплуатационные расходы) и вы поймёте, что даже 10% экономия - это огромный успех! Небольшие кластеры - совсем не тот рынок, на котором стоит акцентировать своё внимание. Это вопрос дискуссионный. Дело в том, что более оптимальная программа в нашей научной среде как раз может сожрать ещё больше электроэнергии, и вот почему. Допустим, неопытный исследователь написал программу, которая вычисляет число расстановок N не бьющих друг друга ферзей на доске NxN (последовательность OEIS:A000170) и она с горем пополам работает для N=20 на домашней машине. Исследователь погонял-погонял её неделю на кластере, дошёл, быть может, до N=21 или N=22 и сказал «хватит», пошёл писать магистерскую диссертацию. Более опытный исследователь сделает что-то похожее, тоже погоняет для N=21,22, затем найдет слабое место, перепишет код, будет гонять для N=23,24, устраивая баню в подвале, где стоит «Ломоносов», затем в силу своих способностей разработает алгоритм для N=25,26 (это уже докторская, без шуток), загрузит кластер на полгода (примерно столько и понадобилось для решения этой задачи, правда, на видеокартах, но не суть). В результате, выходит, что способность разрабатывать более эффективные алгоритмы приводит к тому, что электричества тратится гораздо больше : ) Даже экономия на 10% приведёт к тому, что просто будет решаться больше задач в единицу времени, а энергии будет столько же. Я знаю одну принципиальную схему экономии электроэнергии, которая никогда не будет воплощена руководством ни одного кластера какого-либо российского университета. Схема очень простая и состоит всего лишь из двух пунктов. Руководству следует:
Цитата: Цитата: Либо изобретать принципиально другую архитектуру ЭВМ или даже другую математику. Есть конкретные идеи? Нет вообще. Но есть некоторая критика. Современная математика не всегда хорошо подходит для некоторых задач. Не хватает каких-то её расширений на те области, которыми я занимался. Там почти ни одна задача не может быть по-человечески решена математическими методами. Могу привести пример, в котором на протяжении лет 40 вроде бы считалось, что задача решена, однако впоследствии были показаны две причины, по которым полученная формула, читать и понимать которую довольно трудно, оказалась неподходящей для правильных выводов и давала неправильную асимптотику. Одна причина была показана из физических соображений лет 15 назад, а вторая, более «математичная», – в моей диссертации (в одной из глав). Но не знаю, надо ли печатать здесь эту чудовищную штуковину из многократный интегралов, которую вряд ли кто-то будет серьёзно разбирать : ) А так, идей нет, как можно расширить математику на те случаи, когда не существует никаких способов записать аналитическую формулу правильно. Цитата: Давайте так порассуждаем. Моё [сильное] утверждение состоит в том, что [почти] все рассматриваемые вами задачи на самом деле не требуют специализированной архитектуры и могут быть эффективно реализованы на ЦП общего применения (не обязательно существующих, к ним у меня тоже серьёзные претензии). Предлагаю взять любую задачу и детально проанализировать её. Так видите ли, в чём дело, я согласен, что решить можно эффективно, но вопрос в том, что подразумевать под эффективностью. Я просто уверен, что если бы, с кажем, в процессоре было бы раз в 10 больше регистров и сумматоров, было бы ещё эффективнее. А если бы (если) аппаратная реализация суммы по модулю оказалась быстрее пары команд, то эффективность возросла бы ещё. Не обязательно брать мою задачу, чтобы получился пример. Возьмите задачу подсчёта числа единичных бит в байте, слове, двойном слове и т. д. Эта процедура распадается на несколько более простых базовых команд. Однако же в SSE 4.2 всё-таки затем ввели аппаратную инструкцию, которая выполняет данное действие. Вряд ли они ввели бы её, не будь она более эффективной. Цитата: Ааа, вон оно что. Я полагал, у вас есть идея распараллеливания алгоритмов, а не процессов по ядрам. По моей практике, только ручное распараллеливание алгоритма даёт хороший результат. Да, но и тут не всё так просто, как может показаться сначала. Допустим, пользователь ввёл команду, которая распадается на ряд других команд. Причём для каждой из них известно, на скольких ядрах она эффективно работает (кто-то только на 2, кто-то на 200). Задача в том, чтобы правильно распределить команды по ядрам, чтобы самая медленная программа выполнилась бы как можно быстрее. Причём некоторые команды могут хорошо исполняться только на одном узле кластера (процессоры близко), а некоторые другие могут исполняться хоть в разных странах. Особенно трудно что-то сказать, когда нельзя однозначно определить заранее время работы команды. Тут нужны какие-то эвристики и какой-то способ запоминания. Система запоминает, как долго та или иная команда с теми или иными параметрами работает на том или ином числе ядер и как как бы обучается, чтобы в следующий раз эту информацию использовать. Это не совсем самообучающийся ИИ, а просто таблица данных для задачи сетевого планирования, чем полнее таблица, тем более оптимальным будет план. Других идей пока нет. |
Автор: | Zealint [ 02 дек 2014, 18:41 ] |
Заголовок сообщения: | Re: Беседа о создании новых архитектур для ЭВМ |
Himik писал(а): Ну при чём здесь GCC, он ведь работает только во время компиляции. Так а кто будет компилировать мою СКА? Цитата: И что за мощные сервера такие, что на GCC не хватает памяти, требуется всего 256МБ. Не сервера мощные, а программы такие. Есть программы, пытаясь скомпилировать которые GCC сжирала 4 Гб оперативки, уходила в своп и там тихо умирала. Программы очень сложные: там были циклы, вложенные друг в друга до 6 раз, внутри которых несколько тысяч строк сложных инструкций, каждая из которых состояла из полутора десятков умножений. Цитата: 2. Я полагаю, гарантии качества вам могут дать только производители ОС. Казалось бы, гарантии качества того же Maple, должны давать разработчики Maplesoft. Однако, сколько бы раз я не заходил на сайт ошибок Maple, их там как было пять с половиной тысяч, так и осталось. Аналогично, я с трудом поверю, что разработчики ОС, которые ещё дальше от науки, будут поддерживать нужное именно мне качество. Я могу ошибаться, потому и продолжаю искать. |
Автор: | pavia [ 02 дек 2014, 23:52 ] |
Заголовок сообщения: | Re: Беседа о создании новых архитектур для ЭВМ |
Цитата: Мне почему-то этот стереотип по поводу быстроты аппаратной реализации над программной не кажется столь уж необоснованным. Я вижу это так, действуя по аналогии. Допустим, мы программируем алгоритм, состоящий из нескольких независимых операций А, Б и С. И вдруг оказывается, что у них есть что-то общее (хотя бы даже взятие операторов из памяти), мы это общее «выносим за скобки» - и упрощаем набор действий. Теперь, допустим, есть электронная схема, «зашитая» в процессор. Допустим, есть операции А и Б. Есть отдельная схема для А, есть отдельная схема для Б. Вот, мы решили, что нам нужна операция АБ (сумма + взятие остатка, например). Разве у них совсем нет общих элементов на уровне микроархитектуры? Я не знаю, как в процессоре устроены эти операции, но разве нельзя, посмотрев на схемы внимательно, объединить их в одну? С точки зрения математики, я не вижу такого способа, а с точки зрения электроники? Например, после операции сложения, не помещать промежуточные данные в регистр, чтобы потом вызвать операцию взятия по модулю для этого регистра, а сразу подсоединить выводы сумматора к блоку взятия модуля? Если бы я разбирался в этих схемах, то, может, нашёл бы возможность что-нибудь там упростить при таком объединении двух операций. Знаете, всё-таки я не верю, что эти операции совсем-совсем разные, что у них нет ничего общего. Мой второй аргумент в пользу объединения операций в одну состоит в следующем. Допустим, мы хотим сложить два числа, размером 64 бита. Мы можем вызвать одну команду add на 64-битовыми регистрами, а можем две add / adc над 32-битовыми. Первый способ будет быстрее, но второй, который, как Вы говорите, является комбинацией уже реализованных блоков, будет всё-таки медленнее. Объединить можно, но согласно математики |A+B|<=|A|+|B| Т.е если вы объедините то не факт что скорость повысится. Во вторых операции зависимые. Поэтому вычисления второй части будут по завершению первой. ||A|+B|<=|A|+|B| Так что ускорения получить трудно. В третьих вычисления не идут мгновенно. Всякие электрические элементы обладают емкостью. Т.е имеет задержку срабатывания подобно конденсатору. Для единичного транзистора при своевременных технологиях можете считать 300 ГГц. Теперь возьмем And-Or-Xor, Not - уже около 100 ГГц а потом возьмем сложение. Допустим это сумматор допустим тривиальный алгоритм с переносом. В таком сумматоре задержка распростроняется от разряда к разряду и требуется 2 логических операции для вычисления. Для регистра в 32 имеем частоту процессора 1.56 ГГц Для 64 соотвественно частота 0.78 ГГц для 128 ещё меньше. Конечно тривиальный алгоритм с переносом никто не использует а используют параллельные операции Для 64 бит имеем 6-8 ГГц* Плюс флаги надо вычислять и другие заморочки. А вот 128 бит регистры неудобны так как паралелить двойками нельзя только четвёрками. Это так на пальцах не судите строго если в цифрах ошибся не очень хорошо помню все схемы. Цитата: Я понимаю, что Вы имеете в виду, когда говорите, что мой ПМ (процессорный модуль) будет медленно взаимодействовать с ЦП, ведь они будут передавать друг другу данные по медленной шине. Но я предполагаю, что есть способ как-то «близко» подключить ПМ к ЦП, чтобы взаимодействие стало быстрым. Или это невозможно никак? Насколько я понимаю, раньше кэш L3 на многих процессорах был на отдельном кристалле, но он же не тормозил из-за этого. Или я не о том думаю? Про кэш. Помоему это-го не было. Про шины я уже говорил что надо делать кольцевую. Иначе вся система будет тормозить на Lock шины. Либо паралелить каналы как в PCI-E. Либо делить время. Всё уже продуманно. И тут трудно найти не оптимальные решения. Конечно в частных задачах можно поднять но немного. Короче говоря это системный вопрос. Вот частоту поднять можно, только тогда интерфейс обработки будет большим по площади кристалла. |
Автор: | Himik [ 03 дек 2014, 00:56 ] |
Заголовок сообщения: | Re: Беседа о создании новых архитектур для ЭВМ |
Zealint писал(а): Так а кто будет компилировать мою СКА? Ну допустим секретарша на своей пишущей машинке с 32ГБ памяти. Обязательно на сервере что ли? Ну а если серьёзно, программу лучше разбить на части, т.к. компиляторы на сложных конструкциях не могут эффективно распределять регистры под переменные. Распределите свои циклы по отдельным процедурам, а процедуры по отдельным файлам. Тогда каждый по отдельности скомпилируется на нескольких мегабайтах памяти и будет хорошо оптимизирован. |
Автор: | Yoda [ 03 дек 2014, 15:21 ] |
Заголовок сообщения: | Re: Беседа о создании новых архитектур для ЭВМ |
Zealint писал(а): Вы пишите, что не будет выигрыша от уменьшения числа операций в архитектуре. Я неявно предполагал, что уменьшение числа операций как раз позволит освободить место и сделать больше регистров, больше схем для независимых арифметических действий. Представьте, что если убрать весь мусор из x86, то на уровне микроархитектуры в тот же объём, наверное, можно будет всунуть ещё пару десятков регистров, увеличить кэш в разы и тогда одна из самых частых операций в моих программах (сумма чисел) будет работать быстрее именно за счёт того, что очень много регистров будут складываться параллельно. Мне кажется, вы тоже не поняли мою позицию. Я не утверждаю, что в x86 всё замечательно, это крайне неудачная архитектура. Я рассматриваю эффективность некоторой гипотетической архитектуры, пытаясь понять, какие действия должны кодироваться одной инструкцией, а для каких этого делать не стоит - вот ключевой момент моих рассуждений. Zealint писал(а): Не совсем понятно замечание по поводу модулярной арифметики. Если мы объединим в одну инструкцию сложение и взятие остатка, то разве не уменьшит это размер самой операции? Разве не станет от этого более эффективно работать кэш команд? И разве не сможет процессор исполнять больше таких независимых команд за одно действие? Если каждая из двух последовательных операций выполняется за большее время, чем выборка и декодирование инструкции, то объединение лишено большого смысла. Забота о кэше имеет смысл, если количество инструкции в коде достаточно значительно, скажем, больше 5% от объёма, превышающего размер кэша первого уровня. Обратная сторона медали кодирования всего и вся заключается в том, что кодовое пространство не резиновое и при добавлении новых инструкций возрастёт средняя длина кодов, что также негативно скажется на эффективности. Zealint писал(а): По поводу генератора простых чисел там не описка. Чтобы выполнить расчёты по модулю, нужны, как правило, простые числа (иногда хватает более слабых ограничений – попарно взаимно простых чисел, но простые более удобны по ряду причин). Почему бы не генерировать их аппаратно? Как вы себе это представляете? Zealint писал(а): Там я говорил про то, чтобы увеличить размер регистра. Для регистра в 128 бит... Основным способом увеличения разрядности в процессорах является поддержка векторных операций. Этот способ позволяет эффективно реализовать арифметику с неограниченной разрядностью без использования специализированных инструкций. Zealint писал(а): В моих задачах было до десяти тысяч простых чисел. Здесь уже смысл не в скорости, а в удобстве. Программно-то генерируются они и так мгновенно. Вот видите, если они и так нормально генерируются программно, то какой смысл в аппаратной реализации? Удобство - это не тот фактор, который нужно рассматривать в данном случае. Тем более, я до сих пор не понимаю, каким образом их можно было бы генерировать аппаратно. Zealint писал(а): Допустим, мы программируем алгоритм, состоящий из нескольких независимых операций А, Б и С. И вдруг оказывается, что у них есть что-то общее (хотя бы даже взятие операторов из памяти), мы это общее «выносим за скобки» - и упрощаем набор действий. Теперь, допустим, есть электронная схема, «зашитая» в процессор. Допустим, есть операции А и Б. Есть отдельная схема для А, есть отдельная схема для Б. Вот, мы решили, что нам нужна операция АБ (сумма + взятие остатка, например). Разве у них совсем нет общих элементов на уровне микроархитектуры? Создание архитектуры - это тщательный анализ каждой операции, понимание, откуда берутся задержки и поиск разумных компромиссов. В приведённом выше примере вынесение за скобки - это помещение операнда из памяти в регистр, т.к. регистр - это самый эффективно кодируемый и самый быстрый вид памяти. Смысл регистра заключается в том, чтобы разбить операцию на такие фрагменты, что задержки в получении/сохранении операнда становятся малыми по сравнению с выполнением самой операции. Сумма плюс взятие остатка с сохранением промежуточного результата в регистр не будет сильно медленней, чем с сохранением в другой регистр, не заданный в коде операции. А сохранение в любом случае потребуется. Zealint писал(а): Я не знаю, как в процессоре устроены эти операции, но разве нельзя, посмотрев на схемы внимательно, объединить их в одну? С точки зрения математики, я не вижу такого способа, а с точки зрения электроники? Вся электроника основана на математике. Она не способна творить чудеса, опровергая математические законы. Zealint писал(а): Например, после операции сложения, не помещать промежуточные данные в регистр, чтобы потом вызвать операцию взятия по модулю для этого регистра, а сразу подсоединить выводы сумматора к блоку взятия модуля? Синхронизация работы двух блоков по-любому требует наличия регистра между ними. Zealint писал(а): Допустим, мы хотим сложить два числа, размером 64 бита. Мы можем вызвать одну команду add на 64-битовыми регистрами, а можем две add / adc над 32-битовыми. Первый способ будет быстрее, но второй, который, как Вы говорите, является комбинацией уже реализованных блоков, будет всё-таки медленнее. Нет, посмотрите внимательней, там стоит "или" (...или параллельное выполнение однородных операций). В данном случае сумматоры выполняют однородные действия, что достаточно эффективно кодируется в векторной арифметике. Zealint писал(а): Ещё не до конца ясен момент с размером регистров. Я не понял, каков предел размера регистра для суммы и для умножения (они ведь должны быть разными). С какого размера операция сложения начинает тормозить? А умножения и деления? Сложение начинает тормозить с возникновением переносов. При отсутствии переносов с пропускной спосбностью памяти. Умножение и деление начинают тормозить сразу же. Zealint писал(а): Здесь тоже есть аналогия с параллельными алгоритмами: часто при сильном увеличении числа ядер алгоритм начинает тормозить из-за квадратичного роста побочных эффектов взаимодействия, потому часто алгоритмист пытается разбить алгоритм на как можно большее число независимых кусочков (пусть даже теряя эффективность алгоритма), так как сумма квадратов меньше чем квадрат суммы (для положительных чисел). Аналогично, операция умножения может иметь квадратичный рост по числу бит. Но можно, например, выполнить один-два шага метода Карацубы, когда оба регистра разбиваются пополам, далее вместо 4-х умножений и сложений этих половинок выполняется только 3 умножения и чуть больше сложений/вычитаний. И вместо квадратичного роста (n^2) мы получаем n^(log_2(3)). То есть вместо квадратичного роста получаем значительно более медленный, что может позволить отодвинуть «тормоза» умножения подальше. Ага, а для ещё больших чисел применим алгоритм Тоома-Кука, а для гигантских - алгоритм Фюрера. Только смотрите, какие дела, все эти алгоритмы не являются истинно параллельными, они все основаны на разбиении процедуры умножения на последовательные шаги в которых параллельно выполняются базовые операции, т.е. векторная машина выполнит их практически столь же эффективно, как и 100% аппаратная реализация, только добавьте к аппаратной реализации практическую невозможность работы с "резиновыми" операндами. Zealint писал(а): Я понимаю, что Вы имеете в виду, когда говорите, что мой ПМ (процессорный модуль) будет медленно взаимодействовать с ЦП, ведь они будут передавать друг другу данные по медленной шине. Но я предполагаю, что есть способ как-то «близко» подключить ПМ к ЦП, чтобы взаимодействие стало быстрым. Или это невозможно никак? Насколько я понимаю, раньше кэш L3 на многих процессорах был на отдельном кристалле, но он же не тормозил из-за этого. Или я не о том думаю? Локальность означает максимальную близость к функциональному блоку даже в пределах одного кристалла! Посмотрите - на процессорах все три уровня кэш-памяти находятся на одной микросхеме, но значительно отличаются по объёму и по скорости. Почему нельзя было сделать кэш-память третьего уровня столь же быстрой, как и первого уровня? Потому что размер мешает. Чем больше размер, тем больше площадь. Больше площадь - дальше от функционального блока. А чем дальше, тем больше задержки распространения сигнала. Что-то, находящееся физически за пределами ЦП вы не сделаете более быстродействующим, чем кэш третьего уровня, а это десятки тактов задержки на каждую операцию. Отсюда, кстати, напрямую следует, что вы не сделаете быстрый миллионобитный регистр, он будет работать крайне медленно. Zealint писал(а): Однако вот Вы сами пишите, что современные ОС не ориентированы на HPC. Вот я и думаю, почему бы не сделать сразу ОС и СКА одновременно, чтобы СКА была бы неотъемлемой частью ОС и диктовала бы её развитие. Просто по той причине, что они выполняют совершенно разные функции. Нужно не объединение ОС и СКА, а создание ОС, подходящей под нужды СКА. Zealint писал(а): Такой ситуации не может быть, если у нас миллионбитные регистры, значит они сначала полностью загружаются слагаемыми, а затем складываются без проблем. Регистр - это вид памяти. Миллионобитный регистр по быстродействию примерно сравнится с кэш-памятью второго-третьего уровня. Значит, если брать операнды из памяти и они попадут в кэш-память соответствующих уровней, то скорость работы будет примерно такой же. А значит регистры таких больших размеров лишены всякого смысла. Zealint писал(а): Кроме того, я никогда не пишу программы, которые уходят в своп, вернее, пишу, но стараюсь, чтобы так не происходило. Мне проще получить ошибку «нет памяти» с потерей всех промежуточных данных, что были в ОЗУ, чем останавливать процесс самому. Сама концепция свопа мне как-то не очень нравится. Вы не поняли важного момента. Своп - это только частный случай, я бы вообще запретил свопирование на диск, как источник невероятных тормозов. Page fault в общем случае не привязан к свопированию. Основной источник PF - промах при записи в страницу, которая выделена приложению логически, но ещё не выделена физически. Zealint писал(а): По поводу гибкости я могу согласиться. «Резиновый» регистр заводить не обязательно и даже слишком большой тоже, но хотелось бы иметь что-то побольше, чем 64 бита. Да. И это "больше, чем 64 бита" - векторные регистры, т.е. группы операндов, над которыми за один машинный цикл можно одновременно выполнять одинаковые операции. Zealint писал(а): Но там я подразумевал, что вся архитектура вычислительной машины будет выполнена по единому стандарту, то есть нужно делать что-то одно, что всегда со всем совместимо. Кроме того, я предполагал, что стоимость их не будет уж слишком высокой. Вот для этого и стоит использовать уже существующую высоко стандартизированную шину - PCI-E. Zealint писал(а): Допустим, Вы против модулей, а имеет ли смысл создавать тогда мощный процессор, в котором есть «научный сопроцессор», содержащий наборы базовых алгоритмов математики, если эти алгоритмы удастся реализовать более эффективно, чем программно? Ключевой момент - если эти алгоритмы удастся реализовать более эффективно, чем программно. Поскольку я полагаю, таких алгоритмов практически нет, то не вижу смысла в создании "научного сопроцессора", а точнее, любой ЦП должен изначально быть "научным". Более того, я не вижу разницы между научными приложениями и пользовательскими. Разница только в целях использования, но не в применяемых методах. Например, криптография с открытым ключом также базируется на операциях с большими числами (тысячи бит) и модульной арифметике, но вполне себе пользовательская. Zealint писал(а): Цитата: Берём отладочную карту с мощным FPGA и PCI-E слотом, устанавливаем в комп и программируем наши функции непосредственно в железе. Можете ли Вы подробнее описать этот процесс? Где берём и что конкретно делать? Какую дисциплину для повышения квалификации изучать? Честно говоря, это весьма серьёзная во всех отношениях тема. Затраты времени на погружение в тему могут составить от нескольких месяцев до года и больше, затраты по деньгам выльются в десятки и соти тысяч рублей (если речь идёт о серьёзном изделии). Тем не менее, я действительно знаю предельно дешёвый способ изучить тему, как в теории, так и на практике. 1. Сначала посмотрите в википедии материалы на тему FPGA (ПЛИС), языки HDL (основные - Verilog и VHDL). Цифровые цепи по старинке, рисуя логические элементы ручками и соединяя их проводами, сейчас уже не делают, хотя это возможно. Вместо этого используют языки описания схемы (HDL). 2. Изучите один из основных языков (или оба) - Verilog и VHDL. Я после знакомства с ними остановился на Verilog, доступный учебник, например, здесь - http://irs.nntu.ru/globals/files/bukvarev/verilog.pdf. По VHDL лучше проконсультирует SII. 3. Дальше можно написать что-нибудь на верилоге и смоделировать без использования реальной ПЛИС, это делается при помощи программных симуляторов, например, Icarus Verilog. Этот симулятор работает как под виндой, так и под линуксом. Однако, следует быть осторожным, - программный симулятор позволяет сделать почти всё, что душе угодно, включая физически нереализуемые схемы. Реальные компиляторы накладывают массу ограничений. 4. Если в тему вникли, покупаем настоящую ПЛИС и реализуем первые цифровые цепи, действительно работающие 100% аппаратно. Самая доступная (но при этом далеко не самая плохая) плата - DE0-Nano. Их продают, например, в Чипе-и-Дипе, но дорого, по 7540 рублей. На eBay их можно купить примерно по 70$. Возможности DE0-Nano достаточны, чтобы на ней реализовать процессор уровня ARM или лучше. Недостатком является небольшая скорость, скажем, процессор будет работать на частоте около 50МГц (реальная величина зависит от вашего проекта). 5. Если вы сделали простой процессор на DE0-Nano, то без сомнения, будете настолько погружены в тему, что дальнейший путь вы сможете определять самостоятельно. Zealint писал(а): Цитата: Цитата: Неплохо было бы иметь строковые команды (префикс rep в x86), которые бегут по двум массивам чисел и складывают их с переносом. Так это уже есть. Правда? Я гляну в руководство по командам. Не знал, что rep можно использовать в таких случаях. Простите, невнимательно прочёл. Нет, префиксы нельзя использовать с операциями сложения, только со строковыми операциями. Zealint писал(а): Это вопрос дискуссионный. Дело в том, что более оптимальная программа в нашей научной среде как раз может сожрать ещё больше электроэнергии, и вот почему. Допустим, неопытный исследователь написал программу, которая вычисляет число расстановок N не бьющих друг друга ферзей на доске NxN (последовательность OEIS:A000170) и она с горем пополам работает для N=20 на домашней машине. Исследователь погонял-погонял её неделю на кластере, дошёл, быть может, до N=21 или N=22 и сказал «хватит», пошёл писать магистерскую диссертацию. Более опытный исследователь сделает что-то похожее, тоже погоняет для N=21,22, затем найдет слабое место, перепишет код, будет гонять для N=23,24, устраивая баню в подвале, где стоит «Ломоносов», затем в силу своих способностей разработает алгоритм для N=25,26 (это уже докторская, без шуток), загрузит кластер на полгода (примерно столько и понадобилось для решения этой задачи, правда, на видеокартах, но не суть). В результате, выходит, что способность разрабатывать более эффективные алгоритмы приводит к тому, что электричества тратится гораздо больше Я говорю не про докторскую на тему решения задачи ферзей для новых N, а про докторские на тему, как для того же N найти более оптимальный алгоритм. Первый случай - экстенсивный, он интереса не представляет, хотя на кандидатскую, может и потянет. Zealint писал(а): Даже экономия на 10% приведёт к тому, что просто будет решаться больше задач в единицу времени, а энергии будет столько же. Нет, не так. Задача может быть либо решена, либо не решена. Если она решена, то затраты составят на 10% меньше. Если возможности компьютера возрасли настолько, что стало возможным решить другую задачу, то это - тоже победа. Ломоносов сейчас перегружен, там очередь задач практически не опускается ниже двух сотен. Zealint писал(а): Я знаю одну принципиальную схему экономии электроэнергии... * перестать заниматься фаллометрией... Я тоже полагал, что наши академические СК нужны только для прикладой фаллометрии. Меня убедили, что я ошибаюсь и бОльшая часть задач имеет прямое практическое значение. Другими словами, чтобы влезть в очередь из 200 задач нужно убедить, что твоя там не будет лишней. В конце концов, научные задачи - тоже задачи, и хорошо, если они решаются. Другое дело, что конечно же их надо решать правильно, именно здесь и нужны правильные языки высокого уровня, библиотеки и СКА. А аспиранты и доктора просто не могут быть специалистами во всех областях, поэтому вынуждены пользоваться тем, что есть, и решать задачи так, как умеют. Если кто-то сумел при помощи ПК забить СК, что ж, трижды хвала ему. Zealint писал(а): Цитата: Цитата: Либо изобретать принципиально другую архитектуру ЭВМ или даже другую математику. Есть конкретные идеи? Нет вообще. Но есть некоторая критика. Критиковать - просто. Но если не существует способа решения, критика бесполезна. Zealint писал(а): Современная математика не всегда хорошо подходит для некоторых задач. Не хватает каких-то её расширений на те области, которыми я занимался. Там почти ни одна задача не может быть по-человечески решена математическими методами... ...а значит, как следствие, и компьютерными методами, поскольку работа компьютера целиком основана на математике. Zealint писал(а): Так видите ли, в чём дело, я согласен, что решить можно эффективно, но вопрос в том, что подразумевать под эффективностью. Я просто уверен, что если бы, с кажем, в процессоре было бы раз в 10 больше регистров и сумматоров, было бы ещё эффективнее. 10 сумматоров - пожалуйста, это векторные расчёты. 10 регистров - тоже. Но вот 100 регистров уже будут медленней 10, миллион будут в 10 раз медленней, а миллиарды - в 100 раз. Это и есть "иерархия памяти", и её центральная проблема - чем больше, тем медленней. Zealint писал(а): А если бы (если) аппаратная реализация суммы по модулю оказалась быстрее пары команд, то эффективность возросла бы ещё. Так суть в том, что быстрей не оказывается и на то есть веские причины. Zealint писал(а): Не обязательно брать мою задачу, чтобы получился пример. Возьмите задачу подсчёта числа единичных бит в байте, слове, двойном слове и т. д. Эта процедура распадается на несколько более простых базовых команд. Однако же в SSE 4.2 всё-таки затем ввели аппаратную инструкцию, которая выполняет данное действие. Вряд ли они ввели бы её, не будь она более эффективной. Правильно! И это - хороший пример того, когда аппаратная реализация имеет смысл в рамках данной архитектуры, т.к. операция по сути хорошо параллелизуема, но любая программная реализация на этом процессоре будет работать последовательно, т.е. в цикле. Однако, подсчёт числа единичных бит по сути своей является векторной операцией, представляющей собой свёртку - сумму массива. Ничего специфического касательно математики в данной операции нет, она довольно часто используется и в другой [векторной] архитектуре могла бы быть реализована без использования специальной инструкции. Zealint писал(а): Не сервера мощные, а программы такие. Есть программы, пытаясь скомпилировать которые GCC сжирала 4 Гб оперативки, уходила в своп и там тихо умирала. Хмммм. Чрезвычайно интересный случай! У вас не осталось ли этого кода? Если есть, пришлите мне, пожалуйста, на исследование. Или если в будущем с таким столкнётесь, не забудьте про меня, пожалуйста. |
Автор: | Zealint [ 03 дек 2014, 15:34 ] |
Заголовок сообщения: | Re: Беседа о создании новых архитектур для ЭВМ |
Ух ты : ) Спасибо, SII, за столь подробный ответ. Мне понадобится некоторое немалое время, чтобы его полностью осмыслить. Что касается Вашей догадки, что я математик - это не совсем верно. У меня математическое образование, но скорее алгоритмист-практик. Сам очень не люблю "чистых" математиков. Среди наших "учёных" этого класса мало кто видел реальные задачи и что-то делал своими руками. Это часто было у них предметом споров и обид в мой адрес, когда я называл глупостями их "теоремы", в которых говорится, что вот, мы показали, как нечто сделать для N=1,2,3, аналогично можно и для остальных N. Я всегда отвечал, что как раз на практике на N=3 всё и закончится, если делать так, как они говорят. Поэтому я скорее практик, но, конечно, не архитектор. Моя задача всегда состояла в том, чтобы либо придумать алгоритм, работающий на практике быстро, либо оптимизировать уже известный подход, чтобы минимизировать число операций или их суммарное время выполнения. Меня чаще всего интересуют вопросы типа таких, как выжать из процессора максимум в той или иной программе. Вот, я выжимал, выжимал, и выразил свои пожелания разработчикам архитектуры. Очень хорошо, что нашлись люди, которые аргументированно протестуют, ведь одна из целей этой беседы для меня - больше узнать о железе, ведь я с ним работаю, а также понять, что можно, а чего нельзя поправить, лежат ли причины медленной работы в криворукости архитекторов, или же это физическое ограничение. Постепенно что-то проясняется. |
Автор: | Zealint [ 03 дек 2014, 16:41 ] |
Заголовок сообщения: | Re: Беседа о создании новых архитектур для ЭВМ |
Спасибо подробный за ответ, Yoda. Теперь Ваши аргументы мне понятны, кроме пары. Как Вы предлагаете реализовать длинную арифметику (хотя бы сложение) векторными командами? Я не придумал способа, как с помощью SSE сделать это хоть сколько-нибудь эффективно. Эти переносы портят всю картину, поэтому просто так сложить сразу несколько цифр не получается, нужны дополнительные действия, что сразу убивает весь смысл векторных команд. По поводу реализации генератора простых чисел - это лишь мечты : ) В вопросах генерации основная сложность для программиста - сгенерировать большое простое число. Далеко не все знают, как получить, например, ближайшее снизу к 2^128 простое число. Для этого в общем случае есть алгоритмы, базирующиеся, обычно, на различных схемах определения псевдопростоты и не всегда, правда, они дают на 100% простое число. Раз есть алгоритмы, то я предположил, что можно зашить их аппаратно. Но не только потому, что "хочется", а для полноты картины. Я же, как Вы помните, предлагал концепцию процессорных модулей, которая оказалась глупой. Но в ней был пункт достаточной полноты операций, то есть если делаем процессор для теории чисел, то реализуем в нём основные операции из теории чисел. Сейчас-то я понимаю, что не нужно, в частности из-за того, что нельзя просто так занимать место, которого и так не хватает. Цитата: Другими словами, чтобы влезть в очередь из 200 задач нужно убедить, что твоя там не будет лишней. Вращаясь в этих кругах, могу сказать, что чиновники "лишнесть" или "нелишнесть" задачи определяют только (даже нет, ТОЛЬКО) исходят из размера внешних показателей, которые они приобретут в результате допуска человека на кластер. Если либо чиновник не видит на заявлении подписи какого-нибудь супер-доктора, либо эта задача ему незнакома (а, следовательно, её смысл непонятен), доступ на мощный кластер человек не получит - это я утверждаю на 120% (а ещё можно быть родственником чиновника, тогда не важно, в чём задача). Можно попасть только на какой-нибудь провинциальный, где людям как раз не хватает пользователей. Значительная часть провинциальных кластеров простаивает процентов на 50-90. В качестве примера могу дополнить свою историю рассказом о нашем 80-ядерном кластере в "научном" центре. Когда его только поставили, никто не знал, что с ним делать. Он работал, и за электричество платить нужно было. В течении года я был единственным его пользователем, который умел загружать систему больше чем на 90%. В результате, по сути я и спасал их первый год, хотя этот калькулятор был мне не очень интересен. Потом они и сами научились чему-то. Время простоя у них теперь меньше 70% : ) Также я был в других небольших городах - та же картина. Вы знаете, на сколько процентов обычно загружен "Ломоносов"? Я вот не знаю, но не верю, что больше чем на треть. И не верю, что официальная статистика, если она есть, написана честно. Я знаю, как можно "законно" в отчёте увеличить / уменьшить почти любую цифру в некотором диапазоне, чтобы никто не смог определить ошибку - чиновники пытались учить меня эту годами, - поэтому я давно не верю громким словам. Программу, которая Вам нужна, я поищу позже. Это было 4 года назад, нужно покопаться в архиве. |
Страница 3 из 5 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group http://www.phpbb.com/ |