PIPELINED DESIGN APPROACH TO MICROPROCESSOR

2y ago
15 Views
2 Downloads
1.31 MB
134 Pages
Last View : 1m ago
Last Download : 2m ago
Upload by : Ronan Garica
Transcription

PIPELINED DESIGN APPROACH TO MICROPROCESSORARCHITECTURESA PARTIAL IMPLEMENTATION: MIPS PIPELINEDARCHITECTURE ON FPGAA THESIS SUBMITTED TOTHE GRADUATE SCHOOL OF NATURAL AND APPLIED SCIENCESOFMIDDLE EAST TECHNICAL UNIVERSITYBYMUZAFFER CAN ALTINİĞNELİIN PARTIAL FULFILLMENT OF THE REQUIREMENTSFORTHE DEGREE OF MASTER OF SCIENCEINELECTRICAL AND ELECTRONICS ENGINEERINGDECEMBER 2005

Approval of the Graduate School of Natural and Applied SciencesProf. Dr. Canan ÖZGENDirectorI certify that this thesis satisfies all the requirements as a thesis for the degreeof Master of Science.Prof. Dr. İsmet ERKMENHead of DepartmentThis is to certify that we have read this thesis and that in our opinion it is fullyadequate, in scope and quality, as a thesis for the degree of Master of Science.Prof. Dr. Hasan GÜRANSupervisorExamining Committee MembersAssist. Prof. Dr. Cüneyt BAZLAMAÇCI(METU, EE)Prof. Dr. Hasan GÜRAN(METU, EE)Dr. Ece (GÜRAN) SCHMIDT(METU, EE)Assist. Prof. Dr. İlkay ULUSOY(METU, EE)M.S. Eng. Murat ŞANSAL(ASELSAN)ii

PLAGIARISMI hereby declare that all information in this document has been obtainedand presented in accordance with academic rules and ethical conduct. Ialso declare that, as required by these rules and conduct, I have fully citedand referenced all material and results that are not original to this work.Name, Last Name: Muzaffer Can ALTINİĞNELİSignatureiii:

ABSTRACTPIPELINED DESIGN APPROACH TO MICROPROCESSORARCHITECTURESA PARTIAL IMPLEMENTATION: MIPS PIPELINED ARCHITECTURE ONFPGAALTINİĞNELİ, Muzaffer CanM.S, Department of Electrical and Electronics EngineeringSupervisor: Prof. Dr. Hasan GÜRANSeptember 2005, 120 PagesThis thesis demonstrate how pipelining in a RISC processor is achievedby implementing a subset of MIPS R2000 instructions on FPGA.Pipelining, which is one of the primary concepts to speed up amicroprocessor is emphasized throughout this thesis. Pipelining isfundamentally invisible for high level programming language user andthis work reveals the internals of microprocessor pipelining and thepotential problems encountered while implementing pipelining. Thecomparative and quantitative flow of this thesis allows to understandwhy pipelining is preferred instead of other possible implementationschemes. The methodology for programmable logic development andthe capabilities of programmable logic devices are also given asbackground information. This thesis can be the starting point andreference for programmers who are willing to get familiar withmicroprocessors and pipelining.Keywords: Microprocessor, MIPS, Pipelining, FPGAiv

ÖZMİKRO İŞLEMCİLERDE PIPELINED DİZAYN YAKLAŞIMIMIPS PIPELINED İŞLEMCİ MİMARİSİNİN FPGA ÜZERİNDE KISMIBİR UYGULAMASIALTINİĞNELİ, Muzaffer CanYüksek Lisans, Elektrik Elektronik MühendisliğiTez Yöneticisi: Prof. Dr. Hasan GÜRANEylül 2005, 120 SayfaBu çalışmada, RISC işlemcilerde “Pipelining” konusu, FPGA üzerindeMIPS R2000 komut setinin bir kısmı tamamlanarak açıklanmıştır.Çalışma boyunca, Mikro İşlemcilerin hızlarının arttırılması konusundatemel bir unsur olan “Pipelining” konusu üzerinde durulmuştur. Temelolarak “Pipelining” işlevi, yüksek seviyede programlama yapan kişileregörünmezdir. Bu çalışma “Pipelining” işlevinin ayrıntılarını ve bu leriortayakoymaktadır.“Pipelining” dışındaki diğer tasarım yaklaşımlarının neden uygulanamazoldukları, bu tezin karşılaştırmalı ve nicel akışı sayesinde anlaşılabilir.Donanım tasarımında temel alınan metodolojiler ve donanımlarınkabiliyetleri hakkında tez boyunca bir alt yapı oluşturulmaya daçalışılmıştır. Bu tez, Mikro İşlemciler ve “Pipelining” işlevi ile tanışıklıkkazanmak isteyen programcılar için bir başlangıç ve referans noktasıolabilir.Anahtar Kelimeler: Mikro İşlemci, MIPS, Pipeline, FPGAv

