อัลกอริทึมแบบขนาน - โครงสร้าง
ในการใช้อัลกอริทึมใด ๆ อย่างถูกต้องสิ่งสำคัญอย่างยิ่งที่คุณต้องเลือกโครงสร้างข้อมูลที่เหมาะสม เป็นเพราะการดำเนินการเฉพาะที่ดำเนินการกับโครงสร้างข้อมูลอาจใช้เวลามากกว่าเมื่อเทียบกับการดำเนินการเดียวกันกับโครงสร้างข้อมูลอื่น
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คือจำนวนมิติข้อมูล ไฮเปอร์คิวบ์สามารถสร้างแบบวนซ้ำได้