Serguey Zefirov (thesz) wrote,
Serguey Zefirov
thesz

Category:

Умножение матриц.

Прочитал про алгоритм Кэннона.

Думается мне, его можно получить преобразованием из систолического алгоритма путём укрупнения вычислений на процессорах.

Я провёл эксперимент на своей давней модели машины потока данных, вроде, при увеличении размера обрабатываемых на одном узле подматриц получается ускорение работы.

В README дана командная строка, так вот вот чем больше сдвиг, задаваемый в параметре --taskOption=shift=n, тем быстрее выполняется умножение. При n=0 на одном узле выполняется 32 умножения матриц 1x1, n=1 - 8 умножений матриц 2x2, n=2 - 2 умножения матриц 4x4. При этом количество операций пересылки между процессорами (весьма затратная процедура, много затратней полезных операций сложения и умножения, которые считаются выполняющимися за один такт) значений падает вдвое с ростом размера подматрицы.

И напоследок алгоритмы умножения для сравнения. Простой алгоритм:
for (i=0;i < N;i&plus&plus)
    for (j=0;j < N; j&plus&plus) {
        C [i][j] = 0;
        for (k=0; k < N;k&plus&plus) {
            m = A[i][k] * B[k][j];
            C [i][j] = C [i][j] + m;
        }
    }
И алгоритм, по своим зависимостям и порядку выполнения наиболее приближенный к систолическому:
for (i=0;i < N;i&plus&plus)
    for (j=0;j < N; j&plus&plus)
        C [i][j] = 0;
for (k=0; k < N;k&plus&plus)
    for (i=0;i < N;i&plus&plus)
        for (j=0;j < N; j&plus&plus) {
            m = A[i][k] * B[k][j];
            C [i][j] = C [i][j] + m;
        }
Совершенно неправильное построение обращений к памяти с точки зрения эффективности на обычной машине. А вот на параллельной работает на ура.
Tags: Хаскель, параллельные вычисления, эксперимент
Subscribe

  • Случайный поиск.

    Вот пример решателя SAT, основанного на случайном поиске вокруг текущего присваивания: http://fmv.jku.at/yalsat/ Основной алгоритм у него таков:…

  • Про конфликты, продолжение.

    Я был неправ в указании источника NP-полноты проблемы получения наименьшего конфликта. Моё текущее понимание таково: если мы удаляем литерал l из…

  • Продолжение про поиск наименьшего ограничения.

    Начало про общую идею, необходимые структуры данных и тп. Надо рассмотреть взаимодействие между возможностями уменьшения ограничений. Это довольно…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 7 comments