Table Of Contents For Computer Architecture: A Minimalist Perspective
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Table Of Contents For Computer Architecture: A Minimalist Perspective as PDF for free.
More details
- Words: 723
- Pages: 6
Contents
Preface................................................................................................ XIII Acknowledgments................................................................................XV 1.
One Instruction Set Computing ...................................................1
1.1
What is One Instruction Set Computing? ..................................1
1.2
Why Study OISC? ........................................................................2
1.3
A Look Ahead ...............................................................................3
1.4
Exercises ........................................................................................3
2
Instruction Sets.............................................................................5
2.1
Elements of an Instruction...........................................................5
2.2
Operands .......................................................................................5
2.3 Instruction Formats......................................................................6 2.3.1 4-tuple Form ...........................................................................6 2.3.2 3-tuple Form ...........................................................................7 2.3.3 2-tuple Form ...........................................................................7 2.3.4 1-tuple and 0-tuple Forms.......................................................8 2.3.5 Mixed Forms...........................................................................9 2.4 Core Set of Instructions................................................................9 2.4.1 Horizontal-bit Operation.........................................................9
viii
Contents 2.4.2 2.4.3 2.4.4 2.4.5 2.4.6
Vertical-bit Operation...........................................................10 Control ..................................................................................10 Mathematical ........................................................................10 Data Movement ....................................................................10 Other Instructions .................................................................11
2.5 Addressing Modes.......................................................................11 2.5.1 Immediate Data.....................................................................11 2.5.2 Direct Memory Location ......................................................12 2.5.3 Indirect Memory Location ....................................................12 2.5.4 Other Addressing Modes ......................................................12 2.6
Exercises ......................................................................................12
3
Types of Computer Architectures..............................................15
3.1
Overview......................................................................................15
3.2 A Simple Taxonomy ...................................................................18 3.2.1 Stack .....................................................................................18 3.3
Accumulator................................................................................19
3.4
Register-Memory ........................................................................19
3.5
Register-Oriented .......................................................................20
3.6
Exercises ......................................................................................21
4
Evolution of Instruction Sets .....................................................23
4.1 Motivation ...................................................................................23 4.1.1 “Big Iron” Computers...........................................................23 4.1.2 First Stored Program Computers ..........................................24 4.1.3 Later Mainframes and Minicomputers.................................26 4.2 Evolution of Microprocessors ....................................................27 4.2.1 Complex Instruction Set Microprocessors............................27 4.2.2 Reduced Instruction Set Microprocessors ...........................28 4.2.3 Other Microprocessor Architectures.....................................29 4.3
Timeline .......................................................................................31
4.4
Exercises ......................................................................................31
5
CISC, RISC, OISC ......................................................................33
Contents
ix
5.1
CISC versus RISC ......................................................................33
5.2
Is OISC a CISC or RISC?..........................................................34
5.3 Processor Complexity.................................................................35 5.3.1 Complexity of CISC .............................................................35 5.3.2 RISC .....................................................................................36 5.3.3 OISC .....................................................................................36 5.3.4 Comparing Complexity.........................................................37 5.4
Exercises ......................................................................................38
6
OISC Architectures.....................................................................41
6.1 Single Instruction Types.............................................................41 6.1.1 Subtract and Branch if Negative (SBN)................................41 6.2 MOVE..........................................................................................42 6.2.1 Half Adder ............................................................................43 6.3 Comparing OISC Models...........................................................44 6.3.1 SBN.......................................................................................44 6.3.2 MOVE...................................................................................46 6.3.3 Which OISC Instruction is Better? .......................................47 6.4 Variants of SBN and MOVE......................................................47 6.4.1 Variations on SBN................................................................48 6.4.2 Variations on MOVE............................................................49 6.5
OISC Continuum ........................................................................49
6.6
Exercises ......................................................................................50
7
Historical Review of OISC..........................................................51
7.1 Subtract and Branch if Negative (SBN)....................................51 7.1.1 van der Poel ..........................................................................51 7.1.2 Mavaddat and Parham ..........................................................51 7.1.3 Half Adder (1990).................................................................52 7.2 MOVE-based...............................................................................52 7.2.1 English Electric DEUCE (1953)...........................................52 7.2.2 GRI Computer GRI 909 Minicomputer (1969) ....................52 7.2.3 Burroughs B1700/B1800 Micro Architecture (1972)...........53 7.2.4 New England Digital ABLE (1973) .....................................53 7.2.5 Daniel Tabak/G. Jack Lipovski (1980).................................53 7.2.6 Henk Corporaal/MOVE Transport-Triggered (1987)...........53
x
Contents 7.2.7 7.2.8
Douglas Jones (1988) ...........................................................53 Reconfigurable Architectures ...............................................53
7.3
Timeline .......................................................................................54
7.4
Exercises ......................................................................................54
8
Instruction Set Completeness .....................................................55
8.1 Instruction Set Completeness ....................................................55 8.1.1 Turing Machine Model of Computation...............................55 8.1.2 Böhm-Jacopini Theorem.......................................................56 8.1.3 Extended Böhm-Jacopini Theorem ......................................57 8.1.4 Analysis of GOTO Instruction..............................................59 8.1.5 Principles of Instruction Set Completeness ..........................63 8.1.6 Applying the Principles ........................................................64 8.1.7 Böhm-Jacopini Theorem Revisited ......................................65 8.2
A Practical Approach to Determining Completeness..............66
8.3 Completeness of Two OISCs......................................................67 8.3.1 SBN.......................................................................................67 8.3.2 MOVE...................................................................................69 8.3.3 Half Adder ............................................................................70 8.4
Exercises ......................................................................................71
9
OISC Mappings ...........................................................................73
9.1 Mapping OISC to Conventional Architectures........................73 9.1.1 Stack (0-operand)..................................................................73 9.1.2 Accumulator .........................................................................75 9.1.3 Register-Register / Register-Oriented...................................78 9.1.4 Register-Memory..................................................................80 9.1.5 Summary...............................................................................80 9.2 Synthesizing Instructions ...........................................................80 9.2.1 MOVE...................................................................................81 9.2.2 SBN.......................................................................................85 9.3 Code Fragments ..........................................................................89 9.3.1 High-Level Language C Structures ......................................90 9.3.2 Algorithms and Functions.....................................................96 9.4 Implementing OISC using OISC.............................................110 9.4.1 MOVE with SBN................................................................110 9.4.2 SBN with MOVE................................................................111
Contents
xi
9.5
Exercises ....................................................................................112
10
Parallel Architectures ...........................................................113
10.1
Von Neumann Bottleneck ....................................................113
10.2 Parallel Processing................................................................113 10.2.1 Application Parallelism.......................................................115 10.2.2 Macroparallelism : Parallelization of Quicksort Algorithm118 10.2.3 Instruction-level Parallelism ...............................................119 10.2.4 Information Interchange .....................................................126 10.3 Flynn’s Taxonomy for Parallelism......................................126 10.3.1 Single Instruction Single Data (SISD)................................127 10.3.2 Multiple Instruction Single Data (MISD) ...........................128 10.3.3 Single Instruction Multiple Data (SIMD) ...........................128 10.3.4 Multiple Instruction Multiple Data (MIMD) ......................130 10.4
Exercises ................................................................................131
11
Applications and Implementations ......................................133
11.1 “OISC-like” Phenomena ......................................................133 11.1.1 Transistors in Integrated Circuits........................................133 11.1.2 NAND/NOR Gate Logic ....................................................133 11.1.3 Biological Cells and DNA ..................................................134 11.1.4 Fractals................................................................................134 11.1.5 Cellular Automata...............................................................135 11.2 Field Programmable Gate Arrays.......................................135 11.2.1 Development Environment .................................................138 11.3 Applications...........................................................................139 11.3.1 Genetic Algorithm ..............................................................139 11.4 Image Processing ..................................................................144 11.4.1 Image Representation and Operations ................................144 11.4.2 Implementations in OISC ...................................................146 11.5 Future Work with OISC ......................................................151 11.5.1 Cellular and Biological Computing ....................................151 11.5.2 Implementations of OISC Processor and Compiler............155 11.5.3 Search for Other OISC Instructions....................................156 11.6
Exercises ................................................................................156
xii
Contents Appendix A: A Generic Microprocessor and OISC........................159 Appendix B: One Instruction Set Computer Implementation ........161 B.1 6502 Opcodes Summary...............................................................161 B.2 6502 Opcodes Mapped to MOVE OISC.....................................169 B.3 6502 Addressing as MOVE-based OISC ....................................179 B.4 6502 Addressing Modes and MOVE-based OISC.....................181 Appendix C: Dilation Code Implementation ....................................183 Appendix D: Compiler Output for Dilation......................................189 Appendix E: OISC Equivalent of Dilation........................................193 Glossary................................................................................................197 References ............................................................................................205 Index .....................................................................................................213 About the Authors...............................................................................219
Preface................................................................................................ XIII Acknowledgments................................................................................XV 1.
One Instruction Set Computing ...................................................1
1.1
What is One Instruction Set Computing? ..................................1
1.2
Why Study OISC? ........................................................................2
1.3
A Look Ahead ...............................................................................3
1.4
Exercises ........................................................................................3
2
Instruction Sets.............................................................................5
2.1
Elements of an Instruction...........................................................5
2.2
Operands .......................................................................................5
2.3 Instruction Formats......................................................................6 2.3.1 4-tuple Form ...........................................................................6 2.3.2 3-tuple Form ...........................................................................7 2.3.3 2-tuple Form ...........................................................................7 2.3.4 1-tuple and 0-tuple Forms.......................................................8 2.3.5 Mixed Forms...........................................................................9 2.4 Core Set of Instructions................................................................9 2.4.1 Horizontal-bit Operation.........................................................9
viii
Contents 2.4.2 2.4.3 2.4.4 2.4.5 2.4.6
Vertical-bit Operation...........................................................10 Control ..................................................................................10 Mathematical ........................................................................10 Data Movement ....................................................................10 Other Instructions .................................................................11
2.5 Addressing Modes.......................................................................11 2.5.1 Immediate Data.....................................................................11 2.5.2 Direct Memory Location ......................................................12 2.5.3 Indirect Memory Location ....................................................12 2.5.4 Other Addressing Modes ......................................................12 2.6
Exercises ......................................................................................12
3
Types of Computer Architectures..............................................15
3.1
Overview......................................................................................15
3.2 A Simple Taxonomy ...................................................................18 3.2.1 Stack .....................................................................................18 3.3
Accumulator................................................................................19
3.4
Register-Memory ........................................................................19
3.5
Register-Oriented .......................................................................20
3.6
Exercises ......................................................................................21
4
Evolution of Instruction Sets .....................................................23
4.1 Motivation ...................................................................................23 4.1.1 “Big Iron” Computers...........................................................23 4.1.2 First Stored Program Computers ..........................................24 4.1.3 Later Mainframes and Minicomputers.................................26 4.2 Evolution of Microprocessors ....................................................27 4.2.1 Complex Instruction Set Microprocessors............................27 4.2.2 Reduced Instruction Set Microprocessors ...........................28 4.2.3 Other Microprocessor Architectures.....................................29 4.3
Timeline .......................................................................................31
4.4
Exercises ......................................................................................31
5
CISC, RISC, OISC ......................................................................33
Contents
ix
5.1
CISC versus RISC ......................................................................33
5.2
Is OISC a CISC or RISC?..........................................................34
5.3 Processor Complexity.................................................................35 5.3.1 Complexity of CISC .............................................................35 5.3.2 RISC .....................................................................................36 5.3.3 OISC .....................................................................................36 5.3.4 Comparing Complexity.........................................................37 5.4
Exercises ......................................................................................38
6
OISC Architectures.....................................................................41
6.1 Single Instruction Types.............................................................41 6.1.1 Subtract and Branch if Negative (SBN)................................41 6.2 MOVE..........................................................................................42 6.2.1 Half Adder ............................................................................43 6.3 Comparing OISC Models...........................................................44 6.3.1 SBN.......................................................................................44 6.3.2 MOVE...................................................................................46 6.3.3 Which OISC Instruction is Better? .......................................47 6.4 Variants of SBN and MOVE......................................................47 6.4.1 Variations on SBN................................................................48 6.4.2 Variations on MOVE............................................................49 6.5
OISC Continuum ........................................................................49
6.6
Exercises ......................................................................................50
7
Historical Review of OISC..........................................................51
7.1 Subtract and Branch if Negative (SBN)....................................51 7.1.1 van der Poel ..........................................................................51 7.1.2 Mavaddat and Parham ..........................................................51 7.1.3 Half Adder (1990).................................................................52 7.2 MOVE-based...............................................................................52 7.2.1 English Electric DEUCE (1953)...........................................52 7.2.2 GRI Computer GRI 909 Minicomputer (1969) ....................52 7.2.3 Burroughs B1700/B1800 Micro Architecture (1972)...........53 7.2.4 New England Digital ABLE (1973) .....................................53 7.2.5 Daniel Tabak/G. Jack Lipovski (1980).................................53 7.2.6 Henk Corporaal/MOVE Transport-Triggered (1987)...........53
x
Contents 7.2.7 7.2.8
Douglas Jones (1988) ...........................................................53 Reconfigurable Architectures ...............................................53
7.3
Timeline .......................................................................................54
7.4
Exercises ......................................................................................54
8
Instruction Set Completeness .....................................................55
8.1 Instruction Set Completeness ....................................................55 8.1.1 Turing Machine Model of Computation...............................55 8.1.2 Böhm-Jacopini Theorem.......................................................56 8.1.3 Extended Böhm-Jacopini Theorem ......................................57 8.1.4 Analysis of GOTO Instruction..............................................59 8.1.5 Principles of Instruction Set Completeness ..........................63 8.1.6 Applying the Principles ........................................................64 8.1.7 Böhm-Jacopini Theorem Revisited ......................................65 8.2
A Practical Approach to Determining Completeness..............66
8.3 Completeness of Two OISCs......................................................67 8.3.1 SBN.......................................................................................67 8.3.2 MOVE...................................................................................69 8.3.3 Half Adder ............................................................................70 8.4
Exercises ......................................................................................71
9
OISC Mappings ...........................................................................73
9.1 Mapping OISC to Conventional Architectures........................73 9.1.1 Stack (0-operand)..................................................................73 9.1.2 Accumulator .........................................................................75 9.1.3 Register-Register / Register-Oriented...................................78 9.1.4 Register-Memory..................................................................80 9.1.5 Summary...............................................................................80 9.2 Synthesizing Instructions ...........................................................80 9.2.1 MOVE...................................................................................81 9.2.2 SBN.......................................................................................85 9.3 Code Fragments ..........................................................................89 9.3.1 High-Level Language C Structures ......................................90 9.3.2 Algorithms and Functions.....................................................96 9.4 Implementing OISC using OISC.............................................110 9.4.1 MOVE with SBN................................................................110 9.4.2 SBN with MOVE................................................................111
Contents
xi
9.5
Exercises ....................................................................................112
10
Parallel Architectures ...........................................................113
10.1
Von Neumann Bottleneck ....................................................113
10.2 Parallel Processing................................................................113 10.2.1 Application Parallelism.......................................................115 10.2.2 Macroparallelism : Parallelization of Quicksort Algorithm118 10.2.3 Instruction-level Parallelism ...............................................119 10.2.4 Information Interchange .....................................................126 10.3 Flynn’s Taxonomy for Parallelism......................................126 10.3.1 Single Instruction Single Data (SISD)................................127 10.3.2 Multiple Instruction Single Data (MISD) ...........................128 10.3.3 Single Instruction Multiple Data (SIMD) ...........................128 10.3.4 Multiple Instruction Multiple Data (MIMD) ......................130 10.4
Exercises ................................................................................131
11
Applications and Implementations ......................................133
11.1 “OISC-like” Phenomena ......................................................133 11.1.1 Transistors in Integrated Circuits........................................133 11.1.2 NAND/NOR Gate Logic ....................................................133 11.1.3 Biological Cells and DNA ..................................................134 11.1.4 Fractals................................................................................134 11.1.5 Cellular Automata...............................................................135 11.2 Field Programmable Gate Arrays.......................................135 11.2.1 Development Environment .................................................138 11.3 Applications...........................................................................139 11.3.1 Genetic Algorithm ..............................................................139 11.4 Image Processing ..................................................................144 11.4.1 Image Representation and Operations ................................144 11.4.2 Implementations in OISC ...................................................146 11.5 Future Work with OISC ......................................................151 11.5.1 Cellular and Biological Computing ....................................151 11.5.2 Implementations of OISC Processor and Compiler............155 11.5.3 Search for Other OISC Instructions....................................156 11.6
Exercises ................................................................................156
xii
Contents Appendix A: A Generic Microprocessor and OISC........................159 Appendix B: One Instruction Set Computer Implementation ........161 B.1 6502 Opcodes Summary...............................................................161 B.2 6502 Opcodes Mapped to MOVE OISC.....................................169 B.3 6502 Addressing as MOVE-based OISC ....................................179 B.4 6502 Addressing Modes and MOVE-based OISC.....................181 Appendix C: Dilation Code Implementation ....................................183 Appendix D: Compiler Output for Dilation......................................189 Appendix E: OISC Equivalent of Dilation........................................193 Glossary................................................................................................197 References ............................................................................................205 Index .....................................................................................................213 About the Authors...............................................................................219
Related Documents
Minimalist Architecture
May 2020 6
Table Of Contents For Portfolio
May 2020 9More Documents from "Kristin McNulty"
The Mynx Programming Language July 2007
August 2019 17
Binar Shuffle Algorithm
December 2019 15