Многопроцессорная обработка простых вычислений - PullRequest
Новая
       13

Многопроцессорная обработка простых вычислений

0 голосов
/ 30 сентября 2019

Разбивка проблемы: есть достаточная мотивация, но давайте предположим, что нам дана матрица N (код приведен внизу), и мы хотим решить матрично-векторное уравнение Nv = b, где b - двоичная строка с весом k. В настоящее время я решаю эту проблему, используя numpy.linalg.lstsq. Если «остаток» этого вычисления наименьших квадратов меньше 0,000001, я принимаю его как решение.

Во-первых, мне нужно сгенерировать все двоичные строки определенных length и weight k,Следующая функция делает это. 

'''
This was provided in one of the answers here: 
/12803730/naiti-vse-dvoichnye-stroki-opredelennogo-vesa-maksimalno-bystro
Given a value with weight k, you can get the (co)lexically next value as follows (using bit manipulations).
'''
def ksubsetcolexsuccessor(length,k):
    limit=1<<length
    val=(1<<k)-1
    while val<limit:
        yield "{0:0{1}b}".format(val,length)
        minbit=val&-val
        fillbit = (val+minbit)&~int(val)
        val = val+minbit | (fillbit//(minbit<<1))-1

Так что для length = 6 и k = 2 мы имеем: 0 

00011, 000101, 000110, 001001, 001010, 001100, 010001, 010010, 010100, 011000, 100001, 100010, 100100, 101000, 110000.

Мы подключаем каждый в Nv = b и решаем: 

import numpy as np

solutions = 0
for b in ksubsetcolexsuccessor(n, k):
    v = np.linalg.lstsq(N,np.array(list(b), dtype = float)) 
    if v[1] < 0.000001:
        solutions += 1

Это общее количество решений. Моя проблема в том, что это довольно медленно. Я хотел бы в конечном итоге попробовать n = 72 и k = 8. Я заметил, что используется только часть моего процессора, поэтому я бы хотел многопроцессорность. Я начал с выяснения того, как генерировать вышеупомянутые двоичные строки в чанках. Я написал функцию, которая дает мне значения для val, которая позволяет мне запускать и останавливать генерацию вышеуказанной последовательности двоичных строк в любом месте. Так что мой план состоял в том, чтобы на моей машине было столько кусков, сколько у меня есть ядер. Например:

Процессы Core 1: 000011, 000101, 000110, 001001, 001010, 001100, 010001

Процессы Core 2: 010010, 010100, 011000, 100001, 100010, 100100, 101000, 110000

Я не знаком с multiprocessing и multithreading. Вот что я сделал: 

from multiprocessing import Process

'''
A version where you can specify where to start and end by passing start_val and end_val to the function.
It performs the least-squares computation for each b and tallies the trials that work.
'''
def ksubsetcolexsuccessorSegmentComp(n, k, val, limit, num):
    while val<limit:
        b = "{0:0{1}b}".format(val,n)
        v = np.linalg.lstsq(N,np.array(list(b), dtype = float))
        if v[1] < 0.000001:
            num += 1

        minbit=val&-val
        fillbit = (val+minbit)&~int(val)
        val = val+minbit | (fillbit//(minbit<<1))-1

    print(num)


solutions = 0
length = 6
weight = 2
start_val = (1<<k)-1
mid_val = 18 #If splitting into 2 processes
end_val = 1<<n

#Multiprocessing
p1 = Process(target=ksubsetcolexsuccessorSegmentComp, args=(length, weight, start_val, mid_val, solutions))
p2 = Process(target=ksubsetcolexsuccessorSegmentComp, args=(length, weight, mid_val, end_val, solutions))

p1.start()
p2.start()

p1.join()
p2.join()

Это действительно сокращает время вычислений примерно на 45% (с увеличением длины и веса). Мой процессор работает на уровне около 50% во время этого. Как ни странно, если я разделю на 4 процесса, это займет примерно столько же, сколько если бы я разделился на 2 (даже при том, что мой процессор работает примерно на 85% за это время). На ноутбуке, который я тестирую, у меня есть 2 физических ядра и 4 логических ядра. Сколько процессов является оптимальным на таком процессоре?

Вопросы:

  1. В моем отсутствии знаний о многопроцессорности, я сделал это правильно? то есть это самый быстрый способ многопроцессорной обработки этой программы?
  2. Может кто-нибудь увидеть какой-либо четкий способ улучшить время вычислений? Я смотрел на многопоточность внутри каждого процесса, но, похоже, он замедлял вычисления.
  3. Самая медленная часть этого, безусловно, np.linalg.lsts q. Есть ли какие-нибудь умные способы ускорить эту часть?

Если кто-то хочет проверить код, вот как я генерирую матрицу N: 

'''
Creating the matrix N
'''
def matrixgenerator(G, cardinality, degree):
    matrix = np.zeros((size, (n-1)**2 + 1))
    #Generate the matrix (it'll be missing stab_nn)
    column_index = 0
    for i in range(1,n):
        for j in range(1,n):
            for k in range(size):
                if G[k](i) == j:
                    matrix[k][column_index] = 1
            column_index += 1

    #Determine the final column of N, which is determined by the characteristic vector of stab_nn
    for k in range(size):
        if G[k](n) == n:
            matrix[k][(n-1)**2] = 1

    return matrix

n = 3 #This will give length 6 and weight 2 binary strings
#Try n = 7 and change the second argument below to '4' - this takes roughly 14 min with 2 processes on my device
Group = TransitiveGroup(n, 2) #SageMath 8.8
length = Group.order()
weight = int(size / n)

N = matrixgenerator(Group, length, n)

Это требуетSageMath 8.8. Обратите внимание, что это единственная часть кода, которая требует SageMath. Все остальное эффективно написано на Python 2.7. Заранее спасибо.

...