Тута образовалось две занятные темы. Быстродействие видеосистем и умножение матриц. И вот что мне подумалось, мы разговариваем здесь только в контексте современной традиционной архитектуре. А ведь эти задачи решаемы. Нужно просто отойти от догм традиционной архитектуры.
Что я подразумеваю под традиционной архитектурой. Традиционная архитектура процессор, обращающийся к памяти и последовательно выполняющий команды. То бишь, Фон Нейман во всей его красе и недостатках. Если я скажу, что у архитектуры имеется большой недостаток, я Атлантиды не открою. Это еще сделал Бэкус в знаменитой Тьюринговой лекции Can programming be liberated from the von Neuman style? (правда думаю что это настолько очевидно, что кто-то мог это ляпнуть и раньше). А именно, bottleneck в шине памяти. Можно сколько угодно убыстрять работу памяти, работу процессора, но шину между процессором и памятью убыстрить такими же темпами не удастся. Это в принципе заметно и сейчас – добавление процессора не дает скачка в 100%.
Как решить проблему быстродействия? Легко. C помощью параллельных вычислений. Большинство часто встречающихся и в то же время тяжелых для процессора алгоритмов, как то сортировка, или то же умножение матриц легко делается с помощью алгоритмов разделяй и властвуй. Те же матрицы могут быть разделена на несколько, раздельно вычислены частями и затем вычислены уже в одну матрицу. Или возьмем, ту же видеопамять. Допустим у нас существует 10 процессоров. Каждый работает со своей областью памяти. При приходе команды на вывод строки, команда разделяется по разделам памяти, и каждый процессор выполняет вывод своих символов. Если нельзя увеличить быстроту шины, то почему бы и не увеличить количество шин. Я верю что данная архитектура будет более производительной чем традиционная. И это в принципе доказано. mainframe системы как раз и строятся на параллельных алгоритмах и архитектурах. Мы слишком привыкли к традиционной архитектуре. Все что делается и делалось, например те же учебники по алгоритмам, подразумевают традиционную архитектуру с последовательным выполнением команд.
Некоторые естественно сразу подумали, а ведь современная архитектура уже параллельна. NUMA хоть в виде кэша есть(NUMA – Non uniform Memory Architecture. Каждый процессор имеет свою локальную память). Ну и внутри у него несколько Risk процессоров(а сейчас и ядер несколько). В общем все это есть, а вот счастья нет. Потому как не работает это все на полную мощность. И никогда не заработает, пока все, от железа до OS и компилятора и программиста не смогут распараллелить вычисление сознательно и вручную. Но зато можно сказать, что аппаратных проблем для стандартного писюка уже нет.
Сейчас OS распараллеливает программы и потоки. Ничего хорошего и удобного я об этом сказать не могу. Кроме грыжи и расшатанных нервов такая синхронизация не приносит. И процессор, который на внутреннем уровне состоит из нескольких процессоров, выполняет один поток команд. Мы платим деньги только за один поток команд. А теперь представим, у нас есть несколько управляемых процессоров. У каждого процессора есть своя личная память. Мы загружаем в каждый процессор подпрограмму, и выполняем независимо. Пускай даже эти процессоры работают медленнее чем теперешние, но выигрыш мы получим. Единственное что, языки не поддерживают данное начинание.
Mainstream языки ориентированы на последовательное выполнение команд. Максимум поддержки – это ручная синхронизация данных в виде какой-нибудь lock или critical_section. Ничего кроме торможения, и нелокализованных ошибок это не приносит. Но ведь компилятор имеет всю информацию для того, чтобы организовать параллельную обработку данных. И язык должен вынудить программиста писать программы, которые легко распараллелить. Я не сторонник функциональных языков, но они могут такое. Они вынуждают разделять функциональность на функции без состояния. Только входные и выходные параметры. О синхронизации данных, можно забыть. Можно ли это организоваться в ООП программах? Наверняка можно. Есть фичи типа активных объектов. Это когда объект имеет свой поток выполнения. Считай что набор подпрограмм для процессора. Может данная фича мне и не нравится(это мое личное IMHO) но она все-таки есть. И наверняка есть другие способы безопасного распараллеливания. Я боюсь даже догадываться о том, что можно придумать. У компилятора – вся необходимая информация есть. Если он откажется от мысли, что код должен быть именно такой каким его написали, то ограничения снимаются и возможности повышаются.
Возможна ли революция? По моему нет. Практически все что можно в языках программирования придумали в 50-60 годах. И в том числе Algol, Lisp и параллельное программирование. Ничего кардинально нового не появилось. В mainstream остался только Алгол, который стал вбирать многие средства Lisp(и вбирает до сих пор). Но Лиспом он не стал и не станет. Так же и в архитектурах. Intel вбирает в себя параллельную архитектуру (и вбирает до сих пор), но параллельным не станет. А следовательно будем дальше мучиться с синхронизацией shared memory, и оптимизацией качества кода для конкретного процессора.

