Citation
Heterogeneous construction of spatial data structures

Material Information

Title:
Heterogeneous construction of spatial data structures
Creator:
Butts, Robert O. ( author )
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
1 electronic file (64 pages). : ;

Subjects

Subjects / Keywords:
Spatial data infrastructures ( lcsh )
Geospatial data ( lcsh )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Review:
Linear spatial trees are typically constructed in two discrete, consecutive stages: calculating location codes, and sorting the spatial data according to the codes. Additionally, a GPU R-tree construction algorithm exists which likewise consists of sorting the spatial data and calculating nodes' bounding boxes. Current GPUs are approximately three orders of magnitude faster than CPUs for perfectly vectorizable problems. However, the best known GPU sorting algorithms only achieve 10-20 times speedup over sequential CPU algorithms. Both calculating location codes and bounding boxes are perfectly vectorizable problems. We thus investigate the construction of linear quadtrees, R-trees, and linear k -d trees using the GPU for location code and bounding box calculation, and parallel CPU algorithms for sorting. In this endeavor, we show how existing GPU linear quadtree and R-tree construction algorithms may be modified to be heterogeneous, and we develop a novel linear k -d tree construction algorithm which uses an existing parallel CPU quicksort partition algorithm. We implement these heterogeneous construction algorithms, and we show that heterogeneous construction of spatial data structures can approach the speeds of homogeneous GPU algorithms, while freeing the GPU to be used for better vectorizable problems.
Thesis:
Thesis (M.S.)--University of Colorado Denver. Computer science
Bibliography:
Includes bibliographic references.
System Details:
System requirements: Adobe Reader.
General Note:
Department of Computer Science and Engineering
Statement of Responsibility:
by Robert O. Butts.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
911140946 ( OCLC )
ocn911140946

Downloads

This item is only available as the following downloads:


Full Text

PAGE 18

if

PAGE 19

parallelforparallelvectorforvectorforCreateNodesor

PAGE 20