To My Generous Familyvi

ACKNOWLEDGMENTSI owe much gratitude to my Advisor, Professor Dr. Hasan Güran, forinspiring me to carry out this thesis. His criticism and suggestions bringthis work to this point and I am always aware during our work that thisthesis is first of all for my benefit.Everyone working at ASELSAN deserve my thanks, especially ErdinçAtılgan, Kemal Burak Codur and Murat Şansal. They guided me to righttechnical people, supported me technically and mentally during mywork. This thesis ended up with an implementation because ASELSANgave the hardware support without waiting any outcome despite it is acommercial organization.I also owe lots to my father, mother and sister. They interested in all ofmy needs while I was embedded to my work. I also grasp the idea ofbeing a family in addition to fundamentals of pipelining in microprocessors at the end of this work.vii

TABLE OF CONTENTSPLAGIARISM. iABSTRACT.ivÖZ. vACKNOWLEDGMENTS . viiTABLE OF CONTENTS. viiiLIST OF TABLES .xiLIST OF FIGURES . xiiLIST OF ABBREVIATIONS . xivCHAPTER1. INTRODUCTION . 12. BACKGROUND AND MOTIVATION . 42.1. Programmable Logic Design . 42.1.1. History of Programmable Logic . 52.1.1.1. Simple Programmable Logic Device (SPLD) . 52.1.1.1.1. Programmable Logic Array (PLA). 52.1.1.1.2. Programmable Array Logic (PAL). 62.1.1.2. Complex Programmable Logic Device (CPLD) . 72.1.1.3. Field Programmable Logic Gate Array (FPGA) . 82.1.2. Basic Design Process. 92.2. Integrated Software Environment (ISE ) . 102.3. Virtex FPGA. 132.3.1. Function Generation Capabilities of CLB. 142.3.2. Distributed (Shallow) Memory Usage of CLB . 152.3.3. Shift Register Configuration of CLB . 152.3.4. Arithmetic Capabilities of CLB . 152.4. PCI Host Software: In-Circuit Debugging of the Architecture . 163. RELATED RESEARCH . 193.1. MIPS R2000 Instruction Set Architecture (ISA). 193.2. MIPS Instructions and MIPS Assembly Language . 203.2.1. MIPS Instruction Format . 213.2.2. MIPS Addressing Modes . 223.2.3. MIPS Instruction Decoding . 233.3. Survey of Instruction Set Architecture Implementation Scheme 243.3.1. Single Cycle Implementation Scheme . 253.3.2. Multi Cycle Implementation Scheme. 273.3.3. Pipelined Implementation Scheme . 293.3.4. Quantitative Comparison of Implementation Schemes . 31viii

3.4. Problems and Solutions in Pipelined Architectures . 333.4.1. Structural Hazards . 333.4.2. Brach Hazards. 343.4.3. Data Hazards. 353.4.4. Exception Hazard . 374. IMPLEMENTATION OF MIPS PIPELINED ARCHITECTURE. 384.1. Internal Structure of the Processor. 424.1.1. Instruction Fetch Unit. 424.1.1.1. Input/Output Signals of Instruction Fetch Unit. 434.1.1.2. Function of Instruction Fetch Unit. 454.1.2. Instruction Decode Unit . 454.1.2.1. Input/Output Signals of Instruction Decode Unit. 464.1.2.2. Function of Instruction Decode Unit . 494.1.3. Forwarding and Hazard Detection Unit. 494.1.3.1. Input/Output Signals of Forwarding and HazardDetection Unit . 494.1.3.2. Function of Forwarding and Hazard Detection Unit. 524.1.4. Control Unit. 524.1.4.1. Input/Output Signals of Control Unit. 524.1.4.2. Function of Control Unit . 554.1.5. Execute Unit . 554.1.5.1. Input/Output Signals of Execute Unit . 564.1.5.2. Function of Execute Unit . 574.1.6. Data Memory Unit. 574.1.6.1. Input/Output Signals of Data Memory Unit. 574.1.6.2. Function of Data Memory Unit . 584.1.7. Exception Detection Unit . 584.1.7.1. Input/Output Signals of Exception Detection Unit. 594.1.7.2. Function of Exception Detection Unit . 604.1.8. Register Blocks between Stages of Processor . 604.2. External Structure of the Processor . 614.2.1. External Monitoring of the Processor. 624.2.2. External Manipulation of the Processor . 635. VERIFICATION OF MIPS PIPELINED ARCHITECTURE . 675.1. Verification of Correct Operation of Instructions. 675.2. Verification of Hazard Detection and Handling. 775.3. Verification of Exception Handling. 836. CONCLUSIONS AND FUTURE WORK . 91REFERENCES . 93APPENDICIESA. IMPLEMENTED SUBSET OF MIPS R2000 ISA . 96B. MIPS MONITOR SOFTWARE . 105ix

