El-Ghazawi
`
`Reference 1005
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 1
`
`

`

`INFORMATION TO USERS
`
`This manuscript has been reproduced from the microfilm master. UMI
`films the text directly from the original or copy submitted. Thus, some
`thesis and dissertation copies are in typewriter face, while others may
`be from any type of computer printer.
`
`The quality of this reproduction is dependent upon the quality of the
`copy submitted. Broken or indistinct print, colored or poor quality
`illustrations and photographs, print bleedthrough, substandard margins,
`and improper alignment can adversely affect reproduction.
`
`In the unlikely event that the author did not send UMI a complete
`manusc1ipt and there are missing pages, these will be noted. Also, if
`unauthmized copyright material had to be removed, a note will indicate
`the deletion.
`
`Oversize materials (e.g., maps, drawings, charts) are reproduced by
`sectioning the original, beginning at the upper left-hand comer and
`continuing from left to right in equal sections with small overlaps. Each
`original is also photographed in one exposure and is included in
`reduced form at the back of the book.
`
`Photographs included in the original manuscript have been reproduced
`xerographically in this copy. Higher quality 6" x 9" black and white
`photographic p1ints are available for any photographs or illustrations
`appearing in this copy for an additional charge. Contact UMI directly
`to order.
`
`A Bell &Howell Information Company
`300 North Zeeb Road. Ann Arbor. Ml 48106-13 46 USA
`313 /7 61-4700 800 /521-0600
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 2
`
`

`

`Reproduced with permission of the copyright owner. Further reproduction prohibited without permissiom1..
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 3
`
`

`

`Order Number 9519447'
`
`The functional memory approach to the design of custom
`computing machines
`
`Halverson, Richard Peyton, Jr., Ph.D.
`
`University of Hawaii, 1994
`
`U·M·I
`
`300 N. Zeeb Rd.
`Ann Arbor, MI 48106
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 4
`
`

`

`Reproduced with permission of the copyright owner. Further reproduction prohibited without permissiorn ..
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 5
`
`

`

`THE FUNCTIONAL MEMORY APPROACH TO THE DESIGN
`OF CUSTOM COMPUTING MACHINES
`
`A DISSERTATION SUBMITTED TO THE GRADUATE DIVISION OF THE
`UNIVERSITY OF HAW All IN PARTIAL FULFILLMENT OF THE
`REQUIREMENTS FOR THE DEGREE OF
`
`DOCTOR OF PHILOSOPHY
`
`IN
`
`COMMUNICATION AND INFORMATION SCIENCES
`
`AUGUST 1994
`
`By
`
`Richard Peyton Halverson, Jr.
`
`Dissertation Committee:
`
`Art Lew, Chairperson
`W. Wesley Peterson
`William E. Remus
`Dan J. Wedemeyer
`Edward J. Weldon, Jr.
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 6
`
`

`

`

`

`© Copyright 1994
`by
`Richard Peyton Halverson, Jr.
`All Rights Reserved
`
`iii
`
`·-·-~-----~--------------
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 8
`
`

`

`ACKNOWLEDGEMENTS
`
`I would like to thank the members of my committee for their service. I would also
`
`like to thank the others who made this dissertation possible. Ray Panko provided my
`
`primary financial support throughout my years as a Ph.D. student. Dan Watanabe
`
`provided the initial funding for the hardware. Dominic McCarthy gave me the ideas for
`
`Chapter 7. On a personal level, I would like to thank my father Richard Sr., my late
`
`mother Sau Hung Young Halverson, and my wife Christine David.
`
`I would also like to thank my chair Art Lew for helping me out as much as he did,
`
`especially with this final document. The detail, comprehensiveness, sense and time he
`
`spent was much appreciated.
`
`iv
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 9
`
`

`

