Здравствуйте, remark, Вы писали:
R>Как сделать управление памятью и временем жизни объектов таким же дешевым, как мы могли его иметь в однопоточном окружении?
Помоему в .NET для многопоточноо выделения/освобождения памяти разницы нет.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, jazzer, Вы писали:
J>>В двух словах — пока тебе не понадобилось взаимодействовать с внешним миром, ты можешь оставаться в области чистого ФП.
R>Ок. Т.е. мы уже говорим о меньшей части ПО.
Нет, не так. Я говорю о том, что твоя программа состоит из разных вещей — когда-то ты просто вычисляешь, когда-то ты взаимодействуешь с внешним миром. И на этапе подготовки того, что ты собираешься внешнему миру сказать, ты можешь заниматься чистым ФП со встроенной параллельностью. Но, естественно, для этого программу надо организовать соответствующим образом.
J>>Если у тебя в программе в основном происходит это взаимодействие — тогда да, смысл особого в параллелизме нет вообще,
R>Только взаимодействие с внешним миром... таких наверное всё же очень мало... на ум приходят только прокси/релей сервера.
Да не только. Взаимодействие с миром — это не только сеть, это и БД, и гуй, и даже просто память, если внешний мир для нас (для нашей функции) — это другой поток/процесс.
R>Всё таки некоторые вопросы для меня остались не отвеченными. R>Как сделать потенциальный, не реализованный параллелизм бесплатным? (на Intel TBB он сейчас стоит 530 тактов на одну потенциально параллельную задачу)
это хз. что там с work stealing? вроде, там более-менее дешево получалось.
R>Как обрабатывать разделяемые структуры данных? А ну да, ну да, знаю, в джедайских языках их нет.
это которые в разделяемой памяти сидят? как обычно, организовывать доступ соответвующим образом (т.е. явные читатели, явные писатели); если данных не очень много, делать двойную-тройную буферизацию (в каком-то смысле это аналогично сборке мусора).
R>Как сделать бесплатным переиспользование результатов, вычисленных другим потоком?
можно чуть больше деталей? R>Как автоматически подобрать гранулярность работы?
пусть ос/процессоры этим занимаются. имхо, минимальная гранулярность — вызов функции. R>Как автоматически организовать работу в виде сбалансированного дерева? (вот это очень интересно, хотя бы теоретически)
это хз
с другой стороны, если мы добьемся дешевой параллельности, то сбалансированность дерева уже не будет играть решающей роли. R>Как сделать управление памятью и временем жизни объектов таким же дешевым, как мы могли его иметь в однопоточном окружении?
можно чуть больше деталей?
Здравствуйте, gandjustas, Вы писали:
R>>А сейчас есть функциональные языки, где я могу автоматически получить прирост производительности на многоядерном компьютере, написав обычную "однопоточную" программу?
G>SQL подойдет?
Нет. Я конечно имел в виду языки общего назначения, не DSL. Извиняюсь за возникшие недоразумения.
Здравствуйте, jazzer, Вы писали:
J>Нет, не так. Я говорю о том, что твоя программа состоит из разных вещей — когда-то ты просто вычисляешь, когда-то ты взаимодействуешь с внешним миром. И на этапе подготовки того, что ты собираешься внешнему миру сказать, ты можешь заниматься чистым ФП со встроенной параллельностью. Но, естественно, для этого программу надо организовать соответствующим образом.
Если есть только одна задача в каждый момент времени, то наверное можно. Не знаю. Есть какие-то прототипы? Очень бы хотелось посмотреть.
Но есть есть много задач в каждый момент времени, то распараллеливание каждой отдельной задачи может быть далеко не лучшим решением. Компилятор/рантайм должен уметь как-то это автоматически понимать, что конкретно распараллеливать. Пока же я так понимаю ты говоришь о том, что компилятор пытает тупо распараллелить всё, что потенциально параллелиться.
Есть есть всего несколько задач в каждый момент времени, то ещё непонятнее. Толи выполять их последовательно распараллеливания каждую максимально возможно. Толи выполнять все вместе распараллеливания каждую максимально возможно. Толи выполнять все вместе, но распараллеливания умеренно.
J>>>Если у тебя в программе в основном происходит это взаимодействие — тогда да, смысл особого в параллелизме нет вообще,
R>>Только взаимодействие с внешним миром... таких наверное всё же очень мало... на ум приходят только прокси/релей сервера. J>Да не только. Взаимодействие с миром — это не только сеть, это и БД, и гуй, и даже просто память, если внешний мир для нас (для нашей функции) — это другой поток/процесс.
Не понял мысль. Т.е. если моя программа что-то пишет и читает и из памяти, то тогда смысла особого в параллелизме нет вообще?
R>>Всё таки некоторые вопросы для меня остались не отвеченными. R>>Как сделать потенциальный, не реализованный параллелизм бесплатным? (на Intel TBB он сейчас стоит 530 тактов на одну потенциально параллельную задачу)
J>это хз. что там с work stealing? вроде, там более-менее дешево получалось.
Это и есть work stealing. И это только потенциальный не реализованный параллелизм. Т.е. это оверхед на задачу, которую мы выделили в коде как задачу, которую потенциально ран-тайм при желании может выполнить параллельно, но в действительности она была выполнена не параллельно, а в том же потоке. Оверхед на реализованный параллелизм больше в несколько раз. Как раз поэтому важно организовывать задачи в сбалансированное дерево — что бы было побольше не реализованного параллелизма, и поменьше реализованного.
R>>Как обрабатывать разделяемые структуры данных? А ну да, ну да, знаю, в джедайских языках их нет. J>это которые в разделяемой памяти сидят? как обычно, организовывать доступ соответвующим образом (т.е. явные читатели, явные писатели); если данных не очень много, делать двойную-тройную буферизацию (в каком-то смысле это аналогично сборке мусора).
Допустим у нас есть такая программа:
int x = 0;
for (int i = 0; i != size; ++i)
x = x + f(array[i]);
Допустим компилятор все проанализировал и понял где тут конфликтующие чтения и записи.
Подход при котором на каждой итерации переменная x будет защащаться мьютексом, может затормозить параллельную версию в разы односительно однопоточной.
Можно попробовать применить агрегацию, т.е. у каждого потока есть локальная "копия" переменной х, и он инкрементирует имеено её, а по завершении цикла локальные копии всех потоков складываются в глобальную копию. Но это может повлечь за собой изменение семантики программы, если, например, другой поток "наблюдает" за имененением переменной х и он хочет видеть постепенные изменения в процессе работы. Как это определить без явной помощи программиста, повлечёт это за собой изменение семантики или нет, — не понятно.
"Буферизация" тоже может повлечь за собой изменение семантики программы. Не понятно, толи потоку достаточно видеть некий (возможно не полность актуальный) снапшот структуры, толи он хочет именно видеть все инкрементальные динамические изменения структуры. Возможно применение снапшотов сделает поведение программы нежелательным, возможно не сделает. Как это определить компилятору — не понятно.
R>>Как сделать бесплатным переиспользование результатов, вычисленных другим потоком?
J>можно чуть больше деталей?
LP>>Я могу ошибаться, но мне кажется,что синхронизаций нужно не так много. Давай представим стек ленивых вызовов ввиде разделяемой структуры-дерева, в узлах которого будут вызовы функций, которые согласно п.1 чистые. Тогда второй поток может идти по дереву, вычисляя узлы дерева и записывая результат вычисления в те же узлы совершенно без всяких синхронизаций с основным потоком. Потом, когда придет время для раскрутки, реализация смотрит — если узел на N-ом уровне дерева вычислен, то берет значение из узла, если нет, то вычисляет его.
R>Если без синхронизации, то одно значение может вычисляться N (количество процессоров) раз. Значение может быть *очень* тяжелым. Например при использовании рекурсии одно значение может представлять половину всей работы.
R>>Как автоматически подобрать гранулярность работы?
J>пусть ос/процессоры этим занимаются. имхо, минимальная гранулярность — вызов функции.
Имеется в виду в контексте того, что потенциальный параллелизм у нас совсем не бесплатный. Ты же сейчас не запускаешь отдельный ядерный поток, что бы сложить 2 числа.
R>>Как автоматически организовать работу в виде сбалансированного дерева? (вот это очень интересно, хотя бы теоретически)
J>это хз J>с другой стороны, если мы добьемся дешевой параллельности, то сбалансированность дерева уже не будет играть решающей роли.
Я пока тут не вижу ничего, что могло бы дать принципиальный сдвиг.
Параллельность никогда не будет такой же дешевой как обычный вызов функции. Многоядерная/многопроцессорная система — это распределенная система. Нельзя делать действия и передавать данные в распределенной системе так же быстро как и локально. Если работа распределенной системы станет быстрее, значит локальная обработка тоже станет ещё быстрее. Разрыв будет всегда.
R>>Как сделать управление памятью и временем жизни объектов таким же дешевым, как мы могли его иметь в однопоточном окружении?
J>можно чуть больше деталей?
В однопоточном окружении для управления памятью и временем жизни можно применять подсчёт ссылок или GC. Если мы начинаем активно "раскидывать" небольшие элементы работы по разным физическим процессорам, значит и подсчёт ссылок/GC будет уже "распределенный". Т.е. что бы построить полный граф живых объектов нам надо не только с "локальными" данными процессора поработать, но и с "локальными" данными всех остальных процессоров. Это не может быть "так же быстро". См. выше про распределенные системы.
R>>>> J>>> R>> J>
J>чувствую, к пятнице мы напьемся
Это смотря, что у тебя в этой кружке
Здравствуйте, remark, Вы писали:
R>Допустим у нас есть такая программа: R>
R>int x = 0;
R>for (int i = 0; i != size; ++i)
R> x = x + f(array[i]);
R>
... R>Можно попробовать применить агрегацию, т.е. у каждого потока есть локальная "копия" переменной х, и он инкрементирует имеено её, а по завершении цикла локальные копии всех потоков складываются в глобальную копию. Но это может повлечь за собой изменение семантики программы, если, например, другой поток "наблюдает" за имененением переменной х и он хочет видеть постепенные изменения в процессе работы. Как это определить без явной помощи программиста, повлечёт это за собой изменение семантики или нет, — не понятно.
Надо просто писать не как в твоем примере, а что нибудь вроде:
var x = array.Select(item => f(item)).Aggregate((val, agg) => agg + val);
И тогда уже можно будет паралллелить.
... << RSDN@Home 1.2.0 alpha 4 rev. 1095 on Windows Vista 6.0.6001.65536>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, remark, Вы писали:
R>>Допустим у нас есть такая программа: R>>
R>>int x = 0;
R>>for (int i = 0; i != size; ++i)
R>> x = x + f(array[i]);
R>>
AVK>... R>>Можно попробовать применить агрегацию, т.е. у каждого потока есть локальная "копия" переменной х, и он инкрементирует имеено её, а по завершении цикла локальные копии всех потоков складываются в глобальную копию. Но это может повлечь за собой изменение семантики программы, если, например, другой поток "наблюдает" за имененением переменной х и он хочет видеть постепенные изменения в процессе работы. Как это определить без явной помощи программиста, повлечёт это за собой изменение семантики или нет, — не понятно.
AVK>Надо просто писать не как в твоем примере, а что нибудь вроде: AVK>
Здравствуйте, remark, Вы писали:
R>Здравствуйте, jazzer, Вы писали:
J>>Нет, не так. Я говорю о том, что твоя программа состоит из разных вещей — когда-то ты просто вычисляешь, когда-то ты взаимодействуешь с внешним миром. И на этапе подготовки того, что ты собираешься внешнему миру сказать, ты можешь заниматься чистым ФП со встроенной параллельностью. Но, естественно, для этого программу надо организовать соответствующим образом.
R>Если есть только одна задача в каждый момент времени, то наверное можно. Не знаю. Есть какие-то прототипы? Очень бы хотелось посмотреть.
Да любые задачи, работающие поквантово в цикле, имхо.
Например, торговый сервер, которй решает, когда что купить или продать на бирже.
У него в памяти есть огромная модель рынка и того, что он о рынке думает, он ее крутит так и эдак, вычисляя оптимальную функцию — это этап вычислений.
В результате вычисления функции у нас получается набор ордеров, которые мы посылаем на биржу покапать или продавать — это момент общения с внешним миром.
Теперь принимаем все, что к нам за время расчетов успело с биржи прийти и обновляем модель — это тоже момент общения и обновления модели.
После чего опять уход в расчеты.
Уверен, то же самое можно применить в динамических играх и тому подобных приложениях.
Вот этап вычислений и нужно параллелить, и это отлично удастся сделать, если не наполнять этот этап общением с внешним миром.
R>Но есть есть много задач в каждый момент времени, то распараллеливание каждой отдельной задачи может быть далеко не лучшим решением. Компилятор/рантайм должен уметь как-то это автоматически понимать, что конкретно распараллеливать. Пока же я так понимаю ты говоришь о том, что компилятор пытает тупо распараллелить всё, что потенциально параллелиться.
Так распараллеливание же не ручное должно быть.
Оно должно быть на уровне пометок "вот это можно исполнять как бог на душу положит" (т.е. фьючерсы и слегка континуэйшены).
А как оно уже будет в реальности исполняться — зависит от текущей ситуации с загрузкой процессоров.
R>Есть есть всего несколько задач в каждый момент времени, то ещё непонятнее. Толи выполять их последовательно распараллеливания каждую максимально возможно. Толи выполнять все вместе распараллеливания каждую максимально возможно. Толи выполнять все вместе, но распараллеливания умеренно.
Это все должно решаться на этапе исполнения. Насколько я понимаю, work stealing для этого и существует: как только процессор освободился, он просто забирает себе очередной квант работы. Нет свободных процессоров — все исполняется последовательно. Все свободны — все максимально параллельно.
Насчет накладных расходов — не знаю, я статью на эту тему читал года два, наверное, назад и у меня сложилось впечатление, что при таком подходе накладные расходы небольшие. ...но память у меня хоть и не девичья, но и не GMR
J>>>>Если у тебя в программе в основном происходит это взаимодействие — тогда да, смысл особого в параллелизме нет вообще,
R>>>Только взаимодействие с внешним миром... таких наверное всё же очень мало... на ум приходят только прокси/релей сервера. J>>Да не только. Взаимодействие с миром — это не только сеть, это и БД, и гуй, и даже просто память, если внешний мир для нас (для нашей функции) — это другой поток/процесс.
R>Не понял мысль. Т.е. если моя программа что-то пишет и читает и из памяти, то тогда смысла особого в параллелизме нет вообще?
Если только пишет и только читает — да, если нет параллельности по данным, разумеется. Потому что нечего параллелить, по большому счету. Тем более автоматически.
R>>>Всё таки некоторые вопросы для меня остались не отвеченными. R>>>Как сделать потенциальный, не реализованный параллелизм бесплатным? (на Intel TBB он сейчас стоит 530 тактов на одну потенциально параллельную задачу)
J>>это хз. что там с work stealing? вроде, там более-менее дешево получалось.
R>Это и есть work stealing. И это только потенциальный не реализованный параллелизм. Т.е. это оверхед на задачу, которую мы выделили в коде как задачу, которую потенциально ран-тайм при желании может выполнить параллельно, но в действительности она была выполнена не параллельно, а в том же потоке. Оверхед на реализованный параллелизм больше в несколько раз. Как раз поэтому важно организовывать задачи в сбалансированное дерево — что бы было побольше не реализованного параллелизма, и поменьше реализованного.
ну, возможно, это издержки нынешних архитектур.
Вполне возможно, народ в Интеле/АМД напряжется и родит специальные однотактные команды под это дело, чтоб оверхед не был заметен.
R>>>Как обрабатывать разделяемые структуры данных? А ну да, ну да, знаю, в джедайских языках их нет. J>>это которые в разделяемой памяти сидят? как обычно, организовывать доступ соответвующим образом (т.е. явные читатели, явные писатели); если данных не очень много, делать двойную-тройную буферизацию (в каком-то смысле это аналогично сборке мусора).
R>Допустим у нас есть такая программа: R>
R>int x = 0;
R>for (int i = 0; i != size; ++i)
R> x = x + f(array[i]);
R>
R>Допустим компилятор все проанализировал и понял где тут конфликтующие чтения и записи. R>Подход при котором на каждой итерации переменная x будет защащаться мьютексом, может затормозить параллельную версию в разы односительно однопоточной. R>Можно попробовать применить агрегацию, т.е. у каждого потока есть локальная "копия" переменной х, и он инкрементирует имеено её, а по завершении цикла локальные копии всех потоков складываются в глобальную копию. Но это может повлечь за собой изменение семантики программы, если, например, другой поток "наблюдает" за имененением переменной х и он хочет видеть постепенные изменения в процессе работы. Как это определить без явной помощи программиста, повлечёт это за собой изменение семантики или нет, — не понятно.
Стоп, если мы ведем речь о том, чтоб вот взять нынешнюю императивную программу и ее автоматически распараллелить без участия программиста — тут я не играю
Автоматически параллелятся только чистые ФП-программы.
Все остальное параллелится явно (по крайней мере на уровне деклараций) и автоматически в рантайме, согласно декларациям.
R>"Буферизация" тоже может повлечь за собой изменение семантики программы. Не понятно, толи потоку достаточно видеть некий (возможно не полность актуальный) снапшот структуры, толи он хочет именно видеть все инкрементальные динамические изменения структуры. Возможно применение снапшотов сделает поведение программы нежелательным, возможно не сделает. Как это определить компилятору — не понятно.
Буферизация, естественно, явная. Т.е. в примере с торговым сервером выше можно иметь обсчет снапшота модели параллельно с созданием нового снапшота по мере прихода новых сообщений с биржи. А когда модель посчитана и выдано решение о действиях на бирже, модель сразу же начинае обсчиываться на новом снапшоте, а поток, обрабатывающий сообщения, переключается на обновление старого, и т.д.
Здесь, поскольку модель никак не изменяется в течение кванта расчетного времени, мы имеет для расчетов чистое ФП, со встроенной параллельностью.
R>>>Как сделать бесплатным переиспользование результатов, вычисленных другим потоком?
J>>можно чуть больше деталей?
J>>пусть ос/процессоры этим занимаются. имхо, минимальная гранулярность — вызов функции.
R>Имеется в виду в контексте того, что потенциальный параллелизм у нас совсем не бесплатный. Ты же сейчас не запускаешь отдельный ядерный поток, что бы сложить 2 числа.
это все на откуп ос, ей просто должна быть предоставлена информация относиельно того, что можно параллелить, плюс информация о тяжести каждого действия (это вполне по силам сгенерить компилятору, но и программер тоже может явно чего-нть задать). А ос, зная свои возможности вообще и в текущий момент, пусть решает, что параллелить, а что — нет. Соответственно, на очередной версии оси/железа с меньшими накладными расходами на параллельность та же программа может параллелиться в рантайме гораздо сильнее.
R>>>Как автоматически организовать работу в виде сбалансированного дерева? (вот это очень интересно, хотя бы теоретически)
J>>это хз J>>с другой стороны, если мы добьемся дешевой параллельности, то сбалансированность дерева уже не будет играть решающей роли.
R>Я пока тут не вижу ничего, что могло бы дать принципиальный сдвиг. R>Параллельность никогда не будет такой же дешевой как обычный вызов функции. Многоядерная/многопроцессорная система — это распределенная система. Нельзя делать действия и передавать данные в распределенной системе так же быстро как и локально. Если работа распределенной системы станет быстрее, значит локальная обработка тоже станет ещё быстрее. Разрыв будет всегда.
если части этой системы независимы, то расходы возникнуть только на этапе синхронизации результатов.
Обмен данными — имхо, тупиковый путь, если мы говорим о микропараллельности.
Для микропараллельности никакого взаимодействия между задачами быть не должно.
R>>>Как сделать управление памятью и временем жизни объектов таким же дешевым, как мы могли его иметь в однопоточном окружении?
J>>можно чуть больше деталей?
R>В однопоточном окружении для управления памятью и временем жизни можно применять подсчёт ссылок или GC. Если мы начинаем активно "раскидывать" небольшие элементы работы по разным физическим процессорам, значит и подсчёт ссылок/GC будет уже "распределенный". Т.е. что бы построить полный граф живых объектов нам надо не только с "локальными" данными процессора поработать, но и с "локальными" данными всех остальных процессоров. Это не может быть "так же быстро". См. выше про распределенные системы.
тут я ничего не могу сказать, я не знаю, как эта задача решена в нормальных быстродействующих ФП-языках.
Но опять же, я думаю, поскольку у нас всегда строгое дерево для вычисления результата, то под такой сценарий можно и GC заточить соответственно.
R>>>>> J>>>> R>>> J>> R>
J>>чувствую, к пятнице мы напьемся R>Это смотря, что у тебя в этой кружке
Ну а что у настоящего программиста в кружке.... Конечно, его борода!
Здравствуйте, jazzer, Вы писали:
R>>Если есть только одна задача в каждый момент времени, то наверное можно. Не знаю. Есть какие-то прототипы? Очень бы хотелось посмотреть.
J>Да любые задачи, работающие поквантово в цикле, имхо. J>Например, торговый сервер, которй решает, когда что купить или продать на бирже.
Не, не это
Я имел в виду пример языка общего назначения, который умеет автоматически распараллеливать "однопоточный код", и что бы получалось хоть какое-то ускорение по сравнению с однопоточной версией.
Здравствуйте, jazzer, Вы писали:
R>>Но есть есть много задач в каждый момент времени, то распараллеливание каждой отдельной задачи может быть далеко не лучшим решением. Компилятор/рантайм должен уметь как-то это автоматически понимать, что конкретно распараллеливать. Пока же я так понимаю ты говоришь о том, что компилятор пытает тупо распараллелить всё, что потенциально параллелиться.
J>Так распараллеливание же не ручное должно быть. J>Оно должно быть на уровне пометок "вот это можно исполнять как бог на душу положит" (т.е. фьючерсы и слегка континуэйшены). J>А как оно уже будет в реальности исполняться — зависит от текущей ситуации с загрузкой процессоров.
Тогда я не понимаю, о чём речь... я подразумевал, что речь идёт о следующей ситуации — программист пришет "обычную однопоточную программу", а язык магически всё распараллеливает.
Если мы говорим о явных фьючерсах и континуэйшанах, то просто берёшь Cilk образца 95 года и вот — пожалуйста.
плюс он вообще понимал, что он пишет именно параллельную программу, а не однопоточную, то тут нет никаких проблем автоматически выполнить оставшуюся "нижнюю" часть задачи — т.е. раскидать по процессорам, сделать лоад балансинг, отследить когда вызывать континуэйшены и т.д.
Здравствуйте, remark, Вы писали:
R>Я имел в виду пример языка общего назначения, который умеет автоматически распараллеливать "однопоточный код", и что бы получалось хоть какое-то ускорение по сравнению с однопоточной версией.
Семен Семеныч
Я так понял, что ты вопрос задавал вообще, а не конкретно про автоматическое распараллеливание изначально однопоточного кода.
Про ето я мало могу сказать, разве что такую вот гримасу скорчить:
Хотя в ФП-языках вроде вообще нет деления на однопоточный/параллельный код. Так что чем тебе не пример? Грубо говоря, пока в дереве вычисления выражение только чистое ФП, без всяких монад (а компилятор способен это распознать в месте вызова) — параллель как хочешь.
R>
Здравствуйте, jazzer, Вы писали:
R>>Я имел в виду пример языка общего назначения, который умеет автоматически распараллеливать "однопоточный код", и что бы получалось хоть какое-то ускорение по сравнению с однопоточной версией.
J>Семен Семеныч J>Я так понял, что ты вопрос задавал вообще, а не конкретно про автоматическое распараллеливание изначально однопоточного кода. J>Про ето я мало могу сказать, разве что такую вот гримасу скорчить:
Дык это ж вроде ты изначально сказал, что типа функциональные языки обеспечат автоматическое (т.е. без усилий программиста, т.е. программист как писал так и пишет) "использование" параллельного железа: http://gzip.rsdn.ru/forum/message/3023737.1.aspx
J>Хотя в ФП-языках вроде вообще нет деления на однопоточный/параллельный код. Так что чем тебе не пример? Грубо говоря, пока в дереве вычисления выражение только чистое ФП, без всяких монад (а компилятор способен это распознать в месте вызова) — параллель как хочешь.
Ну вот это я как раз обсуждаю — возможно ли это автоматически распараллелить. Не формально, а именно так, что бы был хотя бы какой-то увеличивающийся прирост производительности. И что бы программисту при этом не надо было вникать в детали распараллеливания.
Здравствуйте, jazzer, Вы писали:
R>>Есть есть всего несколько задач в каждый момент времени, то ещё непонятнее. Толи выполять их последовательно распараллеливания каждую максимально возможно. Толи выполнять все вместе распараллеливания каждую максимально возможно. Толи выполнять все вместе, но распараллеливания умеренно.
J>Это все должно решаться на этапе исполнения. Насколько я понимаю, work stealing для этого и существует: как только процессор освободился, он просто забирает себе очередной квант работы. Нет свободных процессоров — все исполняется последовательно. Все свободны — все максимально параллельно. J>Насчет накладных расходов — не знаю, я статью на эту тему читал года два, наверное, назад и у меня сложилось впечатление, что при таком подходе накладные расходы небольшие. ...но память у меня хоть и не девичья, но и не GMR
Ну вот для TBB как есть — 530 тактов на потенциально параллельную задачу (это на Intel Core, на Pentium4 получается 650).
В принципе, конечно, это можно сделать быстрее. У них реализация, конечно, не самая плохая, но и не самая оптимальная. При чём это касается не только каких-то деталей кода, но и местами применяемых алгоритмов.
Есть ещё идея глубокой интеграции work-stealing'а в язык, типа как в LazyThreads. Они там жёсткие хаки делали, типа совмещения стека выполнения потока и work-stealing deque в одно. Ну и там можно всякие вещи использовать, типа например регистр fs отвести под указатель на контекст потока, что бы его можно было на пару команд быстрее доставать.
Если все эти вещи совместить (эффективная реализация, эффективные алгоритмы, глубокая интеграция в язык), то... ну не знаю, наверное тактов 20-40 на задачу можно получить.
R>>Это и есть work stealing. И это только потенциальный не реализованный параллелизм. Т.е. это оверхед на задачу, которую мы выделили в коде как задачу, которую потенциально ран-тайм при желании может выполнить параллельно, но в действительности она была выполнена не параллельно, а в том же потоке. Оверхед на реализованный параллелизм больше в несколько раз. Как раз поэтому важно организовывать задачи в сбалансированное дерево — что бы было побольше не реализованного параллелизма, и поменьше реализованного.
J>ну, возможно, это издержки нынешних архитектур. J>Вполне возможно, народ в Интеле/АМД напряжется и родит специальные однотактные команды под это дело, чтоб оверхед не был заметен.
Возможно. Когда-то.
Вообще я видел ресерч/академические статьи с разработками аппаратных легковесных шедулеров типа work-stealing deque...
То, что сейчас происходит с Интел/АМД на забавные мысли наводит. Не знаю, насколько это воплотится...
Раньше производители процессоров целись на эффективное выполнение С программ. Ну это типа был такой стандарт де-факто. Сейчас это вроде как отошло на второй план, сейчас Java и C#.
Однако, когда началась работа над многопоточностью С++0x, в процесс были вовлечены большинство вендоров процессоров — AMD, Intel, IBM, ARM. И как бы они сейчас не переключились с поддержки таких фич как транзакционная память и легковесный шедулинг опять на эффективную поддержку С/С++ Пока то, что сделали вендоры процессоров — это обновили техническую документацию по процессорам, что бы было более чётко соответствие модели памяти С++0х, что бы было видно как она "ложится" на этот процессор. Будут ли они делать более эффективную поддержку низкоуровневых С++ примитивов синхронизации... посмотрим
R>>>>>> J>>>>> R>>>> J>>> R>> J>
J>>>чувствую, к пятнице мы напьемся R>>Это смотря, что у тебя в этой кружке J>Ну а что у настоящего программиста в кружке.... Конечно, его борода!
Ну тогда мы скорее к пятнице новый язык программирования создадим
Здравствуйте, jazzer, Вы писали:
J>>>с другой стороны, если мы добьемся дешевой параллельности, то сбалансированность дерева уже не будет играть решающей роли.
R>>Я пока тут не вижу ничего, что могло бы дать принципиальный сдвиг. R>>Параллельность никогда не будет такой же дешевой как обычный вызов функции. Многоядерная/многопроцессорная система — это распределенная система. Нельзя делать действия и передавать данные в распределенной системе так же быстро как и локально. Если работа распределенной системы станет быстрее, значит локальная обработка тоже станет ещё быстрее. Разрыв будет всегда.
J>если части этой системы независимы, то расходы возникнуть только на этапе синхронизации результатов. J>Обмен данными — имхо, тупиковый путь, если мы говорим о микропараллельности. J>Для микропараллельности никакого взаимодействия между задачами быть не должно.
Пусть даже на этапе синхронизации результатов. Просто считать значение булевской переменной этот_узел_дерева_уже_выполнен из кэша другого ядра — 200 тактов. Если все вычисление сводится к суммированию 2 чисел, то получается немного накладно. Уж лучше ничего не считывать, а посчитать. Но с другой стороны, если вычисление длится 1 час, то допустить его делать 2 процессорам одновременно — не приемлимо.
R>>>>Как сделать управление памятью и временем жизни объектов таким же дешевым, как мы могли его иметь в однопоточном окружении?
J>>>можно чуть больше деталей?
R>>В однопоточном окружении для управления памятью и временем жизни можно применять подсчёт ссылок или GC. Если мы начинаем активно "раскидывать" небольшие элементы работы по разным физическим процессорам, значит и подсчёт ссылок/GC будет уже "распределенный". Т.е. что бы построить полный граф живых объектов нам надо не только с "локальными" данными процессора поработать, но и с "локальными" данными всех остальных процессоров. Это не может быть "так же быстро". См. выше про распределенные системы.
J>тут я ничего не могу сказать, я не знаю, как эта задача решена в нормальных быстродействующих ФП-языках.
Пока он однопоточный, то её можно и не решать.
J>Но опять же, я думаю, поскольку у нас всегда строгое дерево для вычисления результата, то под такой сценарий можно и GC заточить соответственно.
Здравствуйте, maggot, Вы писали:
M>Ну а разве ещё в скорость оперативной памяти производительность компьютера не упирается?
Для каких-то приложений, безусловно, упирается.
M>Может её скорость когда нибудь поднимится до скорости кэша... Хотя, может и тут какой-то закон действует
Закон есть такой, что скорость передачи информации ограничена скоростью света. Следовательно пока вся ОП не будет внутри процессора, и при этом процессор останется очень маленьким, скорость ОП не будет равна скорости процессора (кэша). По крайней мере, что касается латентности.
Здравствуйте, remark, Вы писали:
J>>Хотя в ФП-языках вроде вообще нет деления на однопоточный/параллельный код. Так что чем тебе не пример? Грубо говоря, пока в дереве вычисления выражение только чистое ФП, без всяких монад (а компилятор способен это распознать в месте вызова) — параллель как хочешь.
R>Ну вот это я как раз обсуждаю — возможно ли это автоматически распараллелить. Не формально, а именно так, что бы был хотя бы какой-то увеличивающийся прирост производительности. И что бы программисту при этом не надо было вникать в детали распараллеливания.
ну вот я и сказал как, вроде.
мы о чем спорим вообще? что в ФП автораспараллеливание невозможно? так оно возможно.
Оно слищком дорого в рантайме? Не знаю, не мерял, я с чистыми ФП в продакшене не работаю, у меня С++
TBB, все-таки — это не чистое ФП. Тут надо на окамл смотреть какой-нть, он, вроде, самый быстрый среди всех ФП-языков.
Плюс я не уверен, что с ростом популярности ФП мы в результае получим процессоры, которые делают все это дешевым.
Получили же мы, в конце концов, дешевую strcmp ценой в одну инструкцию (repz или как ее там)...
R>>> J>> R>
Здравствуйте, jazzer, Вы писали:
J>мы о чем спорим вообще? что в ФП автораспараллеливание невозможно? так оно возможно.
Ага. Щаз.
Если есть зависимости по данным то ничего ты не распаралелишь.
А если в языке есть _|_, а она есть везде (кроме total function programming) то ваще тушите свет.
J>Оно слищком дорого в рантайме? Не знаю, не мерял, я с чистыми ФП в продакшене не работаю, у меня С++ J>TBB, все-таки — это не чистое ФП. Тут надо на окамл смотреть какой-нть, он, вроде, самый быстрый среди всех ФП-языков.
ОКамл слишком грязный.
Там вобще не подергаешься.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, jazzer, Вы писали:
J>>мы о чем спорим вообще? что в ФП автораспараллеливание невозможно? так оно возможно. WH>Ага. Щаз. WH>Если есть зависимости по данным то ничего ты не распаралелишь. WH>А если в языке есть _|_, а она есть везде (кроме total function programming) то ваще тушите свет.
Ну не совсем ты прав на мой взгляд...
Вычисление кодаты как раз и есть _|_
К тому же ряд _|_ ловится вполне себе тривиально (e.g. деление на ноль, неполный паттерн-матчинг тоже сюда отнести, думаю, можно).
А про зависимости согласен, только вот _|_ — это немного другое, хотя местами эти вещи (зависимости и _|_) связаны.
Пока то, что сделали вендоры процессоров — это обновили техническую документацию по процессорам, что бы было более чётко соответствие модели памяти С++0х, что бы было видно как она "ложится" на этот процессор. Будут ли они делать более эффективную поддержку низкоуровневых С++ примитивов синхронизации... посмотрим 
