otvety_na_voprosy / 21-30

21. - для умножения

- для сложения

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

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

24. разработан ряд алгоритмов быстрого преобразования Фурье (БПФ). Алгоритмы БПФ характеризуются внутренним параллелизмом, поэтому перспективной является их реализация с помощью системы счисления остаточных классов как системы, обладающей высоким уровнем естественного параллелизма при выполнении арифметических операций.

БПФ по основанию 2 с прореживанием по времени заключается в разбиении исходной последовательности отсчетов ,  на две последовательности длинной ,  и , , таких что:  содержит чётные индексы, а  - нечётные,  [3, с. 123]. С учётом этого формула (1) будет иметь вид (2):

       (2)

25. Концепция неограниченного параллелизма отражает уровень математических знаний того времени в области параллельных вычислений. Она имеет как свои недостатки, так и свои достоинства. Рассмотрим некоторые результаты, полученные на ее основе. Для решения одной и той же задачи могут применяться алгоритмы, имеющие различную параллельную сложность. Среди них могут быть и алгоритмы наименьшей высоты. Рассмотрим важный пример вычисления произведения n чисел a1, a2,..., an, в котором отчетливо видна идея, играющая большую роль в построении алгоритмов малой высоты. Пусть n = 8. Обычная схема, реализующая процесс последовательного умножения, выглядит следующим образом:

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

Высота параллельной формы равна 3, ширина равна 4. Существенное снижение высоты произошло за счет более полной загруженности процессоров выполнением полезной работы. Последняя схема очевидным образом распространяется на случай произвольного n. Для ее реализации необходимо на каждом ярусе осуществлять максимально возможное число произведений непересекающихся пар чисел, взятых на предыдущем ярусе. В общем случае высота параллельной формы равна [log2n] , где [α] означает ближайшее к а сверху целое число. Эта параллельная форма реализуется на [n/2] процессорах, но в ней загруженность процессоров уменьшается от яруса к ярусу. Процесс построения чисел каждого яруса по описанной схеме называется процессом сдваивания.

 

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

27.  в такой модели вычислений именно высота определяет время реализации алгоритмов.

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

29. приведение алгоритмов к структурному виду, для последующего их распараллеливания, а также для распознавания типовых алгоритмических фрагментов при автоматическом анализе текстов программ.