Из чего складывается вычислительная производительность.

В последующих главах нам предстоит сравнительный обзор того материала, из которого строятся вычислительные кластеры: процессоров (точнее, рабочих станций, построенных на их базе) и оборудования локальных сетей высокой производительности. Чтобы сравнивать, необходимо сначала сформулировать критерии эффективности. Критериям эффективности коммуникационных сетей целиком посвящен второй раздел настоящей главы. В этом разделе остановимся на критериях эффективности процессоров. Казалось бы, специального раздела для рассмотрения такого простого вопроса явно слишком много. В самом деле, если мы собираемся вычислять с как можно более высокой скоростью, наш критерий эффективности один – вычислительная производительность. Но что это такое, как она определяется, чему равна, в чем измеряется, наконец? Как и многое в технологиях высокопроизводительных вычислений, вопросы эти гораздо сложнее, чем кажется на первый взгляд.

С одной стороны, синонимом быстродействия процессора сегодня принято считать его рабочую частоту. С другой стороны, вычислительное быстродействие принято измерять во флопсах, то есть в количестве арифметических операций с плавающей точкой в секунду (flops – floating point operations per second). А еще есть «пиковое быстродействие». Как все это связано между собой?

Процессор является синхронным устройством дискретного действия, квантом времени, в котором он функционирует, является один такт рабочей частоты. Быстрее, чем за один такт, в процессоре никакая обработка данных не происходит. Объем работы, которую процессор способен выполнить за один такт, определяется его логической схемой, точнее – степенью внутреннего параллелизма в выполнении команд, которую разработчикам удалось реализовать в схеме процессора. Достижимая степень внутреннего параллелизма, в свою очередь, зависит от имеющегося в распоряжении разработчика числа транзисторов. Чем больше транзисторов способны переключаться одновременно, тем больше полезной работы в принципе может быть выполнено за время, необходимое для одного переключения.

Лет 20 назад, когда суммарное число транзисторов в составе процессора было гораздо меньше, чем сейчас, разработчики процессоров были вынуждены «растягивать» выполнение команд на несколько тактов. При этом простые команды, вроде пересылки значения из регистра в регистр, занимали, например, один или два такта, а сложные, вроде умножения чисел с плавающей точкой – десятки тактов. Время выполнения типичной программы вычислительного характера если и не полностью, то в значительной степени определялось временем выполнения операций над числами с плавающей точкой, которые встречались в этой программе. Отсюда пошла традиция измерять быстродействие процессора во флопсах. По мере роста числа транзисторов на кристалле росла и степень внутреннего параллелизма в реализации процессорных команд. Сегодня она такова, что практически любая команда процессора выполняется за одно и то же время, не превышающее времени процессорного такта. Более того, появилась возможность выполнять несколько следующих подряд команд за один такт. Современные версии Pentium [7] и Opteron [8] выполняют, при благоприятных условиях, две команды за такт, в том числе, возможно, и две команды, каждая из которых есть операция над числами с плавающей точкой. Упомянутый здесь коэффициент, равный, для Pentium и Opteron, двум, известен для каждого процессора и определяется его логической схемой. Умножая его на рабочую частоту, получаем пиковое быстродействие.

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

Но это еще не все. Выше мы говорили о способности процессора выполнить две команды за такт при благоприятных условиях. Что это за условия? Если процессор выполняет две команды каждый такт, значит, каждую половину такта он выполняет по одной команде … стоп. Мы ведь начали с того, что ни за половину, ни за 0.99 такта процессор ничего сделать просто не может – ведь он работает дискретно. Следовательно, он, действительно, выполняет за такт две команды, а не за половину такта – по одной, то есть он выполняет их одновременно. Но ведь не всякие две команды, записанные в программе подряд, можно выполнить одновременно! Если следующая команда использует результат предыдущей, то, вообще говоря, выполнять их в одном такте нельзя. Именно по этой причине следует с большой осторожностью относиться к величинам пикового быстродействия процессоров, выполняющих за такт не две, а, скажем, четыре команды. Обеспечить «благоприятные условия», то есть «хорошо упаковать» смесь команд, транслятору используемого Вами языка программирования для такого процессора будет очень и очень непросто.

Серьезнейшим источником отклонения от «благоприятных условий» являются задержки при доступе в оперативную память. Если данные не находятся в кэш-памяти, то адресующая их команда будет выполняться гораздо дольше, чем в идеальном случае. Тем более, когда за право доступа к этой памяти «борются» несколько процессоров (ядер) …

