อัลกอริทึมของโทมาซูโลเป็นอัลกอริทึมฮาร์ดแวร์สถาปัตยกรรมคอมพิวเตอร์สำหรับการจัดตารางคำสั่งแบบไดนามิกที่อนุญาตให้ดำเนินการนอกลำดับและช่วยให้ใช้หน่วยประมวลผลหลายหน่วยได้อย่างมีประสิทธิภาพมากขึ้น อัลกอริทึมนี้ได้รับการพัฒนาโดยโรเบิร์ต โทมาซูโลที่IBMในปี 1967 และถูกนำไปใช้ครั้งแรกในหน่วยประมวลผลจุดลอยตัวของIBM System/360 รุ่น 91 ^{[ 1 ]}

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

โรเบิร์ต โทมาซูโลได้รับรางวัล Eckert–Mauchlyในปี 1997 จากผลงานเกี่ยวกับอัลกอริทึม^{[ 2 ]}

ต่อไปนี้คือแนวคิดที่จำเป็นต่อการนำอัลกอริทึมของโทมาซูโลไปใช้:

Common Data Bus (CDB) เชื่อมต่อสถานีสำรองโดยตรงกับหน่วยการทำงาน ตามที่ Tomasulo กล่าวไว้ว่า "รักษาลำดับความสำคัญในขณะที่ส่งเสริมการทำงานพร้อมกัน" ^{[ 1 ] : 33} สิ่งนี้มีผลสำคัญสองประการ:

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

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

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

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

ในทางปฏิบัติ อาจมีข้อยกเว้นบางประการที่ไม่มีข้อมูลสถานะเพียงพอเกี่ยวกับข้อยกเว้นนั้น ในกรณีดังกล่าว โปรเซสเซอร์อาจสร้างข้อยกเว้นพิเศษที่เรียกว่าข้อยกเว้นที่ไม่แม่นยำข้อยกเว้นที่ไม่แม่นยำไม่สามารถเกิดขึ้นได้ใน การใช้งาน แบบเรียงลำดับเนื่องจากสถานะของโปรเซสเซอร์จะเปลี่ยนแปลงได้เฉพาะตามลำดับของโปรแกรมเท่านั้น (ดูClassic RISC pipeline § Exceptions )

โปรแกรมที่เกิดข้อผิดพลาดแบบระบุเจาะจงได้ (precise exception ) ซึ่งสามารถระบุคำสั่งเฉพาะที่ทำให้เกิดข้อผิดพลาดได้ จะสามารถเริ่มต้นใหม่หรือทำงานต่อจากจุดที่เกิดข้อผิดพลาดได้ อย่างไรก็ตาม โปรแกรมที่เกิดข้อผิดพลาดแบบไม่ระบุเจาะจง (impreciate exception) โดยทั่วไปจะไม่สามารถเริ่มต้นใหม่หรือทำงานต่อได้ เนื่องจากระบบไม่สามารถระบุคำสั่งเฉพาะที่ทำให้เกิดข้อผิดพลาดได้

สามขั้นตอนที่ระบุไว้ด้านล่างนี้ คือขั้นตอนที่คำสั่งแต่ละคำสั่งต้องผ่าน ตั้งแต่เวลาที่ออกคำสั่งจนถึงเวลาที่คำสั่งนั้นดำเนินการเสร็จสมบูรณ์

• RS - สถานะการจอง
• RegisterStat - สถานะการลงทะเบียน; ประกอบด้วยข้อมูลเกี่ยวกับทะเบียนต่างๆ
• regs[x] - ค่าของรีจิสเตอร์ x
• Mem[A] - ค่าของหน่วยความจำที่แอดเดรส A

• rd - หมายเลขลงทะเบียนปลายทาง
• rs, rt - หมายเลขรีจิสเตอร์แหล่งที่มา
• imm - เซ็นต์ขยายช่องทันที
• r - สถานีสำรองหรือบัฟเฟอร์ที่กำหนดคำสั่งนั้นให้

• Op - หมายถึงการดำเนินการที่กำลังกระทำกับตัวถูกดำเนินการ
• Qj, Qk - สถานีสำรองที่จะสร้างตัวดำเนินการต้นทางที่เกี่ยวข้อง (0 หมายถึงค่าอยู่ใน Vj, Vk)
• Vj, Vk - ค่าของตัวถูกดำเนินการต้นทาง
• A - ใช้สำหรับเก็บข้อมูลที่อยู่หน่วยความจำสำหรับการโหลดหรือจัดเก็บ
• สถานะ - ไม่ว่าง - แสดง 1 ถ้ามีของอยู่ แสดง 0 ถ้าไม่มีของ

