Parallelism In The SeqAn Library: “Weekly” Reports

Weekly reports about ThesisParallelismInSeqan.

General

• 05/08–05/11:
  • Work on presentation.

• 10/06:
  • Producing Wrong Data Without Doing Anything Obviously Wrong

Review of existing literature and other implementations

• Done:
  • Singler J., Kosnik B., The GNU libstdc++ parallel mode: Software Engineering Considerations
  • Näher S., Schmitt D., A Framework for Multi-Core Implementations of Divide and Conquer Algorithms and its Application to the Convex Hull Problem
  • Singler J., Sanders P., Putze F., MCSTL: The Multi-core Standard Template Library
  • Bentley J., McIlroy M., Engineering a Sort Function
  • Satish N., Harris M., Garland M., Designing Efficient Sorting Algorithms for Manycore GPUs
  • Musser D., Introspective Sorting and Selection Algorithms
  • Myers G., A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming
  • [Tichy, 2009] Tichy, W. and Pankratius, Victor. Lecture Slide: Softwareentwicklung für moderne, parallele Plattformen. SS2009.
  • [Tichy, 2008] Tichy W. et al. Lecture Slides: Multikernrechner und Rechnerbuendel.
  • [Massingil et al., 2000] B. L. Massingill, T. G. Mattson, and B. A. Sanders. Patterns for finding concurrency for parallel application programs. In 7th. Pattern Languages of Programs Conference (PLOP 2000), 2000.
  • [Mytkowicz et al., 2009] T. Mytkowicz, A. Diwan, M. Hauswirth, and P. F. Sweeney. Producing wrong data without doing anything obviously wrong! SIGPLAN Not., 44:265–276, March 2009.

• To do / in progress:
  • [TBB] Intel Threading Building Blocks http://osstbb.intel.com.
  • [Sanders, 2002] P. Sanders. Presenting Data from Experiments in Algorithmics. In Experimental Algorithmics -- From Algorithm Design to Robust and Efficient Software, volume 2547 of LNCS, pages 181-196. Springer, 2002.
  • …

Cleanup of module find

• 04/12:
  • Some thoughts about the interface.
  • Implementation of the testing framework, several generic tests.
  • Implementation of the array-based naive search.

• 04/15:
  • Implementation of the other array-based search algorithms (Horspool, Shift-And/Or, Myers bit vector).

• 04/20:
  • Implementation of iterator-based naive finder

• 04/21:
  • Implementation of iterator-based Horspool and bitap finders.

• 04/22:
  • Implementation of iterator-based Myers bit vector finder.

• 04/27:
  • Gathering a benchmark data set.
  • Sketch of the benchmark code.

• 04/28:
  • First run of the benchmark.
  • Some analyses of differences and significance.

• 04/29:
  • Redid benchmark with repeated runs of same reads.

• 03/30:
  • Several more test runs with different parameters.

• 05/02:
  • Made benchmark tool controllable via command line options.
  • Small bug fix of memory allocation in shift_or class.

• 05/03:
  • Added Linux support to Makefile.
  • Started work on porting SeqAn find code to benchmark.

Review of patterns for parallelization

• 06/01:
  • Literature research ([Massingill et al. 2000])

• 06/04:
  • Literature research (Massingill, Tichy).

• 06/03:
  • Summarization of patterns started.

• 06/07–06/08:
  • Program structures from Tichy added.

• 06/11:
  • Research on OpenMP.
  • Thesis outline.
  • Research on producer/consumer pattern.

• 06/14:
  • Read-up on types of hardware multithreading, and multicores.
  • Data decomposition.

• 06/15:
  • Read-up on out-of-order execution, branch prediction.
  • Data decomposition (Tichy).

• 06/21:
  • Decomposition and data dependency analysis for the finders.
  • Research load-balancing strategies.
  • Research schedule types in OpenMP.

• 06/22:
  • More sophisticated schedule & planning with Manuel.

• 06/25:
  • Read-up on PCAM in [Foster, 1995].

• 06/28:
  • 1D decomposition.

• 07/02:
  • Mail to Näher & Schmitt, regarding details on D&C scheduling.

• 07/05:
  • Illustrations and (pseudo)code interface for 1D decomposition.

• 07/06:
  • Revision of the 1D decomposition interface with different load balancing strategies.

• 07/08:
  • One more conceptual draft of the 1D decomposition interface.

• 07/09:
  • Minor changes to the draft for 1D load balancing interface
  • Extending interface for divide and conquer.

• 07/13:
  • Divide and conquer with static load balancing.

• 07/14:
  • Started implementation of the 1D load balancing (conversion from interface, build system).

• 07/15:
  • Implementation of the 1D load balancing (mainly debugging, incremental testing).

• 07/16:
  • Implementation of the 1D load balancing: without work stealing.

• 07/19:
  • Revised schema for the 1D load balancing.
  • Proof of concept implementation of a parallel finder (missing setBeginPos etc.).
  • Changed concept of Independent1D data spec to carry host.
  • Temporary workaround for the assignment operator problem caused by references.

