อัลกอริทึมแบบขนาน - คู่มือฉบับย่อ

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

การประมวลผลพร้อมกัน

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

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

Parallelism คืออะไร?

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

ในบทช่วยสอนนี้เราจะพูดถึงเฉพาะ parallel algorithms. ก่อนที่จะดำเนินการต่อไปให้เราพูดคุยเกี่ยวกับอัลกอริทึมและประเภทของอัลกอริทึมก่อน

อัลกอริทึมคืออะไร?

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

  • คอมพิวเตอร์ตามลำดับ
  • คอมพิวเตอร์แบบขนาน

ขึ้นอยู่กับสถาปัตยกรรมของคอมพิวเตอร์เรามีอัลกอริทึมสองประเภท -

  • Sequential Algorithm - อัลกอริทึมที่มีการดำเนินการขั้นตอนต่อเนื่องของคำสั่งตามลำดับเวลาเพื่อแก้ปัญหา

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

ไม่ใช่เรื่องง่ายที่จะแบ่งปัญหาใหญ่ออกเป็น sub-problems. ปัญหาย่อยอาจมีการพึ่งพาข้อมูลระหว่างกัน ดังนั้นหน่วยประมวลผลต้องสื่อสารกันเพื่อแก้ปัญหา

พบว่าเวลาที่โปรเซสเซอร์ต้องการในการสื่อสารระหว่างกันมากกว่าเวลาประมวลผลจริง ดังนั้นในขณะที่ออกแบบอัลกอริทึมแบบขนานควรพิจารณาการใช้งาน CPU ที่เหมาะสมเพื่อให้ได้อัลกอริทึมที่มีประสิทธิภาพ

ในการออกแบบอัลกอริทึมให้ถูกต้องเราต้องมีแนวคิดพื้นฐานที่ชัดเจน model of computation ในคอมพิวเตอร์แบบขนาน

แบบจำลองการคำนวณ

คอมพิวเตอร์ทั้งแบบเรียงลำดับและแบบขนานทำงานบนชุดคำสั่ง (สตรีม) ที่เรียกว่าอัลกอริทึม ชุดคำสั่ง (อัลกอริทึม) เหล่านี้จะสั่งคอมพิวเตอร์เกี่ยวกับสิ่งที่ต้องทำในแต่ละขั้นตอน

คอมพิวเตอร์สามารถแบ่งออกเป็นสี่ประเภททั้งนี้ขึ้นอยู่กับสตรีมคำสั่งและสตรีมข้อมูล

  • สตรีมคำสั่งเดียวคอมพิวเตอร์สตรีมข้อมูลเดียว (SISD)
  • สตรีมคำสั่งเดียวคอมพิวเตอร์หลายสตรีมข้อมูล (SIMD)
  • สตรีมคำสั่งหลายเครื่องคอมพิวเตอร์สตรีมข้อมูลเดียว (MISD)
  • สตรีมคำสั่งหลายเครื่องคอมพิวเตอร์หลายสตรีมข้อมูล (MIMD)

คอมพิวเตอร์ SISD

คอมพิวเตอร์ SISD ประกอบด้วย one control unit, one processing unit, และ one memory unit.

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

คอมพิวเตอร์ SIMD

คอมพิวเตอร์ SIMD ประกอบด้วย one control unit, multiple processing units, และ shared memory or interconnection network.

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

หน่วยประมวลผลแต่ละหน่วยมีหน่วยความจำภายในของตัวเองเพื่อเก็บทั้งข้อมูลและคำสั่ง ในคอมพิวเตอร์ SIMD โปรเซสเซอร์จำเป็นต้องสื่อสารกันเอง สิ่งนี้ทำได้โดยshared memory หรือโดย interconnection network.

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

คอมพิวเตอร์ MISD

ตามชื่อที่แนะนำคอมพิวเตอร์ MISD ประกอบด้วย multiple control units, multiple processing units, และ one common memory unit.

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

คอมพิวเตอร์ MIMD

คอมพิวเตอร์ MIMD มี multiple control units, multiple processing units, และก shared memory หรือ interconnection network.

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

บันทึก

  • คอมพิวเตอร์ MIMD ที่แชร์หน่วยความจำทั่วไปเรียกว่า multiprocessors, ในขณะที่ผู้ที่ใช้เครือข่ายเชื่อมต่อจะเรียกว่า multicomputers.

  • ตามระยะทางกายภาพของโปรเซสเซอร์มัลติคอมพิวเตอร์มีสองประเภท -

    • Multicomputer - เมื่อโปรเซสเซอร์ทั้งหมดอยู่ใกล้กันมาก (เช่นในห้องเดียวกัน)

    • Distributed system - เมื่อโปรเซสเซอร์ทั้งหมดอยู่ห่างไกลจากกัน (เช่น - ในเมืองต่างๆ)

การวิเคราะห์อัลกอริทึมช่วยให้เราทราบว่าอัลกอริทึมมีประโยชน์หรือไม่ โดยทั่วไปอัลกอริทึมจะถูกวิเคราะห์ตามเวลาดำเนินการ(Time Complexity) และจำนวนพื้นที่ (Space Complexity) มันต้องการ.

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

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

  • ความซับซ้อนของเวลา (Execution Time)
  • จำนวนโปรเซสเซอร์ทั้งหมดที่ใช้และ
  • ค่าใช้จ่ายทั้งหมด.

ความซับซ้อนของเวลา

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

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

