LINUX.ORG.RU
Форум — Development  

Где применима многопоточность, а где нет (алгоритмы)?

 ,


2

1

Т.е. какие алгоритмы могут быть запрограммированы многопоточно, а какие наоборот - нет. Мне нужно сделать презентацию на эту тему. Буду рад полезным ссылкам. Не могу найти общей информации по этой теме. Для многопоточности: последовательность в алгоритме должна быть согласованной и линеаризуемоей. Но как доказать линеаризуемость алгоритма!? Да и примеры хорошо бы привести. Нашел инфу по теме http://www.slideshare.net/elizarov/ss-33970658 но там слишком обобщенно всё. Мне нужно больше практических примеров (примеров алгоритмов).


← Серверное приложение на Haskell: что происходит с памятью.
git - вытащить из remote конкретный коммит. →

поиск в отсортированном массиве например, разные там рекурсивные алгоритмы, сам короче ищи, вопрос элементарный

abs ★★★
()
Ответ на: комментарий от abs

поиск в отсортированном массиве например, разные там рекурсивные алгоритмы

по вашему такое можно вставлять в презентацию? гг

сам короче ищи, вопрос элементарный

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

закон Амдала

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

mrXorg
() автор топика
Ответ на: комментарий от mrXorg

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

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

Tark ★★★
()
Ответ на: комментарий от mrXorg

мне нужно доказать, может ли вообще алгоритм работать в нескольких потоках

Построй зависимости вычислений в виде графа, посчитай самый длинный путь от начала до конечного состояния. Если он меньше, чем N-1, алгоритм можно выполнять параллельно.

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

Построй зависимости вычислений в виде графа, посчитай самый длинный путь от начала до конечного состояния. Если он меньше, чем N-1, алгоритм можно выполнять параллельно.

Что-то я не думаю, что всё так просто... Очень хочется чего-нибудь полезного почитать на эту тему, никак не найду ничего толкового

mrXorg
() автор топика

Поддержу тему. Давно хотел почитать про мат. часть многопоточности, но всё никак руки не доходили. Буду очень благодарен за полезные ссылки.

gear ★★★
()

зависимость

а) по данным б) по коду отсюда и пляши

anonymous
()
Ответ на: комментарий от mrXorg

покопай на тему сетей Петри и пи-исчисления (исчисления параллельных процессов), каналов Хоара и сопрограмм (и синхронного/асинхронного кода)

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

anonymous
()

в смысле, виды параллелизма: по коду и по данным. отсюда и пляши. если по данным — SIMD/MIMD и GPGPU/OpenCL, если по коду — пи-исчисление и сети Петри. и т.д. и т.п.

anonymous
()

презентация на урок информатики штоле?

скажем так... если сам не способен к обработке и анализу информации, то берём классическую книгу хоара и делаем её конспект. за прошедшие с её выпуска 30 лет ничего принципиально не изменилось.

anonymous
()
Ответ на: комментарий от bogus_result

В Кормене есть немного.

Спасибо, это то что я искал.

mrXorg
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Серверное приложение на Haskell: что происходит с памятью.
Development
git - вытащить из remote конкретный коммит. →