Processor Architecture From Dataflow to Superscalar and Beyond

Today's microprocessors are the powerful descendants of the von Neumann 1 computer dating back to a memo of Burks, Goldstine, and von Neumann of 1946. The so-called von Neumann architecture is characterized by a se­ quential control flow resulting in a sequential instruction stream. A program counter addresses the next instruction if the preceding instruction is not a control instruction such as, e. g. , jump, branch, subprogram call or return. An instruction is coded in an instruction format of fixed or variable length, where the opcode is followed by one or more operands that can be data, addresses of data, or the address of an instruction in the case of a control instruction. The opcode defines the types of operands. Code and data are stored in a common storage that is linear, addressed in units of memory words (bytes, words, etc. ). The overwhelming design criterion of the von Neumann computer was the minimization of hardware and especially of storage. The most simple implementation of a von Neumann computer is characterized by a microar­ chitecture that defines a closely coupled control and arithmetic logic unit (ALU), a storage unit, and an I/O unit, all connected by a single connection unit. The instruction fetch by the control unit alternates with operand fetches and result stores for the AL U.

1. Basic Pipelining and Simple RISC Processors.- 1.1 The RISC Movement in Processor Architecture.- 1.2 Instruction Set Architecture.- 1.3 Examples of RISC ISAs.- 1.4 Basic Structure of a RISC Processor and Basic Cache MMU Organization.- 1.5 Basic Pipeline Stages.- 1.6 Pipeline Hazards and Solutions.- 1.6.1 Data Hazards and Forwarding.- 1.6.2 Structural Hazards.- 1.6.3 Control Hazards, Delayed Branch Technique, and Static Branch Prediction.- 1.6.4 Multicycle Execution.- 1.7 RISC Processors.- 1.7.1 Early Scalar RISC Processors.- 1.7.2 Sun microSPARC-II.- 1.7.3 MIPS R3000.- 1.7.4 MIPS R4400.- 1.7.5 Other Scalar RISC Processors.- 1.7.6 Sun picoJava-I.- 1.8 Lessons learned from RISC.- 2. Dataflow Processors.- 2.1 Dataflow Versus Control-Flow.- 2.2 Pure Dataflow.- 2.2.1 Static Dataflow.- 2.2.2 Dynamic Dataflow.- 2.2.3 Explicit Token Store Approach.- 2.3 Augmenting Dataflow with Control-Flow.- 2.3.1 Threaded Dataflow.- 2.3.2 Large-Grain Dataflow.- 2.3.3 Dataflow with Complex Machine Operations.- 2.3.4 RISC Dataflow.- 2.3.5 Hybrid Dataflow.- 2.4 Lessons learned from Dataflow.- 3. CISC Processors.- 3.1 A Brief Look at CISC Processors.- 3.2 Out-of-Order Execution.- 3.3 Dynamic Scheduling.- 3.3.1 Scoreboarding.- 3.3.2 Tomasulo’s Scheme.- 3.3.3 Scoreboarding versus Tomasulo’s Scheme.- 3.4 Some CISC Microprocessors.- 3.5 Conclusions.- 4. Multiple-Issue Processors.- 4.1 Overview of Multiple-Issue Processors.- 4.2 I-Cache Access and Instruction Fetch.- 4.3 Dynamic Branch Prediction and Control Speculation.- 4.3.1 Branch-Target Buffer or Branch-Target Address Cache.- 4.3.2 Static Branch Prediction Techniques.- 4.3.3 Dynamic Branch Prediction Techniques.- 4.3.4 Predicated Instructions and Multipath Execution.- 4.3.5 Prediction of Indirect Branches.- 4.3.6 High-Bandwidth Branch Prediction.- 4.4 Decode.- 4.5 Rename.- 4.6 Issue and Dispatch.- 4.7 Execution Stages.- 4.8 Finalizing Pipelined Execution.- 4.8.1 Completion, Commitment, Retirement and Write-Back.- 4.8.2 Precise Interrupts.- 4.8.3 Reorder Buffers.- 4.8.4 Checkpoint Repair Mechanism and History Buffer.- 4.8.5 Relaxing In-order Retirement.- 4.9 State-of-the-Art Superscalar Processors.- 4.9.1 Intel Pentium family.- 4.9.2 AMD-K5, K6 and K7 families.- 4.9.3 Cyrix M II and M 3 Processors.- 4.9.4 DEC Alpha 21x64 family.- 4.9.5 Sun UltraSPARC family.- 4.9.6 HAL SPARC64 family.- 4.9.7 HP PA-7000 family and PA-8000 family.- 4.9.8 MIPS R10000 and descendants.- 4.9.9 IBM POWER family.- 4.9.10 IBM/Motorola/Apple PowerPC family.- 4.9.11 Summary.- 4.10 VLIW and EPIC Processors.- 4.10.1 TI TMS320C6x VLIW Processors.- 4.10.2 EPIC Processors, Intel’s IA-64 ISA and Merced Processor.- 4.11 Conclusions on Multiple-Issue Processors.- 5. Future Processors to use Fine-Grain Parallelism.- 5.1 Trends and Principles in the Giga Chip Era.- 5.1.1 Technology Trends.- 5.1.2 Application-and Economy-Related Trends.- 5.1.3 Architectural Challenges and Implications.- 5.2 Advanced Superscalar Processors.- 5.3 Superspeculative Processors.- 5.4 Multiscalar Processors.- 5.5 Trace Processors.- 5.6 DataScalar Processors.- 5.7 Conclusions.- 6. Future Processors to use Coarse-Grain Parallelism.- 6.1 Utilization of more Coarse-Grain Parallelism.- 6.2 Chip Multiprocessors.- 6.2.1 Principal Chip Multiprocessor Alternatives.- 6.2.2 TI TMS320C8x Multimedia Video Processors.- 6.2.3 Hydra Chip Multiprocessor.- 6.3 Multithreaded Processors.- 6.3.1 Multithreading Approach for Tolerating Latencies.- 6.3.2 Comparison of Multithreading and Non-Multithreading Approaches.- 6.3.3 Cycle-by-Cycle Interleaving.- 6.3.4 Block Interleaving.- 6.3.5 Nanothreading and Microthreading.- 6.4 Simultaneous Multithreading.- 6.4.1 SMT at the University of Washington.- 6.4.2 Karlsruhe Multithreaded Superscalar.- 6.4.3 Other Simultaneous Multithreading Processors.- 6.5 Simultaneous Multithreading versus Chip Multiprocessor.- 6.6 Conclusions.- 7. Processor-in-Memory, Reconfigurable, and Asynchronous Processors.- 7.1 Processor-in-Memory.- 7.1.1 The Processor-in-Memory Principle.- 7.1.2 Processor-in-Memory approaches.- 7.1.3 The Vector IRAM approach.- 7.1.4 The Active Page model.- 7.2 Reconfigurable Computing.- 7.2.1 Concepts of Reconfigurable Computing.- 7.2.2 The MorphoSys system.- 7.2.3 Raw Machine.- 7.2.4 Xputers and KressArrays.- 7.2.5 Other Projects.- 7.3 Asynchronous Processors.- 7.3.1 Asynchronous Logic.- 7.3.2 Projects.- 7.4 Conclusions.- Acronyms.- References.