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

แบบจำลอง BSP ได้รับการพัฒนาโดยLeslie Valiantจากมหาวิทยาลัยฮาร์วาร์ดในช่วงทศวรรษ 1980 บทความฉบับสมบูรณ์ได้รับการตีพิมพ์ในปี 1990 ^{[ 1 ]}

ระหว่างปี 1990 ถึง 1992 เลสลี วาเลียนต์ และบิล แมคคอล จากมหาวิทยาลัยออกซ์ฟอร์ดได้ร่วมกันพัฒนาแนวคิดสำหรับ โมเดลการเขียนโปรแกรม BSP แบบ หน่วยความจำแบบกระจายที่มหาวิทยาลัยพรินซ์ตันและมหาวิทยาลัยฮาร์วาร์ด ระหว่างปี 1992 ถึง 1997 แมคคอลได้นำทีมวิจัยขนาดใหญ่ที่ออกซ์ฟอร์ด ซึ่งได้พัฒนาไลบรารี ภาษา และเครื่องมือการเขียนโปรแกรม BSP ต่างๆ รวมถึงอัลกอริทึม BSP แบบขนานขนาดใหญ่จำนวนมาก ซึ่งรวมถึงตัวอย่างแรกๆ ของอัลกอริทึมแบบขนานประสิทธิภาพสูงที่หลีกเลี่ยงการสื่อสาร ^{[ 2 ]} และอัลกอริทึมแบบขนาน "อมตะ" แบบเรียกซ้ำที่ให้ประสิทธิภาพที่ดีที่สุดและการแลกเปลี่ยนพารามิเตอร์ที่เหมาะสมที่สุด^{[ 3 ]}

ด้วยความสนใจและแรงผลักดันที่เพิ่มขึ้น McColl จึงนำกลุ่มจาก Oxford, Harvard, Florida, Princeton, Bell Labs , Columbia และ Utrecht พัฒนาและเผยแพร่มาตรฐาน BSPlib สำหรับการเขียนโปรแกรม BSP ในปี 1996 ^{[ 4 ]}

Valiant ได้พัฒนาส่วนขยายของโมเดล BSP ในช่วงทศวรรษ 2000 ซึ่งนำไปสู่การเผยแพร่โมเดล Multi-BSP ในปี 2011 ^{[ 5 ]}

ในปี 2017 McColl ได้พัฒนาส่วนขยายใหม่ที่สำคัญของโมเดล BSP ซึ่งให้ความทนทานต่อข้อผิดพลาดและความทนทานต่อส่วนท้ายสำหรับการคำนวณแบบขนานขนาดใหญ่ใน AI การวิเคราะห์ และการคำนวณประสิทธิภาพสูง (HPC) ^{[ 6 ]}ดูเพิ่มเติมที่ ^{[ 7 ]}

คอมพิวเตอร์ BSP ประกอบด้วยส่วนประกอบดังต่อไปนี้:

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

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

อัลกอริทึม BSP อาศัยคุณลักษณะที่สามเป็นอย่างมาก กล่าวคือ การคำนวณจะดำเนินไปตามลำดับของซูเปอร์สเต็ป ทั่วโลก ซึ่งประกอบด้วยส่วนประกอบสามส่วน:

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

การคำนวณและการสื่อสารไม่จำเป็นต้องเรียงลำดับตามเวลา การสื่อสารโดยทั่วไปจะอยู่ในรูปแบบของ การเรียกใช้ PUTและGET แบบทางเดียว ผ่านการเข้าถึงหน่วยความจำโดยตรงระยะไกล (RDMA) มากกว่า การเรียก ใช้การส่งและรับข้อความแบบ สองทางเป็นคู่ๆ

การซิงโครไนซ์ของสิ่งกีดขวางจะสรุปขั้นตอนซูเปอร์สเต็ป—โดยรับประกันว่าการสื่อสารด้านเดียวทั้งหมดจะเสร็จสิ้นอย่างถูกต้อง ระบบที่ใช้การสื่อสารสองด้านจะรวมต้นทุนการซิงโครไนซ์นี้โดยปริยายสำหรับทุกข้อความที่ส่ง วิธีการซิงโครไนซ์ของสิ่งกีดขวางอาศัยสิ่งอำนวยความสะดวกด้านฮาร์ดแวร์ของคอมพิวเตอร์ BSP ในเอกสารต้นฉบับของ Valiant สิ่งอำนวยความสะดวกนี้จะตรวจสอบเป็นระยะว่าถึงจุดสิ้นสุดของซูเปอร์สเต็ปปัจจุบันทั่วโลกหรือไม่ ระยะเวลาของการตรวจสอบนี้แสดงด้วย. ^{[ 1 ]}${\displaystyle L}$

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

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

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

