อัลกอริทึมแบบขนาน - โครงสร้าง

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

Example- การเข้าถึงฉัน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คือจำนวนมิติข้อมูล ไฮเปอร์คิวบ์สามารถสร้างแบบวนซ้ำได้