Mattan’s raw preparation notes

Lecture 24 (11/24/2007) — Data Parallel Memory System

()

Lecture’s Outline

  • Lecture’s Outline
  • Announcements and Lab3
    • Lab 3 focuses on:
    • Lab 3 does not focus on:
    • Memory Hierarchy Question
    • Lab3 Hints
  • Feedback on Lab2
    • Things that people did well
    • Common problems
    • Having Many warps
    • Software pipelineing
    • Question: What about the shared memory?
  • How can you increase locality
    • Increase locality by blocking for reuse.
    • Increase locality by blocking for reuse (Unstructured representation)
    • Partitioning or Domain Decomposition (Another keyword)
    • Geometric partitioning
    • Graph partitioning
    • Space filling curves
    • Meshes
    • Streaming Meshes

Announcements and Lab3

There are some principles that students are supposed to experience in lab3:

Lab 3 focuses on:

  • locality+hierarchy in programming
  • parallelism and locality
  • execution model of Sequoia and Cell
  • performance modeling;
    • figure out the results, what matches and what does not
    • know what should be optimized

Lab 3 does not focus on:

  • Different ways to parallelize
  • performance optimization
  • Don’t waste a lot of time on doing superficial things.
  • Ask me if you’re not sure if something is superficial
  • Performance modeling is really important bit, but we’re looking for back of the envelope stuff. you should figure out the results to find out what matches and what does not match your prediction and expectations.
  • Seriously, be minimalistic in this lab
  • Come see me about project updates!
  • Lab 2 grades will be uploaded today.
  • Next week is going to be wrap up and loose ends (and a bit about future directions)
    • I will quickly go over all current scribe notes
      • please let me know if you’re done with yours
    • I’ll also link one nice paper that I would like to discuss a little bit.

Memory Hierarchy Question

  • What is memory model for clusters of four PS3 systems?
    • We do not need to model the potential virtual level between LS and DRAM. The cluster is some thing with one virtual level above four of PS3 memory hierarchy models.

Lab3 Hints

  • SPMD is about How to distribute tasks among resources
  • Nested Mappar(Nested SPMD) means SPMD both on top and bottom level
  • For cluster of four PS3 systems SPMD over 24 is not ok. It should come down to each PS3.
  • The mappar loop constraints depends on how many parallel resources are you going to spread over.

Feedback on Lab2

Need some intro, this just comes out of nowhere Lab2 was about implementing the bin partitioning problem on GPU with CUDA programming language. The lab was partitioned in three subsection and took about more than 3 weeks. Students were supposed to write CUDA programs and compute the results of different problem with different number of bins each. Here the feedback is given to the students, all common mistakes and good solutions are presented as belows:

Things that people did well

  • Allocated histogram bins vertically to avoid bank conflicts
  • Experimented with number of bins/ (thread blocks)
  • Experimented with bin/pixel partitioning
  • Tried out some shared memory to reduce BW when partitioning bins by reducing the number of access to memory
    • Loading to shared memory then loading to pixels.
  • Many students Ran into 16KB problem:it turned out that 16KB size of the shared memory is not really 16KB as stated in documents but just 14.5 KB. Some of the students tried allocating a few bins in registers.
  • Students Ran into image not fitting in device memory for other two machines (Kandinsky and Chagall) the image just fits on Mondrian memory.
    • My bad on that one, I really apologize.
  • Different ways of doing reductions.

Common problems