จำนวนข้อความขาเข้าหรือขาออกสูงสุดสำหรับซูเปอร์สเต็ปจะถูกกำหนดโดยความสามารถของเครือข่ายการสื่อสารในการส่งข้อมูลจะถูกวัดโดยพารามิเตอร์ซึ่งถูกกำหนดให้ใช้เวลาสำหรับโปรเซสเซอร์ในการส่งข้อความขนาด 1 ${\displaystyle h}$${\displaystyle g}$${\displaystyle hg}$${\displaystyle h}$

ข้อความที่มีความยาว n ย่อมใช้เวลาส่งนานกว่าข้อความที่มีขนาด 1 อย่างเห็นได้ชัด อย่างไรก็ตาม โมเดล BSP ไม่ได้แยกความแตกต่างระหว่างข้อความที่มีความยาว n หรือข้อความที่มีขนาด 1 ในทั้งสองกรณี ค่าใช้จ่ายจะถูกเรียกว่าn ${\displaystyle m}$${\displaystyle m}$${\displaystyle m}$${\displaystyle mg}$

พารามิเตอร์นี้ขึ้นอยู่กับสิ่งต่อไปนี้: ${\displaystyle g}$

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

ในทางปฏิบัติ ค่านี้จะถูกกำหนดโดยวิธีการทดลองสำหรับคอมพิวเตอร์แบบขนานแต่ละเครื่อง โปรดทราบว่าค่านี้ไม่ใช่เวลาในการส่งคำเดียวที่ปรับให้เป็นมาตรฐาน แต่เป็นเวลาในการส่งคำเดียวภายใต้สภาวะการรับส่งข้อมูลอย่างต่อเนื่อง ${\displaystyle g}$${\displaystyle g}$

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

ต้นทุนของการซิงโครไนซ์ระบบกั้นนั้นได้รับผลกระทบจากหลายปัจจัย:

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

ต้นทุนของการซิงโครไนซ์อุปสรรคจะแสดงด้วยโปรดทราบว่าหากกลไกการซิงโครไนซ์ของคอมพิวเตอร์ BSP เป็นไปตามที่ Valiant แนะนำ^{[ 1 ]} ในทางปฏิบัติ ค่าของจะถูกกำหนดโดยประสบการณ์ ${\displaystyle l}$${\displaystyle l<L}$${\displaystyle l}$

ในคอมพิวเตอร์ขนาดใหญ่ อุปสรรคมีราคาแพง และยิ่งมีราคาแพงขึ้นเรื่อยๆ ในระดับที่ใหญ่ขึ้น มีเอกสารจำนวนมากเกี่ยวกับการกำจัดจุดซิงโครไนซ์ออกจากอัลกอริธึมที่มีอยู่แล้วในบริบทของการคำนวณ BSP และอื่นๆ ตัวอย่างเช่น อัลกอริธึมหลายตัวอนุญาตให้ตรวจจับจุดสิ้นสุดทั่วโลกของซูเปอร์สเต็ปได้ง่ายๆ โดยการเปรียบเทียบข้อมูลท้องถิ่นกับจำนวนข้อความที่ได้รับแล้ว ซึ่งจะทำให้ต้นทุนของการซิงโครไนซ์ทั่วโลกเมื่อเทียบกับความหน่วงแฝงขั้นต่ำที่จำเป็นของการสื่อสารเป็นศูนย์^{[ 8 ]}อย่างไรก็ตาม คาดว่าความหน่วงแฝงขั้นต่ำนี้จะเพิ่มขึ้นอีกสำหรับสถาปัตยกรรมซูเปอร์คอมพิวเตอร์และการเชื่อมต่อเครือข่ายในอนาคต โมเดล BSP พร้อมกับโมเดลอื่นๆ สำหรับการคำนวณแบบขนาน จำเป็นต้องปรับตัวเพื่อรับมือกับแนวโน้มนี้ Multi-BSP เป็นโซลูชันหนึ่งที่ใช้ BSP ^{[ 5 ]}

ต้นทุนของขั้นตอนพิเศษ (superstep) ถูกกำหนดโดยผลรวมของสามส่วน:

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

ดังนั้น ต้นทุนของการประมวลผลขั้นสูงหนึ่งขั้นสำหรับโปรเซสเซอร์คือ: ${\displaystyle p}$

