การคำนวณย้อนกลับ (Reverse computation)คือ การประยุกต์ใช้ ซอฟต์แวร์กับแนวคิดของการคำนวณแบบย้อนกลับได้ (Reversible computing )

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

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

จากการประยุกต์ใช้แนวคิดการคำนวณย้อนกลับที่ประสบความสำเร็จในโดเมนซอฟต์แวร์อื่นๆ Chris Carothers, Kalyan Perumalla และRichard Fujimoto ^{[ 9 ]}เสนอแนะการประยุกต์ใช้การคำนวณย้อนกลับเพื่อลดค่าใช้จ่ายในการบันทึกสถานะในการจำลองเหตุการณ์แบบแยกส่วนขนาน (PDES) พวกเขากำหนดแนวทางโดยอิงจากรหัสเหตุการณ์ย้อนกลับ (ซึ่งสามารถสร้างขึ้นโดยอัตโนมัติ) และแสดงให้เห็นถึงข้อได้เปรียบด้านประสิทธิภาพของแนวทางนี้เหนือการบันทึกสถานะแบบดั้งเดิมสำหรับแอปพลิเคชันแบบละเอียด (แอปพลิเคชันที่มีการคำนวณจำนวนน้อยต่อเหตุการณ์) คุณสมบัติสำคัญที่การคำนวณย้อนกลับใช้ประโยชน์คือ การดำเนินการส่วนใหญ่ที่แก้ไขตัวแปรสถานะมีลักษณะ "เชิงสร้างสรรค์" กล่าวคือ การดำเนินการ ยกเลิกสำหรับการดำเนินการดังกล่าวไม่จำเป็นต้องมีประวัติ เพียงแต่ต้องใช้ค่าปัจจุบันที่สุดของตัวแปรในการยกเลิกการดำเนินการ ตัวอย่างเช่น ตัวดำเนินการเช่น ++, ––, +=, -=, *= และ /= จัดอยู่ในประเภทนี้ โปรดทราบว่าตัวดำเนินการ *= และ /= จำเป็นต้องได้รับการจัดการเป็นพิเศษในกรณีของการคูณหรือหารด้วยศูนย์ และเงื่อนไขการล้น/การอันเดอร์โฟลว์ การดำเนินการที่ซับซ้อนกว่า เช่นการเลื่อนแบบวงกลม (การสลับเป็นกรณีพิเศษ) และการสร้างเลขสุ่ม บางประเภท ก็จัดอยู่ในหมวดนี้เช่นกัน

การดำเนินการในรูปแบบ a = b, โมดูลัสและ การคำนวณ แบบบิตไวส์ที่ส่งผลให้ข้อมูลสูญหาย เรียกว่า การดำเนินการทำลายล้าง โดยทั่วไป การดำเนินการเหล่านี้สามารถกู้คืนได้โดยใช้เทคนิคการรักษาสถานะแบบดั้งเดิมเท่านั้น อย่างไรก็ตาม เราสังเกตว่าการดำเนินการทำลายล้างเหล่านี้จำนวนมากเป็นผลมาจากการมาถึงของข้อมูลที่อยู่ในเหตุการณ์ที่กำลังประมวลผล ตัวอย่างเช่น ในงานของ Yaun, Carothers และคณะ กับการจำลองTCP ขนาดใหญ่ ^{[ 10 ]}เวลาที่ส่งครั้งสุดท้ายจะบันทึกการประทับเวลาของแพ็กเก็ตสุดท้ายที่ส่งต่อบนกระบวนการตรรกะของเราเตอร์ การดำเนินการสลับทำให้การดำเนินการนี้สามารถย้อนกลับได้

ในปี พ.ศ. 2528 เจฟเฟอร์สันได้แนะนำโปรโตคอลการซิงโครไนซ์แบบมองโลกในแง่ดี ซึ่งถูกนำมาใช้ในการจำลองเหตุการณ์แบบแยกส่วนขนานที่เรียกว่า Time Warp ^{[ 11 ]} จนถึงปัจจุบัน เทคนิคที่เรียกว่าReverse Computationได้ถูกนำไปใช้ในซอฟต์แวร์สำหรับการจำลองเหตุการณ์แบบแยกส่วนขนานที่ซิงโครไนซ์แบบมองโลกในแง่ดีเท่านั้น

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

ในปี 1998 Carothers และ Perumalla ได้ตีพิมพ์บทความสำหรับการประชุมเชิงปฏิบัติการ Principles of Advanced and Distributed Simulation ^{[ 13 ]}ซึ่งเป็นส่วนหนึ่งของการศึกษาระดับบัณฑิตศึกษาภายใต้ Richard Fujimoto โดยแนะนำเทคนิคการคำนวณย้อนกลับ (Reverse Computation) เป็นกลไกการย้อนกลับทางเลือกในการจำลองเหตุการณ์แบบแยกส่วนขนานที่ซิงโครไนซ์แบบมองโลกในแง่ดี (Time Warp) ในปี 1998 Carothers ได้เป็นรองศาสตราจารย์ที่Rensselaer Polytechnic Instituteโดยทำงานร่วมกับนักศึกษาระดับบัณฑิตศึกษา David Bauer และ Shawn Pearce Carothers ได้บูรณาการการออกแบบ Time Warp ของ Georgia Tech เข้ากับระบบการจำลองแบบมองโลกในแง่ดี (ROSS) ของ Rensselaer ซึ่งรองรับเฉพาะการคำนวณย้อนกลับเป็นกลไกการย้อนกลับเท่านั้น Carothers ยังได้สร้างแบบจำลอง RC สำหรับBitTorrentที่ General Electric รวมถึงโปรโตคอลเครือข่ายจำนวนมากร่วมกับนักศึกษา ( BGP4 , TCP Tahoe, Multicast ) Carothers ได้สร้างหลักสูตรเกี่ยวกับการจำลองแบบขนานและแบบกระจาย ซึ่งนักศึกษาจะต้องสร้างแบบจำลอง RC ใน ROSS

ในช่วงเวลาเดียวกันนั้น Perumalla สำเร็จการศึกษาจากGeorgia Techและไปทำงานที่Oak Ridge National Laboratory (ORNL) ที่นั่นเขาได้สร้างโปรแกรมจำลอง uSik ซึ่งเป็นโปรโตคอล PDES แบบผสมผสานระหว่างมองโลกในแง่ดีและมองโลกในแง่ร้าย ระบบนี้สามารถกำหนดโปรโตคอลที่ดีที่สุดสำหรับ LP ได้อย่างไดนามิก และทำการแมปใหม่ระหว่างการทำงานเพื่อตอบสนองต่อพลวัตของแบบจำลอง ในปี 2550 Perumalla ได้ทดสอบ uSik บนBlue Gene/Lและพบว่า ในขณะที่ความสามารถในการขยายขนาดถูกจำกัดไว้ที่โปรเซสเซอร์ 8,000 ตัวสำหรับการใช้งาน Time Warp อย่างเดียว การใช้งานแบบมองโลกในแง่ร้ายสามารถขยายขนาดได้ถึงโปรเซสเซอร์ 16,000 ตัวที่มีอยู่ โปรดทราบว่าการวัดประสิทธิภาพดำเนินการโดยใช้ PHOLD โดยมีอัตราเหตุการณ์ระยะไกลที่จำกัดไว้ที่ 10% โดยที่เวลาของเหตุการณ์ถูกกำหนดโดยการแจกแจงแบบเอกซ์โพเนนเชียลที่มีค่าเฉลี่ย 1.0 และมีการเพิ่มการมองล่วงหน้าอีก 1.0 ให้กับแต่ละเหตุการณ์ นี่เป็นการใช้งาน PDES ครั้งแรกบน Blue Gene โดยใช้การคำนวณย้อนกลับ

ตั้งแต่ปี 1998 ถึง 2005 Bauer ทำงานระดับบัณฑิตศึกษาที่ RPI ภายใต้การดูแลของ Carothers โดยมุ่งเน้นเฉพาะการคำนวณย้อนกลับ เขาได้พัฒนาระบบ PDES ระบบแรกที่ใช้การคำนวณย้อนกลับเพียงอย่างเดียว เรียกว่า Rensselaer's Optimistic Simulation System (ROSS) ^{[ 14 ]}สำหรับ ระบบหน่วยความจำ ร่วมและแบบกระจายที่ รวมกัน ตั้งแต่ปี 2006 ถึง 2009 Bauer ทำงานภายใต้ EH Page ที่Mitre Corporationและร่วมมือกับ Carothers และ Pearce ผลักดันโปรแกรมจำลอง ROSS ไปยังBlue Gene/P (Intrepid) ที่มีโปรเซสเซอร์ 131,072 ตัว การใช้งานนี้มีความเสถียรสำหรับอัตราเหตุการณ์ระยะไกล 100% (ทุกเหตุการณ์ถูกส่งผ่านเครือข่าย) ในช่วงเวลาที่เขาอยู่ที่ RPI และ MITRE Bauer ได้พัฒนา ระบบ จำลองเครือข่าย ROSS.Net ^{[ 15 ]}ซึ่งสนับสนุนการออกแบบการทดลองแบบกึ่งอัตโนมัติสำหรับการเพิ่มประสิทธิภาพแบบกล่องดำของแบบจำลองโปรโตคอลเครือข่ายที่ทำงานใน ROSS เป้าหมายหลักของระบบคือการเพิ่มประสิทธิภาพแบบจำลองโปรโตคอลเครือข่ายหลายแบบสำหรับการทำงานบน ROSS ตัวอย่างเช่น การสร้างโครงสร้างเลเยอร์ LP เพื่อกำจัดเหตุการณ์ที่ส่งผ่านระหว่าง LP ของโปรโตคอลเครือข่ายบนเครื่องจำลองเดียวกัน จะช่วยเพิ่มประสิทธิภาพการจำลองโหนดเครือข่าย TCP/IP โดยการกำจัดการประทับเวลาแบบออฟเซ็ตศูนย์ระหว่างโปรโตคอล TCP และ IP นอกจากนี้ Bauer ยังสร้างแบบจำลอง RC ที่ใช้เอเจนต์สำหรับเครือข่ายการติดต่อทางสังคมเพื่อศึกษาผลกระทบของโรคติดเชื้อโดยเฉพาะไข้หวัดใหญ่ระบาด ซึ่งมีขนาดใหญ่ถึงหลายร้อยล้านเอเจนต์ รวมถึงแบบจำลอง RC สำหรับเครือข่าย ad-hoc เคลื่อนที่ที่ใช้ฟังก์ชันการเคลื่อนที่ (การตรวจจับระยะใกล้) และการแพร่กระจายคลื่นแม่เหล็กไฟฟ้า ของเลเยอร์ทางกายภาพที่มีความแม่นยำสูง (แบบจำลองเมทริกซ์สายส่ง) ^{[ 16 ]}

นอกจากนี้ ชุมชน PDES ยังได้ผลักดันเข้าสู่ขอบเขตของการจำลองแบบต่อเนื่องเมื่อไม่นานมานี้ ตัวอย่างเช่น Fujimoto และ Perumalla ซึ่งทำงานร่วมกับ Tang et al. ^{[ 17 ]}ได้นำแบบจำลอง RC ของอนุภาคในเซลล์มาใช้ และแสดงให้เห็นถึงความเร็วที่ยอดเยี่ยมเหนือการจำลองแบบต่อเนื่องสำหรับแบบจำลองของแสงในฐานะอนุภาค Bauer และ Page ได้แสดงให้เห็นถึงความเร็วที่ยอดเยี่ยมสำหรับแบบจำลอง RC Transmission Line Matrix (PB Johns, 1971) ซึ่งจำลองแสงเป็นคลื่นที่ความถี่ไมโครเวฟ Bauer ยังได้สร้างตัวแปร RC ของSEIRซึ่งสร้างการปรับปรุงอย่างมากเหนือแบบจำลองแบบต่อเนื่องในด้านการแพร่กระจายของโรคติดเชื้อ ยิ่งไปกว่านั้น แบบจำลอง RC SEIR ยังสามารถจำลองโรคหลายโรคได้อย่างมีประสิทธิภาพ ในขณะที่แบบจำลองแบบต่อเนื่องจะเพิ่มขึ้นแบบทวีคูณเมื่อเทียบกับจำนวนชุดของโรคที่เป็นไปได้ทั่วทั้งประชากร

• RC '05 – การประชุมเชิงปฏิบัติการนานาชาติครั้งที่ 1 ว่าด้วยการคำนวณแบบย้อนกลับได้
• การประชุมเชิงปฏิบัติการ/ชุดการประชุมเกี่ยวกับการคำนวณแบบย้อนกลับได้