อัลกอริทึมแบบขนาน - แบบจำลอง

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

แบบจำลองข้อมูลแบบขนาน
โมเดลกราฟงาน
แบบจำลองสระว่ายน้ำ
นายแบบทาส
ผู้บริโภคของผู้ผลิตหรือรูปแบบไปป์ไลน์
รุ่นไฮบริด

ข้อมูลแบบขนาน

ในแบบจำลองข้อมูลแบบขนานงานจะถูกกำหนดให้กับกระบวนการและแต่ละงานจะดำเนินการประเภทเดียวกันกับข้อมูลที่ต่างกัน Data parallelism เป็นผลมาจากการดำเนินการเดียวที่ถูกนำไปใช้กับรายการข้อมูลหลายรายการ

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

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

Example - การคูณเมทริกซ์หนาแน่น

โมเดลกราฟงาน

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

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

ที่นี่ปัญหาจะแบ่งออกเป็นงานปรมาณูและดำเนินการเป็นกราฟ แต่ละงานเป็นหน่วยงานอิสระที่มีการพึ่งพางานก่อนหน้าอย่างน้อยหนึ่งงาน หลังจากเสร็จสิ้นภารกิจผลลัพธ์ของงานก่อนหน้าจะถูกส่งผ่านไปยังงานที่ต้องพึ่งพา งานที่มีภารกิจก่อนหน้าจะเริ่มดำเนินการก็ต่อเมื่องานก่อนหน้าทั้งหมดเสร็จสิ้น ผลลัพธ์สุดท้ายของกราฟจะได้รับเมื่องานที่ต้องพึ่งพาสุดท้ายเสร็จสิ้น (ภารกิจที่ 6 ในรูปด้านบน)

แบบจำลองสระว่ายน้ำ

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

ไม่มีการกำหนดงานล่วงหน้าที่ต้องการในกระบวนการ การมอบหมายงานจะรวมศูนย์หรือกระจายอำนาจ ตัวชี้ไปที่งานจะถูกบันทึกไว้ในรายการที่ใช้ร่วมกันทางกายภาพในคิวลำดับความสำคัญหรือในตารางแฮชหรือโครงสร้างหรืออาจถูกบันทึกไว้ในโครงสร้างข้อมูลแบบกระจายทางกายภาพ

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

Example - ค้นหาต้นไม้คู่ขนาน

แบบจำลอง Master-Slave

ในโมเดลต้นแบบทาสกระบวนการหลักอย่างน้อยหนึ่งกระบวนการสร้างงานและจัดสรรให้กับกระบวนการทาส งานอาจได้รับการจัดสรรล่วงหน้าถ้า -

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

รุ่นนี้มีความเหมาะสมเท่าเทียมกันกับ shared-address-space หรือ message-passing paradigms, เนื่องจากการโต้ตอบมีสองวิธีตามธรรมชาติ

ในบางกรณีงานอาจต้องทำให้เสร็จเป็นขั้นตอนและงานในแต่ละขั้นตอนจะต้องเสร็จสิ้นก่อนที่จะสามารถสร้างงานในขั้นตอนถัดไปได้ โมเดลต้นแบบทาสสามารถกำหนดให้เป็นhierarchical หรือ multi-level master-slave model ซึ่งมาสเตอร์ระดับบนสุดจะป้อนงานส่วนใหญ่ให้กับมาสเตอร์ระดับสองซึ่งจะแบ่งงานระหว่างทาสของตัวเองและอาจดำเนินการบางส่วนของงานนั้นเอง

ข้อควรระวังในการใช้โมเดลต้นแบบทาส

ควรใช้ความระมัดระวังเพื่อให้มั่นใจว่าต้นแบบจะไม่กลายเป็นจุดแออัด อาจเกิดขึ้นได้หากงานมีขนาดเล็กเกินไปหรือคนงานค่อนข้างเร็ว

ควรเลือกงานในลักษณะที่ค่าใช้จ่ายในการปฏิบัติงานมีส่วนเหนือต้นทุนการสื่อสารและค่าใช้จ่ายในการซิงโครไนซ์

การโต้ตอบแบบอะซิงโครนัสอาจช่วยให้การโต้ตอบซ้อนทับกันและการคำนวณที่เกี่ยวข้องกับการสร้างงานโดยผู้เชี่ยวชาญ

แบบจำลองท่อ

เป็นที่รู้จักกันในชื่อ producer-consumer model. ที่นี่ชุดข้อมูลจะถูกส่งต่อผ่านชุดของกระบวนการซึ่งแต่ละกระบวนการทำงานบางอย่าง ที่นี่การมาถึงของข้อมูลใหม่ทำให้เกิดการดำเนินการของงานใหม่โดยกระบวนการในคิว กระบวนการสามารถสร้างคิวในรูปของอาร์เรย์เชิงเส้นหรือหลายมิติต้นไม้หรือกราฟทั่วไปที่มีหรือไม่มีรอบ

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

Example - อัลกอริธึมการแยกตัวประกอบ LU แบบขนาน