Э. Таненбаум - Архитектура компьютера (1127755), страница 180
Текст из файла (страница 180)
Предположим, что на однопроцессорном компьютере программа работает Т секунд, причем доля (7) от этого времени выполняется последовательно, а доля (1 — 7') потенциально может выполняться параллельно, как показано на рис. 8.41, а. Если параллельный код можно запустить на и процессорах, то время выполнения этого кода в лучшем случае сократится с (1 — 7)Т до (1 — 7)Т/и, как показано на рис. 8.41, б. В результате общее время выполнения программы (и последовательного, и параллельного кода) составит 7Т е (1 — ~)Т/л.
Ускорение — это время выполнения исходной программы (Т), разделенное на это новое время: п Ускорение = 1 е (и — 1))" Для у = 0 мы можем получить линейное ускорение, но для 7' > 0 идеальное ускорение недостижимо, поскольку в программе имеется последовательная часть. Это явление носит название закона Амдала. и работающих процессоров Часть, которая Принципиально может последовательная выполняться часть параллельно 1 работ проц гг (1 — Г) т(п Рис. 8.41.
Помимо последовательной части программа содержит ту часть, которая может выполняться параллельно (а); результат параллельной обработки части программы (б) Закон Амдала — только одна из причин, по которой идеальное ускорение недостижимо. Определенную роль в этом играют и время запаздывания в линиях связи, и ограниченная пропускная способность, и недостатки алгоритмов.
Даже если бы у нас было 1000 процессоров, не все программы можно написать так, чтобы все их использовать, а издержки, связанные с запуском стольких процессоров, могут быть весьма значительными. Больше того, многие известные алгоритмы почти не поддаются параллельной обработке, поэтому их приходится заменять квазиоптимальными алгоритмами. В то же время для многих приклад- 702 Глава 8.
Параллельные компьютерные архитектуры ных задач весьма желательно было бы заставить программу работать в п раз быстрее, даже если для этого потребуются 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 раза, то диаметр и, следовательно, среднее время запаздывания вырастут приблизительно вдвое. В идеале масштабируемая система при добавлении новых процессоров должна сохранять одну и ту же среднюю пропускную способность в расчете на один процессор и постоянное среднее время запаздывания. На практике сохранение Мультикомпьютеры 703 достаточной пропускной способности каждого процессора осуществимо, но время запаздывания с увеличением числа процессоров растет.
Лучше всего было бы сделать так, чтобы она росла логарифмически, как в гиперкубе. Дело в том, что время запаздывания часто является фатальным в отношении производительности мелкомодульных и среднемодульных приложений. Если программе требуются данные, которых нет в ее локальной памяти, на их получение требуется существенное время, причем чем больше система, тем больше получается задержка. Эта проблема характерна и для мультипроцессоров, и для мультикомпьютеров, поскольку в обеих архитектурах физическая память разделена на фиксированные распределенные модули.
Системные разработчики применяют несколько технологий, позволяющих сократить или, по крайней мере, замаскировать время запаздывания. Первая технология — это репликация. Если реплики блока данных можно хранить в нескольких местах, то скорость доступа к этим данным можно повысить. Один из возможных вариантов — использование каша, когда одна или несколько копий блоков данных хранятся рядом с местом, в котором они могут понадобиться и которому они «принадлежат>. Другой вариант — хранить несколько равноправных копий (в противоположность неравноправным отношениям главная-подчиненная, характерным для основной памяти и кэш-памяти).
Когда сохраняется несколько копий, главные вопросы — это кем, когда и куда они помещаются. Здесь возможны самые разные варианты, от аппаратного динамического размещения данных по запросу до их принудительного размещения во время загрузки с помощью соответствующих директив компилятора. В любом случае на первый план выходит задача согласованного управления. Вторая технология — маскирование времени запаздывания путем так называемой упреждающей выборки (рге1егсЬшй), при которой элемент данных вызывается еще до того, как он понадобится.
Это позволяет перекрыть процесс вызова и процесс выполнения, так как программа получает затребованный элемент данных без задержки. Упреждающая выборка может быть реализована как аппаратно, так и программно. В случае упреждающей выборки в кэш загружается не только нужное слово, но и вся содержащая его строка кэша в расчете на то, что другие слова из этой строки пригодятся в будущем.
Упреждающей выборкой можно управлять и непосредственно. Когда компилятор выясняет, что программе в ходе выполнения потребуются те или иные данные, он вставляет в код команду их получения, причем с таким расчетом, чтобы получить нужные данные вовремя. Такая стратегия требует, чтобы компилятор обладал полными знаниями о машине и механизме ее синхронизации, а также контролировал место хранения всех данных. Спекулятивные команды ~ОАо работают лучше всего, когда абсолютно точно известно, что загруженные данные будут использованы.
Ошибка отсутствия страницы при выполнении команды сОА0 для ветви, которая никогда не понадобится, — дело чрезвычайно затратное. Третья технология маскирования времени запаздывания — использование нескольких программных потоков. Если переключение между процессами может выполняться достаточно быстро (например, за счет выделения каждом из них собственной карты памяти и собственных регистров), то когда один поток блокируется в ожидании данных, аппаратно можно быстро переключиться на другой поток, готовый к выполнению. В предельном случае процессор выполняет 704 Глава 8. Параллельные компьютерные архитектуры первую команду из потока 1, вторую команду из потока 2 и т.
д. Таким образом, процессор всегда занят, даже при длительных задержках отдельных потоков. Четвертая технология маскирования времени запаздывания — использование неблокирующих записей. Обычно при выполнении команды 5Т(ЖЕ процессор ждет ее завершения и только после этого продолжает работу. При наличии неблокирующих записей программа продолжает работу, даже когда выполняется операция с памятью.
Продолжать работу программы при выполнении команды ЕЕА0 сложнее, но даже это возможно за счет исполнения с изменением последовательности. Распределенные вычисления Многие сегодняшние задачи в науке, технике, производстве, в области охраны окружающей среды и в других областях очень масштабны и многоплановы. Для их решения требуется объединить знания, умения, средства, возможности, программы и данные многих организаций, зачастую разбросанных по всему миру.
Вот лишь некоторые примеры: + ученые, исследующие все аспекты миссии на Марс; + консорциум, разрабатывающий сложный продукт (например, самолет или дамбу); + интернациональная спасательная команда, координирующая свои действия во время стихийного бедствия. Для некоторых задач требуется более долговременное сотрудничество, для других менее, но у всех есть общая деталь. Разные организации вместе работают для достижения общей цели, используя каждая собственные ресурсы и собственные производственные процедуры. До недавнего времени было очень сложно обеспечить совместную работу разных организаций, в которых используются разные операционные системы, разные базы данных и протоколы.
Однако рост потребности в крупномасштабном сотрудничестве между организациями привел к развитию систем и технологий объединения разрозненных компьютеров в то, что получило название распределенных вычислений (йгн) сошрп11пй). В определенном смысле, распределенные вычисления — это следующий шаг вдоль оси на рис. 8.1. Систему распределенных вычислений можно рассматривать как очень большой, интернациональный слабо связанный гетерогенный кластер. Целью системы распределенных вычислений является создание технической инфраструктуры, которая позволила бы из нескольких организаций, преследующих общую цель, создать единую виртуальную организацию. Эта виртуальная организация должна быть гибкой структурой с динамически изменяющимся числом членов, в которой отдельные члены могут работать вместе в требуемых областях и в то же время полностью контролировать собственные ресурсы. Для этой цели исследователями разрабатываются службы, инструменты и протоколы, и именно это позволяет отдельным членам функционировать в рамках виртуальной организации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
