Реклама:

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

Аппаратные метрики

С позиции аппаратуры наибольший интерес представляет быстродействие процессоров, устройств ввода-вывода и коммуникационной сети. Поскольку скорость работы процессоров и устройств ввода-вывода такая же, как и в однопроцессорной машине, ключевыми в параллельной системе являются параметры коммуникационной сети. Здесь есть две ключевые метрики: время запаздывания и пропускная способность. Мы рассмотрим их по очереди.

Полное время запаздывания, или время оборота, - это время, которое требуется на то, чтобы процессор отправил пакет и получил ответ. Если пакет посылается в память, то время запаздывания - это время, которое требуется на чтение и запись слова или блока слов. Если пакет посылается другому процессору, то время запаздывания - это время, которое требуется на передачу пакетов данного размера между процессорами. Обычно интерес представляет время запаздывания для пакетов минимального размера (как правило, одного слова или небольшой строки кэша).

Величину времени запаздывания определяют несколько факторов, и это время разное для технологий коммутации каналов, коммутации с сохранением и продвижением, виртуальной сквозной маршрутизации. В случае коммутации каналов время запаздывания составляет сумму времени установки соединения и времени передачи. Для установки соединения высылается пробный пакет, позволяющий зарезервировать необходимые ресурсы, обратно возвращается сообщение с отчетом. После этого можно компонововать пакет данных. Когда пакет готов, биты можно передавать на полной скорости, поэтому если общее время установки соединения составляет TS} размер пакета равен р бит, а пропускная способность - Ъ бит/с, время запаздывания в одну сторону составляет Ts + p/b.

Если схема дуплексная, и для ответа установки соединения не требуется, минимальное время запаздывания при передаче пакета размером в р бит и получения ответа размером в р бит составляет Т8 + 2р/Ь секунд.

При коммутации пакетов посылать получателю пробный пакет заранее не нужно, но все равно требуется некоторое время Та на компоновку пакета. Здесь время передачи в одну сторону составляет Та + р/Ь} но за этот период пакет доходит только до первого коммутатора. При прохождении через сам коммутатор получается некоторая задержка, затем происходит переход к следующему коммутатору и т. д. Время Тд состоит из времени обработки и задержки в очереди (когда нужно ждать, пока освободится выходной порт). Если имеется п коммутаторов, то общее время запаздывания в одну сторону составляет Та + п(р/Ь + Тл) + + р/Ъ, где последнее слагаемое отражает факт передачи пакета от последнего коммутатора к получателю.

Время запаздывания в одну сторону для виртуальной сквозной маршрутизации в лучшем случае приближается к значению Та + р/Ь, поскольку здесь нет пробных пакетов для установки соединения и нет задержки, обусловленной промежуточным хранением. По существу, это - время компоновки пакета плюс время передачи битов. Следовало бы еще прибавить задержку на распространение сигнала, но она во всех случаях невелика.

Следующая аппаратная метрика - пропускная способность. Многие параллельные программы, особенно в естественных науках, ориентированы на перемещение огромных объемов данных, поэтому число байтов, которое система способна передавать в секунду, является очень важным показателем производительности. Существует несколько метрик пропускной способности. Одну из них - пропускную способность сечения - мы уже рассмотрели (см. подраздел "Коммуникационные сети" в разделе "Мультикомпьютеры"). Другая метрика - совокупная пропускная способность - вычисляется путем суммирования пропускной способности всех линий связи. Это число показывает максимальное количество битов, которое можно передать единовременно. Еще одна важная метрика - средняя пропускная способность каждого процессора. Если каждый процессор способен производить данные только со скоростью 1 Мбайт/с, то от сети с пропускной способностью сечения в 100 Гбайт/с проку мало. Скорость взаимодействия в этом случае ограничивается скоростными возможностями каждого процессора.

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

Программные метрики

Аппаратные метрики, такие как время запаздывания и пропускная способность, показывают, на что способно аппаратное обеспечение. Но пользователей интересует совсем другое. Они хотят знать, насколько быстрее будут работать их программы на параллельном компьютере по сравнению с однопроцессорным. Для них ключевой метрикой является ускорение: насколько быстрее работает программа в ^-процессорной системе по сравнению с однопроцессорной. Результаты обычно иллюстрируются графически (рис. 8.40.).

Производительность

Рис. 8.40. На практике программы не могут достичь идеального ускорения (показано пунктирной линией)

Здесь мы видим несколько разных параллельных программ, которые работают на мультикомпьютере, состоящем из 64 процессоров Pentium Pro. Каждая кривая показывает ускорение одной программы с к процессорами как функцию от к. Пунктирной линией обозначено идеальное ускорение, при котором использование к процессоров заставляет программу работать в к раз быстрее для любого к. Лишь немногие программы достигают идеального ускорения, хотя существуют довольно много программ, которые приближаются к идеалу. Проблема моделирования N тел за счет параллелизма решается гораздо быстрее, Авари

Производительность

(африканская игра) тоже обсчитывается быстрее, а вот ускорить инвертирование заданной профильной матрицы более чем в пять раз нельзя, сколько бы процессоров мы не использовали. Программы и результаты обсуждаются в [17].

