Re[10]: Java Parallel computing: multicore, Erlang, Scala
От: Gaperton http://gaperton.livejournal.com
Дата: 25.11.08 00:37
Оценка:
Здравствуйте, remark, Вы писали:

G>>>>Так будет не честнее, потому, что преимущество очевидно есть. Акторы гораздо, существеннее устойчивее к латентности системы. К тому же, в ряде случаев у тебя общей памяти натурально нет, и что удивительно, именно тогда, когда высока латентность каналов связи. Возьми кластер, связанный гигабитным ethernet. Что будем делать? Эмулировать общую память (словив огромную латентность)? Знаешь, какая именно просадка в производительности у тебя получится?


R>>>Это просто не тот случай, когда у разделяемой памяти есть приемущества. Зачем его вообще в таком контексте приводить???


G>>Ну надо же, откуда-то вдруг какие-то преимущества нарисовались, которых у разделяемой памяти нет. Зачем? Затем, что чуть выше ты сказал:


R>>>>>...они не имеют разделяемых данных, и связанных с ними проблем и преимуществ в принципе.

R>>>>>Я думаю, так будет честнее.

G>>Помнишь, что ты мне сказал? Теперь поступи так, как считаешь что будет честнее. Скажем, признай, что погорячился. Как вариант.


R>Я надеюсь, это шутка?


Ты о чем? О том, что у современных суперкомпьютеров нет общей памяти? Нет, это не шутка. Разделяемой памяти у них нет, правда.

R>Очевидные и широко-известные приемущества разделяемой памяти — это (1) скорость работы и (2) низкая латентность.


"Очевидное и широко-известное преимущество" не работает на современных суперкомпьютерах, состоящих их сотен или тысяч машин, соединенных сетями InifiniBand или подобными. Там рулит MPI, основанный на модели передачи сообщений.

R>А таком контексте вопрос по поводу факта наличия преимуществ у разделяемлой памяти меня просто шокирует.


Предлагаю перевести мозг в позицию on. И внимательно посмотреть, что я тебе пишу. И свои посты перечитать. Сопоставить. ПОДУМАТЬ.
Re[10]: Java Parallel computing: multicore, Erlang, Scala
От: Sinclair Россия https://github.com/evilguest/
Дата: 25.11.08 03:33
Оценка:
Здравствуйте, remark, Вы писали:
R>http://www.rsdn.ru/forum/message/3186016.1.aspx
Автор: remark
Дата: 24.11.08


R>

Хм. Я, наверное, очень тупой. Но ты сравниваешь какие-то непонятные мне вещи.
Давай сравним по честному.
Итак, у нас есть некоторое число s. Поток 1 передает его в поток 2; поток 2 прибавляет к s некое число q, известное только ему, и возвращает обратно.

Что у нас в случае разделяемой памяти?
поток 1:
unlock(&s);
wait(e1);
lock(&s);
read(&s)


поток 2:
lock(&s);
write(&s, s+q);
unlock(&s);
set(e1);


Это точно будет дешевле, чем обмен сообщениями?
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[11]: Java Parallel computing: multicore, Erlang, Scala
От: remark Россия http://www.1024cores.net/
Дата: 25.11.08 07:58
Оценка: +1
Здравствуйте, Gaperton, Вы писали:

R>>Я надеюсь, это шутка?


G>Ты о чем? О том, что у современных суперкомпьютеров нет общей памяти? Нет, это не шутка. Разделяемой памяти у них нет, правда.


Нет, я не об этом. Я о том, что ты серьёзно утверждаешь, что у разделяемой памяти нет приемуществ. Вопрос на подумать — почему, например, параллельная одновременная сборка мусора в .NET/Java реализована на основе разделяемой памяти, а не основе обмена сообщениями.


R>>Очевидные и широко-известные приемущества разделяемой памяти — это (1) скорость работы и (2) низкая латентность.


G>"Очевидное и широко-известное преимущество" не работает на современных суперкомпьютерах, состоящих их сотен или тысяч машин, соединенных сетями InifiniBand или подобными. Там рулит MPI, основанный на модели передачи сообщений.


R>>А таком контексте вопрос по поводу факта наличия преимуществ у разделяемлой памяти меня просто шокирует.


