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

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

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

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

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

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

Diameter
ความกว้าง Bisection

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

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

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

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

เมทริกซ์ 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 = 2^mเป็นจำนวนโปรเซสเซอร์ทั้งหมด ให้การประมวลผลเป็น P _0, P ₁ ... ..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 ³โปรเซสเซอร์ประมวลผลดังกล่าวว่าในฐานะที่ฉัน 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.