Andreas Unger, Theo Ungerer, Eberhard Zehendner
This project surveys compiler techniques that utilize the specific ability of multithreaded processors to sequence through several closely coupled threads of control simultaneously. The project is pursued in cooperation with Andreas Unger and Prof. Dr. Eberhard Zehendner of the Friedrich-Schiller-University at Jena, Germany.
Our approach - called Simultaneous Speculation Scheduling (S3) - is a combined compiler and architecture technique to control multiple path execution. The S3 technique can be applied to dual path branch speculation in case of unpredictable branches and to multiple path speculative execution of loop iterations.
In our approach separate threads are generated by the compiler that harness thread-level speculation by speculating on the outcome of branches executing in parallel on a multithreaded microprocessor. Loop-carried memory dependences that cannot be disproven by the compiler are handled by data dependence speculation.
The architectural requirements are the ability to run two or more threads in parallel and and three new instructions (fork, sync, wait) to control threads. Our technique aims at simultaneous multithreaded, nanothreaded, and microthreaded processors, but can be modified for multiscalar, datascalar, and trace processors. Applying the S3 technique to branches in kernel sections of SPECint95 benchmark programs shows performance gains of up to 40% over purely static scheduling techniques.
List of Publications
Unger, T. Ungerer, E. Zehendner: A Combined Compiler and Architecture Technique to Control Multithreaded Execution of Branches and Loop Iterations. The 4th Annual Workshop on Interaction between Compilers and Computer Architecture (INTERACT-4), Toulouse, Jan. 9, 2000 (in postscript).
A. Unger, T. Ungerer, E. Zehendner: Simultaneous Speculation Scheduling.
11th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD'99),
Natal, Brazil, September 29 - October 2, 1999.
A. Unger, T. Ungerer, E. Zehendner: Simultaneous Speculation Scheduling – Dynamische Parallelisierung. GI/ITG-Workshop Mikroprozessoren zur Jahrtausendwende: Gestaltungsalternativen zukünftiger Prozessorarchitekturen. Workshop-Volume of the 15th GI/ITG-Fachtagung ARCS’99 Architektur von Rechensystemen 1999, Jena, October 7, 1999, 43-52 (in German, postscript).
A. Unger, T. Ungerer, E. Zehendner: Simultaneous Speculation Scheduling – A
Technique for
Speculative Dual-Path Execution. 15. GI/ITG-Fachtagung ARCS’99 Architektur von
Rechensystemen 1999, Jena, October 4-7, 1999, 75-82
(in postscript).
A. Unger, T. Ungerer, E. Zehendner: Utilising Parallel Resources by Speculation.
7th Euromicro Workshop on Parallel and Distributed Processing. Funchal, Portugal, February
10-12, 1999, pp. 339-343 (in postscript).
A. Unger, T. Ungerer, E. Zehendner: Compiler Supported Speculative Execution on SMT
Processors. Workshop on Multi-Threaded Execution, Architecture and Compilation
(MTEAC 99) in conjunction with Fifth International Symposium on High Performance
Computer Architecture (HPCA-5), Orlando, January 9-12, 1999.
A. Unger, T. Ungerer, E. Zehendner: Parallele Ausführung alternativer Programmpfade.
GI/ITG Workshop PARS, Karlsruhe, September 16-17, 1998, pp. 50-59 (in German, postscript).
A. Unger, T. Ungerer, E. Zehendner: Static Speculation, Dynamic Resolution.
Seventh International Workshop on Compilers for Parallel Computers,
Linköping, Sweden, June 29 - July 1, 1998, pp. 243 - 253 (in
postscript).
A. Unger, T. Ungerer, E. Zehendner: A Compiler Technique for Speculative
Execution of
Alternative Program Paths Targeting Multithreaded Architectures.
The Yale Multithreaded Programming Workshop, Yale University, New Haven,
Connecticut, June 8-9, 1998.
To Ungerer's homepage.
Theo Ungerer, April 2006