G>Предлагаю перевести мозг в позицию on. И внимательно посмотреть, что я тебе пишу. И свои посты перечитать. Сопоставить. ПОДУМАТЬ.


Называется "научи дурака богу молиться...". Я, конечно, извиняюсь, что я не привёл контекст, просто я думал, что это достаточно очевидно. Контекст — многоядерные/многопроцессорные машины, которые имеют разделяемую память и даже более — разделяемая память — это основная (и скорее всего — единственная) физическая модель взимодействия на них. И даже ещё более — даже машины в кластере внутри себя могут общаться на основе разделяемой памяти, если машины — многоядерные/многопроцессорные. Естественно, если мы говорим о распределенных системах, то тут разделяемая память не релевантна. Так же как не релевантен обмен сообщениями на, например, некоторых микроконтроллере, там даже скорее всего и ран-тайм-то не влезет. Ну и что из этого? Если следовать твоей линии рассуждений, то получается, что обмен сообщениями — это @#$%%^, т.к. он не может применяться на маленьких микроконтроллерах. Конечно, это неправильно. Невозможность применения обмена сообщенями в некоторых ситуациях ничего не говорит о нём как таковом, просто значит — это не его область. Точно так же и с разделяемой памятью — просто не пытайся привинчивать её к распределенным кластерам (я этого не делаю). У неё другая область применения — и там у неё есть преимущества.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[11]: Java Parallel computing: multicore, Erlang, Scala
От: remark Россия http://www.1024cores.net/
Дата: 25.11.08 08:24
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Хм. Я, наверное, очень тупой. Но ты сравниваешь какие-то непонятные мне вещи.

S>Давай сравним по честному.
S>Итак, у нас есть некоторое число s. Поток 1 передает его в поток 2; поток 2 прибавляет к s некое число q, известное только ему, и возвращает обратно.

S>Что у нас в случае разделяемой памяти?

S>поток 1:
S>
S>unlock(&s);
S>wait(e1);
S>lock(&s);
S>read(&s)
S>


S>поток 2:

S>
S>lock(&s);
S>write(&s, s+q);
S>unlock(&s);
S>set(e1);
S>


S>Это точно будет дешевле, чем обмен сообщениями?



Это ты и реализовал обмен сообщениями!!! Это не разделяемая память! Ключевое слово — разделяемая, потоки *разделяют* данные. Вот разделяемая память

class foo
{
private:
  mutex guard;
  int q;

public:
  int make(int s)
  {
    int r;
    guard.lock();
    r = q;
    guard.unlock();
    return r + s;
  }
};

void thread(foo& f)
{
  //...
  int s = rand();
  int r = f.foo(s);
  //...
}


Это будет дешевле и значительно быстрее чем обмен сообщениями — нет никаких очередей, блокирований/разблокирований потоков, аллокаций сообщений и т.д.
Это я привёл базовый вариант, данную конкретную задачу на С++ целесообразно реализовать так:

[ccode]
class foo
{
private:
std::mutex guard;
std::atomic<int> q;

public:
int make(int s)
{
return s + q.load(std::memory_order_relaxed);
}
};
[ccode]

Это уже будет на 2-3 порядка (!) (прописью: на два-три порядка, т.е. 100-1000 раз) эффективнее, чем обмен сообщениями. Тут исключили так же модификацию разделяемого состояния и убрали все барьеры памяти. Т.е. всё, что мы платим за синхронизацию — одна обычная инструкция загрузки из памяти. Плюс такая функция скорее всего будет встроена — т.е. вообще на всё-про-всё 0.5 такта.
Естественно, что такие оптимизации не приминимы во всех случаях, но тем не менее иногда они применимы, и зачастую задачу сводят к такому виду, что бы можно было применить такие оптимизации, и тогда можно получать на несколько порядков более эффективные решения, чем обмен сообщениями.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[12]: Java Parallel computing: multicore, Erlang, Scala
От: remark Россия http://www.1024cores.net/
Дата: 25.11.08 08:27
Оценка:
Здравствуйте, remark, Вы писали:

G>>Предлагаю перевести мозг в позицию on. И внимательно посмотреть, что я тебе пишу. И свои посты перечитать. Сопоставить. ПОДУМАТЬ.


