Алгоритм параллельного умножения чисел

Черепнев, М.А.

Автор: Черепнев М.А.
Журнал: International Journal of Open Information Technologies
Том: 8
Номер: 8
Год издания: 2020
Издательство: Лаборатория Открытых Информационных Технологий факультета ВМК МГУ им. М.В. Ломоносова
Местоположение издательства: Москва
Первая страница: 13
Последняя страница: 16
Аннотация: Умножение по модулю, где модуль является n-значным числом, при n приблизительно равном 2 9 , являетсяв настоящий момент основной операцией в алгоритмедискретного логарифмирования. Если рассматриватьуказанный процесс как умножение многозначных чисел споследующим взятием по модулю (деление с остатком), тонаибольшую сложность представляет последнее. Мыпредлагаем взглянуть на этот вопрос по-другому. А именно, сточки зрения минимизации времени при неограниченномколичестве вычислительных узлов. Сюда же входит задачараспараллеливания на кристалле, где узлы, производящиевычисления, многочисленны, но маломощны, прежде всего попамяти, а связи между ними быстрые. Мы предлагаем длявзятия по модулю алгоритм с предвычислениями,хранящимися распределенно. Эта же конфигурация позволитзначительно сократить время на умножения с фиксированныммножителем. Для самого умножения, применяетсяраспараллеленный столбик. Время работы построенногоалгоритма на распределенной вычислительной системеоценивается величиной О(log n), а с учетом конвееризациивыполняется за один такт.
Добавил в систему: Черепнев Михаил Алексеевич

	ИСТИНА	Войти в систему Регистрация
	ФНКЦ РР
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ФНКЦ РР

Алгоритм параллельного умножения чиселстатья

Прикрепленные файлы