text: CS 179: GPU Programming Lecture 10
  
  Embed code:
  
  CS 179: GPU Programming Lecture 10
  
  Download Presentation - The PPT/PDF document "CS 179: GPU Programming Lecture 10" is the property of its rightful owner. Permission is granted to download and print the materials on this web site for personal, non-commercial use only, and to display it on your personal computer provided you do not modify the materials and that you retain all copyright notices contained in the materials. By downloading content from our website, you accept the terms of this agreement.
  
  Presentations text content in CS 179: GPU Programming Lecture 10
  
  Slide1
  
  CS 179: GPU Programming
  
  Lecture 10
  
  Slide2
  
  Topics
  
  Non-numerical algorithms
  
  Texture memory
  
  Slide3
  
  GPUs – good for many numerical calculations…
  
  Slide4
  
  Graph Algorithms
  
  Slide5
  
  Graph Algorithms
  
  Graph G(V, E) consists of:
  
  Vertices
  
  Edges (defined by pairs of vertices)
  
  Complex data structures!
  
  How to store?
  
  How to work around?
  
  Are graph algorithms parallelizable?
  
  Slide6
  
  Given source vertex S:
  
  Find min. #edges to reach every vertex from S
  
  *variation
  
  Slide7
  
  Given source vertex S:
  
  Find min. #edges to reach every vertex from S
  
  (Assume source is vertex 0)
  
  *variation
  
  0
  
  1
  
  1
  
  2
  
  2
  
  3
  
  Slide8
  
  Given source vertex S:
  
  Find min. #edges to reach every vertex from S
  
  (Assume source is vertex 0)
  
  0
  
  1
  
  1
  
  2
  
  2
  
  3
  
  Sequential
  
  pseudocode
  
  :
  
  let Q be a queue
  
  Q.enqueue
  
  (source)
  
  label source as discovered
  
  source.value
  
  <- 0
  
  while Q is not empty
  
  v ←
  
  Q.dequeue
  
  ()
  
  for all edges from v to w in
  
  (v):
  
  if w is not labeled as discovered
  
  Q.enqueue
  
  (w)
  
  label w as discovered,
  
  w.value
  
  <-
  
  v.value
  
  + 1
  
  Slide9
  
  Given source vertex S:
  
  Find min. #edges to reach every vertex from S
  
  (Assume source is vertex 0)
  
  0
  
  1
  
  1
  
  2
  
  2
  
  3
  
  Sequential
  
  pseudocode
  
  :
  
  let Q be a queue
  
  Q.enqueue
  
  (source)
  
  label source as discovered
  
  source.value
  
  <- 0
  
  while Q is not empty
  
  v ←
  
  Q.dequeue
  
  ()
  
  for all edges from v to w in
  
  (v):
  
  if w is not labeled as discovered
  
  Q.enqueue
  
  (w)
  
  label w as discovered,
  
  w.value
  
  <-
  
  v.value
  
  + 1
  
  Runtime:
  
  O( |V| + |E| )
  
  Slide10
  
  Representing Graphs
  
  A: |V| x |V| matrix:
  
  A
  
  ij
  
  = 1 if vertices
  
  i,j
  
  O(V
  
  2
  
  Adjacent vertices noted for each vertex
  
  O(V + E) space
  
  Slide11
  
  Representing Graphs
  
  A: |V| x |V| matrix:
  
  A
  
  ij
  
  = 1 if vertices
  
  i,j
  
  O(V
  
  2
  
  ) space <- hard to fit, more copy overhead
  
  Adjacent vertices noted for each vertex
  
  O(V + E) space
  
  <- easy to fit, less copy overhead
  
  Slide12
  
  Representing Graphs
  
  Array
  
  E
  
  a
  
  : Adjacent vertices to vertex 0, then vertex 1, then …
  
  size: O(E)
  
  Array
  
  V
  
  a
  
  : Delimiters for
  
  E
  
  a
  
  size: O(V)
  
  0
  
  2
  
  4
  
  8
  
  9
  
  11
  
  1
  
  2
  
  0
  
  2
  
  0
  
  1
  
  3
  
  4
  
  2
  
  2
  
  5
  
  4
  
  0
  
  1
  
  2
  
  3
  
  4
  
  5
  
  Vertex:
  
  Slide13
  
  Given source vertex S:
  
  Find min. #edges to reach every vertex from S
  
  (Assume source is vertex 0)
  
  0
  
  1
  
  1
  
  2
  
  2
  
  3
  
  Sequential
  
  pseudocode
  
  :
  
  let Q be a queue
  
  Q.enqueue
  
  (source)
  
  label source as discovered
  
  source.value
  
  <- 0
  
  while Q is not empty
  
  v ←
  
  Q.dequeue
  
  ()
  
  for all edges from v to w in
  
  (v):
  
  if w is not labeled as discovered
  
  Q.enqueue
  
  (w)
  
  label w as discovered,
  
  w.value
  
  <-
  
  v.value
  
  + 1
  
  How to “parallelize” when there’s a queue?
  
  Slide14
  
  0
  
  1
  
  1
  
  2
  
  2
  
  3
  
  Sequential
  
  pseudocode
  
  :
  
  let Q be a queue
  
  Q.enqueue
  
  (source)
  
  label source as discovered
  
  source.value
  
  <- 0
  
  while Q is not empty
  
  v ←
  
  Q.dequeue
  
  ()
  
  for all edges from v to w in
  
  (v):
  
  if w is not labeled as discovered
  
  Q.enqueue
  
  (w)
  
  label w as discovered,
  
  w.value
  
  <-
  
  v.value
  
  + 1
  
  Why do we use a queue?
  
  Slide15
  
  BFS Order
  
  Drichel
  
  Here, vertex #s are possible BFS order
  
  Slide16
  
  BFS Order
  
  Drichel
  
  Permutation within ovals preserves BFS!
  
  Slide17
  
  BFS Order
  
  Queue replaceable if layers preserved!
  
  Drichel
  
  Permutation within ovals preserves BFS!
  
  Slide18
  
  Alternate BFS algorithm
  
  Construct arrays of size |V|:
  
  “Frontier” (denote F):
  
  Boolean array - indicating vertices “to be visited” (at beginning of iteration)
  
  “Visited” (denote X):
  
  Boolean array - indicating already-visited vertices
  
  “Cost” (denote C):
  
  Integer array - indicating #edges to reach each vertex
  
  Goal: Populate C
  
  Slide19
  
  Alternate BFS algorithm
  
  New sequential
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  for 0 ≤
  
  i
  
  < |
  
  Va
  
  |:
  
  if F[
  
  i
  
  ] is true:
  
  F[
  
  i
  
  ] <- false
  
  X[
  
  i
  
  ] <- true
  
  for all neighbors j of i:
  
  if X[j] is false:
  
  C[j] <- C[
  
  i
  
  ] + 1
  
  F[j] <- true
  
  Slide20
  
  Alternate BFS algorithm
  
  New sequential
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  for 0 ≤
  
  i
  
  < |
  
  Va
  
  |:
  
  if F[
  
  i
  
  ] is true:
  
  F[
  
  i
  
  ] <- false
  
  X[
  
  i
  
  ] <- true
  
  for
  
  Ea
  
  [
  
  Va
  
  [
  
  i
  
  ]] ≤ j <
  
  Ea
  
  [
  
  Va
  
  [i+1]]:
  
  if X[j] is false:
  
  C[j] <- C[
  
  i
  
  ] + 1 F[j] <- true
  
  Slide21
  
  Alternate BFS algorithm
  
  New sequential
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  for 0 ≤
  
  i
  
  < |
  
  Va
  
  |:
  
  if F[
  
  i
  
  ] is true:
  
  F[
  
  i
  
  ] <- false
  
  X[
  
  i
  
  ] <- true
  
  for
  
  Ea
  
  [
  
  Va
  
  [
  
  i
  
  ]] ≤ j <
  
  Ea
  
  [
  
  Va
  
  [i+1]]:
  
  if X[j] is false:
  
  C[j] <- C[
  
  i
  
  ] + 1
  
  F[j] <- trueParallelizable!
  
  Slide22
  
  GPU-accelerated BFS
  
  CPU-side
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  call GPU kernel( F, X, C,
  
  Va
  
  ,
  
  Ea
  
  )
  
  GPU-side kernel
  
  pseudocode
  
  :
  
  if F[
  
  ] is true:
  
  F[
  
  ] <- false
  
  X[
  
  ] <- true
  
  for
  
  Ea
  
  [
  
  Va
  
  [
  
  ]] ≤ j <
  
  Ea
  
  [
  
  Va
  
  [
  
  + 1]]: if X[j] is false: C[j] <- C[threadId] + 1 F[j] <- trueCan represent boolean values as integers
  
  Slide23
  
  GPU-accelerated BFS
  
  CPU-side
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  call GPU kernel( F, X, C,
  
  Va
  
  ,
  
  Ea
  
  )
  
  GPU-side kernel
  
  pseudocode
  
  :
  
  if F[
  
  ] is true:
  
  F[
  
  ] <- false
  
  X[
  
  ] <- true
  
  for
  
  Ea
  
  [
  
  Va
  
  [
  
  ]] ≤ j <
  
  Ea
  
  [
  
  Va
  
  [
  
  + 1]]: if X[j] is false: C[j] <- C[threadId] + 1 F[j] <- trueCan represent boolean values as integersUnsafe operation?
  
  Slide24
  
  GPU-accelerated BFS
  
  CPU-side
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  call GPU kernel( F, X, C,
  
  Va
  
  ,
  
  Ea
  
  )
  
  GPU-side kernel
  
  pseudocode
  
  :
  
  if F[
  
  ] is true:
  
  F[
  
  ] <- false
  
  X[
  
  ] <- true
  
  for
  
  Ea
  
  [
  
  Va
  
  [
  
  ]] ≤ j <
  
  Ea
  
  [
  
  Va
  
  [
  
  + 1]]: if X[j] is false: C[j] <- C[threadId] + 1 F[j] <- trueCan represent boolean values as integersSafe! No ambiguity!
  
  Slide25
  
  Summary
  
  Tricky algorithms need drastic measures!
  
  Resources
  
  “Accelerating Large Graph Algorithms on the GPU Using CUDA” (Harish, Narayanan)
  
  Slide26
  
  Texture Memory
  
  Slide27
  
  “Ordinary” Memory Hierarchy
  
  http://www.imm.dtu.dk/~beda/SciComp/caches.png
  
  Slide28
  
  GPU Memory
  
  Lots of types!
  
  Global memory
  
  Shared memory
  
  Constant memory
  
  Slide29
  
  GPU Memory
  
  Lots of types!
  
  Global memory
  
  Shared memory
  
  Constant memory
  
  Must keep in mind:
  
  Coalesced access
  
  Divergence
  
  Bank conflicts
  
  Random serialized access
  
  Size!
  
  Slide30
  
  Hardware vs. Abstraction
  
  Slide31
  
  Hardware vs. Abstraction
  
  Names refer to
  
  manner of access
  
  on device memory:
  
  “Global memory”
  
  “Constant memory”
  
  “Texture memory”
  
  Slide32
  
  Review: Constant Memory
  
  64 KB available, 8 KB cache – small!
  
  Not
  
  const
  
  ”!
  
  Write to region with
  
  cudaMemcpyToSymbol
  
  ()
  
  Slide33
  
  Review: Constant Memory
  
  Downside:
  
  When all threads need different data: Extremely slow!
  
  Slide34
  
  Review: Constant Memory
  
  Example application: Gaussian impulse response (from HW 1):
  
  Not changed
  
  Accessed simultaneously by threads in warp
  
  Slide35
  
  Texture Memory (and co-stars)
  
  Another type of memory system, featuring:
  
  Avoid coalescing worries
  
  Interpolation
  
  (Other) fixed-function capabilities
  
  Graphics interoperability
  
  Slide36
  
  Fixed Functions
  
  Like GPUs in the old days!
  
  Still important/useful for certain things
  
  Slide37
  
  (i.e. cache line)
  
  Memory is linear!
  
  Applies to CPU, GPU L1/L2 cache,
  
  etc
  
  Slide38
  
  Slide39
  
  2D array manipulations:
  
  One direction goes “against the grain” of caching
  
  E.g. if array is stored row-major, traveling along “y-direction” is sub-optimal!
  
  Slide40
  
  Texture-Memory Caching
  
  Can cache “spatially!” (2D, 3D)
  
  Specify dimensions (1D, 2D, 3D) on creation
  
  1D applications:
  
  Interpolation, clipping (later)
  
  Caching when e.g. coalesced access is infeasible
  
  Slide41
  
  Texture Memory
  
  “Memory is just an unshaped bucket of bits”
  
  (CUDA Handbook)
  
  Need
  
  texture reference
  
  in order to:
  
  Interpret data
  
  Deliver to registers
  
  Slide42
  
  Texture References
  
  “Bound” to regions of memory
  
  Specify
  
  (depending on situation)
  
  :
  
  Access dimensions (1D, 2D, 3D)
  
  Interpolation behavior
  
  “Clamping” behavior
  
  Normalization
  
  Slide43
  
  Interpolation
  
  http://cuda-programming.blogspot.com/2013/02/texture-memory-in-cuda-what-is-texture.html
  
  Slide44
  
  Clamping
  
  http://cuda-programming.blogspot.com/2013/02/texture-memory-in-cuda-what-is-texture.html
  
  Slide45
  
  “CUDA Arrays”
  
  So far, we’ve used standard linear arrays
  
  “CUDA arrays”:
  
  (Designed specifically for texturing)
  
  Slide46
  
  Texture Memory
  
  Texture reference can be attached to:
  
  Ordinary device-memory array
  
  “CUDA array”
  
  Many more capabilities
  
  Slide47
  
  Texturing Example (2D)
  
  Slide48
  
  Texturing Example (2D)
  
  Slide49
  
  Texturing Example (2D)
explanation: The provided text extract is from a lecture presentation on GPU Programming, specifically Lecture 10. The document covers topics such as non-numerical algorithms, graph algorithms, and the use of texture memory in GPUs. It includes detailed explanations and pseudocode for algorithms like Breadth-First Search (BFS) and discusses various types of GPU memory, including global, shared, constant, and texture memory.
  
  The document does not contain a specific math question or a question and answer. It is primarily a set of slides that provide educational content on GPU programming concepts and techniques.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: CS 179: GPU Programming Lecture 10
  
  Embed code:
  
  CS 179: GPU Programming Lecture 10
  
  Download Presentation - The PPT/PDF document "CS 179: GPU Programming Lecture 10" is the property of its rightful owner. Permission is granted to download and print the materials on this web site for personal, non-commercial use only, and to display it on your personal computer provided you do not modify the materials and that you retain all copyright notices contained in the materials. By downloading content from our website, you accept the terms of this agreement.
  
  Presentations text content in CS 179: GPU Programming Lecture 10
  
  Slide1
  
  CS 179: GPU Programming
  
  Lecture 10
  
  Slide2
  
  Topics
  
  Non-numerical algorithms
  
  Texture memory
  
  Slide3
  
  GPUs – good for many numerical calculations…
  
  Slide4
  
  Graph Algorithms
  
  Slide5
  
  Graph Algorithms
  
  Graph G(V, E) consists of:
  
  Vertices
  
  Edges (defined by pairs of vertices)
  
  Complex data structures!
  
  How to store?
  
  How to work around?
  
  Are graph algorithms parallelizable?
  
  Slide6
  
  Given source vertex S:
  
  Find min. #edges to reach every vertex from S
  
  *variation
  
  Slide7
  
  Given source vertex S:
  
  Find min. #edges to reach every vertex from S
  
  (Assume source is vertex 0)
  
  *variation
  
  0
  
  1
  
  1
  
  2
  
  2
  
  3
  
  Slide8
  
  Given source vertex S:
  
  Find min. #edges to reach every vertex from S
  
  (Assume source is vertex 0)
  
  0
  
  1
  
  1
  
  2
  
  2
  
  3
  
  Sequential
  
  pseudocode
  
  :
  
  let Q be a queue
  
  Q.enqueue
  
  (source)
  
  label source as discovered
  
  source.value
  
  <- 0
  
  while Q is not empty
  
  v ←
  
  Q.dequeue
  
  ()
  
  for all edges from v to w in
  
  (v):
  
  if w is not labeled as discovered
  
  Q.enqueue
  
  (w)
  
  label w as discovered,
  
  w.value
  
  <-
  
  v.value
  
  + 1
  
  Slide9
  
  Given source vertex S:
  
  Find min. #edges to reach every vertex from S
  
  (Assume source is vertex 0)
  
  0
  
  1
  
  1
  
  2
  
  2
  
  3
  
  Sequential
  
  pseudocode
  
  :
  
  let Q be a queue
  
  Q.enqueue
  
  (source)
  
  label source as discovered
  
  source.value
  
  <- 0
  
  while Q is not empty
  
  v ←
  
  Q.dequeue
  
  ()
  
  for all edges from v to w in
  
  (v):
  
  if w is not labeled as discovered
  
  Q.enqueue
  
  (w)
  
  label w as discovered,
  
  w.value
  
  <-
  
  v.value
  
  + 1
  
  Runtime:
  
  O( |V| + |E| )
  
  Slide10
  
  Representing Graphs
  
  A: |V| x |V| matrix:
  
  A
  
  ij
  
  = 1 if vertices
  
  i,j
  
  O(V
  
  2
  
  Adjacent vertices noted for each vertex
  
  O(V + E) space
  
  Slide11
  
  Representing Graphs
  
  A: |V| x |V| matrix:
  
  A
  
  ij
  
  = 1 if vertices
  
  i,j
  
  O(V
  
  2
  
  ) space <- hard to fit, more copy overhead
  
  Adjacent vertices noted for each vertex
  
  O(V + E) space
  
  <- easy to fit, less copy overhead
  
  Slide12
  
  Representing Graphs
  
  Array
  
  E
  
  a
  
  : Adjacent vertices to vertex 0, then vertex 1, then …
  
  size: O(E)
  
  Array
  
  V
  
  a
  
  : Delimiters for
  
  E
  
  a
  
  size: O(V)
  
  0
  
  2
  
  4
  
  8
  
  9
  
  11
  
  1
  
  2
  
  0
  
  2
  
  0
  
  1
  
  3
  
  4
  
  2
  
  2
  
  5
  
  4
  
  0
  
  1
  
  2
  
  3
  
  4
  
  5
  
  Vertex:
  
  Slide13
  
  Given source vertex S:
  
  Find min. #edges to reach every vertex from S
  
  (Assume source is vertex 0)
  
  0
  
  1
  
  1
  
  2
  
  2
  
  3
  
  Sequential
  
  pseudocode
  
  :
  
  let Q be a queue
  
  Q.enqueue
  
  (source)
  
  label source as discovered
  
  source.value
  
  <- 0
  
  while Q is not empty
  
  v ←
  
  Q.dequeue
  
  ()
  
  for all edges from v to w in
  
  (v):
  
  if w is not labeled as discovered
  
  Q.enqueue
  
  (w)
  
  label w as discovered,
  
  w.value
  
  <-
  
  v.value
  
  + 1
  
  How to “parallelize” when there’s a queue?
  
  Slide14
  
  0
  
  1
  
  1
  
  2
  
  2
  
  3
  
  Sequential
  
  pseudocode
  
  :
  
  let Q be a queue
  
  Q.enqueue
  
  (source)
  
  label source as discovered
  
  source.value
  
  <- 0
  
  while Q is not empty
  
  v ←
  
  Q.dequeue
  
  ()
  
  for all edges from v to w in
  
  (v):
  
  if w is not labeled as discovered
  
  Q.enqueue
  
  (w)
  
  label w as discovered,
  
  w.value
  
  <-
  
  v.value
  
  + 1
  
  Why do we use a queue?
  
  Slide15
  
  BFS Order
  
  Drichel
  
  Here, vertex #s are possible BFS order
  
  Slide16
  
  BFS Order
  
  Drichel
  
  Permutation within ovals preserves BFS!
  
  Slide17
  
  BFS Order
  
  Queue replaceable if layers preserved!
  
  Drichel
  
  Permutation within ovals preserves BFS!
  
  Slide18
  
  Alternate BFS algorithm
  
  Construct arrays of size |V|:
  
  “Frontier” (denote F):
  
  Boolean array - indicating vertices “to be visited” (at beginning of iteration)
  
  “Visited” (denote X):
  
  Boolean array - indicating already-visited vertices
  
  “Cost” (denote C):
  
  Integer array - indicating #edges to reach each vertex
  
  Goal: Populate C
  
  Slide19
  
  Alternate BFS algorithm
  
  New sequential
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  for 0 ≤
  
  i
  
  < |
  
  Va
  
  |:
  
  if F[
  
  i
  
  ] is true:
  
  F[
  
  i
  
  ] <- false
  
  X[
  
  i
  
  ] <- true
  
  for all neighbors j of i:
  
  if X[j] is false:
  
  C[j] <- C[
  
  i
  
  ] + 1
  
  F[j] <- true
  
  Slide20
  
  Alternate BFS algorithm
  
  New sequential
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  for 0 ≤
  
  i
  
  < |
  
  Va
  
  |:
  
  if F[
  
  i
  
  ] is true:
  
  F[
  
  i
  
  ] <- false
  
  X[
  
  i
  
  ] <- true
  
  for
  
  Ea
  
  [
  
  Va
  
  [
  
  i
  
  ]] ≤ j <
  
  Ea
  
  [
  
  Va
  
  [i+1]]:
  
  if X[j] is false:
  
  C[j] <- C[
  
  i
  
  ] + 1 F[j] <- true
  
  Slide21
  
  Alternate BFS algorithm
  
  New sequential
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  for 0 ≤
  
  i
  
  < |
  
  Va
  
  |:
  
  if F[
  
  i
  
  ] is true:
  
  F[
  
  i
  
  ] <- false
  
  X[
  
  i
  
  ] <- true
  
  for
  
  Ea
  
  [
  
  Va
  
  [
  
  i
  
  ]] ≤ j <
  
  Ea
  
  [
  
  Va
  
  [i+1]]:
  
  if X[j] is false:
  
  C[j] <- C[
  
  i
  
  ] + 1
  
  F[j] <- trueParallelizable!
  
  Slide22
  
  GPU-accelerated BFS
  
  CPU-side
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  call GPU kernel( F, X, C,
  
  Va
  
  ,
  
  Ea
  
  )
  
  GPU-side kernel
  
  pseudocode
  
  :
  
  if F[
  
  ] is true:
  
  F[
  
  ] <- false
  
  X[
  
  ] <- true
  
  for
  
  Ea
  
  [
  
  Va
  
  [
  
  ]] ≤ j <
  
  Ea
  
  [
  
  Va
  
  [
  
  + 1]]: if X[j] is false: C[j] <- C[threadId] + 1 F[j] <- trueCan represent boolean values as integers
  
  Slide23
  
  GPU-accelerated BFS
  
  CPU-side
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  call GPU kernel( F, X, C,
  
  Va
  
  ,
  
  Ea
  
  )
  
  GPU-side kernel
  
  pseudocode
  
  :
  
  if F[
  
  ] is true:
  
  F[
  
  ] <- false
  
  X[
  
  ] <- true
  
  for
  
  Ea
  
  [
  
  Va
  
  [
  
  ]] ≤ j <
  
  Ea
  
  [
  
  Va
  
  [
  
  + 1]]: if X[j] is false: C[j] <- C[threadId] + 1 F[j] <- trueCan represent boolean values as integersUnsafe operation?
  
  Slide24
  
  GPU-accelerated BFS
  
  CPU-side
  
  pseudocode
  
  :
  
  Input:
  
  Va
  
  ,
  
  Ea
  
  , source (graph in “compact adjacency list” format)
  
  Create frontier (F), visited array (X), cost array (C)
  
  F <- (all false)
  
  X <- (all false)
  
  C <- (all infinity)
  
  F[source] <- true
  
  C[source] <- 0
  
  while F is not all false:
  
  call GPU kernel( F, X, C,
  
  Va
  
  ,
  
  Ea
  
  )
  
  GPU-side kernel
  
  pseudocode
  
  :
  
  if F[
  
  ] is true:
  
  F[
  
  ] <- false
  
  X[
  
  ] <- true
  
  for
  
  Ea
  
  [
  
  Va
  
  [
  
  ]] ≤ j <
  
  Ea
  
  [
  
  Va
  
  [
  
  + 1]]: if X[j] is false: C[j] <- C[threadId] + 1 F[j] <- trueCan represent boolean values as integersSafe! No ambiguity!
  
  Slide25
  
  Summary
  
  Tricky algorithms need drastic measures!
  
  Resources
  
  “Accelerating Large Graph Algorithms on the GPU Using CUDA” (Harish, Narayanan)
  
  Slide26
  
  Texture Memory
  
  Slide27
  
  “Ordinary” Memory Hierarchy
  
  http://www.imm.dtu.dk/~beda/SciComp/caches.png
  
  Slide28
  
  GPU Memory
  
  Lots of types!
  
  Global memory
  
  Shared memory
  
  Constant memory
  
  Slide29
  
  GPU Memory
  
  Lots of types!
  
  Global memory
  
  Shared memory
  
  Constant memory
  
  Must keep in mind:
  
  Coalesced access
  
  Divergence
  
  Bank conflicts
  
  Random serialized access
  
  Size!
  
  Slide30
  
  Hardware vs. Abstraction
  
  Slide31
  
  Hardware vs. Abstraction
  
  Names refer to
  
  manner of access
  
  on device memory:
  
  “Global memory”
  
  “Constant memory”
  
  “Texture memory”
  
  Slide32
  
  Review: Constant Memory
  
  64 KB available, 8 KB cache – small!
  
  Not
  
  const
  
  ”!
  
  Write to region with
  
  cudaMemcpyToSymbol
  
  ()
  
  Slide33
  
  Review: Constant Memory
  
  Downside:
  
  When all threads need different data: Extremely slow!
  
  Slide34
  
  Review: Constant Memory
  
  Example application: Gaussian impulse response (from HW 1):
  
  Not changed
  
  Accessed simultaneously by threads in warp
  
  Slide35
  
  Texture Memory (and co-stars)
  
  Another type of memory system, featuring:
  
  Avoid coalescing worries
  
  Interpolation
  
  (Other) fixed-function capabilities
  
  Graphics interoperability
  
  Slide36
  
  Fixed Functions
  
  Like GPUs in the old days!
  
  Still important/useful for certain things
  
  Slide37
  
  (i.e. cache line)
  
  Memory is linear!
  
  Applies to CPU, GPU L1/L2 cache,
  
  etc
  
  Slide38
  
  Slide39
  
  2D array manipulations:
  
  One direction goes “against the grain” of caching
  
  E.g. if array is stored row-major, traveling along “y-direction” is sub-optimal!
  
  Slide40
  
  Texture-Memory Caching
  
  Can cache “spatially!” (2D, 3D)
  
  Specify dimensions (1D, 2D, 3D) on creation
  
  1D applications:
  
  Interpolation, clipping (later)
  
  Caching when e.g. coalesced access is infeasible
  
  Slide41
  
  Texture Memory
  
  “Memory is just an unshaped bucket of bits”
  
  (CUDA Handbook)
  
  Need
  
  texture reference
  
  in order to:
  
  Interpret data
  
  Deliver to registers
  
  Slide42
  
  Texture References
  
  “Bound” to regions of memory
  
  Specify
  
  (depending on situation)
  
  :
  
  Access dimensions (1D, 2D, 3D)
  
  Interpolation behavior
  
  “Clamping” behavior
  
  Normalization
  
  Slide43
  
  Interpolation
  
  http://cuda-programming.blogspot.com/2013/02/texture-memory-in-cuda-what-is-texture.html
  
  Slide44
  
  Clamping
  
  http://cuda-programming.blogspot.com/2013/02/texture-memory-in-cuda-what-is-texture.html
  
  Slide45
  
  “CUDA Arrays”
  
  So far, we’ve used standard linear arrays
  
  “CUDA arrays”:
  
  (Designed specifically for texturing)
  
  Slide46
  
  Texture Memory
  
  Texture reference can be attached to:
  
  Ordinary device-memory array
  
  “CUDA array”
  
  Many more capabilities
  
  Slide47
  
  Texturing Example (2D)
  
  Slide48
  
  Texturing Example (2D)
  
  Slide49
  
  Texturing Example (2D)
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text extract is from a lecture presentation on GPU Programming, specifically Lecture 10. The document covers topics such as non-numerical algorithms, graph algorithms, and the use of texture memory in GPUs. It includes detailed explanations and pseudocode for algorithms like Breadth-First Search (BFS) and discusses various types of GPU memory, including global, shared, constant, and texture memory.
  
  The document does not contain a specific math question or a question and answer. It is primarily a set of slides that provide educational content on GPU programming concepts and techniques.
  
  Label: no-question