R>Называется "научи дурака богу молиться...". Я, конечно, извиняюсь, что я не привёл контекст, просто я думал, что это достаточно очевидно. Контекст — многоядерные/многопроцессорные машины, которые имеют разделяемую память и даже более — разделяемая память — это основная (и скорее всего — единственная) физическая модель взимодействия на них. И даже ещё более — даже машины в кластере внутри себя могут общаться на основе разделяемой памяти, если машины — многоядерные/многопроцессорные. Естественно, если мы говорим о распределенных системах, то тут разделяемая память не релевантна. Так же как не релевантен обмен сообщениями на, например, некоторых микроконтроллере, там даже скорее всего и ран-тайм-то не влезет. Ну и что из этого? Если следовать твоей линии рассуждений, то получается, что обмен сообщениями — это @#$%%^, т.к. он не может применяться на маленьких микроконтроллерах. Конечно, это неправильно. Невозможность применения обмена сообщенями в некоторых ситуациях ничего не говорит о нём как таковом, просто значит — это не его область. Точно так же и с разделяемой памятью — просто не пытайся привинчивать её к распределенным кластерам (я этого не делаю). У неё другая область применения — и там у неё есть преимущества.


Дабы не быть голословным — вот пример, где разделяемая память на 2-3 порядка (100-1000 раз) быстрее, чем обмен сообщениями на современном многоядерном железе:
http://www.rsdn.ru/forum/message/3187084.1.aspx
Автор: remark
Дата: 25.11.08



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[12]: Java Parallel computing: multicore, Erlang, Scala
От: Sinclair Россия https://github.com/evilguest/
Дата: 25.11.08 09:01
Оценка:
Здравствуйте, remark, Вы писали:

R>Это ты и реализовал обмен сообщениями!!! Это не разделяемая память! Ключевое слово — разделяемая, потоки *разделяют* данные. Вот разделяемая память


R>
R>class foo
R>{
R>private:
R>  mutex guard;
R>  int q;

R>public:
R>  int make(int s)
R>  {
R>    int r;
R>    guard.lock();
R>    r = q;
R>    guard.unlock();
R>    return r + s;
R>  }
R>};

R>void thread(foo& f)
R>{
R>  //...
R>  int s = rand();
R>  int r = f.foo(s);
R>  //...
R>}
R>

Ничего не понимаю. Ты не воспроизвел пример. У тебя s осталась неизменной, ты разделил q. Это совсем другая задача, при обмене сообщениями она тоже решается гораздо дешевле, чем двунаправленный обмен. Просто один поток пошлет другому s.

R>Это будет дешевле и значительно быстрее чем обмен сообщениями — нет никаких очередей, блокирований/разблокирований потоков,

А как же lock()? Ты думаешь, lock() не приведет к блокировке потока в ожидании того, пока кто-то другой не сделает unlock()?
R>аллокаций сообщений и т.д.
аллокация — это искусственный термин. Её стоимость можно свести к нулю.

Пример на С++ опять же показывает, что можно и вовсе без синхронизации работать, если жить в одном потоке.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[13]: Java Parallel computing: multicore, Erlang, Scala
От: remark Россия http://www.1024cores.net/
Дата: 25.11.08 09:27
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Ничего не понимаю. Ты не воспроизвел пример. У тебя s осталась неизменной, ты разделил q.


Значит, я не понял условия. Опиши его, пожалуйста, более подробно. В условии вроде ничего не было про то, что надо изменить значение s. Но предположительно, если надо изменить s, значит допишем:
s = f.make(s);



S>Это совсем другая задача, при обмене сообщениями она тоже решается гораздо дешевле, чем двунаправленный обмен. Просто один поток пошлет другому s.


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


R>>Это будет дешевле и значительно быстрее чем обмен сообщениями — нет никаких очередей, блокирований/разблокирований потоков,

S>А как же lock()? Ты думаешь, lock() не приведет к блокировке потока в ожидании того, пока кто-то другой не сделает unlock()?

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

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


R>>аллокаций сообщений и т.д.

S>аллокация — это искусственный термин. Её стоимость можно свести к нулю.