Есть ряд причин, по которым практически невозможно достичь идеального ускорения: практически во всех программах есть фрагменты, принципиально выполняемые последовательно, например, инициализация, считывание исходных данных или получение результатов. Увеличение числа процессоров здесь не поможет. Предположим, что на однопроцессорном компьютере программа работает Г секунд, причем доля (/) от этого времени выполняется последовательно, а доля (1 -/) потенциально может выполняться параллельно, как показано на рис. 8.41, а. Если параллельный код можно запустить на п процессорах, то время выполнения этого кода в лучшем случае сократится с(1-/)Гдо(1 -/)Т/п, как показано на рис. 8.41, б. В результате общее время выполнения программы (и последовательного, и параллельного кода) составит /Т + (1 - /)Т/п. Ускорение - это время выполнения исходной программы (Г), разделенное на это новое время:

Для/= 0 мы можем получить линейное ускорение, но для/> 0 идеальное ускорение недостижимо, поскольку в программе имеется последовательная часть. Это явление носит название закона Амдала.

Производительность

Рис. 8.41. Помимо последовательной части программа содержит ту часть, которая может выполняться параллельно (а); результат параллельной обработки части программы (б)

Закон Амдала - только одна из причин, по которой идеальное ускорение недостижимо. Определенную роль в этом играют и время запаздывания в линиях связи, и ограниченная пропускная способность, и недостатки алгоритмов. Даже если бы у нас было 1000 процессоров, не все программы можно написать так, чтобы все их использовать, а издержки, связанные с запуском стольких процессоров, могут быть весьма значительными. Больше того, многие известные алгоритмы почти не поддаются параллельной обработке, поэтому их приходится заменять квазиоптимальными алгоритмами. В то же время для многих прикладных задач весьма желательно было бы заставить программу работать в п раз быстрее, даже если для этого потребуются 2п процессоров. В конце концов, процессоры не такие уж и дорогие.

Приемы повышения производительности

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

Рассмотрим 4 процессора, связанные общей шиной (рис. 8.42, а). Представьте, что мы расширили систему до 16 процессоров, добавив еще 12 (рис. 8.42, б). Если пропускная способность шины составляет Ь Мбайт/с, то, увеличив в 4 раза число процессоров, мы сократим доступную каждому процессору пропускную способность с Ь/4 до Ь/16 Мбайт/с. Такую систему нельзя назвать масштабируемой.

Производительность

Рис. 8.42. Система из 4 процессоров, связанных общей шиной (а); система из 16 процессоров, связанных общей шиной (б); коммуникационная решетка из 4 процессоров (е); коммуникационная решетка из 16 процессоров (г)

А теперь проделаем то же самое с коммуникационной решеткой (рис. 8.42, в и г). В такой топологии добавление новых процессоров означает появление новых линий связи, поэтому при масштабировании системы совокупная пропускная способность каждого процессора не снижается, как в случае с шиной. Фактически отношение числа линий связи к числу процессоров увеличивается от 1,0 при наличии 4 процессоров (4 линии связи) до 1,5 при наличии 16 процессоров (24 линии связи), поэтому с добавлением новых процессоров совокупная пропускная способность каждого процессора растет.

Естественно, пропускная способность - не единственный параметр. Добавление процессоров к шине не увеличивает диаметр сети или время запаздывания, в то время как добавление процессоров к решетке, напротив, увеличивает. Диаметр решетки размером пхп равен 2(п - 1), поэтому в худшем случае время запаздывания растет примерно как квадратный корень от числа процессоров. Для 400 процессоров диаметр равен 38, для 1600 процессоров - 78, поэтому если увеличить число процессоров в 4 раза, то диаметр и, следовательно, среднее время запаздывания вырастут приблизительно вдвое.

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

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

Системные разработчики применяют несколько технологий, позволяющих сократить или, по крайней мере, замаскировать время запаздывания. Первая технология - это репликация. Если реплики блока данных можно хранить в нескольких местах, то скорость доступа к этим данным можно повысить. Один из возможных вариантов - использование кэша, когда одна или несколько копий блоков данных хранятся рядом с местом, в котором они могут понадобиться и которому они "принадлежат". Другой вариант - хранить несколько равноправных копий (в противоположность неравноправным отношениям главная-подчиненная, характерным для основной памяти и кэш-памяти). Когда сохраняется несколько копий, главные вопросы - это кем, когда и куда они помещаются. Здесь возможны самые разные варианты, от аппаратного динамического размещения данных по запросу до их принудительного размещения во время загрузки с помощью соответствующих директив компилятора. В любом случае на первый план выходит задача согласованного управления.

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

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

Третья технология маскирования времени запаздывания - использование нескольких программных потоков. Если переключение между процессами может выполняться достаточно быстро (например, за счет выделения каждом из них собственной карты памяти и собственных регистров), то когда один поток блокируется в ожидании данных, аппаратно можно быстро переключиться на другой поток, готовый к выполнению. В предельном случае процессор выполняет первую команду из потока 1, вторую команду из потока 2 и т. д. Таким образом, процессор всегда занят, даже при длительных задержках отдельных потоков.

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

Общая память на прикладном уровне || Оглавление || Распределенные вычисления