• 07/20:
  • Change in data specification to store an infix of the string.
  • First version of the OpenMP Hello World example code.

• 07/21:
  • Added an atomic scheduler.
  • Changed the iterator specification and the corresponding functions.
  • Fixed the temporary workaround for the assignment operator.

• 07/22:
  • Extensive documentation of the Hello World example code.
  • Added both atomic and blocked data distribution to the example code.

• 07/23:
  • Rewrite of the iterator test finders from the benchmark to use a new interface that can be parallelized.

• 07/26:
  • Re-implementation of split using iterators.
  • Hoisted split to parent class.

• 07/27:
  • Added a test for a manually parallelized finder using OpenMP.
  • Fixed a bug in the manual OpenMP parallelization.

• 07/28:
  • Added sequential finder to serve as benchmark baseline.
  • Got initial compiling benchmark framework code running.

• 08/01:
  • More benchmark code added.
  • Initial version of a statistical analysis code added.

• 08/08:
  • Using valgrind, fixed memory leak bug in benchmark.

• 08/09:
  • Added command line options to the benchmark appliaction.

• 08/10:
  • Improved graphical display for benchmark results implemented.

• 08/11:
  • Rewrite of framework: DataSpec type split into DataSpec and TaskData.

• 08/13:
  • More changes in the data model to improve modularity.
  • Implemented work stealing for blocked decomposition.

• 08/15:
  • Added ScopeGuard class as a replacement for OpenMP’s indiscriminately locking barrier directive.
  • Simplified the block decomposition code by using the BlockingQueue class.
  • Some improvements to the Makefile.

• 08/16:
  • Made number of threads in benchmark configurable.

• 08/17:
  • Statistics module can now produce comparative table across different thread numbers.
  • Implemented a robust outlier removal method.
  • Some bug fixing.

• 08/23:
  • Separated code into multiple header files to represent structure more closely.

• 08/24:
  • Added preliminary testing and diagnostics code.

• 08/25:
  • Improved the interface of the tabulate function in the statistics module.
  • Added unit testing ode.
  • Fixed a bug in the parallel finder.

• 08/26:
  • Collecting and ordering notes for the thesis write-up.

• 08/27:
  • Added a lot more unit tests.

• 08/28:
  • Unit tests for different string types and the bitap finders added.

• 08/29:
  • Test data added to reproduce the problem in the bitap finders.
  • Fixed the bit shifting finder bug.
  • Wrote proposal for improvement of SeqAn to prevent this bug in other code.

• 08/31:
  • Added blocked load balancing code to benchmark.
  • Improved output of statistics script for similar categories.

• 09/01:
  • Theoretical work on which special cases need to be considered for fuzzy finders.

• 09/02:
  • Fix for small tasks (e.g. from small reference string).
  • Enabled longer reads in benchmark (special case for bitap finders).
  • Special treatment for fuzzy finders implemented.

• 09/03:
  • Extensive commenting of test cases.
  • Code clean-up.

• 09/04:
  • Added LaTeX export to statistics library.

• 09/07:
  • Data generator for benchmark data added.

• 09/11:
  • Improved output of the LaTeX export in the statistics library.

• 09/14:
  • Implemented loading data series across multiple files in statistics library.

• 09/17:
  • Refactored test harness to allow SeqAn shim tests.
  • Implemented the SeqAn shim for the naive finder.

• 09/20:
  • Repaired the old finder interface to make all tests run without failure in sequential mode.

• 09/21:
  • Implemented shims for all SeqAn online finders.
  • Added unit tests for SeqAn shims.
  • Added SeqAn shims to sequential benchmark.

• 09/27:
  • Rewrote parallel benchmark code to accomodate SeqAn finders.
  • Added SeqAn finders to parallel benchmark

• 09/29:
  • Bugfix of improper assignment to infixes in parallel finder assignment operator.

• 09/30:
  • Bugfix of graph output in statistics library.
  • Randomized the work stealing code.

• 10/01:
  • Fixed several bugs related to internal problems of the SeqAn finders (e.g. missing copy constructor)
  • Added more unit tests to cover corner cases.
  • Temporarily disabled the Myers finder since it cannot be copied and thus breaks the tests (#319).

• 10/11:
  • Added a convenience script for running all tests.

• 10/12:
  • Made the workstealing algorithm more efficient.

• … TODO: Complete with notes. …

• 11/01–11/12:
  • Grokking work stealing.
  • Implementation of work stealing, adapted from the MCSTL implementation (no explicit lock-free queue).

• 11/15–11/18:
  • Tests and debugging of work stealing algorithm (interrupted, unfinished)

• 11/19–11/21:
  • Documentation

• 11/21–11/27:
  • Fixed workstealing
  • Adjusted load parameters
  • Benchmark of workstealing scheduler
  • Documentation (TODO: what is a concept, what is an abstract class?)
  • Some write-up