Автоматическое распараллеливание (было "Что почитать...") - Философия программирования

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

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

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

R>>>Новые технологии нужны. Но новые технологии — это *не* автоматическое распараллеливание.

LP>>По-момему, автоматический паралеллизм автоматом вытекает из ленивости и чистоты.

LP>>1. Отсутствие побочных эффектов.
LP>>b = fun1(a)
LP>>c = fun2(a)

LP>>т к fun1 и fun2 чистые, то результат, возвращаемый ими, не зависит от порядка вызова. И рантайм запускает каждую функцию в своем потоке, к моменту вычисления fun1 результат fun2 может быть вполне вычислен. Чем не автоматический параллелизм?
R>Тут есть 2 проблемы.
R>Во-первых, а если мы захотим добавить в программу какую-то полезную работу. Ну если программа будет супер быстрая, то она должна хотя бы как-то сообщить об этом, что бы и другие могли порадоваться за неё.
R>Допустим, fun1() и fun2() отправляют что-то по сети. Их уже переставлять нельзя. А может быть и можно, если протокол допускает произвольный порядок этих сообщений. Это, кстати, система автоматического распараллеливания должна будет сама определить. Как ты предлагаешь это делать?

В исходном сообщении ясно подчеркивается, что функции fun1 и fun2 не имеют побочных эффектов. Поэтому к чему вот это:

R>Как это "автоматический распараллеливатель" будет распараллеливать серверное ПО, клиентское GUI ПО, игры, драйверы и т.д.???

R>Во-вторых, даже потенциальный, но не реализованный параллелизм имеет стоимость. Пока, насколько я знаю, никто не сумел сделать его бесплатным. У тебя есть вариант?

R>Да вот ещё, как обрабатывать разделяемые структуры данных???

Далее:

LP>>2. Ленивость. Скажем, параллельно ходу выполнения основного потока в других потоках происходит раскрутка ленивости. Когда потребуются результаты, вместо вычисления всего ленивого кома, просто берет уже вычисленные значения. Чем не автоматический параллелизм?

R>Берут вычисленные значения. Замечательно. А синхронизация сколько будет стоить?
R>Мы же говорим о мелкомодульном паралеллизме, это значит, что затраты на синхронизацию при сегодняшней ситуации могут составлять до ~1000% от полезной работы.

Я могу ошибаться, но мне кажется,что синхронизаций нужно не так много. Давай представим стек ленивых вызовов ввиде разделяемой структуры-дерева, в узлах которого будут вызовы функций, которые согласно п.1 чистые. Тогда второй поток может идти по дереву, вычисляя узлы дерева и записывая результат вычисления в те же узлы совершенно без всяких синхронизаций с основным потоком. Потом, когда придет время для раскрутки, реализация смотрит — если узел на N-ом уровне дерева вычислен, то берет значение из узла, если нет, то вычисляет его. При этом, самое интересное, что второй поток можно не останавливать, пусть скажем при вычислении первым потоком узл на N-ом уровне второй, одновременно с ним вычислив этот узел, приступит к узлу на N-1 уровне. Синхронизаций нет!

LP>>Все вышесказанное настолько очевидно, что спорить с этим невозможно.

R>Блин,а мужики-то не знают!

Мужики не думают, что все очевидно? Или мужики настолько хорошо знают, что все очевидно, что упоминание об этом все равно что сказать "дважды два четыре"?

LP>>Понятно, quckSort таким образом не распараллелить, но реально большое количество операций можно выполнять параллельно. Если учесть, что все это достается задаром (пользователь не догадывается о том, где в какой момент времени сколько будет использоваться потоков, да и вообще сказать это можно только на этапе выполнения), то имхо не стоит просто так отметать преусловутый автопаралеллизм.

R>Бесплатно? Если бы я знал, как это всё сделать бесплатно, то я бы не постил на этом форуме, я бы сейчас отдыхал на своём острове где-нибудь в тихом океане

R>Как ты сделаешь бесплатным потенциальный даже не реализованный параллелизм?
R>Как ты сделаешь бесплатным управлению временем жизни объектов?
R>Как ты сделаешь бесплатным управлению памятью?
R>Как ты сделаешь бесплатным разделяемые структуры данных?
R>Как ты сделаешь бесплатным переиспользование результатов, вычисленных другим потоком?

