[Теория] Многопоточные программы

Двое маляров красят одну стену. С разных концов. Из одного ведра с краской. Дальше - думать.

Если эти потоки ещё и выполняются параллельно разными процессорами/ядрами, то выгода очевидна, имхо. Формально, гугли закон Амдала.

Пример: матричные операции на многопроцессорных системах. Если выполнять их последовательно, один процессор будет во всю напрягаться, а остальные простаивать. Если разобьем на потоки, получим более-менее равномерную загрузку процессоров и уменьшение времени выполнения чуть ли не в N раз, где N - количество процессоров/ядер.

Выгода зависит от алгоритма - какие-то не распараллеливаются, какие-то дают линейный прирост с добавлением потоков

Формально, гугли закон Амдала.

То что надо, спасибо.

>Формально, гугли закон Амдала.

Закон Амдала - куита. Еще один К.О. захотел свое имя увековечить, написав всем очевидную и равно бесполезную хрень

гугли закон Амбала

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

Ну я об этом собвстенно и толкую. Выражение очевидное каждому школьнику не должно приписываться «открывателю» в 20-ом веке.

> Еще один К.О. захотел свое имя увековечить, написав всем очевидную и равно бесполезную хрень

Но ведь смог! ;)

>Выражение очевидное каждому школьнику не должно приписываться «открывателю» в 20-ом веке.

Так он 1967 года. 43 года назад надо было быть Амдалом чтобы его сформулировать. Фундаментальное ограничение в параллельном программировании, актуально до сих пор. Так держать, Амдал!

>>Закон Амдала - куита. Еще один К.О. захотел свое имя увековечить, написав всем очевидную и равно бесполезную хрень

Неистово плюсую.

Туда же отправляются теорема Найквиста, принцип Дирихле и прочие самоочевидости.

теорема Найквиста

это, которая Котельникова?

>С разных концов. Из одного ведра с краской.

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

Она самая. Она фактически гласит что самым грубым образом синус с длиной волны L можно представить столбиками шириной L/2. Гениально.

Амдал? основатель AMD? :)

Хуже чем одному?

>Она самая. Она фактически гласит что самым грубым образом синус с длиной волны L можно представить столбиками шириной L/2. Гениально.

Ну.. не совсем. Она, кстати, сходу не очевидна.

Она гласит, что любой сигнал состоящий из частот с длинной волны меньше L можно _абсолютно_точно_ представить последовательностью замеров через период L/2.

>>Она гласит, что любой сигнал состоящий из частот с длинной волны меньше L можно _абсолютно_точно_ представить последовательностью замеров через период L/2.

Только не меньше L, а больше L.

Математическая суть утверждения лежит именно в упомянутой мной формулировке.

Эм... да, больше

Хотя нет, пожалуй там все сложнее чем просто дискретизация синуса. Хотя нужная двойка всплывает уже на данном этапе рассуждений, и очень хочется её привязать к теореме имеено отсюда.

Пока неясно как.

Она гласит, что любой сигнал состоящий из частот с длинной волны меньше L можно _абсолютно_точно_ представить последовательностью замеров через период L/2.

trivial fix: больше L.

Ой ли? Выходит, что для абсолютно точной передачи звуковой частоты (<20 kHz) достаточно частоты дискретизации 40 kHz?

>Хуже чем одному?

не, хуже, чем одному в правильном варианте.

Смотря, где ведро.

Вариант 1. Если злополучное ведро находится у одного из красящих, то будет быстрее, но немного, поскольку второй человек будет бегать от своего конца забора макать кисточки к первому.

Вариант 2. Если ведро неподвижно находится на некотором расстоянии от забора, то суммарное время на непосредственную покраску и макание для двоих будет меньше,чем для одного, но больше, чем для одного, при условии, что ведро находится у человека (вариант 1), и время на макание сопоставимо с нулём.

Т.е. два, три, ..., миллион, ... неоптимальных процессов могут быть менее эффективными, чем один оптимальный.

>>Выходит, что для абсолютно точной передачи звуковой частоты (<20 kHz) достаточно частоты дискретизации 40 kHz?

Да, только напомню, что речь идет об абстрактном бесконечном периодическом сигнале, бегущем из бесконечности в бесконечность.

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

>Ой ли? Выходит, что для абсолютно точной передачи звуковой частоты (<20 kHz) достаточно частоты дискретизации 40 kHz?

Угу. И это на самом деле сразу не очевидно. Но могу в общем написать приблизительный наглядные рассуждения.