point;node;boundary;depth node:point point i 0;depth bit1 0 bit2 0 point:y>(boundary:topleft:y+(boundary:bottomright:y)]TJ /F5 11.955 Tf -402.38 -14.44 Td[(boundary:topleft:y)/2) bit1 1 point:x>(boundary:topleft:x+(boundary:bottomright:x)]TJ /F5 11.955 Tf -402.38 -14.44 Td[(boundary:topleft:x)/2) bit2 1 bits (bit1<<1)jbit2 node:location node:location<<2)jbits newwidth (boundary:bottomright:x)]TJ /F5 11.955 Tf 11.96 0 Td[(boundary:topleft:x)/2 newheight (boundary:bottomright:y)]TJ /F5 11.955 Tf 11.96 0 Td[(boundary:topleft:y)/2 point:x)]TJ /F5 11.955 Tf 11.95 0 Td[(boundary:topleft:x>newwidth boundary:topleft:x boundary:topleft:x+newwidth point:y)]TJ /F5 11.955 Tf 11.96 0 Td[(boundary:topleft:y>newheight boundary:topleft:y boundary:topleft:y+newheight boundary:bottomright:x boundary:topleft:x+newwidth boundary:bottomright:y boundary:topleft:y+newheight node points;boundary;depth tree newLinearQuadtree i 0;points:length tree:nodes[i] (points[i];tree:nodes[i];boundary;depth) tree nodea;nodeb nodea:location
PAGE 21

boundary:topleft:x floor((point:x)]TJ /F5 11.955 Tf 16.41 0 Td[(boundary:topleft:x)/newwidth)newwidth+boundary:topleft:x boundary:topleft:y floor((point:y)]TJ /F5 11.955 Tf 16.17 0 Td[(boundary:topleft:y)/newheight)newheight+boundary:topleft:y bit1 point:y>(boundary:topleft:y+(boundary:bottomright:y)]TJ /F5 11.955 Tf -402.38 -14.45 Td[(boundary:topleft:y)/2) bit2 point:x>(boundary:topleft:x+(boundary:bottomright:x)]TJ /F5 11.955 Tf -402.38 -14.45 Td[(boundary:topleft:x)/2)

PAGE 22

forCreateNodesSortCreateLinearQuadtreeCreateNodesCreateNode

PAGE 23

nn A0;A1A a0A1 O(n)Bbqbq
PAGE 24

C1A1B1 CC1C2C=fc0iji=0::q;c1iji=q::g A;B;C mergecutoff 2000. A:size+B:size
PAGE 25

a;b a:x1. len Nodes[level)]TJ /F7 11.955 Tf 11.95 0 Td[(1]:Length/ELEMENTSPERNODE i 0;len node newNode j 0;ELEMENTSPERNODE nodes[level] node

PAGE 27

O(n)

PAGE 28

buffer (Data) nextsplitright (buffer;splitvalue) nextsplitleft (buffer;splitvalue) splitposition (Data;splitvalue) Splits newList Splits[0] (Data) MortonCodes (Data;Splits) (Data;Splits;MortonCodes)

PAGE 29

Splits[splitlocation] (Data) splitleftindex splitlocation2+1 splitrightindex splitlocation2+2 splitleftindex>Data:lengthsplitrightindex>Data:length O(n)

PAGE 30

nodeTreeNodes nextsplit (Data) split 0;node:depth nextsplit (Data;nextsplit) Splits[node] nextsplit nn

PAGE 31

2n

PAGE 32

nextsplitright (Data;splitvalue) nextsplitleft (Data;splitvalue) splitposition (Data;splitvalue)

PAGE 33

n2nn

PAGE 35

leftindex (nextleft) rightindex (nextright) leftindexpivot rightindex rightindex+1 leftindex=Left:sizerightindex=Right:size leftindex=Left:size

PAGE 36

remainingleft RemainingIndices[0] remainingright RemainingIndices[RemainingIndices:size] remainingleftmiddle middle middle+BLOCKSIZE remainingleft remainingleft+1 neutralized=RIGHTneutralized=BOTH remainingright
PAGE 37

nextleft 0 nextright Data:size nextremaining 0 RemainingIndices newArray[threadsnumber] 0threadsnumber pivotposition (Data;pivot;RemainingIndices;nextleft)

PAGE 38

SplitsSplits01Splits

PAGE 39

MortonCodes newArray[Data:size] elementData MortonCodes[element] (element;Splits) code 0 currentsplit 0 code code<<1 elementSplits[currentsplit]) currentsplit (GetLeftChild(currentsplit)(element=Splits[currentsplit]))

PAGE 40

2n+12n+2

PAGE 41

treeend Value. Right Left Length length Nodes newArray NodeAcquirer 0 position AtomicFetchAdd(NodeAcquirer) node Nodes[position] node:Value value node:Left treeend node:Right treeend position AtomicFetchAdd(NodeAcquirer) positionLength. node Nodes[position] node:Value value node:Left treeend node:Right treeend Nodes[parent]:Left position Nodes[parent]:Right position Length Nodes NodeAcquirer

PAGE 42

key leftchild rightchild

PAGE 43

nth(n+1)th npqp+nmax(p;q)+qO(nmax(p;q))nnnnkk

PAGE 45

parallelfor)]TJ /F5 11.955 Tf 9.3 0 Td[(O3parallelsort

PAGE 46

0 2 4 6 8 10 12 14 16 0 500 1;000 1;500 2;000 2;500 3;000

PAGE 47

0 500 1;000 1;500 10n

PAGE 48

0 2 4 6 8 10 12 14 16 0 500 1;000 1;500 2;000 2;500 3;000

PAGE 49

0 500 1;000 10n

PAGE 50

4 8 12 14 16 0 500 1;000 1;500 2;000 2;500 3;000 3;500 4;000 4;500 5;000 5;500 6;000

PAGE 51

0 500 1;000 1;500 10n

PAGE 52

0 2 4 6 8 10 12 14 16 0 500 1;000 1;500 2;000 2;500 3;000 0 500 1;000 1;500 2;000 2;500 3;000 10n

PAGE 53

0 2 4 6 8 10 12 14 16 0 500 1;000 1;500 2;000 2;500 3;000 0 500 1;000 1;500 2;000 2;500 3;000 10n

PAGE 54

0 2 4 6 8 10 12 14 16 0 5;000 10;000 15;000 20;000 25;000 30;000 0 1;000 2;000 3;000 4;000 5;000 10n

PAGE 58

10nnn