This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Parallelizing Bzip2: A Case Study in Multicore Software Engineering
November/December 2009 (vol. 26 no. 6)
pp. 70-77
Victor Pankratius, University of Karlsruhe
Ali Jannesari, University of Karlsruhe
Walter F. Tichy, University of Karlsruhe
As multicore computers become mainstream and the demand for parallel software increases, software developers need to know which approaches to parallelism work. A case study in which four teams competitively parallelized the Bzip2 compression algorithm illustrates the difficulties that arise when working with a nonnumeric, real application. The sequential code needed significant restructuring before parallelization could begin; restructuring consumed most of the development time. Parallelization at a high level resulted in significant speedups. Low-level, inner-loop parallelizations performed poorly. The case study yielded several other lessons learned.

1. D. Szafron and J. Schaeffer, "An Experiment to Measure the Usability of Parallel Programming Systems," Concurrency: Practice and Experience, vol. 8, no. 2, 1996, pp. 147–166.
2. L. Hochstein et al., "Parallel Programmer Productivity: A Case Study of Novice Parallel Programmers," Proc. 2005 ACM/IEEE Conf. Supercomputing, IEEE CS Press, 2005, p. 35.
3. L. Hochstein and V.R. Basili, "The ASC-Alliance Projects: A Case Study of Large-Scale Parallel Scientific Code Development," Computer, vol. 41, no. 3, 2008, pp. 50–58.
4. N. Werensteijn Smpbzip2, May 2003; http://home.student.utwente.nl/n.werensteijn smpbzip2.
5. Bzip2smp v. 1.0, Dec. 2005; http:/bzip2smp.sourceforge.net.
6. J. Gilchrist Parallel Bzip2 v. 1.0.2, 25 July 2007; http://compression.capbzip2.
7. R.K. Yin, Case Study Research: Design and Methods, 3rd ed., Sage Publications, 2002.
8. V. Pankratius et al., "Parallelizing Bzip2: A Case Study in Multicore Software Engineering, tech. report, IPD Inst., Univ. of Karlsruhe, Apr. 2008; www.multicore-systems.orgresearch.
9. M. Tamm, "Data Compression with the BWT Algorithm," C't, vol. 16, 2000, pp. 194–201 (in German).
10. V. Pankratius et al., "Software Engineering for Multicore Systems: An Experience Report," Proc. 1st Int'l Workshop Multicore Software Eng. (IWMSE 08), ACM Press, 2008, pp. 53–60.
11. S. Akhter and J. Roberts, Multi-Core Programming, Intel Press, 2006.
12. T.G. Mattson et al., Patterns for Parallel Programming, Addison-Wesley, 2004.
13. J.L. Bentley, Writing Efficient Programs, Prentice Hall, 1982.

Index Terms:
Programming techniques, concurrent programming, parallel programming, multicore systems, bzip, concurrency, synchronization, patterns, OpenMP, Posix
Citation:
Victor Pankratius, Ali Jannesari, Walter F. Tichy, "Parallelizing Bzip2: A Case Study in Multicore Software Engineering," IEEE Software, vol. 26, no. 6, pp. 70-77, Nov.-Dec. 2009, doi:10.1109/MS.2009.183
Usage of this product signifies your acceptance of the Terms of Use.