OSDev

для всех
Текущее время: 28 мар 2024, 15:11

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 41 ]  На страницу Пред.  1, 2, 3, 4, 5  След.
Автор Сообщение
СообщениеДобавлено: 03 дек 2014, 17:06 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
Zealint писал(а):
Программу, которая Вам нужна, я поищу позже. Это было 4 года назад, нужно покопаться в архиве.

Хотя, зачем далеко ходить. Я подозреваю, что Вас заинтересуют все программы этого класса алгоритмов, что у нас есть.

Заходите, пожалуйста, на эту страницу. Там есть раздел "C++ implementation", где можно скачать реализации явных формул для подсчёта коротких циклов в графе (вот прямая ссылка). Я не помню, чем отличаются версии Optimized от NotOptimized (скорее всего, там что-то вынесено за скобки). Посмотрите сразу на файл для циклов длиной 12 или 14 в двудольных графах : ) (это файлы Cycles.12.cpp и Cycles.14b.cpp).

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

В итоге дело было так: GCC с опцией "максимальная оптимизация" умирал тем способом, что был мною описан выше. Компилятор Intel C++ всё это съедал без проблем с любой степенью оптимизации. Вскоре, как мне сказал коллега, GCC тоже научился это съедать, но оптимизация проигрывала интеловской то ли в десятки, то ли в сотни раз : ) Честно слово, не помню уже. Возможно, спустя 4 года всё стало лучше, но желания возиться и проверять сейчас нет. На всякий случай дополню, GCC брался из MinGW. Но это не умоляет поучительность данного примера и степень хорошести теста для тех, кто пишет свой компилятор.

Если кого-то заинтересует вопрос "нафига это!?" и "как это делается?", то читайте работу автора всей этой каши. Он этим надолго закрепил своё первенство в данной области.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 03 дек 2014, 17:48 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
Итак, коль скоро я инициатор беседы и поскольку мои идеи оказались несовместимыми с практикой, я предлагаю теперь опытным участникам кратко выразить свои основные претензии к архитектурам, что доступны рядовому пользователю (x86, ARM, может даже архитектуры современных GPU). Претензии эти я бы попросил обосновать. То есть не как у меня получилось, когда я просто говорю, что мне что-то не нравится или кажется лишним, а чтобы ваша претензия имела бы (гипотетически) практический смысл. Особенно хорошо будет, если кто-то имеет идеи об исправлении указанных им недостатков. Если это не секретная информация : )


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 03 дек 2014, 18:33 
Аватара пользователя

Зарегистрирован: 14 мар 2011, 12:31
Сообщения: 970
Откуда: Дагоба
SII писал(а):
Вы заблуждаетесь просто глубочайшим образом. Львиную долю площади кристалла современных мощных процессоров занимает именно кэш, поэтому сколько-нибудь значительно его нарастить не удастся. Поддержка же всякого мусора архитектуры IA-32 (а эта архитектура -- действительно одна из самых ужасных) требует лишь мизерных дополнительных затрат аппаратуры по сравнению с общим объёмом последней.

По поводу мизерных затрат на мусор и львиной доли кэша позволю себе не согласиться. На странице 29 классической книги Хеннесси и Паттерсона есть рисунок 1.14 - флор-план Intel Core i7, как всего проца, так и каждого из четырёх ядер. Там видно, что совокупно все три уровня кэш-памяти занимают меньше половины площади кристалла. Оценить количество мусора прямо вряд ли возможно, на флор-плане мусор так прямо не отмечен, но есть косвенные критерии, такие как нерегулярная система команд, приводящая к сложности декодирования инструкции и трансляция во внутреннее RISC-представление, что тоже требует немало ресурсов.

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

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

SII писал(а):
Что же касается объединения нескольких операций в одну команду, то да, это позволяет поднять производительность -- и это одна из причин, почему CISC-процессоры архитектуры IA-32 (причём плохой CISC-архитектуры) оказываются в общем случае существенно быстрей, чем RISC-процессоры -- правда, ценой усложнения самого процессора.

Это тот случай, когда под "нож сокращения инструкций" пошли те, которые сокращать было не надо. Но это очень хороший пример, как раз в тему, - как правильно замечено, ранние RISC-процессоры успевали сделать несколько инструкций тогда, как CISC-процессор только одну. Это лишний раз подтверждает тот факт, что объединение команд - далеко не всегда благо.

