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
- Conference
- ”Safe Parallel Programming using Dynamic Dependence Hints“, Chuanle Ke, Lei Liu, Chao Zhang, Tongxin Bai, Bryan Jacobs, and Chen Ding, in Proceedings of the 25th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, October 2011.
- “Software Behavior Oriented Parallelization“, Chen Ding, Xipeng Shen, Kirk Kelsey, Chris Tice, Ruke Huang, and Chengliang Zhang, in Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego CA, June 2007.
- Poster/position papers
- ”Safe Parallel Programming in an Interpreted Language“, Chen Ding, Brian Gernhardt, Pengcheng Li, and Matthew Hertz, in the First Workshop on the High Performance Scripting Languages, February 2015.
- “Two Examples of Parallel Programming without Concurrency Constructs (PP-CC)“, Chen Ding, in Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, February 2011. (poster paper)
- “Continuous Speculative Program Parallelization in Software“, Chao Zhang, Chen Ding, Xiaoming Gu, Kirk Kelsey, Tongxin Bai, and Xiaobing Feng, in Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, February 2010. (poster paper)
- Technical reports
- Ding, C., “Access Annotation for Safe Speculative Parallelization: Semantics and Support”, TR966, Computer Science Dept., U. Rochester, March 2011. 11.tr966_Access_Annotation_for_Safe_Speculative_Parallelization.pdf
- Zhang, C., Ding, C., Kelsey, K., Bai, T., Gu, X., Feng, X., “A Language of Suggestions for Program Parallelization”, TR948, Computer Science Dept., U. Rochester, July 2009. 09.tr948.A_Language_of_Suggestions_for_Program_Parallelization.pdf
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.
Rochester Programming Systems Reseach 
Results on Wednesday by Ben, Cesar, Sanchoen and Yibo on four machines
https://docs.google.com/document/d/1qkXeVAgK56vHWjxyXntOxC4MxRF4oelftWkvHx1V8eM
Hao and Chencheng walked in to see Ben’s code show. Hao questioned that since programmers are responsible for correct access annotation, what are the reasons that we still need speculative parallelization?
There are two reasons. First, annotating data access is an easier task than parallelizing a program. The BOP approach divides the task of parallelization into two sub-problems. The first problem is data sharing. This is solved by annotation, which marks all accesses to shared data by a PPR task. The understanding is required just for each statement. The second problem is control flow, i.e. the relative order in which the statements in a task are executed and the interleaving in which the statements of different tasks are executed. Compared to data sharing, the control flow problem is more difficult especially the understanding and checking of an interleaved execution. BOP solves the second problem automatically through speculation.
Access annotation can be automated using compiler support, and the cost of annotation can be reduced through profiling and compiler analysis (Tongxin Bai’s dissertation). A programmer can insert annotation manually and can use the knowledge about the program to minimize the cost.
Access annotation can be performed statement by statement and function by function. Annotated modules can be used together without change. Therefore, the manual effort to solve the first problem is cumulative, since the task is modular. In contrast, the task of parallelization is not modular. For example, parallel functions that work individually may not work when they are used together.
The second benefit is speculative parallelism, which is more general than static or dynamic parallelism. With speculation, we can parallelize possibly parallel tasks that we may not know whether they are actually parallel until we finish running them. The dependence hint paper (Ke et al. OOPSLA 2011) gives several examples that cannot be parallelized without speculation.
The project of Ruby BOP is a test of the BOP approach and how far these two benefits can take us.