Алгоритмы, структуры данных
Умножение полиномов.
Были разработаны программы комбинированного типа для умножения полиномов многих переменных. Вычислительный граф параллельной программы имеет вид бинарного дерева: каждый из полиномов сомножителей представляется суммой двух полиномов, а произведение представляется суммой четырех произведений, в которых участвуют эти слагаемые. Ниже, на рис. 2 и 3, показаны результаты двух вычислительных экспериментов с параллельными программами умножения полиномов. На рисунках представлены графики роста скорости вычислений при увеличении числа процессоров, участвующих в вычислениях.
Рис. 2. Вычисление произведения полиномов в конечном поле. Коэффициент ускорения равен 76%.
На этих графиках и на всех графиках дальше по горизонтальной шкале откладывается количество процессоров, участвующих в вычислениях, а по вертикальной шкале – величина, обратная времени вычислений. За единицу времени принято 100 сек. Верхний луч соответствует 100% роста скорости (теоретический предел), нижний луч соответствует росту скорости, равному 50%. В первом эксперименте вычислялось произведение двух полиномов от трех переменных, содержащих по 17 тысяч мономов. Коэффициенты брались из конечного поля, характеристика которого не превосходила 2·108. Коэффициент ускорения при переходе от двух к шестнадцати процессорам составил 76%.
Рис. 3. Вычисление произведения полиномов с целыми коэффициентами. Коэффициент ускорения равен 85%.
Во втором эксперименте вычислялось произведение таких же по размеру полиномов, коэффициентами которых были случайные целые числа, не превосходящие по модулю числа 228. Коэффициент ускорения при переходе от двух к шестнадцати процессорам составил 85%.
Продолжение
document.write('');
 |
|
Forekc.ru Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий |