Читаем Игры с Чипом полностью

Игры с Чипом

— Слушай, Сережа, а ты здорово вырос за последний год, — сказал Чип, одновременно для разминки перемножая десятизначные числа. Он вообще никогда не сидел спокойно — говорил фразу и, пока Сережа думал над ответом, успевал решить про себя какую-нибудь задачу. Потом быстро обдумывал Сережины слова, отвечал и снова погружался в расчеты. Однако его собеседник ничего не замечал — так быстро Чип думал.

Чип говорил, что Сережа был для него медленным внешним устройством, а расчет шел в фоновом режиме. То есть на фоне расчета он разговаривал с Сережей, как солист в опере поет на фоне оркестра. Например, ЭВМ может одновременно печатать на машинке и решать сложную задачу. Пока машинка печатает строку, Чип успевает сделать массу вычислений. Потом он прервет решение задачи, пошлет в печать новую строку и возобновит работу с того места, где остановился. Иначе Чипу пришлось бы очень долго, по его понятиям, сидеть без дела, а машины этого не любят. Поэтому в хороших вычислительных машинах могут одновременно решаться десятки проблем, и одна программа не замечает присутствия остальных.

Все это Чип успел рассказать сам себе за ту секунду, которая потребовалась Сереже, чтобы ответить:

— Да. на целых пять сантиметров. А ты почему не растешь? Когда ты станешь таким же большим, как твой папа — Центральный процессор?

— Мы, чипы, не растем, а сразу рождаемся взрослыми: большими или маленькими, умными или глупыми, быстрыми или медленными. Но бывает так, что несколько медленных чипов оказываются быстрее одного быстрого.

— Десять черепах обгоняют одного зайца?

— Почти так, но поскольку машины сами думать не умеют, им должен помочь хороший программист. Вот как-то раз приехал к нам из-за границы нахальный чип Мегафлоп. Был он маленький, гладкий и все ходил и похвалялся: «Эх вы, старикашки! Вам бы на пенсию или в демонтаж! Краска облуплена, час поработаете и перегреваетесь, а уж считаете вы совсем как черепахи. Пока вы два числа сложите, я — сто, пока вы два числа умножите, я — двести. На что вы годны?!» Обидно нам стало, и решили мы пойти к программисту Лене и попросить помощи — неужто и правда нами можно только гвозди забивать?

Леня засмеялся и сказал: «Чипы! Решите-ка такую задачу: по длинной улице идут сплошным потоком машины. Между каждой парой машин может проскочить один человек. За какое время перейдет на другую сторону улицы рота солдат, если один человек перебегает улицу за десять секунд?». «За тысячу секунд», — хором ответили чипы. «Ну и неверно! Кто вам мешает построить солдат вдоль улицы, и тогда вся рота перейдет за десять секунд.

Так же и из вас, медленных чипов, собирают параллельные машины, а мы, программисты, ломаем потом голову: как распределить работу, чтобы вы все решали одну задачу, но каждый делал свои кусок и не зависел от товарищей. Все крупнейшие современные машины устроены по такому принципу. Предложите вашему Мегафлопу соревноваться. Например, сложить, кто быстрее, тысячу чисел. Он будет суммировать их все подряд, а вы сделайте так, как я нарисовал. Вы вместе за десять шагов сложите всю тысячу потому, что вас много, а я дал вам хороший параллельный алгоритм».

— Погоди-ка, — перебил Чипа Сережа. — Ведь тысяча — это не степень двойки. Разделил пополам — 500, сложил 500 пар, разделил на 250 пар, снова попарно сложил, разделил на 125 пар, сложил — и стоп! Дальше не делится! Не додумал твой Леня алгоритм.

— Молодец, — усмехнулся Чип, — не зря я тебя учил. Что же, в этом случае проще всего добавить три числа, равных нулю.

— А зачем нули добавлять?

— Чтобы всем чипам работа досталась. Сумма не изменится, а слагаемых станет 128, их можно до конца разбивать на пары. А еще проще, как только количество чисел становится нечетным, к ним добавляется еще одно число, равное нулю.

— Удивительно! Вроде лишнюю работу делаем, а получается быстрее.

— Зато все чипы при деле, в ногу шагают! — Чип подмигнул Сереже и продолжил: - Так мы и сделали, а потом и сами предложили Мегафлопу вторую задачу: найти наибольшее из тысячи чисел. (Кстати, как это сделать за десять шагов?) Потом третью: вывести оценки за четверть для всей школы (для каждого ученика его оценка за четверть по каждому предмету есть среднее арифметическое его оценок, полученных в течение четверти). Как, по-твоему, мы решили эту задачу?

Проиграл Мегафлоп раз, проиграл другой и от стыда сгорел.

Но тут появилась новая проблема! Приехал младший брат Мегафлопа — Гигафлоп. Он работает так быстро, что за ним не угнаться. Давай предложим ребятам придумать такой алгоритм, чтобы все чипы работали одновременно, ни один не стоял без дела.

— А над какой задачей они должны работать? — спросил Сережа.

— И задачу пусть ребята сами придумают. Чипы могут делать что угодно: умножать, делить, сравнивать... из того, что мы научились делать в прошлом году.

— А на конверте пусть ребята напишут «Сразимся с Гигафлопом».