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

Photo by Pawel Czerwinski on Unsplash

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

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

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

  1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.(任何活細胞周圍不足兩個鄰居時,會因「人口不足」而死去。)
Photo by Leonard Reese on Unsplash

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

  1. 棋盤上的方框只有兩種狀態,活著或死去的細胞。

這樣的規則可以寫成 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]
Photo by Steve Sharp on Unsplash

但還有一個問題:在角落的細胞怎麼辦呢?上面的座標會超出範圍,而該格能判斷的鄰居數量也會有限吧?我個人常用的方式是使用週期性邊界條件(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

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

安裝 SSD1306 驅動程式

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

Photo by Jakob Owens on Unsplash

生命遊戲的程式

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, 0
while 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

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

進一步提升速度的研究

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

在 RPi Pico 使用雙核平行運算

Photo by SpaceX on Unsplash

當然 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

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

生命遊戲:雙核運算版

Photo by Toa Heftiba on Unsplash
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_I2C
gc.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 = 0
i2c = 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

可見就生命遊戲本身的運算來說,時間減少到了原本的 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

Photo by Micaela Parente on Unsplash

當然,說到雙核運算,不免會想到 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 在多執行緒的表現很差。為什麼會這樣呢?

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

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

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

結語

Photo by Thought Catalog on Unsplash

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

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

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

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

Photo by Harrison Broadbent on Unsplash

I just like to write weird stuff that have very little to do with my actual work. My normal blog is https://krantasblog.blogspot.com.

I just like to write weird stuff that have very little to do with my actual work. My normal blog is https://krantasblog.blogspot.com.