Как приблизиться к оптимальной параллельной эффективности для этого простого кода Джулии?

Question

У меня есть следующий простой код:

function hamming4(bits1::Integer, bits2::Integer)
    return count_ones(bits1 ⊻ bits2)
end

function random_strings2(n, N)
    mask = UInt128(1) << n - 1
    return [rand(UInt128) & mask for i in 1:N]
end




function find_min(strings, n, N)
    minsofar = fill(n, Threads.nthreads())
    # minsofar = n
    Threads.@threads for i in 1:N 
    # for i in 1:N
        for j in i+1:N
            dist = hamming4(strings[i], strings[j])
            if dist < minsofar[Threads.threadid()]
                    minsofar[Threads.threadid()] = dist

            end
        end
    end
    return minimum(minsofar)
    #return minsofar
end


function ave_min(n, N)
    ITER = 10
    strings = random_strings2(n, N)
    new_min = find_min(strings, n, N)
    avesofar = new_min
    # print("New min ", new_min, ". New ave ", avesofar, "\n")
    total = avesofar
    for i in 1:ITER-1
        strings = random_strings2(n, N)
        new_min = find_min(strings, n, N)
        avesofar = avesofar*(i/(i+1)) + new_min/(i+1)
        print("Iteration ", i, ". New min ", new_min, ". New ave ", round(avesofar; digits=2), "\n")
    end
    return avesofar
end

N = 2^16
n = 99

print("Overall average ", ave_min(n, N), "\n")

Когда я запускаю его на AMD 8350 в linux загрузка процессора составляет около 430% (вместо близких к 800%).

Возможно ли сделать распараллеливание более эффективным?

Кроме того, я заметил новый впечатляющий пакет под названием LoopVectorization.jl . Поскольку я вычисляю расстояние Хемминга , что выглядит как векторизация, возможно ли также ускорить код таким образом?

Можно ли векторизовать код с помощью LoopVectorization. jl?

(я совсем новичок в Юлии)

Answer 1

Распараллеливание вашего кода кажется правильным.

Скорее всего, вы запускаете его в Atom или другой IDE. Atom по умолчанию использует только половину ядер (точнее, только физические, а не логические ядра).

Например, работающий в Atom на моем компьютере:

julia> Threads.nthreads()
4

Что вам нужно сделать должен явным образом установить JULIA_NUM_THREADS

Windows командную строку (все еще принимая 8 логических ядер)

set JULIA_NUM_THREADS=8

Linux командная строка

export JULIA_NUM_THREADS=8

После выполнения что ваш код занимает 100% на всех моих ядрах.

EDIT

После обсуждения вы можете сократить время до 20% однопоточного времени, используя Distributed вместо Threads, поскольку это позволяет избежать совместного использования памяти:

Код будет выглядеть примерно так:

using Distributed
addprocs(8)

@everywhere function hamming4(bits1::Integer, bits2::Integer)
    return count_ones(bits1 ⊻ bits2)
end

function random_strings2(n, N)
    mask = UInt128(1) << n - 1
    return [rand(UInt128) & mask for i in 1:N]
end

function find_min(strings, n, N)
    return @distributed (min) for i in 1:N-1
        minimum(hamming4(strings[i], strings[j]) for j in i+1:N)
    end
end

### ... the rest of code remains unchanged