อัลกอริทึมแบบขนาน - การคูณเมทริกซ์

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

เครือข่ายตาข่าย

โทโพโลยีที่ชุดของโหนดเป็นกริด p มิติเรียกว่าโทโพโลยีแบบตาข่าย ที่นี่ขอบทั้งหมดขนานกับแกนกริดและโหนดที่อยู่ติดกันทั้งหมดสามารถสื่อสารกันเองได้

จำนวนโหนดทั้งหมด = (จำนวนโหนดในแถว) × (จำนวนโหนดในคอลัมน์)

เครือข่ายตาข่ายสามารถประเมินได้โดยใช้ปัจจัยต่อไปนี้ -

  • Diameter
  • ความกว้าง Bisection

Diameter - ในเครือข่ายตาข่ายยาวที่สุด distanceระหว่างสองโหนดคือเส้นผ่านศูนย์กลาง เครือข่ายตาข่าย p มิติที่มีkP โหนดมีเส้นผ่านศูนย์กลาง p(k–1).

Bisection width - ความกว้างสองส่วนคือจำนวนขอบขั้นต่ำที่จำเป็นในการลบออกจากเครือข่ายเพื่อแบ่งเครือข่ายตาข่ายออกเป็นสองส่วน

การคูณเมทริกซ์โดยใช้เครือข่ายตาข่าย

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

เมทริกซ์ A และ B มีองค์ประกอบเป็นijและ b ijตามลำดับ การประมวลผลองค์ประกอบ PE IJหมายถึงIJและขIJ จัดเรียงเมทริกซ์ A และ B ในลักษณะที่โปรเซสเซอร์ทุกตัวมีคู่ขององค์ประกอบที่จะคูณ องค์ประกอบของเมทริกซ์ A จะเคลื่อนที่ไปในทิศทางซ้ายและองค์ประกอบของเมทริกซ์ B จะเคลื่อนที่ในทิศทางขึ้น การเปลี่ยนแปลงตำแหน่งขององค์ประกอบเหล่านี้ในเมทริกซ์ A และ B นำเสนอองค์ประกอบการประมวลผลแต่ละรายการ PE ซึ่งเป็นคู่ค่าใหม่ที่จะคูณ

ขั้นตอนในอัลกอริทึม

  • ซวนเซสองเมทริกซ์
  • คำนวณผลิตภัณฑ์ทั้งหมด a ik × b kj
  • คำนวณผลรวมเมื่อขั้นตอนที่ 2 เสร็จสมบูรณ์

อัลกอริทึม

Procedure MatrixMulti

Begin
   for k = 1 to n-1
	
   for all Pij; where i and j ranges from 1 to n
      ifi is greater than k then
         rotate a in left direction
      end if
		
   if j is greater than k then
      rotate b in the upward direction
   end if
	
   for all Pij ; where i and j lies between 1 and n
      compute the product of a and b and store it in c
   for k= 1 to n-1 step 1
   for all Pi;j where i and j ranges from 1 to n
      rotate a in left direction
      rotate b in the upward direction
      c=c+aXb
End

Hypercube Network

ไฮเปอร์คิวบ์เป็นโครงสร้าง n มิติที่ขอบตั้งฉากกันเองและมีความยาวเท่ากัน ไฮเปอร์คิวบ์ n มิติเรียกอีกอย่างว่า n-cube หรือคิวบ์ n มิติ

คุณสมบัติของ Hypercube ที่มีโหนด2 k

  • เส้นผ่านศูนย์กลาง = k
  • ความกว้างทวิ = 2 k – 1
  • จำนวนขอบ = k

การคูณเมทริกซ์โดยใช้ Hypercube Network

ข้อกำหนดทั่วไปของเครือข่าย Hypercube -

  • ปล่อย N = 2mเป็นจำนวนโปรเซสเซอร์ทั้งหมด ให้การประมวลผลเป็น P 0, P 1 ... ..P N-1

  • ให้ i และ i bเป็นจำนวนเต็ม 2 จำนวน 0 <i, i b <N-1 และการแทนค่าฐานสองจะแตกต่างกันเฉพาะในตำแหน่ง b, 0 <b <k – 1

  • ให้เราพิจารณาเมทริกซ์ n × n สองเมทริกซ์ A และเมทริกซ์บี

  • Step 1- องค์ประกอบของเมทริกซ์ A และ B เมทริกซ์ได้รับมอบหมายให้ที่ n 3โปรเซสเซอร์ประมวลผลดังกล่าวว่าในฐานะที่ฉัน j, k จะมีjiและขIK

  • Step 2 - โปรเซสเซอร์ทั้งหมดในตำแหน่ง (i, j, k) คำนวณผลิตภัณฑ์

    C (i, j, k) = A (i, j, k) × B (i, j, k)

  • Step 3 - ผลรวม C (0, j, k) = ΣC (i, j, k) สำหรับ 0 ≤ i ≤ n-1 โดยที่ 0 ≤ j, k <n – 1

บล็อกเมทริกซ์

Block Matrix หรือเมทริกซ์ที่แบ่งพาร์ติชันเป็นเมทริกซ์ที่แต่ละองค์ประกอบแสดงถึงเมทริกซ์แต่ละรายการ แต่ละส่วนเหล่านี้เรียกว่าไฟล์block หรือ sub-matrix.

ตัวอย่าง

ในรูป (a) X คือเมทริกซ์บล็อกโดยที่ A, B, C, D เป็นเมทริกซ์เอง รูป (f) แสดงเมทริกซ์ทั้งหมด

การคูณบล็อกเมทริกซ์

เมื่อเมทริกซ์บล็อกสองเมทริกซ์เป็นเมทริกซ์กำลังสองพวกมันจะถูกคูณด้วยวิธีที่เราทำการคูณเมทริกซ์อย่างง่าย ตัวอย่างเช่น,