ขั้นตอนวิธีของแคนนอน

ขั้นตอนวิธีของแคนนอน (อังกฤษ: Cannon's algorithm) คือขั้นตอนวิธีสำหรับการคูณเมทริกซ์สองเมทริกซ์ที่มีมิติ ${\displaystyle n\times n}$ ด้วยการทำงานแบบขนาน นำเสนอโดย ลิน เอลเลียต แคนนอน (Lynn Elliot Cannon) ในปีค.ศ.1969

อธิบายขั้นตอนวิธี

ให้ A และ B เป็นเมทริกซ์ที่ถูกดำเนินการ และ C เป็นเมทริกซ์ผลลัพธ์ แบ่งเมทริกซ์สองเมทริกซ์ A และ B ให้เป็นเมทริกซ์จตุรัสย่อยๆจำนวน p เมทริกซ์ โดยที่ p คือจำนวนกระบวนการ( process )ทั้งหมด โดยที่ทุกกระบวนการทำงานไปพร้อมๆกัน และสามารถส่งผ่านข้อมูลระหว่างกันได้ ส่งเมทริกซ์ย่อย ${\displaystyle A_{ij}}$ และ ${\displaystyle B_{ij}}$ ลงในกระบวนการ ${\displaystyle P_{ij}}$ เริ่มต้นเรียงตำแหน่งของเมทริกซ์ย่อย ให้แถวที่ i ของเมทริกซ์ A เลื่อนหมุนตามแนวนอนไปด้านซ้ายเป็นจำนวน i ช่อง และสดมภ์ที่ j ของเมทริกซ์ B เลื่อนหมุนตามแนวตั้งไปด้านบนเป็นจำนวน j ช่อง ( i และ j มีค่าตั้งแต่ 0 ถึง n-1 )

ตัวอย่างการเรียงเริ่มต้นของเมทริกซ์ขนาด 4 x 4
เมทริกซ์ A
${\displaystyle {\begin{bmatrix}A_{00}&A_{01}&A_{02}&A_{03}\\A_{10}&A_{11}&A_{12}&A_{13}\\A_{20}&A_{21}&A_{22}&A_{23}\\A_{30}&A_{31}&A_{32}&A_{33}\end{bmatrix}}}$ → ${\displaystyle {\begin{bmatrix}A_{00}&A_{01}&A_{02}&A_{03}\\A_{11}&A_{12}&A_{13}&A_{10}\\A_{22}&A_{23}&A_{20}&A_{21}\\A_{33}&A_{30}&A_{31}&A_{32}\end{bmatrix}}}$

เมทริกซ์ B
${\displaystyle {\begin{bmatrix}B_{00}&B_{01}&B_{02}&B_{03}\\B_{10}&B_{11}&B_{12}&B_{13}\\B_{20}&B_{21}&B_{22}&B_{23}\\B_{30}&B_{31}&B_{32}&B_{33}\end{bmatrix}}}$ → ${\displaystyle {\begin{bmatrix}B_{00}&B_{11}&B_{22}&B_{33}\\B_{10}&B_{21}&B_{32}&B_{03}\\B_{20}&B_{31}&B_{02}&B_{13}\\B_{30}&B_{01}&B_{12}&B_{23}\end{bmatrix}}}$

ให้แต่ละกระบวนการ ${\displaystyle P_{ij}}$ คำนวณหาผลคูณของ ${\displaystyle A_{ij}}$ และ ${\displaystyle B_{ij}}$ ในกระบวนการนั้นๆ แล้วนำไปบวกเพิ่มใน ${\displaystyle C_{ij}}$ จากนั้นเลื่อนเมทริกซ์ย่อยของ A ไปด้านซ้ายในแต่ละแถว และเมทริกซ์ย่อยของ B ไปด้านบนในแต่ละแถว ทำเช่นเดิมทั้งหมด ${\displaystyle {\sqrt {p}}}$ ครั้ง จะได้เมทริกซ์ผลลัพธ์คือ เมตริกซ์ C

ตัวอย่างการเลื่อนครั้งที่1ของเมทริกซ์ขนาด 4 x 4
เมทริกซ์ A
${\displaystyle {\begin{bmatrix}A_{00}&A_{01}&A_{02}&A_{03}\\A_{11}&A_{12}&A_{13}&A_{10}\\A_{22}&A_{23}&A_{20}&A_{21}\\A_{33}&A_{30}&A_{31}&A_{32}\end{bmatrix}}}$ → ${\displaystyle {\begin{bmatrix}A_{01}&A_{02}&A_{03}&A_{00}\\A_{12}&A_{13}&A_{10}&A_{11}\\A_{23}&A_{20}&A_{21}&A_{22}\\A_{30}&A_{31}&A_{32}&A_{33}\end{bmatrix}}}$

เมทริกซ์ B
${\displaystyle {\begin{bmatrix}B_{00}&B_{11}&B_{22}&B_{33}\\B_{10}&B_{21}&B_{32}&B_{03}\\B_{20}&B_{31}&B_{02}&B_{13}\\B_{30}&B_{01}&B_{12}&B_{23}\end{bmatrix}}}$ → ${\displaystyle {\begin{bmatrix}B_{10}&B_{21}&B_{32}&B_{03}\\B_{20}&B_{31}&B_{02}&B_{13}\\B_{30}&B_{01}&B_{12}&B_{23}\\B_{00}&B_{11}&B_{22}&B_{33}\end{bmatrix}}}$

รหัสเทียม

s=sqrt(p)
//เรียงmatrixเริ่มต้น
for i=0 to s-1
   left-circular-shift each row of A by i
      up-circular-shift each column of B by i
//ดำเนินการหาผลคูณ
for k=0 to s-1
   for i=0 to s-1 and j=0 to s-1
      C(i,j) =C(i,j)  + A(i,j)*B(i,j)
      left-circular-shift each row of A by 1
      up-circular-shift each column of B by 1

วิเคราะห์ขั้นตอนวิธี

ทางด้านเวลาการทำงาน ถ้ากระบวนการทุกกระบวนการทำงานพร้อมกันแบบขนาน และกระบวนการแต่ละกระบวนการสามารถส่งเมทริกซ์ย่อยไปยังกระบวนการข้างเคียงได้เพียงหนึ่งกระบวนการต่อครั้ง จะเกิดการส่งเมทริกซ์ย่อยทั้งหมด ${\displaystyle 4{\sqrt {p}}-2}$ ครั้ง และการคูณเมทริกซ์ย่อยแต่ละครั้งใช้การคูณตัวเลขทั้งหมด ${\displaystyle ({\frac {n}{\sqrt {p}}})^{3}}$ จะได้เวลาการทำงานเป็น${\displaystyle {\boldsymbol {\Theta }}({\frac {n^{3}}{p}})}$ ทางด้านหน่วยความจำจะใช้หน่วยความจำคงที่เป็น ${\displaystyle {\boldsymbol {\Theta }}(n^{2})}$
อย่างไรก็ตาม ขั้นตอนวิธีนี้จะใช้ได้ก็ต่อเมื่อจำนวนกระบวนการเป็นตัวเลขที่เกิดจากการยกกำลังสอง เมทริกซ์ที่นำมาคูณกันเป็นเมทริกซ์จตุรัส และขนาดของเมทริกซ์หารจำนวนกระบวนการลงตัว

1. http://www.cs.washington.edu/education/courses/csep524/99wi/lectures/lecture1/sld026.htm
2. http://www.phy.ornl.gov/csep/la/node6.html เก็บถาวร 2010-12-24 ที่ เวย์แบ็กแมชชีน
3. http://www.assembla.com/spaces/parallel_graph_algorithms