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

โครงสร้างควบคุมการเขียนโปรแกรมที่การทำขนานอัตโนมัติให้ความสำคัญมากที่สุดคือลูปเนื่องจากโดยทั่วไปแล้วเวลาการทำงาน ส่วนใหญ่ ของโปรแกรมจะเกิดขึ้นภายในลูปรูปแบบใดรูปแบบหนึ่ง มีแนวทางหลักสองประการในการทำขนานลูป ได้แก่ มัลติเธรดแบบไปป์ไลน์และมัลติเธรดแบบวนรอบ^{[ 3 ]}ตัวอย่างเช่น ลองพิจารณาลูปที่ในแต่ละรอบการทำงานจะดำเนินการ 100 ครั้ง และทำงานเป็นเวลา 1,000 รอบ สามารถคิดได้ว่าเป็นตารางขนาด 100 คอลัมน์คูณ 1,000 แถว รวมทั้งหมด 100,000 การดำเนินการ มัลติเธรดแบบวนรอบจะกำหนดแต่ละแถวให้กับเธรดที่แตกต่างกัน มัลติเธรดแบบไปป์ไลน์จะกำหนดแต่ละคอลัมน์ให้กับเธรดที่แตกต่างกัน

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

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

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

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

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

โดยปกติแล้ว คอมไพเลอร์จะทำการวิเคราะห์สองรอบก่อนที่จะทำการประมวลผลแบบขนานจริง เพื่อตรวจสอบสิ่งต่อไปนี้:

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

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

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

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

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

do i = 1 , n z ( i ) = x ( i ) + y ( i ) enddo

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

ในทางกลับกัน โค้ดต่อไปนี้ไม่สามารถประมวลผลแบบขนานอัตโนมัติได้ เนื่องจากค่าของz(i)ขึ้นอยู่กับผลลัพธ์ของการวนซ้ำครั้งก่อนz(i - 1)หน้า

do i = 2 , n z ( i ) = z ( i - 1 ) * 2 enddo

นี่ไม่ได้หมายความว่าโค้ดไม่สามารถประมวลผลแบบขนานได้ อันที่จริง มันเทียบเท่ากับลูป DOALL

do i = 2 , n z ( i ) = z ( 1 ) * 2 ** ( i - 1 ) enddo

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

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

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

ตัวอย่างเช่น ในการผลิตรายการโทรทัศน์ถ่ายทอดสด จะต้องดำเนินการต่างๆ ต่อไปนี้หลายครั้งต่อวินาที:

1. อ่านข้อมูลพิกเซลดิบจากเซ็นเซอร์ภาพ
2. ทำการชดเชยการเคลื่อนไหว ของ MPEG บนข้อมูลดิบ
3. เอนโทรปีจะบีบอัดเวกเตอร์การเคลื่อนที่และข้อมูลอื่นๆ
4. แบ่งข้อมูลที่ถูกบีบอัดออกเป็นแพ็กเก็ต
5. เพิ่มการแก้ไขข้อผิดพลาดที่เหมาะสมและทำการแปลง FFT เพื่อแปลงแพ็กเก็ตข้อมูลเป็น สัญญาณ COFDMและ
6. ส่งสัญญาณ COFDM ออกทางเสาอากาศทีวี

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

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

การทำให้ขนานกันโดยอัตโนมัติโดยคอมไพเลอร์หรือเครื่องมือเป็นเรื่องยากมากเนื่องจากเหตุผลดังต่อไปนี้: ^{[ 6 ]}

• การวิเคราะห์ความสัมพันธ์ระหว่างส่วนต่างๆ ทำได้ยากสำหรับโค้ดที่ใช้การอ้างอิงทางอ้อม ตัวชี้ การเรียกซ้ำ หรือการเรียกฟังก์ชันทางอ้อม เนื่องจากเป็นการยากที่จะตรวจจับความสัมพันธ์ดังกล่าวในระหว่างการคอมไพล์
• ลูปมีจำนวนรอบที่ไม่แน่นอน
• การเข้าถึงทรัพยากรทั่วโลกนั้นยากที่จะประสานงานในแง่ของการจัดสรรหน่วยความจำ การรับส่งข้อมูล และตัวแปรที่ใช้ร่วมกัน
• อัลกอริทึมที่ไม่สม่ำเสมอซึ่งใช้การอ้างอิงทางอ้อมที่ขึ้นอยู่กับอินพุตจะรบกวนการวิเคราะห์และการเพิ่มประสิทธิภาพในเวลาคอมไพล์^{[ 7 ]}

เนื่องจากความยากลำบากโดยธรรมชาติในการสร้างโปรแกรมแบบขนานอัตโนมัติอย่างสมบูรณ์ จึงมีวิธีการที่ง่ายกว่าหลายวิธีในการสร้างโปรแกรมแบบขนานที่มีคุณภาพสูงขึ้น วิธีหนึ่งคือการอนุญาตให้โปรแกรมเมอร์เพิ่ม "คำแนะนำ" ลงในโปรแกรมเพื่อชี้นำการสร้างโปรแกรมแบบขนานโดยคอมไพเลอร์ เช่นHPFสำหรับ ระบบ หน่วยความจำแบบกระจายและOpenMPหรือOpenHMPPสำหรับ ระบบ หน่วยความจำแบบใช้ร่วมกันอีกวิธีหนึ่งคือการสร้างระบบแบบโต้ตอบระหว่างโปรแกรมเมอร์และเครื่องมือ/คอมไพเลอร์สำหรับการสร้างโปรแกรมแบบขนาน ตัวอย่างที่โดดเด่น ได้แก่Pareon ของVector Fabrics , SUIF Explorer (คอมไพเลอร์รูปแบบ Intermediate ของมหาวิทยาลัยสแตนฟอร์ด), คอมไพเลอร์ Polaris และ ParaWise (เดิมชื่อ CAPTools) สุดท้ายนี้ อีกวิธีหนึ่งคือการ สร้าง มัลติเธรดแบบคาดการณ์ล่วงหน้าโดยใช้ฮาร์ดแวร์สนับสนุน

คอมไพเลอร์ สำหรับ การวิจัยส่วนใหญ่ ที่ใช้ สำหรับการประมวลผลแบบขนานอัตโนมัติจะพิจารณา โปรแกรม Fortranเนื่องจาก Fortran ให้การรับประกันเกี่ยวกับการกำหนดชื่อแทนที่ แข็งแกร่ง กว่าภาษาต่างๆ เช่นCตัวอย่างทั่วไปได้แก่:

• คอมไพเลอร์พาราไดม์
• คอมไพเลอร์โพลาริส
• คอมไพเลอร์ Rice Fortran D
• คอมไพเลอร์SUIF
• คอมไพเลอร์เวียนนาฟอร์ทราน

Aubert, Rubiano, Rusch และSeiller ^{[ 8 ]}ใช้เทคนิคการวิเคราะห์การพึ่งพา^{[ 9 ]}เพื่อทำให้ลูปในโปรแกรม C ทำงานแบบขนานโดยอัตโนมัติ

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

• Pountain, Dick (ธันวาคม 1989). "การกำหนดค่าโปรแกรมแบบขนาน ตอนที่ 1: Occam Transpiler ซึ่งอยู่ระหว่างการพัฒนา จะทำให้การเขียนซอฟต์แวร์สำหรับการประมวลผลแบบขนานง่ายขึ้น" . BYTE . เล่มที่ 14, ฉบับที่ 13. McGraw -Hill, Inc.หน้า  349–352 . ISSN  0360-5280 . ark:/13960/t34188734 . สืบค้นเมื่อ6 มกราคม 2022 .(หมายเหตุ: ใช้คำว่าOccam transpilerเป็นคำพ้องความหมายสำหรับคอมไพเลอร์แบบ source-to-sourceที่ทำงานเป็นตัวประมวลผลล่วงหน้า โดยรับโปรแกรม Occamปกติเป็นอินพุต และสร้างซอร์สโค้ด Occam ใหม่เป็นเอาต์พุต พร้อมการกำหนดลิงก์ไปยังช่องสัญญาณ ฯลฯ เพิ่มเข้าไป เพื่อกำหนดค่าสำหรับการประมวลผลแบบขนานให้ทำงานได้อย่างมีประสิทธิภาพสูงสุดบนเครือข่ายของทรานส์พิวเตอร์ )