ความซับซ้อนของเวลาของอัลกอริทึมสามารถแบ่งออกเป็นสามประเภท

  • Worst-case complexity - เมื่อระยะเวลาที่อัลกอริทึมต้องการสำหรับอินพุตที่กำหนดคือ maximum.

  • Average-case complexity - เมื่อระยะเวลาที่อัลกอริทึมต้องการสำหรับอินพุตที่กำหนดคือ average.

  • Best-case complexity - เมื่อระยะเวลาที่อัลกอริทึมต้องการสำหรับอินพุตที่กำหนดคือ minimum.

การวิเคราะห์ Asymptotic

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

Note - Asymptoticเป็นเงื่อนไขที่เส้นมีแนวโน้มที่จะพบกับเส้นโค้ง แต่ไม่ตัดกัน ที่นี่เส้นและเส้นโค้งเป็นแบบไม่แสดงอาการซึ่งกันและกัน

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

  • สัญกรณ์ O ขนาดใหญ่
  • สัญกรณ์โอเมก้า
  • สัญกรณ์เธต้า

สัญกรณ์ O ขนาดใหญ่

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

f (n) = O (g (n))

iff มีค่าคงที่เป็นบวก c และ n0 ดังนั้น f(n) ≤ c * g(n) เพื่อทุกสิ่ง n ที่ไหน n ≥ n0.

สัญกรณ์โอเมก้า

สัญกรณ์ Omega เป็นวิธีการแสดงขอบเขตล่างของเวลาดำเนินการของอัลกอริทึม ฟังก์ชั่น -

ฉ (n) = Ω (g (n))

iff มีค่าคงที่เป็นบวก c และ n0 ดังนั้น f(n) ≥ c * g(n) เพื่อทุกสิ่ง n ที่ไหน n ≥ n0.

สัญลักษณ์ Theta

สัญกรณ์ทีต้าเป็นวิธีการแสดงทั้งขอบเขตล่างและขอบเขตบนของเวลาดำเนินการของอัลกอริทึม ฟังก์ชั่น -

ฉ (n) = θ (g (n))

iff มีค่าคงที่เป็นบวก c1, c2, และ n0 เช่น c1 * g (n) ≤ f (n) ≤ c2 * g (n) สำหรับทุกคน n ที่ไหน n ≥ n0.

เร่งความเร็วของอัลกอริทึม

ประสิทธิภาพของอัลกอริทึมแบบขนานถูกกำหนดโดยการคำนวณ speedup. Speedup ถูกกำหนดให้เป็นอัตราส่วนของเวลาในการดำเนินการกรณีที่เลวร้ายที่สุดของอัลกอริธึมแบบลำดับที่รู้จักกันเร็วที่สุดสำหรับปัญหาเฉพาะกับเวลาดำเนินการกรณีที่เลวร้ายที่สุดของอัลกอริทึมแบบขนาน

speedup =
เวลาดำเนินการเคสที่แย่ที่สุดของลำดับที่ทราบเร็วที่สุดสำหรับปัญหาเฉพาะ / เวลาดำเนินการเคสที่แย่ที่สุดของอัลกอริทึมแบบขนาน

จำนวนโปรเซสเซอร์ที่ใช้

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

ค่าใช้จ่ายทั้งหมด

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

ต้นทุนรวม = ความซับซ้อนของเวลา×จำนวนโปรเซสเซอร์ที่ใช้

ดังนั้นไฟล์ efficiency ของอัลกอริทึมแบบขนานคือ -

ประสิทธิภาพ =
เวลาดำเนินการเคสที่แย่ที่สุดของอัลกอริธึมแบบลำดับ / เวลาดำเนินการเคสที่แย่ที่สุดของอัลกอริทึมแบบขนาน

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

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

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

ในแบบจำลองข้อมูลแบบขนานงานจะถูกกำหนดให้กับกระบวนการและแต่ละงานจะดำเนินการประเภทเดียวกันกับข้อมูลที่ต่างกัน 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 แบบขนาน

รุ่นไฮบริด

ต้องใช้โมเดลอัลกอริธึมแบบไฮบริดเมื่ออาจต้องใช้โมเดลมากกว่าหนึ่งแบบในการแก้ปัญหา

โมเดลไฮบริดอาจประกอบด้วยโมเดลหลายแบบที่ใช้ตามลำดับชั้นหรือหลายโมเดลที่ใช้ตามลำดับกับขั้นตอนต่างๆของอัลกอริทึมแบบขนาน

Example - เรียงลำดับอย่างรวดเร็วแบบขนาน

Parallel Random Access Machines (PRAM)เป็นแบบจำลองซึ่งถือเป็นส่วนใหญ่ของอัลกอริทึมแบบขนาน ที่นี่โปรเซสเซอร์หลายตัวจะเชื่อมต่อกับหน่วยความจำบล็อกเดียว แบบจำลอง PRAM ประกอบด้วย -

  • ชุดของโปรเซสเซอร์ประเภทเดียวกัน

  • โปรเซสเซอร์ทั้งหมดใช้หน่วยความจำร่วมกัน โปรเซสเซอร์สามารถสื่อสารระหว่างกันผ่านหน่วยความจำแบบแบ่งใช้เท่านั้น

  • หน่วยการเข้าถึงหน่วยความจำ (MAU) เชื่อมต่อโปรเซสเซอร์กับหน่วยความจำที่ใช้ร่วมกันเดียว