C. FLOW DIAGRAMS ARCHITECTURE ELEMENTS . 112Instruction Fetch Unit Flow Diagram . 112Instruction Decode Unit Flow Diagram. 113Forwarding and Hazard Detection Unit Flow Diagram . 114Instruction Execute Unit Flow Diagram . 115Instruction Execute Unit Flow Diagram (continued) . 116Data Memory Unit Flow Diagram . 117Exception Detection Unit Flow Diagram . 117Register Block Unit Flow Diagram. 118D. LAYOUT OF BOARD . 119E. RESOURCES IN THIS THESIS . 120x

LIST OF TABLESTABLE3.1: Calculation of CPI for Multi Cycle Implementation Scheme . 323.2: Instruction Time Calculation for Implementation Schemes. 334.1: Forwarding Mechanism for Register Bank Primary Port . 504.2: Forwarding Mechanism for Register Bank Secondary Port. 504.3: ID Control Signal Fields . 534.4: EX Control ALUOp Signal Values. 534.5: Base Addresses of Processor’s Internal Signals . 635.1: Verification of Correct Instruction Operation. 685.2: Timing Diagram for Instruction Operation Verification . 705.3: Verification of Hazard Detection and Handling . 775.4: Timing Diagram for Handling Hazard Verification . 795.5: Verification of Exception Handling “ADDU” and “ADD” . 835.6: Timing Diagram for Exception Handling of ADDU and ADD . 845.7: Verification of Exception Handling “SUBU” and “SUB”. 855.8: Timing Diagram for Exception Handling of SUBU and SUB. 865.9: Verification of Exception Handling “ADDIU” and “ADDI” . 875.10: Timing Diagram for Exception Handling of ADDIU and ADDI . 885.11: Verification of Exception Handling Undefined Instructions . 895.12: Timing Diagram for Undefined Instruction Exception Handling . 90A.1: MIPS Registers . 104xi

LIST OF FIGURESFIGURE2.1: PLA Architecture . 62.2: PAL Architecture . 72.3: CPLD Architecture . 82.4: FPGA Architecture. 82.5: Basic Design Flow in FPGAs, Xilinx . 92.6: MIPS Project Properties Window . 112.7: MIPS Project Source File Listing. 122.8: Virtex Architecture Overview Xilinx . 142.9: Function Generator Configuration of CLB. 142.10: Carry Logic Diagram Xilinx. 152.11: Multiplier Implementation Xilinx. 162.12: MIPS Monitor Software. 183.1: MIPS Instruction Format . 213.2: Immediate Addressing Mode . 223.3: Register Addressing Mode . 223.4: Base Addressing Mode. 223.5: PC Relative Addressing Mode. 233.6: Pseudo Direct Addressing Mode. 233.7: MIPS Opcode Map and Frequency of Instructions. 243.8: Single Cycle Implementation Scheme [COD98] . 263.9: Multi Cycle Implementation Scheme [COD98]. 283.10: State Flow Diagram of Multi Cycle Scheme Control Unit. 293.11: Pipelined Implementation Scheme [COD98]. 303.12: Simultaneously Executing Instructions in Pipeline . 313.13: Single and Multi Cycle Instruction Sequence. 323.14: Data Hazard Solution by Forwarding. 363.15: Data Hazard Solution by Stalling and Forwarding . 363.16: Forwarding of the Most Recent Data. 374.1: Internal Structure of the Pipelined Processor. 404.2: External Structure of the Pipelined Processor . 414.3: Input/Output Signals of Instruction Fetch Unit. 444.4: Input/Output Signals of Instruction Decode Unit. 484.5: Input/Output Signals of Forwarding and Hazard Detection Unit . 514.6: Input/Output Signals of Control Unit . 554.7: Input/Output Signals of Execute Unit. 564.8: Input/Output Signals of Data Memory Unit . 584.9: Input/Output Signals of Exception Detection Unit. 60xii

4.10: Input/Output Signals of Reg Unit. 624.11: Input/Output Signals of Reg Wr Unit . 644.12: StateCAD Diagram of Wait Sm Unit . 654.13: Input/Output Signals of Reg Prg Unit . 66B.1: Main Screen of MIPS Monitor Software. 106B.2: Main Functions of MIPS Monitor Software . 107B.3: PCI Device Selection Dialog. 108B.4: PCI Device Selection Dialog. 109B.5: Unresolved Hazards View. 110B.6: Overflow Exception Detection View. 111B.7: Undefined Instruction Exception Detection View. 111C.1: Instruction Fetch Unit Flow Diagram . 112C.2: Instruction Decode Unit Flow Diagram . 113C.3: Forwarding and Hazard Detection Unit Flow Diagram. 114C.4: Instruction Execute Unit Flow Diagram. 115C.5: Instruction Execute Unit (continued) Flow Diagram . 116C.6: Data Memory Unit Flow Diagram. 117C.7: Exception Detection Unit Flow Diagram . 117C.8: Register Block Unit Flow Diagram. 118D.1: Layout of Board. 119xiii

LIST OF BPLAPROMRISCSoRCSPLDVHDLWBXSTArithmetic Logic UnitApplication InterfaceApplication Specific Integrated CircuitBlock Random Access MemoryComplex Instruction Set ComputerConfigurable Logic BlockCLocKClock cycle Per InstructionComplex Programmable Logic DeviceDelay Locked LoopExecute (stage)Flip FlopField Programmable Gate ArrayGnu C CompilerGeneral Purpose RegisterHardware Description LanguageInstruction Decode (stage)Instruction Fetch (stage)Input Output BlockInstruction Set ArchitectureIntegrated Software EnvironmentLook Up TableMemory (stage)Microprocessor without Interlocked Pipeline StagesMUltiplXerNo Operation (instruction)Programmable Array LogicProgram CounterPrinted Circuit BoardProgrammable Logic ArrayProgrammable Read Only MemoryReduced Instruction Set ComputerSystem on Re-programmable ChipSimple Programmable Logic DeviceVery high speed integrated HW Description LanguageWrite Back (stage)Xilinx Synthesis Technologyxiv

CHAPTER 1INTRODUCTIONFaster execution of computer programs was the one of the

MIPS R2000 komut setinin bir kısmı tamamlanarak açıklanmı ştır. Çalı şma boyunca, Mikro İşlemcilerin hızlarının arttırılması konusunda temel

Related Documents:

ical model to guide the generation of the optimal pipelined query plan. Thus, the tile size of the pipelined query exe-cution can be adapted in a cost-based manner. We evalu-ate GPL with TPC-H queries on both AMD and NVIDIA GPUs. The experimental results show that 1) the analytical model is able to guide determining the suitable parameter

Microprocessor-Based System with Buses: Address, Data, and Control Microprocessor-based Systems Microprocessor ! The microprocessor (MPU) is a computing and logic device that executes binary instructions in a sequence stored in memory. ! Characteristics: " General purpo

A microprocessor which has n data lines is called an n-bit microprocessor i.e., the width of the data bus determines the size of the microprocessor. Hence, an 8-bit microprocessor like 8085 can handle 8-bits of data at

1 Introduction to Microcomputer Microcomputer architecture, organization and its operation. Difference between Microprocessor and Microcontroller. 1 [1] Lecture Notes Introduction to Microprocessor Evolution of Microprocessor, General Architecture, system bus 2 [1] [2] Lecture Notes 2 Functional units of Microprocessor

36 Chapter 3 Microprocessor Types and Specifications Pre-PC Microprocessor History The brain or engine of the PC is the processor (sometimes called microprocessor), or central processing u

A microprocessor can move data from one memory location to another. A microprocessor can make decisions and jump to a new set of instructions based on those decisions. There may be very sophisticated things that a microprocessor

A microprocessor is a programmable electronics chip that has computing and decision making capabilities similar to central processing unit of a computer. Any microprocessor-based systems having limited number of resources are called microcomputers. Nowadays, microprocessor can be seen in almost all types of electronics devices like mobile phones,

different microprocessor knee types James H Campbell1, Phillip M Stevens1,2 and Shane R Wurdeman1,3 Abstract Introduction: Microprocessor knee analyses to date have been primarily limited to microprocessor knees as a cat-egory rather than comparisons across different models. The purpose of the current analysis was to compare outcomes