於 Raspberry Pi Pico 實作雙核平行運算、超頻至 270 MHz 的「康威生命遊戲」— — 使用 MicroPython

Alan Wang

25 min readJun 3, 2021

2020 年 4 月 11 日，英國數學家、身為普林斯頓大學教職員一員的約翰‧何頓‧康威（John Horton Conway）在紐澤西因新冠肺炎引起的併發症逝世，享年 82 歲。相較於慘烈的疫情新聞，這則消息在台灣沒有引起多少關注。

很久以前在自學程式時，偶然聽說了「康威生命遊戲」（Conway’s Game of Life），從此對它深感著迷，多年來還替它寫了好幾種不同程式語言的版本。但就和康威本人一樣，當我和其他寫程式的人談起它時，大部分的人根本沒聽過這是什麼。

生命遊戲（不是桌上遊戲那個生命遊戲）堪稱康威最出名的成就之一，是他在 1970 年發明的一個零和遊戲，在平面棋盤裡進行。其規則如下：

Any live cell with fewer than two live neighbours dies, as if by underpopulation.（任何活細胞周圍不足兩個鄰居時，會因「人口不足」而死去。）
Any live cell with two or three live neighbours lives on to the next generation.（任何活細胞周圍有兩到三個鄰居時，能活到下一世代。）
Any live cell with more than three live neighbours dies, as if by overpopulation.（任何活細胞周圍有超過三個鄰居時，會因「人口過剩」而死去。）
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.（死細胞周圍有剛好三個鄰居時，會因「繁殖」復活。）

我們可以把以上規則整理成如下：

棋盤上的方框只有兩種狀態，活著或死去的細胞。
活著的細胞，周圍八個格子要有 2 或 3 個細胞才能活到下一世代，否則死去。
死去的細胞，周圍八個格子要有 3 個細胞才會在下一世代復活。
計算下一世代的棋盤並反覆過程。

這樣的規則可以寫成 B3/S23 (birth = 3, survival = 2, 3)。

這些規則是如此簡單，數學差的人也很容易理解，用程式更是不難寫出來，但執行的效果卻出乎意料地多變。不僅細胞幾乎能像真實生命演化一般消長、發展難以預料，甚至能用來類比通用圖靈機（Universal Turing Machine）。事實上，細胞自動機在自然世界也真實存在，例如某些貝殼的花紋就是以非常相似的邏輯在自我複製。

康威本人就是個遊戲愛好者，他在劍橋與普林斯頓的歲月經常在交誼廳跟人玩雙陸棋、圍棋以及他自己發明的遊戲。生命遊戲是以馮紐曼的細胞自動機（cellular automaton）為基礎，但大幅簡化了設定複雜度 — — 把生命狀態從 29 個變成 2 個。正因如此，或許還加上迷你電腦剛開始普及，人人都能擁有自己的運算設備，生命遊戲被刊登在《科學人》的專欄後就大受歡迎，重新燃起了世人對細胞自動機的興趣。

有趣的是，康威本人對「生命遊戲」又愛又恨：

我以前常說，現在偶爾也會這樣說…我恨透了生命遊戲。其實現在已經不會了。我會有這種感覺，是因為每當我的名字因某個數學領域被提起時，一定都是跟生命遊戲有關，我也不覺得生命遊戲非常有趣…我有過很多其他數學貢獻，我不認為（生命遊戲）值得如此。我發現生命遊戲蓋過了我更加重要的成就，這讓我很不高興。
但…現在我年歲已高，我猜我恨的能力也變淡了吧。它確實是個成就，我對它深感驕傲。我只是不想一直談論它（笑）

但正因生命遊戲那看似簡單的規則、與其中深奧無比的內涵，它至今仍能抓住一代代世人的想像力。

生命遊戲演算法

要寫個生命遊戲並不難，最直覺的方式是用個二維陣列來代表棋盤，然後準備一個同樣大小的當作「緩衝區」。在計算下個世代時，依次判斷每一個格子的細胞有多少鄰居，然後把它的新狀態（活或死）寫到緩衝區棋盤的同一個位置。最後把緩衝區的內容倒到正式的棋盤取代之，計算就完成了。