Я понимаю. Стоимость практически всего можно свести к нулю. Однако на практике же из всех этих мелочей набегает достаточно значительная цифра. Кто Эрангом занимается скажите, сколько стоит передача запроса-ответа на многоядерном процессоре? Моя интуиция подсказывает, что не меньше 500 тактов должно быть.


S>Пример на С++ опять же показывает, что можно и вовсе без синхронизации работать, если жить в одном потоке.


Нет, ты упустил суть. Это — *многопоточный* код. Именно в многопоточном окружении мы платим всего одну инструкцию загрузки для синхронизации.



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[9]: Java Parallel computing: multicore, Erlang, Scala
От: prVovik Россия  
Дата: 25.11.08 10:07
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Зеленые потоки помогают только в том случае, когда мы реально выполняем в потоке длинную операцию с периодическими засыпаниями в синхронном ожидании события.

Что в свою очередь решается I/O APM
лэт ми спик фром май харт
Re[14]: Java Parallel computing: multicore, Erlang, Scala
От: Sinclair Россия https://github.com/evilguest/
Дата: 25.11.08 10:11
Оценка:
Здравствуйте, remark, Вы писали:
R>Значит, я не понял условия. Опиши его, пожалуйста, более подробно. В условии вроде ничего не было про то, что надо изменить значение s.
А иначе никаких разделяемых данных вовсе нет. Я имел в виду, что совместно используется общее значение s. Его нужно обязательно синхронизировать, потому что никакого контроля за тем, сколько потоков одновременно попробуют получать к нему доступ, нету.

R>Но предположительно, если надо изменить s, значит допишем:

R>
R>s = f.make(s);
R>

Вот этот код — он в каком потоке исполняется?
Ты по прежнему разделяешь данные q, при этом только на чтение.

Может быть, нужно представить какой-то более человеческий пример? Ну вот — пусть у нас N потоков считают сумму массива. Каждый считает свой фрагмент и кидают сумму в общую кучу. В разделяемой памяти каждый вычислительный поток захватывает мьютекс — делает += — отпускает мьютекс.
В MPS один актер хранит сумму, остальные кидают ему слагаемые. Он ловит и прибавляет к своей сумме. Кто больше потратит на синхронизацию?

R>Я понимаю. Стоимость практически всего можно свести к нулю. Однако на практике же из всех этих мелочей набегает достаточно значительная цифра.

Я имею в виду не к мелочи, а к нулю. В том смысле, что передача сообшения на самом деле может вообще никаких операций в памяти не проводить. Просто адрес перестает быть виден одному актеру и становится виден другому. Мы же работаем в общем адресном пространстве — значит, маршалинг не нужен.
Всё, что нужно от MPS для обеспечения thread-safety — это гарантия того, что ни один указатель не достижим со стека более чем одного потока. Единственные "разделяемые" указатели — это ссылки на очереди сообщений. Есть подозрение, что сделать это всё можно крайне эффективно — по крайней мере, не менее эффективно чем lock/unlock для разделяемых данных.

R> Кто Эрангом занимается скажите, сколько стоит передача запроса-ответа на многоядерном процессоре? Моя интуиция подсказывает, что не меньше 500 тактов должно быть.

Подождем, может ответят.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[10]: Java Parallel computing: multicore, Erlang, Scala
От: Sinclair Россия https://github.com/evilguest/
Дата: 25.11.08 10:46
Оценка:
Здравствуйте, prVovik, Вы писали:
V>Что в свою очередь решается I/O APM
Ну то есть опять же пул потоков.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[15]: Java Parallel computing: multicore, Erlang, Scala
От: remark Россия http://www.1024cores.net/
Дата: 25.11.08 11:02
Оценка:
Здравствуйте, Sinclair, Вы писали:

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

R>>Значит, я не понял условия. Опиши его, пожалуйста, более подробно. В условии вроде ничего не было про то, что надо изменить значение s.

S>А иначе никаких разделяемых данных вовсе нет. Я имел в виду, что совместно используется общее значение s. Его нужно обязательно синхронизировать, потому что никакого контроля за тем, сколько потоков одновременно попробуют получать к нему доступ, нету.


Как нет? q — разделяемые данные, множество потоков его меняют и множество — читают.