remark, речь ведь совсем не шла о тотальном распараллеливании всего и вся. Там упоминалось лишь два, строго очерченных случая, когда возможность автораспараллеливания очевидна и даже ты, при всей нелюбви к ней, не будешь отрицать, что хотя бы ТЕОРЕТИЧЕСКИ именно в ЭТИХ случаях автопараллелизм возможен.

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

LP>remark, речь ведь совсем не шла о тотальном распараллеливании всего и вся. Там упоминалось лишь два, строго очерченных случая, когда возможность автораспараллеливания очевидна и даже ты, при всей нелюбви к ней, не будешь отрицать, что хотя бы ТЕОРЕТИЧЕСКИ именно в ЭТИХ случаях автопараллелизм возможен.

Это настолько же очевидно, как и бесполезно, потому что какой процент составляет такой код в существующих программах? 1%? 5%? Я и предлагаю тебе взять любую практическую тулсу на хаскеле и оценить соотношение.

К твоему же примеру следует отметить, что если параллелящиеся ветки слишком короткие, то их дешевле вообще не параллелить. Ибо когда-то параллельные результаты должны слиться вместе, а это синхронизация, и само по себе «дерганье» ядра ради исполнения 50 тактов, с учетом заморочек с кешами и пр. даст только замедление. Несомненно, чистых от побочных эффектов веток хватает в любой программе, а вот сколько там достаточно длинных?

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

R>>Тут есть 2 проблемы.
R>>Во-первых, а если мы захотим добавить в программу какую-то полезную работу. Ну если программа будет супер быстрая, то она должна хотя бы как-то сообщить об этом, что бы и другие могли порадоваться за неё.
R>>Допустим, fun1() и fun2() отправляют что-то по сети. Их уже переставлять нельзя. А может быть и можно, если протокол допускает произвольный порядок этих сообщений. Это, кстати, система автоматического распараллеливания должна будет сама определить. Как ты предлагаешь это делать?

LP>В исходном сообщении ясно подчеркивается, что функции fun1 и fun2 не имеют побочных эффектов.

Тут гляди как ситуация. Примерно такое распараллеливание как ты говоришь уже достаточно давно есть в High Performance Fortran. За счёт ограниченности языка компилятор имеет возможность анализировать циклы на предмет возможности распараллеливания. Но серебрянной пули не получилось.
Во-первых, идеальный цикл разработки выглядит так: программист пишет программу; во время компиляции она магически распараллеливается. На практике это выглядит так: программист пишет программу, думая о том как компилятор сможет её распараллеливать; программа компилируется; программист проверяет, что компилятор распараллелил так, как задумано; если что-то не так, то разработка итеративно повторяется; если всё так, то предпринимаются какие-то меры, что бы впоследствии полученное "хорошее" распараллеливание не "ломалось" от изменений.
Во-вторых, всё равно пришло добавить некоторые "хинты" компилятору, которые бы помогали ему сделать всё правильно. Соотв. расстановка хинтов — обязанность программиста.
В-третьих, как следует из предыдущих пунктов, думать программист обязан на низком уровне, в то время как писать — на высоком. Это причина многих проблем. Например, сложно понять как описать на высоком уровне алгоритм, что бы получить желаемый алгоритм на низком уровне. Не понятно, как надо изменить алгоритм на высоком уровне, что бы получить желаемое изменение алгоритма на низком уровне. Ну и рано или поздно некоторые сталкивались с тем, что необходимость писать на очень ограниченном высоком уровне просто связывает им руки (раз они всё равно думают на низком уровне), это приводило просто к отказу от HPF и возвращение к MPI.

Возьмем твой пример с fun1 и fun2.
Первая проблема. Если есть 100 процессоров и только fun1 и fun2, то будет задействовано максимум 2 процессора (в предположении, что компилятор будет распараллеливать на уровне функций, что вполне разумно). Т.е. программист *обязан* (уже элемент не автоматизма) предоставить компилятору хотя бы средний уровень гранулярности (сотни/тысячи элементов для распараллеливания). Тут встаёт другая проблема — надо не переборщить с гранулярностью работы. Слишком мелкие элементы работы (сложение 2 чисел) тоже будут негативно сказываться на производительности (об этом тоже надо подумать программисту).
Вторая проблема. Возможность для параллелизма должна быть выражена в правильной форме. Например, если используется рекурсия, то дерево вызовов должно быть сбалансированным. Если оно будет не сбалансированное (с множеством коротких путей), то хорошего распараллеливания не получится — расходы на постоянную синхронизацию при шедулинге работы съедят всё время. Если алгоритм выражен в виде цикла, и при этом между итерациями есть зависимости по данным, то никакого распараллеливания не получится вообще. Тут вообще нет никакого автоматизма — программист *обязан* предоставить компилятору "хорошую" структуру программы.
Третья проблема. Учитывая предыдущие 2 пункта получаем 1 и 3 пункты из вышеописанной ситуации с High Performance Fortran. Т.е. цикл разработки: пишем -> проверяем компилятор -> итеративно меняем и т.д. И постоянно боремся с компилятором: вроде всё сделали правильно, а эта сволочь почему-то не распараллелила! Почему? И как поменять программу, что всё-таки распараллелила?

