Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
РЕАЛИЗАЦИЯ АЛГОРИТМОВ МОДУЛЬНОЙ АРИФМЕТИКИ
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
Seminar 1
| РЕАЛИЗАЦИЯ АЛГОРИТМОВ МОДУЛЬНОЙ АРИФМЕТИКИ
В КЛАСТЕРНЫХ СИСТЕМАХ М.С. Дрейбанд Нижегородский государственный технический университет, Институт прикладной физики РАН Введение В связи с использованием вычислительных кластеров возникает большое число вопросов, связанных с оптимальным использованием их ресурсов. При создании параллельных программ возникают сле- дующие проблемы: • Программисту сложно переобучиться, ведь нужно освоить специ- альные языковые конструкции, или даже новые языки программи- рования. • Сложность создания и отладки параллельных алгоритмов. • Накоплены готовые последовательные программы, которые теперь нужно переводить на язык параллельных вычислений. • Далеко не все программные и аппаратные платформы, обеспечи- вающие параллельные вычисления, совместимы друг с другом. Снять эти проблемы позволяют библиотеки, реализующие «скры- тый» параллелизм вычислений базовых арифметических операций. При создании такой библиотеки был использован следующий под- ход: все операции над числами выполняются в «модульном представ- лении». Целое число представляют вычетами по модулям из множест- ва взаимно-простых чисел p i . Если p 1 ,… p k-1 – попарно взаимно про- стые числа и p=p 1* … * p k-1 , то любое целое число u от 0 до p можно од- нозначно представить множеством его вычетов u 1 ,… u k-1 , где u i =u(mod p i ). Сложение, вычитание и умножение легко выполняются, если эти вычисления рассматривать как операции, определенные в поле классов вычетов по модулям p i . При использовании такого подхода в последовательной реализа- ции потенциально можно получить выигрыш на операции умножения, а в параллельной реализации – на всех арифметических операциях. Действия относительно разных модулей могут производиться одно- временно и, тем самым, мы получим существенную экономию во вре- 69 мени выполнения. Добиться же такой экономии с помощью традици- онных методов нельзя, так как необходимо учитывать передачу пере- носа. жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|