R>>Но предположительно, если надо изменить s, значит допишем:

R>>
R>>s = f.make(s);
R>>

S>Вот этот код — он в каком потоке исполняется?

В смысле в каком? В каком-то.

S>Ты по прежнему разделяешь данные q, при этом только на чтение.


q разделяется и на чтение и на запись.


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


S>Может быть, нужно представить какой-то более человеческий пример? Ну вот — пусть у нас N потоков считают сумму массива. Каждый считает свой фрагмент и кидают сумму в общую кучу. В разделяемой памяти каждый вычислительный поток захватывает мьютекс — делает += — отпускает мьютекс.

S>В MPS один актер хранит сумму, остальные кидают ему слагаемые. Он ловит и прибавляет к своей сумме. Кто больше потратит на синхронизацию?

Я думаю, что разделяемые данные будут эффективнее.


R>>Я понимаю. Стоимость практически всего можно свести к нулю. Однако на практике же из всех этих мелочей набегает достаточно значительная цифра.

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

Ну в очередь-то надо что-то класть. Если очередь на основе списка, то нужен элемент, который класть в этот список. Тем более, например, в Эрланг зачастую посылают (PID отправителя, данные), такой структуры у потока нет — она ему не нужна, занчит надо её аллокировать, скопировать в неё данные, потом освободить (это плюс к тому элементу, который находится в очереди на основе списка).


S>Всё, что нужно от MPS для обеспечения thread-safety — это гарантия того, что ни один указатель не достижим со стека более чем одного потока. Единственные "разделяемые" указатели — это ссылки на очереди сообщений. Есть подозрение, что сделать это всё можно крайне эффективно — по крайней мере, не менее эффективно чем lock/unlock для разделяемых данных.


Максимум, чего мне удавалось добиться на достаточно примитивной системе — 70 тактов на одно сообщение. Т.е. в 2 стороны будет 140 тактов. Я делал передачу разделяемых данных, без компированиый/сериализаций, сложно сказать, что будет эффективнее в общем случае (наверное ничего). Плюс у меня не было переключенй контекстов, т.к. не было блокирующих операций приёма сообщений, переключение контекста по-любому не меньше 10-20 тактов.
Большую часть съедают всякие мелочи — аллокация вспомогательной структуры — несколько тактов, освобождение — несколько тактов, инициализация — несколько, проверки тут да там — несколько и т.д.
Я подозреваю, что в Эрланг всё значительно хуже. Тем более, что там есть такие вещи как преобразование PID в указатель (или PID это сразу указатель?), сериализация/десериализация данных, переключения контекстов и т.д.

Плюс разделяемых данных, что их не обязательно делать с мьютексом. Можно с атомарными read-modify-write операциями, можно с обычными чтениями/записями, можно применять "не традиционные" мьютексы, которые способны сводить стоимость lock/unlock практически к нулю.



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[11]: Java Parallel computing: multicore, Erlang, Scala
От: prVovik Россия  
Дата: 25.11.08 11:11
Оценка: +1
Здравствуйте, Sinclair, Вы писали:

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

V>>Что в свою очередь решается I/O APM
S>Ну то есть опять же пул потоков.

Только потоки там халявные, и по сути не потоки вовсе. Это я к тому, что зелёные потоки для этого случая являются скорее средством повышения удобства программирования, чем необходимостью.
лэт ми спик фром май харт
Re[16]: Java Parallel computing: multicore, Erlang, Scala
От: Sinclair Россия https://github.com/evilguest/
Дата: 25.11.08 11:20
Оценка:
Здравствуйте, remark, Вы писали:

S>>А иначе никаких разделяемых данных вовсе нет. Я имел в виду, что совместно используется общее значение s. Его нужно обязательно синхронизировать, потому что никакого контроля за тем, сколько потоков одновременно попробуют получать к нему доступ, нету.


R>Как нет? q — разделяемые данные, множество потоков его меняют и множество — читают.

В твоем примере нет никакой записи в q.

R>В смысле в каком? В каком-то.

Почему этот поток считает, что s можно безопасно модифицировать? Это вырожденный пример. В жизни слагаемые приватны, разделяются именно суммы.
Там, где нет конфликта зависимостей, ничего интересного с точки зрения распараллеливания не происходит.

