อัลกอริทึมแบบขนาน - บทนำ

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

การประมวลผลพร้อมกัน

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

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

Parallelism คืออะไร?

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

ในบทช่วยสอนนี้เราจะพูดถึงเฉพาะ parallel algorithms. ก่อนที่จะดำเนินการต่อไปให้เราพูดคุยเกี่ยวกับอัลกอริทึมและประเภทของอัลกอริทึมก่อน

อัลกอริทึมคืออะไร?

อัน algorithmเป็นลำดับของคำแนะนำตามเพื่อแก้ปัญหา ในขณะที่ออกแบบอัลกอริทึมเราควรพิจารณาสถาปัตยกรรมของคอมพิวเตอร์ที่จะใช้อัลกอริทึม ตามสถาปัตยกรรมมีคอมพิวเตอร์สองประเภท -

• คอมพิวเตอร์ตามลำดับ
• คอมพิวเตอร์แบบขนาน

ขึ้นอยู่กับสถาปัตยกรรมของคอมพิวเตอร์เรามีอัลกอริทึมสองประเภท -

• Sequential Algorithm - อัลกอริทึมที่มีการดำเนินการขั้นตอนต่อเนื่องของคำสั่งตามลำดับเวลาเพื่อแก้ปัญหา

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

ไม่ใช่เรื่องง่ายที่จะแบ่งปัญหาใหญ่ออกเป็น sub-problems. ปัญหาย่อยอาจมีการพึ่งพาข้อมูลระหว่างกัน ดังนั้นหน่วยประมวลผลจึงต้องสื่อสารกันเพื่อแก้ปัญหา

พบว่าเวลาที่หน่วยประมวลผลต้องการในการสื่อสารระหว่างกันมากกว่าเวลาประมวลผลจริง ดังนั้นในขณะที่ออกแบบอัลกอริทึมแบบขนานควรพิจารณาการใช้งาน CPU ที่เหมาะสมเพื่อให้ได้อัลกอริทึมที่มีประสิทธิภาพ

ในการออกแบบอัลกอริทึมให้ถูกต้องเราต้องมีแนวคิดพื้นฐานที่ชัดเจน model of computation ในคอมพิวเตอร์แบบขนาน

แบบจำลองการคำนวณ

คอมพิวเตอร์ทั้งแบบเรียงลำดับและแบบขนานทำงานบนชุดคำสั่ง (สตรีม) ที่เรียกว่าอัลกอริทึม ชุดคำสั่ง (อัลกอริทึม) เหล่านี้จะสั่งคอมพิวเตอร์เกี่ยวกับสิ่งที่ต้องทำในแต่ละขั้นตอน

คอมพิวเตอร์สามารถแบ่งออกเป็นสี่ประเภททั้งนี้ขึ้นอยู่กับสตรีมคำสั่งและสตรีมข้อมูล

• สตรีมคำสั่งเดียวคอมพิวเตอร์สตรีมข้อมูลเดียว (SISD)
• สตรีมคำสั่งเดียวคอมพิวเตอร์หลายสตรีมข้อมูล (SIMD)
• สตรีมคำสั่งหลายเครื่องคอมพิวเตอร์สตรีมข้อมูลเดียว (MISD)
• สตรีมคำสั่งหลายเครื่องคอมพิวเตอร์หลายสตรีมข้อมูล (MIMD)

คอมพิวเตอร์ SISD

คอมพิวเตอร์ SISD ประกอบด้วย one control unit, one processing unit, และ one memory unit.

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

คอมพิวเตอร์ SIMD

คอมพิวเตอร์ SIMD ประกอบด้วย one control unit, multiple processing units, และ shared memory or interconnection network.

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

หน่วยประมวลผลแต่ละหน่วยมีหน่วยความจำภายในของตัวเองเพื่อเก็บทั้งข้อมูลและคำสั่ง ในคอมพิวเตอร์ SIMD โปรเซสเซอร์จำเป็นต้องสื่อสารกันเอง สิ่งนี้ทำได้โดยshared memory หรือโดย interconnection network.

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

คอมพิวเตอร์ MISD

ตามชื่อที่แนะนำคอมพิวเตอร์ MISD ประกอบด้วย multiple control units, multiple processing units, และ one common memory unit.

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

คอมพิวเตอร์ MIMD

คอมพิวเตอร์ MIMD มี multiple control units, multiple processing units, และก shared memory หรือ interconnection network.

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

บันทึก

• คอมพิวเตอร์ MIMD ที่แชร์หน่วยความจำทั่วไปเรียกว่า multiprocessors, ในขณะที่ผู้ที่ใช้เครือข่ายเชื่อมต่อจะเรียกว่า multicomputers.

• ตามระยะทางกายภาพของโปรเซสเซอร์มัลติคอมพิวเตอร์มีสองประเภท -

  • Multicomputer - เมื่อโปรเซสเซอร์ทั้งหมดอยู่ใกล้กันมาก (เช่นในห้องเดียวกัน)

  • Distributed system - เมื่อโปรเซสเซอร์ทั้งหมดอยู่ห่างไกลจากกัน (เช่น - ในเมืองต่างๆ)