На сегодня известна, практически, лишь одна программа вычислительного характера, выполняющая осмысленный расчет, которая способна показывать быстродействие, близкое к пиковому. Это – тест Linpack [4,9], решающий систему линейных алгебраических уравнений методом Гаусса. И дело здесь не в том (точнее, не только в том), что именно метод Гаусса как-то особенно хорош для современных процессоров. Дело в том, что именно этот тест принято использовать для оценки производительности, особенно – для оценки производительности многопроцессорных вычислительных систем. По этой причине, на написание специальных, очень сильно оптимизированных на уровне отдельных команд, версий этого теста (точнее, не самого теста, а библиотек, которыми он пользуется, но сути дела это не меняет) разработчики процессоров тратят громадные силы и средства. Ни одну другую реальную программу никто не оптимизирует так долго и тщательно – это просто практически невозможно. Конечно, метод Гаусса, просто написанный полностью «с нуля» на языке С или Фортране и пропущенный даже через очень хороший транслятор, покажет многократно меньшую производительность, чем специально «выжатые» демонстрационные варианты теста.

Для оценки полезной производительности как отдельного процессора, так и многопроцессорной вычислительной установки в целом, в более или менее реальных условиях, принято использовать так называемые тесты NASA (NAS parallel benchmarks) [10]. Это фрагменты реальных численных методов, используемых в задачах математической физики. Получаемые на этих тестах значения производительности во флопсах очень далеки от пикового, и это совершенно нормально.

Тесты NASA предназначены, в первую очередь, для измерения эффективности параллельной реализации типовых вычислительных алгоритмов. В зависимости от объема обрабатываемых данных, с одной стороны, и свойств коммуникационной среды многопроцессорной установки, с другой, реально достигаемая производительность может колебаться в широких пределах. Но даже верхний порог этих пределов, то есть уровень производительности, достигаемый на отдельно взятом процессоре, безо всяких накладных расходов на распараллеливание, редко бывает выше 15% от пикового. Таким образом, для реальных задач львиная доля потерь производительности кроется не в накладных расходах на распараллеливание, а в локальной обработке данных процессором, по причинам, кратко охарактеризованным выше.

В качестве самостоятельного упражнения можно рекомендовать читателю измерить производительность упоминавшейся выше модельной программы «прогрев кирпича». Автору ни разу не приходилось видеть для этой задачи значения производительности в «полезных флопсах», превышающего 10% от «пика», при использовании одного процессора. И это при том, что данная программа использует регулярную, или индексную, сетку, при работе с которой количество команд, связанных с адресацией обрабатываемых данных, сравнительно мало. Для численных методов на сложно организованных, так называемых «нерегулярных», сетках даже 3% от «пика» - явление совершенно нормальное, хотя, конечно, очень многое зависит от транслятора.

3.1.1. Коэффициент распараллеливания. Закон Амдала.

В предыдущем разделе мы убедились, что измерение производительности вычислительных приложений, и даже выбор подходящей единицы измерения – дело не простое. Гораздо проще обстоит дело, если мы хотим оценить скоростной выигрыш при переходе от выполнения расчета на однопроцессорном компьютере к выполнению того же расчета на многопроцессорной вычислительной системе. В самом деле, полагая процессоры одинаковыми, мы, очевидно, хотели бы всякий раз получать ускорение в N раз, где N – число процессоров. По причине накладных расходов на организацию взаимодействия мы, как правило, получим несколько меньшее ускорение. Сравнивая ожидаемое «идеальное» ускорение с реально получившимся, мы можем совершенно точно сказать, насколько хороша параллельная реализация расчета.

Пусть расчет выполняется на однопроцессорной машине за время T1, а на системе из N процессоров – за время TN. Величину S=TN/T1 будем называть ускорением для данной параллельной реализации расчета.

Нам бы хотелось, чтобы на системе из N процессоров расчет выполнялся за время, равное T1/N. За меру качества параллельной реализации естественно взять отношение этих величин:

P = T1/(N*TN)

Величину P принято называть коэффициентом распараллеливания для данной параллельной реализации расчета. Это – своего рода «коэффициент полезного действия» параллельной реализации. Если на 10 процессорах мы получили время, лишь в 5 раз меньшее, чем на одном, значение P будет равно 0.5.

Верно ли, что значение P не может превышать 1? Нет, не верно. Такие ситуации бывают, и не только на тестах, но и на реальных задачах. Тому есть несколько причин.