S>>Может быть, нужно представить какой-то более человеческий пример? Ну вот — пусть у нас N потоков считают сумму массива. Каждый считает свой фрагмент и кидают сумму в общую кучу. В разделяемой памяти каждый вычислительный поток захватывает мьютекс — делает += — отпускает мьютекс.

S>>В MPS один актер хранит сумму, остальные кидают ему слагаемые. Он ловит и прибавляет к своей сумме. Кто больше потратит на синхронизацию?

R>Я думаю, что разделяемые данные будут эффективнее.

На основании чего ты так думаешь?

R>Ну в очередь-то надо что-то класть. Если очередь на основе списка, то нужен элемент, который класть в этот список.

Пусть в этот список всегда кладется ссылка.

R>Тем более, например, в Эрланг зачастую посылают (PID отправителя, данные), такой структуры у потока нет — она ему не нужна, занчит надо её аллокировать, скопировать в неё данные, потом освободить (это плюс к тому элементу, который находится в очереди на основе списка).

Аллокирование у нас сделано заранее. Ведь данные уже есть, не так ли? Значит, сама передача может выполняться без аллокаций.

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

Ну, я плохо знаком с предметом, но что-то мне подсказывает, что в очереди на основе кольцевого буфера "аллокирование" и "освобождение" может быть сравнимым с выделением в хипе.

R>Плюс разделяемых данных, что их не обязательно делать с мьютексом. Можно с атомарными read-modify-write операциями, можно с обычными чтениями/записями, можно применять "не традиционные" мьютексы, которые способны сводить стоимость lock/unlock практически к нулю.


Вот хочется точно понять, почему такие же трюки неприменимы к передаче сообщений.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[17]: Java Parallel computing: multicore, Erlang, Scala
От: remark Россия http://www.1024cores.net/
Дата: 25.11.08 12:36
Оценка: 25 (2)
Здравствуйте, Sinclair, Вы писали:

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


S>>>А иначе никаких разделяемых данных вовсе нет. Я имел в виду, что совместно используется общее значение s. Его нужно обязательно синхронизировать, потому что никакого контроля за тем, сколько потоков одновременно попробуют получать к нему доступ, нету.


R>>Как нет? q — разделяемые данные, множество потоков его меняют и множество — читают.

S>В твоем примере нет никакой записи в q.


Ну как же нет? Если б не было записи, то не было бы и мьютекса. Подразумевается, что там есть ещё методы, которые захватывают мьютекс и меняют q. Я просто показал только относящуюся к делу часть.


R>>В смысле в каком? В каком-то.


S>Почему этот поток считает, что s можно безопасно модифицировать? Это вырожденный пример. В жизни слагаемые приватны, разделяются именно суммы.

S>Там, где нет конфликта зависимостей, ничего интересного с точки зрения распараллеливания не происходит.

Тут есть конфликт на q. Я просто так понял условие, в условии ничего не было про модификацию s, и уже тем более про одновременную. Так что должно модифицироваться? s? А q?



S>>>Может быть, нужно представить какой-то более человеческий пример? Ну вот — пусть у нас N потоков считают сумму массива. Каждый считает свой фрагмент и кидают сумму в общую кучу. В разделяемой памяти каждый вычислительный поток захватывает мьютекс — делает += — отпускает мьютекс.

S>>>В MPS один актер хранит сумму, остальные кидают ему слагаемые. Он ловит и прибавляет к своей сумме. Кто больше потратит на синхронизацию?

R>>Я думаю, что разделяемые данные будут эффективнее.

S>На основании чего ты так думаешь?

Что будет из себя представлять решение при использовании разделяемых данных — захватываем мьютекс, делаем небольшое действие, отпускаем. Всё. Операция закончена.

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

Если у нас будет паттерн запрос-ответ (клиент-сервер), то всё будет намного хуже — будет ещё блокирование клиента, отправка ответа, доставание ответа, разблокирование клиента.