${\displaystyle max_{i=1}^{p}(w_{i})+max_{i=1}^{p}(h_{i}g)+l}$ โดยที่คือต้นทุนสำหรับการคำนวณภายในกระบวนการและคือจำนวนข้อความที่ส่งหรือรับโดยกระบวนการโปรดทราบว่าในที่นี้ถือว่าโปรเซสเซอร์เป็นแบบเดียวกัน โดยทั่วไปแล้วมักจะเขียนนิพจน์ในรูปแบบที่และคือค่าสูงสุด ต้นทุนของอัลกอริทึม BSP ทั้งหมดคือผลรวมของต้นทุนของแต่ละซูเปอร์สเต็ป ${\displaystyle w_{i}}$${\displaystyle i}$${\displaystyle h_{i}}$${\displaystyle i}$${\displaystyle w+hg+l}$${\displaystyle w}$${\displaystyle h}$

${\displaystyle W+Hg+Sl=\sum _{s=1}^{S}w_{s}+g\sum _{s=1}^{S}h_{s}+Sl}$จำนวนซูเปอร์สเต็ปอยู่ ที่ไหน${\displaystyle S}$

${\displaystyle W}$โดยทั่วไป แล้ว , , และจะถูกจำลองเป็นฟังก์ชันที่แปรผันตามขนาดของปัญหา ลักษณะทั้งสามประการของอัลกอริทึม BSP นี้มักจะอธิบายในแง่ของ สัญ กรณ์เชิงอะซิมโทติกเช่น${\displaystyle H}$${\displaystyle S}$${\displaystyle H\in O(n/p)}$

ความสนใจใน BSP เพิ่มสูงขึ้น โดยGoogleนำมาใช้เป็นเทคโนโลยีหลักสำหรับการวิเคราะห์กราฟในระดับมหาศาลผ่าน Pregel และMapReduce นอกจากนี้ ด้วย Hadoopรุ่นต่อไปที่แยกโมเดล MapReduce ออกจากโครงสร้างพื้นฐาน Hadoop ส่วนที่เหลือ ปัจจุบันมีโครงการโอเพนซอร์สที่ใช้งานอยู่เพื่อเพิ่มการเขียนโปรแกรม BSP อย่างชัดเจน รวมถึงโมเดลการเขียนโปรแกรมแบบขนานประสิทธิภาพสูงอื่นๆ บน Hadoop ตัวอย่างเช่นApache HamaและApache Giraph ^{[ 9 ]}

BSP ได้รับการขยายโดยผู้เขียนหลายคนเพื่อแก้ไขข้อกังวลเกี่ยวกับความไม่เหมาะสมของ BSP ในการสร้างแบบจำลองสถาปัตยกรรมหรือกระบวนทัศน์การคำนวณเฉพาะ ตัวอย่างหนึ่งของเรื่องนี้คือแบบจำลอง BSP ที่สามารถแยกส่วนได้ แบบจำลองนี้ยังถูกนำไปใช้ในการสร้างภาษาโปรแกรมและอินเทอร์เฟซใหม่ ๆ จำนวนมาก เช่น Bulk Synchronous Parallel ML (BSML), BSPLib, Apache Hama [ ^{9 ] และ} Pregel ^{[ 10 ]}

ตัวอย่างการใช้งานที่โดดเด่นของมาตรฐาน BSPLib ได้แก่ ไลบรารี BSP ของมหาวิทยาลัย Paderborn ^{[ 11 ]}และ Oxford BSP Toolset โดย Jonathan Hill ^{[ 12 ]}การใช้งานที่ทันสมัย ​​ได้แก่ BSPonMPI ^{[ 13 ]} (ซึ่งจำลอง BSP บนMessage Passing Interface ) และ MulticoreBSP ^{[ 14 ] [ 15 ]} (การใช้งานใหม่ที่มุ่งเป้าไปที่สถาปัตยกรรมหน่วยความจำร่วมที่ทันสมัย) MulticoreBSP สำหรับ C โดดเด่นเป็นพิเศษในด้านความสามารถในการเริ่มต้นการทำงานของ BSP แบบซ้อนกัน ทำให้สามารถเขียนโปรแกรม Multi-BSP ได้อย่างชัดเจน

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

• DB Skillicorn, Jonathan Hill, WF McColl, คำถามและคำตอบเกี่ยวกับ BSP (1996)
• บีเอสพี เวิลด์ไวด์
• เอกสารที่เกี่ยวข้องกับ BSP
• (ภาษาฝรั่งเศส) การประมวลผลแบบขนานซิงโครนัสจำนวนมาก ( เว็บไซต์อย่างเป็นทางการ(ภาษาอังกฤษ) )
• อาปาเช่ ฮามา
• อะปาเช่ จิราฟ
• ห้องสมุด BSP มหาวิทยาลัยพาเดอร์บอร์น
• บีเอสพีออนเอ็มพีไอ
• มัลติคอร์บีเอสพี