Меня в этом вопросе интересовала реализация этого дела и организация ран-тайм системы поддержки. Поэтому со своей стороны могу дать ссылки, касающиеся именно реализации:
Lazy Threads: Compiler and Runtime Structures for Fine-Grained Parallel Programming: http://www.eecs.berkeley.edu/Pubs/TechRpts/1997/CSD-97-975.pdf
По поводу "автоматически распараллеливаемого кода". Это, конечно, очень громко сказано. Параллельные диалекты Lisp (QLisp, Multilisp etc) существуют с начала 80-ых годов, однако никакого "автоматического распараллеливания" нет и по сей день.
Непосредственно "автоматическое распараллеливание" сейчас есть только для *очень* ограниченного круга задач. Например, компилятор успешно выделяет "цикл" (легко), и успешно понимает, что все итерации независимы (сложно, в общем случае — невыполнимо), тогда компилятор может сгенерировать "параллельный" код. Очевидно, что полагаться на это в промышленной разработке *нельзя*, это не более, чем "игрушка".
"Псевдо-автоматическое распараллеливание" возможно, когда пользователь явно указывает в программе "потенциальный" параллелизм, а компилятор/ран-тайм заставляют его реально выполняться параллельно. К этому типу относятся все эти lazy-вычисления, futures, активные объекты и т.д. Но фактически тут вся работа остаётся на программисте. У компилятора тут маленькая задача. У компилятора тут, как ни странно, задача даже больше не "сделать" параллелизм, а "подавить" параллелизм.
Для таких областей, как, например, серверное ПО, ни о каком "автоматическом распараллеливании" говорить не приходится. И на горизонте ничего не предвидится. Тут всё, начиная от архитектуры и заканчивая структурами данных, лежит полностью на разработчике.
Так же такие области, как game-dev, где требуется 100% отдача от железа, не полагаются на автоматическое распараллеливание. Т.к. тут не устраивает ситуация, что "компилятор наверное что-то как-то распараллелит".
Здравствуйте, remark, Вы писали:
R>Меня в этом вопросе интересовала реализация этого дела и организация ран-тайм системы поддержки. Поэтому со своей стороны могу дать ссылки, касающиеся именно реализации: R>Lazy Threads: Compiler and Runtime Structures for Fine-Grained Parallel Programming: R>http://www.eecs.berkeley.edu/Pubs/TechRpts/1997/CSD-97-975.pdf
R>Cilk: An Efficient Multithreaded Runtime System: R>http://supertech.csail.mit.edu/papers/cilkjpdc96.pdf
Спасибо за ссылки!
R>"Псевдо-автоматическое распараллеливание" возможно, когда пользователь явно указывает в программе "потенциальный" параллелизм, а компилятор/ран-тайм заставляют его реально выполняться параллельно. К этому типу относятся все эти lazy-вычисления, futures, активные объекты и т.д. Но фактически тут вся работа остаётся на программисте. У компилятора тут маленькая задача. У компилятора тут, как ни странно, задача даже больше не "сделать" параллелизм, а "подавить" параллелизм.
Конечно, совсем автоматического распараллеливания, наверное никогда не будет, тут я каюсь слишком громко выразился.
R>Так же такие области, как game-dev, где требуется 100% отдача от железа, не полагаются на автоматическое распараллеливание. Т.к. тут не устраивает ситуация, что "компилятор наверное что-то как-то распараллелит".
Я вот ещё, что имел ввиду, затронув тему автоматизации распараллеливания, в свете будущих перспектив промышленного программирования для работы с многопроцессорными (многоядерными) системами.
Существуют прогнозы, что в ближайшее время (5, 10 лет) нас ожидает скачкообразный рост количества ядер на одном процессоре, вплоть до нескольких сотен ядер где-нибудь к 2015 году. Собственно, например архитектуру Cell или GPGPU можно рассматривать как первую ласточку. А несколько десятков ядер уже есть даже в Roadmap-ах производителей.
Хотя программы с мультипараллельными вычислениями пишут уже довольно давно, ведь кластеры, суперкомпьютеры и сети распределённых вычислений (вроде SETI) появились не сегодня, писать их сложнее и дороже, чем обычные, да и количество программистов, способных их написать невелико. Здесь же имеющийся опыт "обычных" пограммистов не всегда поможет, написание даже двух- четырех-поточной программы для истинно параллельного исполнения на нынешних двух-четырех-ядерниках уже имеет свои тонкости.
В этой связи языки и технологии, вроде Haskell, Lisp с параллельным исполнением и т.п., которые сейчас слишком расточительно расходуют ресурсы, могут оказаться востребованными. Если код на них работает, допустим в 5 — 10 — 20 раз медленее, чем на Си это часто неприемлемо медленно, особенно в вычислительных задачах, но если они позволят программисту быстро написать параллельно исполняющуюся программу на 1600 ядрах это будет всё-равно в 160 раз эффективнее, чем работа однопоточной программы.
То есть в случае массового распространения сильно многоядерных систем может быть экономически оправдано легкое распараллеливание и не беда, что эффективность может оказаться в размере 10% от пиковой, будет полно задач, где это допустимо.
Здравствуйте, Michael7, Вы писали:
M>В этой связи языки и технологии, вроде Haskell, Lisp с параллельным исполнением и т.п., которые сейчас слишком расточительно расходуют ресурсы, могут оказаться востребованными. Если код на них работает, допустим в 5 — 10 — 20 раз медленее, чем на Си это часто неприемлемо медленно, особенно в вычислительных задачах, но если они позволят программисту быстро написать параллельно исполняющуюся программу на 1600 ядрах это будет всё-равно в 160 раз эффективнее, чем работа однопоточной программы.
У вас 1600 ядер? Мы поможем вам загрузить их все своими медленными программами!
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, Michael7, Вы писали:
R>Так же такие области, как game-dev, где требуется 100% отдача от железа, не полагаются на автоматическое распараллеливание. Т.к. тут не устраивает ситуация, что "компилятор наверное что-то как-то распараллелит".
R>No silver bullet!
Меня интересует, как будет делаться делается ручное распараллеивание, скажем, на 100 ядрах. Том Свини, один из авторов Unreal как раз говорит, что с увеличением количества ядер на стандартном декстопе и возвращении к программному рендерингу будут востребованы новые технологии программировнаия. Интервью здесь:
Здравствуйте, Michael7, Вы писали:
M>Существуют прогнозы, что в ближайшее время (5, 10 лет) нас ожидает скачкообразный рост количества ядер на одном процессоре, вплоть до нескольких сотен ядер где-нибудь к 2015 году.
Тут речь как я понимаю идет не о ядрах их сильно больше десятка на один кристал весьма проблематично засунуть. А о аппаратных потоках.
Это немного разные вещи.
Цель аппаратчиков заставить АЛУ работать. Ибо сейчас из-за промахов кеша АЛУ очень часто простаивает. Мне удавалось разгонять алгоритмы укатывая их под кешь процессора от 2 до 100 раз.
Что хотят сделать аппаратчики: Они планируют сделать ядра максимально тупыми (никакого переупорядочивания комманд, спекулятивных вычислений и прочей магии...) за счет этого можно сильно уменьшить размер ядра и уменьшить штрафы вызванные ошибками предсказаний. После чего на ядре запускают 8-16 аппаратных потоков которые переключаются каждый такт. Если поток промазал мимо кеша то ничего страшного... его просто будут пропускать пока данные не приползут в кеш. Таким образом можно гораздо лучше загрузить АЛУ.
Мои размышления на тему (я в разработке процессоров ничего не понимаю по этому можно не читать):
Еще можно сделать 3 типа АЛУ на ядре.
1)Занимается условными и без условными переходами. Чтением/записью в память. Барьеры памяти. И всем остальным что связано с работой с памятью.
2)Целочисленная арифметика.
3)Арифметика с плавающей точкой.
Таким образом у потока может быть 4 состояния
1)Не готов. (Промазал мимо кеша или просто делать нечего.)
2, 3, 4)Комманда для соответствующего АЛУ.
Соответственно шедуллер каждого из АЛУ выберает следующей поток с коммандой для этого АЛУ.
Если немного усложнить шедуллер и добавить приоритеты можно будет делать совсем веселые вещи.
Допустим если сделать 4 уровня приоритетов то высший (3) резервируем за процессором (см дальше), 2 допустим можно назначать обработчикам аппартаных прирываний, 1 реалтайм потокам и 0 нереалтайм потоками.
Ни о какой сраведливости задумываться не надо это работа ОС. Просто АЛУ переключается между своими потоками с максимальным приоритетом.
Комманда lock N, Rx, Ry
Лочит одну или 2 линейки кеша (в которые попадают адреса из регистров Rx и Ry) на время выполнения следующих N (скажем до 16 комманд).
Под локом можно обращаться только к залоченным частям памяти и делать только переходы вперед (никаких циклов под локом) и ессно никаких локов под локом.
Если в одной линейке кеша есть несколько ячеек памяти которые нас интересуют то достаточно указать адрес одной из них но обращаться можно ко всем ибо всеравно вся линейка кеша залочена.
Захвативший лок поток на время выполнения лока получает высший приоритет (ибо лок нужно отпустить как можно быстрее).
Одновременно может выполняться только один лок на одном ядре.
Примеры:
AtomicIncrement
lock 3, r1, r1
ld r1 -> r2
add r2, 1
st r2 -> r1
AtomicCompareExchange
lock 4, r1, r1
ld r1 -> r2
cmp r2, r3
jne end
st r4 -> r1
end:
AtomicSwap
lock 4, r1, r2
ld r1 -> r3
ld r2 -> r4
st r4 -> r1
st r3 -> r2
Думаю на этом базисе можно сделать очень много различных структур данных.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
> В этой связи языки и технологии, вроде Haskell, Lisp с параллельным > исполнением и т.п., которые сейчас слишком расточительно расходуют > ресурсы, могут оказаться востребованными. Если код на них работает, > допустим в 5 — 10 — 20 раз медленее, чем на Си это часто неприемлемо > медленно, особенно в вычислительных задачах, но если они позволят > программисту быстро написать параллельно исполняющуюся программу на 1600 > ядрах это будет всё-равно в 160 раз эффективнее, чем работа однопоточной > программы. > > То есть в случае массового распространения сильно многоядерных систем > может быть экономически оправдано легкое распараллеливание и не беда, что > эффективность может оказаться в размере 10% от пиковой, будет полно задач, > где это допустимо.
Проблема в том, что для реализации такого сценария понадобится
1600-канальная память и 1600 хотя бы полумегабайтных кэшей. Иначе программа
у вас будет не в 160 раз эффективнее, а, например, в 2 раза. Или вообще
медленнее однопоточной. IMHO.
Posted via RSDN NNTP Server 2.1 beta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Здравствуйте, eao197, Вы писали:
E>У вас 1600 ядер? Мы поможем вам загрузить их все своими медленными программами!
Закон eao-remark'а:
Для обеспечения адекватной загрузки аппаратных ресурсов, при увеличении кол-ва ядер в N раз, эффективность программы должна падать как минимум в N раз.
Первое следствие из закона eao-remark'а:
Эффективность программ падает в 2 раза каждые 18 месяцев.
Здравствуйте, LaPerouse, Вы писали:
LP>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, Michael7, Вы писали:
R>>Так же такие области, как game-dev, где требуется 100% отдача от железа, не полагаются на автоматическое распараллеливание. Т.к. тут не устраивает ситуация, что "компилятор наверное что-то как-то распараллелит".
R>>No silver bullet!
LP>Меня интересует, как будет делаться делается ручное распараллеивание, скажем, на 100 ядрах. Том Свини, один из авторов Unreal как раз говорит, что с увеличением количества ядер на стандартном декстопе и возвращении к программному рендерингу будут востребованы новые технологии программировнаия. Интервью здесь:
Новые технологии нужны. Но новые технологии — это *не* автоматическое распараллеливание.
Да в принципе и новых технологий-то особо не нужно. Всё уже давно есть — Cilk, CSP, Erlang, активные объекты, агентно-ориентированные системы и т.д. Просто надо реализовать это нормально. Для людей.
Valve, например, уже пепеписал свой движок для поддержки многоядерных процессоров. Ничего принципиально нового там нет — ран-тайм + хороший шедулер + выделение потенциального параллелизма пользователем.
Здравствуйте, remark, Вы писали:
R>Новые технологии нужны. Но новые технологии — это *не* автоматическое распараллеливание.
По-момему, автоматический паралеллизм автоматом вытекает из ленивости и чистоты.
1. Отсутствие побочных эффектов.
b = fun1(a)
c = fun2(a)
т к fun1 и fun2 чистые, то результат, возвращаемый ими, не зависит от порядка вызова. И рантайм запускает каждую функцию в своем потоке, к моменту вычисления fun1 результат fun2 может быть вполне вычислен. Чем не автоматический параллелизм?
2. Ленивость. Скажем, параллельно ходу выполнения основного потока в других потоках происходит раскрутка ленивости. Когда потребуются результаты, вместо вычисления всего ленивого кома, просто берет уже вычисленные значения. Чем не автоматический параллелизм?
Все вышесказанное настолько очевидно, что спорить с этим невозможно. Понятно, quckSort таким образом не распараллелить, но реально большое количество операций можно выполнять параллельно. Если учесть, что все это достается задаром (пользователь не догадывается о том, где в какой момент времени сколько будет использоваться потоков, да и вообще сказать это можно только на этапе выполнения), то имхо не стоит просто так отметать преусловутый автопаралеллизм.
PS. Что случилось? Отправлять сообщения из RSDN at home невозможно. "You are bunned". Со вчерашнего дня. И не только у меня, у других из подсетки тоже.
Социализм — это власть трудящихся и централизованная плановая экономика.
Здравствуйте, WolfHound, Вы писали:
M>>Существуют прогнозы, что в ближайшее время (5, 10 лет) нас ожидает скачкообразный рост количества ядер на одном процессоре, вплоть до нескольких сотен ядер где-нибудь к 2015 году. WH>Тут речь как я понимаю идет не о ядрах их сильно больше десятка на один кристал весьма проблематично засунуть. А о аппаратных потоках. WH>Это немного разные вещи. WH>Цель аппаратчиков заставить АЛУ работать. Ибо сейчас из-за промахов кеша АЛУ очень часто простаивает. Мне удавалось разгонять алгоритмы укатывая их под кешь процессора от 2 до 100 раз. WH>Что хотят сделать аппаратчики: Они планируют сделать ядра максимально тупыми (никакого переупорядочивания комманд, спекулятивных вычислений и прочей магии...) за счет этого можно сильно уменьшить размер ядра и уменьшить штрафы вызванные ошибками предсказаний. После чего на ядре запускают 8-16 аппаратных потоков которые переключаются каждый такт. Если поток промазал мимо кеша то ничего страшного... его просто будут пропускать пока данные не приползут в кеш. Таким образом можно гораздо лучше загрузить АЛУ.
Плюс к этому так же добавится асимметричная гетерогенная архитектура. Т.е. NUMA архитектура неизбежна для обеспечения масштабирования. SMP системы от AMD уже являются NUMA. Гетерогенная значит, что ядра будут разные — Cell (PPU + 8 SPU), GPCPU и т.д.
Т.е. предвидится такое вот весёленькое будущее: на одном ядре несколько аппаратных потоков, несколько ядер объединены кэшем L2, несколько этих кэшей объединены кэшем L3, несколько таких процессоров объединены в NUMA узлы, несколько таких узлов объединены коммутатором в систему.
WH>Мои размышления на тему (я в разработке процессоров ничего не понимаю по этому можно не читать): WH>Еще можно сделать 3 типа АЛУ на ядре. WH>1)Занимается условными и без условными переходами. Чтением/записью в память. Барьеры памяти. И всем остальным что связано с работой с памятью. WH>2)Целочисленная арифметика. WH>3)Арифметика с плавающей точкой. WH>Таким образом у потока может быть 4 состояния WH>1)Не готов. (Промазал мимо кеша или просто делать нечего.) WH>2, 3, 4)Комманда для соответствующего АЛУ. WH>Соответственно шедуллер каждого из АЛУ выберает следующей поток с коммандой для этого АЛУ.
Так в принципе уже давно и есть. Современные процессоры содержать модули для сохранений/загрузки из памяти, целочисленные модули, модули для работы с плавающей запятой, причём каждого модули может быть несколько.
WH>Если немного усложнить шедуллер и добавить приоритеты можно будет делать совсем веселые вещи. WH>Допустим если сделать 4 уровня приоритетов то высший (3) резервируем за процессором (см дальше), 2 допустим можно назначать обработчикам аппартаных прирываний, 1 реалтайм потокам и 0 нереалтайм потоками. WH>Ни о какой сраведливости задумываться не надо это работа ОС. Просто АЛУ переключается между своими потоками с максимальным приоритетом.
Здравствуйте, remark, Вы писали:
WH>>Если немного усложнить шедуллер и добавить приоритеты можно будет делать совсем веселые вещи. WH>>Допустим если сделать 4 уровня приоритетов то высший (3) резервируем за процессором (см дальше), 2 допустим можно назначать обработчикам аппартаных прирываний, 1 реалтайм потокам и 0 нереалтайм потоками. WH>>Ни о какой сраведливости задумываться не надо это работа ОС. Просто АЛУ переключается между своими потоками с максимальным приоритетом. R>А как быть с голоданием?
А ни как. Если ОСь выставила высокий приоритет одному из потоков на таком проце то на современных процах (я имею в виду широкораспространенные) шедуллер ОС просто задвинит остальные потоки и все.
Те если у нас всплыл реалтаймовый поток в ядре веб сервер по любому пойдет курить. А тут если этот самый реалтаймовый поток будет промахиваться мимо кеша то веб сервер сможет в это время что-то поделать. А вычислительная задача которая что-то считает с плавучкой тем болие ибо врядли в ядре есть работа с плавучкой.
Единственное нужно для каждого из приоритетов держать свой указатель на последний отработавший с данным приоритетом поток.
Тогда не будет проблем с всплывающим каждые 5 тактов высокоприоритетным потоком.
Шедуллер для линеек кеша ессно должен быть отдельным и работать не на уровне потоков, а на уровне ядер.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Комманда lock N, Rx, Ry WH>Лочит одну или 2 линейки кеша (в которые попадают адреса из регистров Rx и Ry) на время выполнения следующих N (скажем до 16 комманд). WH>Под локом можно обращаться только к залоченным частям памяти и делать только переходы вперед (никаких циклов под локом) и ессно никаких локов под локом. WH>Если в одной линейке кеша есть несколько ячеек памяти которые нас интересуют то достаточно указать адрес одной из них но обращаться можно ко всем ибо всеравно вся линейка кеша залочена. WH>Захвативший лок поток на время выполнения лока получает высший приоритет (ибо лок нужно отпустить как можно быстрее). WH>Одновременно может выполняться только один лок на одном ядре. WH>Думаю на этом базисе можно сделать очень много различных структур данных.
Постановка задачи правильная — дать возможность эффективно реализовывать нетривиальные структуры данных. В каком конкретно виде дать эту возможность — это вопрос.
В принципе, примерно так как ты описываешь — это уже есть.
PERFORM LOCKED OPERATION (PLO)
The PERFORM LOCKED OPERATION instruction
can be used in a multiprogramming or multiprocessing
environment to perform compare, load,
compare-and-swap, and store operations on two
or more discontiguous locations that can be words
or doublewords. The operations are performed as
an atomic set of operations under the control of a
lock that is held only for the duration of the execution
of a single PERFORM LOCKED OPERATION
instruction, as opposed to across the execution
of multiple instructions. Since lock contention
is resolved by the CPU and is very brief,
the program need not include a method for
dealing with the case when the lock to be used is
held by a program being executed by another
CPU. Also, there need be no concern that the
program may be interrupted while it holds a lock,
since PERFORM LOCKED OPERATION will complete
its operation and release its lock before an
interruption can occur.
Команда PLO действует примерно так: вначале ты подгатавливаешь микропрограмму в памяти с описанием всех действий, которые необходимо выполнить атомарно, далее скрамливаешь её PLO, и она говорит — успешно или нет. Вот пример функции добавления элемента в очередь:
LA RT,H Initialize addresses in PL (T = temp)
ST RT,PL+76 Op4 address (address of H)
LA RT,C
ST RT,PL+108 p6 address (address of C)
LA RN,N Address of N
ST RN,PL+60 Initialize op3 in PL (address of N)
LA R1,S PLT address = address of S
------------------------------------------------
SR RS,RS Dummy S. CC1 will probably be set
SR R,R Function code (compare andload)
PLO RS,S,RS,S Obtain S while holding lock
------------------------------------------------
LA R,16 Function code 16 (csdst)
LOOP L RT,H Consistent H
ST RT,OFSTF(,RN) OFSTF = offset of F inN
L RT,C Consistent C
LA RT,1(,RT) C+1
ST RT,PL+92 Initialize op5 in PL (C+1)
LA RSP,1(,RS) RS/RSP = even/odd pair.
S+1 in RSP
PLO RS,S,,PL
BNZ LOOP Br if S changed (if CC not 0)
Интерфейс состоит из двух команд chkpt и commit.
Пример использования:
try_trx:
chkpt on_failure ; начинаем транзакцию
; как параметр передаём адрес, куда перейти в случае провала транзакции
; выполняем "произвольные" нужные действия
commit ; пытаемся закоммитить
; если попали сюда, значит успешно
; в случае ошибки попадём на on_failure
jmp on_success
on_failure:
; можно считать регистр cps (checkpoint status), что бы понять почему провалились
; можно выполнить back-off и т.д.
jmp try_trx
on_success:
; транзакция выполнена успешно и атомарно
Почему я написал — "произвольные" нужные действия. Т.к. набор действий, которые можно выполнить внутри транзакции достаточно ограничен (примерно как ты описал) — нельзя выполнять "особые" инструкции, нельзя вызывать функции, нельзя читать/писать слишком много памяти, нельзя выполняться слишком долго и т.д.
Правда, как показали авторы, алгоритмы "влоб" не начинают магически масштабироваться при использовании HTM. Как и ожидалось. No silver bullet there!
Тем не менее в будущем, конечно, хочется иметь более мощные примитивы нежели чем double-word compare-exchange (cmpxchg16b).
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, remark, Вы писали:
WH>>>Если немного усложнить шедуллер и добавить приоритеты можно будет делать совсем веселые вещи. WH>>>Допустим если сделать 4 уровня приоритетов то высший (3) резервируем за процессором (см дальше), 2 допустим можно назначать обработчикам аппартаных прирываний, 1 реалтайм потокам и 0 нереалтайм потоками. WH>>>Ни о какой сраведливости задумываться не надо это работа ОС. Просто АЛУ переключается между своими потоками с максимальным приоритетом. R>>А как быть с голоданием? WH>А ни как. Если ОСь выставила высокий приоритет одному из потоков на таком проце то на современных процах (я имею в виду широкораспространенные) шедуллер ОС просто задвинит остальные потоки и все. WH>Те если у нас всплыл реалтаймовый поток в ядре веб сервер по любому пойдет курить. А тут если этот самый реалтаймовый поток будет промахиваться мимо кеша то веб сервер сможет в это время что-то поделать. А вычислительная задача которая что-то считает с плавучкой тем болие ибо врядли в ядре есть работа с плавучкой.
WH>Единственное нужно для каждого из приоритетов держать свой указатель на последний отработавший с данным приоритетом поток. WH>Тогда не будет проблем с всплывающим каждые 5 тактов высокоприоритетным потоком.
Хммм... Ну вообще на первый взгляд звучит заманчиво.
Но нигде больше я про такое не слышал... Возможно просто производители процессоров ещё не дошли до таких вопросов, т.е. пока технология CMT только обкатывается. Возможно есть какие-то объективные причины против этого.
WH>Шедуллер для линеек кеша ессно должен быть отдельным и работать не на уровне потоков, а на уровне ядер.
А вот, кстати, ещё момент. В SUN'овских CMT процессорах поток, пока заблокирован в ожидании загрузки кэш-линии, не стоит без дела — он переходит в режим hardware scouting. Это очень эффективный вариант hardware prefetching'а, поток начинает выполнять свой код в режиме "перемотки вперёд", т.е. просматривает поток инструкций, предугадывает переходы, и для всех обращений к памяти, которые встречает, инициирует предвыборку.
Т.е. фактически такты ядра не высвобождаются от заблокированных потоков. Поэтому, возможно, приоритеты потоков негативно скажутся на hardware scouting, т.к. высокоприоритетный поток будет отнимать у остальных потоков возможность делать эффективный prefetching, т.е. потом сталкнёмся с большими простоями...
Здравствуйте, Michael7, Вы писали:
R>>Так же такие области, как game-dev, где требуется 100% отдача от железа, не полагаются на автоматическое распараллеливание. Т.к. тут не устраивает ситуация, что "компилятор наверное что-то как-то распараллелит".
M>Я вот ещё, что имел ввиду, затронув тему автоматизации распараллеливания, в свете будущих перспектив промышленного программирования для работы с многопроцессорными (многоядерными) системами. M>Существуют прогнозы, что в ближайшее время (5, 10 лет) нас ожидает скачкообразный рост количества ядер на одном процессоре, вплоть до нескольких сотен ядер где-нибудь к 2015 году. Собственно, например архитектуру Cell или GPGPU можно рассматривать как первую ласточку. А несколько десятков ядер уже есть даже в Roadmap-ах производителей.
M>Хотя программы с мультипараллельными вычислениями пишут уже довольно давно, ведь кластеры, суперкомпьютеры и сети распределённых вычислений (вроде SETI) появились не сегодня, писать их сложнее и дороже, чем обычные, да и количество программистов, способных их написать невелико. Здесь же имеющийся опыт "обычных" пограммистов не всегда поможет, написание даже двух- четырех-поточной программы для истинно параллельного исполнения на нынешних двух-четырех-ядерниках уже имеет свои тонкости.
HPC-сообщество работает над немного другими задачами нежели большинство "обычных" программистов, и они работали на немного других аппаратных платформах, и даже там они не решили все вопросы. Поэтому я *не* считаю, что кто-там всё уже давно решил, а мы тут сидим и тупим просто потому что не знаем, что решение уже как 100 лет есть.
M>В этой связи языки и технологии, вроде Haskell, Lisp с параллельным исполнением и т.п., которые сейчас слишком расточительно расходуют ресурсы, могут оказаться востребованными. Если код на них работает, допустим в 5 — 10 — 20 раз медленее, чем на Си это часто неприемлемо медленно, особенно в вычислительных задачах, но если они позволят программисту быстро написать параллельно исполняющуюся программу на 1600 ядрах это будет всё-равно в 160 раз эффективнее, чем работа однопоточной программы.
M>То есть в случае массового распространения сильно многоядерных систем может быть экономически оправдано легкое распараллеливание и не беда, что эффективность может оказаться в размере 10% от пиковой, будет полно задач, где это допустимо.
У языков типа Haskell, Lisp, несомненно, есть некоторые приемущества. НО. Как ты правильно заметил, они не всегда могут генерировать оптимальный код для однопроцессорной мышины, и могут работать в 10 раз медленнее. Многопроцессорность вносит совершенно новые перпендикулярные аспекты:
— эффективность реализации распараллеливания/синхронизации — если это сделать "не подходящим" образом, то можно получить замедление *ещё* в 10-100 раз.
— гранулярность и состав параллельных частей — если это сделать "не подходящим" образом, то можно получить замедление *ещё* в 10-100 раз.
— принципиальная возможность к масштабированию — наличие нескольких процессоров само по себе не даёт ускорения, скорее даже наоборот — по-умолчанию получается замедление (можешь спросить у eao197 ). *Автоматически* выжать из системы масштабирование совсем не просто, это далеко не просто выделение частей, которые формально безопасно выполнять параллельно.
Безусловно сообщество функциональных языков будет над всем этим работать. В нём очень много умных людей. Допустим даже лет через 10 они доведут эти *дополнительные* накладные расходы до 10х раз. Т.е. получим 10*10 = 100х замедление. Это достаточно сложно оправдать, даже имея 160 процессоров — т.е. программа будет работать как на 1.6 процессорах. Уж проще использовать мой любимый способ ускорения многопоточных программ "SetProcessAffinityMask(GetCurrentProcess(), 1)"
Здравствуйте, remark, Вы писали:
R>Хммм... Ну вообще на первый взгляд звучит заманчиво. R>Но нигде больше я про такое не слышал...
Да мне просто на днях не спалось и я думал о том что можно сделать с процессорами.
R>Возможно просто производители процессоров ещё не дошли до таких вопросов, т.е. пока технология CMT только обкатывается. Возможно есть какие-то объективные причины против этого.
Может есть причины. Я не спец по процам.
А может просто не подумали об этом.
R>А вот, кстати, ещё момент. В SUN'овских CMT процессорах поток, пока заблокирован в ожидании загрузки кэш-линии, не стоит без дела — он переходит в режим hardware scouting. Это очень эффективный вариант hardware prefetching'а, поток начинает выполнять свой код в режиме "перемотки вперёд", т.е. просматривает поток инструкций, предугадывает переходы, и для всех обращений к памяти, которые встречает, инициирует предвыборку.
Тут палка о двух концах... с одной стороны это может предотвратить промах кеша (который у нас и так дешовый) с другой стороны это увеличивает размеры ядра.
Те мы можем поставить меньше ядер или меньше однотипных АЛУ в одном ядре.
R>Т.е. фактически такты ядра не высвобождаются от заблокированных потоков. Поэтому, возможно, приоритеты потоков негативно скажутся на hardware scouting, т.к. высокоприоритетный поток будет отнимать у остальных потоков возможность делать эффективный prefetching, т.е. потом сталкнёмся с большими простоями...
Это не есть факт. Некоторые потоки конечно могут застрять но другие будут работать.
Болие того можно сделать для hardware scouting отдельное АЛУ. И скаутить оно будет сначала потоки с болие высоким приоритетом.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, LaPerouse, Вы писали:
LP>По-момему, автоматический паралеллизм автоматом вытекает из ленивости и чистоты. LP>1. Отсутствие побочных эффектов. LP>т к fun1 и fun2 чистые, то результат, возвращаемый ими, не зависит от порядка вызова. И рантайм запускает каждую функцию в своем потоке, к моменту вычисления fun1 результат fun2 может быть вполне вычислен. Чем не автоматический параллелизм?
Тем что предназначение любой программы — это все-таки вызывать побочные эффекты. Чисто вычисления это лишь малая часть любой практически полезной программы.
Брать абстрактные примеры это ошибка. Попробуй показать автоматическое распараллеливание на простой, но практической программе, например, утилите grep или diff. Можешь писать хоть на самом чистом и ленивом языке, какой сумеешь найти.
Здравствуйте, Кодёнок, Вы писали:
Кё>Здравствуйте, LaPerouse, Вы писали:
LP>>По-момему, автоматический паралеллизм автоматом вытекает из ленивости и чистоты. LP>>1. Отсутствие побочных эффектов. LP>>т к fun1 и fun2 чистые, то результат, возвращаемый ими, не зависит от порядка вызова. И рантайм запускает каждую функцию в своем потоке, к моменту вычисления fun1 результат fun2 может быть вполне вычислен. Чем не автоматический параллелизм?
Кё>Тем что предназначение любой программы — это все-таки вызывать побочные эффекты. Чисто вычисления это лишь малая часть любой практически полезной программы.
Кё>Брать абстрактные примеры это ошибка. Попробуй показать автоматическое распараллеливание на простой, но практической программе, например, утилите grep или diff. Можешь писать хоть на самом чистом и ленивом языке, какой сумеешь найти.
Асинхронный ввод-вывод прекрасно параллелится. Правда, это уже будет не автоматический параллелизм. Речь шла не о том.
Социализм — это власть трудящихся и централизованная плановая экономика.
>> В этой связи языки и технологии, вроде Haskell, Lisp с параллельным >> исполнением и т.п., которые сейчас слишком расточительно расходуют >> ресурсы, могут оказаться востребованными. Если код на них работает, >> допустим в 5 — 10 — 20 раз медленее, чем на Си это часто неприемлемо >> медленно, особенно в вычислительных задачах, но если они позволят >> программисту быстро написать параллельно исполняющуюся программу на 1600 >> ядрах это будет всё-равно в 160 раз эффективнее, чем работа однопоточной >> программы. >> >> То есть в случае массового распространения сильно многоядерных систем >> может быть экономически оправдано легкое распараллеливание и не беда, что >> эффективность может оказаться в размере 10% от пиковой, будет полно задач, >> где это допустимо.
S>Проблема в том, что для реализации такого сценария понадобится S>1600-канальная память и 1600 хотя бы полумегабайтных кэшей. Иначе программа S>у вас будет не в 160 раз эффективнее, а, например, в 2 раза. Или вообще S>медленнее однопоточной. IMHO.
Именно.
К этому всё и движется. У AMD это уже так, у Intel это тоже будет так со следующего семейства процессоров: http://www.intel.com/pressroom/archive/reference/whitepaper_nehalem.pdf
(раздел "New System Architecture: Intel QuickPath Technology")
Я имею в виду, что систему будут ссNUMA.... а потом может быть non-ccNUMA. И такие "асимметричные" архитектуры создают дополнительные проблемы для всех, в том числе и для автоматического распараллеливания.
Здравствуйте, LaPerouse, Вы писали:
LP>Здравствуйте, remark, Вы писали:
R>>Новые технологии нужны. Но новые технологии — это *не* автоматическое распараллеливание.
LP>По-момему, автоматический паралеллизм автоматом вытекает из ленивости и чистоты.
LP>1. Отсутствие побочных эффектов. LP>b = fun1(a) LP>c = fun2(a)
LP>т к fun1 и fun2 чистые, то результат, возвращаемый ими, не зависит от порядка вызова. И рантайм запускает каждую функцию в своем потоке, к моменту вычисления fun1 результат fun2 может быть вполне вычислен. Чем не автоматический параллелизм?
Тут есть 2 проблемы.
Во-первых, а если мы захотим добавить в программу какую-то полезную работу. Ну если программа будет супер быстрая, то она должна хотя бы как-то сообщить об этом, что бы и другие могли порадоваться за неё.
Допустим, fun1() и fun2() отправляют что-то по сети. Их уже переставлять нельзя. А может быть и можно, если протокол допускает произвольный порядок этих сообщений. Это, кстати, система автоматического распараллеливания должна будет сама определить. Как ты предлагаешь это делать?
Как это "автоматический распараллеливатель" будет распараллеливать серверное ПО, клиентское GUI ПО, игры, драйверы и т.д.???
Во-вторых, даже потенциальный, но не реализованный параллелизм имеет стоимость. Пока, насколько я знаю, никто не сумел сделать его бесплатным. У тебя есть вариант?
Да вот ещё, как обрабатывать разделяемые структуры данных???
LP>2. Ленивость. Скажем, параллельно ходу выполнения основного потока в других потоках происходит раскрутка ленивости. Когда потребуются результаты, вместо вычисления всего ленивого кома, просто берет уже вычисленные значения. Чем не автоматический параллелизм?
Берут вычисленные значения. Замечательно. А синхронизация сколько будет стоить?
Мы же говорим о мелкомодульном паралеллизме, это значит, что затраты на синхронизацию при сегодняшней ситуации могут составлять до ~1000% от полезной работы.
LP>Все вышесказанное настолько очевидно, что спорить с этим невозможно.
Блин,а мужики-то не знают!
LP>Понятно, quckSort таким образом не распараллелить, но реально большое количество операций можно выполнять параллельно. Если учесть, что все это достается задаром (пользователь не догадывается о том, где в какой момент времени сколько будет использоваться потоков, да и вообще сказать это можно только на этапе выполнения), то имхо не стоит просто так отметать преусловутый автопаралеллизм.
Бесплатно? Если бы я знал, как это всё сделать бесплатно, то я бы не постил на этом форуме, я бы сейчас отдыхал на своём острове где-нибудь в тихом океане
Как ты сделаешь бесплатным потенциальный даже не реализованный параллелизм?
Как ты сделаешь бесплатным управлению временем жизни объектов?
Как ты сделаешь бесплатным управлению памятью?
Как ты сделаешь бесплатным разделяемые структуры данных?
Как ты сделаешь бесплатным переиспользование результатов, вычисленных другим потоком?
). *Автоматически* выжать из системы масштабирование совсем не просто, это далеко не просто выделение частей, которые формально безопасно выполнять параллельно.