（其實也可以只準備兩個橫列為緩衝區，一行一行往下算，不過一來記憶體用量還可以接受，二來兩個相同棋盤的做法也適用於後面的平行運算方法，因此我還是會使用這種寫法。）

我早期就是用二維陣列來寫的，但你也不見得需要二維陣列，可以單純用一維陣列來模擬。比如棋盤的橫軸長度是 X，那麼每 X 個元素就代表一行，這樣就只需要一層迴圈，說不定還可以減少物件的數量，畢竟陣列或類似的結構本身也需要記憶體。

而在計算每個細胞的鄰居數時，用相對位置找出周圍 8 格和加總細胞數即可。如果是用一維陣列，而棋盤的橫軸長 X，那麼這 9 格的座標就如下：

[i-1-X, i-X, i+1-X]
[i-1  , i  , i+1  ]
[i-1+X, i+X, i+1+X]

但還有一個問題：在角落的細胞怎麼辦呢？上面的座標會超出範圍，而該格能判斷的鄰居數量也會有限吧？我個人常用的方式是使用週期性邊界條件（periodic boundary condition），也就是把超出範圍的座標投射到棋盤另一邊，好像棋盤的邊緣相互銜接在一起。

在下面的程式中，我的做法是先算 i-1 和 i+1 要不要投射到另一邊（辦法是多加或多減一次 X），然後算出上排和下排座標。在 Python 中，負索引會被自動從串列尾端倒推回去，但超出串列尾端的就會變成錯誤。解法是算 [i-1+X, i+X, i+1+X] 這三個值除陣列總長（棋盤總格數）的餘數；若超過串列長度，多出來的餘數就可以看成從頭重新算起的位置。

硬體與接線

如本文標題所提，我們要使用 Raspberry Pi Pico 開發板，韌體為 MicroPython v1.15，這個版本修正了前一版遺漏的一些東西。關於 Pico 的介紹、用 Thonny IDE 安裝 MicroPython 的方式，則請參閱這篇文章。

為了能看到生命遊戲的棋盤，自然需要一個顯示器模組。以下我們使用 0.96 吋（128 x 64 像素）的 SSD1306 OLED：

接線腳位如下：

VCC → 3V3
GND → GND
SCL → GPIO27
SDA → GPIO26

另外 Pico 本身沒有 reset 鈕，筆者會在腳位 RUN 與 GND 之間放一個按鈕做為 reset。

安裝 SSD1306 驅動程式

Pico 的 MicroPython 韌體不像 ESP8266，沒有內建 OLED 驅動模組，但你可以到 https://github.com/stlehmann/micropython-ssd1306 下載。把裡面的 ssd1306.py 存到板子上（在 Thonny 連上 Pico 後，點檔案→儲存複本→以 ssd1306.py 的名稱儲存）即可。

生命遊戲的程式

