Симуляция систолического массива в Python

Question

Я пытаюсь смоделировать структуру систолического массива - все, что я узнал из этих слайдов: http://web.cecs.pdx.edu/~mperkows/temp/May22/0020.Matrix-multiplication-systolic.pdf - для умножения матриц в среде Python. Неотъемлемой частью систолического массива является то, что поток данных между PE совпадает с любым умножением или сложением, которое происходит на каком-либо одном узле. У меня возникают трудности с предположением, как именно реализовать такую ​​параллельную процедуру в Python. В частности, я надеюсь лучше понять вычислительный подход для подачи элементов матриц для умножения в систолический массив каскадным способом, в то же время позволяя этим элементам распространяться через массив одновременно.

Я начал писать некоторый код на python для умножения двух на три массива, но в конечном итоге я хочу смоделировать систолический массив любого размера для работы с матрицами любого размера a и b.

from threading import Thread
from collections import deque

vals_deque = deque(maxlen=9*2)#will hold the interconnections between nodes of the systolicarray
dump=deque(maxlen=9) # will be the output of the SystolicArray
prev_size = 0

def setupSystolicArray():
    global SystolicArray
    SystolicArray = [NodeSystolic(i,j) for i in range(3), for i in range(3)]

def spreadInputs(a,b):
    #needs some way to initially propagate the elements of a and b through the top and leftmost parts of the systolic array

    new = map(lambda x: x.start() , SystolicArray) #start all the nodes of the systolic array, they are waiting for an input

    #even if i found a way to put these inputs into the array at the start, I am not sure how to coordinate future inputs into the array in the cascading fashion described in the slides
    while(len(dump) != 9):
        if(len(vals_deque) != prev_size):

            vals = vals_deque[-1]
            row = vals['t'][0]
            col = vals['l'][0]
            a= vals['t'][1]
            b = vals['l'][1]
            # these if elif statements track whether the outputs are at the edge of the systolic array and can be removed
            if(row >= 3):
                dump.append(a)
            elif(col >= 3):
                dump.append(b)
            else:
                #something is wrong with the logic here
                SystolicArray[t][l-1].update(a,b)
                SystolicArray[t-1][l].update(a,b)   

class NodeSystolic:
    def __init__(self,row, col):
        self.row = row
        self.col = col
        self.currval = 0
        self.up = False
        self.ain = 0#coming in from the top
        self.bin = 0#coming in from the side

    def start(self):
        Thread(target=self.continuous, args = ()).start()

    def continuous(self):
        while True:
            if(self.up = True):
                self.currval = self.ain*self.bin
                self.up = False
                self.passon(self.ain, self.bin)
            else:
                pass

    def update(self, left, top):
        self.up = True
        self.ain = top
        self.bin = left

    def passon(self, t,l):
        #this will passon the inputs this node has received onto the next nodes
        vals_deque.append([{'t': [self.row+ 1, self.ain], 'l': [self.col + 1, self.bin]}])

    def returnValue(self):
        return self.currval


def main():
    a = np.array([
    [1,2,3],
    [4,5,6],
    [7,8,9],
    ])

    b = np.array([
    [1,2,3],
    [4,5,6],
    [7,8,9]
    ])

    setupSystolicArray()
    spreadInputs(a,b)

Приведенный выше код не работает и по-прежнему содержит много ошибок. Я надеялся, что кто-нибудь подскажет мне, как улучшить код, или есть ли гораздо более простой способ моделирования параллельных процедур систолического массива с асинхронными свойствами в Python, поэтому с очень большими размерами систолического массива я выиграл ' не нужно беспокоиться о создании слишком большого количества потоков (узлов).

Answer 1

Интересно подумать об имитации систолического массива в Python, но я думаю, что в этом есть некоторые существенные трудности в соответствии с тем, что вы набросали выше.

Наиболее важно то, что существуют проблемы с ограниченным объемом истинного параллелизма в Python, вызванные глобальной блокировкой интерпретатора. Это означает, что вы не получите никакого существенного параллелизма для задач с ограниченным количеством вычислений, и его потоки, вероятно, лучше всего подходят для обработки задач с ограниченным вводом / выводом, таких как веб-запросы или обращения к файловой системе. Ближайший Python может добраться до этого, вероятно, через многопроцессорный модуль, но для этого потребуется отдельный процесс для каждого узла.

Во-вторых, даже если бы вы собирались получить параллелизм в числовых операциях в вашем систолическом массиве, вам нужно было бы иметь некоторые механизмы блокировки, чтобы позволить различным потокам обмениваться данными (или сообщениями) без повреждения памяти друг друга, когда они пытаются читать и записывать данные одновременно.

Что касается структур данных в вашем примере, я думаю, что вам лучше иметь каждый узел в систолическом массиве, имеющий ссылку на его восходящие узлы, а не знать, что он находится в определенном месте в сетке NxM. Я не думаю, что есть какая-то причина, почему систолический массив должен быть прямоугольной сеткой, и любой из Направленного ациклического графа (DAG) все еще будет иметь потенциал для эффективных распределенных вычислений.

В целом, я ожидаю, что вычислительные затраты на выполнение этого моделирования в Python будут огромными по сравнению с тем, что может быть достигнуто с помощью языков более низкого уровня, таких как Scala или C++. Даже тогда, если каждый узел в систолическом массиве не выполняет много вычислений (то есть намного больше, чем несколько множителей), издержки обмена сообщениями между узлами будут существенными. Итак, я предполагаю, что ваша симуляция в основном предназначена для понимания потоков данных и высокоуровневого поведения массива, а не для того, чтобы приблизиться к тому, что может быть обеспечено специальным аппаратным обеспечением DSP (Digital Signal Processing). Если это так, то у меня будет соблазн просто обойтись без потоков и использовать централизованную очередь сообщений, в которую все узлы отправляют сообщения, доставляемые с помощью глобального механизма распространения сообщений.