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
2.4.2 Vertical-bit Operation..............................................................................10
2.4.3 Control.....................................................................................................10
2.4.4 Mathematical...........................................................................................10
2.4.5 Data Movement.......................................................................................10
2.4.6 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 Microprocessor......................................................................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
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.3.4 Variations on SBN....................................................................................47
6.3.5 Variations on MOVE................................................................................48
6.4 OISC Continuum.......................................................................................49
6.5 Exercises....................................................................................................49
7 Historical Review of OISC........................................................................50
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
7.2.7 Douglas Jones (1988)...............................................................................53
7.2.8 Reconfigurable Architectures...................................................................54
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
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 Algorithm...............118
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
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