Теория и практика параллельных вычислений
Разделение данных
При выполнении параллельных алгоритмов умножения матрицы на вектор, кроме матрицы А, необходимо разделить еще вектор b и вектор результата c. Элементы векторов можно продублировать, то есть скопировать все элементы вектора на все процессоры, составляющие многопроцессорную вычислительную систему, или разделить между процессорами. При блочном разбиении вектора из n элементов каждый процессор обрабатывает непрерывную последовательность из k элементов вектора (мы предполагаем, что размерность вектора n нацело делится на число процессоров, т.е. n= k·p).
Поясним, почему дублирование векторов b и
c между процессорами является допустимым решением (далее для простоты изложения будем полагать, что m=n). Векторы b и с состоят из n элементов, т.е. содержат столько же данных, сколько и одна строка или один столбец матрицы. Если процессор хранит строку или столбец матрицы и одиночные элементы векторов b и с, то общее число сохраняемых элементов имеет порядок O(n). Если процессор хранит строку (столбец) матрицы и все элементы векторов b и с, то общее число сохраняемых элементов также порядка O(n). Таким образом, при дублировании и при разделении векторов требования к объему памяти из одного класса сложности.
