ในวิทยาการคอมพิวเตอร์เครื่องเข้าถึงแบบสุ่มขนาน ( RAM ขนานหรือPRAM ) เป็นเครื่องนามธรรมหน่วยความจำร่วม ดังที่ชื่อบ่งบอก PRAM มีจุดประสงค์เพื่อใช้เป็นแบบจำลองการคำนวณแบบขนานของเครื่องเข้าถึงแบบสุ่ม (RAM) (ไม่ควรสับสนกับหน่วยความจำเข้าถึงแบบสุ่ม ) ^{[ 1 ]}ในทำนองเดียวกันกับที่นักออกแบบอัลกอริทึมแบบลำดับใช้ RAM เพื่อจำลองประสิทธิภาพของอัลกอริทึม (เช่น ความซับซ้อนของเวลา) นักออกแบบอัลกอริทึมแบบขนานก็ใช้ PRAM เพื่อจำลองประสิทธิภาพของอัลกอริทึมแบบขนาน (เช่น ความซับซ้อนของเวลา ซึ่งโดยทั่วไปจะระบุจำนวนโปรเซสเซอร์ที่สมมติไว้ด้วย) คล้ายกับวิธีที่แบบจำลอง RAM ละเลยปัญหาในทางปฏิบัติ เช่น เวลาในการเข้าถึงหน่วยความจำแคชเทียบกับหน่วยความจำหลัก แบบจำลอง PRAM ละเลยปัญหาเช่นการซิงโครไนซ์และการสื่อสารแต่ให้จำนวนโปรเซสเซอร์ใดๆ (ขึ้นอยู่กับขนาดของปัญหา) ต้นทุนของอัลกอริทึม ตัวอย่างเช่น ประมาณโดยใช้พารามิเตอร์สองตัว O(เวลา) และ O(เวลา × จำนวนโปรเซสเซอร์)

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

1. การอ่านและเขียนแบบผูกขาด (EREW) — เซลล์หน่วยความจำแต่ละเซลล์สามารถอ่านหรือเขียนได้โดยโปรเซสเซอร์เพียงตัวเดียวในแต่ละครั้ง
2. การอ่านพร้อมกันและการเขียนแต่เพียงผู้เดียว (CREW) — โปรเซสเซอร์หลายตัวสามารถอ่านเซลล์หน่วยความจำได้ แต่มีเพียงโปรเซสเซอร์เดียวเท่านั้นที่สามารถเขียนได้ในแต่ละครั้ง
3. การอ่านแบบเอกสิทธิ์เฉพาะการเขียนพร้อมกัน (ERCW) — ส่วนใหญ่ไม่เคยถูกพิจารณาเพราะส่วนใหญ่ไม่ได้เพิ่มพลังงาน^{[ 2 ]}
4. การอ่านพร้อมกันและการเขียนพร้อมกัน (CRCW) — โปรเซสเซอร์หลายตัวสามารถอ่านและเขียนได้ บางครั้ง PRAM แบบ CRCW เรียกว่าเครื่องเข้าถึงแบบสุ่มพร้อมกัน^{[ 3 ]}

ในที่นี้ E และ C หมายถึง 'exclusive' และ 'concurrent' ตามลำดับ การอ่านจะไม่ก่อให้เกิดความคลาดเคลื่อนใดๆ ในขณะที่การเขียนแบบพร้อมกันนั้นมีการกำหนดรายละเอียดเพิ่มเติมดังนี้:

หลักการ ทั่วไป — โปรเซสเซอร์ทุกตัวจะเขียนค่าเดียวกัน หากไม่เป็นเช่นนั้นถือว่าผิดกฎหมาย

โดยพลการ — มีเพียงความพยายามโดยพลการเพียงครั้งเดียวเท่านั้นที่ประสบความสำเร็จ ส่วนความพยายามอื่นๆ จะต้องยุติลง

ลำดับ ความสำคัญ —ลำดับของโปรเซสเซอร์บ่งชี้ว่าใครจะได้เขียนข้อมูล

การดำเนินการ ลดขนาดอาร์เรย์ประเภทอื่นเช่น SUM, Logical AND หรือ MAX

มีการตั้งสมมติฐานแบบง่ายหลายประการในการพิจารณาการพัฒนาอัลกอริธึมสำหรับ PRAM ดังนี้:

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

อัลกอริทึมประเภทนี้มีประโยชน์สำหรับการทำความเข้าใจการใช้ประโยชน์จากการทำงานพร้อมกัน โดยแบ่งปัญหาเดิมออกเป็นปัญหาย่อยที่คล้ายกันและแก้ปัญหาเหล่านั้นแบบขนาน การนำเสนอโมเดล 'P-RAM' อย่างเป็นทางการในวิทยานิพนธ์ของ Wyllie ในปี 1979 ^{[ 4 ]}มีเป้าหมายเพื่อหาปริมาณการวิเคราะห์อัลกอริทึมแบบขนานในลักษณะที่คล้ายคลึงกับเครื่องจักรทัวริงการวิเคราะห์มุ่งเน้นไปที่โมเดลการเขียนโปรแกรม MIMD โดยใช้โมเดล CREW แต่แสดงให้เห็นว่าตัวแปรหลายตัว รวมถึงการใช้งานโมเดล CRCW และการใช้งานบนเครื่อง SIMD สามารถทำได้โดยมีค่าใช้จ่ายคงที่เท่านั้น