С уважением, Gleb.

Идею смены архитектуры полностью поддерживаю, так как по-моему назрела она давно.
А вот по поводу способов — как это можно сделать — вызывают большие сомнения.

Начну с самой очевидной идеи распараллеливания — кучи процессоров с собственной памятью. Идея прекрасная и давным-давно уже применяется. Великолепно работает, когда нужно провести много идентичных вычислений, особенно для тех алгоритмов, которые допускают разбиение на отдельные и распараллеливаемые фрагменты (вот как те же матрицы). Однако далеко не все алгоритмы столь хороши. Есть случаи, когда скорость вычислений будет расти как логарифм от числа процессоров. А добиться увеличения производительности в 6-10 раз, за счёт миллиона процессоров — может быть несколько накладно... Это главное препятствие математического плана.

Теперь о программировании. Идея написания языка, который автоматически обеспечивал бы распараллеливание (или хотя бы облегчал его) — витает очень давно. И попытки создать такой язык предпринимались неоднократно — вспомнить хотя бы бум вокруг транспьютеров и языки программирования, которые были для них созданы. И хотя некоторый прогресс и был достигнут — до серебряной пули или базового решения, которое можно было бы использовать, как основу для новой технологии, оказалось довольно далеко. Оказалось, что для достижения действительно высоких результатов от разработчика требуется квалификация и трудозатраты идентичные тем, что требуются для обеспечения параллелизма на обычных языках. То есть — весьма существенные. И это является главным препятствием. Где то я видел оценку, по которой написание и отладка многопоточного (распараллеливаемого кода) получалась от 10 до 50 раз дороже, чем написание кода обычного — однопоточного. Хотите проверить — напишите многопоточную сортировку, которая будет работать быстрее однопоточной

К вопросу о шинах между процессором и памятью. Взгляд совершенно здравый — они действительно являются зачастую узким местом в системе. И их действительно нужно распараллеливать. Однако это не обязательно требует распараллеливания процессоров. Можно увеличить количество шин между процессором и памятью не увеличивая количество ядер. При определённом подходе это даст хороший прирост производительности, особенно, если в пересылку данных одновременно с процессором вовлечены другие устройства или процессоров – несколько. Впрочем, и эта технология сейчас активно применяется.

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

Здравствуйте, AndreyFedotov, Вы писали:

AF>Начну с самой очевидной идеи распараллеливания — кучи процессоров с собственной памятью. Идея прекрасная и давным-давно уже применяется. Великолепно работает, когда нужно провести много идентичных вычислений, особенно для тех алгоритмов, которые допускают разбиение на отдельные и распараллеливаемые фрагменты (вот как те же матрицы). Однако далеко не все алгоритмы столь хороши. Есть случаи, когда скорость вычислений будет расти как логарифм от числа процессоров. А добиться увеличения производительности в 6-10 раз, за счёт миллиона процессоров — может быть несколько накладно... Это главное препятствие математического плана.

Компьютерная графика, например — прекрасно распараллеливается
Интересно — а какие еще задачи создают большую нагрузку на процессор, и насколько легко их можно разделить по процессорам?
Статистика? Базы данных?

Здравствуйте, AndreyFedotov, Вы писали:

AF>Идею смены архитектуры полностью поддерживаю, так как по-моему назрела она давно.
AF>А вот по поводу способов — как это можно сделать — вызывают большие сомнения.

AF>Начну с самой очевидной идеи распараллеливания — кучи процессоров с собственной памятью. Идея прекрасная и давным-давно уже применяется. Великолепно работает, когда нужно провести много идентичных вычислений, особенно для тех алгоритмов, которые допускают разбиение на отдельные и распараллеливаемые фрагменты (вот как те же матрицы). Однако далеко не все алгоритмы столь хороши. Есть случаи, когда скорость вычислений будет расти как логарифм от числа процессоров. А добиться увеличения производительности в 6-10 раз, за счёт миллиона процессоров — может быть несколько накладно... Это главное препятствие математического плана.

