EE382V Lecture 21 - Programming the CELL BE (II)


()

Cell Programming Challenges

  • separate code for PPE & SPE
    • explicit synchronization
  • SPE can access memory through DMAs
    • DMA is asynchronous, prep-instructions are part of SPE code
    • SW manages consistency / coherency, also alignment, granularity, and bank conflicts
  • SPE must be programmed with SIMD
    • lots of pipeline challenges left up to programmer or compiler

Sequoia overview

Sequoia: hierarchy aware programming

  • a language designed for stream programming and deep memory hierarchy
  • exposes abstract memory hierarchy to programmers
    • Compiler often can’t do well with deep memory hierarchy
    • abstract memory hierarchy
      • memory hierarchy aware programming in a generic way
      • tune for a specific machine later
  • benchmark runs well on CELL and cluster of PCs

Key challenge => communication, not parallelism

  • hiding latency
    • generic program structure to hide memory latency
      1. fetch data
      2. compute on data
      3. initiate write results
    • overlap prefetch next data with compute data



  • then compute on the next batch without stall
  • managing Bandwidth, which is very precious resource
    • stall only when compute < bandwidth (always maximize use of scarce resource)



Streaming

Streaming involves structuring algorithms as collections of independent [locality cognizant] computations with well-defined working sets.

  • structuring on any scale
    • keep temporaries in registers
    • cache, scratch pad blocking
    • message passing on a cluster
    • out-of-core algorithm
  • efficient program exhibits this scales at many levels

Sequoia goal

  1. facilitate the development of hierarchy aware stream programming
  2. remain portable across machine
    • programming with abstract memory hierarchy
    • then later tune it for a specific machine
    • works with many program, but sometimes not
  3. pragmatic approach
    • provides stream constructs, which can be implemented efficiently without requiring advanced compiler technology
    • don’t need to wait 10 to 15 years of compiler technology advancements

everything in bulk granularity, so that latency can be hid

Sequoia detail

abstract memory hierarchy model : a tree

  • multi-level memories
  • ALUs only on the leaf cell
    • don’t allow to computation node in inner nodes (except for minimal manipulation to do control)
    • provides simple interface: manages bulk transfer efficiently
  • Not all memory level needs to be physical; virtual memory level sometimes, e.g. base level of cluster PCs; virtual level aggregating the lower levels of memories



Sequoia programming example: matrix multiplication



Sequoia tasks: basic building blocks of Sequoia program



  • task variants: inner or leaf
    • inner task (e.g. matmul:inner( … ) { … } )
      • recursively call matmul task on submatrices, until it reaches leaf task
    • leaf task (e.g. matmul:leaf( … ) { … } )
      • a task for the actual computation
  • call structure: inner task calls either itself or leaf task



  • task (or a function) call semantics: Call By Value Return
    • copy data from higher level to lower level
    • isolated computation
    • return (output) data is copied back to the higher level
    • data transfers can be optimized (semantics of data copying does not necessarily mean the physical data copy, see copy elimination part)
    • data transfers are bulk transfers
  • task working data set resides at a single location in abstract tree
    • leaf task has all inputs/outputs copied to local block, hence its operation is completely isolated
    • input data transfer / kernel computation / output data transfer can be organized with software pipelining
  • arguments: in/out, explicitly define input / output
  • parameters: size of working data set, could be tunable
    • tunable parameters: define the block sizes, can be tuned for a specific architecture later
  • since we have hierarchy of memory, there is hierarchy of tasks also

primitive operations and synchronizations

  • mappar: parallel operations for all iterations
    • a synchronization is implied at the end of iteration space
  • mapseq: sequential operations for each iteration
    • a synchronization is implied at the end of each iteration
  • mapreduce: provided reduction function

Sequoia does not need explicit synchronizations such as mutex, lock, …

Sequoia programming

  • programmers should make sure no input/output aliasing within or across tasks, and additionally no output aliasing across different tasks
  • programming should be done with parallelism
  • no mutexes, no traditional way of explicit synchronization
    • this programming model does not need to have such ways of synchronization
    • if we have, very often it (mutex based fine grain synchronization) prevents to make bulk operations
      • not an efficient way of stream programming
  • tasks express multi-levels of parallelism
    • multi-dimensional
    • hierarchical
  • interacting threads; e.g. multi threads updating a single memory location, or threads receives data from other threads …
    • not allowed, same reason as we don’t have mutex

Parallelism / Locality in Sequoia

  • DLP: mappar operation inherently supports data level parallelism
  • ILP: ILP is not directly supported in Sequoia, but it still exists within a leaf task (e.g. CELL leaf task utilizes ILP and SIMD)
  • TLP: implicitly supported in dependence of operations, allows pipeline parallelism within a mappar (but the current compiler may not interchange loops)
  • Data locality: hierarchy of memories
  • producer - consumer locality: depends on how it is programmed
    • examples) two leaf tasks L1, L2; L2 gets the output of L1

example 1) if we put L1 and L2 in two different mappar blocks, it is not easy to take advantages of producer-consumer locality

mappar( … ) {
L1;
}
mappar( … ) {
L2;
}
  • Barrier is assumed between two different mappars, compiler cannot make inter mixed leak tasks scheduling from two sequential mappars

example 2) if we put L1 and L2 in the same mappar block, it is possible to exploit such locality

mappar( … ) {
L1;
L2;
}

Sequoia Summary

  • abstract memory hierarchy
  • isolation / parallelsim
  • explicit communications
  • bulk operations
  • parameterized portability

Sequoia mapping to real software

  • Sequoia compiler
    • input:
      • Sequoia task definitions, parametrized with tunables
      • mapping specifications
    • output:
      • task instances, not parameterized any more
      • tunable parameters are determined at compile time → no dynamically tunable parameters
    • one Sequoia program can have multiple mapping specifications to generate multiple instances for multiple platform (portability)
      • traditionally, this has been done with many header files, #ifdef …
      • Sequoia simplifies it and provide good portability, and opportunities for optimizations (through tunable parameters)
  • static compiler optimizations
    • copy eliminations
      • constant array, put this in the local memory … don’t copy back and forth
      • producer - consumer locality, don’t need to copy data back to higher level, then copy again ..
    • DMA transfer coalescing
    • operation hoisting
    • array allocation / packing / padding
    • scheduling (tasks and DMAs)

benchmarks: CELL and 16 node clusters

same code different systems, just mapping files are different

applications with low locality, e.g. saxpy

  • CELL: waiting memory most of time
  • Cluster: Sequoia overhead / computation occupies most of time

applications with high locality, e.g. matrix multiplication with blocking

  • in general, compute utilization is very high
  • CELL: copy elimination is static by compiler
  • Cluster: copy elimination is runtime and more complicated

Speedup vs. number of processing elements

  • CELL:
    • some application performances are limited by memory bandwidth → bad scaling
    • good scaling with high locality applications
  • GFLOPS rating is comparable to hand coded applications

Portability

  • only FFT3D were modified slightly for CELL
  • For all others the same code was used
  • some progress in automatic tuning is in progress

Finally, Sequoia for CELL programming

Sequoia manges thread, Synchronization, Communication, DMA, Local Storage, and scheduling

But it doesn’t help much with SPE code => use low-level compiler tools

Also, it doesn’t help bank alignment

Other cell programming

IBM tools

  • CELL SDK 3.0
    • communication, synchronization, DMA by API call
    • intrinsics for SPE, SPE code should be optimized by hand
    • GCC and XLC are supported
  • Accelerated Library Framework, ALF
    • APIs for work queue based model
  • Octopiler, single source XLC for CELL
    • open MP directives
    • relies on software cache

Other industry solutions

  • Mercury Systems; array based language
    • highly tuned BLAS/FFT
  • RapidMind
    • dynamically compiled program relies on array type

Academic researches

  • Sequoia
  • Cell superscalar
    • open mp like language
    • runtime applies superscalar style optimization and scheduling
  • Charm ++
    • very old tool

Comparing CELL and GPU

CELL

  • never allows to access global memory directly
  • no random access to global memory
  • S/W manages task scheduling
  • designed for bulk operations

GPU:

  • more complicated memory structure; shared memory, global memory, texture cache, …
  • H/W manages threads to hide latency

Sequoia is more suitable to CELL style architecture, supporting bulk operations and simpler hierarchical memory structure