This is also feedback

  • A lot of people had divides all over the place. Make constants constant and use >> to divide by powers of 2.
  • in value by value division use literal constant
  • gcc will turn to constant. What will happen to mpcc?
  • Sorry about the image not fitting in GPU memory.
  • Didn’t think about what the expected performance might be (makes optimizing really hard).
  • BW was the issue and other than coalescing, very little discussion of it. Could have tried to maximize both BW and reuse by having many threads gather, but only a few threads compute. Should have also spread out the gather across all memory banks (ROPs).
  • estimating performance
  1. LD pixel
  2. bin = pixel >> BIN_SHIFT (BIN_SHIFT==log2(MAX_VAL/NUM_BINS)
  3. LD hist[bin]
  4. hist[bin]++
  5. ST hist[bin]
  6. Check Loop (perhaps test branch condition)
  7. branch
  • So 6–7 cycles for every pixel load, and can do 128 “cycles” at 1.35GHz:

~25 GW/sec == 100GB/s of ints or 50GB/s for shorts

  • Use short instead of int data type.
  • Desktop can sustain ~8GB/s so best speedup should be about 5 - 10x

Conclusion — maximize locality to reduce BW. Minimize re-reading of pixels and always coalesce (even when doing shorts). Also need to make sure all memory banks are being used.

I don’t really understand this — do you have more detail? this what is written in preparation notes Also need to hide latency of course and deal with reductions.

  • How about the CPU?
    • is it memory BW bounded?
    • or performance bounded?
    • 3 cycles per loop on cpu and in each loop one load from off chip memory so it is memory BW bounded. The ratio is 10 to one so speed up is not more than 10. Some of the groups gave speed up about 13 and that is impossible.

Having Many warps

  • If try to give each their portion of bins this leads to more locality without sacrificing memory map.
  • Multiple blocks results to pipeline on SPEs.

Software pipelineing

  • You want to have software pipelining
  • you need to have multiple blocks
  • you need to use different banks in order to avoid conflicts to access the same bank memory banks (ROPs) I guess
  • Do nor access the same bank and start to use different stream processor.

Question: What about the shared memory?

  • Divide bins and pixels. The optimal size is 8K+4 byte ??
  • what about the Buffer limitation? you have to search about what you get and what you loose for example software pipelining will reduce the size to half which means decreasing the size of available buffer to half but provides pipelining instead. If you look at this problem from the other side BW limits our performance. what about having two separate blocks?
    • read with threads and synchronize (Gathering)
      1. adding threads (Computing)
      2. adding blocks (Scattering)
  • You can get kernel speed up by moving the data to GPU and reuse that data
  • CPU and more GPU
  • Not CPU-GPU-CPU-GPU
  • Don’t forget that running a kernel does not restrict you from transferring data.

Title is not as good as the outline This whole section needs more words and explanations — I’m sure I talked about this for a while. This is why the notes are helpful — it’s because my slides/prep does not have enough detail to follow as is.

How can you increase locality

Increase locality by blocking for reuse.

By blocking the data into smaller blocks the problem becomes a smaller problem for a smaller data set. Blocking is dividing the input space into neighborhoods. Smaller data set can be stored in smaller but faster memories which helps the computation become faster and avoids expensive communication costs. There are some obvious examples that has shown the effectiveness of blocking of the data on the performance. In this course the students have experienced two famous applications which take advantage of blocking.

  • Matrix multiply
  • Histogram

The above applications are structured data sets.

  • What about unstructured data?

To observe how the blocking is done on unstructured data in other applications, some examples can be shown.

*Increase locality by blocking for reuse (Unstructured representation)

  • Geometry
  • Mesh
  • Graphs
  • Adjacency matrix

Partitioning or Domain Decomposition (Another keyword)

This is the same as blocking — really just another name in this context, like “tiling” would be yet another name.

  • First used to divide parallel work

Blocking as mentioned before can make a big problem divided to smaller problems. If the work can be done in parallel and no communication between sub problems is needed this is as dividing a big problem among multi functional units to gain speedup.

  • Load balance

Load balancing for handling the communication and utilization of functional units is needed. The problem should not be divided into too many small sub problems which makes the communication expensive.

  • Minimize communication

The cost of communication is always heavy. Blocking into rational number of smaller sub problems reduces unnecessary communications. Minimize communication to increase locality

Geometric partitioning

  • Kernighan-Lynn
  • Cuthill-McGee

(I found almost nothing in my notes) The geometric partitioning method will divide the space in smaller regions characterized by simple geometric forms.

Graph partitioning

Graphs are one of the most widely used mean to represent the relation between elements in the domain-space.

  • Spectral methods
  • Approximate
    • METIS / ParMETIS (Mattan wanted to put up the links)
    • Jostle
    • Chaco
    • Zoltan
    • PARTY
    • PARTI

all of these methods are based on General divide and conquer problem. These methods will do expensive processes in small representation and then project out.

  • How do we represent a graph?
    • Adjacensy Matrix

The Adjacency Matrix is a way to store graphs. Each node represents a row and a column in this matrix. If two nodes i and j are connected the (j,j)th element of the matrix is a number other than zero. In each graph not all the nodes are connected to each other. This is why sparse matrices are so important because almost all adjacency matrices are holding too many zeros and they are sparse matrices. Blocking a sparse matrix is an important issue. Here is an examples of blocking a sparse matrix. As it can be seen, after reordering , the Adjacensy matrix becomes more symmetric and consistent.



figure of blocking the sparse matrix example

  • There are two common graph based presentations
    • Breath first search graph
    • Depth first search graph

There is same amount of work in each partition

In these graphs the effect of reordering on different application with different number of elements in the input sapce domain is presented. For Water molocules , by reordering no speed up is gained by METIS compared to the original scheme. For finite element mesh METIS works significantly better. In bigger input space domaing, METIS and original scheme gain speed up in same degree.







!!!Space filling curves figure of space filling curves

  • Must have live ordering
  • KD tree is a K dimensional tree (then???)
  • The cardinality between numbers in the range of 0 ad 1 is the same for 2D matrices What does this mean?

The highly counterintuitive result that the cardinality of a unit interval is the same as the cardinality of any finite-dimensional manifold.

  • It is a recursive algorithm which can fill the whole space domain with different precision.

when there are no elements in a region, that region can be presented as a bigger region compared to other regions without a very precise modeling of its smaller sub-regions. But when in a region more samples exist, the space filling is done more precisely by dividing that region to smaller sub-regions and modeling those regions with smaller curves. This precision is gained by going deep in recursion.

The main advantages of this partition method are:

  • It is fast compared to graph partitioning heuristics,
  • It runs in parallel,
  • It requires no administration and no storage of processor neighborhoods.
  • The knowledge of the separators is enough to compute where to find a node and which processor to ask for it.







Meshes

The triangular mesh can be divided in smaller regions. Within each region there are interaction between elements. There is also interaction between elements of different regions. It works for more complicated data structures

  • The m-body data is represented by triangular mesh.

In the other word Surface/Vloume can be interpreted as (interaction between regions)/(interaction between elements inside any region) What is this?

  • Partial Differential Equations
  • Space around the wing

Streaming Meshes

  1. Gather
  2. Compute
  3. Scatter
  • In the streaming algorithms you read finite number of inputs to compute the output

Illustrations of the coherence in the layout of a mesh: the layout after reordering the vertex and triangle arrays using spectral sequencing. The large rendering color-codes triangles based on their position in the array. The layout diagram connects triangles that share the same vertex with horizontal line segments (green) and vertices referenced by the same triangle with vertical line segments (gray). The dragon mesh reordered by (a) a depth-first compressor, (b) a breadth-first compressor, © z-order curve, (d) spatial sort, and (e) spectral sequencing.



Layout and stream measures for the meshes.The skip, vertex span, and triangle width of the original vertex order, and the vertex width and triangle span of the original triangle order (which can be quite incoherent) is reported. Starting from the original layout, the front width and span of pre-order streaming meshes created by interleaving, vertex compaction, and triangle compaction is reported. The rightmost columns highlight the improvements of vertex-compact streams obtained by reordering both triangles and vertices using spectral sequencing, geometric sorting along the axis of maximum extent is also listed below.