ที่นี่ n จำนวนโปรเซสเซอร์ที่สามารถดำเนินการอิสระได้ nจำนวนข้อมูลในหน่วยเวลาหนึ่ง ๆ ซึ่งอาจส่งผลให้มีการเข้าถึงตำแหน่งหน่วยความจำเดียวกันพร้อมกันโดยโปรเซสเซอร์ที่แตกต่างกัน

เพื่อแก้ปัญหานี้ได้มีการบังคับใช้ข้อ จำกัด ต่อไปนี้กับโมเดล PRAM -

  • Exclusive Read Exclusive Write (EREW) - ที่นี่ไม่อนุญาตให้โปรเซสเซอร์สองตัวอ่านหรือเขียนไปยังตำแหน่งหน่วยความจำเดียวกันในเวลาเดียวกัน

  • Exclusive Read Concurrent Write (ERCW) - ที่นี่ไม่อนุญาตให้โปรเซสเซอร์สองตัวอ่านจากตำแหน่งหน่วยความจำเดียวกันในเวลาเดียวกัน แต่ได้รับอนุญาตให้เขียนไปยังตำแหน่งหน่วยความจำเดียวกันในเวลาเดียวกัน

  • Concurrent Read Exclusive Write (CREW) - ที่นี่โปรเซสเซอร์ทั้งหมดได้รับอนุญาตให้อ่านจากตำแหน่งหน่วยความจำเดียวกันในเวลาเดียวกัน แต่ไม่ได้รับอนุญาตให้เขียนไปยังตำแหน่งหน่วยความจำเดียวกันในเวลาเดียวกัน

  • Concurrent Read Concurrent Write (CRCW) - โปรเซสเซอร์ทั้งหมดได้รับอนุญาตให้อ่านหรือเขียนไปยังตำแหน่งหน่วยความจำเดียวกันในเวลาเดียวกัน

มีหลายวิธีในการปรับใช้โมเดล PRAM แต่วิธีที่โดดเด่นที่สุดคือ -

  • โมเดลหน่วยความจำที่ใช้ร่วมกัน
  • แบบจำลองการส่งข้อความ
  • แบบจำลองข้อมูลแบบขนาน

โมเดลหน่วยความจำที่ใช้ร่วมกัน

หน่วยความจำที่ใช้ร่วมกันเน้นบน control parallelism กว่าใน data parallelism. ในโมเดลหน่วยความจำแบบแบ่งใช้กระบวนการต่างๆจะดำเนินการบนโปรเซสเซอร์ที่แตกต่างกันอย่างอิสระ แต่จะใช้พื้นที่หน่วยความจำร่วมกัน เนื่องจากกิจกรรมของตัวประมวลผลใด ๆ หากมีการเปลี่ยนแปลงในตำแหน่งหน่วยความจำใด ๆ โปรเซสเซอร์ที่เหลือจะมองเห็นได้

เนื่องจากโปรเซสเซอร์หลายตัวเข้าถึงตำแหน่งหน่วยความจำเดียวกันอาจเกิดขึ้นได้ในช่วงเวลาใดเวลาหนึ่งโปรเซสเซอร์มากกว่าหนึ่งตัวกำลังเข้าถึงตำแหน่งหน่วยความจำเดียวกัน สมมติว่าคนหนึ่งกำลังอ่านตำแหน่งนั้นและอีกคนกำลังเขียนตำแหน่งนั้น มันอาจสร้างความสับสน เพื่อหลีกเลี่ยงปัญหานี้กลไกการควบคุมบางอย่างเช่นlock / semaphore, ดำเนินการเพื่อให้แน่ใจว่ามีการยกเว้นซึ่งกันและกัน

การเขียนโปรแกรมหน่วยความจำแบบแบ่งใช้ถูกนำไปใช้ดังต่อไปนี้ -

  • Thread libraries- ไลบรารีเธรดอนุญาตให้มีเธรดการควบคุมหลายเธรดที่ทำงานพร้อมกันในตำแหน่งหน่วยความจำเดียวกัน ไลบรารีเธรดจัดเตรียมอินเทอร์เฟซที่สนับสนุนมัลติเธรดผ่านไลบรารีของรูทีนย่อย มันมีรูทีนย่อยสำหรับ

    • การสร้างและทำลายเธรด
    • การจัดกำหนดการดำเนินการเธรด
    • การส่งผ่านข้อมูลและข้อความระหว่างเธรด
    • การบันทึกและการกู้คืนบริบทเธรด

ตัวอย่างของเธรดไลบรารี ได้แก่ - เธรด Solaris ™สำหรับ Solaris เธรด POSIX ที่ใช้งานใน Linux เธรด Win32 ที่มีอยู่ใน Windows NT และ Windows 2000 และเธรด Java ™ซึ่งเป็นส่วนหนึ่งของ Java ™ Development Kit (JDK) มาตรฐาน

  • Distributed Shared Memory (DSM) Systems- ระบบ DSM สร้างส่วนที่เป็นนามธรรมของหน่วยความจำที่ใช้ร่วมกันบนสถาปัตยกรรมคู่แบบหลวม ๆ เพื่อใช้การเขียนโปรแกรมหน่วยความจำแบบแบ่งใช้โดยไม่ต้องรองรับฮาร์ดแวร์ พวกเขาใช้ไลบรารีมาตรฐานและใช้คุณสมบัติการจัดการหน่วยความจำระดับผู้ใช้ขั้นสูงที่มีอยู่ในระบบปฏิบัติการสมัยใหม่ ตัวอย่างเช่น Tread Marks System, Munin, IVY, Shasta, Brazos และ Cashmere

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

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