Zealint писал(а):
Как Вы предлагаете реализовать длинную арифметику (хотя бы сложение) векторными командами? Я не придумал способа, как с помощью SSE сделать это хоть сколько-нибудь эффективно. Эти переносы портят всю картину, поэтому просто так сложить сразу несколько цифр не получается, нужны дополнительные действия, что сразу убивает весь смысл векторных команд.

Нет, если вы посмотрите реальную картину, то увидите, что не портят. Представьте, мы складываем два килобитных числа. Мы разбили их на группы по 16 64-битных чисел (я не говорю применительно к x86, сейчас чисто теоретический анализ), которые сложили одновременно одной векторной инструкцией. Среднестатистически в половине сумм у нас возникнет перенос. Тогда следующей операцией мы одновременно инкрементируем те суммы, перед которыми возник перенос. С вероятностью примерно 1-1/2^48 на этом всё закончится. В оставшемся (невероятно мизерном) количестве случаев в одной или нескольких суммах у нас произойдёт распространение переноса (возможно, циклическое, но в свете вероятности это не важно). Как видите, векторная схема отлично работает без использования математических сопроцессоров!

Zealint писал(а):
По поводу реализации генератора простых чисел ... Раз есть алгоритмы, то я предположил, что можно зашить их аппаратно.

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

Zealint писал(а):
Вращаясь в этих кругах, могу сказать, что чиновники "лишнесть" или "нелишнесть" задачи определяют только (даже нет, ТОЛЬКО) исходят из размера внешних показателей, которые они приобретут в результате допуска человека на кластер. Если либо чиновник не видит на заявлении подписи какого-нибудь супер-доктора, либо эта задача ему незнакома (а, следовательно, её смысл непонятен), доступ на мощный кластер человек не получит - это я утверждаю на 120%

А как иначе отфильтровать клиентов? Я не знаю другого эффективного способа. Либо вникай в задачу, либо смотри на именитые подписи, другого не дано.
По поводу доступа - не так всё плохо, даже студент может получить долю времени. Каждый год проводится Летняя Суперкомпьютерная Академия, в рамках которой доступ к СК Ломоносов может почти любой желающий (ну определённая фильтрация всё же есть - читайте условия).

Zealint писал(а):
Вы знаете, на сколько процентов обычно загружен "Ломоносов"? Я вот не знаю, но не верю, что больше чем на треть.

Я же пишу - у него нет простоя! Работает 24 часа круглый год без выходных и праздников, больше сотни задач ждут в очереди, когда СК освободится. Вы конечно можете не верить, ваше право. Побеседуйте с член-кором РАН Владимиром Воеводиным, с ним традиционно можно пересечься либо на ежегодном фестивале науки, он проводит экскурсии по Ломоносову, либо на СК Академии.

upd
Zealint писал(а):
я предлагаю теперь опытным участникам кратко выразить свои основные претензии к архитектурам, что доступны рядовому пользователю (x86, ARM, может даже архитектуры современных GPU). Претензии эти я бы попросил обосновать.

Претензии весьма обширны. Проблема в том, что кратко выразить их не удастся, тем более с обоснованием. Работа тянет на серьёзную статью.

_________________
Yet Other Developer of Architecture.
The mistery of Yoda’s speech uncovered is:
Just an old Forth programmer Yoda was.

<<< OS Boot Tools. >>>


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 03 дек 2014, 18:58 

Зарегистрирован: 21 сен 2007, 17:24
Сообщения: 1088
Откуда: Балаково
Так, похоже что суперкомпьютер вам больше не нужен, всё решается за 2 минуты на ПК с процессором 3.2ГГц (использовалось только одно ядро) с 8ГБ памяти (занялось только 3ГБ). Процессор Intel Core i5-4570, память DDR-3 1600МГц, Windows-7 64-бит.
gcc -O3 Cycles.12.cpp
время 30 сек, память 1ГБ (2,5ГБ вместе с ОС)

gcc -O3 Cycles.14b.cpp
время 30 сек, память 1,5ГБ (3ГБ вместе с ОС)

Cycles.12.exe c20.in
2514159648000
время 1,5мин. (NotOptimized)
время 6сек. (Optimized)

Cycles.14b.exe c20.in
2586030790406400
время 2мин. (NotOptimized)
время 6сек. (Optimized)

Использую текущий MinGW GCC 4.8.1
На Unix-ах есть 4.9.2, только на MinGW ещё не портирован.

Полагаю, что парк i8086 нельзя приравнять к 1 Pentium. В суперкомпьютерах есть выигрыш только на необычайно распределённых вычислениях, крайне специфических.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 03 дек 2014, 19:36 
Аватара пользователя

