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

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

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

→

 เมทริกซ์ B  

→

ให้แต่ละกระบวนการ  คำนวณหาผลคูณของ  และ  ในกระบวนการนั้น ๆ แล้วนำไปบวกเพิ่มใน  จากนั้นเลื่อนเมทริกซ์ย่อยของ A ไปด้านซ้ายในแต่ละแถว และเมทริกซ์ย่อยของ B ไปด้านบนในแต่ละแถว
ทำเช่นเดิมทั้งหมด  ครั้ง จะได้เมทริกซ์ผลลัพธ์ คือ เมทริกซ์ C

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

→

 เมทริกซ์ B  

→

 รหัสเทียม 
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

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

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

 อ้างอิง 
 http://www.cs.washington.edu/education/courses/csep524/99wi/lectures/lecture1/sld026.htm
 http://www.phy.ornl.gov/csep/la/node6.html 
 http://www.assembla.com/spaces/parallel_graph_algorithms

หมวดหมู่:ขั้นตอนวิธีแบบกระจาย
หมวดหมู่:พีชคณิตเชิงเส้นตัวเลข