1. Field of the Invention
The present invention generally relates to microprocessor and multiprocessor architectures and, more particularly, to thread-level speculative processor execution for achieving high performance and speeding up sequential applications.
2. Description of the Prior Art
As increasing numbers of smaller and faster transistors can be integrated on a single chip, new processors are designed to use these transistors effectively to increase performance. The arising challenge is to find the most effective way to put these transistors in use. Currently, most computer designers opt to use increasing transistor budget to build even bigger and more complex uniprocessors. Another possibility is to place big amounts of memory on the chip. Alternatively, multiple processor cores can be placed on a single chip. The later approach is called chip multiprocessors (CMP).
Performance improvements using a single complex processor is achieved by exploiting ILP (instruction level parallelism), i.e. by finding non-dependent instructions in a program sequence which are then executed at the same time. However, the possible performance gain by exploiting IPL is limited due to finite amount of ILP present in any particular application sequence.
Placing multiple smaller processor cores on a single chip is attractive because single processor core is less complex to design and verify. This results in less costly and complex verification process as once verified module-processor—is repeated multiple times on a chip. Each processor core on a multiprocessor is much smaller than a competitive uniprocessor, minimizing the core design time. In addition, keeping design partitions small—like a single processor core in a CMP—design tools can handle processor complexity much easier, compared to competitive complex uniprocessors. However, many important existing applications are written for uniprocessors, and it is a non-trivial task to convert uniprocessor applications into multiprocessor ones. For this, sequential programs have to be explicitly broken into threads and synchronized properly. So far, parallelizing compilers have been only partly successful at automatically handling these tasks.
Speculative multithreaded processors present possible solution of these difficulties offering high potential performance improvement. A speculative multithreaded processor consists logically of replicated processor cores that cooperatively perform the parallel execution of a sequential program. The sequential program is divided into chunks called speculative threads, and these threads are executed on processor cores concurrently and speculatively. This approach for performance improvement by exploiting coarse-grain parallelism in addition or instead of fine-grain parallelism (e.g., ILP) is called thread level speculation (TLS). In thread level speculation approach, sequential programs are divided into speculative threads which are then executed concurrently on processor cores. Ideally, there are no data and/or control dependences between the threads, but being parts of the same sequential program, speculative threads are both data and control dependant. The data flow between speculative threads in one direction only—from sequentially older threads to younger ones. (Thus, data used in a younger speculative thread can be a result calculated in an older thread.) To ensure that each program executes the same way that it did on a uniprocessor, hardware must track all inherited dependences. When a younger thread in a sequence causes a true dependence violation, the hardware must ensure that the misspeculation is detected, and the misspeculated thread has to re-execute with the correct data.
To support speculation, multiprocessor architecture for thread level speculation has to fulfill the following requirements: 1) it has to maintain a notion of the relative order of the threads—i.e., know which thread is executed before some other thread in a sequential program; 2) it has to forward data between parallel threads, or predict data; 3) it has to support mechanism for dependency violation detection—to detect if read occurred too early; 4) it has to safely discard speculative thread once dependency violation is detected; 5) it has to commit speculative writes in proper order—only after making sure that this thread would have been executed the same in a sequential execution; and, 6) it has to re-execute the misspeculated threads with proper data.
A number of multiprocessor architectures with support for thread level speculation have been proposed. In several of these architectures, a program is chopped into threads by the compiler during the compilation time, such as in a multiscalar processor as proposed in the reference to G. S. Sohi, et al. entitled “Multiscalar Processors”, 27th International Symposium on Computer Architecture (ISCA-22), 1995, or as in a superthreaded architecture or trace processor. In other approaches, hardware dynamically forms the threads during the run time, such as proposed in the reference entitled “Dynamic Multithreaded Processor” by H. Akkary and M. Driscoll in Proc. Of the 31st Annual International Symposium on Microarchitecture (1998) and “Clustered Speculative Multithreaded Processor” proposed by P. Marcuello and A. Gonzales in Proc. Of the 13th Intl. Conference on Supercomputing, pp. 365-372 (1999). All of these architectures require significant changes on the processor core or/and on the L1 and/or L2 level caches to support thread level speculation. These changes include at least one of the following: 1) provision of means for registers forwarding between processors; 2) the addition of new fields in one or more caches to distinguish speculative vs. non-speculative values; 3) a modified processor interface to allow communication of speculative values; and 4) a change of speculation status for the processor. Requiring significant changes to the processor core and/or to the memory nest to enable thread level speculation, existing architectures can not take advantage of increased performance which TLS offers. To support thread level speculation on the existing processor, the processor core needs massive re-design and complete re-verification process. Similarly for the memory nest, re-design and verification effort makes it prohibitive, or at least very expensive, for already existing cores and system.
It would be highly desirable to provide a system and method which would enable thread level speculative execution on existing processors and memory systems without requiring costly changes to the processor core or existing cache hierarchy.