\contentsline {chapter}{\numberline {1}Introduction}{13}
\contentsline {paragraph}{Computing Requirements of Vision.}{14}
\contentsline {paragraph}{Reconfigurable Bit-Parallel Processing.}{15}
\contentsline {paragraph}{Research Approach.}{16}
\contentsline {section}{\numberline {1.1}Microprocessor and SIMD systems clock rate}{18}
\contentsline {chapter}{\numberline {2}Previous and Related Work}{19}
\contentsline {section}{\numberline {2.1}Architectural Design}{20}
\contentsline {section}{\numberline {2.2}High-Speed SIMD Systems}{22}
\contentsline {paragraph}{Clock Distribution}{22}
\contentsline {paragraph}{Instruction Broadcasting}{23}
\contentsline {paragraph}{Instruction Generation}{23}
\contentsline {paragraph}{Data Cache}{24}
\contentsline {paragraph}{High Latency Issues}{24}
\contentsline {section}{\numberline {2.3}Reconfigurable Architectures}{25}
\contentsline {section}{\numberline {2.4}Architectural Studies}{26}
\contentsline {subsection}{\numberline {2.4.1}Normalized Analysis: Holman/Snyder) }{26}
\contentsline {subsection}{\numberline {2.4.2}Simulation-Based Performance Evaluation: Herbordt}{28}
\contentsline {subsection}{\numberline {2.4.3}Dynamic Concatenation: Audet et al.}{29}
\contentsline {subsection}{\numberline {2.4.4}Phase-Specific Reconfiguration: Ligon/Ramachandran}{30}
\contentsline {chapter}{\numberline {3}Reconfigurable Bit-Parallel Architecture}{31}
\contentsline {subsection}{\numberline {3.0.5}The Basic Idea of RBP}{31}
\contentsline {subsection}{\numberline {3.0.6}RBP Performance Model}{32}
\contentsline {subsection}{\numberline {3.0.7}Abacus PE Architecture}{34}
\contentsline {paragraph}{Activity Register}{34}
\contentsline {paragraph}{Network}{35}
\contentsline {paragraph}{Background I/O}{35}
\contentsline {subsection}{\numberline {3.0.8}RBP Algorithms}{35}
\contentsline {paragraph}{Data Representation}{36}
\contentsline {paragraph}{Logical Shift.}{36}
\contentsline {paragraph}{Sum Accumulation.}{36}
\contentsline {paragraph}{Addition.}{37}
\contentsline {paragraph}{Match.}{38}
\contentsline {paragraph}{Comparison.}{38}
\contentsline {paragraph}{Multiplication.}{39}
\contentsline {paragraph}{Mesh Move.}{39}
\contentsline {paragraph}{Scan Operations.}{39}
\contentsline {subsection}{\numberline {3.0.9}Performance Summary.}{40}
\contentsline {chapter}{\numberline {4}Abacus Chip and System}{42}
\contentsline {section}{\numberline {4.1}Processing Element Core}{43}
\contentsline {subsection}{\numberline {4.1.1}Memory }{43}
\contentsline {paragraph}{Design}{43}
\contentsline {paragraph}{Implementation}{43}
\contentsline {subsection}{\numberline {4.1.2}ALU}{45}
\contentsline {paragraph}{Design}{45}
\contentsline {paragraph}{Implementation}{48}
\contentsline {paragraph}{Immediate Constant}{48}
\contentsline {subsection}{\numberline {4.1.3}Network}{49}
\contentsline {paragraph}{Design}{49}
\contentsline {paragraph}{Implementation}{50}
\contentsline {subsection}{\numberline {4.1.4}Data/IO Planes}{52}
\contentsline {subsection}{\numberline {4.1.5}Global OR operation}{53}
\contentsline {subsection}{\numberline {4.1.6}Layout Summary}{53}
\contentsline {section}{\numberline {4.2}On-Chip Signal Distribution }{54}
\contentsline {subsection}{\numberline {4.2.1}Local Buffering}{55}
\contentsline {subsection}{\numberline {4.2.2}Layout Issues: The Trench}{56}
\contentsline {subsection}{\numberline {4.2.3}Timing (2)}{57}
\contentsline {section}{\numberline {4.3}External Interfaces (5)}{58}
\contentsline {subsection}{\numberline {4.3.1}System Synchronization}{58}
\contentsline {subsection}{\numberline {4.3.2}Instruction Distribution (1)}{59}
\contentsline {subsection}{\numberline {4.3.3}Inter-Chip Mesh Communication}{62}
\contentsline {subsection}{\numberline {4.3.4}External Memory Interface}{63}
\contentsline {subsection}{\numberline {4.3.5}Image I/O Interface}{64}
\contentsline {section}{\numberline {4.4}Chip Organization and Control Logic}{65}
\contentsline {subsection}{\numberline {4.4.1}Timing Generator}{67}
\contentsline {subsection}{\numberline {4.4.2}Pad Ring Summary}{67}
\contentsline {subsection}{\numberline {4.4.3}Configuration and Control Registers}{68}
\contentsline {subsection}{\numberline {4.4.4}Power Distribution}{68}
\contentsline {subsection}{\numberline {4.4.5}Opcode Decode}{69}
\contentsline {subsection}{\numberline {4.4.6}TAP Control}{69}
\contentsline {paragraph}{Scan Registers}{70}
\contentsline {subsection}{\numberline {4.4.7}Package}{70}
\contentsline {section}{\numberline {4.5}Testing the Chip}{70}
\contentsline {subsection}{\numberline {4.5.1}Test Environment}{70}
\contentsline {subsubsection}{Test Board}{70}
\contentsline {paragraph}{Board Stackup.}{70}
\contentsline {subsubsection}{Test Equipment}{71}
\contentsline {subsubsection}{Test Process}{72}
\contentsline {subsection}{\numberline {4.5.2}Test Results}{72}
\contentsline {paragraph}{Heartbeat monitor}{72}
\contentsline {paragraph}{IO Burst}{73}
\contentsline {paragraph}{Data Plane Shift}{73}
\contentsline {paragraph}{Register File Toggle}{73}
\contentsline {paragraph}{toggleioB100.ps}{73}
\contentsline {paragraph}{Grid Shift Operation}{73}
\contentsline {paragraph}{Summary}{73}
\contentsline {section}{\numberline {4.6}Design Metacomments (1)}{74}
\contentsline {chapter}{\numberline {5}Abacus-1 System-Level Design}{79}
\contentsline {section}{\numberline {5.1}Sequencer}{79}
\contentsline {section}{\numberline {5.2}PE Board}{83}
\contentsline {paragraph}{Instruction Distribution}{83}
\contentsline {paragraph}{Data Distribution}{83}
\contentsline {paragraph}{Inter-Chip Network Wiring.}{84}
\contentsline {paragraph}{Power And Thermal Considerations.}{84}
\contentsline {section}{\numberline {5.3}I/O Boards}{85}
\contentsline {section}{\numberline {5.4}Parallel Algorithm Implementation and Performance}{88}
\contentsline {subsection}{\numberline {5.4.1}Basic Vision Algorithms}{88}
\contentsline {paragraph}{Edge Detection}{88}
\contentsline {paragraph}{Surface Reconstruction}{88}
\contentsline {paragraph}{Optical Flow}{89}
\contentsline {paragraph}{Performance Summary}{89}
\contentsline {subsection}{\numberline {5.4.2}Early vision subset of the DARPA IU Benchmark}{90}
\contentsline {paragraph}{Connected Component Labelling: Broadcast}{90}
\contentsline {paragraph}{Connected Component Labelling: Shrinking}{92}
\contentsline {paragraph}{K-curvature Tracking and Corner Detection}{92}
\contentsline {paragraph}{Median Filter}{92}
\contentsline {paragraph}{Gradient Magnitude}{93}
\contentsline {paragraph}{Hough Transform}{93}
\contentsline {subsection}{\numberline {5.4.3}Sorting and Routing Algorithms}{94}
\contentsline {paragraph}{ShearSort and RevSort}{94}
\contentsline {paragraph}{Mesh Greedy Routing Algorithm}{94}
\contentsline {section}{\numberline {5.5}Other Algorithms}{95}
\contentsline {paragraph}{Text Retrieval}{95}
\contentsline {paragraph}{Seismic Migration}{95}
\contentsline {chapter}{\numberline {6}Analytical Modelling}{97}
\contentsline {section}{\numberline {6.1}Optimal Bit Width Analysis}{97}
\contentsline {subsection}{\numberline {6.1.1}Ideal Model}{98}
\contentsline {paragraph}{PE Area}{98}
\contentsline {paragraph}{Cycle Time}{98}
\contentsline {paragraph}{Performance}{99}
\contentsline {subsection}{\numberline {6.1.2}Amdahl's Law}{99}
\contentsline {subsection}{\numberline {6.1.3}Off-Chip Data}{103}
\contentsline {subsection}{\numberline {6.1.4}Background Loading}{110}
\contentsline {subsubsection}{Less Predictable Access Patterns}{112}
\contentsline {subsection}{\numberline {6.1.5}Conclusions}{114}
\contentsline {section}{\numberline {6.2}What's Missing}{115}
\contentsline {section}{\numberline {6.3}Slice Optimization}{116}
\contentsline {subsection}{\numberline {6.3.1}Conclusion}{119}
\contentsline {section}{\numberline {6.4}Effect of Virtualization}{121}
\contentsline {section}{\numberline {6.5}Unfinished}{123}
\contentsline {paragraph}{Pin Bandwidth}{123}
\contentsline {paragraph}{Number of Pins}{123}
\contentsline {chapter}{\numberline {7}The Next Generation}{125}
\contentsline {section}{\numberline {7.1}Lessons of Abacus-1}{126}
\contentsline {section}{\numberline {7.2}Abacus-2}{129}
\contentsline {subsection}{\numberline {7.2.1}Pipelining Analysis}{130}
\contentsline {subsection}{\numberline {7.2.2}Fixes of Abacus-1}{132}
\contentsline {paragraph}{Reduced Reconfiguration.}{132}
\contentsline {paragraph}{Fixed Data Formats.}{132}
\contentsline {paragraph}{Rise/Fall Time Issues.}{132}
\contentsline {paragraph}{Double Banked Register File}{132}
\contentsline {paragraph}{Low Integration of ECL Components}{133}
\contentsline {paragraph}{Burst IO}{133}
\contentsline {paragraph}{Alternate Active Bit}{133}
\contentsline {paragraph}{External Memory Interface}{134}
\contentsline {paragraph}{Network Model}{134}
\contentsline {paragraph}{Multiplies}{135}
\contentsline {paragraph}{Global OR}{136}
\contentsline {paragraph}{Scalable I/O}{136}
\contentsline {paragraph}{A Conventional Datapath}{136}
\contentsline {paragraph}{Memory Organization}{137}
\contentsline {subsection}{\numberline {7.2.3}Performance Estimation}{137}
\contentsline {paragraph}{Pin Budget.}{137}
\contentsline {paragraph}{Abacus-2 PE Area Estimation}{137}
\contentsline {paragraph}{Cycle Time Estimation}{137}
\contentsline {paragraph}{Power Estimation}{138}
\contentsline {section}{\numberline {7.3}Beyond SIMD: A Family of Abaci}{138}
\contentsline {paragraph}{Abacus-M: Multi-SIMD Operation.}{138}
\contentsline {paragraph}{Abacus-S: Systolic Operation.}{139}
\contentsline {paragraph}{Abacus-F: FPGA Emulation.}{139}
\contentsline {paragraph}{Abacus-U: Universal Computing Element.}{139}
\contentsline {chapter}{\numberline {8}Conclusions}{141}
\contentsline {section}{\numberline {8.1}Technology Impacts on SIMD Designs}{141}
\contentsline {section}{\numberline {8.2}Blah}{142}
\contentsline {section}{\numberline {8.3}Dealing With Latency}{143}
\contentsline {section}{\numberline {.1}Instruction Format}{145}
\contentsline {subsection}{\numberline {.1.1}Regular Instructions}{146}
\contentsline {subsection}{\numberline {.1.2}Special Instructions}{146}
\contentsline {subsection}{\numberline {.1.3}Timing Information}{149}