Каковы теоретические верхние пределы параллелизуемости?

Question

Меня интересует теоретический верхний предел распараллеливания вычислений.

Допустим, у нас есть процесс, который требует времени T для завершения с 1 ядром.

• Если процесс совершенно не распараллеливается из-за последовательного узкого места (обычно чтение с диска), это займет T секунд, независимо от того, какие ядра мы используем.
• Если процесс идеально распараллеливается , мы могли бы завершить его за T/K секунды, используя K ядер.
• Если у нас есть N эквивалентных процессов для завершения, где N >> K, тогда мы должны запускать несколько процессов параллельно, а не распараллеливать какой-либо конкретный процесс. Идеально распараллеливаемые процессы в любом случае займут NT/K времени, но задания, содержащие последовательное узкое место, могут занять до NT времени. вычислительные рабочие нагрузки, которые потребуют меньше чем T/K секунд каждая для выполнения с K ядрами? Другими словами, рабочие нагрузки, которые на самом деле требуют меньше совокупного общего времени, когда доступно больше ядер. В этом случае было бы предпочтительнее распараллеливать каждое задание в последнем случае с N процессами.

Answer 1

Да, и это большой и важный класс проблем: те, которые связаны с вводом / выводом.

Представьте, что у вас есть 10 000 экземпляров процесса, и каждый экземпляр занимает около 9 секунд ввода-вывода и 1 секунда процессора / время обработки. Теперь скажите, что у вас есть тысяча процессоров. Если вы просто распределяете 10000 экземпляров проблем по 1000 процессорам, временной интервал (общее время выполнения всей работы по всем процессорам) займет около 100 секунд (10 процессов на каждом процессоре, 10 секунд каждый, 100 секунд каждый процессор). Если вместо этого вы запустите все 10000 процессов параллельно, вы увидите, что процесс составляет около 10 секунд.

Это также работает внутри процесса. Представьте себе процесс, который имеет 10 фаз, которые все связаны с вводом / выводом и полностью независимы. Если каждая фаза занимает 10 секунд, то общее время запуска процесса на одном ядре составляет 100 секунд. Если вы распараллелите это на 10 ядрах, то время будет ближе к 10 секундам. Это может быть хорошим кандидатом для вашего «супер-распараллеливаемого» процесса, который выиграет не только от распределения процессов на разные машины, но и от распараллеливания отдельных процессов.

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