Первая и очевидная – эффект использования кэш-памяти. При параллельной реализации объем данных, обрабатываемых одним процессором, уменьшается примерно в N раз. Если при этом преодолевается порог эффективного использования кэш-памяти, например, все или почти все данные, обрабатываемые в критическом цикле, начинают умещаться в кэш-памяти, это дает дополнительное ускорение, и значение P может оказаться заметно больше единицы.

Второй, несколько менее заметный источник дополнительного ускорения – возможные изменения в способе адресации данных. Пусть, например, некоторая программа на Фортране обрабатывает трехмерный массив. При переходе к параллельной реализации каждый слой такого массива было решено поместить на отдельный процессор, и массив в каждом процессоре теперь двумерный. Доступ к элементам массива стал гораздо более эффективным, и это также дало дополнительное ускорение.

Ситуации, когда значение P заметно меньше 1, встречаются на практике гораздо чаще. Рассмотрим ситуацию, когда источники дополнительного ускорения отсутствуют, и зададимся вопросом: как будет меняться значение P по мере роста числа используемых процессоров? Интуиция подсказывает нам, что по мере уменьшения объема обрабатываемых данных будут расти удельные накладные расходы на организацию параллельной обработки. Пойдем еще дальше – рассмотрим идеальный случай, то есть предположим, что накладные расходы равны нулю. Предельное значение P, на которое можно рассчитывать в этом случае, как ни странно, строго меньше единицы, и определяется соотношением, которое называется законом Амдала [3].

Пусть в однопроцессорном варианте программы имеется цикл прохода по некоторому массиву, с его поэлементной обработкой. Разделив массив между N процессорами, написав для каждого процессора аналогичный цикл и пренебрегая накладными расходами на организацию взаимодействия, мы, казалось бы, вправе рассчитывать на ускорение расчета в N раз, поскольку мы поделили выполняемую работу на N частей. К сожалению, мы в действительности, почти наверняка поделили на N частей не всю работу. В реальной программе, скорее всего, выполняется итерационный процесс, в котором проход по массиву выполняется на каждой итерации. Следовательно, имеется цикл по итерациям, внешний по отношению к циклу прохода по массиву, который мы рассматриваем. На каждой итерации этого внешнего цикла проверяется, надо ли выполнять внутренний цикл еще раз, или расчет пора заканчивать. Эту работу мы не поделили – напротив, мы размножили ее по процессорам, то есть каждый из N процессоров теперь выполняет действия по организации своего внешнего цикла, в который вложен сократившийся в N раз внутренний цикл. Совокупная работа, действительно, поделена на N частей, но ее стало больше, чем было в однопроцессорном случае, и будет становиться тем больше, чем больше значение N. Пусть в однопроцессорном варианте программы работа по организации цикла занимала 0.001 суммарного времени. Это означает, что одна тысячная исходной совокупной работы осталась не поделенной, то есть добавление каждого нового процессора увеличивает совокупную работу на одну тысячную от исходной. Как минимум, отсюда следует, что ускориться в 1000 раз мы точно не сможем, даже использовав десять тысяч процессоров.

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

В реальных параллельных программах объем не распараллеленной вычислительной работы изменяется в широких пределах. Зависимость идеального коэффициента ускорения от доли не распараллеленной исходной работы и устанавливается законом Амдала.

Пусть доля не распараллеленных вычислений в программе равна F. Тогда время работы программы на N процессорах не может быть меньше величины:

(T1 – T1*F)/N + T1*F

Соответственно, ускорение не может быть больше, чем:

1/(F+(1 – F)/N)

Именно это неравенство представляет собой формулировку закона Амдала.

3.1.2. Несколько слов о масштабировании приложений.

Масштабированием вычислительных приложений называют их ускорение при выполнении на все большем числе процессоров. Как мы видели в предыдущем разделе, даже в идеальном случае, то есть при отсутствии накладных расходов на организацию межпроцессорного взаимодействия, масштабирование приложения при росте числа используемых процессоров не всегда бывает линейным. С другой стороны, предпринятое в предыдущем разделе рассмотрение идеального случая вовсе не означает, что действительность к нему близка. В подавляющем большинстве реальных приложений накладные расходы на организацию межпроцессорного взаимодействия более чем заметно влияют на общую картину, и, если их доля в общих затратах времени растет, масштабирование быстро теряет смысл.

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

1). Масштабирование по числу процессоров при фиксированном объеме исходных данных.