• Qi - สถานีจองที่ต้องการบันทึกผลลัพธ์ลงในรีจิสเตอร์นี้ (หากว่างเปล่าหรือเป็น 0 หมายความว่าไม่มีค่าใด ๆ สำหรับรีจิสเตอร์นี้)

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

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

ถ้า( RegisterStat [ rs ] .Qi ≠ 0 ) { RS [ r ] .Qj ← RegisterStat [ rs ].Qi } มิฉะนั้น{ RS [ r ].Vj ← Regs [ rs ] ; RS [ r ] .Qj ← 0 ; } ถ้า( RegisterStat [ rt ] .Qi ≠ 0 ) { RS [ r ] .Qk ← RegisterStat [ rt ] .Qi ; } มิฉะนั้น{ RS [ r ] .Vk ← Regs [ rt ]; RS [ r ] .Qk ← 0 ; } RS [ r ] .Busy ← yes ; RegisterStat [ rd ] .Qi ← r ;

ถ้า( RegisterStat [ rs ] .Qi ≠ 0 ) { RS [ r ] .Qj ← RegisterStat [ rs ] .Qi ; } มิเช่นนั้น{ RS [ r ].Vj ← Regs [ rs ] ; RS [ r ] .Qj ← 0 ; } RS [ r ] .A ← imm ; RS [ r ] .Busy ← yes ;

RegisterStat [ rt ]. Qi ← r ;

ถ้า( RegisterStat [ rt ] .Qi ≠ 0 ) { RS [ r ] .Qk ← RegisterStat [ rt ] .Qi ; } มิเช่นนั้น{ RS [ r ].Vk ← Regs [ rt ] ; RS [ r ] .Qk ← 0 };

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

• หากตัวถูกดำเนินการอย่างน้อยหนึ่งตัวยังไม่พร้อมใช้งาน ให้รอจนกว่าตัวถูกดำเนินการจะพร้อมใช้งานใน CDB
• เมื่อตัวถูกดำเนินการทั้งหมดพร้อมใช้งานแล้ว: หากคำสั่งนั้นเป็นคำสั่งโหลดหรือจัดเก็บ
  • คำนวณแอดเดรสที่มีประสิทธิภาพเมื่อรีจิสเตอร์ฐานพร้อมใช้งาน และเก็บไว้ในบัฟเฟอร์โหลด/จัดเก็บ
    • ถ้าคำสั่งนั้นเป็นการโหลดข้อมูล ให้ดำเนินการทันทีที่หน่วยความจำว่าง
    • มิฉะนั้น หากคำสั่งนั้นเป็นคำสั่งจัดเก็บค่า ให้รอจนกว่าค่าจะถูกจัดเก็บเสร็จก่อนจึงค่อยส่งไปยังหน่วยความจำ
• มิฉะนั้น หากคำสั่งนั้นเป็นการ ดำเนินการ ของหน่วยคำนวณและตรรกะ (ALU) ให้ดำเนินการคำสั่งนั้นที่หน่วยการทำงานที่เกี่ยวข้อง

(RS[r].Qj = 0) และ (RS[r].Qk = 0) 

RS[r].A ← RS[r].Vj + RS[r].A; 

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

• หากคำสั่งนั้นเป็นการดำเนินการของ ALU
  • หากผลการตรวจพร้อมแล้ว ให้บันทึกผลลงใน CDB จากนั้นจึงบันทึกไปยังเครื่องบันทึกข้อมูลและสถานีจองใดๆ ที่รอผลการตรวจนี้อยู่
• หรือถ้าคำสั่งนั้นเป็นการจัดเก็บข้อมูล: ให้เขียนข้อมูลลงในหน่วยความจำในขั้นตอนนี้

∀ x ( if ( RegisterStat [ x ]. Qi = r ) { regs [ x ] ← result ; RegisterStat [ x ]. Qi = 0 }); ∀ x ( if ( RS [ x ]. Qj = r ) { RS [ x ]. Vj ← result ; RS [ x ]. Qj ← 0 ; }); ∀ x ( if ( RS [ x ]. Qk = r ) { RS [ x ]. Vk ← result ; RS [ x ]. Qk ← 0 ; }); RS [ r ]. Busy ← no ;

Mem [ RS [ r ]. A ] ← RS [ r ]. Vk ; RS [ r ]. Busy ← no ;

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

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

ด้วยการติดตามตัวดำเนินการสำหรับคำสั่งในสถานีสำรองและการเปลี่ยนชื่อรีจิสเตอร์ในฮาร์ดแวร์ อัลกอริทึมจะลดการอ่านหลังจากเขียน (RAW) และกำจัดอันตรายจากสถาปัตยกรรมคอมพิวเตอร์ เช่นการเขียนหลังจากเขียน (WAW) และการเขียนหลังจากอ่าน (WAR) ซึ่งจะช่วยปรับปรุงประสิทธิภาพโดยการลดเวลาที่สูญเปล่าซึ่งอาจต้องใช้ไปกับการหยุดชะงัก^{[ 1 ] : 33}

การปรับปรุงที่สำคัญอีกประการหนึ่งในอัลกอริทึมคือการออกแบบไม่ได้จำกัดอยู่เฉพาะโครงสร้างไปป์ไลน์ที่เฉพาะเจาะจง การปรับปรุงนี้ทำให้อัลกอริทึมสามารถนำไปใช้ได้อย่างกว้างขวางมากขึ้นโดย โปรเซสเซอร์ หลายรายการนอกจากนี้ อัลกอริทึมยังสามารถขยายได้ง่ายเพื่อเปิดใช้งานการคาดการณ์สาขา^{[ 3 ] : 182}

อัลกอริทึมของโทมาซูโลถูกนำไปใช้ในสถาปัตยกรรม System/360 Model 91 นอกเหนือจาก IBM แล้ว อัลกอริทึมนี้ไม่ได้ถูกนำมาใช้เป็นเวลาหลายปี อย่างไรก็ตาม การใช้งานกลับเพิ่มขึ้นอย่างมากในช่วงทศวรรษ 1990 ด้วยเหตุผล 3 ประการ:

1. เมื่อแคชกลายเป็นเรื่องธรรมดา ความสามารถของอัลกอริธึมในการรักษาการทำงานพร้อมกันในระหว่างช่วงเวลาการโหลดที่ไม่แน่นอนซึ่งเกิดจากการพลาดแคช จึงกลายเป็นสิ่งที่มีค่าในโปรเซสเซอร์
2. การจัดตารางเวลาแบบไดนามิกและการคาดการณ์การแยกสาขาจากอัลกอริทึมช่วยให้ประสิทธิภาพดีขึ้นเมื่อโปรเซสเซอร์ได้รับคำสั่งมากขึ้นเรื่อยๆ
3. การแพร่หลายของซอฟต์แวร์สำหรับตลาดมวลชนหมายความว่าโปรแกรมเมอร์จะไม่ต้องการคอมไพล์สำหรับโครงสร้างไปป์ไลน์เฉพาะ อัลกอริทึมสามารถทำงานได้กับสถาปัตยกรรมไปป์ไลน์ใดๆ ดังนั้นซอฟต์แวร์จึงต้องการการแก้ไขเฉพาะสถาปัตยกรรมเพียงเล็กน้อย^{[ 3 ] : 183}

โปรเซสเซอร์สมัยใหม่จำนวนมากใช้รูปแบบการจัดตารางเวลาแบบไดนามิกซึ่งเป็นรูปแบบต่างๆ ของอัลกอริทึมดั้งเดิมของ Tomasulo รวมถึงชิปIntel x86-64 ที่ได้รับความนิยม ^{[ 5 ] [ 6 ]}

• บัฟเฟอร์จัดลำดับใหม่ (ROB)
• การประมวลผลแบบขนานระดับคำสั่ง (ILP)

• Savard, John JG (2018) [2014]. "Pipelined and Out-of-Order Execution" . quadibloc . เก็บถาวรจากต้นฉบับเมื่อ 2018-07-03 . สืบค้นเมื่อ2018-07-16 .

• การจัดตารางเวลาแบบไดนามิก - อัลกอริทึมของโทมาซูโลที่Wayback Machine (เก็บถาวรเมื่อวันที่ 25 ธันวาคม 2017)
• การจำลองอัลกอริทึมของโทมาซูโลโดยใช้แอปเพล็ต Java ของ HASE