Комментарии 38
Причем даже если все ядра обращаются к одной памяти (почему бы и нет?), то внутри них ещё есть конвейер, который работает гораздо лучше, если в нем идет поток операций и не нужно никого дожидаться. Даже в вашем первом примере хоть количество условных тиков для выполнения операции уменьшилось с 3 до 2, я уверен, что на реальных процессорах вариант с полностью последовательным выполнением будет быстрее.
ps. Возможно я не совсем прав, все-таки более менее я знаком только с x86 архитектурой, и возможно есть примеры, где такое распараллеливание будет удачным, но я о них не знаю.
Я когда-то смотрел конференцию, где пилили Java на Эльбрусе, там цифра была, что среднее кол-во команд в слове, после кучи попыток распараллелить — 2-3, не сильно больше, чем у того же интела. Зато геморроя с VLIW-ом намного, намного больше. Тот же Itanium, который тоже был VLIW-ом, скоропостижно сдулся.
Я, например, считаю VLIW идеологемой весьма перспективной — именно компилятор должен выявлять параллелизм и планировать его выполнение (хотя и Data-Flow меня интересует и я с наслаждением моделирую принципы работы потовых вычислительных систем). Itanium перестали выпускать из-за малой выгодности (рынок серверов меньше рынка персоналок), да ещё и перекомпилировать все исходники надо. Это пройдёт — рановато ИДЕЮ начали реализовывать, время ещё не пришло. В будущем к связке EPIC/VLIW ещё вернутся неоднократно. Посмотрите мною приведённые примеры ЯПФ и увидите, что случаи 1-3 команд во VLIW-связке бывают (и НИКУДА ОТ НИХ НЕ ДЕТЬСЯ — это свойство алгоритма), но редко. Идея помещения во VLIW-связку команд РАЗНЫХ ПРОЦЕССОВ сильно помогла бы, но это нарушает идею временнОго разделения ресурсов...
Я, например, считаю VLIW идеологемой весьма перспективной
VLIW в виде Itanium уже не взлетело, почему оно может взлететь?
Идея помещения во VLIW-связку команд РАЗНЫХ ПРОЦЕССОВ сильно помогла бы, но это нарушает идею временнОго разделения ресурсов...
Непонятно, как компилятор должен объединять команды разных процессов. А в системах без компиляторного VLIW такая фича уже реализована — это HyperThreading, выполняющий "тяжёлые" команды разных процессов на одном физическом ядре. Может, гибкое объединение команд во время выполнения — это как раз то серьёзное преимущество не-VLIW перед VLIW, что убило VLIW?
Это пройдёт — рановато ИДЕЮ начали реализовывать, время ещё не пришло
Идее уже десятки лет, и как минимум 2 реализации. Одна (Itanium) — все, потому что не выгодно, другая (Эльбрус) — еще нет, потому что другого своего все равно ничего нет.
Мне кажется, что из скрытого параллелизма выжали уже все, что можно (оптимизирующий компилятор, суперскалярность, предсказатель переходов), дальше крупицы по 10% выжимать — оверхед по стоимости, и оно того не стоит.
Плюс учитываем современные реалии. Java на Эльбрусе работает где-то в полтора раза хуже, чем на интеле, даже если бы он работал на частоте Эльбруса — это конечно финиш. И лучше похоже не сделать. Сразу весь hadoop/spark стек можно выкинуть, и остаемся без больших данных. Либо пилить свои велосипеды на C++, что дорого и никому не нужно.
Java на Эльбрусе работает где-то в полтора раза хуже, чем на интеле, даже если бы он работал на частоте Эльбруса — это конечно финиш. И лучше похоже не сделать. Сразу весь hadoop/spark стек можно выкинуть, и остаемся без больших данных.
А разве JIT уже оптимизирован под Эльбрус?
Пилили 4 года (2013-2017), больше об этом не слышно. Если взять сравнение (строка «Общий счет») и поделить на 4 (разница в тактовых частотах), получится, что Эльбрус в 1.25 раза хуже интела 10летней давности в среднем, хотя VLIW, параллельность, вот это все.
1.25 на одинаковых частотах — не так много. JIT, очевидно, работает.
Но с учётом низкой тактовой частоты, разница всё равно 5 крат.
ВостОрженная статья про транслятор для VLIW под Эльбрус: https://zen.yandex.ru/media/electromozg/fishka-rossiiskogo-processora-elbrus-nagliadnyi-primer-rasparallelivaniia-koda-604ea09f126a3d455a57c2bf?&disable_feed_under_article=false
Ваша ссылка не относится к JIT, но там есть интересный пример реализации подобия gcc.godbolt.org для Эльбрус.
Можно константировать, что транслятор С++ в ассемблер Эльбруса работает.
В получаемом коде, на мой взгляд, многовато NOP'ов по сравнению с x86, что наводит на всякие мысли о простоях.
Вкупе с низкой тактовой частотой производительности ждать не приходится. Если бы Эльбрус работал на частотах Интела — было бы неплохо, и в специфических задачах даже отлично.
ВостОрженная статья про транслятор для VLIW под Эльбрус: https://zen.yandex.ru/media/electromozg/fishka-rossiiskogo-processora-elbrus-nagliadnyi-primer-rasparallelivaniia-koda-604ea09f126a3d455a57c2bf?&disable_feed_under_article=false
СКРЫТЫЙ ПАРАЛЛЕЛИЗМ имеет свои границы — не выжмешь больше, чем имеется в алгоритме… Реально "выжимается" ОЧЕНЬ НЕМНОГО того, что имеется в наличии (глубоко очень мало кто внутрь алгоритмов лезет). Самые жирные сливки сверху собраны — ну и достаточно! Конечно, алгоритмы нужно бы разрабатывать под параллельное исполнение — но получается, что самые эффективные (с точки зрения математики) алгоритмы обычно являются самыми сложными для программирования (напр., Штрассен)..!
double e(n) { // n - число членов ряда
double sum = 1;
double f = 1;
double f1;
for (int i=1; i<=n; i++) {
f *= i;
f1 = 1 / f;
sum += f1;
}
return sum
}
И, предположим, пытаюсь ее распараллелить. В этом случае, я вижу возможность запуска трех процессов: 1. вычисление факториалов; 2. Вычисление обратного значения факториала; 3. Добавление вычисленного обратного значения в сумму.
Скажите, сможет Ваш программный комплекс, грубо говоря, получив на вход мою программу сгенерировать на выходе распараллеленную программу?
PS: я понимаю, что в приведенном мною примере многое притянуто за уши, например члены ряда быстро выйдут за пределы точности и что накладные расходы по синхронизации потоков на порядки превысят стоимость простого суммирования или умножения. Я хотел просто получить представление в том, насколько в принципе такие классы задач решаемы на сегодняшний день.
накладные расходы по синхронизации потоков
Нужна несколько иная архитектура процессора, на которой эти расходы невелики. Например, VLIW.
На CUDA, насколько я помню, нити внутри одного варпа (группы по 32 потока) выполняются синхронно, как будто имея общий instruction pointer… Но вам нужно выполнять разный код на разных ядрах, так что CUDA не подойдёт.
Да и обычный суперскалярный x86 процессор сам может одновременно загрузить несколько арифметических устройств внутри ядра, так что, возможно, ваша задача уже решается автоматически.
Но вам нужно выполнять разный код на разных ядрах, так что CUDA не подойдёт
А если так:
switch (threadIdx.x)
{
case 0:
r = a * b;
break;
case 1:
r = a / c;
break;
}?
П.С. я понимаю, что производительность у такого решения никакая.
Ну смысл в ускорении. В вашем примере сначала первый поток выполняет инструкцию, а второй ничего не делает, а на следующем такте наоборот. 2 такта на 2 инструкции.
r = funcs[threadId.x](operands1[threadIdx.x], operands2[threadIdx.x]);
? Правда предварительно нужно сделать:
__device__ divis(double a, double b)
{
return a / b;
}
__device__ mult(double a, double b)
{
return a * b;
}
funcs[0] = &divis;
funcs[1] = &mult;
operands1[0] = a;
operands2[0] = b;
operands1[1] = a;
operands2[1] = c;Не могу сказать. Когда я активно изучал CUDA, указателей на функции в device-коде ещё не было. Мне не приходилось применять эту фичу, поэтому я не помню этого момента. Надо смотреть документацию. Если в документации нет — можно попробовать отловить просадку производительности, передавая для варпов либо одинаковые указатели, либо разные...
Для этого применяют планирование.
В принципе, задача уровня средней курсовой 3-4 курса политеха лет 15 назад, если решать под конкретный алгоритм.
В процессе хорошо получается сравнивать SIMD/MIMD/VLIW и их комбинации для конкретных задач распараллеливания.
Естественно, анализ произвольного куска кода, особенно потоков и связей данных — это задача совершенно другого уроня.
Приятно слышать Ваше мнение! Вы правы, конечно — ничего принципиально нового нет. Просто сейчас "дым глаза замстИл" — почти никто не думает об использовании внутренних свойств алгоритмов "наилучшим образом". Налицо "головокружение
от успехов" (как тов. Сталин пИсывал). Огромное количество библиотек "думанию" как раз и не способствует…
Эта система нужна была для обучения молодёжи пониманию сути рационального использования внутреннего ресурса (в смысле потенциала параллелизма) алгоритмов. Выяснилось, что практически никто из "молодых" не представляет, откуда параллелизм берётся… с неба "дыхание господа" падает, что ли? То, что "хвост растёт" именно из алгоритмов (их свойств, конечно!) приходится буквально доказывать (и
мои системы как раз позволяют делать это).
Может, кто-то из молодых в будущем нечто новое, поразмыслив,
придумает в этой области! Так что предлагаемая работа — попытка "инъекции к размышлению"… // PS. А вот сравнение вычислительных трудоёмкостей различных методов получения планов выполнения параллельных программ и выбор лучших — совсем интересная (да и суперпрактичная тоже) вещь..!
Протестировать любую программу на наличие скрытого параллеизма просто. Инсталлируете vbakanov.ru/dataflow/content/install_df.exe (Winэ32, GUI), смотрите примеры программ (*.set — файлы) и список поддерживаемых команд в base.pdf. Для «разгона» позапускайте готовые программы (список в list_of_programs.txt).
Создаёте свою программу и отлаживаете её (все переменные — double float). Не забывайте о требовании однократного присваивания! Условное выполнение реализуется механизмом предикатов (пример в нижней части vbakanov.ru/dataflow/dataflow.htm). Полезно использовать макрос псевдо-массивов (конечная часть base.pdf). Время выполнения операций задёте в data_flow.ini (в тиках Interval, мсек). Сколько параллелизма в Вашем коде найдётся, столько и будет использовано (размер гранулы параллелизма — одна команда; это
и есть ILP).
ПрогонЯете программу с заведомо большим числом параллельных вычислителей (называются АИУ — Арифметически-исполнительными Устройствами), напр., 10^6. При этом определяете максимум АИУ, необходимых для вычислений (пусть P0). Далее исследуете процесс выполнения программы при числе АИУ от 1 (полностью последовательное выполнение) до P0 (максимальное использование потенциала параллелизма). Можно анализировать время выполнения, коэффициент ускорения при распараллеливании, график интенсивности вычислений (F6) etc. Расписание вычислений берёте из лог-файлов tst!*.txt, tpr!*txt и др. (форматы описаны в base.pdf).
При желании сохраняете программу по F7 в виде информационного графа (*.gv — файл). Его используете в системе SPF@home (http://vbakanov.ru/spf@home/content/install_spf.exe) и как
хотите изменяете ЯПФ путём использования API-вызовов на Lua (даю только один пример GeteroCalcs.lua). Без Lua-программирования можно воспользоваться вызовами из выпадающего главного меню (F4, F5/Ctrl+F5, F6, F7).
Далее — собственная настойчивость и личные консультации!
Я («an mass», как говАривал проф. Выбегалло), сотрудничаю
со студентами ВШЭ / МИРЭА. А еще (с глубокой юности) очень
уважаю «пана СтанИслава»:
— По правде, – бурчал Трурль, – надо бы как-то иначе
скомбинировать… Впрочем, важнее всего алгоритм!
— Тоже мне открытие сделал! Известно, без алгоритма
ни шагу ступить! Ну нечего, надо экспериментировать!
/// «Пан СтанИслав» (Станислав Лем), КИБЕРИАДА, новелла
«Путешествие второе, или Какую услугу оказали Трурль и
Клапауций царю Жестокусу», 1964-1979.
Постараюсь выкроить время и поиграться. Дело-то конечно хорошее, но мне пока трудно оценить насколько удобно пользоваться скриптами с практической точки зрения. Вернее мне пока не до конца понятно нужно ли написать скрипт под конкретный процессор (учтя таким образом продолжительность выполнения команд и количество параллельно выполняемых процессором операций) и затем можно применять его к любому алгоритму для его адаптации на данном процессоре? Или скрипт это просто аналог Jupyter notebook и процесс адаптации алгоритма к процессору будет интерактивным и творческим, а не автоматическим?
И еще стОит поправить иллюстрацию «На рисунке — ярусно-параллельная форма алгоритма решения полного квадратного уравнения в вещественных числах в канонической форме (номера ярусов ЯПФ расположены справа)». Красный пунктир от первого и третьего вычислителей следует укоротить на один ярус снизу.
Практически работал только с MPI (на кластере). Клеточные
автоматы знаю только теоретически (знаменитые 29 состояний
фон Неймана). реконфигурируемые системы — то же. Чипы
«в железе» не разрабатывал, конечно! Моя история — vbakanov.ru…
VLIW предполагает наличие ряда параллельных процессоров
(гомогенное поле), на каждый из которых поступает и выполняется
своя инструкция (сгенерированная транслятором и обладающая
свойством независимости по данным от других) из «бандла»
(«сверхдлинное слово») — это классическое описание. Проблема
условности выполнения была решена методом предикатов (96
аппаратных битовых регистров) — похоже на подход ARM.
Lua-скрипты могут делать только то, что предпИсано им в данной
системе… Учитывается только гомогенное или гетерогенное поле
параллельных вычислителей, имеются API-вызовы для определения
возможности выполнения конкретного оператора на конкретном
вычислителе. Ждать описания каждого процессора бессмысленно
— это другое исследование (да, кажется, таких моделй немало).
В этой системе я делаю именно на АЛГОРИТМ (конкретно — на его
свойства в области потенциала распараллеливания и их применение
на уровне СКЕЛЕТА параллельной программы). От техник собственно
паралельного программирования я ухожу (ибо практически работал
только с одной — MPI, но вижу, что они не могут улучшить алгоритмом
заданное качество параллельности, но почти всегда ухудшают из-за
всегда имеющихся технических ограничений).
Из примеров скрипта даю только GeteroCalcs.lua — один из сценариев
распределения операторов на поле параллельных гетерогенных
вычислителей (формально всё описано в API_User.pdf). Надеюсь,
звуки (разные) мешать не будут — приходилось работать с очень
«долгоиграющими» алгоритмами и они (звуки) помогают при
зацикливании и в качестве сигнала прекращения чаепития…
Считаю важной задачей создать классификацию алгритмов по
параметрам распараллеливания (чтобы априори знать, какой из
готовых сценариев — напр., на Lua — эффективнее использовать для
получения рационального скелета расписания при максимальной
плотности кода. Простым взглядом видно, что у исходной
(«естественной») ЯПФ плотность кода невысока (кстати, это явилось
одной из проблем c Itaniumэ'ом — «бандлы» частенько бывали
МАЛОЗАПоЛНЕННЫМИ (см. тот же рис.2). У Intel работали Орды
разработчиков компиляторов (русские / индусы etc), но ПЛОТНОСТЬ
КОДА ВСЁ РАВНО ОСТАЛАСЬ НЕДОСТАТОЧНОЙ (бандл VLIW часто
состоял из одного-двух операторов!).
Диапазон допустимого варьирования положения операторов
100, 102 и 103 на рис.2 вЕрен, но готов рассмотреть аргументы об обратном. Для информации — в списке API-вызовов за определение верхней (минимальный ярус) и нижней (максимальный ярус)
границ расположения оператора Op отвечают операторы GetMinTierMaybeOp(Op) и GetMaxTierMaybeOp(Op) соответственно
(см. API_User.pdf). Без привлечения Lua можно воспользоваться F7 в модуле spf_client.exe (предварительно нужно создать ЯПФ по выбранному графу алгоритма — напр., F5); для рис.2 это файл squa_equ_2.gv.
Клеточные автоматы это другое. Я имел в виду multiclet.com Ребята, на мой взгляд, не смогли убедительно продемонстрировать преимущество своей архитектуры и «сели на мель», запаниковали, попытались оседлать волну блокчейна и не похоже что выгребут. Хотя, не стоит каркать т. к. несколько изделий на их чипах таки пошли в серию, пусть и не очень крупную. Как мне кажется, они уперлись в физические ограничения реализации основы своей архитектуры — коммутатора и поэтому в дальнейшем планировали идти на компромиссы, отклоняясь от каноничности своего подхода. Тем не менее они реализовали в железе несколько версий своего чипа, предлагают девборды и все это вполне доступно для «поиграться». Помимо специфичного ассемблера, как-то реализовали и сишный компилятор. Не знаю насколько он «умный», но мне кажется что ваши наработки могли бы им очень пригодиться т. к. уже реализованные ими чипы хорошо ложатся на ваши математические изыскания.
По поводу рис.2 в тексте явно не указывается что означают красные пунктиры, но они имеют жирную красную точку на нижнем конце, а не на каждом ярусе, и поэтому были восприняты мной как иллюстрация к «Однако легко видеть, что простейшее преобразование (показанные красным пунктиром допустимые перестановки операторов с яруса на ярус) позволяют выполнить тот же алгоритм за то же (минимальное из возможных) время всего на двух вычислителях!» А поскольку операции 107 и 108 с 5-го яруса не могут быть смещены выше, то и операция 100 может занимать ярус не ниже 4-го.
Но если в вашей трактовке красный пунктир это отметка всех ярусов на которых может быть расположена соответствующая операция (без оглядки на ограничение ширины яруса), то конечно их размер правильный. Однако я бы в данном случае либо не ставил точку вообще либо ставил бы точки на каждом ярусе. Впрочем, это ваше право вводить какие угодно обозначения.
MPI нужна была для обеспечения практики работы со студентами на кластере. Получилось неплохо — были разобраны несколько стратегий использования MPI (от фактически ILP до нормальной ленточной процедуры умножения матриц — один из плакатов презентации здесь: https://cloud.mail.ru/public/YfR4/TLkgFn7DY). Естественно, время выполнения каждой гранулы фиксируется по локальным часам ноды, вычитывается время передачи данных (кстати, первая часть исследования — определение латентности сети).
А насчёт красного пунктира разве нечётко в тексте сказано? Картинка примитивная, конечно, но как-то ведь проиллюстрировать нужно было…
Кстати, сейчас экспериментирую с "нижней" формой ЯПФ — очень интересно получается… Наверное, в марте подготовлю публикацию (решил "не более одной в месяц")!..
Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом