ต้นฉบับ https://blog.devel.faith/posts/celular-automata-on-gpu-julia/

ในโพสต์นี้ เราจะเรียนรู้เกี่ยวกับการเขียนโปรแกรม GPU ขั้นพื้นฐานและ Julia โดยการเขียนโค้ด Game of Life ของ Conway คุณอาจต้องการลองค้นหา "Conway's Game of Life" บน Google ;)

ชีวิตคืออะไร? เวอร์ชั่น Tl;dr

สำหรับการวนซ้ำแต่ละครั้ง

  • ประชากรน้อย: เซลล์ใดๆ ที่มีเพื่อนบ้านน้อยกว่า 2 คนจะตาย
  • การมีประชากรมากเกินไป: เซลล์ใดๆ ที่มีเพื่อนบ้านมากกว่า 3 คนจะตาย
  • การสืบพันธุ์: เซลล์ใดๆ ที่มีเพื่อนบ้าน 3 ตัวจะมีชีวิตอยู่

การนำไปปฏิบัติ

ขั้นพื้นฐาน

การเขียนโค้ดสำหรับกฎเหล่านั้นค่อนข้างเป็นเรื่องเล็กน้อย สำหรับแต่ละเซลล์ ให้ตรวจสอบเพื่อนบ้านแล้วทำสิ่งต่างๆ อย่างไรก็ตาม ในบทช่วยสอนนี้ เราต้องการนำตรรกะทั้งหมดมาสู่ GPU การดำเนินการจำนวนมากบนเมทริกซ์สามารถทำได้อย่างมีประสิทธิภาพโดยขนานกันใน GPU ดังนั้นแทนที่จะเขียนการจำลองที่ไร้เดียงสาใน CUDA หรือ OpenCL ระดับต่ำ เราสามารถใช้ประโยชน์จากโค้ดระดับที่สูงกว่าได้โดยการคิดในมุมมองของพีชคณิตเชิงเส้น

การบิดตัว

คุณสามารถคิดว่าการบิดเป็นหน้าต่างที่ทำงานอยู่ เมื่อเคอร์เนล (ตัวกรอง) ทำงานบนบางภูมิภาค มันจะใช้ฟังก์ชันบางประเภทและสร้างค่าใหม่ สิ่งนี้ถูกใช้อย่างมากในการประมวลผลภาพ

สิ่งนี้ทำให้การจำลองของเราเร็วขึ้นได้อย่างไร

การดำเนินการนี้พร้อมใช้งานในไลบรารีพีชคณิตเชิงเส้นส่วนใหญ่ เราเพียงแค่ต้องค้นหาไลบรารี GPU ที่รองรับการบิดแบบ 2D และเคอร์เนลที่คำนวณจำนวนเพื่อนบ้านรอบเซลล์

ถ้าคุณไม่รู้

การคูณพหุนามระดับมัธยมปลายต้องใช้การดำเนินการประมาณ n² (สำหรับแต่ละเทอม ให้คูณกับพจน์ทั้งหมดจากพหุนามอื่น) เราจะทำมันให้ดีขึ้นได้ไหม? จริงๆ แล้ว คุณแค่ต้องการการดำเนินการประมาณ n log n ด้วย fft เมื่อเร็วๆ นี้ มีงานวิจัยแสดงให้เห็นว่าเราสามารถคูณจำนวนเต็มใน O(n log n) ได้เช่นกัน Tl; dr: การบิดมีแนวโน้มที่จะเร็วกว่าลูปทั่วไปของคุณ

รหัส

using ArrayFire
using LinearAlgebra
let
    kernel = convert(Array{Float32}, [1 1 1; 1 0 1; 1 1 1]) |> AFArray
    state = rand(Bool, 30, 30) .+ Float32(.0) |> AFArray
    step = 30
    for i = 1:step
        nb = convolve2(state, kernel, UInt32(0), UInt32(0))
        a = (nb == 2)
        b = (nb == 3)
        state = ((state .* a .+ b) > 0) + Float32(0)
        save_image(string(i, ".tiff"), state)
    end
end

ถึง GIF: convert -scale 2000% -delay 20 -loop 0 *.tiff image.gif