Зарегистрирован: 16 май 2007, 23:46
Сообщения: 1126
За полвека компьютерная техника так ушла далеко вперёд, что найти реальные недостатки сложно.
Тот же интел тоже живёт более 30 лет.

Не нравится долгая выгрузка и загрузка регистров при переключение задач. Хотя для существующих задач не влияет.
Своё ядро для обработки прерываний. С небольшим числом команд.
Для i7 думаю надо систему команд по проще.
Да и вообще всю архитектуру я бы пересмотрел. Думаю система с большим числом простых независимых сопроцессоров была бы эффективнее. При этом кэш первого уровня надо будет перестраивать.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 03 дек 2014, 19:49 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
Himik писал(а):
Так, похоже что суперкомпьютер вам больше не нужен ...

Занятно : ) Спасибо за тестирование. Осталось сравнить с тем, что сможет сделать icc (Intel C++ Compiler), поскольку лично я считаю его самым лучшим по части оптимизации.

Значит, что-то изменилось с тех пор, как мы издевались над компиляторами 4 года назад. Однако память при компиляции всё равно кушает сильно, но, что радует, уже не 4 Гб. Только поправлю: Вы ошибаетесь, когда пытаетесь алгоритм c14b запустить на графе с20. Формально работать будет, но ответ будет неправильный, ведь алгоритм предназначен для двудольных графов, а c20 - полный граф.

Пока осмысливал Ваше сообщение и набирал ответ, запустил VS C++ 2013 для компиляции Cycles12 из папки Optimized. Съел 286 Мб, время компиляции 12 минут. Но зато работает на complete20.in всего 4 секунды (Core i7 3960X @3,3 GHz, 24 Gb DDR3-1333). Да, это лучше. По-моему, студия раньше вообще компилировать отказывалась за разумное время.