Плюс системы на основе сообщений могут иметь ещё один неприятный момент. Этот пример с суммированием как раз ему подвержен. Представь у нас 4 ядра. На 3 ядрах работают агенты, которые постоянно генерируют сообщения для некого одного агента. Даже если мы выделим под этого одного агента отдельное ядро, то всё равно может быть такая ситуация, что другие 3 ядра генерируют для него работу быстрее, чем он может её обрабатывать. В результате — аварийное завершение. Очень неприятная ситуация, тем более, что её возникновение зависит от того, на какой аппаратной платформе мы работаем.
Разделяемая память тут предоставляет некую форму "лоад-балансинга", что типа каждый сам за себя — генерируешь много работы, сам же её и делаешь; делаешь много работы — сильно загружен — генерируешь меньше работы. Т.е. поток не может просто взять и по-хитрому сгенерировать много работы для кого-то другого, тем самым вызывая перегрузку системы.

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


R>>Ну в очередь-то надо что-то класть. Если очередь на основе списка, то нужен элемент, который класть в этот список.

S>Пусть в этот список всегда кладется ссылка.

Ну а узел-то для списка откуда взять?! Ты представляешь как устроен список? Даже если мы хотим туда положить указатель на что-то, то куда мы его записываем?
Далее, если в сообщении должен идти указатель на отправителя, то в общем-то особо не на что будет класть туда указатель. Надо будет формировать дополнительную структуру, которая содержит, указатель на данные + указатель на отправителя. Тем более, что системы на основе сообщений обычно ещё кладут в сообщение ряд вспомогательных полей.



R>>Тем более, например, в Эрланг зачастую посылают (PID отправителя, данные), такой структуры у потока нет — она ему не нужна, занчит надо её аллокировать, скопировать в неё данные, потом освободить (это плюс к тому элементу, который находится в очереди на основе списка).

S>Аллокирование у нас сделано заранее. Ведь данные уже есть, не так ли? Значит, сама передача может выполняться без аллокаций.

Ну это сложный вопрос — смотри выше.


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


S>Ну, я плохо знаком с предметом, но что-то мне подсказывает, что в очереди на основе кольцевого буфера "аллокирование" и "освобождение" может быть сравнимым с выделением в хипе.


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


R>>Плюс разделяемых данных, что их не обязательно делать с мьютексом. Можно с атомарными read-modify-write операциями, можно с обычными чтениями/записями, можно применять "не традиционные" мьютексы, которые способны сводить стоимость lock/unlock практически к нулю.


S>Вот хочется точно понять, почему такие же трюки неприменимы к передаче сообщений.



Модель не предусматривает таких оптимизаций. Мы же сознательно открещиваемся от разделяемых данных. А это как раз оптимизации, которые хорошо ложатся именно на разделяемые данные, потому что данные... *разделяемые* по сути своей.
Ну вот например. Есть некий объект, который обновляется, допустим раз в 100 мкс. Допустим — таблица маршрутизации. Множество потоков/агентов постоянно его читают, он им нужен для выполнения каждой операции (маршрутизации).
В модели с разделяемыми данными потоки могут просто читать объект. При этом можно элиминировать возможные блокирования и модификации разделяемых данных для читателей — т.е. будет экстремально легко и линейная масштабируемость. Обновляющий поток — изменяет этот объект.
В модели с обменом сообщениями как мы можем это решить?
Было бы интересно так же услышать мнение Gaperton, который говорит, что у разделяемых данных нет никаких преимуществ вообще.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[16]: Java Parallel computing: multicore, Erlang, Scala
От: cadet354 Россия
Дата: 26.11.08 07:42
Оценка:
Здравствуйте, remark, Вы писали:



R>Не подскажу, как такое смоделировать... там вроде ещё упоминалась возможность вручную создавать фильтры, может так можно... а может и что встроенное есть. Кстати, там по-моему совсем на днях новая версия вышла.

точно, правда не новая версия, а релиз(странно как-то без беты, сразу из CTP) , появилась платная студия, вот я только не понял, а рантаймом бесплатно можно пользоваться?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[9]: Java Parallel computing: multicore, Erlang, Scala
От: remark Россия http://www.1024cores.net/
Дата: 27.11.08 07:26
Оценка:
Здравствуйте, Gaperton, Вы писали:

R>>Это просто не тот случай, когда у разделяемой памяти есть приемущества. Зачем его вообще в таком контексте приводить???