Да есть алгоритмы где этого не добиться. Ну например, когда одна из подзадач должна работать значительно большее время чем остальные. И прогнозировать время выполнения практически невозможно. Но большинство применяемых алгоритмов хорошо ложатся под разделяй и властвуй.

AF>Теперь о программировании. Идея написания языка, который автоматически обеспечивал бы распараллеливание (или хотя бы облегчал его) — витает очень давно. И попытки создать такой язык предпринимались неоднократно — вспомнить хотя бы бум вокруг транспьютеров и языки программирования, которые были для них созданы. И хотя некоторый прогресс и был достигнут — до серебряной пули или базового решения, которое можно было бы использовать, как основу для новой технологии, оказалось довольно далеко. Оказалось, что для достижения действительно высоких результатов от разработчика требуется квалификация и трудозатраты идентичные тем, что требуются для обеспечения параллелизма на обычных языках. То есть — весьма существенные. И это является главным препятствием. Где то я видел оценку, по которой написание и отладка многопоточного (распараллеливаемого кода) получалась от 10 до 50 раз дороже, чем написание кода обычного — однопоточного.
Но вот с этим несогласен. При текущих мейнстримовых языках, писать многопоточные приложение действительно нелегко. А особенно отлаживаться. Но возьмем к примеру функциональный язык. Он вынуждает программиста не держать состояний за пределами функций. В результате, мы можем прозрачно накормить каждый процессор данной подпрограммой. Но для этого нужно чтобы и OS и процессор знали что такое подпрограмма. То есть, нужно не тупое выполнение последовательности инструкций, нужно выполнение именно подпрограмм.
AF>Хотите проверить — напишите многопоточную сортировку, которая будет работать быстрее однопоточной
Вот как раз quick сортировку описать действительно легко. Только я этого делать не буду. Потому как нет удобных средств распараллеливания. Я вообще не хочу заниматься распараллеливанием. Пускай этим будет заниматься компилятор и OS. У них достаточно знаний для этого.

AF>К вопросу о шинах между процессором и памятью. Взгляд совершенно здравый — они действительно являются зачастую узким местом в системе. И их действительно нужно распараллеливать. Однако это не обязательно требует распараллеливания процессоров. Можно увеличить количество шин между процессором и памятью не увеличивая количество ядер. При определённом подходе это даст хороший прирост производительности, особенно, если в пересылку данных одновременно с процессором вовлечены другие устройства или процессоров – несколько. Впрочем, и эта технология сейчас активно применяется.
Сейчас разговор идет именно о mainstream. В действительности производители уже отошли от увеличения разрядности шины к алгоритмам одновременного доступа. Но говорить что DDR действительно эффективен, по моему, нельзя. Это попытка остаться в рамках текущих технологий. Тут нужны более целенаправленные и эффективные меры, для которых нынешняя архитектура не особо подходит.

AF>В общем-то, очевидно, что сейчас распараллеливание (и ядер и шин и отдельных процессором) является основной технологией и создание средств, которые обеспечивали бы её использование (в том числе и новых языков) – весьма востребовано. Однако как раз в области языков особо новых идей пока и не видно. Хотя возможно вместе до чего и додумаемся.
Честно говоря работа в данной области ведется и не останавливалась. Можно вспомнить гугловские кластеризованные серваки. Или comega.

С уважением, Gleb.

Здравствуйте, Дарней, Вы писали:

Д>Компьютерная графика, например — прекрасно распараллеливается
Д>Интересно — а какие еще задачи создают большую нагрузку на процессор, и насколько легко их можно разделить по процессорам?
Я думаю, что в основном сортировка, поиск, и обработка больших массивов. В остальном производительность процессора избыточна. Для первых двух распараллеливание подходит на 100 процентов. Для обработки больших массивов, частично тоже.
Д>Статистика? Базы данных?
Для баз данных эта проблема уже решена. У них свои алгоритмы распараллеливания. Они разбивают запрос на подзапросы, и раздельно выполняют. Но они и дальше развиваются. Например — здесь. Там было определено дальнейшее развитие теории БД. Отдельным пунктом идет Sensor Data and Sensor Networks. Гугловкий сервак параллелен по самое нехочу. Точно знаю что ведутся работы по разложению XQuery запросов на подзапросы, и раздельное выполнение.

