Putting Heterogeneous High-Performance Computing at the Fingertips of Domain Experts
Organized by:
Wim Vanderbauwhede, University of Glasgow, UK
Sven-Bodo Scholz, Heriot-Watt University, Scotland
Tetsuya Takemi, Kyoto University, Japan
NII Shonan Meeting@ Shonan Village Center, November 17-20, 2015
http://plg.uwaterloo.ca/~olhotak/cdp_2015
RECU:Rochester Elastic Cache Utility
Chencheng Ye1,2, Jack Brock1, Chen Ding1, Hai Jin1 – 1University of Rochester, 2Huazhong University of Science
See presentation slides at https://roclocality.org/wp-content/uploads/2015/11/recu-cdp15.pdf
RubyBOP: Safe Parallel Ruby
Chen Ding, Jacob Bisnett, Benjamin O’Halloran, Cesar De Hoyos, Brian Gernhardt – University of Rochester
Data-centric Combinatorial Optimization of Parallel Code
Hao Luo, Guoyang Chen, Pengcheng Li, Chen Ding, Xipeng Shen – University of Rochester
Dragon Boat Fusion Cuisine 凱龍船
Behavior-oriented parallelization (BOP) provides a suggestion interface for a user to mark possible parallelism and run-time support to guarante correctness and efficient execution whether the hints are correct or not. It enables program parallelization based on partial information and is useful for incrementally parallelizing a program or streamlining it for common uses.
This page contains a tutorial to introduce RubyBOP to a CS undergraduate student who will become a developer of the system.
Introduction
Modern programs often have dynamic parallelism at the high level but are hard to parallelize because of complex code such as the use of bit-level operations, unrestricted pointers, exception handling, custom memory management, and third-party libraries. Moreover, many programs have input-dependent behavior where both the degree and the granularity of parallelism are not guaranteed or even predictable. For manual parallelization, the complexity and the uncertain performance gain do little to warrant the investment of time and the risk of error.
Behavior-oriented parallelization (BOP) addresses these problems by providing a suggestion interface for a user to mark possible parallelism in a program and a run-time system to guarantee correctness and efficiency. If the hints are correct, the program will run in parallel. If the hints are not correct or the suggested parallelism is too fine-grained, the program still finishes as fast as sequential execution. In both cases, the program produces the same output as the sequential execution without hints. BOP is based on frequent, input-dependent behavior rather than definite behavior. It allows program parallelization based on partial information and is useful for incrementally parallelizing a program or streamlining it for common uses.
Paper Reading
Example (Unsafe) OpenMP Programming
Use the add example. It computes on the N elements of an array and adds the results together. It is parallelized in OpenMP. Use GCC to build it and run it in parallel. The executable has two parameters: the number of elements to compute (in millions) and the number of blocks (to divide the elements into and compute in parallel). Change these two parameters and the number of OMP threads. Observe the performance and the result. Do you see a non-deterministic error?
C-BOP Manual
RubyBOP source code is a Mercurial repository. Download it from cycle1.cs.rochester.edu://p/compiler/hg-repos/rubybop/ Here we refer to the root as [repos].
Read the programming manual of C-BOP. C-BOP is the subdirectory [repos]/cbop/. It is a C library that a C program can call to parallel the program.
A description of the library API calls is given in the programming manual in [repos]/cbop/prog_man/. Use a web browser to open the base manual page index.html. The information may be dated or missing. We will update and improve the document as we go.
Write the First C-BOP Program
Use the programming manual and the C-BOP source code to parallel the add program using BOP programming hints.
Ruby C Extension
Use the most recent Ruby release (2.2). Add a new trivial class in C and a public method in the new class to return some number or string. To test your extension, write a Ruby program, standalone or in the interpreter, create an object of this new single-method class and call the method to check the results.
Wednesday, Pengcheng Li “Memory management optimization using all-window liveness”
Thurday, Jacob Brock, “Locality theory in shared cache and beyond”
Friday, Rahman Lavaee, “Hierarchical memory layout: theory and optimization”
Background. Multicore applications share cache. Composable analysis is needed to see how programs interact with dynamic, usage based cache management. Miss ratio/rate doesn’t compose.
Xiaoya’s work. Footprint composes but assumes uniform interleaving.
Jake et al. Common logical time in CCGrid 2015 handles non-equal length component traces, eg. one thread accesses memory 100 times more frequent than another thread. But we still assume uniform interleaving.
Hao repots several advances.
Time-preserving decomposition
Now we can compose threads that have any type of interleaving.
Cache associativity modeling
The Smith method is the dominant solution for nearly 40 years but assumes equal probability of access in all cache sets. Hao’s new solution removes this assumption and uses time-preserving decomposition to also allow non uniform interleaving.
GPU texture cache
Modeled as a sector cache to give composable performance for all cache sizes and associativity as for normal cache.
New studies
Space efficient algorithms for shared footprint analysis.
Possibly memcached or io traces.
Static locality analysis.
Locality aware scheduling
At the 2015 University Day organized in the Systems workshop organized by Wang Chen at IBM Toronto, José Nelson Amaral of University Alberta gave a talk explaining the following studies. The problem is estimating the size of a tree by traversing some but not all nodes.
“Mathematics of computation” by Donald Knuth in American Mathematical Society 1975 gave a sampling solution: Go down random tree paths to the leaves, and take the average of the sampled sub-tree size as the actual average sub-tree size.
Heuristic sampling by Peng Chen in 1992 takes samples but reuses the past results. It uses the term Stratification but the technique sounds like memoization. An example is the Fibonacci series.
The Alberta work is to estimate the number of leaf tasks in a recursive fork-join (Cilk) program. The solution is a complete exploration of the top of the tree until it has the nodes 10 times the number of processors. Then it uses the Knuth method to estimate the size of a sub-tree.
Another example is 3×3 puzzle, 181,440 states and 4×4, more than 10^13 states.
Currently GPU has a thread-centric model, where a task is the work specified by kernel(thread block ID). There two important questions: When to schedule, which software can control through persistent threads, and where to schedule, which is the problem studied in this paper. It groups tasks that share data.
Task co-location is important for locality and for resource utilization. Improper concurrent execution of kernels leads to resource conflicts, e.g. too much shared memory/register demand so another kernel cannot be run.
The solution is SM centric. A worker is started by hardware to run tasks from a queue, controlled by software. The paper has a scheme to start the same number of workers on each SM. In comparison, the past work on persistent threads can only run one worker per SM.
For irregular application, the paper uses GPU to parallel partition the data/tasks into locality groups.
Measured the effect in Co-run ANTT speedup = mean( default Ti / opt Ti), (average normalized turnaround time) and Co-run throughput.
Adriaens+:HPCA12’s study of co-run kernels.
Modern hardware counters are used to find program instructions that cause most cache misses for example, and the way is to measure how many times a counter overflow happens on a particular instruction. However, when an overflow happens as an interrupt, the exact instruction causing the interrupt may be incorrect, a problem that Intel calls a “skid”.
The solution is to consider surrounding instructions as the set of probabilities. Then the overlap of these probabilities will show the most likely instruction.
The problem and solution are hardware dependent.
To model performance, it is necessary to quantify the tradeoff between computation and communication, in particular, between the processing throughput and the data transfer bandwidth. The classic model is the notion called balance by Callahan, Cocke and Kennedy [JPDC 1988]. A balance is the ratio between the peak computing throughput and the peak data transfer bandwidth. It is known in the multicore era as the roofline model [Williams et al. CACM09] and has been known since earlier times as byte per flop.
If a machine is not balanced because the memory is not fast enough, a processor can achieve at most a fraction of its peak performance.
Both a program and a machine have balance. Program balance is the amount of the memory transfer, including both reads (misses) and writes (writebacks) that the program needs for each computation operation; machine balance is the amount of memory transfer that the machine provides for each machine operation at the peak throughput. Specifically, for a scientific program, the program balance is the average number of bytes that must be transferred per floating-point operation (flop) in the program; the machine balance is the number of bytes the machine can transfer per flop in its peak flop rate.
On machines with multiple levels of intermediate memory, the balance includes the data transfer between all adjacent levels [Ding and Kennedy, IPDPS00].
The paper tests the performance of two simple loops on SGI Origin2000 and HP/Convex Exemplar. The first loop takes twice as long because it writes the array to memory and consequently consumes twice as much memory bandwidth.
double precision A[2000000]
for i=1 to N
A[i] = A[i]+0.4
end for
for i=1 to N
sum = sum+A[i]
end for
The paper shows the balance on an SGI Origin2000 machine. For example, convolution requires transferring 6.4 bytes between the level-one cache (L1) and registers, 5.1 bytes between L1 and the level-two cache (L2), and 5.2 bytes between L2 and memory. For each flop at its peak performance, the machine can transfer 4 bytes between registers and cache, 4 bytes between L1 and L2, but merely 0.8 bytes between cache and memory. The greatest bottleneck is the memory bandwidth, the ratio 0.8/5.2 = 0.15 means that the CPU utilization is at most 15%. Note that prefetching cannot alleviate the bandwidth problem because it does not reduce the aggregate volume of data transfer from memory. In fact, it often aggravates the bandwidth problem by generating unnecessary prefetches.
Our earlier work has studied loop fusion and array regrouping [Ding and Kennedy, JPDC 2004] and run-time computation reordering and consecutive packing (data reordering) [Ding and Kennedy, PLDI 1999] to reduce the total bandwidth requirement of a program. There are excellent follow up studies, which would be good to review later.
Foreword/Preface. The book is partly to explain the intuition and reasoning behind the sophisticated mathematical models. 1994 survey of parallel job scheduling included 76 systems and 638 references. Practically every paper showed it was better than other schemes. “If the workload is wrong, the results will be wrong too.” The workload is the experimental basis; otherwise, a study is based on assumptions rather than measurements, and mathematical techniques are misapplied.
Introduction. Three factors of performance: system design, implementation, and its workload. A trivial example is a sorting algorithm. Three problems: job scheduling by size (scaling), processor allocation (distribution), and load balancing (inference). Workload classification. Workload modeling and its many uses in performance evaluation. Modeling is to generalize to transcend specific observation and recording and to simplify to have as few parameters as possible. Descriptive models mimic the phenomena in observation. Generative models capture the process in which the workload is brought about.
6.2 Spatial and Temporal Locality
Locality is ubiquitous [Denning CACM 2005]. 8 types of locality in workloads. Access locality in (1) addresses and pages, (2) file reuse in server, (3) single file access, (4) database and key-value store. Communication locality (5). Repetition in (6) network addresses, (7) document retrieval, and (8) function parameters and memory values. The section runs from page 215 to 231.
6.2.1 Definitions.
Denning’s principle of locality has 3 features: non-uniform reference, slow changing, correlation between immediate past and future. “Not a precise and measurable definition”
Spatial locality definition is similar to our reference affinity. A locality is a group of pages. Spatial regularity. Popularity [Jin & Bestavros 2000]. (The formal connection between popularity and locality will be established in the new category theory, manuscript in preparation)
6.2.2 Statistical Measures of Locality. Access probability. Frequent substrings. “attach a numerical value that represents the degree of locality”
6.2.3 The Stack Distance. (Should be called LRU stack distance or reuse distance) Comparison of reuse distance distribution for an actual and a random trace. Inter-reference distance [Almasi+ MSPC] “The most common way to quantify locality is not be statistical measures, but by its effect … by means of a simulation … The stack is maintained using a move-to-front discipline.”
Later sections in 6.2. Entropy measure of popularity. IRM. Pareto distribution of LRU distances. Markov model of phase transition, limiting distribution (stochastic assumption in [Denning & Schwartz CACM 1972]). Fractal model (idea also used in the IPDPS 2012 paper by Zhibin Yu).
9.2 Desktop and Workstation Workloads
Many interesting ideas with references. Benchmarks for different application areas: CPU, parallel, multimedia and games. The concept of “predicability”. Load balancing based on Pareto run-time distribution.
Koller et al. 2010 [ref 410 in Feitelson book] The flood rate: flood the cache with memory lines not reused before eviction (not in its reuse set), so it takes space / applies pressure to peer applications. The reuse rate: the rate of access to its reuse set. If the reuse rate is lower than the flood rate, its reuse set tends to be evicted. The wastage: the space used for non reusable data.
Rochester Programming Systems Reseach 
