2006 Ответы на экзаменационные вопросы по ПОД (Lilalbrother), страница 6

На выходе схемы ANDпоявляется единица только в том случае,когда на обоих входах выставлены 1.Устройство 1-2 просто дублирует свой входна выходы:Если схемы AND заменить на OR, то получится цепь для реализации механизма «эврика»:как только один ПЭ выставил значение 1, эта единица распространяется всем ПЭ,сигнализируя о некотором событии на ПЭ. Это исключительно полезно, например, взадачах поиска.БИЛЕТ 16. Вычислительные кластеры: узлы, коммуникационная сеть (латентность,пропускная способность), способы построения.Различных вариантов построения кластеров очень много.

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

Латентность — этовремя начальной задержки при посылке сообщений. Пропускная способность сетиопределяется скоростью передачи информации по каналам связи (рис. 3.19). Если впрограмме много маленьких сообщений, то сильно скажется латентность. Если сообщенияпередаются большими порциями, то важна высокая пропускная способность каналовсвязи. Из-за латентности максимальная скорость передачи по сети не может бытьдостигнута на сообщениях с небольшой длиной.На практике пользователям не столько важны заявляемые производителем пиковыехарактеристики, сколько реальные показатели, достигаемые на уровне приложений. Послевызова пользователем функции посылки сообщения Send() сообщение последовательнопроходит через целый набор слоев, определяемых особенностями организациипрограммного обеспечения и аппаратуры.

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

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

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

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

Данная проблема решается проще, есливычислительная система однородна. Очень большие трудности возникают при переходена неоднородные системы, в которых есть значительное различие либо междувычислительными узлами, либо между каналами связи.Существенный фактор — это реальная производительность одного процессоравычислительной системы. Разные модели микропроцессоров могут поддерживатьнесколько уровней кэш-памяти, иметь специализированные функциональные устройства ит. п. Возьмем хотя бы иерархию памяти компьютера Cray T3E: регистры процессора, кэшпамять 1-го уровня, кэш-память 2-го уровня, локальная память процессора, удаленнаяпамять другого процессора. Эффективное использование такой структуры требуетособого внимания при выборе подхода к решению задачи.Дополнительно каждый микропроцессор может иметь элементы векторно-конвейернойархитектуры.

В этом случае ему будут присущи многие факторы, которые мы обсуждалив конце §3.2.К сожалению, как и прежде, на работе каждой конкретной программы в той или иноймере сказываются все эти факторы. Однако в отличие от компьютеров других классов,суммарное воздействие изложенных здесь факторов может снизить реальнуюпроизводительность не в десятки, а в сотни и даже тысячи раз по сравнению с пиковой.Потенциал компьютеров этого класса огромен, добиться на них можно очень многого.Крайняя точка — Интернет. Его тоже можно рассматривать как компьютер сраспределенной памятью. Причем, как самый мощный в мире компьютер.БИЛЕТ 17. Причины уменьшения производительности компьютеров сраспределенной памятью.Начнем с уже упоминавшегося закона Амдала.

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

Так как в программе всегда присутствуетинициализация, ввод/вывод и некоторые сугубо последовательные действия, тонедооценивать данный фактор никак нельзя - практически вся программа должнаисполняться в параллельном режиме, что можно обеспечить только после анализа всей (!)программы.Доля последовательных вычисленийЧислоПЭ50%25%10%5%2%21.331.601.821.901.9681.782.914.715.937.02321.943.667.8012.5519.755121.993.979.8319.2845.6320482.003.999.9619.8248.83Табл.

1. Максимальное ускорение работы программы в зависимости от долипоследовательных вычислений и числа используемых процессоров.Поскольку CRAY T3D - это компьютер с распределенной памятью, то взаимодействиепроцессоров, в основном, осуществляется посредством передачи сообщений друг другу.Отсюда два других замедляющих фактора - время инициализации посылки сообщения(латентность) и собственно время передачи сообщения по сети.

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

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

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

Однако в отличие от векторно-конвейерныхкомпьютеров все изложенные здесь факторы, за исключением, быть может, последнего,могут снизить производительность не в десятки, а в сотни и даже тысячи раз посравнению с пиковыми показателями производительности компьютера. Добиться на этихкомпьютерах, в принципе, можно многого, но усилий это может потребовать во многихслучаях очень больших.БИЛЕТ 18. Метакомпьютер и метакомпьютинг. Отличительные свойствараспределенных вычислительных сред.Вычислительный кластер можно собрать практически в любой лаборатории,отталкиваясь от потребностей в вычислительной мощности и доступного бюджета. Дляцелого класса задач, где не предполагается тесного взаимодействия между параллельнымипроцессами, решение на основе обычных рабочих станций и сети Fast Ethernet будетвполне эффективным.

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

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

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