Алгоритмы, структуры данных


         

Умножение полиномов.


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


Рис. 2. Вычисление произведения полиномов в конечном поле. Коэффициент ускорения равен 76%.

На этих графиках и на всех графиках дальше по горизонтальной шкале откладывается количество процессоров, участвующих в вычислениях, а по вертикальной шкале – величина, обратная времени вычислений. За единицу времени принято 100 сек. Верхний луч соответствует 100% роста скорости (теоретический предел), нижний луч соответствует росту скорости, равному 50%. В первом эксперименте вычислялось произведение двух полиномов от трех переменных, содержащих по 17 тысяч мономов. Коэффициенты брались из конечного поля, характеристика которого не превосходила 2·108. Коэффициент ускорения при переходе от двух к шестнадцати процессорам составил 76%.


Рис. 3. Вычисление произведения полиномов с целыми коэффициентами. Коэффициент ускорения равен 85%.

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

Продолжение

document.write('');

Новости мира IT:

  • 02.08 -
  • 02.08 -
  • 02.08 -
  • 02.08 -
  • 02.08 -
  • 01.08 -
  • 01.08 -
  • 01.08 -
  • 01.08 -
  • 01.08 -
  • 01.08 -
  • 01.08 -
  • 01.08 -
  • 01.08 -
  • 01.08 -
  • 31.07 -
  • 31.07 -
  • 31.07 -
  • 31.07 -
  • 31.07 -

    Архив новостей

  • Последние комментарии:

     (66)

    2 Август, 17:53

     (19)

    2 Август, 17:51

     (34)

    2 Август, 15:40

     (42)

    2 Август, 15:35

     (1)

    2 Август, 14:54

     (3)

    2 Август, 14:34

     (3)

    2 Август, 14:15

     (2)

    2 Август, 13:34

     (7)

    2 Август, 13:04

     (3)

    2 Август, 12:28

    BrainBoard.ru

    Море работы для программистов, сисадминов, вебмастеров.

    Иди и выбирай!

    Loading

    google.load('search', '1', {language : 'ru'}); google.setOnLoadCallback(function() { var customSearchControl = new google.search.CustomSearchControl('018117224161927867877:xbac02ystjy'); customSearchControl.setResultSetSize(google.search.Search.FILTERED_CSE_RESULTSET); customSearchControl.draw('cse'); }, true);

    <

    Содержание  Назад  Вперед