ในช่วงครึ่งศตวรรษที่ผ่านมา อุตสาหกรรมวงจรรวมได้พัฒนาอย่างรวดเร็วภายใต้การแนะนำของกฎของมัวร์ และประสิทธิภาพของอัลกอริทึมก็รักษาการปรับปรุงในวงกว้าง ในปี 2018 IBM Summit คอมพิวเตอร์ที่เร็วที่สุดในโลก เร็วกว่า ENIAC คอมพิวเตอร์อิเล็กทรอนิกส์เครื่องแรกของโลกในปี 1945 เกือบ 30 ล้านล้านเท่า

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

เอกสาร MIT ฉบับใหม่นี้สรุปว่าประสิทธิภาพของอัลกอริธึมได้พัฒนาขึ้นอย่างรวดเร็วในช่วง 80 ปีที่ผ่านมาอย่างไร

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

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

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

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

ทั้งหมดนี้เกี่ยวข้องกับประสิทธิภาพของอัลกอริทึม

เมื่อเร็ว ๆ นี้ นักวิทยาศาสตร์จากห้องปฏิบัติการวิทยาการคอมพิวเตอร์และปัญญาประดิษฐ์ (CSAIL) ของ MIT ถาม: ประสิทธิภาพของอัลกอริธึมจะดีขึ้นเร็วแค่ไหน?

ข้อมูลที่มีอยู่ส่วนใหญ่ในคำถามนี้เป็นเรื่องเล่า และส่วนใหญ่เป็นกรณีศึกษาสำหรับอัลกอริทึมเฉพาะ และผลการศึกษาเหล่านี้เป็นข้อมูลทั่วไป

เนื่องจากขาดข้อมูลการวิจัยเชิงประจักษ์ ทีมวิจัยจึงใช้ข้อมูลจากตำราเรียน 57 เล่มและเอกสารการวิจัยมากกว่า 1,110 ฉบับเพื่อติดตามประวัติการปรับปรุงประสิทธิภาพของอัลกอริทึมเป็นหลัก

เอกสารเหล่านี้บางฉบับแสดงให้เห็นโดยตรงว่าอัลกอริทึมใหม่มีประสิทธิภาพเพียงใดในข้อสรุป ในขณะที่บางฉบับต้องการให้ผู้เขียนสร้างใหม่โดยใช้ "pseudocode" (คำอธิบายอย่างง่ายของรายละเอียดพื้นฐานของอัลกอริทึม)

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

รูปที่ 1 การค้นพบและปรับปรุงอัลกอริทึม (a) จำนวนตระกูลอัลกอริทึมใหม่ที่ค้นพบต่อทศวรรษ (b) สัดส่วนของตระกูลอัลกอริทึมที่รู้จักเพิ่มขึ้นทุก ๆ ทศวรรษ (c) การจำแนกความซับซ้อนของเวลาเชิงซีมโทติคของตระกูลอัลกอริทึมเมื่อค้นพบครั้งแรก (d) ความน่าจะเป็นโดยเฉลี่ยต่อปีในการเปลี่ยนจากขั้นตอนวิธีที่ซับซ้อนครั้งหนึ่งไปเป็นความซับซ้อนของเวลาอื่น (สะท้อนถึงระดับเฉลี่ยของความซับซ้อนที่เพิ่มขึ้นของระบบขั้นตอนวิธี) ความซับซ้อนของเวลาของ ">n3" ใน (c) และ (d) หมายถึงมากกว่าระดับพหุนาม แต่น้อยกว่าระดับเอกซ์โปเนนเชียล

แผนกอัลกอริทึมที่เก่าแก่ที่สุดสามารถย้อนไปถึงปี 1940 แผนกอัลกอริทึมแต่ละแผนกมีอัลกอริทึมเฉลี่ย 8 แผนก และประสิทธิภาพจะค่อย ๆ ดีขึ้นตามลำดับเวลา เพื่อแบ่งปันการค้นพบนี้ ทีมงานได้สร้างหน้า "Algorithm Wiki" (Algorithm-Wiki.org)

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

รูปที่ 2 ประสิทธิภาพสัมพัทธ์ที่เพิ่มขึ้นของตระกูลอัลกอริทึม คำนวณโดยใช้การเปลี่ยนแปลงความซับซ้อนของเวลาเชิงเส้นกำกับ เส้นอ้างอิงคือประสิทธิภาพพื้นฐานของ SPECInt (a) การปรับปรุงในอดีตสำหรับอัลกอริทึมสี่ตระกูลเมื่อเปรียบเทียบกับอัลกอริทึมแรกในซีรีส์ (n = 1 ล้าน) (b) ความไวของการปรับปรุงอัลกอริทึมต่อขนาดอินพุต (n) ของอัลกอริทึมตระกูล "Nearest Neighbor Search" เพื่ออำนวยความสะดวกในการเปรียบเทียบผลการปรับปรุงของอัลกอริทึมเมื่อเวลาผ่านไป ในรูป (b) ระบบอัลกอริทึมและช่วงเวลาเริ่มต้นของเกณฑ์มาตรฐานฮาร์ดแวร์จะอยู่ในแนวเดียวกัน

ผลลัพธ์แสดงตัวแปรที่หลากหลาย แต่ยังเปิดเผยข้อมูลสำคัญเกี่ยวกับการเพิ่มประสิทธิภาพของอัลกอริธึมการเปลี่ยนแปลงในวิทยาการคอมพิวเตอร์ ตอนนี้:

1. สำหรับปัญหาการประมวลผลขนาดใหญ่ ประโยชน์ที่ได้รับจากการปรับปรุงประสิทธิภาพของระบบอัลกอริทึม 43% ไม่น้อยไปกว่าประโยชน์ที่ได้จากกฎของมัวร์

2. ใน 14% ของปัญหา ประโยชน์ของการปรับปรุงประสิทธิภาพของอัลกอริทึมมีมากกว่าประโยชน์ของการปรับปรุงประสิทธิภาพของฮาร์ดแวร์

3. สำหรับปัญหา Big Data ประโยชน์ของการปรับปรุงประสิทธิภาพของอัลกอริทึมนั้นมีมากเป็นพิเศษ ดังนั้น ในช่วงไม่กี่ปีที่ผ่านมา ผลกระทบนี้จึงชัดเจนมากขึ้นเมื่อเทียบกับกฎของมัวร์

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

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

รูปที่ 3 การกระจายความเร็วเฉลี่ยต่อปีของระบบอัลกอริทึม 110 ระบบตามการคำนวณความซับซ้อนของเวลาเชิงซีมโทติค โดยที่ขนาดของปัญหาคือ: (a) n = 1,000, (b) n = 1 ล้าน, (c) n = 1 พันล้าน บรรทัดการปรับปรุงประสิทธิภาพของฮาร์ดแวร์แสดงถึงอัตราการเติบโตเฉลี่ยต่อปีของประสิทธิภาพการวัดประสิทธิภาพ SPECInt ตั้งแต่ปี 1978 ถึง 2017

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

การแก้ปัญหาอยู่ที่การหาอัลกอริทึมของความซับซ้อนพหุนาม

คำอธิบายภาพ

รูปที่ 4 การประเมินความสำคัญของค่าคงที่นำในการปรับปรุงประสิทธิภาพของอัลกอริทึม

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

Neil Thompson ผู้เขียนที่เกี่ยวข้องกล่าวว่า:

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

เมื่อปัญหาขยายใหญ่ขึ้น เช่น จุดข้อมูลหลายพันล้านหรือล้านล้านจุด ประสิทธิภาพของอัลกอริทึมที่เพิ่มขึ้นมีมากกว่าประสิทธิภาพฮาร์ดแวร์ที่เพิ่มขึ้น และมากกว่านั้นอีกมาก

ลิงค์อ้างอิง:

ลิงค์อ้างอิง:

https://news.mit.edu/2021/how-quickly-do-algorithms-improve-0920

https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9540991

บรรณาธิการ: ซู, Interstellar Vision