Блог

Это скорее упражнение в понимании подходящего способа реализации параллелизма. Мне не обязательно нужна оптимальная программа, в частности, для запуска элементарных клеточных автоматов.

Допустим, у нас есть N=10000 ячейки, расположенные в 1d. ECA работает, применяя локальное правило f к каждой ячейке i , учитывая ее соседние состояния и собственное состояние:

 c[t][i] = f(c[t-1][i-1], c[t-1][i], c[t-1][i 1])
 

Способ использования грубой силы для разработки этого для 9999 временных шагов будет примерно таким:

 N = 10000
c[0] = np.random.randint(2, size=N)
for t in range(1, 9999):
    for i in range(N):
        temp[i] = f(c[t-1][i-1], c[t-1][i], c[t-1][i 1])
    c[t] = temp.copy()
 

дайте или примите некоторые инициализации переменных.

Есть ли способ распараллеливать N=10000 приложения на каждом временном шаге? Должно ли это быть сделано с использованием потоков? Или эти локальные правила слишком быстрые и простые, чтобы действительно воспользоваться чем-либо? Я очень мало знаю о том, как использовать преимущества параллелизма с кодом, но это кажется естественной настройкой для него.

Проблема под рукой

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

Ключевая проблема этой проблемы заключается в том, что многопоточность требует решения проблемы, позволяющей выполнять распределенную рабочую нагрузку, которой теоретически является общий клеточный автомат, однако одномерные клеточные автоматы зависят от данных предыдущего поколения (i-1), чтобы получить текущее поколение (i). В результате, если мы выделим, скажем, n потоков для массива из 1 и 0 с длиной n * 256, каждый поток может вычислить правило 258 раз ( 2 из-за границ каждого деления). На первый взгляд это может показаться вполне правдоподобным решением, которым оно и является, однако, если целью является скорость / эффективность, тогда оно будет работать значительно хуже в разной степени в зависимости от используемого языка.

Почему не многопоточность?

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

В дополнение к затратам на раскручивание потоков, если вы не программировали на языке, созданном для параллелизма (т.Е. go-lang), где были встроенные инструменты для ускорения инициализации потоков и обработки конфликтов доступа к памяти (которые вам пришлось бы обрабатывать, учитывая, что каждая новая ячейка зависит от ее ближайшего соседа, которыйперекрытие), есть несколько предостережений, которые вам придется записывать в свои циклы для обработки конфликтов (в основном в памяти) и потенциальных системных сбоев (например, поток блокируется каким-либо системным процессом, что приводит к искажению того, какую часть массива каждый поток должен сравнивать). Все эти крайние случаи в вашей программе значительно замедлят ее, особенно в python, и если только начальное условие вашего клеточного автомата или пространство непосредственной эволюции не было порядка> = n * 500000 за одну эволюцию (по моему опыту), когда время вычисления для одного потока превышает примерно 10секунд на каждые 500000 ячеек не будет повышения производительности и, скорее всего, ухудшения от использования многопоточности.

Вычислительная неприводимость

Другими словами, каждый поток может выполнять вычисления только на одном участке эволюции одновременно. мы не можем использовать потоки для вычисления клеточного автомата по вертикали, а не по горизонтали. Это основа идеи Вольфрама о вычислительной неприводимости (т.е. Весь автомат должен быть вычислен последовательно, чтобы все предыдущие данные были доступны программе). Хотя в некоторых случаях, когда правила могут быть обобщены на логические выражения (ссылочные), это может быть возможно, поскольку результат предсказуем, однако в общем случае это не связано с правилами, такими как правила 30, 110 и 54, которые отображают уникальные вычислительно неприводимые поведения.

Что мы можем сделать?

С учетом сказанного существуют потенциальные способы псевдомногопоточности клеточного автомата с логическими выражениями или без них (описано ниже). Один из этих способов, описанных в книге Wolfram New Kind of Science (справочник), заключается в использовании преимуществ внутреннего размера регистра процессора для распараллеливания сравнений. Метод, описанный в книге, известен как «нарезка битов».

Часто вы можете слышать, как люди ссылаются на то, что компьютеры являются 64-разрядными или 32-разрядными системами, что зависит от размера внутренних регистров. Я говорю, что у нас есть 64-разрядный компьютер, вместо того, чтобы последовательно сравнивать каждый 1 и 0, используя 1/64 размера регистра, мы можем сравнивать единицы по 64 бита или 8 байт, что дает нам теоретический 8-кратный выход скорости на одном ядре. Мы могли бы сделать это, расположив, скажем, на 8-разрядном компьютере начальное условие 1D клеточного автомата по вертикали в виде 3 8-битных чисел.

 1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

1  1  1  0  1  1  0  1  1  0  1  1  0  1  1  0  0  1  1  0  1  1  1  0
     R1|      R2|      R3|      R4|      R5|     R6|      R7|      R8|
 

->

    C1 C2 C3 
 
R1| 1  1  1
R2| 0  1  1
R3| 0  1  1
R4| 0  1  1
R5| 0  1  1
R6| 0  0  1
R7| 1  0  1
R8| 1  1  0    

C1 = 131
C2 = 249
C3 = 254
 

В этой конфигурации левый и правый индексы каждого бита соответствуют биту в той же строке следующего десятичного числа. И, используя эту конфигурацию, мы можем использовать логическое выражение правила и побитовые операторы для этих чисел (при сдвиге первого и последнего чисел) для оценки правила.
Например, в Wolfram Альфа может быть описана как…

 (p, q, r) -> (q AND (NOT p)) OR (q XOR r)  
 

и в go-lang выглядит примерно так, если мы используем битный массив со всеми начальными нулями, предварительно выделенными в 2D-моделировании. Я не слишком знаком с доступом Python к голым металлическим инструкциям, но я могу с уверенностью сказать, что это может быть воспроизведено в python, но очень быстро на статическом языке, таком как go-lang.

 func historicallyAware(evolutions int) {
     for i := 1; i < evolutions 1; i   {
         sim[i][0] = ((^(sim[i-1][len(sim[i-1])-1]) << 1) amp; sim[i-1][0]) | (sim[i-1][0] ^ sim[i-1][1])
         for j := 1; j < len(sim[i])-1; j   {
            sim[i][j] = ((^(sim[i-1][j-1])) amp; sim[i-1][j]) | (sim[i-1][j] ^ sim[i-1][j 1])
         }
         sim[i][len(sim[i])-1] = ((^(sim[i-1][len(sim[i])-2])) amp; sim[i-1][len(sim[i])-1]) | (sim[i-1][len(sim[i])-1] ^ sim[i-1][0]>>1)
    }
}