ข้อดีของการเขียนโปรแกรมหน่วยความจำร่วม

  • พื้นที่ที่อยู่ส่วนกลางให้แนวทางการเขียนโปรแกรมที่ใช้งานง่ายสำหรับหน่วยความจำ

  • เนื่องจากความใกล้ชิดของหน่วยความจำกับ CPU การแบ่งปันข้อมูลระหว่างกระบวนการต่างๆจึงรวดเร็วและสม่ำเสมอ

  • ไม่จำเป็นต้องระบุการสื่อสารข้อมูลระหว่างกระบวนการอย่างชัดเจน

  • ค่าใช้จ่ายในการสื่อสารในกระบวนการมีความสำคัญเล็กน้อย

  • มันง่ายมากที่จะเรียนรู้

ข้อด้อยของการเขียนโปรแกรมหน่วยความจำร่วม

  • ไม่สามารถพกพาได้
  • การจัดการพื้นที่ข้อมูลเป็นเรื่องยากมาก

รูปแบบการส่งข้อความ

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

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

  • ที่อยู่ของโปรเซสเซอร์ที่จะส่งข้อความ

  • ที่อยู่เริ่มต้นของตำแหน่งหน่วยความจำของข้อมูลในโปรเซสเซอร์ที่ส่ง

  • ประเภทข้อมูลของข้อมูลที่ส่ง

  • ขนาดข้อมูลของข้อมูลที่ส่ง

  • ที่อยู่ของโปรเซสเซอร์ที่ข้อความกำลังถูกส่ง

  • ที่อยู่เริ่มต้นของตำแหน่งหน่วยความจำสำหรับข้อมูลในโปรเซสเซอร์ที่รับ

โปรเซสเซอร์สามารถสื่อสารกันได้โดยวิธีใดวิธีหนึ่งดังต่อไปนี้ -

  • การสื่อสารแบบจุดต่อจุด
  • การสื่อสารโดยรวม
  • อินเทอร์เฟซการส่งข้อความ

การสื่อสารแบบจุดต่อจุด

การสื่อสารแบบจุดต่อจุดเป็นรูปแบบการส่งผ่านข้อความที่ง่ายที่สุด ที่นี่ข้อความสามารถส่งจากโปรเซสเซอร์ที่ส่งไปยังโปรเซสเซอร์ที่รับได้โดยใช้โหมดการถ่ายโอนใด ๆ ต่อไปนี้ -

  • Synchronous mode - ข้อความถัดไปจะถูกส่งหลังจากได้รับการยืนยันว่ามีการส่งข้อความก่อนหน้านี้แล้วเท่านั้นเพื่อรักษาลำดับของข้อความ

  • Asynchronous mode - ในการส่งข้อความถัดไปไม่จำเป็นต้องได้รับการยืนยันการส่งข้อความก่อนหน้านี้

การสื่อสารโดยรวม

การสื่อสารโดยรวมเกี่ยวข้องกับโปรเซสเซอร์มากกว่าสองตัวสำหรับการส่งผ่านข้อความ โหมดต่อไปนี้อนุญาตให้มีการสื่อสารร่วมกัน -

  • Barrier - โหมด Barrier เป็นไปได้หากโปรเซสเซอร์ทั้งหมดที่รวมอยู่ในการสื่อสารเรียกใช้ bock เฉพาะ (เรียกว่า barrier block) สำหรับการส่งข้อความ

  • Broadcast - การออกอากาศมีสองประเภท -

    • One-to-all - ที่นี่โปรเซสเซอร์หนึ่งตัวที่มีการดำเนินการเดียวจะส่งข้อความเดียวกันไปยังโปรเซสเซอร์อื่น ๆ ทั้งหมด

    • All-to-all - ที่นี่โปรเซสเซอร์ทั้งหมดจะส่งข้อความไปยังโปรเซสเซอร์อื่น ๆ ทั้งหมด

ข้อความที่ออกอากาศอาจมีสามประเภท -

  • Personalized - ข้อความที่ไม่ซ้ำกันจะถูกส่งไปยังโปรเซสเซอร์ปลายทางอื่น ๆ ทั้งหมด

  • Non-personalized - โปรเซสเซอร์ปลายทางทั้งหมดได้รับข้อความเดียวกัน

  • Reduction - ในการลดการออกอากาศโปรเซสเซอร์หนึ่งตัวในกลุ่มจะรวบรวมข้อความทั้งหมดจากโปรเซสเซอร์อื่น ๆ ทั้งหมดในกลุ่มและรวมเป็นข้อความเดียวซึ่งโปรเซสเซอร์อื่น ๆ ทั้งหมดในกลุ่มสามารถเข้าถึงได้

ข้อดีของการส่งข้อความ

  • ให้การควบคุมความขนานในระดับต่ำ
  • เป็นแบบพกพา
  • เกิดข้อผิดพลาดน้อยลง
  • ค่าใช้จ่ายน้อยลงในการซิงโครไนซ์แบบขนานและการกระจายข้อมูล

ข้อด้อยของการส่งข้อความ

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

ข้อความผ่านไลบรารี

มีไลบรารีการส่งผ่านข้อความจำนวนมาก ในที่นี้เราจะพูดถึงไลบรารีการส่งผ่านข้อความที่ใช้มากที่สุดสองไลบรารี -

  • อินเทอร์เฟซการส่งข้อความ (MPI)
  • เครื่องเสมือนแบบขนาน (PVM)

