Parallelizing a backtracking algorithm in the web browser with Web Workers and WebAssembly

• Daniel T. Rodrigues UPM
• Calebe de Paula Bianchini UPM https://orcid.org/0000-0001-7683-3437

DOI: https://doi.org/10.5753/eradsp.2022.221984

Abstract

The use of modern web browsers shows itself increasingly essential nowadays. Resources like Web Workers are becoming more adopted over the most used browsers of Internet, enabling enhancement of performance in web applications, and by consequence, the execution of more computationally demanding tasks in these browsers. This article explores a technique for task parallelism using Web Workers, presenting as study case an algorithm for crossword generation, executing it in a web browser. The results show even superlinear speedups for the parallel version of the algorithm.

Keywords: Parallel and Distributed Algorithms, Programming Models, Techniques and Methods for Parallelism Extraction

References

Abelson, H., Sussman, G. J., and Sussman, J. (1996). Structure and Interpretation of Computer Programs. MIT Press, 2nd edition.

Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman & Co.

Halic, C. P. S. (2019). Estudo do processo de compilação para webassembly.

Herman, D., Wagner, L., and Zakai, A. (2014). asm.js, http://asmjs.org/spec/latest/.

Herrera, D., Chen, H., Lavoie, E., and Hendren, L. (2018). Webassembly and javascript challenge: Numerical program performance using modern browser technologies and devices. Technical report, University of McGill.

Mozilla (2021). Web workers api, https://developer.mozilla.org/en-us/docs/web/api/web_workers_api.

Rao, V. N. and Kumar, V. (1987). Parallel depth first search. part i. implementation. International Journal of Parallel Programming, 16:479-499.

Rauschmayer, A. (2015). Webassembly: a binary format for the web, https://2ality.com/2015/06/web-assembly.html.

Stats, I. W. (2021). Internet usage statistics, https://internetworldstats.com/stats.htm.

W3C (2021). Web workers. Technical report, World Wide Web Consortium.

Wagner, L. (2013). asm.js in firefox nightly, https://blog.mozilla.org/luke/2013/03/21/asm-js-in-firefox-nightly/.

WCG (2019). Webassembly roadmap, https://webassembly.org/roadmap/.

WHATWG (2021a). Dom living standard, https://dom.spec.whatwg.org/.

WHATWG (2021b). Html living standard, https://html.spec.whatwg.org/.