BOP: Behavior-oriented Parallelization aka Parallel Programming by Hints

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.

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.

We address these problems with behavior-oriented parallelization (BOP), which provides a suggestion interface for a user to mark possible parallelism in a program and a run-time system to guarante 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.

BOP has the following sister systems

  • FastTrack supports suggestible program optimization
  • D-BOP supports distributed execution of a program with BOP parallelization hints
  • A-BOP uses user inserted access annotation rather than automatic techniques for program monitoring

Research for BOP is supported by National Science Foundation (Contract No. CCF-0963759, CNS-0720796, CNS-0509270, and CCR-0238176 (CAREER Award).

BOP Software

BOP currently supports parallelization in C programs.  It requires a C compiler and runs on 64-bit Linux and Mac OS X.  The build commands require Ruby and Rake.

To request a copy of the system, contact Chen Ding <cding@cs.rochester.edu>.

To access programming manual, point the browser to [bop_dir]/doc/prog_man/index.html

Publications

Conference

"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

"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

People

Compiler group in collaboration with

  • Lei Liu, Dr., and Chuanle Ke at Institute of Computing Technology, Chinese Academy of Sciences
  • Sync group at Rochester led by Michael Scott
  • Chao Zhang at Intel Beijing Lab

Groups: Compiler