อินเทอร์เฟซการส่งข้อความ (MPI)

เป็นมาตรฐานสากลในการสื่อสารระหว่างกระบวนการที่เกิดขึ้นพร้อมกันทั้งหมดในระบบหน่วยความจำแบบกระจาย แพลตฟอร์มคอมพิวเตอร์คู่ขนานที่ใช้กันทั่วไปส่วนใหญ่มีการใช้งานอินเทอร์เฟซการส่งข้อความอย่างน้อยหนึ่งรายการ มีการใช้งานเป็นชุดของฟังก์ชันที่กำหนดไว้ล่วงหน้าที่เรียกว่าlibrary และสามารถเรียกได้จากภาษาต่างๆเช่น C, C ++, Fortran เป็นต้น MPI นั้นทั้งรวดเร็วและพกพาได้เมื่อเทียบกับไลบรารีที่ส่งผ่านข้อความอื่น ๆ

Merits of Message Passing Interface

  • รันบนสถาปัตยกรรมหน่วยความจำแบบแบ่งใช้หรือสถาปัตยกรรมหน่วยความจำแบบกระจายเท่านั้น

  • โปรเซสเซอร์แต่ละตัวมีตัวแปรท้องถิ่นของตัวเอง

  • เมื่อเทียบกับคอมพิวเตอร์หน่วยความจำที่ใช้ร่วมกันขนาดใหญ่คอมพิวเตอร์หน่วยความจำแบบกระจายมีราคาไม่แพง

Demerits of Message Passing Interface

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

เครื่องเสมือนแบบขนาน (PVM)

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

Features of PVM

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

การเขียนโปรแกรมข้อมูลแบบขนาน

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

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

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

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

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

ดังนั้นการเลือกโครงสร้างข้อมูลจะต้องพิจารณาจากสถาปัตยกรรมและประเภทของการดำเนินการที่จะดำเนินการ

โครงสร้างข้อมูลต่อไปนี้มักใช้ในการเขียนโปรแกรมแบบขนาน -

  • รายการที่เชื่อมโยง
  • Arrays
  • Hypercube Network

รายการที่เชื่อมโยง

รายการที่เชื่อมโยงคือโครงสร้างข้อมูลที่มีโหนดหรือมากกว่าที่เชื่อมต่อกันด้วยตัวชี้ โหนดอาจใช้ตำแหน่งหน่วยความจำติดต่อกันหรือไม่ก็ได้ แต่ละโหนดมีสองหรือสามส่วน - หนึ่งdata part ที่เก็บข้อมูลและอีกสองรายการคือ link fieldsที่เก็บแอดเดรสของโหนดก่อนหน้าหรือถัดไป แอดเดรสของโหนดแรกจะถูกเก็บไว้ในตัวชี้ภายนอกที่เรียกว่าhead. โหนดสุดท้ายเรียกว่าtail, โดยทั่วไปไม่มีที่อยู่ใด ๆ

รายการที่เชื่อมโยงมีสามประเภท -

  • รายการที่เชื่อมโยงเดี่ยว
  • รายการที่เชื่อมโยงเป็นทวีคูณ
  • รายการที่เชื่อมโยงแบบวงกลม

รายการที่เชื่อมโยงเดี่ยว

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

รายการที่เชื่อมโยงเป็นทวีคูณ

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

รายการที่เชื่อมโยงแบบวงกลม

รายการที่เชื่อมโยงแบบวงกลมมีความคล้ายคลึงกับรายการที่เชื่อมโยงเดี่ยวมากยกเว้นข้อเท็จจริงที่ว่าโหนดสุดท้ายบันทึกที่อยู่ของโหนดแรก

อาร์เรย์

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

  • ใน statically declared arrays, มิติข้อมูลและขนาดของอาร์เรย์เป็นที่ทราบกันดีในขณะคอมไพล์

  • ใน dynamically declared arrays, มิติข้อมูลและขนาดของอาร์เรย์เป็นที่รู้จักในขณะรันไทม์

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

Hypercube Network

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

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

  • แบ่งและพิชิต
  • วิธีโลภ
  • การเขียนโปรแกรมแบบไดนามิก
  • Backtracking
  • สาขา & ผูกพัน
  • การเขียนโปรแกรมเชิงเส้น

วิธีหารและพิชิต

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

แนวทางการแบ่งแยกและพิชิตเกี่ยวข้องกับขั้นตอนต่อไปนี้ในแต่ละระดับ -

  • Divide - ปัญหาเดิมแบ่งเป็นปัญหาย่อย

  • Conquer - ปัญหาย่อยได้รับการแก้ไขแบบวนซ้ำ

  • Combine - การแก้ปัญหาย่อยจะถูกรวมเข้าด้วยกันเพื่อหาทางออกของปัญหาเดิม

แนวทางการแบ่งและพิชิตถูกนำไปใช้ในอัลกอริทึมต่อไปนี้ -

  • การค้นหาแบบไบนารี
  • จัดเรียงด่วน
  • ผสานการจัดเรียง
  • การคูณจำนวนเต็ม
  • การผกผันของเมทริกซ์
  • การคูณเมทริกซ์

วิธีโลภ

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

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

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

การเขียนโปรแกรมแบบไดนามิก

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

อัลกอริทึมแบบเรียกซ้ำสำหรับ Fibonacci Series เป็นตัวอย่างของการเขียนโปรแกรมแบบไดนามิก

