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

จากวิกิพีเดีย สารานุกรมเสรี

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

อธิบายขั้นตอนวิธี[แก้]

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

ตัวอย่างการเรียงเริ่มต้นของเมทริกซ์ขนาด 4 x 4
เมทริกซ์ A

\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}
\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

\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}
\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}

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

ตัวอย่างการเลื่อนครั้งที่1ของเมทริกซ์ขนาด 4 x 4
เมทริกซ์ A

\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}
\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

\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}
\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

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

ทางด้านเวลาการทำงาน ถ้ากระบวนการทุกกระบวนการทำงานพร้อมกันแบบขนาน และกระบวนการแต่ละกระบวนการสามารถส่งเมทริกซ์ย่อยไปยังกระบวนการข้างเคียงได้เพียงหนึ่งกระบวนการต่อครั้ง จะเกิดการส่งเมทริกซ์ย่อยทั้งหมด 4\sqrt{p}-2 ครั้ง และการคูณเมทริกซ์ย่อยแต่ละครั้งใช้การคูณตัวเลขทั้งหมด (\frac{n}{\sqrt{p}})^3 จะได้เวลาการทำงานเป็น\boldsymbol{\Theta} (\frac{n^3}{p}) ทางด้านหน่วยความจำจะใช้หน่วยความจำคงที่เป็น \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
  3. http://www.assembla.com/spaces/parallel_graph_algorithms