Highly Parallel Processing of Relational Databases (Thesis)
Ching C. Hsiao · Purdue e-Pubs (Purdue University System) · 1982
INTRODUCTION 1 1.1 Goal and Methodology 2 1.2 Definitions and Notation 4 1.3 Organization of the Thesis " " 6 vi IJST OF FIGURES. Figure Page 2-1 The system configuration of highly parallel database machines •••••••• .. •.•••• 9 2-2 The systolic array system for performing database operations ., , , 15 2-3 The BK-tree machine , 16 2-4 Two structures of the switch lattice: (a) w;l.d;4; (b) w;2, d;8 •.••••••••••••••••• 19 3-1 State diagram for two idempotent marking functions , , 31 3-2 A "shift-copy and compare" scheme for detecting duplicates in a sorted sequence 33 3-3 Logical structure of the easy-catch system for performing join operations , ,., , , 36 3-4 Two configurations on a CHiP computer for implementing the easy-catch system , 38 4-1 Collapsing the time-complexity hierarchy implying the optimality of POP-SORT ,.. , "., ,•••••••• .. , 43 4-2 PIM machine as a model of parallel computation , , ••• .. • .. ••• 46 4-3 The function of enumeration comaprison methods: table filling and row computation , , • .. ••••.4 9 4-4 The total ordering contained in the semi-digraph , 53 4-5 A general comparison nelwork .. , , •,,•• .. ••• .. •• •• .. •55, " " vii 5-1 (a) Shuffled row-major indexing.(b) Row-major indexing.(c) Snake-like row-major indexing 62 5-2 Rearrangement merge of two 4x4 regions 65 5-3 A triangular interchange scheme to perform unshu:tIle, ,. , 65 5-4 Sorting 176 data items with 4x4 and BxB shadow regions 67 5-5 The interconnection patterns 1 1 .2 composed of three sub-patterns: • viii C-2 An embedding of the perfect shuffle for n = 32 on a CHiP switch lattice, , " , , 118 C-3 Some basic components constructing the embedding in Figure C-2 ,.. ,." , ,..