Параллельный метод умножения матрицы на вектор
Принципы распараллеливания, программная реализация параллельного алгоритма. Характеристика типовых схем коммуникации в многопроцессорных вычислительных системах. Выбор системы высокой производительности. Листинг программы умножения матрицы на вектор.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 04.07.2013 |
| Размер файла | 1,4 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Министерство образования и науки Российской Федерации
Государственное образовательное учреждение высшего профессионального образования
"Владимирский государственный университет имени А.Г. и Н.Г. Столетовых"
Кафедра "Вычислительная техника"
Курсовой проект
по дисциплине "Вычислительные системы высокой производительности"
на тему "Параллельный метод умножения матрицы на вектор"
Выполнил: студент гр. ЗЭВМу - 110
Иванов А.Д.
Проверил:
Буланкин В.Б.
Владимир 2011
Содержание
Введение
1. Математическое описание задачи
1.1 Постановка задачи
1.2 Последовательный алгоритм
1.2.1 Принципы распараллеливания
1.2.2 Параллельный алгоритм
1.2.3 Программная реализация
1.2.4 Умножение матрицы на вектор при разделении данных по столбцам
1.2.5 Умножение матрицы на вектор при блочном разделении данных
1.3 Анализ результатов вычислительных экспериментов
1.3.1 Для умножения матрицы на вектор при разделении данных по строкам
1.3.2 Для умножения матрицы на вектор при разделении данных по столбцам
1.3.3 Для умножения матрицы на вектор при блочном разделении данных
2. Выбор системы высокой производительности
2.1 Классификация архитектур по параллельной обработке данных
2.1.1 Мультипроцессоры
2.1.2 Мультикомпьютеры
2.2 Сетевая технология Marynet 2000
2.3 Характеристика типовых схем коммуникации в многопроцессорных вычислительных системах
2.3.1 Примеры топологий сети передачи данных
3. Выбор языка управления вычислительными процессами
Заключение
Список литературы
Приложение - Листинг программы
Введение
Существует широкий круг вычислительных задач, требующих для своего решения значительно больших вычислительных ресурсов, чем может предоставить обычный персональный компьютер (ПК). Таким задачам необходимо:
- большее быстродействие (Сложные, многомерные задачи, которые необходимо решить в течение определенного, достаточно ограниченного времени, требуют обеспечения большого быстродействия. Один из наиболее характерных примеров - задачи прогноза погоды. Область решения (атмосфера) разбивается на отдельные пространственные ячейки, причем для расчета временных изменений вычисления в каждой ячейке повторяются много раз. Если объем ячейки равен 1 км3, то для моделирования 10 км слоя атмосферы потребуется 5х 108 таких ячеек. Предположим, что вычисления в каждой ячейке потребуют 200 операций с плавающей точкой, тогда за один временной шаг потребуется выполнить 1011 операций с плавающей точкой. Для того чтобы произвести расчет прогноза погоды с заблаговременностью 10 дней с 10-ти минутным шагом по времени, компьютеру производительностью 100 Mflops (108 операций с плавающей точкой в секунду) потребуется 107 секунд или свыше 100 дней. Для того чтобы произвести расчет за 10 мин, потребуется компьютер производительностью 1.7 Tflops (1.7х 1012 операций с плавающей точкой в секунду)
- больший объем оперативной памяти (К категории задач, требующих большого объема оперативной памяти, относятся, например, задачи гидро- и газодинамики по расчету течений сложной пространственно-временной структуры с учетом различных физических и химических процессов. Такие задачи являются, как правило, многомерными, и расчет по каждому направлению хотя бы для нескольких точек требует
оперативной памяти, превышающей 10 Гбайт. В квантовой химии неэмпирические расчеты электронной структуры молекул требуют вычислительных затрат, пропорциональных N4 или N5, где N условно характеризует число молекул. Сейчас многие молекулярные системы вынужденно исследуются в упрощенном модельном представлении, что связано с нехваткой вычислительных ресурсов).
- большое количество передаваемой информации (Требование обеспечения большого количества передаваемой информации характерно для задач гидро- и газодинамики с меняющимися граничными условиями, когда вычислительный алгоритм постоянно требует подведения новой информации; и задач экономической оптимизации, описывающих поведение системы, погруженной в среду с непрерывно меняющимися свойствами, от которых зависит состояние системы).
- обработка и хранение большого объема информации (Проблема обработки и хранения большого объема информации характерна для задач астрономии, спектроскопии, биологии, ядерной физики. Так, в биотехнологической индустрии для отслеживания и анализа работы десятков тысяч протеиновых клеток, каждая из которых может испытывать миллионы различных реакций, требуется суперкомпьютер, который способен обрабатывать и хранить огромные массивы данных. Осуществление международных программ в области ядерной физики, подразумевает обработку и анализ данных исследований в научных центрах разных стран и организацию доступа к ним ученых всего мира. Естественно, что одной из ключевых задач здесь является организация эффективного хранения огромных массивов информации).
Если присутствует хотя бы одно из перечисленных требований, то использование высокопроизводительных вычислений необходимо и оправдано.
В настоящее время фундаментальные и прикладные проблемы, эффективное решение которых возможно только с использованием высокопроизводительных вычислений, включают следующие задачи:
- Предсказания погоды, климата и глобальных изменений в атмосфере;
- Науки о материалах;
- Построение полупроводниковых приборов;
- Сверхпроводимость;
- Структурная биология;
- Разработка фармацевтических препаратов;
- Генетика;
- Квантовая хромодинамика;
- Астрономия;
- Транспортные задачи;
- Гидро- и газодинамика;
- Управляемый термоядерный синтез;
- Эффективность систем сгорания топлива;
- Геоинформационные системы;
- Разведка недр;
- Наука о мировом океане;
- Распознавание и синтез речи;
- Распознавание изображений;
- а также многие другие.
1. Математическое описание задачи
Матрицы и матричные операции широко используются при математическом моделировании самых разнообразных процессов, явлений и систем. Матричные вычисления составляют основу многих научных и инженерных расчетов - среди областей приложений могут быть указаны вычислительная математика, физика, экономика и др.
С учетом значимости эффективного выполнения матричных расчетов многие стандартные библиотеки программ содержат процедуры для различных матричных операций. Объем программного обеспечения для обработки матриц постоянно увеличивается - разрабатываются новые экономные структуры хранения для матриц специального типа (треугольных, ленточных, разреженных и т.п.), создаются различные высокоэффективные машинно-зависимые реализации алгоритмов, проводятся теоретические исследования для поиска более быстрых методов матричных вычислений.
Являясь вычислительно трудоемкими, матричные вычисления представляют собой классическую область применения параллельных вычислений. С одной стороны, использование высокопроизводительных многопроцессорных систем позволяет существенно повысить сложность решаемых задач. С другой стороны, в силу своей достаточно простой формулировки матричные операции предоставляют прекрасную возможность для демонстрации многих приемов и методов параллельного программирования.
1.1 Постановка задачи
алгоритм многопроцессорный матрица листинг
В результате умножения матрицы А размерности m Ч n и вектора b, состоящего из n элементов, получается вектор c размера m, каждый i-й элемент которого есть результат скалярного умножения i-й строки матрицы А (обозначим эту строчку ai) и вектора b:
1.2 Последовательный алгоритм
Последовательный алгоритм умножения матрицы на вектор может быть представлен следующим образом.
Алгоритм 6.1. Последовательный алгоритм умножения матрицы на вектор
Матрично-векторное умножение - это последовательность вычисления скалярных произведений. Поскольку каждое вычисление скалярного произведения векторов длины n требует выполнения n операций умножения и n-1 операций сложения, его трудоемкость порядка O(n). Для выполнения матрично-векторного умножения необходимо осуществить m операций вычисления скалярного произведения, таким образом, алгоритм имеет трудоемкость порядка O(mn).
1.2.1 Принципы распараллеливания
Для многих методов матричных вычислений характерным является повторение одних и тех же вычислительных действий для разных элементов матриц. Данное свойство свидетельствует о наличии параллелизма по данным при выполнении матричных расчетов, и, как результат, распараллеливание матричных операций сводится в большинстве случаев к разделению обрабатываемых матриц между процессорами используемой вычислительной системы. Выбор способа разделения матриц приводит к определению конкретного метода параллельных вычислений; существование разных схем распределения данных порождает целый ряд параллельных алгоритмов матричных вычислений.
Наиболее общие и широко используемые способы разделения матриц состоят в разбиении данных на полосы (по вертикали или горизонтали) или на прямоугольные фрагменты (блоки).
Ленточное разбиение матрицы. При ленточном (block-striped) разбиении каждому процессору выделяется то или иное подмножество строк (rowwise или горизонтальное разбиение) или столбцов (columnwise или вертикальное разбиение) матрицы. Разделение строк и столбцов на полосы в большинстве случаев происходит на непрерывной (последовательной) основе. При таком подходе для горизонтального разбиения по строкам, например, матрица A представляется в виде:
где ai=(ai1,ai2,...,ain), 0i<m, есть i-я строка матрицы A (предполагается, что количество строк m кратно числу процессоров p, т.е. m = k·p). Во всех алгоритмах матричного умножения и умножения матрицы на вектор, применяется разделение данных на непрерывной основе.
Другой возможный подход к формированию полос состоит в применении той или иной схемы чередования (цикличности) строк или столбцов. Как правило, для чередования используется число процессоров p - в этом случае при горизонтальном разбиении матрица A принимает вид:
Циклическая схема формирования полос может оказаться полезной для лучшей балансировки вычислительной нагрузки процессоров (например, при решении системы линейных уравнений с использованием метода Гаусса).
Блочное разбиение матрицы. При блочном (chessboard block) разделении матрица делится на прямоугольные наборы элементов - при этом, как правило, используется разделение на непрерывной основе. Пусть количество процессоров составляет p = s·q, количество строк матрицы является кратным s, а количество столбцов - кратным q, то есть m = k·s и n = l·q. Представим исходную матрицу A в виде набора прямоугольных блоков следующим образом:
где Aij - блок матрицы, состоящий из элементов:
При таком подходе целесообразно, чтобы вычислительная система имела физическую или, по крайней мере, логическую топологию процессорной решетки из s строк и q столбцов. В этом случае при разделении данных на непрерывной основе процессоры, соседние в структуре решетки, обрабатывают смежные блоки исходной матрицы. Следует отметить, однако, что и для блочной схемы может быть применено циклическое чередование строк и столбцов.
Рассматриваются три параллельных алгоритма для умножения квадратной матрицы на вектор. Каждый подход основан на разном типе распределения исходных данных (элементов матрицы и вектора) между процессорами. Разделение данных меняет схему взаимодействия процессоров, поэтому каждый из представленных методов существенным образом отличается от двух остальных.
Рисунок 1.1 - Способы распределения элементов матрицы между процессорами вычислительной системы.
1.2.2 Параллельный алгоритм
Разделение данных. При выполнении параллельных алгоритмов умножения матрицы на вектор, кроме матрицы А, необходимо разделить еще вектор b и вектор результата c. Элементы векторов можно продублировать, то есть скопировать все элементы вектора на все процессоры, составляющие многопроцессорную вычислительную систему, или разделить между процессорами. При блочном разбиении вектора из n элементов каждый процессор обрабатывает непрерывную последовательность из k элементов вектора (мы предполагаем, что размерность вектора n нацело делится на число процессоров, т.е. n= k·p).
Поясним, почему дублирование векторов b и c между процессорами является допустимым решением (далее для простоты изложения будем полагать, что m=n). Векторы b и с состоят из n элементов, т.е. содержат столько же данных, сколько и одна строка или один столбец матрицы. Если процессор хранит строку или столбец матрицы и одиночные элементы векторов b и с, то общее число сохраняемых элементов имеет порядок O(n). Если процессор хранит строку (столбец) матрицы и все элементы векторов b и с, то общее число сохраняемых элементов также порядка O(n). Таким образом, при дублировании и при разделении векторов требования к объему памяти из одного класса сложности. Вариант умножение матрицы на вектор при разделении данных по строкам.
Рассмотрим в качестве первого примера организации параллельных матричных вычислений алгоритм умножения матрицы на вектор, основанный на представлении матрицы непрерывными наборами (горизонтальными полосами) строк. При таком способе разделения данных в качестве базовой подзадачи может быть выбрана операция скалярного умножения одной строки матрицы на вектор.
Выделение информационных зависимостей. Для выполнения базовой подзадачи скалярного произведения процессор должен содержать соответствующую строку матрицы А и копию вектора b. После завершения вычислений каждая базовая подзадача определяет один из элементов вектора результата c. Для объединения результатов расчета и получения полного вектора c на каждом из процессоров вычислительной системы необходимо выполнить операцию обобщенного сбора данных, в которой каждый процессор передает свой вычисленный элемент вектора c всем остальным процессорам. Этот шаг можно выполнить, например, с использованием функции MPI_Allgather из библиотеки MPI.
В общем виде схема информационного взаимодействия подзадач в ходе выполняемых вычислений показана на рис. 1.2.
Рисунок 1.2 - Организация вычислений при выполнении параллельного алгоритма умножения матрицы на вектор, основанного на разделении матрицы по строкам.
Масштабирование и распределение подзадач по процессорам. В процессе умножения плотной матрицы на вектор количество вычислительных операций для получения скалярного произведения одинаково для всех базовых подзадач. Поэтому в случае, когда число процессоров p меньше числа базовых подзадач m, мы можем объединить базовые подзадачи таким образом, чтобы каждый процессор выполнял несколько таких задач, соответствующих непрерывной последовательности строк матрицы А. В этом случае по окончании вычислений каждая базовая подзадача определяет набор элементов результирующего вектора с.
Распределение подзадач между процессорами вычислительной системы может быть выполнено произвольным образом.
Анализ эффективности. Для анализа эффективности параллельных вычислений здесь и далее будут строиться два типа оценок. В первой из них трудоемкость алгоритмов оценивается в количестве вычислительных операций, необходимых для решения поставленной задачи, без учета затрат времени на передачу данных между процессорами, а длительность всех вычислительных операций считается одинаковой. Кроме того, константы в получаемых соотношениях, как правило, не указываются - для первого типа оценок важен прежде всего порядок сложности алгоритма, а не точное выражение времени выполнения вычислений. Как результат, в большинстве случаев подобные оценки получаются достаточно простыми и могут быть использованы для начального анализа эффективности разрабатываемых алгоритмов и методов.
Второй тип оценок направлен на формирование как можно более точных соотношений для предсказания времени выполнения алгоритмов. Получение таких оценок проводится, как правило, при помощи уточнения выражений, полученных на первом этапе. Для этого в имеющиеся соотношения вводятся параметры, задающие длительность выполнения операций, строятся оценки трудоемкости коммуникационных операций, указываются все необходимые константы. Точность получаемых выражений проверяется при помощи вычислительных экспериментов, по результатам которых время выполненных расчетов сравнивается с теоретически предсказанными оценками длительностей вычислений. Как результат, оценки подобного типа имеют, как правило, более сложный вид, но позволяют более точно оценивать эффективность разрабатываемых методов параллельных вычислений.
Рассмотрим трудоемкость алгоритма умножения матрицы на вектор. В случае если матрица А квадратная (m=n), последовательный алгоритм умножения матрицы на вектор имеет сложность T1=n2. В случае параллельных вычислений каждый процессор производит умножение только части (полосы) матрицы A на вектор b, размер этих полос равен n/p строк. При вычислении скалярного произведения одной строки матрицы и вектора необходимо произвести n операций умножения и (n-1) операций сложения. Следовательно, вычислительная трудоемкость параллельного алгоритма определяется выражением:
С учетом этой оценки показатели ускорения и эффективности параллельного алгоритма имеют вид:
Построенные выше оценки времени вычислений выражены в количестве операций и, кроме того, определены без учета затрат на выполнение операций передачи данных. Используем ранее высказанные предположения о том, что выполняемые операции умножения и сложения имеют одинаковую длительность ф. Кроме того, будем предполагать также, что вычислительная система является однородной, т.е. все процессоры, составляющие эту систему, обладают одинаковой производительностью. С учетом введенных предположений время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, составляет
Как результат, длительность выполнения операции сбора данных при использовании модели Хокни может быть определена при помощи следующего выражения
где - латентность сети передачи данных, в - пропускная способность сети. Таким образом, общее время выполнения параллельного алгоритма составляет
(для упрощения выражения в предполагалось, что значения n/p и log2p являются целыми).
1.2.3 Программная реализация
Представим возможный вариант параллельной программы умножения матрицы на вектор с использованием алгоритма разбиения матрицы по строкам. При этом реализация отдельных модулей не приводится, если их отсутствие не оказывает влияние на понимании общей схемы параллельных вычислений.
Главная функция программы. Реализует логику работы алгоритма, последовательно вызывает необходимые подпрограммы.
Функция ProcessInitialization. Эта функция задает размер и элементы для матрицы A и вектора b. Значения для матрицы A и вектора b определяются в функции RandomDataInitialization.
Функция DataDistribution. Осуществляет рассылку вектора b и распределение строк исходной матрицы A по процессам вычислительной системы. Следует отметить, что когда количество строк матрицы n не является кратным числу процессоров p, объем пересылаемых данных для процессов может оказаться разным и для передачи сообщений необходимо использовать функцию MPI_Scatterv библиотеки MPI.
Следует отметить, что такое разделение действий генерации исходных данных и их рассылки между процессами может быть неоправданным в реальных параллельных вычислениях при большом объеме данных. Широко используемый подход в таких случаях состоит в организации передачи сообщений процессам сразу же после того, как данные процессов будут сгенерированы. Снижение затрат памяти для хранения данных может быть достигнуто также и за счет организации генерации данных в последнем процессе (при таком подходе память для пересылаемых данных и для данных процесса может быть одной и той же).
Функция ParallelResultCaculation. Данная функция производит умножение на вектор тех строк матрицы, которые распределены на данный процесс, и таким образом получается блок результирующего вектора с.
Функция ResultReplication. Объединяет блоки результирующего вектора с, полученные на разных процессах, и копирует вектор результата на все процессы вычислительной системы.
1.2.4 Умножение матрицы на вектор при разделении данных по столбцам
Рассмотрим теперь другой подход к параллельному умножению матрицы на вектор, основанный на разделении исходной матрицы на непрерывные наборы (вертикальные полосы) столбцов.
Определение подзадач и выделение информационных зависимостей. При таком способе разделения данных в качестве базовой подзадачи может быть выбрана операция умножения столбца матрицы А на один из элементов вектора b. Для организации вычислений в этом случае каждая базовая подзадача i, 0i<=n, должна содержать i-й столбец матрицы А и i-е элементы bi и ci векторов b и с.
Параллельный алгоритм умножения матрицы на вектор начинается с того, что каждая базовая задача i выполняет умножение своего столбца матрицы А на элемент bi, в итоге в каждой подзадаче получается вектор c'(i) промежуточных результатов. Далее для получения элементов результирующего вектора с подзадачи должны обменяться своими промежуточными данными между собой (элемент j, 0j<=n, частичного результата c'(i) подзадачи i, 0i<=n, должен быть передан подзадаче j). Данная обобщенная передача данных (all-to-all communication или total exchange) является наиболее общей коммуникационной процедурой и может быть реализована при помощи функции MPI_Alltoall библиотеки MPI. После выполнения передачи данных каждая базовая подзадача i, 0i<=n, будет содержать n частичных значений c'i(j), 0j<=n, сложением которых и определяется элемент ci вектора результата с.
Рисунок 1.3 - Организация вычислений при выполнении параллельного алгоритма умножения матрицы на вектор с использованием разбиения матрицы по столбцам
Масштабирование и распределение подзадач по процессорам. Выделенные базовые подзадачи характеризуются одинаковой вычислительной трудоемкостью и равным объемом передаваемых данных. В случае когда количество столбцов матрицы превышает число процессоров, базовые подзадачи можно укрупнить, объединив в рамках одной подзадачи несколько соседних столбцов (в этом случае исходная матрица A разбивается на ряд вертикальных полос). При соблюдении равенства размера полос такой способ агрегации вычислений обеспечивает равномерность распределения вычислительной нагрузки по процессорам, составляющим многопроцессорную вычислительную систему.
Как и в предыдущем алгоритме, распределение подзадач между процессорами вычислительной системы может быть выполнено произвольным образом.
Анализ эффективности. Пусть, как и ранее, матрица А является квадратной, то есть m=n. На первом этапе вычислений каждый процессор умножает принадлежащие ему столбцы матрицы А на элементы вектора b, после умножения полученные значения суммируются для каждой строки матрицы А в отдельности
(j0 и jl-1 есть начальный и конечный индексы столбцов базовой подзадачи i, 0i<=n). Поскольку размеры полосы матрицы А и блока вектора b равны n/p, то трудоемкость таких вычислений может оцениваться как T'= n2/p операций. После обмена данными между подзадачами на втором этапе вычислений каждый процессор суммирует полученные значения для своего блока результирующего вектора c. Количество суммируемых значений для каждого элемента ci вектора c совпадает с числом процессоров p, размер блока вектора c на одном процессоре равен n/p, и, тем самым, число выполняемых операций для второго этапа оказывается равным T''=n. С учетом полученных соотношений показатели ускорения и эффективности параллельного алгоритма могут быть выражены следующим образом:
Теперь рассмотрим более точные соотношения для оценки времени выполнения параллельного алгоритма. С учетом ранее проведенных рассуждений время выполнения вычислительных операций алгоритма может быть оценено при помощи выражения
(здесь, как и ранее, ф есть время выполнения одной элементарной скалярной операции).
Для выполнения операции обобщенной передачи данных рассмотрим два возможных способа реализации. Первый способ обеспечивается алгоритмом, согласно которому каждый процессор последовательно передает свои данные всем остальным процессорам вычислительном системы. Предположим, что процессоры могут одновременно отправлять и принимать сообщения и между любой парой процессоров имеется прямая линия связи, тогда оценка трудоемкости (время исполнения) такого алгоритма обобщенной передачи данных может быть определена как
(напомним, что - латентность сети передачи данных, в - пропускная способность сети, w - размер элемента данных в байтах).
Второй способ выполнения операции обмена данными, когда топология вычислительной сети может быть представлена в виде гиперкуба. Как было показано, выполнение такого алгоритма может быть осуществлено за шагов, на каждом из которых каждый процессор передает и получает сообщение из n/2 элементов. Как результат, время операции передачи данных при таком подходе составляет величину:
Общее время выполнения параллельного алгоритма умножения матрицы на вектор при разбиении данных по столбцам выражается следующими соотношениями.
Для первого способа выполнения операции передачи данных:
Для второго способа выполнения операции передачи данных
После определения ведущей строки на каждом процессе, необходимо выбрать максимальный среди полученных ведущих элементов и определить, на каком процессе он располагается. Для выполнения таких действий в библиотеке MPI предназначена функция MPI_Allreduce. Функция имеет следующий интерфейс:
int MPI_Allreduce(void *sendbuf, void *recvbuf,int count,MPI_Datatype type, MPI_Op op,MPI_Comm comm),
где
sendbuf - буфер памяти с отправляемым сообщением,
recvbuf - буфер памяти для результирующего сообщения,
count - количество элементов в сообщениях,
type - тип элементов сообщений,
op - операция, которая должна быть выполнена над данными,
comm - коммуникатор, в рамках которого выполняется операция.
1.2.5 Умножение матрицы на вектор при блочном разделении данных
Рассмотрим теперь параллельный алгоритм умножения матрицы на вектор, который основан на ином способе разделения данных - на разбиении матрицы на прямоугольные фрагменты (блоки).
Определение подзадач. Блочная схема разбиения матриц подробно рассмотрена при распараллеливании. При таком способе разделения данных исходная матрица A представляется в виде набора прямоугольных блоков:
где Aij, 0i<=s, 0j<=q, есть блок матрицы:
(здесь, как и ранее, предполагается, что p=s·q, количество строк матрицы является кратным s, а количество столбцов - кратным q, то есть m=k·s и n=l·q).
При использовании блочного представления матрицы A базовые подзадачи целесообразно определить на основе вычислений, выполняемых над матричными блоками. Для нумерации подзадач могут применяться индексы располагаемых в подзадачах блоков матрицы A, т.е. подзадача (i,j) содержит блок Aij. Помимо блока матрицы A каждая подзадача должна содержать также и блок вектора b. При этом для блоков одной и той же подзадачи должны соблюдаться определенные правила соответствия - операция умножения блока матрицы A ij может быть выполнена только, если блок вектора b'(i,j) имеет вид
Выделение информационных зависимостей. Рассмотрим общую схему параллельных вычислений для операции умножения матрицы на вектор при блочном разделении исходных данных. После перемножения блоков матрицы A и вектора b каждая подзадача (i,j) будет содержать вектор частичных результатов c'(i,j), определяемый в соответствии с выражениями
Поэлементное суммирование векторов частичных результатов для каждой горизонтальной полосы (данная процедура часто именуется операцией редукции) блоков матрицы A позволяет получить результирующий вектор c
Для размещения вектора c применим ту же схему, что и для исходного вектора b: организуем вычисления таким образом, чтобы при завершении расчетов вектор c располагался поблочно в каждой из вертикальных полос блоков матрицы A (тем самым, каждый блок вектора c должен быть продублирован по каждой горизонтальной полосе). Выполнение всех необходимых действий для этого - суммирование частичных результатов и дублирование блоков результирующего вектора - может быть обеспечено при помощи функции MPI_Allreduce библиотеки MPI.
Общая схема выполняемых вычислений для умножения матрицы на вектор при блочном разделении данных:
Рисунок 1.4 - Общая схема параллельного алгоритма умножения матрицы на вектор при блочном разделении данных: a) исходное распределение результатов, б) распределение векторов частичных результатов, в) распределение блоков результирующего вектора c.
Рассмотрев представленную схему параллельных вычислений, можно сделать вывод, что информационная зависимость базовых подзадач проявляется только на этапе суммирования результатов перемножения блоков матрицы A и блоков вектора b. Выполнение таких расчетов может быть выполнено по обычной каскадной схеме, и, как результат, характер имеющихся информационных связей для подзадач одной и той же горизонтальной полосы блоков соответствует структуре двоичного дерева.
Масштабирование и распределение подзадач по процессорам. Размер блоков матрицы А может быть подобран таким образом, чтобы общее количество базовых подзадач совпадало с числом процессоров p. Так, например, если определить размер блочной решетки как
p=s·q, тоk=m/s, l=n/q,
где k и l есть количество строк и столбцов в блоках матрицы А.
Такой способ определения размера блоков приводит к тому, что объем вычислений в каждой подзадаче является равным, и, тем самым, достигается полная балансировка вычислительной нагрузки между процессорами.
Возможность выбора остается при определении размеров блочной структуры матрицы А. Большое количество блоков по горизонтали приводит к возрастанию числа итераций в операции редукции результатов блочного умножения, а увеличение размера блочной решетки по вертикали повышает объем передаваемых данных между процессорами. Простое, часто применяемое решение состоит в использовании одинакового количества блоков по вертикали и горизонтали, т.е.
Следует отметить, что блочная схема разделения данных является обобщением всех рассмотренных подходов. Действительно, при q=1 блоки сводятся к горизонтальным полосам матрицы А, при s=1 исходные данные разбиваются на вертикальные полосы.
При решении вопроса распределения подзадач между процессорами должна учитываться возможность эффективного выполнения операции редукции. Возможный вариант подходящего способа распределения состоит в выделении для подзадач одной и той же горизонтальной полосы блоков множества процессоров, структура сети передачи данных между которыми имеет вид гиперкуба или полного графа.
Анализ эффективности. Выполним анализ эффективности параллельного алгоритма умножения матрицы на вектор при обычных уже предположениях, что матрица А является квадратной, т.е. m=n. Будем предполагать также, что процессоры, составляющие многопроцессорную вычислительную систему, образуют прямоугольную решетку p=sЧq (s - количество строк в процессорной решетке, q - количество столбцов).
Общий анализ эффективности приводит к идеальным показателям параллельного алгоритма:
Для уточнения полученных соотношений оценим более точно количество вычислительных операций алгоритма и учтем затраты на выполнение операций передачи данных между процессорами.
Общее время умножения блоков матрицы А и вектора b может быть определено как
Операция редукции данных может быть выполнена с использованием каскадной схемы и включает, тем самым, log2q итераций передачи сообщений размера . Как результат, оценка коммуникационных затрат параллельного алгоритма при использовании модели Хокни может быть определена при помощи следующего выражения
Таким образом, общее время выполнения параллельного алгоритма умножения матрицы на вектор при блочном разделении данных составляет
1.3 Анализ результатов вычислительных экспериментов
Рассмотрим результаты вычислительных экспериментов, выполненных для оценки эффективности приведенных выше параллельных алгоритмов умножения матрицы на вектор. Кроме того, используем полученные результаты для сравнения теоретических оценок и экспериментальных показателей времени вычислений и проверим тем самым точность полученных аналитических соотношений. Эксперименты проводились на вычислительном кластере Нижегородского университета на базе процессоров Intel Xeon 4 EM64T, 3000 МГц и сети Gigabit Ethernet под управлением операционной системы Microsoft Windows Server 2003 Standard x64 Edition и системы управления кластером Microsoft Compute Cluster Server.
1.3.1 Для умножения матрицы на вектор при разделении данных по строкам
Определение параметров теоретических зависимостей (величин ф, w, , в) осуществлялось следующим образом. Для оценки длительности ф базовой скалярной операции проводилось решение задачи умножения матрицы на вектор при помощи последовательного алгоритма и полученное таким образом время вычислений делилось на общее количество выполненных операций - в результате подобных экспериментов для величины ф было получено значение 1,93 нсек. Эксперименты, выполненные для определения параметров сети передачи данных, показали значения латентности и пропускной способности в соответственно 47 мкс и 53,29 Мбайт/с. Все вычисления производились над числовыми значениями типа double, т.е. величина w равна 8 байт.
Результаты вычислительных экспериментов приведены в таблице 1.1. Эксперименты проводились с использованием двух, четырех и восьми процессоров. Времена выполнения алгоритмов указаны в секундах.
Таблица 1.1. - Результаты вычислительных экспериментов для параллельного алгоритма умножения матрицы на вектор при ленточной схеме разделения данных по строкам
Сравнение экспериментального времени выполнения параллельного алгоритма и теоретического времени Tp, вычисленного в соответствии с выражением
,
представлено в таблице 1.2 и в графическом виде на рис. 1.5 и 1.6.
Таблица 1.2. - Сравнение экспериментального и теоретического времени выполнения параллельного алгоритма умножения матрицы на вектор, основанного на разбиении матрицы по строкам
Рисунок 1.5 - График зависимости экспериментального T'p и теоретического Tp времени выполнения параллельного алгоритма на двух процессорах от объема исходных данных (ленточное разбиение матрицы по строкам).
Рисунок 1.6 - Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма умножения матрицы на вектор (ленточное разбиение по строкам) для разных размеров матриц.
1.3.2 Для умножения матрицы на вектор при разделении данных по столбцам
Вычислительные эксперименты для оценки эффективности параллельного алгоритма умножения матрицы на вектор при разбиении данных по столбцам проводились при условиях, указанных в п. 1.3. Результаты вычислительных экспериментов приведены в таблице 1.3.
Таблица 1.3. - Результаты вычислительных экспериментов по исследованию параллельного алгоритма умножения матрицы на вектор, основанного на разбиении матрицы по столбцам
Сравнение экспериментального времени выполнения эксперимента и времени Tp, вычисленного по соотношениям
,
,
представлено в таблице 1.4 и на рис. 1.7 и 1.8. Теоретическое время вычисляется согласно
,
а теоретическое время - в соответствии с
Таблица 6.4. - Сравнение экспериментального и теоретического времени выполнения параллельного алгоритма умножения матрицы на вектор, основанного на разбиении матрицы по столбцам
Рисунок 1.7. - График зависимости теоретического и экспериментального времени выполнения параллельного алгоритма на четырех процессорах от объема исходных данных (ленточное разбиение матрицы по столбцам)
Рисунок 1.8. - Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма умножения матрицы на вектор (ленточное разбиение матрицы по столбцам) для разных размеров матриц.
1.3.3 Для умножения матрицы на вектор при блочном разделении данных
Вычислительные эксперименты для оценки эффективности параллельного алгоритма проводились при тех же условиях, что и ранее выполненные расчеты в пункте 1.3. Результаты экспериментов приведены в таблице 1.5. Вычисления проводились с использованием четырех и девяти процессоров.
Сравнение экспериментального времени выполнения эксперимента и теоретического времени T p, вычисленного в соответствии с выражением
,
представлено в таблице 1.5 и на рис. 1.9.
Таблица 1.5. - Результаты вычислительных экспериментов по исследованию параллельного алгоритма умножения матрицы на вектор при блочном разделении данных
Рисунок 1.9 - Зависимость ускорения от количества процессоров при выполнении параллельного алгоритма умножения матрицы на вектор (блочное разбиение матрицы) для разных размеров матриц.
Таблица 1.6. Сравнение экспериментального и теоретического времени выполнения параллельного алгоритма умножения матрицы на вектор при блочном разделении данных
Рисунок 1.10 - График зависимости экспериментального и теоретического времени проведения эксперимента на четырех процессорах от объема исходных данных (блочное разбиение матрицы).
2. Выбор системы высокой производительности
2.1 Классификация архитектур по параллельной обработке данных
Самой ранней и наиболее известной является классификация архитектур вычислительных систем, предложенная в 1966 году М. Флинном. Классификация базируется на понятии потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных, Флинн выделяет четыре класса архитектур:
· SISD = Single Instruction Single Data
· MISD = Multiple Instruction Single Data
· SIMD = Single Instruction Multiple Data
· MIMD = Multiple Instruction Multiple Data)
SISD (single instruction stream / single data stream) - одиночный поток команд и одиночный поток данных. Вообще говоря, эта архитектура не имеет отношения к высокопроизводительным системам. К этому классу относятся, прежде всего, классические последовательные машины. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных.
Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка. В случае векторных систем векторный поток данных следует рассматривать как поток из одиночных неделимых векторов.
MISD (multiple instruction stream / single data stream) - множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не смогли представить убедительный пример реально существующей вычислительной системы, построенной на данном принципе. Ряд исследователей относят конвейерные машины к данному классу, однако это не нашло окончательного признания в научном сообществе. В качестве аналог работы такой системы, по-видимому, можно рассматривать работу банка. С любого терминала можно подать команду и что-то сделать с имеющимся банком данных. Поскольку база данных одна, а команд много, то мы имеем дело с множественным потоком команд и одиночным потоком данных.
SIMD (single instruction stream / multiple data stream) - одиночный поток команд и множественный поток данных. В архитектурах подобного рода сохраняется один поток команд, включающий, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными - элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производиться либо процессорной матрицей, либо с помощью конвейера.
MIMD (multiple instruction stream / multiple data stream) - множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных. Таким образом, в системе такого рода можно наблюдать реальное распараллеливание.
Класс MIMD чрезвычайно широк, поскольку включает в себя всевозможные мультипроцессорные системы: В настоящее время он является чрезвычайно заполненным и возникает потребность в классификации, более избирательно систематизирующее архитектуры, которые попадают в один класс, но совершенно различны по числу процессоров, природе и топологии связи между ними, по способу организации памяти и, конечно же, по технологии программирования. Основная идея такой классификации может состоять, например, в следующем. Считаем, что множественный поток команд может быть обработан двумя способами: либо одним конвейерным устройством обработки, работающем в режиме разделения времени для отдельных потоков, либо каждый поток обрабатывается своим собственным устройством. Первая возможность используется в MIMD компьютерах, которые обычно называют конвейерными или векторными, вторая - в параллельных компьютерах. В основе векторных компьютеров лежит концепция конвейризации, т.е. явного сегментирования арифметического устройства на отдельные части, каждая из которых выполняет свою подзадачу для пары операндов. В основе параллельного компьютера лежит идея использования для решения одной задачи нескольких процессоров, работающих сообща, причем процессоры могут быть как скалярными, так и векторными.
Рисунок 2.1 - Классификация многопроцессорных вычислительных систем.
Данный подход позволяет различать два типа многопроцессорных систем - multiprocessor (мультипроцессоры или системы в общей разделяемой памятью) и multicomputers (мультикомпьютеры или системы с распределенной памятью).
2.1.1 Мультипроцессоры
Для дальнейшей семантики мультипроцессоров учитывается способ построения общей памяти. Возможный подход - использование единой (централизованной) общей памяти (см. рисунок). Такой подход обеспечивает однородный доступ к памяти и служит основой для построения векторных параллельных процессоров (Например: Cray T90) и симметричных мультипроцессоров (Например: IBM eServer, Sun StarFire, HP Superdome, SGI Origin и т.д.).
Рисунок 2.2 - Архитектура многопроцессорных систем с общей (разделяемой) памятью: системы с (а) однородным и (б) неоднородным доступом к памяти
Одной из основных проблем, которые возникают при организации параллельных вычислений на такого типа системах, является доступ с разных процессоров к общим данным и обеспечение, в этой связи, однозначности (когерентности) содержимого разных кэшей (cache coherence problem). Дело в том, что при наличии общих данных копии значений одних и тех же переменных могут оказаться в кэшах разных процессоров. Если в такой ситуации (при наличии копий общих данных) один из процессоров выполнит изменение значения разделяемой переменной, то значения копий в кэшах других процессорах окажутся не соответствующими действительности и их использование приведет к некорректности вычислений. Обеспечение однозначности кэшей обычно реализуется на аппаратном уровне - для этого после изменения значения общей переменной все копии этой переменной в кэшах отмечаются как недействительные и последующий доступ к переменной потребует обязательного обращения к основной памяти. Следует отметить, что необходимость обеспечения когерентности приводит к некоторому снижению скорости вычислений и затрудняет создание систем с достаточно большим количеством процессоров.
Наличие общих данных при выполнении параллельных вычислений приводит к необходимости синхронизации взаимодействия одновременно выполняемых потоков команд. Так, например, если изменение общих данных требует для своего выполнения некоторой последовательности действий, то необходимо обеспечить взаимоисключение (mutual exclusion) с тем, чтобы эти изменения в любой момент времени мог выполнять только один командный поток. Задачи взаимоисключения и синхронизации относятся к числу классических проблем, и их рассмотрение при разработке параллельных программ является одним из основных вопросов параллельного программирования.
Общий доступ к данным может быть обеспечен и при физически распределенной памяти (при этом, естественно, длительность доступа уже не будет одинаковой для всех элементов памяти) - см. рис. 3.1.1.1. Такой подход именуется как неоднородный доступ к памяти (non-uniform memory access or NUMA). Среди систем с таким типом памяти выделяют:
- Системы, в которых для представления данных используется только локальная кэш-память имеющихся процессоров (cache-only memory architecture or COMA); примерами таких систем являются, например, KSR-1 и DDM;
- Системы, в которых обеспечивается когерентность локальных кэшей разных процессоров (cache-coherent NUMA or CC-NUMA); среди систем данного типа SGI Origin 2000, Sun HPC 10000, IBM/Sequent NUMA-Q 2000;
- Системы, в которых обеспечивается общий доступ к локальной памяти разных процессоров без поддержки на аппаратном уровне когерентности кэша (non-cache coherent NUMA or NCC-NUMA); к данному типу относится, например, система Cray T3E.
Использование распределенной общей памяти (distributed sharedmemory or DSM) упрощает проблемы создания мультипроцессоров (известны примеры систем с несколькими тысячами процессоров), однако, возникающие при этом проблемы эффективного использования распределенной памяти (время доступа к локальной и удаленной памяти может различаться на несколько порядков) приводят к существенному повышению сложности параллельного программирования.
Мультипроцессоры COMA
Машины NUMA и CC-NUMA имеют один большой недостаток: обращения к удаленной памяти происходят гораздо медленнее, чем к локальной памяти. В машине CC-NUMA эта разница в производительности в какой-то степени нейтрализуется благодаря использованию кэш-памяти. Однако если количество требуемых удаленных данных сильно превышает вместимость кэш-памяти, промахи будут происходить постоянно и производительность станет очень низкой.
Мы видим, что машины UMA, например, Sun Enterprise 10000, имеют очень высокую производительность, но ограниченны в размерах и довольно дорого стоят. Машины NUMA могут расширяться до больших размеров, но в них требуется ручное или полуавтоматическое размещение страниц, а оно не всегда проходит удачно. Дело в том, что очень трудно предсказать, где какие страницы могут понадобиться, и кроме того, страницы трудно перемещать из-за большого размера. Машины CC-NUMA, например Sequent NUMA-Q, могут работать с очень низкой производительностью, если большому числу процессоров требуется много удаленных данных. Так или иначе, каждая из этих разработок имеет существенные недостатки.
Однако существует процессор, в котором все эти проблемы разрешаются за счет того, что основная память каждого процессора используется как кэш-память. Такая разработка называется COMA (Cache Only Memory Access). В ней страницы не имеют собственных фиксированных машин, как в системах NUMA и CC-NUMA.
Вместо этого физическое адресное пространство делиться на строки, которые перемещаются по системе в случае необходимости. Блоки памяти не имеют собственных машин. Память, которая привлекает строки по мере необходимости, называется Attraction memory. Использование основной памяти в качестве большой кэш-памяти увеличивает частоту успешных обращений в кэш-память, а, следовательно, и производительность.
К сожалению, ничего идеального не бывает. В системе COMA появляется две новых проблемы:
1. Как размещаются строки в кэш-памяти?
2. если строка удаляется из памяти, что произойдет, если это последняя копия?
Первая проблема связана со следующим фактом. Если блок управления памятью транслировал виртуальный адрес в физический и если строки нет в аппаратной кэш-памяти, то очень трудно определить, есть ли вообще эта строка в основной памяти. Аппаратное обеспечение здесь не поможет, поскольку каждая страница состоит из большого количества отдельных строк кэш-памяти, которые перемещаются в системе независимо друг от друга. Даже если известно, что строка отсутствует в основной памяти, как определить, где она находиться? В данном случае нельзя спросить об этом собственную машину, поскольку таковой машины в системе нет.
Было предложено несколько решений этой проблемы. Можно ввести новое аппаратное обеспечение, которое будет следить за тегом каждой строки кэш-памяти. Тогда блок управления памятью может сравнивать тег нужной строки с тегами всех строк кэш-памяти, пока не обнаружит совпадение.
Другое решение - отображать страницы полностью, но при этом не требовать присутствия всех строк кэш-памяти. В этом случае аппаратному обеспечению понадобиться побитовое отображение для каждой страницы, где один бит для каждой строки указывает на присутствие или отсутствие этой строки. Если строка присутствует, она должна находиться в правильной позиции на этой странице. Если она отсутствует, то любая попытка использовать ее вызовет прерывание, что позволит программному обеспечению найти нужную строку и вывести ее.
...Подобные документы
Свободная среда разработки программного обеспечения для компилятора Free Pascal. Библиотека визуальных компонентов. Перенос Delphi-программ с графическим интерфейсом в различные операционные системы. Ввод размерности матрицы и умножение ее на вектор.
контрольная работа [16,9 K], добавлен 09.10.2013Параллельная машина как процессоров, памяти и некоторые методы коммуникации между ними, сферы применения. Рассмотрение особенностей организации параллельности вычислений. Анализ типовых схем коммуникации в многопроцессорных вычислительных системах.
курсовая работа [669,3 K], добавлен 07.09.2015Алгебра матриц: задание численных и символьных элементов вектора и матрицы с и без применения шаблонов, использование векторных и матричных операторов и функций. Операции умножения и деления вектора и матрицы друг на друга и на скалярные числа.
практическая работа [107,0 K], добавлен 05.12.2009Составление процедуры для матрицы, разложения матрицы на множители, решения системы линейных уравнений, нахождения определителя матрицы и матрицы с транспонированием. Суть метода квадратного корня. Разложение матрицы на множители. Листинг программы.
лабораторная работа [39,4 K], добавлен 18.09.2012Абстрактные модели и способы параллельной обработки данных, допустимая погрешность вычислений. Понятие параллельного процесса, их синхронизация и гранулы распараллеливания, определение закона Амдаля. Архитектура многопроцессорных вычислительных систем.
дипломная работа [1,3 M], добавлен 09.09.2010Особенности разработки программы и выбор методов решения задачи. Составление алгоритма, распределение регистров программы и формирование файлов. Описание процедуры очистки памяти, сложения, вычитания, умножения. Тестирование и листинг программы.
лабораторная работа [51,2 K], добавлен 14.05.2011Разработка блок-схемы и программы обработки одномерного массива с доступом к элементам с помощью индексов и с помощью указателей. Словесное описание алгоритма и пользовательского интерфейса, листинг программы обработки матрицы и результат её выполнения.
курсовая работа [391,1 K], добавлен 30.09.2013Описание алгоритма решения задачи по вычислению суммы элементов строк матрицы с использованием графического способа. Детализация укрупненной схемы алгоритма и разработка программы для решения задачи в среде Turbo Pascal. Листинг и тестирование программы.
курсовая работа [446,0 K], добавлен 19.06.2014Реализация программы для решения матричных игр. Задание матрицы игры вручную и случайным образом, нахождение оптимальных стратегий игроков итерационным и методом чистых стратегий. Проектирование и листинг программного кода, сохранение матрицы игры.
контрольная работа [716,7 K], добавлен 11.06.2011Алгоритмы получения реалистических изображений. Применение алгоритма обратной трассировки лучей, ее математическая основа. Составление матрицы и программная реализация. Формирование отраженного и преломленного луча. Модульная структура программы.
курсовая работа [219,3 K], добавлен 24.06.2009Составление алгоритмов и написание программ циклической структуры с использованием векторов, указателей и векторов указателей на вектор на языке C++. Статическое и динамическое распределение памяти. Функция ввода и обработки элементов вектора или матрицы.
контрольная работа [210,5 K], добавлен 25.03.2015Особенности работы с массивами с помощью MS Excel. Вычисление определителей матриц, произведения матриц и матрицы на вектор. Скалярное произведения найденных векторов. Поиск обратных матриц. Решение системы линейных уравнений, проверка найденных решений.
лабораторная работа [270,9 K], добавлен 05.06.2015Понятие определителя матрицы, математические и алгоритмические основы его расчета, функциональные модели, блок-схемы и программная реализация. Сущность метода Гаусса для решения систем линейных алгебраических уравнений и вычисления определителя матрицы.
контрольная работа [455,2 K], добавлен 18.01.2010Разработка алгоритма выполнения операций умножения двоичных чисел в формате расширенной точности на сумматоре обратного кода. Преобразование входной строки в десятичное число. Разработка алгоритма арифметической операции. Тестирование программы-эмулятора.
курсовая работа [119,1 K], добавлен 24.06.2012Разработка программы учета занятости компьютеров в лаборатории. Анализ требований, метод решения. Разработка алгоритма в виде структурных схем. Программная реализация в среде Borland Delphi. Минимальные системные требования для ее корректной работы.
дипломная работа [6,3 M], добавлен 10.06.2013Понятие и основные свойства алгоритма. Линейный, ветвящийся и циклический виды вычислительных процессов. Перевод числа из десятичной системы счисления в двоичную, восьмеричную, шестнадцатеричную системы, сложение чисел, выполнение вычитания и умножения.
контрольная работа [125,7 K], добавлен 15.09.2013Системы линейных алгебраических уравнений. Матричный метод решения систем линейных уравнений. Решение задачи математическим методом. Блок-схема алгоритма и листинг программы. Расчет трудоемкости разработки программы. Расчет себестоимости и цены программы.
дипломная работа [144,8 K], добавлен 25.04.2012Разработка программы на языке Pascal. Описание переменных. Действия, которые должна выполнить программа согласно выбранного алгоритма. Детализация графической части программы. Листинг и тестирование программы. Вывод массива данных на экран монитора.
контрольная работа [360,4 K], добавлен 13.06.2012Разработка эскизного и технического проектов программы преобразования заданной матрицы в ортогональную матрицу. Сравнивание транспонированной матрицы с обратной с целью проверки ортогональности. Выбор состава технических и программных средств реализации.
курсовая работа [52,1 K], добавлен 09.12.2014Характеристика таблицы умножения Пифагора; ее применение. Русские математические изобретения, основанные на манипуляциях, которые приводят к нужному результату. Изучение алгоритма работы русского крестьянского способа умножения. Вычисление длинных чисел.
курсовая работа [1,2 M], добавлен 05.12.2013