Суперкомпьютер нужен всё равно, так как ведь c20 - это лишь граф из 20 вершин, а реально их может быть десятки тысяч. Для частных случаев (граф ферзя, например) код сильно упрощается руками и ускоряется в миллионы раз, но это уже другая история... мы там тоже ряд формул вывели, но они остались "в столе". Наука-то закончилась : (


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 03 дек 2014, 19:59 
Аватара пользователя

Зарегистрирован: 17 фев 2013, 16:13
Сообщения: 163
Yoda писал(а):
Нет, если вы посмотрите реальную картину, то увидите, что не портят. Представьте, мы складываем два килобитных числа. Мы разбили их на группы по 16 64-битных чисел (я не говорю применительно к x86, сейчас чисто теоретический анализ), которые сложили одновременно одной векторной инструкцией. Среднестатистически в половине сумм у нас возникнет перенос. Тогда следующей операцией мы одновременно инкрементируем те суммы, перед которыми возник перенос. С вероятностью примерно 1-1/2^48 на этом всё закончится. В оставшемся (невероятно мизерном) количестве случаев в одной или нескольких суммах у нас произойдёт распространение переноса (возможно, циклическое, но в свете вероятности это не важно). Как видите, векторная схема отлично работает без использования математических сопроцессоров!

В общем случае понятно. Когда я разрабатывал свой подход, у меня была задача применить конкретно SSE. В xmm регистрах у нас всего 2 числа по 64 бита. Я пытался придумать, как после параллельного сложения нескольких регистров учесть все сдвиги (без вероятностного подхода, а просто, рассматривая различные случаи - ведь вероятность вероятностью, а "худший случай" обязательно произойдёт), и у меня не вырисовывалась схема, как это запрограммировать, чтобы стало быстрее, чем последовательность add/adc... Прикинув, сколько будет действий, я счёл невозможным считать такую схему более эффективной. Уже не помню, что именно стало трудностью, давно это было.

Благодарю за пояснения.

Yoda писал(а):
Претензии весьма обширны. Проблема в том, что кратко выразить их не удастся, тем более с обоснованием. Работа тянет на серьёзную статью.

Понимаю. А собираетесь писать статью?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 04 дек 2014, 14:24 

Зарегистрирован: 21 сен 2007, 17:24
Сообщения: 1088
Откуда: Балаково
pavia писал(а):
Не нравится долгая выгрузка и загрузка регистров при переключение задач. Хотя для существующих задач не влияет.

Она не долгая, нормальная. Всё-равно на компьютере запускается задач с полной загрузкой не больше, чем количество процессоров. Да и кванты переключения можно удлинить, т.к. в событийно-управляемой системе квантование не принципиально. В Линуксе вроде уже 1Гц сделали ради экономии энергии на ноутбуках.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 10 дек 2014, 10:07 
Аватара пользователя

Зарегистрирован: 28 май 2012, 23:44
Сообщения: 237
Откуда: Санкт-Петербург
Хабрастатья в тему -- какое ПО используют в научных исследованиях в Великобритании. Просмотрел по диагонали, так как перевод некачественный и орфография хромает.

В свете нашей дискуссии важно то, что 70% мужчин и 30% женщин разрабатывают свое ПО, хоть иногда и не владеют в достаточной степени навыками программирования. Тема актуальна не только в России, выходит.

(Перепостил в эту тему, чтобы не флудить в теме про язык. Эта тема более флудерская).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 10 дек 2014, 15:25 

Зарегистрирован: 15 апр 2014, 14:13
Сообщения: 127
Опять тов. Zealint поднял весьма актуальную тему. Попробую суммировать суть возражений от остальных участников так - новая архитектура кажется сомнительной из-за одной простой штуки - куда не переноси сложность, она всё равно останется сложностью.

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

В общем (как уже и объявлял ранее в других темах) спасение человечества вижу в тесной связке железа с компилятором, которая обеспечивается более дружественным к компилятору языком (например - Java) в сочетании с более дружественной к связке железа с компилятором операционной системой.

Собственно проблема переноса сложности здесь разрывается в части, ответственной за оптимизацию. То есть не переносим тупо один и тот же алгоритм из софта на железо, но пропускаем его через этап эффективной оптимизации. Суть оптимизации всегда простая - адаптировать алгоритм к имеющимся вычислительным ресурсам. Так вот в современном мире адаптировать алгоритм к процессорам от Интел не получится ни у кого, кроме самой фирмы Интел (неплохое конкурентное преимущество). И не получится опять по простой причине - ни кто не знает, как фирма Интел устроила внутренности своих процессоров, что означает отсутствие информации о имеющихся вычислительных ресурсах, помимо указанной в документации. Поэтому (в который уже раз) и предлагается открыть эту самую информацию. Но поскольку фирме Интел это не выгодно - не стоит ждать милости от этого творения природы, но нужно взять все милости самостоятельно, внедрив в обществе простую и понятную архитектуру на основе связки процессор-компилятор с прилагающимися высокоуровневым языком и ОС.

Как оно работает ? Очень просто - если нам нужно сложить число из миллиона бит, то (как здесь уже аргументировали) возникает проблема переносов. Но стоит обратить внимание (как это сделал Yoda) на вероятность возникновения этих самых переносов, как мы сразу находим способ резкого понижения сложности за счёт оптимизации. Вместо регистров на миллион бит или микрокоманд процессора, выполняющих все переносы без разбора, мы используем набор параллельных сумматоров, на выходе которых выполняем проверку наличия переносов. Вот эта самая проверка как раз и выполняется наиболее эффективным способом в связке процессор-компилятор. Ведь если реализовать её в железе, то она чаще всего будет просто отнимать столь нужную нам площадь кристалла, а если реализовать программно с использованием существующих процессоров - тогда получим мегапотери на чтение/запись промежуточных результатов. В случае наличия связки компилятор-процессор железная логика подчинена потребностям компилятора. В результате нет ни каких проблем сказать процессору - закэшируй-ка дружок вот этот мегабит (128кб) по такому-то адресу, затем загрузи в кэш программ коротенькую микропрограмку и запусти её на выполнение. А микропрограмку, естественно, оптимизировал под конкретный набор вычислительных ресурсов на текущем процессоре наш второй дружок - компилятор. В результате максимально эффективный алгоритм будет получен именно под конкретный список вычислителей и адресов внутренних регистров (которые тоже есть тот же кэш). И в следствии максимизации адаптации алгоритма под имеющиеся ресурсы производительность будет на порядки больше, чем в случае с чисто железным решением или же с решением на существующих процессорах. Ни вам обмена с памятью во время вычислений, ни излишних вычислений в случае отсутствия переносов. А ведь обмен с памятью (даже с кэшами верхних уровней) - это множество холостых тактов. Точно так же и ненужные вычисления с битом переноса равным нулю - опять минимум по такту на каждый перенос, и плюс, конечно же, экономия места на кристалле с выделением его под дополнительные вычислители и/или кэш.

Вот такая тривиальная идея. Не понимаю, почему её до сих пор не реализовали ? Готов по этому поводу увидеть мысли ни разу не согласных со мною критиков :)


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 41 ]  На страницу Пред.  1, 2, 3, 4, 5  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB