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