Вдоль или поперек?

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

Представьте себе простейшую вычислительную задачу - найти сумму нескольких чисел. Если в вашем распоряжении один компьютер, то все просто и понятно: "длина" вычисления прямо пропорциональна количеству складываемых чисел. А если компьютеров несколько? Для определенности будем считать, что у вас P компьютеров (то есть "ширина вычислений" равна P), обмен данными между ними занимает пренебрежимо малое время, а количество слагаемых равно 1000. Предположим, что каждое элементарное сложение занимает 1 единицу времени (такт). Мы будем интересоваться алгоритмом решения задачи за наименьшее число тактов на P компьютерах - это количество обозначим T_P. Очевидно, что T₁=1000: в каком порядке ни складывай исходные числа, между ними стоит 999 знаков "+", поэтому для получения результата требуется ровно 999 сложений.

Случай P=2

Второй компьютер позволяет сократить время вычисления почти вдвое. Это достигается, например так: пока первый компьютер находит сумму первых 500 чисел, второй в это же время суммирует остальные 500 чисел. После 499 тактов останется выполнить только одно действие - сложить две накопленных суммы S₁ и S₂ и получить общую сумму S=S₁+S₂. Это сложение выполняется на любом из двух компьютеров, а вторая машина в это время "отдыхает". Итак, T₂=500.

Случай P=4

Разделим весь процесс на четыре равные части. Через 249 тактов компьютеры получат суммы S₁, S₂, S₃ и S₄. За следующий такт можно найти одновременно S₁+S₂ и S₃+S₄, ну, и затем уже вычислить S₁+S₂+S₃+S₄. Итого T₄=251, но при этом в последнем такте работает только один из четырех компьютеров.

Случай P=500

Представим на секундочку, что у нас есть именно такое число компьютеров. Тогда мы можем одновременно выполнить все 500 попарных сложений, на втором шаге получить 250 сумм по 4, и т. д. Чем ближе к концу, тем меньшее число компьютеров будет загружено. На десятом шаге делается последнее сложение (T₅₀₀=10), а остальные 499 компьютеров в этот момент простаивают…

Я описал эти вычисления так подробно только потому, что из них становится понятна принципиальная особенность распараллеливания: чем "шире" идет процесс вычислений, тем он становится короче, но одновременно возрастает доля "холостого хода". В любом случае, PхT_PіT₁, и равенство достигается только в том случае, если в каждом такте вычислений задействованы все имеющиеся компьютеры. При этом рассмотренная мною задача не является чем-то исключительным, - наоборот, почти так же обстоит дело и при построении параллельных алгоритмов для решения самых разных задач.

Одним из важнейших показателей эффективности параллельного алгоритма считается "ценность" f_P=T₁/(PхT_P²) - чем она выше, тем лучше. В приведенных примерах f₁=999/999²=0,00100, f₂=0,00199, f₄=0,00396, f₅₀₀=999/(500*10²)=0,01998. Является ли 0,01998 максимально возможной ценностью? Оказывается, нет - но это уже сюжет для небольших задачек, которые я и предлагаю читателям.

Задача 1

Решите задачу суммирования для P=100 компьютеров за 16 тактов. А потом - для P=175 компьютеров за 12 тактов. ("Ценность" второго решения f₁₇₅ примерно равна 0,03964)

Задача 2

Попробуйте ответить на "обратные" вопросы: какое наименьшее число компьютеров позволяет решить задачу за 13 тактов? за 14 тактов? за 15 тактов? Можно ли решить задачу за 16 тактов, если число компьютеров меньше 100?

Задача 3

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

Перейдем теперь к другим задачам на ту же тему.

Задача 4

Проследите, как изменятся решения всех предыдущих задач (и ответы к ним), если количество суммируемых чисел увеличить в 10 раз.

Понятно, что оптимальное (в смысле ценности) число компьютеров меняется в зависимости от "объема" конкретной задачи. Но надо хорошо понимать, что наша задача - лишь модель, а в реальности при увеличении числа компьютеров сильно растет доля времени, которое непродуктивно тратится на передачу данных между компьютерами.

Задача 5

Решите заново все предыдущие задачи, считая теперь, что передача числа от одного компьютера к другому тоже занимает один такт (при этом числа могут передаваться параллельно).

Задача 6

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

P(x) = a₀ + a₁ x + a₂ x² +…+ a_n xⁿ.

Задача 7

Представьте, что ваш знакомый задумал число, не превышающее одного миллиона, а вам надо его угадать, задавая вопросы, на которые знакомый может отвечать "да" или "нет". Классический метод деления пополам - дихотомии - гарантирует успех за 20 попыток (2²⁰>1000000). А теперь попробуйте придумать экономный "параллельный" алгоритм: задуманное число знают P=4 разных человека, а вы можете за одну "попытку" задать каждому из них свой вопрос и получить ответ на него. Сколько попыток при этом вам хватит для отгадывания задуманного числа? А если P=5? А при P=10?

Можете присылать мне решения понравившихся задач, я постараюсь ответить на все письма читателей.