>Для импульных сигналов это не верно. Если импульс разложить в ряд Фурье, то очевидно всплывут сверхвысокие частоты из-за участков скачкообразного увеличения амплитуды.

Угу... Но на всякий случай (случай аудиофильства например ;), то же самое справедливо и для всяких аналоговых фильтров.

Но могу в общем написать приблизительный наглядные рассуждения.

да-да, напишите. И алгоритм идеальной интерполяции тоже, желательно.

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

А если минимальный фронт этого импульса 1/40000 секунды?

>>Угу. И это на самом деле сразу не очевидно. Но могу в общем написать приблизительный наглядные рассуждения.

Интересно было бы найти простое рассуждение. У Шеннона оно заунывно-формалистичное и мёртвое.

Разумеется это верно для обрезания частоты вообще, независимо от реализации.

случай аудиофильства например

мимо ;)

Выгоду в чём?

> Неистово плюсую. Туда же отправляются теорема Найквиста, принцип Дирихле и прочие самоочевидости.

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

Вот так надо думать и о многопоточности.

Я не о малярах, а о понимании проблем многопоточности.

Хм.. Кажется я немного погорячился :(

Ну ладно. Вообще это следует из прямого и обратного дискретных преобразований Фурье и из их аддитивности.

> вместо 4 слов «критерий компактности в метрическом пространстве»

а в чем этот критерий заключается?

> А если минимальный фронт этого импульса 1/40000 секунды?

К.О. Сообщает, что непереодические сигналы имееют бесконечный спектр.

Но не всё так плохо — в реальном мире идеального представления, естественно, не нужно.

> На самом деле даже простые практически очевидные вещи выигрывают из-за того, что их как-то называют. Я бы согласился, например, назвать именем какого-либо умершего, и совершенно незаслужившего это ученого критерий компактности в метрическом пространстве — вместо 4 слов «критерий компактности в метрическом пространстве» будет 2 — «критерий Пупкина».

Пф, никогд не понимал, зачем вешать подобные ярлыки и зачем их запоминать. Без них — проще. Меньше ненужно информации в голове

ога, а Пифагор тогда вообще просто позорный лох :)

ЗЫ логика ущербна

>ога, а Пифагор тогда вообще просто позорный лох :)

в плане? Если о теореме Пифагора идет речь, то она не такая тривиальная, как закон Амдала и в свое время была огого.

>ога, а Пифагор тогда вообще просто позорный лох :)

в плане? Если о теореме Пифагора идет речь, то она не такая тривиальная, как закон Амдала и в свое время была огого.

ещё какая тривиальная, на сегодняшний момент конечно

Энштейн - он, знаете ли, тоже просто аккумулировал уже известные занния - не больше и, некоторые физики из тех кто в теме, подобно снобам в треде, до сих пор воротят лицо и говорят «фу-фу»

на мой взгляд логика таки ущербна

>>на мой взгляд логика таки ущербна

на мою логику такой взгляд ущербен

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

Пифагора бы не подняли, а того, кто всерьёз выделяет принцип Дирихле — засмеяли бы.

Причем очевидно что сам Дирихле не виноват, наверняка, всё пошло от какого-нибудь тугодума-гуманитария, вцепившегося однажды в этот единственный понятый им факт и раздувшего из него свою «философию».

>>ещё какая тривиальная, на сегодняшний момент конечно

Вот именно что на сегодняшний момент.

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

а того, кто всерьёз выделяет принцип Дирихле

а что не так с принципом Дирихле?

Всерьёз радоваться его пониманию мог бы только альпийский йодный дегенерат.

>>ещё какая тривиальная, на сегодняшний момент конечно

Вот именно что на сегодняшний момент.

непонятно тогда с какой колокольни Вы, к примеру, оцениваете теорему Котельникова? многие, как Вы выражаетесь, школьники до сих пор вообще не в курсе что это

сдаётся мне Вы малец загоняетесь и, если вещь для Вас по тем или иным причинам очевидна, не считаете её за важную, такая практика - порочна

и да, весьма серьёзные и уважаемые люди не корчат такие вот брезгливые лица, как Вы думаете почему?

Всерьёз радоваться его пониманию мог бы только альпийский йодный дегенерат.

не, чёт я не понимаю, может я не так спрашиваю или ещё что?

я спросил: ЧТО не так с принципом Дирихле??

Вы ответить можете или так и будете клована изображать?

Про Котельникова я выше написал, что погорячился.

Что конкретно ты не разжевал в этой формулировке?

Погугли, даже на вики недоумевают по этому поводу.