С уважением, Gleb.

Здравствуйте, GlebZ, Вы писали:

GZ>Но вот с этим несогласен. При текущих мейнстримовых языках, писать многопоточные приложение действительно нелегко. А особенно отлаживаться. Но возьмем к примеру функциональный язык. Он вынуждает программиста не держать состояний за пределами функций. В результате, мы можем прозрачно накормить каждый процессор данной подпрограммой. Но для этого нужно чтобы и OS и процессор знали что такое подпрограмма. То есть, нужно не тупое выполнение последовательности инструкций, нужно выполнение именно подпрограмм.

Так устроены шейдеры в последних поколениях GPU. Это некая подпрограмма, выполняемая для каждого вертекса или пиксела. Они не то что бы очень быстрые, но зато "дуют в 32 струи". Но, со всеми вытекающими — например, сметить подпрограмму шейдера — операция сравнительно дорогая. И там тоже много засад, где можно свести на нет все усилия по распараллеливанию.

http://www.rsdn.ru/Forum/Message.aspx?mid=1410129&only=1

Автор: McSeem2
Дата: 29.09.05

Можно представить себе следующую схему (я, кстати говоря, еще лет 15 назад о такой мечтал). У нас есть светодиодная матрица 8000x6000. Под каждым пикселом находится маленький процессор и сотня байт памяти. Этот процессор умеет выполнять операцию AlphaBlend. В продвинутых случаях — остальные color compositing операции. Управляются эти процессоры строчно-столбцовым способом. Типа "открыть порт для передачи данных по всей строке номер 1343 — передать данные в колонку 2345". Таким образом мы засветили один пиксел. Закраска прямоугольника 1000x1000 при этом требует не миллион итераций, а всего-навсего 1000+1000. Anti-aliasing при таком разрешении нам не нужен и это сильно упрощает дело. Кроме того, каждый пиксел может сам себе быть альфа-маской и/или z-буфером.

Да, очень многие операции поддаются распараллеливанию таким образом. Но не все. Например, что делать, если нам нужно смасштабировать изображение с передискретизацией (resample)? — это основная операция в современных 3D-акселераторах? Надо, что бы кажый элементарный процессор как минимум имел доступ к некой общей памяти или должна быть некая сеть для коммуникации. А вот это уже очень нетривиально обеспечить. Я бы даже сказал, что практически невозможно — количество проводов растет по квадратичному закону.

Но это все в общем-то тривиально — есть вещи гораздо более удивительные. Как бы мы ни наращивали число процессоров — тысячи, миллионы, миллиарды — не имеет значения. Это все жалкие копейки для ряда задач (весьма обширного, кстати). Типичная задача — разложение большого числа на простые сомножители. Если мы задействуем 1000 процессоров с недостижимым коэффициентом распараллеливания в 1.0, мы всего-навсего можем разложить число в 1000 раз большее (грубо говоря три лишние десятичные цифры). Каковы усилия и каков результат?!
Данная задача является вообще не решаемой на машине Тьюринга. И даже на параллельной машине Тьюринга. Казалось бы, она вообще не решается. Однако, математики доказали, что алгоритм Шора позволяет разложить натуральное число n на простые множители за полиномиальное от n время. Но для этого требуется квантовый компьютер. Здесь я боюсь скатиться в дебри, но раз доказано, что алгоритм Шора работает (не имеет значения, что он пока нереализуем на практике), то откуда "черпается" вся эта вычислительная мощность в квантовом мире?! Согласно гипотезе о мультиверсе, в процессе квантового вычисления принимает участие совершенно невообразимое количество параллельных вселенных (юниверсов), скажем, 10^500. И посредством интерференции мы можем "вытащить" результат в наш мир. Убойная трава у этих физиков растет!

