algorithm
Многопоточные алгоритмы

Вступление

Синтаксис

• параллельно перед циклом каждая итерация цикла независима друг от друга и может выполняться параллельно.
• spawn указывает на создание нового потока.
• sync - синхронизировать все созданные потоки.
• Массивы / матрица индексируются от 1 до n в примерах.

Квадратное умножение матрицы многопоточность

multiply-square-matrix-parallel(A, B)
    n = A.lines         
    C = Matrix(n,n) //create a new matrix n*n
    parallel for i = 1 to n
        parallel for j = 1 to n
            C[i][j] = 0
            pour k = 1 to n
                C[i][j] = C[i][j] + A[i][k]*B[k][j]
    return C

Мультипликационный матричный векторный многопоточный

matrix-vector(A,x)
    n = A.lines
    y = Vector(n) //create a new vector of length n
    parallel for i = 1 to n
        y[i] = 0
    parallel for i = 1 to n
        for j = 1 to n
            y[i] = y[i] + A[i][j]*x[j]
    return y

многопоточная слияния

A - это массив и p и q индексы массива, такие как сортировка подматрицы A [p..r] . B - это подматрица, которая будет заполнена сортировкой.

Вызов p-merge-sort (A, p, r, B, s) сортирует элементы из A [p..r] и помещает их в B [s..s + rp] .

p-merge-sort(A,p,r,B,s)
    n = r-p+1
    if n==1
        B[s] = A[p]
    else
        T = new Array(n) //create a new array T of size n
        q = floor((p+r)/2))
        q_prime = q-p+1
        spawn p-merge-sort(A,p,q,T,1)
        p-merge-sort(A,q+1,r,T,q_prime+1)
        sync
        p-merge(T,1,q_prime,q_prime+1,n,B,s)

Вот вспомогательная функция, которая выполняет слияние параллельно.
p-merge предполагает, что две подмассивы для слияния находятся в одном массиве, но не предполагают, что они смежны в массиве. Вот почему нам нужны p1, r1, p2, r2 .

p-merge(T,p1,r1,p2,r2,A,p3)
    n1 = r1-p1+1
    n2 = r2-p2+1
    if n1<n2     //check if n1>=n2
        permute p1 and p2
        permute r1 and r2
        permute n1 and n2
    if n1==0     //both empty?
        return
    else 
        q1 = floor((p1+r1)/2)
        q2 = dichotomic-search(T[q1],T,p2,r2)
        q3 = p3 + (q1-p1) + (q2-p2)
        A[q3] = T[q1]
        spawn p-merge(T,p1,q1-1,p2,q2-1,A,p3)
        p-merge(T,q1+1,r1,q2,r2,A,q3+1)
        sync

А вот вспомогательная функция дихотомического поиска.

x - это ключ к поиску в подматрице T [p..r].

dichotomic-search(x,T,p,r)            
    inf = p
    sup = max(p,r+1)
    while inf<sup
        half = floor((inf+sup)/2)
        if x<=T[half]
            sup = half
        else
            inf = half+1
    return sup