อัลกอริทึม PRAM ไม่สามารถประมวลผลแบบขนานได้เมื่อใช้ CPUร่วมกับหน่วยความจำเข้าถึงแบบสุ่มไดนามิก (DRAM) เนื่องจาก DRAM ไม่อนุญาตให้เข้าถึงแบงค์เดียวพร้อมกัน (แม้แต่ที่อยู่ต่างกันในแบงค์เดียวกัน) แต่สามารถนำไปใช้งานในฮาร์ดแวร์หรืออ่าน/เขียนไปยังบล็อกหน่วยความจำเข้าถึงแบบสุ่มคงที่ (SRAM) ภายในของ อาร์เรย์เกตที่ตั้งโปรแกรมได้ (FPGA) ได้ โดยสามารถทำได้โดยใช้อัลกอริทึม CRCW

อย่างไรก็ตาม การทดสอบความเกี่ยวข้องในทางปฏิบัติของอัลกอริทึม PRAM (หรือ RAM) ขึ้นอยู่กับว่าแบบจำลองต้นทุนของอัลกอริทึมนั้นให้การสร้างนามธรรมที่มีประสิทธิภาพของคอมพิวเตอร์บางประเภทหรือไม่ โครงสร้างของคอมพิวเตอร์นั้นอาจแตกต่างจากแบบจำลองนามธรรมอย่างมาก ความรู้เกี่ยวกับชั้นของซอฟต์แวร์และฮาร์ดแวร์ที่จำเป็นต้องแทรกเข้าไปนั้นอยู่นอกเหนือขอบเขตของบทความนี้ แต่บทความเช่นVishkin (2011)แสดงให้เห็นว่าการสร้างนามธรรมแบบ PRAM สามารถรองรับได้โดย กระบวนทัศน์การทำงานแบบ มัลติเธรดแบบชัดเจน (XMT) และบทความเช่นCaragea & Vishkin (2011)แสดงให้เห็นว่าอัลกอริทึม PRAM สำหรับปัญหาการไหลสูงสุดสามารถให้ความเร็วที่เพิ่มขึ้นอย่างมากเมื่อเทียบกับโปรแกรมอนุกรมที่เร็วที่สุดสำหรับปัญหาเดียวกัน บทความGhanim, Vishkin & Barua (2018)แสดงให้เห็นว่าอัลกอริทึม PRAM สามารถบรรลุประสิทธิภาพที่แข่งขันได้แม้ว่าจะไม่มีความพยายามเพิ่มเติมใด ๆ ในการแปลงให้เป็นโปรแกรมมัลติเธรดบน XMT ก็ตาม

นี่คือตัวอย่าง โค้ด SystemVerilogที่ค้นหาค่าสูงสุดในอาร์เรย์โดยใช้เวลาเพียง 2 รอบสัญญาณนาฬิกา โดยจะเปรียบเทียบค่าต่างๆ ในอาร์เรย์ในรอบสัญญาณนาฬิกาแรก และรวมผลลัพธ์ในรอบสัญญาณนาฬิกาที่สอง โค้ดนี้ใช้หน่วยความจำแบบ CRCW m[i] <= 1และmaxNo <= data[i]เขียนข้อมูลพร้อมกัน การทำงานพร้อมกันนี้ไม่ก่อให้เกิดข้อขัดแย้งใดๆ เพราะอัลกอริทึมรับประกันว่าค่าเดียวกันจะถูกเขียนลงในหน่วยความจำเดียวกัน โค้ดนี้สามารถทำงานบนฮาร์ดแวร์ FPGA ได้

module FindMax #( parameter int len ​​= 8 ) ( input bit clock , resetN , input bit [ 7 : 0 ] data [ len ], output bit [ 7 : 0 ] maxNo ); typedef enum bit [ 1 : 0 ] { COMPARE , MERGE , DONE } State ; State state ; bit m [ len ]; int i , j ; always_ff @( posedge clock , negedge resetN ) begin if ( ! resetN ) begin for ( i = 0 ; i < len ; i ++ ) m [ i ] <= 0 ; state <= COMPARE ; จบมิเช่นนั้นเริ่มกรณี( สถานะ) เปรียบเทียบ: เริ่มสำหรับ( i = 0 ; i < len ; i ++ ) เริ่มสำหรับ( j = 0 ; j < len ; j ++ ) เริ่มถ้า( data [ i ] < data [ j ]) m [ i ] <= 1 ; จบจบสถานะ<= รวม; จบรวม: เริ่มสำหรับ( i = 0 ; i < len ; i ++ ) เริ่มถ้า( m [ i ] == 0 ) maxNo <= data[ i ]; สถานะสุดท้าย<= เสร็จสิ้น; จบกรณี สุดท้าย จบโมดูลสุดท้าย

• การวิเคราะห์อัลกอริธึม PRAM
• อนุกรมวิธานของฟลินน์
• อัลกอริทึมแบบไม่ต้องล็อกและไม่ต้องรอคอย
• เครื่องเข้าถึงแบบสุ่ม
• แบบจำลองการเขียนโปรแกรมแบบขนาน
• เอ็กซ์เอ็มทีซี
• หน่วยความจำภายนอกแบบขนาน (รุ่น)

• ต้นแบบ PRAM ของมหาวิทยาลัยซาร์ลันด์ถูกเก็บถาวรเมื่อวันที่ 3 มีนาคม 2016 ที่Wayback Machine
• ต้นแบบ PRAM-On-Chip ของมหาวิทยาลัยแมริแลนด์ต้นแบบนี้มีเป้าหมายที่จะรวมหน่วยประมวลผลแบบขนานจำนวนมากและโครงสร้างสำหรับเชื่อมต่อเข้าด้วยกันบนชิปเดียว
• XMTC: การเขียนโปรแกรมแบบ PRAM - การเผยแพร่ซอฟต์แวร์