Пусть мы масштабируем решение системы из 1000 линейных уравнений. Наращивая число процессоров, и наблюдая за значением коэффициента ускорения, мы увидим, что почти линейный рост сменится сначала более медленным ростом, а затем – падением. По мере роста числа процессоров приложение пройдет через две точки деградации: в первой добавление новых процессоров перестанет сокращать время счета, во второй – добавление новых процессоров приведет к замедлению по сравнению с однопроцессорным вариантом. Чем больше то число процессоров, при котором наступает первая точка деградации, тем лучше масштабируемость приложения. Почти всегда масштабируемость приложения очень сильно зависит от свойств коммуникационного оборудования.

Такой способ масштабирования является наиболее «честным», или «жестким» способом оценки пригодности многопроцессорной вычислительной системы для решения конкретной задачи. Он соответствует следующей постановке вопроса: «У меня есть конкретная задача, до какой степени я могу ускорить именно ее решение на данной системе»?

2). Масштабирование по числу процессоров с наращиванием объема исходных данных.

Пусть мы решаем систему линейных уравнений произвольного размера. Пусть мы умеем измерять (не важно, в каких именно единицах) достигаемое при этом вычислительное быстродействие. Поставим задачу максимизировать это быстродействие, использовав столько процессоров, сколько удастся. Сначала мы, конечно, зададимся некоторым размером системы, и начнем решать ее на все большем числе процессоров. Заметив признаки деградации, мы не будем прекращать наши усилия – вместо этого просто увеличим число уравнений в системе. Для подавляющего большинства реально применяемых параллельных численных методов это приведет к тому, что точка деградации «отодвинется». Будем поступать так до тех пор, пока не исчерпается оперативная память системы, после чего заявим, что наша система имеет именно такое быстродействие на приложении «решение системы линейных уравнений».

Такой способ масштабирования также не лишен смысла (отметим, что именно он традиционно применяется для ранжирования суперкомпьютеров при включении в известный список «Top-500» [10]). Он соответствует следующей постановке вопроса: «Если Ваша задача плохо ускоряется на нашем суперкомпьютере, значит, она просто мала для него. На таком большом суперкомпьютере, как наш, надо решать действительно большие задачи».

Рассмотрим с этой точки зрения нашу модельную программу. Обратившись к Рис. 1.3, легко увидеть, что объем пересылаемых из процессора в соседние процессоры данных, при выбранном нами методе параллельной реализации, пропорционален размеру расчетной сетки. Объем же вычислительной работы в промежутках между пересылками пропорционален квадрату размера сетки. Естественно ожидать, что для как угодно «плохой» коммуникационной сети по мере роста размера сетки объем накладных расходов на пересылки можно сделать как угодно малым в процентном отношении. Вопросов только два: хватит ли оперативной памяти, и нужны ли пользователю сетки такого размера.

Параллельные вычислительные приложения, которые хорошо масштабируются «жестким» способом, даже на плохих сетях, называют коммуникационно нечувствительными. Формализованному определению смысла слов «плохая» и «хорошая» применительно к коммуникационным сетям посвящен следующий раздел.

3.2. Критерии эффективности коммуникационной сети.

Материал этого раздела частично заимствован из [2]. В предшествующем изложении нам уже приходилось упоминать такие понятия, как, например, «как можно более быстрая сеть». В этом разделе мы узнаем, что само понятие «быстрая сеть» можно понимать, как минимум, двумя разными способами. В то же время, помимо «быстроты», сети обладают еще многими важными свойствами, по наличию или отсутствию которых их можно сравнивать между собой.

Производительность, латентность и цена обмена.

Производительностью канала «точка – точка» между узлами A и B будем называть количество данных, передаваемых по каналу в единицу времени, в среднем за некоторый большой промежуток астрономического времени – скажем, за минуту. Производительность канала можно представить себе как среднюю (за длительное время) скорость передачи данных. Очевидно, производительность канала сильно зависит от того, какой длины сообщения используются при передаче данных, то есть от того, как часто канал «останавливается», с тем, чтобы потом снова «разогнаться».

Пусть узел A передает узлу B сообщение длиной X байтов, и при этом никаких других обменов в сети не происходит. Время T, затрачиваемое на такую передачу, довольно точно оценивается формулой:

T = X/S + L

где L не зависит от X.

В этой формуле, очевидно, S есть пропускная способность канала «точка – точка» на пустой сети, или, попросту, мгновенная скорость передачи данных. S измеряется в (мега)байтах в секунду.