`ABSTRACT
`
`This dissertation describes a software system and related hardware architecture in
`
`which high level language programs are compiled into gate level logic circuitry that is
`
`configured specifically to execute the compiled program. A system whose processor can
`
`be dynamically reconfigured to suit different applications is known as a custom
`
`computing machine (CCM). We have designed a new class of CCMs based on the
`
`concept of functional memory (FM), which we construct by connecting field
`
`programmable gate arrays (FPGAs) in parallel with conventional random access memory
`
`(RAM). FM is used by the processor for computing the (possibly multi-operand)
`
`expressions of the high level language program in the combinational logic provided by the
`
`F.PGAs. When all program expressions are computed in FM, the necessary processor
`
`instruction set reduces to a minimal number of moves and jumps.
`
`Our functional memory computer (FMC) is a four F.PGA FM prototype with a fifth
`
`FPGA programmed as the minimal processor. The language we adopted as the high level
`
`source language for programming the FMC is a decision-table (DT) variation of standard
`
`Pascal. DT programs for a shortest path and two sorting algorithms were translated,
`
`executed, and analyzed on the FMC. The second sorting program demonstrated a
`
`nondeterministic array selection function. An analysis for the shortest path program
`
`showed that memory load/store counts remained comparable for FMC and von Neumann
`
`implementations. However, with the FMC, a 35% reduction in total execution steps
`
`occurred because all computation steps are performed in parallel on the FMC.
`
`The problem of compiling high level DTs to low level FMC object code is more
`
`complex than for conventional machines because each single expression in the source
`
`program can translate into several tens of lines of FPGA circuit definition code. The
`
`V
`
`- - - - - - - - - - -
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 10
`
`

`

`Windows based system developed for this purpose includes a compiler that translates
`
`source programs into intermediate assembly language modules, and an operating system
`
`that invokes system routines for assembling, linking, placing and routing, and loading the
`
`FPGA machine level object code into the minimal processor and functional memory.
`
`vi
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 11
`
`

`

`TABLE OF CONTENTS
`
`Acknowledgements ........................................................................ iv
`
`Abstract ...................................................................................... v
`
`List of Tables ............................................................................... xiii
`
`List of Figures .............................................................................. xiv
`
`Preface ....................................................................................... xviii
`
`Chapter 1.
`
`Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
`
`1.1 Decision Table Programming Model ..................................... 2
`
`1.2 Hardware Background ..................................................... 4
`
`1.2.1 HPC Cache-Only Multiprocessor ............................. 5
`
`1. 3 Levels of Programmability ................................................ 7
`
`1.3.1 Von Neumann Machines ....................................... 7
`
`1.3.2 Microprogrammable Machines ................................. 8
`
`1.3.3 Custom Computing Machines ................................. 11
`
`1.4 Survey of Custom Computing Machines ................................ 12
`
`1.4.1 DEC's Perle-0 ................................................... 13
`
`1.4.2 PRISM-II. ........................................................ 13
`
`1.4. 3 Reconfigurable Processor Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
`
`1.4.4 MoM-4 Xputer ................................................... 14
`
`1.4.5 Splash 2 .......................................................... 14
`
`1.4.6 Any Board ........................................................ 15
`
`1.4.7 Chameleon ....................................................... 15
`
`1.5 The Functional Memory Approach ....................................... 16
`
`1.5.1 Functional Memory ............................................. 16
`
`vii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 12
`
`

`

`1.5.2 A Functional Memory Computer (FMC) ..................... 17
`
`1. 5 .3 High Level Language FMC Programming . . . . . . . . . . . . . . . . . . . 18
`
`1. 6 Other Related Literature .................................................... 20
`
`1.6.1 Hybrid Data Flow Computers ................................. 20
`
`1. 6.2 Functional Programming ....................................... 23
`
`1. 7 Overview of This Dissertation ............................................ 23
`
`Chapter 2. The Design and Implementation of a Functional Memory Computer. 26
`
`2.1 Constructing a Functional Memory ....................................... 26
`
`2.1.1 Programming the FPGA ........................................ 28
`
`2.2 Interface ...................................................................... 31
`
`2.2.1 Address Select ................................................... 31
`
`2.2.2 Input Registers ................................................... 32
`
`2.2.3 Output Multiplexers ............................................. 34
`
`2.3
`
`Implementation of Expression Operators ................................ 35
`
`2.3.1 A
`
`'# B Test ........................................................ 35
`
`2.3.2 Magnitude Comparison Tests .................................. 37
`
`2.3.3 Adding and Subtracting ......................................... 39
`
`2.4 Computing the Rule Address .............................................. 40
`
`2.5 Auto-Clocking Registers ................................................... 43
`
`2.5.1 Automatic Bit Summing ........................................ 43
`
`2.5.2 Auto-Shifting .................................................... 43
`
`2.6 Minimal Processor .......................................................... 45
`
`2.6.1 The Architecture of the Minimal Processor ................... 47
`
`2.6.2 Minimal Processor Instruction Set ............................ 49
`
`2.6.3 Microinstruction Set Implementation .......................... 53
`
`viii
`
`--··----------
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 13
`
`

`

`2.6.4 Minimal Processor Implementation ........................... 55
`
`2.6.5 System Processor Interface .................................... 58
`
`Chapter 3. Decision Table Programming on a Functional Memory Computer ... 61
`
`3.1 Bubble Sort Program Example ............................................ 62
`
`3.1.1 Bubble Sort Functional Memory Map ........................ 64
`
`3.1.2 Bubble Sort Execution Table ................................... 65
`
`3.1.3 Bubble Sort Expression Graphs ............................... 67
`
`3.1.4 Bubble Sort FPGA Ccxle Generation ......................... 69
`
`3.1.5 Bubble Sort Compilation Statistics ............................ 72
`
`3.2 Shortest Path Program Example .......................................... 74
`
`3.2.1 Shortest Path Functional Memory Map ....................... 76
`
`3.2.2 Shortest Path Execution Table ................................. 77
`
`3.2.3 Shortest Path Expression Graphs ............................. 80
`
`3.2.4 Shortest Path FPGA Code Generation ........................ 82
`
`3.2.5 Shortest Path FPGA Compilation Statistics .................. 83
`
`3.3 Conclusions ................................................................. 84
`
`Chapter 4.
`
`Implementing Nondeterministic Programs on a Functional Memory
`
`Computer .................................................................... 86
`
`4.1 Nondetenninistic Constructs .............................................. 87
`
`4.1.1 Nondeterministic Set Operators ................................ 87
`
`4.1.2 Minimum Selection .............................................. 90
`
`4.2 Nondetenninistic Bubble Sort (NBS) .................................... 91
`
`4.2.1 NBS Functional Memory Map ................................. 94
`
`4.2.2 NBS Execution Table ........................................... 95
`
`4.2.3 NBS FPGA Compilation Statistics ............................ 97
`
`ix
`
`--··------ - - - - - -
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 14
`
`

`

`4.3 Conclusions ................................................................. 97
`
`Chapter 5. Analyses of Execution ..................................................... 99
`
`5 .1 Time Comparisons ......................................................... 99
`
`5 .1.1 Shortest Path Execution Times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
`
`5.1.2 Deterministic Bubble Sort Times .............................. 101
`
`5.1.3 Nondeterministic Bubble Sort Times ......................... 103
`
`5.2 Cycle Count Comparisons ................................................. 104
`
`5.2.1 Shortest Path Cycle Counts .................................... 105
`
`5.2.2 Deterministic Bubble Sort Cycle Counts ..................... 107
`
`5.2.3 Nondeterministic Bubble Sort Cycle Counts ................. 108
`
`5.3 Load-Store Comparisons .................................................. 110
`
`5.3.1 Shortest Path Load-Store Analysis ........................... 111
`
`5.4 Conclusion .................................................................. 114
`
`Chapter 6. The Design and Implementation of a Compiler for a Functional
`
`Memory Computer ......................................................... 116
`
`6.1 The Compiling Process .................................................... 116
`
`6.1.1 Generate Intermediate Text (1.0) .............................. 121
`
`6.1.2 Generate Memory Map (2.0) ................................... 123
`
`6.1.3 Generate Microcode Source Module (3.0) ................... 125
`
`6.1.4 Generate FPGA Source Modules (4.0) ....................... 125
`
`6.1.4.1 Expand Function Macros (4.2.2) .................. 128
`
`6.1.4.2 Generate Condition Stub Logic (4.2.3) ........... 129
`
`6.1.4.3 Parsing Expressions (4.2.3.1) ..................... 130
`
`6.1.4.4 Generate Rule Address Logic ( 4.2.4) ............. 133
`
`6.1.4.5 Generate Action Stub Logic (4.2.5) ............... 134
`
`X
`
`- - - ~ - - - - - - - - -
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 15
`
`

`

`6.1.4.6 Generate Input Register Logic (4.2.6) ............. 135
`
`6.1.4. 7 Generate Output Multiplexer Logic (4.2.7) ....... 136
`
`6.1.4.8 Generate Address Select Logic (4.2.8) ............ 137
`
`6.2. The User Interface .......................................................... 138
`
`6.2.1 File Menu ......................................................... 139
`
`6.2.2 View Menu ....................................................... 140
`
`6.2.3 Generate Menu ................................................... 142
`
`6.2.4 Compile Menu ................................................... 145
`
`Chapter 7. Application: Examples in Image Processing ............................. 147
`
`7 .1 Convolution ................................................................. 148
`
`7 .1.1
`
`Image Magnification ............................................ 150
`
`7 .1.2 Pyramid Special Function Implementation ................... 151
`
`7 .1.3 Magnification Program Example .............................. 154
`
`7 .1.4 Magnification Execution Comparison ......................... 156
`
`7 .2 Histograms .................................................................. 157
`
`7 .2.1 Character Classification ......................................... 157
`
`7.2.2 Row-Column Sum Special Function .......................... 158
`
`7.2.3 Histogram Program Example .................................. 160
`
`7.2.4 Row Column Histogram Computation Comparison ........ 161
`
`Chapter 8. Conclusions ................................................................. 162
`
`8.1 Decision Table Computers ................................................. 163
`
`8.2 Custom Computing Machines ............................................. 163
`
`Appendixes. Program Listings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
`
`Appendix 1. Bubble Sort Compiler Listing (BUBBLE.LIS) .............. 165
`
`Appendix 2. Bubble Sort Minimal Processor Code (BUBBLE.ASM) ... 167
`
`xi
`
`. - - · - - - - - - - - - - · - - - -
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 16
`
`

`

`

`

`LIST OF TABLES
`
`Table 2.1.
`
`Minimal Processor Instruction Set.. ......................................... 52
`
`Table 2.2.
`
`Microinstructions for Implementing mP Operations ...................... .56
`
`Table 3.1.
`
`Bubble Sort Functional Memory Map ....................................... 65
`
`Table 3.2.
`
`Bubble Sort Execution Table ................................................. 66
`
`Table 3.3.
`
`Bubble Sort Rule Selection Logic ........................................... 67
`
`Table 3.4.
`
`FPGA Compilation Statistics - Deterministic Bubble Sort ................ 74
`
`Table 3.5.
`
`Shortest Path Functional Memory Map ..................................... 77
`
`Table 3.6.
`
`Shortest Path Execution Table ............................................... 78
`
`Table 3.7.
`
`Shortest Path Rule Address Map ............................................ 79
`
`Table 3.8.
`
`Shortest Path FPGA Compilation Statistics ................................ 84
`
`Table 4.1.
`
`Nondeterministic Bubble Sort Functional Memory Map .................. 95
`
`Table 4.2.
`
`Nondeterministic Bubble Sort Execution Table ............................ 95
`
`Table 4.3.
`
`Nondeterministic Bubble Sort FPGA Compilation Statistics ............. 97
`
`Table 5.1.
`
`Shortest Path Execution Times .............................................. .100
`
`Table 5.2.
`
`Bubble Sort i486 Execution Times .......................................... 102
`
`Table 5.3.
`
`Deterministic Bubble Sort FMC Execution Times ......................... 103
`
`Table 5.4.
`
`Nondeterministic Bubble Sort FMC Execution Times .................... 104
`
`Table 5.5.
`
`Shortest Path Cycle Counts .................................................. 106
`
`Table 5.6.
`
`Bubble Sort Cycles Comparison (Random Array) ........................ 110
`
`Table 5.7.
`
`Shortest Path Load/Store Count Comparison .............................. 115
`
`xiii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 18
`
`

`

`LIST OF FIGURES
`
`Figure 1..1. Decision Table Representation of a Program ............................ .1
`
`Figure 1.2. Decision Table Execution .................................................. .3
`
`Figure 1.3. Decision Table Execution Model ......................................... .4
`
`Figure 1.4. Hawaii Parallel Computer Block Diagram ................................ 6
`
`Figure 1.5.
`
`Compiler for a von Neumann Computer ................................. 8
`
`Figure 1.6.
`
`Compiler for a Microprogrammable Processor .......................... 9
`
`Figure 1.7.
`
`Burroughs Small Reconfigurable Processor ............................. 10
`
`Figure 1.8.
`
`FPGA Based Reconfigurable Processor .................................. 12
`
`Figure 1. 9.
`
`Functional Memory Concept ............................................... 17
`
`Figure 1.10. Functional Memory Computer and Instruction Set ...................... 18
`
`Figure 1.11. Compiling for a FMC ....................................................... 20
`
`Figure 1.12. Categorizing Hybrid Data Flow Computers .............................. 21
`
`Figure 1.13. System for Demonstrating the Functional Memory Approach ......... 24
`
`Figure 2.1.
`
`Implementing Functional Memory - Multiplexer Method .............. 27
`
`Figure 2.2.
`
`Implementing Functional Memory - Logical OR Method .............. 28
`
`Figure 2.3.
`
`Functional Memory FPGA Interface Circuit Shell ...................... 30
`
`Figure 2.4. Address Select PALASM ................................................... 33
`
`Figure 2.5.
`
`Input Register PALASM ................................................... 33
`
`Figure 2.6. Output Multiplexer PALASM .............................................. 34
`
`Figure 2.7. A'#-BTestPALASM ....................................................... 36
`
`Figure 2.8. A = 5 Test FPGA Equations .............................................. .37
`
`Figure 2.9. A< B PALASM ............................................................. 38
`Figure 2.10. D = A + B Equations ........................................................ 39
`
`xiv
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 19
`
`

`

`Figure 2.10 (continued). D =A+ B Equations .......................................... .40
`
`Figure 2.11. Condition Entries Selecting Rule and Rule Starting Addresses ....... .41
`
`Figure 2.12. Rule Jump Address Calculation Example ............................... .42
`
`Figure 2.13. Eight Bit A = A + BO + B 1 Accumulator P ALASM .................... 44
`
`Figure 2.14. 16 Bit Auto Shift Register- Shift Left Eight Bits ...................... .45
`
`Figure 2.15. Functional Memory Computer Board Block Diagram ................. .46
`
`Figure 2.16. Architecture of the Minimal Processor ................................... .48
`
`Figure 2.17. Microinstruction Control Register ......................................... 54
`
`Figure 2.18. Minimal Processor - Detailed Block Diagram ............................ 57
`
`Figure 2.19. System Processor - Minimal Processor Interface ........................ 58
`
`Figure 2.20. System Monitor - User Interface .......................................... 59
`
`Figure 3.1. Bubble Sort Program ....................................................... 62
`
`Figure 3.2. Bubble Sort Flow Chart .................................................... 63
`
`Figure 3.3.
`
`Bubble Sort Program for FM .............................................. 64
`
`Figure 3.4. Deterministic Bubble Sort Expression Graphs ........................... 68
`
`Figure 3.5.
`
`FPGA Operator Macros Used for Deterministic Bubble Sort .......... 70
`
`Figure 3.6.
`
`FPGA Code Generation for j+l ........................................... 71
`
`Figure 3. 7.
`
`Completion of the Compilation Process .................................. 73
`
`Figure 3.8.
`
`Shortest Path Program ...................................................... 75
`
`Figure 3.9.
`
`Shortest Path Rule Address Computation ................................ 81
`
`Figure 3.10. Shortest Path Expression Computation ................................... 82
`
`Figure 4.1.
`
`0(1) Set Operators .......................................................... 88
`
`Figure 4.2.
`
`0(1) Minimum Array Element Selection .................................. 90
`
`Figure 4.3. Nondeterministic Bubble Sort Program .................................. 92
`
`Figure 4.4. Nondeterministic Bubble Sort Flow Chart ............................... 92
`
`Figure 4.5. NBS Exchange Address and Rule Selection ............................. 93
`
`xv
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 20
`
`

`

`Figure 5.1.
`
`Shortest Path Execution Times ............................................ 100
`
`Figure 5.2.
`
`Bubble Sort i486 Execution Times ........................................ 102
`
`Figure 5.3.
`
`Deterministic Bubble Sort FMC Execution Times ....................... 103
`
`Figure 5.4.
`
`Nondeterministic Bubble Sort FMC Execution Times .................. 104
`
`Figure 5.5.
`
`Shortest Path Cycle Counts ................................................ 106
`
`Figure 5.6.
`
`Bubble Sort Cycles Comparison (Random Array) ...................... 110
`
`Figure 5.7.
`
`Shortest Path Load-Store Analysis ........................................ 112
`
`Figure 5.8.
`
`Shortest Path Load/Store Count Comparison ............................ 115
`
`Figure 6.1.
`
`The FMC Compiler Function .............................................. 117
`
`Figure 6.2.
`
`Completion of the Compilation Process Using Off-The-Shelf
`
`Tools .......................................................................... 118
`
`Figure 6.3.
`
`Decision Table Compilation Stages ....................................... 120
`
`Figure 6.4.
`
`1.0 Generate Intermediate Text Hierarchy Chart ...................... 121
`
`Figure 6.5.
`
`Symbol Table Identifier Syntax Diagram ................................. 122
`
`Figure 6.6.
`
`2.0 Generate Memory Map Hierarchy Chart ........................... 123
`
`Figure 6.7.
`
`Syntax Diagrams for Function and Variable Declarations .............. 124
`
`Figure 6.8.
`
`3.0 Generate Microcode Hierarchy Chart .............................. 126
`
`Figure 6.9.
`
`4.0 Generate FPGA PALASM Files Hierarchy Chart ................ 127
`
`Figure 6.10. 4.2.2 FPGA Special Function Expansion Hierarchy Chart .......... .129
`
`Figure 6.11. 4.2.3 Generate FPGA Condition Stub Logic Hierarchy Chart... .... .130
`
`Figure 6.12. Expression Syntax Diagrams .............................................. 131
`
`Figure 6.13. 4.2.3.1 FPGA Expression Hierarchy Chart. ........................... .132
`
`Figure 6.14. 4.2.4 Generate FPGA Rule Address Logic Hierarchy Chart ......... .133
`
`Figure 6.15. 4.2.5 GenerateFPGA Action Stub Expressions Hierarchy Chart .... 135
`
`Figure 6.16. 4.2.6 GenerateFPGA Input Register Logic Hierarchy Chart ......... 136
`
`Figure 6.17. 4.2.7 Generate FPGA Output Multiplexer Logic Hierarchy Chart ... 137
`
`xvi
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 21
`
`

`

`Figure 6.18. 4.2.8 Generate FPGA Address Select Logic Hierarchy Chart ........ 138
`
`Figure 6.19. FMC Compiler -- Opening Screen ........................................ 139
`
`Figure 6.20. File Menu ..................................................................... 140
`
`Figure 6.21. ViewMenu ................................................................... 141
`
`Figure 6.22. Decision Table Full View ................................................... 142
`
`Figure 6.23. Generate Menu ............................................................... 143
`
`Figure 6.24. Memory Map and Execution Table ........................................ 144
`
`Figure 6.25. Assemble Microcode ........................................................ 145
`
`Figure 6.26. Assemble PALASM .PDS to .XNF ...................................... 146
`
`Figure 7 .1.
`
`Steps for 2 to 1 Image Magnification ..................................... 150
`
`Figure 7 .2.
`
`Interpolation Kernels for 2 to 1 Magnification ........................... 151
`
`Figure 7.3. New Pixel Computation .................................................... 152
`
`Figure 7.4.
`
`Parallel Pyramid Convolution Function .................................. 153
`
`Figure 7.5. Decision Table for 2 to 1 Magnification .................................. 155
`
`Figure 7.6.
`
`16 Input I-Bit Adder for Computing Histograms ....................... 158
`
`Figure 7. 7. Bit Counters for Computing Vertical Histograms ....................... 1."9
`
`Figure 7.8. Decision Table for Character Histogram Computation .................. 160
`
`xvii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 22
`
`

`

`PREFACE
`
`In 1986 an engineer friend of mine named Richard Shaffer and I stopped at a local
`
`vendor in Minneapolis to pick up some PALs, when the representative asked us into the
`
`back room to show us something. XILINX had just introduced the first RAM-based
`
`field programmable gate array (FPGA), which was the first very large scale integrated
`
`(VLSI) circuit chip where the circuit is "written into it" not at the factory but after the
`
`power is turned on. In the back room the rep showed us a XILINX 2018 FPGA
`
`development system. He asked, "Can you think of a good application for these things?"
`
`My reply was, "Only if you had a reason to change the circuit as often as you change
`
`RAM, like if the chip could somehow be reprogrammed from a high-level language
`
`compiler." As my friend and I were driving back, I discussed with him how interesting it
`
`would be to write a compiler which would specify the logic circuitry of the machine that
`
`the program would execute on. In 1991 this became my dissertation topic.
`
`xviii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 23
`
`

`

`CHAPTER 1. INTRODUCTION
`
`This dissertation began as a challenge to build a machine designed expressly for
`
`decision table (DT) execution. One advantage of representing a program as a DT
`
`[CODASYL, 1982] is that all the program's conditional statements are consolidated as
`
`"condition stubs" in upper left quadrant of the table with the idea that they can all be
`
`evaluated simultaneously. (See Figure 1.1.) Based on the evaluation of all these
`
`condition stubs, a "rule" corresponding to one of the columns is chosen. The rule
`
`contains a list of statements to execute, which are made up of "action stubs" in the lower
`
`left quadrant of the table.
`
`-Condition Stubs
`
`-Action Stubs
`
`Rules
`
`T
`
`F
`Entry Ta ble
`
`X
`
`X
`
`Figure 1.1. Decision Table Representation of a Program
`
`A machine designed for DT execution would be one where the amount of time it takes
`
`to select a rule is independent of the number of condition stubs and rules. Such a
`
`machine would also be able to compute arithmetic expressions in constant time (within
`
`practical limits). This means that theoretically, the right sides of assignment statements
`
`would also evaluate in unit time, independent of the number of variables or operands. In
`
`the end, theoretical execution time for a program on such a machine would depend only
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`PATENT OWNER DIRECTSTREAM, LLC
`EX. 2169, p. 24
`
`

`

`on (a) the number of iterations of the rules it must execute, pl us (b) the number of
`
`variable changes (i.e., assignment statements) each rule contains.
`
`If "constant time" is on the order of tens or hundreds of microseconds, then such a
`
`machine would only have theoretical value. If this time is on the order of tens or
`
`hundreds of nanoseconds, then the machine would have practical value today. Also, the
`
`machine would have only theoretical value if the sizes of implementable programs are too
`
`small to be of any significance, although "practical limits" of today are much different
`
`than what they will be five years from now.
`
`For this dissertation, we have built a machine whose "constant times" are in the tens
`
`to hundreds of nanoseconds, and whose "practical limits" do not impair it from
`
`potentially impacting important applications (e.g., image processing) over the next five
`
`years. This machine utilizes a relatively new technology, that of field programmable gate
`
`array (FPGA [Brown, et al., 1992]) chips, to extend RAM (memory) to what we call
`
`"functional memory" (FM), which has attached expression computation (function
`
`processing) elements.
`
`1.1 DECISION TABLE PROGRAMMING MODEL
`
`The decision table is used as the high-level programming language to compile because
`
`its structure conveniently separates and consolidates the conditional expressions for
`
`program control into a single expression calculation. Since it has been shown previously
`
`that any comp