R>>Во-вторых, даже потенциальный, но не реализованный параллелизм имеет стоимость. Пока, насколько я знаю, никто не сумел сделать его бесплатным. У тебя есть вариант?

Этот пункт не уходит даже если учитывать только "вычислительные задачи". Для шедулинга работы при распараллеливании сейчас де-факто применяется распределенный шедулер на основе work-stealing deque. Насколько я знаю, пока никто не смог сделать в нём "бесплатный" потенциальный параллелизм. Т.е. даже если один поток выполняет элементы работы, всё-равно приходится платить как-минимум 1 Interlocked операцию, либо тяжёлый барьер памяти (#StoreLoad, mfence) на каждый элемент работы. Так обстоит дело в Cilk, .NET TPL, Java Fork/Join и т.д.

LP>Я могу ошибаться, но мне кажется,что синхронизаций нужно не так много. Давай представим стек ленивых вызовов ввиде разделяемой структуры-дерева, в узлах которого будут вызовы функций, которые согласно п.1 чистые. Тогда второй поток может идти по дереву, вычисляя узлы дерева и записывая результат вычисления в те же узлы совершенно без всяких синхронизаций с основным потоком. Потом, когда придет время для раскрутки, реализация смотрит — если узел на N-ом уровне дерева вычислен, то берет значение из узла, если нет, то вычисляет его.

Если без синхронизации, то одно значение может вычисляться N (количество процессоров) раз. Значение может быть *очень* тяжелым. Например при использовании рекурсии одно значение может представлять половину всей работы.

LP> При этом, самое интересное, что второй поток можно не останавливать, пусть скажем при вычислении первым потоком узл на N-ом уровне второй, одновременно с ним вычислив этот узел, приступит к узлу на N-1 уровне. Синхронизаций нет!

Не понял мысль. Что подразумевается под "остановкой потоков"? И под "уровнями"?

LP>>>Все вышесказанное настолько очевидно, что спорить с этим невозможно.

R>>Блин,а мужики-то не знают!

LP>Мужики не думают, что все очевидно? Или мужики настолько хорошо знают, что все очевидно, что упоминание об этом все равно что сказать "дважды два четыре"?

Мужики *знают*, что всё *не* очевидно.

LP>>>Понятно, quckSort таким образом не распараллелить, но реально большое количество операций можно выполнять параллельно. Если учесть, что все это достается задаром (пользователь не догадывается о том, где в какой момент времени сколько будет использоваться потоков, да и вообще сказать это можно только на этапе выполнения), то имхо не стоит просто так отметать преусловутый автопаралеллизм.

R>>Бесплатно? Если бы я знал, как это всё сделать бесплатно, то я бы не постил на этом форуме, я бы сейчас отдыхал на своём острове где-нибудь в тихом океане

R>>Как ты сделаешь бесплатным потенциальный даже не реализованный параллелизм?
R>>Как ты сделаешь бесплатным управлению временем жизни объектов?
R>>Как ты сделаешь бесплатным управлению памятью?
R>>Как ты сделаешь бесплатным разделяемые структуры данных?
R>>Как ты сделаешь бесплатным переиспользование результатов, вычисленных другим потоком?

LP>remark, речь ведь совсем не шла о тотальном распараллеливании всего и вся. Там упоминалось лишь два, строго очерченных случая, когда возможность автораспараллеливания очевидна и даже ты, при всей нелюбви к ней, не будешь отрицать, что хотя бы ТЕОРЕТИЧЕСКИ именно в ЭТИХ случаях автопараллелизм возможен.

Издержки на шедулинг и на управление памятью/временем жизни объектов будут в *любом* случае.

> 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.
> И такие "асимметричные" архитектуры создают дополнительные проблемы для
> всех, в том числе и для автоматического распараллеливания.

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

Posted via RSDN NNTP Server 2.1 beta

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

>> 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.
>> И такие "асимметричные" архитектуры создают дополнительные проблемы для
>> всех, в том числе и для автоматического распараллеливания.

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

Может там и не будет кэша. В процессорах Cell у SPE ядер нет кэша.
Хотя Tilera умудрилась запихать 64, а Intel — 80 кэшей на одну подложку уже сейчас.

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

LP>Все вышесказанное настолько очевидно, что спорить с этим невозможно. Понятно, quckSort таким образом не распараллелить, но реально большое количество операций можно выполнять параллельно.

Это почему не распараллелить?
По моему как раз очень хорошо можно распараллелить.

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

WH>Шедуллер для линеек кеша ессно должен быть отдельным и работать не на уровне потоков, а на уровне ядер.

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

... << RSDN@Home 1.2.0 alpha rev. 786>>

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

V>Более того, нужно часть шедуллера прямо в железке и делать, и давать возможность этим шедуллером управлять программно.
Что это даст?

Единственное что имеет смысл это для управляемых ОС сделать простенькую комманду для организации safe point'ов.
Это просто условный переход который срабатывает от того что у потока кончился квант времени, ГЦ захотел собрать мусор, случилось прирываение...
По этому переходу переходим на код который сохраняет все регистры которые имеет смысл сохранять, записывает адрес кода который потом востановит сохраненные регистры и передает управление шедуллеру.

V>Аналогично насчёт примитивов синхронизации, десяток-другой тысяч их прямо в ядре не помешал бы.
Каких еще примитивов?
Они ведь очень разные бывают.

Кстати если говорить о всяких там мъютексах, семафорах и тп то меня всегда мягко говоря настораживало то что лочится хрен знает что. Никакой формализации. Одни мутные ничем не проверяемые соглашения.
Мой lock гораздо понятнее. Лочим 1 или 2 куска памяти и с ними работаем. Все что за их приделами трогать нельзя.

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

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

V>Более того, нужно часть шедуллера прямо в железке и делать, и давать возможность этим шедуллером управлять программно. Аналогично насчёт примитивов синхронизации, десяток-другой тысяч их прямо в ядре не помешал бы. Идея-то старая, а с современным кол-вом транзисторов на ядро вполне реализуема для требуемого кол-ва одновременно созданных этих примитивов. (Ну уж если кончатся ядерные, то можно делать по-старинке, в ОП).

Интересно а какой производительности можно добиться для таких аппаратных примитивов синхронизации? Понятно, что можно сделать более специализировано, чем кэш, но фактор расстояния всё равно остаётся...
Кстати, а как быть с многопроцессорными системами? Надо ещё какой-то отдельный канал между процессорами и специальный протокол для этих целей...

Похоже, что HTM как раз и есть реализация таких хардварных примитивов синхронизации. По крайней мере её можно так использовать (HTM lock elission). Причём похоже, что на Sun Rock такая хитрая реализация мьютексов (через HTM lock elission) работает таки быстрее честных мьютексов и масштабируется лучше.

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

WH>Кстати если говорить о всяких там мъютексах, семафорах и тп то меня всегда мягко говоря настораживало то что лочится хрен знает что. Никакой формализации. Одни мутные ничем не проверяемые соглашения.

Так и есть. Мьютекс защищает не данные, а код. TM защищает данные, но не код.

WH>Если уж что-то в процессор вкручивать то ту комманду которую описал я.
WH>На ней можно сделать вобще все. Ибо все данные мъютекса, семафора и тп укатываются в одну линейку кеша.

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

По поводу юзабельности тоже возникают вопросы. Особенно в сравнении с HTM.
Таким примитивом сам бог велел реализовывать уже не мьютексы и семафоры, а сами структуры данных. Т.к. мьютексы и семафоры хорошо реализуются и InterlockedCompareExchange, смысла городить для них что-то более сложное мало. А тут получаем возможность делать lock-free реализации стуктур данных, а это уже немного другое чем структуры на мьютексах и семафорах. А кол-во изменяемых разрозненных слов для произвольной структуры данных уже вполне может быть и не ограничено 2. Очереди, стеки и двух-связанные списки вписываются, а всякие скип-листы, деревья и т.д. уже нет...
Хотя, это бесспорно значительно лучше, чем InterlockedCompareExchange, но если уж мечтать, так мечтать!

Кстати, смотри PLO это практически то, о чем ты говоришь.

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

R>Так и есть. Мьютекс защищает не данные, а код.
Защищать код это мягко говря странное занятие.

R>TM защищает данные, но не код.
Кто?

R>С линейками кэша не покатит. Надо лочить слова.
Один хрен меньше линейки не залочить.
Разве что лиейку сделать размером с слово.

R>Иначе это не будет юзабельно ни в одном высокоуровневом языке (кроме С/С++ с очень большой натяжкой). Т.к. как компиялтору надо будет размещать данные? Ему надо будет как-то угадывать, что разместить в одной линейне, а что в разных. Я думаю, что в общем случае это нельзя будет вписать в высокоуровневые языки. Не говоря о том, что кэш должен быть практически полностью прозрачен для ПО, и размер линейки кэша может меняться от модели процессора к модели.
Вот у С++ будут проблемы.
А у виртуальных машин никаких.
Они под железку легко адаптируются.

R>По поводу юзабельности тоже возникают вопросы. Особенно в сравнении с HTM.
Который не работает.
И работать не будет.
Ибо очень сложный.

R>Таким примитивом сам бог велел реализовывать уже не мьютексы и семафоры, а сами структуры данных.
Так никто и не говорит что ими только мъютексы реализовывать будут.

R>Т.к. мьютексы и семафоры хорошо реализуются и InterlockedCompareExchange, смысла городить для них что-то более сложное мало.
С циклом внутри... А тут нет цикла.

R>А тут получаем возможность делать lock-free реализации стуктур данных, а это уже немного другое чем структуры на мьютексах и семафорах. А кол-во изменяемых разрозненных слов для произвольной структуры данных уже вполне может быть и не ограничено 2.
R>Очереди, стеки и двух-связанные списки вписываются,
Вот их и хватит.

R>а всякие скип-листы, деревья и т.д. уже нет...
А надо?

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

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

R>>Так и есть. Мьютекс защищает не данные, а код.
WH>Защищать код это мягко говря странное занятие.

Ну, что ж делать?

R>>TM защищает данные, но не код.
WH>Кто?

Транзакционная память (TM, Transactional Memory)

R>>С линейками кэша не покатит. Надо лочить слова.
WH>Один хрен меньше линейки не залочить.
WH>Разве что лиейку сделать размером с слово.

А ну если со стороны реализации смотреть, то да, согласен. Я просто посмотрел со стороны семантики.

R>>Иначе это не будет юзабельно ни в одном высокоуровневом языке (кроме С/С++ с очень большой натяжкой). Т.к. как компиялтору надо будет размещать данные? Ему надо будет как-то угадывать, что разместить в одной линейне, а что в разных. Я думаю, что в общем случае это нельзя будет вписать в высокоуровневые языки. Не говоря о том, что кэш должен быть практически полностью прозрачен для ПО, и размер линейки кэша может меняться от модели процессора к модели.
WH>Вот у С++ будут проблемы.
WH>А у виртуальных машин никаких.
WH>Они под железку легко адаптируются.

Ну, если считать, что лочится именно кэш-линия и мы хотим предоставить пользователю возможность этим пользоваться, то сколько смежных слов мы будем гарантировать как попадающию в одну кэш-линию (это нам надо делать на уровне языка)? Потом это, мне кажется, будет накладывать какие-то хитрые ограничения на перемещения объектов GC, на размещение членов внутри объекта, на размещение объектов относительно друг друга и т.д. При этом, что бы знать эти ограничения надо знать к каким объектам будут обращения с помощью этой хитрой команды, а если это не знать, то будет субоптимальные решения. Вобщем, я это особо не продумывал, но мне кажется, что тут будет очень засадно для высокоуровневых (управляемых) языков, в таких языках-то адресов у объектов нет, а тут надо понятие кэш-линии в язык протащить...

R>>По поводу юзабельности тоже возникают вопросы. Особенно в сравнении с HTM.
WH>Который не работает.
WH>И работать не будет.
WH>Ибо очень сложный.

А можно поподробнее? Это просто личные наблюдения или есть какие-то внешние источники? Просто Sun'овская реализация-то готовится к выходу... Пока, конечно, сильно не понятно, как это будет в реальной жизни работать, но судя по результатам моделирования вроде должно. Да и вообще сомнительно, что в железе реализуется вещь, уж совсем не рабочая. Пока это всё было на уровне программных реализаций, то да, это было сильно сомнительно...

R>>Таким примитивом сам бог велел реализовывать уже не мьютексы и семафоры, а сами структуры данных.
WH>Так никто и не говорит что ими только мъютексы реализовывать будут.

Просто с твоих слов:

На ней можно сделать вобще все. Ибо все данные мъютекса, семафора и тп укатываются в одну линейку кеша.

Ризонинг относительно того, что с помощью 2 линеек кэша можно сделать все опирается на то, что 2 линейки кэша достаточно для реализации мьютексов и семафоров.

R>>Т.к. мьютексы и семафоры хорошо реализуются и InterlockedCompareExchange, смысла городить для них что-то более сложное мало.
WH>С циклом внутри... А тут нет цикла.

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

R>>А тут получаем возможность делать lock-free реализации стуктур данных, а это уже немного другое чем структуры на мьютексах и семафорах. А кол-во изменяемых разрозненных слов для произвольной структуры данных уже вполне может быть и не ограничено 2.
R>>Очереди, стеки и двух-связанные списки вписываются,
WH>Вот их и хватит.

Ну их и сейчас можно сделать...

R>>а всякие скип-листы, деревья и т.д. уже нет...
WH>А надо?

Некоторые используют...

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

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

V>>Более того, нужно часть шедуллера прямо в железке и делать, и давать возможность этим шедуллером управлять программно.
WH>Что это даст?

Для многоядерных систем в связке со встроенными примитивами синхронизации даст аппаратное переключение потоков без дорогостоящего механизма прерываний.

V>>Аналогично насчёт примитивов синхронизации, десяток-другой тысяч их прямо в ядре не помешал бы.
WH>Каких еще примитивов?
WH>Они ведь очень разные бывают.

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

WH>Кстати если говорить о всяких там мъютексах, семафорах и тп то меня всегда мягко говоря настораживало то что лочится хрен знает что.

Я имею ввиду, что "лочится" или "отпускается" некий поток, а остальное, действительно, заложено в семантике самой программы.

WH>Никакой формализации. Одни мутные ничем не проверяемые соглашения.

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

WH>Мой lock гораздо понятнее. Лочим 1 или 2 куска памяти и с ними работаем. Все что за их приделами трогать нельзя.

"Лочим" — понятие растяжимое.

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

Угу, и нам нужно будет дёргать АЛУ для банального декремента семафора или проверки состояния события. Это ничем не отличается от существующего подхода.

... << RSDN@Home 1.2.0 alpha rev. 786>>

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

WH>>Защищать код это мягко говря странное занятие.
R>Ну, что ж делать?

Ну не вижу я смысла защищать код.
Ибо защищать нужно только изменяемые данные.

R>Ну, если считать, что лочится именно кэш-линия и мы хотим предоставить пользователю возможность этим пользоваться, то сколько смежных слов мы будем гарантировать как попадающию в одну кэш-линию (это нам надо делать на уровне языка)? Потом это, мне кажется, будет накладывать какие-то хитрые ограничения на перемещения объектов GC, на размещение членов внутри объекта, на размещение объектов относительно друг друга и т.д. При этом, что бы знать эти ограничения надо знать к каким объектам будут обращения с помощью этой хитрой команды, а если это не знать, то будет субоптимальные решения. Вобщем, я это особо не продумывал, но мне кажется, что тут будет очень засадно для высокоуровневых (управляемых) языков, в таких языках-то адресов у объектов нет, а тут надо понятие кэш-линии в язык протащить...
Смысл в том что высокоуровневые ВМ вобще уберают связь с железом прикладного кода.
Разговоры о том что в высокоуровневой ВМ есть комманда которая както отображается на некоторорые железки вобще не имеет смысла.
Такие ВМ можно довети до того что пользователям не нужно будет даже знать слова "модель памяти" ибо можно создать модель в которой переход изменяемых данных между потоками контролируется статически.
А все эти выкрутасы будут нужны только десятку маньяков которые пилят ядро ВМ.
Соответственно эти маньяки берут спецификацию проца и за пару недель выпиливают специализацию ядра под этот проц.

R>А можно поподробнее? Это просто личные наблюдения или есть какие-то внешние источники? Просто Sun'овская реализация-то готовится к выходу... Пока, конечно, сильно не понятно, как это будет в реальной жизни работать, но судя по результатам моделирования вроде должно. Да и вообще сомнительно, что в железе реализуется вещь, уж совсем не рабочая. Пока это всё было на уровне программных реализаций, то да, это было сильно сомнительно...
Я вроде гдето по твоим ссылкам читал что все выкрутасы на эту тему приводили к проездам по памяти.
Да и вобще куча мутной семантики типа грязного чтения итп мягко говоря настораживает.
С деревянными локами куда как понятнее и спокойней.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

V>Для многоядерных систем в связке со встроенными примитивами синхронизации даст аппаратное переключение потоков без дорогостоящего механизма прерываний.

Что нужно я уже сказал.

V>Атомарные аппаратные счётчики, больше ничего не надо, и аппаратная логика для них, которая позволит делать из них семафоры, мьютексы или события. При наличии большого файла регистров вся информация о состоянии потоков может хранится прямо в памяти ядра (опять же, что не поместиться в крайнем случае — по старинке в ОП).
А ты не думал о том что система может работать в совсем другом базисе?

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

WH>>Мой lock гораздо понятнее. Лочим 1 или 2 куска памяти и с ними работаем. Все что за их приделами трогать нельзя.
V>"Лочим" — понятие растяжимое.
В данном случае очень конкретное.
И там все подробно описано.

V>Угу, и нам нужно будет дёргать АЛУ для банального декремента семафора или проверки состояния события. Это ничем не отличается от существующего подхода.
А ты уверен что твой подход вобще имеет смысл делать?
Как насчет систем которые работают на примитивах синхронизации ориентированных на данные?
Для них твой подход не эффективен.

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

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

WH>>>Защищать код это мягко говря странное занятие.
R>>Ну, что ж делать?

WH>Ну не вижу я смысла защищать код.
WH>Ибо защищать нужно только изменяемые данные.

Ну да, последние 40 лет нам сильно не везло с примитивами синхронизации

R>>Ну, если считать, что лочится именно кэш-линия и мы хотим предоставить пользователю возможность этим пользоваться, то сколько смежных слов мы будем гарантировать как попадающию в одну кэш-линию (это нам надо делать на уровне языка)? Потом это, мне кажется, будет накладывать какие-то хитрые ограничения на перемещения объектов GC, на размещение членов внутри объекта, на размещение объектов относительно друг друга и т.д. При этом, что бы знать эти ограничения надо знать к каким объектам будут обращения с помощью этой хитрой команды, а если это не знать, то будет субоптимальные решения. Вобщем, я это особо не продумывал, но мне кажется, что тут будет очень засадно для высокоуровневых (управляемых) языков, в таких языках-то адресов у объектов нет, а тут надо понятие кэш-линии в язык протащить...
WH>Смысл в том что высокоуровневые ВМ вобще уберают связь с железом прикладного кода.
WH>Разговоры о том что в высокоуровневой ВМ есть комманда которая както отображается на некоторорые железки вобще не имеет смысла.
WH>Такие ВМ можно довети до того что пользователям не нужно будет даже знать слова "модель памяти" ибо можно создать модель в которой переход изменяемых данных между потоками контролируется статически.
WH>А все эти выкрутасы будут нужны только десятку маньяков которые пилят ядро ВМ.
WH>Соответственно эти маньяки берут спецификацию проца и за пару недель выпиливают специализацию ядра под этот проц.

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

R>>А можно поподробнее? Это просто личные наблюдения или есть какие-то внешние источники? Просто Sun'овская реализация-то готовится к выходу... Пока, конечно, сильно не понятно, как это будет в реальной жизни работать, но судя по результатам моделирования вроде должно. Да и вообще сомнительно, что в железе реализуется вещь, уж совсем не рабочая. Пока это всё было на уровне программных реализаций, то да, это было сильно сомнительно...
WH>Я вроде гдето по твоим ссылкам читал что все выкрутасы на эту тему приводили к проездам по памяти.
WH>Да и вобще куча мутной семантики типа грязного чтения итп мягко говоря настораживает.
WH>С деревянными локами куда как понятнее и спокойней.

Ты наверное читал про STM (Software Transactional Memory).
С HTM (Hardware Transactional Memory) ситуация получше. Проездов по памяти нет, грязных чтений нет. Производительность вроде лучше, чем у мьютексов... по крайней мере на *некоторых* тестах.

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

R>Ну да, последние 40 лет нам сильно не везло с примитивами синхронизации

Последние 40 лет народ думал не в том направлении.
Ибо защищать код есть бред полный.
Данные защищать нужно. ДАННЫЕ! Не код.

R>В высокоуровневых языках эта команда не будет доступна. Об этом и говорю. Как всегда будет оставаться только ждать пока разработчики языка сами сделают, потом ждать пока они сделают то что нужно, а потом ждать пока они сделают так как нужно, ну а потом можно будет и пользоваться.
На то они и высокоуровневые что бы работать везде (включая железки где даже указатель атомарно не запишешь...) и не напрягать прикладников страшными словами типа "модель памяти".

R>Ты наверное читал про STM (Software Transactional Memory).
Может быть.

R>С HTM (Hardware Transactional Memory) ситуация получше. Проездов по памяти нет, грязных чтений нет. Производительность вроде лучше, чем у мьютексов... по крайней мере на *некоторых* тестах.
Всеравно не верю что хорошо работать будет.
Сложная очень.
Короче ИМХО будет работать только на полегонах.
А как дело дойдет до грязи...

... << RSDN@Home 1.2.0 alpha rev. 745>>

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

R>>В высокоуровневых языках эта команда не будет доступна. Об этом и говорю. Как всегда будет оставаться только ждать пока разработчики языка сами сделают, потом ждать пока они сделают то что нужно, а потом ждать пока они сделают так как нужно, ну а потом можно будет и пользоваться.

WH>На то они и высокоуровневые что бы работать везде (включая железки где даже указатель атомарно не запишешь...)

Ну такую ещё поискать надо. А как, кстати, ты предлагаешь на такой железяке реализовывать Java/C#? Языки-то дают гарантии атомарного присвоения/чтения объектных ссылок. Каждое обращение к объектной ссылке обрамлять в мьютекс это не решение

У С++0х, кстати, в этом плане более грамотный подход — атомарные объекты гарантированно атомарно читаются/пишутся (пусть хоть и с мьютексом), а насчёт "обычных" объектов никаких гарантий нет. Что и разумно, т.к. они *обычные* и к синхронизации потоков отношения не имеют, следовательно и требования атомарности к ним не релевантны. А в Java/C# получается, что любой объект потенциально может использоваться как примитив синхронизации, и компилятор обязан с этим считаться, несмотря на то, что в большинстве случаев это бессмысленно.

WH>и не напрягать прикладников страшными словами типа "модель памяти".

Ну по крайней мере императивные языки с явным тридингом себе такого позволить не могут (Java/C#). Такое себе могут позволить только языки с очень изощренными моделями программирования (DSL типа SQL).

R>>С HTM (Hardware Transactional Memory) ситуация получше. Проездов по памяти нет, грязных чтений нет. Производительность вроде лучше, чем у мьютексов... по крайней мере на *некоторых* тестах.
WH>Всеравно не верю что хорошо работать будет.
WH>Сложная очень.
WH>Короче ИМХО будет работать только на полегонах.
WH>А как дело дойдет до грязи...

Да, хотелось бы увидеть его в деле. Вообще это будет очень серьёзная проверка для всей концепции TM, на которую сейчас возлагаются большие надежды. Ну вообще, посколько это Sun, то зуб даю, что вскоре после выпуска чипов во внутренностях их JVM должно появиться использование этой штуковины, тогда и увидим бенчмарки. А потом и на уровне языка должна появиться поддержка транзакций на основе HTM.

От:	remark	http://www.1024cores.net/
Дата:	24.04.08 19:30
Оценка:

	От:	LaPerouse
	Дата:	25.04.08 06:30
	Оценка:	15 (1)

	От:	Кодёнок
	Дата:	25.04.08 06:56
	Оценка:

От:	remark	http://www.1024cores.net/
Дата:	26.04.08 23:09
Оценка:	4 (1)

	От:	Sergey
	Дата:	27.04.08 08:25
	Оценка:

	От:	maggot
	Дата:	16.07.08 16:58
	Оценка:

	От:	vdimas
	Дата:	22.07.08 18:22
	Оценка:

	От:	WolfHound
	Дата:	22.07.08 19:25
	Оценка:

	От:	WolfHound
	Дата:	22.07.08 20:30
	Оценка: