Super Computing 2007 (A. Shelton's Notes)

Tutorial: Introduction to Scientific Workflow Management and the Kepler System

• One of the presenters mentioned that for complicated workflows, people employ specialists just to produce them in Kepler. This is bad and hints that Kepler is okay for simple stuff (e.g. basic calibration, out of the box reduction routines, etc.), but maybe unwieldy for complicated stuff (e.g. custom science algorithms, etc.).
• REAP
  • REAP (Realtime Environment for Analytical Processing) is an NSF-funded cyberinfrastructure development project, focused on creating technology in which scientific workflows tools can be used to access, monitor, analyze and present information from field-deployed sensor networks, for both the oceanic and terrestrial environments, and across multiple spatiotemporal scales. This near real-time environment for analytical processing will provide an open-source, extensible and customizable framework for designing and executing scientific models that consume data streams from sensor networks. Project investigators will combine the real-time data grid being constructed through other projects (ROADNet, CENS ESS, OPeNDAP, EarthGrid) with the scientific workflow system Kepler (http://kepler-project.org). These open-source software frameworks represent considerable prior investments.

Tutorial: A Tutorial Introduction to High Performance Analytics and Workflow on Grids

• Computation Institute, University of Chicago
• Swift
  • Swift is a system for the rapid and reliable specification, execution, and management of large-scale science and engineering workflows. It supports applications that execute many tasks coupled by disk-resident datasets - as is common, for example, when analyzing large quantities of data or performing parameter studies or ensemble simulations.
  • open source
• PMML - Good for services that have to run 24/7 without going down
  • The Predictive Model Markup Language (PMML) is a mark up language for statistical and data mining models.
• Globus
  • The Globus Alliance is a community of organizations and individuals developing fundamental technologies behind the "Grid," which lets people share computing power, databases, instruments, and other on-line tools securely across corporate, institutional, and geographic boundaries without sacrificing local autonomy.
  • The Globus Toolkit is an open source software toolkit used for building Grid systems and applications. It is being developed by the Globus Alliance and many others all over the world. A growing number of projects and companies are using the Globus Toolkit to unlock the potential of grids for their cause.
• There are two groups at this tutorial - analytics and swift
  • The analytics people (Grossman) just want to glue together analytics with use of grids to get the science/results from the data. This is pretty much what our data reduction users want as well. Common views - easy programming/creation of 90% of the workflow, access to "blackbelt" facilities for the interesting 10%. Their still trying to figure it out as well.
• Lots of scientific workflow packages out there. Indicates that nothing has really caught on yet, people are still flailing about trying to settle on the best approach in terms of ease of use Vs. power.

Tutorial: Introduction to OpenMP

• OpenMP is a specification, not a particular implementation, current is 2.5, soon to come 3.0
• From wikipedia (fount of all knowledge) - http://en.wikipedia.org/wiki/OpenMP
  • The OpenMP (Open Multi-Processing) is an application programming interface (API) that supports multi-platform shared memory multiprocessing programming in C/C++ and Fortran on many architectures, including Unix and Microsoft Windows platforms. It consists of a set of compiler directives, library routines, and environment variables that influence run-time behavior. Jointly defined by a group of major computer hardware and software vendors, OpenMP is a portable, scalable model that gives programmers a simple and flexible interface for developing parallel applications for platforms ranging from the desktop to the supercomputer. An application built with the hybrid model of parallel programming can run on a computer cluster using both OpenMP and Message Passing Interface (MPI).
• Patterns for Parallel Programming
• Programming model: fork-join parallelism, master -> team of threads (a team member can in turn become a master to its own team) -> master -> etc
• Computational model: multiple processing elements, shared address space, multiple light weight processes
• Interesting note - parallelism CPU Vs. GPU
  • CPU - synchronization is expensive, GPU - almost free
  • CPU - thread creation overhead can be expensive, GPU - almost free
• Constructs Vs. Regions: constructs occupy a single compilation unit while a region can span multiple source files.
  • Most of the constructs are compiler directives.
    • For C and C++, the directives are pragmas with the form: #pragma omp construct [clause [clause]…]
  • Most constructs apply to structured blocks.
    • Structured block: a block with one point of entry at the top and one point of exit at the bottom.
    • The only "branch" allowed is exit() in C/C++.
    • In C/C++: a block is a single statement or a group of statements between brackets {}
• An optional if clause causes the parallel region to be active only if the logical expression within the clause evaluates to true. #pragma omp parallel if(N>1000)
• The loop Work-Sharing construct splits up loop iterations among the threads in a team. #pragma omp for
  • By default, there is a barrier at the end of the "omp for". Use the "nowait" clause to turn off the barrier. #pragma omp for nowait
  • The schedule clause affects how loop iterations are mapped onto threads
    • schedule(static [,chunk])
      • Deal-out blocks of iterations of size "chunk" to each thread.
      • Pre-determined and predictable by the programmer
      • Lowest overhead
    • schedule(dynamic[,chunk])
      • Each thread grabs "chunk" iterations off a queue until all iterations have been handled.
      • Unpredictable, highly variable work per iteration
      • High overhead
    • schedule(guided[,chunk]) rarely used
      • Threads dynamically grab blocks of iterations. The size of the block starts large and shrinks down to size "chunk" as the calculation proceeds.
      • Special case of dynamic to reduce scheduling overhead
    • schedule(runtime)
      • Schedule and chunk size taken from the OMP_SCHEDULE environment variable
      • Keeps you from having to recompile while playing
• The Sections work-sharing construct gives a different structured block to each thread.
  • #pragma omp sections
• The master construct denotes a structured block that is only executed by the master thread. The other threads just skip it (no synchronization is implied).
  • #pragma omp master
  • #pragma omp barrier
• The single construct denotes a block of code that is executed by only one thread. A barrier is implied at the end of the single block.
  • #pragma omp single
• Combined parallel/work-share construct
  • Shortcut: Put the "parallel" and the workshare on the same line
• There is also a "parallel sections" construct.
• Data environment
  • Shared Memory programming model - most variables are shared by default, global variables are shared among threads
  • But not everything is shared
    • Stack variables in sub-programs called from parallel regions are private
    • Automatic variables within a statement block are private
  • One can selectively change storage attributes constructs using the following clauses:
    • shared
    • private
      • The value of a private inside a parallel loop can be transmitted to a global value outside the loop with: lastprivate
      • Special case of private - firstprivate
        • Initializes each private copy with the corresponding value from the master thread
    • threadprivate
      • Makes global data private to a thread.
      • Different from making them private
      • *Extremely powerful construct for making your program thread-safe".
      • You initialize threadprivate data using a copyin clause.
    • The default status can be modified with: DEFAULT (PRIVATE | SHARED | NONE)
  • Combine an accumulation operation across threads: reduction (op : list)
    • General Operands: +, *, -
    • C/C++ Only: &, |, ^, &&, ||
    • For good OpenMP implementations, reduction is more scalable than critical.
• Synchronization
  • High level synchronization
    • critical
      • Only one thread at a time can enter a critical region.
    • atomic
      • Atomic provides mutual exclusion execution but only applies to the update of a memory location
    • barrier
      • Each thread waits until all threads arrive.
      • Barriers are implied on the following constructs: end parallel, end do (except when nowait is used), end sections (except when nowait is used), end single (except when nowait is used)
    • ordered
      • The ordered region executes in the sequential order.
      • Presenter uses this for debugging of race conditions. If you need this in your parallel production code, you need to rethink your algorithm.
  • Low level synchronization
    • flush
      • The flush construct denotes a sequence point where a thread tries to create a consistent view of memory for a subset of variables called the flush set.
    • locks (both simple and nested)
      • Sets a point of mutual exclusion, much like critical, but much lower level
        • E.g. Use locks (over critical) when needing mutual exclusion when buried in a data structure
      • Simple: omp_init_lock(), omp_set_lock(), omp_unset_lock(), omp_test_lock(), omp_destroy_lock()
      • Nested: omp_init_nest_lock(), omp_set_nest_lock(), omp_unset_nest_lock(), omp_test_nest_lock(), omp_destroy_nest_lock()
      • Note: a thread always accesses the most recent copy of the lock, so you don't need to use a flush on the lock variable.
      • Can be very risky - deadlocks
• Run-time Environment
  • Commonly used routines
    • Modify/Check the number of threads: omp_set_num_threads(), omp_get_num_threads(), omp_get_thread_num(), omp_get_max_threads()
    • Are we in an active parallel region? omp_in_parallel()
    • Do you want the system to dynamically vary the number of threads from one parallel construct to another? omp_set_dynamic, omp_get_dynamic()
    • How many processors in the system? omp_get_num_procs()
  • Commonly used environmental variables
    • Set the default number of threads to use. OMP_NUM_THREADS int_literal
    • Control how "omp for schedule(RUNTIME)" loop iterations are scheduled. OMP_SCHEDULE "schedule[, chunk_size]"
• MPI: An API for Writing Clustered Applications
  • A library of routines to coordinate the execution of multiple processes.
  • Provides point to point and collective communication in Fortran, C and C++
  • Unifies last 15 years of cluster computing and MPP practice
  • Simple way to differentiate - OpenMP within a host, MPI across hosts
  • How do people mix MPI and OpenMP?
    • Create the MPI program with its data decomposition
    • Use OpenMP inside each MPI process
  • Problems with mixing MPI and OpenMP
    • Messages are sent to a process on a system not to a particular thread.
      • Not all MPIs are threadsafe. MPI 2.0 has the following thread modes:
        • MPI_Thread_Single, MPI_Thread_Funneled, MPI_Thread_Serialized, MPI_Thread_Multiple
      • Can request and test thread modes with MPI_init_thread
    • Environment variables are not propagated by mpirun. You'll need to broadcast OpenMP parameters and set them with the library routines.
    • Keep message passing and threaded sections of your program separate.
      • Setup message passing outside OpenMP regions
      • Surround with appropriate directives (e.g. critical section or master)
      • For certain applications depending on how it is designed it may not matter which thread handles a message.
        • Beware of race conditions though if two threads are probing on the same message and then racing to receive it.
    • Hybrid OpenMP/MPI works, but is it worth it?
      • Literature (L. Adhianto and Chapman, 2007) is mixed on the hybrid model: sometimes its better, sometimes MPI alone is best.
      • There is potential for benefit to the hybrid model
        • MPI algorithms often require replicated data making them less memory efficient.
        • Fewer total MPI communicating agents means fewer messages and less overhead from message conflicts.
        • Algorithms with good cache efficiency should benefit from shared caches of multi-threaded programs.
        • The model maps perfectly with clusters of SMP nodes.
      • But really, it's a case by case basis and to large extent depends on the particular application.
• Cluster OpenMP
  • Cluster OpenMP is a simple extension to OpenMP that lets a subset of OpenMP programs run on a cluster.
  • It is released with the Intel compilers (starting with 9.1).
  • Suitable Programs:
    • Programs that scale successfully with OpenMP on SMP
    • Programs that have good data locality
    • Programs that use synchronization sparingly

Tutorial: Advanced Topics in OpenMP

• Level-setting: a rapid overview of OpenMP
  • OpenMP based upon SMP directive standardization efforts PCF and aborted ANSI X3H5 - late 80's
  • OpenMP 3.0 due in 2007
• Note: You can't assume that you'll get the number of threads you request.
• The OpenMP Memory Model and the flush construct
  • flush denotes a sequence point where a thread tries to create a consistent view of memory for a subset of variables call the flush set
  • The flush operation does not actually synchronize different threads. It just ensures that a thread's values are made consistent with main memory.
  • Shared memory is understood in terms of:
    • Coherence: Behavior of the memory system when a single address is accessed by multiple threads.
      • You can not reference another thread's private variables... even if you have a shared pointer between the two threads.
      • User must keep track of the privateness of pointer dereferences in nested parallel regions.
    • Consistency: Orderings of accesses to different addresses by multiple threads.
      • Sequential Consistency:
        • In a multi-processor, ops (R, W, S) are sequentially consistent if:
          • They remain in program order for each processor.
          • They seen to be in the same overall order by each of the other processors.
        • Program order = code order = commit order
      • Relaxed consistency:
        • Remove some or the ordering constrains for memory ops (R, W, S).
      • OpenMP 2.5 defines consistency as a variant of weak consistency.
        • S ops must be in sequential order across threads.
        • Cannot reorder S ops with R or W ops on the same thread
      • The Synchronization operation relevant to this discussion is flush.
  • Be careful when using flush yourself rather than relying on the "behind the scenes" flushes.
• What do compilers do with OpenMP?
  • OpenMP compiler architecture
    • FE (front end) - Parse language, perform checks, build intermediate language (which may be OpenMP specific)
    • ME (middle end) - Transform pragmas to canonical form, Optimize combinations for pragmas
    • BE (back end) - Generate explicitly threaded code, Generate enough information in rest of IL to understand newly created variables
• OpenMP programs and real hardware
  • OpenMP was created with a particular abstract machine or computational model in mind:
    • Multiple processing elements.
    • A shared address space with "equal-time" access for each processor.
    • Multiple light weight processes (threads) managed outside of OpenMP (the OS or some other "third party").
  • But as soon as we added caches to CPUs, the SMP model implied by OpenMP fell apart.
    • Caches... all memory is equal, but some memory is more equal than others.
  • The computational model implied by OpenMP does not match the characteristics of real computers.
    • OpenMP implies SMP, Reality is NUMA (Non-Uniform Memory Access)
    • Programmers must adapt their algorithms to this reality.
    • Do we need to change OpenMP to address this problem:
      • Yes: future memory hierarchies are getting more complex... we must equip programmers to adapt.
      • No: Just expose lots of extra concurrency and the compiler/runtime will use it to hide latencies.
• Case studies: Mapping OpenMP programs onto real hardware:
  • OpenMP on NUMA systems
    • ccNUMA == Cache Coherent Non-Uniform Memory Architecture. Implication: some memory references slower than others.
    • Large ccNUMA machines traditionally use directory-based protocols (e.g., Sun, SGI), but even smaller machines have NUMA characteristics (e.g., hypertransport-based architectures). Likely to see NUMA on-chip soon.
    • Thread affinity means keeping threads close to the data that they access.
      • Bind threads to processors, so the OS doesn't move them
      • Periodically tell the OS to migrate pages to the locality domain (board) with the processor that is executing the thread (nexttouch)
      • For nested parallelism, more complicated: Teams of the same shape that are formed and reformed need to use the same OS threads
      • OpenMP has no way to express any of these requirements
  • OpenMP on clusters
    • Clusters have no hardware shared memory. Emulate shared memory using software mechanisms using various implementation techniques.
    • A Cluster OpenMP program runs on M processes (one per cluster node), each with N pthreads, resulting in MxN OpenMP threads.
    • Cluster OpenMP uses page-based DVSM; all of sharable virtual memory is mapped at the same address in every process
    • Out-of-date pages are recorded at synchronization points and protected using virtual memory hardware
    • Access to out-of-date pages triggers interrupt, causing communication of up-to-date data, updating of local copy of page and removing protection
    • Porting to Cluster OpenMP involves identifying sharable memory, which is memory accessed by more than one OpenMP thread.
    • Presented a case study which showed the speedup with cluster OpenMP was competitive with MPI up to 4 threads, at 64 threads, MPI speedup over 35, Cluster OpenMP only 5
    • Still a lot of tuning to be done. (Probably should stick with MPI for now)
  • OpenMP on GPUs (not a standard, student thesis)
    • Presented case study
      • Reference: Paul Keir, EPCC, Towards an Implementation of OpenMP on the NVIDIA G80 Series Architecture
      • Platform: NVIDIA G80 series (up to 128 processors), Nvidia CUDA language
    • Source-to-source translation
    • Only parallel constructs executed on GPU
    • All data copied in to GPU at entry and out at exit; no data transfer during execution
    • Pointers, stack allocation, and dynamic allocation introduce complications
    • Extensions to language address these complications
      • #pragma gpump accessible(list)
        • Variables declared in sequential code that are accessed in parallel region
        • Similar to Cluster OpenMP sharable
      • #pragma gpump accessible
        • Followed by function definition
        • Insures that a GPU copy of the function is created
      • Special mallocs: gpump_malloc, gpump_realloc, gpump_free
        • Allocate on host and prepare for GPU allocation
    • Translations
      • C code + OpenMP directives => CUDA with runtime calls
      • gpump_copy_to/from_device performs device memory management, copyin/copyout and handles pointer translation
      • gpump_alloc_list_add creates list of variables for copy routines
      • Utility routines for bounds calculation, etc.
  • OpenMP on Cell
    • Case Study: IBM's compiler
  • OpenMP on Intel's heterogeneous many core chips
    • The future of CPUs is clear: General Purpose Cores, Special Purpose HW, Interconnect fabric
      • Mainstream CPUs will be heterogeneous many core chips.
      • Energy considerations alone will force us to move in this direction... for a given task, special purpose HW consumes a little energy compared to what a general purpose CPU would need.
    • Software Implications
      • Special purpose cores suggests a mixture of instruction sets in one CPU.
      • How will software evolve to meet that challenge?
        • Two common approaches (from GPGPU domain):
          • A driver model: embed functions for special purpose hardware in a library exposed to apps through drivers.
          • Write separate sequences of instructions and laboriously by hand mesh with code running on the general purpose cores
        • Solution - Exosequencer architecture
          • Create an extra layer (Exoskeleton) so general "sequencers" (IA) and special purpose exosequencers can coexist in a single virtual shared memory system.
          • Extent page tables so non-IA and IA instruction sets can share memory.
          • Extend OpenMP so an application can specify tasks and teams of threads to run on specific specialized cores.
          • Source: Wang, et. al. "EXOCHI: Architecture and programming environment for a heterogeneous multi-core multithreaded system", PLDI’07.
• References
  • URLs
    • OpenMP architecture review board URL, the primary source of information about OpenMP: http://www.openmp.org
    • OpenMP User’s Group (cOMPunity) URL: http://www.compunity.org
  • Books
    • Parallel programming in OpenMP, Chandra, Rohit, San. : Francisco, Calif Morgan Kaufmann ; London : Harcourt, 2000, ISBN: 1558606718
    • Using OpenMP; Chapman, Jost, Van der Pas; MIT Press (to appear, Oct 2007)
    • Patterns for Parallel Programming, Mattson, Sanders, Massingill, Addison Wesley, 2004
  • Lots of paper references in tutorial notes as well.