Это я не к тому, чтобы рассуждать на темы множественности миров, а лишь к тому, чтобы подумать — а возможно ли что-то принципиально новое в обычном (неквантовом) вычислительном мире? Мне сдается, что все, что мы можем — лишь наращивать мускулы. Никуда не уйти от банальной машины Тьюринга, сколько бы процессоров мы ни приделывали. Грубо говоря, функциональный язык, распараллеливающий вычисления на 1000 процессоров, всего-навсего эквивалентен процедурному языку, работающему на процессоре в 1000 раз более шустром. То есть, игра с исусственным распараллеливением не стоит свеч. Да, для ряда задач это хорошо и правильно, например, для 3D акселераторов. Но не в качестве универсального вычислителя. У меня есть большие сомнения, что это вообще возможно — построить универсальную машину на принципах искусственного распараллеливания. Распаралеливание должно быть естественным, природным — вот как в теории квантовых вычислений. И вот там, возможно (но не гарантировано), удастся не только создать универсальную параллельную машину, но и решать принципиально новые задачи.

Здравствуйте, GlebZ, Вы писали:

А новый ibm'овский процессор cell (http://www.3dnews.ru/cpu/cell/) это не то что ты хочешь?

Здравствуйте, Дарней, Вы писали:


Д>Компьютерная графика, например — прекрасно распараллеливается

Графику в современых GPU уже аппаратно распаралелили так что вроде дальше некуда

Здравствуйте, McSeem2, Вы писали:

MS>Так устроены шейдеры в последних поколениях GPU. Это некая подпрограмма, выполняемая для каждого вертекса или пиксела. Они не то что бы очень быстрые, но зато "дуют в 32 струи". Но, со всеми вытекающими — например, сметить подпрограмму шейдера — операция сравнительно дорогая. И там тоже много засад, где можно свести на нет все усилия по распараллеливанию.
Занятно, но к сожалению слишком специализированно. А так хочется мэйнстрима.

MS>http://www.rsdn.ru/Forum/Message.aspx?mid=1410129&only=1

Автор: McSeem2
Дата: 29.09.05

Блин, забыл ссылки сделать на сообщение. Именно твое сообщение и дало толчок на написания топика.

MS>Да, очень многие операции поддаются распараллеливанию таким образом. Но не все. Например, что делать, если нам нужно смасштабировать изображение с передискретизацией (resample)? — это основная операция в современных 3D-акселераторах? Надо, что бы кажый элементарный процессор как минимум имел доступ к некой общей памяти или должна быть некая сеть для коммуникации. А вот это уже очень нетривиально обеспечить. Я бы даже сказал, что практически невозможно — количество проводов растет по квадратичному закону.
Нет, это неоптимальность алгоритмов. Во первых, можно ввести принцип достаточности. То бишь, главное чтобы на стыках не било в глаза. И разделить изображение на несколько(как это делается например в фотошопе и фотопаинте), обработать отдельно в промежуточные результаты, и смешать результаты. Возможно что разделенная память не нужна. Нужно окно с помощью которого можно указать что данные в этом окне не должны быть доступны другому процессору. Чтобы не надо было их синхронизировать. В общем творчество.

MS>Но это все в общем-то тривиально — есть вещи гораздо более удивительные. Как бы мы ни наращивали число процессоров — тысячи, миллионы, миллиарды — не имеет значения. Это все жалкие копейки для ряда задач (весьма обширного, кстати).
Миллионы процессоров? Это ты хватанул. Сейчас иметь и 4 проца накладно. А вообще, достаточно и 4 процессоров, только если они будут на mainstream компьютерах, и их ресурсы будут загружены. Операционке на рабочей станции, такое загрузить не подсилу. Это нужно делать явно компилятору и программисту.
Я не предлагаю решать проблемы вселенского масштаба. Я предлагаю решать проблемы именно сейчас стоящие. Скажу даже — бизнес приложений, как наиболее часто встречающихся.
С одной стороны, для бизнес-приложений процессор сейчас не загружен. Но его и не хватает в тех особых случая когда нужна математика. Какие задачи в основном стоят — преобразования большого количества данных, сортировки, поиск. В любом из этих случаев существующие распараллеленые алгоритмы разделяй и властвуй будут выполнятся значительно быстрее и эффективней.