Backtracking Algorithm

การย้อนรอยเป็นเทคนิคการเพิ่มประสิทธิภาพเพื่อแก้ปัญหาที่เกิดร่วมกัน ใช้กับปัญหาทั้งแบบเป็นโปรแกรมและในชีวิตจริง ปัญหาแปดราชินีปริศนาซูโดกุและการเดินผ่านเขาวงกตเป็นตัวอย่างยอดนิยมที่ใช้อัลกอริธึมการย้อนรอย

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

สาขาและขอบเขต

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

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

การเขียนโปรแกรมเชิงเส้น

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

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

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

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

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

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

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

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

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

Bisection width - 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) แสดงเมทริกซ์ทั้งหมด

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

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

การเรียงลำดับเป็นกระบวนการจัดเรียงองค์ประกอบในกลุ่มตามลำดับเฉพาะกล่าวคือเรียงลำดับจากน้อยไปหามากลำดับจากมากไปหาน้อยลำดับตัวอักษร ฯลฯ ในที่นี้จะกล่าวถึงสิ่งต่อไปนี้ -

  • เรียงลำดับการแจงนับ
  • การเรียงลำดับคี่ - คู่
  • เรียงลำดับการผสานแบบขนาน
  • จัดเรียงด่วนอย่างรวดเร็ว

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

เรียงลำดับการแจงนับ

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

ดังนั้นสำหรับการใด ๆ สององค์ประกอบที่ฉันและเจหนึ่งในกรณีดังต่อไปนี้ต้องเป็นจริง -

  • ฉัน <a J
  • i > a j
  • a ผม = a j

อัลกอริทึม

procedure ENUM_SORTING (n)

begin
   for each process P1,j do
      C[j] := 0;
		
   for each process Pi, j do
	
      if (A[i] < A[j]) or A[i] = A[j] and i < j) then
         C[j] := 1;
      else
         C[j] := 0;
			
   for each process P1, j do
      A[C[j]] := A[j];
		
end ENUM_SORTING

การเรียงลำดับคี่ - คู่

Odd-Even Transposition Sort ขึ้นอยู่กับเทคนิค Bubble Sort จะเปรียบเทียบตัวเลขสองตัวที่อยู่ติดกันและสลับตัวเลขหากตัวเลขแรกมากกว่าตัวเลขที่สองเพื่อให้ได้รายการลำดับจากน้อยไปมาก กรณีตรงกันข้ามใช้กับลำดับจากมากไปหาน้อย การเรียงลำดับการขนย้ายคี่ - คู่ทำงานในสองขั้นตอน -odd phase และ even phase. ในทั้งสองเฟสประมวลผลการแลกเปลี่ยนหมายเลขกับหมายเลขที่อยู่ติดกันทางด้านขวา

อัลกอริทึม

procedure ODD-EVEN_PAR (n) 

begin 
   id := process's label 
	
   for i := 1 to n do 
   begin 
	
      if i is odd and id is odd then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
      if i is even and id is even then 
         compare-exchange_min(id + 1); 
      else 
         compare-exchange_max(id - 1);
			
   end for
	
end ODD-EVEN_PAR

เรียงลำดับการผสานแบบขนาน

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

อัลกอริทึม

procedureparallelmergesort(id, n, data, newdata)

begin
   data = sequentialmergesort(data)
	
      for dim = 1 to n
         data = parallelmerge(id, dim, data)
      endfor
		
   newdata = data
end

จัดเรียงด่วนอย่างรวดเร็ว

Hyper quick sort คือการนำการจัดเรียงอย่างรวดเร็วไปใช้บนไฮเปอร์คิวบ์ ขั้นตอนมีดังนี้ -

  • แบ่งรายการที่ไม่เรียงลำดับระหว่างแต่ละโหนด
  • จัดเรียงแต่ละโหนดในเครื่อง
  • จากโหนด 0 ออกอากาศค่ากลาง
  • แยกแต่ละรายการในเครื่องจากนั้นแลกเปลี่ยนครึ่งหนึ่งในมิติสูงสุด
  • ทำซ้ำขั้นตอนที่ 3 และ 4 พร้อมกันจนกว่าขนาดจะถึง 0

อัลกอริทึม

procedure HYPERQUICKSORT (B, n)
begin

   id := process’s label;
	
   for i := 1 to d do
      begin
      x := pivot;
      partition B into B1 and B2 such that B1 ≤ x < B2;
      if ith bit is 0 then
		
      begin
         send B2 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B1 U C;
      endif
      
      else
         send B1 to the process along the ith communication link;
         C := subsequence received along the ith communication link;
         B := B2 U C;
         end else
      end for
		
   sort B using sequential quicksort;
	
end HYPERQUICKSORT

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

  • แบ่งและพิชิต
  • การค้นหาเชิงลึก - แรก
  • การค้นหาแบบกว้าง - แรก
  • Best-First Search

แบ่งและพิชิต

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

แนวทางการแบ่งแยกและพิชิตเกี่ยวข้องกับขั้นตอนต่อไปนี้ในแต่ละระดับ -

  • Divide - ปัญหาเดิมแบ่งเป็นปัญหาย่อย

  • Conquer - ปัญหาย่อยได้รับการแก้ไขแบบวนซ้ำ

  • Combine - การแก้ปัญหาของปัญหาย่อยจะถูกรวมเข้าด้วยกันเพื่อหาทางออกของปัญหาเดิม

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