G>Ну надо же, откуда-то вдруг какие-то преимущества нарисовались, которых у разделяемой памяти нет. Зачем? Затем, что чуть выше ты сказал:


R>>>>...они не имеют разделяемых данных, и связанных с ними проблем и преимуществ в принципе.

R>>>>Я думаю, так будет честнее.

G>Помнишь, что ты мне сказал? Теперь поступи так, как считаешь что будет честнее. Скажем, признай, что погорячился. Как вариант.


Прокомментируй, пожалуйста, вот это сообщение:
http://www.rsdn.ru/forum/message/3187522.1.aspx
Автор: remark
Дата: 25.11.08



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[12]: Java Parallel computing: multicore, Erlang, Scala
От: Gaperton http://gaperton.livejournal.com
Дата: 27.11.08 23:40
Оценка:
Здравствуйте, remark, Вы писали:

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


R>>>Я надеюсь, это шутка?


G>>Ты о чем? О том, что у современных суперкомпьютеров нет общей памяти? Нет, это не шутка. Разделяемой памяти у них нет, правда.


R>Нет, я не об этом. Я о том, что ты серьёзно утверждаешь, что у разделяемой памяти нет приемуществ.


Да ну? Правда штоли? А можно мне посмотреть на мой пост, где я это говорю?

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

http://rsdn.ru/forum/message/3183921.1.aspx
Автор: remark
Дата: 21.11.08

...они не имеют разделяемых данных, и связанных с ними проблем и преимуществ в принципе.


Обрати внимание на конец фразы.
Re[13]: Java Parallel computing: multicore, Erlang, Scala
От: Gaperton http://gaperton.livejournal.com
Дата: 27.11.08 23:55
Оценка:
Здравствуйте, remark, Вы писали:

R>Дабы не быть голословным — вот пример, где разделяемая память на 2-3 порядка (100-1000 раз) быстрее, чем обмен сообщениями на современном многоядерном железе:

R>http://www.rsdn.ru/forum/message/3187084.1.aspx
Автор: remark
Дата: 25.11.08


Ага. Быстрее. До той поры, пока ты не догадаешься в данном примере применить для обмена сообщениями lock-free очередь. Тогда, волшебным образом, обмен сообщениями станет быстрее разделяемой памяти .

Хреновый у тебя пример, на самом деле.
Re[14]: Java Parallel computing: multicore, Erlang, Scala
От: Cyberax Марс  
Дата: 28.11.08 00:24
Оценка:
Здравствуйте, Gaperton, Вы писали:

G>Ага. Быстрее. До той поры, пока ты не догадаешься в данном примере применить для обмена сообщениями lock-free очередь. Тогда, волшебным образом, обмен сообщениями станет быстрее разделяемой памяти .

G>Хреновый у тебя пример, на самом деле.
Да, можно сделать намного лучше

Проблема с message passing в том, что работать с большими массивами меняющихся данных так может быть очень неудобно.
Sapienti sat!
Re[13]: Java Parallel computing: multicore, Erlang, Scala
От: remark Россия http://www.1024cores.net/
Дата: 28.11.08 07:38
Оценка:
Здравствуйте, Gaperton, Вы писали:

R>>>>Я надеюсь, это шутка?


G>>>Ты о чем? О том, что у современных суперкомпьютеров нет общей памяти? Нет, это не шутка. Разделяемой памяти у них нет, правда.


R>>Нет, я не об этом. Я о том, что ты серьёзно утверждаешь, что у разделяемой памяти нет приемуществ.


G>Да ну? Правда штоли? А можно мне посмотреть на мой пост, где я это говорю?


Ну тогда — извини. Я просто не понял (и не понимаю) твоё высказывание, что будет НЕ честнее сказать, что у модели актёров нет преимуществ и недостатков разделяемой памяти (вместо только недостатков).


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


G>http://rsdn.ru/forum/message/3183921.1.aspx
Автор: remark
Дата: 21.11.08

G>

G>...они не имеют разделяемых данных, и связанных с ними проблем и преимуществ в принципе.


G>Обрати внимание на конец фразы.


Извини, но это я тоже не понимаю...


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.