Величина L, в свою очередь, представляет собой время запуска обмена, не зависящее от длины сообщения, и измеряется в (микро)секундах. На профессиональном жаргоне принято называть эту величину латентностью, и мы будем впредь поступать так же, чтобы не нарушать традицию, хотя это, возможно, и не совсем правильно с точки зрения терминологической строгости.

Иногда удобно оперировать латентностью, приведенной к скорости, или ценой обмена, которую мы обозначим как P:

P = L*S

Эта величина измеряется в байтах, и имеет несколько полезных «физических» интерпретаций. Прежде всего, цена обмена – это то число байт, которое канал «точка – точка» мог бы передать за время своего запуска, если бы «умел» запускаться мгновенно. Иными словами, за счет «инертности» канала, к каждому передаваемому им сообщению «как бы добавляется», с точки зрения скорости передачи, P байт.

Таким образом, производительность канала зависит от длин сообщений, используемых при передаче данных. Если X много больше P, то есть длины сообщений много больше цены обмена, производительность близка к пропускной способности. Напротив, если X много меньше P, производительность практически полностью определяется латентностью, а не пропускной способностью. Наконец, при X, равном P, производительность равна в точности половине пропускной способности канала. Тем самым, цена обмена – это такая длина сообщения, при использовании которой производительность канала равна половине его пропускной способности.

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

Замечание о соотношении терминов «латентность» и «время запуска обмена».

Давая выше определение понятия «латентность», мы упоминали некоторую терминологическую неточность этого определения. В строгом терминологическом смысле латентностью коммуникационного канала «точка-точка» следует называть время доставки короткого сообщения от отправителя к получателю. Измеряют ее так. Время многократной (N раз) посылки короткого сообщений «туда-обратно» делится на 2N, что дает среднее астрономическое время доставки одного сообщения. В нашем же определении речь шла о локальном времени запуска обмена. Эта величина измеряется несколько иначе: время многократной (N раз) посылки короткого сообщения в одну сторону делят на N. Какова же причина традиции, действительно имеющей место в профессиональном жаргоне, согласно которой время запуска обмена называют латентностью?

Причина тривиальна. Для подавляющего большинства локальных сетей эти две величины практически совпадают, поскольку время собственно доставки сообщения пренебрежимо мало по сравнению со временем запуска обмена. В последнее время начинают появляться коммуникационные среды, в которых время запуска обмена заметно меньше латентности. Для таких сетей значения «время запуска обмена» и «латентность» следует рассматривать по отдельности. Применительно к таким сетям популярен термин «message rate» - «ритм выдачи сообщений», то есть величина, обратная ко времени запуска обмена.

Полнота сети.

Содержательно, полнота сети есть мера того, насколько несколько одновременно происходящих обменов «мешают» друг другу. Простейшее определение полноты сети – это понятие бисекционной полноты: сеть называется бисекционно полной, если любыеобмены между разными парами узлов, происходящие одновременно и в любом количестве, совсем не мешают друг другу. Или, что то же самое, при любом разделении сети пополам (бисекции) пропускная способность потока данных из одной половины в другую есть сумма пропускных способностей независимых каналов, ведущих из одной половины сети в другую. Типичный пример бисекционно неполной сети – сеть на базе двух однородных коммутаторов, объединенных между собой единственной линией.

Рис. 3.1. Бисекционно неполная сеть.

Следует отметить, что при практической оценке пропускной способности реальной сети в режиме интенсивных перекрестных обменов модель бисекционной полноты недостаточна. Если сеть построена на базе центрального коммутатора (а так бывает чаще всего), то реальное время выполнения серии одновременных обменов, некоторые из которых пересекаются по участвующим процессорам, зависит от особенностей внутренней реализации коммутатора. Достаточно типична ситуация, когда два коммутатора разных моделей, каждый из которых реализует попарно независимые обмены без потери быстродействия, сильно отличаются по времени выполнения одной и той же тестовой серии частично пересекающихся обменов. Следует также отметить, что информацию о внутренней логике поведения коммутатора, по которой можно было бы предсказать его скоростные характеристики в этом режиме, добыть обычно не удается: производители ее не сообщают. При этом, в реальных задачах почти всегда имеет место именно такой режим, когда одни и те же процессоры участвуют одновременно в нескольких разных обменах. Поскольку достоверной информации о внутренней логике коммутатора у нас нет, практически мало целесообразно строить на эту тему какие-то сложные формализованные модели, основанные на выдуманных допущениях. При необходимости оценить качество коммутатора, или сравнить несколько коммутаторов между собой, разумно воспользоваться каким – либо простым эталонным тестом. Такой тест должен циклически, много раз подряд осуществлять обмены всех узлов со всеми сообщениями фиксированной длины X, причем X должно быть заметно больше цены обмена. Все обмены на одном узле должны запускаться одновременно, чтобы исключить их зависимость друг от друга по порядку выполнения. Если среднее время выполнения витка такого теста равно T, то легко подсчитать суммарный объем переданных за это время одним узлом данных D:

D = X*(N-1)

где N – число процессоров. Если бы сеть была идеальна, то есть никакой обмен не мешал никакому другому, этот объем данных мог бы быть передан из узла за время Ti:

Ti = D/S = (X*(N-1))/S

Предполагая канал, связывающий узел с сетью, дуплексным, то есть способным одновременно с передачей принимать данные с той же скоростью, и помня, что узлы работают одновременно, видим, что Ti представляет собой теоретически идеальное время срабатывания витка нашего теста. В действительности, тест будет выполнять виток за экспериментально измеренное время Te, очевидно, большее, чем Ti. Поделив одно на другое, получим экспериментальный коэффициент полноты Fe:

Fe = Ti/Te

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

Потребность сети в вычислительной мощности.

Пусть некоторое вычисление – например, перемножение двух матриц – занимает время Tm. Выполним то же самое вычисление на фоне запущенного обмена, время завершения которого заведомо превосходит Tm. Теперь это же вычисление займет время Tc. Коэффициент замедления счета на фоне обмена C вычисляется по формуле:

C = Tm/Tc

Отметим, что для «более или менее разумной» сети C должно мало отличаться от единицы, то есть сеть не должна заметно потреблять вычислительную мощность узла.

Этот критерий эффективности важен, поскольку в правильно организованных параллельных программах обмены данными стараются совмещать во времени с обработкой других данных. Например, передав операционной системе запрос на посылку в другой процессор некоторого сообщения, программа может заняться вычислениями, не затрагивающими содержимое посылаемого сообщения. ОС, скорее всего, использует для этой передачи режим DMA. С точки зрения сформулированного критерия эффективности, чем меньше работа сетевого адаптера в режиме DMA «нагружает» память, замедляя работу процессора, тем лучше.

В итоге, мы сформулировали четыре независимых критерия эффективности сети, важных с точки зрения ее практического использования. Таковыми являются:

- пропускная способность канала «точка – точка»,

- латентность,

- экспериментальный коэффициент полноты,

- потребность сети в вычислительной мощности.

Существует ли интегральный критерий эффективности?

Четыре независимых критерия эффективности – это хорошо, но много. С практической точки зрения, хотелось бы иметь что-то вроде единого универсального критерия качества коммуникационной сети, способного количественно выразить, насколько одна сеть лучше другой при использовании в реальной работе. Как ни странно, такой интегральный критерий эффективности можно, хотя и с некоторыми существенными оговорками, построить.

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

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

Пусть в алгоритме имеется 100 независимых арифметических операций со 100 парами чисел. Имеет ли смысл поручать их 100 процессорам – по одной операции на процессор? Очевидно, нет: последующая синхронизация, включающая взаимный обмен результатами, уничтожит эффект такого распараллеливания. Так же очевидно и то, что 100 независимых фрагментов по миллиону арифметических операций в каждом можно и нужно выполнять параллельно на 100 процессорах, поскольку накладной расход на последующую синхронизацию, скорее всего, будет оправдан 100-кратным ускорением расчета. Где-то между одной операцией и миллионом операций проходит «грань осмысленности дробления работы от обмена до обмена». Эта грань и называется размером зерна параллелизма.

В литературе по параллельным вычислениям принято говорить о «мелкозернистых» (fine-grained), «среднезернистых» (middle-grained) и крупнозернистых (coarse-grained, буквально - грубозернистый) параллельных вычислительных системах и, соответственно, параллельных алгоритмах. Мелкозернистыми, точнее, допускающими мелкозернистый параллелизм, обычно называют системы с общей памятью, среднезернистыми – кластеры, крупнозернистыми – метакомпьютеры, то есть системы из слабо связанных, сравнительно независимых машин. Довольно очевидно, что чем меньше допускаемый данной вычислительной системой размер зерна параллелизма, тем больше у программиста свободы в выборе способа организации совместной работы многих процессоров над одной задачей, и тем больше вероятность того, что такая организация вообще окажется возможной.