รหัสเทียม

Binarysearch(a, b, low, high)

if low < high then
   return NOT FOUND
else
   mid ← (low+high) / 2
   if b = key(mid) then
      return key(mid)
   else if b < key(mid) then
      return BinarySearch(a, b, low, mid−1)
   else
   
      return BinarySearch(a, b, mid+1, high)

การค้นหาเชิงลึก - แรก

Depth-First Search (หรือ DFS) คืออัลกอริทึมสำหรับการค้นหาต้นไม้หรือโครงสร้างข้อมูลกราฟที่ไม่มีทิศทาง ที่นี่แนวคิดคือการเริ่มต้นจากโหนดเริ่มต้นที่เรียกว่าrootและสำรวจให้ไกลที่สุดในสาขาเดียวกัน หากเราได้โหนดที่ไม่มีโหนดตัวต่อเราจะส่งคืนและดำเนินการต่อด้วยจุดยอดซึ่งยังไม่มีการเยี่ยมชม

ขั้นตอนของการค้นหาความลึก - แรก

  • พิจารณาโหนด (รูท) ที่ไม่ได้เยี่ยมชมก่อนหน้านี้และทำเครื่องหมายว่าเยี่ยมชมแล้ว

  • ไปที่โหนดตัวต่อแรกที่อยู่ติดกันและทำเครื่องหมายว่าเยี่ยมแล้ว

  • หากโหนดตัวต่อทั้งหมดของโหนดที่พิจารณาถูกเยี่ยมชมแล้วหรือไม่มีโหนดตัวต่อให้กลับไปที่โหนดหลัก

รหัสเทียม

ปล่อย v เป็นจุดยอดที่การค้นหาเริ่มต้นในกราฟ G.

DFS(G,v)

   Stack S := {};
	
   for each vertex u, set visited[u] := false;
   push S, v;
   while (S is not empty) do
     u := pop S;
	  
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbour w of u
            push S, w;
      end if
		
   end while
   
END DFS()

การค้นหาแบบกว้าง - แรก

Breadth-First Search (หรือ BFS) เป็นอัลกอริทึมสำหรับการค้นหาต้นไม้หรือโครงสร้างข้อมูลกราฟที่ไม่ได้กำหนดทิศทาง ที่นี่เราเริ่มต้นด้วยโหนดจากนั้นไปที่โหนดที่อยู่ติดกันทั้งหมดในระดับเดียวกันจากนั้นย้ายไปยังโหนดตัวต่อที่อยู่ติดกันในระดับถัดไป นี้เรียกอีกอย่างว่าlevel-by-level search.

ขั้นตอนของการค้นหาแบบกว้าง - แรก

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

รหัสเทียม

ปล่อย v เป็นจุดยอดที่การค้นหาเริ่มต้นในกราฟ G.

BFS(G,v)

   Queue Q := {};
	
   for each vertex u, set visited[u] := false;
   insert Q, v;
   while (Q is not empty) do
      u := delete Q;
		
      if (not visited[u]) then
         visited[u] := true;
         for each unvisited neighbor w of u
            insert Q, w;
      end if
		
   end while
   
END BFS()

Best-First Search

Best-First Search คืออัลกอริทึมที่สำรวจกราฟเพื่อไปยังเป้าหมายในเส้นทางที่สั้นที่สุด ซึ่งแตกต่างจาก BFS และ DFS การค้นหาที่ดีที่สุดจะทำตามฟังก์ชันการประเมินเพื่อพิจารณาว่าโหนดใดเหมาะสมที่สุดในการสำรวจถัดไป

ขั้นตอนของการค้นหาที่ดีที่สุดเป็นอันดับแรก

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

รหัสเทียม

BFS( m )

   Insert( m.StartNode )
   Until PriorityQueue is empty
      c ← PriorityQueue.DeleteMin
      If c is the goal
      Exit
   Else
   
      Foreach neighbor n of c
         If n "Unvisited"
            Mark n "Visited"
            Insert( n )
      Mark c "Examined"
      
End procedure

กราฟคือสัญกรณ์นามธรรมที่ใช้แสดงการเชื่อมต่อระหว่างคู่ของวัตถุ กราฟประกอบด้วย -

  • Vertices- วัตถุที่เชื่อมต่อกันในกราฟเรียกว่าจุดยอด จุดยอดเรียกอีกอย่างว่าnodes.

  • Edges - ขอบคือลิงค์ที่เชื่อมต่อจุดยอด

กราฟมีสองประเภท -

  • Directed graph - ในกราฟกำกับขอบมีทิศทางกล่าวคือขอบจะเปลี่ยนจากจุดยอดหนึ่งไปยังอีกจุดยอดหนึ่ง

  • Undirected graph - ในกราฟที่ไม่มีทิศทางขอบจะไม่มีทิศทาง

การระบายสีกราฟ

การระบายสีกราฟเป็นวิธีการกำหนดสีให้กับจุดยอดของกราฟเพื่อไม่ให้จุดยอดสองจุดที่อยู่ติดกันมีสีเหมือนกัน ปัญหาการระบายสีกราฟคือ -

  • Vertex coloring - วิธีการระบายสีจุดยอดของกราฟเพื่อไม่ให้จุดยอดสองจุดที่อยู่ติดกันมีสีเดียวกัน

  • Edge Coloring - เป็นวิธีการกำหนดสีให้กับแต่ละขอบเพื่อไม่ให้ขอบสองด้านที่อยู่ติดกันมีสีเดียวกัน

  • Face coloring - กำหนดสีให้กับแต่ละใบหน้าหรือภูมิภาคของกราฟระนาบเพื่อไม่ให้สองใบหน้าที่มีขอบเขตร่วมกันมีสีเดียวกัน

