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

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

Математическая модель требует задания граничных условий набесконечности. Реально область исследования берется конечной. Однако из-за обратноговлияния границы ее удаление от объекта должно быть значительным по всемнаправлениям. На практике это составляет десятки длин размера аппарата. Такимобразом, область исследования оказывается трехмерной и весьма большой. Припостроении алгоритмов нахождения численных решений опять используется принципдискретизации.

Из-за сложной конфигурации летательного аппарата разбиениевыбирается очень неоднородным. Общее число элементов, на которые разбиваетсяобласть, определяется сеткой с числом шагов порядка 102 по каждому измерению, т. е.всего будет порядка 106 элементов. В каждой точке надо знать 5 величин. Следовательно,на одном временном слое число неизвестных будет равно 5х106. Для изучениянестационарного режима приходится искать решения в 102—104 слоях по времени.Поэтому одних только значимых результатов промежуточных вычислений необходимонайти около109—1011.

Для получения каждого из них и дальнейшей его обработки нужно выполнить102—103 арифметических операций. И это только для одного варианта компоновки ирежима обтекания. А всего требуется провести расчеты для десятков вариантов.Приближенные оценки показывают, что общее число операций для решения задачиобтекания летательного аппарата в рамках современной модели составляет величину1015—1016. Для достижения реального времени выполнения таких расчетовбыстродействие вычислительной системы должно быть не менее 109—1010арифметических операций с плавающей запятой в секунду при оперативной памяти неменее 109 слов.Задача 3.Пусть исследуемые объекты являются трехмерными.

Чтобы получить приемлемуюточность численного решения, объект нужно покрыть сеткой не менее чем 100x100x100узлов. В каждой точке сетки нужно определить 5—20 функций. Если изучается нестационарное поведение объекта, то состояние всего ансамбля значений функций нужноопределить в 102—104 моментах времени. Поэтому только значимых результатовпромежуточных вычислений для подобных объектов нужно получить порядка 109—1011.Теперь надо принять во внимание, что на вычисление и обработку каждого изпромежуточных результатов, как показывает практика, требуется в среднем выполнить102—103 арифметических операций.

И вот мы уже видим, что для проведения толькоодного варианта численного эксперимента число операций порядка 1011—1014 являетсявполне рядовым. А теперь учтем необходимое число вариантов, накладные расходы навремя решения задачи, появляющиеся за счет качества программирования, компиляции иработы операционной системы.Билет 5. Микроэлектроника и архитектура: оценка вклада в увеличениепроизводительности компьютеров.А почему суперкомпьютеры считают так быстро? Вариантов ответа может бытьнесколько, среди которых два имеют явное преимущество: развитие элементной базы ииспользование новых решений в архитектуре компьютеров.Попробуем разобраться, какой из этих факторов оказывается решающим для достижениярекордной производительности.

Обратимся к известным историческим фактам. На одномиз первых компьютеров мира - EDSAC, появившемся в 1949 году в Кембридже и имевшемвремя такта 2 микросекунды (2*10-6 секунды), можно было выполнить 2*nарифметических операций за 18*n миллисекунд, то есть в среднем 100 арифметическихопераций в секунду.

Сравним с одним вычислительным узлом современногосуперкомпьютера Hewlett-Packard V2600: время такта приблизительно 1.8 наносекунды(1.8*10-9 секунд), а пиковая производительность около 77 миллиардов арифметическихопераций в секунду.Что же получается? За полвека производительность компьютеров выросла более, чем всемьсот миллионов раз. При этом выигрыш в быстродействии, связанный суменьшением времени такта с 2 микросекунд до 1.8 наносекунд, составляет лишь около1000 раз. Откуда же взялось остальное? Ответ очевиден -- использование новых решенийв архитектуре компьютеров. Основное место среди них занимает принцип параллельнойобработки данных, воплощающий идею одновременного (параллельного) выполнениянескольких действий.Билет 6.

Закон Амдала, его следствие, суперлинейное ускорение.Предположим, что в вашей программе доля операций, которые нужно выполнятьпоследовательно, равна f, где 0<=f<=1 (при этом доля понимается не по статическомучислу строк кода, а по числу операций в процессе выполнения). Крайние случаи взначениях f соответствуют полностью параллельным (f=0) и полностьюпоследовательным (f=1) программам. Так вот, для того, чтобы оценить, какое ускорение Sможет быть получено на компьютере из 'p' процессоров при данном значении f, можновоспользоваться законом Амдала:S<=1/(f+(1-f)/p)Если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, тоускорения более, чем в 10 раз получить в принципе невозможно вне зависимости откачества реализации параллельной части кода и числа используемых процессоров (ясно,что 10 получается только в том случае, когда время исполнения параллельной части равно0).Посмотрим на проблему с другой стороны: а какую же часть кода надо ускорить (а значити предварительно исследовать), чтобы получить заданное ускорение? Ответ можно найтив следствии из закона Амдала: для того чтобы ускорить выполнение программы в q разнеобходимо ускорить не менее, чем в q раз не менее, чем (1-1/q)-ю часть программы.Следовательно, если есть желание ускорить программу в 100 раз по сравнению с еепоследовательным вариантом, то необходимо получить не меньшее ускорение не менее,чем на 99.99% кода, что почти всегда составляет значительную часть программы!Отсюда первый вывод - прежде, чем переделывать код для перехода на параллельныйнадо подумать.

Если оценив заложенный в программе алгоритм вы поняли, что доляпоследовательных операций велика, то на значительное ускорение рассчитывать неприходится и нужно думать о замене отдельных компонент алгоритма.В ряде случаев последовательный характер алгоритма изменить не так сложно. Допустим,что в программе есть следующий фрагмент для вычисления суммы n чисел:s=0Do i = 1, ns = s + a(i)EndDo(можно то же самое на любом другом языке)По своей природе он строго последователен, так как на i-й итерации цикла требуетсярезультат с (i-1)-й и все итерации выполняются одна за другой.

Имеем 100%последовательных операций, а значит и никакого эффекта от использования параллельныхкомпьютеров. Вместе с тем, выход очевиден. Поскольку в большинстве реальныхпрограмм (вопрос: а почему в большинстве, а не во всех?) нет существенной разницы, вкаком порядке складывать числа, выберем иную схему сложения. Сначала найдем суммупар соседних элементов: a(1)+a(2), a(3)+a(4), a(5)+a(6) и т.д. Заметим, что при такой схемевсе пары можно складывать одновременно! На следующих шагах будем действоватьабсолютно аналогично, получив вариант параллельного алгоритма.Казалось бы в данном случае все проблемы удалось разрешить.

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

Проблемы кончились?Опять нет! Процессоры выполнили свою работу, но результат-то надо передать другомудля продолжения процесса суммирования... а на передачу уходит время... и в это времяпроцессоры опять простаивают...Словом, заставить параллельную вычислительную систему или супер-ЭВМ работать смаксимальной эффективность на конкретной программе это, прямо скажем, задача не изпростых, поскольку необходимо тщательное согласование структуры программ иалгоритмов с особенностями архитектуры параллельных вычислительных систем.Суперлинейное ускорение. При увеличении числа процессоров, например, в 2раза задача начинает выполняться больше, чем в 2 раза.

Такое возможно, если онаначинается помещаться в кэш процессоров, при условии, что раньше не помещалась иприходилось обращаться к медленной памяти.БИЛЕТ 7. Иерархия памяти, локальность вычислений, локальность использованияпамяти.Регистры - самая быстрая память расположенная на роцессореКэшОПДиски (со своим кэшем)ЛентыБИЛЕТ 8.

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

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