Пионер 1988-02, страница 63

н

м

т

т @

Как обхитрить Мегафлопа

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

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

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

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

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

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

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

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

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

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

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

— Чтобы всем чипам работа досталась. Сумма не