import urandom, utime, gc
from machine import Pin, I2C, freq
from micropython import const
from ssd1306 import SSD1306_I2C# 啟用記憶體垃圾回收
gc.enable()# 超頻到 270 MHz
freq(270000000)# 生命遊戲規則, 以 tuple 儲存
RULE     = ((3, ), (2, 3))  # B3/S23# OLED 螢幕寬高
WIDTH    = const(128)
HEIGHT   = const(64)# 細胞的像素大小 (2 x 2, 因此棋盤就是 64 x 32 大小)
DOT_SIZE = const(2)# 初始時隨機產生活細胞的比例 (25%)
RAND_PCT = const(25)# SCL/SDA 腳位
SCL_PIN  = const(27)
SDA_PIN  = const(26)X      = WIDTH // DOT_SIZE  # 棋盤橫軸長
Y      = HEIGHT // DOT_SIZE  # 棋盤縱軸長
TOTAL  = X * Y  # 棋盤總格數# 產生棋盤並隨機設定細胞
board  = [0 if urandom.randint(0, (100 // RAND_PCT) - 1) else 1 for _ in range(TOTAL)]
gen    = 0# 初始化 OLED 螢幕
i2c = I2C(1, scl=Pin(SCL_PIN), sda=Pin(SDA_PIN), freq=400000)
display = SSD1306_I2C(WIDTH, HEIGHT, i2c)
display.fill(0)
display.show()print('Conway\'s Game of Life: matrix size {} x {}'.format(X, Y))# 計算下一世代的函式
def calculate_next_gen():
    global board
    buffer = [0] * TOTAL  # 建立緩衝區棋盤
    for i in range(TOTAL):
        i1 = (i - 1) if (i % X) - 1 >= 0 else (i - 1) + X
        i3 = (i + 1) if (i % X) + 1 < X else (i + 1) - X
        cells = board[i1] + board[i3] + \
                board[i1 - X] + board[i - X] + board[i3 - X] + \
                board[(i1+X)%TOTAL] + board[(i+X)%TOTAL] + \
                board[(i3+X)%TOTAL]
        if cells in RULE[board[i]]:  # 若鄰居數符合條件, 在緩衝區產生細胞
            buffer[i] = 1
    board = buffer  # 將緩衝區覆蓋到棋盤# 在 OLED 繪製棋盤的函式
def display_board():
    display.fill(0)
    for i in range(TOTAL):
        if board[i]:
            display.fill_rect((i % X) * DOT_SIZE, (i // X) * DOT_SIZE, DOT_SIZE, DOT_SIZE, 1)
    display.show()# 執行生命遊戲並計時
t1, t2 = 0, 0while True:
    gen += 1
    print('Gen {}: {} cell(s) (board = {} ms, draw = {} ms)'.format(gen, sum(board), t2, t1))
    
    start = utime.ticks_ms()
    display_board()  # 繪製棋盤
    t1 = utime.ticks_diff(utime.ticks_ms(), start)
    
    start = utime.ticks_ms()
    calculate_next_gen()  # 計算下一世代
    t2 = utime.ticks_diff(utime.ticks_ms(), start)

執行結果如下：

Conway's Game of Life: matrix size 64 x 32
Gen 1: 515 cell(s) (board = 0 ms, draw = 0 ms)
Gen 2: 565 cell(s) (board = 115 ms, draw = 46 ms)
Gen 3: 527 cell(s) (board = 115 ms, draw = 47 ms)
Gen 4: 488 cell(s) (board = 115 ms, draw = 47 ms)
Gen 5: 432 cell(s) (board = 116 ms, draw = 45 ms)
Gen 6: 403 cell(s) (board = 115 ms, draw = 44 ms)
Gen 7: 428 cell(s) (board = 115 ms, draw = 45 ms)
Gen 8: 392 cell(s) (board = 115 ms, draw = 44 ms)
Gen 9: 451 cell(s) (board = 115 ms, draw = 43 ms)
Gen 10: 412 cell(s) (board = 115 ms, draw = 45 ms)
Gen 11: 366 cell(s) (board = 115 ms, draw = 44 ms)
Gen 12: 409 cell(s) (board = 115 ms, draw = 44 ms)
...

我不會很詳細解釋程式的每個環節，但有點基礎的人應該很快就能看懂。

在 MicroPython v1.14 版之後，I2C 模組更明確地分為 I2C（硬體 I2C）和 SoftI2C（軟體 I2C）。硬體 I2C 的第一個參數會指定你要用板子上的 I2C0 或 I2C1 bus。Pico 的相關腳位如下：

注意到我們利用 machine 模組的 freq() 函式將 Pico 的 RP2040 微處理器超頻到 270 MHz，這數字比 MicroPython 預設的 Pico 時脈 125 MHz 或帳面時脈 133 MHz 多出一倍！

當然，官方指出超頻會用到更高的電壓，這可能會縮短晶片壽命，所以囉，風險自負。我也得指出，供電不夠穩時似乎會讓 Pico 比較容易當掉。
注意你用 freq() 設定了有效時脈後，微處理器就會維持在這個時脈，所以不需要超頻時就得記得手動用程式還原它（比如設回 125 MHz）。

以下是不同時脈的執行效果：

125 MHz：64 x 32 棋盤計算約需 249 ms，OLED 繪圖需 60~70 ms
270 MHz：64 x 32 棋盤計算約需 115 ms，OLED 繪圖需 42~46 ms

可見超頻後的棋盤運算部分有明顯的提升。

進一步提升速度的研究

這算是有點題外話：我也試過使用不同的資料容器，看看執行速度能否有進一步提升。在 MicroPython 其實也只有 bytearray、array.array 這兩個選擇。它們能夠減少記憶體用量（array 的型別要設為 B），速度卻不會比 Python 串列快。在串列中，用數值當資料又是我目前所知最快的，用布林值或字串／空字串反而會變慢一點。

在 RPi Pico 使用雙核平行運算

當然 RP2040 還不僅如此，因為它其實是雙核心 Cortex M0+ 處理器。以上面的程式版本來說，你其實只有用其中一個核心在運算而已。我們能否加入另一個核心來加快生命遊戲的速度呢？

在我寫了之前那篇關於 Raspberry Pi Pico 的文章後，我稍微研究了一下雙核運算。其實，MicroPython 用的就是 Python 的 _thread 模組，這是個比較原始的功能；Python 中已經改用 threading 和 multiprocessing 之類的模組了（這便是為何 thread 前面有條底線）。但這還是可以用，而且反正是雙核，你只能在原本的程式中多開一個執行緒，管理上也不至於那麼困難。

下面是個簡單的示範，用一個有 100 個隨機數的串列當作「任務清單」。主程式和在第二核心執行的執行緒，都會不斷從清單取出值，直到清單沒有內容了為止：

import _thread, random, time# 要處理的任務 (100 個隨機數)
task = [random.randint(1, 100) for x in range(10)]
print('Data:', task)# 互斥鎖
lock = _thread.allocate_lock()# 共用的 worker 函式
def worker(worker_id, is_thread):
    while task:  # 任務清單還有資料時重複迴圈        # 模擬處理時間
        time.sleep(round(random.uniform(0.1, 0.5), 2))        try:
            with lock:  # 在使用資源時開互斥鎖
                d = task.pop()  # 從任務清單移除一筆資料
            '''
            也可以寫成
            lock.acquire()
            d = task.pop()
            lock.release()
            '''
        except:
            break
        
        print('Thread {} processing: {}'.format(worker_id, d))
    
    # 結束執行緒
    print('Thread {} ends'.format(worker_id))
    if is_thread:
        _thread.exit()# 在核心 1 執行 worker() 作為新執行緒
_thread.start_new_thread(worker, (1, True))# 在核心 0 (主程式) 執行 worker()
worker(0, False)while task:  # 等待可能還有的任務直到為空
    pass
print('Done')

如果你嘗試在 Pico 用 start_new_thread() 新增超過一個執行緒，就會產生錯誤。

在寫入共用的資源時，你得對它用互斥鎖，好確保一次只有一個執行緒能寫入（其他人則會等待）。lock 物件符合 Python 的資源管理器（context manager）協定，所以可以搭配 with 使用，或者你可手動用 acquire() 和 release() 來上鎖／解鎖資源。

執行效果如下：

Data: [17, 30, 10, 98, 46, 78, 63, 60, 2, 58]
Thread 1 processing: 58
Thread 0 processing: 2
Thread 1 processing: 60
Thread 0 processing: 63
Thread 1 processing: 78
Thread 0 processing: 46
Thread 1 processing: 98
Thread 0 processing: 10
Thread 0 processing: 30
Thread 1 processing: 17
Thread 1 ends
Thread 0 ends
Done

可以看到兩個執行緒輪流分攤了工作並結束。這麼一來，我可以寫同樣的函式，並把工作分割給兩個執行緒去跑，我不需要知道誰做得較多或較少。同樣的原理也可以套用在前面的生命遊戲程式中。

生命遊戲：雙核運算版

import urandom, utime, gc
from _thread import allocate_lock, start_new_thread, exit
from machine import Pin, I2C, freq
from micropython import const
from ssd1306 import SSD1306_I2Cgc.enable()
freq(270000000)RULE     = ((3, ), (2, 3))
WIDTH    = const(128)
HEIGHT   = const(64)
DOT_SIZE = const(2)
RAND_PCT = const(25)
SCL_PIN  = const(27)
SDA_PIN  = const(26)X      = WIDTH // DOT_SIZE
Y      = HEIGHT // DOT_SIZE
TOTAL  = X * Y
board  = [0 if urandom.randint(0, (100 // RAND_PCT) - 1) else 1 for _ in range(TOTAL)]
buffer = []
task   = []
gen    = 0i2c = I2C(1, scl=Pin(SCL_PIN), sda=Pin(SDA_PIN), freq=400000)
display = SSD1306_I2C(WIDTH, HEIGHT, i2c)
display.fill(0)
display.show()lock = allocate_lock()print('Conway\'s Game of Life: matrix size {} x {}'.format(X, Y))def calculate_cells(is_thread):
    while task:
        try:
            with lock:
                i = task.pop()
        except:
            break
        i1 = (i - 1) if (i % X) - 1 >= 0 else (i - 1) + X
        i3 = (i + 1) if (i % X) + 1 < X else (i + 1) - X
        cells = board[i1] + board[i3] + \
                board[i1 - X] + board[i - X] + board[i3 - X] + \
                board[(i1+X)%TOTAL] + board[(i+X)%TOTAL] + \
                board[(i3+X)%TOTAL]
        if cells in RULE[board[i]]:
            buffer[i] = 1
    if is_thread:
        exit()def display_board():
    display.fill(0)
    for i in range(TOTAL):
        if board[i]:
            display.fill_rect((i % X) * DOT_SIZE, (i // X) * DOT_SIZE, DOT_SIZE, DOT_SIZE, 1)
    display.show()t1, t2 = 0, 0while True:
    gen += 1
    print('Gen {}: {} cell(s) (board = {} ms, draw = {} ms)'.format(gen, sum(board), t2, t1))
    
    start = utime.ticks_ms()
    display_board()
    t1 = utime.ticks_diff(utime.ticks_ms(), start)
    
    start = utime.ticks_ms()
    task = list(range(TOTAL))  # 建立任務
    buffer = [0] * TOTAL  # 緩衝棋盤
    start_new_thread(calculate_cells, (True, ))
    calculate_cells(False)
    while task:
        pass
    board = buffer
    t2 = utime.ticks_diff(utime.ticks_ms(), start)

其實主要只有兩個地方不同。首先，我們用串列 task 來儲存要處理的細胞所引，然後兩個核心的 calculate_cells() 會取出一個值，並計算在緩衝區棋盤上下一個世代的值。寫入 buffer 時沒有用到互斥鎖，因為兩個函式寫入的細胞位置是完全不重疊的。

注意以上的 OLED 繪圖仍然只用主程式來處理，沒有比照平行運算模式。我其實有測試過，速度並不會提升，應該是因為程式得透過 I2C bus 寫入 OLED，而這部分的速度就是固定的。

那麼，雙核版的效能提升了多少呢？我測量得到的數據大概如下：

125 MHz：64 x 32 棋盤計算約需 172 ms，OLED 繪圖需 55~65 ms
270 MHz：64 x 32 棋盤計算約需 79 ms，OLED 繪圖需 42~46 ms

可見就生命遊戲本身的運算來說，時間減少到了原本的 69% 左右，OLED 的繪圖速度則大致不變。

務必注意的是，現在我們已快將 Pico 推到了其性能和記憶體的極限，以上程式可能在跑一陣子後就掛掉，而且每當你想停止它和重啟時，也常會發現 Pico 失去反應。通常重新接電、多按幾次 reset 和稍等一下，應該就能喚醒它了。
另一個可考慮的做法是減少棋盤大小 — — 把 DOT_SIZE 常數設為 3 或更大的數字。這樣也能大大提高運算速度。

Gosper glider gun

接著來玩點好玩的。

Photo by Richard R. Schünemann on Unsplash

在生命遊戲中，偶爾可以看到有幾個點組成下面的形狀，而且會緩緩往一個方向前進。這個圖案被稱為「滑翔機」（glider）：

而 Gosper glider gun 就是一個能在康威生命遊戲中製造滑翔機的圖案：

所以我參考這支程式的做法，直接建立 board 串列後給它設定特定的點，就能產生出一樣的圖案：

board[X*5+1] = board[X*5+2] = 1
board[X*6+1] = board[X*6+2] = 1
board[X*3+35] = board[X*3+36] = 1
board[X*4+35] = board[X*4+36] = 1
board[X*3+13] = board[X*3+14] = 1
board[X*4+12] = board[X*4+16] = 1
board[X*5+11] = board[X*5+17] = 1
board[X*6+11] = board[X*6+15] = 1
board[X*6+17] = board[X*6+18] = 1
board[X*7+11] = board[X*7+17] = 1
board[X*8+12] = board[X*8+16] = 1
board[X*9+13] = board[X*9+14] = 1
board[X*1+25] = 1
board[X*2+23] = board[X*2+25] = 1
board[X*3+21] = board[X*3+22] = 1
board[X*4+21] = board[X*4+22] = 1
board[X*5+21] = board[X*5+22] = 1
board[X*6+23] = board[X*6+25] = 1
board[X*7+25] = 1

只不過嘛，因為滑翔機到了邊界會繞到另一邊，所以一陣子後（要是 Pico 沒當掉的話）滑翔機就會回頭摧毀掉 glider gun 了，還會製造出一堆像爆炸的圖案。

雖然這不是本篇要討論的範圍，不過在維基百科跟其他網路來源也能找到其他細胞自動機的規則，例如 B36/S23 或 B3/S012345678。你也可以自己在程式中試試。

Pico vs. ESP32

當然，說到雙核運算，不免會想到 Pico 的雙核心勁敵 ESP32。ESP32 的 MicroPython 也有 _thread 模組，那麼跑起來的表現如何？

我用的是相當常見的 NodeMCU-32S，其晶片為 ESP32-D0WDQ6，MicroPython 版本一樣是 v1.15。我也用 machine.freq() 將時脈設為 240 MHz，不然預設只會有 160 MHz。結果：

ESP32 單執行緒版：64 x 32 棋盤計算約需 124 ms，OLED 繪圖需 44 ms
ESP32 多執行緒版：64 x 32 棋盤計算約需 350~370 ms，OLED 繪圖需 42~44 ms

很奇怪，ESP32 在多執行緒的表現很差。為什麼會這樣呢？

原來，ESP32 的 MicroPython 是以 ESP-IDF（Espressif IoT Development Framework）為基礎，後者又以 FreeRTOS 為基礎。FreeRTOS 會在其中一個核心執行，並在另一個核心創造執行緒給 MicroPython 跑。因此不管你在 MicroPython 新增多少執行緒，都只會在同一個核心上運作（見這個討論）。

有趣的是，同一個討論串也提到 ESP32 的 GIL（Global Interpreter Lock）是打開的，跟正規 Python 一樣。相對的 Pico 的 GIL 被關掉了，這使得 Pico 得以使用多核心，但也比較容易因為一些小問題而掛掉。

所以某方面來說，Pico 的平行運算功能其實是一種特例或「破解」吧。

結語

生命遊戲簡單中帶有複雜，其多變而難以預料的圖形讓人深感著迷。有時棋盤可能在百步之內就陷入停滯，或者看似瀕臨滅亡的棋局，突然從某個角落死灰復燃，一切都是有可能的。

但想模擬出越龐大的生命遊戲棋盤，就需要越強的硬體計算能力，這對多數微處理器來說都是個挑戰，而 MicroPython 的本質又使它天生就較 C++ 等語言更慢。不過，我們看到了 RPi Pico 如何能藉由一些方式，使一部分運算過程的速度能提升到原來的 3 倍左右。儘管不見得很穩定，但就 Pico 的價位來說，能做到如此仍已經夠顛覆期望了。此外，近期 RP2040 處理器本身也開始以 1 美元的價格對外銷售，以它製成的新一代開發板頗值得關注。

我在之前寫文介紹 RPi Pico 時，曾說我認為 CircuitPython 是短期內更強的選擇；其實就一般用途來說，CircuitPython 的豐富驅動程式及活躍的開發社群，確實使它更為實用，而且你還能運用板子的 USB 空間來儲存一些檔案。不過在我寫這篇時，CircuitPython 或者 Arduino C（乃至才剛開始加入支援的 TinyGo）都還沒有有效的多核運算支援。

當然，若要運用平行運算，你就得找個辦法分割任務，但也不是所有的演算法都能這麼做吧。

於 Raspberry Pi Pico 實作雙核平行運算、超頻至 270 MHz 的「康威生命遊戲 」— — 使用 MicroPython