Сначала половина процессоров посылает свои частичные суммы другой половине процессоров, где эти частичные суммы складываются вместе. Затем одна четверть процессоров (половина от половины) посылает эти новые частичные суммы другой четверти процессоров (оставшейся половине от половины) для следующего раунда суммирования. Это деление пополам, отправка и получение продолжаются до тех пор, пока не будет получена единая сумма всех чисел. Пусть Рп представляет номер процессора, send(x.y) является подпрограммой, которая посылает по объединяющей сети процессору значение у, a receive() является функцией, получающей значение из сети для этого процессора.
Этот код делит все процессоры на отправителей и получателей, и каждый получающий процессор получает только одно сообщение, поэтому мы можем допускать, что получающий процессор будет простаивать до приема сообщения. Таким образом, отправка и получение могут использоваться в качестве примитивов синхронизации, а также для обмена данными, поскольку процессоры знают о передаче данных.
Если количество узлов нечетное, средний узел не участвует в отправке-получении. Тогда граница (limit) устанавливается таким образом, чтобы этот узел стал наивысшим узлом в следующей итерации.
Уточнение. В данном примере подразумевается, что передача сообщения осуществляется практически так же быстро, как и сложение. На самом деле отправка и прием сообщений осуществляются намного медленнее. Для лучшей сбалансированности вычислений и передачи данных можно провести оптимизацию, чтобы множество сумм от других процессоров получало меньшее количество узлов.
Разработчикам намного проще проектировать компьютеры, зависящие от передачи сообщений, чем компьютеры, имеющие общую память и обеспечивающие целостность кэш-памяти. Для программистов преимущество заключается в том, что обмен данными осуществляется в явном виде, значит, будет меньше неожиданностей при выполнении, чем при неявном обмене данными в компьютерах с общей памятью и поддержанием целостности кэш-памяти. А недостатком для программистов является усложненный перенос последовательной программы на компьютер, основанный на передаче сообщений, поскольку каждый обмен данными должен быть идентифицирован заранее, иначе программа не будет работать. Общая память с поддержанием целостности данных кэш-памяти позволяет оборудованию определить, какие данные должны быть переданы, что облегчает перенос программы. Относительно наикратчайшего пути к высокой производительности существуют разные мнения, учитывающие все за и против неявного обмена данными.
Недостатки использования отдельных устройств памяти превращаются в достоинства относительно готовности системы. Поскольку кластер состоит из независимых компьютеров, связанных по локальной сети, то, по сравнению с SMP, заменить машину без остановки системы намного проще. Вообще-то, использование общих адресов означает, что без героических усилий операционной системы изолировать и заменить процессор очень трудно. Поскольку программное обеспечение кластера находится на уровне, работающем поверх локальных операционных систем, сломавшуюся машину отключить и заменить намного проще.
При условии, что кластеры создаются из целых компьютеров и независимых, масштабируемых сетей, эта изолированность также упрощает расширение системы без остановки приложения, запущенного на верхнем уровне кластера.
Более низкая стоимость, высокая готовность, улучшенные параметры энергопотребления и возможность быстрого дополнительного расширения сделали кластеры привлекательными для компаний, предоставляющих сервисы во Всемирной паутине.
Эта технология применяется в поисковых машинах, которыми пользуются каждый день миллионы людей. У таких компаний, как eBay, Google, Microsoft, Yahoo и многих других, имеется множество дата-центров, в каждом из которых работают десятки тысяч процессоров. Вполне очевидно, что использование множества процессоров в компаниях, предоставляющих интернет-сервис, оказалось чрезвычайно успешным.
Уточнение. Еще одной формой крупномасштабных вычислений являются grid- вычисления, где компьютеры разбросаны по большим площадям, из-за чего запущенная в такой системе программа должна осуществлять обмен данными по сетям большой протяженности. Наиболее популярная и уникальная форма grid-вычислений была впервые представлена в рамках проекта SETI@home. Было замечено, что в отдельно взятый момент времени миллионы персональных компьютеров простаивают, не выполняя никакой полезной работы, и они могут быть позаимствованы и с пользой задействованы, если кто-нибудь разработает программное обеспечение, которое может быть запущено на этих компьютерах, после чего даст каждому персональному компьютеру независимую часть задачи, над которой тот будет работать. Первым примером была система поиска внеземного разума Search for Extraterrestrial Intelligence (SETl). Ha SETI@home зарегистрировалось более 5 млн компьютеров в более чем 200 странах, и они внесли суммарный вклад, равный более чем 19 млрд часов вычислительного времени.