Chromatic Number

Chromatic number คือจำนวนสีขั้นต่ำที่ต้องใช้ในการระบายสีกราฟ ตัวอย่างเช่นจำนวนสีของกราฟต่อไปนี้คือ 3

แนวคิดของการระบายสีกราฟถูกนำไปใช้ในการเตรียมตารางเวลาการกำหนดความถี่วิทยุมือถือ Suduku การจัดสรรการลงทะเบียนและการระบายสีแผนที่

ขั้นตอนในการระบายสีกราฟ

  • ตั้งค่าเริ่มต้นของโปรเซสเซอร์แต่ละตัวในอาร์เรย์ n มิติเป็น 1

  • ตอนนี้ในการกำหนดสีเฉพาะให้กับจุดยอดให้พิจารณาว่าสีนั้นถูกกำหนดให้กับจุดยอดที่อยู่ติดกันแล้วหรือไม่

  • หากโปรเซสเซอร์ตรวจพบสีเดียวกันในจุดยอดที่อยู่ติดกันโปรเซสเซอร์จะตั้งค่าในอาร์เรย์เป็น 0

  • หลังจากทำการเปรียบเทียบn 2แล้วหากองค์ประกอบใด ๆ ของอาร์เรย์เป็น 1 แสดงว่าเป็นสีที่ถูกต้อง

Pseudocode สำหรับการระบายสีกราฟ

begin

   create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n
   status[i0,..in-1] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if aj,k=1 and ij=ikthen
            status[i0,..in-1] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

ต้นไม้ที่มีระยะน้อยที่สุด

ต้นไม้ทอดที่มีผลรวมของน้ำหนัก (หรือความยาว) ของขอบทั้งหมดน้อยกว่าต้นไม้ที่ทอดเป็นไปได้อื่น ๆ ทั้งหมดของกราฟ G เรียกว่า a minimal spanning tree หรือ minimum cost spanningต้นไม้. รูปต่อไปนี้แสดงกราฟที่เชื่อมต่อแบบถ่วงน้ำหนัก

แผนภูมิด้านบนที่เป็นไปได้บางส่วนแสดงอยู่ด้านล่าง -

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

ในการใช้งานโครงสร้างต้นทุนขั้นต่ำจะใช้สองวิธีต่อไปนี้ -

  • อัลกอริทึมของ Prim
  • อัลกอริทึมของ Kruskal

อัลกอริทึมของ Prim

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

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

  • เลือกจุดยอดใด ๆ พูดว่า v 1ของกราฟ G

  • เลือกขอบพูดว่า e 1ของ G เช่นว่า1 = v 1 v 2และ v 1 ≠ v 2และ e 1มีน้ำหนักต่ำสุดระหว่างขอบที่เกิดขึ้นบน v 1ในกราฟ G

  • ตอนนี้ดังต่อไปนี้ขั้นตอนที่ 2 เลือกขั้นต่ำถ่วงน้ำหนักเหตุการณ์ที่เกิดขึ้นที่ขอบบนโวลต์2

  • ดำเนินการต่อไปจนกว่าจะเลือกขอบ n – 1 ที่นี่n คือจำนวนจุดยอด

ต้นไม้ที่ทอดน้อยที่สุดคือ -

อัลกอริทึมของ Kruskal

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

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

  • เลือกขอบของน้ำหนักขั้นต่ำ พูดว่า e 1ของ Graph G และ e 1ไม่ใช่การวนซ้ำ

  • เลือกต่ำสุดขอบถ่วงน้ำหนักถัดไปเชื่อมต่อกับ e 1

  • ดำเนินการต่อไปจนกว่าจะเลือกขอบ n – 1 ที่นี่n คือจำนวนจุดยอด

ต้นไม้ระยะต่ำสุดของกราฟด้านบนคือ -

อัลกอริทึมเส้นทางที่สั้นที่สุด

อัลกอริทึมเส้นทางที่สั้นที่สุดคือวิธีการค้นหาเส้นทางที่มีต้นทุนน้อยที่สุดจากโหนดต้นทาง (S) ไปยังโหนดปลายทาง (D) ในที่นี้เราจะพูดถึงอัลกอริทึมของ Moore หรือที่เรียกว่า Breadth First Search Algorithm

อัลกอริทึมของมัวร์

  • ติดป้ายจุดยอดต้นทาง S และติดป้ายกำกับ i และตั้งค่า i=0.

  • ค้นหาจุดยอดที่ไม่มีป้ายกำกับทั้งหมดที่อยู่ติดกับจุดยอดที่มีป้ายกำกับ i. หากไม่มีจุดยอดเชื่อมต่อกับจุดยอด S แล้วจุดยอด D จะไม่เชื่อมต่อกับ S หากมีจุดยอดเชื่อมต่อกับ S ให้ติดป้ายกำกับi+1.

  • หากมีป้ายกำกับ D ให้ไปที่ขั้นตอนที่ 4 มิฉะนั้นไปที่ขั้นตอนที่ 2 เพื่อเพิ่ม i = i + 1

  • หยุดหลังจากพบความยาวของเส้นทางที่สั้นที่สุด