MS>Это я не к тому, чтобы рассуждать на темы множественности миров, а лишь к тому, чтобы подумать — а возможно ли что-то принципиально новое в обычном (неквантовом) вычислительном мире? Мне сдается, что все, что мы можем — лишь наращивать мускулы. Никуда не уйти от банальной машины Тьюринга, сколько бы процессоров мы ни приделывали. Грубо говоря, функциональный язык, распараллеливающий вычисления на 1000 процессоров, всего-навсего эквивалентен процедурному языку, работающему на процессоре в 1000 раз более шустром. То есть, игра с исусственным распараллеливением не стоит свеч. Да, для ряда задач это хорошо и правильно, например, для 3D акселераторов. Но не в качестве универсального вычислителя. У меня есть большие сомнения, что это вообще возможно — построить универсальную машину на принципах искусственного распараллеливания. Распаралеливание должно быть естественным, природным — вот как в теории квантовых вычислений. И вот там, возможно (но не гарантировано), удастся не только создать универсальную параллельную машину, но и решать принципиально новые задачи.
Maybe, но меня интересует именно универсальный вычислитель, именно сейчас и именно в контексте mainstream. Сейчас уже несмотря на квазипараллельность, мы уже подходим к тому что у нас будут почти полноценные процессоры(например двухядерные) которые будут стоять на рабочих станциях. Но в то же время, мы имеем то, что для того чтобы работать с этой параллельностью, мы рискуем словить кучу непонятных ошибок. И в текущем случае, мы получим машину(например если брать двухядерный проц), загруженную на 50 процентов. И нет предпосылок на более полную загрузку машины, поскольку и архитектура этому не способствует(проблема shared memory, которая решается остановкой всех процессоров), и компиляторы нам отнюдь не помогают. Но ничего невозможного и нереального я здесь не вижу. Просто я пока точно не могу сказать как.

С уважением, Gleb.

Здравствуйте, GlebZ, Вы писали:

GZ>Здравствуйте, McSeem2, Вы писали:

MS>>Так устроены шейдеры в последних поколениях GPU. Это некая подпрограмма, выполняемая для каждого вертекса или пиксела. Они не то что бы очень быстрые, но зато "дуют в 32 струи". Но, со всеми вытекающими — например, сметить подпрограмму шейдера — операция сравнительно дорогая. И там тоже много засад, где можно свести на нет все усилия по распараллеливанию.
GZ>Занятно, но к сожалению слишком специализированно. А так хочется мэйнстрима.

Люди на GPU уже математические расчеты делают,которые к графике ни как ни относятся

Здравствуйте, FR, Вы писали:

FR>А новый ibm'овский процессор cell (http://www.3dnews.ru/cpu/cell/) это не то что ты хочешь?
Ага, именно то. Теперь остался вопрос в том, каким должен быть язык для его эффективного использования.

С уважением, Gleb.

Здравствуйте, GlebZ, Вы писали:

GZ>Здравствуйте, FR, Вы писали:

FR>>А новый ibm'овский процессор cell (http://www.3dnews.ru/cpu/cell/) это не то что ты хочешь?
GZ>Ага, именно то. Теперь остался вопрос в том, каким должен быть язык для его эффективного использования.

С языком проблемы, зато распрастранение этот процессор получит большое sony его испоолльзует в своей новой игровой консоли. Microsoft в своем Xbox 360 вместо cell использует практически нечто очень похожее:

Специальный процессор IBM PowerPC: 3 симметричных ядра на частоте 3.2 ГГц; 2 хардварных "потока" на каждое ядро; 3 векторных сопроцессора VMX-128, по одному на каждое ядро; 128 регистров VMX-128 на каждый "хардварный" поток; кэш второго уровня на 1 Мбайт

