หน่วยความจำที่ใช้ร่วมกันและความสอดคล้อง

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

Definition

แบบจำลองความสอดคล้องของหน่วยความจำคือข้อกำหนดของลำดับที่อนุญาตของการอ่านและเขียนหน่วยความจำข้ามโปรเซสเซอร์ในระบบหน่วยความจำที่ใช้ร่วมกัน ซึ่งกำหนดว่าค่าใดที่การโหลด (load) อาจส่งคืน และด้วยเหตุนี้จึงเป็นสัญญา (contract) ระหว่างฮาร์ดแวร์และซอฟต์แวร์แบบพร้อมกัน (concurrent software)

Scope

หัวข้อนี้ครอบคลุมการประมวลผลแบบหลายโปรเซสเซอร์ที่ใช้หน่วยความจำร่วมกัน และโดยเฉพาะอย่างยิ่ง แบบจำลองความสอดคล้องของหน่วยความจำ: ความสอดคล้องเชิงลำดับ, แบบจำลองแบบผ่อนคลายและแบบอ่อน, แผงกั้นหน่วยความจำ (memory fences), และความสัมพันธ์ระหว่างความสอดคล้อง (consistency) และความสอดคล้องกัน (coherence) นอกจากนี้ยังครอบคลุมถึงกลไกพื้นฐานสำหรับการซิงโครไนซ์ (synchronization primitives) ที่อาศัยแบบจำลองความสอดคล้อง หัวข้อนี้ไม่รวมกลไกความสอดคล้องกันต่อตำแหน่ง (โปรโตคอลความสอดคล้องของแคช) และการรวมคอร์ระดับชิป (มัลติคอร์และชิปมัลติโปรเซสเซอร์)

Core questions

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

Key concepts

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

Key theories

ความสอดคล้องเชิงลำดับ

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

Mechanisms

ฮาร์ดแวร์จะจัดเรียงและบัฟเฟอร์การดำเนินการหน่วยความจำใหม่เพื่อประสิทธิภาพ ดังนั้นแบบจำลองความสอดคล้องจึงระบุว่าการจัดเรียงใหม่ใดที่โปรเซสเซอร์อื่น ๆ สามารถมองเห็นได้ ความสอดคล้องเชิงลำดับ (sequential consistency) ห้ามการจัดเรียงใหม่ที่มองเห็นได้ข้ามโปรเซสเซอร์; แบบจำลองแบบผ่อนคลาย (relaxed models) อนุญาตให้มีการจัดเรียงใหม่บางอย่างเพื่อความเร็ว และกำหนดให้นักเขียนโปรแกรมต้องแทรกแผงกั้นหน่วยความจำ (memory fences) เพื่อบังคับใช้ลำดับเมื่อจำเป็น กลไกพื้นฐานสำหรับการซิงโครไนซ์ เช่น ล็อก (locks) และการดำเนินการแบบอะตอมมิก (atomic operations) สร้างขึ้นบนการรับประกันเหล่านี้ และโปรแกรมที่หลีกเลี่ยงสภาวะการแข่งขันของข้อมูล (data races) จะทำงานได้อย่างคาดการณ์ได้

Clinical relevance

แบบจำลองความสอดคล้องของหน่วยความจำเป็นรากฐานของการเขียนโปรแกรมแบบพร้อมกันที่ถูกต้อง: มันกำหนดว่าโปรแกรมแบบมัลติเธรด (multithreaded program) อาจสมมติอะไรได้อย่างถูกต้องเกี่ยวกับการมองเห็นและลำดับของการอัปเดตที่ใช้ร่วมกัน การเข้าใจผิดอาจทำให้เกิดข้อผิดพลาดที่ละเอียดอ่อนและยากต่อการทำซ้ำ และแบบจำลองหน่วยความจำของภาษา (เช่นใน C++ และ Java) สร้างขึ้นโดยตรงจากแนวคิดฮาร์ดแวร์เหล่านี้

History

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

Debates

ความสอดคล้องแบบเข้มงวดเทียบกับแบบผ่อนคลาย

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

Key figures

• Leslie Lamport
• Sarita Adve
• Mark D. Hill
• David E. Culler

Seminal works

• hennessy2019
• culler1999

Frequently asked questions

ความแตกต่างระหว่างความสอดคล้องกัน (coherence) และความสอดคล้อง (consistency) คืออะไร?

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

เหตุใดโปรเซสเซอร์จึงใช้แบบจำลองหน่วยความจำแบบผ่อนคลาย?

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