Введение
Скалярное произведение векторов используется в качестве одной из базовых операций в широком круге методов. При этом используется как в версии скалярного произведения собственно
nn
-мерных векторов (одномерных массивов размера
nn
), так и в версии скалярного произведения строк, столбцов и других линейных подмножеств массивов большей размерности. Последняя отличается от первой тем, что соответствующая подпрограмма получает, кроме стартовых адресов векторов, также и параметры смещения следующих элементов относительно предыдущих (в первой версии эти смещения равны 1). Разные формулы существуют для скалярных произведений в вещественной арифметике и для комплексных векторов. Здесь мы рассматриваем только вещественную арифметику.
Последовательный вариант вычисления скалярного произведения, несмотря на название, имеет ресурс параллелизма степени
2. Дело в том, что, если рассматривать отдельно умножения и сложения, то видно, что при выполнении очередного сложения «подготовительное» умножение к следующему можно выполнить заранее. В принципе, можно, если использовать дополнительную память для хранения всех попарных произведений, вообще выполнить их всех параллельно, а потом последовательно выполнить суммирование вычисленных произведений. Таким образом, в получившемся алгоритме высота параллельной формы будет равна 1 операции умножения плюс
N−1N−1
операций сложения. В таком виде алгоритм должен быть отнесён к алгоритмам линейной сложности как по высоте, так и по ширине параллельной формы. Однако если мы будем последовательно выполнять и умножения, то ширина параллельной формы может быть уменьшена до 2, что даёт нам постоянную сложность по ширине параллельной формы.
Цель исследования: практическое изучение скалярного произведения массива векторов.
Задачи исследования:
1) Определить сущность параллельного программирования: описание, технология, задачи и преимущества;
2) Описать алгоритм действий по решению задачи скалярного произведения массива векторов.
Параллельное программирование: описание, технология, задачи и преимущества
Параллельные вычисления: смысл и реализация
Идеи параллельных вычислений и обработки информации долгое время были уделом специалистов и достаточно значительной проблемой в плане реализации. Особенное значение и массовый интерес они приобрели не так давно. Можно утверждать, что именно развитие интернет-технологий дало новый импульс и параллельное программирование приобрело новые потребительские качества. Это обусловило не только очевидный прогресс технологий и языков программирования. Это реально создало обратное влияние на понимание параллельного процесса.
Технологии параллельного программирования кардинально изменились. Начальное применение компьютерных устройств как вычислителей плавно перешло в использование их как обработчиков информации. Жесткие архитектурные решения уступили место семантике и гибкому распределению программного функционала по «аппаратным исполнителям».
Первоначально основы параллельного программирования закладывались в архитектуре вычислительных устройств. Была предложена классификация на основе понятия потока. Последовательность команд, данных, функционально полных последовательных алгоритмов рассматривалась как объект, который можно исполнить параллельно с другим подобным объектом.
При таком подходе сущность каждого объекта не имела значения, но имело значение такое разбиение на параллельные участки кода, которые могли быть исполнены независимо, то есть данные на входе и выходе каждого потока не пересекались. Каждый поток не зависел от другого потока, а если он нуждался в данных от другого потока, то переходил в режим ожидания. Такая идея привела к четырем архитектурам: SISD - простой поток команд и простой поток данных; MISD - множественный поток команд и простой поток данных; SIMD - простой поток команд и множественный поток данных; MIMD - многовариантный поток команд и множественный поток данных. Эти идеи существовали относительно долго, но не привели к особым эффектам. Сегодня - это история трудного начала. Но это начало создало фундамент для современных достижений.
Как и конструкция жилого здания, архитектура вычислительной системы не касалась семантики. Как будут жить жильцы в здании, какой они смогут сделать ремонт и какую решат установить мебель, никогда не волновало строителей. В самом начале системы параллельного программирования также не придавали значения алгоритму, который должен будет исполняться. Процессор сам разделял код и данные на участки, которые исполнял параллельно. Это давало заметный прирост производительности, но волновала, в частности: проблема разделения памяти между процессами; логика ожидания одним потоком результатов работы другого потока; механизм защиты памяти одного процесса от другого процесса; логика взаимодействия независимых процессоров, ядер; логика переключения между процессами; обмен данными «на лету» между процессами... Разработчики больше ориентировались на аппаратные механизмы, что лишало параллельное многопоточное программирование возможности иметь семантику и не давало возможности программисту управлять процессами адекватно решаемой задаче.