(http://www.dtf.ru/articles/read.php?id=4011)

А программистам ms в своих рекомендацих на разработку игр под новые конслоли предлагает как можно сильнее распаралеливать программы

Здравствуйте, GlebZ, Вы писали:

GZ>Занятно, но к сожалению слишком специализированно. А так хочется мэйнстрима.

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

GZ>Нет, это неоптимальность алгоритмов. Во первых, можно ввести принцип достаточности. То бишь, главное чтобы на стыках не било в глаза. И разделить изображение на несколько(как это делается например в фотошопе и фотопаинте), обработать отдельно в промежуточные результаты, и смешать результаты. Возможно что разделенная память не нужна. Нужно окно с помощью которого можно указать что данные в этом окне не должны быть доступны другому процессору. Чтобы не надо было их синхронизировать. В общем творчество.

Дык вся проблема-то в том, что очень часто нельзя разбить на области — эти области пересекаются. Но ты правильно заметил, что это — именно творчество. Компилятор вряд ли это сделает. Ну или нужен очень творческий компилятор!

GZ>Миллионы процессоров? Это ты хватанул.

Это я не просто "хватанул". Я даже посмею утверждать, что для ряда задач это никак не поможет. И это — никакие не задачи "вселенского масштаба" — они очень даже практические.

GZ>С одной стороны, для бизнес-приложений процессор сейчас не загружен. Но его и не хватает в тех особых случая когда нужна математика. Какие задачи в основном стоят — преобразования большого количества данных, сортировки, поиск. В любом из этих случаев существующие распараллеленые алгоритмы разделяй и властвуй будут выполнятся значительно быстрее и эффективней.

Есть такое дело. Проблема, как мне кажется, в том, что это практически нереально — достичь универсального параллелизма. Во всяком случае, до сих пор этого никому не удавалось, хотя все стараются очень и очень сильно (а уж для супекомпьютеров — ух как стараются!). Чтобы уметь автоматически утилизировать параллельные ресурсы, наш гипотетический творческий компилятор должен знать все взаимосвязи между всеми данными! Иными словами, он должен уметь разгадать замысел программиста. На практике это просто нереально (возможно в квантовом мире это реально, но здесь я рассуждаю лишь на уровне дилетанта). Чем хороша машина Тьюринга? — тем, что это априорное знание в ней сведено до минимума! Машина понятия не имеет о взаимосвязях — она знай себе молотит инструкции. Именно поэтому она и является в принципе работоспособной. Как только мы пытаемся что-то распараллелить, сразу появляется другая задача — "объяснить" машине все возможные взаимосвязи (что от чего у нас зависит). А это может быть гораздо сложнее самой задачи. Поэтому, все, что возможно — это строить специализированные параллельные железки — блок пиксельных шейдеров, блок параллельной сортировки, блок матричных вычислений. То есть, такие, в которых данные либо не являются взаимосвязанными, либо эти взаимосвязи можно заранее описать.

Фактически, чем занимается универсальная машина Тьюринга — выполнение программы как раз и устанавливает (вычисляет) эти взаимосвязи. Но ни сама машина, ни программа для нее не знают этих взаимосвязей заранее в общем случае. Установить эти взаимосвязи — и есть цель вычисления. А при универсальном распараллеливании получается, что надо установить (вычислить) все взаимосвязи до выполнения самого вычисления! Я еще раз повторю — это характерно только для универсального случая. В специализированных случаях машина заранее "что-то знает".

В случае универсальной параллельной машины можно работать лишь в направлении гадания — "а попробуем-ка мы забежать вперед и вычислить вот это параллельно вот этому". А потом смотрим, а не случилось ли у нас некой коллизии. Если случилось — ничего не поделаешь, надо откатываться назад и переделывать всю работу. Это, кстати и делается в современных процессорах — все эти branch prediction и прочее. Вот все, что мы можем себе позволить в случае (повторюсь) универсальной машины. Но здесь из за необходимости переделывать уже сделанную работу (в результате коллизий), коэффициент утилизации резко падает с увеличением количества параллельных потоков. Я рискну предположить, что это и есть фундаментальное свойство универсальной параллельной машины.

GZ>Maybe, но меня интересует именно универсальный вычислитель, именно сейчас и именно в контексте mainstream. Сейчас уже несмотря на квазипараллельность, мы уже подходим к тому что у нас будут почти полноценные процессоры(например двухядерные) которые будут стоять на рабочих станциях. Но в то же время, мы имеем то, что для того чтобы работать с этой параллельностью, мы рискуем словить кучу непонятных ошибок. И в текущем случае, мы получим машину(например если брать двухядерный проц), загруженную на 50 процентов. И нет предпосылок на более полную загрузку машины, поскольку и архитектура этому не способствует(проблема shared memory, которая решается остановкой всех процессоров), и компиляторы нам отнюдь не помогают. Но ничего невозможного и нереального я здесь не вижу. Просто я пока точно не могу сказать как.

Это чем-то напоминает принцип неопределенности. Смотри что получается. В идеале, хотелось бы писать последовательный набор инструкций (на том же C++), который бы автоматически распараллеливался с максимально возможной утилизацией. Но это нереально. Можно пойти на уступки и возложить часть задачи по распараллеливанию на программиста (при помощи специального языка). Можно вообще ничего не делать и полностью положиться на человека — как сейчас, для программирования тех же пиксельных шейдеров. Так вот, чем больше у нас появляется автоматизма, тем менее эффективно работает вся система. И 100%-ная автоматизация приближает эффект от распараллеливания к нулю.

Впрочем, я согласен с тем, что некий промежуточный вариант автоматизации принес бы значительную пользу. Но он все равно останется специализированным. Я лишь пытаюсь обосновать свою точку зрения, что универсальный параллельный компьютер в нашем неквантовом мире построить нереально.

Здравствуйте, FR, Вы писали:

FR>Люди на GPU уже математические расчеты делают,которые к графике ни как ни относятся

Но что бы там они не расчитывали, для параллельной сортировки это все равно непригодно. Следовательно, не является универсальным.

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, FR, Вы писали:

FR>>Люди на GPU уже математические расчеты делают,которые к графике ни как ни относятся

MS>Но что бы там они не расчитывали, для параллельной сортировки это все равно непригодно. Следовательно, не является универсальным.

Ну никто ни обещал панауею
А вообще много что считают: http://www.gpgpu.org/
Если посмотреть на тот же Cell то производители процессоров уже предложили паралельную архитектуру, и не совсем классическую, а так как закон Мура похоже споткнулся, то хочешь не хочешь а придется все распаралеливать.

Здравствуйте, FR, Вы писали:

FR>Графику в современых GPU уже аппаратно распаралелили так что вроде дальше некуда

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

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, FR, Вы писали:

FR>>Графику в современых GPU уже аппаратно распаралелили так что вроде дальше некуда

MS>Распараллелили не графику, а всего-лишь видеоэффекты. Все эти шейдеры почти никак не помогают нарисовать банальную полилинию — произвольной толщины, с заданным line join, с субпиксельной точностью и хорошим качеством сглаживания.

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

Здравствуйте, FR, Вы писали:

FR>Так на 2D производители видеокарт давно плюнули, и вроде на всех современных карточках линии эмулируются через треугольники.

В том-то и дело. И бедным игрушечникам приходится много чего рендерить на CPU для UI. Я сейчас сотрудничаю с http://scaleform.com, так вот, быстро и качественно отрендерить сцену из Flash SWF — это очень нетривиальная задача. И вряд ли в ближайшие годы это удастся сделать с более высоким качеством, чем обеспечивает сам Flash. Быстрее — да, несомненно, но качество сглаживания оставляет желать лучшего. И утилизировать мощь GPU для улучшения качества при этом не получается.

McSeem2 wrote:

> Есть такое дело. Проблема, как мне кажется, в том, что это практически
> нереально — достичь *универсального* параллелизма. Во всяком случае,
> до сих пор этого никому не удавалось, хотя все стараются очень и очень
> сильно (а уж для супекомпьютеров — ух как стараются!). Чтобы уметь
> автоматически утилизировать параллельные ресурсы, наш гипотетический
> творческий компилятор должен знать все взаимосвязи между всеми данными!

Это элементарно делается в чистых функциональных языках — у них есть
такое свойство, как ссылочная целостность. Erlang — фактически полностью
универсально параллелен, да еще и вполне практичен при этом (применяется
в телефонных коммутаторах).

--
С уважением,
Alex Besogonov (alexy@izh.com)

Здравствуйте, Cyberax, Вы писали:


C>Это элементарно делается в чистых функциональных языках — у них есть
C>такое свойство, как ссылочная целостность. Erlang — фактически полностью
C>универсально параллелен, да еще и вполне практичен при этом (применяется
C>в телефонных коммутаторах).

Интересно. Однако, позволю себе усомниться, что он "полностью универсально параллелен". Это бы фактически означало, что такие задачи как, например:
— перемножение матриц
— линейный поиск в списке
— сортировка
— разложение числа на простые сомножители
формулируются на этом языке одинаково легко и одинаково легко поддаются распараллеливанию. Я специально выбрал такой список задач, который на классическом процедурном языке приблизительно одинаков по сложности кодирования (для разложения чисел мы не берем всякие "хитрые" алгоритмы — берем самый тривиальный). Теперь два вопроса:

1. Какова дисперсия по сложности кодирования всех этих задач на Erlang?
2. Насколько хорошо все эти задачи поддаются распараллеливанию на реальном железе?

Только в случае малой дисперсии и хорошего коэффициента утилизации при работе на тысячах процессоров, можно говорить об универсальности — и вот оно, всеобщее "ЩАСТЕ". Но есть сильные сомнения, что это так.